W3C home > Mailing lists > Public > xmlschema-dev@w3.org > May 2010

Re: Implementing the DOM3 Val Spec in Javascript, problem with UPA and creating PSVI.

From: Pete Cordell <petexmldev@codalogic.com>
Date: Sat, 1 May 2010 12:30:11 +0100
Message-ID: <D8206FE7FD704D17BC7C27AC2FE3DB87@Codalogic>
To: "Casey Jordan" <casey.jordan@jorsek.com>, <xmlschema-dev@w3.org>
Is there any similarity between this problem and the intellisense operation 
in code editors where the editor suggests potential valid whole words based 
on a partially typed word?

I don't know how either would work, but when you type a letter into a code 
editor, I imagine that that letter alone is not enough to tell you whether 
it is valid and you have to track back to some anchor point (possibly a 
space or brace in the code case, and a parent element in the XML case) to 
work out the context of the new character.

HTH,

Pete Cordell
Codalogic Ltd
Interface XML to C++ the easy way using XML C++
data binding to convert XSD schemas to C++ classes.
Visit http://codalogic.com/lmx/ or http://www.xml2cpp.com
for more info

----- Original Message ----- 
From: "Casey Jordan" <casey.jordan@jorsek.com>
To: <xmlschema-dev@w3.org>
Sent: Friday, April 30, 2010 6:18 PM
Subject: Implementing the DOM3 Val Spec in Javascript, problem with UPA and 
creating PSVI.


> Hey guys/gals,
>
> Micheal Kay suggested that I posted a problem I am having here in the 
> hopes
> that someone might be able to help me.
>
> I am creating an cross browser Open Source implementation of the DOM3
> Validation 
> Spec<http://www.w3.org/TR/2004/REC-DOM-Level-3-Val-20040127/DOM3-Val.html>,
> at the moment its just a javascript implementation of a XSD validator and
> PSVI interface that conforms to the standard.
>
> I am using a method based on derivatives of regular expressions (
> Deterministic finite automaton ) and have encountered a really tricky
> problem which can be shown by the below example:
>
> Suppose I have a schema with a type like this:
>
> <xs:complexType name="my.type" mixed="false">
>        <xs:sequence>
>            <xs:element ref="h"/>
>            <xs:choice>
>                <xs:element ref="h-sub" maxOccurs="unbounded" />
>                <xs:element ref="section" />
>            </xs:choice>
>            <xs:element ref="section" minOccurs="0" maxOccurs="unbounded" 
> />
>        </xs:sequence>
>    </xs:complexType>
>
> When using finite automata, and the above pattern, while you can determine
> if a document is valid, it would be impossible to determine if a "section"
> element belonged to the xs:choice or the xs:sequence making it also
> impossible to provide a complete PSVI.
>
> For instance suppose I wanted to know what could be added to the following
> xml fragment governed by this pattern:
>
> <h>
> <section/>
> <section/>
>
> If we assumed that the first <section/> element satisfied the xs:choice,
> then all we can do is add more <section/> elements, however if we assume
> that both <section/> elements belong to the xs:sequence then its possible 
> to
> add an <h-sub/> element after the <h/>. This all becomes extremely complex
> as we start nesting more patterns.
>
> So all that being said, I've been racking my brain trying to determine if
> there is an effective way to compute a correct and complete PSVI in a
> situation where this occurs. Ideally without having to look ahead and
> remaining efficient.
>
>
> More Details - For those interested.
> -------------------------
>
> First I transform the schema into json , essentially patterns that 
> represent
> the FSA. So the above type would become the following particles:
>
> {
>   type:'sequence',
>   minOccurs:0,
>   maxOccurs:1,
>   instance:[
>      { type: 'element', ref: 'h', minOccurs:0,maxOccurs:1},
>      { type: 'choice', minOccurs:0,maxOccurs:1
>          instance:[
>                          { type: 'element', ref: 'h-sub',
> minOccurs:0,maxOccurs:1},
>                          { type: 'element', ref: 'section',
> minOccurs:0,maxOccurs:1},
>                       ]
>
>      }
>
>  ]
> }
>
>
> Then to validate a source node I apply a DFSA stepping through the pattern
> and matching it to the source instance. Elements that are 'missing' or 
> could
> be added are inserted into a PSVI which can be exposed to find out
> information like:
>
> Element.allowedNextSiblings
> Element.allowedChildren
> Element.allowedFirstChildren
>
> etc etc. As the spec describes.
>
> -- 
> --
> Casey Jordan
> Jorsek Software LLC.
> "CaseyDJordan" on LinkedIn, Twitter & Facebook
> Cell (585) 771 0189
> Office (585) 239 6060
> Jorsek.com
>
>
> This message is intended only for the use of the Addressee(s) and may
> contain information that is privileged, confidential, and/or exempt from
> disclosure under applicable law.  If you are not the intended recipient,
> please be advised that any disclosure  copying, distribution, or use of
> the information contained herein is prohibited.  If you have received
> this communication in error, please destroy all copies of the message,
> whether in electronic or hard copy format, as well as attachments, and
> immediately contact the sender by replying to this e-mail or by phone.
> Thank you.
> 
Received on Saturday, 1 May 2010 11:30:56 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 11 January 2011 00:15:20 GMT