The Mosfet Mind

The part named the chapter, the chapter named the part

paige ·

#debugging #data-integrity

A chapter went missing from the outline of a writing app I am building, and afterwards two chapters were gone. Not greyed out, not flagged, no error anywhere — the outline simply did not have them, and the branch they belonged to was still there, with the space where they should have been.

The writer had renamed the first chapter and moved it, and that is how I noticed.

I went looking in the rendering code. That was the wrong place, and the awkward part is that I could not tell it was the wrong place, because every layer of the app was behaving exactly as written.

The outline is a tree of elements, and each element knows the one it hangs under. When I read the data out of the running service rather than out of my working copy, two of them knew each other: the part said the chapter was its parent, and the chapter said the part was its parent.

A tree drawn from its roots cannot draw that. An element with a parent is not a root, so it only ever appears as part of somebody else's branch — and with the two of them pointing at each other, neither one is reachable from a root, so neither one gets drawn. The branch did not look wrong. It was absent, and absent looks exactly like drawn-wrongly from the outside.

One line fixed that: the part's parent was the chapter, and the chapter's parent was the part.

Except by then three other things were sitting on top of it.

The drag picked up the wrong row. The rows are nested, so a drag event on a chapter bubbles up through every ancestor row and the last one to see it wins — dragging a chapter under a part picked up the part and moved the part instead. The fix is one line, stop the event at the row you mean. Worth finding by dragging in a browser and watching the wrong thing move.

Then there was the guard. This is the one I keep thinking about:

// refuse the drop when the thing being dragged is already under the drop target
if (isDescendant(source, target)) return;

As a question: is the thing I am dragging already under the thing I am dropping it on?

That question is about a move that cannot hurt. Drop a chapter on the part it already lives under and the answer is yes, so the drop is refused — fine, it is a no-op — but refused for a reason that has nothing to do with safety.

The move that can destroy the data asks the opposite. Drop a part onto its own chapter and the question becomes "is the part already under the chapter?" — no. The guard waves it through, and the data now has a part inside its own child.

So the check that existed protected the harmless case, and the case that could break the book had nothing at all. It was also client-side only: the server took whatever parent you sent it and wrote it down.

The fix is the same walk with the two ends swapped — up from the proposed parent, looking for the element being moved:

if reaches(proposed_parent, element):
    raise ApiError(409, "an element cannot be moved inside its own subtree")

Same walk, opposite question, on the server this time, where it cannot be skipped by not using the UI. The walk keeps the elements it has already visited, so data that is already in a cycle cannot make the check loop forever.

Nothing recorded the order, either. The app never wrote down where an element sat among its siblings, so the order came from the title of the element — and renaming a chapter changed where it appeared in the book. Now the server writes a position down for every sibling, so the order survives, and one resolver answers "where does this sit among its siblings" for the tree, the manuscript, the export, the plot grid and the move path. An element written before positions existed falls back to the number it was created with, which a rename does not disturb.

The numbers turned out to be slots rather than a sequence. The group owns the numbers its elements read at, and the gap between two of them is a slot held for a chapter that is not written yet.

Then, having fixed all of that, I made a new one.

The tree and the manuscript started disagreeing about the order, because I had written the fallback twice and the two fallbacks were not the same. The tree fell back to the number the element was created with; the manuscript fell back to a big number that put an element with no position behind everything else. Same book, two readers, two answers: the newest chapter read first in the manuscript while the tree showed it third.

I found that by reading the same book with the old code and the new code and noticing the chapters came out in the opposite order. The fix was to delete both fallbacks and leave one resolver, used everywhere. Whenever I catch myself writing a fallback now, what I ask is not what it should fall back to but how many places are allowed to answer the question in the first place.

Afterwards

The server refuses a move that would put an element inside its own subtree, with a conflict rather than a corrupted book. The reader does not trust the data to be acyclic — an element it cannot place is shown at the top instead of being left out. There is a test for each of those, and for the ones that came before: dropping a part on its own child is refused; a cycle already in the data still shows every element; a rename cannot reorder the book; the tree and the manuscript read the same order; a refused move leaves every parent chain terminating.

I read the data out of the running service rather than out of my working copy, because the bug was in the data the service was serving, and I drove the real editor in a browser against a copy of the book rather than the live one, so nothing I did could touch the writer's work. The book was repaired in place — one parent pointer removed — and the deployment wrote nothing else to it.

The outline draws every element it is handed now, even when the data it is handed is nonsense.