Sortable set #5083

timse · 2017-06-18T04:57:22Z

What kind of change does this PR introduce?

feature

Did you add tests for your changes?

tested through existing code

If relevant, link to documentation update:

N/A

Summary

Introduce a "SortableSet" Collection that abstracts the sorting out of the responsibility of Module/Chunk

Does this PR introduce a breaking change?

No

Other information

Per default _chunks are flagged as sorted in Module, however, this only holds true as they are initialized empty.
Concatenated Module, however, has initial modules and therefore is not guaranteed to be ordered, the flags should, therefore, be false. Using SortedSet fixes this as a side effect.

use SortableSet to keep "_modules" sorted

use SortableSet to keep "_chunks" sorted

fix tests that was falsy - per default chunks are flagged as sorted in module however this only holds true as they are initialized empty. Concatenated module however has initial modules and therefore is not guaranteed to be ordered, the flags should therfor be false. Using SortedSet fixes this as a sideeffect

sokra · 2017-06-18T12:41:32Z

lib/Chunk.js

 class Chunk {

+	static sortById(a, b) {


Why making this methods public? What was wrong with the original way, which hides them?

Initially I wanted to flip them, so sortByXXX was in Module and Chunk would use Module.sortByXXX to sort its Modules.
As Module should know how to sort modules, not Chunk.
However node and circular dependencies let me down and so this is a left over of that approach, happy to make them private again, but I'd rather find a solution for the intial idea. :D

sokra · 2017-06-18T13:18:26Z

lib/util/SortableSet.js

+	 * @returns {void}
+	 */
+	sortWith(sortFn) {
+		const sortedArray = Array.from(this).sort(sortFn);


The original impl checked if the set was already sorted before sorting. The new SortableSet should do the same. add and clear should be overriden to invalidate sorting. Best store the current active sortFn.

yeah, I wasn't sure if this approach is ok and if I wanted to shadow as little as possible from the initial set (: happy to add some logic there

sokra · 2017-06-18T13:18:38Z

test/statsCases/scope-hoisting-multi/expected.txt

@@ -19,7 +19,7 @@ Child
       [0] (webpack)/test/statsCases/scope-hoisting-multi/common_lazy_shared.js 25 bytes {0} {1} {2} [built]
       [1] (webpack)/test/statsCases/scope-hoisting-multi/vendor.js 25 bytes {5} [built]
           ModuleConcatenation (inner): module is an entrypoint
-       [2] (webpack)/test/statsCases/scope-hoisting-multi/common.js + 1 modules 62 bytes {4} {3} [built]
+       [2] (webpack)/test/statsCases/scope-hoisting-multi/common.js + 1 modules 62 bytes {3} {4} [built]


This should not happen?

see: bd8c6cf

fix tests that was falsy - per default chunks are flagged as sorted in module
however this only holds true as they are initialized empty. Concatenated module however
has initial modules and therefore is not guaranteed to be ordered, the flags should therfor be false.
Using SortedSet fixes this as a sideeffect

Ah okey. 👍

It seem to be different again...

ha yea, it tries to use the sort method from Module but its no longer exposed...

meh, i'd love to just have a compareBy method on them :P maybe in another PR if thats ok :D

webpack-bot · 2017-06-19T12:44:55Z

@timse Thanks for your update.

I labeled the Pull Request so reviewers will review it again.

@sokra Please review the new changes.

sokra · 2017-06-19T13:17:21Z

lib/util/SortableSet.js

+		super(initialIterable);
+		this._sortFn = defaultSort;
+		this._lastActiveSortFn = null;
+		this._isSorted = false;


_isSorted is redundant to _lastActiveSortFn. _isSorted === !!_lastActiveSortFn.

=> _isSorted can be removed.

sokra · 2017-06-19T13:18:16Z

lib/util/SortableSet.js

+	/**
+	 * @returns {void}
+	 */
+	clear() {


clear can be removed, as an empty set is always sorted.

sokra · 2017-06-19T13:19:50Z

lib/util/SortableSet.js

+	 * @returns {void}
+	 */
+	sortWith(sortFn) {
+		if(this._isSorted && sortFn === this._lastActiveSortFn) {


We could skip sorting if this.size === 0. This avoids creating a new empty array below.

sokra · 2017-06-19T13:20:09Z

test/statsCases/scope-hoisting-multi/expected.txt

@@ -19,7 +19,7 @@ Child
       [0] (webpack)/test/statsCases/scope-hoisting-multi/common_lazy_shared.js 25 bytes {0} {1} {2} [built]
       [1] (webpack)/test/statsCases/scope-hoisting-multi/vendor.js 25 bytes {5} [built]
           ModuleConcatenation (inner): module is an entrypoint
-       [2] (webpack)/test/statsCases/scope-hoisting-multi/common.js + 1 modules 62 bytes {4} {3} [built]
+       [2] (webpack)/test/statsCases/scope-hoisting-multi/common.js + 1 modules 62 bytes {3} {4} [built]


Ah okey. 👍

- remove unnecessary _isSorted flag - remove clear-override as an empty set is "sorted" - early return on empty sets

webpack-bot · 2017-06-20T22:28:21Z

Thank you for your pull request! The most important CI builds succeeded, we’ll review the pull request soon.

sokra · 2017-06-21T20:50:51Z

Thanks

timse added 4 commits June 18, 2017 10:41

add SortableSet as a new collection type

0eaa847

use SortableSet in chunks

747efca

use SortableSet to keep "_modules" sorted

use SortableSet in modules

4e5ef0d

use SortableSet to keep "_chunks" sorted

webpack-bot added PR: unreviewed PR: CI-ok labels Jun 18, 2017

sokra requested changes Jun 18, 2017

View reviewed changes

webpack-bot added PR: reviewed-changes-requested and removed PR: unreviewed labels Jun 18, 2017

timse added 2 commits June 19, 2017 22:13

make sort function private

1a16a3e

optimize sortableSet to prevent unnecessary sorting

7a99930

webpack-bot added PR: review-outdated PR: CI-not-ok and removed PR: reviewed-changes-requested PR: CI-ok labels Jun 19, 2017

sokra requested changes Jun 19, 2017

View reviewed changes

webpack-bot added PR: reviewed-changes-requested PR: review-outdated and removed PR: review-outdated PR: reviewed-changes-requested labels Jun 19, 2017

timse added 4 commits June 21, 2017 08:12

allow to set chunks and use it in ConcatenatedModule

f7ffed8

clean up SortableSet

5f16dd8

- remove unnecessary _isSorted flag - remove clear-override as an empty set is "sorted" - early return on empty sets

add tests for sortableset

b2a4244

fix linting/formatting issues

8f3d65a

timse force-pushed the sortable-set branch from b52699b to 8f3d65a Compare June 20, 2017 22:12

webpack-bot added PR: CI-ok and removed PR: CI-not-ok labels Jun 20, 2017

sokra approved these changes Jun 21, 2017

View reviewed changes

webpack-bot added PR: reviewed-approved and removed PR: review-outdated labels Jun 21, 2017

sokra approved these changes Jun 21, 2017

View reviewed changes

sokra merged commit 25a904b into webpack:master Jun 21, 2017

renovate-tests mentioned this pull request Jul 7, 2017

Update dependency webpack to v3 renovate-tests/discover-package-files#13

Open

This was referenced Jul 7, 2017

⬆️ webpack -> ~3.1.0 homezen/hz-test-helpers#54

Merged

⬆️ webpack @ ~3.1.0 homezen/redux-variants#164

Merged

renovate bot mentioned this pull request Jul 7, 2017

Update dependency webpack to version 3.x algolia/react-element-to-jsx-string#105

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sortable set #5083

Sortable set #5083

timse commented Jun 18, 2017

sokra Jun 18, 2017

timse Jun 18, 2017

sokra Jun 18, 2017

timse Jun 18, 2017

sokra Jun 18, 2017

timse Jun 18, 2017

sokra Jun 19, 2017

sokra Jun 19, 2017

timse Jun 20, 2017

webpack-bot commented Jun 19, 2017

sokra Jun 19, 2017

sokra Jun 19, 2017

timse Jun 20, 2017

sokra Jun 19, 2017

timse Jun 20, 2017

sokra Jun 19, 2017

webpack-bot commented Jun 20, 2017

sokra commented Jun 21, 2017

Sortable set #5083

Sortable set #5083

Conversation

timse commented Jun 18, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

webpack-bot commented Jun 19, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

webpack-bot commented Jun 20, 2017

sokra commented Jun 21, 2017