Using updateMany in adapter with custom sortComparer ignores several updates with same id

[karlsoderback]

When I use updateMany in an adapter with a custom sortComparer, I only see effects of the first update when sending several with the same id. See reproducer here.

[karlsoderback]

I also tried a more simple sortComparer: sortComparer: (a, b) => (a.id > b.id ? 1 : -1)
The same issue was experienced with that one as well. The only way I have managed to mitigate the behavior is by having no sortComparer at all.

[markerikson]

Yeah, I think I see what's happening here.

The update logic for processing updateMany is different between "sorted" and "unsorted".

Here's the logic for "sorted":

redux-toolkit/packages/toolkit/src/entities/sorted_state_adapter.ts

Lines 75 to 97 in 3b8d7a9

	function takeUpdatedModel(models: T[], update: Update<T>, state: R): boolean {
	if (!(update.id in state.entities)) {
	return false
	}
	const original = state.entities[update.id]
	const updated = Object.assign({}, original, update.changes)
	const newKey = selectIdValue(updated, selectId)
	delete state.entities[update.id]
	models.push(updated)
	return newKey !== update.id
	}
	function updateManyMutably(
	updates: ReadonlyArray<Update<T>>,
	state: R
	): void {
	const models: T[] = []
	updates.forEach((update) => takeUpdatedModel(models, update, state))

and here's the logic for "unsorted":

redux-toolkit/packages/toolkit/src/entities/unsorted_state_adapter.ts

Lines 125 to 151 in 3b8d7a9

	function updateManyMutably(
	updates: ReadonlyArray<Update<T>>,
	state: R
	): void {
	const newKeys: { [id: string]: EntityId } = {}
	const updatesPerEntity: { [id: string]: Update<T> } = {}
	updates.forEach((update) => {
	// Only apply updates to entities that currently exist
	if (update.id in state.entities) {
	// If there are multiple updates to one entity, merge them together
	updatesPerEntity[update.id] = {
	id: update.id,
	// Spreads ignore falsy values, so this works even if there isn't
	// an existing update already at this key
	changes: {
	...(updatesPerEntity[update.id]
	? updatesPerEntity[update.id].changes
	: null),
	...update.changes,
	},
	}
	}
	})
	updates = Object.values(updatesPerEntity)

The unsorted logic continues to merge together the results for each ID. But, for sorted items, the first time we see an update for a given ID we remove the item from state.entities. When the second update gets processed, the if (!(update.id in state.entities)) check fails and so we skip applying that update.

I'll be honest and say I don't know why the logic is actually organized like this in the first place :) I copy-pasted the structure from @ngrx/entity.

At a minimum, the sorted logic ought to do something similar to what the unsorted logic is doing, or maybe group all updates by ID first. It would be really nice if we could consolidate on a single implementation instead of having this split.

I'm afraid this is somewhat lower priority for me atm, but this is a real thing that ought to get fixed.

[jakeboone02]

@markerikson I'm going to try to address this by merging the sorted/unsorted logic into a single implementation. It doesn't initially appear to make sense to leave them separate.

[markerikson]

Yeah, tbh I don't know why the NgRx folks did it that way to begin with either :) Might want to double-check the early PRs that added the entity adapter code to NgRx in the first place and see if there's hints why they did that?

Oh, now that I write that... I'm pretty sure I remember reading either some GH comments or Twitter discussion where the reasoning was to avoid running sorting logic if it wasn't needed, because that can get expensive.

searching

aha, found it!

ngrx/platform#2333 (comment)

the perf characteristics of always copying both entities and ids up front

GC pauses for managing ids and entities in an immutable way becomes unbearably slow when performing large upserts or patches to the collections.

the completely separate code paths for sorted vs unsorted collections

The implementations have always differed just enough that they had to be separate. @ngrx/entity sorts a collection at time of modification rather than in a selector. I've always had the itch to take this a step further and swap the sorted collection's implementation to use a heap and then sort the heap in a selector.

and:

Oh, another thing about the sorted collection implementation being different: IIRC when I created @ngrx/entity array.sort() wasn't guaranteed to be a stable sort across browsers. Sorting the collection by hand let me guarantee resorting the collection was stable. This felt important to me from a UX perspective if you built a UI that rendered the collection as a list.

also related, this discussion on sorting: ngrx/platform#898

FWIW, I'm totally fine with rearranging / merging the logic in any way that A) keeps the existing tests working, and B) simplifies the implementation. (smaller bundle size would be nice!)

[markerikson]

This should actually be fixed now in #2464 and will be out in whatever the next patch or minor release is.