|
|
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]: '</' }[x.type] || x.type) + '!' + x.syntax.name : null),
|
|
|
// token: token && token.value,
|
|
|
// tokenIndex,
|
|
|
// syntax: syntax.type + (syntax.id ? ' #' + syntax.id : '')
|
|
|
// }, { depth: null })
|
|
|
// );
|
|
|
switch (state.type) {
|
|
|
case '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 (tokenIndex !== tokens.length - 1 || (token.value !== '\\0' && token.value !== '\\9')) {
|
|
|
state = MISMATCH;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// break the main loop, return a result - MATCH
|
|
|
exitReason = EXIT_REASON_MATCH;
|
|
|
break;
|
|
|
}
|
|
|
|
|
|
// go to next syntax (`then` branch)
|
|
|
state = thenStack.nextState;
|
|
|
|
|
|
// check match is not empty
|
|
|
if (state === DISALLOW_EMPTY) {
|
|
|
if (thenStack.matchStack === matchStack) {
|
|
|
state = MISMATCH;
|
|
|
break;
|
|
|
} else {
|
|
|
state = MATCH;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// close syntax if needed
|
|
|
while (thenStack.syntaxStack !== syntaxStack) {
|
|
|
closeSyntax();
|
|
|
}
|
|
|
|
|
|
// pop stack
|
|
|
thenStack = thenStack.prev;
|
|
|
break;
|
|
|
|
|
|
case 'Mismatch':
|
|
|
// when some syntax is stashed
|
|
|
if (syntaxStash !== null && syntaxStash !== false) {
|
|
|
// there is no else branches or a branch reduce match stack
|
|
|
if (elseStack === null || tokenIndex > 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 <custom-ident> 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 <number> or a <length> in a property (such as line-height),
|
|
|
// it must parse as a <number>
|
|
|
(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;
|
|
|
}
|
|
|
};
|
