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 TYPE = require('../tokenizer/const').TYPE; var STUB = 0; 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 = 15000; var totalIterationCount = 0; function reverseList(list) { var prev = null; var next = null; var item = list; while (item !== null) { next = item.prev; item.prev = prev; prev = item; item = next; } return prev; } function areStringsEqualCaseInsensitive(testStr, referenceStr) { if (testStr.length !== referenceStr.length) { return false; } for (var i = 0; i < testStr.length; i++) { var testCode = testStr.charCodeAt(i); var referenceCode = referenceStr.charCodeAt(i); // testCode.toLowerCase() for U+0041 LATIN CAPITAL LETTER A (A) .. U+005A LATIN CAPITAL LETTER Z (Z). if (testCode >= 0x0041 && testCode <= 0x005A) { testCode = testCode | 32; } if (testCode !== referenceCode) { return false; } } return true; } function isContextEdgeDelim(token) { if (token.type !== TYPE.Delim) { return false; } // Fix matching for unicode-range: U+30??, U+FF00-FF9F // Probably we need to check out previous match instead return token.value !== '?'; } function isCommaContextStart(token) { if (token === null) { return true; } return ( token.type === TYPE.Comma || token.type === TYPE.Function || token.type === TYPE.LeftParenthesis || token.type === TYPE.LeftSquareBracket || token.type === TYPE.LeftCurlyBracket || isContextEdgeDelim(token) ); } function isCommaContextEnd(token) { if (token === null) { return true; } return ( token.type === TYPE.RightParenthesis || token.type === TYPE.RightSquareBracket || token.type === TYPE.RightCurlyBracket || token.type === TYPE.Delim ); } function internalMatch(tokens, state, syntaxes) { function moveToNextToken() { do { tokenIndex++; token = tokenIndex < tokens.length ? tokens[tokenIndex] : null; } while (token !== null && (token.type === TYPE.WhiteSpace || token.type === TYPE.Comment)); } function getNextToken(offset) { var nextIndex = tokenIndex + offset; return nextIndex < tokens.length ? tokens[nextIndex] : null; } function stateSnapshotFromSyntax(nextState, prev) { return { nextState: nextState, matchStack: matchStack, syntaxStack: syntaxStack, thenStack: thenStack, tokenIndex: tokenIndex, prev: prev }; } function pushThenStack(nextState) { thenStack = { nextState: nextState, matchStack: matchStack, syntaxStack: syntaxStack, prev: thenStack }; } function pushElseStack(nextState) { elseStack = stateSnapshotFromSyntax(nextState, elseStack); } function addTokenToMatch() { matchStack = { type: TOKEN, syntax: state.syntax, token: token, prev: matchStack }; moveToNextToken(); syntaxStash = null; if (tokenIndex > longestMatch) { longestMatch = tokenIndex; } } function openSyntax() { syntaxStack = { syntax: state.syntax, opts: state.syntax.opts || (syntaxStack !== null && syntaxStack.opts) || null, prev: syntaxStack }; matchStack = { type: OPEN_SYNTAX, syntax: state.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; // null – stashing allowed, nothing stashed // false – stashing disabled, nothing stashed // anithing else – fail stashable syntaxes, some syntax stashed var syntaxStash = null; var iterationCount = 0; // count iterations and prevent infinite loop var exitReason = null; var token = null; var tokenIndex = -1; var longestMatch = 0; var matchStack = { type: STUB, syntax: null, token: null, prev: null }; moveToNextToken(); while (exitReason === null && ++iterationCount < ITERATION_LIMIT) { // function mapList(list, fn) { // var result = []; // while (list) { // result.unshift(fn(list)); // list = list.prev; // } // return result; // } // console.log('--\n', // '#' + iterationCount, // require('util').inspect({ // match: mapList(matchStack, x => x.type === TOKEN ? x.token && x.token.value : x.syntax ? ({ [OPEN_SYNTAX]: '<', [CLOSE_SYNTAX]: ' elseStack.tokenIndex) { // restore state from the stash elseStack = syntaxStash; syntaxStash = false; // disable stashing } } else if (elseStack === null) { // no else branches -> break the main loop // return a result - MISMATCH exitReason = EXIT_REASON_MISMATCH; break; } // go to next syntax (`else` branch) state = elseStack.nextState; // restore all the rest stack states thenStack = elseStack.thenStack; syntaxStack = elseStack.syntaxStack; matchStack = elseStack.matchStack; tokenIndex = elseStack.tokenIndex; token = tokenIndex < tokens.length ? tokens[tokenIndex] : null; // pop stack elseStack = elseStack.prev; break; case 'MatchGraph': state = state.match; break; case 'If': // IMPORTANT: else stack push must go first, // since it stores the state of thenStack before changes if (state.else !== MISMATCH) { pushElseStack(state.else); } if (state.then !== MATCH) { pushThenStack(state.then); } state = state.match; break; case 'MatchOnce': state = { type: 'MatchOnceBuffer', syntax: state, index: 0, mask: 0 }; break; case 'MatchOnceBuffer': var terms = state.syntax.terms; if (state.index === terms.length) { // no matches at all or it's required all terms to be matched if (state.mask === 0 || state.syntax.all) { state = MISMATCH; break; } // a partial match is ok state = MATCH; break; } // all terms are matched if (state.mask === (1 << terms.length) - 1) { state = MATCH; break; } for (; state.index < terms.length; state.index++) { var matchFlag = 1 << state.index; if ((state.mask & matchFlag) === 0) { // IMPORTANT: else stack push must go first, // since it stores the state of thenStack before changes pushElseStack(state); pushThenStack({ type: 'AddMatchOnce', syntax: state.syntax, mask: state.mask | matchFlag }); // match state = terms[state.index++]; break; } } break; case 'AddMatchOnce': state = { type: 'MatchOnceBuffer', syntax: state.syntax, index: 0, mask: state.mask }; break; case 'Enum': if (token !== null) { var name = token.value.toLowerCase(); // drop \0 and \9 hack from keyword name if (name.indexOf('\\') !== -1) { name = name.replace(/\\[09].*$/, ''); } if (hasOwnProperty.call(state.map, name)) { state = state.map[name]; break; } } state = MISMATCH; break; case 'Generic': var opts = syntaxStack !== null ? syntaxStack.opts : null; var lastTokenIndex = tokenIndex + Math.floor(state.fn(token, getNextToken, opts)); if (!isNaN(lastTokenIndex) && lastTokenIndex > tokenIndex) { while (tokenIndex < lastTokenIndex) { addTokenToMatch(); } state = MATCH; } else { state = MISMATCH; } break; case 'Type': case 'Property': var syntaxDict = state.type === 'Type' ? 'types' : 'properties'; var dictSyntax = hasOwnProperty.call(syntaxes, syntaxDict) ? syntaxes[syntaxDict][state.name] : null; if (!dictSyntax || !dictSyntax.match) { throw new Error( 'Bad syntax reference: ' + (state.type === 'Type' ? '<' + state.name + '>' : '<\'' + state.name + '\'>') ); } // stash a syntax for types with low priority if (syntaxStash !== false && token !== null && state.type === 'Type') { var lowPriorityMatching = // https://drafts.csswg.org/css-values-4/#custom-idents // When parsing positionally-ambiguous keywords in a property value, a production // can only claim the keyword if no other unfulfilled production can claim it. (state.name === 'custom-ident' && token.type === TYPE.Ident) || // https://drafts.csswg.org/css-values-4/#lengths // ... if a `0` could be parsed as either a or a in a property (such as line-height), // it must parse as a (state.name === 'length' && token.value === '0'); if (lowPriorityMatching) { if (syntaxStash === null) { syntaxStash = stateSnapshotFromSyntax(state, elseStack); } state = MISMATCH; break; } } openSyntax(); state = dictSyntax.match; break; case 'Keyword': var name = state.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 (areStringsEqualCaseInsensitive(keywordName, name)) { addTokenToMatch(); state = MATCH; break; } } state = MISMATCH; break; case 'AtKeyword': case 'Function': if (token !== null && areStringsEqualCaseInsensitive(token.value, state.name)) { addTokenToMatch(); state = MATCH; break; } state = MISMATCH; break; case 'Token': if (token !== null && token.value === state.value) { addTokenToMatch(); state = MATCH; break; } state = MISMATCH; break; case 'Comma': if (token !== null && token.type === TYPE.Comma) { if (isCommaContextStart(matchStack.token)) { state = MISMATCH; } else { addTokenToMatch(); state = isCommaContextEnd(token) ? MISMATCH : MATCH; } } else { state = isCommaContextStart(matchStack.token) || isCommaContextEnd(token) ? MATCH : MISMATCH; } break; case 'String': var string = ''; for (var lastTokenIndex = tokenIndex; lastTokenIndex < tokens.length && string.length < state.value.length; lastTokenIndex++) { string += tokens[lastTokenIndex].value; } if (areStringsEqualCaseInsensitive(string, state.value)) { while (tokenIndex < lastTokenIndex) { addTokenToMatch(); } state = MATCH; } else { state = MISMATCH; } break; default: throw new Error('Unknown node type: ' + state.type); } } totalIterationCount += iterationCount; switch (exitReason) { case null: console.warn('[csstree-match] BREAK after ' + ITERATION_LIMIT + ' iterations'); exitReason = EXIT_REASON_ITERATION_LIMIT; matchStack = null; break; case EXIT_REASON_MATCH: while (syntaxStack !== null) { closeSyntax(); } break; default: 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) { var item = reverseList(matchResult.match).prev; matchResult.match = []; while (item !== null) { switch (item.type) { case STUB: break; case OPEN_SYNTAX: case CLOSE_SYNTAX: matchResult.match.push({ type: item.type, syntax: item.syntax }); break; default: matchResult.match.push({ token: item.token.value, node: item.token.node }); break; } item = item.prev; } } return matchResult; } function matchAsTree(tokens, matchGraph, syntaxes) { var matchResult = internalMatch(tokens, matchGraph, syntaxes || {}); if (matchResult.match === null) { return matchResult; } var item = matchResult.match; var host = matchResult.match = { syntax: matchGraph.syntax || null, match: [] }; var hostStack = [host]; // revert a list and start with 2nd item since 1st is a stub item item = reverseList(item).prev; // build a tree while (item !== null) { switch (item.type) { case OPEN_SYNTAX: host.match.push(host = { syntax: item.syntax, match: [] }); hostStack.push(host); break; case CLOSE_SYNTAX: hostStack.pop(); host = hostStack[hostStack.length - 1]; break; default: host.match.push({ syntax: item.syntax || null, token: item.token.value, node: item.token.node }); } item = item.prev; } return matchResult; } module.exports = { matchAsList: matchAsList, matchAsTree: matchAsTree, getTotalIterationCount: function() { return totalIterationCount; } };