W3C home > Mailing lists > Public > public-data-shapes-wg@w3.org > March 2015

Re: is there an implementation of Shape Expressions that correctly handles recursive shapes?

From: Eric Prud'hommeaux <eric@w3.org>
Date: Sat, 21 Mar 2015 20:15:02 -0400
To: "Peter F. Patel-Schneider" <pfpschneider@gmail.com>
Cc: RDF Data Shapes Working Group <public-data-shapes-wg@w3.org>
Message-ID: <20150322001500.GA28802@w3.org>
* Eric Prud'hommeaux <eric@w3.org> [2015-03-20 13:25-0400]
> * Peter F. Patel-Schneider <pfpschneider@gmail.com> [2015-03-20 09:29-0700]
> > On 03/20/2015 07:53 AM, Eric Prud'hommeaux wrote:
> > > * Peter F. Patel-Schneider <pfpschneider@gmail.com> [2015-03-20
> > > 06:54-0700]
> > .
> > >> 
> > >> I tried the following example of a recursive shape in all the ways that
> > >> I could think of in the online tools:
> > >> 
> > >> 
> > >> SCHEMA:
> > >> 
> > >> PREFIX ex: <http://ex.example/#> start = <S> <S> { ex:p @<T>* } <T> { (
> > >> ex:q @<Z> | ex:r @<T> ) } <Z> { }
> > >> 
> > >> DATA:
> > >> 
> > >> PREFIX ex: <http://ex.example/#> ex:a ex:p ex:b . ex:a ex:p ex:c . ex:b
> > >> ex:q ex:z . ex:c ex:q ex:z . ex:b ex:r ex:c . ex:c ex:r ex:b .
> > >> 
> > >> ShEx Demo (http://www.w3.org/2013/ShEx/FancyShExDemo) appears to go
> > >> into an infinite loop on this input.
> > > 
> > > Interesting, what browser were you using?
> > 
> > Firefox.  I have attached a screenshot.
> 
> I tracked it down and I have a race condition in my parallelized
> validator. I'm going to have to scratch my head a bit to figure out
> how to deal with this. In the mean time, I add a switch to run it in
> synchronous mode.

Added an Async switch.

http://www.w3.org/2013/ShEx/FancyShExDemo.html?starting-nodes=ex%3Aa&schema=PREFIX%20ex%3A%20%3Chttp%3A%2F%2Fex.example%2F%23%3E%0Astart%20%3D%20%3CS%3E%0A%3CS%3E%20%7B%20ex%3Ap%20%40%3CT%3E*%20%7D%0A%3CT%3E%20%7B%20(%20ex%3Aq%20%40%3CZ%3E%20%7C%20ex%3Ar%20%40%3CT%3E%20)%20%7D%0A%3CZ%3E%20%7B%20%7D%0A&data=PREFIX%20ex%3A%20%3Chttp%3A%2F%2Fex.example%2F%23%3E%0Aex%3Aa%20ex%3Ap%20ex%3Ab%20.%0Aex%3Aa%20ex%3Ap%20ex%3Ac%20.%0Aex%3Ab%20ex%3Aq%20ex%3Az%20.%0Aex%3Ac%20ex%3Aq%20ex%3Az%20.%0Aex%3Ab%20ex%3Ar%20ex%3Ac%20.%0Aex%3Ac%20ex%3Ar%20ex%3Ab%20.%0A#resNo0


> > > I wonder if I need to monkey around with patching Promises. I can check
> > > that by sticking a synchronous (doesn't use the Promises lib) in w3.org
> > > date space.
> > > 
> > > The attached recursiveShEx.png shows what I see with a local checkout of
> > > the synchronous ShEx. The '|' operator is exclusive (or exactlyOne) so
> > > the pattern failed trivially. I changed the data so that only one 
> > > disjunct matched:
> > > 
> > > PREFIX ex: <http://ex.example/#> ex:a ex:p ex:b . ex:a ex:p ex:c . #ex:b
> > > ex:q ex:z . #ex:c ex:q ex:z . ex:b ex:r ex:c . ex:c ex:r ex:b .
> > > 
> > > and saw that ex:a matched with ex:b and ex:c matching <T>:
> > > 
> > > PASS { ex:p @<T>* matched by ex:a ex:p ex:b . PASS { ex:r @<T> matched by
> > > ex:b ex:r ex:c . PASS { ex:r @<T> matched by ex:c ex:r ex:b . PASS {
> > > 
> > > } } } ex:p @<T>* matched by ex:a ex:p ex:c . PASS { ex:r @<T> matched by
> > > ex:c ex:r ex:b . PASS {
> > > 
> > > } } } No remaining triples.
> > 
> > The point of the example is to force the recursion through the negative
> > branch of the exclusive or, so removing the ex:q triples is a very different
> > example.
> 
> 
> Hmm, adding { ex:b ex:q ex:z . ex:c ex:q ex:z . } back in causes it to
> fail trivially on the XOR:
> 
> FAIL {
> Errors:
>  ☹   expected <http://ex.example/#a> <http://ex.example/#p> <http://ex.example/#c>. to match <http://ex.example/#p> @<T>*
>     FAIL {
> Errors:
>  ☹                 no matches of ((<http://ex.example/#q> @<Z>)|
> (<http://ex.example/#r> @<T>))[[]]
> Matches:
>       ex:q @<Z> matched by ex:c ex:q ex:z .
>         PASS {
> 
>         }
>       ex:r @<T> matched by ex:c ex:r ex:b .
>         PASS {
> 
>         }
>     }
> 
> Narrating that a bit I see that it failed on ex:a ex:p ex:c because it
> didn't match the XOR, because it matched both ex:q @<Z> and ex:r @<T>.
> I'm not sure that tested what you wanted to test.
> 
> 
> > >> peter
> > >> 
> > > 
> 
> 
> 
> -- 
> -ericP
> 
> office: +1.617.599.3509
> mobile: +33.6.80.80.35.59
> 
> (eric@w3.org)
> Feel free to forward this message to any list for any purpose other than
> email address distribution.
> 
> There are subtle nuances encoded in font variation and clever layout
> which can only be seen by printing this message on high-clay paper.
> 

-- 
-ericP

office: +1.617.599.3509
mobile: +33.6.80.80.35.59

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.

There are subtle nuances encoded in font variation and clever layout
which can only be seen by printing this message on high-clay paper.
Received on Sunday, 22 March 2015 00:15:05 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 19:30:18 UTC