Interleave

[James Clark <jjc@jclark.com>]

The hardest issue that we have to resolve before we can release RELAX NG 1.0
is the issue of restrictions on interleave.  What progress have people made
on this issue?

I've observed 3 common cases for interleave:

1. Combining attributes.  In this case one or more operands of the
interleave contain just groups of attributes.

2. Unordered content.  In this case the operands contain elements, choice
and oneOrMore.  The operands don't contain group.  The interleave element
may occur within a interleave, choice or group but doesn't occur in
oneOrMore.

3. Inclusions. In this case, one operand of the interleave can be anything,
but the other is a zeroOrMore of a choice of elements. <mixed> is basically
the same.  This case can occur anywhere.

I think case 3 is manageable because you can transform something like

a* & (b, c, d)

into

a*, (b, a*), (c, a*), (d, a*)

I think case 1 is manageable, because interleave is equivalent to group in
such cases.

The requirements I have for a restriction on interleave are:

- It allows the common cases above
- It prohibits cases that cause exponential behaviour in a derivative-based
implementation (such as Jing)
- It makes it practical to determine when one RELAX NG schema subsumes
another
- The restriction can be checked straightforwardly (independently of any
instance)
- The restriction can be specified straightforwardly

I fear it may not be possible to satisfy all these requirements
simultaneously.

James