concrete MatchState {
  refines Formatted
  defines Equals<MatchState>
  defines LessThan<MatchState>

  // Ordered from low to high.

  @type matchFail     () -> (MatchState) // Matching has failed.
  @type matchComplete () -> (MatchState) // End of the pattern.
  @type matchContinue () -> (MatchState) // Matching must continue.
}

@value interface Matcher<#c|> {
  // Returns true if the pattern is complete without additional data.
  matchSatisfied () -> (Bool)

  // This can be called as long as it returns matchContinue(). The matcher does
  // not branch; each call updates it with the next data point in the input.
  //
  // Returns:
  // - matchFail(): The pattern cannot be completed.
  // - matchContinue(): Matching can continue; check matchSatisfied() to see if
  //                    more data is required to complete the pattern.
  // - matchComplete(): The pattern has been completed and cannot match any
  //                    additional data.
  tryNextMatch (#c) -> (MatchState)
}

@value interface MatcherTemplate<#c|> {
  // Returns true if the pattern can match an empty sequence.
  matchesEmpty () -> (Bool)
  newMatcher () -> (Matcher<#c>)
}

@value interface MatchBrancher<#c|> {
  // Returns true if the pattern is complete without additional data.
  matchSatisfied () -> (Bool)

  // NOTE: Calling this invalidates the MatchBrancher. Subsequent calls should
  // be done against the returned branches.
  // Returns:
  // - state: The highest state of the branches checked.
  // - branches: All branches with a status of matchContinue().
  tryBranches (#c) -> (MatchState /*state*/,
                       optional ReadSequence<MatchBrancher<#c>> /*branches*/)
}

@value interface MatchBrancherTemplate<#c|> {
  // Returns true if the pattern can match an empty sequence.
  matchesEmpty () -> (Bool)
  newBrancher () -> (MatchBrancher<#c>)
}

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

  refines MatcherTemplate<#c>

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

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

  refines MatcherTemplate<#c>

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

concrete MatchAny {
  refines MatcherTemplate<any>

  @type create () -> (MatchAny)
}

concrete MatchEmpty {
  refines MatcherTemplate<any>

  @type create () -> (MatchEmpty)
}

concrete MatchRepeat<#c> {
  refines MatcherTemplate<#c>

  @type createZeroPlus (MatcherTemplate<#c>) -> (MatchRepeat<#c>)
  @type createOnePlus (MatcherTemplate<#c>) -> (MatchRepeat<#c>)
  @type createRange (Int,Int,MatcherTemplate<#c>) -> (MatchRepeat<#c>)
}

concrete MatchChoices<#c> {
  refines MatcherTemplate<#c>

  @type create (optional ReadSequence<MatcherTemplate<#c>>) -> (MatchChoices<#c>)
}

concrete MatchBranches<#c> {
  refines MatcherTemplate<#c>

  @type create (MatchBrancherTemplate<#c>) -> (MatcherTemplate<#c>)
}

concrete BranchRepeat<#c> {
  refines MatchBrancherTemplate<#c>

  @type createZeroPlus (MatcherTemplate<#c>) -> (BranchRepeat<#c>)
  @type createOnePlus (MatcherTemplate<#c>) -> (BranchRepeat<#c>)
  @type createRange (Int,Int,MatcherTemplate<#c>) -> (BranchRepeat<#c>)
}

concrete BranchSequence<#c> {
  refines MatchBrancherTemplate<#c>

  @type create (optional ReadSequence<MatcherTemplate<#c>>) -> (BranchSequence<#c>)
}

@value interface ReadSequence<|#c> {
  value () -> (#c)
  next () -> (optional ReadSequence<#c>)
}

concrete LinkedNode<#x> {
  refines ReadSequence<#x>

  @type create (#x,optional ReadSequence<#x>) -> (ReadSequence<#x>)
  @type concatSequences (optional ReadSequence<#x>,optional ReadSequence<#x>) ->
                        (optional ReadSequence<#x>)
}