aboutsummaryrefslogtreecommitdiff
path: root/libgo/go/index
diff options
context:
space:
mode:
authorIan Lance Taylor <iant@google.com>2011-01-21 18:19:03 +0000
committerIan Lance Taylor <ian@gcc.gnu.org>2011-01-21 18:19:03 +0000
commitff5f50c52c421d75940ef9392211e3ab24d71332 (patch)
tree27d8768fb1d25696d3c40b42535eb5e073c278da /libgo/go/index
parentd6ed1c8903e728f4233122554bab5910853338bd (diff)
downloadgcc-ff5f50c52c421d75940ef9392211e3ab24d71332.zip
gcc-ff5f50c52c421d75940ef9392211e3ab24d71332.tar.gz
gcc-ff5f50c52c421d75940ef9392211e3ab24d71332.tar.bz2
Remove the types float and complex.
Update to current version of Go library. Update testsuite for removed types. * go-lang.c (go_langhook_init): Omit float_type_size when calling go_create_gogo. * go-c.h: Update declaration of go_create_gogo. From-SVN: r169098
Diffstat (limited to 'libgo/go/index')
-rw-r--r--libgo/go/index/suffixarray/qsufsort.go164
-rw-r--r--libgo/go/index/suffixarray/suffixarray.go167
-rw-r--r--libgo/go/index/suffixarray/suffixarray_test.go151
3 files changed, 395 insertions, 87 deletions
diff --git a/libgo/go/index/suffixarray/qsufsort.go b/libgo/go/index/suffixarray/qsufsort.go
new file mode 100644
index 0000000..0e6894a
--- /dev/null
+++ b/libgo/go/index/suffixarray/qsufsort.go
@@ -0,0 +1,164 @@
+// Copyright 2011 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This algorithm is based on "Faster Suffix Sorting"
+// by N. Jesper Larsson and Kunihiko Sadakane
+// paper: http://www.larsson.dogma.net/ssrev-tr.pdf
+// code: http://www.larsson.dogma.net/qsufsort.c
+
+// This algorithm computes the suffix array sa by computing its inverse.
+// Consecutive groups of suffixes in sa are labeled as sorted groups or
+// unsorted groups. For a given pass of the sorter, all suffixes are ordered
+// up to their first h characters, and sa is h-ordered. Suffixes in their
+// final positions and unambiguouly sorted in h-order are in a sorted group.
+// Consecutive groups of suffixes with identical first h characters are an
+// unsorted group. In each pass of the algorithm, unsorted groups are sorted
+// according to the group number of their following suffix.
+
+// In the implementation, if sa[i] is negative, it indicates that i is
+// the first element of a sorted group of length -sa[i], and can be skipped.
+// An unsorted group sa[i:k] is given the group number of the index of its
+// last element, k-1. The group numbers are stored in the inverse slice (inv),
+// and when all groups are sorted, this slice is the inverse suffix array.
+
+package suffixarray
+
+import "sort"
+
+func qsufsort(data []byte) []int {
+ // initial sorting by first byte of suffix
+ sa := sortedByFirstByte(data)
+ if len(sa) < 2 {
+ return sa
+ }
+ // initialize the group lookup table
+ // this becomes the inverse of the suffix array when all groups are sorted
+ inv := initGroups(sa, data)
+
+ // the index starts 1-ordered
+ sufSortable := &suffixSortable{sa, inv, 1}
+
+ for sa[0] > -len(sa) { // until all suffixes are one big sorted group
+ // The suffixes are h-ordered, make them 2*h-ordered
+ pi := 0 // pi is first position of first group
+ sl := 0 // sl is negated length of sorted groups
+ for pi < len(sa) {
+ if s := sa[pi]; s < 0 { // if pi starts sorted group
+ pi -= s // skip over sorted group
+ sl += s // add negated length to sl
+ } else { // if pi starts unsorted group
+ if sl != 0 {
+ sa[pi+sl] = sl // combine sorted groups before pi
+ sl = 0
+ }
+ pk := inv[s] + 1 // pk-1 is last position of unsorted group
+ sufSortable.sa = sa[pi:pk]
+ sort.Sort(sufSortable)
+ sufSortable.updateGroups(pi)
+ pi = pk // next group
+ }
+ }
+ if sl != 0 { // if the array ends with a sorted group
+ sa[pi+sl] = sl // combine sorted groups at end of sa
+ }
+
+ sufSortable.h *= 2 // double sorted depth
+ }
+
+ for i := range sa { // reconstruct suffix array from inverse
+ sa[inv[i]] = i
+ }
+ return sa
+}
+
+
+func sortedByFirstByte(data []byte) []int {
+ // total byte counts
+ var count [256]int
+ for _, b := range data {
+ count[b]++
+ }
+ // make count[b] equal index of first occurence of b in sorted array
+ sum := 0
+ for b := range count {
+ count[b], sum = sum, count[b]+sum
+ }
+ // iterate through bytes, placing index into the correct spot in sa
+ sa := make([]int, len(data))
+ for i, b := range data {
+ sa[count[b]] = i
+ count[b]++
+ }
+ return sa
+}
+
+
+func initGroups(sa []int, data []byte) []int {
+ // label contiguous same-letter groups with the same group number
+ inv := make([]int, len(data))
+ prevGroup := len(sa) - 1
+ groupByte := data[sa[prevGroup]]
+ for i := len(sa) - 1; i >= 0; i-- {
+ if b := data[sa[i]]; b < groupByte {
+ if prevGroup == i+1 {
+ sa[i+1] = -1
+ }
+ groupByte = b
+ prevGroup = i
+ }
+ inv[sa[i]] = prevGroup
+ if prevGroup == 0 {
+ sa[0] = -1
+ }
+ }
+ // Separate out the final suffix to the start of its group.
+ // This is necessary to ensure the suffix "a" is before "aba"
+ // when using a potentially unstable sort.
+ lastByte := data[len(data)-1]
+ s := -1
+ for i := range sa {
+ if sa[i] >= 0 {
+ if data[sa[i]] == lastByte && s == -1 {
+ s = i
+ }
+ if sa[i] == len(sa)-1 {
+ sa[i], sa[s] = sa[s], sa[i]
+ inv[sa[s]] = s
+ sa[s] = -1 // mark it as an isolated sorted group
+ break
+ }
+ }
+ }
+ return inv
+}
+
+
+type suffixSortable struct {
+ sa []int
+ inv []int
+ h int
+}
+
+func (x *suffixSortable) Len() int { return len(x.sa) }
+func (x *suffixSortable) Less(i, j int) bool { return x.inv[x.sa[i]+x.h] < x.inv[x.sa[j]+x.h] }
+func (x *suffixSortable) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
+
+
+func (x *suffixSortable) updateGroups(offset int) {
+ prev := len(x.sa) - 1
+ group := x.inv[x.sa[prev]+x.h]
+ for i := prev; i >= 0; i-- {
+ if g := x.inv[x.sa[i]+x.h]; g < group {
+ if prev == i+1 { // previous group had size 1 and is thus sorted
+ x.sa[i+1] = -1
+ }
+ group = g
+ prev = i
+ }
+ x.inv[x.sa[i]] = prev + offset
+ if prev == 0 { // first group has size 1 and is thus sorted
+ x.sa[0] = -1
+ }
+ }
+}
diff --git a/libgo/go/index/suffixarray/suffixarray.go b/libgo/go/index/suffixarray/suffixarray.go
index 0a17472..628e000 100644
--- a/libgo/go/index/suffixarray/suffixarray.go
+++ b/libgo/go/index/suffixarray/suffixarray.go
@@ -18,15 +18,10 @@ package suffixarray
import (
"bytes"
- "container/vector"
+ "regexp"
"sort"
)
-// BUG(gri): For larger data (10MB) which contains very long (say 100000)
-// contiguous sequences of identical bytes, index creation time will be extremely slow.
-
-// TODO(gri): Use a more sophisticated algorithm to create the suffix array.
-
// Index implements a suffix array for fast substring search.
type Index struct {
@@ -36,16 +31,17 @@ type Index struct {
// New creates a new Index for data.
-// Index creation time is approximately O(N*log(N)) for N = len(data).
-//
+// Index creation time is O(N*log(N)) for N = len(data).
func New(data []byte) *Index {
- sa := make([]int, len(data))
- for i, _ := range sa {
- sa[i] = i
- }
- x := &Index{data, sa}
- sort.Sort((*index)(x))
- return x
+ return &Index{data, qsufsort(data)}
+}
+
+
+// Bytes returns the data over which the index was created.
+// It must not be modified.
+//
+func (x *Index) Bytes() []byte {
+ return x.data
}
@@ -54,21 +50,8 @@ func (x *Index) at(i int) []byte {
}
-// Binary search according to "A Method of Programming", E.W. Dijkstra.
func (x *Index) search(s []byte) int {
- i, j := 0, len(x.sa)
- // i < j for non-empty x
- for i+1 < j {
- // 0 <= i < j <= len(x.sa) && (x.at(i) <= s < x.at(j) || (s is not in x))
- h := i + (j-i)/2 // i < h < j
- if bytes.Compare(x.at(h), s) <= 0 {
- i = h
- } else { // s < x.at(h)
- j = h
- }
- }
- // i+1 == j for non-empty x
- return i
+ return sort.Search(len(x.sa), func(i int) bool { return bytes.Compare(x.at(i), s) >= 0 })
}
@@ -78,34 +61,122 @@ func (x *Index) search(s []byte) int {
// Lookup time is O((log(N) + len(result))*len(s)) where N is the
// size of the indexed data.
//
-func (x *Index) Lookup(s []byte, n int) []int {
- var res vector.IntVector
-
+func (x *Index) Lookup(s []byte, n int) (result []int) {
if len(s) > 0 && n != 0 {
// find matching suffix index i
i := x.search(s)
- // x.at(i) <= s < x.at(i+1)
-
- // ignore the first suffix if it is < s
- if i < len(x.sa) && bytes.Compare(x.at(i), s) < 0 {
- i++
- }
+ // x.at(i-1) < s <= x.at(i)
// collect the following suffixes with matching prefixes
- for (n < 0 || len(res) < n) && i < len(x.sa) && bytes.HasPrefix(x.at(i), s) {
- res.Push(x.sa[i])
+ for (n < 0 || len(result) < n) && i < len(x.sa) && bytes.HasPrefix(x.at(i), s) {
+ result = append(result, x.sa[i])
i++
}
}
-
- return res
+ return
}
-// index is used to hide the sort.Interface
-type index Index
+// FindAllIndex returns a sorted list of non-overlapping matches of the
+// regular expression r, where a match is a pair of indices specifying
+// the matched slice of x.Bytes(). If n < 0, all matches are returned
+// in successive order. Otherwise, at most n matches are returned and
+// they may not be successive. The result is nil if there are no matches,
+// or if n == 0.
+//
+func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int) {
+ // a non-empty literal prefix is used to determine possible
+ // match start indices with Lookup
+ prefix, complete := r.LiteralPrefix()
+ lit := []byte(prefix)
+
+ // worst-case scenario: no literal prefix
+ if prefix == "" {
+ return r.FindAllIndex(x.data, n)
+ }
+
+ // if regexp is a literal just use Lookup and convert its
+ // result into match pairs
+ if complete {
+ // Lookup returns indices that may belong to overlapping matches.
+ // After eliminating them, we may end up with fewer than n matches.
+ // If we don't have enough at the end, redo the search with an
+ // increased value n1, but only if Lookup returned all the requested
+ // indices in the first place (if it returned fewer than that then
+ // there cannot be more).
+ for n1 := n; ; n1 += 2 * (n - len(result)) /* overflow ok */ {
+ indices := x.Lookup(lit, n1)
+ if len(indices) == 0 {
+ return
+ }
+ sort.SortInts(indices)
+ pairs := make([]int, 2*len(indices))
+ result = make([][]int, len(indices))
+ count := 0
+ prev := 0
+ for _, i := range indices {
+ if count == n {
+ break
+ }
+ // ignore indices leading to overlapping matches
+ if prev <= i {
+ j := 2 * count
+ pairs[j+0] = i
+ pairs[j+1] = i + len(lit)
+ result[count] = pairs[j : j+2]
+ count++
+ prev = i + len(lit)
+ }
+ }
+ result = result[0:count]
+ if len(result) >= n || len(indices) != n1 {
+ // found all matches or there's no chance to find more
+ // (n and n1 can be negative)
+ break
+ }
+ }
+ if len(result) == 0 {
+ result = nil
+ }
+ return
+ }
-func (x *index) Len() int { return len(x.sa) }
-func (x *index) Less(i, j int) bool { return bytes.Compare(x.at(i), x.at(j)) < 0 }
-func (x *index) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
-func (a *index) at(i int) []byte { return a.data[a.sa[i]:] }
+ // regexp has a non-empty literal prefix; Lookup(lit) computes
+ // the indices of possible complete matches; use these as starting
+ // points for anchored searches
+ // (regexp "^" matches beginning of input, not beginning of line)
+ r = regexp.MustCompile("^" + r.String()) // compiles because r compiled
+
+ // same comment about Lookup applies here as in the loop above
+ for n1 := n; ; n1 += 2 * (n - len(result)) /* overflow ok */ {
+ indices := x.Lookup(lit, n1)
+ if len(indices) == 0 {
+ return
+ }
+ sort.SortInts(indices)
+ result = result[0:0]
+ prev := 0
+ for _, i := range indices {
+ if len(result) == n {
+ break
+ }
+ m := r.FindIndex(x.data[i:]) // anchored search - will not run off
+ // ignore indices leading to overlapping matches
+ if m != nil && prev <= i {
+ m[0] = i // correct m
+ m[1] += i
+ result = append(result, m)
+ prev = m[1]
+ }
+ }
+ if len(result) >= n || len(indices) != n1 {
+ // found all matches or there's no chance to find more
+ // (n and n1 can be negative)
+ break
+ }
+ }
+ if len(result) == 0 {
+ result = nil
+ }
+ return
+}
diff --git a/libgo/go/index/suffixarray/suffixarray_test.go b/libgo/go/index/suffixarray/suffixarray_test.go
index 8280750..b3486a9 100644
--- a/libgo/go/index/suffixarray/suffixarray_test.go
+++ b/libgo/go/index/suffixarray/suffixarray_test.go
@@ -5,7 +5,9 @@
package suffixarray
import (
+ "bytes"
"container/vector"
+ "regexp"
"sort"
"strings"
"testing"
@@ -13,9 +15,9 @@ import (
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 +28,9 @@ var testCases = []testCase{
[]string{
"",
"foo",
+ "(foo)",
+ ".*",
+ "a*",
},
},
@@ -45,6 +50,12 @@ var testCases = []testCase{
"aaaaaaaaa",
"aaaaaaaaaa",
"aaaaaaaaaaa", // 11 a's
+ ".",
+ ".*",
+ "a+",
+ "aa+",
+ "aaaa[b]?",
+ "aaa*",
},
},
@@ -58,6 +69,9 @@ var testCases = []testCase{
"ab",
"bc",
"abc",
+ "a.c",
+ "a(b|c)",
+ "abc?",
},
},
@@ -70,6 +84,7 @@ var testCases = []testCase{
"rab",
"arab",
"barbar",
+ "bara?bar",
},
},
@@ -81,16 +96,17 @@ var testCases = []testCase{
"the time",
"to come the aid",
"is the time for all good men to come to the aid of their",
+ "to (come|the)?",
},
},
}
-// find all occurences of s in source; report at most n occurences
+// find all occurrences of s in source; report at most n occurences
func find(src, s string, n int) []int {
var res vector.IntVector
if s != "" && n != 0 {
- // find at most n occurences of s in src
+ // find at most n occurrences of s in src
for i := -1; n < 0 || len(res) < n; {
j := strings.Index(src[i+1:], s)
if j < 0 {
@@ -104,58 +120,115 @@ func find(src, s string, n int) []int {
}
-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
+ // 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)
+ }
+ }
- // 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)
}
}
}
+// index is used to hide the sort.Interface
+type index Index
+
+func (x *index) Len() int { return len(x.sa) }
+func (x *index) Less(i, j int) bool { return bytes.Compare(x.at(i), x.at(j)) < 0 }
+func (x *index) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
+func (a *index) at(i int) []byte { return a.data[a.sa[i]:] }
+
+
+func testConstruction(t *testing.T, tc *testCase, x *Index) {
+ if !sort.IsSorted((*index)(x)) {
+ t.Errorf("testConstruction failed %s", tc.name)
+ }
+}
+
+
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)
+ testConstruction(t, &tc, x)
+ 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)
}
}