实现一个简单的MVVM-4

2024年08月30日 15.9k 字大概 73 分钟

这部分讲MVVM中编译器的实现。

~~又要被编译原理折磨了（悲~~

作为前端，我们应用编译技术的场景通常是：表格、报表中的自定义公式计算器，设计一种领域特定语言（DSL）等。

编译器

编译器其实只是一段程序，它用来将“一种语言 A”翻译成“另外一种语言 B”。其中，语言 A 通常叫作源代码（source code），语言 B 通常叫作目标代码（object code 或 target code）。编译器将源代码翻译为目标代码的过程叫作编译（compile）。以下是教科书式完整编译过程：

DSL模板编译

对于 Vue.js 模板编译器来说，源代码就是组件的模板，而目标代码是能够在浏览器平台上运行的 JavaScript 代码，或其他拥有 JavaScript 运行时的平台代码，模板编译器的目标代码其实就是渲染函数：

模板编译器会首先对模板进行词法分析和语法分析，得到模板 AST。接着，将模板 AST 转换（transform）成 JavaScript AST。最后，根据 JavaScript AST 生成 JavaScript 代码，即渲染函数代码。

比如我们有这么一段模板：

<div>
    <h1 v-if="ok">
        Template
    </h1>
</div>

将会被编译成如下的AST：

const ast = {
    // 逻辑根节点
    type: 'Root',
    children: [
        type: 'Element',
        tag: 'div',
        children: [
            {
				type: 'Element',
        		tag: 'h1',
        		props: [
        			// v-if 节点
        			{
        				type: 'Directive',
        				name: 'if'
        				// 表达式节点
        				exp: {
							type: 'Expression',
        					conten: 'ok'
                        }
        			}
                ]
            }
        ]
    ]
}

模板 AST 具有与模板同构的嵌套结构。每一棵 AST 都有一个逻辑上的根节点，其类型为 Root。模板中真正的根节点则作为 Root 节点的 children 存在。

不同类型的节点是通过节点的 type 属性进行区分的。例如标签节点的 type 值为 ‘Element’。
标签节点的子节点存储在其 children 数组中。
标签节点的属性节点和指令节点会存储在 props 数组中。
不同类型的节点会使用不同的对象属性进行描述。例如指令节点拥有 name 属性，用来表达指令的名称，而表达式节点拥有 content 属性，用来描述表达式的内容。

parse函数接收字符串模板作为参数，并将解析后得到的 AST 作为返回值返回。

有了模板 AST 后，我们就可以对其进行语义分析，并对模板 AST进行转换了。接着，我们还需要将模板 AST 转换为 JavaScript AST。因为 Vue.js 模板编译器的最终目标是生成渲染函数，而渲染函数本质上是 JavaScript 代码，所以我们需要将模板 AST 转换成用于描述渲染函数的 JavaScript AST。

有了 JavaScript AST 后，我们就可以根据它生成渲染函数了，generate函数会将渲染函数的代码以字符串的形式返回，并存储在code常量中。

下面是完整流程：

`parse`实现原理与状态机

解析器的入参是字符串模板，解析器会逐个读取字符串模板中的字符，并根据一定的规则将整个字符串切割为一个个 Token。下面是这个过程的有限状态自动机，有的圆圈是单线的，而有的圆圈是双线的。双线代表此时状态机是一个合法的 Token：

对于模板<div>Hello</div>，有如下过程：

状态机处于初始状态1
初始状态1读取<，进入标签开始状态2
标签开始状态2读取div，由于是字母，直到读取到>前都处于标签名称状态3
标签名称状态3读取>，回到初始状态1
初始状态1读取到文本内容Hello，直到读取<前都处于文本状态4，并记录在文本状态 4下产生的文本内容，
文本状态4读取<，进入标签开始状态2
标签开始状态2读取/，进入结束标签状态5
结束标签状态5读取div，直到读取到>前都处于结束标签名称状态6
结束标签名称状态6读取>，回到初始状态1，分析结束，并记录在结束标签名称状态 6下生成的结束标签名称。

export function tokenize(str: string) {

  // 状态机当前状态
  let currentState = State.initial
  // 缓存字符
  const chars: Array<string> = []
  // 存储生成 Token
  const tokens: Array<token> = []

  // 使用while循环开启自动机
  while (str) {
    // 查看第一个字符
    const char: string = str[0]
    // 状态匹配
    switch (currentState) {
      /* 初始状态 */
      case State.initial:
        // 进入标签开始状态
        if (char === '<') {
          currentState = State.tagStart
          // 指向下一个字符
          str = str.substring(1)

        } else if (isAlpha(char)) {
          // 进入文本状态

          currentState = State.text
          // 缓存当前字母
          chars.push(char)
          // 指向下一个字符
          str = str.substring(1)

        }
        break

      /* 标签开始状态 */
      case State.tagStart:
        if (isAlpha(char)) {
          // 进入标签名称状态

          currentState = State.tagName
          // 缓存当前字母
          chars.push(char)
          // 指向下一个字符
          str = str.substring(1)

        } else if (char === '/') {
          // 进入结束标签状态

          currentState = State.tagEnd
          // 指向下一个字符
          str = str.substring(1)
        }
        break

      /* 标签名称状态 */
      case State.tagName:
        if (isAlpha(char)) {
          // 缓存当前字母
          chars.push(char)
          // 指向下一个字符
          str = str.substring(1)

        } else if (char === '>') {
          // 切换初始状态

          currentState = State.initial
          // 创建标签token，存储到tokens中
          tokens.push({
            type: "tag",
            name: chars.join('')
          })
          // 重置缓存
          chars.length = 0
          // 指向下一个字符
          str = str.substring(1)
        }
        break

      /* 文本状态 */
      case State.text:
        if (isAlpha(char)) {
          
          chars.push(char)
          str = str.substring(1)
          
        } else if (char === '<') {
          // 进入标签开始状态
          currentState = State.tagStart
          // 创建文本token
          tokens.push({
            type: "text",
            content: chars.join('')
          })
          // 重置缓存
          chars.length = 0
          // 指向下一个字符
          str = str.substring(1)
        }
        break

      /* 标签结束状态 */
        case State.tagEnd:
          if (isAlpha(char)) {
            currentState = State.tagEndName
            // 缓存当前字母
            chars.push(char)
            // 指向下一个字符
            str = str.substring(1)
            
          }
          break

      /* 标签结束名称状态 */
        case State.tagEndName:
          if (isAlpha(char)) {

            chars.push(char)
            str = str.substring(1)

          } else if (char === '>') {
            // 切换初始状态
            currentState = State.initial
            // 保存结束标签token
            tokens.push({
              type: 'tagEnd',
              name: chars.join('')
            })
            // 重置缓存
            chars.length = 0
            // 指向下一个字符
            str = str.substring(1)
            
          }

        
    }
  }
  return tokens

}

上面的代码是最基础的实现方式，易于理解，后续会继续优化这段代码。我们可以通过正则表达式来精简 tokenize 函数的代码。

构造AST

HTML 是一种标记语言，它的格式非常固定，标签元素之间天然嵌套，形成父子关系。因此，一棵用于描述 HTML 的 AST 将拥有与 HTML 标签非常相似的树型结构。

根据 Token 列表构建 AST 的过程，其实就是对 Token 列表进行扫描的过程。从第一个 Token 开始，顺序地扫描整个 Token 列表，直到列表中的所有 Token 处理完毕。在这个过程中，我们需要维护一个栈elementStack，这个栈将用于维护元素间的父子关系。

每遇到一个开始标签节点，我们就构造一个Element类型的 AST 节点，并将其压入栈中。
类似地，每当遇到一个结束标签节点，我们就将当前栈顶的节点弹出。

这样，栈顶的节点将始终充当父节点的角色。扫描过程中遇到的所有节点，都会作为当前栈顶节点的子节点，并添加到栈顶节点的children属性下。

结束状态：

function parse(templateStr) {
  // 获取模板对应token
  const tokens = tokenize(templateStr)
  // 创建Root节点
  const root = {
    type: 'Root',
    children: []
  }

  // 创建 elementStack 栈
  const elementStack = [root]

  // 循环扫描 tokens
  while (tokens.length) {
    // 获取当前栈顶节点作为父节点 parent
    const parent = elementStack[elementStack.length - 1] as AstNode
    // 获取当前 token
    const token = tokens[0]

    switch (token.type) {

      case 'tag':
        // 如果token是开始标签，则创建 Element 类型的AST节点
        const elementNode = {
          type: 'Element',
          tag: token.name,
          children: []
        }
        // 添加到父节点的 children
        parent.children?.push(elementNode)
        // 压栈
        elementStack.push(elementNode)
        break

      case 'text':
        // 如果token是文本节点，则创建 Element 类型的AST节点
        const textNode = {
          type: 'Text',
          content: token.content
        }
        // 添加到父节点的 children
        parent.children?.push(textNode)
        break

      case 'tagEnd':
        // 结束标签则弹出栈顶元素
        elementStack.pop()
        break
    }

    // 移除处理过的 token
    tokens.shift()

  }

  return root

}

AST 的转换与插件化架构

所谓 AST 的转换，指的是对 AST 进行一系列操作，将其转换为新的 AST 的过程。新的 AST 可以是原语言或原 DSL 的描述，也可以是其他语言或其他 DSL 的描述。转换后的 AST 可以用于代码生成。这其实就是 Vue 的模板编译器将模板编译为渲染函数的过程。

为了对 AST 进行转换，我们需要能访问 AST 的每一个节点，这样才有机会对特定节点进行修改、替换、删除等操作。由于 AST 是树型数据结构，所以我们需要编写一个深度优先的遍历算法，从而实现对 AST 中节点的访问。

我们先完成一个工具函数dump用于打印节点信息：

function dump(node, indent = 0) {
  const type = node.type

  const desc = type === 'Root'
  ? ''
  : type === 'Element'
    ? node.tag
    : node.content

  // 打印节点信息
  console.log(`${'-'.repeat(indent)}${type}: ${desc}`)

  // 递归打印
  if (node.children) {
    node.children.forEach((child: AstNode) => {dump(child, indent + 2)})
  }
}

接下来，我们将着手实现对 AST 中节点的访问，从 AST 根节点开始，进行深度优先遍历，我们可以在遍历时对AST进行转换操作：

function traverseNode(ast) {
  // 转换操作，任意
  if (ast.type === 'Element' && ast.tag = 'p') ast.tag = 'h1'
  // 有子节点则递归调用
  const children = ast.children
  if (children) {
    children.forEach((child: AstNode) => {
      traverseNode(child)
    })
  }
}

随着功能的不断增加，traverseNode函数将会变得越来越“臃肿””，我们可以使用回调函数的机制来实现解耦，为traverseNode函数添加一个上下文。

function traverseNode(ast, ctx) {

  // 有子节点则递归调用
  const children = ast.children
  // 获取转换函数
  const transforms = ctx.nodeTransforms

  transforms.forEach(transform => {
    transform(ast, ctx)
  })

  if (children) {
    children.forEach((child: AstNode) => {
      traverseNode(child, ctx)
    })
  }
}

function transform(ast) {
  const ctx = {
    nodeTransforms: [
      transformElement,
      transformText
    ]
  }

  traverseNode(ast, ctx)
}

function transformElement() {}
function transformText() {}

接下来我们继续丰富上下文信息的构造：

export interface transformCtx {
  /**
   * 转换函数组
   * */
  nodeTransforms: Array<Function>

  /**
   * 当前转换节点
   * */
  currentNode: AstNode | null

  /**
   * 当前节点在父节点的 children 中的位置索引。
   * */
  childIndex: number

  /**
   * 当前节点父节点
   * */
  parent: AstNode | null

  /**
   * 节点替换函数
   * */
  replaceNode: (node: AstNode) => void
    
  /**
   * 节点移除函数
   * */
  removeNode: () => void

}

修改transform和traverseNode函数：

function transform(ast) {
  const ctx = {
    nodeTransforms: [
      transformElement,
      transformText
    ],

    currentNode: null,
    childIndex: 0,
    parent: null,

    replaceNode(node) {
      // 找到当前节点在父节点的 children 中的位置 context.childIndex 并替换即可
      if (ctx.parent && ctx.parent.children) {
        ctx.parent.children[ctx.childIndex] = node
        // 更新 currentNode
        ctx.currentNode = node
      } else {
        console.error("children do not exist.")
      }
    },
      
    removeNode() {
      if (ctx.parent && ctx.parent.children) {
        // 根据当前节点的索引删除当前节点
        ctx.parent.children.splice(ctx.childIndex, 1)
        // 置空 currentNode
        ctx.currentNode = null
      } else {
        console.error("children do not exist.")
      }
    }
      
  }

  traverseNode(ast, ctx)
}

function traverseNode(ast, ctx) {
  ctx.currentNode = ast

  ...
  
  transforms.forEach(transform => {
    transform(ast, ctx)
    // 节点被删除则返回
    if (!ctx.currentNode) { return }
  })

  if (children) {
    children.forEach((child: AstNode) => {
      // 设置父节点
      ctx.parent = ast
      // 设置索引
      ctx.childIndex = children.indexOf(child)
      traverseNode(child, ctx)
    })
  }
}

目前的顺序处理的工作流存在的问题是，当一个节点被处理时，意味着它的父节点已经被处理完毕了，并且我们无法再回过头重新处理父节点。父节点的转换操作必须等待其所有子节点全部转换完毕后再执行，我们目前设计的转换工作流并不支持这一能力。

对节点的访问分为两个阶段，即进入阶段和退出阶段。当转换函数处于进入阶段时，它会先进入父节点，再进入子节点。而当转换函数处于退出阶段时，则会先退出子节点，再退出父节点。我们重新修改traverseNode函数：

export function traverseNode(ast: AstNode, ctx: transformCtx) {
  ctx.currentNode = ast
  // 退出阶段的回调函数数组
  const exitFns: Array<Function> = []
  ...

  transforms.forEach(transform => {
    // 存储退出阶段的回调函数
    const onExit = transform(ctx.currentNode, ctx)
    if (onExit) {
      exitFns.push(onExit)
    }
    ...
  })
	...
  
  // 处理退出阶段回调函数，反序执行
  let i = exitFns.length
  while (i--) {
    exitFns[i]()
  }
}

在traverseNode函数的最后，执行这些缓存在exitFns数组中的回调函数保证当退出阶段的回调函数执行时，当前访问的节点的子节点已经全部处理过了。我们在编写转换函数时，可以将转换逻辑编写在退出阶段的回调函数中，从而保证在对当前访问的节点进行转换之前，其子节点一定全部处理完毕。

需要注意的是，退出阶段的回调函数是反序执行的。这意味着，如果注册了多个转换函数，则它们的注册顺序将决定代码的执行结果。例如：

nodeTransForm: [
	transformA,
    transformB
]

// 执行结果
transformA
transformB
transformB
transformA

将模板 AST 转为 JavaScript AST

我们需要将模板 AST 转换为用于描述渲染函数的 JavaScript AST。下面时函数声明语句的组成：

export interface JavaScriptAstNode {
  type: string

  /**
   * 标识符
   * */
  id: JavaScriptAstIdentifier

  /**
   * 函数参数
   * */
  params: []

  /**
   * 函数体
   * */
  body: JavaScriptAstState[]
}

为了简化问题，这里我们不考虑箭头函数、生成器函数、async函数等情况。

id：函数名称，它是一个标识符Identifier。
params：函数的参数，它是一个数组。
body：函数体，由于函数体可以包含多个语句，因此它也是一个数组。

我们分别用CallExpression, StringLiteral, ArrayExpression分别描述函数调用、字符串字面量和数组：

/**
 * 函数调用结构
 * */
export interface CallExp {

  type: "CallExpression"

  /**
   * 用来描述被调用函数的名字称，它本身是一个标识符节点
   * */
  callee: Identifier

  /**
   * 被调用函数的形式参数
   * */
  arguments: AstState[]

}

/**
 * 字符串字面量
 * */
export interface StringLiteral {
  
  type: "StringLiteral"
  
  value: string
  
}

/**
 * 数组
 * */
export interface ArrayExp {
  
  type: "ArrayExpression"
  
  /**
   * 数组元素
   * */
  elements: []
}

下面是一个例子，使用之前的模板：

// <div><p>MVVM</p><p>Template</p></div>
/*
	function render() {
		return h('div', [/* ... */])
	}
*/

const FunctionDeclNode = {
    type: 'FunctionDecl'	// 表示函数声明
    id: {
        type: 'Identifier',
    	name: 'render' 		// 存储标识符的名称
    },
	params: [],
    body: [
        {
            type: 'ReturnStatement',
            // 最外层 h 函数调用
            return: {
                type: 'CallExpression',
                callee: {
                    type: 'Identifier', name: 'h',
                    arguments: [
                        // 字符串字面量`div`
                        {
                            type: 'StringLiteral',
                            value: 'div'
                        },
                        // 数组
                        {
                            type: 'ArrayExpression',
                            elements: [
                                // h 函数调用
                                {
                                    type: 'CallExpression',
                                    callee: { type: 'Identifier', name: 'h'},
                                    arguments: {
                                        {type: "StringLiteral", value: 'p'},
                                    	{type: "StringLiteral", value: 'Vue'},
                                    }
                                },
                        		// 另一节点类似，省略
                            ]
                        }
                    ]
                }
            }
        }
    ]
}

接下来我们开始编写转换函数，将模板 AST 转换为上述 JavaScript AST。不过在开始之前，我们需要编写一些用来创建 JavaScript AST 节点的辅助函数。

/**
 * 创建 StringLiteral 节点
 * */
createStringLiteral(value) {
  return {
    type: 'StringLiteral',
    value: value
  }
}

/**
 * 创建 Identifier 节点
 * */
function createIdentifier(name) {
  return {
    type: 'Identifier',
    name: name
  }
}

/**
 * 创建 ArrayExpression 节点
 * */
function ArrayExpression(elements) {
  return {
    type: 'ArrayExpression',
    elements: elements
  }
}

/**
 * 创建 CallExpression 节点
 * */
function CallExpression(callee, args) {
  return {
    type: 'CallExpression',
    callee: createIdentifier(callee),
    arguments: args
  }
}

为了把模板 AST 转换为 JavaScript AST，我们同样需要两个转换函数transformElement和transformText：

/**
 * 转换标签节点
 * */
function transformElement(node) {
  // 将转换代码编写在退出阶段的回调函数中，保证该标签节点的子节点全部被处理完毕
  return () => {
    // 不是元素节点则返回
    if (node.type !== "Element") {
      return
    }

    // 创建 h 函数调用语句
    const callExp: CallExp = createCallExpression('h', [
      createStringLiteral(node.tag as string)
    ])

    // 处理 h 函数调用的参数
    if (node.children && node.children[0].jsNode) {
      node.children.length === 1
      // 只有一个子节点则使用 jsNode 作为参数
      ? callExp.arguments.push(node.children[0].jsNode)
      // 有多个子节点则创建 ArrayExpression 作为参数
      : callExp.arguments.push(
          createArrayExpression(node.children.map(c => c.jsNode))
        )
    }

    // 添加到 jsNode
    node.jsNode = callExp

  }

}

function transformText(node) {
  // 不是文本节点则不处理
  if (node.type !== 'Text') {
    return
  }

  // 使用 node.content 创建一个 StringLiteral 类型的节点，添加到 node.jsNode 属性下
  node.jsNode = createStringLiteral(node.content as string)
}

转换后得到的 AST 只是用来描述渲染函数render的返回值的，所以我们最后一步要做的就是，补全 JavaScript AST，即把用来描述 render 函数本身的函数声明语句节点附加到 JavaScript AST 中。这需要我们编写transformRoot函数来实现对 Root 根节点的转换：

代码生成

我们将实现 generate 函数来完成代码生成的任务，代码生成也是编译器的最后一步。与 AST 转换一样，代码生成也需要上下文对象。该上下文对象用来维护代码生成过程中程序的运行状态：

export function generate(node) {
  const ctx: generateCtx = {
    // 存储最终生成的渲染代码
    code: '',
    push(code: string) {
      ctx.code += code
    }
  }

  // 代码生成
  genNode(node, ctx)
  
  // 返回渲染函数代码
  return ctx.code

}

我们希望最终生成的代码具有较强的可读性，因此我们应该考虑生成代码的格式，例如缩进和换行等。这就需要我们扩展context对象，为其增加用来完成换行和缩进的工具函数：

export function generate(node: JsAstNode) {
  const ctx: generateCtx = {
    // 存储最终生成的渲染代码
    code: '',
    push(code: string) {
      ctx.code += code
    },

    currentIndent: 0,

    newline() {
      ctx.code += '\n' + `  `.repeat(ctx.currentIndent)
    },
    
    indent() {
      ctx.currentIndent++
      ctx.newline()
    },

    deIndent() {
      ctx.currentIndent--
      ctx.newline
    }

  }

  // 代码生成
  genNode(node, ctx)

  // 返回渲染函数代码
  return ctx.code

}

有了这些基础能力之后，我们就可以开始编写genNode函数来完成代码生成的工作了。代码生成的原理其实很简单，只需要匹配各种类型的 JavaScript AST 节点，并调用对应的生成函数即可：

function genNode(node: JsAstNode, context: generateCtx) {
  switch (node.type) {

    case 'FunctionDecl':
      genFunctionDecl(node, context)
      break

    case 'ReturnStatement':
      genReturnStatement(node, context)
      break

    case 'CallExpression':
      genCallExpression(node, context)
      break

    case 'StringLiteral':
      genStringLiteral(node, context)
      break

    case 'ArrayExpression':
      genArrayExpression(node, context)
      break

  }
}

接下来我们分别实现每一种情况对应的生成函数。首先来看genFunctionDecl，用来为函数声明类型的节点生成对应的 JavaScript 代码。

function genFunctionDecl(node: JsAstNode, context: generateCtx) {
  const { push, indent, deIndent} = context

  push(`function ${(node.id as Identifier).name}`)
  push(`(`)
  // 调用 genNodeList
  genNodeList(node.params as any[], context)
  push(`) {`)
  // 缩进
  indent()
  // 递归为函数体生成代码
  (node.body as JsAstNode[]).forEach((n: JsAstNode) => genNode(n, context))
  // 取消缩进
  deIndent()
  push('}')
}

function genNodeList(params: Array<JsAstNode>, context: generateCtx) {
  const { push } = context
  for (let i = 0 ; i < params.length ; i++) {
    const param = params[i]
    genNode(param, context)

    if (i < params.length - 1) {
      push(', ')
    }
      
  }
}

这里有一个需要注意的点：
1
2
3
indent()
// 递归为函数体生成代码
(node.body as JsAstNode[]).forEach((n: JsAstNode) => genNode(n, context))
这段代码经过Webpack打包后的代码为：
1
2
// 缩进
indent()(node.body).forEach((n) => genNode(n, context));
会引发indent() is not a function错误。为了避免这个问题，最好在indent()后面加上;。

genArrayExpression函数的实现与genNodelist相似，只需要包裹[]即可：

function genArrayExpression(node: ArrayExp, context: generateCtx) {
  const { push } = context
  push('[')
  genNodeList(node.elements, context)
  push(']')
}

genCallExpression也用到了genNodeList用于处理参数：

function genCallExpression(node: CallExp, context: generateCtx) {
  const { push } = context
  // 获取被调用函数名称和参数
  const { callee, arguments: args } = node
  push(`${callee.name}(`)
  genNodeList(args, context)
  push(')')

}

对于ReturnStatement和StringLiteral类型的节点来说，为它们生成代码很简单：

function genReturnStatement(node: JsAstNode, context: generateCtx) {
  const { push } = context
  push('return ')
  genNode(node.return, context)
}

function genStringLiteral(node: StringLiteral, context: generateCtx) {
  const { push } = context
  push(`${node.value}`)
}

解析器

我们将更多地利用正则表达式来实现 HTML 解析器。WHATWG 关于 HTML 的解析规范，其中定义了完整的错误处理和状态机的状态迁移流程，还提及了一些特殊的状态，例如 DATA、CDATA、RCDATA、RAWTEXT 等。

文本模式

文本模式指的是解析器在工作时所进入的一些特殊状态，在不同的特殊状态下，解析器对文本的解析行为会有所不同。具体来说，当解析器遇到一些特殊标签时，会切换模式，从而影响其对文本的解析行为。这些特殊标签是：

<title>, <textarea>标签会切换到RCDATA模式
<style>, <xmp>, <iframe>, <noembed>, <noframes>, <noscript>等标签会切换到RAWTEXT 模式
当解析器遇到<![CDATA[字符串进入CDATA模式

解析器的初始模式则是 DATA 模式。对于 Vue 的模板 DSL 来说，模板中不允许出现<script>标签，因此 Vue 模板解析器在遇到<script>标签时也会切换到 RAWTEXT 模式。

在默认的 DATA 模式下：

解析器在遇到字符<时，会切换到标签开始状态（tag open state）。换句话说，在该模式下，解析器能够解析标签元素。
当解析器遇到字符&时，会切换到字符引用状态（character reference state），也称 HTML字符实体状态。也就是说，在 DATA 模式下，解析器能够处理 HTML字符实体。

在 RCDATA 状态下：

当解析器遇到字符<时，不会再切换到标签开始状态，而会切换到RCDATA less-than sign state状态。
- 如果解析器遇到字符/，则直接切换到 RCDATA 的结束标签状态，即RCDATA end tag open state
- 否则会将当前字符<作为普通字符处理，然后继续处理后面的字符，间接说明了在<textarea>内可以将字符 < 作为普通文本，解析器并不会认为字符<是标签开始的标志
- 解析器仍然支持 HTML 实体。因为当解析器遇到字符&时，会切换到字符引用状态

在 RAWTEXT 模式下的工作方式与在 RCDATA 模式下类似：

解析器会将 HTML 实体字符作为普通字符处理。

CDATA 模式在 RAWTEXT 模式的基础上更进一步：

解析器将把任何字符都作为普通字符处理，直到遇到 CDATA 的结束标志为止。

模式	能否解析标签	能否支持HTML实体
DATA	能	是
RCDATA	否	是
RAWTEXT	否	否
CDATA	否	否

后续编写解析器代码时，我们会将上述模式定义为状态表：

递归下降算法构造模板 AST

解析器的基本架构模型如下：

function parse(templateStr: string): AstNode {
  // 解析器上下文
  const context: parseCtx = {
    // 模板内容
    source: templateStr,
    // 解析器模式
    mode: TextModes.DATA
  }

  const nodes: AstNode[] = parseChildren(context, [])

  return {
    type: 'Root',
    children: nodes
  }

}

与之前的实现不同，创建 Token 与构造模板 AST 的过程可以同时进行，因为模板和模板 AST 具有同构的特性。parseChildren函数是整个解析器的核心。后续我们会递归地调用它来不断地消费模板内容。parseChildren函数会返回解析后得到的子节点。

parseChildren函数本质上也是一个状态机，该状态机有多少种状态取决于子节点的类型数量：

标签节点，例如<div>。
文本插值节点，例如{{ val }}。
普通文本节点，例如：text。
注释节点，例如。
CDATA节点，例如<![CDATA[ xxx ]]>

注意正则表达式/a-z/i中的i，意思是忽略大小写（case insensitive）。

export function parseChildren(ctx: parseCtx, ancestors: AstNode[]) {
  // 定义数组存储子节点
  let nodes: AstNode[] = []
  const { mode, source } = ctx

  while(!isEnd(ctx, ancestors)) {
    let node
    // DATA RCDATA 模式才支持插值节点的解析
    if (mode === TextModes.DATA || mode === TextModes.RCDATA) {
      // 只有 DATA 模式才支持标签节点解析
      if (mode === TextModes.DATA && source[0] === '<') {
        if (source[1] === '!') {
          if (source.startsWith('<!--')) {
            // 注释
            node = parseComment(ctx)
          } else if (source.startsWith('<![CDATA[')) {
            // CDATA
            node = parseCDATA(ctx, ancestors)
          }
        }
      } else if (source[1] === '/') {
        // 结束标签，报错
      } else if (/a-z/i.test(source[1])) {
        // 标签元素
        node = parseElement(ctx, ancestors)
      } else if (source.startsWith('{{')) {
        // 解析插值
        node = parseInterpolation(ctx)
      }
    } 
    
    // node 不存在，作为文本处理
    if (!node) {
      // 解析文本节点
      node = parseText(ctx)
    }
    
    // 将节点添加到 nodes
    nodes.push(node)
    
  }

  return nodes
}

在解析模板时，我们不能忽略空白字符。这些空白字符包括：换行符（）、回车符（、空格（’ ’）、制表符（以及换页符（。我们用加号（+）代表换行符，用减号（-）代表空格字符

接下来我们先实现元素标签解析parseElement。如果一个标签不是自闭合标签，则可以认为，一个完整的标签元素是由开始标签、子节点和结束标签这三部分构成的。为了解析标签的子节点，我们递归地调用了parseChildren函数。这意味着，一个新的状态机开始运行了。随着标签嵌套层次的增加，新的状态机会随着parseChildren函数被递归地调用而不断创建，这就是“递归下降”中“递归”二字的含义。而上级parseChildren函数的调用用于构造上级模板 AST 节点，被递归调用的下级parseChildren函数则用于构造下级模板 AST 节点。最终，会构造出一棵树型结构的模板 AST，这就是“递归下降”中“下降”二字的含义。

状态机的开启与停止

我们在上一节中有一个没有实现的函数isEnd，这个函数用于判断状态机何时停止。

此时“状态机 2”拥有程序的执行权，它持续解析模板直到遇到结束标签</p>。因为这是一个结束标签，并且在父级节点栈中存在与该结束标签同名的标签节点，所以“状态机 2”会停止运行，并弹出父级节点栈中处于栈顶的节点。此时“状态机 2”已经停止运行了，但“状态机 1”仍在运行中，于是会继续解析模板，直到遇到下一个<p>标签。这时“状态机 1”会再次调用parseElement函数解析标签节点，因此又会执行压栈并开启新的“状态机 3”。

“状态机 3”会继续解析模板，直到遇到结束标签</p>。因为这是一个结束标签，并且在父级节点栈中存在与该结束标签同名的标签节点，所以“状态机 3”会停止运行，并弹出父级节点栈中处于栈顶的节点。当“状态机 3”停止运行后，程序的执行权交还给“状态机 1”。“状态机 1”会继续解析模板，直到遇到最后的</div>结束标签。这时“状态机 1”发现父级节点栈中存在与结束标签同名的标签节点，于是将该节点弹出父级节点栈：

这时父级节点栈为空，状态机全部停止运行，模板解析完毕。当解析器遇到开始标签时，会将该标签压入父级节点栈，同时开启新的状态机。当解析器遇到结束标签，并且父级节点栈中存在与该标签同名的开始标签节点时，会停止当前正在运行的状态机。

function isEnd(ctx: parseCtx, ancestors: AstNode[]) {
  // 模板内容解析完毕后停止
  if (!ctx.source) return true

  // 获取父级标签节点
  const parent = ancestors[ancestors.length - 1]
  // 如果遇到结束标签，并且该标签与父级标签节点同名，则停止
  if (parent && ctx.source.startsWith(`</${parent.tag}`)) {
    return true
  }

}

目前的实现有个问题：

1	`<div><span></div></span>`

有两种解释方式：

“状态机 3”遭遇了不符合预期的状态，因为结束标签</div>缺少与之对应的开始标签，所以这时“状态机 3”会抛出错误：“无效的结束标签”。

在parseChildren中体现为：
1
2
3
4
5
6
else if (source[1] === '/') { // 结束标签，报错 console.error(`invalid tag ${ctx.source}`) continue }
在这个过程中，“状态机 2”在调用parseElement解析函数时，parseElement函数能够发现<span>缺少闭合标签，于是会打印错误信息“<span>标签缺少闭合标签”

在parseElement中处理该错误。

我们先来实现辅助函数parseTag和parseEndTag。我们为上下文对象增加了advanceBy函数和advanceSpaces函数。其中advanceBy函数用来消费指定数量的字符。advanceSpaces函数则用来消费无用的空白字符，因为标签中可能存在空白字符，例如在模板<div---->中减号（-）代表空白字符。

// 解析器上下文
const context: parseCtx = {
    // 模板内容
    source: templateStr,
    // 解析器模式
    mode: TextModes.DATA,

    // 消费指定数量的字符
    advanceBy(num: number) {
      // 截取位置 num 后的模板内容，并替换当前模板内容
      context.source = context.source.slice(num)
    },

    // 清除空白字符
    advanceSpaces() {
      const match = /^[\t\r\n\f ]+/.exec(context.source)
      if (match) {
        // 调用 advanceBy 清除
        context.advanceBy(match[0].length)
      }

    }

}

有了advanceBy和 advanceSpaces函数后，我们就可以给出parseTag函数的实现了，如下面的代码所示：

export function parseTag(context, type = 'start') {
  const { advanceBy, advanceSpaces } = context

  // 处理开始标签和结束标签
  const match = type === 'start'
    // 开始标签
    ? /^<([a-z][^\t\r\n\f />]*)/i.exec(context.source)
    // 结束标签
    : /^<\/([a-z][^\t\r\n\f />]*)/i.exec(context.source)

  // 匹配成功正则表达式第一个捕获组的值就是标签名称
  if (match) {
    const tag = match[1]
    // 清除正则表达式匹配的全部内容
    advanceBy(match[0])
    advanceSpaces()

    // 如果消除后字符串以 /> 开头则是自闭合标签
    const isSelfClosing = context.source.startsWith("/>")
    // 如果是自闭合标签，则消费 '/>'， 否则消费 '>'
    advanceBy(isSelfClosing ? 2 : 1)

    // 返回标签节点
    return {
      type: 'Element',
      tag: tag,
      props: [],
      children: [],
      isSelfClosing: isSelfClosing
    }
    
  } else {
    console.error("tag does not match.")
    return 
  }
}

实现了parseTag，我们就可以开始实现parseElement了：

function parseElement(context: parseCtx, ancestors: AstNode[]) {
  const element = parseTag(context) as AstNode
  if (element.isSelfClosing) return element

  // 切换到正确的文本模式
  if (element.tag === 'textarea' || element.tag ==='title') {
    // 解析得到的标签是 <textarea> 或 <title> 切换RCDATA模式
    context.mode = TextModes.RCDATA
  } else if (/style | xmp | iframe | noembed | noframes | noscipt/.test(element.tag as string)) {
    // 上述情况切换 RAWTEXT
    context.mode = TextModes.RAWTEXT
  } else {
    // 其他情况切换到 DATA 模式
    context.mode = TextModes.DATA
  }

  ancestors.push(element)
  // 递归地调用 parseChildren 函数进行标签子节点的解析
  element.children = parseChildren(context, ancestors)
  ancestors.pop()

  if (context.source.startsWith(`</${element.tag}`)) {
    parseTag(context, 'end')
  } else {
    // 缺少闭合标签
    console.error(`${element.tag} is lack of end tag.`)
  }
  
  return element

}

解析属性

parseTag解析函数会消费整个开始标签，这意味着该函数需要有能力处理开始标签中存在属性与指令。为了处理属性和指令，我们需要在parseTag函数中增加parseAttributes解析函数。我们先来看parseAttributes函数：

parseAttributes函数消费模板内容的过程，就是不断地解析属性名称、等于号、属性值的过程。在属性名称解析完毕之后，模板剩余内容一定是以等于号开头的，即：

1	`= 'foo' v-show='display'>`

我们需要消费等于号字符。由于等于号和属性值之间也可能存在空白字符，所以我们也需要消费对应的空白字符。接下来，到了处理属性值的环节。模板中的属性值存在三种情况：

属性值被双引号包裹：id="foo"
属性值被单引号包裹：id='foo'
属性值没有引号包裹：id=foo

因此我们可以通过检查当前模板内容是否以引号开头来确定属性值是否被引用。既然属性值被引号引用了，就意味着在剩余模板内容中，下一个引号之前的内容都应该被解析为属性值。如果属性值没有被引号引用，那么在剩余模板内容中，下一个空白字符之前的所有字符都应该作为属性值。

当属性值和引号被消费之后，由于属性值与下一个属性名称之间可能存在空白字符，所以我们还要消费对应的空白字符。

接下来重新执行上述步骤直到遇到标签的“结束部分”，即字符>，这时，parseAttributes函数中的 while 循环将会停止，完成属性和指令的解析。

function parseAttributes(context: parseCtx) {
  
  const { advanceBy, advanceSpaces } = context
  // 存储属性和指令节点
  const props: any[] = []

  while (!context.source.startsWith('>') && 
        !context.source.startsWith('/>')) {
    // 正则匹配名称
    const match = /^[\t\r\n\f />][^\t\r\n\f />=]*/.exec(context.source)
    
    if (match) {
      // 获取属性名称
      const name = match[0]
      
      // 消费属性名
      advanceBy(name.length)
      // 消除空白字符
      advanceSpaces()
      // 消费 =
      advanceBy(1)
      // 消费空白字符
      advanceSpaces()
      
      // 属性值
      let value = ''
      
      // 获取当前模板内容的第一个字符
      const quote = context.source[0]
      // 判断属性值是否被引号引用
      const isQuoted = quote === '"' || quote === "'"
      
      if (isQuoted) {
        // 属性值被引号引用，消费引号
        advanceBy(1)
        // 获取下一个引号索引
        const endQuoteIndex = context.source.indexOf(quote)
        if (endQuoteIndex > -1) {
          // 获取属性值
          value = context.source.slice(0, endQuoteIndex)
          // 消费属性值
          advanceBy(value.length)
          // 消费引号
          advanceBy(1)
        } else {
          console.error(`${context.source}: Missing quote`)
        }
      } else {
        // 属性值没有被引号引用
        const match = /^[^\t\r\n\f >]+/.exec(context.source)
        if (match) {
          // 获取属性值
          value = match[0]
          // 消费属性值
          advanceBy(value.length)
        } else {
          console.error(`${context.source} can not match.`)
        }
        
      }
      
      // 消费空白字符
      advanceSpaces()
      
      // 创建属性节点，添加到props中
      props.push({
        type: 'Attribute',
        name,
        value
      })
      
    } else {
      console.error(`${context.source} can not match.`)
    }
  }

}

然后修改parseTag以支持属性的解析：

export function parseTag(context: parseCtx, type = 'start'): AstNode | undefined {
  const { advanceBy, advanceSpaces } = context

  // 处理开始标签和结束标签
  const match = type === 'start'
    // 开始标签
    ? /^<([a-z][^\t\r\n\f />]*)/i.exec(context.source)
    // 结束标签
    : /^<\/([a-z][^\t\r\n\f />]*)/i.exec(context.source)

  // 匹配成功正则表达式第一个捕获组的值就是标签名称
  if (match) {
    const tag = match[1]
    // 清除正则表达式匹配的全部内容
    advanceBy(match[0])
    advanceSpaces()
    
    // 获取props
    const props = parseAttributes(context)
    
    // 如果消除后字符串以 /> 开头则是自闭合标签
    const isSelfClosing = context.source.startsWith("/>")
    // 如果是自闭合标签，则消费 '/>'， 否则消费 '>'
    advanceBy(isSelfClosing ? 2 : 1)

    // 返回标签节点
    return {
      type: 'Element',
      tag: tag,
      props: props,
      children: [],
      isSelfClosing: isSelfClosing
    }

  } else {
    console.error("tag does not match.")
    return
  }
}

解析文本与解码HTML实体

解析文本

调用parseText函数处理文本内容。此时解析器会在模板中寻找下一个<字符或插值定界符的位置索引，记为索引 I。然后，解析器会从模板的头部到索引 I 的位置截取内容，这段截取出来的字符串将作为文本节点的内容。

function parseText(context: parseCtx) {
  // endIndex为文本内容结尾索引
  // 默认将整个莫欧版剩余内容都作为文本内容
  let endIndex = context.source.length
  // 寻找 < 
  const ltIndex = context.source.indexOf('<')
  // 寻找 {{
  const delimiterIndex = context.source.indexOf('{{')
  
  // 取 ltIndex 和当前 endIndex 中较小的作为结尾索引
  if (ltIndex > -1 && ltIndex < endIndex) {
    endIndex = ltIndex
  }
  
  // delimiterIndex同理
  if (delimiterIndex > -1 && delimiterIndex < endIndex) {
    endIndex = delimiterIndex
  }
  
  const content = context.source.slice(0, endIndex)
  // 消费content
  context.advanceBy(endIndex)
  
  return {
    type: 'Text',
    content
  }
  
}

解码命名字符引用

HTML 实体是一段以字符&开始的文本内容。实体用来描述 HTML 中的保留字符和一些难以通过普通键盘输入的字符，以及一些不可见的字符。HTML 实体总是以字符&开头，以字符;结尾。之所以需要解析命名字符引用，是因为 Vue 模板中，文本节点所包含的 HTML 实体不会被浏览器解析。这是因为模板中的文本节点最终将通过如el.textContent等文本操作方法设置到页面，而通过el.textContent设置的文本内容是不会经过 HTML 实体解码的。

解析 HTML 实体也是一种状态机：

关于字符引用中的分号：

当存在分号时：执行完整匹配。
当省略分号时：执行最短匹配。

为此，我们需要精心设计命名字符引用表。由于命名字符引用的数量非常多，因此这里我们只取其中一部分作为命名字符引用表的内容：

export const namedCharacterReferences = {
  "gt": ">",
  "gt;": ">",
  "lt": "<",
  "lt;": "<",
  "ltcc;": "⪦" 
}

对于普通文本部分，由于它不需要被解码，因此索引原封不动地保留。而对于可能是字符引用的部分，执行解码工作。

计算出命名字符引用表中实体名称的最大长度。
根据最大长度截取字符串。
用截取后的字符串作为键去命名字符引用表中查询对应的值，即解码。
当发现不匹配时，我们将最大长度减 1，并重新执行第二步，直到找到匹配项为止。

function decodeHTML(rawText: string, asAttr = false) {

  let offset = 0
  const end = rawText.length
  // 解码后的文本
  let decodedText = ''
  // 引用表中实体名称的最大长度
  let maxCRNameLength = 0

  // advance 函数用于消费指定长度的文本
  function advance(length: number) {
    offset += length
    rawText = rawText.slice(length)
  }

  while (offset < end) {
    // 匹配字符串引用的开始部分
    // & 命名字符引用
    // &# 十进制数字字符引用
    // &#* 十六进制数字字符引用
    const head = /&(?:#x?)?/i.exec(rawText)
    // 没有匹配则说明不需要继续解码了
    if (!head) {
      // 计算剩余内容
      const remain = end - offset
      // 将剩余内容加到 decodedText 上
      decodedText += rawText.slice(0, remain)
      // 消费剩余内容
      advance(remain)
      break
    }

    // head.index 为匹配的字符 & 在 rawText 中的位置索引
    // 截取字符 & 之前的内容加到 decodedText 上
    decodedText += rawText.slice(0, head.index)
    // 消费字符 & 之前的内容
    advance(head.index)

    // 如果满足条件则是命名字符引用，否则为数字字符引用
    if (head[0] === '&') {
      let name = ''
      let value: any
      // 字符 & 的下一个字符必须是 ASCII 字母或数字
      if (/[0-9a-z]/i.test(rawText[1])) {
        // 根据引用表计算实体名称的最大长度
        if (!maxCRNameLength) {
          maxCRNameLength = Object.keys(namedCharacterReferences).reduce(
            (max, name) => Math.max(Number(max), name.length), 0
          )
        }

        // 从最大长度开始对文本进行截取，并尝试去引用表中找到对应的项
        for (let length = maxCRNameLength; !value && length > 0 ; length--) {
          name = rawText.substring(1, length)
          value = namedCharacterReferences[name]
        }

        if (value) {
          const semi = name.endsWith(";")

          // 如果解码的文本作为属性值，最后一个匹配的字符不是分号，
          // 并且最后一个匹配字符的下一个字符是等于号（=）、ASCII 字母或
          // 数字，
          // 由于历史原因，将字符 & 和实体名称 name 作为普通文本
          if (asAttr && !semi &&
              /[=a-z0-9]/i.test(rawText[name.length + 1] || '')
          ) {

            decodedText += '&' + name
            advance(1 + name.length)

          } else {
            // 其他情况正常使用解码后的内容拼接到 decodedText
            decodedText += value
            advance(1 + name.length)
          }

        } else {
          // 没找到对应值，解码失败
          decodedText += '&' + name
          advance(1 + name.length)
        }

      } else {
        // 如果字符 & 的下一个字符不是 ASCII 字母或数字，则将字符 & 作为普通文本
        decodedText += '&'
        advance(1)
      }
    }


  }
  return decodedText
}

解码数字字符引用

数字字符引用的格式是：前缀 + Unicode 码点。解码数字字符引用的关键在于，如何提取字符引用中的 Unicode 码点。考虑到数字字符引用的前缀可以是以十进制表示（&#），也可以是以十六进制表示（&#x），所以我们使用下面的代码来完成码点的提取：

// 判断十进制还是十六进制
const hex = head[0] === '&#x'
const pattern = hex ? /^&#x([0-9a-f]+);?/i : /^&#([0-9]+);?/i

// body[1] 的值就是 Unicode 码点
const body = pattern.exec(rawText)
// 调用 String.fromCodePoint 解码
if (body) {
    const cp = parseInt(body[1], hex ? 16 : 10)
    const char = String.fromCodePoint(cp)
}

在真正进行解码前，需要对码点的值进行合法性检查，这里就不做过多叙述了。

if (body) {
    let cp = parseInt(body[1], hex ? 16 : 10)
    
    // 检查合法性
    if (cp === 0) {
        // 如果码点值为 0x00，替换为 0xfffd
        cp = 0xfffd
    } else if (cp > 0x10ffff) {
        // 如果码点值超过 Unicode 的最大值，替换为 0xfffd
        cp = 0xfffd
    } else if (cp >= 0xd800 && cp <= 0xdfff) {
        // 如果码点值处于代理对 surrogate pair 范围内，替换为 0xfffd
        cp = 0xfffd
    } else if ((cp >= 0xfdd0 && cp <= 0xfdef) || (cp & 0xfffe) === 0xfffe) {
        // 如果码点值处于 noncharacter 范围内，则什么都不做，交给平台处理
        // noncharacter 代表 Unicode 永久保留的码点，用于 Unicode 内部
    } else if (
    	// 控制字符集的范围是：[0x01, 0x1f] 加上 [0x7f, 0x9f]
        // 去掉 ASICC 空白符：0x09(TAB)、0x0A(LF)、0x0C(FF)
        // 0x0D(CR) 虽然也是 ASICC 空白符，但需要包含
        (cp >= 0x01 && cp <= 0x08) || cp === 0x0b ||
        (cp >= 0x0d && cp <= 0x1f) || (cp >= 0x7f && cp <= 0x9f)
    ) {
        // 在 CCR_REPLACEMENTS 表中查找替换码点，如果找不到，则使用原码点
        cp = CCR_REPLACEMENTS[cp] || cp
    }
    // 最后进行解码
    const char = String.fromCodePoint(cp)
}

我们将上述代码整合到 decodeHtml 函数中，这样就实现一个完善的 HTML 文本解码函数。

export function decodeHTML(rawText: string, asAttr = false) {

 	...

  while (offset < end) {
    ...

    // 如果满足条件则是命名字符引用，否则为数字字符引用
    if (head[0] === '&') {
        
      ...
      
    } else {
      // 判断十进制还是十六进制
      const hex = head[0] === '&#x'
      const pattern = hex ? /^&#x([0-9a-f]+);?/i : /^&#([0-9]+);?/i

      // body[1] 的值就是 Unicode 码点
      const body = pattern.exec(rawText)
      // 调用 String.fromCodePoint 解码
      if (body) {
        let cp = parseInt(body[1], hex ? 16 : 10)

        // 检查合法性
        if (cp === 0) {
            // 如果码点值为 0x00，替换为 0xfffd
            cp = 0xfffd
        } else if (cp > 0x10ffff) {
            // 如果码点值超过 Unicode 的最大值，替换为 0xfffd
            cp = 0xfffd
        } else if (cp >= 0xd800 && cp <= 0xdfff) {
            // 如果码点值处于代理对 surrogate pair 范围内，替换为 0xfffd
            cp = 0xfffd
        } else if ((cp >= 0xfdd0 && cp <= 0xfdef) || (cp & 0xfffe) === 0xfffe) {
            // 如果码点值处于 noncharacter 范围内，则什么都不做，交给平台处理
            // noncharacter 代表 Unicode 永久保留的码点，用于 Unicode 内部
        } else if (
          // 控制字符集的范围是：[0x01, 0x1f] 加上 [0x7f, 0x9f]
            // 去掉 ASICC 空白符：0x09(TAB)、0x0A(LF)、0x0C(FF)
            // 0x0D(CR) 虽然也是 ASICC 空白符，但需要包含
            (cp >= 0x01 && cp <= 0x08) || cp === 0x0b ||
            (cp >= 0x0d && cp <= 0x1f) || (cp >= 0x7f && cp <= 0x9f)
        ) {
            // 在 CCR_REPLACEMENTS 表中查找替换码点，如果找不到，则使用原码点
            cp = CCR_REPLACEMENTS[cp] || cp
        }
        // 最后进行解码，追加到 decodedText 上
        const char = String.fromCodePoint(cp)
        decodedText += char

        // 消费整个数字字符引用的内容
        advance(body[0].length)

      } else {
        // 如果没有匹配，则不进行解码操作，只是把 head[0] 追加到decodedText 上并消费
        decodedText += head[0]
        advance(head[0].length)
      }
    }


  }
  
  return decodedText
  
}

解析插值与注释

文本插值是 Vue.js 模板中用来渲染动态数据的常用方法，默认情况下，插值以字符串结尾。我们通常将这两个特殊的字符串称为定界符。定界符中间的内容可以是任意合法的 JavaScript 表达式：

1	`{{ obj.fn() }}`

解析器在解析插值时，只需要将文本插值的开始定界符与结束定界符之间的内容提取出来，作为 JavaScript 表达式即可。

function parseInterpolation(context: parseCtx) {
  // 消费开始界定符号
  context.advanceBy('{{'.length)
  // 找到结束定界符的位置索引
  const closeIndex = context.source.indexOf("}}")
  if (closeIndex < 0) {
    console.error(`${context.source} is lack of '}}'`)
  }
  // 截取开始定界符于结束定界符之间的内容作为插值表达式
  const content = context.source.slice(0, closeIndex)
  // 消费表达式的内容
  context.advanceBy(content.length)
  // 消费结束定界符
  context.advanceBy("}}".length)

  // 返回类型为 Interpolation 的节点，代表插值节点
  return {
    type: 'Interpolation',
    content: {
      type: "Expression",
      content: decodeHTML(content)
    }
  }

}

解析注释的思路与解析插值非常相似：

function parseComment(context: parseCtx) {
  // 消费注释的开始部分
  context.advanceBy('<!--'.length)
  // 找到结束索引
  const closeIndex = context.source.indexOf("-->")
  if (closeIndex < 0) {
    console.error(`${context.source} is lack of '-->'`)
  }
  // 截取开始定界符于结束定界符之间的内容作为注释内容
  const content = context.source.slice(0, closeIndex)
  // 消费表达式的内容
  context.advanceBy(content.length)
  // 消费结束定界符
  context.advanceBy("-->".length)

  // 返回类型为 Interpolation 的节点，代表插值节点
  return {
    type: 'Comment',
    content
  }
}

编译优化

编译优化指的是编译器将模板编译为渲染函数的过程中，尽可能多地提取关键信息，并以此指导生成最优代码的过程。优化的方向基本一致，即尽可能地区分动态内容和静态内容，并针对不同的内容采用不同的优化策略。

动态节点收集与补丁标志

传统 Diff 算法的问题

无论哪一种 Diff 算法，当它在比对新旧两棵虚拟 DOM 树的时候，总是要按照虚拟 DOM 的层级结构“一层一层”地遍历。但是我们会发现，在有些模板中并不是所有的 DOM 节点都会发生变化，因此传统 diff 算法存在很多无意义的对比操作。

通过编译手段，我们可以分析出很多关键信息，例如哪些节点是静态的，哪些节点是动态的。为什么虚拟 DOM 会产生额外的性能开销呢？根本原因在于，渲染器在运行时得不到足够的信息。传统 Diff 算法无法利用编译时提取到的任何关键信息，这导致渲染器在运行时不可能去做相关的优化。而 Vue.js 3 的编译器会将编译时得到的关键信息“附着”在它生成的虚拟 DOM 上，这些信息会通过虚拟 DOM 传递给渲染器。最终，渲染器会根据这些关键信息执行“快捷路径”，从而提升运行时的性能。

`Block`与`PatchFlags`

只要运行时能够区分动态内容和静态内容，即可实现极致的优化策略。对于动态节点，我们为它加上一个额外的属性补丁标志patchFlag。我们可以把补丁标志理解为一系列数字标记，并根据数字值的不同赋予它不同的含义，示例如下：

数字 1 ：代表节点有动态的 textContent
数字 2 ：代表元素有动态的 class 绑定
数字 3 ：代表元素有动态的 style 绑定
数字 4 ： …

有了这项信息，我们就可以在虚拟节点的创建阶段，把它的动态子节点提取出来，并将其存储到该虚拟节点的dynamicChildren数组内，我们把带有该属性dynamicChildren数组的虚拟节点称为“块”（Block）。一个Block不仅能够收集它的直接动态子节点，还能够收集所有动态子代节点。

有了Block这个概念之后，渲染器的更新操作将会以Block为维度。也就是说，当渲染器在更新一个Block时，会忽略虚拟节点的children数组，而是直接找到该虚拟节点的dynamicChildren数组，并只更新该数组中的动态节点。同时，由于动态节点中存在对应的补丁标志，所以在更新动态节点的时候，也能够做到靶向更新。

当我们在编写模板代码的时候，所有模板的根节点都会是一个Block节点，带指令的节点也需要作为Block节点。

收集动态节点

在编译器生成的渲染函数代码中，并不会直接包含用来描述虚拟节点的数据结构，而是包含着用来创建虚拟 DOM 节点的辅助函数：

render() {
  return createVNode(...)
}
                       
function createVNode(
  tag: string, 
  props: Array<any>, 
  children: Array<any>, 
  patchFlag?: boolean
) {
  const key = props && props.key
  props && delete props.key
        
  return {
    tag,
    props,
    children,
    key
  }
}

当外层createVNode函数执行时，内层的createVNode函数已经执行完毕了。因此，为了让外层Block节点能够收集到内层动态节点，就需要一个栈结构的数据来临时存储内层的动态节点：

// 动态节点栈
const dynamicChildrenStack = []
// 当前动态节点集合
let currentDynamicChildren = undefined

/**
 * 创建动态节点集合并压栈
 * */
function openBlock() {
  dynamicChildrenStack.push((currentDynamicChildren = []))
}

/**
 * 通过 openBlock 创建的动态节点集合从栈中弹出
 * */
function closeBlock() {
  currentDynamicChildren = dynamicChildrenStack.pop()
}

function createVNode(
  tag,
  props,
  children,
  patchFlag
) {
  const key = props && props.key
  props && delete props.key

  const vnode: Block = {
    tag,
    props,
    children,
    key,
    PatchFlag: patchFlag
  }

  if (typeof patchFlag !== 'undefined' && currentDynamicChildren) {
    currentDynamicChildren.push(vnode)
  }

  return vnode

}

在createVNode函数内部，检测节点是否存在补丁标志。如果存在，则说明该节点是动态节点，于是将其添加到当前动态节点集合。我们还需要重新设计渲染函数的执行方式：

/*

<div>
	<div>{{ foo }}</div>
	<p> bar </p>
</div>

*/

render() {
    // 使用 createBlock 代替 createVNode 来创建根节点 block
    // 每当调用 createBlock 之前，先调用 openBlock
	return (openBlock(), createBlock('div', null, [
        createVNode('div', { class: 'foo'}, null, 1/*PatchFlag*/),
        createVNode('p', { class: 'bar'}, null,),
    ])	
}

function createBlock(
  tag,
  props,
  children
) {
  const block = createVNode(tag, props, children)
  block.dynamicChildren = currentDynamicChildren

  // 关闭 Block
  closeBlock()
  return block
}

由于createVNode函数和createBlock函数的执行顺序是从内向外，所以当createBlock数执行时，内层的所有createVNode函数已经执行完毕了。这时，currentDynamicChildren数组中所存储的就是属于当前Block的所有动态子代节点。

渲染器的运行时支持

在之前实现的patchElement函数中，渲染器在更新标签节点时，使用patchChildren函数来更新标签的子节点。但该函数会使用传统虚拟 DOM 的 Diff 算法进行更新，这样做效率比较低。有了dynamicChildren之后，我们可以直接对比动态节点。

function patchElement(oldNode, newNode) {
  ...

  if (newNode.dynamicChildren) {
    // 只更新动态节点
    patchBlockChildren(oldNode, newNode)
  } else {
    // 更新子节点
    patchChildren(oldNode, newNode, el)
  }

}

/**
 * 更新动态节点
 * */
function patchBlockChildren(oldNode, newNode) {
  for (let i = 0; newNode.dynamicChildren && i < newNode.dynamicChildren.length ; i++) {
    if (oldNode.dynamicChildren) {
      patchElement(oldNode.dynamicChildren[i], newNode.dynamicChildren[i])
    } else {
      console.error("Block does not exist.")
      break
    }
  }
}

动态节点集合能够使得渲染器在执行更新时跳过静态节点，但对于单个动态节点的更新来说，由于它存在对应的补丁标志，因此我们可以针对性地完成靶向更新：

function patchElement(oldNode, newNode) {
  ...

  // 靶向更新
  if (newNode.PatchFlag) {
    const flag = newNode.PatchFlag
    if (flag === 1) {
      // 更新 Text
    } else if(flag === 2) {
      // 更新 class
    } else if (flag === 3) {
      // 更新style
    }

  } else {
    // 全量更新props
    for (const key in newProps) {
      if (newProps[key] !== oldProps[key]) {
        patchProps(el, key, oldProps[key], newProps[key])
      }
    }
    // 将旧Props中不存在于新Props中的属性去掉
    for (const key in oldProps) {
      if (!(key in newProps)) {
        patchProps(el, key, oldProps[key], null)
      }
    }
  }
    
  ...

}

`Block`树

带有结构化指令的节点，如带有v-if和v-for指令的节点，都应该作为Block角色。

`v-if`

<div>
	<section v-if='foo'>
    	<p>
            {{ a }}
        </p>
    </section>
    <div v-else>
        <p>
            {{ a }}
        </p>
    </div>
</div>

dynamicChildren数组中收集的动态节点是忽略虚拟 DOM 树层级的。换句话说，结构化指令会导致更新前后模板的结构发生变化，即模板结构不稳定。我们也需要让带有v-if/v-else-if/v-else等结构化指令的节点作为Block角色即可。

1
2
3

Block(Div)
	- Block(Section v-if)
	- Block(Div v-else)

父级Block除了会收集动态子代节点之外，也会收集子Block。因此，两个子Block(section)将作为父级Block(div)的动态节点被收集到父级Block(div)的dynamicChildren数组中。

const block = {
    tag: 'div',
    dynamicChildren: [
        /* Block(Section v-if) 或 Block(Section v-else)*/
        {
            tag: 'section', 
            {key : 0},
        	dynamicChildren: [...]
        }
    ]
}

当v-if条件为真时，父级Block的dynamicChildren数组中包含的是Block(section v-if)；当v-if的条件为假时，父级Block的dynamicChildren数组中包含的将是Block(section v-else)。在 Diff 过程中，渲染器能够根据Block的key值区分出更新前后的两个Block是不同的，并使用新的Block替换旧的Block。这样就解决了 DOM 结构不稳定引起的更新问题。

`v-for`

对于如下模板：

<div>
    <p v-for="item in list">
        {{ item }}
    </p>
    <i>
    	{{ foo }}
    </i>
    <i>
    	{{ bar }}
    </i>
</div>

由于传统 Diff 的一个非常重要的前置条件是：进行 Diff 操作的节点必须是同层级节点。但是dynamicChildren数组内的节点未必是同层级的。解决方法很简单，我们只需要让带有 v-for 指令的标签也作为 Block 角色即可。这样就能够保证虚拟 DOM 树具有稳定的结构，即无论 v-for 在运行时怎样变化，这棵 Block 树看上去都是一样的：

const block = {
    tag: 'div',
    dynamicChildren: [
        { tag: Fragment, dynamicChildren: [/* v-for 的节点*/] }，
        { tag: 'i', children: ctx.foo, 1/* TEXT */ },
        { tag: 'i', children: ctx.bar, 1/* TEXT */ },
    ]
}

由于v-for指令渲染的是一个片段，所以我们需要使用类型为Fragment的节点来表达v-for指令的渲染结果，并作为 Block 角色。

`Fragment`稳定性

所谓结构不稳定，从结果上看，指的是更新前后一个 block 的dynamicChildren数组中收集的动态节点的数量或顺序不一致。其实对于这种情况，没有更好的解决办法，我们只能放弃根据dynamicChildren数组中的动态节点进行靶向更新的思路，并回退到传统虚拟 DOM 的 Diff 手段，即直接使用Fragment的children而非dynamicChildren来进行 Diff 操作。

但需要注意的是，Fragment的子节点（children）仍然可以是由 Block 组成的数组

而对于稳定的Fragment：

v-for 指令的表达式是常量
模板中有多个根节点。同时，用于描述具有多个根节点的模板的Fragment也是稳定的。

静态提升

静态提升，即把纯静态的节点提升到渲染函数之外，能够减少更新时创建虚拟 DOM 带来的性能开销和内存占用。

// 把静态节点提升到渲染函数之外
const hoist1 = createVNode('p', null, 'text')

function render() {
	return (openBlock(), createBlock('div', null, [
        hoist1,
        createVNode('p', null, ctx.title, 1/* TEXT */)
    ]))
}

静态提升是以树为单位的：

<div>
    <section>
    	<p>
            <span> abc </span>
        </p>
    </section>
</div>

在上面这段模板中，除了根节点会作为Block角色不可提升之外，整个section元素及其子节点都会被提升，如果把上面模板中的静态字符串abc换成动态绑定的{{ abc }}，那么整棵树都不会被提升。

虽然包含动态绑定的节点本身不会被提升，但是该动态节点上仍然可能存在纯静态的属性。遇到静态属性时，可以把它们提升到渲染函数之外：

/*
<div>
	<p foo='bar' a=b> {{ text }} </p>
</div>
*/

// 静态提升的 props 对象  
const hoistProp = { foo: 'bar', a: 'b'}

functiono render(ctx) {
    return (openBlock(), createBlock('div', null, [
        createVNode('p', hoistProp, ctx.text)
    ]))
}

预字符串化

假设模板中包含大量连续纯静态的标签节点，当采用了静态提升优化策略后，预字符串化能够将这些静态节点序列化为字符串，并生成一个Static类型的VNode：

const hoistStatic = createStaticVNode('<p></p><p></p><p></p><p></p>')

render() {
    return (openBlock(), createBlock('div', null, [
        hoistStatic
    ]))
}

这么做有几个明显的优势：

大块的静态内容可以通过 innerHTML 进行设置，在性能上具有一定优势。
减少创建虚拟节点产生的性能开销。
减少内存占用。

缓存内联事件处理函数

缓存内联事件处理函数可以避免不必要的更新。

1	`<Comp @change='a+b'/>`

对于这样的模板，编译器会为其创建一个内联事件处理函数：

function render(ctx) {
    return h(Comp, {
        // 内联时间处理函数
        onChange: () => (ctx.a + ctx.b)
    })
}

每次重新渲染时（即 render 函数重新执行时），都会为 Comp 组件创建一个全新的props对象。同时，props对象中onChange属性的值也会是全新的函数。这会导致渲染器对Comp组件进行更新，造成额外的性能开销。为了避免这类无用的更新，我们需要对内联事件处理函数进行缓存：

function render(ctx) {
    return h(Comp, {
        // 内联时间处理函数
        onChange: () => cache[0] || 
        (cache[0] = ($event) => (ctx.a + ctx.b))
    })
}

这样，当渲染函数重新执行并创建新的虚拟 DOM 树时，会优先读取缓存中的事件处理函数。无论执行多少次渲染函数，props对象中onChange属性的值始终不变，于是就不会触发 Comp 组件更新了。

`v-once`

配合v-once还可实现对虚拟 DOM 的缓存。当编译器遇到v-once指令时，会利用我们上一节介绍的cache数组来缓存渲染函数的全部或者部分执行结果。

<section>
	<div v-once>
        {{ foo }}
    </div>
</section>

函数重新执行时，会优先读取缓存的内容，而不会重新创建虚拟节点。同时，由于虚拟节点被缓存，意味着更新前后的虚拟节点不会发生变化，因此也就不需要这些被缓存的虚拟节点参与 Diff 操作了。

render(ctx, cache) {
	return (openBlock(), createBlock('div', null, [
        cache[1] || (
        	setBlockTracking(-1),	// 阻止这段 VNode 被 Block 收集
            cache[1] = h('div', null, ctx.foo, 1 /* TEXT */ ),
            setBlockTracking(1),	// 恢复
            cache[1]				// 整个表达式的值
    ]))
}

上面这段代码中的setBlockTracking(-1)函数调用，它用来暂停动态节点的收集。换句话说，使用v-once包裹的动态节点不会被父级Block收集。因此，被v-once包裹的动态节点在组件更新时，自然不会参与Diff操作。

v-once 指令通常用于不会发生改变的动态绑定中，为了提升性能，我们可以使用v-once来标记，这样，在组件更新时就会跳过这段内容的更新，从而提升更新性能：

避免组件更新时重新创建虚拟 DOM 带来的性能开销。因为虚拟 DOM 被缓存了，所以更新时无须重新创建。
避免无用的 Diff 开销。这是因为被 v-once 标记的虚拟 DOM 树不会被父级 Block 节点收集。

总结

Vue.js 的模板编译器用于把模板编译为渲染函数。它的工作流程大致分为三个步骤：

分析模板，将其解析为模板 AST。
将模板 AST 转换为用于描述渲染函数的 JavaScript AST。
根据 JavaScript AST 生成渲染函数代码。

我们使用parse来用有限状态自动机构造一个词法分析器，用transform进行转换，最后调用generate进行代码生成。

对于解析器，我们需要了解文本模式，指的是解析器在工作时所进入的一些特殊状态。在解析模板构建 AST 的过程中，parseChildren函数是核心。每次调用parseChildren函数，就意味着新状态机的开启。对于命名字符引用，命名字符引用的解码方案可以总结为两种：当存在分号时执行完整匹配；当省略分号时执行最短匹配。对于数字字符引用，则需要按照 WHATWG 规范中定义的规则逐步实现。

编译优化指的是通过编译的手段提取关键信息，并以此指导生成最优代码的过程。编译优化的核心在于，区分动态节点与静态节点。一个 Block 本质上也是一个虚拟节点，但与普通虚拟节点相比，会多出一个dynamicChildren数组。该数组用来收集所有动态子代节点，这利用了createVNode函数和createBlock函数的层层嵌套调用的特点，即以“由内向外”的方式执行。再配合一个用来临时存储动态节点的节点栈，即可完成动态子代节点的收集。

v-if、v-for等结构化指令会影响 DOM 层级结构，使之不稳定。这会间接导致基于Block树的比对算法失效。而解决方式很简单，只需要让带有v-if、v-for等指令的节点也作为 Block 角色即可。

静态提升：能够减少更新时创建虚拟 DOM 带来的性能开销和内存占用。
预字符串化：在静态提升的基础上，对静态节点进行字符串化。这样做能够减少创建虚拟节点产生的性能开销以及内存占用。
缓存内联事件处理函数：避免造成不必要的组件更新。
v-once指令：缓存全部或部分虚拟节点，能够避免组件更新时重新创建虚拟 DOM 带来的性能开销，也可以避免无用的 Diff 操作。