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/. */
6
7 #ifndef frontend_SourceNotes_h
8 #define frontend_SourceNotes_h
9
10 #include "mozilla/Assertions.h" // MOZ_ASSERT
11
12 #include <algorithm> // std::min
13 #include <stddef.h> // ptrdiff_t, size_t
14 #include <stdint.h> // int8_t, uint8_t, uint32_t
15
16 #include "jstypes.h" // js::{Bit, BitMask}
17
18 namespace js {
19
20 /*
21 * Source notes generated along with bytecode for decompiling and debugging.
22 * A source note is a uint8_t with 4 bits of type and 4 of offset from the pc
23 * of the previous note. If 4 bits of offset aren't enough, extended delta
24 * notes (XDelta) consisting of 1 set high order bit followed by 7 offset
25 * bits are emitted before the next note. Some notes have operand offsets
26 * encoded immediately after them, in note bytes or byte-triples.
27 *
28 * Source Note Extended Delta
29 * +7-6-5-4+3-2-1-0+ +7+6-5-4-3-2-1-0+
30 * | type | delta | |1| ext-delta |
31 * +-------+-------+ +-+-------------+
32 *
33 * At most one "gettable" note (i.e., a note of type other than NewLine,
34 * ColSpan, SetLine, and XDelta) applies to a given bytecode.
35 *
36 * NB: the js::SrcNote::specs_ array is indexed by this enum, so its
37 * initializers need to match the order here.
38 */
39
40 #define FOR_EACH_SRC_NOTE_TYPE(M) \
41 /* Terminates a note vector. */ \
42 M(Null, "null", 0) \
43 /* += or another assign-op follows. */ \
44 M(AssignOp, "assignop", 0) \
45 /* All notes above here are "gettable". See SrcNote::isGettable below. */ \
46 M(ColSpan, "colspan", int8_t(SrcNote::ColSpan::Operands::Count)) \
47 /* Bytecode follows a source newline. */ \
48 M(NewLine, "newline", 0) \
49 M(SetLine, "setline", int8_t(SrcNote::SetLine::Operands::Count)) \
50 /* Bytecode is a recommended breakpoint. */ \
51 M(Breakpoint, "breakpoint", 0) \
52 /* Bytecode is the first in a new steppable area. */ \
53 M(StepSep, "step-sep", 0) \
54 M(Unused7, "unused", 0) \
55 /* 8-15 (0b1xxx) are for extended delta notes. */ \
56 M(XDelta, "xdelta", 0)
57
58 // Note: need to add a new source note? If there's no Unused* note left,
59 // consider bumping SrcNoteType::XDelta to 12-15 and change
60 // SrcNote::XDeltaBits from 7 to 6.
61
62 enum class SrcNoteType : uint8_t {
63 #define DEFINE_SRC_NOTE_TYPE(sym, name, arity) sym,
64 FOR_EACH_SRC_NOTE_TYPE(DEFINE_SRC_NOTE_TYPE)
65 #undef DEFINE_SRC_NOTE_TYPE
66
67 Last,
68 LastGettable = AssignOp
69 };
70
71 static_assert(uint8_t(SrcNoteType::XDelta) == 8, "XDelta should be 8");
72
73 class SrcNote {
74 struct Spec {
75 const char* name_;
76 int8_t arity_;
77 };
78
79 static const Spec specs_[];
80
81 static constexpr unsigned TypeBits = 4;
82 static constexpr unsigned DeltaBits = 4;
83 static constexpr unsigned XDeltaBits = 7;
84
85 static constexpr uint8_t TypeMask = js::BitMask(TypeBits) << DeltaBits;
86 static constexpr ptrdiff_t DeltaMask = js::BitMask(DeltaBits);
87 static constexpr ptrdiff_t XDeltaMask = js::BitMask(XDeltaBits);
88
89 static constexpr ptrdiff_t DeltaLimit = js::Bit(DeltaBits);
90 static constexpr ptrdiff_t XDeltaLimit = js::Bit(XDeltaBits);
91
toShiftedTypeBits(SrcNoteType type)92 static constexpr inline uint8_t toShiftedTypeBits(SrcNoteType type) {
93 return (uint8_t(type) << DeltaBits);
94 }
95
noteValue(SrcNoteType type,ptrdiff_t delta)96 static inline uint8_t noteValue(SrcNoteType type, ptrdiff_t delta) {
97 MOZ_ASSERT((delta & DeltaMask) == delta);
98 return noteValueUnchecked(type, delta);
99 }
100
noteValueUnchecked(SrcNoteType type,ptrdiff_t delta)101 static constexpr inline uint8_t noteValueUnchecked(SrcNoteType type,
102 ptrdiff_t delta) {
103 return toShiftedTypeBits(type) | (delta & DeltaMask);
104 }
105
xDeltaValue(ptrdiff_t delta)106 static inline uint8_t xDeltaValue(ptrdiff_t delta) {
107 return toShiftedTypeBits(SrcNoteType::XDelta) | (delta & XDeltaMask);
108 }
109
110 uint8_t value_;
111
SrcNote(uint8_t value)112 constexpr explicit SrcNote(uint8_t value) : value_(value) {}
113
114 public:
SrcNote()115 constexpr SrcNote() : value_(noteValueUnchecked(SrcNoteType::Null, 0)){};
116
117 SrcNote(const SrcNote& other) = default;
118 SrcNote& operator=(const SrcNote& other) = default;
119
120 SrcNote(SrcNote&& other) = default;
121 SrcNote& operator=(SrcNote&& other) = default;
122
terminator()123 static constexpr SrcNote terminator() { return SrcNote(); }
124
125 private:
typeBits()126 inline uint8_t typeBits() const { return (value_ >> DeltaBits); }
127
isXDelta()128 inline bool isXDelta() const {
129 return typeBits() >= uint8_t(SrcNoteType::XDelta);
130 }
131
isFourBytesOperand()132 inline bool isFourBytesOperand() const {
133 return value_ & FourBytesOperandFlag;
134 }
135
136 // number of operands
arity()137 inline unsigned arity() const {
138 MOZ_ASSERT(uint8_t(type()) < uint8_t(SrcNoteType::Last));
139 return specs_[uint8_t(type())].arity_;
140 }
141
142 public:
type()143 inline SrcNoteType type() const {
144 if (isXDelta()) {
145 return SrcNoteType::XDelta;
146 }
147 return SrcNoteType(typeBits());
148 }
149
150 // name for disassembly/debugging output
name()151 const char* name() const {
152 MOZ_ASSERT(uint8_t(type()) < uint8_t(SrcNoteType::Last));
153 return specs_[uint8_t(type())].name_;
154 }
155
isGettable()156 inline bool isGettable() const {
157 return uint8_t(type()) <= uint8_t(SrcNoteType::LastGettable);
158 }
159
isTerminator()160 inline bool isTerminator() const {
161 return value_ == uint8_t(SrcNoteType::Null);
162 }
163
delta()164 inline ptrdiff_t delta() const {
165 if (isXDelta()) {
166 return value_ & XDeltaMask;
167 }
168 return value_ & DeltaMask;
169 }
170
171 private:
172 /*
173 * Operand fields follow certain notes and are frequency-encoded: an operand
174 * in [0,0x7f] consumes one byte, an operand in [0x80,0x7fffffff] takes four,
175 * and the high bit of the first byte is set.
176 */
177 static constexpr unsigned FourBytesOperandFlag = 0x80;
178 static constexpr unsigned FourBytesOperandMask = 0x7f;
179
180 static constexpr unsigned OperandBits = 31;
181
182 public:
183 static constexpr size_t MaxOperand = (size_t(1) << OperandBits) - 1;
184
isRepresentableOperand(ptrdiff_t operand)185 static inline bool isRepresentableOperand(ptrdiff_t operand) {
186 return 0 <= operand && size_t(operand) <= MaxOperand;
187 }
188
189 class ColSpan {
190 public:
191 enum class Operands {
192 // The column span (the diff between the column corresponds to the
193 // current op and last known column).
194 Span,
195 Count
196 };
197
198 private:
199 /*
200 * SrcNoteType::ColSpan values represent changes to the column number.
201 * Colspans are signed: negative changes arise in describing constructs like
202 * for(;;) loops, that generate code in non-source order. (Negative colspans
203 * also have a history of indicating bugs in updating ParseNodes' source
204 * locations.)
205 *
206 * We store colspans in operands. However, unlike normal operands, colspans
207 * are signed, so we truncate colspans (toOperand) for storage as
208 * operands, and sign-extend operands into colspans when we read them
209 * (fromOperand).
210 */
211 static constexpr ptrdiff_t ColSpanSignBit = 1 << (OperandBits - 1);
212 static constexpr ptrdiff_t MinColSpan = -ColSpanSignBit;
213 static constexpr ptrdiff_t MaxColSpan = ColSpanSignBit - 1;
214
fromOperand(ptrdiff_t operand)215 static inline ptrdiff_t fromOperand(ptrdiff_t operand) {
216 // There should be no bits set outside the field we're going to
217 // sign-extend.
218 MOZ_ASSERT(!(operand & ~((1U << OperandBits) - 1)));
219
220 // Sign-extend the least significant OperandBits bits.
221 return (operand ^ ColSpanSignBit) - ColSpanSignBit;
222 }
223
224 public:
isRepresentable(ptrdiff_t colspan)225 static inline bool isRepresentable(ptrdiff_t colspan) {
226 return MinColSpan <= colspan && colspan <= MaxColSpan;
227 }
228
toOperand(ptrdiff_t colspan)229 static inline ptrdiff_t toOperand(ptrdiff_t colspan) {
230 // Truncate the two's complement colspan, for storage as an operand.
231 ptrdiff_t operand = colspan & ((1U << OperandBits) - 1);
232
233 // When we read this back, we'd better get the value we stored.
234 MOZ_ASSERT(fromOperand(operand) == colspan);
235 return operand;
236 }
237
238 static inline ptrdiff_t getSpan(const SrcNote* sn);
239 };
240
241 class SetLine {
242 public:
243 enum class Operands {
244 // The file-absolute source line number of the current op.
245 Line,
246 Count
247 };
248
249 private:
fromOperand(ptrdiff_t operand)250 static inline size_t fromOperand(ptrdiff_t operand) {
251 return size_t(operand);
252 }
253
254 public:
lengthFor(unsigned line)255 static inline unsigned lengthFor(unsigned line) {
256 return 1 /* SetLine */ + (line > SrcNote::FourBytesOperandMask ? 4 : 1);
257 }
258
toOperand(size_t line)259 static inline ptrdiff_t toOperand(size_t line) { return ptrdiff_t(line); }
260
261 static inline size_t getLine(const SrcNote* sn);
262 };
263
264 friend class SrcNoteWriter;
265 friend class SrcNoteReader;
266 friend class SrcNoteIterator;
267 };
268
269 class SrcNoteWriter {
270 public:
271 // Write a source note with given `type`, and `delta` from the last source
272 // note. This writes the source note itself, and `XDelta`s if necessary.
273 //
274 // This doesn't write or allocate space for operands.
275 // If the source note is not nullary, the caller is responsible for calling
276 // `writeOperand` immediately after this.
277 //
278 // `allocator` is called with the number of bytes required to store the notes.
279 // `allocator` can be called multiple times for each source note.
280 // The last call corresponds to the source note for `type`.
281 template <typename T>
writeNote(SrcNoteType type,ptrdiff_t delta,T allocator)282 static bool writeNote(SrcNoteType type, ptrdiff_t delta, T allocator) {
283 while (delta >= SrcNote::DeltaLimit) {
284 ptrdiff_t xdelta = std::min(delta, SrcNote::XDeltaMask);
285 SrcNote* sn = allocator(1);
286 if (!sn) {
287 return false;
288 }
289 sn->value_ = SrcNote::xDeltaValue(xdelta);
290 delta -= xdelta;
291 }
292
293 SrcNote* sn = allocator(1);
294 if (!sn) {
295 return false;
296 }
297 sn->value_ = SrcNote::noteValue(type, delta);
298 return true;
299 }
300
301 // Write source note operand.
302 //
303 // `allocator` is called with the number of bytes required to store the
304 // operand. `allocator` is called only once.
305 template <typename T>
writeOperand(ptrdiff_t operand,T allocator)306 static bool writeOperand(ptrdiff_t operand, T allocator) {
307 if (operand > ptrdiff_t(SrcNote::FourBytesOperandMask)) {
308 SrcNote* sn = allocator(4);
309 if (!sn) {
310 return false;
311 }
312
313 sn[0].value_ = (SrcNote::FourBytesOperandFlag | (operand >> 24));
314 sn[1].value_ = operand >> 16;
315 sn[2].value_ = operand >> 8;
316 sn[3].value_ = operand;
317 } else {
318 SrcNote* sn = allocator(1);
319 if (!sn) {
320 return false;
321 }
322
323 sn[0].value_ = operand;
324 }
325
326 return true;
327 }
328 };
329
330 class SrcNoteReader {
331 template <typename T>
getOperandHead(T sn,unsigned which)332 static T getOperandHead(T sn, unsigned which) {
333 MOZ_ASSERT(sn->type() != SrcNoteType::XDelta);
334 MOZ_ASSERT(uint8_t(which) < sn->arity());
335
336 T curr = sn + 1;
337 for (; which; which--) {
338 if (curr->isFourBytesOperand()) {
339 curr += 4;
340 } else {
341 curr++;
342 }
343 }
344 return curr;
345 }
346
347 public:
348 // Return the operand of source note `sn`, specified by `which`.
getOperand(const SrcNote * sn,unsigned which)349 static ptrdiff_t getOperand(const SrcNote* sn, unsigned which) {
350 const SrcNote* head = getOperandHead(sn, which);
351
352 if (head->isFourBytesOperand()) {
353 return ptrdiff_t(
354 (uint32_t(head[0].value_ & SrcNote::FourBytesOperandMask) << 24) |
355 (uint32_t(head[1].value_) << 16) | (uint32_t(head[2].value_) << 8) |
356 uint32_t(head[3].value_));
357 }
358
359 return ptrdiff_t(head[0].value_);
360 }
361 };
362
363 /* static */
getSpan(const SrcNote * sn)364 inline ptrdiff_t SrcNote::ColSpan::getSpan(const SrcNote* sn) {
365 return fromOperand(SrcNoteReader::getOperand(sn, unsigned(Operands::Span)));
366 }
367
368 /* static */
getLine(const SrcNote * sn)369 inline size_t SrcNote::SetLine::getLine(const SrcNote* sn) {
370 return fromOperand(SrcNoteReader::getOperand(sn, unsigned(Operands::Line)));
371 }
372
373 // Iterate over SrcNote array, until it hits terminator.
374 //
375 // Usage:
376 // for (SrcNoteIterator iter(notes); !iter.atEnd(); ++iter) {
377 // auto sn = *iter; // `sn` is `const SrcNote*` typed.
378 // ...
379 // }
380 class SrcNoteIterator {
381 const SrcNote* current_;
382
next()383 void next() {
384 unsigned arity = current_->arity();
385 current_++;
386
387 for (; arity; arity--) {
388 if (current_->isFourBytesOperand()) {
389 current_ += 4;
390 } else {
391 current_++;
392 }
393 }
394 }
395
396 public:
397 SrcNoteIterator() = delete;
398
399 SrcNoteIterator(const SrcNoteIterator& other) = delete;
400 SrcNoteIterator& operator=(const SrcNoteIterator& other) = delete;
401
402 SrcNoteIterator(SrcNoteIterator&& other) = default;
403 SrcNoteIterator& operator=(SrcNoteIterator&& other) = default;
404
SrcNoteIterator(const SrcNote * sn)405 explicit SrcNoteIterator(const SrcNote* sn) : current_(sn) {}
406
atEnd()407 bool atEnd() const { return current_->isTerminator(); }
408
409 const SrcNote* operator*() const { return current_; }
410
411 // Pre-increment
412 SrcNoteIterator& operator++() {
413 next();
414 return *this;
415 }
416
417 // Post-increment
418 SrcNoteIterator operator++(int) = delete;
419 };
420
421 } // namespace js
422
423 #endif /* frontend_SourceNotes_h */
424