Minikin Retrospective

There’s a lot of new interest in open source text layout projects, including cosmic-text, and the parley work being done by Chad Brokaw. I’m hopeful we’ll get a good Rust solution soon.

I encourage people working on text to study existing open source code bases, as much of the knowledge is arcane, and there is unfortunately no good textbook on the subject. Obviously browser engines facilitate extremely sophisticated layout, but because of their complexity and the constraints of HTML and CSS compatibility, they may be hard going. The APIs of DirectWrite and Core Text are also worthy of study, but unfortunately their implementations remain closed.

An interesting codebase is Minikin. It powers text layout in the Android framework. I wrote the original version starting back around 2013, but it is since maintained by the very capable Android text team.

A bit of additional context. The design of Minikin was constrained by compatibility with the existing Android text API (mostly exposed through Java, though these days there is a nontrivial NDK surface as well). There is a higher level layer, responsible for rich text representation, editing, and other things, while Minikin is the lower level that powers that and does shaping, itemization, hit testing, and so on. (See Text layout is a loose hierarchy of segmentation if these terms are unfamiliar). For the most part, the interface between the higher and lower levels is runs of text. Line breaking is an interesting case where the responsibility for crossing levels is shared across the layer boundary. For the most part, the higher level iterates its own rich text representation and hands runs to Minikin.

A special feature of Minikin is its optimized line breaking algorithm, strongly inspired by Knuth-Plass. This was motivated largely by the need to handle small screens better, but has some tweaks to make it even better for mobile. The heuristics try not to place a word by itself on the last line, and in general try to balance line lengths. Line breaking generally follows ICU rules, but does special case email addresses and URLs, as those are very common on mobile and the ICU rules work poorly.

There’s also fun stuff in there for grapheme boundaries, deciding between color and text emoji presentation forms, and calculating exactly what should be deleted on backspace (the logic for that is surprisingly complicated and as far as I know has not been written down anywhere).

Much of the internal structure of Minikin is dedicated to itemization, which is done largely on the basis of the cmap coverage of the fonts in the fallback chain. Doing that query font-by-font for every character would be expensive, so there are fancy bitmap acceleration structures. A good, general, cross-platform way to do itemization and fallback is a hard problem, but I think this solution works well for Android’s specific needs.

While there’s unfortunately no excellent documentation on Minkin’s internals, there are some resources, and part of the purpose of this blog is to point people to them. I’ve just gotten permission to publish the Project Minikin slide deck from 2013 (PDF), which explains the motivation and some of the early design ideas. There’s also an lwn article which goes into some detail, largely based on my 2015 ATypI talk (video, slides).

Flutter’s LibTxt was originally based on Minikin, but no doubt has diverged considerably since then, as they have fairly different requirements and of course are not bound by compatibility with Android.

But if you have deep interest in this, I recommend studying the code, as that’s the ultimate source of truth. It’s extremely fortunate that Android’s open source development model gives us access to it!

If you have questions, let me know (an issue on this repo is a good way, or you can ask on Mastodon), and I’ll do my best to answer.

from Hacker News https://ift.tt/cYzxd20