shaping: implement line wrapping

[whereswaldon]

As promised, here's the line wrapping algorithm that currently powers Gio's usage of our typesetter. Please note that I'm not married to the names of symbols in this API, and that nothing is exported right now because I'm not entirely certain what we want to expose.

One detail that I want to call attention to is the output type. It wraps our Output with information about which runes of input correspond to the output. This information was critical for me to be able to correctly map sequences of glyphs to runes in Gio's text editor. I'm happy to change types around, but I want to preserve that somehow. Maybe the right way is simply to add the fields to the normal Output type.

I've tried to frame line wrapping as a simple yes/no decision problem in this implementation. The function shouldKeepSegmentOnLine is that decision. In English, the decision is "should I keep the segment from the current line segment to the given line-break candidate on this line? (given some space constraints)". The decision itself can be made much smarter (it doesn't even break on non-word boundaries right now), but it seems like it might be a good starting point.

The lineWrap function is the real entry point into all of the logic. It's not currently exported because I'm not sure it's the interface we want to export.

I should also note that this simple strategy does not handle the following:

• does not currently enforce mandatory UAX#14 breaks, though it has the information necessary to do so.
• does not check for harfbuzz unsafe to break markers on the glyph clusters adjacent to break candidates

It does, however:

• reject line break candidates that would break a harfbuzz cluster
• properly break RTL and LTR text

~As for the many lines of new go.sum, I'm hoping we can do something about that.~ I've pushed an update that switches to a zero-dep implementation of UAX.

I welcome your thoughts as you have time to look at it!

[benoitkugler]

I'm starting to dig deeper in this PR; thanks for this large work ! One of my first impression is that we should handle the case of wrapping a multi-Output. I've two use cases in mind :

• A line of text with mixed (say) Latin and Arabic will be segmented in two Inputs, yielding two Outputs, but line wrapping needs both Outputs, right ? Unless there is a way to call lineWrap on each Output, adjusting maxWidth, but it feels a bit clunky.
• Similarly, a RTL text embedded in a LTR will yield two (or more) Outputs

What do you think ? We perhaps should use of a new type representing this new level of abstraction : Output is a single run in a line, it is linked to Harfbuzz requirements, and the new type, say LineOutput, would basically be a slice of Outputs, representing a line of text (before line wrapping). Then lineWrap acts on LineOutputs rather than single Outputs. I've not thought of the complication in lineWrap though...

[whereswaldon]

What do you think ? We perhaps should use of a new type representing this new level of abstraction : Output is a single run in a line, it is linked to Harfbuzz requirements, and the new type, say LineOutput, would basically be a slice of Outputs, representing a line of text (before line wrapping). Then lineWrap acts on LineOutputs rather than single Outputs. I've not thought of the complication in lineWrap though...

Hi @benoitkugler , I totally agree that the desired final behavior is having the line wrapper accept []shaping.Output and return []shaping.Output. However, that's yet another hike in complexity. The approach that I've taken is to tackle the simpler (but still hard) case of wrapping a uniform run of text correctly (based on its direction), and then we can look to upgrade to wrapping multiple outputs. Would you be okay reviewing this with the lens that it is only attempting to implement that simpler case?

[benoitkugler]

Would you be okay reviewing this with the lens that it is only attempting to implement that simpler case?

Sure ! Not exporting the current symbols makes a lot of sense then. The current tests will also be very helpful when trying to upgrade to multi-output (because such a change should not change the results for one output.)

[whereswaldon]

@benoitkugler Thanks a bunch for the review. I've adopted your requested changes, and I've also pushed some work I had locally that (I think) further simplifies things. The line break candidates are now generated iteratively as needed instead of up-front. This should allocate less memory and be a little easier to think about.

I also fixed a bug in the tests (there's a separate PR with just that fix available in #22 ) and updated the Go versions we use in CI to ones that support math.MaxInt (1.17+).

[whereswaldon]

I think I'd really like to unify output and Output. The rune range seems (to me) to be a totally reasonable thing to include. Thoughts?

[benoitkugler]

I think I'd really like to unify output and Output. The rune range seems (to me) to be a totally reasonable thing to include. Thoughts?

Yes, good point, let's do it.

[whereswaldon]

I think I'd really like to unify output and Output. The rune range seems (to me) to be a totally reasonable thing to include. Thoughts?

Yes, good point, let's do it.

Done!

While we're at it... Maybe we should export the shapedParagraph type (call it just Paragraph or something?)? It seems like an okay starting point for a public API. I think it will definitely need to change, but it's usable as-is.

You just do:

// assume we have input
var input shaping.Input
shapedOutput, err := shaping.Shape(input)
if err != nil {
    // handle
}
lines := shaping.NewParagraph(shapedOutput).LineWrap(width)

Alternatively, we could expose a package-level LineWrap function that internally uses the shapedParagraph type.

[benoitkugler]

Exposing a Paragraph type seems okay to me. I think it could later be the place to put options influencing line breaking like hyphenation. As you said, it is definitely a good starting point.

By the way, have you already started to think about the multi input/output case ? Or do we remain focused on the single input case as you proposed earlier?

[whereswaldon]

Exposing a Paragraph type seems okay to me. I think it could later be the place to put options influencing line breaking like hyphenation. As you said, it is definitely a good starting point.

On second thought, I think we should call it a Wrapper or perhaps LineWrapper and surface a WrapParagraph method. I think those names match slightly better with what we already have. Later we could add a WrapLine to support the "I only want N lines" usecase that pango can't handle.

By the way, have you already started to think about the multi input/output case ? Or do we remain focused on the single input case as you proposed earlier?

I've thought about it quite a bit, and I think I have a good idea how to go about it. However, it's a pretty involved change to a bit of code that took me nearly a month to get right, so it's not trivial. That's why Gio is raising funds to support the effort. The biggest/hardest change to support Gio gaining font fallback is updating the line wrapper to support multiple heterogeneous shaping.Outputs as input.

[whereswaldon]

I've pushed a minimal exported API like what we discussed, but I don't have strong opinions about the symbol names or structure.

[benoitkugler]

@andydotxyz I share your concern about the dependency on uax. I'm working on a drop in replacement, taking inspiration from its nice API but also from what I've learned studying Pango stack. I need to work on some edges cases, but I'm hoping to propose a PR soon (with more context of course)

[benoitkugler]

@whereswaldon indeed, the names are better, thanks !

[whereswaldon]

@benoitkugler can you elaborate on your concerns with the UAX repo? It's license compatible, (now) zero new transitive dependencies, maintained (albeit by different people), very thoroughly tested, and optimized. We currently need only UAX#14 (line breaking), but we will need UAX#29 (grapheme cluster breaking) in order to properly break within words when we add that feature. I think the existing bidi segmentation algorithm in there may also be a good starting point for us when we try to support that, though I've been less focused on that case.

I'd rather see us improve using it as a starting point than redo all of the work. We can even move that repo into go-text. That being said, I don't yet know where your concerns are coming from. Perhaps you will change my mind. :D

As for the API and the lessons you learned from pango, I'd like to hear more. There are actually things I'd love to change about the UAX API.

[whereswaldon]

This is obsoleted by #25