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