1// SPDX-License-Identifier: MIT
2
3package workflow
4
5import (
6 "fmt"
7 "regexp"
8 "strings"
9)
10
11// Pattern is a compiled filter pattern in the syntax GitHub documents as the
12// "filter pattern cheat sheet" for branches, tags and paths:
13//
14// - zero or more characters, but not /
15// ** zero or more of any character; "**/" at the start of a pattern or
16// after a "/" may also match nothing, so "**/README.md" matches
17// "README.md" and "docs/**/*.md" matches "docs/a.md"
18// ? zero or one of the preceding character
19// - one or more of the preceding character
20// [abc] one character listed or in a range (a-z, A-Z, 0-9)
21// ! at the start of a pattern: negates the patterns before it
22// \ escapes the next character
23//
24// Every other character, "." included, stands for itself. Matching is
25// case-sensitive and covers the whole name.
26//
27// Recorded on github.com (filter-branches, filter-paths, filter-paths-ignore,
28// see TestMatchPushRecordedGlobs): "*", "**", "scn/filter-*/**", "**.md",
29// "*.md" and negation order. TODO(verify with recording): "**/" matching
30// nothing, "\" escapes and how ? and + behave after a wildcard or a bracket
31// are reconstructed.
32type Pattern struct {
33 // Negated is set for a pattern that started with "!".
34 Negated bool
35 // Source is the pattern as written.
36 Source string
37 re *regexp.Regexp
38}
39
40// CompilePattern compiles one pattern. A pattern that cannot be compiled never
41// matches; the error says why.
42func CompilePattern(p string) (*Pattern, error) {
43 pat := &Pattern{Source: p}
44 body := p
45 if strings.HasPrefix(body, "!") {
46 pat.Negated = true
47 body = body[1:]
48 }
49 re, err := regexp.Compile("^(?s:" + translateGlob(body) + ")$")
50 if err != nil {
51 return pat, err
52 }
53 pat.re = re
54 return pat, nil
55}
56
57// Match reports whether name matches the pattern, ignoring any "!" prefix.
58func (p *Pattern) Match(name string) bool { return p.re != nil && p.re.MatchString(name) }
59
60// translateGlob converts a pattern to an RE2 expression.
61func translateGlob(p string) string {
62 var b strings.Builder
63 rs := []rune(p)
64 // quantifiable is true when the last thing written is a single character
65 // or a class that ? and + can apply to.
66 quantifiable := false
67 for i := 0; i < len(rs); i++ {
68 c := rs[i]
69 switch c {
70 case '\\':
71 if i+1 < len(rs) {
72 i++
73 b.WriteString(regexp.QuoteMeta(string(rs[i])))
74 } else {
75 b.WriteString(`\\`)
76 }
77 quantifiable = true
78 case '*':
79 if i+1 < len(rs) && rs[i+1] == '*' {
80 for i+1 < len(rs) && rs[i+1] == '*' {
81 i++
82 }
83 atStart := b.Len() == 0 || (i-2 >= 0 && rs[i-2] == '/')
84 if atStart && i+1 < len(rs) && rs[i+1] == '/' {
85 i++
86 b.WriteString(`(?:.*/)?`)
87 } else {
88 b.WriteString(`.*`)
89 }
90 } else {
91 b.WriteString(`[^/]*`)
92 }
93 quantifiable = false
94 case '?', '+':
95 if quantifiable {
96 b.WriteRune(c)
97 quantifiable = false
98 } else {
99 b.WriteString(regexp.QuoteMeta(string(c)))
100 quantifiable = true
101 }
102 case '[':
103 if class, n, ok := parseClass(rs[i:]); ok {
104 b.WriteString(class)
105 i += n - 1
106 quantifiable = true
107 } else {
108 b.WriteString(`\[`)
109 quantifiable = true
110 }
111 default:
112 b.WriteString(regexp.QuoteMeta(string(c)))
113 quantifiable = true
114 }
115 }
116 return b.String()
117}
118
119// parseClass reads "[...]" at the start of rs: letters, digits and ranges of
120// them. It returns the RE2 class and the number of runes consumed.
121func parseClass(rs []rune) (string, int, bool) {
122 var b strings.Builder
123 b.WriteByte('[')
124 n := 0
125 for i := 1; i < len(rs); i++ {
126 c := rs[i]
127 switch {
128 case c == ']':
129 if n == 0 {
130 return "", 0, false
131 }
132 b.WriteByte(']')
133 return b.String(), i + 1, true
134 case c >= 'a' && c <= 'z', c >= 'A' && c <= 'Z', c >= '0' && c <= '9':
135 b.WriteRune(c)
136 n++
137 case c == '-' && n > 0 && i+1 < len(rs) && rs[i+1] != ']':
138 b.WriteByte('-')
139 default:
140 return "", 0, false
141 }
142 }
143 return "", 0, false
144}
145
146// matchList applies compiled patterns to name in order. A pattern that
147// matches includes the name, a "!" pattern that matches excludes it again, and
148// the last pattern that matches decides. A list with no positive pattern
149// therefore matches nothing.
150func matchList(patterns []*Pattern, name string) bool {
151 matched := false
152 for _, p := range patterns {
153 if p.Match(name) {
154 matched = !p.Negated
155 }
156 }
157 return matched
158}
159
160// compileList compiles a filter list. It reports the first pattern that does
161// not compile.
162func compileList(patterns []string) ([]*Pattern, error) {
163 out := make([]*Pattern, 0, len(patterns))
164 for _, s := range patterns {
165 p, err := CompilePattern(s)
166 if err != nil {
167 return nil, fmt.Errorf("invalid pattern '%s': %w", s, err)
168 }
169 out = append(out, p)
170 }
171 return out, nil
172}