patch.gno
12.42 Kb · 468 lines
1package bylaws
2
3import (
4 "strconv"
5 "strings"
6 "unicode/utf8"
7
8 "gno.land/p/onbloc/diff/v0"
9)
10
11// MaxOps bounds the number of ops a decoded patch may carry. DiffTexts
12// output always stays far below it (see maxMyersRunes), so the cap only
13// rejects hand-built pathological payloads at the wire boundary.
14const MaxOps = 16 * 1024
15
16// maxMyersRunes bounds the combined rune length of the texts handed to
17// MyersDiff, whose memory is O((N+M)·D): past the budget, DiffTexts
18// falls back to replacing the whole changed region in one delete+insert
19// (payload ~ proposed size; replay stays linear). The common prefix and
20// suffix are trimmed first, so ordinary human edits — small changes in a
21// large document — stay within budget and get a minimal script.
22const maxMyersRunes = 1024
23
24// OpType is the kind of a patch operation.
25type OpType byte
26
27const (
28 OpKeep OpType = 'K' // keep the next N runes of the base text
29 OpDelete OpType = 'D' // delete the next N runes of the base text
30 OpInsert OpType = 'I' // insert literal text
31)
32
33// Op is one run of a patch's edit script. Keep and Delete address the
34// base text positionally (a rune count), so only Insert carries bytes —
35// a small edit to a large document stays a small patch.
36type Op struct {
37 Type OpType
38 N int // rune count (Keep and Delete only)
39 Text string // inserted literal (Insert only)
40}
41
42// Patch is a verifiable amendment to one document: the edit script that
43// transforms the document's base text into the proposed text, pinned to
44// that base by hash. Apply rejects the patch unless the target currently
45// hashes to Base, so a patch can never be applied to text it was not
46// diffed against.
47type Patch struct {
48 Path string // target document path
49 Base string // hex sha256 of the base text; "" pins "document absent" (create)
50 Ops []Op // edit script, replayed in order against the base text
51}
52
53// IsCreate reports whether the patch creates the document (its base pins
54// "document absent").
55func (p Patch) IsCreate() bool {
56 return p.Base == ""
57}
58
59// IsRemove reports whether applying the patch removes the document (the
60// script deletes the whole base text and inserts nothing).
61func (p Patch) IsRemove() bool {
62 if len(p.Ops) == 0 {
63 return false
64 }
65 for _, op := range p.Ops {
66 if op.Type != OpDelete {
67 return false
68 }
69 }
70 return true
71}
72
73// IsNoop reports whether applying the patch leaves the document set
74// unchanged (the script only keeps text, or creates an empty document).
75// The check is shape-based: a hand-built script that deletes and
76// reinserts identical text is not detected (Diff never produces one).
77func (p Patch) IsNoop() bool {
78 for _, op := range p.Ops {
79 if op.Type != OpKeep {
80 return false
81 }
82 }
83 return true
84}
85
86// Diff builds the patch that changes the document at path to the
87// proposed text: it diffs against the document's current text and pins
88// its hash. A new path yields a create patch; empty proposed text yields
89// a remove patch.
90func (b *Bylaws) Diff(path, proposed string) (Patch, error) {
91 cur, exists := b.Get(path)
92 return DiffTexts(path, cur, proposed, exists)
93}
94
95// DiffTexts builds the patch transforming base into proposed for the
96// document at path. exists reports whether the document currently exists
97// (base must be "" when it does not); a patch built with exists=false
98// creates the document. Both texts must be valid UTF-8 — documents are
99// plaintext, and the invariant keeps Keep/Delete rune math byte-faithful.
100func DiffTexts(path, base, proposed string, exists bool) (Patch, error) {
101 if !IsValidPath(path) {
102 return Patch{}, ErrInvalidPath
103 }
104 if len(proposed) > MaxDocLen {
105 return Patch{}, ErrDocTooLarge
106 }
107 if !utf8.ValidString(base) || !utf8.ValidString(proposed) {
108 return Patch{}, ErrInvalidText
109 }
110 baseHash := ""
111 if exists {
112 baseHash = HashText(base)
113 }
114 return Patch{
115 Path: path,
116 Base: baseHash,
117 Ops: diffOps(base, proposed),
118 }, nil
119}
120
121// diffOps builds the coalesced edit script from base to proposed: trim
122// the common prefix and suffix, Myers-diff the differing middles, and
123// past the maxMyersRunes budget replace the whole middle instead. The
124// trimmed middles differ at both ends (or are empty), so the pieces
125// never need merging with the surrounding Keep ops.
126func diffOps(base, proposed string) []Op {
127 b, p := []rune(base), []rune(proposed)
128
129 pre := 0
130 for pre < len(b) && pre < len(p) && b[pre] == p[pre] {
131 pre++
132 }
133 suf := 0
134 for suf < len(b)-pre && suf < len(p)-pre && b[len(b)-1-suf] == p[len(p)-1-suf] {
135 suf++
136 }
137 bMid, pMid := b[pre:len(b)-suf], p[pre:len(p)-suf]
138
139 ops := []Op{}
140 if pre > 0 {
141 ops = append(ops, Op{Type: OpKeep, N: pre})
142 }
143 if len(bMid)+len(pMid) > maxMyersRunes {
144 if len(bMid) > 0 {
145 ops = append(ops, Op{Type: OpDelete, N: len(bMid)})
146 }
147 if len(pMid) > 0 {
148 ops = append(ops, Op{Type: OpInsert, Text: string(pMid)})
149 }
150 } else {
151 ops = append(ops, coalesce(diff.MyersDiff(string(bMid), string(pMid)))...)
152 }
153 if suf > 0 {
154 ops = append(ops, Op{Type: OpKeep, N: suf})
155 }
156 return ops
157}
158
159// coalesce collapses a per-rune Myers edit script into run-length ops:
160// runs of Keep/Delete become counts, runs of Insert carry their literal.
161func coalesce(edits []diff.Edit) []Op {
162 ops := []Op{}
163 var (
164 lit strings.Builder
165 count int
166 curType OpType
167 have bool
168 )
169 flush := func() {
170 if !have {
171 return
172 }
173 if curType == OpInsert {
174 ops = append(ops, Op{Type: OpInsert, Text: lit.String()})
175 } else {
176 ops = append(ops, Op{Type: curType, N: count})
177 }
178 lit.Reset()
179 count = 0
180 have = false
181 }
182 for _, e := range edits {
183 var t OpType
184 switch e.Type {
185 case diff.EditKeep:
186 t = OpKeep
187 case diff.EditInsert:
188 t = OpInsert
189 default:
190 t = OpDelete
191 }
192 if !have || t != curType {
193 flush()
194 curType = t
195 have = true
196 }
197 if t == OpInsert {
198 lit.WriteRune(e.Char)
199 } else {
200 count++
201 }
202 }
203 flush()
204 return ops
205}
206
207// Apply verifies the patch and amends the document set: the target's
208// current text must hash to the patch base ("" base means the document
209// must not exist), and the edit script must consume exactly that text.
210// An empty result removes the document. Apply is the package's only
211// mutation; on any error the set is unchanged.
212func (b *Bylaws) Apply(p Patch) error {
213 if !IsValidPath(p.Path) {
214 return ErrInvalidPath
215 }
216 cur, exists := b.Get(p.Path)
217 curHash := ""
218 if exists {
219 curHash = HashText(cur)
220 }
221 if p.Base != curHash {
222 return ErrStalePatch
223 }
224 out, err := replay(cur, p.Ops)
225 if err != nil {
226 return err
227 }
228 if len(out) > MaxDocLen {
229 return ErrDocTooLarge
230 }
231 if out == "" {
232 b.docs.Remove(p.Path)
233 return nil
234 }
235 b.docs.Set(p.Path, out)
236 return nil
237}
238
239// replay runs the edit script against the base text: Keep emits base
240// runes and advances, Delete advances, Insert emits its literal. The
241// script must consume the base exactly, so a script that does not fit
242// the text it runs against fails instead of producing garbage.
243func replay(base string, ops []Op) (string, error) {
244 r := []rune(base)
245 var (
246 sb strings.Builder
247 i int
248 )
249 for _, op := range ops {
250 switch op.Type {
251 case OpKeep:
252 if op.N <= 0 || op.N > len(r)-i {
253 return "", ErrInvalidPatch
254 }
255 sb.WriteString(string(r[i : i+op.N]))
256 i += op.N
257 case OpDelete:
258 if op.N <= 0 || op.N > len(r)-i {
259 return "", ErrInvalidPatch
260 }
261 i += op.N
262 case OpInsert:
263 if op.Text == "" {
264 return "", ErrInvalidPatch
265 }
266 sb.WriteString(op.Text)
267 default:
268 return "", ErrInvalidPatch
269 }
270 }
271 if i != len(r) {
272 return "", ErrInvalidPatch
273 }
274 return sb.String(), nil
275}
276
277// Format renders the patch against its base text as a plain-text change
278// summary: kept runs collapse to a marker, deleted and inserted text is
279// shown literally with every line marker-prefixed ("- "/"+ "), so a
280// multi-line literal cannot masquerade as the summary's own markers (an
281// insertion containing "\n- fake" renders as "+ …" and "+ - fake"). It
282// fails like replay when the script does not fit the base. The output is
283// raw text — callers rendering markdown must escape it (the content is
284// document text, and insertions are proposer-controlled).
285func (p Patch) Format(base string) (string, error) {
286 r := []rune(base)
287 var (
288 sb strings.Builder
289 i int
290 )
291 for _, op := range p.Ops {
292 switch op.Type {
293 case OpKeep:
294 if op.N <= 0 || op.N > len(r)-i {
295 return "", ErrInvalidPatch
296 }
297 sb.WriteString("= " + strconv.Itoa(op.N) + " unchanged\n")
298 i += op.N
299 case OpDelete:
300 if op.N <= 0 || op.N > len(r)-i {
301 return "", ErrInvalidPatch
302 }
303 writeMarked(&sb, "- ", string(r[i:i+op.N]))
304 i += op.N
305 case OpInsert:
306 if op.Text == "" {
307 return "", ErrInvalidPatch
308 }
309 writeMarked(&sb, "+ ", op.Text)
310 default:
311 return "", ErrInvalidPatch
312 }
313 }
314 if i != len(r) {
315 return "", ErrInvalidPatch
316 }
317 return sb.String(), nil
318}
319
320// writeMarked writes text with every line prefixed by marker.
321func writeMarked(sb *strings.Builder, marker, text string) {
322 for _, line := range strings.Split(text, "\n") {
323 sb.WriteString(marker)
324 sb.WriteString(line)
325 sb.WriteByte('\n')
326 }
327}
328
329// Encode serializes the patch to a compact single-string payload fit for
330// a transaction argument: "v0:<path>:<base>:" followed by one segment
331// per op — "K<n>;" and "D<n>;" carry rune counts, "I<len>:<bytes>;"
332// carries the inserted literal length-prefixed by its byte length (no
333// escaping needed). DecodePatch is the exact inverse.
334func (p Patch) Encode() string {
335 var sb strings.Builder
336 sb.WriteString("v0:")
337 sb.WriteString(p.Path)
338 sb.WriteByte(':')
339 sb.WriteString(p.Base)
340 sb.WriteByte(':')
341 for _, op := range p.Ops {
342 switch op.Type {
343 case OpKeep, OpDelete:
344 sb.WriteByte(byte(op.Type))
345 sb.WriteString(strconv.Itoa(op.N))
346 case OpInsert:
347 sb.WriteByte(byte(OpInsert))
348 sb.WriteString(strconv.Itoa(len(op.Text)))
349 sb.WriteByte(':')
350 sb.WriteString(op.Text)
351 }
352 sb.WriteByte(';')
353 }
354 return sb.String()
355}
356
357// DecodePatch parses an Encode payload back into a Patch, validating the
358// path, the base hash shape, and every op (counts must be canonical, so
359// DecodePatch accepts exactly Encode's output shape; insert literals
360// must be valid UTF-8, keeping documents plaintext and Keep's rune math
361// byte-faithful). Replay validity against the actual document is Apply's
362// job; DecodePatch only guarantees the patch is well-formed.
363func DecodePatch(s string) (Patch, error) {
364 if !strings.HasPrefix(s, "v0:") {
365 return Patch{}, ErrInvalidPatch
366 }
367 rest := s[len("v0:"):]
368 i := strings.IndexByte(rest, ':')
369 if i < 0 {
370 return Patch{}, ErrInvalidPatch
371 }
372 path := rest[:i]
373 rest = rest[i+1:]
374 if !IsValidPath(path) {
375 return Patch{}, ErrInvalidPath
376 }
377 j := strings.IndexByte(rest, ':')
378 if j < 0 {
379 return Patch{}, ErrInvalidPatch
380 }
381 base := rest[:j]
382 rest = rest[j+1:]
383 if !isValidBase(base) {
384 return Patch{}, ErrInvalidPatch
385 }
386 ops := []Op{}
387 for len(rest) > 0 {
388 if len(ops) == MaxOps {
389 return Patch{}, ErrInvalidPatch
390 }
391 t := OpType(rest[0])
392 rest = rest[1:]
393 switch t {
394 case OpKeep, OpDelete:
395 k := strings.IndexByte(rest, ';')
396 if k < 0 {
397 return Patch{}, ErrInvalidPatch
398 }
399 n, ok := parseCount(rest[:k])
400 if !ok {
401 return Patch{}, ErrInvalidPatch
402 }
403 ops = append(ops, Op{Type: t, N: n})
404 rest = rest[k+1:]
405 case OpInsert:
406 k := strings.IndexByte(rest, ':')
407 if k < 0 {
408 return Patch{}, ErrInvalidPatch
409 }
410 n, ok := parseCount(rest[:k])
411 if !ok {
412 return Patch{}, ErrInvalidPatch
413 }
414 rest = rest[k+1:]
415 if len(rest) < n+1 || rest[n] != ';' {
416 return Patch{}, ErrInvalidPatch
417 }
418 text := rest[:n]
419 if !utf8.ValidString(text) {
420 return Patch{}, ErrInvalidText
421 }
422 ops = append(ops, Op{Type: OpInsert, Text: text})
423 rest = rest[n+1:]
424 default:
425 return Patch{}, ErrInvalidPatch
426 }
427 }
428 return Patch{Path: path, Base: base, Ops: ops}, nil
429}
430
431// parseCount parses a strictly canonical op count: decimal digits with
432// no sign and no leading zero (so Encode∘DecodePatch is the identity on
433// accepted payloads), in (0, MaxDocLen].
434func parseCount(s string) (int, bool) {
435 if s == "" || s[0] == '0' || len(s) > 6 {
436 return 0, false
437 }
438 n := 0
439 for i := 0; i < len(s); i++ {
440 c := s[i]
441 if c < '0' || c > '9' {
442 return 0, false
443 }
444 n = n*10 + int(c-'0')
445 }
446 if n > MaxDocLen {
447 return 0, false
448 }
449 return n, true
450}
451
452// isValidBase reports whether a base is the empty sentinel (create) or a
453// 64-char lowercase hex sha256.
454func isValidBase(base string) bool {
455 if base == "" {
456 return true
457 }
458 if len(base) != 64 {
459 return false
460 }
461 for i := 0; i < len(base); i++ {
462 c := base[i]
463 if !(c >= '0' && c <= '9' || c >= 'a' && c <= 'f') {
464 return false
465 }
466 }
467 return true
468}