乐趣区

关于vue.js:Vue源码解读四AST抽象语法树

本篇内容是在模板引擎的根底上,联合虚构 DOM 进行的探讨,基于三者之间的关系,总结出下图示意:

graph TD
    A[模板语法] -->| 解析 | B(形象语法树 AST)
    B --> | 调用 |C[渲染函数即 h 函数]
    C -->| 生成 | D[虚构节点 diff/patch]
    D --> | 更新 | E(界面)

1. 形象语法树 (AST) 是什么?

形象语法树,Abstract Syntax Tree(简称:AST)实质上就是一个 js 对象。
模板语法先变成 形象语法树 ,而后再将 语法树(次要起过渡作用)编译为失常的 HTML 语法。
vue 中应用模板语法所写的 html 构造,不是真正的 dom,vue 底层视作字符串,逐字审查字符串,解析为 JS 对象。

2. 形象语法树和虚构节点的关系?

如前文图示,模板语法 -> 形象语法树 AST-> 渲染函数(h 函数)-> 虚构节点 -(diff/patch)> 界面
那既然曾经理解了 AST 是由模板语法失去的,那这个处理过程到底是怎么进行的呢?先从与此相关的最根本算法说起~

3. 相干算法储备

1). 指针思维 (JS 中的指针只是字符串或者数组的一个 下标地位 ,不同于 C 语言中的指针,多说一句,C 语言中的指针是能够操作内存的)
在此列一个算法例子,领会指针在 js 中的利用:找出字符串 aaaaaabbbbbbbcccccccccccccddddd’ 中,间断反复呈现次数最多的字符。
在解这个算法的时候,既然有“最多”,那必然是有比拟,而比拟的对象至多得有两个,因而首先就要想到咱们须要设置两个指针,而这两个指针的地位如何确定呢?再一看题目是“间断”,所以两指针的初始地位必然是相邻的,如下图:

确定了 i,j 两指针地位后,就开始进行比拟了,比拟过程中如果 i,j 指向的字符雷同,则 i 不动,j 后移;否则将 j 此刻的值赋给 i,j 后移一位,阐明在赋值之前,i,j 之前的字符都是雷同的;开启新一轮 i,j 是否雷同的比拟,比拟的完结条件是 i 不小于这个字符串的长度 length。
剖析完解题思路,代码就好写了:

// 给定一个字符串
var str = 'aaaaaabbbbbbbcccccccccccccddddd';
// 设置两指针
var i = 0, j = 1;
// 记录反复最多次数
var maxRepeat = 0;
// 记录反复最多的字符;var maxRepeatStr= '';
// 当 i 还在范畴内的时候,应该持续寻找
while(i <= str.length - 1) {
  // 看 i 指向的字符和 j 指向的字符是不是不雷同
  if (str[i] ==== str[j]) {j++;} else {// console.log(i+'和'+j+'之间的文字间断雷同,字母'+str[i]+'反复了'+ (j - i) + '次')
    // 和以后反复次数最多的进行比拟
    if (j - i > maxRepeat) {
      // 如果以后文字反复次数(j-i)超过了此时的最大值
      // 就让它成为最大值
      maxRepeat = j - i;
      maxRepeatStr = str[i]
    }
    i = j;
    j++;
  }
}
// 循环完结之后,就能够输入答案了
console.log('maxRepeatChar', maxRepeatChar)

2)递归深刻 - 即规定复现
同上列举一个例子,领会递归的运算效率:试输入斐波那契数列的前 10 项,即 1、1、2、3、5、8、13、21、34、55。而后请思考,代码是否有大量反复的计算?应该如何解决反复计算?
察看推理得出,这一列数字从第三项起都是本身得前两项之和,所以每次只有前两项相加即可,高级代码如下:

// 试输入斐波那契数列的前 10 项,即 1、1、2、3、5、8、13、21、34、55
// 创立一个函数,性能是返回下标为 n 的这项的数字
// 递归须要有起点
function fib(n) {console.log('fid-n:', n)
  // 看下标 n 是不是 0 或 1,如果是,返回常数 1
  // 如果不是,就递归
  return n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2)
}
for (var i = 0; i < 9; i++) {console.log(fib(i))
}

这样做的内存开销是十分大的,相当于每次计算都须要把前两项再计算一下

所以优化以上的算法,在此引入一个缓存的概念,这样每次计算的值都进行缓存,再进行下次计算时只须要把缓存里的两项拿进去做计算就能够。

for(var i = 0; i < 10; i ++) {console.log(fib(i));
}
// 定义一个缓存对象,用来寄存曾经计算的项
var  cache = {};
function fib(n) {
  // 判断缓存对象中有没有这个值,如果有,间接返回
  if (cache.hasOwnProperty(n)) {return cache[n]
  }
  // 缓存对象没有这个值
  // 看下标 n 是不是 0 或 1,如果是,返回常数 1
  // 如果不是,就递归
  var v = (n === 0 || n === 1) ? 1 : fib(n -1) + fib(n - 2);
  // 写入缓存,也就是说,每算一个值,就要把这个值存入缓存对象
  cache[n] = v;
  return v;
}

3)递归的深刻用法 (离最终的 AST 算法越来越靠近了~)
试将高维数组 [1, 2, [3, [4, 5], 6], 7, [8], 9] 变为图中所示的对象

{
   children: [{value: 1},
       {value: 2},
       { children: [{value: 3},
            { children: [{ value: 4},
                {value: 5}
             ]},
             {value: 6}
        ]},
        {value: 7},
        { children: [{ value: 8},
            {value: 9}
        ]}
   ]
}

这个算法是将多维数组解决为一个对象,从第一层去遍历,如果是数字,则存为对象,若是数组,则存为该层的一个子级 chldren,再依照此法则解决本人里边的数字,数组,直到再没有数组为止。通常的做法是将这个数组作为整体去递归:

// 解法①
// 测试数组
var arr = [1,2, 3, [4, 5, [6, 7], 8], 9];
var indexI = 0;
// 转换函数
function convert(arr) {
  indexI++;
  // 筹备一个后果数组
  var result = [];
  // 遍历传入的 arr 的每一项
  for (var i = 0; i < arr.length; i++) {
    // 如果遍历到的数字是 number,间接放进去
    if (typeof arr[i] == "number") {result.push({value: arr[i]})
    } else if (Array.isArray(arr[i])) {
      // 如果遍历到的是数组,先建一个 children
      result.push({children: convert(arr[i])
      })
      console.log('result:', result)
    }
  }
  // console.log('result:', result)
  return result;
}
var obj = convert(arr)
console.log(indexI) // 3
console.log(obj)
// 解法②
// 测试数组
var arr1 = [1,2, 3, [4, 5, [6, 7], 8], 9];
var indexJ = 0;
// 转换函数
// 即写法 1 的递归次数小于写法②,写法②中,遇见任何类型数据都要递归一下
function convert1(item) {
  indexJ++;
  if (typeof item == 'number') {return {value: item}
  } else if (Array.isArray(item)) {
    // 如果传进来的参数是数组
    return {children: item.map(_item => convert1(_item))
    }
  }
}
var obj1 = convert1(arr1)
console.log(indexJ) // 12
console.log(obj1)

4)堆栈

  • 又名 堆栈 ,它是一种运算受限的线性表,仅在 表尾 能进行 插入 删除操作 。这一端被称为 栈顶 ,绝对地,把另一端称为 栈底
  • 向一个栈插入新元素又称作 进栈 入栈 压栈 ;从一个栈删除元素又称作 出栈 退栈
  • 后进先出 (LIFO) 特点:栈中的元素,最先进栈的必然最初出栈,后进栈的肯定会先出栈。
  • JS 中,栈能够用 数组 模仿。须要限度只能应用 push()和 pop(),不能应用 unshift()和 shift()。即 数组尾是栈顶
  • 能够用面向对象等伎俩,将栈封装的更好。
  • 栈栈和递归十分像
  • 词法剖析的时候,常常要用到栈这个数据结构

    试编写“智能反复”smartRepeat 函数,实现:
    将 3[abc]变为 abcabcabc
    将 3[2[a]2[b]]变为 aabbaabbaabb
    将 2[1[a]3[b]2[34[d]]]变为 abbbcccddddcccddddabbbcccddddcccdddd
    不必思考输出字符串是非法的状况,比方:
    2[a3[b]]是谬误的,应该补一个 1,即 2[1[a]3[b]]
    [abc]是谬误的,应该补一个 1,即 1[abc]
    看到这个题目,是不是跟下面的指针的例子有点前后响应了,指针的例子是找出反复的字符,而这这个例子则是依照 [ 前的数字开展字符。
    联合栈的概念,那这个例子的解法思路是:
  • 遍历每一个字符,如果是数字,那么就将该数字压入栈①;如果是[,就把空字符串压入栈②;如果是字母,就用这个字符替换栈②顶的空字符串;
  • 如果是 ],就将栈①中的数字 n 弹栈,再把栈②中栈顶的字母反复 n(这个数字) 次数,从栈②中弹出,拼接到新栈②的顶上。
function smartRepeat(templateStr) {
  let index = 0; // 指针
  let stack1 = [], stack2 = []; // stack1 寄存数字,stack2 寄存长期字符串
  var rest = templateStr; // 字符串残余局部
  while(index < templateStr.length - 1){ // 遍历
    rest = templateStr.substring(index); // 残余局部
    if (/^\d+\[/.test(rest)){ // 看以后残余局部是不是以数字和[结尾
      let times = Number(rest.match(/^(\d+)\[/)[1]); // 失去这个数字
      stack1.push(times); // 就把数字压栈
      stack2.push('') // 把空字符串压栈
      index += times.toString().length + 1;  // 让指针后移,times 这个数字是多少位数,就后移多少位在加 1} else if (/^\w+]/.test(rest)){
      // 如果是字母,那么此时就把栈顶这项改为这个字母
      let word = rest.match(/^(\w+)\]/)[1];
      stack2[stack2.length - 1] = word;
      // 让指针后移,word 这个数字是多少位数,就后移多少位在加 1
      index += word.length
    } else {// 如果这个字符是],那么就
      // Ⅰ将 stack1 弹栈,就把字符串栈②的栈②顶的元素反复刚刚这个数字次数,let times_pop = stack1.pop();
      // Ⅱ弹栈②(stack2),let word = stack2.pop();
      // Ⅲ把字符串栈的新栈顶的元素反复刚刚弹出的那个字符串指定次数,拼接到新栈②顶上
      // repeat 是 es6 的办法,比方 'a'.repeat(3), 失去 'aaa'
      stack2[stack2.length - 1] += word.repeat(times_pop)
      index += 1
    }
  }
  // while 完结之后,stack1 和 stack2 中必定还残余 1 项。// 返回栈 2 中剩下的这一项,反复栈 1 中剩下的这 1 项次数,组成这个字符串
  // 如果剩的个数不对,那就是方括号]没有闭合
  return stack2[0].repeat(stack1[0])
}
var str = smartRepeat('3[1[a]3[b]2[34[d]]]')
console.log(str) // abbbcccddddcccddddabbbcccddddcccddddabbbcccddddcccdddd

AST 的造成

有了后面四局部的铺垫,根本把握了 AST 所须要的算法及数据结构,上面给出一个模板字符串(相当于 vue 种 template 中的模板)

var templateString = `
    <div class="box aa" id="mybox">
        <h3> 你好 </h3>
        <ul>
            <li>A</li>
            <li>B</li>
            <li>C</li>
            <li>D</li>
        </ul>
    </div>
`
var ast = parse(templateString)
console.log('ast:\n', ast)

parse 函数就是将模板解析为 AST,最终返回 AST,解析过程和上例基本相同:

parse.js
export default function (templateString) {
    // 指针
    var index = 0;
    // 残余局部
    var rest = '';
    // 开始标记
    var startRegExp = /^\<([a-z]+[1-6]?)(\s[^\<]+)?\>/;
    // 完结标记
    var endRegExp = /^\<\/([a-z]+[1-6]?)/;
    // 筹备两个栈;var stack1 = [];
    var stack2 = [{children: []}];
    // 抓取完结标记前的文字
    var wordRepExp = /^([^\<]+)\<\/[a-z]+[1-6]/
    while (index < templateString.length - 1) {rest = templateString.substring(index)
        // console.log(templateString[index])
        // 辨认遍历到的这个字符,是不是一个开始标签
        if (startRegExp.test(rest)) {let tag = rest.match(startRegExp)[1];
            let attrsString = rest.match(startRegExp)[2];
            // console.log('检测到开始标记:', tag)
            // 将开始标记推入栈中
            stack1.push(tag)
            stack2.push({children: [], tag: tag, attrs: parseAttrString(attrsString)})
            // 指针挪动标签的长度加 2 再加 attrsString 的长度,因为 <> 占两位
            const attrLen = attrsString ? attrsString.length : 0;
            index += tag.length + 2 + attrLen;
        } else if (endRegExp.test(rest)) {
            //  辨认遍历到的字符,是不是完结标签
            // 指针挪动标签的长度加 3,因为 </> 占三位
            let tag = rest.match(endRegExp)[1];
            // 此时 tag 肯定是和 stack1 栈顶元素雷同的
            let pop_tag = stack1.pop();
            if (tag == pop_tag) {let pop_arr = stack2.pop();
                if (stack2.length) {// 查看 stack2[stack2.length - 1]是否有 children 属性,如果没有就创立一个数组
                    stack2[stack2.length - 1].children.push(pop_arr)
                }
            } else {throw new Error(stack1[stack1.length - 1] + '标签没有关闭')
            }
            // console.log('检测到完结标记:', tag)
            index += tag.length + 3;
            // console.log(stack1, JSON.stringify(stack2))
        } else if (wordRepExp.test(rest)) {
            // 辨认遍历到的这个字符,是不是文字,并且不是全空
            let word = rest.match(wordRepExp)[1];
            // 看 word 是不是全是空
            if (!/^\s+$/.test(rest)) {
                // 不是空
                // console.log('检测到文字 -', word)
                // 扭转此时 sctack2 栈顶元素
                stack2[stack2.length - 1].children.push({
                    'text': word,
                    'type': 3
                })
            }
            // 指针挪动标签的长度加字符长度
            index += word.length;
        } else {
            // 标签中的文字
            index++;
        }
    }
    // console.log(stack2)
    // 此时 stack2 就是咱们之前默认搁置的一项了,此时要返回这一项的 children 即可
    return stack2[0].children[0];
}

在这个 AST 的合成过程,还有一个不能疏忽的细节是:标签所带的属性,如 class,id 等,所以 parseAttrString 函数中就是对标签属性的解决:

parseAttrString.js
// 把 attrsString 组装为数组之后返回
export default function (attrsString) {if (!attrsString) return []
    // console.log('attrsString', attrsString)
    // 以后是否在引号内
    var isYinhao = false;
    // 断点
    var point = 0;
    // 完结数组
    var result = [];
    // 遍历 attrsString,而不是用 split()一个空格分隔
    for (let i = 0; i < attrsString.length; i++) {let char = attrsString[i];
        if (char == '"') {isYinhao = !isYinhao} else if (char == ' ' && !isYinhao) {
            // 遇见了空格,并且不在引号内
            // console.log(i)
            if (!/^\s*$/.test(attrsString.substring(point, i))) {result.push(attrsString.substring(point, i).trim())
            }
            point = i;
        }
    }
    // 循环完结之后,最初还剩一个属性 k -v
    result.push(attrsString.substring(point).trim())
    // 上面的代码性能是:将 ["k=v","k=v", "k=v"] 变为 [{name: k, value: v}, {name: k, value: v}] 这种类型
    result = result.map(item => {
        // 依据等号拆分
        const o = item.match(/^(.+)="(.+)"$/);
        return {name: o[1],
            value: o[2]
        }
    })
    console.log(result)
    return result
}
退出移动版