RESOLVED FIXED195264
Web Inspector: CSS Changes: modifications aren't shared for rules that match multiple elements 
https://bugs.webkit.org/show_bug.cgi?id=195264
Summary Web Inspector: CSS Changes: modifications aren't shared for rules that match ...
Devin Rousso
Reported 2019-03-03 20:46:41 PST
# STEPS TO REPRODUCE: 1. inspect any page with CSS 2. find a rule that has multiple selectors (e.g. `body, div`) 3. edit the rule when one of the selectors is matched (e.g. when the <body> is selected, it will match the `body` part of `body, div`) => the rule should show edits (both in the Rules and Changes panels) 4. select a different node where one of the other selectors is matched (e.g. when a <div> is selected, it will match the `div` part of `body, div`) => the edits made in (3) don't appear in the Rules panel (although they appear globally in the Changes panel) 5. edit the rule now that a different selector for that same rule is matched => the Changes panel only displays the most recent edit from (5) as a change (e.g. the changes made in (3) appear as though they were the initial content)
Attachments
Patch (62.72 KB, patch)
2019-04-02 16:42 PDT, Nikita Vasilyev 		nvasilyev: commit-queue-
DetailsFormatted DiffDiff
Patch (61.91 KB, patch)
2019-04-02 16:50 PDT, Nikita Vasilyev 		nvasilyev: commit-queue-
DetailsFormatted DiffDiff
Archive of layout-test-results from ews101 for mac-highsierra (2.61 MB, application/zip)
2019-04-02 17:39 PDT, EWS Watchlist 		no flags
Details
Patch (62.49 KB, patch)
2019-04-02 17:47 PDT, Nikita Vasilyev 		nvasilyev: commit-queue-
DetailsFormatted DiffDiff
Archive of layout-test-results from ews100 for mac-highsierra (2.80 MB, application/zip)
2019-04-02 18:36 PDT, EWS Watchlist 		no flags
Details
Archive of layout-test-results from ews105 for mac-highsierra-wk2 (2.89 MB, application/zip)
2019-04-02 19:18 PDT, EWS Watchlist 		no flags
Details
Archive of layout-test-results from ews117 for mac-highsierra (2.24 MB, application/zip)
2019-04-02 19:35 PDT, EWS Watchlist 		no flags
Details
Patch (63.37 KB, patch)
2019-04-03 16:54 PDT, Nikita Vasilyev 		nvasilyev: commit-queue-
DetailsFormatted DiffDiff
Archive of layout-test-results from ews101 for mac-highsierra (2.62 MB, application/zip)
2019-04-03 17:38 PDT, EWS Watchlist 		no flags
Details
Patch (63.47 KB, patch)
2019-04-03 17:53 PDT, Nikita Vasilyev 		hi: review-
nvasilyev: commit-queue-
DetailsFormatted DiffDiff
Patch (17.99 KB, patch)
2019-04-30 16:29 PDT, Nikita Vasilyev 		hi: review+
hi: commit-queue-
DetailsFormatted DiffDiff
Patch (18.45 KB, patch)
2019-05-04 17:01 PDT, Nikita Vasilyev 		no flags
DetailsFormatted DiffDiff
Patch (18.29 KB, patch)
2019-05-04 17:02 PDT, Nikita Vasilyev 		nvasilyev: review-
DetailsFormatted DiffDiff
[Image] Firefox Changes panel (34.41 KB, image/png)
2019-05-06 16:42 PDT, Nikita Vasilyev 		no flags
Details
Patch (20.66 KB, patch)
2019-05-15 15:41 PDT, Nikita Vasilyev 		no flags
DetailsFormatted DiffDiff
Patch (21.02 KB, patch)
2019-05-18 15:43 PDT, Nikita Vasilyev 		no flags
DetailsFormatted DiffDiff
Patch (21.60 KB, patch)
2019-05-21 20:27 PDT, Nikita Vasilyev 		no flags
DetailsFormatted DiffDiff
Patch (21.05 KB, patch)
2019-05-29 17:22 PDT, Nikita Vasilyev 		hi: review+
DetailsFormatted DiffDiff
Patch (21.07 KB, patch)
2019-05-31 13:54 PDT, Nikita Vasilyev 		no flags
DetailsFormatted DiffDiff
Show Obsolete (17) View All Add attachment proposed patch, testcase, etc.
Radar WebKit Bug Importer
Comment 1 2019-03-03 20:47:17 PST
<rdar://problem/48550023>
Nikita Vasilyev
Comment 2 2019-03-25 14:51:20 PDT
Thank you for reporting this! I wish I'd foresee this scenario sooner. `body, div` rule has different WI.CSSStyleDeclaration instances when inspecting <div> and <body>. However, both of these instances have the same `id`! Perhaps, the best solution here would be to avoid storing `_initialState` on the model directly, and maintain a map (CSSStyleDeclaration.id -> CSSStyleDeclaration) of modified properties on CSSManager.
Nikita Vasilyev
Comment 3 2019-04-02 16:42:49 PDT
Created attachment 366548 [details] Patch This is a sizable patch. I'd like to know if the overall direction is correct.
Nikita Vasilyev
Comment 4 2019-04-02 16:50:07 PDT
Created attachment 366552 [details] Patch Rebaselined.
EWS Watchlist
Comment 5 2019-04-02 17:39:10 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 6 2019-04-02 17:39:12 PDT Comment hidden (obsolete)
Nikita Vasilyev
Comment 7 2019-04-02 17:47:52 PDT
Created attachment 366561 [details] Patch
EWS Watchlist
Comment 8 2019-04-02 18:36:24 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 9 2019-04-02 18:36:26 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 10 2019-04-02 19:17:51 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 11 2019-04-02 19:18:01 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 12 2019-04-02 19:35:03 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 13 2019-04-02 19:35:05 PDT Comment hidden (obsolete)
Nikita Vasilyev
Comment 14 2019-04-03 16:54:07 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 15 2019-04-03 17:38:03 PDT Comment hidden (obsolete)
EWS Watchlist
Comment 16 2019-04-03 17:38:05 PDT Comment hidden (obsolete)
Nikita Vasilyev
Comment 17 2019-04-03 17:53:20 PDT
Created attachment 366683 [details] Patch
Devin Rousso
Comment 18 2019-04-22 10:37:45 PDT
Comment on attachment 366683 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=366683&action=review r-, I'm still confused as to why we "need" jsdiff? It seems like the majority of that library focuses on text diffing, which we aren't using at all. Is there a reason why we can't modify `Array.diffArrays` to support a custom comparator? If there's "more advanced" functionality provided by jsdiff, is it something which we could try to duplicate using our style/logic/methodology in `Array.diffArrays`? If we do end up using jsdiff, you'll need to modify WebInspectorUI/Scripts/copy-user-interface-resources.pl to make sure it's included in minified builds (you should probably also change WebKit/InspectorGResources.cmake). > Source/WebInspectorUI/UserInterface/Models/CSSProperty.js:508 > + ModifiedStatusChanged: "css-property-modified-status-changed", NIT: I realize that there's already a `*StatusChanged` event for this object, but I'd prefer `*StateChanged` (more common), or even better just `*Changed` (the most common). It avoids unnecessary characters and conveys the same message. > Source/WebInspectorUI/UserInterface/Models/CSSStyleDeclaration.js:59 > + set initialState(state) { this._initialState = state || null; } When is this used? Is it necessary to have the fallback `|| null`? > Source/WebInspectorUI/UserInterface/Models/CSSStyleDeclaration.js:434 > + if (item.added) { Is the reason that we don't need to check for `item.removed` as well because the removed value won't be visible in the Rules panel (e.g. it'll have been removed)?
Nikita Vasilyev
Comment 19 2019-04-23 15:04:49 PDT
(In reply to Devin Rousso from comment #18) > Comment on attachment 366683 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=366683&action=review > > r-, I'm still confused as to why we "need" jsdiff? It seems like the > majority of that library focuses on text diffing, which we aren't using at > all. Is there a reason why we can't modify `Array.diffArrays` to support a > custom comparator? Yes, there's a reason. Array.diffArrays can't take a custom comparator. Internally, diffArrays uses sets: Object.defineProperty(Array, "diffArrays", { value(initialArray, currentArray, onEach) { let initialSet = new Set(initialArray); let currentSet = new Set(currentArray); Array.diffArrays requires each item in the array to be unique. It's possible that several CSS properties in the same CSS rule are identical (even though I can't provide of a case when it would be intentional). jsdiff uses an algorithm based on "An O(ND) Difference Algorithm and Its Variations" by Eugene W. Myers. http://blog.robertelder.org/diff-algorithm/ It's a more complex algorithm that I wrote for Array.diffArrays. Yes, >80% of jsdiff code is currently unused. I can reimplement Myers' algorithm. If it isn't too time-consuming, maybe we can avoid using a 3rd party library.
Devin Rousso
Comment 20 2019-04-24 13:39:53 PDT
(In reply to Nikita Vasilyev from comment #19) > Array.diffArrays can't take a custom comparator. Internally, diffArrays uses sets: Can we change it so that it doesn't use sets? We don't need this algorithm to be the *most* efficient it can be, since we're basically only using this for CSS diffing right now and each rule is likely to have a very small (e.g. <100) number of properties. Couldn't we do a "naive" approach by checking all future items in `currentArray` against the current item of `initialArray` (e.g. `initialArray[indexInitial]` compared to all items from `indexCurrent` to `currentArray.length - 1` in `currentArray`)?
Nikita Vasilyev
Comment 21 2019-04-24 13:59:46 PDT
I think it should work. Diff algorithm improvements could be a separate patch.
Nikita Vasilyev
Comment 22 2019-04-26 17:42:45 PDT
(In reply to Nikita Vasilyev from comment #21) > I think it should work. Diff algorithm improvements could be a separate > patch. The naive algorithm produced a very suboptimal diff. It explained well in this article: https://epxx.co/artigos/diff_en.html I'm trying something different to avoid using Myers' algorithm.
Nikita Vasilyev
Comment 23 2019-04-30 16:20:29 PDT
Comment on attachment 366683 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=366683&action=review >> Source/WebInspectorUI/UserInterface/Models/CSSProperty.js:508 >> + ModifiedStatusChanged: "css-property-modified-status-changed", > > NIT: I realize that there's already a `*StatusChanged` event for this object, but I'd prefer `*StateChanged` (more common), or even better just `*Changed` (the most common). It avoids unnecessary characters and conveys the same message. I like `*Changed`. >> Source/WebInspectorUI/UserInterface/Models/CSSStyleDeclaration.js:434 >> + if (item.added) { > > Is the reason that we don't need to check for `item.removed` as well because the removed value won't be visible in the Rules panel (e.g. it'll have been removed)? Correct. (I may add red markers to show removed properties in the future but not in this patch.)
Nikita Vasilyev
Comment 24 2019-04-30 16:29:59 PDT
Created attachment 368625 [details] Patch
Nikita Vasilyev
Comment 25 2019-04-30 16:36:02 PDT
My latest patch doesn't use any 3rd party libraries. I modified the diff method to take a hash function. It allowed me to continue using Sets. To allow repeating items in the arrays, I replaced Sets with Maps to store usage counts.
Devin Rousso
Comment 26 2019-05-03 22:56:17 PDT
Comment on attachment 368625 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=368625&action=review r=me, please address the `Array.diffArrays` question before landing. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:504 > + value(initialArray, currentArray, hashFunction, onEach) NIT: I'd make `hashFunction` an "optional" and have a fallback implementation, which is just an ident function. This matches other uses of this pattern, like `comparator`. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:523 > + function decrementUsageCount(map, key) { Style: put this below the other function so that they're all nearby. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:-531 > - ++deltaCurrent; Why did this move? > Source/WebInspectorUI/UserInterface/Base/Utilities.js:578 > + onEach(initialArray[i], -1); I think you should always be doing this, not just after the final decrement. If I had three items left in this array, I'd expect to see three removals. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:589 > + onEach(current, 1); Ditto (>578). > Source/WebInspectorUI/UserInterface/Models/CSSProperty.js:408 > + let cssProperty = new WI.CSSProperty( > + this._index, > + this._text, > + this._name, > + this._rawValue, > + this._priority, > + this._enabled, > + this._overridden, > + this._implicit, > + this._anonymous, > + this._valid, > + this._styleSheetTextRange); I hate this syntax T.T > Source/WebInspectorUI/UserInterface/Models/CSSStyleDeclaration.js:59 > + set initialState(state) { this._initialState = state; } Why is this needed? > Source/WebInspectorUI/UserInterface/Views/ChangesDetailsSidebarPanel.js:166 > + propertyLineElement.classList.add("css-property-line", className); > + let stylePropertyView = new WI.SpreadsheetStyleProperty(null, cssProperty, {readOnly: true}); Style: missing newline. NIT: you should add a `const delegate = null;` so it's clearer.
Nikita Vasilyev
Comment 27 2019-05-04 16:34:38 PDT
Comment on attachment 368625 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=368625&action=review >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:-531 >> - ++deltaCurrent; > > Why did this move? This shouldn't move. I'm adding more tests now I found this doesn't work correctly with repeating items. >> Source/WebInspectorUI/UserInterface/Models/CSSProperty.js:408 >> + this._styleSheetTextRange); > > I hate this syntax T.T What are you proposing? >> Source/WebInspectorUI/UserInterface/Models/CSSStyleDeclaration.js:59 >> + set initialState(state) { this._initialState = state; } > > Why is this needed? It isn't!
Nikita Vasilyev
Comment 28 2019-05-04 17:01:03 PDT
Created attachment 369076 [details] Patch Resetting to r? since I made changes to Array.diffArrays.
Nikita Vasilyev
Comment 29 2019-05-04 17:02:44 PDT
Created attachment 369077 [details] Patch
Devin Rousso
Comment 30 2019-05-05 22:19:15 PDT
Comment on attachment 369077 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=369077&action=review > LayoutTests/inspector/unit-tests/array-utilities-expected.txt:92 > +["b","a","b"], ["a","b","a"] => [["a",0],["b",0],["b",-1],["a",1]] This seems wrong. I'd expect to see a `["b",-1]` at the very beginning, not the end. ["b","a","b"], ["a","b","a"] => [["b",-1],["a",0],["b",0],["a",1]] > LayoutTests/inspector/unit-tests/array-utilities-expected.txt:95 > +["a","b","b","c"], ["c","b","b","b","a"] => [["c",0],["b",0],["b",0],["b",1],["c",-1],["a",1]] > +["a","b","b","b","c"], ["c","b","b","a"] => [["c",0],["b",0],["b",0],["b",-1],["a",0]] > +["a","a","b","b","c","c"], ["b","b","c","c","a","a"] => [["b",0],["b",0],["c",0],["c",0],["a",0],["a",0]] Ditto (>92). What happened to the starting "a"s? ["a","b","b","c"], ["c","b","b","b","a"] => [["a",-1],["c",1],["b",0],["b",0],["b",1],["c",-1],["a",1]] ["a","b","b","b","c"], ["c","b","b","a"] => [["a",-1],["c",1],["b",0],["b",0],["b",-1],["c",-1],["a",1]] ["a","a","b","b","c","c"], ["b","b","c","c","a","a"] => [["a",-1],["a",-1],["b",0],["b",0],["c",0],["c",0],["a",1],["a",1]] Especially in the last case, it seems like `Array.diffArrays` considers an item that moved as a non-delete-then-add, which I'd disagree with. A move involves a delete at one place and an add at another. The only time we should see a `0` action is when the item is in the same relative positioning as it was initially (like the "bbcc" in the last example). Moves should be a zero-sum of `-1` and `+1` (or in the opposite order).
Nikita Vasilyev
Comment 31 2019-05-06 16:32:55 PDT
Comment on attachment 369077 [details] Patch I was contemplating even adding tests for repeated items because I don't see why would anyone intentionally add CSS properties that are exactly the same. In fact, we already show "Duplicate property" warning in the Styles panel. This is the case that I had in mind: font-size: 12px; [10 other properties] Removing `font-size: 12px` and adding it as the last property would not show any changes, which I understand is a bit unconventional. The goal was to make the output a little less noisy since it's likely to be used for copy/pasting new values. I can go either way but ultimatelly I don't think any developers would even notice it in their workflows.
Nikita Vasilyev
Comment 32 2019-05-06 16:42:01 PDT
Created attachment 369201 [details] [Image] Firefox Changes panel To bolster my case, this what removing the 1st CSS property ("font-size: 4.8rem" in this case) and appending it as the last looks in Firefox. Since they don't display unchanged properties, the diff output becomes confusing.
Nikita Vasilyev
Comment 33 2019-05-06 17:49:07 PDT
Also, if we want an optimal diff output and at the same time don't want to eliminate common (i.e. moved) items, we are back to square one. The solution is Myers' algorithm.
Nikita Vasilyev
Comment 34 2019-05-10 15:08:12 PDT
Comment on attachment 369077 [details] Patch Greg pointed out offline that order does matter: font-size: 12px; font-size: .8rem; If I swap the properties, the diff should indeed display the change.
Nikita Vasilyev
Comment 35 2019-05-15 15:41:16 PDT
Created attachment 369999 [details] Patch
Nikita Vasilyev
Comment 36 2019-05-15 15:45:39 PDT
(In reply to Devin Rousso from comment #30) > Comment on attachment 369077 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=369077&action=review > > > LayoutTests/inspector/unit-tests/array-utilities-expected.txt:92 > > +["b","a","b"], ["a","b","a"] => [["a",0],["b",0],["b",-1],["a",1]] > > This seems wrong. I'd expect to see a `["b",-1]` at the very beginning, not > the end. > > ["b","a","b"], ["a","b","a"] => [["b",-1],["a",0],["b",0],["a",1]] With my latest patch, it's: [["a",1],["b",0],["a",0],["b",-1]] I agree that what you suggested is better. This could be improved by using "patience diff": https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ I'd prefer to do it later.
Nikita Vasilyev
Comment 37 2019-05-15 15:49:28 PDT
(In reply to Nikita Vasilyev from comment #33) > Also, if we want an optimal diff output and at the same time don't want to > eliminate common (i.e. moved) items, we are back to square one. The solution > is Myers' algorithm. My latest patch does NOT eliminate common (e.e. moved) items. I didn't use Myers' algorithm. I used a naive algorithm with an added common suffix and prefix eliminations. It's plenty fast for my case and the output is acceptable, in my opinion.
Nikita Vasilyev
Comment 38 2019-05-18 15:43:16 PDT
Created attachment 370198 [details] Patch Removed an assert that no longer makes sense ("CSSProperty was modified without saving initial state"). The rest is the same as the previous patch.
Devin Rousso
Comment 39 2019-05-20 13:38:53 PDT
Comment on attachment 370198 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370198&action=review > LayoutTests/inspector/unit-tests/array-utilities-expected.txt:92 > +["a"], ["a","a"] => [["a",1],["a",0]] > +["a","a"], ["a"] => [["a",-1],["a",0]] > +["a","a"], ["a","a"] => [["a",0],["a",0]] > +["b","a","b"], ["a","b","a"] => [["a",1],["b",0],["a",0],["b",-1]] NIT: is there any way for you to reverse the ordering of all these? [["a",1],["a",0]] vs [["a",0],["a",1]] [["a",-1],["a",0]] vs [["a",0],["a",-1]] [["a",1],["b",0],["a",0],["b",-1]] vs [["b",-1],["a",0],["b",0],["a",1]] > LayoutTests/inspector/unit-tests/array-utilities-expected.txt:95 > +["a","a","b","b","c","c"], ["b","b","c","c","a","a"] => [["a",-1],["a",-1],["b",0],["b",0],["c",0],["c",0],["a",1],["a",1]] and yet somehow, this one is exactly as I'd expect :) > Source/WebInspectorUI/UserInterface/Base/Utilities.js:512 > + value(initialArray, currentArray, onEach, comparator = (initial, current) => initial === current) Our usual style of default comparators is to do a check in the function itself (see any of the other `Array.prototype` functions). ``` function defaultComparator(initial, current) { return initial === current; } comparator = comparator || defaultComparator; ``` > Source/WebInspectorUI/UserInterface/Base/Utilities.js:514 > + function findShortestEdit(initialArray, currentArray) { Do you actually need these arguments, since this is called with variables of the same name? Please avoid shadowing wherever possible. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:519 > + for (let i = 0; i < initialArray.length; ++i) { > + for (let j = 0; j < currentArray.length; ++j) { If the arrays are [11, 12, 13, 14, 15] and [21, 12, 13, 14, 25], would this think that the entire array was a giant edit? I'd expect two smaller sub-edit "sections" at the beginning (11 and 21) and end (15 and 25). Regardless, this NEEDS a comment or some sort of explanation as to what it's expected to do. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:536 > + function commonPrefixSize(listA, listB) { NIT: use `length` instead of `size` since this is an array (matches `array.length`). > Source/WebInspectorUI/UserInterface/Base/Utilities.js:537 > + let shortListLength = Math.min(listA.length, listB.length); NIT: `shorterListLength` or `commonLength` > Source/WebInspectorUI/UserInterface/Base/Utilities.js:541 > + for (; i < shortListLength; ++i) { > + if (!comparator(listA[i], listB[i])) > + break; Use a while loop. ``` while (i < shortListLength && comparator(listA[i], listB[i])) ++i; ``` > Source/WebInspectorUI/UserInterface/Base/Utilities.js:546 > + function commonSuffixSize(listA, listB) { Ditto (>536). > Source/WebInspectorUI/UserInterface/Base/Utilities.js:548 > + let aLength = listA.length; > + let bLength = listB.length; It's unnecessary to save these to variables. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:549 > + let shortListLength = Math.min(aLength, bLength); Ditto (>537). > Source/WebInspectorUI/UserInterface/Base/Utilities.js:551 > + for (; i < shortListLength; ++i) { Ditto (>541). > Source/WebInspectorUI/UserInterface/Base/Utilities.js:553 > + let a = listA[aLength - i - 1]; > + let b = listB[bLength - i - 1]; Ditto (>548). > Source/WebInspectorUI/UserInterface/Base/Utilities.js:560 > + function callOnEach(count, action, array) { NIT: this name makes me think it's going to invoke `action` (which is a function) on the first `count` items of `array`. I'd use a different name either for the function itself, or just the `action` argument. Alternatively, you could just inline this at each callsite. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:567 > + let suffixLength = commonSuffixSize(initialArray, currentArray); > + let suffix = []; NIT: I'd reverse the order of these so that `suffixLength` lines up with the `if`.
Nikita Vasilyev
Comment 40 2019-05-20 15:08:52 PDT
(In reply to Devin Rousso from comment #39) > Comment on attachment 370198 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=370198&action=review > > > LayoutTests/inspector/unit-tests/array-utilities-expected.txt:92 > > +["a"], ["a","a"] => [["a",1],["a",0]] > > +["a","a"], ["a"] => [["a",-1],["a",0]] > > +["a","a"], ["a","a"] => [["a",0],["a",0]] > > +["b","a","b"], ["a","b","a"] => [["a",1],["b",0],["a",0],["b",-1]] > > NIT: is there any way for you to reverse the ordering of all these? > [["a",1],["a",0]] vs [["a",0],["a",1]] > [["a",-1],["a",0]] vs [["a",0],["a",-1]] > [["a",1],["b",0],["a",0],["b",-1]] vs [["b",-1],["a",0],["b",0],["a",1]] As I said, I'd need to use patience diff/preprocessing algorithm. I agree that what you suggested is better. This could be improved by using "patience diff": https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ I'd prefer to do it later.
Nikita Vasilyev
Comment 41 2019-05-20 15:33:23 PDT
Comment on attachment 370198 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370198&action=review >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:519 >> + for (let j = 0; j < currentArray.length; ++j) { > > If the arrays are [11, 12, 13, 14, 15] and [21, 12, 13, 14, 25], would this think that the entire array was a giant edit? I'd expect two smaller sub-edit "sections" at the beginning (11 and 21) and end (15 and 25). > > Regardless, this NEEDS a comment or some sort of explanation as to what it's expected to do. No, it wouldn't. It does what you expect: - 11 + 21 12 13 14 - 15 + 25 because... > Source/WebInspectorUI/UserInterface/Base/Utilities.js:529 > + if (comparator(initialArray[i], currentArray[j])) { > + if (newEditCount < editCount) { > + editCount = newEditCount; > + deletionCount = i; > + additionCount = j; > + } > + break; ...it exits here. I don't know about the comment. At a high level, findShortestEdit does what it says. I couldn't find a good middle ground between function name and a very long comment.
Devin Rousso
Comment 42 2019-05-20 16:21:29 PDT
Comment on attachment 370198 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370198&action=review >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:529 >> + break; > > ...it exits here. > > I don't know about the comment. At a high level, findShortestEdit does what it says. I couldn't find a good middle ground between function name and a very long comment. This only breaks out of the inner loop though. It will continue iterating the outer loop. The only reason this "ends" is because of the other `break` after `if (newEditCount > editCount)`. The very fact that I didn't understand _how_ it worked means that it needs a comment. That would've made it much easier to understand.
Nikita Vasilyev
Comment 43 2019-05-20 16:27:52 PDT
Comment on attachment 370198 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370198&action=review >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:541 >> + break; > > Use a while loop. > ``` > while (i < shortListLength && comparator(listA[i], listB[i])) > ++i; > ``` This looks too dense for me. Especially... >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:551 >> + for (; i < shortListLength; ++i) { > > Ditto (>541). ...here: while (i < shortListLength && comparator(listA[listA.length - i - 1], listB[listB.length - i - 1]))
Nikita Vasilyev
Comment 44 2019-05-20 17:26:13 PDT
Comment on attachment 370198 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370198&action=review >>> Source/WebInspectorUI/UserInterface/Base/Utilities.js:529 >>> + break; >> >> ...it exits here. >> >> I don't know about the comment. At a high level, findShortestEdit does what it says. I couldn't find a good middle ground between function name and a very long comment. > > This only breaks out of the inner loop though. It will continue iterating the outer loop. The only reason this "ends" is because of the other `break` after `if (newEditCount > editCount)`. > > The very fact that I didn't understand _how_ it worked means that it needs a comment. That would've made it much easier to understand. This got me thinking, that this function could be simplified. This function should find the first longest edit. The current name is misleading. It could break out of the outer loop instead, it seems 🤔
Nikita Vasilyev
Comment 45 2019-05-21 17:51:16 PDT
(In reply to Nikita Vasilyev from comment #44) > Comment on attachment 370198 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=370198&action=review > > >>> Source/WebInspectorUI/UserInterface/Base/Utilities.js:529 > >>> + break; > >> > >> ...it exits here. > >> > >> I don't know about the comment. At a high level, findShortestEdit does what it says. I couldn't find a good middle ground between function name and a very long comment. > > > > This only breaks out of the inner loop though. It will continue iterating the outer loop. The only reason this "ends" is because of the other `break` after `if (newEditCount > editCount)`. > > > > The very fact that I didn't understand _how_ it worked means that it needs a comment. That would've made it much easier to understand. > > This got me thinking, that this function could be simplified. > This function should find the first longest edit. The current name is > misleading. > It could break out of the outer loop instead, it seems 🤔 Actually, I don't think it can be simplified. Consider this case: abbc cbbba Expected result: - a + c b b - c + b + a If I break out of the outside loop, it would result in: + c + b + b + b a - b - b - c It would exit on the first iteration of the outer loop after finding matching "a": abbc cbbba ---- +++ Which is incorrect. When it continues iterating, it finds the shortest edit correctly: abbc cbbba - +
Nikita Vasilyev
Comment 46 2019-05-21 20:27:35 PDT
Created attachment 370376 [details] Patch
Devin Rousso
Comment 47 2019-05-22 21:35:46 PDT
Comment on attachment 370376 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370376&action=review > Source/WebInspectorUI/UserInterface/Base/Utilities.js:584 > + let suffixLength = commonSuffixLength(initialArray, currentArray); What exactly is the point of determining the common suffix? Couldn't you just add a `break` inside the `while` below that checks that `!initialArray.length && !currentArray.length`? Since you are `slice`ing each array in each iteration, eventually the common suffix will be the common prefix (e.g. everything before it would have been `slice`d).
Nikita Vasilyev
Comment 48 2019-05-23 13:55:04 PDT
Comment on attachment 370376 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370376&action=review >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:584 >> + let suffixLength = commonSuffixLength(initialArray, currentArray); > > What exactly is the point of determining the common suffix? Couldn't you just add a `break` inside the `while` below that checks that `!initialArray.length && !currentArray.length`? Since you are `slice`ing each array in each iteration, eventually the common suffix will be the common prefix (e.g. everything before it would have been `slice`d). This is a performance optimization. It's faster to remove the suffix once and don't do extra work in the `while` below. Also, commonSuffixLength has linear time complexity, when findShortestEdit is O(nm). I'd rather keep it.
Devin Rousso
Comment 49 2019-05-27 19:43:38 PDT
Comment on attachment 370376 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370376&action=review > Source/WebInspectorUI/UserInterface/Base/Utilities.js:521 > + // Find the first shortest edit. In the another words, find the prefix of the first longest common sequence. This doesn't really explain what it's doing as far as I understand it. It's really more about finding the first index in each array where the items at those indexes are equal such that the total length of both non-equal prefixes is minimized. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:534 > + if (newEditCount > editCount) { As a potential optimization, it may be worth adding another `break` outside the inner `for` inside an `if (i > editCount)`. This should help avoid some unnecessary looping if the shortest edit is indeed very short :P >>> Source/WebInspectorUI/UserInterface/Base/Utilities.js:584 >>> + let suffixLength = commonSuffixLength(initialArray, currentArray); >> >> What exactly is the point of determining the common suffix? Couldn't you just add a `break` inside the `while` below that checks that `!initialArray.length && !currentArray.length`? Since you are `slice`ing each array in each iteration, eventually the common suffix will be the common prefix (e.g. everything before it would have been `slice`d). > > This is a performance optimization. It's faster to remove the suffix once and don't do extra work in the `while` below. Also, commonSuffixLength has linear time complexity, when findShortestEdit is O(nm). > > I'd rather keep it. I was saying to add the `if (!initialArray.length && !currentArray.length)` after the `if (prefixLength) { ... }`, not after the `findShortestEdit()` call. I don't think what you have right now is more performant, as it has to do the check of finding a common suffix where there might not even be one (e.g. it "front loads" the work). If I had a "sequence" that followed <common prefix> <edit> <common suffix>, then removing the <common suffix> is unnecessary, since the fundamental logic for `commonPrefixLength` and `commonSuffixLength` are the same. The first iteration of the `while` will remove <common prefix> and <edit>, meaning that all that's left is the <common suffix>, which can be handled by the next iteration's `commonPrefixLength` (a prefix is the same as a suffix if the entire string _is_ the prefix). Then, adding the early `break` I suggested would break out of the `while` before it calls `findShortestEdit()` for the second time. In this example, the overall amount of work done is the same (albeit in a different ordering), but if the "sequence" was instead just <common prefix> <edit>, then you'd have tried to find a `commonSuffixLength` for nothing and wasted some "effort" as a result. > Source/WebInspectorUI/UserInterface/Models/CSSStyleDeclaration.js:437 > + }, (a, b) => a.equals(b)); Style: I don't usually like having additional arguments after an inline function argument, so I'd prefer if you moved both of these functions to be non-inline instead. ``` function onEach(cssProperty, action) { ... } function comparator(a, b) { return a.equals(b); } Array.diffArrays(initialCSSProperties, cssProperties, onEach, comparator); ``` > Source/WebInspectorUI/UserInterface/Views/ChangesDetailsSidebarPanel.js:170 > + }, (a, b) => a.equals(b)); Ditto (>CSSStyleDeclaration.js:437).
Nikita Vasilyev
Comment 50 2019-05-29 17:00:59 PDT
Comment on attachment 370376 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370376&action=review >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:521 >> + // Find the first shortest edit. In the another words, find the prefix of the first longest common sequence. > > This doesn't really explain what it's doing as far as I understand it. It's really more about finding the first index in each array where the items at those indexes are equal such that the total length of both non-equal prefixes is minimized. You're correct. Can we simplify your 2nd sentence? How about: "Find the shortest prefix of matching items in both arrays." >> Source/WebInspectorUI/UserInterface/Base/Utilities.js:534 >> + if (newEditCount > editCount) { > > As a potential optimization, it may be worth adding another `break` outside the inner `for` inside an `if (i > editCount)`. This should help avoid some unnecessary looping if the shortest edit is indeed very short :P I like it!
Nikita Vasilyev
Comment 51 2019-05-29 17:22:10 PDT
Created attachment 370902 [details] Patch
Devin Rousso
Comment 52 2019-05-30 20:14:34 PDT
Comment on attachment 370902 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=370902&action=review r=me, nice work! > LayoutTests/inspector/unit-tests/array-utilities-expected.txt:90 > +["a"], ["a","a"] => [["a",0],["a",1]] > +["a","a"], ["a"] => [["a",0],["a",-1]] I love how these are now in the "right" order :) > Source/WebInspectorUI/UserInterface/Base/Utilities.js:532 > + if (i > editCount) This could have a comment like >537. > Source/WebInspectorUI/UserInterface/Base/Utilities.js:534 > + break; > + for (let j = 0; j < currentArray.length; ++j) { Style: missing newline > Source/WebInspectorUI/UserInterface/Models/CSSStyleDeclaration.js:429 > + let initialCSSProperties = this._initialState.visibleProperties; > + let cssProperties = this.visibleProperties; NIT: these can be inlined. > Source/WebInspectorUI/UserInterface/Views/ChangesDetailsSidebarPanel.js:153 > + let initialCSSProperties = style.initialState.visibleProperties; > + let cssProperties = style.visibleProperties; NIT: these can be inlined.
Nikita Vasilyev
Comment 53 2019-05-31 13:54:13 PDT
Created attachment 371081 [details] Patch
WebKit Commit Bot
Comment 54 2019-05-31 15:53:46 PDT
Comment on attachment 371081 [details] Patch Clearing flags on attachment: 371081 Committed r245991: <https://trac.webkit.org/changeset/245991>
WebKit Commit Bot
Comment 55 2019-05-31 15:53:49 PDT
All reviewed patches have been landed. Closing bug.
Devin Rousso
Comment 56 2019-06-17 21:57:16 PDT
*** Bug 194607 has been marked as a duplicate of this bug. ***
Note You need to log in before you can comment on or make changes to this bug.