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-inl.h: Postfix (reverse Polish) notation expression |
33 | // evaluator. |
34 | // |
35 | // Documentation in postfix_evaluator.h. |
36 | // |
37 | // Author: Mark Mentovai |
38 | |
39 | #ifndef PROCESSOR_POSTFIX_EVALUATOR_INL_H__ |
40 | #define PROCESSOR_POSTFIX_EVALUATOR_INL_H__ |
41 | |
42 | #include "processor/postfix_evaluator.h" |
43 | |
44 | #include <stdio.h> |
45 | |
46 | #include <sstream> |
47 | |
48 | #include "google_breakpad/processor/memory_region.h" |
49 | #include "processor/logging.h" |
50 | |
51 | namespace google_breakpad { |
52 | |
53 | using std::istringstream; |
54 | using std::ostringstream; |
55 | |
56 | |
57 | // A small class used in Evaluate to make sure to clean up the stack |
58 | // before returning failure. |
59 | class AutoStackClearer { |
60 | public: |
61 | explicit AutoStackClearer(vector<string>* stack) : stack_(stack) {} |
62 | ~AutoStackClearer() { stack_->clear(); } |
63 | |
64 | private: |
65 | vector<string>* stack_; |
66 | }; |
67 | |
68 | |
69 | template<typename ValueType> |
70 | bool PostfixEvaluator<ValueType>::EvaluateToken( |
71 | const string& token, |
72 | const string& expression, |
73 | DictionaryValidityType* assigned) { |
74 | // There are enough binary operations that do exactly the same thing |
75 | // (other than the specific operation, of course) that it makes sense |
76 | // to share as much code as possible. |
77 | enum BinaryOperation { |
78 | BINARY_OP_NONE = 0, |
79 | BINARY_OP_ADD, |
80 | BINARY_OP_SUBTRACT, |
81 | BINARY_OP_MULTIPLY, |
82 | BINARY_OP_DIVIDE_QUOTIENT, |
83 | BINARY_OP_DIVIDE_MODULUS, |
84 | BINARY_OP_ALIGN |
85 | }; |
86 | |
87 | BinaryOperation operation = BINARY_OP_NONE; |
88 | if (token == "+" ) |
89 | operation = BINARY_OP_ADD; |
90 | else if (token == "-" ) |
91 | operation = BINARY_OP_SUBTRACT; |
92 | else if (token == "*" ) |
93 | operation = BINARY_OP_MULTIPLY; |
94 | else if (token == "/" ) |
95 | operation = BINARY_OP_DIVIDE_QUOTIENT; |
96 | else if (token == "%" ) |
97 | operation = BINARY_OP_DIVIDE_MODULUS; |
98 | else if (token == "@" ) |
99 | operation = BINARY_OP_ALIGN; |
100 | |
101 | if (operation != BINARY_OP_NONE) { |
102 | // Get the operands. |
103 | ValueType operand1 = ValueType(); |
104 | ValueType operand2 = ValueType(); |
105 | if (!PopValues(&operand1, &operand2)) { |
106 | BPLOG(ERROR) << "Could not PopValues to get two values for binary " |
107 | "operation " << token << ": " << expression; |
108 | return false; |
109 | } |
110 | |
111 | // Perform the operation. |
112 | ValueType result; |
113 | switch (operation) { |
114 | case BINARY_OP_ADD: |
115 | result = operand1 + operand2; |
116 | break; |
117 | case BINARY_OP_SUBTRACT: |
118 | result = operand1 - operand2; |
119 | break; |
120 | case BINARY_OP_MULTIPLY: |
121 | result = operand1 * operand2; |
122 | break; |
123 | case BINARY_OP_DIVIDE_QUOTIENT: |
124 | result = operand1 / operand2; |
125 | break; |
126 | case BINARY_OP_DIVIDE_MODULUS: |
127 | result = operand1 % operand2; |
128 | break; |
129 | case BINARY_OP_ALIGN: |
130 | result = |
131 | operand1 & (static_cast<ValueType>(-1) ^ (operand2 - 1)); |
132 | break; |
133 | case BINARY_OP_NONE: |
134 | // This will not happen, but compilers will want a default or |
135 | // BINARY_OP_NONE case. |
136 | BPLOG(ERROR) << "Not reached!" ; |
137 | return false; |
138 | break; |
139 | } |
140 | |
141 | // Save the result. |
142 | PushValue(result); |
143 | } else if (token == "^" ) { |
144 | // ^ for unary dereference. Can't dereference without memory. |
145 | if (!memory_) { |
146 | BPLOG(ERROR) << "Attempt to dereference without memory: " << |
147 | expression; |
148 | return false; |
149 | } |
150 | |
151 | ValueType address; |
152 | if (!PopValue(&address)) { |
153 | BPLOG(ERROR) << "Could not PopValue to get value to derefence: " << |
154 | expression; |
155 | return false; |
156 | } |
157 | |
158 | ValueType value; |
159 | if (!memory_->GetMemoryAtAddress(address, &value)) { |
160 | BPLOG(ERROR) << "Could not dereference memory at address " << |
161 | HexString(address) << ": " << expression; |
162 | return false; |
163 | } |
164 | |
165 | PushValue(value); |
166 | } else if (token == "=" ) { |
167 | // = for assignment. |
168 | ValueType value; |
169 | if (!PopValue(&value)) { |
170 | BPLOG(INFO) << "Could not PopValue to get value to assign: " << |
171 | expression; |
172 | return false; |
173 | } |
174 | |
175 | // Assignment is only meaningful when assigning into an identifier. |
176 | // The identifier must name a variable, not a constant. Variables |
177 | // begin with '$'. |
178 | string identifier; |
179 | if (PopValueOrIdentifier(NULL, &identifier) != POP_RESULT_IDENTIFIER) { |
180 | BPLOG(ERROR) << "PopValueOrIdentifier returned a value, but an " |
181 | "identifier is needed to assign " << |
182 | HexString(value) << ": " << expression; |
183 | return false; |
184 | } |
185 | if (identifier.empty() || identifier[0] != '$') { |
186 | BPLOG(ERROR) << "Can't assign " << HexString(value) << " to " << |
187 | identifier << ": " << expression; |
188 | return false; |
189 | } |
190 | |
191 | (*dictionary_)[identifier] = value; |
192 | if (assigned) |
193 | (*assigned)[identifier] = true; |
194 | } else { |
195 | // The token is not an operator, it's a literal value or an identifier. |
196 | // Push it onto the stack as-is. Use push_back instead of PushValue |
197 | // because PushValue pushes ValueType as a string, but token is already |
198 | // a string. |
199 | stack_.push_back(token); |
200 | } |
201 | return true; |
202 | } |
203 | |
204 | template<typename ValueType> |
205 | bool PostfixEvaluator<ValueType>::EvaluateInternal( |
206 | const string& expression, |
207 | DictionaryValidityType* assigned) { |
208 | // Tokenize, splitting on whitespace. |
209 | istringstream stream(expression); |
210 | string token; |
211 | while (stream >> token) { |
212 | // Normally, tokens are whitespace-separated, but occasionally, the |
213 | // assignment operator is smashed up against the next token, i.e. |
214 | // $T0 $ebp 128 + =$eip $T0 4 + ^ =$ebp $T0 ^ = |
215 | // This has been observed in program strings produced by MSVS 2010 in LTO |
216 | // mode. |
217 | if (token.size() > 1 && token[0] == '=') { |
218 | if (!EvaluateToken("=" , expression, assigned)) { |
219 | return false; |
220 | } |
221 | |
222 | if (!EvaluateToken(token.substr(1), expression, assigned)) { |
223 | return false; |
224 | } |
225 | } else if (!EvaluateToken(token, expression, assigned)) { |
226 | return false; |
227 | } |
228 | } |
229 | |
230 | return true; |
231 | } |
232 | |
233 | template<typename ValueType> |
234 | bool PostfixEvaluator<ValueType>::Evaluate(const string& expression, |
235 | DictionaryValidityType* assigned) { |
236 | // Ensure that the stack is cleared before returning. |
237 | AutoStackClearer clearer(&stack_); |
238 | |
239 | if (!EvaluateInternal(expression, assigned)) |
240 | return false; |
241 | |
242 | // If there's anything left on the stack, it indicates incomplete execution. |
243 | // This is a failure case. If the stack is empty, evalution was complete |
244 | // and successful. |
245 | if (stack_.empty()) |
246 | return true; |
247 | |
248 | BPLOG(ERROR) << "Incomplete execution: " << expression; |
249 | return false; |
250 | } |
251 | |
252 | template<typename ValueType> |
253 | bool PostfixEvaluator<ValueType>::EvaluateForValue(const string& expression, |
254 | ValueType* result) { |
255 | // Ensure that the stack is cleared before returning. |
256 | AutoStackClearer clearer(&stack_); |
257 | |
258 | if (!EvaluateInternal(expression, NULL)) |
259 | return false; |
260 | |
261 | // A successful execution should leave exactly one value on the stack. |
262 | if (stack_.size() != 1) { |
263 | BPLOG(ERROR) << "Expression yielded bad number of results: " |
264 | << "'" << expression << "'" ; |
265 | return false; |
266 | } |
267 | |
268 | return PopValue(result); |
269 | } |
270 | |
271 | template<typename ValueType> |
272 | typename PostfixEvaluator<ValueType>::PopResult |
273 | PostfixEvaluator<ValueType>::PopValueOrIdentifier( |
274 | ValueType* value, string* identifier) { |
275 | // There needs to be at least one element on the stack to pop. |
276 | if (!stack_.size()) |
277 | return POP_RESULT_FAIL; |
278 | |
279 | string token = stack_.back(); |
280 | stack_.pop_back(); |
281 | |
282 | // First, try to treat the value as a literal. Literals may have leading |
283 | // '-' sign, and the entire remaining string must be parseable as |
284 | // ValueType. If this isn't possible, it can't be a literal, so treat it |
285 | // as an identifier instead. |
286 | // |
287 | // Some versions of the libstdc++, the GNU standard C++ library, have |
288 | // stream extractors for unsigned integer values that permit a leading |
289 | // '-' sign (6.0.13); others do not (6.0.9). Since we require it, we |
290 | // handle it explicitly here. |
291 | istringstream token_stream(token); |
292 | ValueType literal = ValueType(); |
293 | bool negative; |
294 | if (token_stream.peek() == '-') { |
295 | negative = true; |
296 | token_stream.get(); |
297 | } else { |
298 | negative = false; |
299 | } |
300 | if (token_stream >> literal && token_stream.peek() == EOF) { |
301 | if (value) { |
302 | *value = literal; |
303 | } |
304 | if (negative) |
305 | *value = -*value; |
306 | return POP_RESULT_VALUE; |
307 | } else { |
308 | if (identifier) { |
309 | *identifier = token; |
310 | } |
311 | return POP_RESULT_IDENTIFIER; |
312 | } |
313 | } |
314 | |
315 | |
316 | template<typename ValueType> |
317 | bool PostfixEvaluator<ValueType>::PopValue(ValueType* value) { |
318 | ValueType literal = ValueType(); |
319 | string token; |
320 | PopResult result; |
321 | if ((result = PopValueOrIdentifier(&literal, &token)) == POP_RESULT_FAIL) { |
322 | return false; |
323 | } else if (result == POP_RESULT_VALUE) { |
324 | // This is the easy case. |
325 | *value = literal; |
326 | } else { // result == POP_RESULT_IDENTIFIER |
327 | // There was an identifier at the top of the stack. Resolve it to a |
328 | // value by looking it up in the dictionary. |
329 | typename DictionaryType::const_iterator iterator = |
330 | dictionary_->find(token); |
331 | if (iterator == dictionary_->end()) { |
332 | // The identifier wasn't found in the dictionary. Don't imply any |
333 | // default value, just fail. |
334 | BPLOG(INFO) << "Identifier " << token << " not in dictionary" ; |
335 | return false; |
336 | } |
337 | |
338 | *value = iterator->second; |
339 | } |
340 | |
341 | return true; |
342 | } |
343 | |
344 | |
345 | template<typename ValueType> |
346 | bool PostfixEvaluator<ValueType>::PopValues(ValueType* value1, |
347 | ValueType* value2) { |
348 | return PopValue(value2) && PopValue(value1); |
349 | } |
350 | |
351 | |
352 | template<typename ValueType> |
353 | void PostfixEvaluator<ValueType>::PushValue(const ValueType& value) { |
354 | ostringstream token_stream; |
355 | token_stream << value; |
356 | stack_.push_back(token_stream.str()); |
357 | } |
358 | |
359 | |
360 | } // namespace google_breakpad |
361 | |
362 | |
363 | #endif // PROCESSOR_POSTFIX_EVALUATOR_INL_H__ |
364 | |