Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
#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 */