The Tor Browser / file revision

 // -*- mode: C++ -*-

 // Copyright (c) 2010 Google Inc.

 // All rights reserved.

 //

 // Redistribution and use in source and binary forms, with or without

 // modification, are permitted provided that the following conditions are

 // met:

 //

 //     * Redistributions of source code must retain the above copyright

 // notice, this list of conditions and the following disclaimer.

 //     * Redistributions in binary form must reproduce the above

 // copyright notice, this list of conditions and the following disclaimer

 // in the documentation and/or other materials provided with the

 // distribution.

 //     * Neither the name of Google Inc. nor the names of its

 // contributors may be used to endorse or promote products derived from

 // this software without specific prior written permission.

 //

 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 // postfix_evaluator.h: Postfix (reverse Polish) notation expression evaluator.

 //

 // PostfixEvaluator evaluates an expression, using the expression itself

 // in postfix (reverse Polish) notation and a dictionary mapping constants

 // and variables to their values.  The evaluator supports standard

 // arithmetic operations, assignment into variables, and when an optional

 // MemoryRange is provided, dereferencing.  (Any unary key-to-value operation

 // may be used with a MemoryRange implementation that returns the appropriate

 // values, but PostfixEvaluator was written with dereferencing in mind.)

 //

 // The expression language is simple.  Expressions are supplied as strings,

 // with operands and operators delimited by whitespace.  Operands may be

 // either literal values suitable for ValueType, or constants or variables,

 // which reference the dictionary.  The supported binary operators are +

 // (addition), - (subtraction), * (multiplication), / (quotient of division),

 // % (modulus of division), and @ (data alignment). The alignment operator (@)

 // accepts a value and an alignment size, and produces a result that is a

 // multiple of the alignment size by truncating the input value.

 // The unary ^ (dereference) operator is also provided.  These operators

 // allow any operand to be either a literal value, constant, or variable.

 // Assignment (=) of any type of operand into a variable is also supported.

 //

 // The dictionary is provided as a map with string keys.  Keys beginning

 // with the '$' character are treated as variables.  All other keys are

 // treated as constants.  Any results must be assigned into variables in the

 // dictionary.  These variables do not need to exist prior to calling

 // Evaluate, unless used in an expression prior to being assigned to.  The

 // internal stack state is not made available after evaluation, and any

 // values remaining on the stack are treated as evidence of incomplete

 // execution and cause the evaluator to indicate failure.

 //

 // PostfixEvaluator is intended to support evaluation of "program strings"

 // obtained from MSVC frame data debugging information in pdb files as

 // returned by the DIA APIs.

 //

 // Author: Mark Mentovai

 #ifndef PROCESSOR_POSTFIX_EVALUATOR_H__

 #define PROCESSOR_POSTFIX_EVALUATOR_H__

 #include <map>

 #include <string>

 #include <vector>

 #include "common/using_std_string.h"

 #include "common/unique_string.h"

 #include "common/module.h"

 namespace google_breakpad {

 using std::map;

 using std::vector;

 class MemoryRegion;

 // A union type for elements in the postfix evaluator's stack.

 template<typename ValueType>

 class StackElem {

  public:

   StackElem(ValueType val) { isValue = true; u.val = val; }

   StackElem(const UniqueString* ustr) { isValue = false; u.ustr = ustr; }

   bool isValue;

   union { ValueType val; const UniqueString* ustr; } u;

 };

 template<typename ValueType>

 class PostfixEvaluator {

  public:

   typedef UniqueStringMap<ValueType> DictionaryType;

   typedef UniqueStringMap<bool>      DictionaryValidityType;

   // Create a PostfixEvaluator object that may be used (with Evaluate) on

   // one or more expressions.  PostfixEvaluator does not take ownership of

   // either argument.  |memory| may be NULL, in which case dereferencing

   // (^) will not be supported.  |dictionary| may be NULL, but evaluation

   // will fail in that case unless set_dictionary is used before calling

   // Evaluate.

   PostfixEvaluator(DictionaryType *dictionary, const MemoryRegion *memory)

       : dictionary_(dictionary), memory_(memory), stack_() {}

   // Evaluate the expression, starting with an empty stack. The results of

   // execution will be stored in one (or more) variables in the dictionary.

   // Returns false if any failures occur during execution, leaving

   // variables in the dictionary in an indeterminate state. If assigned is

   // non-NULL, any keys set in the dictionary as a result of evaluation

   // will also be set to true in assigned, providing a way to determine if

   // an expression modifies any of its input variables.

   bool Evaluate(const Module::Expr &expr, DictionaryValidityType *assigned);

   // Like Evaluate, but expects the expression to denote a value.

   // If evaluation succeeds and (in the case of a postfix expression)

   // leaves exactly one value on the stack, pop that value, store it in

   // *result, and return true. Otherwise, return false.

   bool EvaluateForValue(const Module::Expr& expression, ValueType* result);

   DictionaryType* dictionary() const { return dictionary_; }

   // Reset the dictionary.  PostfixEvaluator does not take ownership.

   void set_dictionary(DictionaryType *dictionary) {dictionary_ = dictionary; }

  private:

   // Return values for PopValueOrIdentifier

   enum PopResult {

     POP_RESULT_FAIL = 0,

     POP_RESULT_VALUE,

     POP_RESULT_IDENTIFIER

   };

   // Retrieves the topmost literal value, constant, or variable from the

   // stack.  Returns POP_RESULT_VALUE if the topmost entry is a literal

   // value, and sets |value| accordingly.  Returns POP_RESULT_IDENTIFIER

   // if the topmost entry is a constant or variable identifier, and sets

   // |identifier| accordingly.  Returns POP_RESULT_FAIL on failure, such

   // as when the stack is empty.

   PopResult PopValueOrIdentifier(ValueType *value,

                                  const UniqueString** identifier);

   // Retrieves the topmost value on the stack.  If the topmost entry is

   // an identifier, the dictionary is queried for the identifier's value.

   // Returns false on failure, such as when the stack is empty or when

   // a nonexistent identifier is named.

   bool PopValue(ValueType *value);

   // Pushes a UniqueString* on the stack.

   void PushIdentifier(const UniqueString* ustr);

   // Retrieves the top two values on the stack, in the style of PopValue.

   // value2 is popped before value1, so that value1 corresponds to the

   // entry that was pushed prior to value2.  Returns false on failure.

   bool PopValues(ValueType *value1, ValueType *value2);

   // Pushes a new value onto the stack.

   void PushValue(const ValueType &value);

   // Evaluate expression, updating *assigned if it is non-zero. Return

   // true if evaluation completes successfully. Do not clear the stack

   // upon successful evaluation.

   bool EvaluateInternal(const string &expression,

                         DictionaryValidityType *assigned);

   bool EvaluateToken(const string &token,

                      const string &expression,

                      DictionaryValidityType *assigned);

   // The dictionary mapping constant and variable identifiers (strings) to

   // values.  Keys beginning with '$' are treated as variable names, and

   // PostfixEvaluator is free to create and modify these keys.  Weak pointer.

   DictionaryType *dictionary_;

   // If non-NULL, the MemoryRegion used for dereference (^) operations.

   // If NULL, dereferencing is unsupported and will fail.  Weak pointer.

   const MemoryRegion *memory_;

   // The stack contains state information as execution progresses.  Values

   // are pushed on to it as the expression string is read and as operations

   // yield values; values are popped when used as operands to operators.

   vector<StackElem<ValueType> > stack_;

 };

 }  // namespace google_breakpad

 #endif  // PROCESSOR_POSTFIX_EVALUATOR_H__