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
79namespace google_breakpad {
80
81using std::map;
82using std::vector;
83
84class MemoryRegion;
85
86template<typename ValueType>
87class 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