Vue.js AST抽象语法树

发表于 更新于 分类于

AST(Abstract Syntax Tree)抽象语法树，Vue中的AST实际上是一个js对象，它用于把我们写的模板转换成h函数，然后通过h函数生成虚拟节点，虚拟节点再生成真实的DOM节点。

知识储备

双指针算法

有一个字符串aaaaaabbbbbbbcccccccccccccccccccccccccddddddd，现在需要找到字符串中连续重复次数最多的一个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var str = "aaaaaabbbbbbbcccccccccccccccccccccccccddddddd";
var i = 0, j = 0;
var maxRepeatChar = '', maxRepeatTime = 0;
while (i <= str.length - 1) {
    if (str[i] != str[j]) {
        if ((j - i) > maxRepeatTime) {
            maxRepeatChar = str[i];
            maxRepeatTime = (j - i);
        }
        i = j;
    }
    j++;
}
console.log(maxRepeatTime, maxRepeatChar);

递归

缓存

输出斐波那契数列的第十项。

一般来说直接想到的想法就是直接递归：

1
2
3
4
5
6
7
8
9
var cache = {};
var time = 0;
function fib(n) {
    var res = n == 1 || n == 0 ? 1 : fib(n - 1) + fib(n - 2);
    time++;
    return res;
}
console.log(fib(10)); // 89
console.log(time);  // 177

上面的代码中新增一个变量，用于记录fib函数调用的次数，可以看到fib函数被调用了177次，是因为在递归计算每一项的时候，都在一直向下计算到fib(0)，导致调用次数多。我们可以使用缓存来减少调用的次数：

1
2
3
4
5
6
7
8
9
10
11
12
13
var cache = {};
var time = 0;
function fib(n) {
    if (n in cache) {
        return cache[n];
    }
    var res = n == 1 || n == 0 ? 1 : fib(n - 1) + fib(n - 2);
    time++;
    cache[n] = res;
    return res;
}
console.log(fib(10)); // 89
console.log(time); // 11

引入缓存后，调用次数变成了11，大大减少了函数的调用次数。

多维数组转换

把数组[1, 2, 3, [4, 5, [6, 7]], [8], 9]转换成下面的JavaScript对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[
    {"value": 1},
    {"value": 2},
    {"value": 3},
    {
        "children": [
            {"value": 4},
            {"value": 5},
            {
                "children": [
                    {"value": 6},
                    {"value": 7}
                ]
            }
        ]
    },
    {
        "children": [
            {"value": 8}
        ]
    },
    {"value": 9}
]

  1. 写法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    var arr = [1, 2, 3, [4, 5, [6, 7]], [8], 9];

    function convert(arr) {
        var res = [];
        for (let i = 0; i < arr.length; i++) {
            if (typeof arr[i] == "number") {
                res.push({ value: arr[i] });
            } else if (Array.isArray(arr[i])) {
                res.push({
                    children: convert(arr[i])
                });
            }
        }
        return res;
    }

    console.log(convert(arr));

  2. 写法二

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    var arr = [1, 2, 3, [4, 5, [6, 7]], [8], 9];

    function convert(item) {
        if (typeof item == "number") {
            return { value: item }
        } else if (Array.isArray(item)) {
            return {
                children: item.map(v => convert(v))
            }
        }
    }

    console.log(convert(arr));

写法二虽然更加简洁，但是递归调用的次数要比写法一要多。

栈

编写smartRepeat函数，实现：

  • 将3[abc]转换成abcabcabc
  • 将2[1[a]3[b]2[3[c]4[d]]]转换成abbbcccddddcccddddabbbcccddddcccdddd
  • 将3[2[a]2[b]]转换成aabbaabbaabb

这题的思路是遍历字符串，有两个栈，一个栈用来存数字，一个栈用来存字符串。当遇到数字时，数字进栈，同时将一个空字符串压栈；如果遇到了字符或字符串，就把字符串栈的栈顶变成该字符串；如果遇到了]，数字栈和字符串栈同时出栈一个元素，字符串栈的栈顶变成字符串出栈的元素重复数字栈出栈的元素的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function smartRepeat(str) {
    var result = "";
    var idx = 0;
    var numStack = [], strStack = [];
    var res = str;
    while (idx < str.length - 1) {
        res = str.substring(idx)
        if (/^\d+\[/.test(res)) {
            let matched = res.match(/^(\d+)\[/)[1];
            idx += matched.length + 1;
            let num = parseInt(matched)
            numStack.push(num);
            strStack.push("");
        } else if (/^\w+/.test(res)) {
            let matched = res.match(/^(\w+)/)[1];
            idx += matched.length;
            strStack[strStack.length - 1] = matched;
        } else if (res[0] == ']') {
            let time = numStack.pop();
            let word = strStack.pop();
            word = word.repeat(time);
            strStack[strStack.length - 1] += word;
            idx++;
        }
    }
    return strStack[0].repeat(numStack[0])
}

console.log(smartRepeat("3[2[a]2[b]]"));

AST实现原理

AST实现原理和上面栈的算法很像。假如有下面的模板字符串：

1
2
3
4
5
6
7
8
<div class="box" id="box1">
    <h3 class="title">Hello World</h3>
    <ul>
        <li class="item">A</li>
        <li class="item">B</li>
        <li class="item">C</li>
    </ul>
</div>

先创建两个栈，一个用来存放标签，一个用来存放元素。遍历字符串，如果遇到了开始标签，就先提取出标签名和属性，然后向元素栈入栈，再修改指针的位置；如果遇到了结束标签，先判断结束标签和标签栈的栈顶是不是一样的，元素栈栈顶出栈，并保存起来，push进元素栈新栈顶的children中；如果遇到文字，就先判断文字是不是空字符串，如果不是的话，就把文字push进元素栈顶的children中。遍历完成后，结果就是元素栈的栈顶元素。

parse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import parseAttrs from "./parseAttrs";

export default function parse(templateStr) {
    var idx = 0;
    // 剩余字符串
    var rest = "";
    // 开始标记正则,结束标记正则,文字正则
    var startTagRegExp = /^\<([a-z]+[1-6]?)(\s[^\<]+)?\>/;
    var endTagRegExp = /^\<\/([a-z]+[1-6]?)\>/;
    var wordRegExp = /^([^\<]+)\<\/[a-z]+[1-6]?\>/;
    // 一个标记栈,一个元素栈
    var tagStack = [], eleStack = [{ children: [] }];

    // 开始遍历模板字符串
    while (idx < templateStr.length) {
        rest = templateStr.substring(idx);
        // 检测到开始标签
        if (startTagRegExp.test(rest)) {
            // 匹配标签名
            let tag = rest.match(startTagRegExp)[1];
            // 匹配属性
            let attrs = rest.match(startTagRegExp)[2];
            tagStack.push(tag);
            // 元素入栈
            eleStack.push({ tag: tag, children: [], attrs: attrs == undefined ? [] : parseAttrs(attrs) });
            // 修改指针的位置
            idx += tag.length + 2;
            idx += attrs == undefined ? 0 : attrs.length;
        }
        // 检测到结束标签
        else if (endTagRegExp.test(rest)) {
            // 获取结束标签名称
            let tag = rest.match(endTagRegExp)[1];
            // 如果结束标签名称等于标签栈栈顶
            if (tag == tagStack[tagStack.length - 1]) {
                // 出栈
                tagStack.pop();
                let pop = eleStack.pop();
                // 将元素栈顶出栈,并加入到新栈顶的children中
                if (eleStack.length > 0) {
                    eleStack[eleStack.length - 1].children.push(pop);
                }
            } else {
                throw new Error(tagStack[tagStack.length - 1] + "missing end tag!")
            }
            idx += tag.length + 3;
        }
        // 检测到文字
        else if (wordRegExp.test(rest)) {
            // 提取文字
            let word = rest.match(wordRegExp)[1]
            // 检测文字是不是空字符
            if (!/^\s+$/.test(word)) {
                idx += word.length;
                // 将提取到的文字,加到元素栈顶的children中
                eleStack[eleStack.length - 1].children.push({ text: word, type: 3 })
            } else {
                idx += word.length;
            }
        } else {
            idx++;
        }
    }
    return eleStack[0];
}

parseAttrs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
export default function parseAttrs(str) {
    // 是不是在引号里
    var isInQuote = false;
    // 断点
    var point = 0;
    var result = []
    str = str.trim();
    // 遍历字符串
    for (let i = 0; i < str.length; i++) {
        // 如果字符是引号
        if (str[i] == '"') {
            // 取反
            isInQuote = !isInQuote;
            // 如果是字符串中的最后一个引号,就直接切割字符串,放进结果数组
            if (i == str.length - 1) {
                result.push(str.slice(point, i + 1).trim());
            }
        }
        // 如果字符是空格,并且不在引号里
        else if (str[i] == " " && !isInQuote) {
            // 先判断是不是空字符串
            if (!/^\s*$/.test(str.slice(point, i))) {
                // 如果不是的话就切割,放进结果字符串
                result.push(str.slice(point, i).trim());
                point = i;
            }
        }
    }


    // 将结果字符串转成映射对象
    result = result.map(v => {
        var matched = v.match(/^(.+)="(.+)"$/);
        return {
            name: matched[1],
            value: matched[2]
        }
    })
    return result;
}

在HTML文件中引入该js文件：

1
2
3
4
5
6
7
import parse from "./parse";

var templateStr = document.querySelector("script[type='text/template']").innerHTML;

var ast = parse(templateStr);

console.log(ast);

上面示例的模板字符串转换成AST的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
{
    "children": [
        {
            "tag": "div",
            "children": [
                {
                    "tag": "h3",
                    "children": [{ "text": "Hello World", "type": 3 }],
                    "attrs": [{ "name": "class", "value": "title" }]
                },
                {
                    "tag": "ul", "children": [
                        {
                            "tag": "li",
                            "children": [{ "text": "A", "type": 3 }],
                            "attrs": [{ "name": "class", "value": "item" }]
                        },
                        {
                            "tag": "li",
                            "children": [{ "text": "B", "type": 3 }],
                            "attrs": [{ "name": "class", "value": "item" }]
                        },
                        {
                            "tag": "li",
                            "children": [{ "text": "C", "type": 3 }],
                            "attrs": [{ "name": "class", "value": "item" }]
                        }],
                    "attrs": []
                }
            ],
            "attrs": [
                { "name": "class", "value": "box" },
                { "name": "id", "value": "box1" }
            ]
        }
    ]
}