michael@0: // -*- mode: C++ -*- michael@0: michael@0: // Copyright (c) 2010 Google Inc. michael@0: // All rights reserved. michael@0: // michael@0: // Redistribution and use in source and binary forms, with or without michael@0: // modification, are permitted provided that the following conditions are michael@0: // met: michael@0: // michael@0: // * Redistributions of source code must retain the above copyright michael@0: // notice, this list of conditions and the following disclaimer. michael@0: // * Redistributions in binary form must reproduce the above michael@0: // copyright notice, this list of conditions and the following disclaimer michael@0: // in the documentation and/or other materials provided with the michael@0: // distribution. michael@0: // * Neither the name of Google Inc. nor the names of its michael@0: // contributors may be used to endorse or promote products derived from michael@0: // this software without specific prior written permission. michael@0: // michael@0: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS michael@0: // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT michael@0: // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR michael@0: // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT michael@0: // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, michael@0: // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT michael@0: // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, michael@0: // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY michael@0: // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT michael@0: // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE michael@0: // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. michael@0: michael@0: // postfix_evaluator.h: Postfix (reverse Polish) notation expression evaluator. michael@0: // michael@0: // PostfixEvaluator evaluates an expression, using the expression itself michael@0: // in postfix (reverse Polish) notation and a dictionary mapping constants michael@0: // and variables to their values. The evaluator supports standard michael@0: // arithmetic operations, assignment into variables, and when an optional michael@0: // MemoryRange is provided, dereferencing. (Any unary key-to-value operation michael@0: // may be used with a MemoryRange implementation that returns the appropriate michael@0: // values, but PostfixEvaluator was written with dereferencing in mind.) michael@0: // michael@0: // The expression language is simple. Expressions are supplied as strings, michael@0: // with operands and operators delimited by whitespace. Operands may be michael@0: // either literal values suitable for ValueType, or constants or variables, michael@0: // which reference the dictionary. The supported binary operators are + michael@0: // (addition), - (subtraction), * (multiplication), / (quotient of division), michael@0: // % (modulus of division), and @ (data alignment). The alignment operator (@) michael@0: // accepts a value and an alignment size, and produces a result that is a michael@0: // multiple of the alignment size by truncating the input value. michael@0: // The unary ^ (dereference) operator is also provided. These operators michael@0: // allow any operand to be either a literal value, constant, or variable. michael@0: // Assignment (=) of any type of operand into a variable is also supported. michael@0: // michael@0: // The dictionary is provided as a map with string keys. Keys beginning michael@0: // with the '$' character are treated as variables. All other keys are michael@0: // treated as constants. Any results must be assigned into variables in the michael@0: // dictionary. These variables do not need to exist prior to calling michael@0: // Evaluate, unless used in an expression prior to being assigned to. The michael@0: // internal stack state is not made available after evaluation, and any michael@0: // values remaining on the stack are treated as evidence of incomplete michael@0: // execution and cause the evaluator to indicate failure. michael@0: // michael@0: // PostfixEvaluator is intended to support evaluation of "program strings" michael@0: // obtained from MSVC frame data debugging information in pdb files as michael@0: // returned by the DIA APIs. michael@0: // michael@0: // Author: Mark Mentovai michael@0: michael@0: #ifndef PROCESSOR_POSTFIX_EVALUATOR_H__ michael@0: #define PROCESSOR_POSTFIX_EVALUATOR_H__ michael@0: michael@0: michael@0: #include michael@0: #include michael@0: #include michael@0: michael@0: #include "common/using_std_string.h" michael@0: #include "common/unique_string.h" michael@0: #include "common/module.h" michael@0: michael@0: namespace google_breakpad { michael@0: michael@0: using std::map; michael@0: using std::vector; michael@0: michael@0: class MemoryRegion; michael@0: michael@0: // A union type for elements in the postfix evaluator's stack. michael@0: template michael@0: class StackElem { michael@0: public: michael@0: StackElem(ValueType val) { isValue = true; u.val = val; } michael@0: StackElem(const UniqueString* ustr) { isValue = false; u.ustr = ustr; } michael@0: bool isValue; michael@0: union { ValueType val; const UniqueString* ustr; } u; michael@0: }; michael@0: michael@0: template michael@0: class PostfixEvaluator { michael@0: public: michael@0: typedef UniqueStringMap DictionaryType; michael@0: typedef UniqueStringMap DictionaryValidityType; michael@0: michael@0: // Create a PostfixEvaluator object that may be used (with Evaluate) on michael@0: // one or more expressions. PostfixEvaluator does not take ownership of michael@0: // either argument. |memory| may be NULL, in which case dereferencing michael@0: // (^) will not be supported. |dictionary| may be NULL, but evaluation michael@0: // will fail in that case unless set_dictionary is used before calling michael@0: // Evaluate. michael@0: PostfixEvaluator(DictionaryType *dictionary, const MemoryRegion *memory) michael@0: : dictionary_(dictionary), memory_(memory), stack_() {} michael@0: michael@0: // Evaluate the expression, starting with an empty stack. The results of michael@0: // execution will be stored in one (or more) variables in the dictionary. michael@0: // Returns false if any failures occur during execution, leaving michael@0: // variables in the dictionary in an indeterminate state. If assigned is michael@0: // non-NULL, any keys set in the dictionary as a result of evaluation michael@0: // will also be set to true in assigned, providing a way to determine if michael@0: // an expression modifies any of its input variables. michael@0: bool Evaluate(const Module::Expr &expr, DictionaryValidityType *assigned); michael@0: michael@0: // Like Evaluate, but expects the expression to denote a value. michael@0: // If evaluation succeeds and (in the case of a postfix expression) michael@0: // leaves exactly one value on the stack, pop that value, store it in michael@0: // *result, and return true. Otherwise, return false. michael@0: bool EvaluateForValue(const Module::Expr& expression, ValueType* result); michael@0: michael@0: DictionaryType* dictionary() const { return dictionary_; } michael@0: michael@0: // Reset the dictionary. PostfixEvaluator does not take ownership. michael@0: void set_dictionary(DictionaryType *dictionary) {dictionary_ = dictionary; } michael@0: michael@0: private: michael@0: // Return values for PopValueOrIdentifier michael@0: enum PopResult { michael@0: POP_RESULT_FAIL = 0, michael@0: POP_RESULT_VALUE, michael@0: POP_RESULT_IDENTIFIER michael@0: }; michael@0: michael@0: // Retrieves the topmost literal value, constant, or variable from the michael@0: // stack. Returns POP_RESULT_VALUE if the topmost entry is a literal michael@0: // value, and sets |value| accordingly. Returns POP_RESULT_IDENTIFIER michael@0: // if the topmost entry is a constant or variable identifier, and sets michael@0: // |identifier| accordingly. Returns POP_RESULT_FAIL on failure, such michael@0: // as when the stack is empty. michael@0: PopResult PopValueOrIdentifier(ValueType *value, michael@0: const UniqueString** identifier); michael@0: michael@0: // Retrieves the topmost value on the stack. If the topmost entry is michael@0: // an identifier, the dictionary is queried for the identifier's value. michael@0: // Returns false on failure, such as when the stack is empty or when michael@0: // a nonexistent identifier is named. michael@0: bool PopValue(ValueType *value); michael@0: michael@0: // Pushes a UniqueString* on the stack. michael@0: void PushIdentifier(const UniqueString* ustr); michael@0: michael@0: // Retrieves the top two values on the stack, in the style of PopValue. michael@0: // value2 is popped before value1, so that value1 corresponds to the michael@0: // entry that was pushed prior to value2. Returns false on failure. michael@0: bool PopValues(ValueType *value1, ValueType *value2); michael@0: michael@0: // Pushes a new value onto the stack. michael@0: void PushValue(const ValueType &value); michael@0: michael@0: // Evaluate expression, updating *assigned if it is non-zero. Return michael@0: // true if evaluation completes successfully. Do not clear the stack michael@0: // upon successful evaluation. michael@0: bool EvaluateInternal(const string &expression, michael@0: DictionaryValidityType *assigned); michael@0: michael@0: bool EvaluateToken(const string &token, michael@0: const string &expression, michael@0: DictionaryValidityType *assigned); michael@0: michael@0: // The dictionary mapping constant and variable identifiers (strings) to michael@0: // values. Keys beginning with '$' are treated as variable names, and michael@0: // PostfixEvaluator is free to create and modify these keys. Weak pointer. michael@0: DictionaryType *dictionary_; michael@0: michael@0: // If non-NULL, the MemoryRegion used for dereference (^) operations. michael@0: // If NULL, dereferencing is unsupported and will fail. Weak pointer. michael@0: const MemoryRegion *memory_; michael@0: michael@0: // The stack contains state information as execution progresses. Values michael@0: // are pushed on to it as the expression string is read and as operations michael@0: // yield values; values are popped when used as operands to operators. michael@0: vector > stack_; michael@0: }; michael@0: michael@0: } // namespace google_breakpad michael@0: michael@0: michael@0: #endif // PROCESSOR_POSTFIX_EVALUATOR_H__