[WebKit内核] JavaScript引擎深度解析--基础篇（一）字节码生成及语法树的构建详情分析

版权声明：本文为博主原创文章，未经博主允许不得转载。

      看到HorkeyChen写的文章《[WebKit] JavaScriptCore解析--基础篇(三)从脚本代码到JIT编译的代码实现》，写的很好，深受启发。想补充一些Horkey没有写到的细节比如字节码是如何生成的等等，为此成文。

      JSC对JavaScript的处理，其实与Webkit对CSS的处理许多地方是类似的，它这么几个部分：

（1）词法分析->出来词语(Token)；

（2）语法分析->出来抽象语法树（AST：Abstract Syntax Tree）；

（3）遍历抽象语法树->生成字节码（Bytecode）；

（4）用解释器（LLInt：Low Level Interpreter）执行字节码；

（5）如果性能不够好就用Baseline JIT编译字节码生成机器码、然后执行此机器码；

（6）如果性能还不够好，就用DFG JIT重新编译字节码生成更好的机器码、然后执行此机器码；

（7）最后，如果还不好，就祭出重器--虚拟器（LLVM：Low Level Virtual Machine）来编译DFG的中间表示代码、生成更高优化的机器码并执行。接下来，我将会用一下系列文章描述此过程。

      其中，步骤1、2是类似的，3、4、5步的思想，CSS JIT也是采用类似方法，请参考[1]。想写写JSC的文章，用菜鸟和愚公移山的方式，敲开JSC的冰山一角。

 一、 JavaScriptCore的词法分析器工作流程分析

    W3C是这么解释词法和语法工作流程的：

 词法器Tokenizer的工作过程如下，就是不断从字符串中寻找一个个的词（Token），比如找到连续的“true”字符串，就创建一个TokenTrue。词法器工作过程如下：

[cpp] view plain copy

 

 

1. JavaScriptCore/interpreter/interpreter.cpp:  
2. template <typename CharType>  
3. template <ParserMode mode> TokenType LiteralParser<CharType>::Lexer::lex(LiteralParserToken<CharType>& token)  
4. {  
5.     while (m_ptr < m_end && isJSONWhiteSpace(*m_ptr))  
6.         ++m_ptr;  
7.   
8.     if (m_ptr >= m_end) {  
9.         token.type = TokEnd;  
10.         token.start = token.end = m_ptr;  
11.         return TokEnd;  
12.     }  
13.     token.type = TokError;  
14.     token.start = m_ptr;  
15.     switch (*m_ptr) {  
16.         case ‘[‘:  
17.             token.type = TokLBracket;  
18.             token.end = ++m_ptr;  
19.             return TokLBracket;  
20.         case ‘]‘:  
21.             token.type = TokRBracket;  
22.             token.end = ++m_ptr;  
23.             return TokRBracket;  
24.         case ‘(‘:  
25.             token.type = TokLParen;  
26.             token.end = ++m_ptr;  
27.             return TokLParen;  
28.         case ‘)‘:  
29.             token.type = TokRParen;  
30.             token.end = ++m_ptr;  
31.             return TokRParen;  
32.         case ‘,‘:  
33.             token.type = TokComma;  
34.             token.end = ++m_ptr;  
35.             return TokComma;  
36.         case ‘:‘:  
37.             token.type = TokColon;  
38.             token.end = ++m_ptr;  
39.             return TokColon;  
40.         case ‘"‘:  
41.             return lexString<mode, ‘"‘>(token);  
42.         case ‘t‘:  
43.             if (m_end - m_ptr >= 4 && m_ptr[1] == ‘r‘ && m_ptr[2] == ‘u‘ && m_ptr[3] == ‘e‘) {  
44.                 m_ptr += 4;  
45.                 token.type = TokTrue;  
46.                 token.end = m_ptr;  
47.                 return TokTrue;  
48.             }  
49.             break;  
50.         case ‘-‘:  
51.         case ‘0‘:  
52.         case ‘9‘:  
53.             return lexNumber(token);  
54.     }  
55.     if (m_ptr < m_end) {  
56.         if (*m_ptr == ‘.‘) {  
57.             token.type = TokDot;  
58.             token.end = ++m_ptr;  
59.             return TokDot;  
60.         }  
61.         if (*m_ptr == ‘=‘) {  
62.             token.type = TokAssign;  
63.             token.end = ++m_ptr;  
64.             return TokAssign;  
65.         }  
66.         if (*m_ptr == ‘;‘) {  
67.             token.type = TokSemi;  
68.             token.end = ++m_ptr;  
69.             return TokAssign;  
70.         }  
71.         if (isASCIIAlpha(*m_ptr) || *m_ptr == ‘_‘ || *m_ptr == ‘$‘)  
72.             return lexIdentifier(token);  
73.         if (*m_ptr == ‘\‘‘) {  
74.             return lexString<mode, ‘\‘‘>(token);  
75.         }  
76.     }  
77.     m_lexErrorMessage = String::format("Unrecognized token ‘%c‘", *m_ptr).impl();  
78.     return TokError;  
79. }  

      下面我们看看，语法解析具体过程：

JavaScriptCore/parser/parser.cpp:

[cpp] view plain copy

 

 

1. PassRefPtr<ParsedNode> Parser<LexerType>::parse(JSGlobalObject* lexicalGlobalObject, Debugger* debugger, ExecState* debuggerExecState, JSObject** exception)</span>  

[cpp] view plain copy

 

 

1. {  
2.     ASSERT(lexicalGlobalObject);  
3.     ASSERT(exception && !*exception);  
4.     int errLine;  
5.     UString errMsg;  
6.   
7.     if (ParsedNode::scopeIsFunction)  
8.         m_lexer->setIsReparsing();  
9.   
10.     m_sourceElements = 0;  
11.   
12.     errLine = -1;  
13.     errMsg = UString();  
14.   
15.     UString parseError = parseInner();  
16.     。。。  
17. ｝  

创建抽象语法树Builder，并用来解析、生成语法节点：

[cpp] view plain copy

 

 

1. UString Parser<LexerType>::parseInner(){  
2.     UString parseError = UString();  
3.    unsigned oldFunctionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;  
4.     //抽象语法树Builder：  
5.     ASTBuilder context(const_cast<JSGlobalData*>(m_globalData), const_cast<SourceCode*>(m_source));  
6.     if (m_lexer->isReparsing())  
7.         m_statementDepth--;  
8.     ScopeRef scope = currentScope();  
9.     //开始解析生成语法树的一个节点：  
10.     SourceElements* sourceElements = parseSourceElements<CheckForStrictMode>(context);  
11.     if (!sourceElements || !consume(EOFTOK))  
12. ｝  

         举例说来，根据Token的类型，JSC认为输入的Token是一个常量声明，就会使用如下的模板函数生成语法节点（Node），然后放入ASTBuilder里面,我们先看ASTBuilder的结构：

[cpp] view plain copy

 

 

1. class ASTBuilder {  
2.     ......  
3.     Scope m_scope;  
4.     Vector<BinaryOperand, 10> m_binaryOperandStack;  
5.     Vector<AssignmentInfo, 10> m_assignmentInfoStack;  
6.     Vector<pair<int, int>, 10> m_binaryOperatorStack;  
7.     Vector<pair<int, int>, 10> m_unaryTokenStack;  
8.     int m_evalCount;  
9. };  

[cpp] view plain copy

 

 

1. template <typename LexerType>  
2. template <SourceElementsMode mode, class TreeBuilder> TreeSourceElements Parser<LexerType>::parseSourceElements(TreeBuilder& context)  
3. {  
4.     const unsigned lengthOfUseStrictLiteral = 12; // "use strict".length  
5.     TreeSourceElements sourceElements = context.createSourceElements();  
6.     bool seenNonDirective = false;  
7.     const Identifier* directive = 0;  
8.     unsigned directiveLiteralLength = 0;  
9.     unsigned startOffset = m_token.m_info.startOffset;  
10.     unsigned oldLastLineNumber = m_lexer->lastLineNumber();  
11.     unsigned oldLineNumber = m_lexer->lineNumber();  
12.     bool hasSetStrict = false;  
13.     //解析语法节点--语句  
14.     while (TreeStatement statement = parseStatement(context, directive, &directiveLiteralLength)) {  
15.         if (mode == CheckForStrictMode && !seenNonDirective) {  
16.             if (directive) {  
17.                 // "use strict" must be the exact literal without escape sequences or line continuation.  
18.                 if (!hasSetStrict && directiveLiteralLength == lengthOfUseStrictLiteral && m_globalData->propertyNames->useStrictIdentifier == *directive) {  
19.                     setStrictMode();  
20.                     hasSetStrict = true;  
21.                     failIfFalse(isValidStrictMode());  
22.                     m_lexer->setOffset(startOffset);  
23.                     next();  
24.                     m_lexer->setLastLineNumber(oldLastLineNumber);  
25.                     m_lexer->setLineNumber(oldLineNumber);  
26.                     failIfTrue(m_error);  
27.                     continue;  
28.                 }  
29.             } else  
30.                 seenNonDirective = true;  
31.         }  
32.         context.appendStatement(sourceElements, statement); //添加语法节点到ASTBuilder  
33.     }  
34.       
35.     if (m_error)  
36.         fail();  
37.     return sourceElements;  
38. }  

解析语句就是各种switch case，效率不高啊！

[cpp] view plain copy

 

 

1. template <typename LexerType>  
2. template <class TreeBuilder> TreeStatement Parser<LexerType>::parseStatement(TreeBuilder& context, const Identifier*& directive, unsigned* directiveLiteralLength)  
3. {  
4.     DepthManager statementDepth(&m_statementDepth);  
5.     m_statementDepth++;  
6.     directive = 0;  
7.     int nonTrivialExpressionCount = 0;  
8.     failIfStackOverflow();  
9.     switch (m_token.m_type) {  
10.     case OPENBRACE:  
11.         return parseBlockStatement(context);  
12.     case VAR:  
13.         return parseVarDeclaration(context);  
14.     case CONSTTOKEN:  
15.         return parseConstDeclaration(context);  
16.     case FUNCTION:  
17.         failIfFalseIfStrictWithMessage(m_statementDepth == 1, "Functions cannot be declared in a nested block in strict mode");  
18.         return parseFunctionDeclaration(context);  
19.     case SEMICOLON:  
20.         next();  
21.         return context.createEmptyStatement(m_lexer->lastLineNumber());  
22.     case IF:  
23.         return parseIfStatement(context);  
24.     case DO:  
25.         return parseDoWhileStatement(context);  
26.     case WHILE:  
27.         return parseWhileStatement(context);  
28.     case FOR:  
29.         return parseForStatement(context);  
30.     case CONTINUE:  
31.         return parseContinueStatement(context);  
32.     case BREAK:  
33.         return parseBreakStatement(context);  
34.     case RETURN:  
35.         return parseReturnStatement(context);  
36.     case WITH:  
37.         return parseWithStatement(context);  
38.     case SWITCH:  
39.         return parseSwitchStatement(context);  
40.     case THROW:  
41.         return parseThrowStatement(context);  
42.     case TRY:  
43.         return parseTryStatement(context);  
44.     case DEBUGGER:  
45.         return parseDebuggerStatement(context);  
46.     case EOFTOK:  
47.     case CASE:  
48.     case CLOSEBRACE:  
49.     case DEFAULT:  
50.         // These tokens imply the end of a set of source elements  
51.         return 0;  
52.     case IDENT:  
53.         return parseExpressionOrLabelStatement(context);  
54.     case STRING:  
55.         directive = m_token.m_data.ident;  
56.         if (directiveLiteralLength)  
57.             *directiveLiteralLength = m_token.m_info.endOffset - m_token.m_info.startOffset;  
58.         nonTrivialExpressionCount = m_nonTrivialExpressionCount;  
59.     default:  
60.         TreeStatement exprStatement = parseExpressionStatement(context);  
61.         if (directive && nonTrivialExpressionCount != m_nonTrivialExpressionCount)  
62.             directive = 0;  
63.         return exprStatement;  
64.     }  
65. }  

[cpp] view plain copy

 

 

1. template <typename LexerType>  
2. template <class TreeBuilder> TreeConstDeclList Parser<LexerType>::parseConstDeclarationList(TreeBuilder& context)  
3. {  
4.     failIfTrue(strictMode());  
5.     TreeConstDeclList constDecls = 0;  
6.     TreeConstDeclList tail = 0;  
7.     do {  
8.         next();  
9.         matchOrFail(IDENT);  

[cpp] view plain copy

 

 

1. //取出词（Token）：  
2. const Identifier* name = m_token.m_data.ident;  
3. next();  

[cpp] view plain copy

 

 

1. //是一个=吗？  
2. bool hasInitializer = match(EQUAL);  

[cpp] view plain copy

 

 

1. //  
2. declareVariable(name);  
3. context.addVar(name, DeclarationStacks::IsConstant | (hasInitializer ? DeclarationStacks::HasInitializer : 0));  
4. TreeExpression initializer = 0;  
5. if (hasInitializer) {  
6.     next(TreeBuilder::DontBuildStrings); // consume ‘=‘  
7.     initializer = parseAssignmentExpression(context);  
8. }  

[cpp] view plain copy

 

 

1. <span style="white-space:pre">    </span>新建一个“常量申明节点”放入ASTBuilder里面：  
2.         tail = context.appendConstDecl(m_lexer->lastLineNumber(), tail, name, initializer);  
3.         if (!constDecls)  
4.             constDecls = tail;  
5.     } while (match(COMMA));  
6.     return constDecls;  
7. }  

ASTBuilder.h:

[cpp] view plain copy

 

 

1. ConstDeclNode* appendConstDecl(int lineNumber, ConstDeclNode* tail, const Identifier* name, ExpressionNode* initializer)  
2. {  
3.         ConstDeclNode* result = new (m_globalData) ConstDeclNode(lineNumber, *name, initializer);  
4.         if (tail)  
5.             tail->m_next = result;  
6.         return result;  
7. }  

调用堆栈 如下：

[cpp] view plain copy

 

 

1. #0  JSC::ASTBuilder::BinaryExprContext::BinaryExprContext (this=0x7fffffffbb6f)    at JavaScriptCore/parser/ASTBuilder.h:85  
2. #1  JSC::Parser<JSC::Lexer<unsigned char> >::parseBinaryExpression<JSC::ASTBuilder> (this=0x7fffffffc330, context=...)JavaScriptCore/parser/Parser.cpp:1143  
3. #2  JSC::Parser<JSC::Lexer<unsigned char> >::parseConditionalExpression<JSC::ASTBuilder> (this=0x7fffffffc330, context=...)   at JavaScriptCore/parser/Parser.cpp:1109  
4. #3  JSC::Parser<JSC::Lexer<unsigned char> >::parseAssignmentExpression<JSC::ASTBuilder> (this=0x7fffffffc330, context=...)  
5.     at /opt/src/opt/src/mp50/framework/webkit/WebKit_123412/Source/JavaScriptCore/parser/Parser.cpp:1051  
6. #4  JSC::Parser<JSC::Lexer<unsigned char> >::parseVarDeclarationList<JSC::ASTBuilder> (this=, context=...,   declarations=@0x7fffffffbd3c: 1, lastIdent=@0x7fffffffbd30: 0xdb3060, lastInitializer=@0x7fffffffbd28: 0x0, identStart=@0x7fffffffbd24: 5,   initStart=@0x7fffffffbd24: 5, initEnd=@: 5)    at parser/Parser.cpp:263  
7. #5  JSC::Parser<JSC::Lexer<unsigned char> >::parseVarDeclaration<JSC::ASTBuilder> (this=0x7fffffffc330, context=...)   at JavaScriptCore/parser/Parser.cpp:181  
8. #6  JSC::Parser<JSC::Lexer<unsigned char> >::parseStatement<JSC::ASTBuilder> (this=0x7fffffffc330, context=..., directive=: 0x0,directiveLiteralLength=)   Parser.cpp:682  
9. #7  JSC::Parser<JSC::Lexer<unsigned char> >::parseSourceElements<(JSC::SourceElementsMode)0, JSC::ASTBuilder> (this, context=...) at parser/Parser.cpp:145  
10. #8  JSC::Parser<JSC::Lexer<unsigned char> >::parseInner (this=0x7fffffffc330)    at Parser.cpp:93  
11. #9  JSC::Parser<JSC::Lexer<unsigned char> >::parse<JSC::ProgramNode> (this=, lexicalGlobalObject=,   debugger=0x0, debuggerExecState=, exception=) Parser.h:990  
12. #10 JSC::parse<JSC::ProgramNode> (globalData=http://www.mamicode.com/, lexicalGlobalObject=source,parameters, strictness=JSParseNormal,parserMode=JSParseProgramCode, debugger, execState=, exception=) Parser.h:1048
13. #11 JSC::ProgramExecutable::compileInternal (this=, exec=, scopeChainNode=, jitType=JSC::JITCode::BaselineJIT) at JavaScriptCore/runtime/Executable.cpp:338  
14. #12 JSC::ProgramExecutable::compile (this=0x7ffff7fbb580, exec=0x7ffff7f9fb90, scopeChainNode=0x7ffff7f7ffc0)JavaScriptCore/runtime/Executable.h:446  
15. #13 JSC::Interpreter::execute (this=, program=, callFrame=, scopeChain=,  thisObj=0x7ffff7f9f980) at JavaScriptCore/interpreter/Interpreter.cpp:1224  
16. #14 JSC::evaluate (exec=, scopeChain=, source=..., thisValue=http://www.mamicode.com/..., returnedException=) JavaScriptCore/runtime/Completion.cpp:75
17. #15 runWithScripts (globalObject=0x7ffff7f9f980, scripts=, dump=false)   at JavaScriptCore/jsc.cpp:545  
18. #16 jscmain (argc=2, argv=0x7fffffffdc88) at JavaScriptCore/jsc.cpp:733  
19. #17 main (argc=2, argv=0x7fffffffdc88) atavaScriptCore/jsc.cpp:510  

      接下来，就会调用BytecodeGenerator::generate生成字节码，具体分下节分析。我们先看看下面来自JavaScript的一个个语法树节点生成字节码的过程：

JavaScriptCore/bytecompiler/BytecodeGenerator.cpp:
RegisterID* BooleanNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

[cpp] view plain copy

 

 

1. {  
2.     if (dst == generator.ignoredResult())  
3.         return 0;  
4.     return generator.emitLoad(dst, m_value);  
5. }  

     以下是我准备写的文章题目：

一、 JavaScriptCore的词法分析器工作流程分析；

二、 JavaScriptCore的语法分析器工作流程分析；

三、 JavaScriptCore的字节码生成流程分析；

四、 LLInt解释器工作流程分析；

五、 Baseline JIT编译器的工作流程分析；

六、 DFG JIT编译器的工作流程分析；

七、LLVM虚拟机的工作流程分析；

八、JavaScriptCore的未来展望；

     文笔粗糙，不善表达，希望能越写越好。

原创，转载请注明：http://blog.csdn.NET/lichwei1983/article/details/44658533