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

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;
 }