1f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// Copyright 2013 The Chromium Authors. All rights reserved. 2f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// found in the LICENSE file. 4f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 5f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#include "ui/accessibility/ax_tree.h" 6f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 7f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#include <set> 8f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 9a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)#include "base/logging.h" 10a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)#include "base/strings/stringprintf.h" 11f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#include "ui/accessibility/ax_node.h" 12f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 13f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)namespace ui { 14f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace { 165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)std::string TreeToStringHelper(AXNode* node, int indent) { 180529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch std::string result = std::string(2 * indent, ' '); 195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) result += node->data().ToString() + "\n"; 205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < node->child_count(); ++i) 215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) result += TreeToStringHelper(node->ChildAtIndex(i), indent + 1); 225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return result; 235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // anonymous namespace 265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 27a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Intermediate state to keep track of during a tree update. 28a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)struct AXTreeUpdateState { 29a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // During an update, this keeps track of all nodes that have been 30a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // implicitly referenced as part of this update, but haven't been 31a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // updated yet. It's an error if there are any pending nodes at the 32a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // end of Unserialize. 33a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<AXNode*> pending_nodes; 34a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 35a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Keeps track of new nodes created during this update. 36a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<AXNode*> new_nodes; 37a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}; 38a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 39a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)AXTreeDelegate::AXTreeDelegate() { 40a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 41a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 42a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)AXTreeDelegate::~AXTreeDelegate() { 43a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 44a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 45f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)AXTree::AXTree() 46a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) : delegate_(NULL), root_(NULL) { 47f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) AXNodeData root; 480529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch root.id = -1; 49f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) root.role = AX_ROLE_ROOT_WEB_AREA; 50f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 51f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) AXTreeUpdate initial_state; 52f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) initial_state.nodes.push_back(root); 53a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) CHECK(Unserialize(initial_state)) << error(); 54f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 55f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 56f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)AXTree::AXTree(const AXTreeUpdate& initial_state) 57a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) : delegate_(NULL), root_(NULL) { 58a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) CHECK(Unserialize(initial_state)) << error(); 59f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 60f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 61f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)AXTree::~AXTree() { 62f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (root_) 63f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DestroyNodeAndSubtree(root_); 64f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 65f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 66a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void AXTree::SetDelegate(AXTreeDelegate* delegate) { 67a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) delegate_ = delegate; 68a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 69a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 70f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)AXNode* AXTree::GetRoot() const { 71f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return root_; 72f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 73f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 74f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)AXNode* AXTree::GetFromId(int32 id) const { 75f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) base::hash_map<int32, AXNode*>::const_iterator iter = id_map_.find(id); 76f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return iter != id_map_.end() ? (iter->second) : NULL; 77f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 78f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 79f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)bool AXTree::Unserialize(const AXTreeUpdate& update) { 80a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) AXTreeUpdateState update_state; 81a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) int32 old_root_id = root_ ? root_->id() : 0; 82a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 83a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (update.node_id_to_clear != 0) { 84a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) AXNode* node = GetFromId(update.node_id_to_clear); 85a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (!node) { 86a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) error_ = base::StringPrintf("Bad node_id_to_clear: %d", 87a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) update.node_id_to_clear); 88a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return false; 89a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 90a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (node == root_) { 91a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) DestroyNodeAndSubtree(root_); 92a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) root_ = NULL; 93a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } else { 94a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) for (int i = 0; i < node->child_count(); ++i) 95a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) DestroyNodeAndSubtree(node->ChildAtIndex(i)); 96a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) std::vector<AXNode*> children; 97a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) node->SwapChildren(children); 98a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) update_state.pending_nodes.insert(node); 99a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 100a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 101a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 102f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (size_t i = 0; i < update.nodes.size(); ++i) { 103a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (!UpdateNode(update.nodes[i], &update_state)) 104f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 105f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 106f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 107a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (!update_state.pending_nodes.empty()) { 108a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) error_ = "Nodes left pending by the update:"; 109a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (std::set<AXNode*>::iterator iter = update_state.pending_nodes.begin(); 110a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) iter != update_state.pending_nodes.end(); ++iter) { 111a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) error_ += base::StringPrintf(" %d", (*iter)->id()); 112a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 113a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) return false; 114a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 115a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 116a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (delegate_) { 117a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (size_t i = 0; i < update.nodes.size(); ++i) { 118a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) AXNode* node = GetFromId(update.nodes[i].id); 119a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (update_state.new_nodes.find(node) != update_state.new_nodes.end()) { 1200529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch delegate_->OnNodeCreationFinished(node); 121a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) update_state.new_nodes.erase(node); 122a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } else { 1230529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch delegate_->OnNodeChangeFinished(node); 124a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 125a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 126a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (root_->id() != old_root_id) 127a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) delegate_->OnRootChanged(root_); 128a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 129a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 130f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return true; 131f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 132f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 1335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)std::string AXTree::ToString() const { 1345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return TreeToStringHelper(root_, 0); 1355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1370529e5d033099cbfc42635f6f6183833b09dff6eBen MurdochAXNode* AXTree::CreateNode( 1380529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch AXNode* parent, int32 id, int32 index_in_parent) { 1390529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch AXNode* new_node = new AXNode(parent, id, index_in_parent); 1400529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch id_map_[new_node->id()] = new_node; 1410529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (delegate_) 1420529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch delegate_->OnNodeCreated(new_node); 1430529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch return new_node; 144f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 145f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 146a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)bool AXTree::UpdateNode( 147a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const AXNodeData& src, AXTreeUpdateState* update_state) { 148f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // This method updates one node in the tree based on serialized data 149f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // received in an AXTreeUpdate. See AXTreeUpdate for pre and post 150f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // conditions. 151f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 152f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // Look up the node by id. If it's not found, then either the root 153f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // of the tree is being swapped, or we're out of sync with the source 154f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // and this is a serious error. 155a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) AXNode* node = GetFromId(src.id); 156116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch AXNode* new_root = NULL; 157a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (node) { 158a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) update_state->pending_nodes.erase(node); 1590529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch node->SetData(src); 160a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } else { 161a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (src.role != AX_ROLE_ROOT_WEB_AREA) { 162a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) error_ = base::StringPrintf( 163a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) "%d is not in the tree and not the new root", src.id); 164f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 165a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 166116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch new_root = CreateNode(NULL, src.id, 0); 167116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch node = new_root; 168a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) update_state->new_nodes.insert(node); 1690529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch node->SetData(src); 170f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 171f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 172f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (delegate_) 173f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) delegate_->OnNodeChanged(node); 174f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 175f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // First, delete nodes that used to be children of this node but aren't 176f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // anymore. 1770529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (!DeleteOldChildren(node, src.child_ids)) { 178116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (new_root) 179116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch DestroyNodeAndSubtree(new_root); 180f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 1810529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 182f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 183f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // Now build a new children vector, reusing nodes when possible, 184f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // and swap it in. 185f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) std::vector<AXNode*> new_children; 186a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) bool success = CreateNewChildVector( 187a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) node, src.child_ids, &new_children, update_state); 188f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) node->SwapChildren(new_children); 189f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 190f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // Update the root of the tree if needed. 191f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (src.role == AX_ROLE_ROOT_WEB_AREA && 192f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) (!root_ || root_->id() != src.id)) { 193f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (root_) 194f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DestroyNodeAndSubtree(root_); 195f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) root_ = node; 196f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 197f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 198f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return success; 199f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 200f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 201f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)void AXTree::DestroyNodeAndSubtree(AXNode* node) { 202f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) id_map_.erase(node->id()); 203a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) for (int i = 0; i < node->child_count(); ++i) 204a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) DestroyNodeAndSubtree(node->ChildAtIndex(i)); 205a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (delegate_) 206a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) delegate_->OnNodeWillBeDeleted(node); 207f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) node->Destroy(); 208f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 209f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 210f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)bool AXTree::DeleteOldChildren(AXNode* node, 211a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const std::vector<int32> new_child_ids) { 212f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // Create a set of child ids in |src| for fast lookup, and return false 213f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // if a duplicate is found; 214f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) std::set<int32> new_child_id_set; 215f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (size_t i = 0; i < new_child_ids.size(); ++i) { 216a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (new_child_id_set.find(new_child_ids[i]) != new_child_id_set.end()) { 217a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) error_ = base::StringPrintf("Node %d has duplicate child id %d", 218a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) node->id(), new_child_ids[i]); 219f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return false; 220a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 221f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) new_child_id_set.insert(new_child_ids[i]); 222f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 223f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 224f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // Delete the old children. 225f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const std::vector<AXNode*>& old_children = node->children(); 226f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (size_t i = 0; i < old_children.size(); ++i) { 227f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) int old_id = old_children[i]->id(); 228f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (new_child_id_set.find(old_id) == new_child_id_set.end()) 229f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DestroyNodeAndSubtree(old_children[i]); 230f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 231f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 232f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return true; 233f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 234f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 235f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)bool AXTree::CreateNewChildVector(AXNode* node, 236a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) const std::vector<int32> new_child_ids, 237a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) std::vector<AXNode*>* new_children, 238a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) AXTreeUpdateState* update_state) { 239f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) bool success = true; 240f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (size_t i = 0; i < new_child_ids.size(); ++i) { 241f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) int32 child_id = new_child_ids[i]; 242f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) int32 index_in_parent = static_cast<int32>(i); 243a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) AXNode* child = GetFromId(child_id); 244f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (child) { 245f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (child->parent() != node) { 246f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // This is a serious error - nodes should never be reparented. 247f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // If this case occurs, continue so this node isn't left in an 248f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // inconsistent state, but return failure at the end. 249a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) error_ = base::StringPrintf( 250a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) "Node %d reparented from %d to %d", 251a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) child->id(), 252a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) child->parent() ? child->parent()->id() : 0, 253a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) node->id()); 254f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) success = false; 255f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) continue; 256f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 257f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) child->SetIndexInParent(index_in_parent); 258f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } else { 2590529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch child = CreateNode(node, child_id, index_in_parent); 260a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) update_state->pending_nodes.insert(child); 261a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) update_state->new_nodes.insert(child); 262f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 263f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) new_children->push_back(child); 264f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 265f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 266f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return success; 267f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} 268f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 269f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} // namespace ui 270