| var parse = require('./grammar/parse'); |
| |
| var MATCH = { type: 'Match' }; |
| var MISMATCH = { type: 'Mismatch' }; |
| var DISALLOW_EMPTY = { type: 'DisallowEmpty' }; |
| var LEFTPARENTHESIS = 40; // ( |
| var RIGHTPARENTHESIS = 41; // ) |
| |
| function createCondition(match, thenBranch, elseBranch) { |
| // reduce node count |
| if (thenBranch === MATCH && elseBranch === MISMATCH) { |
| return match; |
| } |
| |
| if (match === MATCH && thenBranch === MATCH && elseBranch === MATCH) { |
| return match; |
| } |
| |
| if (match.type === 'If' && match.else === MISMATCH && thenBranch === MATCH) { |
| thenBranch = match.then; |
| match = match.match; |
| } |
| |
| return { |
| type: 'If', |
| match: match, |
| then: thenBranch, |
| else: elseBranch |
| }; |
| } |
| |
| function isFunctionType(name) { |
| return ( |
| name.length > 2 && |
| name.charCodeAt(name.length - 2) === LEFTPARENTHESIS && |
| name.charCodeAt(name.length - 1) === RIGHTPARENTHESIS |
| ); |
| } |
| |
| function isEnumCapatible(term) { |
| return ( |
| term.type === 'Keyword' || |
| term.type === 'AtKeyword' || |
| term.type === 'Function' || |
| term.type === 'Type' && isFunctionType(term.name) |
| ); |
| } |
| |
| function buildGroupMatchGraph(combinator, terms, atLeastOneTermMatched) { |
| switch (combinator) { |
| case ' ': |
| // Juxtaposing components means that all of them must occur, in the given order. |
| // |
| // a b c |
| // = |
| // match a |
| // then match b |
| // then match c |
| // then MATCH |
| // else MISMATCH |
| // else MISMATCH |
| // else MISMATCH |
| var result = MATCH; |
| |
| for (var i = terms.length - 1; i >= 0; i--) { |
| var term = terms[i]; |
| |
| result = createCondition( |
| term, |
| result, |
| MISMATCH |
| ); |
| }; |
| |
| return result; |
| |
| case '|': |
| // A bar (|) separates two or more alternatives: exactly one of them must occur. |
| // |
| // a | b | c |
| // = |
| // match a |
| // then MATCH |
| // else match b |
| // then MATCH |
| // else match c |
| // then MATCH |
| // else MISMATCH |
| |
| var result = MISMATCH; |
| var map = null; |
| |
| for (var i = terms.length - 1; i >= 0; i--) { |
| var term = terms[i]; |
| |
| // reduce sequence of keywords into a Enum |
| if (isEnumCapatible(term)) { |
| if (map === null && i > 0 && isEnumCapatible(terms[i - 1])) { |
| map = Object.create(null); |
| result = createCondition( |
| { |
| type: 'Enum', |
| map: map |
| }, |
| MATCH, |
| result |
| ); |
| } |
| |
| if (map !== null) { |
| var key = (isFunctionType(term.name) ? term.name.slice(0, -1) : term.name).toLowerCase(); |
| if (key in map === false) { |
| map[key] = term; |
| continue; |
| } |
| } |
| } |
| |
| map = null; |
| |
| // create a new conditonal node |
| result = createCondition( |
| term, |
| MATCH, |
| result |
| ); |
| }; |
| |
| return result; |
| |
| case '&&': |
| // A double ampersand (&&) separates two or more components, |
| // all of which must occur, in any order. |
| |
| // Use MatchOnce for groups with a large number of terms, |
| // since &&-groups produces at least N!-node trees |
| if (terms.length > 5) { |
| return { |
| type: 'MatchOnce', |
| terms: terms, |
| all: true |
| }; |
| } |
| |
| // Use a combination tree for groups with small number of terms |
| // |
| // a && b && c |
| // = |
| // match a |
| // then [b && c] |
| // else match b |
| // then [a && c] |
| // else match c |
| // then [a && b] |
| // else MISMATCH |
| // |
| // a && b |
| // = |
| // match a |
| // then match b |
| // then MATCH |
| // else MISMATCH |
| // else match b |
| // then match a |
| // then MATCH |
| // else MISMATCH |
| // else MISMATCH |
| var result = MISMATCH; |
| |
| for (var i = terms.length - 1; i >= 0; i--) { |
| var term = terms[i]; |
| var thenClause; |
| |
| if (terms.length > 1) { |
| thenClause = buildGroupMatchGraph( |
| combinator, |
| terms.filter(function(newGroupTerm) { |
| return newGroupTerm !== term; |
| }), |
| false |
| ); |
| } else { |
| thenClause = MATCH; |
| } |
| |
| result = createCondition( |
| term, |
| thenClause, |
| result |
| ); |
| }; |
| |
| return result; |
| |
| case '||': |
| // A double bar (||) separates two or more options: |
| // one or more of them must occur, in any order. |
| |
| // Use MatchOnce for groups with a large number of terms, |
| // since ||-groups produces at least N!-node trees |
| if (terms.length > 5) { |
| return { |
| type: 'MatchOnce', |
| terms: terms, |
| all: false |
| };; |
| } |
| |
| // Use a combination tree for groups with small number of terms |
| // |
| // a || b || c |
| // = |
| // match a |
| // then [b || c] |
| // else match b |
| // then [a || c] |
| // else match c |
| // then [a || b] |
| // else MISMATCH |
| // |
| // a || b |
| // = |
| // match a |
| // then match b |
| // then MATCH |
| // else MATCH |
| // else match b |
| // then match a |
| // then MATCH |
| // else MATCH |
| // else MISMATCH |
| var result = atLeastOneTermMatched ? MATCH : MISMATCH; |
| |
| for (var i = terms.length - 1; i >= 0; i--) { |
| var term = terms[i]; |
| var thenClause; |
| |
| if (terms.length > 1) { |
| thenClause = buildGroupMatchGraph( |
| combinator, |
| terms.filter(function(newGroupTerm) { |
| return newGroupTerm !== term; |
| }), |
| true |
| ); |
| } else { |
| thenClause = MATCH; |
| } |
| |
| result = createCondition( |
| term, |
| thenClause, |
| result |
| ); |
| }; |
| |
| return result; |
| } |
| } |
| |
| function buildMultiplierMatchGraph(node) { |
| var result = MATCH; |
| var matchTerm = buildMatchGraph(node.term); |
| |
| if (node.max === 0) { |
| // disable repeating of empty match to prevent infinite loop |
| matchTerm = createCondition( |
| matchTerm, |
| DISALLOW_EMPTY, |
| MISMATCH |
| ); |
| |
| // an occurrence count is not limited, make a cycle; |
| // to collect more terms on each following matching mismatch |
| result = createCondition( |
| matchTerm, |
| null, // will be a loop |
| MISMATCH |
| ); |
| |
| result.then = createCondition( |
| MATCH, |
| MATCH, |
| result // make a loop |
| ); |
| |
| if (node.comma) { |
| result.then.else = createCondition( |
| { type: 'Comma', syntax: node }, |
| result, |
| MISMATCH |
| ); |
| } |
| } else { |
| // create a match node chain for [min .. max] interval with optional matches |
| for (var i = node.min || 1; i <= node.max; i++) { |
| if (node.comma && result !== MATCH) { |
| result = createCondition( |
| { type: 'Comma', syntax: node }, |
| result, |
| MISMATCH |
| ); |
| } |
| |
| result = createCondition( |
| matchTerm, |
| createCondition( |
| MATCH, |
| MATCH, |
| result |
| ), |
| MISMATCH |
| ); |
| } |
| } |
| |
| if (node.min === 0) { |
| // allow zero match |
| result = createCondition( |
| MATCH, |
| MATCH, |
| result |
| ); |
| } else { |
| // create a match node chain to collect [0 ... min - 1] required matches |
| for (var i = 0; i < node.min - 1; i++) { |
| if (node.comma && result !== MATCH) { |
| result = createCondition( |
| { type: 'Comma', syntax: node }, |
| result, |
| MISMATCH |
| ); |
| } |
| |
| result = createCondition( |
| matchTerm, |
| result, |
| MISMATCH |
| ); |
| } |
| } |
| |
| return result; |
| } |
| |
| function buildMatchGraph(node) { |
| if (typeof node === 'function') { |
| return { |
| type: 'Generic', |
| fn: node |
| }; |
| } |
| |
| switch (node.type) { |
| case 'Group': |
| var result = buildGroupMatchGraph( |
| node.combinator, |
| node.terms.map(buildMatchGraph), |
| false |
| ); |
| |
| if (node.disallowEmpty) { |
| result = createCondition( |
| result, |
| DISALLOW_EMPTY, |
| MISMATCH |
| ); |
| } |
| |
| return result; |
| |
| case 'Multiplier': |
| return buildMultiplierMatchGraph(node); |
| |
| case 'Type': |
| case 'Property': |
| return { |
| type: node.type, |
| name: node.name, |
| syntax: node |
| }; |
| |
| case 'Keyword': |
| return { |
| type: node.type, |
| name: node.name.toLowerCase(), |
| syntax: node |
| }; |
| |
| case 'AtKeyword': |
| return { |
| type: node.type, |
| name: '@' + node.name.toLowerCase(), |
| syntax: node |
| }; |
| |
| case 'Function': |
| return { |
| type: node.type, |
| name: node.name.toLowerCase() + '(', |
| syntax: node |
| }; |
| |
| case 'String': |
| // convert a one char length String to a Token |
| if (node.value.length === 3) { |
| return { |
| type: 'Token', |
| value: node.value.charAt(1), |
| syntax: node |
| }; |
| } |
| |
| // otherwise use it as is |
| return { |
| type: node.type, |
| value: node.value, |
| syntax: node |
| }; |
| |
| case 'Token': |
| return { |
| type: node.type, |
| value: node.value, |
| syntax: node |
| }; |
| |
| case 'Comma': |
| return { |
| type: node.type, |
| syntax: node |
| }; |
| |
| default: |
| throw new Error('Unknown node type:', node.type); |
| } |
| } |
| |
| module.exports = { |
| MATCH: MATCH, |
| MISMATCH: MISMATCH, |
| DISALLOW_EMPTY: DISALLOW_EMPTY, |
| buildMatchGraph: function(syntaxTree, ref) { |
| if (typeof syntaxTree === 'string') { |
| syntaxTree = parse(syntaxTree); |
| } |
| |
| return { |
| type: 'MatchGraph', |
| match: buildMatchGraph(syntaxTree), |
| syntax: ref || null, |
| source: syntaxTree |
| }; |
| } |
| }; |