Re: Prohibiting duplicate attributes.

[Murata Makoto <mura034@attglobal.net>]

Murata Makoto wrote:

> 
> This restriction allows eager construction of hedge automata 
> even for attribute-element content models (no combinatory 
> explosion).  More about this, see my next mail.

After prohibiting duplicate attributes, we can use RELAX-Core-style validation.  
I would also argue that JTREX-style validation can be improved.

1.  Preprocessing

As usual, I assume that our patterns are normalized.

I introduce <doesNotExist>p1</doesNotExist> as an internal mechanism.  This 
construct bans attributes matching p1.

For every <choice>p1 p2</choice>, we rewrite it as follows:

	<choice>
	  <group><doesNotExist><attribute>a1</attribute></doesNotExist>p1</group>
	  <group><doesNotExist><attribute>a2</attribute></doesNotExist>p2</group>
	</choice>

where

	a1 is the difference of checkDuplicatedAttributeDcl(p2) 
	and checkDuplicatedAttributeDcl(p1), and 

	a2 the difference of checkDuplicatedAttributeDcl(p1) 
	and checkDuplicatedAttributeDcl(p2).

The below example

<choice>
  <attribute name="a"/>
  <attribute name="b"/>
</choice>

is rewritten as below

<choice>
  <group>
    <doesNotExist><attribute name="b"/></doesNotExist>
    <attribute name="a"/>
  </group>
  <group>
    <doesNotExist><attribute name="a"/></doesNotExist>
    <attribute name="b"/>
  </group>
</choice>

Another example

<choice>
  <group><attribute name="a"/><ref name="fooElem"/></group>
  <attribute><anyName/></attribute>
</choice>

is rewritten as below

<choice>
  <group>
    <doesNotExist>
      <attribute>
        <difference><anyName/><name>a</name></difference>
      </attribute>
    </doesNotExist>
    <group><attribute name="a"/><ref name="fooElem"/></group>
  </group>
  <group>
    <doesNotExist><attribute name="a"/></doesNotExist>
    <attribute><anyName/></attribute>
  </group>
</choice>

I do not provide a proof here, but this rewriting preserves 
the meaning of patterns.  


2.  JTREX-style validation

When an attribute multiple <attribute> elements in a content model, 
JTREX creates a derivative by consuming each of the <attribute> 
elements, and then wraps these derivatives with <choice>.  However, 
having introduced the restriction and <doesNotExist>, we can create 
a derivative by consuming all of the <attribute> elements and all 
satisfied <doesNotExist> elements.

Suppse that we have <... a="">.  Then, the derivative for the previous
example is:

<choice>
  <group>
    <group><ref name="fooElem"/></group>
  </group>
  <group>
    <doesNotExist><attribute name="a"/></doesNotExist>
  </group>
</choice>

Suppose that we have <... notA="">.  Then, the derivaive is:

<choice>
  <group>
    <doesNotExist>
      <attribute>
        <difference><anyName/><name>a</name></difference>
      </attribute>
    </doesNotExist>
    <group><attribute name="a"/><ref name="fooElem"/></group>
  </group>
  <group>
  </group>
</choice>


3.  RELAX-Core-style validation

Two validators for RELAX Core create string automata for content models.  
Likewise, our validator for RELAX NG can create string automata for 
content models.  The only difference is that transitions of our string automata 
may be labelled by <attribute> or <doesNotExist>.  This construction 
can be done before we receive an instance document.

Validation of instance documents is similar to that in RELAX Core.  
The difference is handling of start or empty-element tags.  Given 
a start or empty-element tag and a content model, those <attribute> 
or <doesNotExist> transitions which are satisfied are used as null-
transitions.  Those which are not satisfied are ignored.

Consider our previous example again.

<choice>
  <group>
    <doesNotExist>
      <attribute>
        <difference><anyName/><name>a</name></difference>
      </attribute>
    </doesNotExist>
    <group><attribute name="a"/><ref name="fooElem"/></group>
  </group>
  <group>
    <doesNotExist><attribute name="a"/></doesNotExist>
    <attribute><anyName/></attribute>
  </group>
</choice>

A deterministic string automaton for  this content model is 
as below:

start states: s0
final states: s3, s5

transitions:
(s0, <doesNotExist>attributes other than @a</doesNotExist>, s1)
(s1, @a, s2)
(s2, fooElem, s3)
(s0, <doesNotExist>@a</doesNotExist>, s4)
(s4, @*, s5)

If we have <... a="">, the transitions are changes as below:

(s0, null, s1)  //if we can reach s0, we can also reach s1
(s1, null, s2)  //if we can reach s1, we can also reach s2
(s2, fooElem, s3)
(s4, null, s5)  //if we can reach s4, we can also reach s5

If we have <... notA="">, the transitions are changes as below:
 
(s2, fooElem, s3)
(s0, null, s4)//if we can reach s0, we can also reach s4
(s4, null, s5)//if we can reach s4, we can also reach s5


Cheers,

Makoto