The Tor Browser: comparison toolkit/crashreporter/google-breakpad/src/processor/postfix

--1:000000000000
+:9288f43cccf0
+// -*- 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.h: Postfix (reverse Polish) notation expression evaluator.
+//
+// PostfixEvaluator evaluates an expression, using the expression itself
+// in postfix (reverse Polish) notation and a dictionary mapping constants
+// and variables to their values.  The evaluator supports standard
+// arithmetic operations, assignment into variables, and when an optional
+// MemoryRange is provided, dereferencing.  (Any unary key-to-value operation
+// may be used with a MemoryRange implementation that returns the appropriate
+// values, but PostfixEvaluator was written with dereferencing in mind.)
+//
+// The expression language is simple.  Expressions are supplied as strings,
+// with operands and operators delimited by whitespace.  Operands may be
+// either literal values suitable for ValueType, or constants or variables,
+// which reference the dictionary.  The supported binary operators are +
+// (addition), - (subtraction), * (multiplication), / (quotient of division),
+// % (modulus of division), and @ (data alignment). The alignment operator (@)
+// accepts a value and an alignment size, and produces a result that is a
+// multiple of the alignment size by truncating the input value.
+// The unary ^ (dereference) operator is also provided.  These operators
+// allow any operand to be either a literal value, constant, or variable.
+// Assignment (=) of any type of operand into a variable is also supported.
+//
+// The dictionary is provided as a map with string keys.  Keys beginning
+// with the '$' character are treated as variables.  All other keys are
+// treated as constants.  Any results must be assigned into variables in the
+// dictionary.  These variables do not need to exist prior to calling
+// Evaluate, unless used in an expression prior to being assigned to.  The
+// internal stack state is not made available after evaluation, and any
+// values remaining on the stack are treated as evidence of incomplete
+// execution and cause the evaluator to indicate failure.
+//
+// PostfixEvaluator is intended to support evaluation of "program strings"
+// obtained from MSVC frame data debugging information in pdb files as
+// returned by the DIA APIs.
+//
+// Author: Mark Mentovai
+#ifndef PROCESSOR_POSTFIX_EVALUATOR_H__
+#define PROCESSOR_POSTFIX_EVALUATOR_H__
+#include <map>
+#include <string>
+#include <vector>
+#include "common/using_std_string.h"
+#include "common/unique_string.h"
+#include "common/module.h"
+namespace google_breakpad {
+using std::map;
+using std::vector;
+class MemoryRegion;
+// A union type for elements in the postfix evaluator's stack.
+template<typename ValueType>
+class StackElem {
+public:
+StackElem(ValueType val) { isValue = true; u.val = val; }
+StackElem(const UniqueString* ustr) { isValue = false; u.ustr = ustr; }
+bool isValue;
+union { ValueType val; const UniqueString* ustr; } u;
+};
+template<typename ValueType>
+class PostfixEvaluator {
+public:
+typedef UniqueStringMap<ValueType> DictionaryType;
+typedef UniqueStringMap<bool>      DictionaryValidityType;
+// Create a PostfixEvaluator object that may be used (with Evaluate) on
+// one or more expressions.  PostfixEvaluator does not take ownership of
+// either argument.  |memory| may be NULL, in which case dereferencing
+// (^) will not be supported.  |dictionary| may be NULL, but evaluation
+// will fail in that case unless set_dictionary is used before calling
+// Evaluate.
+PostfixEvaluator(DictionaryType *dictionary, const MemoryRegion *memory)
+: dictionary_(dictionary), memory_(memory), stack_() {}
+// Evaluate the expression, starting with an empty stack. The results of
+// execution will be stored in one (or more) variables in the dictionary.
+// Returns false if any failures occur during execution, leaving
+// variables in the dictionary in an indeterminate state. If assigned is
+// non-NULL, any keys set in the dictionary as a result of evaluation
+// will also be set to true in assigned, providing a way to determine if
+// an expression modifies any of its input variables.
+bool Evaluate(const Module::Expr &expr, DictionaryValidityType *assigned);
+// Like Evaluate, but expects the expression to denote a value.
+// If evaluation succeeds and (in the case of a postfix expression)
+// leaves exactly one value on the stack, pop that value, store it in
+// *result, and return true. Otherwise, return false.
+bool EvaluateForValue(const Module::Expr& expression, ValueType* result);
+DictionaryType* dictionary() const { return dictionary_; }
+// Reset the dictionary.  PostfixEvaluator does not take ownership.
+void set_dictionary(DictionaryType *dictionary) {dictionary_ = dictionary; }
+private:
+// Return values for PopValueOrIdentifier
+enum PopResult {
+POP_RESULT_FAIL = 0,
+POP_RESULT_VALUE,
+POP_RESULT_IDENTIFIER
+};
+// Retrieves the topmost literal value, constant, or variable from the
+// stack.  Returns POP_RESULT_VALUE if the topmost entry is a literal
+// value, and sets |value| accordingly.  Returns POP_RESULT_IDENTIFIER
+// if the topmost entry is a constant or variable identifier, and sets
+// |identifier| accordingly.  Returns POP_RESULT_FAIL on failure, such
+// as when the stack is empty.
+PopResult PopValueOrIdentifier(ValueType *value,
+const UniqueString** identifier);
+// Retrieves the topmost value on the stack.  If the topmost entry is
+// an identifier, the dictionary is queried for the identifier's value.
+// Returns false on failure, such as when the stack is empty or when
+// a nonexistent identifier is named.
+bool PopValue(ValueType *value);
+// Pushes a UniqueString* on the stack.
+void PushIdentifier(const UniqueString* ustr);
+// Retrieves the top two values on the stack, in the style of PopValue.
+// value2 is popped before value1, so that value1 corresponds to the
+// entry that was pushed prior to value2.  Returns false on failure.
+bool PopValues(ValueType *value1, ValueType *value2);
+// Pushes a new value onto the stack.
+void PushValue(const ValueType &value);
+// Evaluate expression, updating *assigned if it is non-zero. Return
+// true if evaluation completes successfully. Do not clear the stack
+// upon successful evaluation.
+bool EvaluateInternal(const string &expression,
+DictionaryValidityType *assigned);
+bool EvaluateToken(const string &token,
+const string &expression,
+DictionaryValidityType *assigned);
+// The dictionary mapping constant and variable identifiers (strings) to
+// values.  Keys beginning with '$' are treated as variable names, and
+// PostfixEvaluator is free to create and modify these keys.  Weak pointer.
+DictionaryType *dictionary_;
+// If non-NULL, the MemoryRegion used for dereference (^) operations.
+// If NULL, dereferencing is unsupported and will fail.  Weak pointer.
+const MemoryRegion *memory_;
+// The stack contains state information as execution progresses.  Values
+// are pushed on to it as the expression string is read and as operations
+// yield values; values are popped when used as operands to operators.
+vector<StackElem<ValueType> > stack_;
+};
+}  // namespace google_breakpad
+#endif  // PROCESSOR_POSTFIX_EVALUATOR_H__

The Tor Browser / file comparison

comparison: toolkit/crashreporter/google-breakpad/src/processor/postfix_evaluator.h

toolkit/crashreporter/google-breakpad/src/processor/postfix_evaluator.h