Daniel Veillard <daniel@v...> writes:

> On Sun, Oct 10, 2004 at 10:57:32PM +0100, Henry S. Thompson wrote:
>> Daniel Veillard <daniel@v...> writes:
>> 
>> > libxml2 regexps used counters since day 1 for min/maxoccurs
>> > implementation.  The explosion didn't look a supportable
>> > alternative to me as it opens the door to trivial DoS attacks or
>> > forces to break the schemas validation which is also a big
>> > problem if you consider schemas as a contract between two
>> > communicating parties.
>> 
>> I would be very interested, as I'm sure would others, in a description
>> of your algorithm.
>
> Well nothing fancy really. You need to add state to the regexp, in
> that case the state is the number of time you went through the
> transition labelled by the element name:namespace pair. Due to the
> single particle rule, it means you have no need to be able to
> rollback the state to enter a different transition labelled by the
> same name:namespace pair.  Which means the effective state required
> is purely linear based on the number of counted transition you have
> in your regexp: one integer counter is sufficient per such
> transition in the regexp runtime structure. It's actually more
> automata with state that I'm using than pure regexps.  And the
> generated constructs for something like x{a,b} involves 3 states
> (IIRC) a couple of epsilon transitions and the counted regexp, but
> it's not really rocket sience either, very similar to what I was
> taught in the classroom.

Right, that works fine for exponents on individual elements, but I
don't see how it works for groups.

Here's a real example from a published schema document [1]:

<xsd:sequence minOccurs="0" maxOccurs="1000">
    <xsd:element ref="ReferenceIdentification" minOccurs="0"/>
    <xsd:element ref="Message" minOccurs="0" maxOccurs="1000"/>
</xsd:sequence>

Or consider a (constructed) case that's tricky in a different way:

<xsd:sequence minOccurs="2" maxOccurs="2">
    <xsd:element ref="a" minOccurs="1" maxOccurs="2"/>
    <xsd:element ref="b" minOccurs="0"/>
</xsd:sequence>

which allows _inter alia_

 <a/><a/>
 <a/><a/><a/>
 <a/><a/><a/><a/>

ht
 
[1] http://www.idealliance.org/spacexml/files/spacexmlv100.zip
-- 
 Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
                     Half-time member of W3C Team
    2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
            Fax: (44) 131 650-4587, e-mail: ht@i...
                   URL: http://www.ltg.ed.ac.uk/~ht/
[mail really from me _always_ has this .sig -- mail without it is forged spam]

From veillard@v... Mon Oct 11 15:17:46 2004
Received: from bart.w3.org ([128.30.52.40])
	by frink.