ax_tree.cc | Explore in Territory

// Copyright 2013 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "ui/accessibility/ax_tree.h"

#include <stddef.h>

#include <numeric>
#include <utility>

#include "base/auto_reset.h"
#include "base/check_op.h"
#include "base/command_line.h"
#include "base/containers/adapters.h"
#include "base/containers/contains.h"
#include "base/memory/ptr_util.h"
#include "base/memory/raw_ptr.h"
#include "base/memory/raw_ref.h"
#include "base/metrics/histogram_macros.h"
#include "base/no_destructor.h"
#include "base/not_fatal_until.h"
#include "base/notreached.h"
#include "base/observer_list.h"
#include "base/strings/stringprintf.h"
#include "base/timer/elapsed_timer.h"
#include "components/crash/core/common/crash_key.h"
#include "third_party/abseil-cpp/absl/cleanup/cleanup.h"
#include "ui/accessibility/ax_enums.mojom.h"
#include "ui/accessibility/ax_event.h"
#include "ui/accessibility/ax_language_detection.h"
#include "ui/accessibility/ax_node.h"
#include "ui/accessibility/ax_node_position.h"
#include "ui/accessibility/ax_role_properties.h"
#include "ui/accessibility/ax_selection.h"
#include "ui/accessibility/ax_table_info.h"
#include "ui/accessibility/ax_tree_observer.h"
#include "ui/gfx/geometry/transform.h"

namespace ui {

namespace {

// This is the list of reverse relations that are computed.
// This purposely does not include relations such as kRadioGroupIds where
// the reverse relation is not interesting to consumers.
constexpr ax::mojom::IntListAttribute kReverseRelationIntListAttributes[] = …;
constexpr ax::mojom::IntAttribute kReverseRelationIntAttributes[] = …;

std::string TreeToStringHelper(const AXNode* node, int indent, bool verbose) { … }

template <typename K, typename V>
bool KeyValuePairsKeysMatch(std::vector<std::pair<K, V>> pairs1,
                            std::vector<std::pair<K, V>> pairs2) { … }

template <typename K, typename V>
std::map<K, V> MapFromKeyValuePairs(std::vector<std::pair<K, V>> pairs) { … }

// Given two vectors of <K, V> key, value pairs representing an "old" vs "new"
// state, or "before" vs "after", calls a callback function for each key that
// changed value. Note that if an attribute is removed, that will result in
// a call to the callback with the value changing from the previous value to
// |empty_value|, and similarly when an attribute is added.
template <typename K, typename V, typename F>
void CallIfAttributeValuesChanged(const std::vector<std::pair<K, V>>& old_pairs,
                                  const std::vector<std::pair<K, V>>& new_pairs,
                                  const V& empty_value,
                                  F callback) { … }

bool IsCollapsed(const AXNode* node) { … }

}  // namespace

// static
bool AXTree::is_focused_node_always_unignored_ = …;

// This object is used to track structure changes that will occur for a specific
// AXID. This includes how many times we expect that a node with a specific AXID
// will be created and/or destroyed, and how many times a subtree rooted at AXID
// expects to be destroyed during an AXTreeUpdate.
//
// An AXTreeUpdate is a serialized representation of an atomic change to an
// AXTree. See also |AXTreeUpdate| which documents the nature and invariants
// required to atomically update the AXTree.
//
// The reason that we must track these counts, and the reason these are counts
// rather than a bool/flag is because an AXTreeUpdate may contain multiple
// AXNodeData updates for a given AXID. A common way that this occurs is when
// multiple AXTreeUpdates are merged together, combining their AXNodeData list.
// Additionally AXIDs may be reused after being removed from the tree,
// most notably when "reparenting" a node. A "reparent" occurs when an AXID is
// first destroyed from the tree then created again in the same AXTreeUpdate,
// which may also occur multiple times with merged updates.
//
// We need to accumulate these counts for 3 reasons :
//   1. To determine what structure changes *will* occur before applying
//      updates to the tree so that we can notify observers of structure changes
//      when the tree is still in a stable and unchanged state.
//   2. Capture any errors *before* applying updates to the tree structure
//      due to the order of (or lack of) AXNodeData entries in the update
//      so we can abort a bad update instead of applying it partway.
//   3. To validate that the expectations we accumulate actually match
//      updates that are applied to the tree.
//
// To reiterate the invariants that this structure is taking a dependency on
// from |AXTreeUpdate|, suppose that the next AXNodeData to be applied is
// |node|. The following invariants must hold:
// 1. Either
//   a) |node.id| is already in the tree, or
//   b) the tree is empty, and
//      |node| is the new root of the tree, and
//      |node.role| == kRootWebArea.
// 2. Every child id in |node.child_ids| must either be already a child
//        of this node, or a new id not previously in the tree. It is not
//        allowed to "reparent" a child to this node without first removing
//        that child from its previous parent.
// 3. When a new id appears in |node.child_ids|, the tree should create a
//        new uninitialized placeholder node for it immediately. That
//        placeholder must be updated within the same AXTreeUpdate, otherwise
//        it's a fatal error. This guarantees the tree is always complete
//        before or after an AXTreeUpdate.
struct PendingStructureChanges { … };

// Represents the different states when computing PendingStructureChanges
// required for tree Unserialize.
enum class AXTreePendingStructureStatus { … };

// Intermediate state to keep track of during a tree update.
struct AXTreeUpdateState { … };

AXTree::NodeSetSizePosInSetInfo::NodeSetSizePosInSetInfo() = default;
AXTree::NodeSetSizePosInSetInfo::~NodeSetSizePosInSetInfo() = default;

struct AXTree::OrderedSetContent { … };

struct AXTree::OrderedSetItemsMap { … };

// static
void AXTree::SetFocusedNodeShouldNeverBeIgnored() { … }

// static
bool AXTree::ComputeNodeIsIgnored(const AXTreeData* optional_tree_data,
                                  const AXNodeData& node_data) { … }

// static
bool AXTree::ComputeNodeIsIgnoredChanged(
    const AXTreeData* optional_old_tree_data,
    const AXNodeData& old_node_data,
    const AXTreeData* optional_new_tree_data,
    const AXNodeData& new_node_data) { … }

AXTree::AXTree() { … }

AXTree::AXTree(const AXTreeUpdate& initial_state) { … }

AXTree::~AXTree() { … }

void AXTree::AddObserver(AXTreeObserver* observer) { … }

bool AXTree::HasObserver(AXTreeObserver* observer) { … }

void AXTree::RemoveObserver(AXTreeObserver* observer) { … }

const AXTreeID& AXTree::GetAXTreeID() const { … }

const AXTreeData& AXTree::data() const { … }

AXNode* AXTree::GetFromId(AXNodeID id) const { … }

void AXTree::Destroy() { … }

void AXTree::UpdateDataForTesting(const AXTreeData& new_data) { … }

gfx::RectF AXTree::RelativeToTreeBoundsInternal(const AXNode* node,
                                                gfx::RectF bounds,
                                                bool* offscreen,
                                                bool clip_bounds,
                                                bool skip_container_offset,
                                                bool allow_recursion) const { … }

gfx::RectF AXTree::RelativeToTreeBounds(const AXNode* node,
                                        gfx::RectF bounds,
                                        bool* offscreen,
                                        bool clip_bounds,
                                        bool skip_container_offset) const { … }

gfx::RectF AXTree::GetTreeBounds(const AXNode* node,
                                 bool* offscreen,
                                 bool clip_bounds) const { … }

std::set<AXNodeID> AXTree::GetReverseRelations(ax::mojom::IntAttribute attr,
                                               AXNodeID dst_id) const { … }

std::set<AXNodeID> AXTree::GetReverseRelations(ax::mojom::IntListAttribute attr,
                                               AXNodeID dst_id) const { … }

std::set<AXNodeID> AXTree::GetNodeIdsForChildTreeId(
    AXTreeID child_tree_id) const { … }

const std::set<AXTreeID> AXTree::GetAllChildTreeIds() const { … }

bool AXTree::Unserialize(const AXTreeUpdate& update) { … }

#if DCHECK_IS_ON()
void AXTree::CheckTreeConsistency(const AXTreeUpdate& update) { … }
#endif

AXTableInfo* AXTree::GetTableInfo(const AXNode* const_table_node) const { … }

std::string AXTree::ToString(bool verbose) const { … }

AXNode* AXTree::CreateNode(AXNode* parent,
                           AXNodeID id,
                           size_t index_in_parent,
                           AXTreeUpdateState* update_state) { … }

bool AXTree::ComputePendingChanges(const AXTreeUpdate& update,
                                   AXTreeUpdateState* update_state) { … }

bool AXTree::ComputePendingChangesToNode(const AXNodeData& new_data,
                                         bool is_new_root,
                                         AXTreeUpdateState* update_state) { … }

bool AXTree::UpdateNode(const AXNodeData& src,
                        bool is_new_root,
                        AXTreeUpdateState* update_state) { … }

void AXTree::NotifySubtreeWillBeReparentedOrDeleted(
    AXNode* node,
    const AXTreeUpdateState* update_state) { … }

void AXTree::NotifyNodeWillBeReparentedOrDeleted(
    AXNode* node,
    const AXTreeUpdateState* update_state) { … }

void AXTree::RecursivelyNotifyNodeDeletedForTreeTeardown(AXNode* node) { … }

void AXTree::NotifyNodeHasBeenDeleted(AXNodeID node_id) { … }

void AXTree::NotifyNodeHasBeenReparentedOrCreated(
    AXNode* node,
    const AXTreeUpdateState* update_state) { … }

void AXTree::NotifyChildTreeConnectionChanged(AXNode* node,
                                              AXTree* child_tree) { … }

void AXTree::NotifyNodeAttributesWillChange(
    AXNode* node,
    AXTreeUpdateState& update_state,
    const AXTreeData* optional_old_tree_data,
    const AXNodeData& old_data,
    const AXTreeData* optional_new_tree_data,
    const AXNodeData& new_data) { … }

void AXTree::NotifyNodeAttributesHaveBeenChanged(
    AXNode* node,
    AXTreeUpdateState& update_state,
    const AXTreeData* optional_old_tree_data,
    const AXNodeData& old_data,
    const AXTreeData* optional_new_tree_data,
    const AXNodeData& new_data) { … }

void AXTree::UpdateReverseRelations(AXNode* node,
                                    const AXNodeData& new_data,
                                    bool is_new_node) { … }

bool AXTree::ValidatePendingChangesComplete(
    const AXTreeUpdateState& update_state) { … }

void AXTree::MarkSubtreeForDestruction(AXNodeID node_id,
                                       AXTreeUpdateState* update_state) { … }

void AXTree::MarkNodesForDestructionRecursive(AXNodeID node_id,
                                              AXTreeUpdateState* update_state) { … }

void AXTree::DestroySubtree(AXNode* node,
                            AXTreeUpdateState* update_state) { … }

void AXTree::DestroyNodeAndSubtree(AXNode* node,
                                   AXTreeUpdateState* update_state) { … }

void AXTree::DeleteOldChildren(AXNode* node,
                               const std::vector<AXNodeID>& new_child_ids,
                               AXTreeUpdateState* update_state) { … }

bool AXTree::CreateNewChildVector(
    AXNode* node,
    const std::vector<AXNodeID>& new_child_ids,
    std::vector<raw_ptr<AXNode, VectorExperimental>>* new_children,
    AXTreeUpdateState* update_state) { … }

AXNode* AXTree::GetUnignoredAncestorFromId(AXNodeID node_id) const { … }

AXNodeID AXTree::GetNextNegativeInternalNodeId() { … }

void AXTree::PopulateOrderedSetItemsMap(
    const AXNode& original_node,
    const AXNode* ordered_set,
    OrderedSetItemsMap* items_map_to_be_populated) const { … }

void AXTree::RecursivelyPopulateOrderedSetItemsMap(
    const AXNode& original_node,
    const AXNode* ordered_set,
    const AXNode* local_parent,
    std::optional<int> ordered_set_min_level,
    std::optional<int> prev_level,
    OrderedSetItemsMap* items_map_to_be_populated) const { … }

// Given an ordered_set, compute pos_in_set and set_size for all of its items
// and store values in cache.
// Ordered_set should never be nullptr.
void AXTree::ComputeSetSizePosInSetAndCache(const AXNode& node,
                                            const AXNode* ordered_set) { … }

void AXTree::ComputeSetSizePosInSetAndCacheHelper(
    const OrderedSetContent& ordered_set_content) { … }

std::optional<int> AXTree::GetPosInSet(const AXNode& node) { … }

std::optional<int> AXTree::GetSetSize(const AXNode& node) { … }

AXSelection AXTree::GetSelection() const { … }

AXSelection AXTree::GetUnignoredSelection() const { … }

bool AXTree::GetTreeUpdateInProgressState() const { … }

void AXTree::SetTreeUpdateInProgressState(bool set_tree_update_value) { … }

bool AXTree::HasPaginationSupport() const { … }

void AXTree::NotifyTreeManagerWillBeRemoved(AXTreeID previous_tree_id) { … }

void AXTree::RecordError(const AXTreeUpdateState& update_state,
                         std::string new_error,
                         bool is_fatal) { … }

}  // namespace ui
chromium/ui/accessibility/ax_tree.cc
