KAS Blog

Please see outline on the left.

Why I created kas-text

September 2020

Existing libraries

This is going to be a very brief (and fairly naive) dive into text rendering and the state of available Rust libraries, written in easy English with minimal jargon.

The basics

Lets see. You're writing a small graphical game/tool/general UI and wish to print a simple string of text, say, "Hello World!" There are many APIs that can do this, but still several steps involved:

Selecting a font: this might be embedded or the app may try to discover a "standard" system font. The font-kit crate can discover system fonts.
Reading the font: there are a selection of libraries available, from the low level ttf-parser to the mid-level ab_glyph to more complex tool sets including font-kit, rusttype and fontdue.
Translating the input string to a sequence of positioned and scaled glyphs (layout): the above-mentioned font-kit, rusttype and fontdue can all accomplish this, along with the more specialised glyph_brush_layout.
Rasterising glyphs: this is the job of glyph_brush and, again, font-kit, rusttype and fontdue.
Integrating rasterisation with the graphics pipeline: e.g. gfx_glyph and wgpu_glyph do this job. Several high-level libraries (e.g. ggez and amethyst_ui) provide direct text support.

Of course, mostly you only need consider steps 1 and 5 and you're done.

Above, we considered only a short line of text: "Hello World!" Frequently you will have longer pieces of text that require wrapping (usually on word boundaries), and you may wish the result to be aligned to the left, centre or right, or even justified. Fortunately the above libraries already have you covered (aside from justified text, which is less often supported).

Text wrapping is a deceptively simple problem, but more on that in my next post.

Shaping

The above libraries all use a fairly simple layout system: match each char to a font glyph, place this at the previous glyph's "advance position", then if the font provides kerning data for this pair of glyphs use it to adjust the gap between the two. For English (and probably most languages) this is sufficient, at least most of the time.

Shaping allows more complex glyph selection and positioning, and is an important part of real text libraries. See e.g. HarfBuzz on shaping and Wikipedia on Complex Text Layout (although the latter also concerns bidirectional text; more on that later).

Essentially, shaping takes a text string along with a font and spits out a sequence of positioned glyphs. This means that replacing the basic layout system used above with a text shaper should, in theory, be straightforward.

For Rust, we have the HarfBuzz binding harfbuzz-rs, as well as two immature pure-Rust libraries, rustybuzz and allsorts. Of the general-purpose text libraries, only fontdue includes shaping in its roadmap.

Right-to-left and bidirectional text

Several scripts, such as Hebrew and Arabic, are written right-to-left. Supporting such scripts generally also requires supporting embedded left-to-right fragments, and thus requires supporting bidirectional texts.

Unicode, as part of TR9, specifies how to determine the bidi embedding level and thus the text direction for each character in the source text, as well as how to re-order the input from logical order into display order. Unfortunately, integrating support for bidi texts into layout is not so simple (this is most of the topic of the next post).

The unicode-bidi crate implements much of Unicode TR9, but on its own this is insufficient. None of the above libraries support bidirectional text.

Formatting

Formatting may apply one of several effects to text. These include:

adjusting the font size
changing the font's (foreground) colour
using a bold variant (or more generally, adjusting the weight)
using an italic variant (either via use of another font variant or via slanting glyphs during rendering)
drawing underline or strike-through

Some of the above font libraries have limited support for formatting specified via a list of text sections each with a font size and font identifier, and in some cases also colour information. The user is expected to translate formatted text from its source format as well as to select appropriate fonts.

Font properties and variable fonts

When mentioning font selection above, we glossed over a couple of issues. How does one select an appropriate italic or bold variant? Can these be synthesised if not provided?

The font-kit crate can help with the above: it allows font selection by family, weight and style. Some fonts are variable, meaning that glyphs can be synthesised to the required weight (giving much more control than simply "bold" or "normal"). The style allows selection of normal, italic (curved) or oblique (slanted) variants.

I have not investigated this topic, but it appears that only font-kit's rasteriser API supports selection of weight or style; all other Rust libraries select font only by path/bytes and variant index (for multiple fonts embedded in a font pack).

Font fallbacks

What if your chosen font doesn't include all required glyphs, e.g. if you choose a font covering most European alphabets, but your user starts writing Korean? I believe that no Rust libraries have even started trying to address this problem.

The first sub-problem is an extension of font selection: choosing appropriate fallback font(s). CSS allows the user direct control here: see article. On Linux this is usually handled by Fontconfig.

The other sub-problem(s) concern integration: breaking text layout into multiple runs should your shaper not support multiple fonts (as HarfBuzz doesn't), then stitching the result back together.

KAS-text

The above libraries cover simple layout and rasterisation fairly well, but also leave a lot out, especially regarding complex layout and use of formatted input texts.

KAS-text attempts to fill this gap: translate from a raw input text to a sequence of positioned glyphs, which can be easily adapted for use by renderers such as wgpu_glyph. Additionally, it exposes a stateful prepared::Text object, allowing fast re-draws and re-wrapping of a given input text (though this stateful API may not be appropriate for all users).

Since this article is written after-the-fact, kas-text v0.1 already exists. You can read its API docs here. v0.1 already supports shaping (via HarfBuzz) and bidirectional text, which, to my knowledge, makes it the first Rust library to support these features (on the full layout cycle from raw text input to positioned glyphs), admittedly with imperfections.

Near-future plans include support for formatted text, including translation from Markdown or (simple) HTML input and mostly-automatic font selection. Other topics, such as vertical text, font synthesis, font fallbacks and emoticons, have not been planned but could eventually be added.

KAS GUI

The v0.5 release of KAS has integration with KAS-text, including a reasonably functional multi-line text-editor. Check it out or run yourself:

git clone https://github.com/kas-gui/kas.git
cd kas/kas-wgpu
cargo run --example layout --features shaping

Line wrapping: the hardest problem in text layout?

September 2020

Obviously the title can't be true. Can it?

Unicode provides a ~~short~~ somewhat long technical report on line breaking. To quote from its overview:

Line breaking, also known as word wrapping, is the process of breaking a section of text into lines such that it will fit in the available width of a page, window or other display area. The Unicode Line Breaking Algorithm performs part of this process. Given an input text, it produces a set of positions called "break opportunities" that are appropriate points to begin a new line. The selection of actual line break positions from the set of break opportunities is not covered by the Unicode Line Breaking Algorithm, but is in the domain of higher level software with knowledge of the available width and the display size of the text.

To summarise, this algorithm tells us about mandatory breaks (e.g. after \n) and optional breaks (roughly speaking, the start of each word).

Fortunately for us, the Unicode Line Breaking Algorithm has already been implemented in Rust, by the xi-unicode library (from the same people as Xi Editor and Druid).

One foot in front of the other

glyph metrics

Lets start with the basics: horizontal, left-to-right text with simple layout. In this case, we use a caret starting at the line's origin. The first glyph is placed on this caret, then the caret is advanced by the glyph's advance width. The next glyph is placed similarly, except that if this pair of glyphs appears in the font's kerning table, then an offset is applied (this allows e.g. the 'T' in 'To' to hang over the 'o').

Line wrapping such text is simple: whenever the caret position extends beyond the available width, we back-step to the last optional line-break position, and line-break there. Well, not quite: we allow whitespace to extend beyond the line width (so if a bunch of extra spaces are inserted at the point a line is wrapped, they don't actually add space anywhere).

The above is what the glyph_brush_layout crate (of glyph-brush) does. It works fine for most left-to-right languages, provided no complicated layout is needed.

Actually, there is another point missing from this story: hyphenation. We leave this as a foot-note for now.

Shaping

Shaping was discussed previously and is an essential part of complex text support: the above advance-and-apply-kerning rules are insufficient for ligatures and entirely insufficient for complex texts like Arabic. A shaper is a separate tool which, given a sequence of (Unicode) text and a font, returns a list of positioned glyphs from this font. One such shaper is HarfBuzz.

Modifying our text layout system to support a shaper is not so hard (given a suitable design). Integrating line wrapping with an external shaper is only a little harder: the shaper returns a single line of text, within which we must track the positions of optional line-breaks.

KAS-text implements support for both simple layout (directly) and complex layout (via `harfbuzz-rs) within its shaper module.

Right-to-left and bi-directional text

This is where things start to get fun. When going left-to-right (hereafter LTR), we only need to implement the caret position. When going RTL, if only we could simply use the same logic but with flipped direction: alas, all font glyphs are positioned from the left, so we have to typeset them backwards.

Worse, RTL texts may embed short sequences (such as numbers) or even quote another language in the LTR direction — in some cases even embedding RTL text within LTR within RTL. Unicode TR9 specifies the Basic Display Algorithm, which essentially has three parts:

Split the input text into paragraphs (trivial).
Resolve embedding levels, where levels run from 0 to 125 and odd levels indicate RTL direction. This is complex but well specified and implemented by libraries such as unicode-bidi (albeit with bugs).
Re-order the text. This is complex and inseparable from line-wrapping.

To go into further detail, according to Unicode TR9, re-ordering text involves:

Split the input text into level runs: maximal sub-sets of characters with consistent embedding level.
For each level run, apply shaping to yield a glyph sequence.
Using the result of shaping, calculate line-wrapping positions.
For each line, apply a sequence of rules (L1-L4) to re-order characters on that line.

Unfortunately this leaves us a problem: we cannot resolve where lines start and end without first applying shaping, and we but are given a set of rules to re-order characters (i.e. Unicode code points) not glyphs. There are two ways of, er, "solving", this problem:

Apply shaping, calculate line-break positions, re-order (at char level), shape again. Not only does this require doing shaping twice, but further there is no guarantee that the result of doing so will still fit within our length bounds. Also, shapers like HarfBuzz expect text in logical order.
Transform the re-ordering logic to work with glyph sequences instead of characters. HarfBuzz has implicit support for RTL text, so we never re-order characters, but only runs and only then at embedding level 2 and higher.

Option (2) is now the obvious choice, but there are still several details to work out: line-wrapping both LTR and RTL text, correctly applying alignment, embedding LTR within RTL and vice-versa, and a few corner cases. Each line has a dominant (initial) direction (which may not be the same as the paragraph direction). On that line one may append a whole run (in either direction) or part of a wrapped line — but since the logical end of a line should not be in its middle we only allow line wrapping when the run direction matches the line direction. [This may need adjustment.]

Summary

As we have seen, line-wrapping is only a small problem within the scope of text layout, but surprisingly complex in practice due to its inherent inseparability from other aspects of text layout.

Easy Cast

Introducing: easy-cast.

Problem: correct casts aren't easy

Let me ask you, have you ever done this?


#![allow(unused)]
fn main() {
fn make_some_vec() -> Vec<u8> { vec![] }
let v: Vec<_> = make_some_vec();

// We need a fixed-size type (not usize), or just want to save space.
// We can assume length <= u32::MAX.
let len = v.len() as u32;
}

Of course, you could write this instead:


#![allow(unused)]
fn main() {
fn make_some_vec() -> Vec<u8> { vec![] }
let v: Vec<_> = make_some_vec();

// We need a fixed-size type (not usize), or just want to save space.
use std::convert::TryFrom;
let len = u32::try_from(v.len()).unwrap();
}

What about this?


#![allow(unused)]
fn main() {
let x: f32 = 1234.5678;

// Convert to the nearest integer, assuming it fits
let x = (x.round()) as i32;
assert_eq!(x, 1235);
}

Or this?


#![allow(unused)]
fn main() {
use rand_distr::{Poisson, Distribution};
let poi = Poisson::new(1e6_f64).unwrap();
let num = poi.sample(&mut rand::thread_rng());

// Note: u64::MAX as f64 rounds to 2^64, so we need to use < not <= here!
assert!(0.0 <= num && num < u64::MAX as f64);
let num = num as u64;
}

Or even this?


#![allow(unused)]
fn main() {
fn some_value() -> i32 { 0 }
let x: i32 = some_value();
let y = x as f32;
if y as i32 == x {
    println!("No loss of precision!");
    // WARNING: this test is WRONG since e.g. i32::MAX rounds to 2^31 on cast
    // to f32, then rounds back to i32::MAX on cast to i32.
}
}

Summary

It should be easy and safe to convert one numeric type to another, but frequently it's not:

Using x as T is easy but not safe: it may truncate, sign-convert, round, or saturate. (Before Rust 1.45.0 behaviour might even be undefined.)
Using T::try_from(x).unwrap() is clunky when you expect the conversion to succeed.
TryFrom doesn't even support float conversions.
Conceptually, "convert a float to the nearest integer" is a single operation, yet most solutions require separate rounding and conversion steps.

It turns out this is not an easy problem to solve in general. I wrote an RFC on this. Nearly three years and a long discussion later, it's still unsolved.

Existing solutions

The standard library provides:

From, but it only covers portably infallible conversions
TryFrom, but it misses float conversions and expects you to do your own error handling

There are existing libraries on crates.io, yet all of them fall short in some way:

num_traits::NumCast: API is not extensible to user types; error handling is the user's responsibility; it's a relatively big library if you just want casts
cast: different API for fallible and infallible conversions; API around isize and usize is platform-dependent; error handling is the user's responsibility

Introducing easy-cast

Eventually I gave up trying to find a standard solution and wrote my own, starting with one particular problem (converting between usize and u32 indices in KAS-text, which stores many text and list indices). This tiny beginning grew into the easy-cast library:

a From-like trait, Conv, for all integer conversions
direct support for float-to-int-with-rounding via ConvFloat
easier usage via the Cast trait (like Into)
try_cast and try_conv, allowing user error handling on all conversions
and of course a few bug fixes and diagnostic improvements

Examples

Now, we can revisit the above problems using easy-cast:


#![allow(unused)]
fn main() {
use easy_cast::Conv;

fn make_some_vec() -> Vec<u8> { vec![] }
let v: Vec<_> = make_some_vec();
// Expect success, panic on failure
let len = u32::conv(v.len());
}


#![allow(unused)]
fn main() {
use easy_cast::CastFloat;

let x: f32 = 1234.5678;
// Convert to the nearest integer, panic if out-of-range
let x: i32 = x.cast_nearest();
}


#![allow(unused)]
fn main() {
use easy_cast::CastFloat;

use rand_distr::{Poisson, Distribution};
let poi = Poisson::new(1e6_f64).unwrap();
let num = poi.sample(&mut rand::thread_rng());

let num: u64 = num.cast_trunc();
}


#![allow(unused)]
fn main() {
use easy_cast::Conv;

fn some_value() -> i32 { 0 }
let x: i32 = some_value();
match f32::try_conv(x) {
    Ok(y) => println!("{x} is exactly representable by f32: {y}"),
    Err(e) => println!("{x} is not representable by f32: {e}"),
}
}

For any integer x and any integer or float type T, we get:

T::conv(x)
x.cast() with type inference
T::try_conv(x) and x.try_cast() returning Result<T, Error>

And for any float value x and integer type T we have:

x.cast_nearest(), x.cast_trunc(), x.cast_floor(), x.cast_ceil()
T::conv_nearest(x), etc.
T::try_conv_trunc(x), x.try_cast_floor(), etc.

Don't need the fuses?

One of the design goals for easy-cast was check everything in Debug builds, maybe not in Release builds. In a Debug build, or when the always_assert crate feature is used, cast and conv will panic on inexact conversions. In Release builds without this flag, the cast reduces to just x as T.

The same is not true for try_cast and try_from which always fail on inexact conversions.

We may make some adjustments here in future versions, e.g. to use always_assert by default (but if so, it will be considered a breaking change).

Impl-tools: beyond derive

Allow me introduce the impl-tools crate, by discussing the limitations of #[derive].

Deriving `Default`...

... over a method

Frequently, a type's public API includes a fn new() -> Self constructor, with Default implemented over this. impl_default lets us skip some boilerplate:


#![allow(unused)]
fn main() {
use impl_tools::impl_default;

#[impl_default(Foo::new())]
pub struct Foo {
    // fields here
}

impl Foo {
    pub fn new() -> Foo {
        Foo { /* fields here */ }
    }
}

let foo = Foo::default();
}

... for an enum

Similarly, we can derive Default for enums:


#![allow(unused)]
fn main() {
#[impl_tools::impl_default(Option::None)]
pub enum Option<T> {
    None,
    Some(T),
}

// (Yes, the impl is correct with regards to generics — see below.)
let x: Option<std::time::Instant> = Default::default();
}

... with specified field values

Lets say we want to implement Default for a struct with non-default values for fields:


#![allow(unused)]
fn main() {
struct CarStats {
    num_doors: u8,
    fuel_is_diesel: bool,
    fuel_capacity_liters: f32,
}
}

Wouldn't it be nice to be able to specify our default values in-place? We can, if we re-write using impl-tools:


#![allow(unused)]
fn main() {
use impl_tools::{impl_scope, impl_default};

impl_scope! {
    #[impl_default]
    struct CarStats {
        num_doors: u8 = 3,    // specified default value
        fuel_is_diesel: bool, // no initializer: uses type's default value
        fuel_capacity_liters: f32 = 50.0,
    }
}
}

Note that field: Ty = val is not (currently) Rust syntax. The impl_scope macro has special support for this, besides other functionality.

Deriving `Debug`: ignoring hidden fields

For example, let us consider Lcg64Xsh32 (also known as PCG32). This is a simple random number generator, and as per policy of the RngCore trait, does not print out internal state in its Debug implementation.


#![allow(unused)]
fn main() {
#[derive(Clone, PartialEq, Eq)]
pub struct Lcg64Xsh32 {
    state: u64,
    increment: u64,
}

// We still implement `Debug` since generic code often requires it
use std::fmt;
impl fmt::Debug for Lcg64Xsh32 {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Lcg64Xsh32 {{}}")
    }
}
}

Using impl-tools we could reduce this to:


#![allow(unused)]
fn main() {
#[impl_tools::autoimpl(Debug ignore self.state, self.increment)]
#[derive(Clone, PartialEq, Eq)]
pub struct Lcg64Xsh32 {
    state: u64,
    increment: u64,
}
}

(This applies equally to fields which do not themselves implement Debug.)

Deriving `Deref`

How could we derive Deref and DerefMut? By using a specified field:


#![allow(unused)]
fn main() {
#[impl_tools::autoimpl(Deref, DerefMut using self.animal)]
struct Named<A> {
    name: String,
    animal: A,
}
}

Generics

An experienced Rustacean should know that #[derive] makes some incorrect assumptions with regards to generics. For example,

/// Implements Clone where T: Clone (correct)
#[derive(Clone)]
enum Option<T> {
    None,
    Some(T),
}

/// Implements Clone where T: Clone (unnecessary bound)
#[derive(Clone)]
struct Shared<T> {
    inner: std::rc::Rc<T>,
}

/// Attempts to implement Clone where T: Clone
/// (error: Clone for Cell<T> requires T: Copy)
#[derive(Clone)]
struct InnerMutable<T> {
    inner: std::cell::Cell<T>,
}

The #[autoimpl] macro takes a different approach: do not assume any bounds, but allow explicit listing of bounds as required.


#![allow(unused)]
fn main() {
use impl_tools::autoimpl;

// Note: autoimpl does not currently support enums (issue #6)

// No bound on T assumed
#[autoimpl(Clone)]
struct Shared<T> {
    inner: std::rc::Rc<T>,
}

// Explicit bound on T
#[autoimpl(Clone where T: Copy)]
struct InnerMutable<T> {
    inner: std::cell::Cell<T>,
}
}

To simplify the most common usage and to cover the case where multiple traits are implemented simultaneously, the keyword trait may be used as a bound:


#![allow(unused)]
fn main() {
use impl_tools::autoimpl;
#[autoimpl(Clone, Debug, Default where T: trait)]
struct Wrapper<T>(T);
}

Auto trait implementations

Lets say you write a trait, and wish to implement that trait for reference types:


#![allow(unused)]
fn main() {
trait Greet {
    fn greet(&self, name: &str);
}

impl<T: Greet + ?Sized> Greet for &T {
    fn greet(&self, name: &str) {
        (*self).greet(name);
    }
}

// Also impl for &mut T, Box<T>, ...
}

This can be quite tedious, enough so that macros (by example) are often used to deduplicate the implementations. But why should we have to write even the first implementation? It's all trivial code!


#![allow(unused)]
fn main() {
use impl_tools::autoimpl;

// One line to do it all:
#[autoimpl(for<T: trait + ?Sized> &T, &mut T, Box<T>)]
trait Greet {
    fn greet(&self, name: &str);
}

// A test, just to prove it works:
impl Greet for String {
    fn greet(&self, name: &str) {
        println!("Hi {name}, my name is {self}!");
    }
}
let s = "Zoe".to_string();
s.greet("Alex");
(&s).greet("Bob");
Box::new("Bob".to_string()).greet("Zoe");
}

Limitations

To conclude this article, let us briefly discuss limitations.

Support other standard traits: should be easy. #[autoimpl] currently supports only the most-frequently-used subset of traits supported by #[derive] (plus Deref and DerefMut). The crate should likely support everything that #[derive] does by default, and possibly more (see derive_more).

Extensibility: #[autoimpl] could be useful for user-defined traits; impl_scope could be useful for user-defined attribute macros. It would be nice if these could be extended in the same way as #[derive] is, but that is impossible (without direct support from Rust itself). Instead, the impl-tools crate is split in two: impl-tools-lib (contains all functionality) and impl-tools itself (just a thin proc-macro driver). An alternative driver containing additional functionality may be used instead of impl-tools. Exemplar: kas-macros (from v0.11).

KAS blog

KAS Blog

Why I created kas-text

Existing libraries

The basics

Wrapping and alignment

Shaping

Right-to-left and bidirectional text

Formatting

Font properties and variable fonts

Font fallbacks

KAS-text

KAS GUI

Line wrapping: the hardest problem in text layout?

One foot in front of the other

Shaping

Right-to-left and bi-directional text

Summary

Easy Cast

Problem: correct casts aren't easy

Summary

Existing solutions

Introducing easy-cast

Examples

Don't need the fuses?

Impl-tools: beyond derive

Deriving `Default`...

... over a method

... for an enum

... with specified field values

Deriving `Debug`: ignoring hidden fields

Deriving `Deref`

Generics

Auto trait implementations

Limitations