tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

SwitchEmitter.cpp (10931B)

      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 #include "frontend/SwitchEmitter.h"
      8 
      9 #include "mozilla/Assertions.h"  // MOZ_ASSERT
     10 #include "mozilla/Span.h"        // mozilla::Span
     11 
     12 #include <algorithm>  // std::min, std::max
     13 
     14 #include "jstypes.h"  // JS_BIT
     15 
     16 #include "frontend/BytecodeEmitter.h"  // BytecodeEmitter
     17 #include "frontend/SharedContext.h"    // StatementKind
     18 #include "js/friend/ErrorMessages.h"   // JSMSG_*
     19 #include "js/TypeDecls.h"              // jsbytecode
     20 #include "util/BitArray.h"
     21 #include "vm/BytecodeUtil.h"  // SET_JUMP_OFFSET, JUMP_OFFSET_LEN, SET_RESUMEINDEX
     22 #include "vm/Opcodes.h"       // JSOp, JSOpLength_TableSwitch
     23 #include "vm/Runtime.h"       // ReportOutOfMemory
     24 
     25 using namespace js;
     26 using namespace js::frontend;
     27 
     28 bool SwitchEmitter::TableGenerator::addNumber(int32_t caseValue) {
     29  if (isInvalid()) {
     30    return true;
     31  }
     32 
     33  if (unsigned(caseValue + int(Bit(15))) >= unsigned(Bit(16))) {
     34    setInvalid();
     35    return true;
     36  }
     37 
     38  if (intmap_.isNothing()) {
     39    intmap_.emplace();
     40  }
     41 
     42  low_ = std::min(low_, caseValue);
     43  high_ = std::max(high_, caseValue);
     44 
     45  // Check for duplicates, which are not supported in a table switch.
     46  // We bias caseValue by 65536 if it's negative, and hope that's a rare case
     47  // (because it requires a malloc'd bitmap).
     48  if (caseValue < 0) {
     49    caseValue += Bit(16);
     50  }
     51  if (caseValue >= intmapBitLength_) {
     52    size_t newLength = NumWordsForBitArrayOfLength(caseValue + 1);
     53    if (!intmap_->resize(newLength)) {
     54      ReportOutOfMemory(bce_->fc);
     55      return false;
     56    }
     57    intmapBitLength_ = newLength * BitArrayElementBits;
     58  }
     59  if (IsBitArrayElementSet(intmap_->begin(), intmap_->length(), caseValue)) {
     60    // Duplicate entry is not supported in table switch.
     61    setInvalid();
     62    return true;
     63  }
     64  SetBitArrayElement(intmap_->begin(), intmap_->length(), caseValue);
     65  return true;
     66 }
     67 
     68 void SwitchEmitter::TableGenerator::finish(uint32_t caseCount) {
     69  intmap_.reset();
     70 
     71 #ifdef DEBUG
     72  finished_ = true;
     73 #endif
     74 
     75  if (isInvalid()) {
     76    return;
     77  }
     78 
     79  if (caseCount == 0) {
     80    low_ = 0;
     81    high_ = -1;
     82    return;
     83  }
     84 
     85  // Compute table length. Don't use table switch if overlarge or more than
     86  // half-sparse.
     87  tableLength_ = uint32_t(high_ - low_ + 1);
     88  if (tableLength_ >= Bit(16) || tableLength_ > 2 * caseCount) {
     89    setInvalid();
     90  }
     91 }
     92 
     93 uint32_t SwitchEmitter::TableGenerator::toCaseIndex(int32_t caseValue) const {
     94  MOZ_ASSERT(finished_);
     95  MOZ_ASSERT(isValid());
     96  uint32_t caseIndex = uint32_t(caseValue - low_);
     97  MOZ_ASSERT(caseIndex < tableLength_);
     98  return caseIndex;
     99 }
    100 
    101 uint32_t SwitchEmitter::TableGenerator::tableLength() const {
    102  MOZ_ASSERT(finished_);
    103  MOZ_ASSERT(isValid());
    104  return tableLength_;
    105 }
    106 
    107 SwitchEmitter::SwitchEmitter(BytecodeEmitter* bce) : bce_(bce) {}
    108 
    109 bool SwitchEmitter::emitDiscriminant(uint32_t switchPos) {
    110  MOZ_ASSERT(state_ == State::Start);
    111  switchPos_ = switchPos;
    112 
    113  // Ensure that the column of the switch statement is set properly.
    114  if (!bce_->updateSourceCoordNotes(switchPos_)) {
    115    return false;
    116  }
    117 
    118  state_ = State::Discriminant;
    119  return true;
    120 }
    121 
    122 bool SwitchEmitter::emitLexical(LexicalScope::ParserData* bindings) {
    123  MOZ_ASSERT(state_ == State::Discriminant);
    124  MOZ_ASSERT(bindings);
    125 
    126  tdzCacheLexical_.emplace(bce_);
    127  emitterScope_.emplace(bce_);
    128  if (!emitterScope_->enterLexical(bce_, ScopeKind::Lexical, bindings)) {
    129    return false;
    130  }
    131 
    132  state_ = State::Lexical;
    133  return true;
    134 }
    135 
    136 bool SwitchEmitter::validateCaseCount(uint32_t caseCount) {
    137  MOZ_ASSERT(state_ == State::Discriminant || state_ == State::Lexical);
    138  if (caseCount > Bit(16)) {
    139    bce_->reportError(switchPos_, JSMSG_TOO_MANY_CASES);
    140    return false;
    141  }
    142  caseCount_ = caseCount;
    143 
    144  state_ = State::CaseCount;
    145  return true;
    146 }
    147 
    148 bool SwitchEmitter::emitCond() {
    149  MOZ_ASSERT(state_ == State::CaseCount);
    150 
    151  kind_ = Kind::Cond;
    152 
    153  // After entering the scope if necessary, push the switch control.
    154  controlInfo_.emplace(bce_, StatementKind::Switch);
    155  top_ = bce_->bytecodeSection().offset();
    156 
    157  if (!caseOffsets_.resize(caseCount_)) {
    158    ReportOutOfMemory(bce_->fc);
    159    return false;
    160  }
    161 
    162  MOZ_ASSERT(top_ == bce_->bytecodeSection().offset());
    163 
    164  tdzCacheCaseAndBody_.emplace(bce_);
    165 
    166  state_ = State::Cond;
    167  return true;
    168 }
    169 
    170 bool SwitchEmitter::emitTable(const TableGenerator& tableGen) {
    171  MOZ_ASSERT(state_ == State::CaseCount);
    172  kind_ = Kind::Table;
    173 
    174  // After entering the scope if necessary, push the switch control.
    175  controlInfo_.emplace(bce_, StatementKind::Switch);
    176  top_ = bce_->bytecodeSection().offset();
    177 
    178  if (!caseOffsets_.resize(tableGen.tableLength())) {
    179    ReportOutOfMemory(bce_->fc);
    180    return false;
    181  }
    182 
    183  MOZ_ASSERT(top_ == bce_->bytecodeSection().offset());
    184  if (!bce_->emitN(JSOp::TableSwitch,
    185                   JSOpLength_TableSwitch - sizeof(jsbytecode))) {
    186    return false;
    187  }
    188 
    189  // Skip default offset.
    190  jsbytecode* pc =
    191      bce_->bytecodeSection().code(top_ + BytecodeOffsetDiff(JUMP_OFFSET_LEN));
    192 
    193  // Fill in switch bounds, which we know fit in 16-bit offsets.
    194  SET_JUMP_OFFSET(pc, tableGen.low());
    195  SET_JUMP_OFFSET(pc + JUMP_OFFSET_LEN, tableGen.high());
    196 
    197  state_ = State::Table;
    198  return true;
    199 }
    200 
    201 bool SwitchEmitter::emitCaseOrDefaultJump(uint32_t caseIndex, bool isDefault) {
    202  MOZ_ASSERT(kind_ == Kind::Cond);
    203 
    204  if (isDefault) {
    205    if (!bce_->emitJump(JSOp::Default, &condSwitchDefaultOffset_)) {
    206      return false;
    207    }
    208    return true;
    209  }
    210 
    211  JumpList caseJump;
    212  if (!bce_->emitJump(JSOp::Case, &caseJump)) {
    213    return false;
    214  }
    215  caseOffsets_[caseIndex] = caseJump.offset;
    216  lastCaseOffset_ = caseJump.offset;
    217 
    218  return true;
    219 }
    220 
    221 bool SwitchEmitter::prepareForCaseValue() {
    222  MOZ_ASSERT(kind_ == Kind::Cond);
    223  MOZ_ASSERT(state_ == State::Cond || state_ == State::Case);
    224 
    225  if (!bce_->emit1(JSOp::Dup)) {
    226    return false;
    227  }
    228 
    229  state_ = State::CaseValue;
    230  return true;
    231 }
    232 
    233 bool SwitchEmitter::emitCaseJump() {
    234  MOZ_ASSERT(kind_ == Kind::Cond);
    235  MOZ_ASSERT(state_ == State::CaseValue);
    236 
    237  if (!bce_->emit1(JSOp::StrictEq)) {
    238    return false;
    239  }
    240 
    241  if (!emitCaseOrDefaultJump(caseIndex_, false)) {
    242    return false;
    243  }
    244  caseIndex_++;
    245 
    246  state_ = State::Case;
    247  return true;
    248 }
    249 
    250 bool SwitchEmitter::emitImplicitDefault() {
    251  MOZ_ASSERT(kind_ == Kind::Cond);
    252  MOZ_ASSERT(state_ == State::Cond || state_ == State::Case);
    253  if (!emitCaseOrDefaultJump(0, true)) {
    254    return false;
    255  }
    256 
    257  caseIndex_ = 0;
    258 
    259  // No internal state after emitting default jump.
    260  return true;
    261 }
    262 
    263 bool SwitchEmitter::emitCaseBody() {
    264  MOZ_ASSERT(kind_ == Kind::Cond);
    265  MOZ_ASSERT(state_ == State::Cond || state_ == State::Case ||
    266             state_ == State::CaseBody || state_ == State::DefaultBody);
    267 
    268  tdzCacheCaseAndBody_.reset();
    269 
    270  if (state_ == State::Cond || state_ == State::Case) {
    271    // For cond switch, JSOp::Default is always emitted.
    272    if (!emitImplicitDefault()) {
    273      return false;
    274    }
    275  }
    276 
    277  JumpList caseJump;
    278  caseJump.offset = caseOffsets_[caseIndex_];
    279  if (!bce_->emitJumpTargetAndPatch(caseJump)) {
    280    return false;
    281  }
    282 
    283  JumpTarget here;
    284  if (!bce_->emitJumpTarget(&here)) {
    285    return false;
    286  }
    287  caseIndex_++;
    288 
    289  tdzCacheCaseAndBody_.emplace(bce_);
    290 
    291  state_ = State::CaseBody;
    292  return true;
    293 }
    294 
    295 bool SwitchEmitter::emitCaseBody(int32_t caseValue,
    296                                 const TableGenerator& tableGen) {
    297  MOZ_ASSERT(kind_ == Kind::Table);
    298  MOZ_ASSERT(state_ == State::Table || state_ == State::CaseBody ||
    299             state_ == State::DefaultBody);
    300 
    301  tdzCacheCaseAndBody_.reset();
    302 
    303  JumpTarget here;
    304  if (!bce_->emitJumpTarget(&here)) {
    305    return false;
    306  }
    307  caseOffsets_[tableGen.toCaseIndex(caseValue)] = here.offset;
    308 
    309  tdzCacheCaseAndBody_.emplace(bce_);
    310 
    311  state_ = State::CaseBody;
    312  return true;
    313 }
    314 
    315 bool SwitchEmitter::emitDefaultBody() {
    316  MOZ_ASSERT(state_ == State::Cond || state_ == State::Table ||
    317             state_ == State::Case || state_ == State::CaseBody);
    318  MOZ_ASSERT(!hasDefault_);
    319 
    320  tdzCacheCaseAndBody_.reset();
    321 
    322  if (state_ == State::Cond || state_ == State::Case) {
    323    // For cond switch, JSOp::Default is always emitted.
    324    if (!emitImplicitDefault()) {
    325      return false;
    326    }
    327  }
    328  JumpTarget here;
    329  if (!bce_->emitJumpTarget(&here)) {
    330    return false;
    331  }
    332  defaultJumpTargetOffset_ = here;
    333 
    334  tdzCacheCaseAndBody_.emplace(bce_);
    335 
    336  hasDefault_ = true;
    337  state_ = State::DefaultBody;
    338  return true;
    339 }
    340 
    341 bool SwitchEmitter::emitEnd() {
    342  MOZ_ASSERT(state_ == State::Cond || state_ == State::Table ||
    343             state_ == State::CaseBody || state_ == State::DefaultBody);
    344 
    345  tdzCacheCaseAndBody_.reset();
    346 
    347  if (!hasDefault_) {
    348    // If no default case, offset for default is to end of switch.
    349    if (!bce_->emitJumpTarget(&defaultJumpTargetOffset_)) {
    350      return false;
    351    }
    352  }
    353  MOZ_ASSERT(defaultJumpTargetOffset_.offset.valid());
    354 
    355  // Set the default offset (to end of switch if no default).
    356  jsbytecode* pc;
    357  if (kind_ == Kind::Cond) {
    358    pc = nullptr;
    359    bce_->patchJumpsToTarget(condSwitchDefaultOffset_,
    360                             defaultJumpTargetOffset_);
    361  } else {
    362    // Fill in the default jump target.
    363    pc = bce_->bytecodeSection().code(top_);
    364    SET_JUMP_OFFSET(pc, (defaultJumpTargetOffset_.offset - top_).value());
    365    pc += JUMP_OFFSET_LEN;
    366  }
    367 
    368  if (kind_ == Kind::Table) {
    369    // Skip over the already-initialized switch bounds.
    370    pc += 2 * JUMP_OFFSET_LEN;
    371 
    372    // Use the 'default' offset for missing cases.
    373    for (uint32_t i = 0, length = caseOffsets_.length(); i < length; i++) {
    374      if (caseOffsets_[i].value() == 0) {
    375        caseOffsets_[i] = defaultJumpTargetOffset_.offset;
    376      }
    377    }
    378 
    379    // Allocate resume index range.
    380    uint32_t firstResumeIndex = 0;
    381    mozilla::Span<BytecodeOffset> offsets =
    382        mozilla::Span(caseOffsets_.begin(), caseOffsets_.end());
    383    if (!bce_->allocateResumeIndexRange(offsets, &firstResumeIndex)) {
    384      return false;
    385    }
    386    SET_RESUMEINDEX(pc, firstResumeIndex);
    387  }
    388 
    389  // Patch breaks before leaving the scope, as all breaks are under the
    390  // lexical scope if it exists.
    391  if (!controlInfo_->patchBreaks(bce_)) {
    392    return false;
    393  }
    394 
    395  if (emitterScope_ && !emitterScope_->leave(bce_)) {
    396    return false;
    397  }
    398 
    399  tdzCacheLexical_.reset();
    400 
    401  controlInfo_.reset();
    402 
    403  // LIFO construction order is enforced hence we should reset the
    404  // emitterScope_ after controlInfo_ has been reset.
    405  emitterScope_.reset();
    406 
    407  state_ = State::End;
    408  return true;
    409 }
    410 
    411 InternalSwitchEmitter::InternalSwitchEmitter(BytecodeEmitter* bce)
    412    : SwitchEmitter(bce) {
    413 #ifdef DEBUG
    414  // Skip emitDiscriminant (see the comment above InternalSwitchEmitter)
    415  state_ = State::Discriminant;
    416 #endif
    417 }