Repository navigation
Expand file tree
/
Copy pathindex.go
More file actions
537 lines (499 loc) · 15.3 KB
/
Copy pathindex.go
File metadata and controls
537 lines (499 loc) · 15.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
<
8000
div data-line-number="513" class="react-line-number react-code-text" style="padding-right:16px">513514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
// SPDX-License-Identifier: Unlicense OR MIT
package widget
import (
"bufio"
"image"
"io"
"math"
"sort"
"gioui.org/text"
"github.com/go-text/typesetting/segmenter"
"golang.org/x/image/math/fixed"
)
type lineInfo struct {
xOff fixed.Int26_6
yOff int
width fixed.Int26_6
ascent, descent fixed.Int26_6
glyphs int
}
func (l lineInfo) getLineEnd() fixed.Int26_6 {
return l.xOff + l.width
}
type glyphIndex struct {
// glyphs holds the glyphs processed.
glyphs []text.Glyph
// positions contain all possible caret positions, sorted by rune index.
positions []combinedPos
// lines contains metadata about the size and position of each line of
// text.
lines []lineInfo
// currentLineMin and currentLineMax track the dimensions of the line
// that is being indexed.
currentLineMin, currentLineMax fixed.Int26_6
// currentLineGlyphs tracks how many glyphs are contained within the
// line that is being indexed.
currentLineGlyphs int
// pos tracks attributes of the next valid cursor position within the indexed
// text.
pos combinedPos
// prog tracks the current glyph text progression to detect bidi changes.
prog text.Flags
// clusterAdvance accumulates the advances of glyphs in a glyph cluster.
clusterAdvance fixed.Int26_6
// truncated indicates that the text was truncated by the shaper.
truncated bool
// midCluster tracks whether the next glyph processed is not the first glyph in a
// cluster.
midCluster bool
}
// reset prepares the index for reuse.
func (g *glyphIndex) reset() {
g.glyphs = g.glyphs[:0]
g.positions = g.positions[:0]
g.lines = g.lines[:0]
g.currentLineMin = 0
g.currentLineMax = 0
g.currentLineGlyphs = 0
g.pos = combinedPos{}
g.prog = 0
g.clusterAdvance = 0
g.truncated = false
g.midCluster = false
}
// screenPos represents a character position in text line and column numbers,
// not pixels.
type screenPos struct {
// col is the column, measured in runes.
// FIXME: we only ever use col for start or end of lines.
// We don't need accurate accounting, so can we get rid of it?
col int
line int
}
// combinedPos is a point in the editor.
type combinedPos struct {
// runes is the offset in runes.
runes int
lineCol screenPos
// Pixel coordinates
x fixed.Int26_6
y int
ascent, descent fixed.Int26_6
// runIndex tracks which run this position is within, counted each time
// the index processes an end of run marker.
runIndex int
// towardOrigin tracks whether this glyph's run is progressing toward the
// origin or away from it.
towardOrigin bool
}
// incrementPosition returns the next position after pos (if any). Pos _must_ be
// an unmodified position acquired from one of the closest* methods. If eof is
// true, there was no next position.
func (g *glyphIndex) incrementPosition(pos combinedPos) (next combinedPos, eof bool) {
candidate, index := g.closestToRune(pos.runes)
for candidate != pos && index+1 < len(g.positions) {
index++
candidate = g.positions[index]
}
if index+1 < len(g.positions) {
return g.positions[index+1], false
}
return candidate, true
}
func (g *glyphIndex) insertPosition(pos combinedPos) {
lastIdx := len(g.positions) - 1
if lastIdx >= 0 {
8000
lastPos := g.positions[lastIdx]
if lastPos.runes == pos.runes && (lastPos.y != pos.y || (lastPos.x == pos.x)) {
// If we insert a consecutive position with the same logical position,
// overwrite the previous position with the new one.
g.positions[lastIdx] = pos
return
}
}
g.positions = append(g.positions, pos)
}
// Glyph indexes the provided glyph, generating text cursor positions for it.
func (g *glyphIndex) Glyph(gl text.Glyph) {
g.glyphs = append(g.glyphs, gl)
g.currentLineGlyphs++
if len(g.positions) == 0 {
// First-iteration setup.
g.currentLineMin = math.MaxInt32
g.currentLineMax = 0
}
if gl.X < g.currentLineMin {
g.currentLineMin = gl.X
}
if end := gl.X + gl.Advance; end > g.currentLineMax {
g.currentLineMax = end
}
needsNewLine := gl.Flags&text.FlagLineBreak != 0
needsNewRun := gl.Flags&text.FlagRunBreak != 0
breaksParagraph := gl.Flags&text.FlagParagraphBreak != 0
breaksCluster := gl.Flags&text.FlagClusterBreak != 0
// We should insert new positions if the glyph we're processing terminates
// a glyph cluster, has nonzero runes, and is not a hard newline.
insertPositionsWithin := breaksCluster && !breaksParagraph && gl.Runes > 0
// Get the text progression/direction right.
g.prog = gl.Flags & text.FlagTowardOrigin
g.pos.towardOrigin = g.prog == text.FlagTowardOrigin
if !g.midCluster {
// Create the text position prior to the glyph.
g.pos.x = gl.X
g.pos.y = int(gl.Y)
g.pos.ascent = gl.Ascent
g.pos.descent = gl.Descent
if g.pos.towardOrigin {
g.pos.x += gl.Advance
}
g.insertPosition(g.pos)
}
g.midCluster = !breaksCluster
if breaksParagraph {
// Paragraph breaking clusters shouldn't have positions generated for both
// sides of them. They're always zero-width, so doing so would
// create two visually identical cursor positions. Just reset
// cluster state, increment by their runes, and move on to the
// next glyph.
g.clusterAdvance = 0
g.pos.runes += int(gl.Runes)
}
// Always track the cumulative advance added by the glyph, even if it
// doesn't terminate a cluster itself.
g.clusterAdvance += gl.Advance
if insertPositionsWithin {
// Construct the text positions _within_ gl.
g.pos.y = int(gl.Y)
g.pos.ascent = gl.Ascent
g.pos.descent = gl.Descent
width := g.clusterAdvance
positionCount := int(gl.Runes)
runesPerPosition := 1
if gl.Flags&text.FlagTruncator != 0 {
// Treat the truncator as a single unit that is either selected or not.
positionCount = 1
runesPerPosition = int(gl.Runes)
g.truncated = true
}
perRune := width / fixed.Int26_6(positionCount)
adjust := fixed.Int26_6(0)
if g.pos.towardOrigin {
// If RTL, subtract increments from the width of the cluster
// instead of adding.
adjust = width
perRune = -perRune
}
for i := 1; i <= positionCount; i++ {
g.pos.x = gl.X + adjust + perRune*fixed.Int26_6(i)
g.pos.runes += runesPerPosition
g.pos.lineCol.col += runesPerPosition
g.insertPosition(g.pos)
}
g.clusterAdvance = 0
}
if needsNewRun {
g.pos.runIndex++
}
if needsNewLine {
g.lines = append(g.lines, lineInfo{
xOff: g.currentLineMin,
yOff: int(gl.Y),
width: g.currentLineMax - g.currentLineMin,
ascent: g.positions[len(g.positions)-1].ascent,
descent: g.positions[len(g.positions)-1].descent,
glyphs: g.currentLineGlyphs,
})
g.pos.lineCol.line++
g.pos.lineCol.col = 0
g.pos.runIndex = 0
g.currentLineMin = math.MaxInt32
g.currentLineMax = 0
g.currentLineGlyphs = 0
}
}
func (g *glyphIndex) closestToRune(runeIdx int) (combinedPos, int) {
n := len(g.positions)
if n == 0 {
return combinedPos{}, 0
}
i := sort.Search(n, func(i int) bool {
pos := g.positions[i]
return pos.runes >= runeIdx
})
notFound := i == n
if notFound {
return g.positions[n-1], n - 1
}
return g.positions[i], i
}
func (g *glyphIndex) closestToLineCol(lineCol screenPos) combinedPos {
n := len(g.positions)
if n == 0 {
return combinedPos{}
}
i := sort.Search(n, func(i int) bool {
pos := g.positions[i]
return pos.lineCol.line > lineCol.line || (pos.lineCol.line == lineCol.line && pos.lineCol.col >= lineCol.col)
})
notFound := i == n
if notFound {
return g.positions[n-1]
}
pos := g.positions[i]
foundInNextLine := pos.lineCol.line > lineCol.line
if foundInNextLine && i > 0 {
prior := g.positions[i-1]
prior.x = g.lines[lineCol.line].getLineEnd()
return prior
}
return pos
}
func (g *glyphIndex) atStartOfLine(pos combinedPos) bool {
if pos.runes == 0 {
return true
}
prevRuneIndex := pos.runes - 1
lineOfPrevRune := g.positions[prevRuneIndex].lineCol.line
return lineOfPrevRune < pos.lineCol.line
}
func (g *glyphIndex) atEndOfLine(pos combinedPos) bool {
if pos.runes == g.positions[len(g.positions)-1].runes {
return true
}
next := pos.runes + 1
hasNext := next < len(g.positions)
return hasNext && g.positions[next].lineCol.line > pos.lineCol.line
}
func dist(a, b fixed.Int26_6) fixed.Int26_6 {
if a > b {
return a - b
}
return b - a
}
func (g *glyphIndex) closestToXY(x fixed.Int26_6, y int) (pos combinedPos, atEndOfLine bool) {
if len(g.positions) == 0 {
return combinedPos{}, false
}
i := sort.Search(len(g.positions), func(i int) bool {
pos := g.positions[i]
return pos.y+pos.descent.Round() >= y
})
// If no position was greater than the provided Y, the text is too
// short. Return either the last position or (if there are no
// positions) the zero position.
if i == len(g.positions) {
return g.positions[i-1], false
}
first := g.positions[i]
// Find the best X coordinate.
closest := i
closestDist := dist(first.x, x)
line := first.lineCol.line
// NOTE(whereswaldon): there isn't a simple way to accelerate this. Bidi text means that the x coordinates
// for positions have no fixed relationship. In the future, we can consider sorting the positions
// on a line by their x coordinate and caching that. It'll be a one-time O(nlogn) per line, but
// subsequent uses of this function for that line become O(logn). Right now it's always O(n).
for i := i + 1; i < len(g.positions) && g.positions[i].lineCol.line == line; i++ {
candidate := g.positions[i]
distance := dist(candidate.x, x)
// If we are *really* close to the current position candidate, just choose it.
if distance.Round() == 0 {
return g.positions[i], false
}
if distance < closestDist {
closestDist = distance
closest = i
}
}
next := closest + 1
hasNext := next < len(g.positions)
if hasNext && g.atEndOfLine(g.positions[closest]) {
distance := dist(g.lines[line].getLineEnd(), x)
if distance < closestDist {
return g.positions[next], true
}
}
return g.positions[closest], false
}
// makeRegion creates a text-aligned rectangle from start to end. The vertical
// dimensions of the rectangle are derived from the provided line's ascent and
// descent, and the y offset of the line's baseline is provided as y.
func makeRegion(line lineInfo, y int, start, end fixed.Int26_6) Region {
if start > end {
start, end = end, start
}
dotStart := image.Pt(start.Round(), y)
dotEnd := image.Pt(end.Round(), y)
return Region{
Bounds: image.Rectangle{
Min: dotStart.Sub(image.Point{Y: line.ascent.Ceil()}),
Max: dotEnd.Add(image.Point{Y: line.descent.Floor()}),
},
Baseline: line.descent.Floor(),
}
}
// Region describes the position and baseline of an area of interest within
// shaped text.
type Region struct {
// Bounds is the coordinates of the bounding box relative to the containing
// widget.
Bounds image.Rectangle
// Baseline is the quantity of vertical pixels between the baseline and
// the bottom of bounds.
Baseline int
}
// locate returns highlight regions covering the glyphs that represent the runes in
// [startRune,endRune). If the rects parameter is non-nil, locate will use it to
// return results instead of allocating, provided that there is enough capacity.
// The returned regions have their Bounds specified relative to the provided
// viewport.
func (g *glyphIndex) locate(viewport image.Rectangle, startRune, endRune int, rects []Region) []Region {
if startRune > endRune {
startRune, endRune = endRune, startRune
}
rects = rects[:0]
caretStart, _ := g.closestToRune(startRune)
caretEnd, _ := g.closestToRune(endRune)
for lineIdx := caretStart.lineCol.line; lineIdx < len(g.lines); lineIdx++ {
if lineIdx > caretEnd.lineCol.line {
break
}
pos := g.closestToLineCol(screenPos{line: lineIdx})
if int(pos.y)+pos.descent.Ceil() < viewport.Min.Y {
continue
}
if int(pos.y)-pos.ascent.Ceil() > viewport.Max.Y {
break
}
line := g.lines[lineIdx]
if lineIdx > caretStart.lineCol.line && lineIdx < caretEnd.lineCol.line {
startX := line.xOff
endX := startX + line.width
// The entire line is selected.
rects = append(rects, makeRegion(line, pos.y, startX, endX))
continue
}
selectionStart := caretStart
selectionEnd := caretEnd
if lineIdx != caretStart.lineCol.line {
// This line does not contain the beginning of the selection.
selectionStart = g.closestToLineCol(screenPos{line: lineIdx})
}
if lineIdx != caretEnd.lineCol.line {
// This line does not contain the end of the selection.
selectionEnd = g.closestToLineCol(screenPos{line: lineIdx, col: math.MaxInt})
}
var (
startX, endX fixed.Int26_6
eof bool
)
lineLoop:
for !eof {
startX = selectionStart.x
if selectionStart.runIndex == selectionEnd.runIndex {
// Commit selection.
endX = selectionEnd.x
rects = append(rects, makeRegion(line, pos.y, startX, endX))
break
} else {
currentDirection := selectionStart.towardOrigin
previous := selectionStart
runLoop:
for !eof {
// Increment the start position until the next logical run.
for startRun := selectionStart.runIndex; selectionStart.runIndex == startRun; {
previous = selectionStart
selectionStart, eof = g.incrementPosition(selectionStart)
if eof {
endX = selectionStart.x
rects = append(rects, makeRegion(line, pos.y, startX, endX))
break runLoop
}
}
if selectionStart.towardOrigin != currentDirection {
endX = previous.x
rects = append(rects, makeRegion(line, pos.y, startX, endX))
break
}
if selectionStart.runIndex == selectionEnd.runIndex {
// Commit selection.
endX = selectionEnd.x
rects = append(rects, makeRegion(line, pos.y, startX, endX))
break lineLoop
}
}
}
}
}
for i := range rects {
rects[i].Bounds = rects[i].Bounds.Sub(viewport.Min)
}
return rects
}
// graphemeReader segments paragraphs of text into grapheme clusters.
type graphemeReader struct {
segmenter.Segmenter
graphemes []int
paragraph []rune
source io.ReaderAt
cursor int64
reader *bufio.Reader
runeOffset int
}
// SetSource configures the reader to pull from source.
func (p *graphemeReader) SetSource(source io.ReaderAt) {
p.source = source
p.cursor = 0
p.reader = bufio.NewReader(p)
p.runeOffset = 0
}
// Read exists to satisfy io.Reader. It should not be directly invoked.
func (p *graphemeReader) Read(b []byte) (int, error) {
n, err := p.source.ReadAt(b, p.cursor)
p.cursor += int64(n)
return n, err
}
// next decodes one paragraph of rune data.
func (p *graphemeReader) next() ([]rune, bool) {
p.paragraph = p.paragraph[:0]
var err error
var r rune
for err == nil {
r, _, err = p.reader.ReadRune()
if err != nil {
break
}
p.paragraph = append(p.paragraph, r)
if r == '\n' {
break
}
}
return p.paragraph, err == nil
}
// Graphemes will return the next paragraph's grapheme cluster boundaries,
// if any. If it returns an empty slice, there is no more data (all paragraphs
// have been segmented).
func (p *graphemeReader) Graphemes() []int {
var more bool
p.graphemes = p.graphemes[:0]
p.paragraph, more = p.next()
if len(p.paragraph) == 0 && !more {
return nil
}
p.Segmenter.Init(p.paragraph)
iter := p.Segmenter.GraphemeIterator()
if iter.Next() {
graph := iter.Grapheme()
p.graphemes = append(p.graphemes,
p.runeOffset+graph.Offset,
p.runeOffset+graph.Offset+len(graph.Text),
)
}
for iter.Next() {
graph := iter.Grapheme()
p.graphemes = append(p.graphemes, p.runeOffset+graph.Offset+len(graph.Text))
}
p.runeOffset += len(p.paragraph)
return p.graphemes
}