深入V8引擎-AST(5)_ZenDei技術網路在線

懶得發首頁了，有時候因為貼的代碼太多會被下，而且這東西本來也只是對自己學習的記錄，閱讀體驗極差，所以就本地自娛自樂的寫著吧！由於是解析字元串，所以在開始之前介紹一下詞法結構體中關於管理字元串類的屬性。之前在TokenDesc中，有兩個屬性，如下。當時沒有詳細講，主要也是比較麻煩，在這裡介紹一下該 ...

懶得發首頁了，有時候因為貼的代碼太多會被下，而且這東西本來也只是對自己學習的記錄，閱讀體驗極差，所以就本地自娛自樂的寫著吧！

由於是解析字元串，所以在開始之前介紹一下詞法結構體中關於管理字元串類的屬性。之前在TokenDesc中，有兩個屬性，如下。

/**
 * 詞法結構體
 * 每一個TokenDesc代表單獨一段詞法
 */
struct TokenDesc {
  /**
   * 字元串詞法相關
   */
  LiteralBuffer literal_chars;
  LiteralBuffer raw_literal_chars;
  // ...     
}

當時沒有詳細講，主要也是比較麻煩，在這裡介紹一下該類。

class LiteralBuffer final {
  public:
    /**
     * 根據字元Unicode數值判斷是單位元組還是雙位元組字元
     */
    void AddChar(uc32 code_unit) {
      if (is_one_byte()) {
        if (code_unit <= static_cast<uc32>(unibrow::Latin1::kMaxChar)) {
          AddOneByteChar(static_cast<byte>(code_unit));
          return;
        }
        ConvertToTwoByte();
      }
      AddTwoByteChar(code_unit);
    }
  private:
    /**
     * 配置
     * constexpr int MB = KB * KB; constexpr int KB = 1024; 
     */
    static const int kInitialCapacity = 16;
    static const int kGrowthFactor = 4;
    static const int kMaxGrowth = 1 * MB;
    /**
     * 向容器加字元
     */
    void AddOneByteChar(byte one_byte_char) {
      if (position_ >= backing_store_.length()) ExpandBuffer();
      backing_store_[position_] = one_byte_char;
      position_ += kOneByteSize;
    }
    /**
     * 容器擴容
     * 初始至少有64的容量 根據需要擴容
     * 會生成一個新容量的vector 把數據複製過去並摧毀老的容器
     */
    void LiteralBuffer::ExpandBuffer() {
      int min_capacity = Max(kInitialCapacity, backing_store_.length());
      Vector<byte> new_store = Vector<byte>::New(NewCapacity(min_capacity));
      if (position_ > 0) {
        MemCopy(new_store.begin(), backing_store_.begin(), position_);
      }
      backing_store_.Dispose();
      backing_store_ = new_store;
    }
    /**
     * 擴容演算法
     * min_capacity代表容器最小所需容量
     * (1024 * 1024) / 3 是一個閾值
     * 小於該值容量以4倍的速度擴張 大於該值容量直接寫死
     */
    int LiteralBuffer::NewCapacity(int min_capacity) {
      return min_capacity < (kMaxGrowth / (kGrowthFactor - 1))
                ? min_capacity * kGrowthFactor
                : min_capacity + kMaxGrowth;
    }
    /**
     * Vector容器用來裝字元
     * potions_根據單/雙字元類型影響length的計算
     */
    Vector<byte> backing_store_;
    int position_;
    bool is_one_byte_;
};

其實原理非常簡單，用一個Vector容器去裝字元，如果容量不夠，會進行擴張。

暫時不管雙位元組字元(比如中文)，所以需要關註的屬性和方法就是上面的那些，有一個地方可以關註一下，就是擴容。根據擴容機制，初始會有16 * 4的容量，當所需容量大到一定程度，會寫死，這裡來計算一下寫死的最大容量。

/**
 * 計算 kMaxGrowth = 1024 * 1024 = 1048576
 * 得到閾值 (kMaxGrowth / (kGrowthFactor - 1) = 1048576 / (4 - 1) = 349525.333
 * 而未達到閾值前容器容量會從16開始每次乘以4 如下
 * 64 256 1024 4096 16384 65536 262144 1048576
 * 當擴容第7次時才出現比閾值大的數 這個值恰好等於1mb 因此容器容量最大值就是2mb
 */

單個字元串的解析長度原來是有上限的，最大為2mb，長度約為200萬，此時會向Vector容量外的下標賦值，不知道會出現什麼情況。

回到上一篇的結尾，由於匹配到單引號，所以會走ScanString方法，源碼如下。

Token::Value Scanner::ScanString() {
  uc32 quote = c0_;
  /**
   * 初始化
   */
  next().literal_chars.Start();
  while (true) {
    /**
     * 對字元串的結尾預檢測
     */
    AdvanceUntil([this](uc32 c0) {
      // ...
    });
    /**
     * 遇到‘\’直接步進
     * 後面如果直接是字元串結尾標識符 判定為非法
     */
    while (c0_ == '\\') {
      Advance();
      if (V8_UNLIKELY(c0_ == kEndOfInput || !ScanEscape<false>())) {
        return Token::ILLEGAL;
      }
    }
    /**
     * 又遇到了同一個字元串標識符
     * 說明字元串解析完成
     */
    if (c0_ == quote) {
      Advance();
      return Token::STRING;
    }
    
    /**
     * 沒有合攏的字元串 返回非法標記
     */
    if (V8_UNLIKELY(c0_ == kEndOfInput || unibrow::IsStringLiteralLineTerminator(c0_))) {
      return Token::ILLEGAL;
    }
    // 向Vector裡面塞一個字元
    AddLiteralChar(c0_);
  }
}

總的來說還是比較簡單的，正常步進是初始化用過的Advance。代碼中有一個方法叫AdvanceUntil，從函數名判斷是一個預檢函數。這個方法調用的結構非常奇怪，C++語法我也是TM日了狗，主要作用就是預先判斷一下當前解析的字元串是否合法，整個函數結構如下。

/**
 * 參數是一個匿名函數
 */
AdvanceUntil([this](uc32 c0) {
  // Unicode大於127的特殊字元
  if (V8_UNLIKELY(static_cast<uint32_t>(c0) > kMaxAscii)) {
    /**
     * 檢測是否是換行符
     * \r\n以及\n
     */
    if (V8_UNLIKELY(unibrow::IsStringLiteralLineTerminator(c0))) {
      return true;
    }
    AddLiteralChar(c0);
    return false;
  }
  /**
   * 檢查是否是字元串結束符
   */
  uint8_t char_flags = character_scan_flags[c0];
  if (MayTerminateString(char_flags)) return true;
  AddLiteralChar(c0);
  return false;
});

/**
 * 這個方法會對c0_進行賦值
 */
void AdvanceUntil(FunctionType check) {
  c0_ = source_->AdvanceUntil(check);
}

template <typename FunctionType>
V8_INLINE uc32 AdvanceUntil(FunctionType check) {
  while (true) {
    /**
     * 從游標位置到結尾搜索符合條件的字元
     */
    auto next_cursor_pos =
        std::find_if(buffer_cursor_, buffer_end_, [&check](uint16_t raw_c0_) {
          uc32 c0_ = static_cast<uc32>(raw_c0_);
          return check(c0_);
        });
    /**
     * 1、碰到第二個參數 說明沒有符合條件的字元 直接返回結束符
     * 2、有符合條件的字元 把游標屬性指向該字元的後一位 返回該字元
     */
    if (next_cursor_pos == buffer_end_) {
      buffer_cursor_ = buffer_end_;
      if (!ReadBlockChecked()) {
        buffer_cursor_++;
        return kEndOfInput;
      }
    } else {
      buffer_cursor_ = next_cursor_pos + 1;
      return static_cast<uc32>(*next_cursor_pos);
    }
  }
}

這裡的調用方式比較邪門，其實就是JS的高階函數，函數作為參數傳入函數，比較核心的就是find_if方法與函數參數，這裡就不講std的方法了，用JS翻譯一下，不然看起來實在太痛苦。

const callback = (str) => IsStringLiteralLineTerminator(str);

const AdvanceUntil = (callback) => {
  let tarArea = buffer_.slice(buffer_cursor_, buffer_end_);
  let tarIdx = tarArea.findIdx(v => callback(v));
  if(tarIdx === - 1) return '非法字元串';
  buffer_cursor_ = tarIdx + 1;
  c0_ = buffer_[tarIdx];
}

就是這麼簡單，變數直接對應，邏輯的話也就上面這些，find_if也就是根據索引來找符合對應條件的值。也就是說，唯一需要講解的就是字元串結束符的判斷。

涉及的新屬性有兩個，其中一個是映射數組character_scan_flags，另外一個是MayTerminateString方法，兩者其實是一個東西，可以放一起看。

inline bool MayTerminateString(uint8_t scan_flags) {
  return (scan_flags & static_cast<uint8_t>(ScanFlags::kStringTerminator));
}

/**
 * 字元掃描標記
 */
enum class ScanFlags : uint8_t {
  kTerminatesLiteral = 1 << 0,
  // "Cannot" rather than "can" so that this flag can be ORed together across
  // multiple characters.
  kCannotBeKeyword = 1 << 1,
  kCannotBeKeywordStart = 1 << 2,
  kStringTerminator = 1 << 3,
  kIdentifierNeedsSlowPath = 1 << 4,
  kMultilineCommentCharacterNeedsSlowPath = 1 << 5,
};

/**
 * 映射表
 * 對字元的可能性進行分類
 */
static constexpr const uint8_t character_scan_flags[128] = {
#define CALL_GET_SCAN_FLAGS(N) GetScanFlags(N),
    INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
#undef CALL_GET_SCAN_FLAGS
};

首先可以看出，character_scan_flags也是類似於之前那個Unicode與Ascii的表，對所有字元做一個映射，映射的值就是那個枚舉類型，一個字元可能對應多個可能性。這裡的計算方法可以參照我之前那篇利用枚舉與位運算做配置，需要哪個屬性，就用對應的枚舉與字元映射值做與運算。

這個映射表的生成比較簡單粗暴，會對每一個字元做6重或運算生成一個數，目前只看字元串終止符那塊。

constexpr uint8_t GetScanFlags(char c) {
  return
    /** 1 */ | /** 2 */ | /** 3 */ |
    // Possible string termination characters.
    ((c == '\'' || c == '"' || c == '\n' || c == '\r' || c == '\\')
          ? static_cast<uint8_t>(ScanFlags::kStringTerminator)
          : 0) | /** 5 */ | /** 6 */
}

也就是說，當前字元是單雙引號、換行與反斜杠時，會被認定可能是一個字元串的結尾。

回到編譯字元串'Hello'，由於在字元結束之前，就存在另一個單引號，所以這個符號被認為可能是結束符號賦值給了c0_，Stream類的游標也直接移到了那個位置。至於中間的H、e、l、l、o5個字元，因為不存在任何特殊性，所以在最後的AddLiteralChar方法中被添加進了容器中。

結束後，整個函數正常返回Token::STRING作為詞法結構體的類型，結構體的Literal_chars的容器則存儲著對應的字元串。