/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

/* vim: set ts=8 sts=2 et sw=2 tw=80: */

// 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.

// CFI reader author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>

// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>

// Implementation of dwarf2reader::LineInfo, dwarf2reader::CompilationUnit,

// and dwarf2reader::CallFrameInfo. See dwarf2reader.h for details.

// This file is derived from the following files in

// toolkit/crashreporter/google-breakpad:

//   src/common/dwarf/bytereader.cc

//   src/common/dwarf/dwarf2reader.cc

//   src/common/dwarf_cfi_to_module.cc

#include <stdint.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <map>

#include <stack>

#include <string>

#include "mozilla/Assertions.h"

#include "mozilla/Sprintf.h"

#include "LulCommonExt.h"

#include "LulDwarfInt.h"

// Set this to 1 for verbose logging

#define DEBUG_DWARF 0

namespace lul {

using std::string;

ByteReader::ByteReader(enum Endianness endian)

    :offset_reader_(NULL), address_reader_(NULL), endian_(endian),

     address_size_(0), offset_size_(0),

     have_section_base_(), have_text_base_(), have_data_base_(),

     have_function_base_() { }

ByteReader::~ByteReader() { }

void ByteReader::SetOffsetSize(uint8 size) {

  offset_size_ = size;

  MOZ_ASSERT(size == 4 || size == 8);

  if (size == 4) {

    this->offset_reader_ = &ByteReader::ReadFourBytes;

  } else {

    this->offset_reader_ = &ByteReader::ReadEightBytes;

  }

}

void ByteReader::SetAddressSize(uint8 size) {

  address_size_ = size;

  MOZ_ASSERT(size == 4 || size == 8);

  if (size == 4) {

    this->address_reader_ = &ByteReader::ReadFourBytes;

  } else {

    this->address_reader_ = &ByteReader::ReadEightBytes;

  }

}

uint64 ByteReader::ReadInitialLength(const char* start, size_t* len) {

  const uint64 initial_length = ReadFourBytes(start);

  start += 4;

  // In DWARF2/3, if the initial length is all 1 bits, then the offset

  // size is 8 and we need to read the next 8 bytes for the real length.

  if (initial_length == 0xffffffff) {

    SetOffsetSize(8);

    *len = 12;

    return ReadOffset(start);

  } else {

    SetOffsetSize(4);

    *len = 4;

  }

  return initial_length;

}

bool ByteReader::ValidEncoding(DwarfPointerEncoding encoding) const {

  if (encoding == DW_EH_PE_omit) return true;

  if (encoding == DW_EH_PE_aligned) return true;

  if ((encoding & 0x7) > DW_EH_PE_udata8)

    return false;

  if ((encoding & 0x70) > DW_EH_PE_funcrel)

    return false;

  return true;

}

bool ByteReader::UsableEncoding(DwarfPointerEncoding encoding) const {

  switch (encoding & 0x70) {

    case DW_EH_PE_absptr:  return true;

    case DW_EH_PE_pcrel:   return have_section_base_;

    case DW_EH_PE_textrel: return have_text_base_;

    case DW_EH_PE_datarel: return have_data_base_;

    case DW_EH_PE_funcrel: return have_function_base_;

    default:               return false;

  }

}

uint64 ByteReader::ReadEncodedPointer(const char *buffer,

                                      DwarfPointerEncoding encoding,

                                      size_t *len) const {

  // UsableEncoding doesn't approve of DW_EH_PE_omit, so we shouldn't

  // see it here.

  MOZ_ASSERT(encoding != DW_EH_PE_omit);

  // The Linux Standards Base 4.0 does not make this clear, but the

  // GNU tools (gcc/unwind-pe.h; readelf/dwarf.c; gdb/dwarf2-frame.c)

  // agree that aligned pointers are always absolute, machine-sized,

  // machine-signed pointers.

  if (encoding == DW_EH_PE_aligned) {

    MOZ_ASSERT(have_section_base_);

    // We don't need to align BUFFER in *our* address space. Rather, we

    // need to find the next position in our buffer that would be aligned

    // when the .eh_frame section the buffer contains is loaded into the

    // program's memory. So align assuming that buffer_base_ gets loaded at

    // address section_base_, where section_base_ itself may or may not be

    // aligned.

    // First, find the offset to START from the closest prior aligned

    // address.

    uint64 skew = section_base_ & (AddressSize() - 1);

    // Now find the offset from that aligned address to buffer.

    uint64 offset = skew + (buffer - buffer_base_);

    // Round up to the next boundary.

    uint64 aligned = (offset + AddressSize() - 1) & -AddressSize();

    // Convert back to a pointer.

    const char *aligned_buffer = buffer_base_ + (aligned - skew);

    // Finally, store the length and actually fetch the pointer.

    *len = aligned_buffer - buffer + AddressSize();

    return ReadAddress(aligned_buffer);

  }

  // Extract the value first, ignoring whether it's a pointer or an

  // offset relative to some base.

  uint64 offset;

  switch (encoding & 0x0f) {

    case DW_EH_PE_absptr:

      // DW_EH_PE_absptr is weird, as it is used as a meaningful value for

      // both the high and low nybble of encoding bytes. When it appears in

      // the high nybble, it means that the pointer is absolute, not an

      // offset from some base address. When it appears in the low nybble,

      // as here, it means that the pointer is stored as a normal

      // machine-sized and machine-signed address. A low nybble of

      // DW_EH_PE_absptr does not imply that the pointer is absolute; it is

      // correct for us to treat the value as an offset from a base address

      // if the upper nybble is not DW_EH_PE_absptr.

      offset = ReadAddress(buffer);

      *len = AddressSize();

      break;

    case DW_EH_PE_uleb128:

      offset = ReadUnsignedLEB128(buffer, len);

      break;

    case DW_EH_PE_udata2:

      offset = ReadTwoBytes(buffer);

      *len = 2;

      break;

    case DW_EH_PE_udata4:

      offset = ReadFourBytes(buffer);

      *len = 4;

      break;

    case DW_EH_PE_udata8:

      offset = ReadEightBytes(buffer);

      *len = 8;

      break;

    case DW_EH_PE_sleb128:

      offset = ReadSignedLEB128(buffer, len);

      break;

    case DW_EH_PE_sdata2:

      offset = ReadTwoBytes(buffer);

      // Sign-extend from 16 bits.

      offset = (offset ^ 0x8000) - 0x8000;

      *len = 2;

      break;

    case DW_EH_PE_sdata4:

      offset = ReadFourBytes(buffer);

      // Sign-extend from 32 bits.

      offset = (offset ^ 0x80000000ULL) - 0x80000000ULL;

      *len = 4;

      break;

    case DW_EH_PE_sdata8:

      // No need to sign-extend; this is the full width of our type.

      offset = ReadEightBytes(buffer);

      *len = 8;

      break;

    default:

      abort();

  }

  // Find the appropriate base address.

  uint64 base;

  switch (encoding & 0x70) {

    case DW_EH_PE_absptr:

      base = 0;

      break;

    case DW_EH_PE_pcrel:

      MOZ_ASSERT(have_section_base_);

      base = section_base_ + (buffer - buffer_base_);

      break;

    case DW_EH_PE_textrel:

      MOZ_ASSERT(have_text_base_);

      base = text_base_;

      break;

    case DW_EH_PE_datarel:

      MOZ_ASSERT(have_data_base_);

      base = data_base_;

      break;

    case DW_EH_PE_funcrel:

      MOZ_ASSERT(have_function_base_);

      base = function_base_;

      break;

    default:

      abort();

  }

  uint64 pointer = base + offset;

  // Remove inappropriate upper bits.

  if (AddressSize() == 4)

    pointer = pointer & 0xffffffff;

  else

    MOZ_ASSERT(AddressSize() == sizeof(uint64));

  return pointer;

}

// A DWARF rule for recovering the address or value of a register, or

// computing the canonical frame address. There is one subclass of this for

// each '*Rule' member function in CallFrameInfo::Handler.

//

// It's annoying that we have to handle Rules using pointers (because

// the concrete instances can have an arbitrary size). They're small,

// so it would be much nicer if we could just handle them by value

// instead of fretting about ownership and destruction.

//

// It seems like all these could simply be instances of std::tr1::bind,

// except that we need instances to be EqualityComparable, too.

//

// This could logically be nested within State, but then the qualified names

// get horrendous.

class CallFrameInfo::Rule {

 public:

  virtual ~Rule() { }

  // Tell HANDLER that, at ADDRESS in the program, REG can be

  // recovered using this rule. If REG is kCFARegister, then this rule

  // describes how to compute the canonical frame address. Return what the

  // HANDLER member function returned.

  virtual bool Handle(Handler *handler, uint64 address, int reg) const = 0;

  // Equality on rules. We use these to decide which rules we need

  // to report after a DW_CFA_restore_state instruction.

  virtual bool operator==(const Rule &rhs) const = 0;

  bool operator!=(const Rule &rhs) const { return ! (*this == rhs); }

  // Return a pointer to a copy of this rule.

  virtual Rule *Copy() const = 0;

  // If this is a base+offset rule, change its base register to REG.

  // Otherwise, do nothing. (Ugly, but required for DW_CFA_def_cfa_register.)

  virtual void SetBaseRegister(unsigned reg) { }

  // If this is a base+offset rule, change its offset to OFFSET. Otherwise,

  // do nothing. (Ugly, but required for DW_CFA_def_cfa_offset.)

  virtual void SetOffset(long long offset) { }

  // A RTTI workaround, to make it possible to implement equality

  // comparisons on classes derived from this one.

  enum CFIRTag {

    CFIR_UNDEFINED_RULE,

    CFIR_SAME_VALUE_RULE,

    CFIR_OFFSET_RULE,

    CFIR_VAL_OFFSET_RULE,

    CFIR_REGISTER_RULE,

    CFIR_EXPRESSION_RULE,

    CFIR_VAL_EXPRESSION_RULE

  };

  // Produce the tag that identifies the child class of this object.

  virtual CFIRTag getTag() const = 0;

};

// Rule: the value the register had in the caller cannot be recovered.

class CallFrameInfo::UndefinedRule: public CallFrameInfo::Rule {

 public:

  UndefinedRule() { }

  ~UndefinedRule() { }

  CFIRTag getTag() const override { return CFIR_UNDEFINED_RULE; }

  bool Handle(Handler *handler, uint64 address, int reg) const override {

    return handler->UndefinedRule(address, reg);

  }

  bool operator==(const Rule &rhs) const override {

    if (rhs.getTag() != CFIR_UNDEFINED_RULE) return false;

    return true;

  }

  Rule *Copy() const override { return new UndefinedRule(*this); }

};

// Rule: the register's value is the same as that it had in the caller.

class CallFrameInfo::SameValueRule: public CallFrameInfo::Rule {

 public:

  SameValueRule() { }

  ~SameValueRule() { }

  CFIRTag getTag() const override { return CFIR_SAME_VALUE_RULE; }

  bool Handle(Handler *handler, uint64 address, int reg) const override {

    return handler->SameValueRule(address, reg);

  }

  bool operator==(const Rule &rhs) const override {

    if (rhs.getTag() != CFIR_SAME_VALUE_RULE) return false;

    return true;

  }

  Rule *Copy() const override { return new SameValueRule(*this); }

};

// Rule: the register is saved at OFFSET from BASE_REGISTER.  BASE_REGISTER

// may be CallFrameInfo::Handler::kCFARegister.

class CallFrameInfo::OffsetRule: public CallFrameInfo::Rule {

 public:

  OffsetRule(int base_register, long offset)

      : base_register_(base_register), offset_(offset) { }

  ~OffsetRule() { }

  CFIRTag getTag() const override { return CFIR_OFFSET_RULE; }

  bool Handle(Handler *handler, uint64 address, int reg) const override {

    return handler->OffsetRule(address, reg, base_register_, offset_);

  }

  bool operator==(const Rule &rhs) const override {

    if (rhs.getTag() != CFIR_OFFSET_RULE) return false;

    const OffsetRule *our_rhs = static_cast<const OffsetRule *>(&rhs);

    return (base_register_ == our_rhs->base_register_ &&

            offset_ == our_rhs->offset_);

  }

  Rule *Copy() const override { return new OffsetRule(*this); }

  // We don't actually need SetBaseRegister or SetOffset here, since they

  // are only ever applied to CFA rules, for DW_CFA_def_cfa_offset, and it

  // doesn't make sense to use OffsetRule for computing the CFA: it

  // computes the address at which a register is saved, not a value.

 private:

  int base_register_;

  long offset_;

};

// Rule: the value the register had in the caller is the value of

// BASE_REGISTER plus offset. BASE_REGISTER may be

// CallFrameInfo::Handler::kCFARegister.

class CallFrameInfo::ValOffsetRule: public CallFrameInfo::Rule {

 public:

  ValOffsetRule(int base_register, long offset)

      : base_register_(base_register), offset_(offset) { }

  ~ValOffsetRule() { }

  CFIRTag getTag() const override { return CFIR_VAL_OFFSET_RULE; }

  bool Handle(Handler *handler, uint64 address, int reg) const override {

    return handler->ValOffsetRule(address, reg, base_register_, offset_);

  }

  bool operator==(const Rule &rhs) const override {

    if (rhs.getTag() != CFIR_VAL_OFFSET_RULE) return false;

    const ValOffsetRule *our_rhs = static_cast<const ValOffsetRule *>(&rhs);

    return (base_register_ == our_rhs->base_register_ &&

            offset_ == our_rhs->offset_);

  }

  Rule *Copy() const override { return new ValOffsetRule(*this); }

  void SetBaseRegister(unsigned reg) override { base_register_ = reg; }

  void SetOffset(long long offset) override { offset_ = offset; }

 private:

  int base_register_;

  long offset_;

};

// Rule: the register has been saved in another register REGISTER_NUMBER_.

class CallFrameInfo::RegisterRule: public CallFrameInfo::Rule {

 public:

  explicit RegisterRule(int register_number)

      : register_number_(register_number) { }

  ~RegisterRule() { }

  CFIRTag getTag() const override { return CFIR_REGISTER_RULE; }

  bool Handle(Handler *handler, uint64 address, int reg) const override {

    return handler->RegisterRule(address, reg, register_number_);

  }

  bool operator==(const Rule &rhs) const override {

    if (rhs.getTag() != CFIR_REGISTER_RULE) return false;

    const RegisterRule *our_rhs = static_cast<const RegisterRule *>(&rhs);

    return (register_number_ == our_rhs->register_number_);

  }

  Rule *Copy() const override { return new RegisterRule(*this); }

 private:

  int register_number_;

};

// Rule: EXPRESSION evaluates to the address at which the register is saved.

class CallFrameInfo::ExpressionRule: public CallFrameInfo::Rule {

 public:

  explicit ExpressionRule(const string &expression)

      : expression_(expression) { }

  ~ExpressionRule() { }

  CFIRTag getTag() const override { return CFIR_EXPRESSION_RULE; }

  bool Handle(Handler *handler, uint64 address, int reg) const override {

    return handler->ExpressionRule(address, reg, expression_);

  }

  bool operator==(const Rule &rhs) const override {

    if (rhs.getTag() != CFIR_EXPRESSION_RULE) return false;

    const ExpressionRule *our_rhs = static_cast<const ExpressionRule *>(&rhs);

    return (expression_ == our_rhs->expression_);

  }

  Rule *Copy() const override { return new ExpressionRule(*this); }

 private:

  string expression_;

};

// Rule: EXPRESSION evaluates to the previous value of the register.

class CallFrameInfo::ValExpressionRule: public CallFrameInfo::Rule {

 public:

  explicit ValExpressionRule(const string &expression)

      : expression_(expression) { }

  ~ValExpressionRule() { }

  CFIRTag getTag() const override { return CFIR_VAL_EXPRESSION_RULE; }

  bool Handle(Handler *handler, uint64 address, int reg) const override {

    return handler->ValExpressionRule(address, reg, expression_);

  }

  bool operator==(const Rule &rhs) const override {

    if (rhs.getTag() != CFIR_VAL_EXPRESSION_RULE) return false;

    const ValExpressionRule *our_rhs =

        static_cast<const ValExpressionRule *>(&rhs);

    return (expression_ == our_rhs->expression_);

  }

  Rule *Copy() const override { return new ValExpressionRule(*this); }

 private:

  string expression_;

};

// A map from register numbers to rules.

class CallFrameInfo::RuleMap {

 public:

  RuleMap() : cfa_rule_(NULL) { }

  RuleMap(const RuleMap &rhs) : cfa_rule_(NULL) { *this = rhs; }

  ~RuleMap() { Clear(); }

  RuleMap &operator=(const RuleMap &rhs);

  // Set the rule for computing the CFA to RULE. Take ownership of RULE.

  void SetCFARule(Rule *rule) { delete cfa_rule_; cfa_rule_ = rule; }

  // Return the current CFA rule. Unlike RegisterRule, this RuleMap retains

  // ownership of the rule. We use this for DW_CFA_def_cfa_offset and

  // DW_CFA_def_cfa_register, and for detecting references to the CFA before

  // a rule for it has been established.

  Rule *CFARule() const { return cfa_rule_; }

  // Return the rule for REG, or NULL if there is none. The caller takes

  // ownership of the result.

  Rule *RegisterRule(int reg) const;

  // Set the rule for computing REG to RULE. Take ownership of RULE.

  void SetRegisterRule(int reg, Rule *rule);

  // Make all the appropriate calls to HANDLER as if we were changing from

  // this RuleMap to NEW_RULES at ADDRESS. We use this to implement

  // DW_CFA_restore_state, where lots of rules can change simultaneously.

  // Return true if all handlers returned true; otherwise, return false.

  bool HandleTransitionTo(Handler *handler, uint64 address,

                          const RuleMap &new_rules) const;

 private:

  // A map from register numbers to Rules.

  typedef std::map<int, Rule *> RuleByNumber;

  // Remove all register rules and clear cfa_rule_.

  void Clear();

  // The rule for computing the canonical frame address. This RuleMap owns

  // this rule.

  Rule *cfa_rule_;

  // A map from register numbers to postfix expressions to recover

  // their values. This RuleMap owns the Rules the map refers to.

  RuleByNumber registers_;

};

CallFrameInfo::RuleMap &CallFrameInfo::RuleMap::operator=(const RuleMap &rhs) {

  Clear();

  // Since each map owns the rules it refers to, assignment must copy them.

  if (rhs.cfa_rule_) cfa_rule_ = rhs.cfa_rule_->Copy();

  for (RuleByNumber::const_iterator it = rhs.registers_.begin();

       it != rhs.registers_.end(); it++)

    registers_[it->first] = it->second->Copy();

  return *this;

}

CallFrameInfo::Rule *CallFrameInfo::RuleMap::RegisterRule(int reg) const {

  MOZ_ASSERT(reg != Handler::kCFARegister);

  RuleByNumber::const_iterator it = registers_.find(reg);

  if (it != registers_.end())

    return it->second->Copy();

  else

    return NULL;

}

void CallFrameInfo::RuleMap::SetRegisterRule(int reg, Rule *rule) {

  MOZ_ASSERT(reg != Handler::kCFARegister);

  MOZ_ASSERT(rule);

  Rule **slot = &registers_[reg];

  delete *slot;

  *slot = rule;

}

bool CallFrameInfo::RuleMap::HandleTransitionTo(

    Handler *handler,

    uint64 address,

    const RuleMap &new_rules) const {

  // Transition from cfa_rule_ to new_rules.cfa_rule_.

  if (cfa_rule_ && new_rules.cfa_rule_) {

    if (*cfa_rule_ != *new_rules.cfa_rule_ &&

        !new_rules.cfa_rule_->Handle(handler, address, Handler::kCFARegister))

      return false;

  } else if (cfa_rule_) {

    // this RuleMap has a CFA rule but new_rules doesn't.

    // CallFrameInfo::Handler has no way to handle this --- and shouldn't;

    // it's garbage input. The instruction interpreter should have

    // detected this and warned, so take no action here.

  } else if (new_rules.cfa_rule_) {

    // This shouldn't be possible: NEW_RULES is some prior state, and

    // there's no way to remove entries.

    MOZ_ASSERT(0);

  } else {

    // Both CFA rules are empty.  No action needed.

  }

  // Traverse the two maps in order by register number, and report

  // whatever differences we find.

  RuleByNumber::const_iterator old_it = registers_.begin();

  RuleByNumber::const_iterator new_it = new_rules.registers_.begin();

  while (old_it != registers_.end() && new_it != new_rules.registers_.end()) {

    if (old_it->first < new_it->first) {

      // This RuleMap has an entry for old_it->first, but NEW_RULES

      // doesn't.

      //

      // This isn't really the right thing to do, but since CFI generally

      // only mentions callee-saves registers, and GCC's convention for

      // callee-saves registers is that they are unchanged, it's a good

      // approximation.

      if (!handler->SameValueRule(address, old_it->first))

        return false;

      old_it++;

    } else if (old_it->first > new_it->first) {

      // NEW_RULES has entry for new_it->first, but this RuleMap

      // doesn't. This shouldn't be possible: NEW_RULES is some prior

      // state, and there's no way to remove entries.

      MOZ_ASSERT(0);

    } else {

      // Both maps have an entry for this register. Report the new

      // rule if it is different.

      if (*old_it->second != *new_it->second &&

          !new_it->second->Handle(handler, address, new_it->first))

        return false;

      new_it++; old_it++;

    }

  }

  // Finish off entries from this RuleMap with no counterparts in new_rules.

  while (old_it != registers_.end()) {

    if (!handler->SameValueRule(address, old_it->first))

      return false;

    old_it++;

  }

  // Since we only make transitions from a rule set to some previously

  // saved rule set, and we can only add rules to the map, NEW_RULES

  // must have fewer rules than *this.

  MOZ_ASSERT(new_it == new_rules.registers_.end());

  return true;

}

// Remove all register rules and clear cfa_rule_.

void CallFrameInfo::RuleMap::Clear() {

  delete cfa_rule_;

  cfa_rule_ = NULL;

  for (RuleByNumber::iterator it = registers_.begin();

       it != registers_.end(); it++)

    delete it->second;

  registers_.clear();

}

// The state of the call frame information interpreter as it processes

// instructions from a CIE and FDE.

class CallFrameInfo::State {

 public:

  // Create a call frame information interpreter state with the given

  // reporter, reader, handler, and initial call frame info address.

  State(ByteReader *reader, Handler *handler, Reporter *reporter,

        uint64 address)

      : reader_(reader), handler_(handler), reporter_(reporter),

        address_(address), entry_(NULL), cursor_(NULL),

        saved_rules_(NULL) { }

  ~State() {

    if (saved_rules_)

      delete saved_rules_;

  }

  // Interpret instructions from CIE, save the resulting rule set for

  // DW_CFA_restore instructions, and return true. On error, report

  // the problem to reporter_ and return false.

  bool InterpretCIE(const CIE &cie);

  // Interpret instructions from FDE, and return true. On error,

  // report the problem to reporter_ and return false.

  bool InterpretFDE(const FDE &fde);

 private:

  // The operands of a CFI instruction, for ParseOperands.

  struct Operands {

    unsigned register_number;  // A register number.

    uint64 offset;             // An offset or address.

    long signed_offset;        // A signed offset.

    string expression;         // A DWARF expression.

  };

  // Parse CFI instruction operands from STATE's instruction stream as

  // described by FORMAT. On success, populate OPERANDS with the

  // results, and return true. On failure, report the problem and

  // return false.

  //

  // Each character of FORMAT should be one of the following:

  //

  //   'r'  unsigned LEB128 register number (OPERANDS->register_number)

  //   'o'  unsigned LEB128 offset          (OPERANDS->offset)

  //   's'  signed LEB128 offset            (OPERANDS->signed_offset)

  //   'a'  machine-size address            (OPERANDS->offset)

  //        (If the CIE has a 'z' augmentation string, 'a' uses the

  //        encoding specified by the 'R' argument.)

  //   '1'  a one-byte offset               (OPERANDS->offset)

  //   '2'  a two-byte offset               (OPERANDS->offset)

  //   '4'  a four-byte offset              (OPERANDS->offset)

  //   '8'  an eight-byte offset            (OPERANDS->offset)

  //   'e'  a DW_FORM_block holding a       (OPERANDS->expression)

  //        DWARF expression

  bool ParseOperands(const char *format, Operands *operands);

  // Interpret one CFI instruction from STATE's instruction stream, update

  // STATE, report any rule changes to handler_, and return true. On

  // failure, report the problem and return false.

  bool DoInstruction();

  // The following Do* member functions are subroutines of DoInstruction,

  // factoring out the actual work of operations that have several

  // different encodings.

  // Set the CFA rule to be the value of BASE_REGISTER plus OFFSET, and

  // return true. On failure, report and return false. (Used for

  // DW_CFA_def_cfa and DW_CFA_def_cfa_sf.)

  bool DoDefCFA(unsigned base_register, long offset);

  // Change the offset of the CFA rule to OFFSET, and return true. On

  // failure, report and return false. (Subroutine for

  // DW_CFA_def_cfa_offset and DW_CFA_def_cfa_offset_sf.)

  bool DoDefCFAOffset(long offset);

  // Specify that REG can be recovered using RULE, and return true. On

  // failure, report and return false.

  bool DoRule(unsigned reg, Rule *rule);

  // Specify that REG can be found at OFFSET from the CFA, and return true.

  // On failure, report and return false. (Subroutine for DW_CFA_offset,

  // DW_CFA_offset_extended, and DW_CFA_offset_extended_sf.)

  bool DoOffset(unsigned reg, long offset);

  // Specify that the caller's value for REG is the CFA plus OFFSET,

  // and return true. On failure, report and return false. (Subroutine

  // for DW_CFA_val_offset and DW_CFA_val_offset_sf.)

  bool DoValOffset(unsigned reg, long offset);

  // Restore REG to the rule established in the CIE, and return true. On

  // failure, report and return false. (Subroutine for DW_CFA_restore and

  // DW_CFA_restore_extended.)

  bool DoRestore(unsigned reg);

  // Return the section offset of the instruction at cursor. For use

  // in error messages.

  uint64 CursorOffset() { return entry_->offset + (cursor_ - entry_->start); }

  // Report that entry_ is incomplete, and return false. For brevity.

  bool ReportIncomplete() {

    reporter_->Incomplete(entry_->offset, entry_->kind);

    return false;

  }

  // For reading multi-byte values with the appropriate endianness.

  ByteReader *reader_;

  // The handler to which we should report the data we find.

  Handler *handler_;

  // For reporting problems in the info we're parsing.

  Reporter *reporter_;

  // The code address to which the next instruction in the stream applies.

  uint64 address_;

  // The entry whose instructions we are currently processing. This is

  // first a CIE, and then an FDE.

  const Entry *entry_;

  // The next instruction to process.

  const char *cursor_;

  // The current set of rules.

  RuleMap rules_;

  // The set of rules established by the CIE, used by DW_CFA_restore

  // and DW_CFA_restore_extended. We set this after interpreting the

  // CIE's instructions.

  RuleMap cie_rules_;

  // A stack of saved states, for DW_CFA_remember_state and

  // DW_CFA_restore_state.

  std::stack<RuleMap>* saved_rules_;

};

bool CallFrameInfo::State::InterpretCIE(const CIE &cie) {

  entry_ = &cie;

  cursor_ = entry_->instructions;

  while (cursor_ < entry_->end)

    if (!DoInstruction())

      return false;

  // Note the rules established by the CIE, for use by DW_CFA_restore

  // and DW_CFA_restore_extended.

  cie_rules_ = rules_;

  return true;

}

bool CallFrameInfo::State::InterpretFDE(const FDE &fde) {

  entry_ = &fde;

  cursor_ = entry_->instructions;

  while (cursor_ < entry_->end)

    if (!DoInstruction())

      return false;

  return true;

}

bool CallFrameInfo::State::ParseOperands(const char *format,

                                         Operands *operands) {

  size_t len;

  const char *operand;

  for (operand = format; *operand; operand++) {

    size_t bytes_left = entry_->end - cursor_;

    switch (*operand) {

      case 'r':

        operands->register_number = reader_->ReadUnsignedLEB128(cursor_, &len);

        if (len > bytes_left) return ReportIncomplete();

        cursor_ += len;

        break;

      case 'o':

        operands->offset = reader_->ReadUnsignedLEB128(cursor_, &len);

        if (len > bytes_left) return ReportIncomplete();

        cursor_ += len;

        break;

      case 's':

        operands->signed_offset = reader_->ReadSignedLEB128(cursor_, &len);

        if (len > bytes_left) return ReportIncomplete();

        cursor_ += len;

        break;

      case 'a':

        operands->offset =

          reader_->ReadEncodedPointer(cursor_, entry_->cie->pointer_encoding,

                                      &len);

        if (len > bytes_left) return ReportIncomplete();

        cursor_ += len;

        break;

      case '1':

        if (1 > bytes_left) return ReportIncomplete();

        operands->offset = static_cast<unsigned char>(*cursor_++);

        break;

      case '2':

        if (2 > bytes_left) return ReportIncomplete();

        operands->offset = reader_->ReadTwoBytes(cursor_);

        cursor_ += 2;

        break;

      case '4':

        if (4 > bytes_left) return ReportIncomplete();

        operands->offset = reader_->ReadFourBytes(cursor_);

        cursor_ += 4;

        break;

      case '8':

        if (8 > bytes_left) return ReportIncomplete();

        operands->offset = reader_->ReadEightBytes(cursor_);

        cursor_ += 8;

        break;

      case 'e': {

        size_t expression_length = reader_->ReadUnsignedLEB128(cursor_, &len);

        if (len > bytes_left || expression_length > bytes_left - len)

          return ReportIncomplete();

        cursor_ += len;

        operands->expression = string(cursor_, expression_length);

        cursor_ += expression_length;

        break;

      }

      default:

        MOZ_ASSERT(0);

    }

  }

  return true;

}

bool CallFrameInfo::State::DoInstruction() {

  CIE *cie = entry_->cie;

  Operands ops;

  // Our entry's kind should have been set by now.

  MOZ_ASSERT(entry_->kind != kUnknown);

  // We shouldn't have been invoked unless there were more

  // instructions to parse.

  MOZ_ASSERT(cursor_ < entry_->end);

  unsigned opcode = *cursor_++;

  if ((opcode & 0xc0) != 0) {

    switch (opcode & 0xc0) {

      // Advance the address.

      case DW_CFA_advance_loc: {

        size_t code_offset = opcode & 0x3f;

        address_ += code_offset * cie->code_alignment_factor;

        break;

      }

      // Find a register at an offset from the CFA.

      case DW_CFA_offset:

        if (!ParseOperands("o", &ops) ||

            !DoOffset(opcode & 0x3f, ops.offset * cie->data_alignment_factor))

          return false;

        break;

      // Restore the rule established for a register by the CIE.

      case DW_CFA_restore:

        if (!DoRestore(opcode & 0x3f)) return false;

        break;

      // The 'if' above should have excluded this possibility.

      default:

        MOZ_ASSERT(0);

    }

    // Return here, so the big switch below won't be indented.

    return true;

  }

  switch (opcode) {

    // Set the address.

    case DW_CFA_set_loc:

      if (!ParseOperands("a", &ops)) return false;

      address_ = ops.offset;

      break;

    // Advance the address.

    case DW_CFA_advance_loc1:

      if (!ParseOperands("1", &ops)) return false;

      address_ += ops.offset * cie->code_alignment_factor;

      break;

    // Advance the address.

    case DW_CFA_advance_loc2:

      if (!ParseOperands("2", &ops)) return false;

      address_ += ops.offset * cie->code_alignment_factor;

      break;

    // Advance the address.

    case DW_CFA_advance_loc4:

      if (!ParseOperands("4", &ops)) return false;

      address_ += ops.offset * cie->code_alignment_factor;

      break;

    // Advance the address.

    case DW_CFA_MIPS_advance_loc8:

      if (!ParseOperands("8", &ops)) return false;

      address_ += ops.offset * cie->code_alignment_factor;

      break;