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 // We can enable allocation because we keep the table in a handle. 202 no_gc.Release(); 203 } 204 205 SourcePositionTableIterator::SourcePositionTableIterator( 206 Vector<const byte> bytes) 207 : raw_table_(bytes) { 208 Advance(); 209 // We can enable allocation because the underlying vector does not move. 210 no_gc.Release(); 211 } 212 213 void SourcePositionTableIterator::Advance() { 214 Vector<const byte> bytes = 215 table_.is_null() ? raw_table_ : VectorFromByteArray(*table_); 216 DCHECK(!done()); 217 DCHECK(index_ >= 0 && index_ <= bytes.length()); 218 if (index_ >= bytes.length()) { 219 index_ = kDone; 220 } else { 221 PositionTableEntry tmp; 222 DecodeEntry(bytes, &index_, &tmp); 223 AddAndSetEntry(current_, tmp); 224 } 225 } 226 227 } // namespace internal 228 } // namespace v8 229