def try_plus_lazy(re, str, pos, md, &b)
  # implement this method.
end

def try_moretimes(re, str, pos, md, &b)
  # implement this method.
end

def cap_include(r, str)
  str = str.split(//)
  0.upto(str.length) {|b|
    try(r, str, b, {}) {|e, md|
      md = md.dup
      md[:all] = b...e
      return md 
    }
  }
  nil
end

def cap_exact(r, str)
  str = str.split(//)
  try(r, str, 0, {}) {|e, md|
    if str.length == e
      md = md.dup
      md[:all] = 0...e
      return md 
    end
  }
  nil
end

def match_include(r, str)
  str = str.split(//)
  0.upto(str.length) {|b|
    try(r, str, b, {}) {|e, md|
      return b...e
    }
  }
  nil
end

def match_exact(r, str)
  str = str.split(//)
  try(r, str, 0, {}) {|e, md|
    if str.length == e
      return 0...e
    end
  }
  nil
end

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

def try(re, str, pos, md, &b)
  if re.respond_to? :to_str
    yield pos+1, md if str[pos] == re
  else
    case re[0]
    when :empset
      # nothing to do
    when :empstr
      yield pos, md
    when :string_start
      yield pos, md if pos == 0
    when :string_end
      yield pos, md if pos == str.length
    when :line_start
      yield pos, md if pos == 0 || (pos < str.length && str[pos-1] == "\n")
    when :line_end
      yield pos, md if pos == str.length || str[pos] == "\n"
    when :cat
      try_cat(re, str, pos, md, &b)
    when :alt
      try_alt(re, str, pos, md, &b)
    when :rep
      try_rep(re, str, pos, md, &b)
    when :rep_lazy
      try_rep_lazy(re, str, pos, md, &b)
    when :plus
      try_plus(re, str, pos, md, &b)
    when :plus_lazy
      try_plus_lazy(re, str, pos, md, &b)
    when :capture
      try_capture(re, str, pos, md, &b)
    when :opt
      try_opt(re, str, pos, md, &b)
    when :opt_lazy
      try_opt_lazy(re, str, pos, md, &b)
    when :times
      try_times(re, str, pos, md, &b)
    when :moretimes
      try_moretimes(re, str, pos, md, &b)
    when :anychar
      yield pos+1, md if pos < str.length
    else
      raise ArgumentError, "unexpected: #{re.inspect}"
    end
  end
end

def try_cat(re, str, pos, md, &b)
  if re.length == 1
    yield pos, md
  else
    re2 = [:cat] + re[2..-1]
    try(re[1], str, pos, md) {|pos2, md2|
      try_cat(re2, str, pos2, md2, &b)
    }
  end
end

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

def try_rep(re, str, pos, md, &b)
  try(re[1], str, pos, md) {|pos2, md2|
    try(re, str, pos2, md2, &b) if pos < pos2
  }
  yield pos, md
end

def try_rep_lazy(re, str, pos, md, &b)
  yield pos, md
  try(re[1], str, pos, md) {|pos2, md2|
    try(re, str, pos2, md2, &b) if pos < pos2
  }
end

def try_plus(re, str, pos, md, &b)
  try(re[1], str, pos, md) {|pos2, md2|
    try([:rep, re[1]], str, pos2, md2, &b)
  }
end

def try_opt(re, str, pos, md, &b)
  try(re[1], str, pos, md, &b)
  yield pos, md
end

def try_opt_lazy(re, str, pos, md, &b)
  yield pos, md
  try(re[1], str, pos, md, &b)
end

def try_times(re, str, pos, md, &b)
  m = re[1]
  n = re[2]
  r = re[3]
  if 0 < n
    try(r, str, pos, md) {|pos2, md2|
      try([:times, m-1, n-1, r], str, pos2, md2, &b)
    }
  end
  yield pos, md if m <= 0
end

def try_capture(re, str, pos, md, &b)
  name = re[1]
  r = re[2]
  try(r, str, pos, md) {|pos2, md2|
    md3 = md2.dup
    md3[name] = pos...pos2
    yield pos2, md3
  }
end

def rx_exact(r, str)
  str = str.split(//)
  try(r, str, 0, {}) {|e, md|
    return true if str.length == e
  }
  false
end

def rx_include(r, str)
  str = str.split(//)
  0.upto(str.length) {|b|
    try(r, str, b, {}) {|e, md|
      return true
    }
  }
  false
end

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

  def rx_results(re, str, pos)
    a = []
    try(re, str.split(//), pos, {}) {|pos2, md2| a << [pos2, md2] }
    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_anychar
      assert_equal([], rx_ends([:anychar], "", 0))
      assert_equal([1], rx_ends([:anychar], "a", 0))
      assert_equal([1], rx_ends([:anychar], "b", 0))
      assert_equal([1], rx_ends([:anychar], "cd", 0))
      assert_equal([], rx_ends([:anychar], "a", 1))
      assert_equal([2], rx_ends([:anychar], "cd", 1))
      assert_equal([2], rx_ends([:anychar], "cde", 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))
      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_capture
      assert_equal([[1, {:n=>0...1}]], rx_results([:capture, :n, "a"], "a", 0))
      assert_equal(
        [
          [2, {:n=>0...2}],
          [1, {:n=>0...1}],
          [0, {:n=>0...0}],
        ],
        rx_results([:capture, :n, [:rep, "a"]], "aab", 0))
      assert_equal(
        [
          [8, {:key=>0...3, :val=>4...8}],
          [7, {:key=>0...3, :val=>4...7}],
          [6, {:key=>0...3, :val=>4...6}],
          [5, {:key=>0...3, :val=>4...5}],
          [4, {:key=>0...3, :val=>4...4}],
        ],
        rx_results(
          [:cat, [:capture, :key, [:rep, "k"]],
            [:cat, "=",
              [:capture, :val, [:rep, "v"]]]],
          "kkk=vvvv", 0))
      assert_equal(
        [
          [15, {:key=>0...8, :val=>9...15}],
          [14, {:key=>0...8, :val=>9...14}],
          [13, {:key=>0...8, :val=>9...13}],
          [12, {:key=>0...8, :val=>9...12}],
          [11, {:key=>0...8, :val=>9...11}],
          [10, {:key=>0...8, :val=>9...10}],
          [9, {:key=>0...8, :val=>9...9}],
        ],
        rx_results(
          [:cat, [:capture, :key, [:rep, [:anychar]]],
            [:cat, "=",
              [:capture, :val, [:rep, [:anychar]]]]],
          "favorite=banana", 0))
      assert_equal(
        [[5, {:scheme=>0...4}]],
        rx_results(
          [:cat, [:capture, :scheme, [:rep, [:anychar]]], ":"],
          "http://www.example.org", 0))
      assert_equal(
        [[7, {:scheme=>0...6}]],
        rx_results(
          [:cat, [:capture, :scheme, [:rep, [:anychar]]], ":"],
          "mailto:foo@example.net", 0))
      assert_equal(
        [[8, {:field1=>0...3, :field2=>4...7}]],
        rx_results(
          [:cat, [:capture, :field1, [:rep, [:anychar]]],
            [:cat, ",",
              [:cat, [:capture, :field2, [:rep, [:anychar]]],
                ","]]],
          "foo,128,", 0))
      assert_equal(
        [[9, {:mname=>4...8}]],
        rx_results(
          [:cat, "d",
            [:cat, "e",
              [:cat, "f",
                [:cat, " ",
                  [:cat, [:capture, :mname, [:rep, [:anychar]]],
                    "("]]]]],
          "def plus(a,b) a + b end", 0))
      assert_equal(
        [[1, {:a=>0...1}]],
        rx_results(
          [:alt, [:capture, :a, "a"],
            [:alt, [:capture, :b, "b"],
              [:capture, :c, "c"]]],
          "a", 0))
      assert_equal(
        [[1, {:b=>0...1}]],
        rx_results(
          [:alt, [:capture, :a, "a"],
            [:alt, [:capture, :b, "b"],
              [:capture, :c, "c"]]],
          "b", 0))
      assert_equal(
        [[1, {:c=>0...1}]],
        rx_results(
          [:alt, [:capture, :a, "a"],
            [:alt, [:capture, :b, "b"],
              [:capture, :c, "c"]]],
          "c", 0))
      assert_equal(
        [[15, {:k1=>1...14,
               :k2=>2...3,
               :k3=>4...5,
               :k4=>6...13,
               :k5=>7...10,
               :k6=>8...9,
               :k7=>11...12}]],
        rx_results(
          [:cat,
            "a",
            [:cat,
              [:capture, :k1,
                [:cat,
                  "b",
                  [:cat,
                    [:capture, :k2, "c"],
                    [:cat,
                      "d",
                      [:cat,
                        [:capture, :k3, "e"],
                        [:cat,
                          "f",
                          [:cat,
                            [:capture, :k4,
                              [:cat,
                                "g",
                                [:cat,
                                  [:capture, :k5,
                                    [:cat,
                                      "h",
                                      [:cat,
                                        [:capture, :k6, "i"],
                                        "j"]]],
                                  [:cat,
                                    "k",
                                    [:cat,
                                      [:capture, :k7, "l"],
                                      "m"]]]]],
                            "n"]]]]]]],
              "o"]],
          "abcdefghijklmno", 0))
      assert_equal(
        [[5, {:scheme=>0...4}]],
        rx_results(
          [:cat,
            [:capture, :scheme,
              [:cat,
                [:alt, [:cat, "h", "t"], "f"],
                [:cat, "t", "p"]]],
            ":"],
          "http://www.example.org", 0))
      assert_equal(
        [[5, {:scheme=>0...4, :xxx=>0...2}]],
        rx_results(
          [:cat,
            [:capture, :scheme,
              [:cat,
                [:capture, :xxx, [:alt, [:cat, "h", "t"], "f"]],
                [:cat, "t", "p"]]],
            ":"],
          "http://www.example.org", 0))
      assert_equal(
        [
         [6, {:k1=>0...1, :k2=>1...3, :k3=>3...6}],
         [5, {:k1=>0...1, :k2=>1...3, :k3=>3...5}],
         [4, {:k1=>0...1, :k2=>1...3, :k3=>3...4}],
         [3, {:k1=>0...1, :k2=>1...3, :k3=>3...3}],
         [2, {:k1=>0...1, :k2=>1...2, :k3=>2...2}],
         [1, {:k1=>0...1, :k2=>1...1, :k3=>1...1}],
         [0, {:k1=>0...0, :k2=>0...0, :k3=>0...0}],
        ],
        rx_results(
          [:cat, [:capture, :k1, [:rep, "a"]],
            [:cat, [:capture, :k2, [:rep, "b"]],
              [:capture, :k3, [:rep, "c"]]]],
          "abbccc", 0))
      assert_equal(
        [
         [6, {:k1=>0...1, :k2=>1...3, :k3=>3...6}],
         [5, {:k1=>0...1, :k2=>1...3, :k3=>3...5}],
         [4, {:k1=>0...1, :k2=>1...3, :k3=>3...4}],
        ],
        rx_results(
          [:cat, [:capture, :k1, [:cat, "a", [:rep, "a"]]],
            [:cat, [:capture, :k2, [:cat, "b", [:rep, "b"]]],
              [:capture, :k3, [:cat, "c", [:rep, "c"]]]]],
          "abbccc", 0))
      assert_equal(
        [[2, {}]],
        rx_results(
          [:alt,
            [:cat, [:capture, :k, "a"], "b"],
            [:cat, "a", "c"]],
          "ac", 0))
      assert_equal(
        [[2, {:k=>0...1}], [2, {}]],
        rx_results(
          [:alt,
            [:cat, [:capture, :k, "a"], "x"],
            [:cat, "a", "x"]],
          "ax", 0))
    end

    def test_cat_multiarg_capture
      assert_equal(
        [
          [8, {:key=>0...3, :val=>4...8}],
          [7, {:key=>0...3, :val=>4...7}],
          [6, {:key=>0...3, :val=>4...6}],
          [5, {:key=>0...3, :val=>4...5}],
          [4, {:key=>0...3, :val=>4...4}]
        ],
        rx_results([:cat,
                     [:capture, :key, [:rep, [:anychar]]],
                     "=",
                     [:capture, :val, [:rep, [:anychar]]]],
                   "foo=hoge", 0))
      assert_equal(
        [
          [8, {:key=>0...3, :val=>4...8}],
          [7, {:key=>0...3, :val=>4...7}],
          [6, {:key=>0...3, :val=>4...6}],
          [5, {:key=>0...3, :val=>4...5}],
          [4, {:key=>0...3, :val=>4...4}],
        ],
        rx_results(
          [:cat,
            [:capture, :key, [:rep, "k"]],
            "=",
            [:capture, :val, [:rep, "v"]]],
          "kkk=vvvv", 0))
      assert_equal(
        [
          [15, {:key=>0...8, :val=>9...15}],
          [14, {:key=>0...8, :val=>9...14}],
          [13, {:key=>0...8, :val=>9...13}],
          [12, {:key=>0...8, :val=>9...12}],
          [11, {:key=>0...8, :val=>9...11}],
          [10, {:key=>0...8, :val=>9...10}],
          [9, {:key=>0...8, :val=>9...9}],
        ],
        rx_results(
          [:cat,
            [:capture, :key, [:rep, [:anychar]]],
            "=",
            [:capture, :val, [:rep, [:anychar]]]],
          "favorite=banana", 0))
      assert_equal(
        [[8, {:field1=>0...3, :field2=>4...7}]],
        rx_results(
          [:cat,
            [:capture, :field1, [:rep, [:anychar]]],
            ",",
            [:capture, :field2, [:rep, [:anychar]]],
            ","],
          "foo,128,", 0))
      assert_equal(
        [[9, {:mname=>4...8}]],
        rx_results(
          [:cat, "d", "e", "f", " ", [:capture, :mname, [:rep, [:anychar]]], "("],
          "def plus(a,b) a + b end", 0))
      assert_equal(
        [[15, {:k1=>1...14,
               :k2=>2...3,
               :k3=>4...5,
               :k4=>6...13,
               :k5=>7...10,
               :k6=>8...9,
               :k7=>11...12}]],
        rx_results(
          [:cat,
            "a",
            [:capture, :k1,
              [:cat,
                "b",
                [:capture, :k2, "c"],
                "d",
                [:capture, :k3, "e"],
                "f",
                [:capture, :k4,
                  [:cat,
                    "g",
                    [:capture, :k5,
                      [:cat,
                        "h",
                        [:capture, :k6, "i"],
                        "j"]],
                    "k",
                    [:capture, :k7, "l"],
                    "m"]],
                "n"]],
            "o"],
          "abcdefghijklmno", 0))
      assert_equal(
        [[5, {:scheme=>0...4}]],
        rx_results(
          [:cat,
            [:capture, :scheme,
              [:cat,
                [:alt, [:cat, "h", "t"], "f"],
                "t",
                "p"]],
            ":"],
          "http://www.example.org", 0))
      assert_equal(
        [[5, {:scheme=>0...4, :xxx=>0...2}]],
        rx_results(
          [:cat,
            [:capture, :scheme,
              [:cat,
                [:capture, :xxx, [:alt, [:cat, "h", "t"], "f"]],
                "t",
                "p"]],
            ":"],
          "http://www.example.org", 0))
      assert_equal(
        [
         [6, {:k1=>0...1, :k2=>1...3, :k3=>3...6}],
         [5, {:k1=>0...1, :k2=>1...3, :k3=>3...5}],
         [4, {:k1=>0...1, :k2=>1...3, :k3=>3...4}],
         [3, {:k1=>0...1, :k2=>1...3, :k3=>3...3}],
         [2, {:k1=>0...1, :k2=>1...2, :k3=>2...2}],
         [1, {:k1=>0...1, :k2=>1...1, :k3=>1...1}],
         [0, {:k1=>0...0, :k2=>0...0, :k3=>0...0}],
        ],
        rx_results(
          [:cat,
            [:capture, :k1, [:rep, "a"]],
            [:capture, :k2, [:rep, "b"]],
            [:capture, :k3, [:rep, "c"]]],
          "abbccc", 0))
      assert_equal(
        [
         [6, {:k1=>0...1, :k2=>1...3, :k3=>3...6}],
         [5, {:k1=>0...1, :k2=>1...3, :k3=>3...5}],
         [4, {:k1=>0...1, :k2=>1...3, :k3=>3...4}],
        ],
        rx_results(
          [:cat,
            [:capture, :k1, [:cat, "a", [:rep, "a"]]],
            [:capture, :k2, [:cat, "b", [:rep, "b"]]],
            [:capture, :k3, [:cat, "c", [:rep, "c"]]]],
          "abbccc", 0))
      assert_equal(
        [[6, {:k1=>0...1, :k2=>1...2, :k3=>2...3, :k4=>3...4, :k5=>4...5, :k6=>5...6}]],
        rx_results(
          [:cat,
            [:capture, :k1, [:alt, "a", "b"]],
            [:capture, :k2, [:alt, "a", "b"]],
            [:capture, :k3, [:alt, "a", "b"]],
            [:capture, :k4, [:alt, "a", "b"]],
            [:capture, :k5, [:alt, "a", "b"]],
            [:capture, :k6, [:alt, "a", "b"]]],
          "abbababbab", 0))
    end

    def test_alt_multiarg_capture
      assert_equal(
        [
          [3, {:foo=>0...3}],
          [2, {:foo=>0...2}],
          [1, {:foo=>0...1}],
          [0, {:foo=>0...0}],
          [0, {:bar=>0...0}],
          [0, {:baz=>0...0}],
        ],
        rx_results([:alt,
                     [:capture, :foo, [:rep, "a"]],
                     [:capture, :bar, [:rep, "b"]],
                     [:capture, :baz, [:rep, "c"]]],
                   "aaa", 0))
      assert_equal(
        [
          [0, {:foo=>0...0}],
          [3, {:bar=>0...3}],
          [2, {:bar=>0...2}],
          [1, {:bar=>0...1}],
          [0, {:bar=>0...0}],
          [0, {:baz=>0...0}],
        ],
        rx_results([:alt,
                     [:capture, :foo, [:rep, "a"]],
                     [:capture, :bar, [:rep, "b"]],
                     [:capture, :baz, [:rep, "c"]]],
                   "bbb", 0))
      assert_equal(
        [[1, {:a=>0...1}]],
        rx_results(
          [:alt,
            [:capture, :a, "a"],
            [:capture, :b, "b"],
            [:capture, :c, "c"]],
          "a", 0))
      assert_equal(
        [[1, {:b=>0...1}]],
        rx_results(
          [:alt,
            [:capture, :a, "a"],
            [:capture, :b, "b"],
            [:capture, :c, "c"]],
          "b", 0))
      assert_equal(
        [[1, {:c=>0...1}]],
        rx_results(
          [:alt,
            [:capture, :a, "a"],
            [:capture, :b, "b"],
            [:capture, :c, "c"]],
          "c", 0))
    end

    def test_string_start
      assert_equal(0...0, match_include([:string_start], "abc"))
      assert_equal(0...0, match_include([:string_start], ""))
      assert_equal(0...1, match_include([:cat, [:string_start], "a"], "abc"))
      assert_equal(nil, match_include([:cat, [:string_start], "b"], "abc"))
    end

    def test_string_end
      assert_equal(3...3, match_include([:string_end], "abc"))
      assert_equal(0...0, match_include([:string_end], ""))
      assert_equal(2...3, match_include([:cat, "c", [:string_end]], "abc"))
      assert_equal(nil, match_include([:cat, "b", [:string_end]], "abc"))
    end

    def test_line_start
      assert_equal(0...0, match_include([:line_start], "abc"))
      assert_equal([2,0],
                   rx_ends(
                     [:cat, [:rep, [:anychar]], [:line_start]],
                     "a\nb\n", 0))
    end

    def test_line_end
      assert_equal(3...3, match_include([:line_end], "abc"))
      assert_equal([4,3,1],
                   rx_ends(
                     [:cat, [:rep, [:anychar]], [:line_end]],
                     "a\nb\n", 0))
    end

    def test_opt
      assert_equal([1,0], rx_ends([:opt, "a"], "a", 0))
      assert_equal([0], rx_ends([:opt, "a"], "b", 0))
      assert_equal(0...9, match_exact([:cat, "b", "e", "h", "a", "v", "i", "o", [:opt, "u"], "r"], "behaviour"))
      assert_equal(0...8, match_exact([:cat, "b", "e", "h", "a", "v", "i", "o", [:opt, "u"], "r"], "behavior"))
    end

    def test_opt
      assert_equal([0,1], rx_ends([:opt_lazy, "a"], "aa", 0))
      assert_equal([0], rx_ends([:opt_lazy, "a"], "b", 0))
    end

    def test_plus
      assert_equal([3,2,1], rx_ends([:plus, "a"], "aaa", 0))
    end

    def test_plus_lazy
      assert_equal([], rx_ends([:plus_lazy, "a"], "", 0))
      assert_equal([1], rx_ends([:plus_lazy, "a"], "a", 0))
      assert_equal([1], rx_ends([:plus_lazy, "a"], "abc", 0))
      assert_equal([], rx_ends([:plus_lazy, "a"], "abc", 1))
      assert_equal([2], rx_ends([:plus_lazy, "a"], "cat", 1))
      assert_equal([1,2,3], rx_ends([:plus_lazy, "a"], "aaa", 0))
      assert_equal([2,4,6], rx_ends([:plus_lazy, [:cat, "a", "a"]], "aaaaaaa", 0))
      assert_equal([2], rx_ends([:plus_lazy, [:cat, "b", "a"]], "banana", 0))
      assert_equal([2,3], rx_ends([:plus_lazy, "p"], "apple", 1))
      assert_equal([4], rx_ends([:cat, [:plus_lazy, "p"], "l"], "apple", 1))
      assert_equal([2,4,6], rx_ends([:plus_lazy, [:cat, [:alt, "b", "n"], "a"]], "banana", 0))
      assert_equal([1,2,6,5,4,3], rx_ends([:cat, [:plus_lazy, "a"], [:rep, "b"]], "aaabbb", 0))
    end

    def test_rep_lazy
      assert_equal([0,1,2,3], rx_ends([:rep_lazy, "a"], "aaa", 0))
    end

    def test_times
      assert_equal([], rx_ends([:times, 3, 5, "a"], "", 0))
      assert_equal([], rx_ends([:times, 3, 5, "a"], "a", 0))
      assert_equal([], rx_ends([:times, 3, 5, "a"], "aa", 0))
      assert_equal([3], rx_ends([:times, 3, 5, "a"], "aaa", 0))
      assert_equal([4,3], rx_ends([:times, 3, 5, "a"], "aaaa", 0))
      assert_equal([5,4,3], rx_ends([:times, 3, 5, "a"], "aaaaa", 0))
      assert_equal([5,4,3], rx_ends([:times, 3, 5, "a"], "aaaaaa", 0))
      assert_equal([5,4,3], rx_ends([:times, 3, 5, "a"], "aaaaaaa", 0))
      assert_equal([5,4,3], rx_ends([:times, 3, 5, "a"], "aaaaaaaa", 0))
    end

    def test_moretimes
      assert_equal([], rx_ends([:moretimes,                 3, "a"], "", 0))
      assert_equal([], rx_ends([:moretimes,                 3, "a"], "a", 0))
      assert_equal([], rx_ends([:moretimes,                 3, "a"], "aa", 0))
      assert_equal([3], rx_ends([:moretimes,                3, "a"], "aaa", 0))
      assert_equal([4,3], rx_ends([:moretimes,              3, "a"], "aaaa", 0))
      assert_equal([5,4,3], rx_ends([:moretimes,            3, "a"], "aaaaa", 0))
      assert_equal([6,5,4,3], rx_ends([:moretimes,          3, "a"], "aaaaaa", 0))
      assert_equal([7,6,5,4,3], rx_ends([:moretimes,        3, "a"], "aaaaaaa", 0))
      assert_equal([8,7,6,5,4,3], rx_ends([:moretimes,      3, "a"], "aaaaaaaa", 0))
      assert_equal([9,8,7,6,5,4,3], rx_ends([:moretimes,    3, "a"], "aaaaaaaaa", 0))
      assert_equal([10,9,8,7,6,5,4,3], rx_ends([:moretimes, 3, "a"], "aaaaaaaaaa", 0))
      assert_equal([6,4,2], rx_ends([:moretimes, 0, [:cat, "n", "a"]], "banana", 2))
      assert_equal([], rx_ends([:moretimes, 3, [:cat, "n", "a"]], "banana", 2))
      assert_equal([6], rx_ends([:moretimes, 2, [:cat, "n", "a"]], "banana", 2))
      assert_equal([5,3,1], rx_ends([:moretimes, 0, [:cat, "a", "n"]], "banana", 1))
      assert_equal([6,4,2], rx_ends([:cat, [:moretimes, 0, [:cat, "a", "n"]], "a"], "banana", 1))
      assert_equal([6], rx_ends([:cat, [:moretimes, 0, [:cat, "a", "n"]], "a", [:string_end]], "banana", 1))
    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

    def test_cap_include
      assert_equal({:all=>0...0}, cap_include([:empstr], ""))
      assert_equal(nil, cap_include("z", ""))
      assert_equal({:all=>3...4}, cap_include("c", "avocado"))
      assert_equal({:all=>4...6}, cap_include([:cat, "a", "p"], "pineapple"))
      assert_equal({:all=>0...1}, cap_include([:cat, [:rep, "a"], "p"], "pineapple"))
      assert_equal({:all=>0...1, :a=>0...0}, cap_include([:cat, [:capture, :a, [:rep, "a"]], "p"], "pineapple"))
      assert_equal({:all=>4...7}, cap_include([:cat, "a", [:rep, "p"]], "pineapple"))
      assert_equal({:all=>0...14, :key=>0...8, :val=>9...14},
                   cap_include([:cat, [:capture, :key, [:rep, [:anychar]]],
                                      "=",
                                      [:capture, :val, [:rep, [:anychar]]]],
                                      "favorite=mango"))
    end

    def test_cap_exact
      assert_equal({:all=>0...4}, cap_exact([:rep, [:anychar]], "kiwi"))
      assert_equal({:all=>0...9, :ap=>4...9},
                   cap_include([:cat, "p", "i", "n", "e",
                                 [:capture, :ap, [:cat, "a", "p", "p", "l", "e"]]],
                               "pineapple"))
    end

    def test_match_include
      assert_equal(3...5, match_include([:cat, "n", "g"], "orange"))
      assert_equal(1...4, match_include([:cat, "e", [:rep, "r"]], "berry"))
      assert_equal(0...1, match_include([:anychar], "z"))
      assert_equal(nil, match_include([:alt, "b", "c"], "a"))
      assert_equal(0...1, match_include([:alt, "b", "c"], "b"))
      assert_equal(0...1, match_include([:alt, "b", "c"], "c"))
      assert_equal(4...9, match_include([:cat, "b", "e", "r", "r", "y"], "blueberry"))
      assert_equal(4...9, match_include([:cat, "b", "e", "r", "r", "y"], "raspberry"))
      assert_equal(5...10, match_include([:cat, "b", "e", "r", "r", "y"], "strawberry"))
      assert_equal(3...10, match_include([:cat, "a", [:rep, [:anychar]]], "strawberry"))
      assert_equal(0...0, match_include([:string_start], "abc"))
    end

    def test_match_exact
      %w[blueberry raspberry strawberry].each {|w|
        assert_equal(0...w.length,
          match_exact([:cat, [:alt, [:cat, "b", "l", "u", "e"],
                                    [:cat, "r", "a", "s", "p"],
                                    [:cat, "s", "t", "r", "a", "w"]],
                             "b", "e", "r", "r", "y"],
                      w))
      }
    end
  end
end