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/codegen/source-position-table.h"
6
7#include "src/base/export-template.h"
8#include "src/base/logging.h"
9#include "src/common/assert-scope.h"
10#include "src/heap/local-factory-inl.h"
11#include "src/objects/objects-inl.h"
12#include "src/objects/objects.h"
13
14namespace v8 {
15namespace internal {
16
17// We'll use a simple encoding scheme to record the source positions.
18// Conceptually, each position consists of:
19// - code_offset: An integer index into the BytecodeArray or code.
20// - source_position: An integer index into the source string.
21// - position type: Each position is either a statement or an expression.
22//
23// The basic idea for the encoding is to use a variable-length integer coding,
24// where each byte contains 7 bits of payload data, and 1 'more' bit that
25// determines whether additional bytes follow. Additionally:
26// - we record the difference from the previous position,
27// - we just stuff one bit for the type into the code offset,
28// - we write least-significant bits first,
29// - we use zig-zag encoding to encode both positive and negative numbers.
30
31namespace {
32
33// Each byte is encoded as MoreBit | ValueBits.
34using MoreBit = base::BitField8<bool, 7, 1>;
35using ValueBits = base::BitField8<unsigned, 0, 7>;
36
37// Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
38void AddAndSetEntry(PositionTableEntry* value,
39                    const PositionTableEntry& other) {
40  value->code_offset += other.code_offset;
41  DCHECK_IMPLIES(value->code_offset != kFunctionEntryBytecodeOffset,
42                 value->code_offset >= 0);
43  value->source_position += other.source_position;
44  DCHECK_LE(0, value->source_position);
45  value->is_statement = other.is_statement;
46}
47
48// Helper: Subtract the offsets from 'other' from 'value'.
49void SubtractFromEntry(PositionTableEntry* value,
50                       const PositionTableEntry& other) {
51  value->code_offset -= other.code_offset;
52  value->source_position -= other.source_position;
53}
54
55// Helper: Encode an integer.
56template <typename T>
57void EncodeInt(ZoneVector<byte>* bytes, T value) {
58  using unsigned_type = typename std::make_unsigned<T>::type;
59  // Zig-zag encoding.
60  static constexpr int kShift = sizeof(T) * kBitsPerByte - 1;
61  value = ((static_cast<unsigned_type>(value) << 1) ^ (value >> kShift));
62  DCHECK_GE(value, 0);
63  unsigned_type encoded = static_cast<unsigned_type>(value);
64  bool more;
65  do {
66    more = encoded > ValueBits::kMax;
67    byte current =
68        MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
69    bytes->push_back(current);
70    encoded >>= ValueBits::kSize;
71  } while (more);
72}
73
74// Encode a PositionTableEntry.
75void EncodeEntry(ZoneVector<byte>* bytes, const PositionTableEntry& entry) {
76  // We only accept ascending code offsets.
77  DCHECK_LE(0, entry.code_offset);
78  // All but the first entry must be *strictly* ascending (no two entries for
79  // the same position).
80  // TODO(11496): This DCHECK fails tests.
81  // DCHECK_IMPLIES(!bytes->empty(), entry.code_offset > 0);
82  // Since code_offset is not negative, we use sign to encode is_statement.
83  EncodeInt(bytes,
84            entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
85  EncodeInt(bytes, entry.source_position);
86}
87
88// Helper: Decode an integer.
89template <typename T>
90T DecodeInt(base::Vector<const byte> bytes, int* index) {
91  byte current;
92  int shift = 0;
93  T decoded = 0;
94  bool more;
95  do {
96    current = bytes[(*index)++];
97    decoded |= static_cast<typename std::make_unsigned<T>::type>(
98                   ValueBits::decode(current))
99               << shift;
100    more = MoreBit::decode(current);
101    shift += ValueBits::kSize;
102  } while (more);
103  DCHECK_GE(decoded, 0);
104  decoded = (decoded >> 1) ^ (-(decoded & 1));
105  return decoded;
106}
107
108void DecodeEntry(base::Vector<const byte> bytes, int* index,
109                 PositionTableEntry* entry) {
110  int tmp = DecodeInt<int>(bytes, index);
111  if (tmp >= 0) {
112    entry->is_statement = true;
113    entry->code_offset = tmp;
114  } else {
115    entry->is_statement = false;
116    entry->code_offset = -(tmp + 1);
117  }
118  entry->source_position = DecodeInt<int64_t>(bytes, index);
119}
120
121base::Vector<const byte> VectorFromByteArray(ByteArray byte_array) {
122  return base::Vector<const byte>(byte_array.GetDataStartAddress(),
123                                  byte_array.length());
124}
125
126#ifdef ENABLE_SLOW_DCHECKS
127void CheckTableEquals(const ZoneVector<PositionTableEntry>& raw_entries,
128                      SourcePositionTableIterator* encoded) {
129  // Brute force testing: Record all positions and decode
130  // the entire table to verify they are identical.
131  auto raw = raw_entries.begin();
132  for (; !encoded->done(); encoded->Advance(), raw++) {
133    DCHECK(raw != raw_entries.end());
134    DCHECK_EQ(encoded->code_offset(), raw->code_offset);
135    DCHECK_EQ(encoded->source_position().raw(), raw->source_position);
136    DCHECK_EQ(encoded->is_statement(), raw->is_statement);
137  }
138  DCHECK(raw == raw_entries.end());
139}
140#endif
141
142}  // namespace
143
144SourcePositionTableBuilder::SourcePositionTableBuilder(
145    Zone* zone, SourcePositionTableBuilder::RecordingMode mode)
146    : mode_(mode),
147      bytes_(zone),
148#ifdef ENABLE_SLOW_DCHECKS
149      raw_entries_(zone),
150#endif
151      previous_() {
152}
153
154void SourcePositionTableBuilder::AddPosition(size_t code_offset,
155                                             SourcePosition source_position,
156                                             bool is_statement) {
157  if (Omit()) return;
158  DCHECK(source_position.IsKnown());
159  int offset = static_cast<int>(code_offset);
160  AddEntry({offset, source_position.raw(), is_statement});
161}
162
163void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
164  PositionTableEntry tmp(entry);
165  SubtractFromEntry(&tmp, previous_);
166  EncodeEntry(&bytes_, tmp);
167  previous_ = entry;
168#ifdef ENABLE_SLOW_DCHECKS
169  raw_entries_.push_back(entry);
170#endif
171}
172
173template <typename IsolateT>
174Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
175    IsolateT* isolate) {
176  if (bytes_.empty()) return isolate->factory()->empty_byte_array();
177  DCHECK(!Omit());
178
179  Handle<ByteArray> table = isolate->factory()->NewByteArray(
180      static_cast<int>(bytes_.size()), AllocationType::kOld);
181  MemCopy(table->GetDataStartAddress(), bytes_.data(), bytes_.size());
182
183#ifdef ENABLE_SLOW_DCHECKS
184  // Brute force testing: Record all positions and decode
185  // the entire table to verify they are identical.
186  SourcePositionTableIterator it(
187      *table, SourcePositionTableIterator::kAll,
188      SourcePositionTableIterator::kDontSkipFunctionEntry);
189  CheckTableEquals(raw_entries_, &it);
190  // No additional source positions after creating the table.
191  mode_ = OMIT_SOURCE_POSITIONS;
192#endif
193  return table;
194}
195
196template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
197    Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
198        Isolate* isolate);
199template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
200    Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
201        LocalIsolate* isolate);
202
203base::OwnedVector<byte>
204SourcePositionTableBuilder::ToSourcePositionTableVector() {
205  if (bytes_.empty()) return base::OwnedVector<byte>();
206  DCHECK(!Omit());
207
208  base::OwnedVector<byte> table = base::OwnedVector<byte>::Of(bytes_);
209
210#ifdef ENABLE_SLOW_DCHECKS
211  // Brute force testing: Record all positions and decode
212  // the entire table to verify they are identical.
213  SourcePositionTableIterator it(
214      table.as_vector(), SourcePositionTableIterator::kAll,
215      SourcePositionTableIterator::kDontSkipFunctionEntry);
216  CheckTableEquals(raw_entries_, &it);
217  // No additional source positions after creating the table.
218  mode_ = OMIT_SOURCE_POSITIONS;
219#endif
220  return table;
221}
222
223void SourcePositionTableIterator::Initialize() {
224  Advance();
225  if (function_entry_filter_ == kSkipFunctionEntry &&
226      current_.code_offset == kFunctionEntryBytecodeOffset && !done()) {
227    Advance();
228  }
229}
230
231SourcePositionTableIterator::SourcePositionTableIterator(
232    ByteArray byte_array, IterationFilter iteration_filter,
233    FunctionEntryFilter function_entry_filter)
234    : raw_table_(VectorFromByteArray(byte_array)),
235      iteration_filter_(iteration_filter),
236      function_entry_filter_(function_entry_filter) {
237  Initialize();
238}
239
240SourcePositionTableIterator::SourcePositionTableIterator(
241    Handle<ByteArray> byte_array, IterationFilter iteration_filter,
242    FunctionEntryFilter function_entry_filter)
243    : table_(byte_array),
244      iteration_filter_(iteration_filter),
245      function_entry_filter_(function_entry_filter) {
246  Initialize();
247#ifdef DEBUG
248  // We can enable allocation because we keep the table in a handle.
249  no_gc.Release();
250#endif  // DEBUG
251}
252
253SourcePositionTableIterator::SourcePositionTableIterator(
254    base::Vector<const byte> bytes, IterationFilter iteration_filter,
255    FunctionEntryFilter function_entry_filter)
256    : raw_table_(bytes),
257      iteration_filter_(iteration_filter),
258      function_entry_filter_(function_entry_filter) {
259  Initialize();
260#ifdef DEBUG
261  // We can enable allocation because the underlying vector does not move.
262  no_gc.Release();
263#endif  // DEBUG
264}
265
266void SourcePositionTableIterator::Advance() {
267  base::Vector<const byte> bytes =
268      table_.is_null() ? raw_table_ : VectorFromByteArray(*table_);
269  DCHECK(!done());
270  DCHECK(index_ >= 0 && index_ <= bytes.length());
271  bool filter_satisfied = false;
272  while (!done() && !filter_satisfied) {
273    if (index_ >= bytes.length()) {
274      index_ = kDone;
275    } else {
276      PositionTableEntry tmp;
277      DecodeEntry(bytes, &index_, &tmp);
278      AddAndSetEntry(&current_, tmp);
279      SourcePosition p = source_position();
280      filter_satisfied =
281          (iteration_filter_ == kAll) ||
282          (iteration_filter_ == kJavaScriptOnly && p.IsJavaScript()) ||
283          (iteration_filter_ == kExternalOnly && p.IsExternal());
284    }
285  }
286}
287
288}  // namespace internal
289}  // namespace v8
290