1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef frontend_SourceNotes_h
8 #define frontend_SourceNotes_h
10 #include "mozilla/Assertions.h" // MOZ_ASSERT
12 #include <algorithm> // std::min
13 #include <stddef.h> // ptrdiff_t, size_t
14 #include <stdint.h> // int8_t, uint8_t, uint32_t
16 #include "jstypes.h" // js::{Bit, BitMask}
17 #include "js/ColumnNumber.h" // JS::ColumnNumberOffset, JS::LimitedColumnNumberOneOrigin
22 * [SMDOC] Source Notes
24 * Source notes are generated along with bytecode for associating line/column
25 * to opcode, and annotating opcode as breakpoint for debugging.
27 * A source note is a uint8_t with 4 bits of type and 4 bits of offset from
28 * the pc of the previous note. If 4 bits of offset aren't enough, extended
29 * delta notes (XDelta) consisting of 1 set high order bit followed by 7 offset
30 * bits are emitted before the next note.
32 * Source Note Extended Delta
33 * +7-6-5-4+3-2-1-0+ +7+6-5-4-3-2-1-0+
34 * | type | delta | |1| ext-delta |
35 * +-------+-------+ +-+-------------+
37 * Extended Delta with `ext-delta == 0` is used as terminator, which is
38 * padded between the end of source notes and the next notes in the
39 * ImmutableScriptData.
46 * Some notes have operand offsets encoded immediately after them. Each operand
47 * is encoded either in single-byte or 4-bytes, depending on the range.
49 * Single-byte Operand (0 <= operand <= 127)
55 * 4-bytes Operand (128 <= operand)
57 * (operand_3 << 24) | (operand_2 << 16) | (operand_1 << 8) | operand_0
59 * +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+
60 * |1| operand_3 | | operand_2 | | operand_1 | | operand_0 |
61 * +---------------+ +---------------+ +---------------+ +---------------+
63 * NB: the js::SrcNote::specs_ array is indexed by this enum, so its
64 * initializers need to match the order here.
67 #define FOR_EACH_SRC_NOTE_TYPE(M) \
68 M(ColSpan, "colspan", int8_t(SrcNote::ColSpan::Operands::Count)) \
69 /* Bytecode follows a source newline. */ \
70 M(NewLine, "newline", 0) \
71 M(NewLineColumn, "newlinecolumn", \
72 int8_t(SrcNote::NewLineColumn::Operands::Count)) \
73 M(SetLine, "setline", int8_t(SrcNote::SetLine::Operands::Count)) \
74 M(SetLineColumn, "setlinecolumn", \
75 int8_t(SrcNote::SetLineColumn::Operands::Count)) \
76 /* Bytecode is a recommended breakpoint. */ \
77 M(Breakpoint, "breakpoint", 0) \
78 /* Bytecode is a recommended breakpoint, and the first in a */ \
79 /* new steppable area. */ \
80 M(BreakpointStepSep, "breakpoint-step-sep", 0) \
81 M(Unused7, "unused", 0) \
82 /* 8-15 (0b1xxx) are for extended delta notes. */ \
83 M(XDelta, "xdelta", 0)
85 // Note: need to add a new source note? If there's no Unused* note left,
86 // consider bumping SrcNoteType::XDelta to 12-15 and change
87 // SrcNote::XDeltaBits from 7 to 6.
89 enum class SrcNoteType
: uint8_t {
90 #define DEFINE_SRC_NOTE_TYPE(sym, name, arity) sym,
91 FOR_EACH_SRC_NOTE_TYPE(DEFINE_SRC_NOTE_TYPE
)
92 #undef DEFINE_SRC_NOTE_TYPE
97 static_assert(uint8_t(SrcNoteType::XDelta
) == 8, "XDelta should be 8");
105 static const Spec specs_
[];
107 static constexpr unsigned TypeBits
= 4;
108 static constexpr unsigned DeltaBits
= 4;
109 static constexpr unsigned XDeltaBits
= 7;
111 static constexpr uint8_t TypeMask
= js::BitMask(TypeBits
) << DeltaBits
;
112 static constexpr ptrdiff_t DeltaMask
= js::BitMask(DeltaBits
);
113 static constexpr ptrdiff_t XDeltaMask
= js::BitMask(XDeltaBits
);
115 static constexpr ptrdiff_t DeltaLimit
= js::Bit(DeltaBits
);
116 static constexpr ptrdiff_t XDeltaLimit
= js::Bit(XDeltaBits
);
118 static constexpr inline uint8_t toShiftedTypeBits(SrcNoteType type
) {
119 return (uint8_t(type
) << DeltaBits
);
122 static inline uint8_t noteValue(SrcNoteType type
, ptrdiff_t delta
) {
123 MOZ_ASSERT((delta
& DeltaMask
) == delta
);
124 return noteValueUnchecked(type
, delta
);
127 static constexpr inline uint8_t noteValueUnchecked(SrcNoteType type
,
129 return toShiftedTypeBits(type
) | (delta
& DeltaMask
);
132 static inline uint8_t xDeltaValue(ptrdiff_t delta
) {
133 return toShiftedTypeBits(SrcNoteType::XDelta
) | (delta
& XDeltaMask
);
138 constexpr explicit SrcNote(uint8_t value
) : value_(value
) {}
141 // A default value for padding.
142 constexpr SrcNote() : value_(noteValueUnchecked(SrcNoteType::XDelta
, 0)) {}
144 SrcNote(const SrcNote
& other
) = default;
145 SrcNote
& operator=(const SrcNote
& other
) = default;
147 SrcNote(SrcNote
&& other
) = default;
148 SrcNote
& operator=(SrcNote
&& other
) = default;
150 static constexpr SrcNote
padding() { return SrcNote(); }
153 inline uint8_t typeBits() const { return (value_
>> DeltaBits
); }
155 inline bool isXDelta() const {
156 return typeBits() >= uint8_t(SrcNoteType::XDelta
);
159 inline bool isFourBytesOperand() const {
160 return value_
& FourBytesOperandFlag
;
163 // number of operands
164 inline unsigned arity() const {
165 MOZ_ASSERT(uint8_t(type()) < uint8_t(SrcNoteType::Last
));
166 return specs_
[uint8_t(type())].arity_
;
170 inline SrcNoteType
type() const {
172 return SrcNoteType::XDelta
;
174 return SrcNoteType(typeBits());
177 // name for disassembly/debugging output
178 const char* name() const {
179 MOZ_ASSERT(uint8_t(type()) < uint8_t(SrcNoteType::Last
));
180 return specs_
[uint8_t(type())].name_
;
183 inline bool isTerminator() const {
184 return value_
== noteValueUnchecked(SrcNoteType::XDelta
, 0);
187 inline ptrdiff_t delta() const {
189 return value_
& XDeltaMask
;
191 return value_
& DeltaMask
;
196 * Operand fields follow certain notes and are frequency-encoded: an operand
197 * in [0,0x7f] consumes one byte, an operand in [0x80,0x7fffffff] takes four,
198 * and the high bit of the first byte is set.
200 static constexpr unsigned FourBytesOperandFlag
= 0x80;
201 static constexpr unsigned FourBytesOperandMask
= 0x7f;
203 static constexpr unsigned OperandBits
= 31;
206 static constexpr size_t MaxOperand
= (size_t(1) << OperandBits
) - 1;
208 static inline bool isRepresentableOperand(ptrdiff_t operand
) {
209 return 0 <= operand
&& size_t(operand
) <= MaxOperand
;
214 enum class Operands
{
215 // The column span (the diff between the column corresponds to the
216 // current op and last known column).
223 * SrcNoteType::ColSpan values represent changes to the column number.
224 * Colspans are signed: negative changes arise in describing constructs like
225 * for(;;) loops, that generate code in non-source order. (Negative colspans
226 * also have a history of indicating bugs in updating ParseNodes' source
229 * We store colspans in operands. However, unlike normal operands, colspans
230 * are signed, so we truncate colspans (toOperand) for storage as
231 * operands, and sign-extend operands into colspans when we read them
234 static constexpr ptrdiff_t ColSpanSignBit
= 1 << (OperandBits
- 1);
236 static inline JS::ColumnNumberOffset
fromOperand(ptrdiff_t operand
) {
237 // There should be no bits set outside the field we're going to
239 MOZ_ASSERT(!(operand
& ~((1U << OperandBits
) - 1)));
241 // Sign-extend the least significant OperandBits bits.
242 return JS::ColumnNumberOffset((operand
^ ColSpanSignBit
) -
247 static constexpr ptrdiff_t MinColSpan
= -ColSpanSignBit
;
248 static constexpr ptrdiff_t MaxColSpan
= ColSpanSignBit
- 1;
250 static inline ptrdiff_t toOperand(JS::ColumnNumberOffset colspan
) {
251 // Truncate the two's complement colspan, for storage as an operand.
252 ptrdiff_t operand
= colspan
.value() & ((1U << OperandBits
) - 1);
254 // When we read this back, we'd better get the value we stored.
255 MOZ_ASSERT(fromOperand(operand
) == colspan
);
259 static inline JS::ColumnNumberOffset
getSpan(const SrcNote
* sn
);
262 class NewLineColumn
{
264 enum class Operands
{ Column
, Count
};
267 static inline JS::LimitedColumnNumberOneOrigin
fromOperand(
269 return JS::LimitedColumnNumberOneOrigin(operand
);
273 static inline ptrdiff_t toOperand(JS::LimitedColumnNumberOneOrigin column
) {
274 return column
.oneOriginValue();
277 static inline JS::LimitedColumnNumberOneOrigin
getColumn(const SrcNote
* sn
);
282 enum class Operands
{
283 // The file-absolute source line number of the current op.
289 static inline size_t fromOperand(ptrdiff_t operand
) {
290 return size_t(operand
);
294 static inline unsigned lengthFor(unsigned line
, size_t initialLine
) {
295 unsigned operandSize
= toOperand(line
, initialLine
) >
296 ptrdiff_t(SrcNote::FourBytesOperandMask
)
299 return 1 /* SetLine */ + operandSize
;
302 static inline ptrdiff_t toOperand(size_t line
, size_t initialLine
) {
303 MOZ_ASSERT(line
>= initialLine
);
304 return ptrdiff_t(line
- initialLine
);
307 static inline size_t getLine(const SrcNote
* sn
, size_t initialLine
);
310 class SetLineColumn
{
312 enum class Operands
{ Line
, Column
, Count
};
315 static inline size_t lineFromOperand(ptrdiff_t operand
) {
316 return size_t(operand
);
319 static inline JS::LimitedColumnNumberOneOrigin
columnFromOperand(
321 return JS::LimitedColumnNumberOneOrigin(operand
);
325 static inline ptrdiff_t columnToOperand(
326 JS::LimitedColumnNumberOneOrigin column
) {
327 return column
.oneOriginValue();
330 static inline size_t getLine(const SrcNote
* sn
, size_t initialLine
);
331 static inline JS::LimitedColumnNumberOneOrigin
getColumn(const SrcNote
* sn
);
334 friend class SrcNoteWriter
;
335 friend class SrcNoteReader
;
336 friend class SrcNoteIterator
;
339 class SrcNoteWriter
{
341 // Write a source note with given `type`, and `delta` from the last source
342 // note. This writes the source note itself, and `XDelta`s if necessary.
344 // This doesn't write or allocate space for operands.
345 // If the source note is not nullary, the caller is responsible for calling
346 // `writeOperand` immediately after this.
348 // `allocator` is called with the number of bytes required to store the notes.
349 // `allocator` can be called multiple times for each source note.
350 // The last call corresponds to the source note for `type`.
351 template <typename T
>
352 static bool writeNote(SrcNoteType type
, ptrdiff_t delta
, T allocator
) {
353 while (delta
>= SrcNote::DeltaLimit
) {
354 ptrdiff_t xdelta
= std::min(delta
, SrcNote::XDeltaMask
);
355 SrcNote
* sn
= allocator(1);
359 sn
->value_
= SrcNote::xDeltaValue(xdelta
);
363 SrcNote
* sn
= allocator(1);
367 sn
->value_
= SrcNote::noteValue(type
, delta
);
371 static void convertNote(SrcNote
* sn
, SrcNoteType newType
) {
372 ptrdiff_t delta
= sn
->delta();
373 sn
->value_
= SrcNote::noteValue(newType
, delta
);
376 // Write source note operand.
378 // `allocator` is called with the number of bytes required to store the
379 // operand. `allocator` is called only once.
380 template <typename T
>
381 static bool writeOperand(ptrdiff_t operand
, T allocator
) {
382 if (operand
> ptrdiff_t(SrcNote::FourBytesOperandMask
)) {
383 SrcNote
* sn
= allocator(4);
388 sn
[0].value_
= (SrcNote::FourBytesOperandFlag
| (operand
>> 24));
389 sn
[1].value_
= operand
>> 16;
390 sn
[2].value_
= operand
>> 8;
391 sn
[3].value_
= operand
;
393 SrcNote
* sn
= allocator(1);
398 sn
[0].value_
= operand
;
405 class SrcNoteReader
{
406 template <typename T
>
407 static T
getOperandHead(T sn
, unsigned which
) {
408 MOZ_ASSERT(sn
->type() != SrcNoteType::XDelta
);
409 MOZ_ASSERT(uint8_t(which
) < sn
->arity());
412 for (; which
; which
--) {
413 if (curr
->isFourBytesOperand()) {
423 // Return the operand of source note `sn`, specified by `which`.
424 static ptrdiff_t getOperand(const SrcNote
* sn
, unsigned which
) {
425 const SrcNote
* head
= getOperandHead(sn
, which
);
427 if (head
->isFourBytesOperand()) {
429 (uint32_t(head
[0].value_
& SrcNote::FourBytesOperandMask
) << 24) |
430 (uint32_t(head
[1].value_
) << 16) | (uint32_t(head
[2].value_
) << 8) |
431 uint32_t(head
[3].value_
));
434 return ptrdiff_t(head
[0].value_
);
439 inline JS::ColumnNumberOffset
SrcNote::ColSpan::getSpan(const SrcNote
* sn
) {
440 return fromOperand(SrcNoteReader::getOperand(sn
, unsigned(Operands::Span
)));
444 inline JS::LimitedColumnNumberOneOrigin
SrcNote::NewLineColumn::getColumn(
446 return fromOperand(SrcNoteReader::getOperand(sn
, unsigned(Operands::Column
)));
450 inline size_t SrcNote::SetLine::getLine(const SrcNote
* sn
, size_t initialLine
) {
452 fromOperand(SrcNoteReader::getOperand(sn
, unsigned(Operands::Line
)));
456 inline size_t SrcNote::SetLineColumn::getLine(const SrcNote
* sn
,
457 size_t initialLine
) {
458 return initialLine
+ lineFromOperand(SrcNoteReader::getOperand(
459 sn
, unsigned(Operands::Line
)));
463 inline JS::LimitedColumnNumberOneOrigin
SrcNote::SetLineColumn::getColumn(
465 return columnFromOperand(
466 SrcNoteReader::getOperand(sn
, unsigned(Operands::Column
)));
469 // Iterate over SrcNote array, until it hits terminator.
472 // for (SrcNoteIterator iter(notes); !iter.atEnd(); ++iter) {
473 // auto sn = *iter; // `sn` is `const SrcNote*` typed.
476 class SrcNoteIterator
{
477 const SrcNote
* current_
;
481 unsigned arity
= current_
->arity();
484 for (; arity
; arity
--) {
485 if (current_
->isFourBytesOperand()) {
494 SrcNoteIterator() = delete;
496 SrcNoteIterator(const SrcNoteIterator
& other
) = delete;
497 SrcNoteIterator
& operator=(const SrcNoteIterator
& other
) = delete;
499 SrcNoteIterator(SrcNoteIterator
&& other
) = default;
500 SrcNoteIterator
& operator=(SrcNoteIterator
&& other
) = default;
502 SrcNoteIterator(const SrcNote
* sn
, const SrcNote
* end
)
503 : current_(sn
), end_(end
) {}
506 MOZ_ASSERT(current_
<= end_
);
507 return current_
== end_
|| current_
->isTerminator();
510 const SrcNote
* operator*() const { return current_
; }
513 SrcNoteIterator
& operator++() {
519 SrcNoteIterator
operator++(int) = delete;
524 #endif /* frontend_SourceNotes_h */