define MatchState {
  @value Int enum
  @value String name
  @category MatchState matchFailVal     <- MatchState{ 0, "matchFail" }
  @category MatchState matchCompleteVal <- MatchState{ 1, "matchComplete" }
  @category MatchState matchContinueVal <- MatchState{ 2, "matchContinue" }

  formatted () {
    return "MatchState$" + name + "()"
  }

  equals (x,y) {
    return x.getEnum() == y.getEnum()
  }

  lessThan (x,y) {
    return x.getEnum() < y.getEnum()
  }

  matchFail () {
    return matchFailVal
  }

  matchComplete () {
    return matchCompleteVal
  }

  matchContinue () {
    return matchContinueVal
  }

  @value getEnum () -> (Int)
  getEnum () {
    return enum
  }
}

define MatchSingle {
  @value #c match

  create (match) {
    return MatchSingle<#c>{ match }
  }

  matchesEmpty () {
    return false
  }

  newMatcher () {
    return MatchSingleMatcher<#c>$create(match)
  }
}

concrete MatchSingleMatcher<#c> {
  #c defines Equals<#c>

  refines Matcher<#c>

  @type create (#c) -> (MatchSingleMatcher<#c>)
}

define MatchSingleMatcher {
  @value #c match
  @value MatchState state

  create (match) {
    return MatchSingleMatcher<#c>{ match, MatchState$matchContinue() }
  }

  matchSatisfied () {
    return state `MatchState$equals` MatchState$matchComplete()
  }

  tryNextMatch (data) {
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      return (state <- MatchState$matchFail())
    }
    if (data `#c$equals` match) {
      return (state <- MatchState$matchComplete())
    } else {
      return (state <- MatchState$matchFail())
    }
  }
}

define MatchRange {
  @value #c minMatch
  @value #c maxMatch

  create (minMatch,maxMatch) {
    return MatchRange<#c>{ minMatch, maxMatch }
  }

  matchesEmpty () {
    return false
  }

  newMatcher () {
    return MatchRangeMatcher<#c>$create(minMatch,maxMatch)
  }
}

concrete MatchRangeMatcher<#c> {
  #c defines LessThan<#c>

  refines Matcher<#c>

  @type create (#c,#c) -> (MatchRangeMatcher<#c>)
}

define MatchRangeMatcher {
  @value #c minMatch
  @value #c maxMatch
  @value MatchState state

  create (minMatch,maxMatch) {
    return MatchRangeMatcher<#c>{ minMatch, maxMatch, MatchState$matchContinue() }
  }

  matchSatisfied () {
    return state `MatchState$equals` MatchState$matchComplete()
  }

  tryNextMatch (data) {
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      return (state <- MatchState$matchFail())
    }
    if (!(data `#c$lessThan` minMatch) && !(maxMatch `#c$lessThan` data)) {
      return (state <- MatchState$matchComplete())
    } else {
      return (state <- MatchState$matchFail())
    }
  }
}

define MatchAny {
  create () {
    return MatchAny{ }
  }

  matchesEmpty () {
    return false
  }

  newMatcher () {
    return MatchAnyMatcher$create()
  }
}

concrete MatchAnyMatcher {
  refines Matcher<any>

  @type create () -> (MatchAnyMatcher)
}

define MatchAnyMatcher {
  @value MatchState state

  create () {
    return MatchAnyMatcher{ MatchState$matchContinue() }
  }

  matchSatisfied () {
    return state `MatchState$equals` MatchState$matchComplete()
  }

  tryNextMatch (data) {
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      return (state <- MatchState$matchFail())
    }
    return (state <- MatchState$matchComplete())
  }
}

define MatchEmpty {
  create () {
    return MatchEmpty{ }
  }

  matchesEmpty () {
    return true
  }

  newMatcher () {
    return MatchEmptyMatcher$create()
  }
}

concrete MatchEmptyMatcher {
  refines Matcher<any>

  @type create () -> (MatchEmptyMatcher)
}

define MatchEmptyMatcher {
  @value Bool failed

  create () {
    return MatchEmptyMatcher{ false }
  }

  matchSatisfied () {
    return !failed
  }

  tryNextMatch (data) {
    failed <- true
    return MatchState$matchFail()
  }
}

define MatchRepeat {
  @value MatcherTemplate<#c> template
  @value Int minCount
  @value Int maxCount

  createZeroPlus (template) {
    return createRange(0,0,template)
  }

  createOnePlus (template) {
    return createRange(1,0,template)
  }

  createRange (minCount,maxCount,template) {
    return MatchRepeat<#c>{ template, minCount, maxCount }
  }

  matchesEmpty () {
    return minCount <= 0 || template.matchesEmpty()
  }

  newMatcher () {
    return MatchRepeatMatcher<#c>$create(minCount,maxCount,template)
  }
}

concrete MatchRepeatMatcher<#c> {
  refines Matcher<#c>

  @type create (Int,Int,MatcherTemplate<#c>) -> (MatchRepeatMatcher<#c>)
}

define MatchRepeatMatcher {
  @value MatcherTemplate<#c> template
  @value Matcher<#c> matcher
  @value Int minCount
  @value Int maxCount // 0 means unlimited.
  @value Int repetitionCount
  @value MatchState lastState

  create (minCount,maxCount,template) {
    return MatchRepeatMatcher<#c>{ template, template.newMatcher(), minCount,
                                   maxCount, 0, MatchState$matchComplete() }
  }

  matchSatisfied () {
    if (lastState `MatchState$equals` MatchState$matchFail()) {
      return false
    }
    if (lastState `MatchState$equals` MatchState$matchContinue() &&
        (repetitionCount+1 >= minCount || template.matchesEmpty()) &&
        matcher.matchSatisfied()) {
      // The rest of the current repetition can be ignored.
      return true
    }
    if (lastState `MatchState$equals` MatchState$matchComplete() &&
        (repetitionCount >= minCount || template.matchesEmpty())) {
      return true
    }
    return false
  }

  tryNextMatch (data) (state) {
    if (atMax() || lastState `MatchState$equals` MatchState$matchFail()) {
      return MatchState$matchFail()
    }
    Bool canSkip <- matcher.matchSatisfied()
    state <- matcher.tryNextMatch(data)
    if (state `MatchState$equals` MatchState$matchFail() &&
        lastState `MatchState$equals` MatchState$matchContinue() && canSkip) {
      // Handle the case where an optional end to the pattern can be skipped.
      ~ incrementMatch()
      ~ startRepeat()
      state <- matcher.tryNextMatch(data)
    }
    lastState <- state
    if (state `MatchState$equals` MatchState$matchComplete()) {
      ~ incrementMatch()
      ~ startRepeat()
      if (atMax()) {
        state <- MatchState$matchComplete()
      } else {
        state <- MatchState$matchContinue()
      }
    }
  }

  @value incrementMatch () -> ()
  incrementMatch () {
    repetitionCount <- repetitionCount+1
  }

  @value atMax () -> (Bool)
  atMax () {
    return maxCount > 0 && repetitionCount >= maxCount
  }

  @value startRepeat () -> ()
  startRepeat () {
    matcher <- template.newMatcher()
  }
}

define MatchChoices {
  @value optional ReadSequence<MatcherTemplate<#c>> choices

  create (choices) {
    return MatchChoices<#c>{ choices }
  }

  matchesEmpty () {
    scoped {
      optional ReadSequence<MatcherTemplate<#c>> current <- choices
    } in while (present(current)) {
      if (require(current).value().matchesEmpty()) {
        return true
      }
    } update {
      current <- require(current).next()
    }
    return false
  }

  newMatcher () {
    return MatchChoicesMatcher<#c>$create(recursiveNewMatcher(choices))
  }

  @type recursiveNewMatcher (optional ReadSequence<MatcherTemplate<#c>>) ->
                            (optional ReadSequence<Matcher<#c>>)
  recursiveNewMatcher (choices) {
    if (!present(choices)) {
      return empty
    }
    return LinkedNode<Matcher<#c>>$create(require(choices).value().newMatcher(),
                                          recursiveNewMatcher(require(choices).next()))
  }
}

concrete MatchChoicesMatcher<#c> {
  refines Matcher<#c>

  @type create (optional ReadSequence<Matcher<#c>>) -> (MatchChoicesMatcher<#c>)
}

define MatchChoicesMatcher {
  @value optional ReadSequence<Matcher<#c>> choices

  create (choices) {
    return MatchChoicesMatcher<#c>{ choices }
  }

  matchSatisfied () {
    scoped {
      optional ReadSequence<Matcher<#c>> current <- choices
    } in while (present(current)) {
      if (require(current).value().matchSatisfied()) {
        return true
      }
    } update {
      current <- require(current).next()
    }
    return false
  }

  tryNextMatch (data) (state) {
    state <- MatchState$matchFail()
    scoped {
      optional ReadSequence<Matcher<#c>> current <- choices
    } in while (present(current)) {
      // NOTE: Failing matchers are left in for simplicity, under the assumption
      // that they will keep failing.
      MatchState state2 <- require(current).value().tryNextMatch(data)
      if (state `MatchState$lessThan` state2) {
        state <- state2
      }
    } update {
      current <- require(current).next()
    }
  }
}

define MatchBranches {
  @value MatchBrancherTemplate<#c> template

  create (template) {
    return MatchBranches<#c>{ template }
  }

  matchesEmpty () {
    return template.matchesEmpty()
  }

  newMatcher () {
    return MatchBranchesMatcher<#c>$create(template.newBrancher())
  }
}

concrete MatchBranchesMatcher<#c> {
  refines Matcher<#c>

  @type create (MatchBrancher<#c>) -> (MatchBranchesMatcher<#c>)
}

define MatchBranchesMatcher {
  @value optional ReadSequence<MatchBrancher<#c>> branches
  @value Bool complete

  create (brancher) {
    return MatchBranchesMatcher<#c>{ LinkedNode<MatchBrancher<#c>>$create(brancher,empty), false }
  }

  matchSatisfied () {
    if (complete) {
      return true
    }
    scoped {
      optional ReadSequence<MatchBrancher<#c>> current <- branches
    } in while (present(current)) {
      if (require(current).value().matchSatisfied()) {
        return true
      }
    } update {
      current <- require(current).next()
    }
    return false
  }

  tryNextMatch (data) (state) {
    state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<#c>> current <- branches
    branches <- empty
    complete <- false
    scoped {
    } in while(present(current)) {
      { MatchState state2, optional ReadSequence<MatchBrancher<#c>> branches2 } <-
          require(current).value().tryBranches(data)
      if (state2 `MatchState$equals` MatchState$matchComplete()) {
        complete <- true
      }
      if (state `MatchState$lessThan` state2) {
        state <- state2
      }
      branches <- LinkedNode<MatchBrancher<#c>>$concatSequences(branches2,branches)
    } update {
      current <- require(current).next()
    }
  }
}

concrete BranchRepeatMatcher<#c> {
  refines MatchBrancher<#c>

  @type create (Int,Int,MatcherTemplate<#c>) -> (BranchRepeatMatcher<#c>)
  @value tryBranches (#c) -> (MatchState,optional ReadSequence<BranchRepeatMatcher<#c>>)
}

define BranchRepeatMatcher {
  @value MatcherTemplate<#c> template
  @value Matcher<#c> matcher
  @value Int minCount
  @value Int maxCount // 0 means unlimited.
  @value Int repetitionCount
  @value MatchState lastState

  create (minCount,maxCount,template) {
    return BranchRepeatMatcher<#c>{ template, template.newMatcher(), minCount,
                                    maxCount, 0, MatchState$matchComplete() }
  }

  matchSatisfied () {
    if (lastState `MatchState$equals` MatchState$matchFail()) {
      return false
    }
    if (lastState `MatchState$equals` MatchState$matchContinue() &&
        (repetitionCount+1 >= minCount || template.matchesEmpty()) &&
        matcher.matchSatisfied()) {
      // The rest of the current repetition can be ignored.
      return true
    }
    if (lastState `MatchState$equals` MatchState$matchComplete() &&
        (repetitionCount >= minCount || template.matchesEmpty())) {
      return true
    }
    return false
  }

  tryBranches (data) (state,branch) {
    state <- MatchState$matchFail()
    branch <- empty
    if (atMax() || lastState `MatchState$equals` MatchState$matchFail()) {
      return _
    }
    if (lastState `MatchState$equals` MatchState$matchContinue()) {
      // Handle a possible single branch.
      Bool canSkip <- matcher.matchSatisfied()
      state <- matcher.tryNextMatch(data)
      if (canSkip) {
        if (state `MatchState$equals` MatchState$matchContinue()) {
          // Add a branch for the optional suffix.
          branch <- LinkedNode<BranchRepeatMatcher<#c>>$create(
              BranchRepeatMatcher<#c>{ template, matcher, minCount,
                                       maxCount, repetitionCount,
                                       MatchState$matchContinue() },empty)
        }
        // Continue, skipping over the optional suffix.
        ~ incrementMatch()
        ~ startRepeat()
        if (atMax()) {
          // Skipping the branch puts us at the max.
          return _
        }
        state <- matcher.tryNextMatch(data)
      }
    } else {
      // Branching is not possible.
      state <- matcher.tryNextMatch(data)
    }
    lastState <- state
    if (state `MatchState$equals` MatchState$matchComplete()) {
      ~ incrementMatch()
      ~ startRepeat()
      if (!atMax()) {
        branch <- LinkedNode<BranchRepeatMatcher<#c>>$create(self,branch)
      }
    } elif (state `MatchState$equals` MatchState$matchContinue()) {
      branch <- LinkedNode<BranchRepeatMatcher<#c>>$create(self,branch)
    }
    if (present(branch)) {
      state <- MatchState$matchContinue()
    }
  }

  @value incrementMatch () -> ()
  incrementMatch () {
    repetitionCount <- repetitionCount+1
  }

  @value atMax () -> (Bool)
  atMax () {
    return maxCount > 0 && repetitionCount >= maxCount
  }

  @value startRepeat () -> ()
  startRepeat () {
    matcher <- template.newMatcher()
  }
}

define BranchSequence {
  @value optional ReadSequence<MatcherTemplate<#c>> sequence

  create (sequence) {
    return BranchSequence<#c>{ sequence }
  }

  matchesEmpty () {
    scoped {
      optional ReadSequence<MatcherTemplate<#c>> current <- sequence
    } in while (present(current)) {
      if (!require(current).value().matchesEmpty()) {
        return false
      }
    } update {
      current <- require(current).next()
    }
    return true
  }

  newBrancher () {
    return BranchSequenceMatcher<#c>$create(sequence)
  }
}

concrete BranchSequenceMatcher<#c> {
  refines MatchBrancher<#c>

  @type create (optional ReadSequence<MatcherTemplate<#c>>) -> (BranchSequenceMatcher<#c>)
  @value tryBranches (#c) -> (MatchState,optional ReadSequence<BranchSequenceMatcher<#c>>)
}

define BranchSequenceMatcher {
  @value optional Matcher<#c> continued
  @value optional ReadSequence<MatcherTemplate<#c>> sequence
  @value Bool consumed

  create (sequence) {
    return BranchSequenceMatcher<#c>{ empty, sequence, false }
  }

  matchSatisfied () {
    if (consumed) {
      return false
    }
    if (present(continued) && !require(continued).matchSatisfied()) {
      return false
    }
    scoped {
      optional ReadSequence<MatcherTemplate<#c>> current <- sequence
    } in while (present(current)) {
      if (!require(current).value().matchesEmpty()) {
        return false
      }
    } update {
      current <- require(current).next()
    }
    return true
  }

  tryBranches (data) {
    if (consumed) {
      return { MatchState$matchFail(), empty }
    }
    consumed <- true
    return recursiveBranch(data,continued,sequence)
  }

  @type recursiveBranch (#c,optional Matcher<#c>,optional ReadSequence<MatcherTemplate<#c>>) ->
                        (MatchState,optional ReadSequence<BranchSequenceMatcher<#c>>)
  recursiveBranch (data,continued,sequence) (state,branch) {
    state <- MatchState$matchFail()
    branch <- empty
    if (!present(continued) && !present(sequence)) {
      return _
    }
    optional Matcher<#c> continued2 <- continued
    optional ReadSequence<MatcherTemplate<#c>> sequence2 <- sequence
    if (!present(continued2)) {
      continued2 <- require(sequence2).value().newMatcher()
      sequence2 <- require(sequence2).next()
    }
    if (require(continued2).matchSatisfied()) {
      { MatchState state2, branch } <- recursiveBranch(data,empty,sequence2)
      if (state `MatchState$lessThan` state2) {
        state <- state2
      }
    }
    MatchState state2 <- require(continued2).tryNextMatch(data)
    if (state `MatchState$lessThan` state2) {
      state <- state2
    }
    if (state2 `MatchState$equals` MatchState$matchComplete()) {
      if (present(sequence2)) {
        // Add a branch to continue this sequence.
        branch <- LinkedNode<BranchSequenceMatcher<#c>>$create(
            BranchSequenceMatcher<#c>{ empty, sequence2, false },branch)
        state <- MatchState$matchContinue()
      } else {
        // Add a branch to serve as a record of completeness. It will fail to
        // match anything, but matchSatisfied() will return true.
        branch <- LinkedNode<BranchSequenceMatcher<#c>>$create(
            BranchSequenceMatcher<#c>{ empty, empty, false },branch)
      }
    } elif (state `MatchState$equals` MatchState$matchContinue()) {
        // Add a branch to continue this sequence.
        branch <- LinkedNode<BranchSequenceMatcher<#c>>$create(
            BranchSequenceMatcher<#c>{ continued2, sequence2, false },branch)
    }
  }
}

define BranchRepeat {
  @value MatcherTemplate<#c> template
  @value Int minCount
  @value Int maxCount

  createZeroPlus (template) {
    return createRange(0,0,template)
  }

  createOnePlus (template) {
    return createRange(1,0,template)
  }

  createRange (minCount,maxCount,template) {
    return BranchRepeat<#c>{ template, minCount, maxCount }
  }

  matchesEmpty () {
    return minCount <= 0 || template.matchesEmpty()
  }

  newBrancher () {
    return BranchRepeatMatcher<#c>$create(minCount,maxCount,template)
  }
}

define LinkedNode {
  @value optional ReadSequence<#x> nextNode
  @value #x data

  create (data,nextNode) {
    return LinkedNode<#x>{ nextNode, data }
  }

  concatSequences (head1,head2) {
    if (!present(head2)) {
      return head1
    } elif (present(head1)) {
      return LinkedNode<#x>$create(require(head1).value(),
                                   concatSequences(require(head1).next(),head2))
    } else {
      return head2
    }
  }

  value () {
    return data
  }

  next () {
    return nextNode
  }
}