wiki.gno
14.24 Kb · 512 lines
1package wiki
2
3import (
4 "errors"
5 "time"
6
7 "gno.land/p/moul/fifo/v0"
8 "gno.land/p/moul/ulist/v0"
9 "gno.land/p/nt/avl/v0"
10)
11
12// Defaults for New. Retention is the number of most-recent revisions per page
13// whose body stays on chain; MaxBody caps a single revision.
14const (
15 DefaultRetention = 3
16 DefaultMaxBody = 32 << 10 // 32 KiB
17 DefaultRecent = 50
18 MaxSummaryLen = 200
19)
20
21var (
22 ErrNoSuchPage = errors.New("wiki: no such page")
23 ErrPageExists = errors.New("wiki: page already exists")
24 ErrBodyTooLarge = errors.New("wiki: body exceeds the size limit")
25 ErrEmptyBody = errors.New("wiki: empty body")
26 ErrNoChange = errors.New("wiki: body is identical to the current revision")
27 ErrSummaryTooLong = errors.New("wiki: edit summary too long")
28 ErrBadProtection = errors.New("wiki: unknown protection level")
29 ErrNoSuchRevision = errors.New("wiki: no such revision")
30 ErrBodyEvicted = errors.New("wiki: that revision's body is no longer held on chain")
31 ErrSpecial = errors.New("wiki: the Special namespace is generated, not stored")
32)
33
34// Wiki is the whole encyclopedia: pages, the indexes derived from them, and
35// the recent-changes feed.
36//
37// Every mutating method takes author, now and height from the caller instead
38// of reading them from the chain, so the engine has no chain imports and the
39// tests drive time and height explicitly.
40type Wiki struct {
41 pages *avl.Tree // Title.Key() -> *Page
42 backlinks *avl.Tree // target Title.Key() -> *avl.Tree (source key -> Title)
43 cats *avl.Tree // category Title.Key() -> *avl.Tree (member key -> Title)
44 talk *avl.Tree // Title.Key() -> *ulist.List of *Comment (see talk.gno)
45 recent *fifo.List
46
47 nextRev uint64
48 nextComment uint64
49 retention int
50 maxBody int
51
52 numPages int // pages with at least one revision and not blanked
53 numRevs int
54 numComments int
55 bytesHeld int // retained body and comment bytes, the realm's visible rent
56}
57
58// New returns an empty wiki. A retention or maxBody below 1 falls back to the
59// package default.
60func New(retention, maxBody int) *Wiki {
61 if retention < 1 {
62 retention = DefaultRetention
63 }
64 if maxBody < 1 {
65 maxBody = DefaultMaxBody
66 }
67 return &Wiki{
68 pages: avl.NewTree(),
69 backlinks: avl.NewTree(),
70 cats: avl.NewTree(),
71 talk: avl.NewTree(),
72 recent: fifo.New(DefaultRecent),
73 retention: retention,
74 maxBody: maxBody,
75 }
76}
77
78// Stats is a snapshot of the wiki's size and of what it is paying for.
79type Stats struct {
80 Pages int
81 Revisions int
82 Comments int
83 BytesHeld int // bytes of article text and comments currently on chain
84 Retention int
85}
86
87// Stats returns the current counters.
88func (w *Wiki) Stats() Stats {
89 return Stats{
90 Pages: w.numPages,
91 Revisions: w.numRevs,
92 Comments: w.numComments,
93 BytesHeld: w.bytesHeld,
94 Retention: w.retention,
95 }
96}
97
98// Page returns the page stored at raw, without following redirects.
99func (w *Wiki) Page(raw string) (*Page, error) {
100 t, err := ParseTitle(raw)
101 if err != nil {
102 return nil, err
103 }
104 return w.PageByTitle(t)
105}
106
107// PageByTitle is Page for an already-parsed title.
108func (w *Wiki) PageByTitle(t Title) (*Page, error) {
109 v := w.pages.Get(t.Key())
110 if v == nil {
111 return nil, ErrNoSuchPage
112 }
113 return v.(*Page), nil
114}
115
116// Exists reports whether a title has a page. A blanked page still exists: its
117// history is the point of the wiki.
118func (w *Wiki) Exists(t Title) bool { return w.pages.Has(t.Key()) }
119
120// Resolve follows at most one redirect hop and returns the destination page
121// along with the page that was asked for. MediaWiki also stops at one hop:
122// chains are a vandalism vector and a loop is unrenderable.
123func (w *Wiki) Resolve(raw string) (dest, asked *Page, err error) {
124 p, err := w.Page(raw)
125 if err != nil {
126 return nil, nil, err
127 }
128 if p.redirect == "" {
129 return p, p, nil
130 }
131 target, err := w.Page(p.redirect)
132 if err != nil {
133 return p, p, nil // dangling redirect: render the stub itself
134 }
135 return target, p, nil
136}
137
138// Edit writes a new revision. It does not check authority: the caller decides
139// who may write, using Page.Protection and whatever roster it keeps. Passing a
140// body byte-identical to the current one is an error, so a no-op edit cannot
141// be used to spam the history or the recent-changes feed.
142func (w *Wiki) Edit(author address, now time.Time, height int64, raw, body, summary string, minor bool) (*Revision, error) {
143 t, err := ParseTitle(raw)
144 if err != nil {
145 return nil, err
146 }
147 if t.NS == NSSpecial {
148 return nil, ErrSpecial
149 }
150 if body == "" {
151 return nil, ErrEmptyBody
152 }
153 if len(body) > w.maxBody {
154 return nil, ErrBodyTooLarge
155 }
156 if len(summary) > MaxSummaryLen {
157 return nil, ErrSummaryTooLong
158 }
159
160 p, _ := w.PageByTitle(t)
161 kind := KindEdit
162 if p == nil {
163 kind = KindCreate
164 } else if p.head != nil && p.head.Hash == hashBody(body) {
165 return nil, ErrNoChange
166 }
167 return w.commit(p, t, author, now, height, body, summary, kind, minor), nil
168}
169
170// Revert restores the body of an earlier revision as a new revision, the way
171// a wiki undo works: the vandalized revision stays in the history, it is just
172// no longer current. It fails if that revision's body has aged out of the
173// retention window, which is the honest failure mode of a bounded history.
174func (w *Wiki) Revert(author address, now time.Time, height int64, raw string, revID uint64, summary string) (*Revision, error) {
175 p, err := w.Page(raw)
176 if err != nil {
177 return nil, err
178 }
179 old := p.Revision(revID)
180 if old == nil {
181 return nil, ErrNoSuchRevision
182 }
183 body, ok := old.Body()
184 if !ok {
185 return nil, ErrBodyEvicted
186 }
187 if p.head != nil && p.head.Hash == old.Hash {
188 return nil, ErrNoChange
189 }
190 if len(summary) > MaxSummaryLen {
191 return nil, ErrSummaryTooLong
192 }
193 return w.commit(p, p.Title, author, now, height, body, summary, KindRevert, false), nil
194}
195
196// Blank replaces a page's content with a tombstone revision. It is the
197// deletion a chain can honestly offer: the page stops rendering and stops
198// costing rent as its bodies age out, while the revision spine stays as proof
199// that something was there and who removed it. Use Purge to release the
200// retained bytes immediately.
201func (w *Wiki) Blank(author address, now time.Time, height int64, raw, reason string) (*Revision, error) {
202 p, err := w.Page(raw)
203 if err != nil {
204 return nil, err
205 }
206 if len(reason) > MaxSummaryLen {
207 return nil, ErrSummaryTooLong
208 }
209 rev := w.commit(p, p.Title, author, now, height, "", reason, KindBlank, false)
210 if !p.Blanked {
211 p.Blanked = true
212 w.numPages--
213 }
214 return rev, nil
215}
216
217// Purge evicts every retained body of a page immediately and returns the
218// number of bytes released. The spine, including each body's hash, is
219// untouched. This is the lever for content that must stop being served from
220// realm state; it cannot and does not remove the transactions that wrote it.
221func (w *Wiki) Purge(raw string) (int, error) {
222 p, err := w.Page(raw)
223 if err != nil {
224 return 0, err
225 }
226 released := 0
227 p.revs.Iterator(0, p.revs.Size()-1, func(_ int, v any) bool {
228 released += v.(*Revision).evict()
229 return false
230 })
231 w.bytesHeld -= released
232 return released, nil
233}
234
235// Move renames a page, keeping its history, and leaves a redirect behind at
236// the old title so existing links keep resolving.
237func (w *Wiki) Move(author address, now time.Time, height int64, from, to, summary string) error {
238 src, err := w.Page(from)
239 if err != nil {
240 return err
241 }
242 dst, err := ParseTitle(to)
243 if err != nil {
244 return err
245 }
246 if dst.NS == NSSpecial {
247 return ErrSpecial
248 }
249 if w.Exists(dst) {
250 return ErrPageExists
251 }
252
253 old := src.Title
254 w.unindex(src)
255 w.pages.Remove(old.Key())
256 src.Title = dst
257 w.pages.Set(dst.Key(), src)
258 w.index(src)
259
260 w.pushRecent(src.Title, w.metaRevision(src, author, now, height, "moved from "+old.String(), KindMove))
261
262 stub := "#REDIRECT [[" + dst.String() + "]]\n"
263 w.commit(nil, old, author, now, height, stub, "moved to "+dst.String(), KindMove, false)
264 return nil
265}
266
267// SetProtection changes a page's edit gate.
268func (w *Wiki) SetProtection(author address, now time.Time, height int64, raw, level string) error {
269 p, err := w.Page(raw)
270 if err != nil {
271 return err
272 }
273 lvl, err := ParseProtection(level)
274 if err != nil {
275 return err
276 }
277 p.Protection = lvl
278 w.pushRecent(p.Title, w.metaRevision(p, author, now, height, "protection: "+lvl.String(), KindProtect))
279 return nil
280}
281
282// metaRevision records an event that changed a page without changing its text
283// (a move, a protection change). It carries no body of its own and inherits
284// the current revision's hash and size, so the history reads as "this is still
285// the same text" instead of "the article was blanked".
286func (w *Wiki) metaRevision(p *Page, author address, now time.Time, height int64, summary string, kind Kind) *Revision {
287 rev := w.newRevision(p, author, now, height, "", summary, kind, true)
288 rev.kept = false
289 if p.head != nil {
290 rev.Hash = p.head.Hash
291 rev.Size = p.head.Size
292 }
293 return rev
294}
295
296// commit appends a revision, re-derives the page's indexes from the new body
297// and enforces the retention window. p may be nil, in which case the page is
298// created at t.
299func (w *Wiki) commit(p *Page, t Title, author address, now time.Time, height int64, body, summary string, kind Kind, minor bool) *Revision {
300 if p == nil {
301 p = &Page{Title: t, Created: now, revs: ulist.New()}
302 w.pages.Set(t.Key(), p)
303 w.numPages++
304 } else {
305 w.unindex(p)
306 if p.Blanked && body != "" {
307 p.Blanked = false
308 w.numPages++
309 }
310 }
311
312 rev := w.newRevision(p, author, now, height, body, summary, kind, minor)
313 p.head = rev
314 w.reindex(p, body)
315 w.enforceRetention(p)
316 w.pushRecent(p.Title, rev)
317 return rev
318}
319
320// newRevision allocates the next revision, appends it and accounts its bytes.
321func (w *Wiki) newRevision(p *Page, author address, now time.Time, height int64, body, summary string, kind Kind, minor bool) *Revision {
322 w.nextRev++
323 prev := uint64(0)
324 if n := p.revs.Size(); n > 0 {
325 prev = p.revs.MustGet(n - 1).(*Revision).ID
326 }
327 rev := &Revision{
328 ID: w.nextRev,
329 Prev: prev,
330 Kind: kind,
331 Author: author,
332 Time: now,
333 Height: height,
334 Summary: summary,
335 Hash: hashBody(body),
336 Size: len(body),
337 Minor: minor,
338 body: body,
339 kept: true,
340 }
341 p.revs.Append(rev)
342 w.numRevs++
343 w.bytesHeld += len(body)
344 return rev
345}
346
347// enforceRetention evicts the body that just fell out of the window.
348//
349// It counts only revisions that still hold a body, so bodyless move and
350// protection entries do not push real text out of the window early. One
351// eviction per commit is enough because the window only ever moves by one, and
352// the backward walk is bounded by scanLimit so a page with a long run of meta
353// revisions cannot make a single edit O(history).
354func (w *Wiki) enforceRetention(p *Page) {
355 const scanLimit = 64
356 kept, scanned := 0, 0
357 p.revs.Iterator(p.revs.Size()-1, 0, func(_ int, v any) bool {
358 scanned++
359 r := v.(*Revision)
360 if !r.kept {
361 return scanned >= scanLimit
362 }
363 kept++
364 if kept > w.retention {
365 w.bytesHeld -= r.evict()
366 return true
367 }
368 return scanned >= scanLimit
369 })
370}
371
372func (w *Wiki) pushRecent(t Title, r *Revision) {
373 w.recent.Prepend(&Change{Title: t, Rev: r})
374}
375
376// Recent returns up to n changes, newest first.
377func (w *Wiki) Recent(n int) []*Change {
378 out := []*Change{}
379 for _, e := range w.recent.Entries() {
380 if len(out) >= n {
381 break
382 }
383 out = append(out, e.(*Change))
384 }
385 return out
386}
387
388// reindex derives the page's redirect target, outgoing links and categories
389// from body, and writes them into the wiki-wide indexes.
390func (w *Wiki) reindex(p *Page, body string) {
391 p.redirect = redirectTarget(body)
392 p.links = nil
393 p.cats = nil
394
395 for _, raw := range ScanLinks(body, "[[", "]]") {
396 t, err := ParseTitle(raw.Target)
397 if err != nil || t == p.Title {
398 continue
399 }
400 if t.NS == NSCategory && !raw.Explicit {
401 p.cats = appendUnique(p.cats, t.Key())
402 continue
403 }
404 p.links = appendUnique(p.links, t.Key())
405 }
406 w.index(p)
407}
408
409// index adds the page to every index its current content implies.
410func (w *Wiki) index(p *Page) {
411 for _, key := range p.links {
412 addTo(w.backlinks, key, p)
413 }
414 for _, key := range p.cats {
415 addTo(w.cats, key, p)
416 }
417}
418
419// unindex removes the page from every index, so the next reindex starts clean.
420func (w *Wiki) unindex(p *Page) {
421 for _, key := range p.links {
422 removeFrom(w.backlinks, key, p.Title.Key())
423 }
424 for _, key := range p.cats {
425 removeFrom(w.cats, key, p.Title.Key())
426 }
427}
428
429func addTo(idx *avl.Tree, key string, p *Page) {
430 v := idx.Get(key)
431 var set *avl.Tree
432 if v == nil {
433 set = avl.NewTree()
434 idx.Set(key, set)
435 } else {
436 set = v.(*avl.Tree)
437 }
438 set.Set(p.Title.Key(), p.Title)
439}
440
441func removeFrom(idx *avl.Tree, key, member string) {
442 v := idx.Get(key)
443 if v == nil {
444 return
445 }
446 set := v.(*avl.Tree)
447 set.Remove(member)
448 if set.Size() == 0 {
449 idx.Remove(key)
450 }
451}
452
453func members(idx *avl.Tree, key string) []Title {
454 out := []Title{}
455 v := idx.Get(key)
456 if v == nil {
457 return out
458 }
459 v.(*avl.Tree).Iterate("", "", func(_ string, val any) bool {
460 out = append(out, val.(Title))
461 return false
462 })
463 return out
464}
465
466// Backlinks returns the titles whose current revision links to t, in key
467// order. Redlinks are indexed too, so a page created later immediately knows
468// who was already pointing at it.
469func (w *Wiki) Backlinks(t Title) []Title { return members(w.backlinks, t.Key()) }
470
471// CategoryMembers returns the pages that declare [[Category:name]].
472func (w *Wiki) CategoryMembers(t Title) []Title { return members(w.cats, t.Key()) }
473
474// Categories returns every category that has at least one member.
475func (w *Wiki) Categories() []Title {
476 out := []Title{}
477 w.cats.Iterate("", "", func(key string, _ any) bool {
478 out = append(out, Title{NS: NSCategory, Name: key[len(NSCategory.Prefix()):]})
479 return false
480 })
481 return out
482}
483
484// Titles returns up to count page titles in key order, skipping offset of
485// them. An empty ns prefix walks every namespace.
486func (w *Wiki) Titles(prefix string, offset, count int) []Title {
487 out := []Title{}
488 skipped := 0
489 w.pages.Iterate(prefix, "", func(key string, v any) bool {
490 if prefix != "" && !hasPrefix(key, prefix) {
491 return true
492 }
493 if skipped < offset {
494 skipped++
495 return false
496 }
497 out = append(out, v.(*Page).Title)
498 return len(out) >= count
499 })
500 return out
501}
502
503func hasPrefix(s, p string) bool { return len(s) >= len(p) && s[:len(p)] == p }
504
505func appendUnique(list []string, v string) []string {
506 for _, e := range list {
507 if e == v {
508 return list
509 }
510 }
511 return append(list, v)
512}
