Home | History | Annotate | Download | only in src 
      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 
     11 namespace v8 {
     12 namespace 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 
     28 namespace {
     29 
     30 // Each byte is encoded as MoreBit | ValueBits.
     31 class MoreBit : public BitField8<bool, 7, 1> {};
     32 class ValueBits : public BitField8<unsigned, 0, 7> {};
     33 
     34 // Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
     35 void 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'.
     43 void 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.
     50 template <typename T>
     51 void 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.
     68 void 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.
     78 template <typename T>
     79 T 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 
     97 void 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 
    111 SourcePositionTableBuilder::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 
    121 void 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 
    130 void 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 
    140 Handle<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 
    170 SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
    171     : table_(byte_array), index_(0), current_() {
    172   Advance();
    173 }
    174 
    175 void 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