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 79namespace google_breakpad { 80 81using std::map; 82using std::vector; 83 84class MemoryRegion; 85 86template<typename ValueType> 87class 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. 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 116 DictionaryType* dictionary() const { return dictionary_; } 117 118 // Reset the dictionary. PostfixEvaluator does not take ownership. 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