Some questions about the design of the cursor

[CMCDragonkai]

I'm working on an immutable data structure that needs a cursor concept as well.

One of the challenges that I'm facing is similar to what you describe in the README.

I need a "stable iterator", such that the cursor as its iterating over the data structure, that iteration would be as if no modifications were made to the data structure. It's a consistent read essentially.

I came up with a similar solution, where every cursor maintains the root pointer to a "snapshot" of the immutable data structure (it's a variation of a B+tree designed to represent hierarchies).

However one of the issues, is now what do you do when you apply a modification with the cursor. What does the modification function return?

I reasoned it would make sense that to ensure immutability, that this modification function should return a new derived cursor (that now keeps a reference to the new snapshot of the tree).

So here's some pseudo code:

c1 = getCursor(immutableDatastructure);
// iterating as usual
c1.next()
c1.next()
c2 = c1.modifyDataStructure(...)
// now c2 and c1 have references to different data structures (but are doing structure sharing)
c1.next() // this is still iterating over the old structure
c2.next() // this is now reading in possible modifications (that could have the new changes applied)

Now the problem is that if we run multiple modifications over the c1 cursor, each one is creating a new data structure, and also a new derived cursor. There's nothing serialising the modifications into 1 global data structure (like an MVCC database might).

How then, does your cursor serialise changes back into the original data structure without performing a sort of "tree" merge?

I realise that this may involve implementing a sort of MVCC transactional control. Because the point is that if I pass this cursor into 2 async functions, they may both perform modifications that can conflict, for example, if the first async function inserts a new child node underneath another node. But the other async function deletes that node that the child node would be inserted underneath.

---

Also my immutability strategy is implemented via path-copying (similar to this: https://en.wikipedia.org/wiki/Persistent_data_structure#Trees)

[jameshopkins]

Hey! Super unsure how I missed being notified of this issue! Will respond very soon!