forked from rgburke/grv
/
search.go
201 lines (158 loc) · 4.82 KB
/
search.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
package main
import (
"fmt"
"regexp"
"runtime"
)
const (
searchMaxIterationsBeforeYeild = 1000
)
// SearchDirection describes the direction the search should be performed in
type SearchDirection int
// The set of search search directions
const (
SdForward SearchDirection = iota
SdBackward
)
var actionSearchDirection = map[ActionType]SearchDirection{
ActionSearch: SdForward,
ActionReverseSearch: SdBackward,
}
// SearchInputProvidor provides input to the search alorithm
// This abstracts the source of the data from the search logic
type SearchInputProvidor interface {
Line(lineIndex uint) (line string)
LineNumber() (lineNumber uint)
}
// SearchMatchIndex describes the byte range of a match on a line
type SearchMatchIndex struct {
ByteStartIndex uint
ByteEndIndex uint
}
// SearchMatch contains all search match positions for a line
type SearchMatch struct {
RowIndex uint
MatchIndexes []SearchMatchIndex
}
// Search manages performing a search on an input providor
type Search struct {
direction SearchDirection
pattern string
regex *regexp.Regexp
inputProvidor SearchInputProvidor
}
// CreateSearchFromAction is a utility method to create a search configured based on the action that triggered it
func CreateSearchFromAction(action Action, inputProvidor SearchInputProvidor) (search *Search, err error) {
direction, ok := actionSearchDirection[action.ActionType]
if !ok {
return search, fmt.Errorf("Invalid ActionType: %v", action.ActionType)
}
if !(len(action.Args) > 0) {
return search, fmt.Errorf("Expected search pattern")
}
pattern, ok := action.Args[0].(string)
if !ok {
return search, fmt.Errorf("Expected search pattern")
}
return NewSearch(direction, pattern, inputProvidor)
}
// NewSearch creates a new search instance
func NewSearch(direction SearchDirection, pattern string, inputProvidor SearchInputProvidor) (search *Search, err error) {
search = &Search{
direction: direction,
pattern: pattern,
inputProvidor: inputProvidor,
}
if search.regex, err = regexp.Compile(pattern); err != nil {
return
}
return
}
// FindNext looks for the next match starting from the line index provided
func (search *Search) FindNext(startLineIndex uint) (matchedLineIndex uint, found bool) {
switch search.direction {
case SdForward:
return search.findNext(startLineIndex)
case SdBackward:
return search.findPrev(startLineIndex)
}
panic(fmt.Sprintf("Invalid search direction: %v", search.direction))
}
// FindPrev looks for the next match in the reverse direction starting from the line index provided
func (search *Search) FindPrev(startLineIndex uint) (matchedLineIndex uint, found bool) {
switch search.direction {
case SdForward:
return search.findPrev(startLineIndex)
case SdBackward:
return search.findNext(startLineIndex)
}
panic(fmt.Sprintf("Invalid search direction: %v", search.direction))
}
func (search *Search) findNext(startLineIndex uint) (matchedLineIndex uint, found bool) {
currentLineIndex := startLineIndex + 1
wrapped := false
for !wrapped || currentLineIndex <= startLineIndex {
if currentLineIndex >= search.inputProvidor.LineNumber() {
currentLineIndex = 0
wrapped = true
}
line := search.inputProvidor.Line(currentLineIndex)
if search.regex.MatchString(line) {
matchedLineIndex = currentLineIndex
found = true
break
}
currentLineIndex++
if currentLineIndex%searchMaxIterationsBeforeYeild == 0 {
runtime.Gosched()
}
}
return
}
func (search *Search) findPrev(startLineIndex uint) (matchedLineIndex uint, found bool) {
currentLineIndex := startLineIndex
wrapped := false
for !wrapped || currentLineIndex > startLineIndex {
if currentLineIndex == 0 {
currentLineIndex = search.inputProvidor.LineNumber()
if currentLineIndex == 0 {
break
}
wrapped = true
}
currentLineIndex--
line := search.inputProvidor.Line(currentLineIndex)
if search.regex.MatchString(line) {
matchedLineIndex = currentLineIndex
found = true
break
}
if currentLineIndex%searchMaxIterationsBeforeYeild == 0 {
runtime.Gosched()
}
}
return
}
// FindAll find all matches across the entire input provided
func (search *Search) FindAll() (matches []SearchMatch) {
for lineIndex := uint(0); lineIndex < search.inputProvidor.LineNumber(); lineIndex++ {
line := search.inputProvidor.Line(lineIndex)
lineMatches := search.regex.FindAllStringIndex(line, -1)
if len(lineMatches) > 0 {
searchMatch := SearchMatch{
RowIndex: lineIndex,
}
for _, lineMatch := range lineMatches {
searchMatch.MatchIndexes = append(searchMatch.MatchIndexes, SearchMatchIndex{
ByteStartIndex: uint(lineMatch[0]),
ByteEndIndex: uint(lineMatch[1]),
})
}
matches = append(matches, searchMatch)
}
if (lineIndex+1)%searchMaxIterationsBeforeYeild == 0 {
runtime.Gosched()
}
}
return
}