nx_grep_rt.nx source
↩ module page · 167 lines · 6518 B
1// nx_grep.nx -- S1 first stone of NISHI_SHELL_REPLACEMENT_ROADMAP.md.
2//
3// Canonical: this is the substrate-wide canonical grep primitive
4// per [[feedback-bits-up-shell-replace-linux-brother-tools]].
5// Substring + line-number reporting over a byte buffer. Composes
6// nx_str_find from nx_string_ops.nx; no Linux-brother grep / ripgrep
7// dependency.
8//
9// Bits-up doctrine applied to the shell tier: substrate's audit /
10// tooling layer stops depending on grep. S2 will add regex (RE2-
11// style DFA + NFA hybrid). S2.5+ will add SIMD substring (Muła-
12// Lemire 2020), Aho-Corasick multi-pattern (1975), and tournament-
13// based variant selection per-die via ETG.
14//
15// API:
16// nx_grep_count(buf, n_buf, pattern, n_pat)
17// -> total occurrences of pattern in buf (overlapping matches
18// NOT counted; substring search advances past each match)
19//
20// nx_grep_first_offset(buf, n_buf, pattern, n_pat)
21// -> byte offset of first occurrence, -1 if none
22//
23// nx_grep_lines_match_count(buf, n_buf, pattern, n_pat)
24// -> count of DISTINCT lines containing at least one match
25// (a line with N occurrences counts as 1)
26//
27// nx_grep_first_line_number(buf, n_buf, pattern, n_pat)
28// -> 1-based line number of the first matching line, -1 if none
29//
30// nx_grep_any(buf, n_buf, pattern, n_pat)
31// -> 1 if pattern occurs at least once, 0 otherwise
32//
33// Composes:
34// [[NISHI_SHELL_REPLACEMENT_ROADMAP]] S1 (this is the first stone)
35// nx_string_ops.nx (nx_str_find substring search; SHIPPED)
36// [[feedback-bits-up-shell-replace-linux-brother-tools]] (cardinal)
37// [[feedback-bits-up-exceed-never-match]] (research absorbed +
38// substrate exceeds; cannot exceed grep by cloning grep)
39// [[feedback-no-tool-proliferation-bit-level]] (nx_grep is the
40// canonical; future grep-adjacent primitives compose this)
41//
42// Research lineage (clean-room cite; no copying):
43// Knuth-Morris-Pratt 1977 (single-pattern linear)
44// Boyer-Moore 1977 (skip-on-mismatch; this primitive's variant
45// queued for S1.5; nx_str_find current impl is simpler scan)
46// Aho-Corasick 1975 (multi-pattern; queued S2.5)
47// bitap / Shift-Or 1992 (approximate match; queued S2)
48// RE2 / Cox 2009 (DFA+NFA regex; queued S2)
49// Hyperscan 2014 (SIMD vectorized; queued S5+ per-die ETG)
50// ripgrep 2016 (architectural cite; we EXCEED via bits-up)
51// Muła+Lemire 2020 (SIMD substring; queued S5+)
52
53// nx_safety_envelope:
54// intended_use: "canonical substring + line-number grep
55// primitive composing nx_str_find; first
56// stone of the substrate's shell-replacement
57// tier"
58// sil_target: SIL2
59// evidence: [kat_substring_match,
60// kat_no_match_returns_negative,
61// kat_line_number_correct,
62// kat_overlapping_handled_correctly]
63// hazard_register: [bug-tape-empty-pattern-undefined,
64// bug-tape-overlap-counted-twice,
65// bug-tape-line-number-off-by-one]
66// verdict: NOT_YET_EVALUATED
67
68import "nx_syscalls.nx"
69import "nx_string_ops.nx"
70
71// ===== Counting matches ===========================================
72//
73// Walk the buffer; for each found occurrence, advance past it
74// (non-overlapping match counting). Returns total count.
75
76func nx_grep_count(buf: *u8, n_buf: nx_int, pattern: *u8, n_pat: nx_int) -> nx_int {
77 if n_pat <= 0 { return 0 }
78 if n_buf < n_pat { return 0 }
79 var count: nx_int = 0
80 var pos: nx_int = 0
81 while pos <= n_buf - n_pat {
82 // Use canonical nx_str_find on the suffix starting at pos.
83 let buf_tail: *u8 = (buf as *u8) + pos
84 let n_tail: nx_int = n_buf - pos
85 let hit: nx_int = nx_str_find(buf_tail, n_tail, pattern, n_pat)
86 if hit < 0 {
87 return count
88 }
89 count = count + 1
90 pos = pos + hit + n_pat // advance past the match
91 }
92 return count
93}
94
95// ===== First occurrence ============================================
96
97func nx_grep_first_offset(buf: *u8, n_buf: nx_int, pattern: *u8, n_pat: nx_int) -> nx_int {
98 if n_pat <= 0 { return -1 }
99 if n_buf < n_pat { return -1 }
100 return nx_str_find(buf, n_buf, pattern, n_pat)
101}
102
103// ===== Any match ==================================================
104
105func nx_grep_any(buf: *u8, n_buf: nx_int, pattern: *u8, n_pat: nx_int) -> nx_int {
106 if nx_grep_first_offset(buf, n_buf, pattern, n_pat) >= 0 {
107 return 1
108 }
109 return 0
110}
111
112// ===== Line number of byte offset =================================
113//
114// Helper: given a byte offset within buf, compute the 1-based line
115// number by counting '\n' bytes before that offset.
116
117func _grep_line_number_at_offset(buf: *u8, off: nx_int) -> nx_int {
118 var line: nx_int = 1
119 var i: nx_int = 0
120 while i < off {
121 if buf[i] == 10 { // '\n'
122 line = line + 1
123 }
124 i = i + 1
125 }
126 return line
127}
128
129// First matching line number (1-based; -1 if no match).
130func nx_grep_first_line_number(buf: *u8, n_buf: nx_int, pattern: *u8, n_pat: nx_int) -> nx_int {
131 let off: nx_int = nx_grep_first_offset(buf, n_buf, pattern, n_pat)
132 if off < 0 { return -1 }
133 return _grep_line_number_at_offset(buf, off)
134}
135
136// ===== Distinct matching lines count ==============================
137//
138// Walk matches; for each, compute its line number; count distinct
139// line numbers. Two matches on the same line count as 1 line.
140//
141// Substrate-honest: for the first stone, we use a simple O(n*m)
142// scan; tournament variants (SIMD line indexing, suffix-array
143// indexed match) land at S5+.
144
145func nx_grep_lines_match_count(buf: *u8, n_buf: nx_int, pattern: *u8, n_pat: nx_int) -> nx_int {
146 if n_pat <= 0 { return 0 }
147 if n_buf < n_pat { return 0 }
148 var distinct_lines: nx_int = 0
149 var last_line_seen: nx_int = -1
150 var pos: nx_int = 0
151 while pos <= n_buf - n_pat {
152 let buf_tail: *u8 = (buf as *u8) + pos
153 let n_tail: nx_int = n_buf - pos
154 let hit: nx_int = nx_str_find(buf_tail, n_tail, pattern, n_pat)
155 if hit < 0 {
156 return distinct_lines
157 }
158 let abs_off: nx_int = pos + hit
159 let line_no: nx_int = _grep_line_number_at_offset(buf, abs_off)
160 if line_no != last_line_seen {
161 distinct_lines = distinct_lines + 1
162 last_line_seen = line_no
163 }
164 pos = abs_off + n_pat
165 }
166 return distinct_lines
167}