diff.gno
3.87 Kb · 152 lines
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}
