1// Package hints finds clickable targets for hint mode: it captures the last
2// frame of an output through the capture pipeline and reads uncovered windows with OCR.
3package hints
4
5import (
6 "context"
7 "errors"
8 "fmt"
9 "hash/maphash"
10 "image"
11 "math"
12 "strings"
13 "time"
14
15 "github.com/bnema/neferwl/internal/adapters/logging"
16 "github.com/bnema/neferwl/internal/ports"
17)
18
19// ErrBusy answers a request that arrives while another one is in flight.
20var ErrBusy = errors.New("hints: scan in progress")
21
22// ErrTimeout is the error of a capture that is not answered in time.
23var ErrTimeout = errors.New("hints: capture timed out")
24
25// ErrBadRequest is the error of a request without a usable buffer size.
26var ErrBadRequest = errors.New("hints: invalid output size")
27
28const (
29 captureTimeout = time.Second
30 // formatXRGB8888 is the capture format: opaque BGRA in memory.
31 formatXRGB8888 = 1
32 maxPixels = 1 << 28
33)
34
35// Run serves requests until ctx is done. It handles one request at a time;
36// a request that arrives meanwhile is answered with ErrBusy. Every request
37// gets exactly one result on results.
38func Run(ctx context.Context, requests <-chan ports.HintScanRequest, captures chan<- ports.CaptureRequest, captured <-chan ports.CaptureDone, results chan<- ports.HintScanResult, opts Options) error {
39 return run(ctx, requests, captures, captured, results, captureTimeout, opts)
40}
41
42// targetSource finds hint targets in the accessibility tree of windows. It
43// returns the targets (logical output-local) and the windows they cover.
44type targetSource interface {
45 Targets(ctx context.Context, windows []ports.HintWindow, linksOnly bool) ([]ports.HintTarget, map[ports.WindowID]bool, error)
46 // Close releases the source. It is called once, by the worker goroutine,
47 // when the worker returns; the source is not safe for concurrent use.
48 Close() error
49}
50
51// atspiResult is what the source found for one request.
52type atspiResult struct {
53 targets []ports.HintTarget
54 covered map[ports.WindowID]bool
55 dur time.Duration
56 err error
57}
58
59type worker struct {
60 source targetSource
61 cache map[bandKey]bandCache
62 cacheSeed maphash.Seed
63 ocr ocrState
64 warnedSource bool
65 n uint64
66 dumpDir string
67 pending *dumpJob
68 // orphans are capture buffers the output may still write: they are
69 // released when its CaptureDone finally arrives.
70 orphans map[uint64]*mapping
71 live int // mappings not released yet
72}
73
74// frame is the captured output: BGRA pixels, nil when no capture was needed.
75type frame struct {
76 pix []byte
77 stride int
78 m *mapping
79}
80
81func run(ctx context.Context, requests <-chan ports.HintScanRequest, captures chan<- ports.CaptureRequest, captured <-chan ports.CaptureDone, results chan<- ports.HintScanResult, timeout time.Duration, opts Options) error {
82 w := &worker{dumpDir: opts.DumpDir, source: opts.Source}
83 if opts.Source != nil {
84 // The worker goroutine is the only one to touch the source.
85 defer func() { _ = opts.Source.Close() }()
86 }
87 for {
88 select {
89 case <-ctx.Done():
90 return nil
91 case done := <-captured:
92 // A capture abandoned by a timeout is finally done: release it.
93 w.reap(done.ID)
94 case req := <-requests:
95 res := w.serve(ctx, req, requests, captures, captured, results, timeout)
96 if !send(ctx, results, res) {
97 // The dump job will never run: release its frame.
98 if j := w.pending; j != nil {
99 w.pending = nil
100 j.m.unmap()
101 }
102 return nil
103 }
104 w.dump(ctx)
105 }
106 }
107}
108
109// dump writes the last successful scan, after its result was sent, then
110// releases its frame.
111func (w *worker) dump(ctx context.Context) {
112 j := w.pending
113 w.pending = nil
114 if j == nil {
115 return
116 }
117 defer j.m.unmap()
118 if err := writeDump(w.dumpDir, j); err != nil {
119 log := logging.For(ctx, "hints")
120 log.Warn().Err(err).Str("dir", w.dumpDir).Msg("hint debug dump failed")
121 }
122}
123
124func send(ctx context.Context, results chan<- ports.HintScanResult, res ports.HintScanResult) bool {
125 select {
126 case results <- res:
127 return true
128 case <-ctx.Done():
129 return false
130 }
131}
132
133// needFrame reports whether the scan must capture the output: OCR has a
134// window to read, or the debug dump wants the frame. With OCR unavailable
135// (tesseract missing) and no dump, the accessibility targets are the result.
136func (w *worker) needFrame(ctx context.Context, req ports.HintScanRequest, ar atspiResult) bool {
137 ocr := w.ocrReady(ctx)
138 if w.dumpDir != "" {
139 return true
140 }
141 if !ocr {
142 return false
143 }
144 for _, win := range req.Windows {
145 if !ar.covered[win.ID] && !windowCrop(win.Rect, req.Scale, req.Width, req.Height).Empty() {
146 return true
147 }
148 }
149 return false
150}
151
152func (w *worker) serve(ctx context.Context, req ports.HintScanRequest, requests <-chan ports.HintScanRequest, captures chan<- ports.CaptureRequest, captured <-chan ports.CaptureDone, results chan<- ports.HintScanResult, timeout time.Duration) ports.HintScanResult {
153 log := logging.For(ctx, "hints")
154 res := ports.HintScanResult{Seq: req.Seq, Output: req.Output}
155 fail := func(err error) ports.HintScanResult {
156 log.Info().Err(err).Str("output", req.Output).Msg("hint scan failed")
157 res.Err = err
158 return res
159 }
160
161 if req.Width <= 0 || req.Height <= 0 || req.Width*req.Height > maxPixels {
162 return fail(fmt.Errorf("%w: %dx%d", ErrBadRequest, req.Width, req.Height))
163 }
164 // The accessibility query is always waited for: the source is not shared
165 // between requests. The capture only starts once it is known whether any
166 // window needs OCR.
167 atspi := w.startSource(ctx, req)
168 defer func() { <-atspi.done }()
169 if !w.needFrame(ctx, req, atspi.wait()) {
170 return w.scan(ctx, req, frame{}, 0, res, atspi)
171 }
172 // The capture buffer is anonymous mapped memory, outside the Go heap. It
173 // is released once the crops are extracted, or by the dump job.
174 m := w.alloc(req.Width * req.Height * 4)
175 keep := false // the mapping outlives this call: dump job or pending capture
176 defer func() {
177 if !keep {
178 m.unmap()
179 }
180 }()
181 buf := m.b
182
183 w.n++
184 id := ports.CaptureIDInternal | w.n
185 stride := req.Width * 4
186 start := time.Now()
187 creq := ports.CaptureRequest{
188 ID: id,
189 Output: req.Output,
190 Region: image.Rect(0, 0, req.Width, req.Height),
191 Mapped: buf,
192 Width: req.Width,
193 Height: req.Height,
194 Stride: stride,
195 Format: formatXRGB8888,
196 Indicate: false,
197 }
198
199 timer := time.NewTimer(timeout)
200 defer timer.Stop()
201
202 select {
203 case captures <- creq:
204 case <-timer.C:
205 return fail(ErrTimeout)
206 case <-ctx.Done():
207 return fail(ctx.Err())
208 }
209 // From here the output owns buf until CaptureDone.
210 abandon := func() {
211 if w.orphans == nil {
212 w.orphans = map[uint64]*mapping{}
213 }
214 w.orphans[id] = m
215 keep = true
216 }
217
218 for {
219 select {
220 case done := <-captured:
221 if done.ID != id {
222 w.reap(done.ID)
223 continue
224 }
225 if done.Err != nil {
226 return fail(fmt.Errorf("hints: capture: %w", done.Err))
227 }
228 res = w.scan(ctx, req, frame{pix: buf, stride: stride, m: m}, time.Since(start), res, atspi)
229 keep = w.pending != nil && w.pending.m == m
230 return res
231 case other := <-requests:
232 // The buffer is in use until the capture is done: answer now.
233 busy := ports.HintScanResult{Seq: other.Seq, Output: other.Output, Err: ErrBusy}
234 if !send(ctx, results, busy) {
235 abandon()
236 return fail(ctx.Err())
237 }
238 case <-timer.C:
239 // The output may still write into buf: it is released when its
240 // CaptureDone arrives.
241 abandon()
242 return fail(ErrTimeout)
243 case <-ctx.Done():
244 abandon()
245 return fail(ctx.Err())
246 }
247 }
248}
249
250// reap releases the buffer of an abandoned capture that is finally done.
251func (w *worker) reap(id uint64) {
252 if m, ok := w.orphans[id]; ok {
253 delete(w.orphans, id)
254 m.unmap()
255 }
256}
257
258// bandJob is one OCR band of one window crop.
259type bandJob struct {
260 win int // index into the scan's windows
261 key bandKey //
262 ext image.Rectangle // crop-local rows read, with context
263 own [2]int // crop-local rows owned: words centred there are kept
264 hash uint64
265 hit bool
266 gray *image.Gray
267 words []OCRWord
268 err error
269}
270
271func (w *worker) scan(ctx context.Context, req ports.HintScanRequest, fr frame, captureDur time.Duration, res ports.HintScanResult, atspi *pendingSource) ports.HintScanResult {
272 log := logging.For(ctx, "hints")
273 ar := atspi.wait()
274 if ar.err != nil && !w.warnedSource {
275 log.Warn().Err(ar.err).Msg("accessibility targets unavailable; using OCR only")
276 w.warnedSource = true
277 }
278 out := make([]ports.HintTarget, 0, len(ar.targets))
279 for _, t := range ar.targets {
280 if !req.LinksOnly || t.Kind == ports.HintLink {
281 out = append(out, t)
282 }
283 }
284 nAtspi := len(out)
285 t0 := time.Now()
286 if w.cacheSeed == (maphash.Seed{}) {
287 w.cacheSeed = maphash.MakeSeed()
288 }
289 nextCache := make(map[bandKey]bandCache)
290 var crops []image.Rectangle
291 var allWords []OCRWord
292 pixels, links := 0, 0
293 ocrOn := fr.pix != nil && w.ocrReady(ctx)
294 // Phase 1 reads the frame: the bands that miss the cache are copied, as
295 // grayscale, into one arena. Phase 2 (OCR) does not need the frame.
296 var jobs []*bandJob
297 var rects []image.Rectangle // crop of each window that has bands
298 var arena *mapping
299 if ocrOn {
300 type pending struct {
301 r image.Rectangle
302 jobs []*bandJob
303 }
304 var wins []pending
305 need := 0
306 for _, win := range req.Windows {
307 if ar.covered[win.ID] {
308 continue
309 }
310 r := windowCrop(win.Rect, req.Scale, req.Width, req.Height)
311 if r.Empty() {
312 continue
313 }
314 crops = append(crops, r)
315 pixels += r.Dx() * r.Dy()
316 p := pending{r: r}
317 for _, b := range bandsOf(r.Dy()) {
318 ext := image.Rect(0, b.top, r.Dx(), b.bottom)
319 j := &bandJob{win: len(wins), ext: ext, own: [2]int{b.ownTop, b.ownBottom},
320 key: bandKey{output: req.Output, window: win.ID, band: b.idx, bands: b.n}}
321 j.hash = w.cropHash(fr.pix, fr.stride, ext.Add(r.Min))
322 entry, ok := w.cache[j.key]
323 if ok && entry.hash == j.hash && entry.ext == ext {
324 j.hit, j.words = true, entry.words
325 } else {
326 need += ext.Dx() * ext.Dy()
327 }
328 p.jobs = append(p.jobs, j)
329 }
330 wins = append(wins, p)
331 }
332 if need > 0 {
333 arena = w.alloc(need)
334 }
335 off := 0
336 for _, p := range wins {
337 rects = append(rects, p.r)
338 for _, j := range p.jobs {
339 if !j.hit {
340 n := j.ext.Dx() * j.ext.Dy()
341 j.gray = cropGray(fr.pix, fr.stride, j.ext.Add(p.r.Min), arena.b[off:off+n])
342 off += n
343 }
344 jobs = append(jobs, j)
345 }
346 }
347 } else if w.dumpDir != "" {
348 for _, win := range req.Windows {
349 if !ar.covered[win.ID] {
350 if r := windowCrop(win.Rect, req.Scale, req.Width, req.Height); !r.Empty() {
351 crops = append(crops, r)
352 }
353 }
354 }
355 }
356 if w.dumpDir != "" && fr.pix != nil {
357 // The dump reads the frame after the result is sent and releases it.
358 w.pending = &dumpJob{when: time.Now(), req: req, pix: fr.pix, m: fr.m, stride: fr.stride, crops: crops, captureD: captureDur, atspiD: ar.dur}
359 } else {
360 fr.m.unmap() // the crops are extracted: give the frame back
361 }
362 fr.pix = nil
363
364 hits := 0
365 if len(jobs) > 0 {
366 w.recognize(ctx, jobs)
367 for _, j := range jobs {
368 if j.hit {
369 hits++
370 }
371 }
372 }
373 arena.unmap()
374
375 // Merge the bands of each window, in order.
376 k := 0
377 for wi, r := range rects {
378 var words []OCRWord
379 for ; k < len(jobs) && jobs[k].win == wi; k++ {
380 j := jobs[k]
381 if j.err != nil {
382 failureWarning.Do(func() { log.Warn().Err(j.err).Msg("OCR unavailable; install tesseract and tesseract-data-eng") })
383 continue
384 }
385 nextCache[j.key] = bandCache{hash: j.hash, ext: j.ext, words: j.words}
386 for _, word := range j.words {
387 word.Rect = word.Rect.Add(r.Min)
388 if word.Underlined {
389 word.UnderL, word.UnderR = word.UnderL+r.Min.X, word.UnderR+r.Min.X
390 }
391 if !duplicateWord(words, word) {
392 words = append(words, word)
393 }
394 }
395 }
396 allWords = append(allWords, words...)
397 targets := textLinks(words, req.Scale)
398 links += len(targets)
399 out = append(out, targets...)
400 }
401 w.cache = nextCache
402 ocrDur := time.Since(t0)
403 res.Targets = out
404 if p := w.pending; p != nil {
405 p.targets, p.atspi, p.words, p.scanD = out, nAtspi, allWords, ocrDur
406 }
407 log.Info().Str("output", req.Output).
408 Float64("atspi_ms", ms(ar.dur)).Int("atspi_windows", len(ar.covered)).Int("atspi_targets", nAtspi).
409 Int("ocr_windows", len(rects)).Float64("ocr_ms", ms(ocrDur)).Int("ocr_px", pixels).
410 Int("ocr_bands", len(jobs)).Int("band_hits", hits).
411 Int("words", len(allWords)).Int("ocr_links", links).Bool("cache_hit", len(jobs) > 0 && hits == len(jobs)).
412 Int("targets", len(out)).Msg("hint scan")
413 return res
414}
415
416// duplicateWord reports whether words already holds word (the same text at
417// the same place), as happens where two bands overlap.
418func duplicateWord(words []OCRWord, word OCRWord) bool {
419 for _, old := range words {
420 if strings.EqualFold(word.Text, old.Text) && overlap(word.Rect, old.Rect) > .5 {
421 return true
422 }
423 }
424 return false
425}
426
427// bandKey identifies one OCR band of a window on an output.
428type bandKey struct {
429 output string
430 window ports.WindowID
431 band int
432 bands int
433}
434
435// bandCache is the OCR result of a band whose pixels hash to hash. words are
436// crop-local and only the ones the band owns.
437type bandCache struct {
438 hash uint64
439 ext image.Rectangle
440 words []OCRWord
441}
442
443// windowCrop rounds outwards in physical pixels, then intersects the output.
444func windowCrop(r ports.Rect, scale float64, width, height int) image.Rectangle {
445 if scale <= 0 {
446 scale = 1
447 }
448 if r.W <= 0 || r.H <= 0 {
449 return image.Rectangle{}
450 }
451 return image.Rect(int(math.Floor(float64(r.X)*scale)), int(math.Floor(float64(r.Y)*scale)),
452 int(math.Ceil(float64(r.X+r.W)*scale)), int(math.Ceil(float64(r.Y+r.H)*scale))).Intersect(image.Rect(0, 0, width, height))
453}
454
455// cropHash hashes the raw pixels of r without copying them.
456func (w *worker) cropHash(buf []byte, stride int, r image.Rectangle) uint64 {
457 var h maphash.Hash
458 h.SetSeed(w.cacheSeed)
459 for y := r.Min.Y; y < r.Max.Y; y++ {
460 _, _ = h.Write(buf[y*stride+r.Min.X*4 : y*stride+r.Max.X*4])
461 }
462 return h.Sum64()
463}
464
465// cropGray converts the BGRA pixels of r to 8-bit luma into dst, which must
466// hold r.Dx()*r.Dy() bytes; only this band is converted, not the output.
467func cropGray(buf []byte, stride int, r image.Rectangle, dst []byte) *image.Gray {
468 img := &image.Gray{Pix: dst[:r.Dx()*r.Dy()], Stride: r.Dx(), Rect: image.Rect(0, 0, r.Dx(), r.Dy())}
469 for y := 0; y < r.Dy(); y++ {
470 src := buf[(r.Min.Y+y)*stride+r.Min.X*4:][:r.Dx()*4]
471 row := img.Pix[y*img.Stride:][:r.Dx()]
472 for x := range row {
473 p := src[x*4 : x*4+4 : x*4+4]
474 row[x] = uint8((uint32(p[2])*299 + uint32(p[1])*587 + uint32(p[0])*114 + 500) / 1000)
475 }
476 }
477 return img
478}
479
480// pendingSource is an accessibility query in flight.
481type pendingSource struct {
482 done chan struct{}
483 res atspiResult
484}
485
486// startSource starts the accessibility query of req, if there is a source and
487// a window to ask about. done is closed when res is set.
488func (w *worker) startSource(ctx context.Context, req ports.HintScanRequest) *pendingSource {
489 p := &pendingSource{done: make(chan struct{})}
490 if w.source == nil || len(req.Windows) == 0 {
491 close(p.done)
492 return p
493 }
494 go func() {
495 defer close(p.done)
496 t0 := time.Now()
497 targets, covered, err := w.source.Targets(ctx, req.Windows, req.LinksOnly)
498 p.res = atspiResult{targets: targets, covered: covered, dur: time.Since(t0), err: err}
499 }()
500 return p
501}
502
503// wait returns the result of the query.
504func (p *pendingSource) wait() atspiResult {
505 <-p.done
506 return p.res
507}