V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
source-position-table.cc
1 // Copyright 2016 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/source-position-table.h"
6 
7 #include "src/objects-inl.h"
8 #include "src/objects.h"
9 
10 namespace v8 {
11 namespace internal {
12 
13 // We'll use a simple encoding scheme to record the source positions.
14 // Conceptually, each position consists of:
15 // - code_offset: An integer index into the BytecodeArray or code.
16 // - source_position: An integer index into the source string.
17 // - position type: Each position is either a statement or an expression.
18 //
19 // The basic idea for the encoding is to use a variable-length integer coding,
20 // where each byte contains 7 bits of payload data, and 1 'more' bit that
21 // determines whether additional bytes follow. Additionally:
22 // - 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 namespace {
28 
29 // Each byte is encoded as MoreBit | ValueBits.
30 class MoreBit : public BitField8<bool, 7, 1> {};
31 class ValueBits : public BitField8<unsigned, 0, 7> {};
32 
33 // Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
34 void AddAndSetEntry(PositionTableEntry& value,
35  const PositionTableEntry& other) {
36  value.code_offset += other.code_offset;
37  value.source_position += other.source_position;
38  value.is_statement = other.is_statement;
39 }
40 
41 // Helper: Subtract the offsets from 'other' from 'value'.
42 void SubtractFromEntry(PositionTableEntry& value,
43  const PositionTableEntry& other) {
44  value.code_offset -= other.code_offset;
45  value.source_position -= other.source_position;
46 }
47 
48 // 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  value = ((value << 1) ^ (value >> kShift));
54  DCHECK_GE(value, 0);
55  auto encoded = static_cast<typename std::make_unsigned<T>::type>(value);
56  bool more;
57  do {
58  more = encoded > ValueBits::kMax;
59  byte current =
60  MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
61  bytes.push_back(current);
62  encoded >>= ValueBits::kSize;
63  } while (more);
64 }
65 
66 // 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  // Since code_offset is not negative, we use sign to encode is_statement.
71  EncodeInt(bytes,
72  entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
73  EncodeInt(bytes, entry.source_position);
74 }
75 
76 // Helper: Decode an integer.
77 template <typename T>
78 T DecodeInt(Vector<const byte> bytes, int* index) {
79  byte current;
80  int shift = 0;
81  T decoded = 0;
82  bool more;
83  do {
84  current = bytes[(*index)++];
85  decoded |= static_cast<typename std::make_unsigned<T>::type>(
86  ValueBits::decode(current))
87  << shift;
88  more = MoreBit::decode(current);
89  shift += ValueBits::kSize;
90  } while (more);
91  DCHECK_GE(decoded, 0);
92  decoded = (decoded >> 1) ^ (-(decoded & 1));
93  return decoded;
94 }
95 
96 void DecodeEntry(Vector<const byte> bytes, int* index,
97  PositionTableEntry* entry) {
98  int tmp = DecodeInt<int>(bytes, index);
99  if (tmp >= 0) {
100  entry->is_statement = true;
101  entry->code_offset = tmp;
102  } else {
103  entry->is_statement = false;
104  entry->code_offset = -(tmp + 1);
105  }
106  entry->source_position = DecodeInt<int64_t>(bytes, index);
107 }
108 
109 Vector<const byte> VectorFromByteArray(ByteArray byte_array) {
110  return Vector<const byte>(byte_array->GetDataStartAddress(),
111  byte_array->length());
112 }
113 
114 #ifdef ENABLE_SLOW_DCHECKS
115 void CheckTableEquals(std::vector<PositionTableEntry>& raw_entries,
116  SourcePositionTableIterator& encoded) {
117  // Brute force testing: Record all positions and decode
118  // the entire table to verify they are identical.
119  auto raw = raw_entries.begin();
120  for (; !encoded.done(); encoded.Advance(), raw++) {
121  DCHECK(raw != raw_entries.end());
122  DCHECK_EQ(encoded.code_offset(), raw->code_offset);
123  DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
124  DCHECK_EQ(encoded.is_statement(), raw->is_statement);
125  }
126  DCHECK(raw == raw_entries.end());
127 }
128 #endif
129 
130 } // namespace
131 
132 SourcePositionTableBuilder::SourcePositionTableBuilder(
133  SourcePositionTableBuilder::RecordingMode mode)
134  : mode_(mode), previous_() {}
135 
136 void SourcePositionTableBuilder::AddPosition(size_t code_offset,
137  SourcePosition source_position,
138  bool is_statement) {
139  if (Omit()) return;
140  DCHECK(source_position.IsKnown());
141  int offset = static_cast<int>(code_offset);
142  AddEntry({offset, source_position.raw(), is_statement});
143 }
144 
145 void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
146  PositionTableEntry tmp(entry);
147  SubtractFromEntry(tmp, previous_);
148  EncodeEntry(bytes_, tmp);
149  previous_ = entry;
150 #ifdef ENABLE_SLOW_DCHECKS
151  raw_entries_.push_back(entry);
152 #endif
153 }
154 
155 Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
156  Isolate* isolate) {
157  if (bytes_.empty()) return isolate->factory()->empty_byte_array();
158  DCHECK(!Omit());
159 
160  Handle<ByteArray> table = isolate->factory()->NewByteArray(
161  static_cast<int>(bytes_.size()), TENURED);
162  MemCopy(table->GetDataStartAddress(), bytes_.data(), bytes_.size());
163 
164 #ifdef ENABLE_SLOW_DCHECKS
165  // Brute force testing: Record all positions and decode
166  // the entire table to verify they are identical.
167  SourcePositionTableIterator it(*table);
168  CheckTableEquals(raw_entries_, it);
169  // No additional source positions after creating the table.
170  mode_ = OMIT_SOURCE_POSITIONS;
171 #endif
172  return table;
173 }
174 
175 OwnedVector<byte> SourcePositionTableBuilder::ToSourcePositionTableVector() {
176  if (bytes_.empty()) return OwnedVector<byte>();
177  DCHECK(!Omit());
178 
179  OwnedVector<byte> table = OwnedVector<byte>::Of(bytes_);
180 
181 #ifdef ENABLE_SLOW_DCHECKS
182  // Brute force testing: Record all positions and decode
183  // the entire table to verify they are identical.
184  SourcePositionTableIterator it(table.as_vector());
185  CheckTableEquals(raw_entries_, it);
186  // No additional source positions after creating the table.
187  mode_ = OMIT_SOURCE_POSITIONS;
188 #endif
189  return table;
190 }
191 
192 SourcePositionTableIterator::SourcePositionTableIterator(ByteArray byte_array)
193  : raw_table_(VectorFromByteArray(byte_array)) {
194  Advance();
195 }
196 
197 SourcePositionTableIterator::SourcePositionTableIterator(
198  Handle<ByteArray> byte_array)
199  : table_(byte_array) {
200  Advance();
201 #ifdef DEBUG
202  // We can enable allocation because we keep the table in a handle.
203  no_gc.Release();
204 #endif // DEBUG
205 }
206 
207 SourcePositionTableIterator::SourcePositionTableIterator(
208  Vector<const byte> bytes)
209  : raw_table_(bytes) {
210  Advance();
211 #ifdef DEBUG
212  // We can enable allocation because the underlying vector does not move.
213  no_gc.Release();
214 #endif // DEBUG
215 }
216 
217 void SourcePositionTableIterator::Advance() {
218  Vector<const byte> bytes =
219  table_.is_null() ? raw_table_ : VectorFromByteArray(*table_);
220  DCHECK(!done());
221  DCHECK(index_ >= 0 && index_ <= bytes.length());
222  if (index_ >= bytes.length()) {
223  index_ = kDone;
224  } else {
225  PositionTableEntry tmp;
226  DecodeEntry(bytes, &index_, &tmp);
227  AddAndSetEntry(current_, tmp);
228  }
229 }
230 
231 } // namespace internal
232 } // namespace v8
Definition: libplatform.h:13