1
A grep, from scratch, in Go[github]
1
2
A grep built from scratch in Go with no regex libraries — the
3
pattern is compiled by hand into a token list, and matching is a
4
backtracking DFS where every token reports all the ways it could
5
consume the input, greedy-first.
6
7
Supports ERE-flavored syntax (character classes, anchors,
8
quantifiers including {n,m} ranges, grouping and alternation),
9
capture groups that survive nesting, and multiple and nested
10
backreferences, behind a grep-style CLI with recursive directory
11
walk and a goroutine-per-file fan-out. Built end-to-end as the
12
CodeCrafters 'Build Your Own grep' challenge, including the
13
Backreferences and File Search extensions.
14
15
16
18
19
func (t Backreference) Match(input []rune, i int, matched []*TokenMatchResult) []*TokenMatchResult {
20
var match *TokenMatchResult
21
for _, m := range matched {
22
if m.GroupNumber == int(t) {
23
match = m
24
}
25
}
26
if match == nil {
27
return nil
28
}
29
30
expected := input[match.Start:match.End]
31
if i+len(expected) > len(input) {
32
return nil
33
}
34
if slices.Equal(expected, input[i:i+len(expected)]) {
35
return []*TokenMatchResult{{Start: i, End: i + len(expected)}}
36
}
37
return nil
38
}
39
40
41
42
43
44
func (t Backreference) Match(input []rune, i int, matched []*TokenMatchResult) []*TokenMatchResult {
var match *TokenMatchResult
for _, m := range matched {
if m.GroupNumber == int(t) {
match = m
}
}
if match == nil {
return nil
}
expected := input[match.Start:match.End]
if i+len(expected) > len(input) {
return nil
}
if slices.Equal(expected, input[i:i+len(expected)]) {
return []*TokenMatchResult{{Start: i, End: i + len(expected)}}
}
return nil
}
func (t Range) String() string {
to := ""
if t.To == math.MaxInt {
to = ""
} else {
to = fmt.Sprintf("%d", t.To)
}
return fmt.Sprintf("%s{%d:%s}", t.Token.String(), t.From, to)
}
func (t Range) Match(input []rune, i int, matched []*TokenMatchResult) []*TokenMatchResult {
m := map[int]struct{}{}
if t.From == 0 {
m[i] = struct{}{}
}
t.matchFully(input, i, matched, 0, t.From, t.To, map[[2]int]struct{}{}, m)
var res []*TokenMatchResult
for it := range m {
res = append(res, &TokenMatchResult{Start: i, End: it})
}
slices.SortFunc(res, func(a, b *TokenMatchResult) int {
return a.End - b.End
})
slices.Reverse(res)
return res
}
func (t Group) Match(input []rune, i int, matched []*TokenMatchResult) []*TokenMatchResult {
m := map[int][]*TokenMatchResult{}
matchFullyAllOptions(t.Tokens, input, i, 0, false, matched, m)
if len(m) == 0 {
return nil
}
var res []*TokenMatchResult
for end, matchedPath := range m {
res = append(
res,
&TokenMatchResult{
Start: i,
End: end,
// record only subpath, without all previous matches
Subs: matchedPath[len(matched):],
GroupNumber: t.Number,
},
)
}
slices.SortFunc(res, func(a, b *TokenMatchResult) int {
return a.End - b.End
})
slices.Reverse(res)
return res
}
func (t Or) Match(input []rune, i int, matched []*TokenMatchResult) []*TokenMatchResult {
if i >= len(input) {
return nil
}
m := map[int][]*TokenMatchResult{}
matchFullyAllOptions([]Token(t.Left), input, i, 0, false, matched, m)
matchFullyAllOptions([]Token(t.Right), input, i, 0, false, matched, m)
if len(m) == 0 {
return nil
}
var res []*TokenMatchResult
for end := range m {
res = append(res, &TokenMatchResult{Start: i, End: end})
}
slices.SortFunc(res, func(a, b *TokenMatchResult) int {
return b.End - a.End
})
return res
}