testcase "MatchSingle match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "x"
    MatcherTemplate<Char> template <- MatchSingle<Char>$create('x')
    Matcher<Char> matcher <- template.newMatcher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Should only match once.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Should match again after reset.
    matcher <- template.newMatcher()
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
  }
}


testcase "MatchSingle non-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "x"
    MatcherTemplate<Char> template <- MatchSingle<Char>$create('x')
    Matcher<Char> matcher <- template.newMatcher()

    MatchState state <- matcher.tryNextMatch('y')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }

    // Should keep failing to match.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
  }
}


testcase "MatchRange match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]"
    MatcherTemplate<Char> template <- MatchRange<Char>$create('w','y')
    Matcher<Char> matcher <- template.newMatcher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Should only match once.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Should match again after reset.
    matcher <- template.newMatcher()
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
  }
}


testcase "MatchRange non-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]"
    MatcherTemplate<Char> template <- MatchRange<Char>$create('w','y')
    Matcher<Char> matcher <- template.newMatcher()

    MatchState state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }

    // Should keep failing to match.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
  }
}


testcase "MatchAny" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "."
    MatcherTemplate<Char> template <- MatchAny$create()
    Matcher<Char> matcher <- template.newMatcher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Should only match once.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Should match again after reset.
    matcher <- template.newMatcher()
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
  }
}


testcase "MatchEmpty" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: ""
    MatcherTemplate<Char> template <- MatchEmpty$create()
    Matcher<Char> matcher <- template.newMatcher()

    if (!template.matchesEmpty()) {
      fail("doesn't match empty")
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Should match again after reset.
    matcher <- template.newMatcher()
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }
  }
}


testcase "MatchRepeat match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]{2,3}"
    MatcherTemplate<Char> template <-
        MatchRepeat<Char>$createRange(2,3,MatchRange<Char>$create('w','y'))
    Matcher<Char> matcher <- template.newMatcher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('y')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Third character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }

    // Fourth character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Reset to reuse the matcher.
    matcher <- template.newMatcher()

    // Fourth character.
    state <- matcher.tryNextMatch('w')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Fifth character.
    state <- matcher.tryNextMatch('w')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }
  }
}


testcase "MatchRepeat nested" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "(x*){2,}"
    MatcherTemplate<Char> template <-
        MatchRepeat<Char>$createRange(2,0,
            MatchRepeat<Char>$createZeroPlus(MatchSingle<Char>$create('x')))
    Matcher<Char> matcher <- template.newMatcher()

    if (!template.matchesEmpty()) {
      fail("doesn't match empty")
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Third character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }
  }
}


testcase "MatchRepeat non-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]{2,3}"
    MatcherTemplate<Char> template <-
        MatchRepeat<Char>$createRange(2,3,MatchRange<Char>$create('w','y'))
    Matcher<Char> matcher <- template.newMatcher()

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('q')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Should keep failing to match.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
  }
}


testcase "MatchRepeat optional suffix" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "(ab*)*"
    MatcherTemplate<Char> template <-
        MatchRepeat<Char>$createZeroPlus(
            MatchBranches<Char>$create(
                BranchSequence<Char>$create(
                    LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),
                        LinkedNode<MatcherTemplate<Char>>$create(
                            MatchRepeat<Char>$createZeroPlus(MatchSingle<Char>$create('b')),empty)))))
    Matcher<Char> matcher <- template.newMatcher()

    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('b')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Third character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }
  }
}


testcase "MatchChoices match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]|a*"
    MatcherTemplate<Char> template <-
        MatchChoices<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(MatchRange<Char>$create('w','y'),
                LinkedNode<MatcherTemplate<Char>>$create(
                    MatchBranches<Char>$create(
                        BranchRepeat<Char>$createZeroPlus(MatchSingle<Char>$create('a'))),empty)))
    Matcher<Char> matcher <- template.newMatcher()

    MatchState state <- MatchState$matchFail()

    if (!template.matchesEmpty()) {
      fail("doesn't match empty")
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // First character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }

    // Second character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }

    // Third character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }

    // Reset to reuse the matcher.
    matcher <- template.newMatcher()

    // First character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
  }
}


testcase "MatchChoices non-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]|a*"
    MatcherTemplate<Char> template <-
        MatchChoices<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(MatchRange<Char>$create('w','y'),
                LinkedNode<MatcherTemplate<Char>>$create(
                    MatchBranches<Char>$create(
                        BranchRepeat<Char>$createZeroPlus(MatchSingle<Char>$create('a'))),empty)))
    Matcher<Char> matcher <- template.newMatcher()

    if (!template.matchesEmpty()) {
      fail("doesn't match empty")
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }

    // Should keep failing to match.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
  }
}


testcase "MatchChoices empty choice" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]|a{2,2}|"
    MatcherTemplate<Char> template <-
        MatchChoices<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(MatchRange<Char>$create('w','y'),
                LinkedNode<MatcherTemplate<Char>>$create(
                    MatchBranches<Char>$create(
                        BranchRepeat<Char>$createRange(2,2,MatchSingle<Char>$create('a'))),
                    LinkedNode<MatcherTemplate<Char>>$create(
                        MatchEmpty$create(),empty))))
    Matcher<Char> matcher <- template.newMatcher()

    if (!template.matchesEmpty()) {
      fail("doesn't match empty")
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }
  }
}


testcase "BranchRepeat match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]{2,3}"
    MatchBrancherTemplate<Char> template <-
        BranchRepeat<Char>$createRange(2,3,MatchRange<Char>$create('w','y'))
    MatchBrancher<Char> brancher <- template.newBrancher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (brancher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }

    brancher <- require(branches).value()
    if (brancher.matchSatisfied()) {
      fail("match satisfied")
    }
    branches <- require(branches).next()
    if (present(branches)) {
      fail("branch present")
    }

    // Second character.
    { state, branches } <- brancher.tryBranches('y')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }
    if (!brancher.matchSatisfied()) {
      fail("match not satisfied")
    }

    brancher <- require(branches).value()
    branches <- require(branches).next()
    if (present(branches)) {
      fail("branch present")
    }

    // Third character.
    { state, branches } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (present(branches)) {
      fail("branch present")
    }

    // Reset to reuse the brancher.
    brancher <- template.newBrancher()

    // Fourth character.
    { state, branches } <- brancher.tryBranches('w')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }
  }
}


testcase "BranchRepeat nested" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "(x*){2,}"
    MatchBrancherTemplate<Char> template <-
        BranchRepeat<Char>$createRange(2,0,
            MatchBranches<Char>$create(
                BranchRepeat<Char>$createZeroPlus(MatchSingle<Char>$create('x'))))
    MatchBrancher<Char> brancher <- template.newBrancher()

    if (!template.matchesEmpty()) {
      fail("doesn't match empty")
    }
    if (!brancher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }

    brancher <- require(branches).value()
    if (!brancher.matchSatisfied()) {
      fail("match not satisfied")
    }
    branches <- require(branches).next()
    if (present(branches)) {
      fail("branch present")
    }

    // Second character.
    { state, branches } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }

    brancher <- require(branches).value()
    if (!brancher.matchSatisfied()) {
      fail("match not satisfied")
    }
    // Expect one additional branch to continue "xx*".
    branches <- require(branches).next()
    if (!present(branches)) {
      fail("branch missing")
    }

    // Third character, branch 1.
    { state, _ } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }

    brancher <- require(branches).value()
    if (!brancher.matchSatisfied()) {
      fail("match not satisfied")
    }
    // No more branches expected.
    branches <- require(branches).next()
    if (present(branches)) {
      fail("branch present")
    }

    // Third character, branch 2.
    { state, _ } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
  }
}


testcase "BranchRepeat non-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]{2,3}"
    MatchBrancherTemplate<Char> template <-
        BranchRepeat<Char>$createRange(2,3,MatchRange<Char>$create('w','y'))
    MatchBrancher<Char> brancher <- template.newBrancher()

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }

    brancher <- require(branches).value()
    if (brancher.matchSatisfied()) {
      fail("match satisfied")
    }
    branches <- require(branches).next()
    if (present(branches)) {
      fail("branch present")
    }

    // Second character.
    { state, branches } <- brancher.tryBranches('q')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (present(branches)) {
      fail("branch present")
    }
  }
}


testcase "BranchSequence match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]a"
    MatchBrancherTemplate<Char> template <-
        BranchSequence<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(MatchRange<Char>$create('w','y'),
                LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),empty)))
    MatchBrancher<Char> brancher <- template.newBrancher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (brancher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }

    brancher <- require(branches).value()
    branches <- require(branches).next()
    if (present(branches)) {
      fail("branch present")
    }

    // Second character.
    { state, branches } <- brancher.tryBranches('a')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }

    // The final branch should just be a record of completeness.
    if (!require(branches).value().matchSatisfied()) {
      fail("match not satisfied")
    }
    { state, branches } <- require(branches).value().tryBranches('a')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }

    // Reset to reuse the brancher.
    brancher <- template.newBrancher()

    // Third character.
    { state, branches } <- brancher.tryBranches('y')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }
  }
}


testcase "BranchSequence non-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]a"
    MatchBrancherTemplate<Char> template <-
        BranchSequence<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(MatchRange<Char>$create('w','y'),
                LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),empty)))
    MatchBrancher<Char> brancher <- template.newBrancher()

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('q')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (present(branches)) {
      fail("branch present")
    }

    // Should keep failing to match.
    { state, branches } <- brancher.tryBranches('x')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
  }
}


testcase "BranchSequence skip empty failed" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "a*b"
    MatchBrancherTemplate<Char> template <-
        BranchSequence<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(
                MatchBranches<Char>$create(
                    BranchRepeat<Char>$createZeroPlus(MatchSingle<Char>$create('a'))),
                LinkedNode<MatcherTemplate<Char>>$create(
                    MatchSingle<Char>$create('b'),empty)))
    MatchBrancher<Char> brancher <- template.newBrancher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (brancher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('b')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }
  }
}


testcase "BranchSequence fail non-empty field" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "a+b"
    MatchBrancherTemplate<Char> template <-
        BranchSequence<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(
                MatchBranches<Char>$create(
                    BranchRepeat<Char>$createOnePlus(MatchSingle<Char>$create('a'))),
                LinkedNode<MatcherTemplate<Char>>$create(
                    MatchSingle<Char>$create('b'),empty)))
    MatchBrancher<Char> brancher <- template.newBrancher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (brancher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('b')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (present(branches)) {
      fail("branch present")
    }
  }
}


testcase "BranchSequence branch sequence multi-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "a*a{0,2}"
    MatchBrancherTemplate<Char> template <-
        BranchSequence<Char>$create(
            LinkedNode<MatcherTemplate<Char>>$create(
                MatchBranches<Char>$create(
                    BranchRepeat<Char>$createZeroPlus(MatchSingle<Char>$create('a'))),
                LinkedNode<MatcherTemplate<Char>>$create(
                    MatchBranches<Char>$create(
                        BranchRepeat<Char>$createRange(0,2,MatchSingle<Char>$create('a'))),empty)))
    MatchBrancher<Char> brancher <- template.newBrancher()

    if (!template.matchesEmpty()) {
      fail("doesn't match empty")
    }
    if (!brancher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- MatchState$matchFail()
    optional ReadSequence<MatchBrancher<Char>> branches <- empty

    // First character.
    { state, branches } <- brancher.tryBranches('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!present(branches)) {
      fail("branch missing")
    }

    brancher <- require(branches).value()
    branches <- require(branches).next()
    if (!present(branches)) {
      fail("branch missing")
    }

    // TODO: This assumes that the branches are ordered from longest to shortest
    // remaining sequence.

    // Second character, branch 1.
    { state, _ } <- brancher.tryBranches('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }

    brancher <- require(branches).value()
    branches <- require(branches).next()
    if (present(branches)) {
      fail("branch present")
    }

    // Second character, branch 2.
    { state, _ } <- brancher.tryBranches('a')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
  }
}


testcase "MatchBranches match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]a"
    MatcherTemplate<Char> template <-
        MatchBranches<Char>$create(
            BranchSequence<Char>$create(
                LinkedNode<MatcherTemplate<Char>>$create(MatchRange<Char>$create('w','y'),
                    LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),empty))))
    Matcher<Char> matcher <- template.newMatcher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Reset to reuse the matcher.
    matcher <- template.newMatcher()

    // Third character.
    state <- matcher.tryNextMatch('y')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
  }
}


testcase "MatchBranches non-match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "[w-y]a"
    MatcherTemplate<Char> template <-
        MatchBranches<Char>$create(
            BranchSequence<Char>$create(
                LinkedNode<MatcherTemplate<Char>>$create(MatchRange<Char>$create('w','y'),
                    LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),empty))))
    Matcher<Char> matcher <- template.newMatcher()

    if (template.matchesEmpty()) {
      fail("matches empty")
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('x')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('q')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Should keep failing to match.
    state <- matcher.tryNextMatch('y')
    if (!(state `MatchState$equals` MatchState$matchFail())) {
      fail(state)
    }
  }
}


testcase "MatchBranches branched match" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "ab"
    MatcherTemplate<Char> templateAB <-
        MatchBranches<Char>$create(
            BranchSequence<Char>$create(
                LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),
                    LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('b'),empty))))
    // Pattern: "ac"
    MatcherTemplate<Char> templateAC <-
        MatchBranches<Char>$create(
            BranchSequence<Char>$create(
                LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),
                    LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('c'),empty))))
    // Pattern: "(ab)*ac"
    MatcherTemplate<Char> template <-
        MatchBranches<Char>$create(
            BranchSequence<Char>$create(
                LinkedNode<MatcherTemplate<Char>>$create(
                    MatchBranches<Char>$create(
                        BranchRepeat<Char>$createZeroPlus(templateAB)),
                    LinkedNode<MatcherTemplate<Char>>$create(templateAC,empty))))
    Matcher<Char> matcher <- template.newMatcher()

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('c')
    if (!(state `MatchState$equals` MatchState$matchComplete())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    // Reset to reuse the matcher.
    matcher <- template.newMatcher()

    // First character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('b')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }
  }
}


testcase "MatchBranches partial repeat" {
  success Test$execute()
}

concrete Test {
  @type execute () -> ()
}

define Test {
  execute () {
    // Pattern: "(ab)*"
    MatcherTemplate<Char> template <-
        MatchBranches<Char>$create(
            BranchRepeat<Char>$createZeroPlus(
                MatchBranches<Char>$create(
                    BranchSequence<Char>$create(
                        LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('a'),
                            LinkedNode<MatcherTemplate<Char>>$create(MatchSingle<Char>$create('b'),empty))))))
    Matcher<Char> matcher <- template.newMatcher()

    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }

    MatchState state <- MatchState$matchFail()

    // First character.
    state <- matcher.tryNextMatch('a')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (matcher.matchSatisfied()) {
      fail("match satisfied")
    }

    // Second character.
    state <- matcher.tryNextMatch('b')
    if (!(state `MatchState$equals` MatchState$matchContinue())) {
      fail(state)
    }
    if (!matcher.matchSatisfied()) {
      fail("match not satisfied")
    }
  }
}