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"
	"strings"
	"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
)

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

// 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
	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.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)
}

// 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 {
		if count > maxReviewCharacters {
			return VisibleText{Limited: true}, nil
		}
		// 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 {
		return VisibleText{Limited: true}, nil
	}
	result := VisibleText{Known: true}
	for offset, lines := start, 0; offset < end; lines++ {
		if err := ctx.Err(); err != nil {
			return unknown, err
		}
		if lines >= maxReviewRanges {
			return VisibleText{Limited: true}, nil
		}
		line, err := source.line(ctx, offset)
		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 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) > maxReviewLineCharacters*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)
		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
			}
			clipped, visible := bounds.Intersection(clip)
			if visible && clipped == bounds {
				result.Ranges = append(result.Ranges, TextRange{lineStart + start, lineStart + end, string(runes[start:end]), bounds})
			} else if visible {
				// A clipped rectangle alone cannot hide offscreen characters. Check each
				// character only for partially clipped runs, preserving disjoint spans.
				for i := start; i < end; 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
					}
					if charClip, ok := charBounds.Intersection(clip); ok {
						result.Ranges = append(result.Ranges, TextRange{lineStart + i, lineStart + i + 1, string(runes[i]), charClip})
					}
					if len(result.Ranges) > maxReviewRanges {
						return VisibleText{Limited: true}, nil
					}
				}
			}
			if len(result.Ranges) > maxReviewRanges {
				return VisibleText{Limited: true}, nil
			}
			start = end
		}
		offset = max(line.End, offset+1)
	}
	return result, ctx.Err()
}

// 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
}