From ff5f50c52c421d75940ef9392211e3ab24d71332 Mon Sep 17 00:00:00 2001
From: Ian Lance Taylor <iant@google.com>
Date: Fri, 21 Jan 2011 18:19:03 +0000
Subject: 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
---
 libgo/go/index/suffixarray/qsufsort.go         | 164 ++++++++++++++++++++++++
 libgo/go/index/suffixarray/suffixarray.go      | 167 ++++++++++++++++++-------
 libgo/go/index/suffixarray/suffixarray_test.go | 151 ++++++++++++++++------
 3 files changed, 395 insertions(+), 87 deletions(-)
 create mode 100644 libgo/go/index/suffixarray/qsufsort.go

(limited to 'libgo/go/index')

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)
 	}
 }
-- 
cgit v1.1