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
51namespace google_breakpad {
52
53using std::istringstream;
54using std::ostringstream;
55
56
57// A small class used in Evaluate to make sure to clean up the stack
58// before returning failure.
59class 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
69template<typename ValueType>
70bool 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
204template<typename ValueType>
205bool 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
233template<typename ValueType>
234bool 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
252template<typename ValueType>
253bool 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
271template<typename ValueType>
272typename PostfixEvaluator<ValueType>::PopResult
273PostfixEvaluator<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
316template<typename ValueType>
317bool 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
345template<typename ValueType>
346bool PostfixEvaluator<ValueType>::PopValues(ValueType* value1,
347 ValueType* value2) {
348 return PopValue(value2) && PopValue(value1);
349}
350
351
352template<typename ValueType>
353void 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