Exporse oppsite of .getElemId(index)

[Gozala]

As per suggestion in #193

The Text class has a .getElemId(index) method that looks up the element ID for a particular index; the translation in the opposite direction doesn't seem to be exposed in the API at the moment, but that would be easy to add.

I attempted to add .getElemIndex(id) method to Text.prototype but I'm afraid I failed to figure out how to do it. contex.js does not seem to have anything relevant as far as I can tell.

I would love to help address this but I'd need some mentoring to get it done.

[ept]

Oh crap. I had thought it would be easy, but I misremembered some of the details.

Well, there is an easy method, which is to do a linear scan over the this.elems array in Text, and to find the index of the element whose .elemId property matches. But that's O(n) slow.

What I had in mind was to use the indexOf method of the SkipList class in the backend, which does the same in O(log n) time. But since the Text object lives in the frontend, and the frontend is not supposed to directly access data structures in the backend (they are supposed to communicate only by message-passing), that method can't be used directly.

It's annoying that the frontend/backend split is making this difficult. Perhaps we need to put a better data structure like the skiplist in the frontend, but I had been trying to keep the frontend as lightweight as possible, otherwise what's the point of splitting the two?

[Gozala]

Oh crap. I had thought it would be easy, but I misremembered some of the details.

Well, there is an easy method, which is to do a linear scan over the this.elems array in Text, and to find the index of the element whose .elemId property matches. But that's O(n) slow.

That’s actually not going to work either, because deleted characters are no longer in there

[ept]

deleted characters are no longer in there

Oh yes, you're right. I think the backend skiplist retains deleted element IDs and calculates indexes correctly (deleted elements can be looked up by element ID, but don't count towards indexes), but I'm still not sure how to give the frontend access to that information.

[Gozala]

I'm pretty lost in the code base, can't seem to figure out where do frontend / backend even communicate.

@ept would you mind providing a bit more insights on how I can go about this ? At this point I'm open to some dirty hacks so I can make more progress on my editor prototype & learn more about how things work internally in the process.

[ept]

I just did some experimentation, and realised that I had mis-remembered: in fact, the skip list does not keep track of deleted elements either. But the backend opset combined with the skip list has enough information to convert an element ID into an index, handling deleted elements.

Here's a very dirty hack to get you started:

let doc = Automerge.from({text: new Automerge.Text('hello')})
let backend = Automerge.Frontend.getBackendState(doc)
let elemIds = backend.getIn(['opSet', 'byObject', Automerge.getObjectId(doc.text), '_elemIds'])
elemIds.keyOf(0) // '404582db-07e8-40ce-b782-8ece5eca337a:1'
elemIds.indexOf(elemIds.keyOf(3)) // 3

That elemIds object is an instance of the SkipList class, and it can convert between element IDs and indexes for element IDs that exist. For deleted elements, .indexOf() returns -1.

In order to find the index of a deleted element, we search for the closest predecessor element that exists, and look up the index of that. The algorithm for this is at op_set.js:159–167. Hope you can get it working; please let me know if you get stuck.

[ept]

Closing this as there's nothing further to be done for now; please re-open in case of problems.