ahocorasickdemo.gno

  1// Package ahocorasickdemo is a small gnoweb demo of the
  2// [p/moul/x/daily/ahocorasick](/p/moul/x/daily/ahocorasick/v0) library: it runs
  3// one automaton over a text once and shows the overlapping matches a k-pass
  4// scan would have to pay k passes for.
  5//
  6// It contains no search logic of its own. Stateless, so Render is
  7// deterministic.
  8package ahocorasickdemo
  9
 10import (
 11	"strconv"
 12	"strings"
 13
 14	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
 15	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
 16	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/ahocorasick/v0"
 17)
 18
 19// Fixed inputs, never chain state: a demo whose output moves with the block
 20// height cannot be pinned by an example test.
 21var (
 22	textbookPatterns = []string{"he", "she", "his", "hers"}
 23	textbookText     = "ushers"
 24
 25	dictPatterns = []string{"the", "he", "fox", "over", "lazy"}
 26	sentence     = "the quick brown fox jumps over the lazy dog"
 27
 28	textbook = ahocorasick.New(textbookPatterns)
 29	dict     = ahocorasick.New(dictPatterns)
 30)
 31
 32// Render renders the demo for gnoweb.
 33//
 34//	Render("") / Render("/")  -> the textbook automaton and the sentence scan
 35//	Render("/<text>")         -> scan that text with the same dictionary
 36func Render(path string) string {
 37	var b strings.Builder
 38	b.WriteString("# Aho-Corasick\n\n")
 39	b.WriteString("One automaton for the whole dictionary, one pass over the text, ")
 40	b.WriteString("demoing the [`p/moul/x/daily/ahocorasick`](/p/moul/x/daily/ahocorasick/v0) library.\n\n")
 41
 42	if arg := parseArg(path); arg != "" {
 43		b.WriteString(renderScan(arg))
 44		return b.String()
 45	}
 46
 47	b.WriteString("## The 1975 example\n\n")
 48	b.WriteString("Patterns " + list(textbookPatterns) + " over " + md.InlineCode(textbookText) + ". ")
 49	b.WriteString("Three of the four overlap, and `hers` ends where nothing else starts.\n\n")
 50	b.WriteString(matchTable(textbook, textbookText))
 51
 52	b.WriteString("\n## One pass over a sentence\n\n")
 53	b.WriteString("Patterns " + list(dictPatterns) + " over " + md.InlineCode(sentence) + ".\n\n")
 54	b.WriteString(matchTable(dict, sentence))
 55
 56	b.WriteString("\n")
 57	b.WriteString(stats(dict, sentence))
 58
 59	b.WriteString("\n> Scan your own text: append it to the path, for instance ")
 60	b.WriteString("[`/thermos`](/r/moul/x/daily/ahocorasickdemo/v0:/thermos), ")
 61	b.WriteString("where `the` and `he` overlap on the same three letters.\n")
 62	return b.String()
 63}
 64
 65// renderScan scans the visitor's text with the sentence dictionary.
 66//
 67// The argument is the visitor's text and it is shown inside a code span, so it
 68// goes through md.InlineCode and not ui.Cell: a cell escaper backslashes a
 69// backtick, and a backslash does not close a backtick inside a span. Only a
 70// fence wider than anything in the argument does, which is what md.InlineCode
 71// picks. The table itself only ever holds offsets and dictionary words, never
 72// a slice of the argument.
 73func renderScan(arg string) string {
 74	var b strings.Builder
 75	b.WriteString("## ")
 76	b.WriteString(md.InlineCode(arg))
 77	b.WriteString("\n\nPatterns " + list(dictPatterns) + ".\n\n")
 78
 79	ms := dict.FindAll(arg)
 80	if len(ms) == 0 {
 81		b.WriteString("No pattern occurs in it.\n")
 82		return b.String()
 83	}
 84	b.WriteString(matchTable(dict, arg))
 85	b.WriteString("\n")
 86	b.WriteString(stats(dict, arg))
 87	return b.String()
 88}
 89
 90// matchTable renders every match as offsets plus the pattern that matched.
 91// It never echoes a slice of the scanned text: the pattern is already the
 92// matched bytes, and it comes from the fixed dictionary rather than from the
 93// caller.
 94func matchTable(m *ahocorasick.Matcher, text string) string {
 95	ms := m.FindAll(text)
 96	t := ui.NewTable("start", "end", "pattern")
 97	for _, match := range ms {
 98		t.Row(
 99			"`"+strconv.Itoa(match.Start)+"`",
100			"`"+strconv.Itoa(match.End)+"`",
101			"`"+match.Pattern+"`",
102		)
103	}
104	return t.String()
105}
106
107// stats says what the pass actually cost, which is the whole claim: the text
108// is read once whatever the dictionary holds.
109func stats(m *ahocorasick.Matcher, text string) string {
110	return "`" + strconv.Itoa(len(m.Patterns())) + "` patterns, `" +
111		strconv.Itoa(m.Nodes()) + "` automaton nodes, `" +
112		strconv.Itoa(len(text)) + "` bytes read once, `" +
113		strconv.Itoa(len(m.FindAll(text))) + "` matches. " +
114		"Running a single-pattern scan per word would read those bytes `" +
115		strconv.Itoa(len(m.Patterns())) + "` times instead.\n"
116}
117
118// list renders a pattern set as code spans. The patterns are this file's own
119// constants, never the caller's.
120func list(patterns []string) string {
121	parts := make([]string, 0, len(patterns))
122	for _, p := range patterns {
123		parts = append(parts, "`"+p+"`")
124	}
125	return strings.Join(parts, ", ")
126}
127
128// parseArg takes the one routing slash off and nothing else. It does not cut
129// at a later slash and it does not trim: a page that offers to scan what the
130// caller typed either scans that string or says it found nothing, and never
131// quietly substitutes a shorter or tidier one.
132func parseArg(path string) string {
133	return strings.TrimPrefix(path, "/")
134}