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.

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}