[Webkit-unassigned] [Bug 103911] New: Web Inspector: more robust treeoutline.findTreeElement

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=103911

           Summary: Web Inspector: more robust treeoutline.findTreeElement
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: All
        OS/Version: All
            Status: UNCONFIRMED
          Severity: Normal
          Priority: P2
         Component: Web Inspector
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: johnjbarton at chromium.org
                CC: timothy at apple.com, rik at webkit.org, keishi at webkit.org,
                    pmuellr at yahoo.com, joepeck at webkit.org,
                    pfeldman at chromium.org, yurys at chromium.org,
                    bweinstein at apple.com, apavlov at chromium.org,
                    loislo at chromium.org, vsevik at chromium.org,
                    web-inspector-bugs at googlegroups.com


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 ;-).

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.