Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

An option without automatic packing #17

Open
RReverser opened this issue Oct 23, 2020 · 0 comments
Open

An option without automatic packing #17

RReverser opened this issue Oct 23, 2020 · 0 comments

Comments

@RReverser
Copy link

TL;DR: Would it be possible to add an option to tell .push() to only push items to the end, without using unused_indices?


In some scenarios, it might be useful to always .push to the end, without using the unused indices, and later .pack() manually.

In particular, this helps when you want to delete / reorder / insert a bunch of items, then check that there are no external references to the deleted items in a single pass, and only then pack what remains. Automatic packing makes such checks quite hard.

Let's take a simple example: we start with a list

[0] => A
[1] => B
[2] => C

and there are some external references, let's have just two for this primitive example:

ref1 => [1] (=> B)
ref2 => [2] (=> C)

Let's say we want to delete B from the list and immediately push D. In the current algorithm, this will result in the following structure:

[0] => A
[1] => D
[2] => C

now the external reference silently points to the wrong data:

ref1 => [1] (=> *D*)
ref2 => [2] (=> C)

Instead, we would want to be able to end up with the list like this:

[0] => A
[1] => (deleted)
[2] => C
[3] => D

then walk through references to check if there are any dead ones - in this case we'd find one:

ref1 => [1] (=> *(deleted)*)
ref2 => [2] (=> C)

And only when this check passes, then we want to .pack() the array and remap any external IDs:

[0] => A
[1] => D
[2] => C

This way, at any point of mutations we can be sure that there are no references that would silently start pointing to incorrect data because ID got reused.

This particularly helps with cyclical structures, where it's not possible to check if there are any dandling references until all the mutations are finished and you finally can do essentially mark-and-sweep via .pack().

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant