cthulhu/internal/atspi/tree.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 (
	"errors"
	"fmt"
	"sync"
)

// Large browser documents can expose more than ten thousand accessible nodes.
// Capture still has a time limit and a finite node budget on the native thread.
const maxTreeNodes = 30000

var (
	ErrStaleGeometry  = errors.New("accessible geometry requires recapture")
	ErrIncompleteTree = errors.New("accessible children require recapture")
	ErrInvalidTree    = errors.New("invalid accessible tree")
	ErrDeadObject     = errors.New("defunct accessible object")
	ErrObjectNotFound = errors.New("accessible object not found")
	ErrStaleObject    = errors.New("stale accessible object")
	ErrStaleSnapshot  = errors.New("accessible semantics require recapture")
)

// TreeNode is an owned, immutable accessible snapshot and the identities of
// its children in application-provided order. NewAccessibleTree and Replace
// copy Children before retaining a node.
type TreeNode struct {
	Geometry Geometry
	Text     VisibleText
	Snapshot Snapshot
	Children []ObjectID
}

// ObjectReference is a generation-checked reference to an owned snapshot. A
// reference becomes stale when its object or an ancestor is invalidated, or
// when a replacement tree no longer contains that object.
type ObjectReference struct {
	id         ObjectID
	generation uint64
}

func (reference ObjectReference) ID() ObjectID {
	return reference.id
}

func (reference ObjectReference) Valid() bool {
	return reference.id.Valid() && reference.generation != 0
}

type treeEntry struct {
	snapshotInvalid bool
	text            VisibleText
	textInvalid     bool
	geometry        Geometry
	geometryInvalid bool
	childrenInvalid bool
	snapshot        Snapshot
	children        []ObjectID
	parent          ObjectID
	hasParent       bool
	generation      uint64
}

// AccessibleTree owns a validated accessibility tree. It contains no native
// references and supports concurrent readers while events replace or
// invalidate cached objects.
type AccessibleTree struct {
	mu             sync.RWMutex
	root           ObjectID
	nodes          map[ObjectID]treeEntry
	nextGeneration uint64
}

func NewAccessibleTree(root ObjectID, nodes []TreeNode) (*AccessibleTree, error) {
	tree := &AccessibleTree{}
	if err := tree.Replace(root, nodes); err != nil {
		return nil, err
	}
	return tree, nil
}

// Replace atomically installs a complete tree. References to identities that
// remain live retain their generation; removed identities become stale. If an
// invalidated identity later reappears, it receives a new generation.
func (tree *AccessibleTree) Replace(root ObjectID, nodes []TreeNode) error {
	next, err := validateTree(root, nodes)
	if err != nil {
		return err
	}

	tree.mu.Lock()
	defer tree.mu.Unlock()
	for id, entry := range next {
		if current, ok := tree.nodes[id]; ok {
			entry.generation = current.generation
		} else {
			tree.nextGeneration++
			if tree.nextGeneration == 0 {
				// Reaching this would require creating more than 2^64 distinct
				// object generations in one process. Keep zero reserved for an
				// invalid reference if it nevertheless occurs.
				tree.nextGeneration++
			}
			entry.generation = tree.nextGeneration
		}
		next[id] = entry
	}
	tree.root = root
	tree.nodes = next
	return nil
}

func (tree *AccessibleTree) Root() (ObjectReference, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, ok := tree.nodes[tree.root]
	if !ok {
		return ObjectReference{}, ErrObjectNotFound
	}
	return newObjectReference(tree.root, entry), nil
}

func (tree *AccessibleTree) Reference(id ObjectID) (ObjectReference, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, ok := tree.nodes[id]
	if !ok {
		return ObjectReference{}, fmt.Errorf("%w: bus %q path %q", ErrObjectNotFound, id.BusName, id.Path)
	}
	return newObjectReference(id, entry), nil
}

func (tree *AccessibleTree) Resolve(reference ObjectReference) (Snapshot, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, err := tree.resolveLocked(reference)
	if err != nil {
		return Snapshot{}, err
	}
	return entry.snapshot, nil
}

// InvalidateSnapshot refreshes presentation and matching data without retiring
// a live identity. A renamed button is still the same browse-caret position.
func (tree *AccessibleTree) InvalidateSnapshot(id ObjectID) int {
	tree.mu.Lock()
	defer tree.mu.Unlock()
	entry, ok := tree.nodes[id]
	if !ok || entry.snapshotInvalid {
		return 0
	}
	entry.snapshotInvalid = true
	tree.nodes[id] = entry
	return 1
}

// nativeRefresh copies a dirty tree for incremental native recapture.
// Unchanged nodes and child lists can be reused; dirty fields and newly added
// objects must be read from the provider. A missing or replaced root cannot
// inherit this cache.
func (tree *AccessibleTree) nativeRefresh(root ObjectID) map[ObjectID]treeEntry {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	if tree.root != root {
		return nil
	}
	if _, ok := tree.nodes[root]; !ok {
		return nil
	}
	dirty := false
	nodes := make(map[ObjectID]treeEntry, len(tree.nodes))
	for id, entry := range tree.nodes {
		dirty = dirty || entry.snapshotInvalid || entry.childrenInvalid || entry.textInvalid || entry.geometryInvalid
		entry.children = append([]ObjectID(nil), entry.children...)
		entry.text.Ranges = append([]TextRange(nil), entry.text.Ranges...)
		nodes[id] = entry
	}
	if !dirty {
		return nil
	}
	return nodes
}

// subtreeIDs returns the captured identities rooted at reference. It is used
// only by the native adapter to classify the bounded burst of caret/focus and
// defunct events produced by browser caret placement. No native references
// escape through this copy.
func (tree *AccessibleTree) subtreeIDs(reference ObjectReference) ([]ObjectID, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	if _, err := tree.resolveLocked(reference); err != nil {
		return nil, err
	}
	result := make([]ObjectID, 0, 4)
	pending := []ObjectID{reference.id}
	for len(pending) != 0 {
		last := len(pending) - 1
		id := pending[last]
		pending = pending[:last]
		entry, ok := tree.nodes[id]
		if !ok {
			return nil, ErrIncompleteTree
		}
		result = append(result, id)
		pending = append(pending, entry.children...)
	}
	return result, nil
}

// Geometry returns capture-time screen bounds, or ErrStaleGeometry after a
// layout/visibility event. Structural identity remains live across such events.
func (tree *AccessibleTree) Geometry(reference ObjectReference) (Geometry, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, err := tree.resolveLocked(reference)
	if err != nil {
		return Geometry{}, err
	}
	if entry.geometryInvalid {
		return Geometry{}, ErrStaleGeometry
	}
	return entry.geometry, nil
}

// InvalidateGeometry marks an object's subtree for recapture without changing
// focus snapshots, identity generations, or child/sibling traversal. Moving a
// container can move every descendant. Work is bounded by maxTreeNodes.
func (tree *AccessibleTree) InvalidateGeometry(id ObjectID) int {
	tree.mu.Lock()
	defer tree.mu.Unlock()
	pending := []ObjectID{id}
	invalidated := 0
	for len(pending) != 0 {
		last := len(pending) - 1
		currentID := pending[last]
		pending = pending[:last]
		entry, ok := tree.nodes[currentID]
		if !ok || entry.geometryInvalid {
			// A marked ancestor already marked its entire subtree. Only a
			// complete Replace can introduce fresh descendants.
			continue
		}
		pending = append(pending, entry.children...)
		invalidated++
		entry.geometryInvalid = true
		tree.nodes[currentID] = entry
	}
	return invalidated
}

func (tree *AccessibleTree) Parent(reference ObjectReference) (ObjectReference, bool, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, err := tree.resolveLocked(reference)
	if err != nil {
		return ObjectReference{}, false, err
	}
	if !entry.hasParent {
		return ObjectReference{}, false, nil
	}
	parent := tree.nodes[entry.parent]
	return newObjectReference(entry.parent, parent), true, nil
}

func (tree *AccessibleTree) FirstChild(reference ObjectReference) (ObjectReference, bool, error) {
	return tree.child(reference, false)
}

func (tree *AccessibleTree) LastChild(reference ObjectReference) (ObjectReference, bool, error) {
	return tree.child(reference, true)
}

func (tree *AccessibleTree) child(reference ObjectReference, last bool) (ObjectReference, bool, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, err := tree.resolveLocked(reference)
	if err != nil {
		return ObjectReference{}, false, err
	}
	if entry.childrenInvalid {
		return ObjectReference{}, false, ErrIncompleteTree
	}
	if len(entry.children) == 0 {
		return ObjectReference{}, false, nil
	}
	index := 0
	if last {
		index = len(entry.children) - 1
	}
	id := entry.children[index]
	return newObjectReference(id, tree.nodes[id]), true, nil
}

func (tree *AccessibleTree) PreviousSibling(reference ObjectReference) (ObjectReference, bool, error) {
	return tree.sibling(reference, -1)
}

func (tree *AccessibleTree) NextSibling(reference ObjectReference) (ObjectReference, bool, error) {
	return tree.sibling(reference, 1)
}

func (tree *AccessibleTree) sibling(reference ObjectReference, direction int) (ObjectReference, bool, error) {
	tree.mu.RLock()
	defer tree.mu.RUnlock()
	entry, err := tree.resolveLocked(reference)
	if err != nil {
		return ObjectReference{}, false, err
	}
	if !entry.hasParent {
		return ObjectReference{}, false, nil
	}
	parent := tree.nodes[entry.parent]
	for index, id := range parent.children {
		if id != reference.id {
			continue
		}
		siblingIndex := index + direction
		if siblingIndex < 0 || siblingIndex >= len(parent.children) {
			return ObjectReference{}, false, nil
		}
		siblingID := parent.children[siblingIndex]
		return newObjectReference(siblingID, tree.nodes[siblingID]), true, nil
	}
	return ObjectReference{}, false, fmt.Errorf("%w: parent does not contain child", ErrInvalidTree)
}

// Invalidate removes an object and all of its descendants. It returns the
// number of removed objects. An unknown identity is an idempotent no-op.
func (tree *AccessibleTree) Invalidate(id ObjectID) int {
	tree.mu.Lock()
	defer tree.mu.Unlock()
	entry, ok := tree.nodes[id]
	if !ok {
		return 0
	}
	if entry.hasParent {
		parent := tree.nodes[entry.parent]
		for index, childID := range parent.children {
			if childID == id {
				parent.children = append(parent.children[:index:index], parent.children[index+1:]...)
				tree.nodes[entry.parent] = parent
				break
			}
		}
	}

	removed := 0
	pending := []ObjectID{id}
	for len(pending) != 0 {
		last := len(pending) - 1
		currentID := pending[last]
		pending = pending[:last]
		current, present := tree.nodes[currentID]
		if !present {
			continue
		}
		pending = append(pending, current.children...)
		delete(tree.nodes, currentID)
		removed++
	}
	return removed
}

// InvalidateChildren removes every descendant of a live parent while keeping
// the parent reference valid. Structural additions use this conservative path
// because the cached child order is no longer complete until the next capture.
// Child traversal returns ErrIncompleteTree until Replace installs a fresh tree;
// the parent snapshot and its own parent/sibling relationships remain usable.
func (tree *AccessibleTree) InvalidateChildren(parentID ObjectID) int {
	tree.mu.Lock()
	defer tree.mu.Unlock()
	parent, ok := tree.nodes[parentID]
	if !ok {
		return 0
	}
	pending := append([]ObjectID(nil), parent.children...)
	parent.children = nil
	parent.childrenInvalid = true
	tree.nodes[parentID] = parent
	removed := 0
	for len(pending) != 0 {
		last := len(pending) - 1
		currentID := pending[last]
		pending = pending[:last]
		current, present := tree.nodes[currentID]
		if !present {
			continue
		}
		pending = append(pending, current.children...)
		delete(tree.nodes, currentID)
		removed++
	}
	return removed
}

// MarkChildrenChanged requires fresh child order without declaring the existing
// children dead. A document insertion does not replace its surviving siblings.
// Document traversal refuses the old order until Replace validates the capture;
// explicit removals and lifecycle events still retire their object generations.
func (tree *AccessibleTree) MarkChildrenChanged(parentID ObjectID) int {
	tree.mu.Lock()
	defer tree.mu.Unlock()
	parent, ok := tree.nodes[parentID]
	if !ok || parent.childrenInvalid {
		return 0
	}
	parent.childrenInvalid = true
	tree.nodes[parentID] = parent
	return 1
}

func (tree *AccessibleTree) resolveLocked(reference ObjectReference) (treeEntry, error) {
	entry, ok := tree.nodes[reference.id]
	if !ok {
		if reference.Valid() {
			return treeEntry{}, fmt.Errorf("%w: bus %q path %q", ErrStaleObject, reference.id.BusName, reference.id.Path)
		}
		return treeEntry{}, fmt.Errorf("%w: bus %q path %q", ErrObjectNotFound, reference.id.BusName, reference.id.Path)
	}
	if reference.generation == 0 || reference.generation != entry.generation {
		return treeEntry{}, fmt.Errorf("%w: bus %q path %q", ErrStaleObject, reference.id.BusName, reference.id.Path)
	}
	if entry.snapshotInvalid {
		return treeEntry{}, ErrStaleSnapshot
	}
	return entry, nil
}

func newObjectReference(id ObjectID, entry treeEntry) ObjectReference {
	return ObjectReference{id: id, generation: entry.generation}
}

func validateTree(root ObjectID, nodes []TreeNode) (map[ObjectID]treeEntry, error) {
	if !root.Valid() {
		return nil, fmt.Errorf("%w: root identity is empty", ErrInvalidTree)
	}
	if len(nodes) == 0 {
		return nil, fmt.Errorf("%w: tree is empty", ErrInvalidTree)
	}
	if len(nodes) > maxTreeNodes {
		return nil, fmt.Errorf("%w: %d nodes exceeds limit %d", ErrInvalidTree, len(nodes), maxTreeNodes)
	}

	entries := make(map[ObjectID]treeEntry, len(nodes))
	textBytes := 0
	for _, node := range nodes {
		id := node.Snapshot.ID()
		if !id.Valid() {
			return nil, fmt.Errorf("%w: node identity is empty", ErrInvalidTree)
		}
		if _, exists := entries[id]; exists {
			return nil, fmt.Errorf("%w: duplicate bus %q path %q", ErrInvalidTree, id.BusName, id.Path)
		}
		if node.Snapshot.Defunct {
			return nil, fmt.Errorf("%w: %w at bus %q path %q", ErrInvalidTree, ErrDeadObject, id.BusName, id.Path)
		}
		if !node.Geometry.valid() {
			return nil, fmt.Errorf("%w: invalid component geometry", ErrInvalidTree)
		}
		if !node.Text.valid(node.Geometry) {
			return nil, fmt.Errorf("%w: invalid visible text", ErrInvalidTree)
		}
		for _, r := range node.Text.Ranges {
			textBytes += len(r.Text)
		}
		if textBytes > maxTreeTextBytes {
			return nil, fmt.Errorf("%w: visible text exceeds tree limit", ErrInvalidTree)
		}
		text := node.Text
		text.Ranges = append([]TextRange(nil), text.Ranges...)
		children := append([]ObjectID(nil), node.Children...)
		entries[id] = treeEntry{snapshot: node.Snapshot, children: children, geometry: node.Geometry, text: text}
	}
	if _, ok := entries[root]; !ok {
		return nil, fmt.Errorf("%w: root is missing", ErrInvalidTree)
	}

	parents := make(map[ObjectID]ObjectID, len(nodes)-1)
	for parentID, entry := range entries {
		seenChildren := make(map[ObjectID]struct{}, len(entry.children))
		for _, childID := range entry.children {
			if !childID.Valid() {
				return nil, fmt.Errorf("%w: child identity is empty", ErrInvalidTree)
			}
			if _, exists := entries[childID]; !exists {
				return nil, fmt.Errorf("%w: child bus %q path %q is missing", ErrInvalidTree, childID.BusName, childID.Path)
			}
			if _, duplicate := seenChildren[childID]; duplicate {
				return nil, fmt.Errorf("%w: duplicate child bus %q path %q", ErrInvalidTree, childID.BusName, childID.Path)
			}
			seenChildren[childID] = struct{}{}
			if _, exists := parents[childID]; exists {
				return nil, fmt.Errorf("%w: child bus %q path %q has multiple parents", ErrInvalidTree, childID.BusName, childID.Path)
			}
			parents[childID] = parentID
		}
	}
	if _, hasParent := parents[root]; hasParent {
		return nil, fmt.Errorf("%w: root has a parent", ErrInvalidTree)
	}
	for id, entry := range entries {
		parent, hasParent := parents[id]
		if id != root && !hasParent {
			return nil, fmt.Errorf("%w: bus %q path %q is disconnected", ErrInvalidTree, id.BusName, id.Path)
		}
		entry.parent = parent
		entry.hasParent = hasParent
		entries[id] = entry
	}

	visited := make(map[ObjectID]bool, len(entries))
	active := make(map[ObjectID]bool, len(entries))
	var visit func(ObjectID) error
	visit = func(id ObjectID) error {
		if active[id] {
			return fmt.Errorf("%w: cycle at bus %q path %q", ErrInvalidTree, id.BusName, id.Path)
		}
		if visited[id] {
			return nil
		}
		active[id] = true
		for _, childID := range entries[id].children {
			if err := visit(childID); err != nil {
				return err
			}
		}
		active[id] = false
		visited[id] = true
		return nil
	}
	if err := visit(root); err != nil {
		return nil, err
	}
	if len(visited) != len(entries) {
		return nil, fmt.Errorf("%w: tree contains unreachable nodes", ErrInvalidTree)
	}
	return entries, nil
}