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