Clean up the text handling pipeline

[simoncozens]

OK, this is going to be a bit of a stream-of-consciousness issue. I am trying to understand a major structural issue with SILE and understand how to fix it, and I'm struggling. Any help would be appreciated.

@mhosken recently pointed me to a situation where the shaping engine needs to see the whole paragraph, not just individual tokens. This is something that has come up before (#138, #173), so it's something we definitely need to look into. I have a proof of concept package which does this (and it makes me happy that this can be implemented as a package) but it's a bit of a mess. But the current situation is also a mess, and we need to decide which mess is less messy.

Definitions

First, a few definitions:

• Shaping, we all know, involves passing text to Harfbuzz and getting back position/width/cluster information.
• Bidi reordering, hyphenation, line breaking again we all know.
• Node creation involves bundling up style/font/size/etc. information along with the text.
• Tokenizing involves splitting the text into smaller units.
• What I'll call language handling involves language-specific processing of the input stream. Example: Japanese kinsokushori rules and inter-character-class spacing rules.

Also the types of horizontal node that SILE deals with, since this isn't documented anywhere and it's confusing:

• Penalty and glue nodes represent line break opportunities and white space respectively. This is the same as TeX.
• hbox nodes can define their own output routines and hence can actually be whatever you like, but their default state is to contain font information and a series of glyph IDs.
• nnodes were initially based on XeTeX's native nodes, but have diverged quite a bit from that. They represent collections of hboxes that we want to keep together for logical processing. Critically, an nnode also carries around the text which produced it. For instance, hyphenation is implemented by splitting an nnode into its hyphenation parts (N<after> becomes N<af>D<->N<ter>) but these split nodes know their parent. This means that if the word ends up not being hyphenated by the Knuth-Plass algorithm, we can ask the node to output its parent instead. This allows us to output N<after> in the unhyphenated case, instead of having to output N<af>N<ter>; the idea is to improve the PDF output.
• unshaped nodes are just text plus font options.

Current situation

The current system takes some text, and then performs tokenizing and language handling. Each language support routine can implement their own tokenizer - a tokenizer is an iterator which emits either bits of text, or ready-formed nodes (again, think of Japanese kinsokushori, which is implemented as splitting the text into individual characters and then interweaving penalties and glue nodes with the text output).

Any text tokens are wrapped into unshaped nodes. Now we have a stream of nodes. For English, they might look like U<after>G<2.6pt plus 0.73pt>U<several>U<2.6pt plus 0.73pt>days. For Japanese, they would look like U<私>G<0pt plus 2.5pt>U<は>G<0pt plus 2.5pt minus 5pt>U<「>U<SILE>U<」>G<0pt>U<で>G<0pt plus 2.5pt>U<す>.

They are then broken into lines - to do this, unshaped nodes are shaped into nnodes so we know their widths. After line breaking we do bidi reordering. (Quoting UAX#14: "In bidirectional text, line breaks are determined before applying rule L1 of the Unicode Bidirectional Algorithm." - see discussion in #137 and #173, where @behdad cryptically said "Bidi is not a one-off operation. It happens in stages." I don't know what the stages are.)

Bidi reordering currently works like this: for each line of the paragraph, the nodelist is transformed into a new nodelist, where individual characters (UTF8 codepoints) from the text of each nnode are split into their own unshaped nodes. So in the English case we now go down to U<a>U<f>U<t>U<e>U<r>G<2.6pt plus 0.73pt>... These nodes are fed to @khaledhosny's Lua bidi implementation, and reordered, and then we try to reconstitute them into nnodes again afterwards: U<after>G<2.6pt plus 0.73pt> or U<retfa>G<2.6pt plus 0.73pt> as the case may be. The reconstituting process is suspect. And then we shape the unshaped nodes again, and now everything is ready to be sent to the page builder.

So the pattern goes: tokenising / language handling, forming nodes, shaping nodes, line breaking, bidi, shaping again.

Proof of concept situation

The harfbuzz-only-shaper works by each incoming bit of text into one big unshaped node. So now you get U<after several days> and U<私は「SILE」です>. No tokenizing or language handling is done, but we do bidi processing on the unshaped nodes at this stage, in the same way as described above.

Then the unshaped nodes are shaped. We get back a stream of glyphs and their measurements from Harfbuzz, which we assemble into nnodes. If at any point in the glyph stream we see glyph named space, (how brittle is that?!) we output the nnode we've been assembling so far, and then turn the space glyph into a glue node.

Nnodes need to know their text content (for hyphenation, etc.) so we use the cluster index (from Harfbuzz) of the first glyph and last glyphs in the current nnode to substring the paragraph content. This feels like it isn't quite right, because I'm sure some languages produce shaped glyphs in a different order to Unicode stream. (Thai?)

Then line breaking, and straight to the page builder.

Problems with the proof of content

• No tokenizing or language handling. So Japanese fails, because it doesn't have spaces, and so no glue nodes are generated, which means there's no potential break points.
• Each "incoming bit of text" is sent into an unshaped node. This is not the same as shaping the whole paragraph. In fact we are shaping runs. Hello \em{there} world would create three unshaped nodes U<Hello >U<there>U< world>, which would each get sent to Harfbuzz independently. I think that is fine - because U<there> has a different font, and so needs to be shaped differently - but then bidi reordering happens on each of them independently, not as a whole, which is clearly wrong.
• Bidi handling happens before line breaking, which means we have a "my is full of eels hovercraft" issue (see second example of Bidirectionality misfeature? #137).
• X offsets. When we output the glyphs, we adjust the output cursor by the x_offset value that Harfbuzz reported for each glyph. This works nicely when we shape a token at a time. However, for some reason we end up with huge x_offsets for glyphs at the end of the line. (I assumed that x_offsets were relative to the current advance position, but I am seeing x_offsets like -120pt, which makes no sense to me.)

Where we want to be

This is what I think we want to be doing. But I am not sure.

• Turn each run of text into an unshaped node. No bidi here.
• When it's time to set the paragraph, shape each run. (We still haven't done bidi yet so we are sending U<abc>U<[aleph][beth][gimel]> to the shaper in logical, Unicode storage order. Is that right? Is mixed English/Arabic going to shape correctly? Does each run need to know its text direction?)
• Shaping will return a bunch of glyphs and positioning information.
• Before we break into lines, we need to turn the glyphs/positions into nnodes. But we let language-specific handlers interact with that process. The default handler assembles characters into nnodes and spaces into glue, just like the harfbuzz-only-shaper. The Japanese handler will insert glues and penalties between glyphs. South Asian handlers will do clever algorithmic stuff on the text of the nnodes to determine line breaking possibilities.
• Now we break into lines.
• Now it's bidi time. The bidi process will have to be quite different from the current practice. We have a bunch of nnodes containing text, and we have glyphs within the nnodes which know their offset into the text. Then we do what @khaledhosny suggested in Use ICU for bidi #173:

• Convert node list to a string, using 0xFFFC for anything that is not a character.
• Use ICU to get the embedding levels of the string and assign them back to each node.
• Use the embedding levels to reorder the nodes, which I think can be done after line breaking.

• Do we now need to reshape the reordered nodes at this stage? We've reordered the text, so I would think so, but maybe if we've just reordered runs that won't affect the shaping? I don't know.

And then we're done. I still don't know how to handle the x_offsets issue, but if this is correct, it seems like it should work.

Worries

• Is hyphenation still going to work?
• Will I get the bidi reordering wrong?
• Will we correctly extract text from cluster information returned by Harfbuzz?
• Will language-specific handlers be able to do all the things they need given that they are now receiving a string of glyphs instead of text?
• How do I correctly compute the x_offset for marks from the previous character, not from the start of the line?

I will start mucking with all this in the new-pipeline branch. Thanks for reading to the end and if anyone cc'd could make any comments ("Yes, that'll work", "No, you've misunderstood") or pick up things I've missed that would help me a lot!

[mhosken]

Dear Simon,

This is what I think we want to be doing. But I am not sure.

• Turn each run of text into an unshaped node. No bidi here.
• When it's time to set the paragraph, shape each run. (We still haven't done bidi yet so we are sending U<abc>U<[aleph][beth][gimel]> to the shaper in logical, Unicode storage order. Is that right? Is mixed English/Arabic going to shape correctly? Does each run need to know its text direction?)

Yes it does. The way to handle this is to run most of the bidi algorithm before shaping, but not to actually reorder. The bidi algorithm is run to split the text into runs with the same bidi level. So you start with a sequence of runs that represent the paragraph, including multiple runs for font changes, etc. The bidi algorithm runs through the whole text as if it were one run, allocating bidi levels (and taking into account if a run has a bidi override in it. Not sure if you support that yet, but you will probably want to one day). Then the runs are further split according to their bidi levels.

Shaping then is a matter of passing the direction of each run along with the run for each run.

• Shaping will return a bunch of glyphs and positioning information.

So now you have one nnode per run containing a bunch of hboxes for each cluster. I don't see a value in having one hbox per glyph.

Hmm perhaps this is too simplistic. What is really being called for here is an nnode per run containing an nnode per cluster which contains the text of the cluster and a single hbox for the cluster. Either that or you need to beef up hbox to hold the source text of the glyphs it's representing.

• Before we break into lines, we need to turn the glyphs/positions into nnodes. But we let language-specific handlers interact with that process. The default handler assembles characters into nnodes and spaces into glue, just like the harfbuzz-only-shaper. The Japanese handler will insert glues and penalties between glyphs. South Asian handlers will do clever algorithmic stuff on the text of the nnodes to determine line breaking possibilities.
• Now we break into lines.

Which is a matter of finding the line break points.

• Now it's bidi time. The bidi process will have to be quite different from the current practice. We have a bunch of nnodes containing text, and we have glyphs within the nnodes which know their offset into the text. Then we do what @khaledhosny suggested in Use ICU for bidi #173:

Now you complete the second half of the bidi algorithm: reordering. You have all the levels and within each run, the text has its appropriate surface order (whether by reordering the run or having positions that put later glyphs before earlier ones). So it's merely a case of handling the higher level run reoderings. A fun algorithm to work through.

And then we're done. I still don't know how to handle the x_offsets issue, but if this is correct, it seems like it should work.

Yup.

Worries

• Is hyphenation still going to work?

Hyphenation should still work because at the point you are line breaking, you are dealing with nnodes for each run of text and so you have access to the text to do hyphenation. I'm not sure if you have to reshape the subruns should you actually insert a hyphen.

• Will I get the bidi reordering wrong?

Hopefully not now :)

• Will we correctly extract text from cluster information returned by Harfbuzz?

If you go cluster by cluster, you should be OK. Opentype clusters are monotonic in their progression. As an aside, this differs from Graphite which allows for reordered clusters. But there graphite harfbuzz integration layer merges reordered clusters into a single cluster to keep the monotonic rule. The problem with that is that if you add intercluster glue, like you suggest for Japanese, and actually is probably the best way to do justification for all languages, then you don't get consistent results because an OpenType cluster can be more than one visual cluster (base + diacritics). So you get to choose where your handle the pain: easy monotonic runs for line breaking etc, and hard justification or the other way around.

• Will language-specific handlers be able to do all the things they need given that they are now receiving a string of glyphs instead of text?

Yes, with the above caveat. I think that inter cluster spacing is of such general use that I would make it core and have a document.charskip glue that if set is inserted before every cluster. Notice though that the TeX justification algorithm takes into account how much stretch the glue has in allocating the amount of actual stretch to apply at each node. For example, if space is 10pt plus 5pt (ignoring shrink for the moment) and interchar is 0pt plus 0.5pt then 10x as much stretch will be given to spaces as to characters.

• How do I correctly compute the x_offset for marks from the previous character, not from the start of the line?

Keep track of the start of the cluster and treat it as 0, then run the normal positioning algorithm for advance and offset, through the cluster until you hit a new one. Then store all glyphs in the hbox relative to the start of the hbox, which in this case is a single cluster.

I will start mucking with all this in the new-pipeline branch. Thanks for reading to the end and if anyone cc'd could make any comments ("Yes, that'll work", "No, you've misunderstood") or pick up things I've missed that would help me a lot!

HTH.
GB,
Martin

[simoncozens]

Yes it does. The way to handle this is to run most of the bidi algorithm before shaping, but not to actually reorder.

Ah, OK. That makes sense now, and explains what Behdad meant by several stages.

Hmm perhaps this is too simplistic. What is really being called for here is an nnode per run containing an nnode per cluster which contains the text of the cluster and a single hbox for the cluster.

Yeah, normally you have one nnode containing one hbox with all the glyphs in it. This sounds redundant but the idea is that after hyphenation the nnode may contain a bunch of hboxes and discretionaries.

If you go cluster by cluster, you should be OK. Opentype clusters are monotonic in their progression. As an aside, this differs from Graphite which allows for reordered clusters. But there graphite harfbuzz integration layer merges reordered clusters into a single cluster to keep the monotonic rule. The problem with that is that if you add intercluster glue, like you suggest for Japanese, and actually is probably the best way to do justification for all languages, then you don't get consistent results because an OpenType cluster can be more than one visual cluster (base + diacritics). So you get to choose where your handle the pain: easy monotonic runs for line breaking etc, and hard justification or the other way around.

I don't really understand this. But I think that might be because I don't understand Harfbuzz's clusters very well. I'm just treating the .cluster that it returns as an index into the string and getting frustrated that it only tells me where a glyph's character starts and not where it ends.

• Will language-specific handlers be able to do all the things they need given that they are now receiving a string of glyphs instead of text?
  Yes, with the above caveat.

Related to the above, I've found an interesting failure mode at the moment. The test string "official official official..." typesets perfectly, with hyphenation, in Gentium, but if I switch to something with a ffi ligature such as EB Garamond, it all falls apart. This is because SILE now thinks it is typesetting N<Of>D<->N<cial> and all the widths go wrong. So as predicted I have failed to correctly get the text
back out of Harfbuzz.

I think that inter cluster spacing is of such general use that I would make it core and have a document.charskip glue that if set is inserted before every cluster.

Well, there are a few things going on here. Yes, we should have a generic document.charskip setting which inserts constant glue before every cluster. But also many of the language support packages will want to insert their own custom glue based on the value of the previous cluster and the upcoming cluster. Japanese intercharacter glue is a based on such a two-way lookup. And maybe you will want to do something similar for Arabic.

I will try and convert the existing Japanese tokenizer into a nodeMaker in the new-pipeline branch, because that will make a good example.

Keep track of the start of the cluster and treat it as 0, then run the normal positioning algorithm for advance and offset, through the cluster until you hit a new one.

I tried doing that for your cross-space kerning example but it seemed to mess up the spaces. I will try it with the new branch... as soon as I have got bidi working a bit better.

[mhosken]

Dear Simon,

I don't really understand this. But I think that might be because I
don't understand Harfbuzz's clusters very well. I'm just treating the
.cluster that it returns as an index into the string and getting
frustrated that it only tells me where a glyph's character starts and
not where it ends.

Since clusters are monotonic increasing the start of one cluster is the end of another. In other words if you have the end[x] = start[x+1] where x is the cluster number (assuming end is the position past the end of the cluster).

• Will language-specific handlers be able to do all the things
  they
  need given that they are now receiving a string of glyphs instead of
  text?

Yes, with the above caveat.

Related to the above, I've found an interesting failure mode at the
moment. The test string "official official official..." typesets
perfectly, with hyphenation, in Gentium, but if I switch to something
with a ffi ligature such as EB Garamond, it all falls apart. This is
because SILE now thinks it is typesetting N<Of>D<->N<cial> and all the
widths go wrong. So as predicted I have failed to correctly get the text
back out of Harfbuzz.

You are getting back o@0, ffi@1, c@4, i@5, a@6, l@7 where @ precedes the cluster start. so the text for each one is o@[0:1], ffi@[1:4], c@[4:5] ... (using python array indexing there).

I think that inter cluster spacing is of such general use that I
would make it core and have a document.charskip glue that if set is
inserted before every cluster.

Well, there are a few things going on here. Yes, we should have a
generic document.charskip setting which inserts constant glue before
every cluster. But also many of the language support packages will want
to insert their own custom glue based on the value of the previous
cluster and the upcoming cluster. Japanese intercharacter glue is a
based on such a two-way lookup. And maybe you will want to do something
similar for Arabic.

Well intercharacter spacing is generally handled by the font and graphite even has the capability to describe justification (kashidas, ligature removal, etc.). But yes, having language interaction can only help.

Keep track of the start of the cluster and treat it as 0, then run
the normal positioning algorithm for advance and offset, through the
cluster until you hit a new one.

I tried doing that for your cross-space kerning example but it seemed to
mess up the spaces. I will try it with the new branch... as soon as I
have got bidi working a bit better.

It'll tie your head in knots (perhaps). Consider it a rite of passage :)

GB,
Martin

[simoncozens]

It'll tie your head in knots (perhaps). Consider it a rite of passage :)

Seriously.

I think I understand why it's not working. (as at 4e6daab) Here's a simple bidi example:

\begin[papersize=a5]{document}
\font[family=SBL Hebrew,language=he,size=25pt]
\set[parameter=document.baselineskip,value=29pt]

My hovercraft is full of eels.

הרחפת שלי מלאה בצלופחים

One two אבג three four

אחד שתיים ABC שלוש ארבע

\set[parameter=typesetter.breakwidth,value=50mm]

My hovercraft is full of eels.

הרחפת שלי מלאה בצלופחים
\end{document}

And its output:

Before we shape, we split into bidi runs and assign levels:

U(My hovercraft is full of eels.)   LTR 0
No patterns for language he
U(הרחפת שלי מלאה בצלופחים)  RTL 1
U(One two ) LTR 0
U(אבג)   RTL 1
U( three four)  LTR 0
U(אחד שתיים )   RTL 1
U(ABC)  LTR 2
U( שלוש ארבע)   RTL 1
U(My hovercraft is full of eels.)   LTR 0
U(הרחפת שלי מלאה בצלופחים)  RTL 1

This all looks correct. However, after we've shaped the nodes, the items within them come back in visual order (which makes sense, because we've asked Harfbuzz to lay them, and so it has done.) But I think at this stage the bidi algorithm is still expecting us to be in logical order, because we only want to do reordering after line breaking has happened. Anyway, we're now in visual order, and we then turn spaces into glue, and get (for the last line):

1 N<89.2578125pt>^20.47119140625-0.37841796875v(םיחפולצב)   RTL 1
2 G<8.115234375pt plus 3.38134765625pt minus 2.2542317708333pt> nil nil
3 N<53.80859375pt>^20.47119140625-0.37841796875v(האלמ)  RTL 1
4 G<8.115234375pt plus 3.38134765625pt minus 2.2542317708333pt> nil nil
5 N<34.375pt>^20.47119140625-0.40283203125v(ילש) RTL 1
6 G<8.115234375pt plus 3.38134765625pt minus 2.2542317708333pt> nil nil
7 N<68.07861328125pt>^14.14794921875-0.37841796875v(תפחרה) RTL 1

(Remember that this was initially one big buffer out of Harfbuzz, that I've chopped into nodes at spaces.)

Now line breaking happens and "My hovercraft" is now at nodes 5-7, and a line break comes at node 4, meaning "my hovercraft" is on the second line and "is full of eels" is the first line. No matter how we reorder the text within the line we're not going to sort this out. So I think the problem is that Harfbuzz is reordering the characters for me.

Do I need to reverse the order of items from any RTL output from Harfbuzz, so as to keep things in logical order until after line breaking is done? And will that mess up Arabic joining?

[mhosken]

Dear Simon,

This all looks correct. However, after we've shaped the nodes, the items within them come back in visual order (which makes sense, because we've asked Harfbuzz to lay them, and so it has done.) But I think at this stage the bidi algorithm is still expecting us to be in logical order, because we only want to do reordering after line breaking has happened. Anyway, we're now in visual order, and we then turn spaces into glue, and get (for the last line):

1 N<89.2578125pt>^20.47119140625-0.37841796875v(םיחפולצב) RTL 1
2 G<8.115234375pt plus 3.38134765625pt minus 2.2542317708333pt>   nil nil
3 N<53.80859375pt>^20.47119140625-0.37841796875v(האלמ)    RTL 1
4 G<8.115234375pt plus 3.38134765625pt minus 2.2542317708333pt>   nil nil
5 N<34.375pt>^20.47119140625-0.40283203125v(ילש)   RTL 1
6 G<8.115234375pt plus 3.38134765625pt minus 2.2542317708333pt>   nil nil
7 N<68.07861328125pt>^14.14794921875-0.37841796875v(תפחרה)   RTL 1

(Remember that this was initially one big buffer out of Harfbuzz, that I've chopped into nodes at spaces.)

If hb is generating stuff in visual order, shouldn't the first word be at the end? IOW shouldn't the nodes be in the opposite order? It looks like you reversed them, because it's rtl. It makes sense, but as we'll see, I'm not sure it's necessarily the best solution at this stage.

Now line breaking happens and "My hovercraft" is now at nodes 5-7, and a line break comes at node 4, meaning "my hovercraft" is on the second line and "is full of eels" is the first line. No matter how we reorder the text within the line we're not going to sort this out. So I think the problem is that Harfbuzz is reordering the characters for me.

Do I need to reverse the order of items from any RTL output from Harfbuzz, so as to keep things in logical order until after line breaking is done? And will that mess up Arabic joining?

Line breaking is interesting because we need to measure rtl runs from the right. Notice that line breaking may occur at other places than at glue nodes (hyphenation, non-hyphenating languages, zwsp, etc.). So I'm not sure I buy the idea of reversing the node list in an rtl run. Probably better just to run the break points backwards into the tex line breaking graph with their measurements (measured from the end of the run for rtl). But you are the one who has to program this.

Now we have the string broken into lines, it's time to reorder the runs on the line. The next step is to reorder the runs according to their bidi levels somewhat according to UAX#9 L2. The trick here is that you don't reorder the characters within the runs, just the runs in relation. So for example consider Example 4 from UAX#9

Input: DID YOU SAY '>he said "<car MEANS CAR="='?
Levels: 111111111111112222222222444333333333322111
Shaped: >' YAS UOY DIDhe said "<carRAC SNEAM ="?'=
Levels: 111111111111112222222222444333333333322111
stage1: >' YAS UOY DIDhe said "<RAC SNEAM car="?'=
Levels: 111111111111112222222222333333333344422111
stage2: >' YAS UOY DID="carRAC SNEAM he said "<?'=
Levels: 111111111111112244433333333332222222222111
stage3: ?'=he said "<RAC SNEAM car=">' YAS UOY DID
Levels: 111222222222233333333334442211111111111111

There's a stage 0 where we take the level 4 and not reverse it. Then for stage 1 we reverse levels 3 and 4, but notice we only reverse the run orders not the runs themselves. Then we reverse levels 2, 3 & 4 (again just run orders). Finally we reverse levels 1-4 (again just run orders). Notice we don't reverse for level 0.

GB,
Martin

[simoncozens]

If hb is generating stuff in visual order, shouldn't the first word be at the end?

It is. The first word of the Hebrew input was הרחפת, which is now the last node.

[simoncozens]

(It may be that github/your mail client is doing bidi for you and showing the input in visual not logical order. Oh, bidi is fun.)

[simoncozens]

Notice that line breaking may occur at other places than at glue nodes (hyphenation, non-hyphenating languages, zwsp, etc.).

Well, the job of the node maker (which is the thing that makes the glue nodes) is also to create the correct penalty nodes for potential line breaks. See the Japanese examples in language/ja.lua.

Probably better just to run the break points backwards into the tex line breaking graph with their measurements (measured from the end of the run for rtl). But you are the one who has to program this.

Your use of the word "just" here... I just about understand the line breaking algorithm, so long as I don't have to mess with it too much. Filling up the line in logical order, and then flipping it, should work just fine, for line breaking.

Now I am doing something which seems wrong - reordering the items returned from the shaper so they're in logical order, line breaking, running L2 of the UBA but also reordering the items in each odd-level node so they're back into visual order - I get this:

and in a base direction RTL context, this:

which modulo the crazy spacing and punctuation doesn't seem too far off.

[mhosken]

Dear Simon,

Probably better just to run the break points backwards into the tex line breaking graph with their measurements (measured from the end of the run for rtl). But you are the one who has to program this.

Your use of the word "just" here... I just about understand the line breaking algorithm, so long as I don't have to mess with it too much. Filling up the line in logical order, and then flipping it, should work just fine, for line breaking.

An unjust use of just. Completely unjustified!

Now I am doing something which seems wrong - reordering the items returned from the shaper so they're in logical order, line breaking, running L2 of the UBA but also reordering the items in each odd-level node so they're back into visual order - I get this:

and in a base direction RTL context, this:

which modulo the crazy spacing and punctuation doesn't seem too far off.

All of bidi seems wrong. But it does work and it seems that, as you say sans spacing and punctuation, things are looking good.

GB,
Martin

[behdad]

I really want to contribute to this discussion but am far behind work after many weeks of vacation+travel and this thread deserves more than a few minutes...

Simon, I still think it would be a good idea if we can meet somewhere later this year. WDYT? The pipeline needs to be redesigned from the ground up, and communicating how it should work over written text is going to be quite a feat.

I'd be happy to answer questions though. Re "bidi happens in stages", in first stage you get the embedding level for each character for a paragraph of text. You use that in shaping and line breaking, then for each line, you do some more processing and then reordering.

[simoncozens]

Sadly I don't think anyone's going to fly me around the world to hack on a spare-time project. :-) If you do end up coming to Japan, let me know. Otherwise, linux.conf.au next year might be a possibility.

I guess if I had one question it would be this: I have got the embedding level for each character, split the string up into bidi runs, assigned them a direction and embedding level, and sent those runs to the shaper including the direction. Harfbuzz has sent me back RTL runs in visual order (I sent it "abc def" "UVW XYZ" "ghi" and it returned "abc def" "ZYX WVU" "ghi"). But, like you say, I don't want to reorder yet until after line breaking. Can I get Harfbuzz to not reorder the run, so I can do it myself?

[behdad]

I guess if I had one question it would be this: I have got the embedding level for each character, split the string up into bidi runs, assigned them a direction and embedding level, and sent those runs to the shaper including the direction. Harfbuzz has sent me back RTL runs in visual order (I sent it "abc def" "UVW XYZ" "ghi" and it returned "abc def" "ZYX WVU" "ghi"). But, like you say, I don't want to reorder yet until after line breaking. Can I get Harfbuzz to not reorder the run, so I can do it myself?

No, keep what HarfBuzz returned. You don't want to reorder runs within a line until after line breaking..

Why do you need what you are asking? If you are going to break within a run, you have to reshape both sides. And since you know the run direction you know which part goes on the first line and which one on the second.

[simoncozens]

OK, do you know what, I think we're pretty much there:

The only dodgy bit is the punctuation in an RTL frame, but that's what @khaledhosny's bidi implementation does, so who am I to argue?

??My hovercraft is full of eels.
11222222222222222222222222222221

Once I solve the x_offset issue, I think I'm going to merge this into master.

[simoncozens]

In attempting to describe the x_offset problem to the harfbuzz mailing list, the answer has become stunning obvious.

$ hb-shape --output-format=json martin/Awami_test.ttf 'دنیا دے سارے انسان ہکو ڄئے تے نہ مکڻ والے' | perl -pe 's/},{/},\n{/g'
[{"g":"nlqBariyehFin","cl":40,"dx":0,"dy":0,"ax":2261,"ay":0},
{"g":"absLamIni.by","cl":39,"dx":-2261,"dy":148,"ax":878,"ay":0},
{"g":"absAlef","cl":38,"dx":-975,"dy":0,"ax":324,"ay":0},
{"g":"absWaw","cl":37,"dx":-782,"dy":0,"ax":731,"ay":0},
{"g":"space","cl":36,"dx":-878,"dy":0,"ax":75,"ay":0},
{"g":".notdef","cl":35,"dx":-878,"dy":0,"ax":1300,"ay":0},
{"g":"absKehehFin","cl":34,"dx":-1013,"dy":0,"ax":2056,"ay":0},
{"g":"absMeemIni","cl":33,"dx":-889,"dy":-110,"ax":557,"ay":0},
{"g":"space","cl":32,"dx":-889,"dy":0,"ax":75,"ay":0},
...
{"g":"space","cl":4,"dx":-5420,"dy":0,"ax":75,"ay":0},
{"g":"absAlefFin","cl":3,"dx":-5469,"dy":0,"ax":381,"ay":0},
{"g":"absBehMed","cl":2,"dx":-5578,"dy":-53,"ax":815,"ay":0},
{"g":"_dot2l","cl":2,"dx":-6247,"dy":-453,"ax":1,"ay":0},
{"g":"absBehIni.beM2","cl":1,"dx":-5929,"dy":-100,"ax":571,"ay":0},
{"g":"_dot1u","cl":1,"dx":-6079,"dy":926,"ax":1,"ay":0},
{"g":"absDal","cl":0,"dx":-5862,"dy":0,"ax":751,"ay":0}]

The question is: what happens if we break this run for a line break? How do we reset the x offsets to something sensible, rather than having them offsetting the painting by 5000 units?

The answer is easy now: whenever you see a space and turn it into glue, store the space's x offset within the node. When you break into lines, subtract the x_offset of the glue node which caused the break from the x_offset of each of the items within the line.

This seems a crazy special case to have to do to keep one font happy, but I'm sure there might be others too...

[simoncozens]

OK, this is all implemented and merged into master for 0.9.4, and (apart from the crazy x_offset issue) seems to work very nicely. Thanks to all who helped clear up my thinking. Of course if you have nasty bidi test cases which don't work, please let me know.