正文

《Chrome V8源码》23.编译4：数据结构、重要的自动机

admin
admin V管理员 /0 评论 /18 阅读
0321
此篇文章发布距今已超过1141天，您需要注意文章的内容或图片是否可用！

 

1 摘要

本篇是编译链专题的第四篇，梳理V8编译期间涉及到的数据结构和自动机，并解释其作用。

 

2 Parse_Info

1.  // A container for the inputs, configuration options, and outputs of parsing.
2.  class V8_EXPORT_PRIVATE ParseInfo {
3.  public:
4.  //省略................
5.  AstValueFactory* ast_value_factory() const {
6.    DCHECK(ast_value_factory_.get());
7.    return ast_value_factory_.get();
8.  }
9.  const AstRawString* function_name() const { return function_name_; }
10.  void set_function_name(const AstRawString* function_name) {
11.    function_name_ = function_name;
12.  }
13.  FunctionLiteral* literal() const { return literal_; }
14.  void set_literal(FunctionLiteral* literal) { literal_ = literal; }
15.  private:
16.   //------------- Inputs to parsing and scope analysis -----------------------
17.   const UnoptimizedCompileFlags flags_;
18.   UnoptimizedCompileState* state_;
19.   std::unique_ptr<Zone> zone_;
20.     v8::Extension* extension_;
21.     DeclarationScope* script_scope_;
22.     uintptr_t stack_limit_;
23.     int parameters_end_pos_;
24.     int max_function_literal_id_;
25.     //----------- Inputs+Outputs of parsing and scope analysis -----------------
26.     std::unique_ptr<Utf16CharacterStream> character_stream_;
27.     std::unique_ptr<ConsumedPreparseData> consumed_preparse_data_;
28.     std::unique_ptr<AstValueFactory> ast_value_factory_;
29.     const AstRawString* function_name_;
30.     RuntimeCallStats* runtime_call_stats_;
31.     SourceRangeMap* source_range_map_;  // Used when block coverage is enabled.
32.     //----------- Output of parsing and scope analysis ------------------------
33.     FunctionLiteral* literal_;
34.     bool allow_eval_cache_ : 1;
35.   #if V8_ENABLE_WEBASSEMBLY
36.     bool contains_asm_module_ : 1;
37.   #endif  // V8_ENABLE_WEBASSEMBLY
38.     LanguageMode language_mode_ : 1;
39.   };

把JavaScript源码（v8::internal::source）封装成ParseInfo。上述第5行代码是AST的工厂方法；13行代码是AST成员的获取方法；17行代码（UnoptimizedCompileFlags flags）作用是优化标记；33行代码存储生成的AST。AST是最重要的成员，在学习这部分源码时只要盯住这个成员就可以了，其它成员和方法可以忽略。

 

3 AST树

1.  class FunctionLiteral final : public Expression {
2.   public:
3.    template <typename IsolateT>//省略很多代码...............
4.    MaybeHandle<String> GetName(IsolateT* isolate) const {  }
5.    const AstConsString* raw_name() const { return raw_name_; }
6.    DeclarationScope* scope() const { return scope_; }
7.    ZonePtrList<Statement>* body() { return &body_; }
8.    bool is_anonymous_expression() const {
9.      return syntax_kind() == FunctionSyntaxKind::kAnonymousExpression;
10.    }
11.    V8_EXPORT_PRIVATE LanguageMode language_mode() const;
12.    void add_expected_properties(int number_properties) {}
13.    std::unique_ptr<char[]> GetDebugName() const;
14.    Handle<String> GetInferredName(Isolate* isolate) {  }
15.    Handle<String> GetInferredName(LocalIsolate* isolate) const {}
16.    const AstConsString* raw_inferred_name() { return raw_inferred_name_; }
17.    FunctionSyntaxKind syntax_kind() const {}
18.    FunctionKind kind() const;
19.    bool IsAnonymousFunctionDefinition() const {  }
20.    int suspend_count() { return suspend_count_; }
21.    int function_literal_id() const { return function_literal_id_; }
22.    void set_function_literal_id(int function_literal_id) {  }
23.   private:
24.    const AstConsString* raw_name_;
25.    DeclarationScope* scope_;
26.    ZonePtrList<Statement> body_;
27.    AstConsString* raw_inferred_name_;
28.    Handle<String> inferred_name_;
29.    ProducedPreparseData* produced_preparse_data_;
30.  };

以函数为单位生成的AST树保存在FunctionLiteral类的根节点中。通过ZonePtrList<Statement> body_成员（26行代码）可以遍历树中的每个节点。具体遍历方法可参考bytecode生成时的相关操作。通过代码4~15行可以设置函数的语言模式（strict sloppy）等相关信息。18行代码是函数的类型，定义如下：

1.  enum FunctionKind : uint8_t {
2.    // BEGIN constructable functions
3.    kNormalFunction,kModule,kAsyncModule,kBaseConstructor,kDefaultBaseConstructor,
4.    kDefaultDerivedConstructor,
5.    kDerivedConstructor,
6.  //省略很多..............
7.    kLastFunctionKind = kClassStaticInitializerFunction,
8.  };

上述代码中的类型和JavaScript语言教材中提到的函数类型并非是一一对应的，这是因为在V8实现中对JavaScript语言的函数类型划分比较详细。

 

4 AST树节点

1.  #define DECLARATION_NODE_LIST(V) \
2.    V(VariableDeclaration)         \
3.    V(FunctionDeclaration)
4.  #define ITERATION_NODE_LIST(V) \
5.    V(DoWhileStatement)          \
6.    V(WhileStatement)            \
7.    V(ForStatement)              \
8.    V(ForInStatement)            \
9.    V(ForOfStatement)
10.  #define BREAKABLE_NODE_LIST(V) \
11.    V(Block)                     \
12.    V(SwitchStatement)
13.  #define STATEMENT_NODE_LIST(V)       \
14.    ITERATION_NODE_LIST(V)             \
15.    BREAKABLE_NODE_LIST(V)             \
16.    V(ExpressionStatement)             \
17.    V(EmptyStatement)                  \
18.    V(SloppyBlockFunctionStatement)    \
19.    V(IfStatement)                     \
20.    V(InitializeClassStaticElementsStatement)//省略很多
21.  #define LITERAL_NODE_LIST(V) \
22.    V(RegExpLiteral)           \
23.    V(ObjectLiteral)           \
24.    V(ArrayLiteral)
25.  #define EXPRESSION_NODE_LIST(V) \
26.    LITERAL_NODE_LIST(V)          \
27.    V(Assignment)                 \
28.    V(Await)                      \
29.    V(BinaryOperation)            \
30.    V(NaryOperation)              \
31.    V(Call)                       \
32.    V(YieldStar)//省略很多
33.  #define FAILURE_NODE_LIST(V) V(FailureExpression)
34.  #define AST_NODE_LIST(V)                        \
35.    DECLARATION_NODE_LIST(V)                      \
36.    STATEMENT_NODE_LIST(V)                        \
37.    EXPRESSION_NODE_LIST(V)

AST树节点由宏模板实现，通过34行代码可知节点共分为三个子类型，分别是DECLARATION、STATEMENT和EXPRESSION，在构建语法树节点时EXPRESSION可能会有左、右之分（左EXPRESSION和右EXPRESSION）。

class AstNode: public ZoneObject {
 public:
#define DECLARE_TYPE_ENUM(type) k##type,
  enum NodeType : uint8_t {
    AST_NODE_LIST(DECLARE_TYPE_ENUM) /* , */
    FAILURE_NODE_LIST(DECLARE_TYPE_ENUM)
  };
#undef DECLARE_TYPE_ENUM
//省略很多..................
}

上述代码中，树节点类型由枚举成员NodeType表示，在构建语法的自动机中NodeType是判断条件。展开FAILURE_NODE_LIST和AST_NODE_LIST后可以看到所有类型的树节点。

 

5 Token宏模板

1.  #define TOKEN_LIST(T, K)                                           \
2.    T(TEMPLATE_SPAN, nullptr, 0)                                     \
3.    T(TEMPLATE_TAIL, nullptr, 0)                                     \
4.    /* BEGIN Property */                                             \
5.    T(PERIOD, ".", 0)                                                \
6.    T(LBRACK, "[", 0)                                                \
7.    /* END Property */                                               \
8.    /* END Member */                                                 \
9.    T(QUESTION_PERIOD, "?.", 0)                                      \
10.    T(LPAREN, "(", 0)                                                \
11.    /* END PropertyOrCall */                                         \
12.    T(RPAREN, ")", 0)                                                \
13.    T(RBRACK, "]", 0)                                                \
14.    T(LBRACE, "{", 0)                                                \
15.    T(COLON, ":", 0)                                                 \
16.    T(ELLIPSIS, "...", 0)                                            \
17.    T(CONDITIONAL, "?", 3)                                           \
18.  //省略很多..................

上述第5行代码表明Token的类型是PERIOD,对应JavaScript源码中的语法符号”.”；10，12行代码表明Token的类型是左右括号；Token的其他类型还有“+，-”等操作，样例代码中已省略，请读者自行分析。以10行代码T(LPAREN, “(“, 0)为例，第三个参数0是优先级，优先级的具体用法把TOKEN_LIST展开就明白了。
一宏多用是V8的代码风格，在宏定义时尽可能全面定义所有的参数，而使用时可以只用部分参数。例如下面的样例中只使用了TOKEN_LIST宏的第一个参数name，代码如下：

#define T(name, string, precedence) #name,
const char* const Token::name_[NUM_TOKENS] = {TOKEN_LIST(T, T)};
#undef T

 

6 两个自动机

词法分析和语法分析的核心功能都是由自动机实现的，源码如下：

1.  V8_INLINE Token::Value Scanner::ScanSingleToken() {
2.   Token::Value token;
3.   do {
4.     next().location.beg_pos = source_pos();
5.     if (V8_LIKELY(static_cast<unsigned>(c0_) <= kMaxAscii)) {
6.       token = one_char_tokens[c0_];
7.       switch (token) {
8.         case Token::LPAREN:
9.         case Token::RPAREN:
10.          case Token::LBRACE:
11.          case Token::RBRACE:
12.          case Token::LBRACK:
13.          case Token::RBRACK:
14.          case Token::COLON:
15.          case Token::SEMICOLON:
16.          case Token::COMMA:
17.          case Token::BIT_NOT:
18.          case Token::ILLEGAL:
19.            // One character tokens.
20.            return Select(token);
21.          case Token::CONDITIONAL:
22.            // ? ?. ?? ??=
23.            Advance();
24.            if (c0_ == '.') {
25.              Advance();
26.              if (!IsDecimalDigit(c0_)) return Token::QUESTION_PERIOD;
27.              PushBack('.');
28.            } else if (c0_ == '?') {
29.              return Select('=', Token::ASSIGN_NULLISH, Token::NULLISH);
30.            }
31.            return Token::CONDITIONAL;
32.  //省略很多
33.          case Token::WHITESPACE:
34.            token = SkipWhiteSpace();
35.            continue;
36.          case Token::NUMBER:
37.            return ScanNumber(false);
38.          case Token::IDENTIFIER:
39.            return ScanIdentifierOrKeyword();
40.          default:
41.            UNREACHABLE();
42.        }
43.      }
44.      if (IsIdentifierStart(c0_) ||
45.          (CombineSurrogatePair() && IsIdentifierStart(c0_))) {
46.        return ScanIdentifierOrKeyword();
47.      }
48.    } while (token == Token::WHITESPACE);
49.    return token;
50.  }

ScanSingleToken()扫描一个Token，8~40行代码中每个case代表一种Token类型。第6行代码one_char_tokens数组的作用是判断字符的Token类型，数组采用宏模板定义，详见第四篇文章。

1.  ParserBase<Impl>::ParseStatementListItem() {
2.    switch (peek()) {
3.      case Token::FUNCTION:
4.        return ParseHoistableDeclaration(nullptr, false);
5.      case Token::CLASS:
6.        Consume(Token::CLASS);
7.        return ParseClassDeclaration(nullptr, false);
8.      case Token::VAR:
9.      case Token::CONST:
10.        return ParseVariableStatement(kStatementListItem, nullptr);
11.      case Token::LET:
12.        if (IsNextLetKeyword()) {
13.          return ParseVariableStatement(kStatementListItem, nullptr);
14.        }
15.        break;
16.      case Token::ASYNC:
17.        if (PeekAhead() == Token::FUNCTION &&
18.            !scanner()->HasLineTerminatorAfterNext()) {
19.          Consume(Token::ASYNC);
20.          return ParseAsyncFunctionDeclaration(nullptr, false);
21.        }
22.        break;
23.      default:
24.        break;
25.    }
26.    return ParseStatement(nullptr, nullptr, kAllowLabelledFunctionStatement);
27.  }

ParseStatementListItem()生成AST树节点的自动机，在词法分析和语法分析阶段自动机会被频繁使用。在V8源码中，跟踪上述代码的执行可以看到完整的执行流程。
要点总结
（1） 上述内容包括了V8编译的主要数据结构，看懂这些就能明白V8的编译原理；
（2） 宏模板是V8的编码风格，一宏多用的情况随处可见，简单的宏展开可以用纸笔完成，复杂的宏可以利用编译器输出预处理文件展开。

好了，今天到这里，下次见。

恳请读者批评指正、提出宝贵意见
微信：qq9123013 备注：v8交流 邮箱：[email protected]