diff options
Diffstat (limited to 'js/src/frontend/SourceNotes.h')
| -rw-r--r-- | js/src/frontend/SourceNotes.h | 524 |
1 files changed, 524 insertions, 0 deletions
diff --git a/js/src/frontend/SourceNotes.h b/js/src/frontend/SourceNotes.h new file mode 100644 index 0000000000..fba1544083 --- /dev/null +++ b/js/src/frontend/SourceNotes.h @@ -0,0 +1,524 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef frontend_SourceNotes_h +#define frontend_SourceNotes_h + +#include "mozilla/Assertions.h" // MOZ_ASSERT + +#include <algorithm> // std::min +#include <stddef.h> // ptrdiff_t, size_t +#include <stdint.h> // int8_t, uint8_t, uint32_t + +#include "jstypes.h" // js::{Bit, BitMask} +#include "js/ColumnNumber.h" // JS::ColumnNumberOffset, JS::LimitedColumnNumberOneOrigin + +namespace js { + +/** + * [SMDOC] Source Notes + * + * Source notes are generated along with bytecode for associating line/column + * to opcode, and annotating opcode as breakpoint for debugging. + * + * A source note is a uint8_t with 4 bits of type and 4 bits of offset from + * the pc of the previous note. If 4 bits of offset aren't enough, extended + * delta notes (XDelta) consisting of 1 set high order bit followed by 7 offset + * bits are emitted before the next note. + * + * Source Note Extended Delta + * +7-6-5-4+3-2-1-0+ +7+6-5-4-3-2-1-0+ + * | type | delta | |1| ext-delta | + * +-------+-------+ +-+-------------+ + * + * Extended Delta with `ext-delta == 0` is used as terminator, which is + * padded between the end of source notes and the next notes in the + * ImmutableScriptData. + * + * Terminator + * +7+6-5-4-3-2-1-0+ + * |1|0 0 0 0 0 0 0| + * +-+-------------+ + * + * Some notes have operand offsets encoded immediately after them. Each operand + * is encoded either in single-byte or 4-bytes, depending on the range. + * + * Single-byte Operand (0 <= operand <= 127) + * + * +7+6-5-4-3-2-1-0+ + * |0| operand | + * +-+-------------+ + * + * 4-bytes Operand (128 <= operand) + * + * (operand_3 << 24) | (operand_2 << 16) | (operand_1 << 8) | operand_0 + * + * +7-6-5-4-3-2-1-0+ +7-6-5-4-3-2-1-0+ +7-6-5-4-3-2-1-0+ +7-6-5-4-3-2-1-0+ + * |1| operand_3 | | operand_2 | | operand_1 | | operand_0 | + * +---------------+ +---------------+ +---------------+ +---------------+ + * + * NB: the js::SrcNote::specs_ array is indexed by this enum, so its + * initializers need to match the order here. + */ + +#define FOR_EACH_SRC_NOTE_TYPE(M) \ + M(ColSpan, "colspan", int8_t(SrcNote::ColSpan::Operands::Count)) \ + /* Bytecode follows a source newline. */ \ + M(NewLine, "newline", 0) \ + M(NewLineColumn, "newlinecolumn", \ + int8_t(SrcNote::NewLineColumn::Operands::Count)) \ + M(SetLine, "setline", int8_t(SrcNote::SetLine::Operands::Count)) \ + M(SetLineColumn, "setlinecolumn", \ + int8_t(SrcNote::SetLineColumn::Operands::Count)) \ + /* Bytecode is a recommended breakpoint. */ \ + M(Breakpoint, "breakpoint", 0) \ + /* Bytecode is a recommended breakpoint, and the first in a */ \ + /* new steppable area. */ \ + M(BreakpointStepSep, "breakpoint-step-sep", 0) \ + M(Unused7, "unused", 0) \ + /* 8-15 (0b1xxx) are for extended delta notes. */ \ + M(XDelta, "xdelta", 0) + +// Note: need to add a new source note? If there's no Unused* note left, +// consider bumping SrcNoteType::XDelta to 12-15 and change +// SrcNote::XDeltaBits from 7 to 6. + +enum class SrcNoteType : uint8_t { +#define DEFINE_SRC_NOTE_TYPE(sym, name, arity) sym, + FOR_EACH_SRC_NOTE_TYPE(DEFINE_SRC_NOTE_TYPE) +#undef DEFINE_SRC_NOTE_TYPE + + Last, +}; + +static_assert(uint8_t(SrcNoteType::XDelta) == 8, "XDelta should be 8"); + +class SrcNote { + struct Spec { + const char* name_; + int8_t arity_; + }; + + static const Spec specs_[]; + + static constexpr unsigned TypeBits = 4; + static constexpr unsigned DeltaBits = 4; + static constexpr unsigned XDeltaBits = 7; + + static constexpr uint8_t TypeMask = js::BitMask(TypeBits) << DeltaBits; + static constexpr ptrdiff_t DeltaMask = js::BitMask(DeltaBits); + static constexpr ptrdiff_t XDeltaMask = js::BitMask(XDeltaBits); + + static constexpr ptrdiff_t DeltaLimit = js::Bit(DeltaBits); + static constexpr ptrdiff_t XDeltaLimit = js::Bit(XDeltaBits); + + static constexpr inline uint8_t toShiftedTypeBits(SrcNoteType type) { + return (uint8_t(type) << DeltaBits); + } + + static inline uint8_t noteValue(SrcNoteType type, ptrdiff_t delta) { + MOZ_ASSERT((delta & DeltaMask) == delta); + return noteValueUnchecked(type, delta); + } + + static constexpr inline uint8_t noteValueUnchecked(SrcNoteType type, + ptrdiff_t delta) { + return toShiftedTypeBits(type) | (delta & DeltaMask); + } + + static inline uint8_t xDeltaValue(ptrdiff_t delta) { + return toShiftedTypeBits(SrcNoteType::XDelta) | (delta & XDeltaMask); + } + + uint8_t value_; + + constexpr explicit SrcNote(uint8_t value) : value_(value) {} + + public: + // A default value for padding. + constexpr SrcNote() : value_(noteValueUnchecked(SrcNoteType::XDelta, 0)) {} + + SrcNote(const SrcNote& other) = default; + SrcNote& operator=(const SrcNote& other) = default; + + SrcNote(SrcNote&& other) = default; + SrcNote& operator=(SrcNote&& other) = default; + + static constexpr SrcNote padding() { return SrcNote(); } + + private: + inline uint8_t typeBits() const { return (value_ >> DeltaBits); } + + inline bool isXDelta() const { + return typeBits() >= uint8_t(SrcNoteType::XDelta); + } + + inline bool isFourBytesOperand() const { + return value_ & FourBytesOperandFlag; + } + + // number of operands + inline unsigned arity() const { + MOZ_ASSERT(uint8_t(type()) < uint8_t(SrcNoteType::Last)); + return specs_[uint8_t(type())].arity_; + } + + public: + inline SrcNoteType type() const { + if (isXDelta()) { + return SrcNoteType::XDelta; + } + return SrcNoteType(typeBits()); + } + + // name for disassembly/debugging output + const char* name() const { + MOZ_ASSERT(uint8_t(type()) < uint8_t(SrcNoteType::Last)); + return specs_[uint8_t(type())].name_; + } + + inline bool isTerminator() const { + return value_ == noteValueUnchecked(SrcNoteType::XDelta, 0); + } + + inline ptrdiff_t delta() const { + if (isXDelta()) { + return value_ & XDeltaMask; + } + return value_ & DeltaMask; + } + + private: + /* + * Operand fields follow certain notes and are frequency-encoded: an operand + * in [0,0x7f] consumes one byte, an operand in [0x80,0x7fffffff] takes four, + * and the high bit of the first byte is set. + */ + static constexpr unsigned FourBytesOperandFlag = 0x80; + static constexpr unsigned FourBytesOperandMask = 0x7f; + + static constexpr unsigned OperandBits = 31; + + public: + static constexpr size_t MaxOperand = (size_t(1) << OperandBits) - 1; + + static inline bool isRepresentableOperand(ptrdiff_t operand) { + return 0 <= operand && size_t(operand) <= MaxOperand; + } + + class ColSpan { + public: + enum class Operands { + // The column span (the diff between the column corresponds to the + // current op and last known column). + Span, + Count + }; + + private: + /* + * SrcNoteType::ColSpan values represent changes to the column number. + * Colspans are signed: negative changes arise in describing constructs like + * for(;;) loops, that generate code in non-source order. (Negative colspans + * also have a history of indicating bugs in updating ParseNodes' source + * locations.) + * + * We store colspans in operands. However, unlike normal operands, colspans + * are signed, so we truncate colspans (toOperand) for storage as + * operands, and sign-extend operands into colspans when we read them + * (fromOperand). + */ + static constexpr ptrdiff_t ColSpanSignBit = 1 << (OperandBits - 1); + + static inline JS::ColumnNumberOffset fromOperand(ptrdiff_t operand) { + // There should be no bits set outside the field we're going to + // sign-extend. + MOZ_ASSERT(!(operand & ~((1U << OperandBits) - 1))); + + // Sign-extend the least significant OperandBits bits. + return JS::ColumnNumberOffset((operand ^ ColSpanSignBit) - + ColSpanSignBit); + } + + public: + static constexpr ptrdiff_t MinColSpan = -ColSpanSignBit; + static constexpr ptrdiff_t MaxColSpan = ColSpanSignBit - 1; + + static inline ptrdiff_t toOperand(JS::ColumnNumberOffset colspan) { + // Truncate the two's complement colspan, for storage as an operand. + ptrdiff_t operand = colspan.value() & ((1U << OperandBits) - 1); + + // When we read this back, we'd better get the value we stored. + MOZ_ASSERT(fromOperand(operand) == colspan); + return operand; + } + + static inline JS::ColumnNumberOffset getSpan(const SrcNote* sn); + }; + + class NewLineColumn { + public: + enum class Operands { Column, Count }; + + private: + static inline JS::LimitedColumnNumberOneOrigin fromOperand( + ptrdiff_t operand) { + return JS::LimitedColumnNumberOneOrigin(operand); + } + + public: + static inline ptrdiff_t toOperand(JS::LimitedColumnNumberOneOrigin column) { + return column.oneOriginValue(); + } + + static inline JS::LimitedColumnNumberOneOrigin getColumn(const SrcNote* sn); + }; + + class SetLine { + public: + enum class Operands { + // The file-absolute source line number of the current op. + Line, + Count + }; + + private: + static inline size_t fromOperand(ptrdiff_t operand) { + return size_t(operand); + } + + public: + static inline unsigned lengthFor(unsigned line, size_t initialLine) { + unsigned operandSize = toOperand(line, initialLine) > + ptrdiff_t(SrcNote::FourBytesOperandMask) + ? 4 + : 1; + return 1 /* SetLine */ + operandSize; + } + + static inline ptrdiff_t toOperand(size_t line, size_t initialLine) { + MOZ_ASSERT(line >= initialLine); + return ptrdiff_t(line - initialLine); + } + + static inline size_t getLine(const SrcNote* sn, size_t initialLine); + }; + + class SetLineColumn { + public: + enum class Operands { Line, Column, Count }; + + private: + static inline size_t lineFromOperand(ptrdiff_t operand) { + return size_t(operand); + } + + static inline JS::LimitedColumnNumberOneOrigin columnFromOperand( + ptrdiff_t operand) { + return JS::LimitedColumnNumberOneOrigin(operand); + } + + public: + static inline ptrdiff_t columnToOperand( + JS::LimitedColumnNumberOneOrigin column) { + return column.oneOriginValue(); + } + + static inline size_t getLine(const SrcNote* sn, size_t initialLine); + static inline JS::LimitedColumnNumberOneOrigin getColumn(const SrcNote* sn); + }; + + friend class SrcNoteWriter; + friend class SrcNoteReader; + friend class SrcNoteIterator; +}; + +class SrcNoteWriter { + public: + // Write a source note with given `type`, and `delta` from the last source + // note. This writes the source note itself, and `XDelta`s if necessary. + // + // This doesn't write or allocate space for operands. + // If the source note is not nullary, the caller is responsible for calling + // `writeOperand` immediately after this. + // + // `allocator` is called with the number of bytes required to store the notes. + // `allocator` can be called multiple times for each source note. + // The last call corresponds to the source note for `type`. + template <typename T> + static bool writeNote(SrcNoteType type, ptrdiff_t delta, T allocator) { + while (delta >= SrcNote::DeltaLimit) { + ptrdiff_t xdelta = std::min(delta, SrcNote::XDeltaMask); + SrcNote* sn = allocator(1); + if (!sn) { + return false; + } + sn->value_ = SrcNote::xDeltaValue(xdelta); + delta -= xdelta; + } + + SrcNote* sn = allocator(1); + if (!sn) { + return false; + } + sn->value_ = SrcNote::noteValue(type, delta); + return true; + } + + static void convertNote(SrcNote* sn, SrcNoteType newType) { + ptrdiff_t delta = sn->delta(); + sn->value_ = SrcNote::noteValue(newType, delta); + } + + // Write source note operand. + // + // `allocator` is called with the number of bytes required to store the + // operand. `allocator` is called only once. + template <typename T> + static bool writeOperand(ptrdiff_t operand, T allocator) { + if (operand > ptrdiff_t(SrcNote::FourBytesOperandMask)) { + SrcNote* sn = allocator(4); + if (!sn) { + return false; + } + + sn[0].value_ = (SrcNote::FourBytesOperandFlag | (operand >> 24)); + sn[1].value_ = operand >> 16; + sn[2].value_ = operand >> 8; + sn[3].value_ = operand; + } else { + SrcNote* sn = allocator(1); + if (!sn) { + return false; + } + + sn[0].value_ = operand; + } + + return true; + } +}; + +class SrcNoteReader { + template <typename T> + static T getOperandHead(T sn, unsigned which) { + MOZ_ASSERT(sn->type() != SrcNoteType::XDelta); + MOZ_ASSERT(uint8_t(which) < sn->arity()); + + T curr = sn + 1; + for (; which; which--) { + if (curr->isFourBytesOperand()) { + curr += 4; + } else { + curr++; + } + } + return curr; + } + + public: + // Return the operand of source note `sn`, specified by `which`. + static ptrdiff_t getOperand(const SrcNote* sn, unsigned which) { + const SrcNote* head = getOperandHead(sn, which); + + if (head->isFourBytesOperand()) { + return ptrdiff_t( + (uint32_t(head[0].value_ & SrcNote::FourBytesOperandMask) << 24) | + (uint32_t(head[1].value_) << 16) | (uint32_t(head[2].value_) << 8) | + uint32_t(head[3].value_)); + } + + return ptrdiff_t(head[0].value_); + } +}; + +/* static */ +inline JS::ColumnNumberOffset SrcNote::ColSpan::getSpan(const SrcNote* sn) { + return fromOperand(SrcNoteReader::getOperand(sn, unsigned(Operands::Span))); +} + +/* static */ +inline JS::LimitedColumnNumberOneOrigin SrcNote::NewLineColumn::getColumn( + const SrcNote* sn) { + return fromOperand(SrcNoteReader::getOperand(sn, unsigned(Operands::Column))); +} + +/* static */ +inline size_t SrcNote::SetLine::getLine(const SrcNote* sn, size_t initialLine) { + return initialLine + + fromOperand(SrcNoteReader::getOperand(sn, unsigned(Operands::Line))); +} + +/* static */ +inline size_t SrcNote::SetLineColumn::getLine(const SrcNote* sn, + size_t initialLine) { + return initialLine + lineFromOperand(SrcNoteReader::getOperand( + sn, unsigned(Operands::Line))); +} + +/* static */ +inline JS::LimitedColumnNumberOneOrigin SrcNote::SetLineColumn::getColumn( + const SrcNote* sn) { + return columnFromOperand( + SrcNoteReader::getOperand(sn, unsigned(Operands::Column))); +} + +// Iterate over SrcNote array, until it hits terminator. +// +// Usage: +// for (SrcNoteIterator iter(notes); !iter.atEnd(); ++iter) { +// auto sn = *iter; // `sn` is `const SrcNote*` typed. +// ... +// } +class SrcNoteIterator { + const SrcNote* current_; + const SrcNote* end_; + + void next() { + unsigned arity = current_->arity(); + current_++; + + for (; arity; arity--) { + if (current_->isFourBytesOperand()) { + current_ += 4; + } else { + current_++; + } + } + } + + public: + SrcNoteIterator() = delete; + + SrcNoteIterator(const SrcNoteIterator& other) = delete; + SrcNoteIterator& operator=(const SrcNoteIterator& other) = delete; + + SrcNoteIterator(SrcNoteIterator&& other) = default; + SrcNoteIterator& operator=(SrcNoteIterator&& other) = default; + + SrcNoteIterator(const SrcNote* sn, const SrcNote* end) + : current_(sn), end_(end) {} + + bool atEnd() const { + MOZ_ASSERT(current_ <= end_); + return current_ == end_ || current_->isTerminator(); + } + + const SrcNote* operator*() const { return current_; } + + // Pre-increment + SrcNoteIterator& operator++() { + next(); + return *this; + } + + // Post-increment + SrcNoteIterator operator++(int) = delete; +}; + +} // namespace js + +#endif /* frontend_SourceNotes_h */ |