1package cellbuf
2
3import (
4 "github.com/charmbracelet/x/ansi"
5)
6
7// hash returns the hash value of a [Line].
8func hash(l Line) (h uint64) {
9 for _, c := range l {
10 var r rune
11 if c == nil {
12 r = ansi.SP
13 } else {
14 r = c.Rune
15 }
16 h += (h << 5) + uint64(r)
17 }
18 return
19}
20
21// hashmap represents a single [Line] hash.
22type hashmap struct {
23 value uint64
24 oldcount, newcount int
25 oldindex, newindex int
26}
27
28// The value used to indicate lines created by insertions and scrolls.
29const newIndex = -1
30
31// updateHashmap updates the hashmap with the new hash value.
32func (s *Screen) updateHashmap() {
33 height := s.newbuf.Height()
34 if len(s.oldhash) >= height && len(s.newhash) >= height {
35 // rehash changed lines
36 for i := 0; i < height; i++ {
37 _, ok := s.touch[i]
38 if ok {
39 s.oldhash[i] = hash(s.curbuf.Line(i))
40 s.newhash[i] = hash(s.newbuf.Line(i))
41 }
42 }
43 } else {
44 // rehash all
45 if len(s.oldhash) != height {
46 s.oldhash = make([]uint64, height)
47 }
48 if len(s.newhash) != height {
49 s.newhash = make([]uint64, height)
50 }
51 for i := 0; i < height; i++ {
52 s.oldhash[i] = hash(s.curbuf.Line(i))
53 s.newhash[i] = hash(s.newbuf.Line(i))
54 }
55 }
56
57 s.hashtab = make([]hashmap, height*2)
58 for i := 0; i < height; i++ {
59 hashval := s.oldhash[i]
60
61 // Find matching hash or empty slot
62 idx := 0
63 for idx < len(s.hashtab) && s.hashtab[idx].value != 0 {
64 if s.hashtab[idx].value == hashval {
65 break
66 }
67 idx++
68 }
69
70 s.hashtab[idx].value = hashval // in case this is a new hash
71 s.hashtab[idx].oldcount++
72 s.hashtab[idx].oldindex = i
73 }
74 for i := 0; i < height; i++ {
75 hashval := s.newhash[i]
76
77 // Find matching hash or empty slot
78 idx := 0
79 for idx < len(s.hashtab) && s.hashtab[idx].value != 0 {
80 if s.hashtab[idx].value == hashval {
81 break
82 }
83 idx++
84 }
85
86 s.hashtab[idx].value = hashval // in case this is a new hash
87 s.hashtab[idx].newcount++
88 s.hashtab[idx].newindex = i
89
90 s.oldnum[i] = newIndex // init old indices slice
91 }
92
93 // Mark line pair corresponding to unique hash pairs.
94 for i := 0; i < len(s.hashtab) && s.hashtab[i].value != 0; i++ {
95 hsp := &s.hashtab[i]
96 if hsp.oldcount == 1 && hsp.newcount == 1 && hsp.oldindex != hsp.newindex {
97 s.oldnum[hsp.newindex] = hsp.oldindex
98 }
99 }
100
101 s.growHunks()
102
103 // Eliminate bad or impossible shifts. This includes removing those hunks
104 // which could not grow because of conflicts, as well those which are to be
105 // moved too far, they are likely to destroy more than carry.
106 for i := 0; i < height; {
107 var start, shift, size int
108 for i < height && s.oldnum[i] == newIndex {
109 i++
110 }
111 if i >= height {
112 break
113 }
114 start = i
115 shift = s.oldnum[i] - i
116 i++
117 for i < height && s.oldnum[i] != newIndex && s.oldnum[i]-i == shift {
118 i++
119 }
120 size = i - start
121 if size < 3 || size+min(size/8, 2) < abs(shift) {
122 for start < i {
123 s.oldnum[start] = newIndex
124 start++
125 }
126 }
127 }
128
129 // After clearing invalid hunks, try grow the rest.
130 s.growHunks()
131}
132
133// scrollOldhash
134func (s *Screen) scrollOldhash(n, top, bot int) {
135 if len(s.oldhash) == 0 {
136 return
137 }
138
139 size := bot - top + 1 - abs(n)
140 if n > 0 {
141 // Move existing hashes up
142 copy(s.oldhash[top:], s.oldhash[top+n:top+n+size])
143 // Recalculate hashes for newly shifted-in lines
144 for i := bot; i > bot-n; i-- {
145 s.oldhash[i] = hash(s.curbuf.Line(i))
146 }
147 } else {
148 // Move existing hashes down
149 copy(s.oldhash[top-n:], s.oldhash[top:top+size])
150 // Recalculate hashes for newly shifted-in lines
151 for i := top; i < top-n; i++ {
152 s.oldhash[i] = hash(s.curbuf.Line(i))
153 }
154 }
155}
156
157func (s *Screen) growHunks() {
158 var (
159 backLimit int // limits for cells to fill
160 backRefLimit int // limit for references
161 i int
162 nextHunk int
163 )
164
165 height := s.newbuf.Height()
166 for i < height && s.oldnum[i] == newIndex {
167 i++
168 }
169 for ; i < height; i = nextHunk {
170 var (
171 forwardLimit int
172 forwardRefLimit int
173 end int
174 start = i
175 shift = s.oldnum[i] - i
176 )
177
178 // get forward limit
179 i = start + 1
180 for i < height &&
181 s.oldnum[i] != newIndex &&
182 s.oldnum[i]-i == shift {
183 i++
184 }
185
186 end = i
187 for i < height && s.oldnum[i] == newIndex {
188 i++
189 }
190
191 nextHunk = i
192 forwardLimit = i
193 if i >= height || s.oldnum[i] >= i {
194 forwardRefLimit = i
195 } else {
196 forwardRefLimit = s.oldnum[i]
197 }
198
199 i = start - 1
200
201 // grow back
202 if shift < 0 {
203 backLimit = backRefLimit + (-shift)
204 }
205 for i >= backLimit {
206 if s.newhash[i] == s.oldhash[i+shift] ||
207 s.costEffective(i+shift, i, shift < 0) {
208 s.oldnum[i] = i + shift
209 } else {
210 break
211 }
212 i--
213 }
214
215 i = end
216 // grow forward
217 if shift > 0 {
218 forwardLimit = forwardRefLimit - shift
219 }
220 for i < forwardLimit {
221 if s.newhash[i] == s.oldhash[i+shift] ||
222 s.costEffective(i+shift, i, shift > 0) {
223 s.oldnum[i] = i + shift
224 } else {
225 break
226 }
227 i++
228 }
229
230 backLimit = i
231 backRefLimit = backLimit
232 if shift > 0 {
233 backRefLimit += shift
234 }
235 }
236}
237
238// costEffective returns true if the cost of moving line 'from' to line 'to' seems to be
239// cost effective. 'blank' indicates whether the line 'to' would become blank.
240func (s *Screen) costEffective(from, to int, blank bool) bool {
241 if from == to {
242 return false
243 }
244
245 newFrom := s.oldnum[from]
246 if newFrom == newIndex {
247 newFrom = from
248 }
249
250 // On the left side of >= is the cost before moving. On the right side --
251 // cost after moving.
252
253 // Calculate costs before moving.
254 var costBeforeMove int
255 if blank {
256 // Cost of updating blank line at destination.
257 costBeforeMove = s.updateCostBlank(s.newbuf.Line(to))
258 } else {
259 // Cost of updating exiting line at destination.
260 costBeforeMove = s.updateCost(s.curbuf.Line(to), s.newbuf.Line(to))
261 }
262
263 // Add cost of updating source line
264 costBeforeMove += s.updateCost(s.curbuf.Line(newFrom), s.newbuf.Line(from))
265
266 // Calculate costs after moving.
267 var costAfterMove int
268 if newFrom == from {
269 // Source becomes blank after move
270 costAfterMove = s.updateCostBlank(s.newbuf.Line(from))
271 } else {
272 // Source gets updated from another line
273 costAfterMove = s.updateCost(s.curbuf.Line(newFrom), s.newbuf.Line(from))
274 }
275
276 // Add cost of moving source line to destination
277 costAfterMove += s.updateCost(s.curbuf.Line(from), s.newbuf.Line(to))
278
279 // Return true if moving is cost effective (costs less or equal)
280 return costBeforeMove >= costAfterMove
281}
282
283func (s *Screen) updateCost(from, to Line) (cost int) {
284 var fidx, tidx int
285 for i := s.newbuf.Width() - 1; i > 0; i, fidx, tidx = i-1, fidx+1, tidx+1 {
286 if !cellEqual(from.At(fidx), to.At(tidx)) {
287 cost++
288 }
289 }
290 return
291}
292
293func (s *Screen) updateCostBlank(to Line) (cost int) {
294 var tidx int
295 for i := s.newbuf.Width() - 1; i > 0; i, tidx = i-1, tidx+1 {
296 if !cellEqual(nil, to.At(tidx)) {
297 cost++
298 }
299 }
300 return
301}