Re: [xml] xmllint reports non-determinist content model for schema

[Daniel Veillard <veillard redhat com>]

On Wed, Aug 22, 2012 at 10:40:20PM +0200, Johan Corveleyn wrote:
> On Fri, Aug 17, 2012 at 10:32 PM, Johan Corveleyn <jcorvel gmail com> wrote:
> > On Fri, Feb 24, 2012 at 2:14 PM, Johan Corveleyn <jcorvel gmail com> wrote:
> > ...
> > > I'm running into a "non-determinist" error with a schema even though I
> > > don't think it's non-determinist (and both XSV and Xerces agree with
> > > me; they too have no problem with the schema). I have reduced my
> > > test-case to a simple example, see below.
> >
> > On Tue, Feb 28, 2012 at 6:00 AM, Daniel Veillard <veillard redhat com> wrote:
> > ...
> > >  Well in that case it seems the underlying code is generating a
> > > wrong automata so it should be a matter of running that minimal
> > > test case under gdb with the breakpoint appropriately set to find out
> > > what wrong transition got added ...
> >
> > I'd like to take a stab at this issue. I've been able to get the
> > latest 2.9.0 snapshot (from
> > ftp://xmlsoft.org/libxml2/libxml2-git-snapshot.tar.gz) to build in
> > Visual Studio 2010. I can still reproduce the issue.
> >
> > But I need some guidance. What part of the code should I be looking
> > at? Where do I have to set the "breakpoint appropriately to find out
> > the wrong transition that got added"?
> >
> > Alternatively, if you or anyone else on this list can fix the issue
> > already, that would be even better :-).
> >
> > To summarize, the issue is this:
> > > Given the following schema:
> > >
> > >         <?xml version="1.0" encoding="UTF-8"?>
> > >         <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema";>
> > >                 <xs:element name="rules">
> > >                         <xs:complexType>
> > >                                 <xs:sequence>
> > >                                         <xs:element name="rule" minOccurs="0" maxOccurs="unbounded"/>
> > >                                         <xs:sequence minOccurs="0" maxOccurs="1">
> > >                                                 <xs:element name="specialRule" minOccurs="1" 
> > > maxOccurs="1"/>
> > >                                                 <xs:element name="rule" minOccurs="0" 
> > > maxOccurs="unbounded"/>
> > >                                         </xs:sequence>
> > >                                 </xs:sequence>
> > >                         </xs:complexType>
> > >                 </xs:element>
> > >         </xs:schema>
> > >
> > > xmllint complains with "Schemas parser error : local
> > > complex type: The content model is not determinist."
> > > But it isn't.
> >
> > See also https://bugzilla.gnome.org/show_bug.cgi?id=670865.
>
> Hi,
>
> I could really use some guidance here. I've been able to set up
> everything in Visual Studio 2010, and reproduced the issue from within
> the debugger. So I can set a breakpoint etc. But I mostly lack some
> basic knowledge about how this all works.
>
> Is there some (preferable concise) reading about basic concepts like
> how xml schemas automata work, how these are built, etc? What should
> the automata in this case look like (in terms of the data structures
> inside the code)? How can I see that the automata is non-determinist,
> and what would a determinist automata look like, ... ?

    Johan,

  sorry for the slow answer,

I will look at this, promise, but all that code is rooted in automata
theory, there is quite some litterature about it, and well unless you
go though the process of learning that code and possibly the theory
behind it, it's not something that can be hacked trivially. Basically
I run this in debug mode, look at the automata generated, there is pro
bably an error there and then this need fixing and a lot of checking.
To be honnest that one of the hardest part of the library to change
with the core of the parser.
  Theory is usually learnt though the 'Dragon Book', by Aho and Al.
and the code is actually more complex since using extended automata
operations not found in basic automata ...

    If you have time looking at this may be interesting, but
it's really not trivial at least more complex than other parts of the
code :-)

Daniel

-- 
Daniel Veillard      | libxml Gnome XML XSLT toolkit  http://xmlsoft.org/
daniel veillard com  | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library  http://libvirt.org/