Implement Knuth-Plass for text layout

[chris-morgan]

I have a project for which a better text layout algorithm than simple overflow wrapping is required, and limn may well be what I need for the project as a whole. In any case (whether I end up using it or not), it’d be nice to have Knuth-Plass as a wrapping option. This will necessitate things like a hyphenation crate and more flexibility, so if this went as a new variant on Wrap it’d probably need to have at least one additional field, for the hyphenator.

Being a comparatively heavy feature, this should be a Cargo feature which can be disabled (but enable it by default, I say).

I generally intend to implement this myself, but give no ETA. I have some bones of a Knuth-Plass implementation that used rusttype from a while ago, but it worked right up to the point where it gave the wrong results, and debugging it without being able to properly render its results was tricky. I’ll see what I come up with.

[christolliday]

So I just did some research into the state of text layout libraries, because I know there are a lot of missing features which should be supported and a general feeling that they would be better implemented outside of the core of limn. A lot of the missing functionality relates to properly handling non-latin scripts, which is a broader issue but should ultimately be supported.

It turns out what text_layout does (font + unicode in, glyphs and positions out) is actually usually called text shaping, at least in the terminology of Pango and HarfBuzz, which seem to be the most common cross platform libraries for this. Pango is higher level and is used by Gtk, and HarfBuzz is lower level and is used by servo and pango.

It would be nice to have a library in pure Rust, but it would be a huge project to reach feature parity with those libraries, and would be much better to develop it separately from limn.

I think ultimately limn will either replace text_layout with a dependency on Pango or HarfBuzz (probably Pango), or it will act as a wrapper around bindings to one of those libraries.

Anyway back to your original issue, do you know if using HarfBuzz or Pango implement Knuth-Plass or allow the control over hyphenation and line breaking that you need? I couldn't find much info on it after a quick look.

here are some related links that could be useful, for my own reference if nothing else
http://mces.blogspot.ca/2009/11/pango-vs-harfbuzz.html
https://en.wikipedia.org/wiki/Complex_text_layout
http://behdad.org/text/
https://www.microsoft.com/typography/otspec/ttochap1.htm
https://lwn.net/Articles/662569/

[jrmuizel]

HarfBuzz does not do any line breaking. Pango does but I'm not sure what algorithm it uses.

Chrome and Firefox both use HarfBuzz for shaping on all platforms. However to avoid creating a dependency on HarfBuzz it could be worth using the system libraries for shaping (CoreText on macOS, Uniscribe/DirectWrite on Windows and HarfBuzz on Linux)

[christolliday]

@jrmuizel thanks that's good to know, I guess you are in favor of also not depending on Pango for the sake of minimizing dependencies?

I agree it might be preferable also to use the native solutions over HarfBuzz to have fewer dependencies on some platforms, but it would be a pretty low priority for me. I'd like to avoid as much variability between platforms as possible, until limn is more mature at least.

@chris-morgan I just looked into the API for Pangos layout module and it's pretty similar to text_layout, I don't think it's a massive amount of code and doesn't have many more features, so it might be worth continuing to maintain the text_layout code and get it to parity with Pango layout. If that does happen it could make sense to add Knuth-Plass as an alternative line breaking algorithm. I'm not 100% sure yet though, want to do a little more research first.