aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjimblandy <jimblandy@4c0a9323-5329-0410-9bdc-e9ce6186880e>2010-02-05 17:51:35 +0000
committerjimblandy <jimblandy@4c0a9323-5329-0410-9bdc-e9ce6186880e>2010-02-05 17:51:35 +0000
commit89e07bf2c75e3a91abddde3219e1108c75059985 (patch)
tree36a2476332a7439ed3e5d52fe64a220e0fc901c4
parentBreakpad x86 Stack Walker: Pass "out" parameters by address, not reference. (diff)
downloadbreakpad-89e07bf2c75e3a91abddde3219e1108c75059985.tar.xz
Breakpad processor: Support evaluating a postfix expression to produce a value.
This adds an EvaluateForValue member function to PostfixEvaluator, and along with appropriate unit tests. a=jimblandy, r=nealsid git-svn-id: http://google-breakpad.googlecode.com/svn/trunk@511 4c0a9323-5329-0410-9bdc-e9ce6186880e
-rw-r--r--src/processor/postfix_evaluator-inl.h47
-rw-r--r--src/processor/postfix_evaluator.h28
-rw-r--r--src/processor/postfix_evaluator_unittest.cc90
3 files changed, 151 insertions, 14 deletions
diff --git a/src/processor/postfix_evaluator-inl.h b/src/processor/postfix_evaluator-inl.h
index b08cd182..3d2a7d14 100644
--- a/src/processor/postfix_evaluator-inl.h
+++ b/src/processor/postfix_evaluator-inl.h
@@ -1,3 +1,5 @@
+// -*- mode: c++ -*-
+
// Copyright (c) 2006, Google Inc.
// All rights reserved.
//
@@ -64,11 +66,9 @@ class AutoStackClearer {
template<typename ValueType>
-bool PostfixEvaluator<ValueType>::Evaluate(const string &expression,
- DictionaryValidityType *assigned) {
- // Ensure that the stack is cleared before returning.
- AutoStackClearer clearer(&stack_);
-
+bool PostfixEvaluator<ValueType>::EvaluateInternal(
+ const string &expression,
+ DictionaryValidityType *assigned) {
// Tokenize, splitting on whitespace.
istringstream stream(expression);
string token;
@@ -194,13 +194,46 @@ bool PostfixEvaluator<ValueType>::Evaluate(const string &expression,
}
}
+ return true;
+}
+
+template<typename ValueType>
+bool PostfixEvaluator<ValueType>::Evaluate(const string &expression,
+ DictionaryValidityType *assigned) {
+ // Ensure that the stack is cleared before returning.
+ AutoStackClearer clearer(&stack_);
+
+ if (!EvaluateInternal(expression, assigned))
+ return false;
+
// If there's anything left on the stack, it indicates incomplete execution.
// This is a failure case. If the stack is empty, evalution was complete
// and successful.
- BPLOG_IF(ERROR, !stack_.empty()) << "Incomplete execution: " << expression;
- return stack_.empty();
+ if (stack_.empty())
+ return true;
+
+ BPLOG(ERROR) << "Incomplete execution: " << expression;
+ return false;
}
+template<typename ValueType>
+bool PostfixEvaluator<ValueType>::EvaluateForValue(const string &expression,
+ ValueType *result) {
+ // Ensure that the stack is cleared before returning.
+ AutoStackClearer clearer(&stack_);
+
+ if (!EvaluateInternal(expression, NULL))
+ return false;
+
+ // A successful execution should leave exactly one value on the stack.
+ if (stack_.size() != 1) {
+ BPLOG(ERROR) << "Expression yielded bad number of results: "
+ << "'" << expression << "'";
+ return false;
+ }
+
+ return PopValue(result);
+}
template<typename ValueType>
typename PostfixEvaluator<ValueType>::PopResult
diff --git a/src/processor/postfix_evaluator.h b/src/processor/postfix_evaluator.h
index d70bcaa0..a8979051 100644
--- a/src/processor/postfix_evaluator.h
+++ b/src/processor/postfix_evaluator.h
@@ -1,3 +1,5 @@
+// -*- mode: C++ -*-
+
// Copyright (c) 2010, Google Inc.
// All rights reserved.
//
@@ -93,15 +95,21 @@ class PostfixEvaluator {
PostfixEvaluator(DictionaryType *dictionary, const MemoryRegion *memory)
: dictionary_(dictionary), memory_(memory), stack_() {}
- // Evaluate the expression. The results of execution will be stored
- // in one (or more) variables in the dictionary. Returns false if any
- // failures occure during execution, leaving variables in the dictionary
- // in an indeterminate state. If assigned is non-NULL, any keys set in
- // the dictionary as a result of evaluation will also be set to true in
- // assigned, providing a way to determine if an expression modifies any
- // of its input variables.
+ // Evaluate the expression, starting with an empty stack. The results of
+ // execution will be stored in one (or more) variables in the dictionary.
+ // Returns false if any failures occur during execution, leaving
+ // variables in the dictionary in an indeterminate state. If assigned is
+ // non-NULL, any keys set in the dictionary as a result of evaluation
+ // will also be set to true in assigned, providing a way to determine if
+ // an expression modifies any of its input variables.
bool Evaluate(const string &expression, DictionaryValidityType *assigned);
+ // Like Evaluate, but provides the value left on the stack to the
+ // caller. If evaluation succeeds and leaves exactly one value on
+ // the stack, pop that value, store it in *result, and return true.
+ // Otherwise, return false.
+ bool EvaluateForValue(const string &expression, ValueType *result);
+
DictionaryType* dictionary() const { return dictionary_; }
// Reset the dictionary. PostfixEvaluator does not take ownership.
@@ -137,6 +145,12 @@ class PostfixEvaluator {
// Pushes a new value onto the stack.
void PushValue(const ValueType &value);
+ // Evaluate expression, updating *assigned if it is non-zero. Return
+ // true if evaluation completes successfully. Do not clear the stack
+ // upon successful evaluation.
+ bool EvaluateInternal(const string &expression,
+ DictionaryValidityType *assigned);
+
// The dictionary mapping constant and variable identifiers (strings) to
// values. Keys beginning with '$' are treated as variable names, and
// PostfixEvaluator is free to create and modify these keys. Weak pointer.
diff --git a/src/processor/postfix_evaluator_unittest.cc b/src/processor/postfix_evaluator_unittest.cc
index 73aec468..0e6f0577 100644
--- a/src/processor/postfix_evaluator_unittest.cc
+++ b/src/processor/postfix_evaluator_unittest.cc
@@ -103,6 +103,18 @@ struct EvaluateTestSet {
};
+struct EvaluateForValueTest {
+ // Expression passed to PostfixEvaluator::Evaluate.
+ const string expression;
+
+ // True if the expression is expected to be evaluable, false if evaluation
+ // is expected to fail.
+ bool evaluable;
+
+ // If evaluable, the value we expect it to yield.
+ unsigned int value;
+};
+
static bool RunTests() {
// The first test set checks the basic operations and failure modes.
PostfixEvaluator<unsigned int>::DictionaryType dictionary_0;
@@ -289,6 +301,84 @@ static bool RunTests() {
}
}
+ // EvaluateForValue tests.
+ PostfixEvaluator<unsigned int>::DictionaryType dictionary_2;
+ dictionary_2["$ebp"] = 0xbfff0010;
+ dictionary_2["$eip"] = 0x10000000;
+ dictionary_2["$esp"] = 0xbfff0000;
+ dictionary_2[".cbSavedRegs"] = 4;
+ dictionary_2[".cbParams"] = 4;
+ dictionary_2[".raSearchStart"] = 0xbfff0020;
+ const EvaluateForValueTest evaluate_for_value_tests_2[] = {
+ { "28907223", true, 28907223 }, // simple constant
+ { "89854293 40010015 +", true, 89854293 + 40010015 }, // arithmetic
+ { "-870245 8769343 +", true, 7899098 }, // negative constants
+ { "$ebp $esp - $eip +", true, 0x10000010 }, // variable references
+ { "18929794 34015074", false, 0 }, // too many values
+ { "$ebp $ebp 4 - =", false, 0 }, // too few values
+ { "$new $eip = $new", true, 0x10000000 }, // make new variable
+ { "$new 4 +", true, 0x10000004 }, // see prior assignments
+ { ".cfa 42 = 10", false, 0 } // can't set constants
+ };
+ const int evaluate_for_value_tests_2_size
+ = (sizeof (evaluate_for_value_tests_2)
+ / sizeof (evaluate_for_value_tests_2[0]));
+ map<string, unsigned int> validate_data_2;
+ validate_data_2["$eip"] = 0x10000000;
+ validate_data_2["$ebp"] = 0xbfff000c;
+ validate_data_2["$esp"] = 0xbfff0000;
+ validate_data_2["$new"] = 0x10000000;
+ validate_data_2[".cbSavedRegs"] = 4;
+ validate_data_2[".cbParams"] = 4;
+ validate_data_2[".raSearchStart"] = 0xbfff0020;
+
+ postfix_evaluator.set_dictionary(&dictionary_2);
+ for (int i = 0; i < evaluate_for_value_tests_2_size; i++) {
+ const EvaluateForValueTest *test = &evaluate_for_value_tests_2[i];
+ unsigned int result;
+ if (postfix_evaluator.EvaluateForValue(test->expression, &result)
+ != test->evaluable) {
+ fprintf(stderr, "FAIL: evaluate for value test %d, "
+ "expected evaluation to %s, but it %s\n",
+ i, test->evaluable ? "succeed" : "fail",
+ test->evaluable ? "failed" : "succeeded");
+ return false;
+ }
+ if (test->evaluable && result != test->value) {
+ fprintf(stderr, "FAIL: evaluate for value test %d, "
+ "expected value to be 0x%x, but it was 0x%x\n",
+ i, test->value, result);
+ return false;
+ }
+ }
+
+ for (map<string, unsigned int>::iterator v = validate_data_2.begin();
+ v != validate_data_2.end(); v++) {
+ map<string, unsigned int>::iterator a = dictionary_2.find(v->first);
+ if (a == dictionary_2.end()) {
+ fprintf(stderr, "FAIL: evaluate for value dictionary check: "
+ "expected dict[\"%s\"] to be 0x%x, but it was unset\n",
+ v->first.c_str(), v->second);
+ return false;
+ } else if (a->second != v->second) {
+ fprintf(stderr, "FAIL: evaluate for value dictionary check: "
+ "expected dict[\"%s\"] to be 0x%x, but it was 0x%x\n",
+ v->first.c_str(), v->second, a->second);
+ return false;
+ }
+ dictionary_2.erase(a);
+ }
+
+ map<string, unsigned int>::iterator remaining = dictionary_2.begin();
+ if (remaining != dictionary_2.end()) {
+ fprintf(stderr, "FAIL: evaluation of test expressions put unexpected "
+ "values in dictionary:\n");
+ for (; remaining != dictionary_2.end(); remaining++)
+ fprintf(stderr, " dict[\"%s\"] == 0x%x\n",
+ remaining->first.c_str(), remaining->second);
+ return false;
+ }
+
return true;
}