tor-browser

SwitchEmitter.h (14106B)

---

/* -*- 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_SwitchEmitter_h
#define frontend_SwitchEmitter_h

#include "mozilla/Assertions.h"  // MOZ_ASSERT
#include "mozilla/Attributes.h"  // MOZ_STACK_CLASS
#include "mozilla/Maybe.h"       // mozilla::Maybe

#include <stddef.h>  // size_t
#include <stdint.h>  // int32_t, uint32_t

#include "frontend/BytecodeControlStructures.h"  // BreakableControl
#include "frontend/EmitterScope.h"               // EmitterScope
#include "frontend/JumpList.h"                   // JumpList, JumpTarget
#include "frontend/TDZCheckCache.h"              // TDZCheckCache
#include "js/AllocPolicy.h"                      // SystemAllocPolicy
#include "js/Value.h"                            // JSVAL_INT_MAX, JSVAL_INT_MIN
#include "js/Vector.h"                           // Vector
#include "vm/Scope.h"                            // LexicalScope

namespace js {
namespace frontend {

struct BytecodeEmitter;

// Class for emitting bytecode for switch-case-default block.
//
// Usage: (check for the return value is omitted for simplicity)
//
//   `switch (discriminant) { case c1_expr: c1_body; }`
//     SwitchEmitter se(this);
//     se.emitDiscriminant(offset_of_switch);
//     emit(discriminant);
//
//     se.validateCaseCount(1);
//     se.emitCond();
//
//     se.prepareForCaseValue();
//     emit(c1_expr);
//     se.emitCaseJump();
//
//     se.emitCaseBody();
//     emit(c1_body);
//
//     se.emitEnd();
//
//   `switch (discriminant) { case c1_expr: c1_body; case c2_expr: c2_body;
//                            default: def_body; }`
//     SwitchEmitter se(this);
//     se.emitDiscriminant(offset_of_switch);
//     emit(discriminant);
//
//     se.validateCaseCount(2);
//     se.emitCond();
//
//     se.prepareForCaseValue();
//     emit(c1_expr);
//     se.emitCaseJump();
//
//     se.prepareForCaseValue();
//     emit(c2_expr);
//     se.emitCaseJump();
//
//     se.emitCaseBody();
//     emit(c1_body);
//
//     se.emitCaseBody();
//     emit(c2_body);
//
//     se.emitDefaultBody();
//     emit(def_body);
//
//     se.emitEnd();
//
//   `switch (discriminant) { case c1_expr: c1_body; case c2_expr: c2_body; }`
//   with Table Switch
//     SwitchEmitter::TableGenerator tableGen(this);
//     tableGen.addNumber(c1_expr_value);
//     tableGen.addNumber(c2_expr_value);
//     tableGen.finish(2);
//
//     // If `!tableGen.isValid()` here, `emitCond` should be used instead.
//
//     SwitchEmitter se(this);
//     se.emitDiscriminant(offset_of_switch);
//     emit(discriminant);
//     se.validateCaseCount(2);
//     se.emitTable(tableGen);
//
//     se.emitCaseBody(c1_expr_value, tableGen);
//     emit(c1_body);
//
//     se.emitCaseBody(c2_expr_value, tableGen);
//     emit(c2_body);
//
//     se.emitEnd();
//
//   `switch (discriminant) { case c1_expr: c1_body; case c2_expr: c2_body;
//                            default: def_body; }`
//   with Table Switch
//     SwitchEmitter::TableGenerator tableGen(bce);
//     tableGen.addNumber(c1_expr_value);
//     tableGen.addNumber(c2_expr_value);
//     tableGen.finish(2);
//
//     // If `!tableGen.isValid()` here, `emitCond` should be used instead.
//
//     SwitchEmitter se(this);
//     se.emitDiscriminant(offset_of_switch);
//     emit(discriminant);
//     se.validateCaseCount(2);
//     se.emitTable(tableGen);
//
//     se.emitCaseBody(c1_expr_value, tableGen);
//     emit(c1_body);
//
//     se.emitCaseBody(c2_expr_value, tableGen);
//     emit(c2_body);
//
//     se.emitDefaultBody();
//     emit(def_body);
//
//     se.emitEnd();
//
//   `switch (discriminant) { case c1_expr: c1_body; }`
//   in case c1_body contains lexical bindings
//     SwitchEmitter se(this);
//     se.emitDiscriminant(offset_of_switch);
//     emit(discriminant);
//
//     se.validateCaseCount(1);
//
//     se.emitLexical(bindings);
//
//     se.emitCond();
//
//     se.prepareForCaseValue();
//     emit(c1_expr);
//     se.emitCaseJump();
//
//     se.emitCaseBody();
//     emit(c1_body);
//
//     se.emitEnd();
//
//   `switch (discriminant) { case c1_expr: c1_body; }`
//   in case c1_body contains hosted functions
//     SwitchEmitter se(this);
//     se.emitDiscriminant(offset_of_switch);
//     emit(discriminant);
//
//     se.validateCaseCount(1);
//
//     se.emitLexical(bindings);
//     emit(hosted functions);
//
//     se.emitCond();
//
//     se.prepareForCaseValue();
//     emit(c1_expr);
//     se.emitCaseJump();
//
//     se.emitCaseBody();
//     emit(c1_body);
//
//     se.emitEnd();
//
class MOZ_STACK_CLASS SwitchEmitter {
 // Bytecode for each case.
 //
 // Cond Switch (uses an equality comparison for each case)
 //     {discriminant}
 //
 //     {c1_expr}
 //     JSOp::Case c1
 //
 //     JSOp::JumpTarget
 //     {c2_expr}
 //     JSOp::Case c2
 //
 //     ...
 //
 //     JSOp::JumpTarget
 //     JSOp::Default default
 //
 //   c1:
 //     JSOp::JumpTarget
 //     {c1_body}
 //     JSOp::Goto end
 //
 //   c2:
 //     JSOp::JumpTarget
 //     {c2_body}
 //     JSOp::Goto end
 //
 //   default:
 //   end:
 //     JSOp::JumpTarget
 //
 // Table Switch
 //     {discriminant}
 //     JSOp::TableSwitch c1, c2, ...
 //
 //   c1:
 //     JSOp::JumpTarget
 //     {c1_body}
 //     JSOp::Goto end
 //
 //   c2:
 //     JSOp::JumpTarget
 //     {c2_body}
 //     JSOp::Goto end
 //
 //   ...
 //
 //   end:
 //     JSOp::JumpTarget

public:
 enum class Kind { Table, Cond };

 // Class for generating optimized table switch data.
 class MOZ_STACK_CLASS TableGenerator {
   BytecodeEmitter* bce_;

   // Bit array for given numbers.
   mozilla::Maybe<js::Vector<size_t, 128, SystemAllocPolicy>> intmap_;

   // The length of the intmap_.
   int32_t intmapBitLength_ = 0;

   // The length of the table.
   uint32_t tableLength_ = 0;

   // The lower and higher bounds of the table.
   int32_t low_ = JSVAL_INT_MAX, high_ = JSVAL_INT_MIN;

   // Whether the table is still valid.
   bool valid_ = true;

#ifdef DEBUG
   bool finished_ = false;
#endif

  public:
   explicit TableGenerator(BytecodeEmitter* bce) : bce_(bce) {}

   void setInvalid() { valid_ = false; }
   [[nodiscard]] bool isValid() const { return valid_; }
   [[nodiscard]] bool isInvalid() const { return !valid_; }

   // Add the given number to the table.  The number is the value of
   // `expr` for `case expr:` syntax.
   [[nodiscard]] bool addNumber(int32_t caseValue);

   // Finish generating the table.
   // `caseCount` should be the number of cases in the switch statement,
   // excluding the default case.
   void finish(uint32_t caseCount);

  private:
   friend SwitchEmitter;

   // The following methods can be used only after calling `finish`.

   // Returns the lower bound of the added numbers.
   int32_t low() const {
     MOZ_ASSERT(finished_);
     return low_;
   }

   // Returns the higher bound of the numbers.
   int32_t high() const {
     MOZ_ASSERT(finished_);
     return high_;
   }

   // Returns the index in SwitchEmitter.caseOffsets_ for table switch.
   uint32_t toCaseIndex(int32_t caseValue) const;

   // Returns the length of the table.
   // This method can be called only if `isValid()` is true.
   uint32_t tableLength() const;
 };

private:
 BytecodeEmitter* bce_;

 // `kind_` should be set to the correct value in emitCond/emitTable.
 Kind kind_ = Kind::Cond;

 // True if there's explicit default case.
 bool hasDefault_ = false;

 // The number of cases in the switch statement, excluding the default case.
 uint32_t caseCount_ = 0;

 // Internal index for case jump and case body, used by cond switch.
 uint32_t caseIndex_ = 0;

 // Bytecode offset after emitting `discriminant`.
 BytecodeOffset top_;

 // Bytecode offset of the previous JSOp::Case.
 BytecodeOffset lastCaseOffset_;

 // Bytecode offset of the JSOp::JumpTarget for default body.
 JumpTarget defaultJumpTargetOffset_;

 // Bytecode offset of the JSOp::Default.
 JumpList condSwitchDefaultOffset_;

 // Instantiated when there's lexical scope for entire switch.
 mozilla::Maybe<TDZCheckCache> tdzCacheLexical_;
 mozilla::Maybe<EmitterScope> emitterScope_;

 // Instantiated while emitting case expression and case/default body.
 mozilla::Maybe<TDZCheckCache> tdzCacheCaseAndBody_;

 // Control for switch.
 mozilla::Maybe<BreakableControl> controlInfo_;

 uint32_t switchPos_ = 0;

 // Cond Switch:
 //   Offset of each JSOp::Case.
 // Table Switch:
 //   Offset of each JSOp::JumpTarget for case.
 js::Vector<BytecodeOffset, 32, SystemAllocPolicy> caseOffsets_;

 // The state of this emitter.
 //
 // +-------+ emitDiscriminant +--------------+
 // | Start |----------------->| Discriminant |-+
 // +-------+                  +--------------+ |
 //                                             |
 // +-------------------------------------------+
 // |
 // |                              validateCaseCount +-----------+
 // +->+------------------------>+------------------>| CaseCount |-+
 //    |                         ^                   +-----------+ |
 //    | emitLexical +---------+ |                                 |
 //    +------------>| Lexical |-+                                 |
 //                  +---------+                                   |
 //                                                                |
 // +--------------------------------------------------------------+
 // |
 // | emitTable +-------+
 // +---------->| Table |----------------------------------->+-+
 // |           +-------+                                    ^ |
 // |                                                        | |
 // | emitCond  +------+                                     | |
 // +---------->| Cond |-+------------------------------->+->+ |
 //             +------+ |                                ^    |
 //                      |                                |    |
 //   +------------------+                                |    |
 //   |                                                   |    |
 //   |prepareForCaseValue  +-----------+                 |    |
 //   +----------+--------->| CaseValue |                 |    |
 //              ^          +-----------+                 |    |
 //              |             |                          |    |
 //              |             | emitCaseJump +------+    |    |
 //              |             +------------->| Case |->+-+    |
 //              |                            +------+  |      |
 //              |                                      |      |
 //              +--------------------------------------+      |
 //                                                            |
 // +----------------------------------------------------------+
 // |
 // |                                              emitEnd +-----+
 // +-+----------------------------------------->+-------->| End |
 //   |                                          ^         +-----+
 //   |      emitCaseBody    +----------+        |
 //   +->+-+---------------->| CaseBody |--->+-+-+
 //      ^ |                 +----------+    ^ |
 //      | |                                 | |
 //      | | emitDefaultBody +-------------+ | |
 //      | +---------------->| DefaultBody |-+ |
 //      |                   +-------------+   |
 //      |                                     |
 //      +-------------------------------------+
 //
protected:
 enum class State {
   // The initial state.
   Start,

   // After calling emitDiscriminant.
   Discriminant,

   // After calling validateCaseCount.
   CaseCount,

   // After calling emitLexical.
   Lexical,

   // After calling emitCond.
   Cond,

   // After calling emitTable.
   Table,

   // After calling prepareForCaseValue.
   CaseValue,

   // After calling emitCaseJump.
   Case,

   // After calling emitCaseBody.
   CaseBody,

   // After calling emitDefaultBody.
   DefaultBody,

   // After calling emitEnd.
   End
 };
 State state_ = State::Start;

public:
 explicit SwitchEmitter(BytecodeEmitter* bce);

 // `switchPos` is the offset in the source code for the character below:
 //
 //   switch ( cond ) { ... }
 //   ^
 //   |
 //   switchPos
 [[nodiscard]] bool emitDiscriminant(uint32_t switchPos);

 // `caseCount` should be the number of cases in the switch statement,
 // excluding the default case.
 [[nodiscard]] bool validateCaseCount(uint32_t caseCount);

 // `bindings` is a lexical scope for the entire switch, in case there's
 // let/const effectively directly under case or default blocks.
 [[nodiscard]] bool emitLexical(LexicalScope::ParserData* bindings);

 [[nodiscard]] bool emitCond();
 [[nodiscard]] bool emitTable(const TableGenerator& tableGen);

 [[nodiscard]] bool prepareForCaseValue();
 [[nodiscard]] bool emitCaseJump();

 [[nodiscard]] bool emitCaseBody();
 [[nodiscard]] bool emitCaseBody(int32_t caseValue,
                                 const TableGenerator& tableGen);
 [[nodiscard]] bool emitDefaultBody();
 [[nodiscard]] bool emitEnd();

private:
 [[nodiscard]] bool emitCaseOrDefaultJump(uint32_t caseIndex, bool isDefault);
 [[nodiscard]] bool emitImplicitDefault();
};

// Class for emitting bytecode for switch-case-default block that doesn't
// correspond to a syntactic `switch`.
// Compared to SwitchEmitter, this class doesn't require `emitDiscriminant`,
// and the discriminant can already be on the stack. Usage is otherwise
// the same as SwitchEmitter.
class MOZ_STACK_CLASS InternalSwitchEmitter : public SwitchEmitter {
public:
 explicit InternalSwitchEmitter(BytecodeEmitter* bce);
};

} /* namespace frontend */
} /* namespace js */

#endif /* frontend_SwitchEmitter_h */