| 'use strict'; |
| |
| var hasOwnProperty = Object.prototype.hasOwnProperty; |
| var matchGraph = require('./match-graph'); |
| var MATCH = matchGraph.MATCH; |
| var MISMATCH = matchGraph.MISMATCH; |
| var DISALLOW_EMPTY = matchGraph.DISALLOW_EMPTY; |
| |
| var TOKEN = 1; |
| var OPEN_SYNTAX = 2; |
| var CLOSE_SYNTAX = 3; |
| |
| var EXIT_REASON_MATCH = 'Match'; |
| var EXIT_REASON_MISMATCH = 'Mismatch'; |
| var EXIT_REASON_ITERATION_LIMIT = 'Maximum iteration number exceeded (please fill an issue on https://github.com/csstree/csstree/issues)'; |
| |
| var ITERATION_LIMIT = 10000; |
| var totalIterationCount = 0; |
| |
| function mapList(list, fn) { |
| var result = []; |
| |
| while (list) { |
| result.unshift(fn(list)); |
| list = list.prev; |
| } |
| |
| return result; |
| } |
| |
| function isCommaContextStart(token) { |
| if (token === null) { |
| return true; |
| } |
| |
| token = token.value.charAt(token.value.length - 1); |
| |
| return ( |
| token === ',' || |
| token === '(' || |
| token === '[' || |
| token === '/' |
| ); |
| } |
| |
| function isCommaContextEnd(token) { |
| if (token === null) { |
| return true; |
| } |
| |
| token = token.value.charAt(0); |
| |
| return ( |
| token === ')' || |
| token === ']' || |
| token === '/' |
| ); |
| } |
| |
| function internalMatch(tokens, syntax, syntaxes) { |
| function moveToNextToken() { |
| do { |
| tokenCursor++; |
| token = tokenCursor < tokens.length ? tokens[tokenCursor] : null; |
| } while (token !== null && !/\S/.test(token.value)); |
| } |
| |
| function getNextToken(offset) { |
| var nextIndex = tokenCursor + offset; |
| |
| return nextIndex < tokens.length ? tokens[nextIndex] : null; |
| } |
| |
| function pushThenStack(nextSyntax) { |
| thenStack = { |
| nextSyntax: nextSyntax, |
| matchStack: matchStack, |
| syntaxStack: syntaxStack, |
| prev: thenStack |
| }; |
| } |
| |
| function pushElseStack(nextSyntax) { |
| elseStack = { |
| nextSyntax: nextSyntax, |
| matchStack: matchStack, |
| syntaxStack: syntaxStack, |
| thenStack: thenStack, |
| tokenCursor: tokenCursor, |
| token: token, |
| prev: elseStack |
| }; |
| } |
| |
| function addTokenToMatch() { |
| matchStack = { |
| type: TOKEN, |
| syntax: syntax.syntax, |
| token: token, |
| prev: matchStack |
| }; |
| |
| moveToNextToken(); |
| |
| if (tokenCursor > longestMatch) { |
| longestMatch = tokenCursor; |
| } |
| |
| return matchStack.token; |
| } |
| |
| function openSyntax() { |
| syntaxStack = { |
| syntax: syntax, |
| prev: syntaxStack |
| }; |
| |
| matchStack = { |
| type: OPEN_SYNTAX, |
| syntax: syntax.syntax, |
| token: matchStack.token, |
| prev: matchStack |
| }; |
| } |
| |
| function closeSyntax() { |
| if (matchStack.type === OPEN_SYNTAX) { |
| matchStack = matchStack.prev; |
| } else { |
| matchStack = { |
| type: CLOSE_SYNTAX, |
| syntax: syntaxStack.syntax, |
| token: matchStack.token, |
| prev: matchStack |
| }; |
| } |
| |
| syntaxStack = syntaxStack.prev; |
| } |
| |
| var syntaxStack = null; |
| var thenStack = null; |
| var elseStack = null; |
| |
| var iterationCount = 0; |
| var exitReason = EXIT_REASON_MATCH; |
| |
| var matchStack = { type: 'Stub', syntax: null, token: null, tokenCursor: -1, prev: null }; |
| var longestMatch = 0; |
| var tokenCursor = -1; |
| var token = null; |
| |
| moveToNextToken(); |
| |
| while (true) { |
| // console.log('--\n', |
| // '#' + iterationCount, |
| // require('util').inspect({ |
| // match: mapList(matchStack, x => x.type === TOKEN ? x.token && x.token.value : x.syntax ? x.type + '!' + x.syntax.name : null), |
| // elseStack: mapList(elseStack, x => x.id), |
| // thenStack: mapList(thenStack, x => x.id), |
| // token: token && token.value, |
| // tokenCursor, |
| // syntax |
| // }, { depth: null }) |
| // ); |
| |
| // prevent infinite loop |
| if (++iterationCount === ITERATION_LIMIT) { |
| console.warn('[csstree-match] BREAK after ' + ITERATION_LIMIT + ' iterations'); |
| exitReason = EXIT_REASON_ITERATION_LIMIT; |
| break; |
| } |
| |
| if (syntax === MATCH) { |
| if (thenStack === null) { |
| // turn to MISMATCH when some tokens left unmatched |
| if (token !== null) { |
| // doesn't mismatch if just one token left and it's an IE hack |
| if (tokenCursor !== tokens.length - 1 || (token.value !== '\\0' && token.value !== '\\9')) { |
| syntax = MISMATCH; |
| continue; |
| } |
| } |
| |
| // break the main loop, return a result - MATCH |
| exitReason = EXIT_REASON_MATCH; |
| break; |
| } |
| |
| // go to next syntax (`then` branch) |
| syntax = thenStack.nextSyntax; |
| |
| // check match is not empty |
| if (syntax === DISALLOW_EMPTY) { |
| if (thenStack.matchStack.token === matchStack.token) { |
| syntax = MISMATCH; |
| continue; |
| } else { |
| syntax = MATCH; |
| } |
| } |
| |
| // close syntax if needed |
| while (syntaxStack !== null && thenStack.syntaxStack !== syntaxStack) { |
| closeSyntax(); |
| } |
| |
| // pop stack |
| thenStack = thenStack.prev; |
| continue; |
| } |
| |
| if (syntax === MISMATCH) { |
| if (elseStack === null) { |
| // break the main loop, return a result - MISMATCH |
| exitReason = EXIT_REASON_MISMATCH; |
| break; |
| } |
| |
| // go to next syntax (`else` branch) |
| syntax = elseStack.nextSyntax; |
| |
| // restore all the rest stack states |
| thenStack = elseStack.thenStack; |
| syntaxStack = elseStack.syntaxStack; |
| matchStack = elseStack.matchStack; |
| tokenCursor = elseStack.tokenCursor; |
| token = elseStack.token; |
| |
| // pop stack |
| elseStack = elseStack.prev; |
| continue; |
| } |
| |
| switch (syntax.type) { |
| case 'MatchGraph': |
| syntax = syntax.match; |
| break; |
| |
| case 'If': |
| // IMPORTANT: else stack push must go first, |
| // since it stores the state of thenStack before changes |
| if (syntax.else !== MISMATCH) { |
| pushElseStack(syntax.else); |
| } |
| |
| if (syntax.then !== MATCH) { |
| pushThenStack(syntax.then); |
| } |
| |
| syntax = syntax.match; |
| break; |
| |
| case 'MatchOnce': |
| syntax = { |
| type: 'MatchOnceBuffer', |
| terms: syntax.terms, |
| all: syntax.all, |
| matchStack: matchStack, |
| index: 0, |
| mask: 0 |
| }; |
| break; |
| |
| case 'MatchOnceBuffer': |
| if (syntax.index === syntax.terms.length) { |
| // if no matches during a cycle |
| if (syntax.matchStack === matchStack) { |
| // no matches at all or it's required all terms to be matched |
| if (syntax.mask === 0 || syntax.all) { |
| syntax = MISMATCH; |
| break; |
| } |
| |
| // a partial match is ok |
| syntax = MATCH; |
| break; |
| } else { |
| // start trying to match from the start |
| syntax.index = 0; |
| syntax.matchStack = matchStack; |
| } |
| } |
| |
| for (; syntax.index < syntax.terms.length; syntax.index++) { |
| if ((syntax.mask & (1 << syntax.index)) === 0) { |
| // IMPORTANT: else stack push must go first, |
| // since it stores the state of thenStack before changes |
| pushElseStack(syntax); |
| pushThenStack({ |
| type: 'AddMatchOnce', |
| buffer: syntax |
| }); |
| |
| // match |
| syntax = syntax.terms[syntax.index++]; |
| break; |
| } |
| } |
| break; |
| |
| case 'AddMatchOnce': |
| syntax = syntax.buffer; |
| |
| var newMask = syntax.mask | (1 << (syntax.index - 1)); |
| |
| // all terms are matched |
| if (newMask === (1 << syntax.terms.length) - 1) { |
| syntax = MATCH; |
| continue; |
| } |
| |
| syntax = { |
| type: 'MatchOnceBuffer', |
| terms: syntax.terms, |
| all: syntax.all, |
| matchStack: syntax.matchStack, |
| index: syntax.index, |
| mask: newMask |
| }; |
| |
| break; |
| |
| case 'Enum': |
| var name = token !== null ? token.value.toLowerCase() : ''; |
| |
| // drop \0 and \9 hack from keyword name |
| if (name.indexOf('\\') !== -1) { |
| name = name.replace(/\\[09].*$/, ''); |
| } |
| |
| if (hasOwnProperty.call(syntax.map, name)) { |
| syntax = syntax.map[name]; |
| } else { |
| syntax = MISMATCH; |
| } |
| |
| break; |
| |
| case 'Generic': |
| syntax = syntax.fn(token, addTokenToMatch, getNextToken) ? MATCH : MISMATCH; |
| break; |
| |
| case 'Type': |
| case 'Property': |
| openSyntax(); |
| |
| var syntaxDict = syntax.type === 'Type' ? 'types' : 'properties'; |
| |
| if (hasOwnProperty.call(syntaxes, syntaxDict) && syntaxes[syntaxDict][syntax.name]) { |
| syntax = syntaxes[syntaxDict][syntax.name].match; |
| } else { |
| syntax = undefined; |
| } |
| |
| if (!syntax) { |
| throw new Error( |
| 'Bad syntax reference: ' + |
| (syntaxStack.syntax.type === 'Type' |
| ? '<' + syntaxStack.syntax.name + '>' |
| : '<\'' + syntaxStack.syntax.name + '\'>') |
| ); |
| } |
| |
| break; |
| |
| case 'Keyword': |
| var name = syntax.name; |
| |
| if (token !== null) { |
| var keywordName = token.value; |
| |
| // drop \0 and \9 hack from keyword name |
| if (keywordName.indexOf('\\') !== -1) { |
| keywordName = keywordName.replace(/\\[09].*$/, ''); |
| } |
| |
| if (keywordName.toLowerCase() === name) { |
| addTokenToMatch(); |
| |
| syntax = MATCH; |
| break; |
| } |
| } |
| |
| syntax = MISMATCH; |
| break; |
| |
| case 'AtKeyword': |
| case 'Function': |
| if (token !== null && token.value.toLowerCase() === syntax.name) { |
| addTokenToMatch(); |
| |
| syntax = MATCH; |
| break; |
| } |
| |
| syntax = MISMATCH; |
| break; |
| |
| case 'Token': |
| if (token !== null && token.value === syntax.value) { |
| addTokenToMatch(); |
| |
| syntax = MATCH; |
| break; |
| } |
| |
| syntax = MISMATCH; |
| break; |
| |
| case 'Comma': |
| if (token !== null && token.value === ',') { |
| if (isCommaContextStart(matchStack.token)) { |
| syntax = MISMATCH; |
| } else { |
| addTokenToMatch(); |
| syntax = isCommaContextEnd(token) ? MISMATCH : MATCH; |
| } |
| } else { |
| syntax = isCommaContextStart(matchStack.token) || isCommaContextEnd(token) ? MATCH : MISMATCH; |
| } |
| |
| break; |
| |
| // case 'String': |
| // TODO: strings with length other than 1 char |
| |
| default: |
| throw new Error('Unknown node type: ' + syntax.type); |
| } |
| } |
| |
| totalIterationCount += iterationCount; |
| |
| if (exitReason === EXIT_REASON_MATCH) { |
| while (syntaxStack !== null) { |
| closeSyntax(); |
| } |
| } else { |
| matchStack = null; |
| } |
| |
| return { |
| tokens: tokens, |
| reason: exitReason, |
| iterations: iterationCount, |
| match: matchStack, |
| longestMatch: longestMatch |
| }; |
| } |
| |
| function matchAsList(tokens, matchGraph, syntaxes) { |
| var matchResult = internalMatch(tokens, matchGraph, syntaxes || {}); |
| |
| if (matchResult.match !== null) { |
| matchResult.match = mapList(matchResult.match, function(item) { |
| if (item.type === OPEN_SYNTAX || item.type === CLOSE_SYNTAX) { |
| return { type: item.type, syntax: item.syntax }; |
| } |
| |
| return { |
| syntax: item.syntax, |
| token: item.token && item.token.value, |
| node: item.token && item.token.node |
| }; |
| }).slice(1); |
| } |
| |
| return matchResult; |
| } |
| |
| function matchAsTree(tokens, matchGraph, syntaxes) { |
| var matchResult = internalMatch(tokens, matchGraph, syntaxes || {}); |
| |
| if (matchResult.match === null) { |
| return matchResult; |
| } |
| |
| var cursor = matchResult.match; |
| var host = matchResult.match = { |
| syntax: matchGraph.syntax || null, |
| match: [] |
| }; |
| var stack = [host]; |
| |
| // revert a list |
| var prev = null; |
| var next = null; |
| while (cursor !== null) { |
| next = cursor.prev; |
| cursor.prev = prev; |
| prev = cursor; |
| cursor = next; |
| } |
| |
| // init the cursor to start with 2nd item since 1st is a stub item |
| cursor = prev.prev; |
| |
| // build a tree |
| while (cursor !== null && cursor.syntax !== null) { |
| var entry = cursor; |
| |
| switch (entry.type) { |
| case OPEN_SYNTAX: |
| host.match.push(host = { |
| syntax: entry.syntax, |
| match: [] |
| }); |
| stack.push(host); |
| break; |
| |
| case CLOSE_SYNTAX: |
| stack.pop(); |
| host = stack[stack.length - 1]; |
| break; |
| |
| default: |
| host.match.push({ |
| syntax: entry.syntax || null, |
| token: entry.token.value, |
| node: entry.token.node |
| }); |
| } |
| |
| cursor = cursor.prev; |
| } |
| |
| return matchResult; |
| } |
| |
| module.exports = { |
| matchAsList: matchAsList, |
| matchAsTree: matchAsTree, |
| getTotalIterationCount: function() { |
| return totalIterationCount; |
| } |
| }; |
