Bug 196890 - Web Inspector: Heap: don't use recursion when calculating root paths
Summary: Web Inspector: Heap: don't use recursion when calculating root paths
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Inspector (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Devin Rousso
Keywords: InRadar
Depends on:
Reported: 2019-04-12 18:26 PDT by Devin Rousso
Modified: 2019-04-15 16:49 PDT (History)
5 users (show)

See Also:

Patch (3.77 KB, patch)
2019-04-12 18:30 PDT, Devin Rousso
no flags Details | Formatted Diff | Diff
Patch (4.23 KB, patch)
2019-04-15 14:35 PDT, Devin Rousso
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Devin Rousso 2019-04-12 18:26:42 PDT
If a path is extremely deep, it can cause a stack overflow.
Comment 1 Radar WebKit Bug Importer 2019-04-12 18:28:46 PDT
Comment 2 Devin Rousso 2019-04-12 18:30:30 PDT
Created attachment 367366 [details]
Comment 3 Joseph Pecoraro 2019-04-15 11:18:04 PDT
Comment on attachment 367366 [details]

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


> Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshot.js:756
> +        for (let i = 0; i < stack.length; ++i) {
> +            let {currentPath, nodeOrdinal} = stack[i];

This list is not being treated as a stack. In fact it is always growing because nothing nothing is ever removed.

Normally when we have a stack approach like this we process it to exhaustion like this:

    let stack = [{...entry...}];
    while (stack.length) {
        let entry = stack.pop();
        // Process entry, maybe push new stack entries.

Which I think could be done here as long as you convert these two lines to:

    while (stack.length) {
        let {currentPath, nodeOridinal} = stack.pop();

That said, items are going to be processes on the stack in reverse order... so to get unchanging output you could iterate the edges in forward order such as:

    while (stack.length) {
        let {currentPath, nodeOridinal} = stack.unshift();

That should get you output that is consistent with the current code.
Comment 4 Devin Rousso 2019-04-15 14:35:21 PDT
Created attachment 367460 [details]
Comment 5 WebKit Commit Bot 2019-04-15 16:49:09 PDT
Comment on attachment 367460 [details]

Clearing flags on attachment: 367460

Committed r244308: <https://trac.webkit.org/changeset/244308>
Comment 6 WebKit Commit Bot 2019-04-15 16:49:10 PDT
All reviewed patches have been landed.  Closing bug.