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/log.h"
8#include "src/objects-inl.h"
9#include "src/objects.h"
10
11namespace v8 {
12namespace internal {
13
14// We'll use a simple encoding scheme to record the source positions.
15// Conceptually, each position consists of:
16// - code_offset: An integer index into the BytecodeArray or code.
17// - source_position: An integer index into the source string.
18// - position type: Each position is either a statement or an expression.
19//
20// The basic idea for the encoding is to use a variable-length integer coding,
21// where each byte contains 7 bits of payload data, and 1 'more' bit that
22// determines whether additional bytes follow. Additionally:
23// - we record the difference from the previous position,
24// - we just stuff one bit for the type into the code offset,
25// - we write least-significant bits first,
26// - we use zig-zag encoding to encode both positive and negative numbers.
27
28namespace {
29
30// Each byte is encoded as MoreBit | ValueBits.
31class MoreBit : public BitField8<bool, 7, 1> {};
32class ValueBits : public BitField8<unsigned, 0, 7> {};
33
34// Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
35void AddAndSetEntry(PositionTableEntry& value,
36                    const PositionTableEntry& other) {
37  value.code_offset += other.code_offset;
38  value.source_position += other.source_position;
39  value.is_statement = other.is_statement;
40}
41
42// Helper: Substract the offsets from 'other' from 'value'.
43void SubtractFromEntry(PositionTableEntry& value,
44                       const PositionTableEntry& other) {
45  value.code_offset -= other.code_offset;
46  value.source_position -= other.source_position;
47}
48
49// Helper: Encode an integer.
50template <typename T>
51void EncodeInt(ZoneVector<byte>& bytes, T value) {
52  // Zig-zag encoding.
53  static const int kShift = sizeof(T) * kBitsPerByte - 1;
54  value = ((value << 1) ^ (value >> kShift));
55  DCHECK_GE(value, 0);
56  auto encoded = static_cast<typename std::make_unsigned<T>::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(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
69  // We only accept ascending code offsets.
70  DCHECK(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(ByteArray* bytes, int* index) {
80  byte current;
81  int shift = 0;
82  T decoded = 0;
83  bool more;
84  do {
85    current = bytes->get((*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(ByteArray* bytes, int* index, 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}  // namespace
110
111SourcePositionTableBuilder::SourcePositionTableBuilder(
112    Zone* zone, SourcePositionTableBuilder::RecordingMode mode)
113    : mode_(mode),
114      bytes_(zone),
115#ifdef ENABLE_SLOW_DCHECKS
116      raw_entries_(zone),
117#endif
118      previous_() {
119}
120
121void SourcePositionTableBuilder::AddPosition(size_t code_offset,
122                                             SourcePosition source_position,
123                                             bool is_statement) {
124  if (Omit()) return;
125  DCHECK(source_position.IsKnown());
126  int offset = static_cast<int>(code_offset);
127  AddEntry({offset, source_position.raw(), is_statement});
128}
129
130void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
131  PositionTableEntry tmp(entry);
132  SubtractFromEntry(tmp, previous_);
133  EncodeEntry(bytes_, tmp);
134  previous_ = entry;
135#ifdef ENABLE_SLOW_DCHECKS
136  raw_entries_.push_back(entry);
137#endif
138}
139
140Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
141    Isolate* isolate, Handle<AbstractCode> code) {
142  if (bytes_.empty()) return isolate->factory()->empty_byte_array();
143  DCHECK(!Omit());
144
145  Handle<ByteArray> table = isolate->factory()->NewByteArray(
146      static_cast<int>(bytes_.size()), TENURED);
147
148  MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size());
149
150  LOG_CODE_EVENT(isolate, CodeLinePosInfoRecordEvent(*code, *table));
151
152#ifdef ENABLE_SLOW_DCHECKS
153  // Brute force testing: Record all positions and decode
154  // the entire table to verify they are identical.
155  auto raw = raw_entries_.begin();
156  for (SourcePositionTableIterator encoded(*table); !encoded.done();
157       encoded.Advance(), raw++) {
158    DCHECK(raw != raw_entries_.end());
159    DCHECK_EQ(encoded.code_offset(), raw->code_offset);
160    DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
161    DCHECK_EQ(encoded.is_statement(), raw->is_statement);
162  }
163  DCHECK(raw == raw_entries_.end());
164  // No additional source positions after creating the table.
165  mode_ = OMIT_SOURCE_POSITIONS;
166#endif
167  return table;
168}
169
170SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
171    : table_(byte_array), index_(0), current_() {
172  Advance();
173}
174
175void SourcePositionTableIterator::Advance() {
176  DCHECK(!done());
177  DCHECK(index_ >= 0 && index_ <= table_->length());
178  if (index_ >= table_->length()) {
179    index_ = kDone;
180  } else {
181    PositionTableEntry tmp;
182    DecodeEntry(table_, &index_, &tmp);
183    AddAndSetEntry(current_, tmp);
184  }
185}
186
187}  // namespace internal
188}  // namespace v8
189