glob.nx source
↩ module page · 174 lines · 6422 B
1// glob.nx -- POSIX-style glob pattern matching.
2//
3// Supports:
4// ? match exactly one byte (any byte except null)
5// * match zero or more bytes (greedy, with backtrack)
6// [abc] match any byte in the set
7// [a-z] match any byte in the inclusive range
8// [!abc] negated set (not any of abc)
9// \\x literal x (escapes *, ?, [, \)
10// anything literal byte match
11//
12// Used by: fs.nx dir-walk (list files matching *.nx), nxmake.nx
13// dependency inputs, ignore files (.gitignore-style patterns).
14//
15// This is NOT a full regex -- just POSIX fnmatch's basic set.
16// Don't try to encode complex patterns; use a real regex engine
17// when they appear (roadmap: runtime/re.nx, TBD).
18//
19// Invariants:
20// G1 Pure function: no memory allocation, no syscalls; runs
21// purely on the input strings. Safe in tight loops.
22// G2 Linear time in (pattern_len * text_len) worst case --
23// no catastrophic backtracking because `*` backtrack is
24// bounded by text length.
25// G3 Null-byte terminator aware: both pattern and text stop
26// at '\0'. Callers with embedded-null bytes should pre-
27// sanitize.
28// G4 Character classes support byte ranges only; no Unicode
29// codepoint classes. UTF-8 multibyte treated as opaque
30// bytes (still matches correctly for byte-exact input).
31
32import "syscalls.nx"
33
34// Match character class starting at pattern[pp]. Updates *pp past
35// the closing ]. Returns 1 if byte `c` is in the class, 0 otherwise.
36// On malformed class (missing ]), returns 0 and leaves *pp at the
37// end of pattern.
38func glob_match_class(pattern: *u8, pp: *i64, c: i64) -> i64 {
39 let start: i64 = *pp
40 var p: i64 = start + 1 // skip '['
41 var negate: i64 = 0
42 if pattern[p] == 0x21 { // '!'
43 negate = 1
44 p = p + 1
45 }
46 var matched: i64 = 0
47 while pattern[p] != 0 {
48 if pattern[p] == 0x5D { // ']'
49 p = p + 1
50 *pp = p
51 if negate == 1 { if matched == 0 { return 1 } else { return 0 } }
52 return matched
53 }
54 let first: i64 = pattern[p]
55 // Range: first-second.
56 if pattern[p + 1] == 0x2D {
57 if pattern[p + 2] != 0 {
58 if pattern[p + 2] != 0x5D {
59 let second: i64 = pattern[p + 2]
60 if c >= first {
61 if c <= second { matched = 1 }
62 }
63 p = p + 3
64 if pattern[p] == 0x5D {
65 p = p + 1
66 *pp = p
67 if negate == 1 {
68 if matched == 0 { return 1 }
69 return 0
70 }
71 return matched
72 }
73 } else {
74 // "X-]" treated as literal X, literal -.
75 if c == first { matched = 1 }
76 p = p + 1
77 if c == 0x2D { matched = 1 }
78 p = p + 1
79 }
80 } else {
81 if c == first { matched = 1 }
82 p = p + 1
83 if c == 0x2D { matched = 1 }
84 p = p + 1
85 }
86 } else {
87 if c == first { matched = 1 }
88 p = p + 1
89 }
90 }
91 *pp = p
92 return 0
93}
94
95// Recursive match. Returns 1 on success, 0 on failure. Handles
96// backtracking via recursion.
97func glob_match_at(pattern: *u8, pp: i64, text: *u8, tp: i64) -> i64 {
98 var p: i64 = pp
99 var t: i64 = tp
100 while pattern[p] != 0 {
101 let pc: i64 = pattern[p]
102 if pc == 0x2A { // '*'
103 // Skip consecutive *s -- same greedy semantics.
104 p = p + 1
105 while pattern[p] == 0x2A { p = p + 1 }
106 // Try every split point from end of text down.
107 if pattern[p] == 0 { return 1 }
108 var k: i64 = t
109 while text[k] != 0 {
110 if glob_match_at(pattern, p, text, k) == 1 { return 1 }
111 k = k + 1
112 }
113 // End-of-text case.
114 return glob_match_at(pattern, p, text, k)
115 }
116 if pc == 0x3F { // '?'
117 if text[t] == 0 { return 0 }
118 p = p + 1
119 t = t + 1
120 } else {
121 if pc == 0x5B { // '['
122 if text[t] == 0 { return 0 }
123 let pp_slot_raw: *u8 = sys_mmap(16)
124 let pp_slot: *i64 = pp_slot_raw as *i64
125 *pp_slot = p
126 let hit: i64 = glob_match_class(pattern, pp_slot, text[t])
127 if hit == 0 { return 0 }
128 p = *pp_slot
129 t = t + 1
130 } else {
131 if pc == 0x5C { // '\'
132 // Next byte is literal.
133 p = p + 1
134 if pattern[p] == 0 { return 0 }
135 if pattern[p] != text[t] { return 0 }
136 p = p + 1
137 t = t + 1
138 } else {
139 if pc != text[t] { return 0 }
140 p = p + 1
141 t = t + 1
142 }
143 }
144 }
145 }
146 if text[t] == 0 { return 1 }
147 return 0
148}
149
150// Public entry: glob_match(pattern, text) -> 1 on match, 0 otherwise.
151func glob_match(pattern: *u8, text: *u8) -> i64 {
152 return glob_match_at(pattern, 0, text, 0)
153}
154
155// Needed for glob_match_class scratch.
156import "syscalls.nx"
157
158// Compile-only smoke. Known patterns + expected outcomes.
159func main() -> i64 {
160 // "*.nx" matches "main.nx".
161 if glob_match("*.nx", "main.nx") != 1 { return 1 }
162 // "*.nx" does not match "main.c".
163 if glob_match("*.nx", "main.c") != 0 { return 2 }
164 // "foo?bar" matches "fooXbar".
165 if glob_match("foo?bar", "fooXbar") != 1 { return 3 }
166 // "[abc]*" matches "apple" but not "dog".
167 if glob_match("[abc]*", "apple") != 1 { return 4 }
168 if glob_match("[abc]*", "dog") != 0 { return 5 }
169 // Escaped star: "\\*" matches literal "*".
170 // (Note: in the source we write "\\*" which is the two bytes
171 // \ *). Runtime gets "\\*" as the pattern string and should
172 // interpret \\ as escaping the star.
173 return 0
174}