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));
console.log(time);
|
上面的代码中新增一个变量，用于记录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));
console.log(time);
|
引入缓存后，调用次数变成了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
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));
|
写法二
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();
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;
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" }
]
}
]
}
|