[xml] Exponential running time in RELAX NG matching of optional attributes

[Nikolai Weibull <now disu se>]

Hi!

The following RELAX NG schema requires exponential running time when matching attributes (15 attributes is 
where my computer begins to show the symptoms, this may vary with your set-up):

a.rng:

<?xml version="1.0" encoding="UTF-8"?>
<grammar xmlns="http://relaxng.org/ns/structure/1.0";>
  <start>
    <element>
      <name>a</name>
      <group>
        <optional><attribute><name ns="">a</name><text/></attribute></optional>
        <optional><attribute><name ns="">b</name><text/></attribute></optional>
        <optional><attribute><name ns="">c</name><text/></attribute></optional>
        <optional><attribute><name ns="">d</name><text/></attribute></optional>
        <optional><attribute><name ns="">e</name><text/></attribute></optional>
        <optional><attribute><name ns="">f</name><text/></attribute></optional>
        <optional><attribute><name ns="">g</name><text/></attribute></optional>
        <optional><attribute><name ns="">h</name><text/></attribute></optional>
        <optional><attribute><name ns="">i</name><text/></attribute></optional>
        <optional><attribute><name ns="">j</name><text/></attribute></optional>
        <optional><attribute><name ns="">k</name><text/></attribute></optional>
        <optional><attribute><name ns="">l</name><text/></attribute></optional>
        <optional><attribute><name ns="">m</name><text/></attribute></optional>
        <optional><attribute><name ns="">n</name><text/></attribute></optional>
        <optional><attribute><name ns="">o</name><text/></attribute></optional>
      </group>
    </element>
  </start>
</grammar>

a.xml:

<?xml version="1.0" encoding="UTF-8"?>
<a a="1" b="2" c="3" d="4" e="5" f="6" g="7" h="8" i="9" j="10" k="11" l="12" m="13" n="14" o="15"/>

% time xmllint --noout --relaxng a.rng a.xml
real: 3.175, user: 3.147, system: 0.014 (99%)

Changing the group to an interleave, that is,

b.rng:

<?xml version="1.0" encoding="UTF-8"?>
<grammar xmlns="http://relaxng.org/ns/structure/1.0";>
  <start>
    <element>
      <name>a</name>
      <interleave>
        <optional><attribute><name ns="">a</name><text/></attribute></optional>
        <optional><attribute><name ns="">b</name><text/></attribute></optional>
        <optional><attribute><name ns="">c</name><text/></attribute></optional>
        <optional><attribute><name ns="">d</name><text/></attribute></optional>
        <optional><attribute><name ns="">e</name><text/></attribute></optional>
        <optional><attribute><name ns="">f</name><text/></attribute></optional>
        <optional><attribute><name ns="">g</name><text/></attribute></optional>
        <optional><attribute><name ns="">h</name><text/></attribute></optional>
        <optional><attribute><name ns="">i</name><text/></attribute></optional>
        <optional><attribute><name ns="">j</name><text/></attribute></optional>
        <optional><attribute><name ns="">k</name><text/></attribute></optional>
        <optional><attribute><name ns="">l</name><text/></attribute></optional>
        <optional><attribute><name ns="">m</name><text/></attribute></optional>
        <optional><attribute><name ns="">n</name><text/></attribute></optional>
        <optional><attribute><name ns="">o</name><text/></attribute></optional>
      </interleave>
    </element>
  </start>
</grammar>

gives

% time xmllint --noout --relaxng b.rng a.xml
real: 0.008, user: 0.003, system: 0.002 (54%)

Making the attributes required instead of optional also fixes the issue:

c.rng:

<?xml version="1.0" encoding="UTF-8"?>
<grammar xmlns="http://relaxng.org/ns/structure/1.0";>
  <start>
    <element>
      <name>a</name>
      <group>
        <attribute><name ns="">a</name><text/></attribute>
        <attribute><name ns="">b</name><text/></attribute>
        <attribute><name ns="">c</name><text/></attribute>
        <attribute><name ns="">d</name><text/></attribute>
        <attribute><name ns="">e</name><text/></attribute>
        <attribute><name ns="">f</name><text/></attribute>
        <attribute><name ns="">g</name><text/></attribute>
        <attribute><name ns="">h</name><text/></attribute>
        <attribute><name ns="">i</name><text/></attribute>
        <attribute><name ns="">j</name><text/></attribute>
        <attribute><name ns="">k</name><text/></attribute>
        <attribute><name ns="">l</name><text/></attribute>
        <attribute><name ns="">m</name><text/></attribute>
        <attribute><name ns="">n</name><text/></attribute>
        <attribute><name ns="">o</name><text/></attribute>
      </group>
    </element>
  </start>
</grammar>

% time xmllint --noout --relaxng c.rng a.xml
real: 0.008, user: 0.003, system: 0.002 (55%)

The problem seems to be that xmlRelaxNGValidateDefinition keeps adding states that I feel don’t need 
checking, but I can’t figure out how to avoid this from happening.

Daniel, do you have any input on this?  I’d gladly work on fixing this, but I feel that I need some guidance 
as to what’s going wrong and perhaps also how to fix it.

Thank you,
  Nikolai