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
10namespace v8 {
11namespace 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
27namespace {
28
29// Each byte is encoded as MoreBit | ValueBits.
30class MoreBit : public BitField8<bool, 7, 1> {};
31class ValueBits : public BitField8<unsigned, 0, 7> {};
32
33// Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
34void 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'.
42void 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.
49template <typename T>
50void EncodeInt(std::vector<byte>& bytes, T value) {
51 typedef typename std::make_unsigned<T>::type unsigned_type;
52 // Zig-zag encoding.
53 static const int kShift = sizeof(T) * kBitsPerByte - 1;
54 value = ((static_cast<unsigned_type>(value) << 1) ^ (value >> kShift));
55 DCHECK_GE(value, 0);
56 unsigned_type encoded = static_cast<unsigned_type>(value);
57 bool more;
58 do {
59 more = encoded > ValueBits::kMax;
60 byte current =
61 MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
62 bytes.push_back(current);
63 encoded >>= ValueBits::kSize;
64 } while (more);
65}
66
67// Encode a PositionTableEntry.
68void EncodeEntry(std::vector<byte>& bytes, const PositionTableEntry& entry) {
69 // We only accept ascending code offsets.
70 DCHECK_GE(entry.code_offset, 0);
71 // Since code_offset is not negative, we use sign to encode is_statement.
72 EncodeInt(bytes,
73 entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
74 EncodeInt(bytes, entry.source_position);
75}
76
77// Helper: Decode an integer.
78template <typename T>
79T DecodeInt(Vector<const byte> bytes, int* index) {
80 byte current;
81 int shift = 0;
82 T decoded = 0;
83 bool more;
84 do {
85 current = bytes[(*index)++];
86 decoded |= static_cast<typename std::make_unsigned<T>::type>(
87 ValueBits::decode(current))
88 << shift;
89 more = MoreBit::decode(current);
90 shift += ValueBits::kSize;
91 } while (more);
92 DCHECK_GE(decoded, 0);
93 decoded = (decoded >> 1) ^ (-(decoded & 1));
94 return decoded;
95}
96
97void DecodeEntry(Vector<const byte> bytes, int* index,
98 PositionTableEntry* entry) {
99 int tmp = DecodeInt<int>(bytes, index);
100 if (tmp >= 0) {
101 entry->is_statement = true;
102 entry->code_offset = tmp;
103 } else {
104 entry->is_statement = false;
105 entry->code_offset = -(tmp + 1);
106 }
107 entry->source_position = DecodeInt<int64_t>(bytes, index);
108}
109
110Vector<const byte> VectorFromByteArray(ByteArray byte_array) {
111 return Vector<const byte>(byte_array->GetDataStartAddress(),
112 byte_array->length());
113}
114
115#ifdef ENABLE_SLOW_DCHECKS
116void CheckTableEquals(std::vector<PositionTableEntry>& raw_entries,
117 SourcePositionTableIterator& encoded) {
118 // Brute force testing: Record all positions and decode
119 // the entire table to verify they are identical.
120 auto raw = raw_entries.begin();
121 for (; !encoded.done(); encoded.Advance(), raw++) {
122 DCHECK(raw != raw_entries.end());
123 DCHECK_EQ(encoded.code_offset(), raw->code_offset);
124 DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
125 DCHECK_EQ(encoded.is_statement(), raw->is_statement);
126 }
127 DCHECK(raw == raw_entries.end());
128}
129#endif
130
131} // namespace
132
133SourcePositionTableBuilder::SourcePositionTableBuilder(
134 SourcePositionTableBuilder::RecordingMode mode)
135 : mode_(mode), previous_() {}
136
137void SourcePositionTableBuilder::AddPosition(size_t code_offset,
138 SourcePosition source_position,
139 bool is_statement) {
140 if (Omit()) return;
141 DCHECK(source_position.IsKnown());
142 int offset = static_cast<int>(code_offset);
143 AddEntry({offset, source_position.raw(), is_statement});
144}
145
146void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
147 PositionTableEntry tmp(entry);
148 SubtractFromEntry(tmp, previous_);
149 EncodeEntry(bytes_, tmp);
150 previous_ = entry;
151#ifdef ENABLE_SLOW_DCHECKS
152 raw_entries_.push_back(entry);
153#endif
154}
155
156Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
157 Isolate* isolate) {
158 if (bytes_.empty()) return isolate->factory()->empty_byte_array();
159 DCHECK(!Omit());
160
161 Handle<ByteArray> table = isolate->factory()->NewByteArray(
162 static_cast<int>(bytes_.size()), AllocationType::kOld);
163 MemCopy(table->GetDataStartAddress(), bytes_.data(), bytes_.size());
164
165#ifdef ENABLE_SLOW_DCHECKS
166 // Brute force testing: Record all positions and decode
167 // the entire table to verify they are identical.
168 SourcePositionTableIterator it(*table, SourcePositionTableIterator::kAll);
169 CheckTableEquals(raw_entries_, it);
170 // No additional source positions after creating the table.
171 mode_ = OMIT_SOURCE_POSITIONS;
172#endif
173 return table;
174}
175
176OwnedVector<byte> SourcePositionTableBuilder::ToSourcePositionTableVector() {
177 if (bytes_.empty()) return OwnedVector<byte>();
178 DCHECK(!Omit());
179
180 OwnedVector<byte> table = OwnedVector<byte>::Of(bytes_);
181
182#ifdef ENABLE_SLOW_DCHECKS
183 // Brute force testing: Record all positions and decode
184 // the entire table to verify they are identical.
185 SourcePositionTableIterator it(table.as_vector(),
186 SourcePositionTableIterator::kAll);
187 CheckTableEquals(raw_entries_, it);
188 // No additional source positions after creating the table.
189 mode_ = OMIT_SOURCE_POSITIONS;
190#endif
191 return table;
192}
193
194SourcePositionTableIterator::SourcePositionTableIterator(ByteArray byte_array,
195 IterationFilter filter)
196 : raw_table_(VectorFromByteArray(byte_array)), filter_(filter) {
197 Advance();
198}
199
200SourcePositionTableIterator::SourcePositionTableIterator(
201 Handle<ByteArray> byte_array, IterationFilter filter)
202 : table_(byte_array), filter_(filter) {
203 Advance();
204#ifdef DEBUG
205 // We can enable allocation because we keep the table in a handle.
206 no_gc.Release();
207#endif // DEBUG
208}
209
210SourcePositionTableIterator::SourcePositionTableIterator(
211 Vector<const byte> bytes, IterationFilter filter)
212 : raw_table_(bytes), filter_(filter) {
213 Advance();
214#ifdef DEBUG
215 // We can enable allocation because the underlying vector does not move.
216 no_gc.Release();
217#endif // DEBUG
218}
219
220void SourcePositionTableIterator::Advance() {
221 Vector<const byte> bytes =
222 table_.is_null() ? raw_table_ : VectorFromByteArray(*table_);
223 DCHECK(!done());
224 DCHECK(index_ >= 0 && index_ <= bytes.length());
225 bool filter_satisfied = false;
226 while (!done() && !filter_satisfied) {
227 if (index_ >= bytes.length()) {
228 index_ = kDone;
229 } else {
230 PositionTableEntry tmp;
231 DecodeEntry(bytes, &index_, &tmp);
232 AddAndSetEntry(current_, tmp);
233 SourcePosition p = source_position();
234 filter_satisfied = (filter_ == kAll) ||
235 (filter_ == kJavaScriptOnly && p.IsJavaScript()) ||
236 (filter_ == kExternalOnly && p.IsExternal());
237 }
238 }
239}
240
241} // namespace internal
242} // namespace v8
243