render_example_test.gno
4.19 Kb · 83 lines
1package globdemo
2
3// ExampleRender pins the realm Render output as a testable example.
4//
5// The block below is copied verbatim from what gno printed, never hand
6// typed: every verdict in it is computed by the library under test, so a
7// change in the matcher shows up here as a diff rather than as prose.
8func ExampleRender() {
9 print(Render(""))
10 // Output:
11 // # Glob
12 //
13 // Shell-style pattern matching, demoing the [`p/moul/x/daily/glob`](/p/moul/x/daily/glob/v0) library. Two modes: `Match`, where `*` crosses everything, and `MatchPath`, where `/` is a boundary only `**` crosses.
14 //
15 // ## The grammar
16 //
17 // | token | matches | pattern | subject | Match |
18 // | --- | --- | --- | --- | --- |
19 // | `?` | any single byte | `a?c` | `abc` | yes |
20 // | `*` | any run of bytes, including none | `a*c` | `abbbc` | yes |
21 // | `[abc]` | any one of the listed bytes | `[abc]x` | `bx` | yes |
22 // | `[a-z]` | any byte in the range, ends included | `[a-z]1` | `q1` | yes |
23 // | `[!a-z]` | any byte NOT listed | `[!a-z]1` | `Q1` | yes |
24 // | `\*` | the literal byte after the backslash | `a\*c` | `a*c` | yes |
25 //
26 // Matching is by byte, not by rune. `?` matches one byte, so it takes two of them to cover a single `é`, and a class range compares byte values. The subjects this package is for, package paths and bech32 addresses, are ASCII.
27 //
28 // ## The two modes
29 //
30 // | pattern | subject | Match | MatchPath |
31 // | --- | --- | --- | --- |
32 // | `gno.land/*` | `gno.land/home` | yes | yes |
33 // | `gno.land/*` | `gno.land/r/moul/home` | yes | no |
34 // | `gno.land/**` | `gno.land/r/moul/home` | yes | yes |
35 // | `*/home` | `gno.land/r/moul/home` | yes | no |
36 // | `**/home` | `gno.land/r/moul/home` | yes | yes |
37 //
38 // `*` and `?` and a class stay inside one segment under `MatchPath`. A `**` that is a whole segment crosses as many segments as it needs, including none, so `a/**/b` matches `a/b`.
39 //
40 // ## The allowlist
41 //
42 // The reason the package exists. Two rules, six candidate paths, one boolean each:
43 //
44 // | rule | kind |
45 // | --- | --- |
46 // | `gno.land/r/moul/home` | one exact path |
47 // | `gno.land/r/moul/x/daily/**` | that subtree, any depth |
48 //
49 // | candidate path | AnyPath | HasPrefix |
50 // | --- | --- | --- |
51 // | `gno.land/r/moul/home` | yes | yes |
52 // | `gno.land/r/moul/x/daily/globdemo` | yes | yes |
53 // | `gno.land/r/moul/x/daily/glob/deeper` | yes | yes |
54 // | `gno.land/r/moul/blog` | no | no |
55 // | `gno.land/r/moul/homeless` | no | yes |
56 // | `gno.land/r/moul/x/dailyevil/drain` | no | yes |
57 //
58 // The last two rows are the whole argument. `gno.land/r/moul/homeless` and `gno.land/r/moul/x/dailyevil/drain` both pass a `strings.HasPrefix` check against those rules, and neither is inside them: a prefix has no idea where a path segment ends. Registering a sibling name one byte longer than an allowed one is a cheap attack, and the only fix is a matcher that knows the separator.
59 //
60 // ## Valid, and what happens when it is not
61 //
62 // | pattern | Valid | Match against `gno.land/r/moul/home` |
63 // | --- | --- | --- |
64 // | `gno.land/r/moul/**` | yes | yes |
65 // | `[a-z0-9]*` | yes | no |
66 // | `a\*b` | yes | no |
67 // | `[a-z` | no | no |
68 // | `[]` | no | no |
69 // | `abc\` | no | no |
70 //
71 // `Match` has no error return, so a malformed pattern has to be either inert or permissive. It is inert: an allowlist entry with a typo grants nothing instead of granting everything. `Any` skips a bad entry and keeps evaluating the good ones, so one typo costs one rule.
72 //
73 // ## Why the matcher is a loop
74 //
75 // The recursive matcher every glob tutorial shows branches at each `*` and is exponential in the number of them. This one walks forward and remembers a single backtrack point, the most recent star, which is `O(len(pattern) * len(name))` in time and constant in space.
76 //
77 // | pattern | subject | MatchPath |
78 // | --- | --- | --- |
79 // | `a*a*a*a*a*a*b` | `aaaaaaaaaaaaaaaaaaaaaaaa` | no |
80 // | `a*a*a*a*a*a*b` | `aaaaaaaaaaaaaaaaaaaaaaab` | yes |
81 //
82 // Six stars against twenty-four bytes is where the recursive version stops returning. On chain that is not a slow page, it is a gas bomb a caller gets to aim, because the pattern is usually the thing stored and the subject is usually the thing supplied.
83}