source-position-table.cc 6.09 KB
Newer Older
1 2 3 4
// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/source-position-table.h"
6 7 8 9 10 11 12

#include "src/objects-inl.h"
#include "src/objects.h"

namespace v8 {
namespace internal {

13 14
// We'll use a simple encoding scheme to record the source positions.
// Conceptually, each position consists of:
15
// - code_offset: An integer index into the BytecodeArray or code.
16 17 18 19 20 21 22
// - source_position: An integer index into the source string.
// - position type: Each position is either a statement or an expression.
//
// The basic idea for the encoding is to use a variable-length integer coding,
// where each byte contains 7 bits of payload data, and 1 'more' bit that
// determines whether additional bytes follow. Additionally:
// - we record the difference from the previous position,
23
// - we just stuff one bit for the type into the code offset,
24
// - we write least-significant bits first,
25
// - we use zig-zag encoding to encode both positive and negative numbers.
26 27 28 29 30

namespace {

// Each byte is encoded as MoreBit | ValueBits.
class MoreBit : public BitField8<bool, 7, 1> {};
31
class ValueBits : public BitField8<unsigned, 0, 7> {};
32 33 34 35

// Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
void AddAndSetEntry(PositionTableEntry& value,
                    const PositionTableEntry& other) {
36
  value.code_offset += other.code_offset;
37 38 39 40
  value.source_position += other.source_position;
  value.is_statement = other.is_statement;
}

41
// Helper: Subtract the offsets from 'other' from 'value'.
42 43
void SubtractFromEntry(PositionTableEntry& value,
                       const PositionTableEntry& other) {
44
  value.code_offset -= other.code_offset;
45 46 47 48
  value.source_position -= other.source_position;
}

// Helper: Encode an integer.
49
template <typename T>
50
void EncodeInt(std::vector<byte>& bytes, T value) {
51
  // Zig-zag encoding.
52
  static const int kShift = sizeof(T) * kBitsPerByte - 1;
53 54
  value = ((value << 1) ^ (value >> kShift));
  DCHECK_GE(value, 0);
55
  auto encoded = static_cast<typename std::make_unsigned<T>::type>(value);
56 57
  bool more;
  do {
58
    more = encoded > ValueBits::kMax;
59 60 61
    byte current =
        MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
    bytes.push_back(current);
62
    encoded >>= ValueBits::kSize;
63 64 65 66
  } while (more);
}

// Encode a PositionTableEntry.
67
void EncodeEntry(std::vector<byte>& bytes, const PositionTableEntry& entry) {
68
  // We only accept ascending code offsets.
69
  DCHECK_GE(entry.code_offset, 0);
70 71 72
  // Since code_offset is not negative, we use sign to encode is_statement.
  EncodeInt(bytes,
            entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
73 74 75 76
  EncodeInt(bytes, entry.source_position);
}

// Helper: Decode an integer.
77 78
template <typename T>
T DecodeInt(ByteArray* bytes, int* index) {
79
  byte current;
80
  int shift = 0;
81
  T decoded = 0;
82 83 84
  bool more;
  do {
    current = bytes->get((*index)++);
85 86 87
    decoded |= static_cast<typename std::make_unsigned<T>::type>(
                   ValueBits::decode(current))
               << shift;
88
    more = MoreBit::decode(current);
89
    shift += ValueBits::kSize;
90
  } while (more);
91 92
  DCHECK_GE(decoded, 0);
  decoded = (decoded >> 1) ^ (-(decoded & 1));
93
  return decoded;
94 95 96
}

void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
97
  int tmp = DecodeInt<int>(bytes, index);
98 99
  if (tmp >= 0) {
    entry->is_statement = true;
100
    entry->code_offset = tmp;
101 102
  } else {
    entry->is_statement = false;
103
    entry->code_offset = -(tmp + 1);
104
  }
105
  entry->source_position = DecodeInt<int64_t>(bytes, index);
106 107 108
}

}  // namespace
109

110
SourcePositionTableBuilder::SourcePositionTableBuilder(
111 112
    SourcePositionTableBuilder::RecordingMode mode)
    : mode_(mode), previous_() {}
yangguo's avatar
yangguo committed
113

114
void SourcePositionTableBuilder::AddPosition(size_t code_offset,
115
                                             SourcePosition source_position,
116
                                             bool is_statement) {
117
  if (Omit()) return;
118
  DCHECK(source_position.IsKnown());
119
  int offset = static_cast<int>(code_offset);
120
  AddEntry({offset, source_position.raw(), is_statement});
121 122
}

123
void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
124
  PositionTableEntry tmp(entry);
125 126
  SubtractFromEntry(tmp, previous_);
  EncodeEntry(bytes_, tmp);
127
  previous_ = entry;
128
#ifdef ENABLE_SLOW_DCHECKS
129
  raw_entries_.push_back(entry);
130
#endif
131 132
}

133
Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
134
    Isolate* isolate) {
135
  if (bytes_.empty()) return isolate->factory()->empty_byte_array();
136
  DCHECK(!Omit());
137

138
  Handle<ByteArray> table = isolate->factory()->NewByteArray(
139 140 141 142 143 144 145 146 147 148 149
      static_cast<int>(bytes_.size()), TENURED);

  MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size());

#ifdef ENABLE_SLOW_DCHECKS
  // Brute force testing: Record all positions and decode
  // the entire table to verify they are identical.
  auto raw = raw_entries_.begin();
  for (SourcePositionTableIterator encoded(*table); !encoded.done();
       encoded.Advance(), raw++) {
    DCHECK(raw != raw_entries_.end());
150
    DCHECK_EQ(encoded.code_offset(), raw->code_offset);
151
    DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
152
    DCHECK_EQ(encoded.is_statement(), raw->is_statement);
153
  }
154
  DCHECK(raw == raw_entries_.end());
155 156
  // No additional source positions after creating the table.
  mode_ = OMIT_SOURCE_POSITIONS;
157
#endif
158 159 160
  return table;
}

161
SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
162
    : raw_table_(byte_array) {
163 164 165
  Advance();
}

166 167 168 169 170 171 172 173
SourcePositionTableIterator::SourcePositionTableIterator(
    Handle<ByteArray> byte_array)
    : table_(byte_array) {
  Advance();
  // We can enable allocation because we keep the table in a handle.
  no_gc.Release();
}

174
void SourcePositionTableIterator::Advance() {
175
  ByteArray* table = raw_table_ ? raw_table_ : *table_;
176
  DCHECK(!done());
177 178
  DCHECK(index_ >= 0 && index_ <= table->length());
  if (index_ >= table->length()) {
179 180 181
    index_ = kDone;
  } else {
    PositionTableEntry tmp;
182
    DecodeEntry(table, &index_, &tmp);
183
    AddAndSetEntry(current_, tmp);
184 185 186 187 188
  }
}

}  // namespace internal
}  // namespace v8