← Back to branch summary

~ubuntu-branches/ubuntu/trusty/tomahawk/trusty-proposed

« back to all changes in this revision

Viewing changes to thirdparty/breakpad/processor/postfix_evaluator-inl.h

  • Committer: Package Import Robot
  • Author(s): Harald Sitter
  • Date: 2013-03-07 23:40:27 UTC
  • mfrom: (1.1.1)
  • Revision ID: package-import@ubuntu.com-20130307234027-1jc3yomfdliyapta
Tags: 0.6.0+dfsg1-0ubuntu1
Reduce dfsg stripping to fix build (source remains still DFSG compliant)

Show diffs side-by-side

added added

removed removed

Lines of Context:
thirdparty/breakpad/processor/postfix_evaluator-inl.h
 
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__