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 _______________________________________________ xml mailing list, project page http://xmlsoft.org/ xml@gnome.org https://mail.gnome.org/mailman/listinfo/xml
