Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

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}