cthulhu/internal/atspi/text.go

// Cthulhu screen reader.
// Copyright (c) 2026 Storm Dragon
// Authors: Storm Dragon, Angus Kola
//
// This program is free software: you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the Free
// Software Foundation, either version 3 of the License, or (at your option)
// any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
// more details.
//
// You should have received a copy of the GNU General Public License along with
// this program. If not, see <https://www.gnu.org/licenses/gpl-3.0.html>.

package atspi

import (
	"context"
	"errors"
	"math"
	"strings"
	"unicode"
	"unicode/utf8"
)

const (
	// A large terminal viewport can contain thousands of padded cells.
	// Keep the per-line query and web line-repair budgets independently small.
	maxReviewCharacters       = 1 << 16
	maxReviewLineCharacters   = 4096
	maxReviewRanges           = 256
	maxTreeTextBytes          = 1 << 20
	maxReviewBoundsCharacters = 128
)

var ErrStaleText = errors.New("accessible text requires recapture")

var errReviewLineTooLong = errors.New("review line requires viewport retrieval")

// TextCaptureIssue describes omitted text without retaining provider content.
type TextCaptureIssue string

const (
	TextViewportUnavailable TextCaptureIssue = "viewport-unavailable"
	TextCharacterLimit      TextCaptureIssue = "character-limit"
	TextRangeLimit          TextCaptureIssue = "range-limit"
	TextTreeLimit           TextCaptureIssue = "tree-byte-limit"
	TextProviderFailure     TextCaptureIssue = "text-provider-failure"
	TextViewportScanLimit   TextCaptureIssue = "viewport-query-limit"
)

// TextRange owns exact UTF-8 text and AT-SPI character offsets [Start, End).
// Bounds are clipped screen coordinates. Offsets count Unicode code points,
// not bytes or grapheme clusters. Embedded objects have their own tree nodes.
type TextRange struct {
	Start, End int
	Text       string
	Bounds     Rectangle
}

// VisibleText distinguishes a complete capture from unavailable or oversized
// text. A limited capture contains no partial ranges. Known empty text is valid.
// Visibility describes component clipping, not occlusion by other windows.
type VisibleText struct {
	Known       bool
	Limited     bool
	Issue       TextCaptureIssue
	Ranges      []TextRange
	CaretKnown  bool
	CaretOffset int
}

func (text VisibleText) valid(geometry Geometry) bool {
	if text.CaretKnown && (!text.Known || text.CaretOffset < 0) || !text.CaretKnown && text.CaretOffset != 0 {
		return false
	}
	if text.Known && (text.Limited || text.Issue != "") || !text.Known && len(text.Ranges) != 0 || len(text.Ranges) > maxReviewRanges {
		return false
	}
	if text.Known && !geometry.BoundsKnown {
		return false
	}
	previous, characters := 0, 0
	for _, r := range text.Ranges {
		// Native offsets can include arbitrarily long offscreen scrollback.
		// Bound the captured characters, not their absolute source offsets.
		if r.Start < previous || r.End <= r.Start || !utf8.ValidString(r.Text) || utf8.RuneCountInString(r.Text) != r.End-r.Start || strings.ContainsRune(r.Text, '\ufffc') {
			return false
		}
		// A newline-only range represents a blank visual row. Mixed text
		// and line breaks must still be split by the capture provider.
		if strings.ContainsAny(r.Text, "\n\r") && strings.Trim(r.Text, "\n\r") != "" {
			return false
		}
		clipped, ok := r.Bounds.Intersection(geometry.Bounds)
		if !ok || clipped != r.Bounds {
			return false
		}
		previous = r.End
		characters += r.End - r.Start
	}
	return characters <= maxReviewCharacters
}

func (tree *AccessibleTree) VisibleText(reference ObjectReference) (VisibleText, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, err := tree.resolveLocked(reference)
	if err != nil {
		return VisibleText{}, err
	}
	if entry.textInvalid || entry.geometryInvalid {
		return VisibleText{}, ErrStaleText
	}
	text := entry.text
	text.Ranges = append([]TextRange(nil), text.Ranges...)
	return text, nil
}

// InvalidateText preserves identity and geometry. Layout invalidation also
// invalidates text via geometryInvalid, including every moved descendant.
func (tree *AccessibleTree) InvalidateText(id ObjectID) int {
	tree.mu.Lock()
	defer tree.mu.Unlock()
	entry, ok := tree.nodes[id]
	if !ok || entry.textInvalid {
		return 0
	}
	entry.textInvalid = true
	entry.text = VisibleText{}
	tree.nodes[id] = entry
	return 1
}

type reviewTextSource interface {
	count(context.Context) (int, error)
	line(context.Context, int) (TextRange, error)
	bounds(context.Context, int, int) (Rectangle, error)
}

// Optional spatial retrieval avoids requesting an entire enormous native line.
// Implementations must bound copied characters and ranges before returning.
type reviewViewportSource interface {
	viewport(context.Context, int, int, Rectangle) ([]TextRange, error)
}

// bounded_review_bounds preserves the full range's bounding rectangle without
// asking a provider to measure thousands of characters in one synchronous call.
// GTK text cells can exceed libatspi's timeout on such requests. Union every
// chunk rather than inferring bounds from endpoints, which would lose bidi runs.
func bounded_review_bounds(ctx context.Context, start, end int, query func(context.Context, int, int) (Rectangle, error)) (Rectangle, error) {
	var bounds Rectangle
	for offset := start; offset < end; {
		if err := ctx.Err(); err != nil {
			return Rectangle{}, err
		}
		next := offset + min(end-offset, maxReviewBoundsCharacters)
		chunk, err := query(ctx, offset, next)
		if err != nil {
			return Rectangle{}, err
		}
		offset = next
		// Formatting characters can have no rectangle; other chunks still
		// contribute to the complete range, just as in the provider's union.
		if !chunk.Valid() {
			continue
		}
		if !bounds.Valid() {
			bounds = chunk
			continue
		}
		left, top := min(bounds.X, chunk.X), min(bounds.Y, chunk.Y)
		right := max(int64(bounds.X)+int64(bounds.Width), int64(chunk.X)+int64(chunk.Width))
		bottom := max(int64(bounds.Y)+int64(bounds.Height), int64(chunk.Y)+int64(chunk.Height))
		if right-int64(left) > math.MaxInt32 || bottom-int64(top) > math.MaxInt32 {
			return Rectangle{}, errors.New("review range bounds exceed coordinate limits")
		}
		bounds = Rectangle{left, top, int32(right - int64(left)), int32(bottom - int64(top))}
	}
	return bounds, ctx.Err()
}

// VTE can report UTF-8 bytes as its character count while its text and line
// methods use character offsets. Locate the actual end with bounded single-
// character queries, without copying or scanning terminal scrollback.
func terminalCharacterCount(ctx context.Context, reported int, exists func(context.Context, int) (bool, error)) (int, error) {
	if reported <= 0 {
		return reported, ctx.Err()
	}
	present, err := exists(ctx, reported-1)
	if err != nil || present {
		return reported, err
	}
	low, high := 0, reported-1
	for low < high {
		if err := ctx.Err(); err != nil {
			return 0, err
		}
		middle := low + (high-low)/2
		present, err := exists(ctx, middle)
		if err != nil {
			return 0, err
		}
		if present {
			low = middle + 1
		} else {
			high = middle
		}
	}
	return low, ctx.Err()
}

// captureVisibleText finds the visible portion of native text before walking
// its visual lines. This avoids starting at an offscreen terminal scrollback
// offset: some terminal providers return the first on-screen line when asked
// for offset zero, with a later reported start offset.
func captureVisibleText(ctx context.Context, source reviewTextSource, clip Rectangle) (VisibleText, error) {
	unknown := VisibleText{}
	if err := ctx.Err(); err != nil {
		return unknown, err
	}
	count, err := source.count(ctx)
	if err != nil {
		return unknown, err
	}
	if count < 0 {
		return unknown, errors.New("negative review character count")
	}
	start, end, err := visibleTextOffsets(ctx, source, count, clip)
	if err != nil && count > maxReviewCharacters {
		if ctx.Err() != nil {
			return unknown, ctx.Err()
		}
		start, end, err = visible_line_offsets(ctx, source, count, clip)
	}
	if err != nil {
		if ctx.Err() != nil {
			return unknown, ctx.Err()
		}
		if count > maxReviewCharacters {
			return capture_review_viewport(ctx, source, count, clip, TextViewportUnavailable)
		}
		// Some otherwise usable GTK text providers do not expose per-character
		// extents. Retain the established bounded line capture for those small
		// objects; large providers still need a viewport to avoid scrollback.
		start, end = 0, count
	}
	if end-start > maxReviewCharacters {
		if spatial, ok := source.(reviewViewportSource); ok {
			ranges, spatialErr := spatial.viewport(ctx, start, end, clip)
			if spatialErr == nil && len(ranges) > 0 {
				return capture_review_lines(ctx, source, count, 0, count, clip, ranges)
			}
			if errors.Is(spatialErr, errReviewViewportScanLimit) {
				return VisibleText{Limited: true, Issue: TextViewportScanLimit}, ctx.Err()
			}
			if ctx.Err() != nil {
				return unknown, ctx.Err()
			}
		}
	}
	if end-start > maxReviewCharacters {
		return VisibleText{Limited: true, Issue: TextCharacterLimit}, nil
	}
	return capture_review_lines(ctx, source, count, start, end, clip, nil)
}

func capture_review_lines(ctx context.Context, source reviewTextSource, count, start, end int, clip Rectangle, spatial []TextRange) (VisibleText, error) {
	unknown := VisibleText{}
	if spatial != nil {
		if err := validate_viewport_ranges(spatial, count); err != nil {
			return unknown, err
		}
		spatial = split_viewport_lines(spatial)
	}
	result := VisibleText{Known: true}
	characters := 0
	for offset, lines := start, 0; offset < end; lines++ {
		if err := ctx.Err(); err != nil {
			return unknown, err
		}
		if spatial != nil && lines == len(spatial) {
			break
		}
		if lines >= maxReviewRanges {
			return VisibleText{Limited: true, Issue: TextRangeLimit}, nil
		}
		var line TextRange
		var err error
		if spatial != nil {
			line = spatial[lines]
			if line.Start < offset {
				return unknown, errors.New("unordered review viewport ranges")
			}
			offset = line.Start
		} else {
			line, err = source.line(ctx, offset)
		}
		if errors.Is(err, errReviewLineTooLong) {
			return capture_review_viewport(ctx, source, count, clip, TextCharacterLimit)
		}
		if err != nil {
			return unknown, err
		}
		// Some AT-SPI providers return a line whose reported start is just
		// after the requested offset. Python Cthulhu retries one character
		// earlier for that provider quirk before rejecting the capture.
		if spatial == nil && line.Start > offset && offset > 0 {
			line, err = source.line(ctx, offset-1)
			if err != nil {
				return unknown, err
			}
		}
		if line.Start < 0 || line.Start > offset || line.End <= offset || line.End > count || len(line.Text) > maxReviewCharacters*utf8.UTFMax || !utf8.ValidString(line.Text) || utf8.RuneCountInString(line.Text) != line.End-line.Start {
			return unknown, errors.New("invalid review line offsets or content")
		}
		lineStart := max(line.Start, offset)
		lineEnd := min(line.End, end)
		characters += lineEnd - lineStart
		if characters > maxReviewCharacters {
			return VisibleText{Limited: true, Issue: TextCharacterLimit}, nil
		}
		runes := []rune(line.Text)[lineStart-line.Start : lineEnd-line.Start]
		// Python retains newline-only TextZones. Keep their exact offsets and
		// native bounds so empty terminal rows remain navigable and speak blank.
		blankLine := len(runes) > 0 && strings.Trim(string(runes), "\n\r") == ""
		for start := 0; start < len(runes); {
			if !blankLine && (runes[start] == '\n' || runes[start] == '\r') || runes[start] == '\ufffc' {
				start++
				continue
			}
			end := start + 1
			if blankLine {
				// Some terminal providers combine consecutive empty visual rows
				// into one newline-only line range. Preserve each row as its own
				// range so line review can advance through all of them. Treat CRLF
				// as one row rather than two.
				if runes[start] == '\r' && end < len(runes) && runes[end] == '\n' {
					end++
				}
			} else {
				for end < len(runes) && runes[end] != '\n' && runes[end] != '\r' && runes[end] != '\ufffc' {
					end++
				}
			}
			bounds, err := source.bounds(ctx, lineStart+start, lineStart+end)
			if err != nil {
				return unknown, err
			}
			if !bounds.Valid() {
				return unknown, errors.New("unavailable review line geometry")
			}
			clipped, visible := bounds.Intersection(clip)
			singleRow := true
			if spatial != nil && visible && end-start > 1 {
				first, firstErr := source.bounds(ctx, lineStart+start, lineStart+start+1)
				last, lastErr := source.bounds(ctx, lineStart+end-1, lineStart+end)
				if firstErr != nil || lastErr != nil {
					return unknown, errors.Join(firstErr, lastErr)
				}
				singleRow = first.Valid() && last.Valid() && first.Y == last.Y && first.Height == last.Height
			}
			if visible && singleRow && (clipped == bounds || clipped.X == bounds.X && clipped.Width == bounds.Width) {
				// Vertical clipping of one visual row does not hide letters.
				// This also supports providers with only line rectangles.
				result.Ranges = append(result.Ranges, TextRange{lineStart + start, lineStart + end, string(runes[start:end]), clipped})
			} else if visible {
				// A clipped rectangle alone cannot hide offscreen characters. Check each
				// visible character, preserving disjoint spans. Reject offscreen blocks
				// first so a horizontally clipped long line does not require thousands
				// of individual provider calls. Test every block for bidi text.
				// Keep consecutive visible characters on the same visual row in
				// one range. The budget bounds spans, not individual glyphs.
				// Flush at an offset gap so bidi runs never include hidden text.
				spanStart, spanEnd := -1, -1
				var spanBounds Rectangle
				flushSpan := func() {
					if spanStart >= 0 {
						result.Ranges = append(result.Ranges, TextRange{lineStart + spanStart, lineStart + spanEnd, string(runes[spanStart:spanEnd]), spanBounds})
						spanStart = -1
					}
				}
				for blockStart := start; blockStart < end; {
					blockEnd := blockStart + min(end-blockStart, maxReviewBoundsCharacters)
					if end-start > maxReviewBoundsCharacters {
						blockBounds, err := source.bounds(ctx, lineStart+blockStart, lineStart+blockEnd)
						if err != nil {
							return unknown, err
						}
						if _, ok := blockBounds.Intersection(clip); !ok {
							blockStart = blockEnd
							continue
						}
					}
					for i := blockStart; i < blockEnd; i++ {
						if err := ctx.Err(); err != nil {
							return unknown, err
						}
						charBounds, err := source.bounds(ctx, lineStart+i, lineStart+i+1)
						if err != nil {
							return unknown, err
						}
						charClip, ok := charBounds.Intersection(clip)
						if !charBounds.Valid() && spanEnd == i && spanStart >= 0 && review_cluster_continuation(runes[i]) {
							// Combining marks and joiners belong to the visible base
							// even when they have no independent glyph rectangle.
							charClip, ok = spanBounds, true
						}
						if ok {
							if spanStart >= 0 && (spanEnd != i || spanBounds.Y != charClip.Y || spanBounds.Height != charClip.Height) {
								flushSpan()
							}
							if spanStart < 0 {
								spanStart, spanBounds = i, charClip
							} else {
								left := min(spanBounds.X, charClip.X)
								right := max(int64(spanBounds.X)+int64(spanBounds.Width), int64(charClip.X)+int64(charClip.Width))
								spanBounds.X, spanBounds.Width = left, int32(right-int64(left))
							}
							spanEnd = i + 1
						}
						if len(result.Ranges) > maxReviewRanges {
							return VisibleText{Limited: true, Issue: TextRangeLimit}, nil
						}
					}
					blockStart = blockEnd
				}
				flushSpan()
			}
			if len(result.Ranges) > maxReviewRanges {
				return VisibleText{Limited: true, Issue: TextRangeLimit}, nil
			}
			start = end
		}
		offset = max(line.End, offset+1)
	}
	return result, ctx.Err()
}

func review_cluster_continuation(character rune) bool {
	return unicode.IsMark(character) || character == '\u200c' || character == '\u200d'
}

// visibleTextOffsets uses character extents only to locate the native viewport;
// the returned text remains line-based. AT-SPI text offsets are ordered by
// visual rows for the providers supported by flat review, allowing bounded
// binary searches instead of a scan through terminal scrollback.
func visibleTextOffsets(ctx context.Context, source reviewTextSource, count int, clip Rectangle) (int, int, error) {
	if count == 0 {
		return 0, 0, nil
	}
	if !clip.Valid() {
		return 0, 0, errors.New("invalid review text clip")
	}
	bottom := int64(clip.Y) + int64(clip.Height)
	first, err := searchTextOffset(ctx, source, count, func(bounds Rectangle) bool {
		return int64(bounds.Y)+int64(bounds.Height) > int64(clip.Y)
	})
	if err != nil {
		return 0, 0, err
	}
	if first == count {
		return count, count, nil
	}
	end, err := searchTextOffset(ctx, source, count, func(bounds Rectangle) bool {
		return int64(bounds.Y) >= bottom
	})
	if err != nil {
		return 0, 0, err
	}
	if end < first {
		return 0, 0, errors.New("invalid review text viewport order")
	}
	return first, end, nil
}

func searchTextOffset(ctx context.Context, source reviewTextSource, count int, after func(Rectangle) bool) (int, error) {
	low, high := 0, count
	for low < high {
		if err := ctx.Err(); err != nil {
			return 0, err
		}
		middle := low + (high-low)/2
		bounds, err := source.bounds(ctx, middle, middle+1)
		if err != nil {
			return 0, err
		}
		if !bounds.Valid() {
			return 0, errors.New("invalid review character bounds")
		}
		if after(bounds) {
			high = middle
		} else {
			low = middle + 1
		}
	}
	return low, nil
}

// recover_review_component distinguishes synthetic Text interfaces from failed
// text-bearing objects. It never invents offsets or uses editable values as names.
// A label is usable only when it exactly matches the bounded native text and the
// component is fully inside the clip. Embedded-only text belongs to children.
func recover_review_component(ctx context.Context, source interface {
	reviewTextSource
	reviewSpanSource
}, snapshot Snapshot, geometry Geometry, clip Rectangle) (VisibleText, bool) {
	if snapshot.Editable {
		return VisibleText{}, false
	}
	label := false
	switch snapshot.Role {
	case "button", "push button", "toggle button", "check box", "radio button", "page tab",
		"menu item", "check menu item", "radio menu item", "link", "label", "static", "separator":
		label = true
	case "frame", "panel", "tool bar", "page tab list", "alert", "menu", "menu bar":
	default:
		return VisibleText{}, false
	}
	count, err := source.count(ctx)
	if err != nil || count <= 0 || count > maxReviewLineCharacters {
		return VisibleText{}, false
	}
	var content strings.Builder
	for start := 0; start < count; {
		end := start + min(count-start, maxReviewBoundsCharacters)
		span, err := source.text_span(ctx, start, end)
		if err != nil || !utf8.ValidString(span) || utf8.RuneCountInString(span) != end-start {
			return VisibleText{}, false
		}
		content.WriteString(span)
		start = end
	}
	if ctx.Err() != nil {
		return VisibleText{}, false
	}
	value := content.String()
	if strings.Trim(value, "\ufffc") == "" {
		// Review will visit the embedded children and count unavailable
		// subtrees separately. No text of this object's own was lost.
		return VisibleText{Known: true}, true
	}
	if label && snapshot.Name != "" && value == snapshot.Name && geometry.BoundsKnown && geometry.Bounds == clip {
		// Leave text unknown: layout uses the existing synthetic name path
		// only if children do not already supply displayed content.
		return VisibleText{}, true
	}
	return VisibleText{}, false
}