Bug 193605 - Web Inspector: Frontend performance is very slow reloading theverge.com - 50% of time in TreeOutline _indexOfTreeElement
Summary: Web Inspector: Frontend performance is very slow reloading theverge.com - 50%...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Inspector (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P1 Normal
Assignee: Matt Baker
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2019-01-18 19:08 PST by Joseph Pecoraro
Modified: 2019-02-17 12:49 PST (History)
8 users (show)

See Also:


Attachments
[IMAGE] JavaScript Profile (1.28 MB, image/png)
2019-01-18 19:08 PST, Joseph Pecoraro
no flags Details
Patch (87.46 KB, patch)
2019-02-11 15:35 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Patch (87.58 KB, patch)
2019-02-11 15:43 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ews100 for mac-highsierra (2.56 MB, application/zip)
2019-02-11 16:40 PST, Build Bot
no flags Details
Archive of layout-test-results from ews106 for mac-highsierra-wk2 (2.72 MB, application/zip)
2019-02-11 17:21 PST, Build Bot
no flags Details
Archive of layout-test-results from ews113 for mac-highsierra (2.11 MB, application/zip)
2019-02-11 17:22 PST, Build Bot
no flags Details
Patch (87.77 KB, patch)
2019-02-12 12:50 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ews104 for mac-highsierra-wk2 (2.83 MB, application/zip)
2019-02-12 13:49 PST, Build Bot
no flags Details
Archive of layout-test-results from ews101 for mac-highsierra (2.44 MB, application/zip)
2019-02-12 13:51 PST, Build Bot
no flags Details
Archive of layout-test-results from ews117 for mac-highsierra (2.10 MB, application/zip)
2019-02-12 14:36 PST, Build Bot
no flags Details
Patch (90.60 KB, patch)
2019-02-13 16:22 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Patch (92.44 KB, patch)
2019-02-13 18:49 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Patch (92.66 KB, patch)
2019-02-14 16:26 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Patch (92.65 KB, patch)
2019-02-14 16:28 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Patch (92.52 KB, patch)
2019-02-15 17:11 PST, Matt Baker
no flags Details | Formatted Diff | Diff
Patch for landing (93.21 KB, patch)
2019-02-16 16:50 PST, Matt Baker
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Joseph Pecoraro 2019-01-18 19:08:40 PST
Created attachment 359577 [details]
[IMAGE] JavaScript Profile

Frontend performance is very slow reloading theverge.com - 50% of time in TreeOutline _indexOfTreeElement

Steps to Reproduce:
1. Inspect <https://www.theverge.com>
2. Reload the page
  => Very slow inspector UI

Notes:
• Profiling Web Inspector shows massive time spent in TreeOutline code. See attached screeshot
Comment 1 Radar WebKit Bug Importer 2019-01-18 19:09:00 PST
<rdar://problem/47403986>
Comment 2 Joseph Pecoraro 2019-02-06 13:40:12 PST
Inspector is unusable on <https://www.nationalgeographic.com> due to this.
Comment 3 Matt Baker 2019-02-11 15:35:28 PST
Created attachment 361719 [details]
Patch
Comment 4 Matt Baker 2019-02-11 15:38:26 PST
(In reply to Matt Baker from comment #3)
> Created attachment 361719 [details]
> Patch

This is a _very_ large patch. Much of it is straightforward, however it would be nice to roll this in two steps:

1) Update SelectionController and Table
2) Update TreeOutline

To do this would require creating a temporary LegacySelectionController for TreeOutline to use, which would be removed in step 2.

I'd rather avoid this extra step if possible.
Comment 5 Matt Baker 2019-02-11 15:43:49 PST
Created attachment 361722 [details]
Patch
Comment 6 Matt Baker 2019-02-11 15:51:21 PST
Testing shows that the TreeElement comparator needs to be changed slightly for DOMTreeElements. The DOMTreeElement for a node's closing tag appears as a sibling of the open tag to the user, but is in fact a child.

This needs to be addressed for selection behavior to match the expectations set by the appearance of elements in the DOM tree.
Comment 7 Build Bot 2019-02-11 16:40:27 PST
Comment on attachment 361722 [details]
Patch

Attachment 361722 [details] did not pass mac-ews (mac):
Output: https://webkit-queues.webkit.org/results/11114669

New failing tests:
inspector/table/table-selection.html
inspector/table/table-remove-rows.html
Comment 8 Build Bot 2019-02-11 16:40:31 PST
Created attachment 361731 [details]
Archive of layout-test-results from ews100 for mac-highsierra

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews100  Port: mac-highsierra  Platform: Mac OS X 10.13.6
Comment 9 Matt Baker 2019-02-11 17:02:30 PST
(In reply to Build Bot from comment #7)
> Comment on attachment 361722 [details]
> Patch
> 
> Attachment 361722 [details] did not pass mac-ews (mac):
> Output: https://webkit-queues.webkit.org/results/11114669
> 
> New failing tests:
> inspector/table/table-selection.html

- Table.SelectAndDeselectRow.NotCached

> inspector/table/table-remove-rows.html

- Table.RemoveRow.Selected
- Table.RemoveRow.NotCached

Fixing now.
Comment 10 Build Bot 2019-02-11 17:21:47 PST
Comment on attachment 361722 [details]
Patch

Attachment 361722 [details] did not pass mac-wk2-ews (mac-wk2):
Output: https://webkit-queues.webkit.org/results/11115152

New failing tests:
inspector/table/table-selection.html
inspector/table/table-remove-rows.html
Comment 11 Build Bot 2019-02-11 17:21:49 PST
Created attachment 361739 [details]
Archive of layout-test-results from ews106 for mac-highsierra-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews106  Port: mac-highsierra-wk2  Platform: Mac OS X 10.13.6
Comment 12 Build Bot 2019-02-11 17:22:04 PST
Comment on attachment 361722 [details]
Patch

Attachment 361722 [details] did not pass mac-debug-ews (mac):
Output: https://webkit-queues.webkit.org/results/11114828

New failing tests:
inspector/table/table-selection.html
inspector/table/table-remove-rows.html
Comment 13 Build Bot 2019-02-11 17:22:06 PST
Created attachment 361740 [details]
Archive of layout-test-results from ews113 for mac-highsierra

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews113  Port: mac-highsierra  Platform: Mac OS X 10.13.6
Comment 14 Matt Baker 2019-02-11 20:50:15 PST
Comment on attachment 361722 [details]
Patch

r- until test failures are resolved.
Comment 15 Matt Baker 2019-02-12 12:47:02 PST
(In reply to Matt Baker from comment #14)
> Comment on attachment 361722 [details]
> Patch
> 
> r- until test failures are resolved.

(In reply to Matt Baker from comment #6)
> Testing shows that the TreeElement comparator needs to be changed slightly
> for DOMTreeElements. The DOMTreeElement for a node's closing tag appears as
> a sibling of the open tag to the user, but is in fact a child.
> 
> This needs to be addressed for selection behavior to match the expectations
> set by the appearance of elements in the DOM tree.

This isn't specific to DOMTreeElements. The comparator breaks when comparing a parent with one of its descendants.
Comment 16 Matt Baker 2019-02-12 12:50:21 PST
Created attachment 361822 [details]
Patch
Comment 17 Matt Baker 2019-02-12 12:51:45 PST
(In reply to Matt Baker from comment #16)
> Created attachment 361822 [details]
> Patch

Fixed the shift-selection issue. Still need to fix tests.
Comment 18 Build Bot 2019-02-12 13:49:20 PST
Comment on attachment 361822 [details]
Patch

Attachment 361822 [details] did not pass mac-wk2-ews (mac-wk2):
Output: https://webkit-queues.webkit.org/results/11125318

New failing tests:
inspector/table/table-selection.html
inspector/table/table-remove-rows.html
Comment 19 Build Bot 2019-02-12 13:49:21 PST
Created attachment 361832 [details]
Archive of layout-test-results from ews104 for mac-highsierra-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews104  Port: mac-highsierra-wk2  Platform: Mac OS X 10.13.6
Comment 20 Build Bot 2019-02-12 13:51:53 PST
Comment on attachment 361822 [details]
Patch

Attachment 361822 [details] did not pass mac-ews (mac):
Output: https://webkit-queues.webkit.org/results/11125441

New failing tests:
inspector/table/table-selection.html
inspector/table/table-remove-rows.html
Comment 21 Build Bot 2019-02-12 13:51:55 PST
Created attachment 361835 [details]
Archive of layout-test-results from ews101 for mac-highsierra

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews101  Port: mac-highsierra  Platform: Mac OS X 10.13.6
Comment 22 Devin Rousso 2019-02-12 13:53:37 PST
Comment on attachment 361722 [details]
Patch

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

Personally, I think you can keep using "Item" instead of "Object", unless you want to enforce that `WI.SelectionController` only uses objects (in which case we should add some assertions).  I find that "Item" is a bit more applicable, as it implies that it's part of a collection, whereas "object" is just kinda general.

It's unfortunate that we are creating so many copied `Set`s whenever modifying the selection.  Is there a way to duplicate most of the logic without having to create these new `Set`s?

> Source/WebInspectorUI/ChangeLog:95
> +        (WI.TreeOutline.):

NIT: we should probably fix `prepare-ChangeLog` to not generate these :|

> Source/WebInspectorUI/UserInterface/Base/Utilities.js:121
> +Object.defineProperty(Set.prototype, "equals",

NIT: much of this is the same logic as `isSubsetOf`, so you could simplify:

    return this.size === other.size && this.isSubsetOf(other);

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:36
> +        if (!this._comparator)
> +            this._comparator = (a, b) => a - b;

I think we should just force (with an assertion) callers to provide a `comparator`, rather than having this fallback.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:77
> +            this._updateSelectedObjects(newObjects);

NIT: you can inline construct the `Set`:

    this._updateSelectedObjects(new Set([this._lastSelectedObject]));

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:-111
> -        console.assert(index >= 0 && index < this.numberOfItems);

Ditto (<89).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:153
> +        this._lastSelectedObject = Array.from(newObjects).lastValue;

Rather than array-ify-ing the set, could you save the value of `this._lastSelectableObject()` and use that (you'd also probably want to assert that it's included in `newObjects` after calling `_addObjectRange` with it instead of `null`)?

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:162
> +        this._deselectAllAndSelect(null);

NIT: given you pass `null` here, that means we are effectively assuming that any selected "object" is non-falsy.  We should add assertions to that effect inside `select` (and other similar places).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:165
> +    willRemoveSelectedObjects()

Why this name change?  Using "will" is a bit of a misnomer as we are actually deselecting in this function, so it's not future.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:263
> +            this._addObjectRange(newObjects, this._firstSelectableObject(), object);

You can use `this._shiftAnchorObject` instead of calling `_firstSelectableObject()` again (the same is true for `_lastSelectedObject` and `object`).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:279
>          }

Style: missing semicolon.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:317
> +            let object = goingUp ? this._lastSelectableObject() : this._firstSelectableObject();

NIT: I'd just inline this on the line below.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:336
> +        if (!this.isSelected(priorObject)) {

Should we also be checking that `priorObject` is non-falsy?

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:357
> +        return this._delegate.selectionControllerFirstSelectableObject(this);

We should assert that this exists on `_delegate` in the constructor.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:362
> +        return this._delegate.selectionControllerLastSelectableObject(this);

Ditto (>357).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:377
> +        if (this._selectedObjects.equals(newObjects))

Having this check means that we're effectively iterating over the `Set` three times (assuming they're not equal).  Would it be "cheaper" to always assign to `_selectedObjects` and instead only fire `_delegate.selectionControllerSelectionDidChange` if `deselected` or `selected` is non-empty?

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:380
> +        let oldSelectedObjects = new Set(this._selectedObjects);

Why is this copy necessary?  You're about to override `_selectedObjects` anyways, which should be the only reference to the `Set` it holds (before it's assigned to `newObjects`).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:388
> +        this._delegate.selectionControllerSelectionDidChange(this, deselected, selected);

Ditto (>357).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:396
> +            if (current === lastObject)

We should assert that if `lastObject` is provided, it is included in `objects` (e.g. to cover the case where we `lastObject` isn't reachable.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:407
> +            if (current === lastObject)

Ditto (>396), except we'd want to assert that it's not included in `objects`.

> Source/WebInspectorUI/UserInterface/Views/Table.js:243
> +        return this._selectionController.isSelected(this._cachedRows.get(rowIndex));

I don't think this is how we should be using `WI.SelectionController` with `WI.Table`.  The rows are created/destroyed in most `WI.Table` operations (basically anything except scrolling).  I think we should be using the actual `representedObject` for each row, not the DOM node that is currently the "view" for that `representedObject`.  This would probably require `WI.Table` to have additional delegate calls for "what is the index for this object", and it would have to call back and forth between it's `_delegate` and `_selectionController` to translate between `representedObject` (for `WI.SelectionController` to track) and `index` (for `WI.Table` to visualize).  This way, if we re-sort (or really do any sort of regeneration), the underlying object for any given row will have it's selection preserved without any effort whatsoever, and the owner of the `WI.SelectionController` can then just query for the selected objects once it's done doing its work.

> Source/WebInspectorUI/UserInterface/Views/Table.js:616
> +            let rowIndex = Array.from(selectedObjects)[0].__index;

Rather than convert the entire `Set` to an array, you can use its iterator.

    selectedObjects.values().next().value

Perhaps we can make this into a prototype function, like `firstValue`?

> Source/WebInspectorUI/UserInterface/Views/Table.js:628
> +        // FIXME: needs to work for uncached rows
> +        return this._cachedRows.get(0);

This is another reason why I suggested using `representedObjects` on >243.  `WI.Table` should really be reaching out to its own `_delegate` and asking this question there.

> Source/WebInspectorUI/UserInterface/Views/Table.js:634
> +        // FIXME: needs to work for uncached rows
> +        return this._cachedRows.get(this.numberOfRows - 1);

Ditto (>627).

> Source/WebInspectorUI/UserInterface/Views/Table.js:1411
> +        for (let row of rows) {

Rather than iterate over `rows` and retrieve `__index` each time, you could use `removedIndexes` from below (or even merge the two loops entirely).

> Source/WebInspectorUI/UserInterface/Views/Table.js:-1414
> -        this._selectionController.didRemoveItems(rowIndexes);

Shouldn't we be calling `didRemoveObjects`?

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:60
> +        let comparator = (a, b) => {

NIT: I think this can be inlined.

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:-349
> -            treeOutline._selectionController.didRemoveItems(removedIndexes);

Ditto (<Table.js:1414).

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:-397
> -                treeOutline._selectionController.didRemoveItems(removedIndexes);

Ditto (<Table.js:1414).

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:865
> +        // TODO: used by SelectionController when:
> +        //  1) hitting the up arrow key when nothing is selected
> +        //  2) Doing a select all

Is this supposed to be in this patch, or a future one?
Comment 23 Build Bot 2019-02-12 14:36:44 PST
Comment on attachment 361822 [details]
Patch

Attachment 361822 [details] did not pass mac-debug-ews (mac):
Output: https://webkit-queues.webkit.org/results/11125651

New failing tests:
http/tests/inspector/network/resource-initiatorNode.html
inspector/table/table-remove-rows.html
inspector/table/table-selection.html
Comment 24 Build Bot 2019-02-12 14:36:46 PST
Created attachment 361845 [details]
Archive of layout-test-results from ews117 for mac-highsierra

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews117  Port: mac-highsierra  Platform: Mac OS X 10.13.6
Comment 25 Matt Baker 2019-02-13 16:06:21 PST
Comment on attachment 361722 [details]
Patch

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

>> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:-111
>> -        console.assert(index >= 0 && index < this.numberOfItems);
> 
> Ditto (<89).

?

>> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:165
>> +    willRemoveSelectedObjects()
> 
> Why this name change?  Using "will" is a bit of a misnomer as we are actually deselecting in this function, so it's not future.

The function doesn't actually remove anything, it just deselects the current selection and selects a new item in preparation for the selected items being removed. I'll see if I can come up with a better name.

>> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:377
>> +        if (this._selectedObjects.equals(newObjects))
> 
> Having this check means that we're effectively iterating over the `Set` three times (assuming they're not equal).  Would it be "cheaper" to always assign to `_selectedObjects` and instead only fire `_delegate.selectionControllerSelectionDidChange` if `deselected` or `selected` is non-empty?

I think this is a good idea. The majority of the time `this._selectedObjects.equals(newObjects)` will be false.

>> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:380
>> +        let oldSelectedObjects = new Set(this._selectedObjects);
> 
> Why is this copy necessary?  You're about to override `_selectedObjects` anyways, which should be the only reference to the `Set` it holds (before it's assigned to `newObjects`).

Oops!

>> Source/WebInspectorUI/UserInterface/Views/Table.js:616
>> +            let rowIndex = Array.from(selectedObjects)[0].__index;
> 
> Rather than convert the entire `Set` to an array, you can use its iterator.
> 
>     selectedObjects.values().next().value
> 
> Perhaps we can make this into a prototype function, like `firstValue`?

I like it.

>> Source/WebInspectorUI/UserInterface/Views/Table.js:1411
>> +        for (let row of rows) {
> 
> Rather than iterate over `rows` and retrieve `__index` each time, you could use `removedIndexes` from below (or even merge the two loops entirely).

I simplified this a bit.

>> Source/WebInspectorUI/UserInterface/Views/Table.js:-1414
>> -        this._selectionController.didRemoveItems(rowIndexes);
> 
> Shouldn't we be calling `didRemoveObjects`?

Actually I think we can eliminate didRemoveObjets entirely. Removing non-selected items doesn't affect the controller, and selected items are deselected before they are removed.

>> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:-349
>> -            treeOutline._selectionController.didRemoveItems(removedIndexes);
> 
> Ditto (<Table.js:1414).

TreeElements are always deselected before being removed, so this isn't necessary.
Comment 26 Matt Baker 2019-02-13 16:22:40 PST
Created attachment 361955 [details]
Patch
Comment 27 Matt Baker 2019-02-13 16:24:47 PST
(In reply to Matt Baker from comment #26)
> Created attachment 361955 [details]
> Patch

I need to resolve one outstanding issue with DOMTreeOutline before this can land. The problem is that DOMTreeElements for closing tags have the same represented object as the opening tag.

Should be easy to fix by subclassing DOMNode. Code using the closing tag DOMTreeElement's represented object will be none the wiser.
Comment 28 Matt Baker 2019-02-13 16:33:26 PST
(In reply to Matt Baker from comment #27)
> (In reply to Matt Baker from comment #26)
> > Created attachment 361955 [details]
> > Patch
> 
> I need to resolve one outstanding issue with DOMTreeOutline before this can
> land. The problem is that DOMTreeElements for closing tags have the same
> represented object as the opening tag.
> 
> Should be easy to fix by subclassing DOMNode. Code using the closing tag
> DOMTreeElement's represented object will be none the wiser.

Hmm, I think this won't work because we make comparisons using the DOMTreeElement's represented object, and we expect it to be a DOMNode. I'll try a different approach for ensuring the uniqueness of selectable items.
Comment 29 Matt Baker 2019-02-13 17:55:23 PST
Messing with the DOMTreeElement's representedObject is asking for trouble, so I came up with this hack:

class TreeOutline
{
    // Protected

    objectForSelection(treeElement)
    {
       return treeElement.representedObject;
    }
}

class DOMTreeOutline extends TreeOutline
{
    // Protected

    objectForSelection(treeElement)
    {
        if (treeElement instanceof WI.DOMTreeElement && treeElement.isCloseTag()) {
            if (!treeElement.__closeTagProxyObject)
                treeElement.__closeTagProxyObject = {originalRepresentedObject: treeElement.representedObject};
            return treeElement.__closeTagProxyObject;
        }

        return super.objectForSelection(treeElement);
    }
}

Whenever the SelectionController needs an object for selection, TreeOutline can just call `this.objectForSelection(treeElement)` instead of `treeElement.representedObject`. TreeOutline.getCachedTreeElement can be modified to check for `originalRepresentedObject`.
Comment 30 Matt Baker 2019-02-13 18:02:15 PST
(In reply to Matt Baker from comment #29)
> Messing with the DOMTreeElement's representedObject is asking for trouble,
> so I came up with this hack:
> 
> class TreeOutline
> {
>     // Protected
> 
>     objectForSelection(treeElement)
>     {
>        return treeElement.representedObject;
>     }
> }
> 
> class DOMTreeOutline extends TreeOutline
> {
>     // Protected
> 
>     objectForSelection(treeElement)
>     {
>         if (treeElement instanceof WI.DOMTreeElement &&
> treeElement.isCloseTag()) {
>             if (!treeElement.__closeTagProxyObject)
>                 treeElement.__closeTagProxyObject =
> {originalRepresentedObject: treeElement.representedObject};

Actually, we can modify the proxy object to be compatible with TreeOutline.getCachedTreeElement:

treeElement.__closeTagProxyObject = {__treeElementIdentifier: treeElement.representedObject.__treeElementIdentifier}

>             return treeElement.__closeTagProxyObject;
>         }
> 
>         return super.objectForSelection(treeElement);
>     }
> }
Comment 31 Matt Baker 2019-02-13 18:48:32 PST
(In reply to Matt Baker from comment #30)
> (In reply to Matt Baker from comment #29)
> > Messing with the DOMTreeElement's representedObject is asking for trouble,
> > so I came up with this hack:
> > 
> > class TreeOutline
> > {
> >     // Protected
> > 
> >     objectForSelection(treeElement)
> >     {
> >        return treeElement.representedObject;
> >     }
> > }
> > 
> > class DOMTreeOutline extends TreeOutline
> > {
> >     // Protected
> > 
> >     objectForSelection(treeElement)
> >     {
> >         if (treeElement instanceof WI.DOMTreeElement &&
> > treeElement.isCloseTag()) {
> >             if (!treeElement.__closeTagProxyObject)
> >                 treeElement.__closeTagProxyObject =
> > {originalRepresentedObject: treeElement.representedObject};
> 
> Actually, we can modify the proxy object to be compatible with
> TreeOutline.getCachedTreeElement:

It's simpler to just add a `treeElement` property to the proxy.
Comment 32 Matt Baker 2019-02-13 18:49:06 PST
Created attachment 361980 [details]
Patch
Comment 33 Devin Rousso 2019-02-13 23:18:41 PST
Comment on attachment 361980 [details]
Patch

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

r-, as this breaks selection in the Network table.  Everything else looks great, although I'd like to see a followup.  Awesome work!

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:32
> +        console.assert(typeof comparator === "function");

NIT: this should be below the `delegate` assertion, since it's listed after in the parameters.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:35
> +        this._comparator = comparator;

Ditto (>32).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:136
> +                let previous = this._previousSelectableItem(item);
> +                let next = this._nextSelectableItem(item);
> +
> +                while (!this.hasSelectedItem(previous) && !this.hasSelectedItem(next)) {
> +                    previous = this._previousSelectableItem(previous);
> +                    next = this._nextSelectableItem(next);
>                  }
> +
> +                if (this.hasSelectedItem(previous))
> +                    this._lastSelectedItem = previous;
> +                else if (this.hasSelectedItem(next))
> +                    this._lastSelectedItem = next;

It could be potentially costly to try to "eagerly" find the closest item in _both_ directions _at the same time_.  I think we should be a bit more "incremental", meaning we should only try one thing at a time.

    let previous = item;
    let next = item;
    while (!this._lastSelectedItem && previous && next) {
        previous = this._previousSelectableItem(previous);
        if (this.hasSelectedItem(previous)) {
            this._lastSelectedItem = previous;
            break;
        }

        next = this._nextSelectableItem(next);
        if (this.hasSelectedItem(next)) {
            this._lastSelectableItem = next;
            break;
        }
    }

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:167
> -    removeSelectedItems()
> +    willRemoveSelectedItems()

I personally think that `removeSelectedItems` is a better name, as it is "removing" the selected items from this controller.  Adding "will" makes me think that there's some sort of timeout/rAF that will "delay"  the removal.  None of the callers have any sort of "will" (or future tense) naming either, so I think it makes sense to match (e.g. no "will").

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:172
> +        let orderedSelection = Array.from(this._selectedItems).sort(this._comparator);

Rather than sort the entire list of selected items, couldn't we just find the first/last item (e.g. some sort of `min` and `max` for the array)?  I've written utilities functions for something like this in the past.

    Object.defineProperty(Array.prototype, "min",
    {
        value(comparator)
        {
            function defaultComparator(a, b)
            {
                return a - b;
            }
            comparator = comparator || defaultComparator;

            let min = 0;
            for (let i = 1; i < this.length; ++i) {
                if (comparator(this[min], this[i]) > 0)
                    min = i;
            }
            return this[min];
        },
    });

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:175
> +        let lastSelectedItem = orderedSelection.lastValue;

Ditto (>172).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:369
>          if (this._suppressSelectionDidChange || !this._delegate.selectionControllerSelectionDidChange)

NIT: we should remove the `!this._delegate.selectionControllerSelectionDidChange` check if we assert that it exists in thee constructor.

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:383
> +            if (current === lastItem)

We should assert that if `lastItem` is provided, it is included in `items` (e.g. to cover the case where we `lastItem` isn't reachable).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:394
> +            if (current === lastItem)

Ditto (>383), except we'd want to assert that it's not included in `items`.

> Source/WebInspectorUI/UserInterface/Views/CookieStorageContentView.js:86
> +        if (index < 0 || index >= this._cookies.length)
> +            return null;

This check seems unnecessary.  If anything, we should just be asserting, as `undefined` is effectively equivalent to `null` for our typical falsy checks.

> Source/WebInspectorUI/UserInterface/Views/DOMTreeOutline.js:327
> +            if (!treeElement.__closeTagProxyObject) {

Style: unnecessary brackets.

> Source/WebInspectorUI/UserInterface/Views/DOMTreeOutline.js:328
> +                treeElement.__closeTagProxyObject = {treeElement};

Can we use the `__treeElementIdentifier` instead?  Regardless, I think we should always have a `__` prefix, as we're effectively tacking on a view object to a model object (I realize that this is a "fake" model object, but the principle stands nonetheless).  If not, maybe we could use a different key, like `__proxyObjectTreeElement`?

> Source/WebInspectorUI/UserInterface/Views/NetworkTableContentView.js:332
> +        return this._rowIndexForRepresentedObject(object);

This is not the right function to use.  `_rowIndexForRepresentedObject` is only supposed to be used with actual model objects (e.g. `Resource` or `Node`), not the "bag-of-stuff" objects used by the Network table.  You should just use `this._filteredEntries.indexOf(object)`.

> Source/WebInspectorUI/UserInterface/Views/NetworkTableContentView.js:338
> +        if (index < 0 || index >= this._filteredEntries.length)
> +            return null;

Ditto (>CookieStorageContentView.js:85).

> Source/WebInspectorUI/UserInterface/Views/Table.js:1421
> +

Style: extra newline.

> Source/WebInspectorUI/UserInterface/Views/Table.js:1423
> +            if (rowIndexes.binaryIndexOf(index) >= 0) {

Clever!

> Source/WebInspectorUI/UserInterface/Views/Table.js:-1414
> -        this._selectionController.didRemoveItems(rowIndexes);

This slightly scares me, as it assumes that the caller deselects an item before it is removed.  I think we should either find some way of asserting (inside `SelectionController`) that removed items aren't selected or not remove `didRemoveItems` and have `SelectionController` simply remove items from its set.

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:60
> +        let comparator = (a, b) => {

Nicely written!

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:-349
> -            treeOutline._selectionController.didRemoveItems(removedIndexes);

Ditto (<Table.js:1414).

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:-397
> -                treeOutline._selectionController.didRemoveItems(removedIndexes);

Ditto (<Table.js:1414).

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:848
> +                treeElement.listItemElement.classList.remove("selected");

Style: missing newline after.

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:858
> +                treeElement.listItemElement.classList.add("selected");

Style: missing newline after.
Comment 34 Matt Baker 2019-02-14 16:10:12 PST
Comment on attachment 361980 [details]
Patch

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

>> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:136
>> +                    this._lastSelectedItem = next;
> 
> It could be potentially costly to try to "eagerly" find the closest item in _both_ directions _at the same time_.  I think we should be a bit more "incremental", meaning we should only try one thing at a time.
> 
>     let previous = item;
>     let next = item;
>     while (!this._lastSelectedItem && previous && next) {
>         previous = this._previousSelectableItem(previous);
>         if (this.hasSelectedItem(previous)) {
>             this._lastSelectedItem = previous;
>             break;
>         }
> 
>         next = this._nextSelectableItem(next);
>         if (this.hasSelectedItem(next)) {
>             this._lastSelectableItem = next;
>             break;
>         }
>     }

I like this better. We're still trying both direction at the same time, but written this way we can break out sooner.

>> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:172
>> +        let orderedSelection = Array.from(this._selectedItems).sort(this._comparator);
> 
> Rather than sort the entire list of selected items, couldn't we just find the first/last item (e.g. some sort of `min` and `max` for the array)?  I've written utilities functions for something like this in the past.
> 
>     Object.defineProperty(Array.prototype, "min",
>     {
>         value(comparator)
>         {
>             function defaultComparator(a, b)
>             {
>                 return a - b;
>             }
>             comparator = comparator || defaultComparator;
> 
>             let min = 0;
>             for (let i = 1; i < this.length; ++i) {
>                 if (comparator(this[min], this[i]) > 0)
>                     min = i;
>             }
>             return this[min];
>         },
>     });

Since this happens on a human time scale I think a sort is fine. This could definitely be made more efficient though. Looking at this again, I notice that the first value (min) Isn't even used unless we fail to find a selectable item after the last value (max).

For the sake of expediency I'd rather leave this as is for now.

>> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:369
>>          if (this._suppressSelectionDidChange || !this._delegate.selectionControllerSelectionDidChange)
> 
> NIT: we should remove the `!this._delegate.selectionControllerSelectionDidChange` check if we assert that it exists in thee constructor.

Now I'm reconsidering this. I can easily imagine use cases for Table that don't need to know about the selection changing, only _what_ is selected. I think we should only force the client to implement delegate methods that the Table needs for its essential functioning.

>> Source/WebInspectorUI/UserInterface/Views/DOMTreeOutline.js:328
>> +                treeElement.__closeTagProxyObject = {treeElement};
> 
> Can we use the `__treeElementIdentifier` instead?  Regardless, I think we should always have a `__` prefix, as we're effectively tacking on a view object to a model object (I realize that this is a "fake" model object, but the principle stands nonetheless).  If not, maybe we could use a different key, like `__proxyObjectTreeElement`?

Will change the property to __treeElement.

We can't use the __treeElementIdentifier of the represented object, because it is associated with the DOMTreeElement for the open tag.

>> Source/WebInspectorUI/UserInterface/Views/Table.js:-1414
>> -        this._selectionController.didRemoveItems(rowIndexes);
> 
> This slightly scares me, as it assumes that the caller deselects an item before it is removed.  I think we should either find some way of asserting (inside `SelectionController`) that removed items aren't selected or not remove `didRemoveItems` and have `SelectionController` simply remove items from its set.

Will add back.

Since SelectionCntroller.didRemoveIndexes is now SelectionCntroller.didRemoveItems, I'll need to make a slight change to avoid unnecessary index <-> object conversions.

>> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:-349
>> -            treeOutline._selectionController.didRemoveItems(removedIndexes);
> 
> Ditto (<Table.js:1414).

Since the item is deselected in this very same function, it seems overkill.
Comment 35 Matt Baker 2019-02-14 16:26:04 PST
Created attachment 362078 [details]
Patch
Comment 36 Matt Baker 2019-02-14 16:28:13 PST
Created attachment 362079 [details]
Patch
Comment 37 Matt Baker 2019-02-14 16:28:55 PST
(In reply to Matt Baker from comment #36)
> Created attachment 362079 [details]
> Patch

Fixed a copy-paste typo: s/_updateSelectedObjects/_updateSelectedItems
Comment 38 Devin Rousso 2019-02-14 17:08:07 PST
Comment on attachment 362079 [details]
Patch

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

r=me, nice work!

One bug that I've been able to intermittently reproduce is that sometimes, deleting a `DOMTreeElement` won't select the previous node, instead selecting the first child:
1. inspect <https://webkit.org>
2. expand <head> and <body>
3. select <body>
4. press ⌫
 => head > body > header is selected (in the path), even though that element is no longer in the tree

It seems to select the first child rathe than the previous sibling (only seems to be an issue with the DOM tree).

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:212
> +        let newItems = new Set(this._selectedItems);
> +        for (let item of items)
> +            newItems.delete(item);

NIT: you could leverage `Set.prototype.difference`.

    this._updateSelectedItems(this._selectedItems.difference(items));

> Source/WebInspectorUI/UserInterface/Views/CookieStorageContentView.js:80
> +        return this._cookies.indexOf(object);

While you're at it, we could also assert that `this._cookies.includes(object)` so that we check in both "directions (converting object-to-index and index-to-object).

> Source/WebInspectorUI/UserInterface/Views/NetworkTableContentView.js:332
> +        return this._filteredEntries.indexOf(object);

Ditto (>CookieStorageContentView.js:78).

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:480
> +        if (representedObject.__treeElement)

This should probably have a comment, not necessarily about the DOM tree, but about how this can be used to have multiple `TreeElement` that all effectively have the same `representedObject`.

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:904
> +        console.assert(treeElement, "Missing TreeElement for representedObject.", item);

I feel like this assertion may get triggered if we try to get the previous item after selecting the first item.  Perhaps we should just remove it (or modify it to also pass if `item === this.selectionControllerLastSelectableItem(controller)`).

> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:923
> +        console.assert(treeElement, "Missing TreeElement for representedObject.", item);

Ditto (>TreeOutline.js:904).
Comment 39 Matt Baker 2019-02-15 12:14:22 PST
Comment on attachment 362079 [details]
Patch

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

Setting r-. While addressing Devin's latest feedback I noticed an issue with shift-selecting using the up/down arrow keys. I think it was introduced in the switch from the index- to object-based SelectionController.

>> Source/WebInspectorUI/UserInterface/Views/CookieStorageContentView.js:80
>> +        return this._cookies.indexOf(object);
> 
> While you're at it, we could also assert that `this._cookies.includes(object)` so that we check in both "directions (converting object-to-index and index-to-object).

I'd rather not add a second O(N) function call for every index lookup. We could have Table assert that the value returned by the data source is non-false.

>> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:480
>> +        if (representedObject.__treeElement)
> 
> This should probably have a comment, not necessarily about the DOM tree, but about how this can be used to have multiple `TreeElement` that all effectively have the same `representedObject`.

Actually that is the problem this solves. We currently have a one-to-many relationship between represented objects and DOMTreeElements, and we need a one-to-one for SelectionController to function.

>> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:904
>> +        console.assert(treeElement, "Missing TreeElement for representedObject.", item);
> 
> I feel like this assertion may get triggered if we try to get the previous item after selecting the first item.  Perhaps we should just remove it (or modify it to also pass if `item === this.selectionControllerLastSelectableItem(controller)`).

This only asserts if the starting TreeElement (in the case you mention that would be the first item) can't be found, which should not happen.
Comment 40 Matt Baker 2019-02-15 16:54:27 PST
Comment on attachment 362079 [details]
Patch

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

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:341
> +        if (priorItem && !this.hasSelectedItem(priorItem)) {

This change was the problem. We need to take this branch when `priorItem` is null. We can either remove the check or write it like:

if (!priorItem || !this.hasSelectedItem(priorItem)) {
    ...
}
Comment 41 Matt Baker 2019-02-15 17:11:49 PST
Created attachment 362190 [details]
Patch
Comment 42 Devin Rousso 2019-02-16 11:31:39 PST
Comment on attachment 362079 [details]
Patch

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

>>> Source/WebInspectorUI/UserInterface/Views/CookieStorageContentView.js:80
>>> +        return this._cookies.indexOf(object);
>> 
>> While you're at it, we could also assert that `this._cookies.includes(object)` so that we check in both "directions (converting object-to-index and index-to-object).
> 
> I'd rather not add a second O(N) function call for every index lookup. We could have Table assert that the value returned by the data source is non-false.

Some sort of assertion would be great, just so we can catch those cases (and to balance the assertion when going from index-to-object).

>>> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:480
>>> +        if (representedObject.__treeElement)
>> 
>> This should probably have a comment, not necessarily about the DOM tree, but about how this can be used to have multiple `TreeElement` that all effectively have the same `representedObject`.
> 
> Actually that is the problem this solves. We currently have a one-to-many relationship between represented objects and DOMTreeElements, and we need a one-to-one for SelectionController to function.

I agree, but some sort of comment explaining that here would be appreciated.  Anyone unfamiliar with the code (specifically `DOMTreeElement`) will not know why this exists.

>>> Source/WebInspectorUI/UserInterface/Views/TreeOutline.js:904
>>> +        console.assert(treeElement, "Missing TreeElement for representedObject.", item);
>> 
>> I feel like this assertion may get triggered if we try to get the previous item after selecting the first item.  Perhaps we should just remove it (or modify it to also pass if `item === this.selectionControllerLastSelectableItem(controller)`).
> 
> This only asserts if the starting TreeElement (in the case you mention that would be the first item) can't be found, which should not happen.

That's the entire point having an assertion :|

I agree that that shouldn't happen, but that can change in the future.  An assertion will prevent us from shooting ourselves in the foot.
Comment 43 Devin Rousso 2019-02-16 11:34:04 PST
Comment on attachment 362190 [details]
Patch

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

r=me, nice work :)

Please address my comments on the last patch.

> Source/WebInspectorUI/ChangeLog:74
> +        (WI.Table):

NIT: we should probably fix `prepare-ChangeLog` to not generate these :|

> Source/WebInspectorUI/ChangeLog:97
> +        (WI.TreeOutline.):

NIT: we should probably fix `prepare-ChangeLog` to not generate these :|
Comment 44 Devin Rousso 2019-02-16 11:41:06 PST
I just discovered a few bugs :(

1. inspect <https://apple.com>
2. open the Storage tab to Cookies
3. select the last cookie
4. press shift-↑ (bottom two items should be selected)
5. press shift-↓ (bottom item should be selected)
6. press shift-↓
 => bottom item and top item are selected
(continuing to shift-↓ down will progressively select down the list)

1. inspect <https://apple.com>
2. open the Storage tab to Cookies
3. select from the last to the first items (e.g. ⇧-click from bottom to top)
5. press shift-↓ (all but first item are selected)
6. press shift-↓
 => all items are selected
(continuing to shift-↓ will toggle the first item selected and deselected)
Comment 45 Devin Rousso 2019-02-16 11:43:51 PST
(In reply to Devin Rousso from comment #44)
Dunno why this saved 🤔

> 1. inspect <https://apple.com>
> 2. open the Storage tab to Cookies
> 3. select the last cookie
> 4. press shift-↑ (bottom two items should be selected)
> 5. press shift-↓ (bottom item should be selected)
> 6. press shift-↓
>  => bottom item and top item are selected
> (continuing to shift-↓ down will progressively select down the list)
Doing this in a `TreeOutline` will cause the selected item (e.g. the path component) to be "lost" after (5) such that any future ⇧↑ or ⇧↓ will have no effect.

> 1. inspect <https://apple.com>
> 2. open the Storage tab to Cookies
> 3. select from the last to the first items (e.g. ⇧-click from bottom to top)
> 5. press shift-↓ (all but first item are selected)
> 6. press shift-↓
>  => all items are selected
> (continuing to shift-↓ will toggle the first item selected and deselected)
Doing this in a `TreeOutline` will cause the selected item (e.g. the path component) to be "lost" after (5) such that any future ⇧↑ or ⇧↓ will have no effect.
Comment 46 Devin Rousso 2019-02-16 11:49:36 PST
Comment on attachment 362190 [details]
Patch

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

> Source/WebInspectorUI/UserInterface/Controllers/SelectionController.js:135
> +                        this._lastSelectableItem = next;

I think you mean `_lastSelectedItem`.  Changing that fixes the issues I mentioned in comment #43 and comment #44.
Comment 47 Matt Baker 2019-02-16 16:50:21 PST
Created attachment 362222 [details]
Patch for landing
Comment 48 WebKit Commit Bot 2019-02-17 12:49:44 PST
Comment on attachment 362222 [details]
Patch for landing

Clearing flags on attachment: 362222

Committed r241652: <https://trac.webkit.org/changeset/241652>
Comment 49 WebKit Commit Bot 2019-02-17 12:49:46 PST
All reviewed patches have been landed.  Closing bug.