cthulhu/internal/review/document.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 review

import (
	"context"
	"errors"
	"strings"
	"sync"

	"git.stormux.org/storm/cthulhu/internal/atspi"
)

// NavigationOrigin distinguishes native focus from document navigation for
// the future browse/focus-mode policy. Flat review never changes this cursor.
type NavigationOrigin uint8

const (
	NativeNavigation NavigationOrigin = iota
	StructuralNavigation
	CaretNavigation
)

type DocumentPosition struct {
	Document atspi.ObjectReference
	Object   atspi.ObjectReference
	Snapshot atspi.Snapshot
	// LinkedHeading is the link associated with a heading target, if any.
	LinkedHeading *atspi.Snapshot
	Origin        NavigationOrigin
	Offset        int
}

// DocumentMoveResult reports whether a semantic move crossed a document
// boundary and wrapped to the opposite end.
type DocumentMoveResult struct {
	Position DocumentPosition
	Moved    bool
	Wrapped  bool
}

type documentPlace struct {
	document              atspi.ObjectReference
	object                atspi.ObjectReference
	focus                 atspi.ObjectReference
	origin                NavigationOrigin
	offset                int
	tableCell             atspi.ObjectID
	tableRow, tableColumn int
}

// DocumentCursor remembers at most 16 document positions in least-recently-
// used order. Leaving a document suspends navigation without losing its place;
// invalidated/reused identities cannot inherit it. The caller owns the tree's
// capture/recapture lifecycle. Methods serialize cursor state and do no native
// work, key handling, focus changes, or speech.
type DocumentCursor struct {
	mu     sync.Mutex
	tree   *atspi.AccessibleTree
	places []documentPlace
	active atspi.ObjectReference
}

// rebindPlace keeps the selected target after a semantic refresh retires its
// old tree references between a move and native caret placement.
func (cursor *DocumentCursor) rebindPlace(tree *atspi.AccessibleTree, oldPosition, newPosition DocumentPosition) {
	cursor.mu.Lock()
	defer cursor.mu.Unlock()
	if cursor.tree != tree || len(cursor.places) == 0 {
		return
	}
	place := &cursor.places[len(cursor.places)-1]
	if place.document != oldPosition.Document || place.object != oldPosition.Object {
		return
	}
	place.document = newPosition.Document
	place.object = newPosition.Object
	if focus, err := tree.Reference(place.focus.ID()); err == nil {
		place.focus = focus
	}
	cursor.active = newPosition.Document
}

func NewDocumentCursor(tree *atspi.AccessibleTree) (*DocumentCursor, error) {
	if tree == nil {
		return nil, errors.New("create document cursor: nil accessible tree")
	}
	return &DocumentCursor{tree: tree}, nil
}

// ActivationTarget resolves the current browse position, including text
// children inside a link, without consulting the browser's retained focus.
func (cursor *DocumentCursor) ActivationTarget() (atspi.ObjectReference, error) {
	cursor.mu.Lock()
	defer cursor.mu.Unlock()
	if !cursor.active.Valid() || len(cursor.places) == 0 {
		return atspi.ObjectReference{}, ErrNoCurrent
	}
	place := cursor.places[len(cursor.places)-1]
	if place.document != cursor.active {
		return atspi.ObjectReference{}, ErrNoCurrent
	}
	current := place.object
	var clickable atspi.ObjectReference
	selectedHeading := false
	for depth := 0; depth < 128; depth++ {
		snapshot, err := cursor.tree.Resolve(current)
		if err != nil {
			return atspi.ObjectReference{}, err
		}
		if depth == 0 {
			selectedHeading = snapshot.Role == "heading"
		}
		if snapshot.Role == "link" {
			return current, nil
		}
		if !clickable.Valid() && snapshot.SupportsClick &&
			snapshot.Role != "document web" && snapshot.Role != "document frame" {
			clickable = current
		}
		if current == place.document {
			break
		}
		parent, ok, err := cursor.tree.Parent(current)
		if err != nil {
			return atspi.ObjectReference{}, err
		}
		if !ok {
			break
		}
		current = parent
	}
	if place.origin == StructuralNavigation && selectedHeading {
		doc, err := cursor.tree.Document(context.Background(), place.object)
		if err != nil {
			return atspi.ObjectReference{}, err
		}
		link, ok, ambiguous := linkedHeadingNode(doc, place.object)
		if ok {
			return link.Reference, nil
		}
		if ambiguous {
			return atspi.ObjectReference{}, ErrNoCurrent
		}
	}
	if clickable.Valid() {
		return clickable, nil
	}
	return atspi.ObjectReference{}, ErrNoCurrent
}

func (cursor *DocumentCursor) SyncFocus(ctx context.Context, focus atspi.ObjectID) (DocumentPosition, error) {
	cursor.mu.Lock()
	defer cursor.mu.Unlock()
	// Failed ownership resolution must never leave web navigation active for
	// the previous focus (e.g. address bar, another application, stale object).
	cursor.active = atspi.ObjectReference{}
	ref, err := cursor.tree.Reference(focus)
	if err != nil {
		return DocumentPosition{}, err
	}
	doc, err := cursor.tree.Document(ctx, ref)
	if err != nil {
		return DocumentPosition{}, err
	}
	place := documentPlace{document: doc.Context.TopLevel, object: ref, focus: ref}
	for index, saved := range cursor.places {
		if saved.document != place.document {
			continue
		}
		if saved.focus == ref || saved.object == ref {
			if _, ok := documentObject(doc, saved.object); ok {
				place = saved
				place.focus = ref
			}
		}
		cursor.places = append(cursor.places[:index], cursor.places[index+1:]...)
		break
	}
	if len(cursor.places) == 16 {
		cursor.places = cursor.places[1:]
	}
	cursor.places = append(cursor.places, place)
	cursor.active = place.document
	return documentPosition(doc, place), nil
}

// JumpToFragment follows a browser document load whose URI names an element.
// The browser has already scrolled to that element; keep the independent
// browse cursor with the first named link in its subtree when available.
func (cursor *DocumentCursor) JumpToFragment(ctx context.Context, fragment string) (DocumentPosition, bool, error) {
	cursor.mu.Lock()
	defer cursor.mu.Unlock()
	if !cursor.active.Valid() || len(cursor.places) == 0 || fragment == "" {
		return DocumentPosition{}, false, ErrNoCurrent
	}
	place := &cursor.places[len(cursor.places)-1]
	doc, err := cursor.tree.Document(ctx, place.object)
	if err != nil {
		return DocumentPosition{}, false, err
	}
	indexByID := make(map[atspi.ObjectID]int, len(doc.Nodes))
	for index, node := range doc.Nodes {
		indexByID[node.Reference.ID()] = index
	}
	var target *atspi.DocumentNode
	for index := range doc.Nodes {
		if doc.Nodes[index].Snapshot.ElementID != fragment || doc.Nodes[index].Hidden {
			continue
		}
		root := &doc.Nodes[index]
		target = root
		var namedDescendant *atspi.DocumentNode
		pending := append([]atspi.ObjectID(nil), root.Children...)
		for len(pending) > 0 {
			id := pending[0]
			pending = pending[1:]
			childIndex, ok := indexByID[id]
			if !ok {
				continue
			}
			child := &doc.Nodes[childIndex]
			if child.Hidden {
				continue
			}
			if namedDescendant == nil && child.Snapshot.Name != "" {
				namedDescendant = child
			}
			if child.Snapshot.Role == "link" && child.Snapshot.Name != "" {
				target = child
				break
			}
			pending = append(append([]atspi.ObjectID(nil), child.Children...), pending...)
		}
		if target == root && namedDescendant != nil {
			target = namedDescendant
		}
		break
	}
	if target == nil {
		return DocumentPosition{}, false, nil
	}
	place.object, place.offset, place.origin = target.Reference, 0, CaretNavigation
	return documentPosition(doc, *place), true, nil
}

type DocumentTarget uint8

const (
	DocumentHeading DocumentTarget = iota + 1
	DocumentLink
	DocumentButton
	DocumentCheckBox
	DocumentList
	DocumentSeparator
	DocumentBlockQuote
	DocumentComboBox
	DocumentEntry
	DocumentFormField
	DocumentImage
	DocumentLandmark
	DocumentListItem
	DocumentLiveRegion
	DocumentParagraph
	DocumentRadioButton
	DocumentTable
	DocumentUnvisitedLink
	DocumentVisitedLink
	DocumentClickable
	DocumentChunk
)

// Move searches in accessible tree order, wrapping once to the opposite end.
// Heading level zero means any level. This is a semantic traversal primitive,
// not yet the full Python structural-navigation policy or a native caret/focus
// operation.
func (cursor *DocumentCursor) Move(ctx context.Context, target DocumentTarget, level int, backwards bool) (DocumentMoveResult, error) {
	cursor.mu.Lock()
	defer cursor.mu.Unlock()
	if !validDocumentTarget(target) || level < 0 || level > 6 || target != DocumentHeading && level != 0 {
		return DocumentMoveResult{}, errors.New("invalid document navigation target")
	}
	if !cursor.active.Valid() || len(cursor.places) == 0 {
		return DocumentMoveResult{}, ErrNoCurrent
	}
	place := &cursor.places[len(cursor.places)-1]
	doc, err := cursor.tree.Document(ctx, place.object)
	if err != nil {
		return DocumentMoveResult{}, err
	}
	// Reparenting a live object into a different document must not transfer
	// the old document's cursor, even when the object's ID remains live.
	if doc.Context.TopLevel != place.document {
		return DocumentMoveResult{}, atspi.ErrStaleObject
	}
	index := -1
	for i, node := range doc.Nodes {
		if node.Reference == place.object {
			index = i
			break
		}
	}
	if index < 0 {
		return DocumentMoveResult{}, atspi.ErrStaleObject
	}
	// Python treats a focused descendant as being within its nearest matching
	// ancestor. Anchor the search there so previous navigation does not select
	// and reannounce the containing link, heading, or other target.
	indexByID := make(map[atspi.ObjectID]int, len(doc.Nodes))
	parentByID := make(map[atspi.ObjectID]atspi.ObjectID, len(doc.Nodes))
	for candidateIndex, node := range doc.Nodes {
		indexByID[node.Reference.ID()] = candidateIndex
		for _, child := range node.Children {
			parentByID[child] = node.Reference.ID()
		}
	}
	for parent := place.object.ID(); parent.Valid(); parent = parentByID[parent] {
		candidateIndex, ok := indexByID[parent]
		if !ok {
			break
		}
		if documentTargetMatches(target, doc.Nodes[candidateIndex], level) {
			index = candidateIndex
			break
		}
	}
	step := 1
	if backwards {
		step = -1
	}
	for i := index + step; i >= 0 && i < len(doc.Nodes); i += step {
		node := doc.Nodes[i]
		if node.Hidden {
			continue
		}
		match := documentTargetMatches(target, node, level)
		if match {
			place.tableCell = atspi.ObjectID{}
			place.object = node.Reference
			place.origin = StructuralNavigation
			place.offset = 0
			return DocumentMoveResult{Position: documentPosition(doc, *place), Moved: true}, nil
		}
	}
	firstMatch, lastMatch := -1, -1
	for i := 0; i < len(doc.Nodes); i++ {
		node := doc.Nodes[i]
		if node.Hidden {
			continue
		}
		if !documentTargetMatches(target, node, level) {
			continue
		}
		if firstMatch < 0 {
			firstMatch = i
		}
		lastMatch = i
	}
	wrappedIndex := firstMatch
	if backwards {
		wrappedIndex = lastMatch
	}
	if wrappedIndex >= 0 {
		node := doc.Nodes[wrappedIndex]
		place.tableCell = atspi.ObjectID{}
		place.object = node.Reference
		place.origin = StructuralNavigation
		place.offset = 0
		return DocumentMoveResult{
			Position: documentPosition(doc, *place),
			Moved:    true,
			Wrapped:  true,
		}, nil
	}
	return DocumentMoveResult{Position: documentPosition(doc, *place)}, nil
}

func validDocumentTarget(target DocumentTarget) bool {
	return target >= DocumentHeading && target <= DocumentChunk
}

func documentTargetMatches(target DocumentTarget, node atspi.DocumentNode, level int) bool {
	snapshot := node.Snapshot
	switch target {
	case DocumentHeading:
		return snapshot.Role == "heading" && (level == 0 || snapshot.HeadingLevel == level)
	case DocumentLink:
		return snapshot.Role == "link" && snapshot.Focusable
	case DocumentButton:
		return snapshot.Role == "button" || snapshot.Role == "push button" || snapshot.Role == "toggle button"
	case DocumentCheckBox:
		return snapshot.Role == "check box"
	case DocumentList:
		return snapshot.Role == "list"
	case DocumentSeparator:
		return snapshot.Role == "separator"
	case DocumentBlockQuote:
		return snapshot.Role == "block quote"
	case DocumentComboBox:
		return snapshot.Role == "combo box"
	case DocumentEntry:
		return snapshot.Editable && snapshot.Focusable && !node.ParentEditable
	case DocumentFormField:
		return snapshot.Focusable && documentFormFieldRole(snapshot)
	case DocumentImage:
		return snapshot.Role == "image" || snapshot.Role == "image map"
	case DocumentLandmark:
		return snapshot.Role == "landmark"
	case DocumentListItem:
		return snapshot.Role == "list item"
	case DocumentLiveRegion:
		return snapshot.LiveRegion
	case DocumentParagraph:
		if snapshot.Role == "heading" {
			return true
		}
		return snapshot.Role == "paragraph" && snapshot.CharacterCount > 2
	case DocumentRadioButton:
		return snapshot.Role == "radio button"
	case DocumentTable:
		return snapshot.Role == "table" && len(node.Children) != 0 && snapshot.TableRowCount > 0 && !snapshot.LayoutTable
	case DocumentUnvisitedLink:
		return snapshot.Role == "link" && snapshot.Focusable && !snapshot.Visited
	case DocumentVisitedLink:
		return snapshot.Role == "link" && snapshot.Focusable && snapshot.Visited
	case DocumentClickable:
		return snapshot.SupportsClick && !snapshot.Focusable && !documentClickExcludedRole(snapshot) && !documentHasXMLRole(snapshot, "gridcell")
	case DocumentChunk:
		if documentChunkRole(snapshot) {
			return snapshot.Role == "heading" || snapshot.Role == "list" || snapshot.Role == "table" ||
				(snapshot.CharacterCount > 75 && snapshot.EmbeddedObjectCount*20 < snapshot.CharacterCount)
		}
		return false
	default:
		return false
	}
}

func documentHasXMLRole(snapshot atspi.Snapshot, role string) bool {
	for _, candidate := range strings.Fields(snapshot.XMLRoles) {
		if candidate == role {
			return true
		}
	}
	return false
}

func documentFormFieldRole(snapshot atspi.Snapshot) bool {
	switch snapshot.Role {
	case "button", "push button", "check box", "radio button", "combo box", "list box", "entry", "password text", "spin button", "toggle button":
		return true
	case "document frame", "text":
		if snapshot.Role == "document frame" {
			return snapshot.Editable
		}
		return true
	default:
		return false
	}
}

func documentClickExcludedRole(snapshot atspi.Snapshot) bool {
	switch snapshot.Role {
	case "combo box", "entry", "list box", "menu", "menu item", "check menu item", "radio menu item", "page tab", "page tab list", "password text", "progress bar", "slider", "spin button", "tool bar", "tree item", "tree table", "tree":
		return true
	default:
		return false
	}
}

func documentChunkRole(snapshot atspi.Snapshot) bool {
	switch snapshot.Role {
	case "heading", "list item", "math", "paragraph", "static", "column header", "row header", "table cell", "table row", "text", "section", "article", "description term", "description value", "document email", "document frame", "document presentation", "document spreadsheet", "document text", "document web", "block quote", "description list", "form", "footer", "header", "landmark", "log", "list", "marquee", "panel", "table", "tree", "tree table":
		return true
	default:
		return false
	}
}

func documentObject(doc atspi.DocumentSnapshot, ref atspi.ObjectReference) (atspi.Snapshot, bool) {
	for _, node := range doc.Nodes {
		if node.Reference == ref {
			return node.Snapshot, true
		}
	}
	return atspi.Snapshot{}, false
}

func documentPosition(doc atspi.DocumentSnapshot, place documentPlace) DocumentPosition {
	snapshot, _ := documentObject(doc, place.object)
	position := DocumentPosition{Document: place.document, Object: place.object, Snapshot: snapshot, Origin: place.origin, Offset: place.offset}
	if place.origin == StructuralNavigation && snapshot.Role == "heading" {
		if link, ok, _ := linkedHeadingNode(doc, place.object); ok {
			position.LinkedHeading = &link.Snapshot
		}
	}
	return position
}

// A heading inside a link and a heading containing exactly one link have the
// same activation target. With multiple links, use the link at the first
// readable caret position, matching Python's heading navigation. A heading
// starting with plain text has no unambiguous link target.
func linkedHeadingNode(doc atspi.DocumentSnapshot, heading atspi.ObjectReference) (atspi.DocumentNode, bool, bool) {
	byID := make(map[atspi.ObjectID]atspi.DocumentNode, len(doc.Nodes))
	parents := make(map[atspi.ObjectID]atspi.ObjectID, len(doc.Nodes))
	for _, node := range doc.Nodes {
		byID[node.Reference.ID()] = node
		for _, child := range node.Children {
			parents[child] = node.Reference.ID()
		}
	}
	root, ok := byID[heading.ID()]
	if !ok || root.Snapshot.Role != "heading" {
		return atspi.DocumentNode{}, false, false
	}
	for parent := parents[heading.ID()]; parent.Valid(); parent = parents[parent] {
		node, found := byID[parent]
		if !found || atspi.IsWebDocumentRole(node.Snapshot.Role) {
			break
		}
		if node.Snapshot.Role == "link" {
			return node, true, false
		}
	}
	var match atspi.DocumentNode
	count := 0
	pending := append([]atspi.ObjectID(nil), root.Children...)
	for len(pending) != 0 && count < 2 {
		id := pending[len(pending)-1]
		pending = pending[:len(pending)-1]
		node, found := byID[id]
		if !found || node.Hidden || node.Snapshot.Role == "heading" {
			continue
		}
		if node.Snapshot.Role == "link" {
			match, count = node, count+1
			continue
		}
		pending = append(pending, node.Children...)
	}
	if count > 1 {
		// Semantic captures need not include text offsets (notably Gecko's
		// link leaves). Use readable content and provider child order here.
		pending = append([]atspi.ObjectID(nil), root.Children...)
		for left, right := 0, len(pending)-1; left < right; left, right = left+1, right-1 {
			pending[left], pending[right] = pending[right], pending[left]
		}
		for len(pending) != 0 {
			id := pending[len(pending)-1]
			pending = pending[:len(pending)-1]
			node, found := byID[id]
			if !found || node.Hidden {
				continue
			}
			if node.Snapshot.Role == "heading" || atspi.IsWebDocumentRole(node.Snapshot.Role) {
				break
			}
			readable := strings.TrimSpace(node.Snapshot.Name+node.Snapshot.Text) != "" || node.Snapshot.CharacterCount > 0
			if !wholeCaretNode(node.Snapshot) && !(readable && (len(node.Children) == 0 || node.Snapshot.Role == "link")) {
				for child := len(node.Children) - 1; child >= 0; child-- {
					pending = append(pending, node.Children[child])
				}
				continue
			}
			var firstLink atspi.DocumentNode
			for ; id.Valid(); id = parents[id] {
				if id == heading.ID() {
					if firstLink.Reference.Valid() {
						// Gecko may omit plain text between child accessibles.
						// A named first link must also start the heading label.
						headingName := strings.TrimSpace(root.Snapshot.Name)
						linkName := strings.TrimSpace(firstLink.Snapshot.Name)
						if headingName != "" && linkName != "" && !strings.HasPrefix(headingName, linkName) {
							break
						}
						return firstLink, true, false
					}
					break
				}
				node := byID[id]
				if node.Snapshot.Role == "heading" || atspi.IsWebDocumentRole(node.Snapshot.Role) {
					break
				}
				if node.Snapshot.Role == "link" && !firstLink.Reference.Valid() {
					firstLink = node
				}
			}
			// Only the heading's starting caret position can select a link.
			break
		}
	}
	return match, count == 1, count > 1
}