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