More options for inserting based on siteId

[trepidacious]

I was just looking at the case for inserting an identifier at the same position as the previous identifier, but with a greater site id:

      } else if (diff === 1 && siteID > prevSiteID) {
        return [[prevInt, siteID]];

This makes sense, but is there not also a similar case:

      } else if (diff === 1 && siteID < nextSiteID) {
        return [[nextInt, siteID]];

And a final case (which would actually have to come first in the conditional):

      } else if (diff === 0 && siteId > prevSiteId && siteID < nextSiteID) {
        return [[nextInt, siteID]]; // Or equivalently use prevInt

Do these all actually make sense? If the existing case works, I can't see why the new ones wouldn't.

Practically I don't know whether these will actually come up that often - in the original logoot paper I don't think any of these options are deliberately used on an individual site, but they could still happen from concurrency so I can't see any harm in using them except performance. Actually the algorithm in the original logoot paper doesn't seem to work because of an off by one error and a more important logical problem with generating the line positions (as far as I can tell!).

[trepidacious]

I was also working through the effect of this, and it's interesting that the implementation needs the site id to be > 0, so as not to conflict with the min and max positions used. I think it would be possible to permit arbitrary site ids by just enforcing that all identifiers other than the min and max positions' identifiers have a pos at least 1. This is another way of ensuring that the min identifier is less than or equal to all identifiers, so we can always generate a position before any other position. This is only slightly less efficient than requiring site id to be positive, but a lot less likely to go wrong as a result of someone not realising site id must be positive?

[jclem]

It's been over a year since I've looked into this code. I'll have to see if I can find time to look into this at some point. There was a brief period where I was investigating various text CRDTs for use in Canvas (now shut down), and at that time came to the conclusion that Logoot was a no-go for us, but I learned a lot from this making implementation.

On your first comment: I'm not sure if it really makes a difference. I believe that both versions (with your conditionals and without) are both correct. One just results in longer identifiers in some cases. I am not sure what the implications are, though, off the top of my head.

On your second comment: This is probably a good idea, but I wasn't really looking towards productionization, yet, when I originally wrote this. There is much more that would have to happen, and I don't think Logoot is suited to collaborative document editing, in the first place, for most use cases. It was really intended for editing in environments where users don't edit the same line at the same time, which isn't practical in my experience. No character-wise CRDT is, in my opinion. I think a string-aware CRDT (if there even is a good one) or good, old-fashioned operational transformation end up working better, in practice.

[trepidacious]

Ah that's interesting, I think I'm just re-treading the same path you followed a year ago... I'd like to support collaborative text editing as well, and Logoot seemed like a relatively simple and established way to do this. Looking at the implementation now makes me think it's not so simple (all the edge cases!), and I'm not sure I've found anyone who is actually actively using Logoot. On the other hand I do have a use case for just rearranging/editing lists where I think Logoot would be much better - it has much shorter sequences with much less editing than a collaborative string, so maybe that is still practical.

I'm guessing that your conclusion that Logoot isn't suited is from the overhead, or also from problems with intent of editing? As far as a string-aware CRDT goes, I guess Logoot could maybe be used on a word level, at least for English.