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. PostfixEvaluator(DictionaryType * dictionary,const MemoryRegion * memory)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 dictionary()115 DictionaryType* dictionary() const { return dictionary_; } 116 117 // Reset the dictionary. PostfixEvaluator does not take ownership. set_dictionary(DictionaryType * dictionary)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__ 179