How to handle nested contextual substitutions properly?
mikeday opened this issue · 2 comments
Problem
The behaviour of nested contextual substitutions is not clearly specified when the context of the child subst extends beyond the context of the parent subst.
The current Allsorts GSUB implementation assumes that this never happens, and can assert in some cases and potentially give misleading output in others.
How should nested contextual substitutions be handled, how do current implementations treat them, and how can this behaviour be specified for clarity and interoperability?
Explanation
Consider that a MultipleSubst can replace a glyph with zero or more replacement glyphs:
'a' → 'bc'
'a' → ''
(Technically the OpenType spec does not actually allow MultipleSubst to have a zero-length replacement but this is interoperably supported by implementations).
Substitutions are applied to each glyph in the input buffer in turn. If a substitution inserts multiple glyphs they will be skipped, a substitution is not reapplied to the glyphs that it just inserted.
Contextual substitutions are slightly different in that they are applied to a context of multiple glyphs, and if the context matches then it may apply multiple individual substitutions to glyphs within that context. Once all the substitutions have been applied, potentially growing or shrinking the context due to glyphs being inserted or removed, the contextual substitution will be applied to the next glyph following the context. For example, consider this contextual substitution:
context: 'abc'
subst index 1: 'b' → 'zzz'
subst index 4: 'c' → ''
If this subst is applied to the glyph sequence 'abcxabc' then the context will match the first three glyphs and two substitutions will be performed before it moves on:
'[]abcxabc' // begin at start of glyph sequence
'[abc]xabc' // context matches
'[azzzc]xabc' // subst applies at index 1
'[azzz]xabc' // subst applies at index 4
'azzz[]xabc' // substitution continues after previous context
'azzzx[]abc' // glyph did not match context
'azzzx[abc]' // context matches, etc.
As shown in this example, an individual subst can grow or shrink the context of the contextual subst that invokes it, and the indices for following substs take this into account. Although the context of the subst was originally three glyphs, after it has finished applying it will advance four glyphs ahead in the input buffer.
Things get more complicated when a contextual substitution invokes another contextual substitution whose context extends beyond that of the parent. Consider:
context: 'a'
subst index 0:
context: 'ab'
subst index 1: 'b' → 'ab'
This could cause an infinite loop if executed naively:
'[]ab' // begin at start of glyph sequence
'[a]b' // context matches
'[ab]' // nested context matches at index 0
'[aab]' // subst applies at index 1
'[a]ab' // return to parent context, uh oh!
'a[]ab' // move on to next glyph
'a[a]b' // context matches, infinite loop!
Allowing nested contextual substitutions to insert glyphs ahead of their parent context creates a stack that allows Turing complete computation, presumably undesirable in a font.
Allowing deletes is also problematic given that a delete inside the parent context needs to shrink it but a delete outside the parent context does not.
Possible Solutions
The simplest solution is to ensure that the contexts of nested substitutions do not extend outside the context of their parent. However other OpenType implementations appear to allow this.
Alternatively, pass down the current size of the ancestor context when performing nested substitutions and update it if insertions or deletions take place within this context and leave it unchanged if not.
This would allow a nested substitution to delete multiple glyphs from outside of the parent context without the parent context underflowing and triggering an assertion, which is currently affecting the Addition font. However, it would also allow Turing complete fonts with infinite loops, which would require careful resource tracking to terminate them if they appear to be looping indefinitely.
(There are also some edge cases that would require attention with this approach, such as a nested subst creating a ligature that spans across the boundary of the parent context and thus deletes glyphs inside and outside of it simultaneously).
Another possibility would be to allow a nested substitution to substitute glyphs outside of its parent context but to expand the parent context to include these changes, so that the parent will skip them when it moves on, preventing infinite loops as it will not be able to insert glyphs ahead of itself and then recursively consume them.
Hi Michael,
Thanks for writing down. This is indeed one of the peculiar corners of OpenType Layout. A few remarks:
Deletion
MultipleSubst in the spec specifically says it cannot be used to delete glyphs. However, we found evidence that Uniscribe does allow deleting. So we made HarfBuzz follow. The details are in HarfBuzz commit logs. This should be considered a spec bug and fixed.
Turing-completeness / infinite loops
I find it easier to accept that lookup application can take forever. I've shown Turing-completeness in one of my talks, though that does indeed rely on nested contextuals working beyond their parent context. Video & slides here: https://www.youtube.com/watch?v=lK_myoawb0U
One needs to limit work done by GSUB/GPOS or bad things can happen even without Turing-completeness. Just exponentially expanding the number of glyphs can DoS any app unless the engine limits how much work can be done. HarfBuzz does that.
Also, a contextual that recurses to itself at position 0 is the simplest infinite loop.
Reaching outside parent context
I don't remember which implementations allow nested contextuals to reach outside their context. I know @litherum studied that as well: https://litherum.blogspot.com/2019/03/addition-font.html
If Windows doesn't allow it, we can reconsider in HarfBuzz. Is doable, just not something we considered when implementing this originally.
End of context tracking
In HarfBuzz what we do is we keep track of the end of the context, and every time we call a nested lookup, we check how much the buffer length changed, and assume that the change (insertion / deletion / ...) was done within the context. So we move the context end marker appropriately. Even that limited action has been very tricky to get right. It still is buggy: harfbuzz/harfbuzz#1611
The code is this function, perhaps the trickiest part of HarfBuzz: https://github.com/harfbuzz/harfbuzz/blob/2e1bf61dd5afcef71957b349254b80e7cfd14e45/src/hb-ot-layout-gsubgpos.hh#L1177
Happy to converge on a solution. Thanks.
Thanks Behdad, your feedback is much appreciated!
Your point about Turing completeness is well-taken, I've been shying away from it out of fear, but since we need to be careful with exponential resource consumption anyway it might not make things any worse than they already are. Although if we give font designers the ability to perform arbitrary computation in their fonts it might be difficult to put that genie back in the bottle! 😆
If DirectWrite doesn't allow child contexts to extend beyond parent contexts then that simplifies matters considerably. But if HarfBuzz and CoreText do support it, do you know if any fonts take advantage of this ability, besides experiments like the Addition font? Would we be breaking anything by disallowing it? Because it is quite a complex extension to specify correctly, and if Microsoft don't implement it then that would make it less useful in practice, I assume.