1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/crashreporter/google-breakpad/src/processor/postfix_evaluator.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,195 @@
1.4 +// -*- mode: C++ -*-
1.5 +
1.6 +// Copyright (c) 2010 Google Inc.
1.7 +// All rights reserved.
1.8 +//
1.9 +// Redistribution and use in source and binary forms, with or without
1.10 +// modification, are permitted provided that the following conditions are
1.11 +// met:
1.12 +//
1.13 +// * Redistributions of source code must retain the above copyright
1.14 +// notice, this list of conditions and the following disclaimer.
1.15 +// * Redistributions in binary form must reproduce the above
1.16 +// copyright notice, this list of conditions and the following disclaimer
1.17 +// in the documentation and/or other materials provided with the
1.18 +// distribution.
1.19 +// * Neither the name of Google Inc. nor the names of its
1.20 +// contributors may be used to endorse or promote products derived from
1.21 +// this software without specific prior written permission.
1.22 +//
1.23 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.24 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.25 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.26 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.27 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.28 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.29 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.30 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.31 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.32 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.33 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.34 +
1.35 +// postfix_evaluator.h: Postfix (reverse Polish) notation expression evaluator.
1.36 +//
1.37 +// PostfixEvaluator evaluates an expression, using the expression itself
1.38 +// in postfix (reverse Polish) notation and a dictionary mapping constants
1.39 +// and variables to their values. The evaluator supports standard
1.40 +// arithmetic operations, assignment into variables, and when an optional
1.41 +// MemoryRange is provided, dereferencing. (Any unary key-to-value operation
1.42 +// may be used with a MemoryRange implementation that returns the appropriate
1.43 +// values, but PostfixEvaluator was written with dereferencing in mind.)
1.44 +//
1.45 +// The expression language is simple. Expressions are supplied as strings,
1.46 +// with operands and operators delimited by whitespace. Operands may be
1.47 +// either literal values suitable for ValueType, or constants or variables,
1.48 +// which reference the dictionary. The supported binary operators are +
1.49 +// (addition), - (subtraction), * (multiplication), / (quotient of division),
1.50 +// % (modulus of division), and @ (data alignment). The alignment operator (@)
1.51 +// accepts a value and an alignment size, and produces a result that is a
1.52 +// multiple of the alignment size by truncating the input value.
1.53 +// The unary ^ (dereference) operator is also provided. These operators
1.54 +// allow any operand to be either a literal value, constant, or variable.
1.55 +// Assignment (=) of any type of operand into a variable is also supported.
1.56 +//
1.57 +// The dictionary is provided as a map with string keys. Keys beginning
1.58 +// with the '$' character are treated as variables. All other keys are
1.59 +// treated as constants. Any results must be assigned into variables in the
1.60 +// dictionary. These variables do not need to exist prior to calling
1.61 +// Evaluate, unless used in an expression prior to being assigned to. The
1.62 +// internal stack state is not made available after evaluation, and any
1.63 +// values remaining on the stack are treated as evidence of incomplete
1.64 +// execution and cause the evaluator to indicate failure.
1.65 +//
1.66 +// PostfixEvaluator is intended to support evaluation of "program strings"
1.67 +// obtained from MSVC frame data debugging information in pdb files as
1.68 +// returned by the DIA APIs.
1.69 +//
1.70 +// Author: Mark Mentovai
1.71 +
1.72 +#ifndef PROCESSOR_POSTFIX_EVALUATOR_H__
1.73 +#define PROCESSOR_POSTFIX_EVALUATOR_H__
1.74 +
1.75 +
1.76 +#include <map>
1.77 +#include <string>
1.78 +#include <vector>
1.79 +
1.80 +#include "common/using_std_string.h"
1.81 +#include "common/unique_string.h"
1.82 +#include "common/module.h"
1.83 +
1.84 +namespace google_breakpad {
1.85 +
1.86 +using std::map;
1.87 +using std::vector;
1.88 +
1.89 +class MemoryRegion;
1.90 +
1.91 +// A union type for elements in the postfix evaluator's stack.
1.92 +template<typename ValueType>
1.93 +class StackElem {
1.94 + public:
1.95 + StackElem(ValueType val) { isValue = true; u.val = val; }
1.96 + StackElem(const UniqueString* ustr) { isValue = false; u.ustr = ustr; }
1.97 + bool isValue;
1.98 + union { ValueType val; const UniqueString* ustr; } u;
1.99 +};
1.100 +
1.101 +template<typename ValueType>
1.102 +class PostfixEvaluator {
1.103 + public:
1.104 + typedef UniqueStringMap<ValueType> DictionaryType;
1.105 + typedef UniqueStringMap<bool> DictionaryValidityType;
1.106 +
1.107 + // Create a PostfixEvaluator object that may be used (with Evaluate) on
1.108 + // one or more expressions. PostfixEvaluator does not take ownership of
1.109 + // either argument. |memory| may be NULL, in which case dereferencing
1.110 + // (^) will not be supported. |dictionary| may be NULL, but evaluation
1.111 + // will fail in that case unless set_dictionary is used before calling
1.112 + // Evaluate.
1.113 + PostfixEvaluator(DictionaryType *dictionary, const MemoryRegion *memory)
1.114 + : dictionary_(dictionary), memory_(memory), stack_() {}
1.115 +
1.116 + // Evaluate the expression, starting with an empty stack. The results of
1.117 + // execution will be stored in one (or more) variables in the dictionary.
1.118 + // Returns false if any failures occur during execution, leaving
1.119 + // variables in the dictionary in an indeterminate state. If assigned is
1.120 + // non-NULL, any keys set in the dictionary as a result of evaluation
1.121 + // will also be set to true in assigned, providing a way to determine if
1.122 + // an expression modifies any of its input variables.
1.123 + bool Evaluate(const Module::Expr &expr, DictionaryValidityType *assigned);
1.124 +
1.125 + // Like Evaluate, but expects the expression to denote a value.
1.126 + // If evaluation succeeds and (in the case of a postfix expression)
1.127 + // leaves exactly one value on the stack, pop that value, store it in
1.128 + // *result, and return true. Otherwise, return false.
1.129 + bool EvaluateForValue(const Module::Expr& expression, ValueType* result);
1.130 +
1.131 + DictionaryType* dictionary() const { return dictionary_; }
1.132 +
1.133 + // Reset the dictionary. PostfixEvaluator does not take ownership.
1.134 + void set_dictionary(DictionaryType *dictionary) {dictionary_ = dictionary; }
1.135 +
1.136 + private:
1.137 + // Return values for PopValueOrIdentifier
1.138 + enum PopResult {
1.139 + POP_RESULT_FAIL = 0,
1.140 + POP_RESULT_VALUE,
1.141 + POP_RESULT_IDENTIFIER
1.142 + };
1.143 +
1.144 + // Retrieves the topmost literal value, constant, or variable from the
1.145 + // stack. Returns POP_RESULT_VALUE if the topmost entry is a literal
1.146 + // value, and sets |value| accordingly. Returns POP_RESULT_IDENTIFIER
1.147 + // if the topmost entry is a constant or variable identifier, and sets
1.148 + // |identifier| accordingly. Returns POP_RESULT_FAIL on failure, such
1.149 + // as when the stack is empty.
1.150 + PopResult PopValueOrIdentifier(ValueType *value,
1.151 + const UniqueString** identifier);
1.152 +
1.153 + // Retrieves the topmost value on the stack. If the topmost entry is
1.154 + // an identifier, the dictionary is queried for the identifier's value.
1.155 + // Returns false on failure, such as when the stack is empty or when
1.156 + // a nonexistent identifier is named.
1.157 + bool PopValue(ValueType *value);
1.158 +
1.159 + // Pushes a UniqueString* on the stack.
1.160 + void PushIdentifier(const UniqueString* ustr);
1.161 +
1.162 + // Retrieves the top two values on the stack, in the style of PopValue.
1.163 + // value2 is popped before value1, so that value1 corresponds to the
1.164 + // entry that was pushed prior to value2. Returns false on failure.
1.165 + bool PopValues(ValueType *value1, ValueType *value2);
1.166 +
1.167 + // Pushes a new value onto the stack.
1.168 + void PushValue(const ValueType &value);
1.169 +
1.170 + // Evaluate expression, updating *assigned if it is non-zero. Return
1.171 + // true if evaluation completes successfully. Do not clear the stack
1.172 + // upon successful evaluation.
1.173 + bool EvaluateInternal(const string &expression,
1.174 + DictionaryValidityType *assigned);
1.175 +
1.176 + bool EvaluateToken(const string &token,
1.177 + const string &expression,
1.178 + DictionaryValidityType *assigned);
1.179 +
1.180 + // The dictionary mapping constant and variable identifiers (strings) to
1.181 + // values. Keys beginning with '$' are treated as variable names, and
1.182 + // PostfixEvaluator is free to create and modify these keys. Weak pointer.
1.183 + DictionaryType *dictionary_;
1.184 +
1.185 + // If non-NULL, the MemoryRegion used for dereference (^) operations.
1.186 + // If NULL, dereferencing is unsupported and will fail. Weak pointer.
1.187 + const MemoryRegion *memory_;
1.188 +
1.189 + // The stack contains state information as execution progresses. Values
1.190 + // are pushed on to it as the expression string is read and as operations
1.191 + // yield values; values are popped when used as operands to operators.
1.192 + vector<StackElem<ValueType> > stack_;
1.193 +};
1.194 +
1.195 +} // namespace google_breakpad
1.196 +
1.197 +
1.198 +#endif // PROCESSOR_POSTFIX_EVALUATOR_H__
