Upgrade blevesearch to v0.8.1 (#9177)

For #1441

https://github.com/blevesearch/bleve/commit/a91b427b59b893f112021841ba7370d285f8426f

11 files changed, 114 insertions, 33 deletions

diff --git a/vendor/github.com/couchbase/vellum/fst_iterator.go b/vendor/github.com/couchbase/vellum/fst_iterator.go
index eb731395b2..d04ad63fb1 100644
--- a/vendor/github.com/couchbase/vellum/fst_iterator.go
+++ b/vendor/github.com/couchbase/vellum/fst_iterator.go
@@ -18,7 +18,7 @@ import (
 	"bytes"
 )
 
-// Iterator represents a means of visity key/value pairs in order.
+// Iterator represents a means of visiting key/value pairs in order.
 type Iterator interface {
 
 	// Current() returns the key/value pair currently pointed to.
@@ -186,20 +186,29 @@ func (i *FSTIterator) Next() error {
 }
 
 func (i *FSTIterator) next(lastOffset int) error {
-	// remember where we started
+	// remember where we started with keysStack in this next() call
 	i.nextStart = append(i.nextStart[:0], i.keysStack...)
 
 	nextOffset := lastOffset + 1
+	allowCompare := false
 
 OUTER:
 	for true {
 		curr := i.statesStack[len(i.statesStack)-1]
 		autCurr := i.autStatesStack[len(i.autStatesStack)-1]
 
-		if curr.Final() && i.aut.IsMatch(autCurr) &&
-			bytes.Compare(i.keysStack, i.nextStart) > 0 {
-			// in final state greater than start key
-			return nil
+		if curr.Final() && i.aut.IsMatch(autCurr) && allowCompare {
+			// check to see if new keystack might have gone too far
+			if i.endKeyExclusive != nil &&
+				bytes.Compare(i.keysStack, i.endKeyExclusive) >= 0 {
+				return ErrIteratorDone
+			}
+
+			cmp := bytes.Compare(i.keysStack, i.nextStart)
+			if cmp > 0 {
+				// in final state greater than start key
+				return nil
+			}
 		}
 
 		numTrans := curr.NumTransitions()
@@ -207,8 +216,12 @@ OUTER:
 	INNER:
 		for nextOffset < numTrans {
 			t := curr.TransitionAt(nextOffset)
+
 			autNext := i.aut.Accept(autCurr, t)
 			if !i.aut.CanMatch(autNext) {
+				// TODO: potential optimization to skip nextOffset
+				// forwards more directly to something that the
+				// automaton likes rather than a linear scan?
 				nextOffset += 1
 				continue INNER
 			}
@@ -234,30 +247,41 @@ OUTER:
 			i.valsStack = append(i.valsStack, v)
 			i.autStatesStack = append(i.autStatesStack, autNext)
 
-			// check to see if new keystack might have gone too far
-			if i.endKeyExclusive != nil &&
-				bytes.Compare(i.keysStack, i.endKeyExclusive) >= 0 {
-				return ErrIteratorDone
-			}
-
 			nextOffset = 0
+			allowCompare = true
+
 			continue OUTER
 		}
 
+		// no more transitions, so need to backtrack and stack pop
 		if len(i.statesStack) <= 1 {
 			// stack len is 1 (root), can't go back further, we're done
 			break
 		}
 
-		// no transitions, and still room to pop
-		i.statesStack = i.statesStack[:len(i.statesStack)-1]
-		i.keysStack = i.keysStack[:len(i.keysStack)-1]
+		// if the top of the stack represents a linear chain of states
+		// (i.e., a suffix of nodes linked by single transitions),
+		// then optimize by popping the suffix in one shot without
+		// going back all the way to the OUTER loop
+		var popNum int
+		for j := len(i.statesStack) - 1; j > 0; j-- {
+			if i.statesStack[j].NumTransitions() != 1 {
+				popNum = len(i.statesStack) - 1 - j
+				break
+			}
+		}
+		if popNum < 1 { // always pop at least 1 entry from the stacks
+			popNum = 1
+		}
 
-		nextOffset = i.keysPosStack[len(i.keysPosStack)-1] + 1
+		nextOffset = i.keysPosStack[len(i.keysPosStack)-popNum] + 1
+		allowCompare = false
 
-		i.keysPosStack = i.keysPosStack[:len(i.keysPosStack)-1]
-		i.valsStack = i.valsStack[:len(i.valsStack)-1]
-		i.autStatesStack = i.autStatesStack[:len(i.autStatesStack)-1]
+		i.statesStack = i.statesStack[:len(i.statesStack)-popNum]
+		i.keysStack = i.keysStack[:len(i.keysStack)-popNum]
+		i.keysPosStack = i.keysPosStack[:len(i.keysPosStack)-popNum]
+		i.valsStack = i.valsStack[:len(i.valsStack)-popNum]
+		i.autStatesStack = i.autStatesStack[:len(i.autStatesStack)-popNum]
 	}
 
 	return ErrIteratorDone
diff --git a/vendor/github.com/couchbase/vellum/go.mod b/vendor/github.com/couchbase/vellum/go.mod
new file mode 100644
index 0000000000..0e304159d4
--- /dev/null
+++ b/vendor/github.com/couchbase/vellum/go.mod
@@ -0,0 +1,10 @@
+module github.com/couchbase/vellum
+
+go 1.12
+
+require (
+	github.com/edsrzf/mmap-go v1.0.0
+	github.com/spf13/cobra v0.0.5
+	github.com/willf/bitset v1.1.10
+	golang.org/x/sys v0.0.0-20190813064441-fde4db37ae7a // indirect
+)
diff --git a/vendor/github.com/couchbase/vellum/go.sum b/vendor/github.com/couchbase/vellum/go.sum
new file mode 100644
index 0000000000..f14998530d
--- /dev/null
+++ b/vendor/github.com/couchbase/vellum/go.sum
@@ -0,0 +1,39 @@
+github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU=
+github.com/armon/consul-api v0.0.0-20180202201655-eb2c6b5be1b6/go.mod h1:grANhF5doyWs3UAsr3K4I6qtAmlQcZDesFNEHPZAzj8=
+github.com/coreos/etcd v3.3.10+incompatible/go.mod h1:uF7uidLiAD3TWHmW31ZFd/JWoc32PjwdhPthX9715RE=
+github.com/coreos/go-etcd v2.0.0+incompatible/go.mod h1:Jez6KQU2B/sWsbdaef3ED8NzMklzPG4d5KIOhIy30Tk=
+github.com/coreos/go-semver v0.2.0/go.mod h1:nnelYz7RCh+5ahJtPPxZlU+153eP4D4r3EedlOD2RNk=
+github.com/cpuguy83/go-md2man v1.0.10/go.mod h1:SmD6nW6nTyfqj6ABTjUi3V3JVMnlJmwcJI5acqYI6dE=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/edsrzf/mmap-go v1.0.0 h1:CEBF7HpRnUCSJgGUb5h1Gm7e3VkmVDrR8lvWVLtrOFw=
+github.com/edsrzf/mmap-go v1.0.0/go.mod h1:YO35OhQPt3KJa3ryjFM5Bs14WD66h8eGKpfaBNrHW5M=
+github.com/fsnotify/fsnotify v1.4.7/go.mod h1:jwhsz4b93w/PPRr/qN1Yymfu8t87LnFCMoQvtojpjFo=
+github.com/hashicorp/hcl v1.0.0/go.mod h1:E5yfLk+7swimpb2L/Alb/PJmXilQ/rhwaUYs4T20WEQ=
+github.com/inconshreveable/mousetrap v1.0.0 h1:Z8tu5sraLXCXIcARxBp/8cbvlwVa7Z1NHg9XEKhtSvM=
+github.com/inconshreveable/mousetrap v1.0.0/go.mod h1:PxqpIevigyE2G7u3NXJIT2ANytuPF1OarO4DADm73n8=
+github.com/magiconair/properties v1.8.0/go.mod h1:PppfXfuXeibc/6YijjN8zIbojt8czPbwD3XqdrwzmxQ=
+github.com/mitchellh/go-homedir v1.1.0/go.mod h1:SfyaCUpYCn1Vlf4IUYiD9fPX4A5wJrkLzIz1N1q0pr0=
+github.com/mitchellh/mapstructure v1.1.2/go.mod h1:FVVH3fgwuzCH5S8UJGiWEs2h04kUh9fWfEaFds41c1Y=
+github.com/pelletier/go-toml v1.2.0/go.mod h1:5z9KED0ma1S8pY6P1sdut58dfprrGBbd/94hg7ilaic=
+github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
+github.com/russross/blackfriday v1.5.2/go.mod h1:JO/DiYxRf+HjHt06OyowR9PTA263kcR/rfWxYHBV53g=
+github.com/spf13/afero v1.1.2/go.mod h1:j4pytiNVoe2o6bmDsKpLACNPDBIoEAkihy7loJ1B0CQ=
+github.com/spf13/cast v1.3.0/go.mod h1:Qx5cxh0v+4UWYiBimWS+eyWzqEqokIECu5etghLkUJE=
+github.com/spf13/cobra v0.0.5 h1:f0B+LkLX6DtmRH1isoNA9VTtNUK9K8xYd28JNNfOv/s=
+github.com/spf13/cobra v0.0.5/go.mod h1:3K3wKZymM7VvHMDS9+Akkh4K60UwM26emMESw8tLCHU=
+github.com/spf13/jwalterweatherman v1.0.0/go.mod h1:cQK4TGJAtQXfYWX+Ddv3mKDzgVb68N+wFjFa4jdeBTo=
+github.com/spf13/pflag v1.0.3 h1:zPAT6CGy6wXeQ7NtTnaTerfKOsV6V6F8agHXFiazDkg=
+github.com/spf13/pflag v1.0.3/go.mod h1:DYY7MBk1bdzusC3SYhjObp+wFpr4gzcvqqNjLnInEg4=
+github.com/spf13/viper v1.3.2/go.mod h1:ZiWeW+zYFKm7srdB9IoDzzZXaJaI5eL9QjNiN/DMA2s=
+github.com/stretchr/testify v1.2.2/go.mod h1:a8OnRcib4nhh0OaRAV+Yts87kKdq0PP7pXfy6kDkUVs=
+github.com/ugorji/go/codec v0.0.0-20181204163529-d75b2dcb6bc8/go.mod h1:VFNgLljTbGfSG7qAOspJ7OScBnGdDN/yBr0sguwnwf0=
+github.com/willf/bitset v1.1.10 h1:NotGKqX0KwQ72NUzqrjZq5ipPNDQex9lo3WpaS8L2sc=
+github.com/willf/bitset v1.1.10/go.mod h1:RjeCKbqT1RxIR/KWY6phxZiaY1IyutSBfGjNPySAYV4=
+github.com/xordataexchange/crypt v0.0.3-0.20170626215501-b2862e3d0a77/go.mod h1:aYKd//L2LvnjZzWKhF00oedf4jCCReLcmhLdhm1A27Q=
+golang.org/x/crypto v0.0.0-20181203042331-505ab145d0a9/go.mod h1:6SG95UA2DQfeDnfUPMdvaQW0Q7yPrPDi9nlGo2tz2b4=
+golang.org/x/sys v0.0.0-20181205085412-a5c9d58dba9a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
+golang.org/x/sys v0.0.0-20190813064441-fde4db37ae7a h1:aYOabOQFp6Vj6W1F80affTUvO9UxmJRx8K0gsfABByQ=
+golang.org/x/sys v0.0.0-20190813064441-fde4db37ae7a/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/yaml.v2 v2.2.2/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
diff --git a/vendor/github.com/couchbase/vellum/levenshtein2/LICENSE b/vendor/github.com/couchbase/vellum/levenshtein/LICENSE
index 6b0b1270ff..6b0b1270ff 100644
--- a/vendor/github.com/couchbase/vellum/levenshtein2/LICENSE
+++ b/vendor/github.com/couchbase/vellum/levenshtein/LICENSE
diff --git a/vendor/github.com/couchbase/vellum/levenshtein2/README.md b/vendor/github.com/couchbase/vellum/levenshtein/README.md
index 582b69c77e..582b69c77e 100644
--- a/vendor/github.com/couchbase/vellum/levenshtein2/README.md
+++ b/vendor/github.com/couchbase/vellum/levenshtein/README.md
diff --git a/vendor/github.com/couchbase/vellum/levenshtein2/alphabet.go b/vendor/github.com/couchbase/vellum/levenshtein/alphabet.go
index 4bf64fef2e..ec285129ca 100644
--- a/vendor/github.com/couchbase/vellum/levenshtein2/alphabet.go
+++ b/vendor/github.com/couchbase/vellum/levenshtein/alphabet.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package levenshtein2
+package levenshtein
 
 import (
 	"fmt"
diff --git a/vendor/github.com/couchbase/vellum/levenshtein2/dfa.go b/vendor/github.com/couchbase/vellum/levenshtein/dfa.go
index e82a780a52..d0e43cac24 100644
--- a/vendor/github.com/couchbase/vellum/levenshtein2/dfa.go
+++ b/vendor/github.com/couchbase/vellum/levenshtein/dfa.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package levenshtein2
+package levenshtein
 
 import (
 	"fmt"
diff --git a/vendor/github.com/couchbase/vellum/levenshtein2/levenshtein.go b/vendor/github.com/couchbase/vellum/levenshtein/levenshtein.go
index 1ca0aaa65b..aa652df844 100644
--- a/vendor/github.com/couchbase/vellum/levenshtein2/levenshtein.go
+++ b/vendor/github.com/couchbase/vellum/levenshtein/levenshtein.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package levenshtein2
+package levenshtein
 
 import "fmt"
 
diff --git a/vendor/github.com/couchbase/vellum/levenshtein2/levenshtein_nfa.go b/vendor/github.com/couchbase/vellum/levenshtein/levenshtein_nfa.go
index bed9b99d56..68db5d191c 100644
--- a/vendor/github.com/couchbase/vellum/levenshtein2/levenshtein_nfa.go
+++ b/vendor/github.com/couchbase/vellum/levenshtein/levenshtein_nfa.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package levenshtein2
+package levenshtein
 
 import (
 	"math"
diff --git a/vendor/github.com/couchbase/vellum/levenshtein2/parametric_dfa.go b/vendor/github.com/couchbase/vellum/levenshtein/parametric_dfa.go
index ebd9311959..d08e5da639 100644
--- a/vendor/github.com/couchbase/vellum/levenshtein2/parametric_dfa.go
+++ b/vendor/github.com/couchbase/vellum/levenshtein/parametric_dfa.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package levenshtein2
+package levenshtein
 
 import (
 	"crypto/md5"
diff --git a/vendor/github.com/couchbase/vellum/regexp/compile.go b/vendor/github.com/couchbase/vellum/regexp/compile.go
index 55280164c7..92284d0a87 100644
--- a/vendor/github.com/couchbase/vellum/regexp/compile.go
+++ b/vendor/github.com/couchbase/vellum/regexp/compile.go
@@ -75,15 +75,23 @@ func (c *compiler) c(ast *syntax.Regexp) (err error) {
 					Rune0: [2]rune{r, r},
 				}
 				next.Rune = next.Rune0[0:2]
-				return c.c(&next)
-			}
-			c.sequences, c.rangeStack, err = utf8.NewSequencesPrealloc(
-				r, r, c.sequences, c.rangeStack, c.startBytes, c.endBytes)
-			if err != nil {
-				return err
-			}
-			for _, seq := range c.sequences {
-				c.compileUtf8Ranges(seq)
+				// try to find more folded runes
+				for r1 := unicode.SimpleFold(r); r1 != r; r1 = unicode.SimpleFold(r1) {
+					next.Rune = append(next.Rune, r1, r1)
+				}
+				err = c.c(&next)
+				if err != nil {
+					return err
+				}
+			} else {
+				c.sequences, c.rangeStack, err = utf8.NewSequencesPrealloc(
+					r, r, c.sequences, c.rangeStack, c.startBytes, c.endBytes)
+				if err != nil {
+					return err
+				}
+				for _, seq := range c.sequences {
+					c.compileUtf8Ranges(seq)
+				}
 			}
 		}
 	case syntax.OpAnyChar: