path: root/js/src/frontend/SwitchEmitter.h

/* -*- 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, MOZ_MUST_USE
#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 "gc/Rooting.h"                          // Handle
#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(Some(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(Some(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(Some(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(Some(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(Some(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(Some(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; }
    MOZ_MUST_USE bool isValid() const { return valid_; }
    MOZ_MUST_USE bool isInvalid() const { return !valid_; }

    // Add the given number to the table.  The number is the value of
    // `expr` for `case expr:` syntax.
    MOZ_MUST_USE 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_;

  mozilla::Maybe<uint32_t> switchPos_;

  // 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 |-+ |
  //      |                   +-------------+   |
  //      |                                     |
  //      +-------------------------------------+
  //
  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
  //
  // Can be Nothing() if not available.
  MOZ_MUST_USE bool emitDiscriminant(const mozilla::Maybe<uint32_t>& switchPos);

  // `caseCount` should be the number of cases in the switch statement,
  // excluding the default case.
  MOZ_MUST_USE 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.
  MOZ_MUST_USE bool emitLexical(LexicalScope::ParserData* bindings);

  MOZ_MUST_USE bool emitCond();
  MOZ_MUST_USE bool emitTable(const TableGenerator& tableGen);

  MOZ_MUST_USE bool prepareForCaseValue();
  MOZ_MUST_USE bool emitCaseJump();

  MOZ_MUST_USE bool emitCaseBody();
  MOZ_MUST_USE bool emitCaseBody(int32_t caseValue,
                                 const TableGenerator& tableGen);
  MOZ_MUST_USE bool emitDefaultBody();
  MOZ_MUST_USE bool emitEnd();

 private:
  MOZ_MUST_USE bool emitCaseOrDefaultJump(uint32_t caseIndex, bool isDefault);
  MOZ_MUST_USE bool emitImplicitDefault();
};

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

#endif /* frontend_SwitchEmitter_h */