1  // -*- mode: C++ -*-
  2  
  3  // Copyright 2010 Google LLC
  4  //
  5  // Redistribution and use in source and binary forms, with or without
  6  // modification, are permitted provided that the following conditions are
  7  // met:
  8  //
  9  //     * Redistributions of source code must retain the above copyright
 10  // notice, this list of conditions and the following disclaimer.
 11  //     * Redistributions in binary form must reproduce the above
 12  // copyright notice, this list of conditions and the following disclaimer
 13  // in the documentation and/or other materials provided with the
 14  // distribution.
 15  //     * Neither the name of Google LLC nor the names of its
 16  // contributors may be used to endorse or promote products derived from
 17  // this software without specific prior written permission.
 18  //
 19  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 20  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 21  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 22  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 23  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 24  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 25  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 26  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 27  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 28  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 29  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 30  
 31  // postfix_evaluator.h: Postfix (reverse Polish) notation expression evaluator.
 32  //
 33  // PostfixEvaluator evaluates an expression, using the expression itself
 34  // in postfix (reverse Polish) notation and a dictionary mapping constants
 35  // and variables to their values.  The evaluator supports standard
 36  // arithmetic operations, assignment into variables, and when an optional
 37  // MemoryRange is provided, dereferencing.  (Any unary key-to-value operation
 38  // may be used with a MemoryRange implementation that returns the appropriate
 39  // values, but PostfixEvaluator was written with dereferencing in mind.)
 40  //
 41  // The expression language is simple.  Expressions are supplied as strings,
 42  // with operands and operators delimited by whitespace.  Operands may be
 43  // either literal values suitable for ValueType, or constants or variables,
 44  // which reference the dictionary.  The supported binary operators are +
 45  // (addition), - (subtraction), * (multiplication), / (quotient of division),
 46  // % (modulus of division), and @ (data alignment). The alignment operator (@)
 47  // accepts a value and an alignment size, and produces a result that is a
 48  // multiple of the alignment size by truncating the input value.
 49  // The unary ^ (dereference) operator is also provided.  These operators
 50  // allow any operand to be either a literal value, constant, or variable.
 51  // Assignment (=) of any type of operand into a variable is also supported.
 52  //
 53  // The dictionary is provided as a map with string keys.  Keys beginning
 54  // with the '$' character are treated as variables.  All other keys are
 55  // treated as constants.  Any results must be assigned into variables in the
 56  // dictionary.  These variables do not need to exist prior to calling
 57  // Evaluate, unless used in an expression prior to being assigned to.  The
 58  // internal stack state is not made available after evaluation, and any
 59  // values remaining on the stack are treated as evidence of incomplete
 60  // execution and cause the evaluator to indicate failure.
 61  //
 62  // PostfixEvaluator is intended to support evaluation of "program strings"
 63  // obtained from MSVC frame data debugging information in pdb files as
 64  // returned by the DIA APIs.
 65  //
 66  // Author: Mark Mentovai
 67  
 68  #ifndef PROCESSOR_POSTFIX_EVALUATOR_H__
 69  #define PROCESSOR_POSTFIX_EVALUATOR_H__
 70  
 71  
 72  #include <map>
 73  #include <string>
 74  #include <vector>
 75  
 76  #include "common/using_std_string.h"
 77  
 78  namespace google_breakpad {
 79  
 80  using std::map;
 81  using std::vector;
 82  
 83  class MemoryRegion;
 84  
 85  template<typename ValueType>
 86  class PostfixEvaluator {
 87   public:
 88    typedef map<string, ValueType> DictionaryType;
 89    typedef map<string, bool> DictionaryValidityType;
 90  
 91    // Create a PostfixEvaluator object that may be used (with Evaluate) on
 92    // one or more expressions.  PostfixEvaluator does not take ownership of
 93    // either argument.  |memory| may be NULL, in which case dereferencing
 94    // (^) will not be supported.  |dictionary| may be NULL, but evaluation
 95    // will fail in that case unless set_dictionary is used before calling
 96    // Evaluate.
 97    PostfixEvaluator(DictionaryType* dictionary, const MemoryRegion* memory)
 98        : dictionary_(dictionary), memory_(memory), stack_() {}
 99  
100    // Evaluate the expression, starting with an empty stack. The results of
101    // execution will be stored in one (or more) variables in the dictionary.
102    // Returns false if any failures occur during execution, leaving
103    // variables in the dictionary in an indeterminate state. If assigned is
104    // non-NULL, any keys set in the dictionary as a result of evaluation
105    // will also be set to true in assigned, providing a way to determine if
106    // an expression modifies any of its input variables.
107    bool Evaluate(const string& expression, DictionaryValidityType* assigned);
108  
109    // Like Evaluate, but provides the value left on the stack to the
110    // caller. If evaluation succeeds and leaves exactly one value on
111    // the stack, pop that value, store it in *result, and return true.
112    // Otherwise, return false.
113    bool EvaluateForValue(const string& expression, ValueType* result);
114  
115    DictionaryType* dictionary() const { return dictionary_; }
116  
117    // Reset the dictionary.  PostfixEvaluator does not take ownership.
118    void set_dictionary(DictionaryType* dictionary) {dictionary_ = dictionary; }
119  
120   private:
121    // Return values for PopValueOrIdentifier
122    enum PopResult {
123      POP_RESULT_FAIL = 0,
124      POP_RESULT_VALUE,
125      POP_RESULT_IDENTIFIER
126    };
127  
128    // Retrieves the topmost literal value, constant, or variable from the
129    // stack.  Returns POP_RESULT_VALUE if the topmost entry is a literal
130    // value, and sets |value| accordingly.  Returns POP_RESULT_IDENTIFIER
131    // if the topmost entry is a constant or variable identifier, and sets
132    // |identifier| accordingly.  Returns POP_RESULT_FAIL on failure, such
133    // as when the stack is empty.
134    PopResult PopValueOrIdentifier(ValueType* value, string* identifier);
135  
136    // Retrieves the topmost value on the stack.  If the topmost entry is
137    // an identifier, the dictionary is queried for the identifier's value.
138    // Returns false on failure, such as when the stack is empty or when
139    // a nonexistent identifier is named.
140    bool PopValue(ValueType* value);
141  
142    // Retrieves the top two values on the stack, in the style of PopValue.
143    // value2 is popped before value1, so that value1 corresponds to the
144    // entry that was pushed prior to value2.  Returns false on failure.
145    bool PopValues(ValueType* value1, ValueType* value2);
146  
147    // Pushes a new value onto the stack.
148    void PushValue(const ValueType& value);
149  
150    // Evaluate expression, updating *assigned if it is non-zero. Return
151    // true if evaluation completes successfully. Do not clear the stack
152    // upon successful evaluation.
153    bool EvaluateInternal(const string& expression,
154                          DictionaryValidityType* assigned);
155  
156    bool EvaluateToken(const string& token,
157                       const string& expression,
158                       DictionaryValidityType* assigned);
159  
160    // The dictionary mapping constant and variable identifiers (strings) to
161    // values.  Keys beginning with '$' are treated as variable names, and
162    // PostfixEvaluator is free to create and modify these keys.  Weak pointer.
163    DictionaryType* dictionary_;
164  
165    // If non-NULL, the MemoryRegion used for dereference (^) operations.
166    // If NULL, dereferencing is unsupported and will fail.  Weak pointer.
167    const MemoryRegion* memory_;
168  
169    // The stack contains state information as execution progresses.  Values
170    // are pushed on to it as the expression string is read and as operations
171    // yield values; values are popped when used as operands to operators.
172    vector<string> stack_;
173  };
174  
175  }  // namespace google_breakpad
176  
177  
178  #endif  // PROCESSOR_POSTFIX_EVALUATOR_H__