The DA in WebDAV literally means Distributed Authoring. This in, in particular, means we can have race conditions: when I load document X and you load document X and we both change it differently and then both want to save it, we have a problem. There is no way around, in the general case, that one version must win. A well known fact in computing.
In specific cases, the two changes can be automatically merged, but if you write
Here comes the last line of the document, it is —yada—while I write
Here comes the last line of the document, it is —bobo—then only one can be true. So what can be done:
We could say, last one wins. But this is particularly nasty to you as you cannot be notified that luck was not on your side.
Or we could say: first writer wins. This has the benefit that the system can tell me immediately, as I try to write my version, that I am late, that the document changed in the meantime and that some decision has to be made: your version, my version or I manually and consciously merge your and my version of the text. Sounds better.
How can the machinery tell that when I want to write my version of the text, it was changed by you in the meantime.
The safest way: I send both, the original and my changes, to the server. The server compares the original with the currently stored data and either saves the changes or lets me know that I am late. But it requires to always send old and new text to the server as well as comparing the full documents. Somewhat inefficient.
A less bandwidth-gobbling way is to associate either an incremental version or a checksum with each change of the document. As we read the document in order to change it, we also get the checksum along. As you write the changed document, you also send back the checksum, the server compares it with the current checksum and as they are the same, the document is written and a new checksum is computed. As I come along with my changes later, my checksum does not match and the server can notify me to take manual action to make the decision.
Lets ponder what the server should send back as a response to a successful change write. The server is responsible for computing the checksum with whatever algorithm is implemented. The client, my browser or app, should not try to mimic it. When the client sends a successful change, the server alone knows the new checksum. But before the client can continue making changes, it needs to know the checksum to send along with the next write of further changes.
It seems to be obvious that the first suggestion, to send back the updated checksum in response to a successful change write, is easy and efficient.
Ooooompf, except this is not how its done in WebDAV, at least not in the Apache
HTTP Server. The reason seems to be in
section 9.3.4
of RFC 9110 which allows that the content of the change request may be
processed before saved. That would mean the client's data is not the exact same
of what the server stored. Although it also implicitly says that sending the
checksum (ETag is the official name) back is OK if the server stores
exactly what was send. Sadly, Apache's mod_dav takes the easy route
and never sends ETags back for PUT requests. Tell me, if I am
missing a configuration that fixes this.
So, I have to resolve to strategy 3 above. Not the end of the world, but for my glorified view of the HTTP world when I started to read about ETag and thought, yeah, of course, this is what I need.
The need for what is called Fractional Indexing arises if a list of items can be arbitrarily re-ordered and we want an item to have a key representing its position in the order.
The canonical example is a todo-list where a user may change the order (priority) of items at whim.
We start with giving each item a number as a key and use the following algorithm for a new or moved item:
Step two has a problem which cannot be avoided: each step moves the least significant bit to the right by one. As an example, consider repeatedly inserting between the first and second element of a list which starts with the keys 5 and 7. We get for the first two keys:
```
5 7 -> 5 6 -> 5 5+1/2 -> 5 5+1/4 -> 5 5+1/8 ...
``` The $1/{2^N}$ is coded by a 1-bit which moves ever further to the right.
If the insert position degenerates to be always the same for some unforseeable reason, you need n bits of precision after n insertions. Double values provided by most programming languages have a 52 bit mantissa, which means you get rounding errors the latest after 52 insertions. Which is not a lot.
Using infinite precision decimals does not make it much better because the key requires at least n/8 bytes after n insertions. After 1024 insertions which, by bad luck, happen on the same position, the key has a length of at least 128 bytes.
There is no remedy if the general case is considered. If users work with a list where the creation of each single item is a manual step, it is hard to imagine they have 1000 insertions at the same place. Yet if it is a todo-list maintained over a few years, the 52 bit mantissa of a double value may actually become a problem.
And it is a problem of the ugly kind. The program may actually work perfectly for months, even years. And when it starts to fail, the failure is subtle as items may or may not be sorted in the wrong place, depending on the "random" order how the comparison of identical keys spits them out.
I spend three days from noticing that I want a manually maintained sort key which does not require re-numbering whenever an item gets inserted between two others, over learning that it is called fractional indexing, reading about it, implementing it myself for the general case, to seeing live from test output how fast degenerate insertion gets bad to writing this piece, finally accepting defeat.
The original reason I wanted to avoid re-numbering is that it causes a brief but noticable data-reload in the app I am writing.
How to chose N? Using N=1 means any insert operation has to renumber all following items, the case I wanted to avoid in the first place. The larger the N gets, the longer it takes between re-numbering with pros and cons.
Hmmm?
The figma blog somewhat casually brushes over the index length problem saying:
The first drawback (index length) isn’t a concern for us since we don’t need to order huge numbers of elements. The number of reordering operations is bounded by user activity in practice, and normal usage patterns never generate prohibitively-large index lengths.While I tend to agree, this somewhat reminds me of the year 2000 problem or the year 2038 problem. In my case, the app shall operate on the same data structure potentially for years, and while arbitrary re-ordering is expected, new items tend to be added to the front, which will certainly grow the keys near the front of the list. Adding only a handful of items per day to the front over a year makes already 1825 insertions or, worst case over 200 bytes for the key.
Given modern hardware, these will be handled without problems for a long some time, until it suddenly wrecks somewhere. For my little app, used by only few people, this will not be the end of the world, but it is the general attitude towards good software which is not mine. I wish there were an efficient solution where I would not need to rely on the specific circumstances of the typical use of the app for it not to crash.
Recently I said that checked exceptions or not really exceptional. Here is a good example about the trade-offs.
Consider building a directed acyclic graph
(DAG), a
dependency graph for example. The Node class has a
method to add a child:
class Node {
public void addChild(Node child) { ... }
}
We must make sure that the graph stays acyclic. So the child node may not be an
ancestor of the current node. We add a check to addChild.
class Node {
public void addChild(Node child) {
if (child.hasDescendant(this)) {
/* NOT SUITABLE */
}
}
public boolean hasDescendant(Node other) { ... }
}
What shall we do at NOT SUITABLE? We have three options:
ISPARENT, to tell the caller that the
operation is not possible.The arguments:
An unchecked exception indicates a programming error, and there are two different situations:
If addChild() is an API method, used as part of a user
action, it is normal business to get a node which can not be made a
child.
We could require the caller to first call hasDescendant()
explicitly, which again would turn the NOT SUITABLE part into
a programming error, but addChild() has to call it again to
be sure. How silly. As is often the case, first verifying that an
operation is possible is the same effort as just running it, possibly
being told it cannot be done.
So assume we are in the API situation, not in the algorithm-guarantees-non-fuckup situation.
Throwing a checked exception would be a strong hint that the operation may not succeed on circumstances. Yet, as I argued in the article linked above: this is not exceptional. It is normal business?
Which leads us to the special-value return. I started to call those an Explainer. It encodes why the operation was not possible, with as much detail as needed. Examples:
Map.get(key) a null return is a good
Explainer with as enough detail, telling us "no value for 'key'". More is
not needed.
OK, NOOP, ISPARENT for the
cases "child was added", "child was already added" and "given node is an
ancestor so not a suitable child".Did you note how I tried above to not say that an operation "failed". Not easy after being brain-washed for 40 years.😀
In languages with union types, like Python and TypeScript, it is slightly
easier to return either a result or an Explainer. In Java it
would be some Either<Stuff, Explainer> that needs to be
defined.
Is there a case for checked exceptions still? The longer I ponder it the thinner the case gets. It seems nice to ignore the Explainer (exception) and let it bubble up. Lets compare:
public Either<Result, Explainer> doStuff() {
Either<String, Explainer> s = compute(...);
if (s.isRight()) {
return Either.ofRight(s.right());
}
...
}
with
public Result doStuff() throws Explainer {
String s = compute(...);
...
}
The latter is obviously more concise in Java, though the main eye-strainer
for me is more the new Either() necessary to match the result
type. In a language with union types, like TypeScript, this is just:
public doStuff(): Result | Explainer {
const s = compute(...);
if (s instanceof Explainer) {
return s;
}
... move on with s
}
The advantage of exception forwarding amounts to the avoidance of a mere if/return combo. Yes, you say, but what if there are four for five of those in a row? Then auto-bubbling looks much better — hmm, until you have to debug at what line exactly in the 😠 code the exception is raised.
What if we made explicit forwarding simpler. If we have union types, like in Python and TypeScript, imagine a syntax like:
const text: string = compute(...) or return;
The compiler would unpack this into
const text: string | Explainer = compute(...);
if (text instanceof Explainer) {
return text;
}
Easy forwarding, Explainer need not come along as exceptions and it is obvious were the code did the short turn, eventually. I am dreaming.