Make tree serialization more robust and add more unit tests.

Make tree serialization more robust and add more unit tests.

BUG=316726
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=238569

[dmazzoni, 2013-11-27 07:23:08]

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
File ui/accessibility/ax_tree_serializer.h (left):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:183: SerializeChangedNodes(parent,
ids_serialized, out_update);
Note: this line was buggy. Basically, if a node was reparented, we tried to
first serialize its old parent recursively - this fixed some cases but not all
cases.

The new solution is a bit more code, but more foolproof. When we detect a node
is reparented, we find the least common ancestor of the old parent and new
parent and re-serialize the whole subtree rooted at that LCA. That guarantees
there's no messy reparenting.

Reparenting should be rare. The common case in Blink code is when a node is
"ignored" but has children that aren't ignored, and then a change causes it to
no longer be ignored.

[aboxhall, 2013-12-02 17:18:08]

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc
File ui/accessibility/ax_tree.cc (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc#n...
ui/accessibility/ax_tree.cc:23: CHECK(Unserialize(initial_state));
<< error() ? (and below)

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc#n...
ui/accessibility/ax_tree.cc:51: error_ = base::StringPrintf("Bad
node_id_to_clear: %d",
Should this be behind an #ifdef DEBUG ?

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc#n...
ui/accessibility/ax_tree.cc:89: const AXNodeData& src, std::set<AXNode*>*
pending_nodes) {
This is called orphaned_nodes in the header.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.h
File ui/accessibility/ax_tree.h (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.h#ne...
ui/accessibility/ax_tree.h:47: // Subclasses can override this to do additional
processing.
Could you comment what orphaned_nodes is used for?

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.h#ne...
ui/accessibility/ax_tree.h:73: // error. Returns true on success, false on fatal
error.
Could you comment what pending_nodes is used for?

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
File ui/accessibility/ax_tree_serializer.h (left):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:183: SerializeChangedNodes(parent,
ids_serialized, out_update);
On 2013/11/27 07:23:08, Dominic Mazzoni wrote:
> Note: this line was buggy. Basically, if a node was reparented, we tried to
> first serialize its old parent recursively - this fixed some cases but not all
> cases.
> 
> The new solution is a bit more code, but more foolproof. When we detect a node
> is reparented, we find the least common ancestor of the old parent and new
> parent and re-serialize the whole subtree rooted at that LCA. That guarantees
> there's no messy reparenting.
> 
> Reparenting should be rare. The common case in Blink code is when a node is
> "ignored" but has children that aren't ignored, and then a change causes it to
> no longer be ignored.

Thanks for the explanation. The new code is also (to me at least) easier to
understand why it's working.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
File ui/accessibility/ax_tree_serializer.h (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:23: // XTree. An AXTreeSerializer keeps
track of the tree of node ids that its
AXTree (although I do miss XTree Gold)

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:80: // The least common ancestor is the
closest ancestor to |node| (which
This open parenthesis doesn't have a matching close parenthesis. I think it
should go after 'itself' below?

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:206: while (i < std::min(ancestors.size(),
client_ancestors.size())) {
Will this call to min() reliably be pulled out of the loop by the compiler?

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:208:
client_ancestors[client_ancestors.size() - i - 1]->id) {
Why not have two index variables which count down from (ancestors.size() - 1)
and (client_ancestors.size() - 1) respectively? Then you wouldn't need to
calculate min or do this calculation each time - just check both are >=0 in the
while loop.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:232: bool
AXTreeSerializer<AXSourceNode>::CheckForReparenting(
AnyDescendantWasReparented() ?

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:294: need_delete = true;
Trivial suggestion:
need_delete = CheckForReparenting(lca, &lca);

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:376: CHECK(!client_child ||
client_child->parent == client_node);
Maybe comment the purpose of this CHECK.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
File ui/accessibility/ax_tree_serializer_unittest.cc (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer_unittest.cc:15: // The framework for these
tests is that each test sets up |treedata1_|
treedata0_ and treedata1_

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer_unittest.cc:48: // Serialize tree0.
This comment might need a bit more information - is the purpose of serializing
at this point to get the client_tree up to date?

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer_unittest.cc:150: // (1 (2 (3 (4 (5)))))
Perhaps explicitly comment which node has been reparented to where (5 to 4?)

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_unit...
File ui/accessibility/ax_tree_unittest.cc (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_unit...
ui/accessibility/ax_tree_unittest.cc:62: TEST(AXTreeTest, EmptyUpdateFails) {
This test doesn't assert anything?

[dmazzoni, 2013-12-03 08:35:04]

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc
File ui/accessibility/ax_tree.cc (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc#n...
ui/accessibility/ax_tree.cc:23: CHECK(Unserialize(initial_state));
On 2013/12/02 17:18:08, aboxhall wrote:
> << error() ? (and below)

Good catch! I thought of that when I added error() but forgot to add it here.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc#n...
ui/accessibility/ax_tree.cc:51: error_ = base::StringPrintf("Bad
node_id_to_clear: %d",
On 2013/12/02 17:18:08, aboxhall wrote:
> Should this be behind an #ifdef DEBUG ?

I think these are useful for release mode, and it's not that much code. I'm
hoping these logs will be useful if they ever happen "in the wild"

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.cc#n...
ui/accessibility/ax_tree.cc:89: const AXNodeData& src, std::set<AXNode*>*
pending_nodes) {
On 2013/12/02 17:18:08, aboxhall wrote:
> This is called orphaned_nodes in the header.

Done.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.h
File ui/accessibility/ax_tree.h (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.h#ne...
ui/accessibility/ax_tree.h:47: // Subclasses can override this to do additional
processing.
On 2013/12/02 17:18:08, aboxhall wrote:
> Could you comment what orphaned_nodes is used for?

Done. Sorry, I renamed it to pending_nodes in the impl, so that's fixed too.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree.h#ne...
ui/accessibility/ax_tree.h:73: // error. Returns true on success, false on fatal
error.
On 2013/12/02 17:18:08, aboxhall wrote:
> Could you comment what pending_nodes is used for?

Done.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
File ui/accessibility/ax_tree_serializer.h (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:23: // XTree. An AXTreeSerializer keeps
track of the tree of node ids that its
On 2013/12/02 17:18:08, aboxhall wrote:
> AXTree (although I do miss XTree Gold)

Done. (ha ha! I'll bet you don't miss 8.3 filenames, though!)

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:80: // The least common ancestor is the
closest ancestor to |node| (which
On 2013/12/02 17:18:08, aboxhall wrote:
> This open parenthesis doesn't have a matching close parenthesis. I think it
> should go after 'itself' below?

Done.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:206: while (i < std::min(ancestors.size(),
client_ancestors.size())) {
On 2013/12/02 17:18:08, aboxhall wrote:
> Will this call to min() reliably be pulled out of the loop by the compiler?

Moot, I like your idea below.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:208:
client_ancestors[client_ancestors.size() - i - 1]->id) {
On 2013/12/02 17:18:08, aboxhall wrote:
> Why not have two index variables which count down from (ancestors.size() - 1)
> and (client_ancestors.size() - 1) respectively? Then you wouldn't need to
> calculate min or do this calculation each time - just check both are >=0 in
the
> while loop.

Good idea. I have faith that the compiler could have optimized it, but your idea
is more readable.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:232: bool
AXTreeSerializer<AXSourceNode>::CheckForReparenting(
On 2013/12/02 17:18:08, aboxhall wrote:
> AnyDescendantWasReparented() ?

I like that.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:294: need_delete = true;
On 2013/12/02 17:18:08, aboxhall wrote:
> Trivial suggestion:
> need_delete = CheckForReparenting(lca, &lca);

No, because it's possible that need_delete was true before and that would make
it false.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer.h:376: CHECK(!client_child ||
client_child->parent == client_node);
On 2013/12/02 17:18:08, aboxhall wrote:
> Maybe comment the purpose of this CHECK.

Done.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
File ui/accessibility/ax_tree_serializer_unittest.cc (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer_unittest.cc:15: // The framework for these
tests is that each test sets up |treedata1_|
On 2013/12/02 17:18:08, aboxhall wrote:
> treedata0_ and treedata1_

Done.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer_unittest.cc:48: // Serialize tree0.
On 2013/12/02 17:18:08, aboxhall wrote:
> This comment might need a bit more information - is the purpose of serializing
> at this point to get the client_tree up to date?

Yes, I tried to clarify that.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_seri...
ui/accessibility/ax_tree_serializer_unittest.cc:150: // (1 (2 (3 (4 (5)))))
On 2013/12/02 17:18:08, aboxhall wrote:
> Perhaps explicitly comment which node has been reparented to where (5 to 4?)

Done.

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_unit...
File ui/accessibility/ax_tree_unittest.cc (right):

https://codereview.chromium.org/90853002/diff/1/ui/accessibility/ax_tree_unit...
ui/accessibility/ax_tree_unittest.cc:62: TEST(AXTreeTest, EmptyUpdateFails) {
On 2013/12/02 17:18:08, aboxhall wrote:
> This test doesn't assert anything?

Good catch, thanks. I actually changed my mind about this test and forgot. I
don't see any problem with an empty update; the issue I was worried about is
handled by LeaveOrphanedDeletedSubtreeFails.

[aboxhall, 2013-12-03 15:50:14]

lgtm

https://codereview.chromium.org/90853002/diff/20001/ui/accessibility/ax_tree_...
File ui/accessibility/ax_tree_serializer_unittest.cc (right):

https://codereview.chromium.org/90853002/diff/20001/ui/accessibility/ax_tree_...
ui/accessibility/ax_tree_serializer_unittest.cc:52: AXTreeUpdate update0;
Might be nice to make explicit that this is never used (e.g. unused_update or
unused_update0).

[dmazzoni, 2013-12-03 16:46:50]

https://codereview.chromium.org/90853002/diff/20001/ui/accessibility/ax_tree_...
File ui/accessibility/ax_tree_serializer_unittest.cc (right):

https://codereview.chromium.org/90853002/diff/20001/ui/accessibility/ax_tree_...
ui/accessibility/ax_tree_serializer_unittest.cc:52: AXTreeUpdate update0;
On 2013/12/03 15:50:14, aboxhall wrote:
> Might be nice to make explicit that this is never used (e.g. unused_update or
> unused_update0).

Good idea, done.

[aboxhall, 2013-12-03 18:34:18]

lgtm

[commit-bot: I haz the power, 2013-12-03 18:38:16]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/dmazzoni@chromium.org/90853002/40001

[commit-bot: I haz the power, 2013-12-03 19:14:59]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/dmazzoni@chromium.org/90853002/40001

[commit-bot: I haz the power, 2013-12-03 23:44:14]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/dmazzoni@chromium.org/90853002/40001

[commit-bot: I haz the power, 2013-12-04 04:38:05]

Change committed as 238569