409 lines
13 KiB
Go
409 lines
13 KiB
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"
|
|
"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)
|
|
}
|
|
}
|