shuntingyarddemo.gno
8.38 Kb · 239 lines
1// Package shuntingyarddemo is a small gnoweb demo of the
2// [p/moul/x/daily/shuntingyard](/p/moul/x/daily/shuntingyard/v0) library: it
3// shows the three stages of the algorithm (tokens, reverse Polish notation,
4// value) and the refusals that make it safe to point at a caller's string.
5//
6// It contains no parsing or arithmetic of its own, and it has no state. The
7// root page is computed from the fixed tables at the top of this file, never
8// from chain state, which is what lets an example test pin it; the `?e=`
9// page is computed from the query alone, which is still a pure function of
10// its input and therefore equally pinnable.
11package shuntingyarddemo
12
13import (
14 "net/url"
15 "strconv"
16 "strings"
17
18 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
19 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/realmpath/v0"
20 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/shuntingyard/v0"
21)
22
23// selfPath is where this realm answers, used to build the try-it links.
24const selfPath = "/r/moul/x/daily/shuntingyarddemo/v0:"
25
26// worked are the expressions on the root page. Each one is here because it
27// groups in a way the naive left-to-right reading gets wrong.
28var worked = []struct {
29 expr string
30 why string
31}{
32 {"2+3*4", "multiplication binds tighter"},
33 {"(2+3)*4", "parentheses beat precedence"},
34 {"10-3-2", "subtraction associates left"},
35 {"2^3^2", "but power associates right"},
36 {"-3^2", "a prefix minus binds looser than a power"},
37 {"3*-2", "the same byte, now unary, after an operator"},
38 {"-7/2", "integer division truncates toward zero"},
39 {"-7%2", "and the remainder keeps the dividend's sign"},
40}
41
42// refused are the inputs worth showing precisely because nothing panics on
43// them. A realm that renders a stored expression is one bad input away from a
44// permanently broken page, and a public path cannot be redeployed.
45var refused = []string{
46 "1/0",
47 "2^-1",
48 "9223372036854775807+1",
49 "2^64",
50 "1 2",
51 "(1",
52 "1$2",
53}
54
55// Render renders the demo for gnoweb.
56//
57// Render("") -> the demo page
58// Render("?e=<expr>") -> the three stages for one expression
59func Render(path string) string {
60 req := realmpath.Parse(path)
61 // Any non-empty `e` goes to the per-expression page, including one that is
62 // only whitespace: the parser already answers that with "unexpected end of
63 // expression at offset 0", which is a better page than silently showing the
64 // index to someone who asked a question.
65 if expr := req.Query.Get("e"); expr != "" {
66 return renderOne(expr)
67 }
68 return renderIndex()
69}
70
71// renderIndex is the fixed page: what the algorithm does, and what it refuses.
72func renderIndex() string {
73 var b strings.Builder
74
75 b.WriteString("# Shunting-yard\n\n")
76 b.WriteString("Dijkstra's 1961 algorithm, demoing the ")
77 b.WriteString("[`p/moul/x/daily/shuntingyard`](/p/moul/x/daily/shuntingyard/v0) ")
78 b.WriteString("library: an infix expression becomes reverse Polish notation ")
79 b.WriteString("in one left-to-right pass, with one stack and no recursion, ")
80 b.WriteString("and the RPN evaluates with one more stack.\n\n")
81
82 b.WriteString("## Worked examples\n\n")
83 wt := ui.NewTable("expression", "RPN", "value", "why it is here")
84 for _, w := range worked {
85 rpn, value := trace(w.expr)
86 wt.Row("`"+w.expr+"`", "`"+rpn+"`", "`"+value+"`", w.why)
87 }
88 b.WriteString(wt.String() + "\n")
89 b.WriteString("Every cell above is computed by the library at render time. ")
90 b.WriteString("The RPN column is the whole output of the conversion: an ")
91 b.WriteString("expression that groups surprisingly groups visibly.\n\n")
92
93 b.WriteString("## The precedence table is the parser\n\n")
94 b.WriteString("Grouping is data here, not control flow. These eight rows are ")
95 b.WriteString("the only thing that decides how an expression reads, which is ")
96 b.WriteString("why adding an operator is a row rather than a branch.\n\n")
97 pt := ui.NewTable("operator", "precedence", "associativity", "arity")
98 for _, op := range shuntingyard.Operators() {
99 assoc := "left"
100 if op.Right {
101 assoc = "right"
102 }
103 arity := "binary"
104 if op.Unary {
105 arity = "unary prefix"
106 }
107 pt.Row("`"+op.Op+"`", strconv.Itoa(op.Prec), assoc, arity)
108 }
109 b.WriteString(pt.String() + "\n")
110 b.WriteString("`u-` and `u+` are the prefix forms. They are separate ")
111 b.WriteString("operators rather than a flag on `-` and `+` because they ")
112 b.WriteString("take one operand instead of two and sit at a different ")
113 b.WriteString("precedence, and conflating the two is how a parser ends up ")
114 b.WriteString("reading `-3^2` as `9`.\n\n")
115
116 b.WriteString("## What it refuses\n\n")
117 b.WriteString("None of these panics. A realm that evaluates a stored ")
118 b.WriteString("expression inside `Render` cannot be made permanently ")
119 b.WriteString("unreadable by one bad input, and an expression that would ")
120 b.WriteString("wrap `int64` says so instead of returning a plausible wrong ")
121 b.WriteString("amount.\n\n")
122 rt := ui.NewTable("expression", "error")
123 for _, src := range refused {
124 _, err := shuntingyard.Eval(src)
125 msg := "no error"
126 if err != nil {
127 msg = err.Error()
128 }
129 rt.Row("`"+src+"`", ui.Cell(msg))
130 }
131 b.WriteString(rt.String() + "\n")
132
133 b.WriteString("## Try one\n\n")
134 links := make([]string, 0, len(worked))
135 for _, w := range worked {
136 links = append(links, tryLink(w.expr))
137 }
138 b.WriteString(strings.Join(links, " · ") + "\n\n")
139 b.WriteString("Or append your own: `?e=2*(3+4)`.\n")
140
141 return b.String()
142}
143
144// renderOne shows the three stages for one caller-supplied expression.
145//
146// The raw query string and every error message go through ui.Inline: both can
147// carry whatever byte the caller sent, and until they are escaped they are
148// attacker-controlled markdown.
149//
150// Tokens and the RPN do not, and are shown as code spans instead. Tokenize
151// accepts a closed alphabet (digits, parentheses and the six operator bytes)
152// and rejects everything else, so a token can only ever spell itself. Running
153// those through ui.Inline would put a literal backslash inside a code span,
154// where markdown does not process escapes, so escaping there makes the page
155// wrong rather than safer.
156func renderOne(expr string) string {
157 var b strings.Builder
158
159 b.WriteString("# Shunting-yard: " + ui.Inline(expr) + "\n\n")
160 b.WriteString("[back to the demo](" + selfPath + ")\n\n")
161
162 toks, err := shuntingyard.Tokenize(expr)
163 if err != nil {
164 b.WriteString("## Rejected while reading it\n\n")
165 b.WriteString(ui.Inline(err.Error()) + "\n")
166 return b.String()
167 }
168
169 b.WriteString("## Tokens\n\n")
170 tt := ui.NewTable("#", "kind", "token", "offset")
171 for i, tok := range toks {
172 tt.Row(strconv.Itoa(i), kindName(tok.Kind), "`"+tok.String()+"`", strconv.Itoa(tok.Pos))
173 }
174 b.WriteString(tt.OrEmpty("Nothing to tokenize.") + "\n")
175
176 rpn, err := shuntingyard.ToRPN(toks)
177 if err != nil {
178 b.WriteString("## Rejected while converting it\n\n")
179 b.WriteString(ui.Inline(err.Error()) + "\n")
180 return b.String()
181 }
182
183 b.WriteString("## Reverse Polish notation\n\n")
184 b.WriteString("`" + shuntingyard.FormatRPN(rpn) + "`\n\n")
185
186 value, err := shuntingyard.EvalRPN(rpn)
187 if err != nil {
188 b.WriteString("## Rejected while evaluating it\n\n")
189 b.WriteString(ui.Inline(err.Error()) + "\n")
190 return b.String()
191 }
192
193 b.WriteString("## Value\n\n")
194 b.WriteString("`" + strconv.FormatInt(value, 10) + "`\n")
195
196 return b.String()
197}
198
199// trace returns the RPN and the value of an expression, as display strings. A
200// failure renders as its error, because the refusals are part of the demo.
201func trace(expr string) (string, string) {
202 toks, err := shuntingyard.Tokenize(expr)
203 if err != nil {
204 return "", err.Error()
205 }
206 rpn, err := shuntingyard.ToRPN(toks)
207 if err != nil {
208 return "", err.Error()
209 }
210 value, err := shuntingyard.EvalRPN(rpn)
211 if err != nil {
212 return shuntingyard.FormatRPN(rpn), err.Error()
213 }
214 return shuntingyard.FormatRPN(rpn), strconv.FormatInt(value, 10)
215}
216
217// tryLink builds a link to this realm's own ?e= page.
218//
219// The escape is not decoration: a '+' in a query string decodes to a space,
220// so an unescaped "2+3" would reach the parser as "2 3" and be rejected as
221// two numbers in a row.
222func tryLink(expr string) string {
223 return "[`" + expr + "`](" + selfPath + "?e=" + url.QueryEscape(expr) + ")"
224}
225
226// kindName names a token kind for the table.
227func kindName(k shuntingyard.Kind) string {
228 switch k {
229 case shuntingyard.KindNumber:
230 return "number"
231 case shuntingyard.KindOperator:
232 return "operator"
233 case shuntingyard.KindLParen:
234 return "("
235 case shuntingyard.KindRParen:
236 return ")"
237 }
238 return "?"
239}