Is there a way to use textwrap with a font-sepecific line measure

[NeverGivinUp]

SVG does not wrap text. (SVG2 does, but the specification is years from being finished.)

I'm considering wrapping text for SVG in web browsers.

• In SVG the length depends on the font (and it's formating, as in bold, italics, subscript, etc). So textwrap would need to use the browser's measure function. Is that possible? Is there an example for it?
• How would that work with regard to speed (assuming I need to wrap about 5000 Texts of about 250 characters)
• How much code and data would I add to my app, using textwrap and the crates it depends on -- the language specific dictionaries not excluded.

[mgeisler]

Hi @NeverGivinUp,

Great questions! In short, yes, you can use textwrap to wrap more than just terminal text. I made a crazy example here were I use the wrap_first_fit function to create a daily schedule by stuffing "tasks" into "days".

Put differently, the core wrapping code does not know about "words", it knows about Fragments. A fragment is the smallest wrappable unit in textwrap. For text, it corresponds to a word: a Fragment has a width, a width of the trailing whitespace, and a width of a penalty which is inserted if the word ends a line. Here is an example:

    let text = "Hello World!";
    println!(
        "{:?} -> {:#?}",
        text,
        textwrap::core::find_words("Hello  World!").collect::<Vec<_>>()
    );

If you run this on the playground, you'll get

"Hello World!" -> [
    Word {
        word: "Hello",
        width: 5,
        whitespace: "  ",
        penalty: "",
    },
    Word {
        word: "World!",
        width: 6,
        whitespace: "",
        penalty: "",
    },
]

The Word struct implements the Fragment trait. The penalty field is empty here, but it would be "-" if you use the hyphenation crate to do automatic hyphenation. You could then end up with words like this:

[
    Word {
        word: "Hel",
        width: 3,
        whitespace: "",
        penalty: "-",
    },
    Word {
        word: "lo",
        width: 2,
        whitespace: "",
        penalty: "",
    },
]

This simply says that we can break "Hello" as "Hel-" and "lo". The - is then only taken into account if the word is at the end of the line.

For your purposes, you would need to make your own struct which implements Fragment. Your struct would need to carry the width of your breakable unit of text — the width should be computed somehow by taking the formatting into account. You also need the trailing whitespace and

• How would that work with regard to speed (assuming I need to wrap about 5000 Texts of about 250 characters)

The best you can do here would be to clone the repository and run cargo criterion (from https://github.com/bheisler/cargo-criterion). That will tell you how fast you can wrap strings of various lengths. When I benchmark wrapping strings of length 400 characters, i get

% cargo criterion optimal_fit/400
    Finished bench [optimized] target(s) in 0.05s
String lengths/fill_optimal_fit/400
                        time:   [18.150 us 18.551 us 19.052 us]

In other words, finding words wrapping them and turning the result into a String takes about 18 microseconds. So wrapping 5k such strings might take around 92 millisecond. Your results will be slower since you will need to do more work to measure your text — console text is pretty fast to measure.

• How much code and data would I add to my app, using textwrap and the crates it depends on -- the language specific dictionaries not excluded.

All dependencies are optional, so you can simply disable them with:

[dependencies]
textwrap = { version = "0.13", default-features = false }

This just gives you the core wrapping logic. This code is honestly not rocket science, but it might be an advantage that it provides a battle-tested structure for you to plug your own logic into.

What kind of constraints do you have for your application which makes it important if you depend on a few KB more or less?

[mgeisler]

Please also see the discussion with @truchi here: #300 where we discussed using textwrap to deal with colored text in a terminal. The theme is the same: wrap some text with more information than just the text.

[NeverGivinUp]

Thanks a lot for the detailed explanations and the cute house building example , @mgeisler :)

Allow me to clarify some the problem and some resulting requirements:

Application size

My app runs in the user's web browser, which may be a mobile phone. Application size matters, because the app needs to be downloaded to the browser from the server. Possibly over a 2G or 3G phone connection.

If we are taking about a few KB more or less, that is still fine. I was worried that hyphenation might use the order of magnitude of hundreds of KB or even some MB, which would rule out text wrapping in SVG.

Runtime

The app lays out a potentially big graph of tweet-sized text nodes (so 300 characters). To keep the layout visually smooth, the app must lay out the whole graph before it presents it -- even if it starts by presenting only a dozen nodes initially. To lay out the graph, the app must know the sizes of all nodes. The text of all nodes must be wrapped before the graph layout can be computed.

My speed question really is about the number of calls to the measurement method: Is it called for each fragment, for each fragment and combination of a word, for each fit-test? Does it differ by language? E.g. for Arabic which, to my very limited knowledge, can combine letters to complex glyphs? So assuming that the measurement method runs in linear time -- it takes x*n seconds to measure a text of n characters -- how long will text wrapping with hyphenation take?

Measurement

Hyphenation and variable width fonts are necessary for putting the maximum amount of text in a given space -- at any given font size. Using super- and subscripts is essential for clear differentiation of content and notes. For text-fitting it can be considered equal to using smaller font size for some characters than for others. So we are dealing with text, set in variable width fonts, set in variable font sizes and with variable font weights.

textwrap clearly solves the hyphenation problem (though I do not know at what cost yet).

The Fragment trait deals with integers. However, the length of text is a floating point number. It cannot be converted to integers without a serious loss of precision. Thus we'd need a different trait, say VariableFragment that returns floating point values.

Non-separatables

Super- and subscripts must not be separated from the words before them. Can you give an example/inspiration on how to communicate that to hyphenator and the textwrapper?

[mgeisler]

Hi @NeverGivinUp, thanks for the background information!

My speed question really is about the number of calls to the measurement method: Is it called for each fragment, for each fragment and combination of a word, for each fit-test?

This is basically up to you.

As an example, the textwrap::wrap function (which is only for console text), will split the text on space characters and measure display width of each fragment. The width here means the column width if printed in a terminal (see core::display_width). It then uses wrap_optimal_fit or wrap_first_fit to wrap the fragments into lines, and uses these lines to cut apart the original input string so we can return a Vec<Cow<'_, str>> to the caller. The Cow<'_, str> type lets us return borrowed lines when possible (it is possible if the wrapped line is a substring of the input). We return an owned line if the wrapped line is not a substring, i.e., if a '-' has been inserted. This only happens if you use the hyphenation feature or if you add indentation.

The sketch in textwrap::core outlines the wrapping process — the top-level textwrap::wrap function is built on the functions in textwrap::core.

Does it differ by language? E.g. for Arabic which, to my very limited knowledge, can combine letters to complex glyphs?

For console text (which is not your use case), the text is not measured differently depending on the language — the display_width function simply assigns a width to each Unicode character. Put differently, textwrap does not have access to font-specific information.

So assuming that the measurement method runs in linear time -- it takes x*n seconds to measure a text of n characters -- how long will text wrapping with hyphenation take?

The time complexity of wrap_optimal_fit and wrap_first_fit is O(n) where n is the number of fragments you need to wrap. As mentioned above, a fragment is roughly equivalent to a word: an unit which you don't want to break any further. You should be able to measure the width of each fragment in time linear in the number of characters in a fragment, which makes the overall wrapping take linear time in the length of your input.

---

textwrap clearly solves the hyphenation problem (though I do not know at what cost yet).

This is done outside of the main wrapping code, see the WordSplitter trait. The hyphenation is done by the hyphenation crate, which knows how to split a word into syllables. I believe this is also a linear time operation.

The Fragment trait deals with integers. However, the length of text is a floating point number. It cannot be converted to integers without a serious loss of precision. Thus we'd need a different trait, say VariableFragment that returns floating point values.

Yes, you're right, this is not super nice for variable width fonts! I've been playing with rendering text on a HTML canvas, and I simply worked around this by multiplying the width of each fragment by 10 or 100. Could you try this as a work-around? You'll of course also need to multiply the line width by 100 in this case.

I'll be happy to make this more flexible in the next version, I suppose the type of the widths could be generic. For terminal applications, a u16 should be enough since the syscalls which reports the terminal size deals in u16. So many command line applications could save memory by packing the fragments denser than today.

Another problem I found by scaling up the fragment widths is that the defaults used by wrap_optimal_fit don't work any longer. The function looks at all possible ways of breaking the lines and selects the one which minimizes a set of penalties — all to find line breaks which give a nice even right margin. The current penalties work when the line width is in the range 100 or so (which is what you get when you count columns). If you instead use the actual width in pixels, you're likely to get line widths in the order of 500-1000.

Be sure so select the wrap_first_fit function in this case since it doesn't use the penalties.

---

Super- and subscripts must not be separated from the words before them. Can you give an example/inspiration on how to communicate that to hyphenator and the textwrapper?

You would need to take this into account when you form your fragments. For console text, we simply split on ' ', so any super- and subscripts will naturally be put together with the word immediately before them.

[NeverGivinUp]

This all sounds very good. Thanks a lot :)

I will try using multiplied values for a start. But generifying clearly is the superior solution, that does not add artificial inaccuracies to the measurements.
The wrapping algorithms wrap_first_fit and wrap_optimal_fit expect line_width closures that return a usize. That would need to be generified as well.

Regarding the constants:
I don't know if OVERFLOW_PENALTY could really work. In the simplest case it would become a function of the character, which basically returns its width in the given font. The algorithm would multiply it by an overflow penalty weight and then square it to get the penalty. That closure could cache the width, so it wouldn't be much slower than the constant. However if that width varies depending on the following character, a more complex solution would be necessary. The HYPHEN_PENALTY really is just a special case of the OVERFLOW_PENALTY, isn't it?
You could provide a default closure, that always returns 1.

[mgeisler]

I will try using multiplied values for a start. But generifying clearly is the superior solution, that does not add artificial inaccuracies to the measurements.
The wrapping algorithms wrap_first_fit and wrap_optimal_fit expect line_width closures that return a usize. That would need to be generified as well.

Yes, I agree! As you can tell, Textwrap is born out of the world of terminal text. It was only with version 0.13 that it became possible to wrap other things via custom Fragment implementations.

I've just put up #310, which contain an example of using Textwrap for wrapping text with f64 widths. The text in question is drawn on a HTML canvas using WebAssembly — the result is live at https://mgeisler.github.io/textwrap/.

I'll flesh out #310 a bit more before merging it, but in short, I reimplemented the relevant parts of textwrap::wrap and reused the find_words function to do the splitting of the text. Instead of returning a Vec, the words are painted onto a canvas. You can see the multiplication hack I spoke about above:

#[derive(Debug, Copy, Clone, PartialEq)]
pub struct CanvasWord<'a> {
    word: &'a str,
    width: f64,
    whitespace: &'a str,
    whitespace_width: f64,
    penalty: &'a str,
    penalty_width: f64,
}

const PRECISION: usize = 10;

impl core::Fragment for CanvasWord<'_> {
    #[inline]
    fn width(&self) -> usize {
        (self.width * PRECISION as f64) as usize
    }
    // ...
}

and later in draw_wrapped_words:

        let line_lengths = |_| width * PRECISION;
        let wrapped_words = core::wrap_first_fit(&canvas_words, line_lengths);

It's a hack for sure, but it seems to work okay in the little demo I wrote.

I don't know if OVERFLOW_PENALTY could really work. In the simplest case it would become a function of the character, which basically returns its width in the given font.

The width of the fragments is computed on the fragment as a whole — not on a per-character basis. Does that help answer your concern?

If you're thinking of how kerning changes the width of characters depending on neighboring characters, then you're completely right that this isn't taken into account right now. The assumption is that we can measure the fragments individually and then simply put them into lines. I believe (hope) kerning will only cause minor changes in the widths, so that we can basically ignore it for the purpose of line breaking — though the layout engine which renders the text should still take it into account.

As for the penalty, the idea (for terminal text) was to make it so large that overflowing a line by even 1 column is so expensive that it never happens. For text in other contexts, one could actually imagine that one would allow a tiny bit of overflow if this results in much better line breaks on the other lines. Like an overflow of 3pt might be preferably to leaving a gap of 30pt at the end of the line.

The HYPHEN_PENALTY really is just a special case of the OVERFLOW_PENALTY, isn't it?

Not entirely, it's an additional penalty for hyphens: with the value of 25 I use currently, a - inserted via automatic hyphenation costs the same as a gap of 5 characters. Put differently, to introduce an extra -, it has to pay off.

You can test this by running

$ cargo run --example interactive --all-features 'Linear time complexities.'

and then adjusting the width to 16 characters. You should see

 ┌                ┐
 │Linear time     │
 │complexities.   │
 └                ┘

If you adjust HYPHEN_PENALTY to 24 or lower and rerun the example, you'll get

 ┌                ┐
 │Linear time com-│
 │plexities.      │
 └                ┘

Yeah, I want to make the penalties adjustable at runtime — and I should let the interactive example take the initial line width as a second command line argument.

[NeverGivinUp]

Thank you for the explanations of the penalty constants. I clearly misread them.
Sounds like you have a little roadmap in mind, that goes very much in the direction of a general text wrapping engine. At your current speed it won't take long, but if you happen to have a day job or a life -- you know "distractions" -- it might be worth explicating the roadmap in the readme or in issues before moving on implementation.

The demo is just great! As a practical usage example as well as a baseline for comparison and a demonstration of the effects of different options. Great work! Thanks again :)

[NeverGivinUp]

The assumption is that we can measure the fragments individually and then simply put them into lines.

Kerning wasn't actually what I was thinking about (though it is relevant). I was worried that hyphenation would create breaks at positions, where the combined characters might be shorter than the broken ones, even if accounting for the hyphen. The "fi"-ligature might be shorter in some fonts than the letters f and i separately. It is my guess from the Unicode line breaking algorithm however, that this won't happen. I did not find an explicit statement, when scanning the text, however. All I found was that in "line layout emergencies", where there are no otherwise permitted line break opportunities "it is recommended that grapheme clusters be kept together."

[mgeisler]

Thank you for the explanations of the penalty constants. I clearly misread them.

Nah, it's definitely not your fault since they're not very well explained at all! Partly because they're hard-coded and partly because the effect is somewhat subtle. I spent some days playing with different values and these values seems to be okay-ish for terminal text. In reality it's all a bit arbitrary and that's also why I want to make them user-controllable.

Sounds like you have a little roadmap in mind, that goes very much in the direction of a general text wrapping engine

Yes, the scope has grown a lot after I rewrote the core wrapping logic. You're completely right about the distractions — I have both a job and I try to have a life, though corona lockdowns have put a damper on that 😐

I'll try to outline the plans a bit and see if I can involve more people, thanks for the nudge!

The demo is just great!

Thanks, I'm glad you like it! It's the modern version the interactive example — and frankly, it's much easier since the browser does a lot of the heavy lifting for you.

I was worried that hyphenation would create breaks at positions, where the combined characters might be shorter than the broken ones, even if accounting for the hyphen. The "fi"-ligature might be shorter in some fonts than the letters f and i separately.

Yes, that's a great example and I guess a "ffi" ligature could end up being split when hyphenating. And if break_words is enabled, then you're right that breaks can occur anywhere — though we probably don't need to care much then since the output is already pretty broken?

[mgeisler]

Please see the newly created project for issue related to making Textwrap work better outside of the terminal.

[mgeisler]

I've converted the issue to a "discussion" — that should let us continue talking in a more tree-like fashion instead of a long linear string of comments.

[mgeisler]

See also #312 for discussion about the demo in particular.