kitten.sh
1const _state = 'state';
2const _node = 'node';
3const _match = 'x';
4
5function js(/* arguments */) {
6 let body = arguments[0][0];
7 for (let i = 1; i < arguments.length; i++)
8 body = body + arguments[i] + arguments[0][i];
9 return body.trim();
10}
11
12const copy = (prev) => {
13 const next = {};
14 for (const key in prev) next[key] = prev[key];
15 return next;
16};
17
18const assignIndex = (depth) => js`
19 var y${depth} = ${_state}.y,
20 x${depth} = ${_state}.x;
21`;
22
23const restoreIndex = (depth) => js`
24 ${_state}.y = y${depth};
25 ${_state}.x = x${depth};
26`;
27
28const astExpression = (ast, depth, opts) => {
29 const capture = !!opts.capture && !ast.capture;
30 const restoreLength =
31 (opts.length && opts.abort && js`${_node}.length = ln${opts.length};`) ||
32 '';
33 const expression = `${ast.expression.id}(${_state})`;
34 return js`
35 if ((${_match} = ${ast.expression.id}(${_state})) != null) {
36 ${capture ? js`${_node}.push(${_match})` : ''}
37 } else {
38 ${opts.onAbort}
39 ${restoreIndex(opts.index)}
40 ${restoreLength}
41 ${opts.abort}
42 }
43 `;
44};
45
46const astGroup = (ast, depth, opts) => {
47 const capture = !!opts.capture && !ast.capture;
48
49 opts = copy(opts);
50 opts.capture = capture;
51
52 if (!opts.length && capture) {
53 opts.length = depth;
54 return js`
55 ${js`var ln${depth} = ${_node}.length;`}
56 ${astSequence(ast.sequence, depth + 1, opts)}
57 `;
58 }
59
60 return astSequence(ast.sequence, depth + 1, opts);
61};
62
63const astChild = (ast, depth, opts) =>
64 ast.expression ? astExpression(ast, depth, opts) : astGroup(ast, depth, opts);
65
66const astQuantifier = (ast, depth, opts) => {
67 const { index, abort, onAbort } = opts;
68 const invert = `inv_${depth}`;
69 const loop = `loop_${depth}`;
70 const count = `j${depth}`;
71
72 opts = copy(opts);
73 if (ast.capture === '!') {
74 opts.index = depth;
75 opts.abort = js`break ${invert}`;
76 }
77
78 let child;
79 if (ast.quantifier === '+') {
80 opts.onAbort = js`
81 if (${count}) {
82 ${restoreIndex(depth)}
83 break ${loop};
84 } else {
85 ${onAbort}
86 }
87 `;
88
89 child = js`
90 ${loop}: for (var ${count} = 0; 1; ${count}++) {
91 ${assignIndex(depth)}
92 ${astChild(ast, depth, opts)}
93 }
94 `;
95 } else if (ast.quantifier === '*') {
96 opts.length = 0;
97 opts.index = depth;
98 opts.abort = js`break ${loop};`;
99 opts.onAbort = '';
100
101 child = js`
102 ${loop}: for (;;) {
103 ${assignIndex(depth)}
104 ${astChild(ast, depth, opts)}
105 }
106 `;
107 } else if (ast.quantifier === '?') {
108 opts.index = depth;
109 opts.abort = '';
110 opts.onAbort = '';
111
112 child = js`
113 ${assignIndex(depth)}
114 ${astChild(ast, depth, opts)}
115 `;
116 } else {
117 child = astChild(ast, depth, opts);
118 }
119
120 if (ast.capture === '!') {
121 return js`
122 ${invert}: {
123 ${assignIndex(depth)}
124 ${child}
125 ${restoreIndex(index)}
126 ${abort}
127 }
128 `;
129 } else if (ast.capture === '=') {
130 return js`
131 ${assignIndex(depth)}
132 ${child}
133 ${restoreIndex(depth)}
134 `;
135 } else {
136 return child;
137 }
138};
139
140const astSequence = (ast, depth, opts) => {
141 const alternation = ast.alternation ? `alt_${depth}` : '';
142
143 let body = '';
144 for (; ast; ast = ast.alternation) {
145 const block = `block_${depth}`;
146
147 let childOpts = opts;
148 if (ast.alternation) {
149 childOpts = copy(opts);
150 childOpts.index = depth;
151 childOpts.abort = js`break ${block};`;
152 childOpts.onAbort = '';
153 }
154
155 let sequence = '';
156 for (let i = 0; i < ast.length; i++)
157 sequence += astQuantifier(ast[i], depth, childOpts);
158
159 if (!ast.alternation) {
160 body += sequence;
161 } else {
162 body += js`
163 ${block}: {
164 ${assignIndex(depth)}
165 ${sequence}
166 break ${alternation};
167 }
168 `;
169 }
170 }
171
172 if (!alternation) return body;
173
174 return js`
175 ${alternation}: {
176 ${body}
177 }
178 `;
179};
180
181const astRoot = (ast, name, transform) => {
182 return js`
183 (function (${_state}) {
184 ${assignIndex(1)}
185 var ${_node} = [];
186 var ${_match};
187
188 ${astSequence(ast, 2, {
189 index: 1,
190 length: 0,
191 onAbort: '',
192 abort: js`return;`,
193 capture: true,
194 })}
195
196 ${_node}.tag = ${name};
197 return ${transform ? js`(${transform})(${_node})` : _node};
198 })
199 `;
200};
201
202export { astRoot };