diff.gno

  1package wiki
  2
  3import "strings"
  4
  5// DiffOp is what happened to one line between two revisions.
  6type DiffOp uint8
  7
  8const (
  9	OpEqual DiffOp = iota
 10	OpInsert
 11	OpDelete
 12)
 13
 14// DiffLine is one line of a rendered diff.
 15type DiffLine struct {
 16	Op   DiffOp
 17	Text string
 18}
 19
 20// DiffMaxLines bounds the changed region a diff will compute exactly.
 21//
 22// The cost of an LCS over the changed region is O(n*m), and this runs inside
 23// vm/qrender, which has a gas ceiling a reader cannot raise. 80 lines caps the
 24// table at 6,400 cells; beyond it, a diff degrades to "this block was replaced"
 25// rather than making the page unrenderable. Both revisions are still available
 26// in full through the raw view, so nothing is hidden by the degradation.
 27const DiffMaxLines = 80
 28
 29// TODO(#140 Q5): decide whether diffing belongs on chain at all. Both options
 30// are still open: keep this bounded server-side diff, or drop it and let
 31// clients diff two /raw responses themselves, which costs the chain nothing
 32// and removes DiffMaxLines entirely. Keeping it for now because a diff a
 33// reader can reach from a plain URL is most of what makes a history readable,
 34// and 691M gas at the body cap leaves room. Revisit if MaxBody ever rises.
 35
 36// DiffLines compares two bodies line by line.
 37//
 38// exact reports whether the result is a real line diff. When it is false the
 39// changed region was larger than DiffMaxLines and the result is the coarse
 40// form: every removed line, then every added line.
 41func DiffLines(older, newer string) (out []DiffLine, exact bool) {
 42	a := splitLines(older)
 43	b := splitLines(newer)
 44
 45	// Trim the common prefix and suffix. Ordinary wiki edits touch a few
 46	// lines of a long article, so this alone brings almost every real diff
 47	// under the exact-computation bound.
 48	head := 0
 49	for head < len(a) && head < len(b) && a[head] == b[head] {
 50		head++
 51	}
 52	tailA, tailB := len(a), len(b)
 53	for tailA > head && tailB > head && a[tailA-1] == b[tailB-1] {
 54		tailA--
 55		tailB--
 56	}
 57
 58	midA := a[head:tailA]
 59	midB := b[head:tailB]
 60
 61	out = []DiffLine{}
 62	for _, l := range a[:head] {
 63		out = append(out, DiffLine{OpEqual, l})
 64	}
 65
 66	exact = len(midA) <= DiffMaxLines && len(midB) <= DiffMaxLines
 67	if exact {
 68		out = append(out, lcsDiff(midA, midB)...)
 69	} else {
 70		for _, l := range midA {
 71			out = append(out, DiffLine{OpDelete, l})
 72		}
 73		for _, l := range midB {
 74			out = append(out, DiffLine{OpInsert, l})
 75		}
 76	}
 77
 78	for _, l := range a[tailA:] {
 79		out = append(out, DiffLine{OpEqual, l})
 80	}
 81	return out, exact
 82}
 83
 84// DiffStat counts added and removed lines.
 85func DiffStat(lines []DiffLine) (added, removed int) {
 86	for _, l := range lines {
 87		switch l.Op {
 88		case OpInsert:
 89			added++
 90		case OpDelete:
 91			removed++
 92		}
 93	}
 94	return added, removed
 95}
 96
 97// lcsDiff is the textbook longest-common-subsequence diff, bounded by the
 98// caller to DiffMaxLines on each side.
 99func lcsDiff(a, b []string) []DiffLine {
100	n, m := len(a), len(b)
101	if n == 0 && m == 0 {
102		return []DiffLine{}
103	}
104	// table[i][j] is the LCS length of a[i:] and b[j:].
105	table := make([][]int, n+1)
106	for i := range table {
107		table[i] = make([]int, m+1)
108	}
109	for i := n - 1; i >= 0; i-- {
110		for j := m - 1; j >= 0; j-- {
111			if a[i] == b[j] {
112				table[i][j] = table[i+1][j+1] + 1
113			} else if table[i+1][j] >= table[i][j+1] {
114				table[i][j] = table[i+1][j]
115			} else {
116				table[i][j] = table[i][j+1]
117			}
118		}
119	}
120
121	out := []DiffLine{}
122	i, j := 0, 0
123	for i < n && j < m {
124		switch {
125		case a[i] == b[j]:
126			out = append(out, DiffLine{OpEqual, a[i]})
127			i++
128			j++
129		case table[i+1][j] >= table[i][j+1]:
130			out = append(out, DiffLine{OpDelete, a[i]})
131			i++
132		default:
133			out = append(out, DiffLine{OpInsert, b[j]})
134			j++
135		}
136	}
137	for ; i < n; i++ {
138		out = append(out, DiffLine{OpDelete, a[i]})
139	}
140	for ; j < m; j++ {
141		out = append(out, DiffLine{OpInsert, b[j]})
142	}
143	return out
144}
145
146func splitLines(s string) []string {
147	if s == "" {
148		return []string{}
149	}
150	s = strings.TrimSuffix(s, "\n")
151	return strings.Split(s, "\n")
152}