aboutsummaryrefslogtreecommitdiff
path: root/src/processor/postfix_evaluator-inl.h
blob: b1252f6806c1df43994f319eeb85d2906ba2e8ea (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
// -*- mode: c++ -*-

// Copyright (c) 2010 Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// postfix_evaluator-inl.h: Postfix (reverse Polish) notation expression
// evaluator.
//
// Documentation in postfix_evaluator.h.
//
// Author: Mark Mentovai

#ifndef PROCESSOR_POSTFIX_EVALUATOR_INL_H__
#define PROCESSOR_POSTFIX_EVALUATOR_INL_H__


#include <cstdio>
#include <sstream>

#include "processor/postfix_evaluator.h"
#include "google_breakpad/processor/memory_region.h"
#include "processor/logging.h"

namespace google_breakpad {

using std::istringstream;
using std::ostringstream;


// A small class used in Evaluate to make sure to clean up the stack
// before returning failure.
class AutoStackClearer {
 public:
  explicit AutoStackClearer(vector<string> *stack) : stack_(stack) {}
  ~AutoStackClearer() { stack_->clear(); }

 private:
  vector<string> *stack_;
};


template<typename ValueType>
bool PostfixEvaluator<ValueType>::EvaluateInternal(
    const string &expression,
    DictionaryValidityType *assigned) {
  // Tokenize, splitting on whitespace.
  istringstream stream(expression);
  string token;
  while (stream >> token) {
    // There are enough binary operations that do exactly the same thing
    // (other than the specific operation, of course) that it makes sense
    // to share as much code as possible.
    enum BinaryOperation {
      BINARY_OP_NONE = 0,
      BINARY_OP_ADD,
      BINARY_OP_SUBTRACT,
      BINARY_OP_MULTIPLY,
      BINARY_OP_DIVIDE_QUOTIENT,
      BINARY_OP_DIVIDE_MODULUS
    };

    BinaryOperation operation = BINARY_OP_NONE;
    if (token == "+")
      operation = BINARY_OP_ADD;
    else if (token == "-")
      operation = BINARY_OP_SUBTRACT;
    else if (token == "*")
      operation = BINARY_OP_MULTIPLY;
    else if (token == "/")
      operation = BINARY_OP_DIVIDE_QUOTIENT;
    else if (token == "%")
      operation = BINARY_OP_DIVIDE_MODULUS;

    if (operation != BINARY_OP_NONE) {
      // Get the operands.
      ValueType operand1, operand2;
      if (!PopValues(&operand1, &operand2)) {
        BPLOG(ERROR) << "Could not PopValues to get two values for binary "
                        "operation " << token << ": " << expression;
        return false;
      }

      // Perform the operation.
      ValueType result;
      switch (operation) {
        case BINARY_OP_ADD:
          result = operand1 + operand2;
          break;
        case BINARY_OP_SUBTRACT:
          result = operand1 - operand2;
          break;
        case BINARY_OP_MULTIPLY:
          result = operand1 * operand2;
          break;
        case BINARY_OP_DIVIDE_QUOTIENT:
          result = operand1 / operand2;
          break;
        case BINARY_OP_DIVIDE_MODULUS:
          result = operand1 % operand2;
          break;
        case BINARY_OP_NONE:
          // This will not happen, but compilers will want a default or
          // BINARY_OP_NONE case.
          BPLOG(ERROR) << "Not reached!";
          return false;
          break;
      }

      // Save the result.
      PushValue(result);
    } else if (token == "^") {
      // ^ for unary dereference.  Can't dereference without memory.
      if (!memory_) {
        BPLOG(ERROR) << "Attempt to dereference without memory: " <<
                        expression;
        return false;
      }

      ValueType address;
      if (!PopValue(&address)) {
        BPLOG(ERROR) << "Could not PopValue to get value to derefence: " <<
                        expression;
        return false;
      }

      ValueType value;
      if (!memory_->GetMemoryAtAddress(address, &value)) {
        BPLOG(ERROR) << "Could not dereference memory at address " <<
                        HexString(address) << ": " << expression;
        return false;
      }

      PushValue(value);
    } else if (token == "=") {
      // = for assignment.
      ValueType value;
      if (!PopValue(&value)) {
        BPLOG(ERROR) << "Could not PopValue to get value to assign: " <<
                        expression;
        return false;
      }

      // Assignment is only meaningful when assigning into an identifier.
      // The identifier must name a variable, not a constant.  Variables
      // begin with '$'.
      string identifier;
      if (PopValueOrIdentifier(NULL, &identifier) != POP_RESULT_IDENTIFIER) {
        BPLOG(ERROR) << "PopValueOrIdentifier returned a value, but an "
                        "identifier is needed to assign " <<
                        HexString(value) << ": " << expression;
        return false;
      }
      if (identifier.empty() || identifier[0] != '$') {
        BPLOG(ERROR) << "Can't assign " << HexString(value) << " to " <<
                        identifier << ": " << expression;
        return false;
      }

      (*dictionary_)[identifier] = value;
      if (assigned)
        (*assigned)[identifier] = true;
    } else {
      // The token is not an operator, it's a literal value or an identifier.
      // Push it onto the stack as-is.  Use push_back instead of PushValue
      // because PushValue pushes ValueType as a string, but token is already
      // a string.
      stack_.push_back(token);
    }
  }

  return true;
}

template<typename ValueType>
bool PostfixEvaluator<ValueType>::Evaluate(const string &expression,
                                           DictionaryValidityType *assigned) {
  // Ensure that the stack is cleared before returning.
  AutoStackClearer clearer(&stack_);

  if (!EvaluateInternal(expression, assigned))
    return false;

  // If there's anything left on the stack, it indicates incomplete execution.
  // This is a failure case.  If the stack is empty, evalution was complete
  // and successful.
  if (stack_.empty())
    return true;
    
  BPLOG(ERROR) << "Incomplete execution: " << expression;
  return false;
}

template<typename ValueType>
bool PostfixEvaluator<ValueType>::EvaluateForValue(const string &expression,
                                                   ValueType *result) {
  // Ensure that the stack is cleared before returning.
  AutoStackClearer clearer(&stack_);

  if (!EvaluateInternal(expression, NULL))
    return false;

  // A successful execution should leave exactly one value on the stack.
  if (stack_.size() != 1) {
    BPLOG(ERROR) << "Expression yielded bad number of results: "
                 << "'" << expression << "'";
    return false;
  } 

  return PopValue(result);
}

template<typename ValueType>
typename PostfixEvaluator<ValueType>::PopResult
PostfixEvaluator<ValueType>::PopValueOrIdentifier(
    ValueType *value, string *identifier) {
  // There needs to be at least one element on the stack to pop.
  if (!stack_.size())
    return POP_RESULT_FAIL;

  string token = stack_.back();
  stack_.pop_back();

  // First, try to treat the value as a literal. Literals may have leading
  // '-' sign, and the entire remaining string must be parseable as
  // ValueType. If this isn't possible, it can't be a literal, so treat it
  // as an identifier instead.
  //
  // Some versions of the libstdc++, the GNU standard C++ library, have
  // stream extractors for unsigned integer values that permit a leading
  // '-' sign (6.0.13); others do not (6.0.9). Since we require it, we
  // handle it explicitly here.
  istringstream token_stream(token);
  ValueType literal;
  bool negative;
  if (token_stream.peek() == '-') {
    negative = true;
    token_stream.get();
  } else {
    negative = false;
  }
  if (token_stream >> literal && token_stream.peek() == EOF) {
    if (value) {
      *value = literal;
    }
    if (negative)
      *value = -*value;
    return POP_RESULT_VALUE;
  } else {
    if (identifier) {
      *identifier = token;
    }
    return POP_RESULT_IDENTIFIER;
  }
}


template<typename ValueType>
bool PostfixEvaluator<ValueType>::PopValue(ValueType *value) {
  ValueType literal;
  string token;
  PopResult result;
  if ((result = PopValueOrIdentifier(&literal, &token)) == POP_RESULT_FAIL) {
    return false;
  } else if (result == POP_RESULT_VALUE) {
    // This is the easy case.
    *value = literal;
  } else {  // result == POP_RESULT_IDENTIFIER
    // There was an identifier at the top of the stack.  Resolve it to a
    // value by looking it up in the dictionary.
    typename DictionaryType::const_iterator iterator =
        dictionary_->find(token);
    if (iterator == dictionary_->end()) {
      // The identifier wasn't found in the dictionary.  Don't imply any
      // default value, just fail.
      BPLOG(ERROR) << "Identifier " << token << " not in dictionary";
      return false;
    }

    *value = iterator->second;
  }

  return true;
}


template<typename ValueType>
bool PostfixEvaluator<ValueType>::PopValues(ValueType *value1,
                                            ValueType *value2) {
  return PopValue(value2) && PopValue(value1);
}


template<typename ValueType>
void PostfixEvaluator<ValueType>::PushValue(const ValueType &value) {
  ostringstream token_stream;
  token_stream << value;
  stack_.push_back(token_stream.str());
}


}  // namespace google_breakpad


#endif  // PROCESSOR_POSTFIX_EVALUATOR_INL_H__