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. |
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 | |