suffixarray: implememted FindAllIndex regexp search
Implementation uses fast suffixarray lookup to find
initial matches if the regular expression starts with
a suitable prefix without meta characters.
R=r, rsc
CC=golang-dev
https://golang.org/cl/3720042
diff --git a/src/pkg/index/suffixarray/suffixarray_test.go b/src/pkg/index/suffixarray/suffixarray_test.go
index 8280750..cc252a9 100644
--- a/src/pkg/index/suffixarray/suffixarray_test.go
+++ b/src/pkg/index/suffixarray/suffixarray_test.go
@@ -6,6 +6,7 @@
import (
"container/vector"
+ "regexp"
"sort"
"strings"
"testing"
@@ -13,9 +14,9 @@
type testCase struct {
- name string // name of test case
- source string // source to index
- lookups []string // strings to lookup
+ name string // name of test case
+ source string // source to index
+ patterns []string // patterns to lookup
}
@@ -26,6 +27,9 @@
[]string{
"",
"foo",
+ "(foo)",
+ ".*",
+ "a*",
},
},
@@ -45,6 +49,12 @@
"aaaaaaaaa",
"aaaaaaaaaa",
"aaaaaaaaaaa", // 11 a's
+ ".",
+ ".*",
+ "a+",
+ "aa+",
+ "aaaa[b]?",
+ "aaa*",
},
},
@@ -58,6 +68,9 @@
"ab",
"bc",
"abc",
+ "a.c",
+ "a(b|c)",
+ "abc?",
},
},
@@ -70,6 +83,7 @@
"rab",
"arab",
"barbar",
+ "bara?bar",
},
},
@@ -81,6 +95,7 @@
"the time",
"to come the aid",
"is the time for all good men to come to the aid of their",
+ "to (come|the)?",
},
},
}
@@ -104,47 +119,86 @@
}
-func testLookups(t *testing.T, src string, x *Index, tc *testCase, n int) {
- for _, s := range tc.lookups {
- res := x.Lookup([]byte(s), n)
- exp := find(tc.source, s, n)
+func testLookup(t *testing.T, tc *testCase, x *Index, s string, n int) {
+ res := x.Lookup([]byte(s), n)
+ exp := find(tc.source, s, n)
- // check that the lengths match
- if len(res) != len(exp) {
- t.Errorf("test %q, lookup %q (n = %d): expected %d results; got %d", tc.name, s, n, len(exp), len(res))
+ // check that the lengths match
+ if len(res) != len(exp) {
+ t.Errorf("test %q, lookup %q (n = %d): expected %d results; got %d", tc.name, s, n, len(exp), len(res))
+ }
+
+ // if n >= 0 the number of results is limited --- unless n >= all results,
+ // we may obtain different positions from the Index and from find (because
+ // Index may not find the results in the same order as find) => in general
+ // we cannot simply check that the res and exp lists are equal
+
+ // check that each result is in fact a correct match and there are no duplicates
+ sort.SortInts(res)
+ for i, r := range res {
+ if r < 0 || len(tc.source) <= r {
+ t.Errorf("test %q, lookup %q, result %d (n = %d): index %d out of range [0, %d[", tc.name, s, i, n, r, len(tc.source))
+ } else if !strings.HasPrefix(tc.source[r:], s) {
+ t.Errorf("test %q, lookup %q, result %d (n = %d): index %d not a match", tc.name, s, i, n, r)
}
+ if i > 0 && res[i-1] == r {
+ t.Errorf("test %q, lookup %q, result %d (n = %d): found duplicate index %d", tc.name, s, i, n, r)
+ }
+ }
- // if n >= 0 the number of results is limited --- unless n >= all results,
- // we may obtain different positions from the Index and from find (because
- // Index may not find the results in the same order as find) => in general
- // we cannot simply check that the res and exp lists are equal
-
- // check that there are no duplicates
- sort.SortInts(res)
+ if n < 0 {
+ // all results computed - sorted res and exp must be equal
for i, r := range res {
- if i > 0 && res[i-1] == r {
- t.Errorf("test %q, lookup %q, result %d (n = %d): found duplicate index %d", tc.name, s, i, n, r)
+ e := exp[i]
+ if r != e {
+ t.Errorf("test %q, lookup %q, result %d: expected index %d; got %d", tc.name, s, i, e, r)
}
}
+ }
+}
- // check that each result is in fact a correct match
+
+func testFindAllIndex(t *testing.T, tc *testCase, x *Index, rx *regexp.Regexp, n int) {
+ res := x.FindAllIndex(rx, n)
+ exp := rx.FindAllStringIndex(tc.source, n)
+
+ // check that the lengths match
+ if len(res) != len(exp) {
+ t.Errorf("test %q, FindAllIndex %q (n = %d): expected %d results; got %d", tc.name, rx, n, len(exp), len(res))
+ }
+
+ // if n >= 0 the number of results is limited --- unless n >= all results,
+ // we may obtain different positions from the Index and from regexp (because
+ // Index may not find the results in the same order as regexp) => in general
+ // we cannot simply check that the res and exp lists are equal
+
+ // check that each result is in fact a correct match and the result is sorted
+ for i, r := range res {
+ if r[0] < 0 || r[0] > r[1] || len(tc.source) < r[1] {
+ t.Errorf("test %q, FindAllIndex %q, result %d (n == %d): illegal match [%d, %d]", tc.name, rx, i, n, r[0], r[1])
+ } else if !rx.MatchString(tc.source[r[0]:r[1]]) {
+ t.Errorf("test %q, FindAllIndex %q, result %d (n = %d): [%d, %d] not a match", tc.name, rx, i, n, r[0], r[1])
+ }
+ }
+
+ if n < 0 {
+ // all results computed - sorted res and exp must be equal
for i, r := range res {
- if r < 0 || len(src) <= r {
- t.Errorf("test %q, lookup %q, result %d (n = %d): index %d out of range [0, %d[", tc.name, s, i, n, r, len(src))
- } else if !strings.HasPrefix(src[r:], s) {
- t.Errorf("test %q, lookup %q, result %d (n = %d): index %d not a match", tc.name, s, i, n, r)
+ e := exp[i]
+ if r[0] != e[0] || r[1] != e[1] {
+ t.Errorf("test %q, FindAllIndex %q, result %d: expected match [%d, %d]; got [%d, %d]",
+ tc.name, rx, i, e[0], e[1], r[0], r[1])
}
}
+ }
+}
- if n < 0 {
- // all results computed - sorted res and exp must be equal
- for i, r := range res {
- e := exp[i]
- if r != e {
- t.Errorf("test %q, lookup %q, result %d: expected index %d; got %d", tc.name, s, i, e, r)
- continue
- }
- }
+
+func testLookups(t *testing.T, tc *testCase, x *Index, n int) {
+ for _, pat := range tc.patterns {
+ testLookup(t, tc, x, pat, n)
+ if rx, err := regexp.Compile(pat); err == nil {
+ testFindAllIndex(t, tc, x, rx, n)
}
}
}
@@ -153,9 +207,10 @@
func TestIndex(t *testing.T) {
for _, tc := range testCases {
x := New([]byte(tc.source))
- testLookups(t, tc.source, x, &tc, 0)
- testLookups(t, tc.source, x, &tc, 1)
- testLookups(t, tc.source, x, &tc, 10)
- testLookups(t, tc.source, x, &tc, -1)
+ testLookups(t, &tc, x, 0)
+ testLookups(t, &tc, x, 1)
+ testLookups(t, &tc, x, 10)
+ testLookups(t, &tc, x, 2e9)
+ testLookups(t, &tc, x, -1)
}
}
