globdemo.gno
7.75 Kb · 201 lines
1// Package globdemo is a gnoweb demo of the shell-pattern matcher provided by
2// the [p/moul/x/daily/glob](/p/moul/x/daily/glob/v0) library: the grammar, the
3// two matching modes, and the allowlist the package exists for.
4//
5// It contains no matching logic of its own. Stateless, so Render is
6// deterministic: every verdict below is computed by the library from the fixed
7// tables at the top of this file, never from chain state, which is what lets
8// an example test pin the page.
9package globdemo
10
11import (
12 "strings"
13
14 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
15 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/glob/v0"
16)
17
18// grammar is the token table, each row paired with a subject that exercises it.
19var grammar = []struct {
20 token string
21 meaning string
22 pattern string
23 subject string
24}{
25 {"`?`", "any single byte", "a?c", "abc"},
26 {"`*`", "any run of bytes, including none", "a*c", "abbbc"},
27 {"`[abc]`", "any one of the listed bytes", "[abc]x", "bx"},
28 {"`[a-z]`", "any byte in the range, ends included", "[a-z]1", "q1"},
29 {"`[!a-z]`", "any byte NOT listed", "[!a-z]1", "Q1"},
30 {"`\\*`", "the literal byte after the backslash", `a\*c`, "a*c"},
31}
32
33// modes is the pair of subjects that separate the two modes. Each row is run
34// through both matchers, and the two columns disagree on purpose.
35var modes = []struct {
36 pattern string
37 subject string
38}{
39 {"gno.land/*", "gno.land/home"},
40 {"gno.land/*", "gno.land/r/moul/home"},
41 {"gno.land/**", "gno.land/r/moul/home"},
42 {"*/home", "gno.land/r/moul/home"},
43 {"**/home", "gno.land/r/moul/home"},
44}
45
46// allow is the worked allowlist: what a realm would store to decide which
47// package paths a delegated key may call.
48var allow = []string{
49 "gno.land/r/moul/home",
50 "gno.land/r/moul/x/daily/**",
51}
52
53// subjects are the paths the allowlist is asked about. The last two are the
54// point of the whole table: both pass a naive strings.HasPrefix check against
55// the rules above, and neither is inside them.
56var subjects = []string{
57 "gno.land/r/moul/home",
58 "gno.land/r/moul/x/daily/globdemo",
59 "gno.land/r/moul/x/daily/glob/deeper",
60 "gno.land/r/moul/blog",
61 "gno.land/r/moul/homeless",
62 "gno.land/r/moul/x/dailyevil/drain",
63}
64
65// patterns is the validity table: three well-formed, three typos.
66var patterns = []string{
67 "gno.land/r/moul/**",
68 "[a-z0-9]*",
69 `a\*b`,
70 "[a-z",
71 "[]",
72 `abc\`,
73}
74
75// Render renders the demo for gnoweb.
76//
77// Render("") / Render("/") -> the full demo
78func Render(path string) string {
79 var b strings.Builder
80
81 b.WriteString("# Glob\n\n")
82 b.WriteString("Shell-style pattern matching, demoing the ")
83 b.WriteString("[`p/moul/x/daily/glob`](/p/moul/x/daily/glob/v0) library. ")
84 b.WriteString("Two modes: `Match`, where `*` crosses everything, and ")
85 b.WriteString("`MatchPath`, where `/` is a boundary only `**` crosses.\n\n")
86
87 b.WriteString("## The grammar\n\n")
88 gt := ui.NewTable("token", "matches", "pattern", "subject", "Match")
89 for _, g := range grammar {
90 gt.Row(g.token, g.meaning, code(g.pattern), code(g.subject),
91 verdict(glob.Match(g.pattern, g.subject)))
92 }
93 b.WriteString(gt.String() + "\n")
94 b.WriteString("Matching is by byte, not by rune. `?` matches one byte, so ")
95 b.WriteString("it takes two of them to cover a single `é`, and a class ")
96 b.WriteString("range compares byte values. The subjects this package is ")
97 b.WriteString("for, package paths and bech32 addresses, are ASCII.\n\n")
98
99 b.WriteString("## The two modes\n\n")
100 mt := ui.NewTable("pattern", "subject", "Match", "MatchPath")
101 for _, m := range modes {
102 mt.Row(code(m.pattern), code(m.subject),
103 verdict(glob.Match(m.pattern, m.subject)),
104 verdict(glob.MatchPath(m.pattern, m.subject)))
105 }
106 b.WriteString(mt.String() + "\n")
107 b.WriteString("`*` and `?` and a class stay inside one segment under ")
108 b.WriteString("`MatchPath`. A `**` that is a whole segment crosses as many ")
109 b.WriteString("segments as it needs, including none, so `a/**/b` matches ")
110 b.WriteString("`a/b`.\n\n")
111
112 b.WriteString("## The allowlist\n\n")
113 b.WriteString("The reason the package exists. Two rules, six candidate ")
114 b.WriteString("paths, one boolean each:\n\n")
115 at := ui.NewTable("rule", "kind")
116 at.Row(code(allow[0]), "one exact path")
117 at.Row(code(allow[1]), "that subtree, any depth")
118 b.WriteString(at.String() + "\n")
119 st := ui.NewTable("candidate path", "AnyPath", "HasPrefix")
120 for _, s := range subjects {
121 st.Row(code(s), verdict(glob.AnyPath(allow, s)), verdict(naivePrefix(s)))
122 }
123 b.WriteString(st.String() + "\n")
124 b.WriteString("The last two rows are the whole argument. ")
125 b.WriteString("`gno.land/r/moul/homeless` and ")
126 b.WriteString("`gno.land/r/moul/x/dailyevil/drain` both pass a ")
127 b.WriteString("`strings.HasPrefix` check against those rules, and neither ")
128 b.WriteString("is inside them: a prefix has no idea where a path segment ")
129 b.WriteString("ends. Registering a sibling name one byte longer than an ")
130 b.WriteString("allowed one is a cheap attack, and the only fix is a ")
131 b.WriteString("matcher that knows the separator.\n\n")
132
133 b.WriteString("## Valid, and what happens when it is not\n\n")
134 vt := ui.NewTable("pattern", "Valid", "Match against `gno.land/r/moul/home`")
135 for _, p := range patterns {
136 vt.Row(code(p), verdict(glob.Valid(p)), verdict(glob.MatchPath(p, allow[0])))
137 }
138 b.WriteString(vt.String() + "\n")
139 b.WriteString("`Match` has no error return, so a malformed pattern has to ")
140 b.WriteString("be either inert or permissive. It is inert: an allowlist ")
141 b.WriteString("entry with a typo grants nothing instead of granting ")
142 b.WriteString("everything. `Any` skips a bad entry and keeps evaluating ")
143 b.WriteString("the good ones, so one typo costs one rule.\n\n")
144
145 b.WriteString("## Why the matcher is a loop\n\n")
146 b.WriteString("The recursive matcher every glob tutorial shows branches at ")
147 b.WriteString("each `*` and is exponential in the number of them. This one ")
148 b.WriteString("walks forward and remembers a single backtrack point, the ")
149 b.WriteString("most recent star, which is `O(len(pattern) * len(name))` in ")
150 b.WriteString("time and constant in space.\n\n")
151 bt := ui.NewTable("pattern", "subject", "MatchPath")
152 for _, s := range []string{
153 "aaaaaaaaaaaaaaaaaaaaaaaa",
154 "aaaaaaaaaaaaaaaaaaaaaaab",
155 } {
156 bt.Row(code(bomb), code(s), verdict(glob.MatchPath(bomb, s)))
157 }
158 b.WriteString(bt.String() + "\n")
159 b.WriteString("Six stars against twenty-four bytes is where the recursive ")
160 b.WriteString("version stops returning. On chain that is not a slow page, ")
161 b.WriteString("it is a gas bomb a caller gets to aim, because the pattern ")
162 b.WriteString("is usually the thing stored and the subject is usually the ")
163 b.WriteString("thing supplied.\n")
164
165 return b.String()
166}
167
168// bomb is the pattern that makes a recursive matcher blow up. Kept as a
169// constant so the two rows of the last table cannot drift apart.
170const bomb = "a*a*a*a*a*a*b"
171
172// naivePrefix is the wrong implementation, kept so the page can show it being
173// wrong rather than assert it. It is what an allowlist looks like before
174// somebody notices that a prefix does not know where a segment ends.
175func naivePrefix(path string) bool {
176 for _, rule := range allow {
177 if strings.HasPrefix(path, strings.TrimSuffix(rule, "/**")) {
178 return true
179 }
180 }
181 return false
182}
183
184// verdict renders a boolean as a symbol, so a column of them reads at a glance.
185func verdict(ok bool) string {
186 if ok {
187 return "yes"
188 }
189 return "no"
190}
191
192// code wraps s in a markdown code span.
193//
194// A pipe is escaped rather than passed to ui.Cell: inside a code span
195// CommonMark performs no backslash escapes, so ui.Cell's output would render
196// its own backslashes literally. Nothing on this page contains a pipe today,
197// and the escape is here so that adding a pattern with one does not silently
198// open a column.
199func code(s string) string {
200 return "`" + strings.ReplaceAll(s, "|", `\|`) + "`"
201}