Add OR operator

Close #412

4 files changed, 127 insertions, 53 deletions

diff --git a/README.md b/README.md
index 23841c64..60698363 100644
--- a/README.md
+++ b/README.md
@@ -127,6 +127,14 @@ If you don't prefer fuzzy matching and do not wish to "quote" every word,
 start fzf with `-e` or `--exact` option. Note that when  `--exact` is set,
 `'`-prefix "unquotes" the term.
 
+A single bar character term acts as an OR operator. For example, the following
+query matches entries that start with `core` and end with either `go`, `rb`,
+or `py`.
+
+```
+^core go$ | rb$ | py$
+```
+
 #### Environment variables
 
 - `FZF_DEFAULT_COMMAND`
diff --git a/man/man1/fzf.1 b/man/man1/fzf.1
index 50de48e8..275e6598 100644
--- a/man/man1/fzf.1
+++ b/man/man1/fzf.1
@@ -401,6 +401,13 @@ If you don't prefer fuzzy matching and do not wish to "quote" (prefixing with
 \fB'\fR) every word, start fzf with \fB-e\fR or \fB--exact\fR option. Note that
 when \fB--exact\fR is set, \fB'\fR-prefix "unquotes" the term.
 
+.SS OR operator
+A single bar character term acts as an OR operator. For example, the following
+query matches entries that start with \fBcore\fR and end with either \fBgo\fR,
+\fBrb\fR, or \fBpy\fR.
+
+e.g. \fB^core go$ | rb$ | py$\fR
+
 .SH AUTHOR
 Junegunn Choi (\fIjunegunn.c@gmail.com\fR)
 
diff --git a/src/pattern.go b/src/pattern.go
index 7c81ea02..795fbb52 100644
--- a/src/pattern.go
+++ b/src/pattern.go
@@ -36,6 +36,8 @@ type term struct {
 	origText      []rune
 }
 
+type termSet []term
+
 // Pattern represents search pattern
 type Pattern struct {
 	fuzzy         bool
@@ -43,8 +45,8 @@ type Pattern struct {
 	caseSensitive bool
 	forward       bool
 	text          []rune
-	terms         []term
-	hasInvTerm    bool
+	termSets      []termSet
+	cacheable     bool
 	delimiter     Delimiter
 	nth           []Range
 	procFun       map[termType]func(bool, bool, []rune, []rune) (int, int)
@@ -88,14 +90,20 @@ func BuildPattern(fuzzy bool, extended bool, caseMode Case, forward bool,
 		return cached
 	}
 
-	caseSensitive, hasInvTerm := true, false
-	terms := []term{}
+	caseSensitive, cacheable := true, true
+	termSets := []termSet{}
 
 	if extended {
-		terms = parseTerms(fuzzy, caseMode, asString)
-		for _, term := range terms {
-			if term.inv {
-				hasInvTerm = true
+		termSets = parseTerms(fuzzy, caseMode, asString)
+	Loop:
+		for _, termSet := range termSets {
+			for idx, term := range termSet {
+				// If the query contains inverse search terms or OR operators,
+				// we cannot cache the search scope
+				if idx > 0 || term.inv {
+					cacheable = false
+					break Loop
+				}
 			}
 		}
 	} else {
@@ -113,8 +121,8 @@ func BuildPattern(fuzzy bool, extended bool, caseMode Case, forward bool,
 		caseSensitive: caseSensitive,
 		forward:       forward,
 		text:          []rune(asString),
-		terms:         terms,
-		hasInvTerm:    hasInvTerm,
+		termSets:      termSets,
+		cacheable:     cacheable,
 		nth:           nth,
 		delimiter:     delimiter,
 		procFun:       make(map[termType]func(bool, bool, []rune, []rune) (int, int))}
@@ -129,9 +137,11 @@ func BuildPattern(fuzzy bool, extended bool, caseMode Case, forward bool,
 	return ptr
 }
 
-func parseTerms(fuzzy bool, caseMode Case, str string) []term {
+func parseTerms(fuzzy bool, caseMode Case, str string) []termSet {
 	tokens := _splitRegex.Split(str, -1)
-	terms := []term{}
+	sets := []termSet{}
+	set := termSet{}
+	switchSet := false
 	for _, token := range tokens {
 		typ, inv, text := termFuzzy, false, token
 		lowerText := strings.ToLower(text)
@@ -145,6 +155,11 @@ func parseTerms(fuzzy bool, caseMode Case, str string) []term {
 			typ = termExact
 		}
 
+		if text == "|" {
+			switchSet = false
+			continue
+		}
+
 		if strings.HasPrefix(text, "!") {
 			inv = true
 			text = text[1:]
@@ -173,15 +188,23 @@ func parseTerms(fuzzy bool, caseMode Case, str string) []term {
 		}
 
 		if len(text) > 0 {
-			terms = append(terms, term{
+			if switchSet {
+				sets = append(sets, set)
+				set = termSet{}
+			}
+			set = append(set, term{
 				typ:           typ,
 				inv:           inv,
 				text:          []rune(text),
 				caseSensitive: caseSensitive,
 				origText:      origText})
+			switchSet = true
 		}
 	}
-	return terms
+	if len(set) > 0 {
+		sets = append(sets, set)
+	}
+	return sets
 }
 
 // IsEmpty returns true if the pattern is effectively empty
@@ -189,7 +212,7 @@ func (p *Pattern) IsEmpty() bool {
 	if !p.extended {
 		return len(p.text) == 0
 	}
-	return len(p.terms) == 0
+	return len(p.termSets) == 0
 }
 
 // AsString returns the search query in string type
@@ -203,11 +226,10 @@ func (p *Pattern) CacheKey() string {
 		return p.AsString()
 	}
 	cacheableTerms := []string{}
-	for _, term := range p.terms {
-		if term.inv {
-			continue
+	for _, termSet := range p.termSets {
+		if len(termSet) == 1 && !termSet[0].inv {
+			cacheableTerms = append(cacheableTerms, string(termSet[0].origText))
 		}
-		cacheableTerms = append(cacheableTerms, string(term.origText))
 	}
 	return strings.Join(cacheableTerms, " ")
 }
@@ -218,7 +240,7 @@ func (p *Pattern) Match(chunk *Chunk) []*Item {
 
 	// ChunkCache: Exact match
 	cacheKey := p.CacheKey()
-	if !p.hasInvTerm { // Because we're excluding Inv-term from cache key
+	if p.cacheable {
 		if cached, found := _cache.Find(chunk, cacheKey); found {
 			return cached
 		}
@@ -243,7 +265,7 @@ Loop:
 
 	matches := p.matchChunk(space)
 
-	if !p.hasInvTerm {
+	if p.cacheable {
 		_cache.Add(chunk, cacheKey, matches)
 	}
 	return matches
@@ -260,7 +282,7 @@ func (p *Pattern) matchChunk(chunk *Chunk) []*Item {
 		}
 	} else {
 		for _, item := range *chunk {
-			if offsets := p.extendedMatch(item); len(offsets) == len(p.terms) {
+			if offsets := p.extendedMatch(item); len(offsets) == len(p.termSets) {
 				matches = append(matches, dupItem(item, offsets))
 			}
 		}
@@ -275,7 +297,7 @@ func (p *Pattern) MatchItem(item *Item) bool {
 		return sidx >= 0
 	}
 	offsets := p.extendedMatch(item)
-	return len(offsets) == len(p.terms)
+	return len(offsets) == len(p.termSets)
 }
 
 func dupItem(item *Item, offsets []Offset) *Item {
@@ -301,15 +323,20 @@ func (p *Pattern) basicMatch(item *Item) (int, int, int) {
 func (p *Pattern) extendedMatch(item *Item) []Offset {
 	input := p.prepareInput(item)
 	offsets := []Offset{}
-	for _, term := range p.terms {
-		pfun := p.procFun[term.typ]
-		if sidx, eidx, tlen := p.iter(pfun, input, term.caseSensitive, p.forward, term.text); sidx >= 0 {
-			if term.inv {
+Loop:
+	for _, termSet := range p.termSets {
+		for _, term := range termSet {
+			pfun := p.procFun[term.typ]
+			if sidx, eidx, tlen := p.iter(pfun, input, term.caseSensitive, p.forward, term.text); sidx >= 0 {
+				if term.inv {
+					break Loop
+				}
+				offsets = append(offsets, Offset{int32(sidx), int32(eidx), int32(tlen)})
+				break
+			} else if term.inv {
+				offsets = append(offsets, Offset{0, 0, 0})
 				break
 			}
-			offsets = append(offsets, Offset{int32(sidx), int32(eidx), int32(tlen)})
-		} else if term.inv {
-			offsets = append(offsets, Offset{0, 0, 0})
 		}
 	}
 	return offsets
diff --git a/src/pattern_test.go b/src/pattern_test.go
index 8b41a695..6bf571cd 100644
--- a/src/pattern_test.go
+++ b/src/pattern_test.go
@@ -9,20 +9,25 @@ import (
 
 func TestParseTermsExtended(t *testing.T) {
 	terms := parseTerms(true, CaseSmart,
-		"aaa 'bbb ^ccc ddd$ !eee !'fff !^ggg !hhh$ ^iii$")
+		"| aaa 'bbb ^ccc ddd$ !eee !'fff !^ggg !hhh$ | ^iii$ ^xxx | 'yyy | | zzz$ | !ZZZ |")
 	if len(terms) != 9 ||
-		terms[0].typ != termFuzzy || terms[0].inv ||
-		terms[1].typ != termExact || terms[1].inv ||
-		terms[2].typ != termPrefix || terms[2].inv ||
-		terms[3].typ != termSuffix || terms[3].inv ||
-		terms[4].typ != termFuzzy || !terms[4].inv ||
-		terms[5].typ != termExact || !terms[5].inv ||
-		terms[6].typ != termPrefix || !terms[6].inv ||
-		terms[7].typ != termSuffix || !terms[7].inv ||
-		terms[8].typ != termEqual || terms[8].inv {
+		terms[0][0].typ != termFuzzy || terms[0][0].inv ||
+		terms[1][0].typ != termExact || terms[1][0].inv ||
+		terms[2][0].typ != termPrefix || terms[2][0].inv ||
+		terms[3][0].typ != termSuffix || terms[3][0].inv ||
+		terms[4][0].typ != termFuzzy || !terms[4][0].inv ||
+		terms[5][0].typ != termExact || !terms[5][0].inv ||
+		terms[6][0].typ != termPrefix || !terms[6][0].inv ||
+		terms[7][0].typ != termSuffix || !terms[7][0].inv ||
+		terms[7][1].typ != termEqual || terms[7][1].inv ||
+		terms[8][0].typ != termPrefix || terms[8][0].inv ||
+		terms[8][1].typ != termExact || terms[8][1].inv ||
+		terms[8][2].typ != termSuffix || terms[8][2].inv ||
+		terms[8][3].typ != termFuzzy || !terms[8][3].inv {
 		t.Errorf("%s", terms)
 	}
-	for idx, term := range terms {
+	for idx, termSet := range terms[:8] {
+		term := termSet[0]
 		if len(term.text) != 3 {
 			t.Errorf("%s", term)
 		}
@@ -30,20 +35,25 @@ func TestParseTermsExtended(t *testing.T) {
 			t.Errorf("%s", term)
 		}
 	}
+	for _, term := range terms[8] {
+		if len(term.origText) != 4 {
+			t.Errorf("%s", term)
+		}
+	}
 }
 
 func TestParseTermsExtendedExact(t *testing.T) {
 	terms := parseTerms(false, CaseSmart,
 		"aaa 'bbb ^ccc ddd$ !eee !'fff !^ggg !hhh$")
 	if len(terms) != 8 ||
-		terms[0].typ != termExact || terms[0].inv || len(terms[0].text) != 3 ||
-		terms[1].typ != termFuzzy || terms[1].inv || len(terms[1].text) != 3 ||
-		terms[2].typ != termPrefix || terms[2].inv || len(terms[2].text) != 3 ||
-		terms[3].typ != termSuffix || terms[3].inv || len(terms[3].text) != 3 ||
-		terms[4].typ != termExact || !terms[4].inv || len(terms[4].text) != 3 ||
-		terms[5].typ != termFuzzy || !terms[5].inv || len(terms[5].text) != 3 ||
-		terms[6].typ != termPrefix || !terms[6].inv || len(terms[6].text) != 3 ||
-		terms[7].typ != termSuffix || !terms[7].inv || len(terms[7].text) != 3 {
+		terms[0][0].typ != termExact || terms[0][0].inv || len(terms[0][0].text) != 3 ||
+		terms[1][0].typ != termFuzzy || terms[1][0].inv || len(terms[1][0].text) != 3 ||
+		terms[2][0].typ != termPrefix || terms[2][0].inv || len(terms[2][0].text) != 3 ||
+		terms[3][0].typ != termSuffix || terms[3][0].inv || len(terms[3][0].text) != 3 ||
+		terms[4][0].typ != termExact || !terms[4][0].inv || len(terms[4][0].text) != 3 ||
+		terms[5][0].typ != termFuzzy || !terms[5][0].inv || len(terms[5][0].text) != 3 ||
+		terms[6][0].typ != termPrefix || !terms[6][0].inv || len(terms[6][0].text) != 3 ||
+		terms[7][0].typ != termSuffix || !terms[7][0].inv || len(terms[7][0].text) != 3 {
 		t.Errorf("%s", terms)
 	}
 }
@@ -61,9 +71,9 @@ func TestExact(t *testing.T) {
 	pattern := BuildPattern(true, true, CaseSmart, true,
 		[]Range{}, Delimiter{}, []rune("'abc"))
 	sidx, eidx := algo.ExactMatchNaive(
-		pattern.caseSensitive, pattern.forward, []rune("aabbcc abc"), pattern.terms[0].text)
+		pattern.caseSensitive, pattern.forward, []rune("aabbcc abc"), pattern.termSets[0][0].text)
 	if sidx != 7 || eidx != 10 {
-		t.Errorf("%s / %d / %d", pattern.terms, sidx, eidx)
+		t.Errorf("%s / %d / %d", pattern.termSets, sidx, eidx)
 	}
 }
 
@@ -74,9 +84,9 @@ func TestEqual(t *testing.T) {
 
 	match := func(str string, sidxExpected int, eidxExpected int) {
 		sidx, eidx := algo.EqualMatch(
-			pattern.caseSensitive, pattern.forward, []rune(str), pattern.terms[0].text)
+			pattern.caseSensitive, pattern.forward, []rune(str), pattern.termSets[0][0].text)
 		if sidx != sidxExpected || eidx != eidxExpected {
-			t.Errorf("%s / %d / %d", pattern.terms, sidx, eidx)
+			t.Errorf("%s / %d / %d", pattern.termSets, sidx, eidx)
 		}
 	}
 	match("ABC", -1, -1)
@@ -130,3 +140,25 @@ func TestOrigTextAndTransformed(t *testing.T) {
 		}
 	}
 }
+
+func TestCacheKey(t *testing.T) {
+	test := func(extended bool, patStr string, expected string, cacheable bool) {
+		pat := BuildPattern(true, extended, CaseSmart, true, []Range{}, Delimiter{}, []rune(patStr))
+		if pat.CacheKey() != expected {
+			t.Errorf("Expected: %s, actual: %s", expected, pat.CacheKey())
+		}
+		if pat.cacheable != cacheable {
+			t.Errorf("Expected: %s, actual: %s (%s)", cacheable, pat.cacheable, patStr)
+		}
+		clearPatternCache()
+	}
+	test(false, "foo !bar", "foo !bar", true)
+	test(false, "foo | bar !baz", "foo | bar !baz", true)
+	test(true, "foo  bar  baz", "foo bar baz", true)
+	test(true, "foo !bar", "foo", false)
+	test(true, "foo !bar   baz", "foo baz", false)
+	test(true, "foo | bar baz", "baz", false)
+	test(true, "foo | bar | baz", "", false)
+	test(true, "foo | bar !baz", "", false)
+	test(true, "| | | foo", "foo", true)
+}