name</th>	license</th>	who is behind it</th>	code review</th>	is it objectively ugly</th>	notes</th></tr> </thead>
Centrally hosted (with self-hosting as an option)</th></tr>
Codeberg</a>/Forgejo</a></td>	GPL</td>	nonprofit based in Germany</td>	branch-based</td>	no</td>	FOSS or noncommercial projects only; fork of gitea</td></tr>
SourceHut</a></td>	AGPL</td>	indie for-profit, not VC funded</td>	git send-email</td>	ugly (in a good way)</td>	costs $4–12/month, financial aid available</td></tr>
Gitea</a></td>	MIT</td>	small startup, VC backed</td>	branch-based</td>	ugly (some parts)</td>	weird vibes, and the free cloud hosting seems sort of like a demo instance; fork of Gogs</td></tr>
GitLab CE</a></td>	MIT</td>	publicly traded company</td>	branch-based with stacking</td>	just ugly</td>	limited features for free accounts</td></tr>
Decentralized/federated</th></tr>
Tangled</a></td>	MIT</td>	small startup, $300k+ in VC funding</td>	patch-based with stacking</td>	no</td>	no private repos, built on ATProtocol</td></tr>
Radicle</a></td>	MIT+Apache</td>	some ethereum thing, $12M+ in VC funding</td>	patch-based</td>	no</td>	private repos must be self-hosted</td></tr>
Self-hosted only</th></tr>
j3</a></td>	GPL</td>	i wrote it myself last week</td>	no code review</td>	i like to think not</td>	barebones read-only web ui</td></tr>
Gerrit</a></td>	Apache</td>	Google</td>	patch-based with stacking</td>	ugly</td>	code hosting/review only; no issues, etc</td></tr>
Gogs</a></td>	MIT</td>	single maintainer</td>	branch-based</td>	no</td>	</td></tr> </tbody></table> </div> My personal take on these options: since these days my projects mostly don't have external contributors, I've chosen to move them to j3</a>, a small local binary I wrote in Rust that lets you use an s3 bucket as a Git remote, and automatically pushes a read-only web UI to the bucket's `index.html</code>. If I had a startup that needed private code hosting, I would probably set up a Gerrit instance. If I was working on an open source project that wanted to make it easy for people in the open-source community to contribute, I would probably choose Codeberg, assuming I was not tempted by Tangled's code review workflow.</p>` `What is "patch-based" code review?</strong></p>`If you're familiar with GitHub's pull request workflow, you've done branch</em>-based merges before. You prepare a branch with your changes, and then submit a pull request asking to merge your branch into main</code>. If somebody gives you feedback, you push additional commits on top of your base commit. In contrast, with the patch</em>-based merge workflow originally popularized by Gerrit, you amend the existing commit and push it — something like git commit --amend && git push --force</code>. If you try this in GitHub, this would make the original commit you pushed disappear, but in patch-based review tools, your reviewers will instead see a diff from the original commit to the new one. In general, I'm trying to move towards patch-based workflows, since they work better with jiujutsu</a>. "Stacking" here means it's easy to submit multiple pull requests for simultaneous code review, where each pull request builds upon the changes from the prior one in a chain. On GitHub, this is very difficult!</p> </blockquote> Appendix B: Migration bash scripts</h2> To do the migration, I used the gh</code> GitHub CLI (brew install gh && gh auth login</code> on mac) extensively. To start, I cloned all my repos into three folders: migrate</code> holds non-fork public repos, archive</code> holds public forks, and private</code> holds all private repos. The plan is to migrate public repos to a publicly visible host, migrate private repos to somewhere else, and archive most forks in-place on GitHub after adding a notice to the readme.</p> mkdir</span> migrate archive private </span>(</span>cd</span> migrate </span>&& </span> </span>gh</span> repo list</span> --visibility</span> public</span> --source --json</span> sshUrl</span> --limit</span> 10000</span> --jq </span>'.[].sshUrl' </span>\| </span> </span>xargs</span> -I </span>{} git clone {}) </span>(</span>cd</span> archive </span>&& </span> </span>gh</span> repo list</span> --visibility</span> public</span> --fork --json</span> sshUrl</span> --limit</span> 10000</span> --jq </span>'.[].sshUrl' </span>\| </span> </span>xargs</span> -I </span>{} git clone {}) </span>(</span>cd</span> private </span>&& </span> </span>gh</span> repo list</span> --visibility</span> private</span> --json</span> sshUrl</span> --limit</span> 10000</span> --jq </span>'.[].sshUrl' </span>\| </span> </span>xargs</span> -I </span>{} git clone {}) </span></code></pre> At this point, I sorted through the list of repos, moving any that needed individual attention out of these three folders. I also skimmed through the archive</code> folder to see if there were any forks that deserved to be moved to migrate</code> instead of just getting archived. This script prints which repos have external collaborators, which was useful here:</p> gh</span> repo list</span> --visibility</span> public</span> --json</span> nameWithOwner</span> --limit</span> 10000</span> --jq </span>'.[].nameWithOwner' </span>\| </span> </span>xargs</span> -I </span>{} gh api </span>"repos/{}/collaborators"</span> --jq </span>'if length > 1 then "{}: \([.[].login] \| join(", "))" else empty end' </span></code></pre> Then, for every repo to migrate, I pushed all branches and tags to the new site. This script worked for my j3</a> remote, where pushing to a new remote implicitly creates a repo, but if you're uploading to codeberg or similar you'll need to change neworigin's url, and probably add a command to actually create the repo.</p> pushd</span> migrate </span>for</span> dir </span>in </span>$(</span>ls</span>)</span>; </span>do </span> </span>pushd </span>$dir </span> </span>git</span> remote add neworigin j3://$ID_KEY:$ID_SECRET@$BUCKET_REMOTE/code/$dir </span> </span> </span># per https://stackoverflow.com/a/59745167 </span> </span>git</span> symbolic-ref</span> --delete</span> refs/remotes/origin/HEAD </span> </span>git</span> push neworigin</span> --tags </span>"refs/remotes/origin/:refs/heads/" </span> </span> </span>popd </span>done </span>popd </span></code></pre> Finally, I replaced the repos on GitHub with a notice. I created a new migration-notice</code> orphan branch in the hope that this reduces the risk of downstream problems. I ran a similar script on the archive</code> directory; I decided to leave existing branches in-place there, since I wasn't migrating them.</p> pushd</span> migrate </span>for</span> dir </span>in </span>$(</span>ls</span>)</span>; </span>do </span> </span>pushd </span>$dir </span> </span># mark as unarchived if its archived rn, so we can add the notice </span> </span>gh</span> repo unarchive</span> --yes </span> </span>git</span> switch</span> --orphan</span> migration-notice </span> </span>cat </span>></span> readme.md </span><< </span>EOF </span>I have chosen to migrate my projects off of GitHub until Microsoft terminates its contracts with ICE and </span>the IDF. A [read-only archive](https://code.lord.io/$</span>dir</span>/) of this repo is still available. </span> </span>You can read more about my decision to leave on [my blog](https://lord.io/leaving-github/). </span>EOF </span> </span>git</span> add readme.md </span> </span>git</span> commit</span> -m </span>"add migration readme" </span> </span>git</span> push origin migration-notice </span> </span>gh</span> repo edit</span> --default-branch</span> migration-notice </span> </span> </span># delete branches that aren't migration-notice </span> </span>git</span> branch</span> -r </span>\| </span>grep </span>' origin/' </span>\| </span>grep</span> -v </span>'migration-notice$' </span>\| </span>grep</span> -v</span> HEAD </span>\| </span>cut</span> -d</span>/</span> -f2- </span>\| </span>xargs</span> -I </span>{} git push origin :heads/{} </span> </span> </span># mark the repo as archived </span> </span>gh</span> repo archive</span> --yes </span> </span>popd </span>done </span>popd </span></code></pre> Appendix C: GitHub stars and network effects</h2> If you want people to discover your personal projects, you might say that GitHub stars, forks, and followers are a great way to enable this. While this is an interesting question, and I'm sure some people find these tools valuable, my personal experience has been that few people look at their GitHub feed, and this was before the Copilot prompt box pushed it further down the homepage. I've also heard it got diluted by LLM-generated bug reports, but honestly, I don't look at it any more.</p> To show one data point using star counts as a proxy for attention, I had a little over 700 followers in 2020, so while I wasn't one of the most followed users on GitHub, I still had more followers than the vast majority of GitHub users. Throughout 2020, I worked publicly on a Rust side project called Anchors, which by October had accrued a grand total of 4 stars. On November 9th, I published How to Recalculate a Spreadsheet</a>, a tedious and technical blog post which discussed Anchors starting about 2000 words in. By the next day, Anchors jumped to 19 stars, and then (despite essentially zero code changes to the Anchors project itself) slowly climbed up to ~130 stars by late 2023. Clearly the blog post was the catalyst for these stars, and without it, Anchors would still have single digit stars today. That said, I can't prove to you that GitHub's feed didn't multiply</em> the attention the repo got from the blog post. But at an average rate of 1 star every 10 days, and given the minimal stars the project had prior to the blog post, I guess it's hard for me to imagine GitHub's feed played a major role.</p> Assuming it's even your goal for your project to get discovered by others (for most of my projects it is not!) I think your side project will likely reach orders of magnitude more people on Bluesky, Twitter, or your personal blog than they will via GitHub. GitHub stars are a good sign of social proof, but I would argue they don't serve this role substantially better than stars on Codeberg.</p> Appendix D: Further reading</h2> I've already mentioned Zig's</a> and Leiningen's</a> posts, but if you want to read what individual people have said about leaving GitHub, here is what I could find:</p> Dave Gauer</a> (2023)</li> David Eisinger</a> (2024)</li> James Brind</a> (2022)</li> Kord Extensions</a> (2025)</li> Janik von Rotz</a> (2025)</li> Logan Connolly</a> (2023)</li> Macoy Madson</a> (2022)</li> Nicole Tietz-Sokolskaya</a> (2022)</li> Nils Norman Haukås</a> (2024)</li> Sam Thursfield</a> (2025)</li> Simon Tatham</a> (2025)</li> Tom Szilagyi</a> (2024)</li> </ul> Appendix E: Richard Stallman, "A Free Digital Society" (New York, 2014)</h2> </p> How to Recalculate a Spreadsheet 2020-11-09T00:00:00+00:00 Let's say I'm ordering burritos for my two friends while they quarantine in Jersey City, and want to calculate the total price of my order:</p> </picture></div> It's a little confusing to follow the flow of data in a spreadsheet when it's written like that, so I hope you don't mind this equivalent diagram that represents it as a graph:</p> </picture></p> We're rounding the cost of an El Farolito super vegi burrito to $8, so assuming the per-burrito delivery toll remains at just $2 per burrito, it looks like the total for our two burritos will be $20.</p> Oh no, I completely forgot! One of my friends loves to wolf down multiple burritos at a time, so I actually want to place an order for three burritos. If I update Num Burritos</code>, a naïve spreadsheet engine might recompute the entire document, recalculating first the cells with no inputs, and then recalculating any cell whose inputs are ready until we've finished every cell. In this case, we'd first calculate Burrito Price</code> and Num Burritos</code>, then Burrito Price w Ship</code>, and then a new final Total</code> of $30.</p> </picture></p> This simple strategy of recalculating the whole document may sound wasteful, but it's actually already better</em> than VisiCalc, the first spreadsheet software ever made, and the first so-called "killer app", responsible for popularizing the Apple II. VisiCalc would repeatedly recalculate cells from left-to-right and top-to-bottom, sweeping over them again and again until none of them changed. Despite this "interesting" algorithm, VisiCalc remained the dominant spreadsheet software for four years. Its reign ended in 1983, when Lotus 1-2-3 swept the market with "natural-order recalculation", as described by Tracy Robnett Licklider in Byte Magazine</a>:</p> Lotus 1-2-3 exploited natural-order recalculation, although it also supported VisiCalc’s row- and column-order modes. Natural-order recalculation maintained a cell dependency list and recalculated a cell before recalculating cells that depended on it.</p> </blockquote> Lotus 1-2-3 implemented the "recalculate everything" strategy we've shown above, and for the first decade of spreadsheets, that was as good as it got. Yes, we recalculate every cell in the document, but at least we only recalculate every cell once.</p> but what about "burrito price w ship"</h2> Great point, header 2. In my three burrito example there's no reason to recompute Burrito Price w Ship</code>, because changing the number of burritos we order can't possibly influence the per-burrito price. In 1989, one of Lotus' competitors realized this, and created SuperCalc5, presumably naming it after the theory of super burritos at the core of this algorithm. SuperCalc5 recalculated "only cells dependent on changed cells", which would make updating the burrito count look more like this:</p> </picture></p> By only updating a cell when one of its inputs changes, we can avoid recalculating Burrito Price w Ship</code>. In this case, it saves just a single addition, but on larger spreadsheets it can save quite a bit of time! Unfortunately, we now have another problem. Let's say my friends now want meat burritos, which cost a dollar more, and simultaneously El Farolito adds a $2 fee paid per-order, regardless of how many burritos you order. Before any formula outputs are recalculated, our graph might look like this:</p> </picture></p> Since there are two updated cells here, we have a problem. Should we recalculate Burrito Price</code> first, or Total</code>? Ideally, we first calculate Burrito Price</code>, notice that its output has changed, then recalculate Burrito Price w Ship</code>, and finally recalculate Total</code>. However, if we instead recalculate Total</code> first, we'll have to recalculate it a second time once the new $9 burrito price propagates down. If we don't calculate cells in the right order, this algorithm isn't better than recalculating the whole document. In some cases, it's as slow as VisiCalc!</p> Clearly, it's important for us to figure out the right order to update our cells. Broadly, there are two solutions to this problem: dirty marking and topological sorting.</p> This first solution involves marking all cells downstream from an edit as dirty. For instance, when we update Burrito Price</code>, we would mark the downstream cells Burrito Price w Ship</code> and Total</code> as dirty, even before doing any recalculations:</p> </picture></p> Then, in a loop, we find a dirty cell that has no dirty inputs, and recalculate it. When there are no dirty cells left, we're done! This solves our ordering problem. There's one downside though — if a cell is recalculated and we find its new output to be the same as its previous output, we'll still recalculate downstream cells! A little bit of extra logic can avoid actually running the formula trouble in this case, but we unfortunately still waste time marking and unmarking a lot of cells as dirty.</p> The second solution is topological sorting. If a cell has no inputs, we mark its height as 0. If a cell has inputs, we mark its height as the maximum of the heights of its inputs, plus one. This guarantees all cells have a greater height than any of their inputs, so we just keep track of all cells with a changed input, always choosing the cell with the lowest height to recalculate first:</p> </picture></p> In our double-update example, Burrito Price</code> and Total</code> would be initially added to the recalculation heap. Burrito Price</code> has lesser height, and would be recalculated first. Since its output changes, we then would add Burrito Price w Ship</code> to the recalculation heap, and since it too has less height than Total</code>, it would be recalculated before we finally recalculate Total</code>.</p> This has a big advantage over the first solution: no cell is ever marked dirty unless one of its inputs actually change. However, it requires we keep all cells pending recalculation in sorted order. If we use a heap, this results in an O(n log n)</code> slowdown, so in the worst case, asymptotically slower than Lotus 1-2-3's strategy of recalculating everything.</p> Modern-day Excel uses a combination of dirty marking and topological sorting</a>, which you can read more about in their docs.</p> demand-driven complications</h2> We've now more or less reached the algorithms used in modern-day spreadsheet recalculation. Unfortunately, I suspect there is basically no business case to be made for ever improving it further. The few people with the problem "my Excel spreadsheet is too slow" have already written enough Excel formulas that migration to any other platform is impossible. Fortunately, I have no understanding of business, and so we're going to look at further improvements anyway.</p> Beyond caching, one of the cool aspects of a spreadsheet-style computation graph is we can only calculate the cells that we're interested in. This is sometimes called lazy computation, or demand-driven computation. As a more concrete example, here's a slightly expanded burrito spreadsheet graph. This example is the same as before, but we've added what is best described as "salsa calculations". Each burrito contains 40 grams of salsa, and we perform a quick multiplication to know how much salsa is in our entire order. In this case, since our order has three burritos, there's a total of 120 grams of salsa in our entire order.</p> </picture></p> Of course, astute readers will have spotted the problem here already: knowing the total weight of salsa in an order is a pretty useless measurement. Who cares that it's 120 grams? What am I supposed to do with this information?? Unfortunately, a regular spreadsheet would waste cycles calculating Salsa In Order</code>, even if we don't want it recalculated most of the time.</p> This is where demand-driven recalculation can help. If we could somehow specify that we're only interested in the output of Total</code>, we could only recompute that cell and its dependencies, and skip touching Salsa In Order</code> and Salsa Per Burrito</code>. Let's call Total</code> an observed</em> cell, since we're trying to look at its output. We can also call both Total</code> and its three dependencies necessary</em> cells, since they're necessary to compute some observed cell. Salsa In Order</code> and Salsa Per Burrito</code> would be aptly described as unnecessary</em>.</p> Some folks on the Rust team created the Salsa</a> framework to solve this problem, clearly naming it after the unnecessary salsa calculations their computers were wasting cycles on. Salsa is really cool, and I'm sure they can explain</a> how it works better than I can. Very roughly, they use revision numbers to track whether a cell needs recalculation. Any mutation to a formula or input increments the global revision number, and every cell tracks two revisions: verified_at</code> to track the revision its output was last brought up-to-date, and changed_at</code> to track the revision its output last actually changed.</p> </picture></p> When the user indicates they'd like a fresh value for Total</code>, we'd first recursively recalculate any cell necessary to Total</code>, skipping cells if their last_updated</code> revision is equal to the global revision. Once the dependencies of Total</code> are up-to-date, we only rerun the actual formula in Total</code> if either Burrito Price w Ship</code> or Num Burrito</code> have a changed_at</code> revision greater than the verified_at</code> revision of Total</code>. This is great for Salsa's purposes in the rust-analyzer, where simplicity is important and each cell takes a significant amount of time to compute. However, we can see the disadvantages in our burrito graph above — if Salsa Per Burrito</code> constantly changes, our global revision number will frequently tick up. This will make each observation of Total</code> walk the three cells necessary to it, even though none of those cells have actually changed. No formulas will be recalculated, but if the graph is large, repeatedly walking all of a cell's dependencies could get expensive.</p> faster demand-driven solutions</h2> Instead of inventing new algorithms for demand-driven spreadsheets, what if we instead draw from the two classical spreadsheet algorithms mentioned earlier: dirty marking and topological sorting? As you might imagine, a demand-driven model complicates both of these, but both are still viable.</p> Let's first look at dirty marking. As before, when we change a cell's formula, we mark all downstream cells as dirty. So if we update Salsa Per Burrito</code>, it would look something like this:</p> </picture></p> However, instead of immediately recomputing all</em> cells that are dirty, we wait for the user to observe a cell. Then we run Salsa's algorithm on the observed cell, but instead of reverifying dependencies with outdated verified_at</code> revision numbers, we instead only reverify cells marked as dirty. This is the technique used by Adapton</a>. You'll note that when we observe Total</code>, we'll find it isn't dirty, and so we can skip the graph walk that Salsa would have performed!</p> If we instead decide to observe Salsa In Order</code>, we'll find it is</em> marked as dirty, and so we'll reverify and recompute both Salsa Per Burrito</code> and Salsa In Order</code>. Even here, there are benefits over using just revision numbers, since we'll be able to skip a recursive walk on the still-clean Num Burritos</code> cell.</p> Demand-driven dirty marking performs fantastically when the set of cells we're trying to observe changes frequently. Unfortunately, this has the same downsides as the dirty marking algorithm from before. If a cell with many downstream cells changes, we may waste a lot of time marking and unmarking cells as dirty, even if their inputs won't actually have changed when we go to recalculate them. In the worst case, each changes causes us to mark the entire graph as dirty, which would give us the same ~order of magnitude performance as Salsa's algorithm.</p> Moving on from dirty marking, we can also adapt topological sorting for demand-driven computations. This is the technique used by Jane Street's Incremental</a> library, and requires major tricks</a> to get right. Before we added demand-driven computations, our topological sorting algorithm used a heap to determine which cell would be recomputed next. But now, we only want to recompute cells that are necessary</em>. How? We don't want to walk the entire tree from our observed cells like Adapton, since a complete tree walk defeats the entire purpose of topological sorting, and would give us performance characteristics similar to Adapton.</p> Instead, Incremental maintains a set of cells that the user has marked observed</em>, as well as the set of cells that are necessary</em> to any observed cell. Whenever a cell is marked observed or unobserved, Incremental walks that cell's dependencies to make sure the necessary marks are applied correctly. Then, we only add cells to the recalculation heap if they're marked necessary. In our burrito graph, if only Total</code> is part of the observed set, changing Salsa in Order</code> would not result in any walking of the graph, since only necessary cells are recomputed:</p> </picture></p> This solves our problem without eagerly walking the graph to mark cells as dirty! We still have to remember that Salsa per Burrito</code> is dirty, since if it later becomes necessary, we will need to recompute it. But unlike Adapton's algorithm, we don't need to push this single dirty mark down the entire graph.</p> anchors, a hybrid solution</h2> Both Adapton and Incremental walk the graph, even when not recomputing cells. Incremental walks the graph upstream when the set of observed cells changes, and Adapton walks the graph downstream when a formula changes. With these small graphs, it may not be immediately apparent that this graph walking is expensive. However, if your graph is large and your cells are relatively cheap to compute — often the case with spreadsheets — you'll find that most of your costs come from wasted graph walking! When cells are cheap, marking a bit on a cell can cost roughly the same as just recomputing the cell from scratch. So ideally, if we want our algorithm to be substantially faster than computing from scratch, we've got to avoid unnecessarily walking the graph as best we can.</p> The more I thought about the problem, the more I realized that they waste time walking the graph in roughly opposite situations. In our burrito graph, let's imagine cell formulas rarely change, but we rapidly switch between first observing Total</code>, and then observing Salsa in Order</code>.</p> </picture></p> In this case, Adapton will never walk the tree. No inputs are changing, and so we never need to mark anything as dirty. Since nothing is dirty, each observation is cheap as well, since we can simply return the cached value from a clean cell immediately. However, Incremental performs poorly in this example. Even though no values are ever recomputed, Incremental will repeatedly mark and unmark many cells as necessary and unnecessary.</p> In the opposite case, let's imagine a graph where our formulas are rapidly changing, but we don't change which cells we're observing. For instance, we could imagine we're observing Total</code> while rapidly changing Burrito Price</code> from 4+4</code> to 24</code>.</p> </picture></p> Just like the previous example, we aren't really recomputing many cells. 4+4</code> and 24</code> both equal 8</code>, so ideally we only recompute that one bit of arithmetic when the user makes this change. However, unlike the previous example, Incremental is now the library that avoids tree walking. With Incremental, we've cached the fact that Burrito Price</code> is a necessary cell, and so when it changes, we can recalculate it without walking the graph. With Adapton, we waste time marking Burrito Price w Ship</code> and Total</code> as dirty, even though the output of Burrito Price</code> won't have changed.</p> Given each algorithm performs well in the other's degenerate cases, wouldn't it be ideal if we could just detect those degenerate cases, and switch to the faster algorithm? This is what I have attempted to do with my own library, Anchors</a>. Anchors runs both algorithms simultaneously on the same graph! If this sounds wild and unnecessary and overly complicated, that's probably because it is.</p> In many cases, Anchors follows Incremental's algorithm exactly, which avoids Adapton's degenerate case above. But when cells are marked as unobserved, its behavior diverges slightly. Let's look at what happens. We start with marking Total</code> as observed:</p> </picture></p> If we then mark Total</code> as unobserved and Salsa in Order</code> as observed, the traditional Incremental algorithm would alter the graph to look like this, walking through every cell in the process:</p> </picture></p> Anchors also walks every cell for this change, but instead produces a graph that looks like this:</p> </picture></p> Note the "clean" flags! When a cell is no longer necessary, we mark it as "clean". Let's look at what happens when we switch from observing Salsa in Order</code> to Total</code>:</p> </picture></p> That's right — our graph now has no</em> necessary cells. If a cell has a "clean" flag, we never mark it as observed. At this point, no matter what cell we mark as observed or unobserved, Anchors will never waste time walking the graph — it knows that none of the inputs have changed.</p> Looks like there's a discount at El Farolito! Let's drop Burrito Price</code> by a dollar. How does Anchors know Total</code> needs to be recomputed? Before we recompute any formulas, let's look at how Anchors will see the graph right after we change just Burrito Price</code>, before recomputing anything:</p> </picture></p> If a cell has a clean flag, we run the traditional Adapton algorithm on it, eagerly marking downstream cells as dirty. When we later run the Incremental algorithm, we can quickly tell that there is an observed cell marked as dirty, and know we need to recompute its dependencies. After that's finished, the final graph will look like this:</p> </picture></p> We only recompute cells if they're necessary, so whenever we recompute a dirty cell, we also mark it as necessary. At a high level, you can imagine these three cell states form a looping state machine:</p> </picture></p> On necessary cells, we run the Incremental's topological sorting algorithm. On unnecessary cells, we run the Adapton algorithm.</p> burrito syntax</h2> I'd like to finish up by answering a final question: so far, we're been discussing the many problems the demand-driven model causes for our recomputation strategy. But the problems aren't just for the algorithm: there are syntactic problems to solve too. For instance, let's make a spreadsheet to select a burrito emoji for our customer. We'd write an IF</code> statement in the spreadsheet like this:</p> </picture></div> Because traditional spreadsheets aren't demand-driven, we can compute B1</code>, B2</code>, and B3</code> in any order, so long as we compute our IF</code> cell after all three inputs are ready. In a demand-driven world however, if we can calculate the value of B1</code> first, we can peek at the value to know which of B2</code> or B3</code> we need to recalculate. Unfortunately, a traditional spreadsheet's IF</code> has no way to express this!</p> The problem: B2</code> simultaneously references cell B2</code> and retrieves its value, 🥦. Most demand-driven libraries mentioned in this post instead explicitly distinguish between a reference to a cell and the act of retrieving its actual value. In Anchors, we call this cell reference an Anchor</code>. Much like a burrito in real life wraps a bunch of ingredients together, the Anchor<T></code> type wraps T</code> — which I suppose makes our vegi burrito cell Anchor<Burrito></code>, a sort of ridiculous burrito of burritos. Functions can pass around our Anchor<Burrito></code> as much as they'd like — it's only when they actually unwrap the burrito to access the Burrito</code> inside that we create a dependency edge in our graph, indicating to the recomputation algorithm that the cell may be necessary and need recomputing.</p> The approach taken by Salsa and Adapton is to use function calls and normal control flow as a way to unwrap these values. For instance, in Adapton, we might write our "Burrito for Customer" cell something like this:</p> let</span> burrito_for_customer </span>= </span>cell!</span>({ </span> </span>if </span>get!</span>(is_vegetarian) { </span> </span>get!</span>(vegi_burrito) </span> } </span>else </span>{ </span> </span>get!</span>(meat_burrito) </span> } </span>})</span>; </span></code></pre> By distinguishing between a cell reference (vegi_burrito</code> here) and the act of unwrapping its value (get!</code>), Adapton can piggy-back on top of Rust's control flow operators like if</code>. This is a great solution! However, a little bit of magical global state is needed to correctly connect the get!</code> calls to the cell!</code> that needs recomputing when is_vegetarian</code> changes. The approach I've taken with Anchors, inspired by Incremental, is a slightly less magical system. Similar to a pre-async/await Future</code>, Anchors allows you to use operations like map</code> and then</code> on an Anchor<T></code>. For instance, the example above would look something like this:</p> let</span> burrito_for_customer</span>: </span>Anchor<Burrito> </span>=</span> is_vegetarian</span>.</span>then</span>(\|</span>is_vegetarian</span>: </span>bool</span>\| </span>-> </span>Anchor<Burrito> { </span> </span>if</span> is_vegetarian { </span> vegi_burrito </span> } </span>else </span>{ </span> meat_burrito </span> } </span>})</span>; </span></code></pre> further reading</h2> In this already long and winding blog post, there is so much I didn't have space to talk about. Hopefully these resources can shed a little bit more light on this very interesting problem.</p> Seven Implementations of Incremental</a>, a great in-depth look at Incremental internals, as well as a bunch of optimizations like always-increasing heights I didn't have time to talk about, as well as clever ways to handle cells that change dependencies. Also worth reading from Ron Minsky: Breaking down FRP</a>.</li> Salsa's explanation videos</a> explains how it works quite well.</li> This Salsa issue</a>, where you can watch Matthew Hammer, creator of Adapton, patiently explain cutoffs to some rando (me) who repeatedly fails to understand how they work.</li> Raph Levien's Rustlab keynote</a> has some really interesting stuff about this topic in the context of GUIs. In response to this post, he says How Autotracking Works</a> and Autotracking: Elegant DX Via Cutting-Edge CS</a> are great resources.</li> I have to admit I don't actually understand Differential Dataflow</a>, but it's the backbone of the Materialize</a> database. Query planning in general seems like maybe a solution to the big cache missing problems that many of these frameworks suffer from? It doesn't have built-in demand-driven computation, but Jamie Brandon (thanks!) kindly pointed me to their blog post Lateral Joins and Demand-Driven Queries</a> which explains how you can add demand as an input. Also of relevance is the Noira project</a> from MIT.</li> Adapton's documentation</a> is very comprehensive.</li> Turns out this way of thinking also applies to build systems</a>.</li> Slightly Incremental Ray Tracing</a> is a slightly incremental ray tracer written in Ocaml.</li> Just saw Partial State in Dataflow-Based Materialized Views</a> today and it seems relevant.</li> Gustav Westling (thanks!) pointed out Build Systems à la Carte</a> is one of the first papers about the similarities between build systems and spreadsheets.</li> Skip</a> and Imp</a> also look really interesting.</li> </ul> And of course, you can always check out the framework I built, Anchors</a>.</p> Thanks to Syd Botz, Adam Perry, and Peter Stefek for feedback and discussion!</em></p> Invariant Lifetimes as Static, Unique Tokens 2020-10-12T00:00:00+00:00 Some of you may know I quit my job to work on a little text editor for fun. Unfortunately, in the process of doing that, I got distracted by the challenging problem of self-adjusting computation</a>. And unfortunately, to solve that problem in a performant way, you need really fast graphs, a notorious problem in Rust. And to get really fast graphs, I've found this cursed technique that takes advantage of Rust's lifetime rules and higher ranked trait bounds, which is what I'd like to talk about today. Beyond its dubious interpretation of variance, I'm proud to say this blog post represents an unprecidented achievement in yak-shaving for me, clocking in at four, maybe five levels deep. It's remarkable I'm even still using Rust — the traditional move at this deep level is to "realize" writing your own programming language is just the only reasonable way to build a text editor so you can finally write the code you wanted to write originally.</p> Let's first briefly talk about my experimental graph library, arena-graph</a>. To have fast edges in a graph, we want our nodes to have pointers that directly point to other nodes. My understanding is it's perfectly safe to cast a const Node</code> to a &Node</code>, so long as the resource targeted by that raw pointer still exists, has not been moved, and will not be moved so long as &Node</code> exists. Arena allocation gives us these properties! We only store our const Node</code> in places that will be dropped at the same time as the arena — either inside a node, or alongside the arena in the same struct. We also make sure any &Node</code> we hand out won't outlive the arena. This guarantees the raw pointers won't outlive the arena they point into.</p> However, there's still one problem. Let's say we have a set_parent</code> method like this:</p> impl </span>TreeNode </span>{ </span> </span>fn </span>set_parent</span>(</span>&</span>self</span>, </span>new_parent</span>: </span>&</span>TreeNode) { </span> </span>self</span>.</span>parent</span>.</span>set</span>(new_parent </span>as </span>const</span> TreeNode)</span>; </span> } </span>} </span></code></pre> In this example, there's no guarantee that new_parent</code> is a TreeNode in the same graph as self</code>. If these two nodes are part of different arenas, new_parent</code> could be deallocated at a different time from self</code>, self</code> later goes to dereference its parent, and we've hit undefined behavior.</p> To avoid this, we need to ensure new_parent</code> and self</code> are part of the same tree, so the tree's arena drops both nodes at the same time. One way to do this is to have TreeNode</code> have some sort of unique arena ID, and we could compare these IDs any time we add an edge from one graph node to another. This check is frustrating, though. If we're already going to all this trouble of avoiding slotmap-style checks, ideally we wouldn't have any checks at all, even when adding new edges. Another solution is we could just have the user promise they won't do this, but marking set_parent</code> as unsafe</code> will clutter up our users' code with countless unsafe blocks.</p> What if instead, we could have the Rust compiler statically check that self</code> and new_parent</code> come from the same graph? The bet of this library is that you maybe can hack this in with Rust's lifetime system, if you can guarantee that:</p> When adding an edge from &'a TreeNode</code> to &'b TreeNode</code>, we ensure that 'a</code> and 'b</code> have exactly the same lifetime.</li> If &'a TreeNode</code> and &'b TreeNode</code> came from different graphs, 'a</code> and 'b</code> will be different lifetimes.</li> </ul> To get these properties, we have to talk briefly about variance.</p> A brief aside about variance</h2> The following code compiles</a>:</p> #</span>[</span>derive</span>(Debug)] </span>struct </span>NoClone</span>(</span>i32</span>)</span>; </span> </span>fn </span>main</span>() { </span> </span>let</span> num_1 </span>=</span> NoClone(</span>1</span>)</span>; </span> </span>let</span> num_1_ref </span>= &</span>num_1</span>; </span> </span>let</span> num_2 </span>=</span> NoClone(</span>2</span>)</span>; </span> </span>let</span> num_2_ref </span>= &</span>num_2</span>; </span> </span>print_numbers</span>(num_1_ref</span>,</span> num_2_ref)</span>; </span> std</span>::</span>mem</span>::</span>drop(num_2)</span>; </span> </span>println!</span>(</span>"</span>{:?}</span>"</span>,</span> num_1_ref)</span>; </span>} </span> </span>fn </span>print_numbers</span><</span>'a</span>>(</span>num_1</span>: </span>&</span>'a</span> NoClone, </span>num_2</span>: </span>&</span>'a</span> NoClone) { </span> </span>println!</span>(</span>"</span>{:?} {:?}</span>"</span>,</span> num_1</span>,</span> num_2)</span>; </span>} </span></code></pre> At first, this may seem weird. print_numbers</code> is asking for two numbers with the same lifetime, but the two numbers have different lifetimes — num_2</code> is dropped in main</code> before we print num_1_ref</code>.</p> The answer is variance</a>. &'a NoClone</code> is covariant for 'a</code>, which has a complex type theory meaning but for our purposes means you can replace 'a</code> with any lifetime longer than 'a</code>. The two arguments passed into print_numbers</code> can have two different lifetimes, so long as both lifetimes last at least as long as the call to print_numbers</code>.</p> However, the following doesn't compile</a>:</p> #</span>[</span>derive</span>(Debug)] </span>struct </span>NoClone</span>(</span>i32</span>)</span>; </span> </span>fn </span>main</span>() { </span> </span>let</span> num_1 </span>=</span> NoClone(</span>1</span>)</span>; </span> </span>let mut</span> num_1_ref </span>= &</span>num_1</span>; </span> </span>let</span> num_2 </span>=</span> NoClone(</span>2</span>)</span>; </span> </span>let mut</span> num_2_ref </span>= &</span>num_2</span>; </span> </span>print_numbers</span>(</span>&</span>mut</span> num_1_ref</span>, </span>&</span>mut</span> num_2_ref)</span>; </span> std</span>::</span>mem</span>::</span>drop(num_2)</span>; </span>// delete this line to make it compile </span> </span>println!</span>(</span>"</span>{:?}</span>"</span>,</span> num_1_ref)</span>; </span>} </span> </span>fn </span>print_numbers</span><</span>'a</span>>(</span>num_1</span>: </span>&</span>mut </span>&</span>'a</span> NoClone, </span>num_2</span>: </span>&</span>mut </span>&</span>'a</span> NoClone) { </span> </span>println!</span>(</span>"</span>{:?} {:?}</span>"</span>,</span> num_1</span>,</span> num_2)</span>; </span>} </span></code></pre> All we've changed here is switched print_numbers</code> to accept &mut &'a NoClone</code> arguments instead of &'a NoClone</code>. Why is this invalid? Well, we could add a quick line to print_numbers</code>:</p> </span>num_1 </span>= </span>num_2</span>; </span></code></pre> In our main</code> function, this would update num_1_ref</code> to point to num_2</code>. Since num_2</code> is dropped before num_1_ref</code> is printed, this swap would cause undefined behavior, so the compiler is right to complain about this.</p> How does lifetime variance prevent this second case, but allow the first one? &'b mut T</code> is (just like &'b T</code>) covariant for 'b</code>. However, it's invariant</em> for T</code>, which means only and exactly a T</code> can be passed in. Since T</code> in this example is &'a NoClone</code>, our new print_numbers</code> requires the two &'a NoClone</code> to have exactly the same lifetime 'a</code>.</p> Applying this to our graph</h2> We mentioned earlier we want our add edge method to have two properties:</p> When adding an edge from &'a TreeNode</code> and &'b TreeNode</code>, we ensure that 'a</code> and 'b</code> have exactly the same lifetime.</li> If &'a TreeNode</code> and &'b TreeNode</code> came from different graphs, 'a</code> and 'b</code> will be different lifetimes.</li> </ul> To get the first property, we just need to make sure &'a TreeNode</code> is invariant for 'a</code>. To get this, we can use a PhantomData</code> and a wrapper struct:</p> use </span>std</span>::</span>marker</span>::</span>PhantomData</span>; </span> </span>#</span>[</span>derive</span>(Clone</span>,</span> Copy)] </span>struct </span>TreeNodeRef</span><</span>'a</span>> { </span> inner</span>: </span>&</span>'a</span> TreeNode, </span> mark_invariant</span>: </span>PhantomData<</span>&</span>'a mut </span>&</span>'a </span>()>, </span>} </span> </span>impl </span><</span>'a</span>> </span>TreeNodeRef</span><</span>'a</span>> { </span> </span>fn </span>set_parent</span>(</span>self</span>, </span>new_parent</span>: </span>TreeNodeRef<</span>'a</span>>) { </span> </span>self</span>.</span>parent</span>.</span>set</span>(new_parent</span>.</span>inner </span>as </span>const</span> TreeNode)</span>; </span> } </span> </span>fn </span>get_parent</span>(</span>self</span>) </span>-> </span>TreeNodeRef<</span>'a</span>> { </span> TreeNodeRef { </span> inner</span>: </span>unsafe </span>{ </span>&*</span>self</span>.</span>parent</span>.</span>get</span>() }</span>, </span> mark_invariant</span>:</span> PhantomData</span>, </span> } </span> } </span>} </span></code></pre> We still need that second property, though, where two trees always produce TreeNodeRef</code>s with different lifetimes. There's a lot here that won't work. For instance, this stripped down example initially appears to error correctly:</p> use </span>std</span>::</span>marker</span>::</span>PhantomData</span>; </span> </span>#</span>[</span>derive</span>(Clone</span>,</span> Copy</span>,</span> Debug)] </span>struct </span>TreeNodeRef</span><</span>'a</span>> { </span> </span>// inner node data ommited for brevity </span> mark_invariant</span>: </span>PhantomData<</span>&</span>'a mut </span>&</span>'a </span>()>, </span>} </span> </span>fn </span>same_lifetime</span><</span>'a</span>>(</span>a</span>: </span>TreeNodeRef<</span>'a</span>>, </span>b</span>: </span>TreeNodeRef<</span>'a</span>>) { </span> </span>// two nodes have same lifetime; set recursive pointers here </span>} </span> </span>struct </span>Tree</span>; </span>impl </span>Tree </span>{ </span> </span>fn </span>root</span><</span>'a</span>>(</span>&</span>'a </span>self</span>) </span>-> </span>TreeNodeRef<</span>'a</span>> { </span> TreeNodeRef { </span> mark_invariant</span>:</span> PhantomData</span>, </span> } </span> } </span>} </span> </span>fn </span>main</span>() { </span> </span>let</span> tree_1 </span>=</span> Tree</span>; </span> </span>let</span> root_1 </span>=</span> tree_1</span>.</span>root</span>()</span>; </span> { </span> </span>let</span> tree_2 </span>=</span> Tree</span>; </span> </span>let</span> root_2 </span>=</span> tree_2</span>.</span>root</span>()</span>; </span> </span>same_lifetime</span>(root_1</span>,</span> root_2)</span>; </span> } </span> </span>println!</span>(</span>"</span>{:?}</span>"</span>,</span> root_1)</span>; </span>} </span></code></pre> This fails because root_1</code> and root_2</code> have different lifetimes. But move the creation of root_1</code> into the block, and we can get this to incorrectly compile:</p> fn </span>main</span>() { </span> </span>let</span> tree_1 </span>=</span> Tree</span>; </span> { </span> </span>let</span> tree_2 </span>=</span> Tree</span>; </span> </span>let</span> root_1 </span>=</span> tree_1</span>.</span>root</span>()</span>; </span> </span>let</span> root_2 </span>=</span> tree_2</span>.</span>root</span>()</span>; </span> </span>same_lifetime</span>(root_1</span>,</span> root_2)</span>; </span> } </span> </span>println!</span>(</span>"</span>{:?}</span>"</span>,</span> tree_1</span>.</span>root</span>())</span>; </span>} </span></code></pre> Now root_1 and root_2 are created at the same time, and so share the same lifetime. How do we make this impossible? Initially it may seem we could use a closure to force the root()</code> calls to be in different scopes:</p> struct </span>Tree</span>; </span>impl </span>Tree </span>{ </span> </span>fn </span>with_root</span><</span>'a</span>, F</span>: </span>FnOnce</span>(TreeNodeRef<</span>'a</span>>)>(</span>&</span>'a </span>self</span>, </span>func</span>:</span> F) { </span> </span>func</span>(TreeNodeRef { </span> mark_invariant</span>:</span> PhantomData</span>, </span> }) </span> } </span>} </span> </span>fn </span>main</span>() { </span> </span>let</span> tree_1 </span>=</span> Tree</span>; </span> </span>let</span> tree_2 </span>=</span> Tree</span>; </span> tree_1</span>.</span>with_root</span>(\|</span>root_1</span>\| { </span> tree_2</span>.</span>with_root</span>(\|</span>root_2</span>\| { </span> </span>same_lifetime</span>(root_1</span>,</span> root_2)</span>; </span> }) </span> })</span>; </span>} </span></code></pre> However, you'll find that this actually compiles! How is this possible? My understanding gets a little fuzzier here, but I'm pretty sure since with_root</code>'s &'a self</code> is covariant for 'a</code>, it allows the constructed TreeNodeRef<'a></code> to also have an arbitrarily long lifetime. How can we make this correctly error? Ideally we need some way to express that the FnOnce</code> passed to with_root</code> should not</em> have a lifetime selected by the caller, but instead some unique lifetime determined by with_root</code>. Fortunately for us, Rust has a bit of magic called higher ranked trait bounds</a> that does exactly that:</p> impl </span>Tree </span>{ </span> </span>fn </span>with_root</span><F</span>:</span> for <</span>'any</span>> </span>FnOnce</span>(TreeNodeRef<</span>'any</span>>)>(</span>&</span>self</span>, </span>func</span>:</span> F) { </span> </span>func</span>(TreeNodeRef { </span> mark_invariant</span>:</span> PhantomData</span>, </span> }) </span> } </span>} </span></code></pre> With the code above, our main</code> will correctly fail to compile, since root_1</code> and root_2</code> will be guaranteed to have different lifetimes.</p> Why not Cell<&'a Node<'a>></code>?</h2> Some ppl construct graphs using a node that looks something like this:</p> struct </span>Node</span><</span>'a</span>> { </span> parent</span>: </span>Cell<</span>Option</span><</span>&</span>'a Self</span>>> </span>} </span></code></pre> While this has the advantage of not needing unsafe, it unfortunately means your graph struct has a lifetime in it:</p> struct </span>Graph</span><</span>'a</span>> { </span> arena</span>: </span>Arena<Node<</span>'a</span>>>, </span>} </span></code></pre> I've found that this lifetime gets in the way a lot, and results in unergonomic interfaces. It also means the Graph</code> can never be moved after a node is inserted, which is an unnecessary requirement, given how arena allocated nodes are always on the heap.</p> Is this really a good idea??</h2> Sometimes we don't do things because they're good. We do them because they are bad.</p> See also</h2> Just minutes after publishing this, I came across</a> Alexis Beingessner's thesis</a>, which describes this exact technique in section 6.3, although PhantomData<Cell<'a u8>></code> is used to make the lifetime invariant instead of my PhantomData<&'a mut &'a ()></code>. To quote Alexis:</p> we really</em> don’t recommend doing this</p> </blockquote> I guess this is just one more post to add to the pile of evidence</a> that my blog is just a cheap ripoff of Alexis'</a>.</p> Identity Beyond Usernames 2020-07-07T00:00:00+00:00 In 2006, Robert Andersen sent the first tweet that @mentioned another user</a>, and an internet convention was born.</p> </p> In a world without smartphones, Twitter's primary interface was SMS. There were no threads, no @username autocomplete. If a user said something and you wanted to reply, your only option was to compose a new text to 40404, manually typing the @mention into your phone's SMS text box. SMS was also the origin of Twitter's original 140 character</a> limit:</p> Twitter began as an SMS text-based service. This limited the original Tweet length to 140 characters (which was partly driven by the 160 character limit of SMS, with 20 characters reserved for commands and usernames).</p> </blockquote> Also a holdover from the SMS days, Twitter does not allow any formatted or rich text. Users today work around this limitation by using the wide array of possibilities that Unicode affords. Text generators</a> convert ASCII characters into 𝔲𝔫𝔲𝔰𝔲𝔞𝔩 𝔘𝔫𝔦𝔠𝔬𝔡𝔢 𝔠𝔥𝔞𝔯𝔞𝔠𝔱𝔢𝔯𝔰. Memes take advantage of repeated spaces to position text, or to draw Unicode houses. (All of that is, of course, completely inaccessible to screen readers.) Emoji modifiers allow expressing a wide range of emotions with modifiers for skin tones and gender.</p> </p> Critically, this "plain" text is fully copy-pastable into any app with Unicode support. While many Twitter users from 2006 were likely limited to the GSM-7 encoding</a>, the limitations of the T9 keyboard</a>, and their phone's limited text rendering and shaping, modern users have found new ways to express themselves using the full Unicode character space. Nowadays, tweets, names, URLs, hashtags, basically everything</em> can contain Unicode characters. Of course, everything except the @mention.</p> Usernames on Twitter have more or less the same requirements as during the SMS era — up to 15 letters from a-z</code>, numbers from 0-9</code> and the underscore _</code>. This requirement is similar to many other websites: GitHub only allows alphanumeric characters and non-repeating hyphens, and Facebook allows just alphanumeric characters and the period.</p> As we will see, this limitation is one of several problems with usernames.</p> Unicode Usernames</h2> Imagine if instead of alphanumerics, GitHub allowed usernames to only be made up of the numbers 0-9</code> and Chinese characters. It would be pretty frustrating, right? If forced to use a system like this, we would likely ignore the Chinese characters, and just use the numbers as usernames. This is often what happens on social media platforms in countries that don't use Latin script. In China, the QQ instant messaging service (originally started in 1999) completely got rid of usernames used by similar services like AOL. Instead, each user is assigned a unique number, their QQ ID. This number cannot be chosen by the user, and is immutable. WeChat similarly assigns users a random number when they sign up, although it does allow each user exactly one opportunity to change it to an alphanumeric string of their choice. Typing long numbers isn't particularly ergonomic, which could help explain the widespread use of QR codes in China.</p> Even in Latin-speaking countries, AOL-style usernames had issues. By requiring a username when logging in, and also</em> requiring usernames to be unique among all users, users are often forced to use different usernames on different services, creating a second password that they had to memorize. Thankfully, most services have fixed at least this small problem by having login be email- instead of username-based.</p> Throughout the world, usernames are alphanumeric only. Why can't we just allow Unicode, so that usernames could contain Chinese, Cyrillic, or other non-Latin alphabets? Unfortunately Unicode usernames have their own issues — just look at the largest username system in the world, the domain name system and the extension that allowed non-ASCII characters</a>. This was an essential upgrade, and yet it has inperfections, allowing the registration of websites</a> such as this one:</p> </p> This is latest Firefox, as of July 2020, displaying what appears to be "epic.com", the website of a large healthcare company. However, as you can see, the content is actually some random blog reminding people to drink water. How is this possible? If we stick the code into a Unicode character inspector, we can see what's going on:</p> </p> Byte-wise, the real "epic.com" and the false website "еріс.com" are completely different. But visually, they're indistinguishable from each other in the URL bar, allowing phishing problems to run amock. Unicode canonicalization and normalization</a> can help with certain cases of this problem, but does nothing for our epic.com example.</p> This particular example isn't visible in Chrome, which instead shows https://xn--e1awd7f.com/</code>, the "punycode"</a> representation of the domain name. This is thanks to Chrome's complex, 13 step process</a> for detecting if a domain name is likely to be a Unicode phish or not. "Well, it may be complex," you tell me, "but at least it solves the phishing problem!" Unfortunately it does not.</p> Specific instances of IDN homograph attacks have been reported to Chrome, and we continually update our IDN policy to prevent against these attacks.</p> </blockquote> The Unicode spec is apparently too large to solve this problem 100% perfectly, and so their "solution" is to pay $2000 to anybody who finds new edge cases. This also doesn't actually solve the problem for non-Latin alphabets — if for example, I own a Chinese domain name, it will never show punycode, and attackers can phish my site using duplicate encodings for those Chinese characters. Chrome just attempts to solve the much smaller problem of the numerous Unicode characters that visually look like the Latin alphabet.</p> This is probably frustrating to read, and you may want to point fingers at Unicode, for failing to provide canonical encodings for a series of graphemes. Or perhaps we can blame the domain name registrars, for allowing visually identical registrations. But I think the real culprit here is the incorrect assumption we Latin script users have when we build usernames into our systems. We assume that two visually-identical printed text tokens will have the same bytewise encoding. This is simply not true for a huge portion of computer users, and is a root failing with username-based systems today. The only solution is to develop systems that don't have usernames.</p> Even in a trusted system with no bad actors, there is no guarantee a user retyping a non-Latin username from a printed document will end up with the same bytes as the original document.</p> Changing Usernames</h2> Let's say you're building a site for English use only, and so even after reading all of this, you think perhaps it's ok to have usernames. After all, you'll probably find, like Twitter did, that this makes text entry for @mentions much</em> simpler to implement. You get to use just a plain text field, instead of building an input field that can insert custom @mention objects.</p> Unfortunately, you will still run into the issue of somebody changing</em> their username. This is often an extremely complex problem. Take GitHub</a> for example. Changing your username there will redirect your old repository links to new ones. However, somebody else can come in and use your old username. What happens if they create a repo with the same name as your old one?</p> If the new owner of your old username creates a repository with the same name as your repository, that will override the redirect entry and your redirect will stop working.</p> </blockquote> URLs aren't the only place GitHub usernames are used. Using the web interface, in some cases, will create commits with the email myusername@users.noreply.github.com</code>. These commits will permanantly be disconnected from your account, unless you somehow are able to force push edited commit headers to every repository you've ever contributed to. Good luck with that.</p> Instagram has issues with changing usernames, too. Up until 2015, updating your username would cause you to lose all your previous @mentions. They've since fixed this; old @mentions eventually update. Twitter supposedly will also preserve your replies, although my testing shows this is an unreliable feature at best. Updating the actual @mention as it's listed in the Tweet would have other issues, since if a user mentioned in a 280-character tweet adds 5 characters to their username, you'd suddenly get a 285-character tweet. Hope your Twitter clients can all support that.</p> The final example of username switching pains I have is from my year at Google. I was fortunate enough to never switch my username, perfectly satisfied every morning when I opened my laptop and saw lard@google.com</code> on the login screen. But countless internal systems used by engineers there assume usernames are immutable, making a username switch a multi-day process that is never really complete.</p> There is one easy "solution" to all of this, of course, which is to make it impossible to change your username. This is what gmail does</a>:</p> If your account's email address ends in @gmail.com, you usually can't change it.</p> </blockquote> I love the "usually". I guess in certain, mysterious cases it's possible to change it? In any case, making a random, numeric user ID immutable is fine. But if that user ID contains letters and is user-selected, making it immutable is an unacceptable solution for real-world situations. Whether it contains a user's deadname, or an old nickname they don't go by any longer, or even for those of us who, in sixth grade, decided "lordjubjub" would be an excellent and professional email address (just a hypothetical example, of course), usernames need to be editable. If they're editable, why not avoid all these username troubles and just go for a fully-Unicode, non-unique display name instead?</p> Username Alternatives</h2> 250 million people have registered for Discord, a chat app similar to Slack or IRC. However, unlike Slack and IRC whose usernames are local to a particular server, Discord has just one server, and usernames are universal. With 250 million users in a single username space, collisions become a massive problem, finding short or reasonable usernames becomes nearly impossible, and you start to see users mass-registering accounts to sell the usernames for Bitcoin.</p> To avoid all these issues, Discord dropped uniqueness requirements. Multiple users can all have the same username, although they aren't quite a display name, since a Discord-generated #1234</code> discriminator number appears at the end of usernames in certain contexts. This even allows them to have fully-Unicode usernames</a>; username phishing is less of a problem when users expect duplicate usernames, and none of your systems depend on username uniqueness.</p> Slack went futher than this, and in 2017 decided to phase out usernames completely</a> in favor of display names only. Users @mention each other by typing an @</code>, a few characters of a person's name, and clicking on the dropdown. In some cases when there are duplicate display names, not selecting from the dropdown will result in an error:</p> </p> As a text editing engineer, I also can't help but look at this through the lens of text editing technologies. (Yes, that's right! It's always about text editing.) Usernames are a product of the text input and encoding systems used in decades past — just look at how Twitter's username needs were influenced by SMS protocols. The username advances made by Slack and Discord are only possible because they're able to build rich text editors (difficult with modern frameworks!</a>) that allow embedded, autocompleted @mentions that don't rely on the uniqueness of text tokens. You might be surprised just how much of the UI landscape is driven by these changes and advances in text editing.</p> I've just got one final note: while they're extremely common, usernames are far from the only example of text as a unique token. JSON APIs use text tokens everywhere; we've only recently seen protocols with renamable fields like protobuf</a> and capnproto</a> gain popularity. Variables in programming languages are also common text tokens, and while arguably changing a name isn't a large deal for local variables, changing the name of a public class in most languages I know is a breaking change. Filesystem directories, too, are unique text tokens, and can suffer from naming conflicts where two bits of software have the same command name, or store their settings in the same directory.</p> Proposing to get rid of variable labels or filenames may sound impossible, or wild, or unnecessary, but our industry's waning love for the username shows there are numerous benefits to avoiding text-based unique tokens. If we want to move onward from these limitations, we shouldn't look toward fixing the tokens themselves. We already know technically how to generate unique numeric identifiers, and we could easily just generate unique numbers for directories or programming language entities. Instead, Slack and Discord show us the main problem — plain text editing forces us to conflate our model of identity with our model for labels.</p> It turns out this isn't a text token problem. It's a text editing problem.</p> Text Editing Hates You Too 2019-10-28T00:00:00+00:00 Alexis Beingessner's Text Rendering Hates You</a>, published exactly a month ago today, hits very close to my heart.</p> Back in 2017, I was building a rich text editor in the browser. Unsatisfied with existing libraries that used ContentEditable, I thought to myself "hey, I'll just reimplement text selection myself! How difficult could it possibly be?" I was young. Naive. I estimated it would take two weeks. In reality, attempting to solve this problem would consume several years of my life, and even landed me a full time job for a year implementing text editing for a new operating system.</p> While on the job, I was lucky enough to learn from mentors1</a></sup> who had tons of experience in this field. I heard many, many horror stories, including of one person maintaining a Windows application that had a custom text field implementation. They wanted to upgrade from the legacy Windows text input API to a newer version. Let's look at the interface list</a> for that newer version:</p> That's right, the Windows text input APIs contain 128 interfaces. I'm pretty sure there are also eight (8!) different types of locks to fix concurrency issues, although I honestly haven't read their documentation, so don't quote me on that. Anyway, this engineer I heard about spent a year and a half (full-time!) attempting the upgrade, and in the end, their efforts ended in failure. They ended up staying on the legacy API.</p> Text input is difficult.</p> Alexis already touches on selection in a couple places, but as she mentions in her article, her experience is with working on text rendering. From the perspective of somebody who worked on the editing side of things, I have just a few points to add.</p> Vertical Cursor Movement</h2> In this example, if the user presses up, the caret will go to the beginning of the line, before "hello". This is pretty reasonable so far. However, if the user presses up and then down, the caret will first jump before "hello", and then after the word "some".</p> This may seem unintuitive. Why does it jump rightward? Well, each caret remembers an x-position in pixels that is used for vertical movements, and this position is only updated when the user presses left or right, not</em> up and down. This is the same behavior that prevents carets from migrating left when vertically moving past short lines.</p> Affinity</h2> Ok, so we now know that a text selection has two</em> chunks of state, the byte offsets of its position inside the string and the x-position in pixels mentioned above. Problem solved? Well, no.</p> Let's look at two caret positions on a very long line:</p> Since "loooooooooong" is a single word, the two caret positions have exactly the same byte offset in the string</em>. There's no newline character between them, since the line is soft wrapped. Our carets will need an extra bit that tells them which line to tend towards. Most systems call this bit "affinity". This same bit is also used in mixed bidirectional text, which we'll get to in a moment.</p> Emoji Modifiers</h2> Let's say I'm sending a message to my friend. To emphasize my excitement, I want to add in a fun lil emoji. I fill a textarea with a thumbs up, the letter a</code>, and an emoji skin tone modifier. It looks like this:</p> Whoops, I didn't mean to put the a</code> there. I position the caret after the a</code> and press backspace. What happens? I've seen several outcomes, depending on the editor.</p> Bad #1</strong> may look</em> correct. But this is what happens in a text editor that has outdated emoji rendering support, like Sublime Text. This is bad because a light skin tone thumbs up emoji is encoded as the yellow thumbs up emoji immediately followed by the light skin tone modifier. Byte-wise, this should be rendered as a single emoji. Even if I copy-pasted one from another application, it would still be rendered incorrectly like this.</li> Bad #2</strong> is what Chrome 77 does in the address bar. Not on web pages, just the address bar. This is not a rendering problem, since copy-pasting a emoji with a skin tone works. Instead, Chrome deletes the a</code>, and then noticing that the a</code> is modified by a skin tone, deletes the skin tone too. Whoops.</li> Bad #3</strong> is "correct" according to the Unicode spec in that the two emoji merge into one. But it's pretty confusing for users, and bytewise, our caret has to move in order to not be stuck halfway inside a single emoji.</li> </ul> Those options are all bad, so you're probably hoping there's some fourth option. There is! Many editors, like TextEdit, won't even allow us to put a caret after the a</code>, since the skin tone modifier is treated as a single unit with its previous character. This makes sense in the emoji context, and even works alright for this a</code>. However, what happens when the emoji modifier is the first character on a line?</p> The emoji modifier is now modifying the newline character. TextEdit won't let us place a caret at the start of the second line! I'd personally consider this solution "also bad".</p> You also may have noticed that the thumbs up has switched to a thumbs down. I changed that myself to reflect my feelings about this whole situation.</p> As an aside, TextEdit specifically makes carets on the first line very</em> buggy. For instance, guess what happens if I press 4</code> here?</p> Yup. You also may think there are spaces between those numbers. There aren't.</p> Bidirectional Text</h2> Alexis mentions disconnected selections in mixed bi-directional text, like this example from TextEdit:</p> This actually makes sense, since Arabic in strings is encoded from right to left, so this selection appears disconnected, but byte-wise represents a contiguous range of the string.</p> This makes it a little surprising, then, that we can get this</em> selection:</p> Yes, that is a visually contiguous, byte-wise disconnected selection. Yes, this is bad. Some text editing engines do this when you select with the arrow keys instead of the mouse. The alternative is flipping left/right arrow keys inside the RTL range, which is also bad. There are no good solutions here.</p> For extra credit, you can try to figure out what's going on here:</p> I don't want to talk about that selection.</p> Input Methods are a Thing</h2> The software that translates keypresses into input is called an "input method" or "input method editor". For the Latin alphabet used by English speakers, this isn't terribly interesting software, since each keypress gets directly mapped to inserting a single character. But quite a few languages have too many characters for a single keyboard, and so they need to get creative. For instance, with some Chinese input methods, the user types the pronounciation of what they're trying to say, and get a list of characters that match phonetically:</p> This is sometimes called a composing region, and it often appears as underlined text. Sometimes the input method needs to style this region. This Japanese input method on Android, for example, uses background color to create a split suggestion region:</p> (Thanks to Shae for the screenshot!)</small></p> Do all these various highlight and compose ranges interact with bidirectional text? Let's not think about that.</p> Input methods have to work everywhere, even inside a terminal</em>:</p> Nothing is actually sent to Vim until the Chinese character is selected from the list. You're probably thinking "but how would that work with Vim's command mode?" Not very well. This is why, on the web, text input and keypresses are separate events. Terminals conflate these two, causing problems.</p> This is just one example of the many, many different ways that people input text. (Don't forget about non-keyboard methods like voice and handwriting input!) Fortunately for text field implementors, the operating system provides all these input methods for you. Unfortunately for text field implementors, you have to get your text field to speak the common text input protocol used by all these input methods. For Windows, that's those 128 interfaces listed at the beginning of this article. Other operating systems have simpler interfaces, but usually they're still tricky to implement.</p> You also may have noticed that the input method is a separate process from our text field, and since both the input method and application can make modifications to the state of the text field, this protocol is a concurrent editing protocol. Windows solves this with its eight (8!) types of locks. Although holding a lock across process boundaries may sound questionable to you, most other platforms try to use imperfect heuristics to fix concurrency issues. Or they just hope race conditions don't happen. In my experience, prayers are not a very effective concurrency primitive.</p> Why is this so complicated??</h2> Jonathan Blow, in a talk about how software is getting worse, points to the example of Ken Thompson's text editor</a>, which Ken built in a single week. Plenty of the code in this blog post is accidental complexity. Does Windows need 128 interfaces and 8 kinds of locks to provide text input? Absolutely not. Are the bugs we've found in TextEdit disappointing, and a result of a complicated editing model? Yes. Are the wealth of bugs in modern programs something we should be worried about? I'm worried, at least.</p> But at the same time, Ken Thompson's editor was much, much simpler than what we expect from our text editors today. Unicode supports almost every one of the ~7000 living languages used around the world, and plenty more dead languages too. These use a variety of scripts, directions, and input methods that each impose tricky (and in some cases, unsolved) problems on any editor we'd like to make. Our editor also needs to be usable by vision-impaired folks who use screen readers.</p> The necessary complexity here is immense</em>, and this post only scratches the very surface of it. If anything, it's a miracle of the simplicity of modern programming that we're able to just slap down a <textarea></code> on a web page and instantly provide a text input for every internet user around the globe.</p> ^{1</sup> Thanks, as always, to Raph Levien and Yohei Yukawa, who taught me everything I know about text input.</p> </div>} Hatched Icosahedron 2019-10-23T00:00:00+00:00

Appendix E: Richard Stallman, "A Free Digital Society" (New York, 2014)</h2>

How to Recalculate a Spreadsheet

2020-11-09T00:00:00+00:00

Let's say I'm ordering burritos for my two friends while they quarantine in Jersey City, and want to calculate the total price of my order:

</picture></div>

It's a little confusing to follow the flow of data in a spreadsheet when it's written like that, so I hope you don't mind this equivalent diagram that represents it as a graph:

</picture>

We're rounding the cost of an El Farolito super vegi burrito to $8, so assuming the per-burrito delivery toll remains at just $2 per burrito, it looks like the total for our two burritos will be $20.

Oh no, I completely forgot! One of my friends loves to wolf down multiple burritos at a time, so I actually want to place an order for three burritos. If I update Num Burritos</code>, a naïve spreadsheet engine might recompute the entire document, recalculating first the cells with no inputs, and then recalculating any cell whose inputs are ready until we've finished every cell. In this case, we'd first calculate Burrito Price</code> and Num Burritos</code>, then Burrito Price w Ship</code>, and then a new final Total</code> of $30.

</picture>

This simple strategy of recalculating the whole document may sound wasteful, but it's actually already better than VisiCalc, the first spreadsheet software ever made, and the first so-called "killer app", responsible for popularizing the Apple II. VisiCalc would repeatedly recalculate cells from left-to-right and top-to-bottom, sweeping over them again and again until none of them changed. Despite this "interesting" algorithm, VisiCalc remained the dominant spreadsheet software for four years. Its reign ended in 1983, when Lotus 1-2-3 swept the market with "natural-order recalculation", as described by Tracy Robnett Licklider in Byte Magazine</a>:

Lotus 1-2-3 exploited natural-order recalculation, although it also supported VisiCalc’s row- and column-order modes. Natural-order recalculation maintained a cell dependency list and recalculated a cell before recalculating cells that depended on it. </blockquote> Lotus 1-2-3 implemented the "recalculate everything" strategy we've shown above, and for the first decade of spreadsheets, that was as good as it got. Yes, we recalculate every cell in the document, but at least we only recalculate every cell once. but what about "burrito price w ship"</h2> Great point, header 2. In my three burrito example there's no reason to recompute Burrito Price w Ship</code>, because changing the number of burritos we order can't possibly influence the per-burrito price. In 1989, one of Lotus' competitors realized this, and created SuperCalc5, presumably naming it after the theory of super burritos at the core of this algorithm. SuperCalc5 recalculated "only cells dependent on changed cells", which would make updating the burrito count look more like this: </picture> By only updating a cell when one of its inputs changes, we can avoid recalculating Burrito Price w Ship</code>. In this case, it saves just a single addition, but on larger spreadsheets it can save quite a bit of time! Unfortunately, we now have another problem. Let's say my friends now want meat burritos, which cost a dollar more, and simultaneously El Farolito adds a $2 fee paid per-order, regardless of how many burritos you order. Before any formula outputs are recalculated, our graph might look like this: </picture> Since there are two updated cells here, we have a problem. Should we recalculate Burrito Price</code> first, or Total</code>? Ideally, we first calculate Burrito Price</code>, notice that its output has changed, then recalculate Burrito Price w Ship</code>, and finally recalculate Total</code>. However, if we instead recalculate Total</code> first, we'll have to recalculate it a second time once the new $9 burrito price propagates down. If we don't calculate cells in the right order, this algorithm isn't better than recalculating the whole document. In some cases, it's as slow as VisiCalc! Clearly, it's important for us to figure out the right order to update our cells. Broadly, there are two solutions to this problem: dirty marking and topological sorting. This first solution involves marking all cells downstream from an edit as dirty. For instance, when we update Burrito Price</code>, we would mark the downstream cells Burrito Price w Ship</code> and Total</code> as dirty, even before doing any recalculations: </picture> Then, in a loop, we find a dirty cell that has no dirty inputs, and recalculate it. When there are no dirty cells left, we're done! This solves our ordering problem. There's one downside though — if a cell is recalculated and we find its new output to be the same as its previous output, we'll still recalculate downstream cells! A little bit of extra logic can avoid actually running the formula trouble in this case, but we unfortunately still waste time marking and unmarking a lot of cells as dirty. The second solution is topological sorting. If a cell has no inputs, we mark its height as 0. If a cell has inputs, we mark its height as the maximum of the heights of its inputs, plus one. This guarantees all cells have a greater height than any of their inputs, so we just keep track of all cells with a changed input, always choosing the cell with the lowest height to recalculate first: </picture> In our double-update example, Burrito Price</code> and Total</code> would be initially added to the recalculation heap. Burrito Price</code> has lesser height, and would be recalculated first. Since its output changes, we then would add Burrito Price w Ship</code> to the recalculation heap, and since it too has less height than Total</code>, it would be recalculated before we finally recalculate Total</code>. This has a big advantage over the first solution: no cell is ever marked dirty unless one of its inputs actually change. However, it requires we keep all cells pending recalculation in sorted order. If we use a heap, this results in an O(n log n)</code> slowdown, so in the worst case, asymptotically slower than Lotus 1-2-3's strategy of recalculating everything. Modern-day Excel uses a combination of dirty marking and topological sorting</a>, which you can read more about in their docs. demand-driven complications</h2> We've now more or less reached the algorithms used in modern-day spreadsheet recalculation. Unfortunately, I suspect there is basically no business case to be made for ever improving it further. The few people with the problem "my Excel spreadsheet is too slow" have already written enough Excel formulas that migration to any other platform is impossible. Fortunately, I have no understanding of business, and so we're going to look at further improvements anyway. Beyond caching, one of the cool aspects of a spreadsheet-style computation graph is we can only calculate the cells that we're interested in. This is sometimes called lazy computation, or demand-driven computation. As a more concrete example, here's a slightly expanded burrito spreadsheet graph. This example is the same as before, but we've added what is best described as "salsa calculations". Each burrito contains 40 grams of salsa, and we perform a quick multiplication to know how much salsa is in our entire order. In this case, since our order has three burritos, there's a total of 120 grams of salsa in our entire order. </picture> Of course, astute readers will have spotted the problem here already: knowing the total weight of salsa in an order is a pretty useless measurement. Who cares that it's 120 grams? What am I supposed to do with this information?? Unfortunately, a regular spreadsheet would waste cycles calculating Salsa In Order</code>, even if we don't want it recalculated most of the time. This is where demand-driven recalculation can help. If we could somehow specify that we're only interested in the output of Total</code>, we could only recompute that cell and its dependencies, and skip touching Salsa In Order</code> and Salsa Per Burrito</code>. Let's call Total</code> an observed cell, since we're trying to look at its output. We can also call both Total</code> and its three dependencies necessary cells, since they're necessary to compute some observed cell. Salsa In Order</code> and Salsa Per Burrito</code> would be aptly described as unnecessary. Some folks on the Rust team created the Salsa</a> framework to solve this problem, clearly naming it after the unnecessary salsa calculations their computers were wasting cycles on. Salsa is really cool, and I'm sure they can explain</a> how it works better than I can. Very roughly, they use revision numbers to track whether a cell needs recalculation. Any mutation to a formula or input increments the global revision number, and every cell tracks two revisions: verified_at</code> to track the revision its output was last brought up-to-date, and changed_at</code> to track the revision its output last actually changed. </picture> When the user indicates they'd like a fresh value for Total</code>, we'd first recursively recalculate any cell necessary to Total</code>, skipping cells if their last_updated</code> revision is equal to the global revision. Once the dependencies of Total</code> are up-to-date, we only rerun the actual formula in Total</code> if either Burrito Price w Ship</code> or Num Burrito</code> have a changed_at</code> revision greater than the verified_at</code> revision of Total</code>. This is great for Salsa's purposes in the rust-analyzer, where simplicity is important and each cell takes a significant amount of time to compute. However, we can see the disadvantages in our burrito graph above — if Salsa Per Burrito</code> constantly changes, our global revision number will frequently tick up. This will make each observation of Total</code> walk the three cells necessary to it, even though none of those cells have actually changed. No formulas will be recalculated, but if the graph is large, repeatedly walking all of a cell's dependencies could get expensive. faster demand-driven solutions</h2> Instead of inventing new algorithms for demand-driven spreadsheets, what if we instead draw from the two classical spreadsheet algorithms mentioned earlier: dirty marking and topological sorting? As you might imagine, a demand-driven model complicates both of these, but both are still viable. Let's first look at dirty marking. As before, when we change a cell's formula, we mark all downstream cells as dirty. So if we update Salsa Per Burrito</code>, it would look something like this: </picture> However, instead of immediately recomputing all cells that are dirty, we wait for the user to observe a cell. Then we run Salsa's algorithm on the observed cell, but instead of reverifying dependencies with outdated verified_at</code> revision numbers, we instead only reverify cells marked as dirty. This is the technique used by Adapton</a>. You'll note that when we observe Total</code>, we'll find it isn't dirty, and so we can skip the graph walk that Salsa would have performed! If we instead decide to observe Salsa In Order</code>, we'll find it is marked as dirty, and so we'll reverify and recompute both Salsa Per Burrito</code> and Salsa In Order</code>. Even here, there are benefits over using just revision numbers, since we'll be able to skip a recursive walk on the still-clean Num Burritos</code> cell. Demand-driven dirty marking performs fantastically when the set of cells we're trying to observe changes frequently. Unfortunately, this has the same downsides as the dirty marking algorithm from before. If a cell with many downstream cells changes, we may waste a lot of time marking and unmarking cells as dirty, even if their inputs won't actually have changed when we go to recalculate them. In the worst case, each changes causes us to mark the entire graph as dirty, which would give us the same ~order of magnitude performance as Salsa's algorithm. Moving on from dirty marking, we can also adapt topological sorting for demand-driven computations. This is the technique used by Jane Street's Incremental</a> library, and requires major tricks</a> to get right. Before we added demand-driven computations, our topological sorting algorithm used a heap to determine which cell would be recomputed next. But now, we only want to recompute cells that are necessary. How? We don't want to walk the entire tree from our observed cells like Adapton, since a complete tree walk defeats the entire purpose of topological sorting, and would give us performance characteristics similar to Adapton. Instead, Incremental maintains a set of cells that the user has marked observed, as well as the set of cells that are necessary to any observed cell. Whenever a cell is marked observed or unobserved, Incremental walks that cell's dependencies to make sure the necessary marks are applied correctly. Then, we only add cells to the recalculation heap if they're marked necessary. In our burrito graph, if only Total</code> is part of the observed set, changing Salsa in Order</code> would not result in any walking of the graph, since only necessary cells are recomputed: </picture> This solves our problem without eagerly walking the graph to mark cells as dirty! We still have to remember that Salsa per Burrito</code> is dirty, since if it later becomes necessary, we will need to recompute it. But unlike Adapton's algorithm, we don't need to push this single dirty mark down the entire graph. anchors, a hybrid solution</h2> Both Adapton and Incremental walk the graph, even when not recomputing cells. Incremental walks the graph upstream when the set of observed cells changes, and Adapton walks the graph downstream when a formula changes. With these small graphs, it may not be immediately apparent that this graph walking is expensive. However, if your graph is large and your cells are relatively cheap to compute — often the case with spreadsheets — you'll find that most of your costs come from wasted graph walking! When cells are cheap, marking a bit on a cell can cost roughly the same as just recomputing the cell from scratch. So ideally, if we want our algorithm to be substantially faster than computing from scratch, we've got to avoid unnecessarily walking the graph as best we can. The more I thought about the problem, the more I realized that they waste time walking the graph in roughly opposite situations. In our burrito graph, let's imagine cell formulas rarely change, but we rapidly switch between first observing Total</code>, and then observing Salsa in Order</code>. </picture> In this case, Adapton will never walk the tree. No inputs are changing, and so we never need to mark anything as dirty. Since nothing is dirty, each observation is cheap as well, since we can simply return the cached value from a clean cell immediately. However, Incremental performs poorly in this example. Even though no values are ever recomputed, Incremental will repeatedly mark and unmark many cells as necessary and unnecessary. In the opposite case, let's imagine a graph where our formulas are rapidly changing, but we don't change which cells we're observing. For instance, we could imagine we're observing Total</code> while rapidly changing Burrito Price</code> from 4+4</code> to 2*4</code>. </picture> Just like the previous example, we aren't really recomputing many cells. 4+4</code> and 2*4</code> both equal 8</code>, so ideally we only recompute that one bit of arithmetic when the user makes this change. However, unlike the previous example, Incremental is now the library that avoids tree walking. With Incremental, we've cached the fact that Burrito Price</code> is a necessary cell, and so when it changes, we can recalculate it without walking the graph. With Adapton, we waste time marking Burrito Price w Ship</code> and Total</code> as dirty, even though the output of Burrito Price</code> won't have changed. Given each algorithm performs well in the other's degenerate cases, wouldn't it be ideal if we could just detect those degenerate cases, and switch to the faster algorithm? This is what I have attempted to do with my own library, Anchors</a>. Anchors runs both algorithms simultaneously on the same graph! If this sounds wild and unnecessary and overly complicated, that's probably because it is. In many cases, Anchors follows Incremental's algorithm exactly, which avoids Adapton's degenerate case above. But when cells are marked as unobserved, its behavior diverges slightly. Let's look at what happens. We start with marking Total</code> as observed: </picture> If we then mark Total</code> as unobserved and Salsa in Order</code> as observed, the traditional Incremental algorithm would alter the graph to look like this, walking through every cell in the process: </picture> Anchors also walks every cell for this change, but instead produces a graph that looks like this: </picture> Note the "clean" flags! When a cell is no longer necessary, we mark it as "clean". Let's look at what happens when we switch from observing Salsa in Order</code> to Total</code>: </picture> That's right — our graph now has no necessary cells. If a cell has a "clean" flag, we never mark it as observed. At this point, no matter what cell we mark as observed or unobserved, Anchors will never waste time walking the graph — it knows that none of the inputs have changed. Looks like there's a discount at El Farolito! Let's drop Burrito Price</code> by a dollar. How does Anchors know Total</code> needs to be recomputed? Before we recompute any formulas, let's look at how Anchors will see the graph right after we change just Burrito Price</code>, before recomputing anything: </picture> If a cell has a clean flag, we run the traditional Adapton algorithm on it, eagerly marking downstream cells as dirty. When we later run the Incremental algorithm, we can quickly tell that there is an observed cell marked as dirty, and know we need to recompute its dependencies. After that's finished, the final graph will look like this: </picture> We only recompute cells if they're necessary, so whenever we recompute a dirty cell, we also mark it as necessary. At a high level, you can imagine these three cell states form a looping state machine: </picture> On necessary cells, we run the Incremental's topological sorting algorithm. On unnecessary cells, we run the Adapton algorithm. burrito syntax</h2> I'd like to finish up by answering a final question: so far, we're been discussing the many problems the demand-driven model causes for our recomputation strategy. But the problems aren't just for the algorithm: there are syntactic problems to solve too. For instance, let's make a spreadsheet to select a burrito emoji for our customer. We'd write an IF</code> statement in the spreadsheet like this: </picture></div> Because traditional spreadsheets aren't demand-driven, we can compute B1</code>, B2</code>, and B3</code> in any order, so long as we compute our IF</code> cell after all three inputs are ready. In a demand-driven world however, if we can calculate the value of B1</code> first, we can peek at the value to know which of B2</code> or B3</code> we need to recalculate. Unfortunately, a traditional spreadsheet's IF</code> has no way to express this! The problem: B2</code> simultaneously references cell B2</code> and retrieves its value, 🥦. Most demand-driven libraries mentioned in this post instead explicitly distinguish between a reference to a cell and the act of retrieving its actual value. In Anchors, we call this cell reference an Anchor</code>. Much like a burrito in real life wraps a bunch of ingredients together, the Anchor<T></code> type wraps T</code> — which I suppose makes our vegi burrito cell Anchor<Burrito></code>, a sort of ridiculous burrito of burritos. Functions can pass around our Anchor<Burrito></code> as much as they'd like — it's only when they actually unwrap the burrito to access the Burrito</code> inside that we create a dependency edge in our graph, indicating to the recomputation algorithm that the cell may be necessary and need recomputing. The approach taken by Salsa and Adapton is to use function calls and normal control flow as a way to unwrap these values. For instance, in Adapton, we might write our "Burrito for Customer" cell something like this: let burrito_for_customer = cell!({ if get!(is_vegetarian) { get!(vegi_burrito) } else { get!(meat_burrito) } }); </code></pre> By distinguishing between a cell reference (vegi_burrito</code> here) and the act of unwrapping its value (get!</code>), Adapton can piggy-back on top of Rust's control flow operators like if</code>. This is a great solution! However, a little bit of magical global state is needed to correctly connect the get!</code> calls to the cell!</code> that needs recomputing when is_vegetarian</code> changes. The approach I've taken with Anchors, inspired by Incremental, is a slightly less magical system. Similar to a pre-async/await Future</code>, Anchors allows you to use operations like map</code> and then</code> on an Anchor<T></code>. For instance, the example above would look something like this: let burrito_for_customer: Anchor<Burrito> = is_vegetarian.then(|is_vegetarian: bool| -> Anchor<Burrito> { if is_vegetarian { vegi_burrito } else { meat_burrito } }); </code></pre> further reading</h2> In this already long and winding blog post, there is so much I didn't have space to talk about. Hopefully these resources can shed a little bit more light on this very interesting problem. Seven Implementations of Incremental</a>, a great in-depth look at Incremental internals, as well as a bunch of optimizations like always-increasing heights I didn't have time to talk about, as well as clever ways to handle cells that change dependencies. Also worth reading from Ron Minsky: Breaking down FRP</a>.</li> Salsa's explanation videos</a> explains how it works quite well.</li> This Salsa issue</a>, where you can watch Matthew Hammer, creator of Adapton, patiently explain cutoffs to some rando (me) who repeatedly fails to understand how they work.</li> Raph Levien's Rustlab keynote</a> has some really interesting stuff about this topic in the context of GUIs. In response to this post, he says How Autotracking Works</a> and Autotracking: Elegant DX Via Cutting-Edge CS</a> are great resources.</li> I have to admit I don't actually understand Differential Dataflow</a>, but it's the backbone of the Materialize</a> database. Query planning in general seems like maybe a solution to the big cache missing problems that many of these frameworks suffer from? It doesn't have built-in demand-driven computation, but Jamie Brandon (thanks!) kindly pointed me to their blog post Lateral Joins and Demand-Driven Queries</a> which explains how you can add demand as an input. Also of relevance is the Noira project</a> from MIT.</li> Adapton's documentation</a> is very comprehensive.</li> Turns out this way of thinking also applies to build systems</a>.</li> Slightly Incremental Ray Tracing</a> is a slightly incremental ray tracer written in Ocaml.</li> Just saw Partial State in Dataflow-Based Materialized Views</a> today and it seems relevant.</li> Gustav Westling (thanks!) pointed out Build Systems à la Carte</a> is one of the first papers about the similarities between build systems and spreadsheets.</li> Skip</a> and Imp</a> also look really interesting.</li> </ul> And of course, you can always check out the framework I built, Anchors</a>. Thanks to Syd Botz, Adam Perry, and Peter Stefek for feedback and discussion!

Invariant Lifetimes as Static, Unique Tokens

2020-10-12T00:00:00+00:00

Some of you may know I quit my job to work on a little text editor for fun. Unfortunately, in the process of doing that, I got distracted by the challenging problem of self-adjusting computation</a>. And unfortunately, to solve that problem in a performant way, you need really fast graphs, a notorious problem in Rust. And to get really fast graphs, I've found this cursed technique that takes advantage of Rust's lifetime rules and higher ranked trait bounds, which is what I'd like to talk about today. Beyond its dubious interpretation of variance, I'm proud to say this blog post represents an unprecidented achievement in yak-shaving for me, clocking in at four, maybe five levels deep. It's remarkable I'm even still using Rust — the traditional move at this deep level is to "realize" writing your own programming language is just the only reasonable way to build a text editor so you can finally write the code you wanted to write originally.
Let's first briefly talk about my experimental graph library, arena-graph</a>. To have fast edges in a graph, we want our nodes to have pointers that directly point to other nodes. My understanding is it's perfectly safe to cast a *const Node</code> to a &Node</code>, so long as the resource targeted by that raw pointer still exists, has not been moved, and will not be moved so long as &Node</code> exists. Arena allocation gives us these properties! We only store our *const Node</code> in places that will be dropped at the same time as the arena — either inside a node, or alongside the arena in the same struct. We also make sure any &Node</code> we hand out won't outlive the arena. This guarantees the raw pointers won't outlive the arena they point into.
However, there's still one problem. Let's say we have a set_parent</code> method like this:
impl TreeNode { fn set_parent(&self, new_parent: &TreeNode) { self.parent.set(new_parent as *const TreeNode); } } </code></pre> In this example, there's no guarantee that new_parent</code> is a TreeNode in the same graph as self</code>. If these two nodes are part of different arenas, new_parent</code> could be deallocated at a different time from self</code>, self</code> later goes to dereference its parent, and we've hit undefined behavior. To avoid this, we need to ensure new_parent</code> and self</code> are part of the same tree, so the tree's arena drops both nodes at the same time. One way to do this is to have TreeNode</code> have some sort of unique arena ID, and we could compare these IDs any time we add an edge from one graph node to another. This check is frustrating, though. If we're already going to all this trouble of avoiding slotmap-style checks, ideally we wouldn't have any checks at all, even when adding new edges. Another solution is we could just have the user promise they won't do this, but marking set_parent</code> as unsafe</code> will clutter up our users' code with countless unsafe blocks. What if instead, we could have the Rust compiler statically check that self</code> and new_parent</code> come from the same graph? The bet of this library is that you maybe can hack this in with Rust's lifetime system, if you can guarantee that:
When adding an edge from &'a TreeNode</code> to &'b TreeNode</code>, we ensure that 'a</code> and 'b</code> have exactly the same lifetime.</li>
If &'a TreeNode</code> and &'b TreeNode</code> came from different graphs, 'a</code> and 'b</code> will be different lifetimes.</li> </ul> To get these properties, we have to talk briefly about variance.A brief aside about variance</h2> The following code compiles</a>: #[derive(Debug)] struct NoClone(i32); fn main() { let num_1 = NoClone(1); let num_1_ref = &num_1; let num_2 = NoClone(2); let num_2_ref = &num_2; print_numbers(num_1_ref, num_2_ref); std::mem::drop(num_2); println!("{:?}", num_1_ref); } fn print_numbers<'a>(num_1: &'a NoClone, num_2: &'a NoClone) { println!("{:?} {:?}", num_1, num_2); } </code></pre> At first, this may seem weird. print_numbers</code> is asking for two numbers with the same lifetime, but the two numbers have different lifetimes — num_2</code> is dropped in main</code> before we print num_1_ref</code>. The answer is variance</a>. &'a NoClone</code> is covariant for 'a</code>, which has a complex type theory meaning but for our purposes means you can replace 'a</code> with any lifetime longer than 'a</code>. The two arguments passed into print_numbers</code> can have two different lifetimes, so long as both lifetimes last at least as long as the call to print_numbers</code>. However, the following doesn't compile</a>: #[derive(Debug)] struct NoClone(i32); fn main() { let num_1 = NoClone(1); let mut num_1_ref = &num_1; let num_2 = NoClone(2); let mut num_2_ref = &num_2; print_numbers(&mut num_1_ref, &mut num_2_ref); std::mem::drop(num_2); // delete this line to make it compile println!("{:?}", num_1_ref); } fn print_numbers<'a>(num_1: &mut &'a NoClone, num_2: &mut &'a NoClone) { println!("{:?} {:?}", num_1, num_2); } </code></pre> All we've changed here is switched print_numbers</code> to accept &mut &'a NoClone</code> arguments instead of &'a NoClone</code>. Why is this invalid? Well, we could add a quick line to print_numbers</code>: *num_1 = *num_2; </code></pre> In our main</code> function, this would update num_1_ref</code> to point to num_2</code>. Since num_2</code> is dropped before num_1_ref</code> is printed, this swap would cause undefined behavior, so the compiler is right to complain about this. How does lifetime variance prevent this second case, but allow the first one? &'b mut T</code> is (just like &'b T</code>) covariant for 'b</code>. However, it's invariant for T</code>, which means only and exactly a T</code> can be passed in. Since T</code> in this example is &'a NoClone</code>, our new print_numbers</code> requires the two &'a NoClone</code> to have exactly the same lifetime 'a</code>. Applying this to our graph</h2> We mentioned earlier we want our add edge method to have two properties: When adding an edge from &'a TreeNode</code> and &'b TreeNode</code>, we ensure that 'a</code> and 'b</code> have exactly the same lifetime.</li> If &'a TreeNode</code> and &'b TreeNode</code> came from different graphs, 'a</code> and 'b</code> will be different lifetimes.</li> </ul> To get the first property, we just need to make sure &'a TreeNode</code> is invariant for 'a</code>. To get this, we can use a PhantomData</code> and a wrapper struct: use std::marker::PhantomData; #[derive(Clone, Copy)] struct TreeNodeRef<'a> { inner: &'a TreeNode, mark_invariant: PhantomData<&'a mut &'a ()>, } impl <'a> TreeNodeRef<'a> { fn set_parent(self, new_parent: TreeNodeRef<'a>) { self.parent.set(new_parent.inner as *const TreeNode); } fn get_parent(self) -> TreeNodeRef<'a> { TreeNodeRef { inner: unsafe { &*self.parent.get() }, mark_invariant: PhantomData, } } } </code></pre> We still need that second property, though, where two trees always produce TreeNodeRef</code>s with different lifetimes. There's a lot here that won't work. For instance, this stripped down example initially appears to error correctly: use std::marker::PhantomData; #[derive(Clone, Copy, Debug)] struct TreeNodeRef<'a> { // inner node data ommited for brevity mark_invariant: PhantomData<&'a mut &'a ()>, } fn same_lifetime<'a>(a: TreeNodeRef<'a>, b: TreeNodeRef<'a>) { // two nodes have same lifetime; set recursive pointers here } struct Tree; impl Tree { fn root<'a>(&'a self) -> TreeNodeRef<'a> { TreeNodeRef { mark_invariant: PhantomData, } } } fn main() { let tree_1 = Tree; let root_1 = tree_1.root(); { let tree_2 = Tree; let root_2 = tree_2.root(); same_lifetime(root_1, root_2); } println!("{:?}", root_1); } </code></pre> This fails because root_1</code> and root_2</code> have different lifetimes. But move the creation of root_1</code> into the block, and we can get this to incorrectly compile: fn main() { let tree_1 = Tree; { let tree_2 = Tree; let root_1 = tree_1.root(); let root_2 = tree_2.root(); same_lifetime(root_1, root_2); } println!("{:?}", tree_1.root()); } </code></pre> Now root_1 and root_2 are created at the same time, and so share the same lifetime. How do we make this impossible? Initially it may seem we could use a closure to force the root()</code> calls to be in different scopes: struct Tree; impl Tree { fn with_root<'a, F: FnOnce(TreeNodeRef<'a>)>(&'a self, func: F) { func(TreeNodeRef { mark_invariant: PhantomData, }) } } fn main() { let tree_1 = Tree; let tree_2 = Tree; tree_1.with_root(|root_1| { tree_2.with_root(|root_2| { same_lifetime(root_1, root_2); }) }); } </code></pre> However, you'll find that this actually compiles! How is this possible? My understanding gets a little fuzzier here, but I'm pretty sure since with_root</code>'s &'a self</code> is covariant for 'a</code>, it allows the constructed TreeNodeRef<'a></code> to also have an arbitrarily long lifetime. How can we make this correctly error? Ideally we need some way to express that the FnOnce</code> passed to with_root</code> should not have a lifetime selected by the caller, but instead some unique lifetime determined by with_root</code>. Fortunately for us, Rust has a bit of magic called higher ranked trait bounds</a> that does exactly that: impl Tree { fn with_root<F: for <'any> FnOnce(TreeNodeRef<'any>)>(&self, func: F) { func(TreeNodeRef { mark_invariant: PhantomData, }) } } </code></pre> With the code above, our main</code> will correctly fail to compile, since root_1</code> and root_2</code> will be guaranteed to have different lifetimes. Why not Cell<&'a Node<'a>></code>?</h2> Some ppl construct graphs using a node that looks something like this: struct Node<'a> { parent: Cell<Option<&'a Self>> } </code></pre> While this has the advantage of not needing unsafe, it unfortunately means your graph struct has a lifetime in it: struct Graph<'a> { arena: Arena<Node<'a>>, } </code></pre> I've found that this lifetime gets in the way a lot, and results in unergonomic interfaces. It also means the Graph</code> can never be moved after a node is inserted, which is an unnecessary requirement, given how arena allocated nodes are always on the heap. Is this really a good idea??</h2> Sometimes we don't do things because they're good. We do them because they are bad. See also</h2> Just minutes after publishing this, I came across</a> Alexis Beingessner's thesis</a>, which describes this exact technique in section 6.3, although PhantomData<Cell<'a u8>></code> is used to make the lifetime invariant instead of my PhantomData<&'a mut &'a ()></code>. To quote Alexis: we really don’t recommend doing this </blockquote> I guess this is just one more post to add to the pile of evidence</a> that my blog is just a cheap ripoff of Alexis'</a>.
Identity Beyond Usernames 2020-07-07T00:00:00+00:00 In 2006, Robert Andersen sent the first tweet that @mentioned another user</a>, and an internet convention was born. In a world without smartphones, Twitter's primary interface was SMS. There were no threads, no @username autocomplete. If a user said something and you wanted to reply, your only option was to compose a new text to 40404, manually typing the @mention into your phone's SMS text box. SMS was also the origin of Twitter's original 140 character</a> limit: Twitter began as an SMS text-based service. This limited the original Tweet length to 140 characters (which was partly driven by the 160 character limit of SMS, with 20 characters reserved for commands and usernames). </blockquote> Also a holdover from the SMS days, Twitter does not allow any formatted or rich text. Users today work around this limitation by using the wide array of possibilities that Unicode affords. Text generators</a> convert ASCII characters into 𝔲𝔫𝔲𝔰𝔲𝔞𝔩 𝔘𝔫𝔦𝔠𝔬𝔡𝔢 𝔠𝔥𝔞𝔯𝔞𝔠𝔱𝔢𝔯𝔰. Memes take advantage of repeated spaces to position text, or to draw Unicode houses. (All of that is, of course, completely inaccessible to screen readers.) Emoji modifiers allow expressing a wide range of emotions with modifiers for skin tones and gender. Critically, this "plain" text is fully copy-pastable into any app with Unicode support. While many Twitter users from 2006 were likely limited to the GSM-7 encoding</a>, the limitations of the T9 keyboard</a>, and their phone's limited text rendering and shaping, modern users have found new ways to express themselves using the full Unicode character space. Nowadays, tweets, names, URLs, hashtags, basically everything can contain Unicode characters. Of course, everything except the @mention. Usernames on Twitter have more or less the same requirements as during the SMS era — up to 15 letters from a-z</code>, numbers from 0-9</code> and the underscore _</code>. This requirement is similar to many other websites: GitHub only allows alphanumeric characters and non-repeating hyphens, and Facebook allows just alphanumeric characters and the period. As we will see, this limitation is one of several problems with usernames. Unicode Usernames</h2> Imagine if instead of alphanumerics, GitHub allowed usernames to only be made up of the numbers 0-9</code> and Chinese characters. It would be pretty frustrating, right? If forced to use a system like this, we would likely ignore the Chinese characters, and just use the numbers as usernames. This is often what happens on social media platforms in countries that don't use Latin script. In China, the QQ instant messaging service (originally started in 1999) completely got rid of usernames used by similar services like AOL. Instead, each user is assigned a unique number, their QQ ID. This number cannot be chosen by the user, and is immutable. WeChat similarly assigns users a random number when they sign up, although it does allow each user exactly one opportunity to change it to an alphanumeric string of their choice. Typing long numbers isn't particularly ergonomic, which could help explain the widespread use of QR codes in China. Even in Latin-speaking countries, AOL-style usernames had issues. By requiring a username when logging in, and also requiring usernames to be unique among all users, users are often forced to use different usernames on different services, creating a second password that they had to memorize. Thankfully, most services have fixed at least this small problem by having login be email- instead of username-based. Throughout the world, usernames are alphanumeric only. Why can't we just allow Unicode, so that usernames could contain Chinese, Cyrillic, or other non-Latin alphabets? Unfortunately Unicode usernames have their own issues — just look at the largest username system in the world, the domain name system and the extension that allowed non-ASCII characters</a>. This was an essential upgrade, and yet it has inperfections, allowing the registration of websites</a> such as this one: This is latest Firefox, as of July 2020, displaying what appears to be "epic.com", the website of a large healthcare company. However, as you can see, the content is actually some random blog reminding people to drink water. How is this possible? If we stick the code into a Unicode character inspector, we can see what's going on: Byte-wise, the real "epic.com" and the false website "еріс.com" are completely different. But visually, they're indistinguishable from each other in the URL bar, allowing phishing problems to run amock. Unicode canonicalization and normalization</a> can help with certain cases of this problem, but does nothing for our epic.com example. This particular example isn't visible in Chrome, which instead shows https://xn--e1awd7f.com/</code>, the "punycode"</a> representation of the domain name. This is thanks to Chrome's complex, 13 step process</a> for detecting if a domain name is likely to be a Unicode phish or not. "Well, it may be complex," you tell me, "but at least it solves the phishing problem!" Unfortunately it does not. Specific instances of IDN homograph attacks have been reported to Chrome, and we continually update our IDN policy to prevent against these attacks. </blockquote> The Unicode spec is apparently too large to solve this problem 100% perfectly, and so their "solution" is to pay $2000 to anybody who finds new edge cases. This also doesn't actually solve the problem for non-Latin alphabets — if for example, I own a Chinese domain name, it will never show punycode, and attackers can phish my site using duplicate encodings for those Chinese characters. Chrome just attempts to solve the much smaller problem of the numerous Unicode characters that visually look like the Latin alphabet. This is probably frustrating to read, and you may want to point fingers at Unicode, for failing to provide canonical encodings for a series of graphemes. Or perhaps we can blame the domain name registrars, for allowing visually identical registrations. But I think the real culprit here is the incorrect assumption we Latin script users have when we build usernames into our systems. We assume that two visually-identical printed text tokens will have the same bytewise encoding. This is simply not true for a huge portion of computer users, and is a root failing with username-based systems today. The only solution is to develop systems that don't have usernames. Even in a trusted system with no bad actors, there is no guarantee a user retyping a non-Latin username from a printed document will end up with the same bytes as the original document. Changing Usernames</h2> Let's say you're building a site for English use only, and so even after reading all of this, you think perhaps it's ok to have usernames. After all, you'll probably find, like Twitter did, that this makes text entry for @mentions much simpler to implement. You get to use just a plain text field, instead of building an input field that can insert custom @mention objects. Unfortunately, you will still run into the issue of somebody changing their username. This is often an extremely complex problem. Take GitHub</a> for example. Changing your username there will redirect your old repository links to new ones. However, somebody else can come in and use your old username. What happens if they create a repo with the same name as your old one? If the new owner of your old username creates a repository with the same name as your repository, that will override the redirect entry and your redirect will stop working. </blockquote> URLs aren't the only place GitHub usernames are used. Using the web interface, in some cases, will create commits with the email myusername@users.noreply.github.com</code>. These commits will permanantly be disconnected from your account, unless you somehow are able to force push edited commit headers to every repository you've ever contributed to. Good luck with that. Instagram has issues with changing usernames, too. Up until 2015, updating your username would cause you to lose all your previous @mentions. They've since fixed this; old @mentions eventually update. Twitter supposedly will also preserve your replies, although my testing shows this is an unreliable feature at best. Updating the actual @mention as it's listed in the Tweet would have other issues, since if a user mentioned in a 280-character tweet adds 5 characters to their username, you'd suddenly get a 285-character tweet. Hope your Twitter clients can all support that. The final example of username switching pains I have is from my year at Google. I was fortunate enough to never switch my username, perfectly satisfied every morning when I opened my laptop and saw lard@google.com</code> on the login screen. But countless internal systems used by engineers there assume usernames are immutable, making a username switch a multi-day process that is never really complete. There is one easy "solution" to all of this, of course, which is to make it impossible to change your username. This is what gmail does</a>: If your account's email address ends in @gmail.com, you usually can't change it. </blockquote> I love the "usually". I guess in certain, mysterious cases it's possible to change it? In any case, making a random, numeric user ID immutable is fine. But if that user ID contains letters and is user-selected, making it immutable is an unacceptable solution for real-world situations. Whether it contains a user's deadname, or an old nickname they don't go by any longer, or even for those of us who, in sixth grade, decided "lordjubjub" would be an excellent and professional email address (just a hypothetical example, of course), usernames need to be editable. If they're editable, why not avoid all these username troubles and just go for a fully-Unicode, non-unique display name instead? Username Alternatives</h2> 250 million people have registered for Discord, a chat app similar to Slack or IRC. However, unlike Slack and IRC whose usernames are local to a particular server, Discord has just one server, and usernames are universal. With 250 million users in a single username space, collisions become a massive problem, finding short or reasonable usernames becomes nearly impossible, and you start to see users mass-registering accounts to sell the usernames for Bitcoin. To avoid all these issues, Discord dropped uniqueness requirements. Multiple users can all have the same username, although they aren't quite a display name, since a Discord-generated #1234</code> discriminator number appears at the end of usernames in certain contexts. This even allows them to have fully-Unicode usernames</a>; username phishing is less of a problem when users expect duplicate usernames, and none of your systems depend on username uniqueness. Slack went futher than this, and in 2017 decided to phase out usernames completely</a> in favor of display names only. Users @mention each other by typing an @</code>, a few characters of a person's name, and clicking on the dropdown. In some cases when there are duplicate display names, not selecting from the dropdown will result in an error: As a text editing engineer, I also can't help but look at this through the lens of text editing technologies. (Yes, that's right! It's always about text editing.) Usernames are a product of the text input and encoding systems used in decades past — just look at how Twitter's username needs were influenced by SMS protocols. The username advances made by Slack and Discord are only possible because they're able to build rich text editors (difficult with modern frameworks!</a>) that allow embedded, autocompleted @mentions that don't rely on the uniqueness of text tokens. You might be surprised just how much of the UI landscape is driven by these changes and advances in text editing. I've just got one final note: while they're extremely common, usernames are far from the only example of text as a unique token. JSON APIs use text tokens everywhere; we've only recently seen protocols with renamable fields like protobuf</a> and capnproto</a> gain popularity. Variables in programming languages are also common text tokens, and while arguably changing a name isn't a large deal for local variables, changing the name of a public class in most languages I know is a breaking change. Filesystem directories, too, are unique text tokens, and can suffer from naming conflicts where two bits of software have the same command name, or store their settings in the same directory. Proposing to get rid of variable labels or filenames may sound impossible, or wild, or unnecessary, but our industry's waning love for the username shows there are numerous benefits to avoiding text-based unique tokens. If we want to move onward from these limitations, we shouldn't look toward fixing the tokens themselves. We already know technically how to generate unique numeric identifiers, and we could easily just generate unique numbers for directories or programming language entities. Instead, Slack and Discord show us the main problem — plain text editing forces us to conflate our model of identity with our model for labels. It turns out this isn't a text token problem. It's a text editing problem. Text Editing Hates You Too 2019-10-28T00:00:00+00:00 Alexis Beingessner's Text Rendering Hates You</a>, published exactly a month ago today, hits very close to my heart. Back in 2017, I was building a rich text editor in the browser. Unsatisfied with existing libraries that used ContentEditable, I thought to myself "hey, I'll just reimplement text selection myself! How difficult could it possibly be?" I was young. Naive. I estimated it would take two weeks. In reality, attempting to solve this problem would consume several years of my life, and even landed me a full time job for a year implementing text editing for a new operating system. While on the job, I was lucky enough to learn from mentors1</a> who had tons of experience in this field. I heard many, many horror stories, including of one person maintaining a Windows application that had a custom text field implementation. They wanted to upgrade from the legacy Windows text input API to a newer version. Let's look at the interface list</a> for that newer version: That's right, the Windows text input APIs contain 128 interfaces. I'm pretty sure there are also eight (8!) different types of locks to fix concurrency issues, although I honestly haven't read their documentation, so don't quote me on that. Anyway, this engineer I heard about spent a year and a half (full-time!) attempting the upgrade, and in the end, their efforts ended in failure. They ended up staying on the legacy API. Text input is difficult. Alexis already touches on selection in a couple places, but as she mentions in her article, her experience is with working on text rendering. From the perspective of somebody who worked on the editing side of things, I have just a few points to add. Vertical Cursor Movement</h2> In this example, if the user presses up, the caret will go to the beginning of the line, before "hello". This is pretty reasonable so far. However, if the user presses up and then down, the caret will first jump before "hello", and then after the word "some". This may seem unintuitive. Why does it jump rightward? Well, each caret remembers an x-position in pixels that is used for vertical movements, and this position is only updated when the user presses left or right, not up and down. This is the same behavior that prevents carets from migrating left when vertically moving past short lines. Affinity</h2> Ok, so we now know that a text selection has two chunks of state, the byte offsets of its position inside the string and the x-position in pixels mentioned above. Problem solved? Well, no. Let's look at two caret positions on a very long line: Since "loooooooooong" is a single word, the two caret positions have exactly the same byte offset in the string. There's no newline character between them, since the line is soft wrapped. Our carets will need an extra bit that tells them which line to tend towards. Most systems call this bit "affinity". This same bit is also used in mixed bidirectional text, which we'll get to in a moment. Emoji Modifiers</h2> Let's say I'm sending a message to my friend. To emphasize my excitement, I want to add in a fun lil emoji. I fill a textarea with a thumbs up, the letter a</code>, and an emoji skin tone modifier. It looks like this: Whoops, I didn't mean to put the a</code> there. I position the caret after the a</code> and press backspace. What happens? I've seen several outcomes, depending on the editor. Bad #1 may look correct. But this is what happens in a text editor that has outdated emoji rendering support, like Sublime Text. This is bad because a light skin tone thumbs up emoji is encoded as the yellow thumbs up emoji immediately followed by the light skin tone modifier. Byte-wise, this should be rendered as a single emoji. Even if I copy-pasted one from another application, it would still be rendered incorrectly like this.</li> Bad #2 is what Chrome 77 does in the address bar. Not on web pages, just the address bar. This is not a rendering problem, since copy-pasting a emoji with a skin tone works. Instead, Chrome deletes the a</code>, and then noticing that the a</code> is modified by a skin tone, deletes the skin tone too. Whoops.</li> Bad #3 is "correct" according to the Unicode spec in that the two emoji merge into one. But it's pretty confusing for users, and bytewise, our caret has to move in order to not be stuck halfway inside a single emoji.</li> </ul> Those options are all bad, so you're probably hoping there's some fourth option. There is! Many editors, like TextEdit, won't even allow us to put a caret after the a</code>, since the skin tone modifier is treated as a single unit with its previous character. This makes sense in the emoji context, and even works alright for this a</code>. However, what happens when the emoji modifier is the first character on a line? The emoji modifier is now modifying the newline character. TextEdit won't let us place a caret at the start of the second line! I'd personally consider this solution "also bad". You also may have noticed that the thumbs up has switched to a thumbs down. I changed that myself to reflect my feelings about this whole situation. As an aside, TextEdit specifically makes carets on the first line very buggy. For instance, guess what happens if I press 4</code> here? Yup. You also may think there are spaces between those numbers. There aren't. Bidirectional Text</h2> Alexis mentions disconnected selections in mixed bi-directional text, like this example from TextEdit: This actually makes sense, since Arabic in strings is encoded from right to left, so this selection appears disconnected, but byte-wise represents a contiguous range of the string. This makes it a little surprising, then, that we can get this selection: Yes, that is a visually contiguous, byte-wise disconnected selection. Yes, this is bad. Some text editing engines do this when you select with the arrow keys instead of the mouse. The alternative is flipping left/right arrow keys inside the RTL range, which is also bad. There are no good solutions here. For extra credit, you can try to figure out what's going on here: I don't want to talk about that selection. Input Methods are a Thing</h2> The software that translates keypresses into input is called an "input method" or "input method editor". For the Latin alphabet used by English speakers, this isn't terribly interesting software, since each keypress gets directly mapped to inserting a single character. But quite a few languages have too many characters for a single keyboard, and so they need to get creative. For instance, with some Chinese input methods, the user types the pronounciation of what they're trying to say, and get a list of characters that match phonetically: This is sometimes called a composing region, and it often appears as underlined text. Sometimes the input method needs to style this region. This Japanese input method on Android, for example, uses background color to create a split suggestion region: (Thanks to Shae for the screenshot!) Do all these various highlight and compose ranges interact with bidirectional text? Let's not think about that. Input methods have to work everywhere, even inside a terminal: Nothing is actually sent to Vim until the Chinese character is selected from the list. You're probably thinking "but how would that work with Vim's command mode?" Not very well. This is why, on the web, text input and keypresses are separate events. Terminals conflate these two, causing problems. This is just one example of the many, many different ways that people input text. (Don't forget about non-keyboard methods like voice and handwriting input!) Fortunately for text field implementors, the operating system provides all these input methods for you. Unfortunately for text field implementors, you have to get your text field to speak the common text input protocol used by all these input methods. For Windows, that's those 128 interfaces listed at the beginning of this article. Other operating systems have simpler interfaces, but usually they're still tricky to implement. You also may have noticed that the input method is a separate process from our text field, and since both the input method and application can make modifications to the state of the text field, this protocol is a concurrent editing protocol. Windows solves this with its eight (8!) types of locks. Although holding a lock across process boundaries may sound questionable to you, most other platforms try to use imperfect heuristics to fix concurrency issues. Or they just hope race conditions don't happen. In my experience, prayers are not a very effective concurrency primitive. Why is this so complicated??</h2> Jonathan Blow, in a talk about how software is getting worse, points to the example of Ken Thompson's text editor</a>, which Ken built in a single week. Plenty of the code in this blog post is accidental complexity. Does Windows need 128 interfaces and 8 kinds of locks to provide text input? Absolutely not. Are the bugs we've found in TextEdit disappointing, and a result of a complicated editing model? Yes. Are the wealth of bugs in modern programs something we should be worried about? I'm worried, at least. But at the same time, Ken Thompson's editor was much, much simpler than what we expect from our text editors today. Unicode supports almost every one of the ~7000 living languages used around the world, and plenty more dead languages too. These use a variety of scripts, directions, and input methods that each impose tricky (and in some cases, unsolved) problems on any editor we'd like to make. Our editor also needs to be usable by vision-impaired folks who use screen readers. The necessary complexity here is immense, and this post only scratches the very surface of it. If anything, it's a miracle of the simplicity of modern programming that we're able to just slap down a <textarea></code> on a web page and instantly provide a text input for every internet user around the globe. ^{1 Thanks, as always, to Raph Levien and Yohei Yukawa, who taught me everything I know about text input. </div>} Hatched Icosahedron 2019-10-23T00:00:00+00:00

How to Recalculate a Spreadsheet

Invariant Lifetimes as Static, Unique Tokens

Identity Beyond Usernames

Text Editing Hates You Too

Hatched Icosahedron

Lord.io

A Programmer's Guide to Leaving GitHub

Lord.io

A Programmer's Guide to Leaving GitHub

Appendix E: Richard Stallman, "A Free Digital Society" (New York, 2014)</h2> </p>

How to Recalculate a Spreadsheet

further reading</h2> In this already long and winding blog post, there is so much I didn't have space to talk about. Hopefully these resources can shed a little bit more light on this very interesting problem.</p>

Invariant Lifetimes as Static, Unique Tokens

Applying this to our graph</h2> We mentioned earlier we want our add edge method to have two properties:</p> When adding an edge from &'a TreeNode</code> and &'b TreeNode</code>, we ensure that 'a</code> and 'b</code> have exactly the same lifetime.</li>

Identity Beyond Usernames

Text Editing Hates You Too

Hatched Icosahedron