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