def try(re, str, pos)
  if re.respond_to? :to_str
    yield pos+1 if str[pos] == re
  else
    case re[0]
    when :empset
      # nothing to do
    when :empstr
      yield pos
    when :cat
      try_cat(re, str, pos) {|pos2| yield pos2 }
    when :alt
      try_alt(re, str, pos) {|pos2| yield pos2 }
    when :rep
      try_rep(re, str, pos) {|pos2| yield pos2 }
    else
      raise ArgumentError, "unexpected regexp: #{re.inspect}"
    end
  end
end

def try_cat(re, str, pos)
  if re.length == 1
    yield pos
  else
    re2 = [:cat]
    2.upto(re.length-1) {|i| re2 << re[i] }
    try(re[1], str, pos) {|pos2|
      try(re2, str, pos2) {|pos3|
        yield pos3
      }
    }
  end
end

def try_alt(re, str, pos)
  1.upto(re.length-1) {|i|
    try(re[i], str, pos) {|pos2| yield pos2 }
  }
end

def try_rep(re, str, pos)
  try(re[1], str, pos) {|pos2|
    try(re, str, pos2) {|pos3|
      yield pos3
    }
  }
  yield pos
end

def rx_exact(r, str)
  str = str.split(//)
  false # describe here
end

def rx_include(r, str)
  str = str.split(//)
  false # describe here
end

if __FILE__ == $0
  require 'test/unit'

  def rx_ends(re, str, pos)
    a = []
    # str.split(//) returns an array which contains characters of str.
    try(re, str.split(//), pos) {|pos2| a << pos2 }
    a
  end

  class TestRX < Test::Unit::TestCase
    def test_empset
      assert_equal([], rx_ends([:empset], "", 0))
      assert_equal([], rx_ends([:empset], "cat", 0))
    end

    def test_empstr
      assert_equal([0], rx_ends([:empstr], "", 0))
      assert_equal([0], rx_ends([:empstr], "cat", 0))
    end

    def test_char
      assert_equal([1], rx_ends("a", "a", 0))
      assert_equal([1], rx_ends("c", "cat", 0))
      assert_equal([], rx_ends("a", "cat", 0))
      assert_equal([], rx_ends("c", "cat", 1))
      assert_equal([2], rx_ends("a", "cat", 1))
    end

    def test_cat
      assert_equal([2], rx_ends([:cat, "a", "b"], "ab", 0))
      assert_equal([2], rx_ends([:cat, "a", "b"], "ab", 0))
      assert_equal([2], rx_ends([:cat, "c", "a"], "cat", 0))
      assert_equal([2], rx_ends([:cat, [:alt, "a", "b"],
                                       [:alt, "a", "b"]], "abcd", 0))
      assert_equal([2,1,1,0], rx_ends([:cat, [:alt, "a", [:empstr]],
                                             [:alt, "a", [:empstr]]],
                                      "aaaa", 0), "p,35")
      assert_equal([2,3,3,4], rx_ends([:cat, [:alt, "a", [:cat, "a", "a"]],
                                             [:alt, "a", [:cat, "a", "a"]]], "aaaa", 0))

      assert_equal([1], rx_ends("a", "aaaaa", 0))
      assert_equal([2], rx_ends([:cat, "a", "a"], "aaaaa", 0))
      assert_equal([1,2], rx_ends([:alt, "a", [:cat, "a", "a"]], "aaaaa", 0))
      assert_equal([2,3,3,4],
                   rx_ends([:cat, [:alt, "a", [:cat, "a", "a"]],
                                  [:alt, "a", [:cat, "a", "a"]]], "aaaaa", 0))
    end

    def test_alt
      assert_equal([1], rx_ends([:alt, "a", "b"], "ab", 0))
      assert_equal([1], rx_ends([:alt, "c", "a"], "cat", 0))
      assert_equal([2], rx_ends([:alt, "c", "a"], "cat", 1))
      assert_equal([], rx_ends([:alt, "c", "a"], "cat", 2))
      assert_equal([1,2], rx_ends([:alt, "a", [:cat, "a", "b"]], "ab", 0))
    end

    def test_rep
      assert_equal([3,2,1,0], rx_ends([:rep, "a"], "aaa", 0))
      assert_equal([1,0], rx_ends([:rep, "c"], "cat", 0))
      assert_equal([2], rx_ends([:rep, "c"], "cat", 2))
      assert_equal([7,6,5], rx_ends([:rep, "p"], "pineapple", 5))
      assert_equal([2], rx_ends([:rep, "p"], "pineapple", 2))
      assert_equal([4,3,2,1,0], rx_ends([:rep, "a"], "aaaa", 0))
      assert_equal([9,8,7,6,5,4,3,2,1,0], rx_ends([:rep, "a"], "aaaaaaaaa", 0))
    end

    def test_alt_multiarg
      assert_equal([1], rx_ends([:alt, "a", "b", "c"], "a", 0))
      assert_equal([1], rx_ends([:alt, "a", "b", "c"], "b", 0))
      assert_equal([1], rx_ends([:alt, "a", "b", "c"], "c", 0))
      assert_equal([1,2], rx_ends([:alt, "a", [:cat, "a", "a"]], "aa", 0))

      assert_equal([1], rx_ends([:alt, "a", "b", "c", "d"], "a", 0))
      assert_equal([1], rx_ends([:alt, "a", "b", "c", "d"], "b", 0))
      assert_equal([1], rx_ends([:alt, "a", "b", "c", "d"], "c", 0))
      assert_equal([1], rx_ends([:alt, "a", "b", "c", "d"], "d", 0))
      assert_equal([1], rx_ends([:alt, "a"], "a", 0))
      assert_equal([], rx_ends([:alt], "a", 0))
      assert_equal([2,4,3,1], rx_ends([:alt, [:cat, "a", "a"],
                                       [:cat, "a", "a", "a", "a"],
                                       [:cat, "a", "a", "a"],
                                       "a",], "aaaaaaaa", 0))
    end

    def test_cat_multiarg
      assert_equal([4], rx_ends([:cat, "a", "b", "c", "d"], "abcd", 0))

      assert_equal([3,4,4,5,4,5,5,6],
                   rx_ends([:cat, [:alt, "a", [:cat, "a", "a"]],
                                  [:alt, "a", [:cat, "a", "a"]],
                                  [:alt, "a", [:cat, "a", "a"]]], "aaaaaa", 0))
      assert_equal([3,4,4,5,4,5,5],
                   rx_ends([:cat, [:alt, "a", [:cat, "a", "a"]],
                                  [:alt, "a", [:cat, "a", "a"]],
                                  [:alt, "a", [:cat, "a", "a"]]], "aaaaa", 0))

      assert_equal([6], rx_ends([:cat, [:alt, "c", "f"], "a", [:alt, "n", "t"]],
                                "education", 3))
      assert_equal([3], rx_ends([:cat, [:alt, "c", "f"], "a", [:alt, "n", "t"]],
                                "catch", 0))
      assert_equal([3], rx_ends([:cat, [:alt, "c", "f"], "a", [:alt, "n", "t"]],
                                "candle", 0))
      assert_equal([3], rx_ends([:cat, [:alt, "c", "f"], "a", [:alt, "n", "t"]],
                                "fatal", 0))
      assert_equal([3], rx_ends([:cat, [:alt, "c", "f"], "a", [:alt, "n", "t"]],
                                "fang", 0))

      assert_equal([7], rx_ends([:cat, "a", "p", "p"], "pineapple", 4))
      assert_equal([], rx_ends([:cat, "a", "p", "p"], "pineapple", 3))
    end

    def test_rx_exact
      assert_equal(false, rx_exact([:empset], ""))
      assert_equal(false, rx_exact([:empset], "a"))
      assert_equal(true, rx_exact([:empstr], ""))
      assert_equal(false, rx_exact([:empstr], "a"))
      assert_equal(true, rx_exact("a", "a"))
      assert_equal(false, rx_exact("a", "b"))
      assert_equal(false, rx_exact("a", "ab"))
      assert_equal(false, rx_exact("a", "ba"))
      assert_equal(true, rx_exact([:rep, "a"], "aaa"))
      assert_equal(true, rx_exact([:rep, "a"], ""))
      assert_equal(false, rx_exact([:rep, "a"], "bbb"))
      assert_equal(false, rx_exact([:rep, "a"], "aaab"))
      assert_equal(false, rx_exact([:rep, "a"], "baaa"))
      assert_equal(false, rx_exact([:cat, [:rep, "a"], "b"], "aaa"))
      assert_equal(false, rx_exact([:cat, [:rep, "a"], "b"], "baaa"))
      assert_equal(true, rx_exact([:cat, [:rep, "a"], "b"], "aaab"))
      assert_equal(false, rx_exact([:cat, [:rep, "a"], "b"], "aaabb"))
      assert_equal(true, rx_exact([:alt, [:cat, "c", [:cat, "a", "t"]],
                                         [:cat, "d", [:cat, "o", "g"]]], "dog"))
      assert_equal(true, rx_exact([:alt, [:cat, "c", [:cat, "a", "t"]],
                                         [:cat, "d", [:cat, "o", "g"]]], "cat"))
      assert_equal(true, rx_exact([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "ac"))
      assert_equal(true, rx_exact([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "ad"))
      assert_equal(true, rx_exact([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "bc"))
      assert_equal(true, rx_exact([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "bd"))
      assert_equal(false, rx_exact([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "acbd"))
      assert_equal(true, rx_exact([:rep, [:alt, "a", "b"]], "abababbaabbabab"))
      assert_equal(false, rx_exact([:rep, [:alt, "a", "b"]], "abababbzabbabab"))
    end

    def test_rx_include
      assert_equal(false, rx_include([:empset], ""))
      assert_equal(false, rx_include([:empset], "a"))
      assert_equal(true, rx_include([:empstr], ""))
      assert_equal(true, rx_include([:empstr], "a"))
      assert_equal(true, rx_include("a", "a"))
      assert_equal(false, rx_include("a", "b"))
      assert_equal(true, rx_include("a", "ab"))
      assert_equal(true, rx_include("a", "ba"))
      assert_equal(true, rx_include([:rep, "a"], "aaa"))
      assert_equal(true, rx_include([:rep, "a"], ""))
      assert_equal(true, rx_include([:rep, "a"], "bbb"))
      assert_equal(true, rx_include([:rep, "a"], "aaab"))
      assert_equal(true, rx_include([:rep, "a"], "baaa"))
      assert_equal(false, rx_include([:cat, [:rep, "a"], "b"], "aaa"))
      assert_equal(true, rx_include([:cat, [:rep, "a"], "b"], "baaa"))
      assert_equal(true, rx_include([:cat, [:rep, "a"], "b"], "aaab"))
      assert_equal(true, rx_include([:cat, [:rep, "a"], "b"], "aaabb"))
      assert_equal(true, rx_include([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "ac"))
      assert_equal(true, rx_include([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "ad"))
      assert_equal(true, rx_include([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "bc"))
      assert_equal(true, rx_include([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "bd"))
      assert_equal(true, rx_include([:cat, [:alt, "a", "b"], [:alt, "c", "d"]], "acbd"))
      assert_equal(true, rx_include([:rep, [:alt, "a", "b"]], "abababbaabbabab"))
      assert_equal(true, rx_include([:rep, [:alt, "a", "b"]], "abababbzabbabab"))
      assert_equal(false, rx_include([:cat, [:alt, "a", "b"], [:rep, [:alt, "a", "b"]]], "xyz"))
      assert_equal(false, rx_include([:cat, [:rep, [:alt, "a", "b"]], [:alt, "a", "b"]], "xyz"))
    end

    def test_rx_exact_shortcut
      assert_nothing_raised {
        # :non_regexp is not a valid regexp.
        # try(:non_regexp, str, pos) causes an error.
        # If rx_exact terminates try call within first yield,
        # no exception raised because try(:non_regexp) is not called.
        assert_equal(true, rx_exact([:alt, [:cat, "a", "b", "c"],
                                           [:cat, "a", "b", :non_regexp]], "abc"))
      }
    end

    def test_rx_include_shortcut
      assert_nothing_raised {
        # :non_regexp is not a valid regexp.
        # try(:non_regexp, str, pos) causes an error.
        # If rx_include returns just after first yielf from try call,
        # no exception raised because try(:non_regexp) is not called.
        assert_equal(true, rx_include([:alt, "a", "b", "c", :non_regexp], "banana"))
      }
    end

  end
end