blob: f11ded45a693984b004182135cd96994c43580a9 [file] [log] [blame]
// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
#define UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
#include <stddef.h>
#include <stdint.h>
#include <vector>
#include "base/containers/hash_tables.h"
#include "base/logging.h"
#include "ui/accessibility/ax_export.h"
#include "ui/accessibility/ax_tree_source.h"
#include "ui/accessibility/ax_tree_update.h"
namespace ui {
struct ClientTreeNode;
// AXTreeSerializer is a helper class that serializes incremental
// updates to an AXTreeSource as a AXTreeUpdate struct.
// These structs can be unserialized by a client object such as an
// AXTree. An AXTreeSerializer keeps track of the tree of node ids that its
// client is aware of so that it will never generate an AXTreeUpdate that
// results in an invalid tree.
//
// Every node in the source tree must have an id that's a unique positive
// integer, the same node must not appear twice.
//
// Usage:
//
// You must call SerializeChanges() every time a node in the tree changes,
// and send the generated AXTreeUpdate to the client. Changes to the
// AXTreeData, if any, are also automatically included in the AXTreeUpdate.
//
// If a node is added, call SerializeChanges on its parent.
// If a node is removed, call SerializeChanges on its parent.
// If a whole new subtree is added, just call SerializeChanges on its root.
// If the root of the tree changes, call SerializeChanges on the new root.
//
// AXTreeSerializer will avoid re-serializing nodes that do not change.
// For example, if node 1 has children 2, 3, 4, 5 and then child 2 is
// removed and a new child 6 is added, the AXTreeSerializer will only
// update nodes 1 and 6 (and any children of node 6 recursively). It will
// assume that nodes 3, 4, and 5 are not modified unless you explicitly
// call SerializeChanges() on them.
//
// As long as the source tree has unique ids for every node and no loops,
// and as long as every update is applied to the client tree, AXTreeSerializer
// will continue to work. If the source tree makes a change but fails to
// call SerializeChanges properly, the trees may get out of sync - but
// because AXTreeSerializer always keeps track of what updates it's sent,
// it will never send an invalid update and the client tree will not break,
// it just may not contain all of the changes.
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
class AXTreeSerializer {
public:
explicit AXTreeSerializer(
AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree);
~AXTreeSerializer();
// Throw out the internal state that keeps track of the nodes the client
// knows about. This has the effect that the next update will send the
// entire tree over because it assumes the client knows nothing.
void Reset();
// Sets the maximum number of nodes that will be serialized, or zero
// for no maximum. This is not a hard maximum - once it hits or
// exceeds this maximum it stops walking the children of nodes, but
// it may exceed this value a bit in order to create a consistent
// tree.
void set_max_node_count(size_t max_node_count) {
max_node_count_ = max_node_count;
}
// Serialize all changes to |node| and append them to |out_update|.
// Returns true on success. On failure, returns false and calls Reset();
// this only happens when the source tree has a problem like duplicate
// ids or changing during serialization.
bool SerializeChanges(AXSourceNode node,
AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update);
// Invalidate the subtree rooted at this node, ensuring that the whole
// subtree is re-serialized the next time any of those nodes end up
// being serialized.
void InvalidateSubtree(AXSourceNode node);
// Return whether or not this node is in the client tree. If you call
// this immediately after serializing, this indicates whether a given
// node is in the set of nodes that the client (the recipient of
// the AXTreeUpdates) is aware of.
//
// For example, you could use this to determine if a given node is
// reachable. If one of its ancestors is hidden and it was pruned
// from the accessibility tree, this would return false.
bool IsInClientTree(AXSourceNode node);
// Only for unit testing. Normally this class relies on getting a call
// to SerializeChanges() every time the source tree changes. For unit
// testing, it's convenient to create a static AXTree for the initial
// state and then call ChangeTreeSourceForTesting and then SerializeChanges
// to simulate the changes you'd get if a tree changed from the initial
// state to the second tree's state.
void ChangeTreeSourceForTesting(
AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* new_tree);
private:
// Return the least common ancestor of a node in the source tree
// and a node in the client tree, or nullptr if there is no such node.
// The least common ancestor is the closest ancestor to |node| (which
// may be |node| itself) that's in both the source tree and client tree,
// and for which both the source and client tree agree on their ancestor
// chain up to the root.
//
// Example 1:
//
// Client Tree Source tree |
// 1 1 |
// / \ / \ |
// 2 3 2 4 |
//
// LCA(source node 2, client node 2) is node 2.
// LCA(source node 3, client node 4) is node 1.
//
// Example 2:
//
// Client Tree Source tree |
// 1 1 |
// / \ / \ |
// 2 3 2 3 |
// / \ / / |
// 4 7 8 4 |
// / \ / \ |
// 5 6 5 6 |
//
// LCA(source node 8, client node 7) is node 2.
// LCA(source node 5, client node 5) is node 1.
// It's not node 5, because the two trees disagree on the parent of
// node 4, so the LCA is the first ancestor both trees agree on.
AXSourceNode LeastCommonAncestor(AXSourceNode node,
ClientTreeNode* client_node);
// Return the least common ancestor of |node| that's in the client tree.
// This just walks up the ancestors of |node| until it finds a node that's
// also in the client tree and not inside an invalid subtree, and then calls
// LeastCommonAncestor on the source node and client node.
AXSourceNode LeastCommonAncestor(AXSourceNode node);
// Walk the subtree rooted at |node| and return true if any nodes that
// would be updated are being reparented. If so, update |out_lca| to point
// to the least common ancestor of the previous LCA and the previous
// parent of the node being reparented.
bool AnyDescendantWasReparented(AXSourceNode node,
AXSourceNode* out_lca);
ClientTreeNode* ClientTreeNodeById(int32_t id);
// Invalidate the subtree rooted at this node.
void InvalidateClientSubtree(ClientTreeNode* client_node);
// Delete the client subtree rooted at this node.
void DeleteClientSubtree(ClientTreeNode* client_node);
// Helper function, called recursively with each new node to serialize.
bool SerializeChangedNodes(
AXSourceNode node,
AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update);
// Visit all of the descendants of |node| once.
void WalkAllDescendants(AXSourceNode node);
// Delete the entire client subtree but don't set the did_reset_ flag
// like when Reset() is called.
void InternalReset();
// The tree source.
AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree_;
// The tree data most recently sent to the client.
AXTreeData client_tree_data_;
// Our representation of the client tree.
ClientTreeNode* client_root_ = nullptr;
// A map from IDs to nodes in the client tree.
base::hash_map<int32_t, ClientTreeNode*> client_id_map_;
// The maximum number of nodes to serialize in a given call to
// SerializeChanges, or 0 if there's no maximum.
size_t max_node_count_ = 0;
// Keeps track of if Reset() was called. If so, we need to always
// explicitly set node_id_to_clear to ensure that the next serialized
// tree is treated as a completely new tree and not a partial update.
bool did_reset_ = false;
};
// In order to keep track of what nodes the client knows about, we keep a
// representation of the client tree - just IDs and parent/child
// relationships, and a marker indicating whether it's been invalidated.
struct AX_EXPORT ClientTreeNode {
ClientTreeNode();
virtual ~ClientTreeNode();
int32_t id;
ClientTreeNode* parent;
std::vector<ClientTreeNode*> children;
bool invalid;
};
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::AXTreeSerializer(
AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* tree)
: tree_(tree) {}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::~AXTreeSerializer() {
Reset();
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::Reset() {
InternalReset();
did_reset_ = true;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::InternalReset() {
client_tree_data_ = AXTreeData();
// Normally we use DeleteClientSubtree to remove nodes from the tree,
// but Reset() needs to work even if the tree is in a broken state.
// Instead, iterate over |client_id_map_| to ensure we clear all nodes and
// start from scratch.
for (auto&& item : client_id_map_)
delete item.second;
client_id_map_.clear();
client_root_ = nullptr;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
ChangeTreeSourceForTesting(
AXTreeSource<AXSourceNode, AXNodeData, AXTreeData>* new_tree) {
tree_ = new_tree;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
AXSourceNode
AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::LeastCommonAncestor(
AXSourceNode node,
ClientTreeNode* client_node) {
if (!tree_->IsValid(node) || client_node == nullptr)
return tree_->GetNull();
std::vector<AXSourceNode> ancestors;
while (tree_->IsValid(node)) {
ancestors.push_back(node);
node = tree_->GetParent(node);
}
std::vector<ClientTreeNode*> client_ancestors;
while (client_node) {
client_ancestors.push_back(client_node);
client_node = client_node->parent;
}
// Start at the root. Keep going until the source ancestor chain and
// client ancestor chain disagree. The last node before they disagree
// is the LCA.
AXSourceNode lca = tree_->GetNull();
int source_index = static_cast<int>(ancestors.size() - 1);
int client_index = static_cast<int>(client_ancestors.size() - 1);
while (source_index >= 0 && client_index >= 0) {
if (tree_->GetId(ancestors[source_index]) !=
client_ancestors[client_index]->id) {
return lca;
}
lca = ancestors[source_index];
source_index--;
client_index--;
}
return lca;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
AXSourceNode
AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::LeastCommonAncestor(
AXSourceNode node) {
// Walk up the tree until the source node's id also exists in the
// client tree, whose parent is not invalid, then call LeastCommonAncestor
// on those two nodes.
//
// Note that it's okay if |client_node| is invalid - the LCA can be the
// root of an invalid subtree, since we're going to serialize the
// LCA. But it's not okay if |client_node->parent| is invalid - that means
// that we're inside of an invalid subtree that all needs to be
// re-serialized, so the LCA should be higher.
ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
while (
tree_->IsValid(node) &&
(!client_node || (client_node->parent && client_node->parent->invalid))) {
node = tree_->GetParent(node);
if (tree_->IsValid(node))
client_node = ClientTreeNodeById(tree_->GetId(node));
}
return LeastCommonAncestor(node, client_node);
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
AnyDescendantWasReparented(AXSourceNode node, AXSourceNode* out_lca) {
bool result = false;
int id = tree_->GetId(node);
std::vector<AXSourceNode> children;
tree_->GetChildren(node, &children);
for (size_t i = 0; i < children.size(); ++i) {
AXSourceNode& child = children[i];
int child_id = tree_->GetId(child);
ClientTreeNode* client_child = ClientTreeNodeById(child_id);
if (client_child) {
if (!client_child->parent) {
// If the client child has no parent, it must have been the
// previous root node, so there is no LCA and we can exit early.
*out_lca = tree_->GetNull();
return true;
} else if (client_child->parent->id != id) {
// If the client child's parent is not this node, update the LCA
// and return true (reparenting was found).
*out_lca = LeastCommonAncestor(*out_lca, client_child);
result = true;
} else if (!client_child->invalid) {
// This child is already in the client tree and valid, we won't
// recursively serialize it so we don't need to check this
// subtree recursively for reparenting.
continue;
}
}
// This is a new child or reparented child, check it recursively.
if (AnyDescendantWasReparented(child, out_lca))
result = true;
}
return result;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
ClientTreeNode*
AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::ClientTreeNodeById(
int32_t id) {
base::hash_map<int32_t, ClientTreeNode*>::iterator iter =
client_id_map_.find(id);
if (iter != client_id_map_.end())
return iter->second;
return nullptr;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::SerializeChanges(
AXSourceNode node,
AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update) {
// Send the tree data if it's changed since the last update, or if
// out_update->has_tree_data is already set to true.
AXTreeData new_tree_data;
if (tree_->GetTreeData(&new_tree_data) &&
(out_update->has_tree_data || new_tree_data != client_tree_data_)) {
out_update->has_tree_data = true;
out_update->tree_data = new_tree_data;
client_tree_data_ = new_tree_data;
}
// If the node isn't in the client tree, we need to serialize starting
// with the LCA.
AXSourceNode lca = LeastCommonAncestor(node);
// This loop computes the least common ancestor that includes the old
// and new parents of any nodes that have been reparented, and clears the
// whole client subtree of that LCA if necessary. If we do end up clearing
// any client nodes, keep looping because we have to search for more
// nodes that may have been reparented from this new LCA.
bool need_delete;
do {
need_delete = false;
if (client_root_) {
if (tree_->IsValid(lca)) {
// Check for any reparenting within this subtree - if there is
// any, we need to delete and reserialize the whole subtree
// that contains the old and new parents of the reparented node.
if (AnyDescendantWasReparented(lca, &lca))
need_delete = true;
}
if (!tree_->IsValid(lca)) {
// If there's no LCA, just tell the client to destroy the whole
// tree and then we'll serialize everything from the new root.
out_update->node_id_to_clear = client_root_->id;
InternalReset();
} else if (need_delete) {
// Otherwise, if we need to reserialize a subtree, first we need
// to delete those nodes in our client tree so that
// SerializeChangedNodes() will be sure to send them again.
out_update->node_id_to_clear = tree_->GetId(lca);
ClientTreeNode* client_lca = ClientTreeNodeById(tree_->GetId(lca));
CHECK(client_lca);
DeleteClientSubtree(client_lca);
}
}
} while (need_delete);
// Serialize from the LCA, or from the root if there isn't one.
if (!tree_->IsValid(lca))
lca = tree_->GetRoot();
// Work around flaky source trees where nodes don't figure out their
// correct parent/child relationships until you walk the whole tree once.
// Covered by this test in the content_browsertests suite:
// DumpAccessibilityTreeTest.AccessibilityAriaOwns.
WalkAllDescendants(lca);
if (!SerializeChangedNodes(lca, out_update))
return false;
// If we had a reset, ensure that the old tree is cleared before the client
// unserializes this update. If we didn't do this, there's a chance that
// treating this update as an incremental update could result in some
// reparenting.
if (did_reset_) {
out_update->node_id_to_clear = tree_->GetId(lca);
did_reset_ = false;
}
return true;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::InvalidateSubtree(
AXSourceNode node) {
ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
if (client_node)
InvalidateClientSubtree(client_node);
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::IsInClientTree(
AXSourceNode node) {
return !!ClientTreeNodeById(tree_->GetId(node));
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
InvalidateClientSubtree(ClientTreeNode* client_node) {
client_node->invalid = true;
for (size_t i = 0; i < client_node->children.size(); ++i)
InvalidateClientSubtree(client_node->children[i]);
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
DeleteClientSubtree(ClientTreeNode* client_node) {
for (size_t i = 0; i < client_node->children.size(); ++i) {
client_id_map_.erase(client_node->children[i]->id);
DeleteClientSubtree(client_node->children[i]);
delete client_node->children[i];
}
client_node->children.clear();
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
bool AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::
SerializeChangedNodes(
AXSourceNode node,
AXTreeUpdateBase<AXNodeData, AXTreeData>* out_update) {
// This method has three responsibilities:
// 1. Serialize |node| into an AXNodeData, and append it to
// the AXTreeUpdate to be sent to the client.
// 2. Determine if |node| has any new children that the client doesn't
// know about yet, and call SerializeChangedNodes recursively on those.
// 3. Update our internal data structure that keeps track of what nodes
// the client knows about.
// First, find the ClientTreeNode for this id in our data structure where
// we keep track of what accessibility objects the client already knows
// about. If we don't find it, then this must be the new root of the
// accessibility tree.
int id = tree_->GetId(node);
ClientTreeNode* client_node = ClientTreeNodeById(id);
if (!client_node) {
if (client_root_)
Reset();
client_root_ = new ClientTreeNode();
client_node = client_root_;
client_node->id = id;
client_node->parent = nullptr;
client_id_map_[client_node->id] = client_node;
}
// We're about to serialize it, so mark it as valid.
client_node->invalid = false;
// Iterate over the ids of the children of |node|.
// Create a set of the child ids so we can quickly look
// up which children are new and which ones were there before.
// If we've hit the maximum number of serialized nodes, pretend
// this node has no children but keep going so that we get
// consistent results.
base::hash_set<int32_t> new_child_ids;
std::vector<AXSourceNode> children;
if (max_node_count_ == 0 || out_update->nodes.size() < max_node_count_) {
tree_->GetChildren(node, &children);
} else if (max_node_count_ > 0) {
static bool logged_once = false;
if (!logged_once) {
LOG(WARNING) << "Warning: not serializing AX nodes after a max of "
<< max_node_count_;
logged_once = true;
}
}
for (size_t i = 0; i < children.size(); ++i) {
AXSourceNode& child = children[i];
int new_child_id = tree_->GetId(child);
new_child_ids.insert(new_child_id);
// There shouldn't be any reparenting because we've already handled it
// above. If this happens, reset and return an error.
ClientTreeNode* client_child = client_id_map_[new_child_id];
if (client_child && client_child->parent != client_node) {
Reset();
return false;
}
}
// Go through the old children and delete subtrees for child
// ids that are no longer present, and create a map from
// id to ClientTreeNode for the rest. It's important to delete
// first in a separate pass so that nodes that are reparented
// don't end up children of two different parents in the middle
// of an update, which can lead to a double-free.
base::hash_map<int32_t, ClientTreeNode*> client_child_id_map;
std::vector<ClientTreeNode*> old_children;
old_children.swap(client_node->children);
for (size_t i = 0; i < old_children.size(); ++i) {
ClientTreeNode* old_child = old_children[i];
int old_child_id = old_child->id;
if (new_child_ids.find(old_child_id) == new_child_ids.end()) {
client_id_map_.erase(old_child_id);
DeleteClientSubtree(old_child);
delete old_child;
} else {
client_child_id_map[old_child_id] = old_child;
}
}
// Serialize this node. This fills in all of the fields in
// AXNodeData except child_ids, which we handle below.
size_t serialized_node_index = out_update->nodes.size();
out_update->nodes.push_back(AXNodeData());
{
// Take the address of an element in a vector only within a limited
// scope because otherwise the pointer can become invalid if the
// vector is resized.
AXNodeData* serialized_node = &out_update->nodes[serialized_node_index];
tree_->SerializeNode(node, serialized_node);
if (serialized_node->id == client_root_->id)
out_update->root_id = serialized_node->id;
}
// Iterate over the children, serialize them, and update the ClientTreeNode
// data structure to reflect the new tree.
std::vector<int32_t> actual_serialized_node_child_ids;
client_node->children.reserve(children.size());
for (size_t i = 0; i < children.size(); ++i) {
AXSourceNode& child = children[i];
int child_id = tree_->GetId(child);
// Skip if the child isn't valid.
if (!tree_->IsValid(child))
continue;
// Skip if the same child is included more than once.
if (new_child_ids.find(child_id) == new_child_ids.end())
continue;
new_child_ids.erase(child_id);
actual_serialized_node_child_ids.push_back(child_id);
if (client_child_id_map.find(child_id) != client_child_id_map.end()) {
ClientTreeNode* reused_child = client_child_id_map[child_id];
client_node->children.push_back(reused_child);
// Re-serialize it if the child is marked as invalid, otherwise
// we don't have to because the client already has it.
if (reused_child->invalid) {
if (!SerializeChangedNodes(child, out_update))
return false;
}
} else {
ClientTreeNode* new_child = new ClientTreeNode();
new_child->id = child_id;
new_child->parent = client_node;
new_child->invalid = false;
client_node->children.push_back(new_child);
client_id_map_[child_id] = new_child;
if (!SerializeChangedNodes(child, out_update))
return false;
}
}
// Finally, update the child ids of this node to reflect the actual child
// ids that were valid during serialization.
out_update->nodes[serialized_node_index].child_ids.swap(
actual_serialized_node_child_ids);
return true;
}
template <typename AXSourceNode, typename AXNodeData, typename AXTreeData>
void AXTreeSerializer<AXSourceNode, AXNodeData, AXTreeData>::WalkAllDescendants(
AXSourceNode node) {
std::vector<AXSourceNode> children;
tree_->GetChildren(node, &children);
for (size_t i = 0; i < children.size(); ++i)
WalkAllDescendants(children[i]);
}
} // namespace ui
#endif // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_