Re: [relax-ng] Re: RELAX NG + Schematron

[James Clark <jjc@jclark.com>]

>> For the other approach, it would make more sense to simply have an
>> attribute with an XPath expression:
>>
>> <element name="orders" x:require="count(order) > 4">
>>   <oneOrMore>
>>     <ref name="order"/>
>>   </oneOrMore>
>> </element>
>
> I don't think the syntax of writing assertions has something to do
> with the algorithm. This way of writing assertions can work fine with
> the "RNG-first-n-Schematron-later" style, and writing <s:rule> and
> <s:assertion> can work well with the "use-schematron-to-guide-RNG"
> style, too.

The issue isn't the syntax but the fact that the Schematron assertion 
specifies an error message to be given to the user.  With the 
use-schematron-to-guide-RNG approach, it may be ambiguous which Schematron 
constraint was not satisfied, so there's no way to determine which message 
to the user. If you just have attribute (x:require) with no message, then 
that doesn't matter.

> function check( Pattern p ) {
>   if( p is already checked )    return;
>
>   for( each e in first(p) ) {
>     E' := { e' | e' \in first(p) and e ~ e' }
>
>     if( E' contains more than one element with assertion )
>         eureka!;
>
>     check( choice of all content models in E' );
>     check( residual of p by E' );
>   }
> }

That doesn't look quite right to me. If we have

<choice>
  <element>
    <anyName/>
    <empty/>
  </element>
  <element name="a">
    <s:assert test="x">...</s:assert>
    <ref name="any"/>
  </element>
  <element name="b">
    <s:assert test="y">...</s:assert>
    <ref name="any"/>
  </element>
</choice>

then your algorithm would appear to make this ambiguous (when e is the 
<anyName/> case).

I think it should be something like

function check( Pattern p ) {
  if( p is already checked )    return;

  for( each x in witnesses(first(p)) ) {
    E' := { e' | e' \in first(p) and x \in e' }

    if( E' contains more than one element with assertion )
        eureka!;

    check( choice of all content models in E' );
    check( residual of p by <x/> );
  }
}

where witnesses(Pattern p) returns a set of names with one name from each 
equivalence class of names where two names are equivalent iff for any name 
class in p the two names both belong to the name class or both do no belong.

Isn't checking this going to be exponential with something like

(a? & b? & c? & ...)*

?

James