text: 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;
      }
  };
  