source: imaps-frontend/node_modules/css-tree/lib/lexer/match-graph.js@ d565449

main
Last change on this file since d565449 was d565449, checked in by stefan toskovski <stefantoska84@…>, 4 weeks ago

Update repo after prototype presentation
  • Property mode set to 100644
File size: 12.3 KB
RevLine 
[d565449]1var parse = require('../definition-syntax/parse');
2
3var MATCH = { type: 'Match' };
4var MISMATCH = { type: 'Mismatch' };
5var DISALLOW_EMPTY = { type: 'DisallowEmpty' };
6var LEFTPARENTHESIS = 40; // (
7var RIGHTPARENTHESIS = 41; // )
8
9function createCondition(match, thenBranch, elseBranch) {
10 // reduce node count
11 if (thenBranch === MATCH && elseBranch === MISMATCH) {
12 return match;
13 }
14
15 if (match === MATCH && thenBranch === MATCH && elseBranch === MATCH) {
16 return match;
17 }
18
19 if (match.type === 'If' && match.else === MISMATCH && thenBranch === MATCH) {
20 thenBranch = match.then;
21 match = match.match;
22 }
23
24 return {
25 type: 'If',
26 match: match,
27 then: thenBranch,
28 else: elseBranch
29 };
30}
31
32function isFunctionType(name) {
33 return (
34 name.length > 2 &&
35 name.charCodeAt(name.length - 2) === LEFTPARENTHESIS &&
36 name.charCodeAt(name.length - 1) === RIGHTPARENTHESIS
37 );
38}
39
40function isEnumCapatible(term) {
41 return (
42 term.type === 'Keyword' ||
43 term.type === 'AtKeyword' ||
44 term.type === 'Function' ||
45 term.type === 'Type' && isFunctionType(term.name)
46 );
47}
48
49function buildGroupMatchGraph(combinator, terms, atLeastOneTermMatched) {
50 switch (combinator) {
51 case ' ':
52 // Juxtaposing components means that all of them must occur, in the given order.
53 //
54 // a b c
55 // =
56 // match a
57 // then match b
58 // then match c
59 // then MATCH
60 // else MISMATCH
61 // else MISMATCH
62 // else MISMATCH
63 var result = MATCH;
64
65 for (var i = terms.length - 1; i >= 0; i--) {
66 var term = terms[i];
67
68 result = createCondition(
69 term,
70 result,
71 MISMATCH
72 );
73 };
74
75 return result;
76
77 case '|':
78 // A bar (|) separates two or more alternatives: exactly one of them must occur.
79 //
80 // a | b | c
81 // =
82 // match a
83 // then MATCH
84 // else match b
85 // then MATCH
86 // else match c
87 // then MATCH
88 // else MISMATCH
89
90 var result = MISMATCH;
91 var map = null;
92
93 for (var i = terms.length - 1; i >= 0; i--) {
94 var term = terms[i];
95
96 // reduce sequence of keywords into a Enum
97 if (isEnumCapatible(term)) {
98 if (map === null && i > 0 && isEnumCapatible(terms[i - 1])) {
99 map = Object.create(null);
100 result = createCondition(
101 {
102 type: 'Enum',
103 map: map
104 },
105 MATCH,
106 result
107 );
108 }
109
110 if (map !== null) {
111 var key = (isFunctionType(term.name) ? term.name.slice(0, -1) : term.name).toLowerCase();
112 if (key in map === false) {
113 map[key] = term;
114 continue;
115 }
116 }
117 }
118
119 map = null;
120
121 // create a new conditonal node
122 result = createCondition(
123 term,
124 MATCH,
125 result
126 );
127 };
128
129 return result;
130
131 case '&&':
132 // A double ampersand (&&) separates two or more components,
133 // all of which must occur, in any order.
134
135 // Use MatchOnce for groups with a large number of terms,
136 // since &&-groups produces at least N!-node trees
137 if (terms.length > 5) {
138 return {
139 type: 'MatchOnce',
140 terms: terms,
141 all: true
142 };
143 }
144
145 // Use a combination tree for groups with small number of terms
146 //
147 // a && b && c
148 // =
149 // match a
150 // then [b && c]
151 // else match b
152 // then [a && c]
153 // else match c
154 // then [a && b]
155 // else MISMATCH
156 //
157 // a && b
158 // =
159 // match a
160 // then match b
161 // then MATCH
162 // else MISMATCH
163 // else match b
164 // then match a
165 // then MATCH
166 // else MISMATCH
167 // else MISMATCH
168 var result = MISMATCH;
169
170 for (var i = terms.length - 1; i >= 0; i--) {
171 var term = terms[i];
172 var thenClause;
173
174 if (terms.length > 1) {
175 thenClause = buildGroupMatchGraph(
176 combinator,
177 terms.filter(function(newGroupTerm) {
178 return newGroupTerm !== term;
179 }),
180 false
181 );
182 } else {
183 thenClause = MATCH;
184 }
185
186 result = createCondition(
187 term,
188 thenClause,
189 result
190 );
191 };
192
193 return result;
194
195 case '||':
196 // A double bar (||) separates two or more options:
197 // one or more of them must occur, in any order.
198
199 // Use MatchOnce for groups with a large number of terms,
200 // since ||-groups produces at least N!-node trees
201 if (terms.length > 5) {
202 return {
203 type: 'MatchOnce',
204 terms: terms,
205 all: false
206 };
207 }
208
209 // Use a combination tree for groups with small number of terms
210 //
211 // a || b || c
212 // =
213 // match a
214 // then [b || c]
215 // else match b
216 // then [a || c]
217 // else match c
218 // then [a || b]
219 // else MISMATCH
220 //
221 // a || b
222 // =
223 // match a
224 // then match b
225 // then MATCH
226 // else MATCH
227 // else match b
228 // then match a
229 // then MATCH
230 // else MATCH
231 // else MISMATCH
232 var result = atLeastOneTermMatched ? MATCH : MISMATCH;
233
234 for (var i = terms.length - 1; i >= 0; i--) {
235 var term = terms[i];
236 var thenClause;
237
238 if (terms.length > 1) {
239 thenClause = buildGroupMatchGraph(
240 combinator,
241 terms.filter(function(newGroupTerm) {
242 return newGroupTerm !== term;
243 }),
244 true
245 );
246 } else {
247 thenClause = MATCH;
248 }
249
250 result = createCondition(
251 term,
252 thenClause,
253 result
254 );
255 };
256
257 return result;
258 }
259}
260
261function buildMultiplierMatchGraph(node) {
262 var result = MATCH;
263 var matchTerm = buildMatchGraph(node.term);
264
265 if (node.max === 0) {
266 // disable repeating of empty match to prevent infinite loop
267 matchTerm = createCondition(
268 matchTerm,
269 DISALLOW_EMPTY,
270 MISMATCH
271 );
272
273 // an occurrence count is not limited, make a cycle;
274 // to collect more terms on each following matching mismatch
275 result = createCondition(
276 matchTerm,
277 null, // will be a loop
278 MISMATCH
279 );
280
281 result.then = createCondition(
282 MATCH,
283 MATCH,
284 result // make a loop
285 );
286
287 if (node.comma) {
288 result.then.else = createCondition(
289 { type: 'Comma', syntax: node },
290 result,
291 MISMATCH
292 );
293 }
294 } else {
295 // create a match node chain for [min .. max] interval with optional matches
296 for (var i = node.min || 1; i <= node.max; i++) {
297 if (node.comma && result !== MATCH) {
298 result = createCondition(
299 { type: 'Comma', syntax: node },
300 result,
301 MISMATCH
302 );
303 }
304
305 result = createCondition(
306 matchTerm,
307 createCondition(
308 MATCH,
309 MATCH,
310 result
311 ),
312 MISMATCH
313 );
314 }
315 }
316
317 if (node.min === 0) {
318 // allow zero match
319 result = createCondition(
320 MATCH,
321 MATCH,
322 result
323 );
324 } else {
325 // create a match node chain to collect [0 ... min - 1] required matches
326 for (var i = 0; i < node.min - 1; i++) {
327 if (node.comma && result !== MATCH) {
328 result = createCondition(
329 { type: 'Comma', syntax: node },
330 result,
331 MISMATCH
332 );
333 }
334
335 result = createCondition(
336 matchTerm,
337 result,
338 MISMATCH
339 );
340 }
341 }
342
343 return result;
344}
345
346function buildMatchGraph(node) {
347 if (typeof node === 'function') {
348 return {
349 type: 'Generic',
350 fn: node
351 };
352 }
353
354 switch (node.type) {
355 case 'Group':
356 var result = buildGroupMatchGraph(
357 node.combinator,
358 node.terms.map(buildMatchGraph),
359 false
360 );
361
362 if (node.disallowEmpty) {
363 result = createCondition(
364 result,
365 DISALLOW_EMPTY,
366 MISMATCH
367 );
368 }
369
370 return result;
371
372 case 'Multiplier':
373 return buildMultiplierMatchGraph(node);
374
375 case 'Type':
376 case 'Property':
377 return {
378 type: node.type,
379 name: node.name,
380 syntax: node
381 };
382
383 case 'Keyword':
384 return {
385 type: node.type,
386 name: node.name.toLowerCase(),
387 syntax: node
388 };
389
390 case 'AtKeyword':
391 return {
392 type: node.type,
393 name: '@' + node.name.toLowerCase(),
394 syntax: node
395 };
396
397 case 'Function':
398 return {
399 type: node.type,
400 name: node.name.toLowerCase() + '(',
401 syntax: node
402 };
403
404 case 'String':
405 // convert a one char length String to a Token
406 if (node.value.length === 3) {
407 return {
408 type: 'Token',
409 value: node.value.charAt(1),
410 syntax: node
411 };
412 }
413
414 // otherwise use it as is
415 return {
416 type: node.type,
417 value: node.value.substr(1, node.value.length - 2).replace(/\\'/g, '\''),
418 syntax: node
419 };
420
421 case 'Token':
422 return {
423 type: node.type,
424 value: node.value,
425 syntax: node
426 };
427
428 case 'Comma':
429 return {
430 type: node.type,
431 syntax: node
432 };
433
434 default:
435 throw new Error('Unknown node type:', node.type);
436 }
437}
438
439module.exports = {
440 MATCH: MATCH,
441 MISMATCH: MISMATCH,
442 DISALLOW_EMPTY: DISALLOW_EMPTY,
443 buildMatchGraph: function(syntaxTree, ref) {
444 if (typeof syntaxTree === 'string') {
445 syntaxTree = parse(syntaxTree);
446 }
447
448 return {
449 type: 'MatchGraph',
450 match: buildMatchGraph(syntaxTree),
451 syntax: ref || null,
452 source: syntaxTree
453 };
454 }
455};
Note: See TracBrowser for help on using the repository browser.