Line data Source code
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 116622110 : value.code_offset += other.code_offset;
37 116622110 : value.source_position += other.source_position;
38 116622110 : 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 35972916 : value.code_offset -= other.code_offset;
45 35972916 : value.source_position -= other.source_position;
46 : }
47 :
48 : // Helper: Encode an integer.
49 : template <typename T>
50 71946813 : void 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 71946813 : 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 81495011 : do {
59 81491907 : more = encoded > ValueBits::kMax;
60 : byte current =
61 162983814 : MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
62 81491907 : bytes.push_back(current);
63 81495011 : encoded >>= ValueBits::kSize;
64 : } while (more);
65 71949917 : }
66 :
67 : // Encode a PositionTableEntry.
68 35973377 : void 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 58619445 : EncodeInt(bytes,
73 94592822 : entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
74 35974376 : EncodeInt(bytes, entry.source_position);
75 35975504 : }
76 :
77 : // Helper: Decode an integer.
78 : template <typename T>
79 : T DecodeInt(Vector<const byte> bytes, int* index) {
80 : byte current;
81 : int shift = 0;
82 : T decoded = 0;
83 : bool more;
84 246707035 : do {
85 493414070 : current = bytes[(*index)++];
86 246707035 : decoded |= static_cast<typename std::make_unsigned<T>::type>(
87 : ValueBits::decode(current))
88 : << shift;
89 : more = MoreBit::decode(current);
90 246707035 : shift += ValueBits::kSize;
91 : } while (more);
92 : DCHECK_GE(decoded, 0);
93 233244206 : decoded = (decoded >> 1) ^ (-(decoded & 1));
94 : return decoded;
95 : }
96 :
97 116622103 : void DecodeEntry(Vector<const byte> bytes, int* index,
98 : PositionTableEntry* entry) {
99 : int tmp = DecodeInt<int>(bytes, index);
100 116622103 : if (tmp >= 0) {
101 66990309 : entry->is_statement = true;
102 66990309 : entry->code_offset = tmp;
103 : } else {
104 49631794 : entry->is_statement = false;
105 49631794 : entry->code_offset = -(tmp + 1);
106 : }
107 116622103 : entry->source_position = DecodeInt<int64_t>(bytes, index);
108 116622103 : }
109 :
110 : Vector<const byte> VectorFromByteArray(ByteArray byte_array) {
111 : return Vector<const byte>(byte_array->GetDataStartAddress(),
112 12002018 : byte_array->length());
113 : }
114 :
115 : #ifdef ENABLE_SLOW_DCHECKS
116 : void 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 :
133 5228072 : SourcePositionTableBuilder::SourcePositionTableBuilder(
134 : SourcePositionTableBuilder::RecordingMode mode)
135 10456144 : : mode_(mode), previous_() {}
136 :
137 35972391 : void SourcePositionTableBuilder::AddPosition(size_t code_offset,
138 : SourcePosition source_position,
139 : bool is_statement) {
140 35972391 : if (Omit()) return;
141 : DCHECK(source_position.IsKnown());
142 35972512 : int offset = static_cast<int>(code_offset);
143 35972512 : AddEntry({offset, source_position.raw(), is_statement});
144 : }
145 :
146 35972916 : void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
147 35972916 : PositionTableEntry tmp(entry);
148 : SubtractFromEntry(tmp, previous_);
149 35972916 : EncodeEntry(bytes_, tmp);
150 35975363 : previous_ = entry;
151 : #ifdef ENABLE_SLOW_DCHECKS
152 : raw_entries_.push_back(entry);
153 : #endif
154 35975363 : }
155 :
156 3681310 : Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
157 : Isolate* isolate) {
158 3681310 : if (bytes_.empty()) return isolate->factory()->empty_byte_array();
159 : DCHECK(!Omit());
160 :
161 : Handle<ByteArray> table = isolate->factory()->NewByteArray(
162 2552125 : 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 2552141 : return table;
174 : }
175 :
176 1437307 : OwnedVector<byte> SourcePositionTableBuilder::ToSourcePositionTableVector() {
177 1437307 : if (bytes_.empty()) return OwnedVector<byte>();
178 : DCHECK(!Omit());
179 :
180 272732 : 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 :
194 4279970 : SourcePositionTableIterator::SourcePositionTableIterator(ByteArray byte_array,
195 : IterationFilter filter)
196 12839910 : : raw_table_(VectorFromByteArray(byte_array)), filter_(filter) {
197 4279970 : Advance();
198 4279970 : }
199 :
200 528978 : SourcePositionTableIterator::SourcePositionTableIterator(
201 : Handle<ByteArray> byte_array, IterationFilter filter)
202 1057956 : : table_(byte_array), filter_(filter) {
203 528978 : 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 528985 : }
209 :
210 153282 : SourcePositionTableIterator::SourcePositionTableIterator(
211 : Vector<const byte> bytes, IterationFilter filter)
212 459846 : : raw_table_(bytes), filter_(filter) {
213 153282 : Advance();
214 : #ifdef DEBUG
215 : // We can enable allocation because the underlying vector does not move.
216 : no_gc.Release();
217 : #endif // DEBUG
218 153282 : }
219 :
220 119296674 : void SourcePositionTableIterator::Advance() {
221 : Vector<const byte> bytes =
222 119296674 : table_.is_null() ? raw_table_ : VectorFromByteArray(*table_);
223 : DCHECK(!done());
224 : DCHECK(index_ >= 0 && index_ <= bytes.length());
225 : bool filter_satisfied = false;
226 238593366 : while (!done() && !filter_satisfied) {
227 119296687 : if (index_ >= bytes.length()) {
228 2674582 : index_ = kDone;
229 : } else {
230 : PositionTableEntry tmp;
231 116622105 : DecodeEntry(bytes, &index_, &tmp);
232 : AddAndSetEntry(current_, tmp);
233 : SourcePosition p = source_position();
234 233244218 : filter_satisfied = (filter_ == kAll) ||
235 233243145 : (filter_ == kJavaScriptOnly && p.IsJavaScript()) ||
236 1077 : (filter_ == kExternalOnly && p.IsExternal());
237 : }
238 : }
239 119296679 : }
240 :
241 : } // namespace internal
242 120216 : } // namespace v8
|
