Removing elements from a mutable red-black tree affects its immutable clones

[not-an-aardvark]

Using current master (https://github.com/frptools/collectable/commit/84d7bdb4475e823f97405da408514e6fbe6d5d0b):

const RBT = require('./packages/red-black-tree');

const mutableTree = RBT.emptyWithNumericKeys(true);

RBT.set(1, 'one', mutableTree);
RBT.set(2, 'two', mutableTree);
RBT.set(3,'three', mutableTree);
RBT.set(4, 'four', mutableTree);

const immutableClone = RBT.clone(mutableTree, false);

RBT.remove(1, mutableTree);

console.log([...RBT.keys(immutableClone)])

Expected output:

[1, 2, 3, 4]

Actual output:

[2]

I encountered this when I tried to use an immutable clone for stable iterators in https://github.com/frptools/collectable/issues/44#issuecomment-314350166. I think I'm using the new API correctly (freeze/thaw seem to have been removed), but let me know if I'm misunderstanding how it's supposed to work.

[axefrog]

Ah, sorry yeah the documentation doesn't exist yet so I admit there's a little trial and error you have to go through at the moment.

The gotcha in this case is that cloning from mutable to immutable is an unsafe operation. Safe cloning must always be performed from an immutable source. What you need to do is perform any mutations you care about, then commit (formerly "freeze") the changes. To perform further mutations, create a mutable clone thereof. The methods you want are modify() (and variants) and commit().

Take a look at the jsdoc comments for mutation.ts in frptools/core. The main points are:

• There is the concept of a mutation context. It has two parts; the mutability token, and and the ownership flag. Every persistent data structure has a mutation context that governs whether it behaves mutably or immutably, and helps it decide which of its internals can be safely modified without violating external immutability assumptions.
• The mutability token is a unary array with a boolean element. When a mutable context exists on a persistent structure, the mutability token is set to true. When the mutability token is set to false, any associated persistent structures are implicitly frozen as a result.
• A new mutable mutation context (usually created either by cloning an immutable object via the modify() method, or when creating a new, mutable, empty collection/structure), will have the ownership flag set to true.
• A subordinate context is a mutation context that contains a reference to a shared mutability token, but the ownership flag set to false. Mutable objects cannot be frozen via a subordinate context (or an object with which it is associated). Only a reference to an owning context (or the object to which it is attached) can be used to freeze a mutation context.
• By creating a mutable object, then either creating, or cloning as mutable, one or more other objects as subordinate to the original object (i.e. cloning them with the original object as their mutability argument), you can create an entire batch of mutations, and then freeze them all in O(1) time via the commit() function, which toggles the mutability token to the "frozen" position.
• An immutable context can never be made mutable, which is why the immutability guarantee is possible. The modify() function creates a clone of the top level object representing the data structure, and the operations such as set(), get(), etc., look at the mutation context attached to each internal node/object that the overall structure is comprised of, and use that as the basis for figuring out which of those internal structures can be mutated directly, or must be cloned as subordinates of the new mutation context.
• When calling modify() against an already-mutable object, a reference count is incremented rather than a clone being created. A subsequent call to commit() will then decrement the reference count rather than performing a final freeze on the mutation context. This allows a data structure to be mutated freely throughout a call stack without each nested call needing to concern itself with the initial mutability state of the operand. Instead, each can independently call modify() and commit() without worrying about inadvertently creating multiple clones of the original object. All that is required is that any call to modify() should eventually be paired with a call to commit(), assuming you don't just leave it mutable forever.

As I said, take a look at mutation.ts and let me know if you have any questions.

[not-an-aardvark]

I see, thanks for clarifying. Closing this issue since it's not a bug.