// 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"
	"testing"
)

func testID(path string) ObjectID {
	return ObjectID{BusName: ":1.42", Path: path}
}

func testNode(path, name string, children ...ObjectID) TreeNode {
	snapshot := NewSnapshot(path, name, "push button", "", "")
	snapshot.BusName = ":1.42"
	return TreeNode{Snapshot: snapshot, Children: children}
}

func testTree(t *testing.T) *AccessibleTree {
	t.Helper()
	tree, err := NewAccessibleTree(testID("/root"), []TreeNode{
		testNode("/root", "Window", testID("/first"), testID("/second")),
		testNode("/first", "First"),
		testNode("/second", "Second", testID("/grandchild")),
		testNode("/grandchild", "Grandchild"),
	})
	if err != nil {
		t.Fatal(err)
	}
	return tree
}

func TestAccessibleTreeTraversal(t *testing.T) {
	tree := testTree(t)
	root, err := tree.Root()
	if err != nil {
		t.Fatal(err)
	}
	first, ok, err := tree.FirstChild(root)
	if err != nil || !ok || first.ID() != testID("/first") {
		t.Fatalf("first child = %#v, %v, %v", first, ok, err)
	}
	second, ok, err := tree.NextSibling(first)
	if err != nil || !ok || second.ID() != testID("/second") {
		t.Fatalf("next sibling = %#v, %v, %v", second, ok, err)
	}
	previous, ok, err := tree.PreviousSibling(second)
	if err != nil || !ok || previous.ID() != first.ID() {
		t.Fatalf("previous sibling = %#v, %v, %v", previous, ok, err)
	}
	last, ok, err := tree.LastChild(root)
	if err != nil || !ok || last.ID() != second.ID() {
		t.Fatalf("last child = %#v, %v, %v", last, ok, err)
	}
	parent, ok, err := tree.Parent(second)
	if err != nil || !ok || parent.ID() != root.ID() {
		t.Fatalf("parent = %#v, %v, %v", parent, ok, err)
	}
	grandchild, ok, err := tree.FirstChild(second)
	if err != nil || !ok {
		t.Fatalf("grandchild = %#v, %v, %v", grandchild, ok, err)
	}
	snapshot, err := tree.Resolve(grandchild)
	if err != nil || snapshot.Name != "Grandchild" {
		t.Fatalf("resolved snapshot = %#v, %v", snapshot, err)
	}
}

func TestAccessibleTreeTraversalBoundaries(t *testing.T) {
	tree := testTree(t)
	root, _ := tree.Root()
	first, _, _ := tree.FirstChild(root)
	second, _, _ := tree.LastChild(root)
	grandchild, _, _ := tree.FirstChild(second)

	checks := []struct {
		name string
		call func() (ObjectReference, bool, error)
	}{
		{name: "root parent", call: func() (ObjectReference, bool, error) { return tree.Parent(root) }},
		{name: "root sibling", call: func() (ObjectReference, bool, error) { return tree.NextSibling(root) }},
		{name: "first previous", call: func() (ObjectReference, bool, error) { return tree.PreviousSibling(first) }},
		{name: "last next", call: func() (ObjectReference, bool, error) { return tree.NextSibling(second) }},
		{name: "leaf child", call: func() (ObjectReference, bool, error) { return tree.FirstChild(grandchild) }},
	}
	for _, check := range checks {
		t.Run(check.name, func(t *testing.T) {
			_, ok, err := check.call()
			if err != nil || ok {
				t.Fatalf("ok = %v, error = %v", ok, err)
			}
		})
	}
}

func TestAccessibleTreeInvalidatesSubtreeAndDetachesIt(t *testing.T) {
	tree := testTree(t)
	root, _ := tree.Root()
	second, _, _ := tree.LastChild(root)
	grandchild, _, _ := tree.FirstChild(second)

	if removed := tree.Invalidate(second.ID()); removed != 2 {
		t.Fatalf("removed = %d, want 2", removed)
	}
	if _, err := tree.Resolve(second); !errors.Is(err, ErrStaleObject) {
		t.Fatalf("second error = %v, want stale object", err)
	}
	if _, err := tree.Resolve(grandchild); !errors.Is(err, ErrStaleObject) {
		t.Fatalf("grandchild error = %v, want stale object", err)
	}
	last, ok, err := tree.LastChild(root)
	if err != nil || !ok || last.ID() != testID("/first") {
		t.Fatalf("remaining last child = %#v, %v, %v", last, ok, err)
	}
	if removed := tree.Invalidate(second.ID()); removed != 0 {
		t.Fatalf("second invalidation removed = %d, want 0", removed)
	}
}

func TestAccessibleTreeInvalidatesChildrenAndKeepsParent(t *testing.T) {
	tree := testTree(t)
	root, _ := tree.Root()
	first, _, _ := tree.FirstChild(root)
	second, _, _ := tree.LastChild(root)
	if removed := tree.InvalidateChildren(root.ID()); removed != 3 {
		t.Fatalf("removed = %d, want 3", removed)
	}
	if _, err := tree.Resolve(root); err != nil {
		t.Fatalf("root became stale: %v", err)
	}
	if _, err := tree.Resolve(first); !errors.Is(err, ErrStaleObject) {
		t.Fatalf("first error = %v, want stale object", err)
	}
	if _, err := tree.Resolve(second); !errors.Is(err, ErrStaleObject) {
		t.Fatalf("second error = %v, want stale object", err)
	}
	if _, ok, err := tree.FirstChild(root); !errors.Is(err, ErrIncompleteTree) || ok {
		t.Fatalf("root child after invalidation: ok = %v, error = %v", ok, err)
	}
}

func TestAccessibleTreeCopiesSubtreeIdentities(t *testing.T) {
	tree := testTree(t)
	first, err := tree.Reference(testID("/second"))
	if err != nil {
		t.Fatal(err)
	}
	ids, err := tree.subtreeIDs(first)
	if err != nil {
		t.Fatal(err)
	}
	want := map[ObjectID]bool{testID("/second"): true, testID("/grandchild"): true}
	if len(ids) != len(want) {
		t.Fatalf("subtree identities = %v", ids)
	}
	for _, id := range ids {
		if !want[id] {
			t.Fatalf("unexpected subtree identity %v", id)
		}
	}
}

func TestAccessibleTreeReferenceGeneration(t *testing.T) {
	tree := testTree(t)
	first, err := tree.Reference(testID("/first"))
	if err != nil {
		t.Fatal(err)
	}
	updated := []TreeNode{
		testNode("/root", "Window", testID("/first")),
		testNode("/first", "Updated"),
	}
	if err := tree.Replace(testID("/root"), updated); err != nil {
		t.Fatal(err)
	}
	snapshot, err := tree.Resolve(first)
	if err != nil || snapshot.Name != "Updated" {
		t.Fatalf("stable reference resolved %#v, %v", snapshot, err)
	}

	tree.Invalidate(first.ID())
	if err := tree.Replace(testID("/root"), updated); err != nil {
		t.Fatal(err)
	}
	if _, err := tree.Resolve(first); !errors.Is(err, ErrStaleObject) {
		t.Fatalf("reintroduced object resolved with old reference: %v", err)
	}
	reintroduced, err := tree.Reference(first.ID())
	if err != nil {
		t.Fatal(err)
	}
	if reintroduced == first {
		t.Fatal("reintroduced object reused its invalidated generation")
	}
}

func TestAccessibleTreeReplaceFailureIsAtomicAndChildrenAreOwned(t *testing.T) {
	children := []ObjectID{testID("/child")}
	tree, err := NewAccessibleTree(testID("/root"), []TreeNode{
		testNode("/root", "Root", children...),
		testNode("/child", "Child"),
	})
	if err != nil {
		t.Fatal(err)
	}
	root, _ := tree.Root()
	children[0] = testID("/changed")
	child, ok, err := tree.FirstChild(root)
	if err != nil || !ok || child.ID() != testID("/child") {
		t.Fatalf("owned child = %#v, %v, %v", child, ok, err)
	}

	err = tree.Replace(testID("/root"), []TreeNode{
		testNode("/root", "Broken", testID("/missing")),
	})
	if !errors.Is(err, ErrInvalidTree) {
		t.Fatalf("replace error = %v, want invalid tree", err)
	}
	snapshot, err := tree.Resolve(root)
	if err != nil || snapshot.Name != "Root" {
		t.Fatalf("tree changed after rejected replacement: %#v, %v", snapshot, err)
	}
}

func TestAccessibleTreeSeparatesSamePathOnDifferentBuses(t *testing.T) {
	rootSnapshot := NewSnapshot("/same", "First application", "application", "", "")
	rootSnapshot.BusName = ":1.10"
	childSnapshot := NewSnapshot("/same", "Second application", "application", "", "")
	childSnapshot.BusName = ":1.11"
	childID := childSnapshot.ID()
	tree, err := NewAccessibleTree(rootSnapshot.ID(), []TreeNode{
		{Snapshot: rootSnapshot, Children: []ObjectID{childID}},
		{Snapshot: childSnapshot},
	})
	if err != nil {
		t.Fatal(err)
	}
	child, err := tree.Reference(childID)
	if err != nil {
		t.Fatal(err)
	}
	got, err := tree.Resolve(child)
	if err != nil || got.Name != "Second application" {
		t.Fatalf("snapshot = %#v, error = %v", got, err)
	}
}

func TestAccessibleTreeRejectsMalformedTrees(t *testing.T) {
	root := testID("/root")
	defunct := testNode("/root", "Defunct")
	defunct.Snapshot.Defunct = true
	tests := []struct {
		name  string
		root  ObjectID
		nodes []TreeNode
	}{
		{name: "empty root", nodes: []TreeNode{testNode("/root", "Root")}},
		{name: "empty tree", root: root},
		{name: "missing root", root: root, nodes: []TreeNode{testNode("/other", "Other")}},
		{name: "empty node identity", root: root, nodes: []TreeNode{{Snapshot: Snapshot{}}}},
		{name: "malformed node identity", root: root, nodes: []TreeNode{{Snapshot: Snapshot{BusName: "not unique", Path: "relative"}}}},
		{name: "defunct node", root: root, nodes: []TreeNode{defunct}},
		{name: "duplicate node", root: root, nodes: []TreeNode{testNode("/root", "One"), testNode("/root", "Two")}},
		{name: "missing child", root: root, nodes: []TreeNode{testNode("/root", "Root", testID("/missing"))}},
		{name: "duplicate child", root: root, nodes: []TreeNode{
			testNode("/root", "Root", testID("/child"), testID("/child")), testNode("/child", "Child"),
		}},
		{name: "multiple parents", root: root, nodes: []TreeNode{
			testNode("/root", "Root", testID("/one"), testID("/two")),
			testNode("/one", "One", testID("/child")), testNode("/two", "Two", testID("/child")),
			testNode("/child", "Child"),
		}},
		{name: "cycle", root: root, nodes: []TreeNode{
			testNode("/root", "Root", testID("/child")), testNode("/child", "Child", root),
		}},
		{name: "disconnected", root: root, nodes: []TreeNode{
			testNode("/root", "Root"), testNode("/other", "Other"),
		}},
	}
	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			_, err := NewAccessibleTree(test.root, test.nodes)
			if !errors.Is(err, ErrInvalidTree) {
				t.Fatalf("error = %v, want invalid tree", err)
			}
		})
	}
}

func TestAccessibleTreeRejectsOversizedTree(t *testing.T) {
	nodes := make([]TreeNode, maxTreeNodes+1)
	for index := range nodes {
		nodes[index] = testNode(fmt.Sprintf("/%d", index), "Node")
	}
	_, err := NewAccessibleTree(testID("/0"), nodes)
	if !errors.Is(err, ErrInvalidTree) {
		t.Fatalf("error = %v, want invalid tree", err)
	}
}

func TestAccessibleTreeAcceptsLargeBrowserDocument(t *testing.T) {
	const count = 10001 // The former limit rejected this complete document.
	nodes := make([]TreeNode, count)
	children := make([]ObjectID, 0, count-1)
	for index := 1; index < count; index++ {
		path := fmt.Sprintf("/%d", index)
		children = append(children, testID(path))
		nodes[index] = testNode(path, "Heading")
		nodes[index].Snapshot.Role = "heading"
	}
	nodes[0] = testNode("/0", "Document", children...)
	nodes[0].Snapshot.Role = "document web"
	tree, err := NewAccessibleTree(testID("/0"), nodes)
	if err != nil {
		t.Fatal(err)
	}
	root, err := tree.Root()
	if err != nil {
		t.Fatal(err)
	}
	document, err := tree.Document(t.Context(), root)
	if err != nil || len(document.Nodes) != count {
		t.Fatalf("large document: nodes=%d, err=%v", len(document.Nodes), err)
	}
}

func TestAccessibleTreeConcurrentInvalidation(t *testing.T) {
	tree := testTree(t)
	reference, err := tree.Reference(testID("/grandchild"))
	if err != nil {
		t.Fatal(err)
	}
	start := make(chan struct{})
	done := make(chan struct{})
	var wait sync.WaitGroup
	for range 8 {
		wait.Add(1)
		go func() {
			defer wait.Done()
			<-start
			for {
				select {
				case <-done:
					return
				default:
					_, resolveErr := tree.Resolve(reference)
					if resolveErr != nil && !errors.Is(resolveErr, ErrStaleObject) {
						t.Errorf("resolve error = %v", resolveErr)
						return
					}
				}
			}
		}()
	}
	close(start)
	tree.Invalidate(testID("/second"))
	close(done)
	wait.Wait()
	if _, err := tree.Resolve(reference); !errors.Is(err, ErrStaleObject) {
		t.Fatalf("final resolve error = %v, want stale object", err)
	}
}

func TestAccessibleTreeInvalidatedEmptyChildrenRequireRecapture(t *testing.T) {
	tree := testTree(t)
	leaf, _ := tree.Reference(testID("/first"))
	tree.InvalidateChildren(leaf.ID())
	for _, traverse := range []func(ObjectReference) (ObjectReference, bool, error){tree.FirstChild, tree.LastChild} {
		if _, ok, err := traverse(leaf); ok || !errors.Is(err, ErrIncompleteTree) {
			t.Fatalf("invalidated empty children: ok=%v err=%v", ok, err)
		}
	}
	if _, err := tree.Resolve(leaf); err != nil {
		t.Fatal(err)
	}
	if _, ok, err := tree.Parent(leaf); err != nil || !ok {
		t.Fatalf("parent: %v %v", ok, err)
	}
	if err := tree.Replace(testID("/root"), []TreeNode{
		testNode("/root", "Window", testID("/first")),
		testNode("/first", "First", testID("/added")),
		testNode("/added", "Added"),
	}); err != nil {
		t.Fatal(err)
	}
	child, ok, err := tree.FirstChild(leaf)
	if err != nil || !ok || child.ID() != testID("/added") {
		t.Fatalf("recaptured child: %v %v %v", child, ok, err)
	}
}