Open design decisions

[raphlinus]

After digging into various details, I find myself facing quite a large number of design decisions. I'm going to try to summarize them in an issue, and hopefully converge over the next few days.

Caching vs no-cache performance

One of the most fundamental architectural decisions is whether to address slow shaping performance by adding a word cache, or try to optimize performance in the no-cache case.

A cache is likely to have a good hit rate, however it is not without its own issues. A cache consumes memory, has concurrency issues, and will always be slower in the cold case. Further, the cost of hashing and comparing cache keys is nontrivial, especially as the cache key must incorporate all inputs that can affect they layout result.

Further, it's not obvious where the cache boundaries are. In #4, behdad points out that the HarfBuzz hb_ot_layout_lookup_collect_glyphs() call can determine whether space participates in shaping, and disable the word cache.

Precedents: Minikin and Firefox both use a word cache. Blink LayoutNG does not.

This still feels like a difficult question, but I am leaning toward exploring no cache and seeing how well that works.

Layout substring queries

#4 makes a very good point, that in a common paragraph layout task, there will in general be 3 layout operations on the same text - maximum intrinsic width, minimum intrinsic width, and lines based on actual line breaks. Android deals with this by relying heavily on the cache - the first layout operation should warm the cache for subsequent operations. As I commented in #4, an appealing alternative is to retain the layout along with enough information that layout of any substring can be queried, usually by reusing the existing layout, but doing relayout if the layout is invalidated.

I am not aware of any low level text API that has this substring query, though it would not be surprising if higher levels in stacks like CoreText and DirectWrite internally did something like this. For example, the DirectWrite TexttLayout object retains an entire paragraph, has methods such as min intrinsic width, and so it would make sense to retain a layout object that supports substring queries.

More recent versions of Minikin have a LayoutPieces API which might be a useful reference.

I am leaning for this type of API; the advantages seem pretty clear, and the complexity is manageable (better than many other approaches for improving performance).

Interning of style parameters

This is related to both above topics, especially caching. The complete cache key for a cached element is a large data structure (in Minikin it has 17 fields, some of which (the locale list) are themselves composite). It is likely that many layout operations will happen with the same style parameters. One approach to this is to intern the parameters. For maximum efficiency, the interned style would be exposed in the public API.

That said, it adds a lot of complexity, and interned styles would need lifetimes managed.

The substring query API would allow interning of style once per major query, and avoiding it for substring queries. This would simplify lifetime management (the style would be simply owned by the queryable layout result) and public API.

I'm now leaning against interning, especially exposing it through public API.

Shaper-driven vs coverage driven itemization

Minikin computes cmap coverage of fonts in a font list (using a sophisticated bitmap based data structure), and chooses the best-matching font for each character in the source text (I'm simplifying it slightly). An alternative is shaper-driven itemization, which is effectively iterating through all fonts in the list, asking the shaper to use each one, and stopping when there is successful layout.

Using the shaper to drive itemization is potentially more accurate than using Unicode coverage - among other things, the shaper can take Unicode normalization into account. For custom fonts, a strong argument can be made for letting the shaper drive the process.

For fallback fonts, the story is more complicated. For one, a typical fallback font stack is dozens of fonts; iterating through all of them might be quite slow. For two, platform access to the fallbacks varies. On Mac, you get a list of fonts (with priority order based on script list), but on Windows you basically get the one best-matching font for a particular string.

Should access to fallback fonts be the same interface on all platforms? The common-denominator interface is to pass in a string and get a font back (as this works on Windows). That API can be simulated on Mac and Android (I haven't carefully researched Linux yet), but requires logic to pick the font, most likely based on Unicode coverage. Otherwise, different interfaces can be provided on different platforms. Note: I think it should be a goal that custom fonts be itemized the same on all platforms; the differences should affect system fallbacks only (where it is by definition impossible to get cross-platform consistency).

A potential hybrid approach is to use different tactics depending on script. For some scripts (most languages that have coherent blocks in Unicode), the script should be enough information to choose a font, or to exclude it from consideration. For others (latin, common, and symbols) the story is more complex. We could use script to winnow the list down, then apply shaper driven itemization.

Font matching in font-kit vs skribo

This is basically a question of where to draw architectural lines between font-kit and skribo. Right now, it seems we should iterate the design of the two crates together.

Right now font-kit has a matching algorithm. This should probably be expanded to support fallback. That's a fairly major increase in API surface, and means a lot of the work of itemization will likely happen in font-kit, as well as likely access to data such as faux style synthesis. I don't see that as a bad thing.

Moving matching to skribo is conceptually appealing, but requires designing an API in font-kit that exposes all necessary information up to the higher level. That might be practical, but I don't immediately see how to do it.

Abstraction for platform low-level text?

The original design brief for skribo calls for an abstraction so that it can either do its own layout, or depend on the platform text stack. I'm now questioning whether this is a good idea; the abstraction should likely happen at the higher level, and skribo's scope should be be strictly cases where it does the layout itself. This simplifies the design, and obviates whether a "skribo but no font-kit" configuration should be supported.

That said, as pcwalton has said it might make sense to split out some data types (especially style representation) so that they can be in common between skribo and a future high-level text abstraction.

[RazrFalcon]

I've tried to implement a simple shaper-driven itemization using fontconfig, but immediately stumbled on a lot of problems.

My algorithm is pretty simple:

• Shape a string using harfbuzz.
• Check for missing glyphs.
• Detect their scripts.
• Query fonts for each script via font-kit.

So all I need is a font-kit method like:

Source::select_by_script(script: unicode_script::Script, properties: &Properties) -> Result<Handle, SelectionError>

The problem is that fontconfig doesn't support this at all. I can query a font by lang and by charset.

lang is fontconfig's own languages/scripts/whatever list, which doesn't map on Unicode Script, or locale, or anything. Qt, for example, uses it's own Unicode Script list, that it calls WritingSystem and it matches it with fontconfig's lang manually. So if we want to match Unicode Script with lang than we have to do this ourselves.
Also, lang is a sort of simplified. For example, Han, Hiragana, and Katakana in fontconfig is just ja.

We can also use charset, which basically checks that font has the specified code point. But I'm not sure how correct it is. Also, querying fonts for each code point will be way slower than by lang/script and redundant.

I didn't look into DirectWrite and Core Text yet.

Also, I saw your attempt to add get_fallback to font-kit, but I don't understand how it works. It returns only one font, but what if a string has like 5 different scripts and needs 5 different fonts (in worst case scenario)?