Bug 103911 – Web Inspector: more robust treeoutline.findTreeElement

• Component: Web Inspector (Deprecated)
• Status: RESOLVED FIXED

[johnjbarton]

The current implementation of findTreeElement() calls itself recursively. If the tree data is correct, the algorithm (evidently) terminates. If the tree data is incorrect, the algorithm goes in to a loop.  

I hit this when debugging, the result is 100% CPU and sometimes no slow-script dialog and sometimes memory increases without bound. With the current behavior I am unable to determine what input data is incorrect since I cannot get control or output from the CPU bound process. 

I believe the current algorithm fails when given incorrect data because of the isAncestor search:
    for (var i = 0; i < this.children.length; ++i) {
        item = this.children[i];
        if (item.representedObject === representedObject || isAncestor(item.representedObject, representedObject)) {
            found = true;
            break;
        }
    }
When we call findTreeElement() recursively we are expecting an immediate child -- represented by the first conditional expression -- to match. After all we are walking down the ancestor chain from a known treeElement so one step should not require the isAncestor() path. 

However, if the match we need is not the first child, we check isAncestor() anyway (needlessly in the correct-data case). If we have bad data, then this first child could incorrectly report true for isAncestor(). Then the rest of the code in findTreeElement will cause us to recurse again. This should never happen with correct data. 

Obviously the errant data need not be in the first child, just any child before the true child.

Note that the current code has this comment immediately before the recursive call:
  // FIXME: we could do something faster than findTreeElement since we will know the next
  // ancestor exists in the tree
A more robust implementation would fix this ;-).

[johnjbarton]

Created attachment 177296 [details]
Patch

[Pavel Feldman]

Comment on attachment 177296 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=177296&action=review

> Source/WebCore/inspector/front-end/treeoutline.js:279
> +        function oneLevel() {

{ should go on the next line

I also don't think this is right: imagine you get here due to isAncestor(item.representedObject, representedObject) returning true above. And there are no tree elements created for the path from root to given representedObject yet. You get into recursive findTreeElement for the parent object as the next step, but oneLevel (isAncestor substitude) returns false and you never call onpopulate on the parent.

> Source/WebCore/inspector/front-end/treeoutline.js:282
> +        function noAncestors() {

ditto

[johnjbarton]

(In reply to comment #2)

> I also don't think this is right: imagine you get here due to isAncestor(item.representedObject, representedObject) returning true above. And there are no tree elements created for the path from root to given representedObject yet. You get into recursive findTreeElement for the parent object as the next step, but oneLevel (isAncestor substitude) returns false and you never call onpopulate on the parent.

When we reach the first recursive findTreeElement call:

  childTreeElement = childTreeElement.treeOutline.findTreeElement(ancestors[i], oneLevel, noAncestors);
  
we have i = 0. So the first call to findTreeElement() will use ancestors[0]. This value will be the representedObject for the 'found' childTreeElement, which is one of this.children[]. 

I was assuming that this.children[] are all in the cache, so the findTreeElement() will return the childTreeElement and we will call onpopulate() on it to begin the process of building the children-tree. 

Is this assumption incorrect? (all the tests pass FWIW).

If my assumption is incorrect, then we need to prepend this.representedObject to the ancestors list.

If my assumption is correct, then I will add comments to the code.

[johnjbarton]

Created attachment 177595 [details]
Patch

[Build Bot]

Comment on attachment 177595 [details]
Patch

Attachment 177595 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/15147284

[johnjbarton]

This patch is only JavaScript. As far as I can tell the win EWS never ran tests, it just failed in some way. Any hints?

[WebKit Review Bot]

Comment on attachment 177595 [details]
Patch

Clearing flags on attachment: 177595

Committed r136706: <http://trac.webkit.org/changeset/136706>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[johnjbarton]

In my original report I cited a 100% CPU problem tracked down to the code patched here. I claimed that incorrect remote data could cause the algorithm to recurse. 

With the patched WebInspector I attempted to reproduce the remote data problem. However I think my understanding of the issue was not quite correct.

Here are some outputs from the command line when we are in the patched code just after calling treeElement.onpopulate():

representedObject._nodeName
"BODY"
treeElement.representedObject._nodeName
"HTML"
treeElement.children.map(function(c){return c.representedObject._nodeName;});
["HEAD", "BODY", "HTML"]

So for an HTML tag, the representation has three children: HEAD, BODY, and -- surprise to me -- HTML. Evidently the closing tag is represented as child treeElement:

treeElement.representedObject === treeElement.children[2].representedObject
true

Thus the DOMNode data is a tree, but the treeoutline never is.

Suppose we have 
<html><head><body><div></div></body></html>
and suppose we have the body treeElement built but not the div. In the old algorithm we visit children of HTML, and we should find BODY because isAncestor(BODY, DIV) should be true. But any failure that might cause this test to fail will result in infinite recursion because the last child will always be true, eg isAncestor(HTML, DIV).

This does not explain how the test can fail but it does explain why my testing to verify that the treeoutline is itself a tree fails.