Boost › The Spirit Parser Library › spirit-general

Proposal for qi::seek[] directive

Classic

List

Threaded

18 messages Options

TONGARI

Proposal for qi::seek[] directive

Hi there,

I've made this component for months, and I'm now ready for a review.

The doc:
http://jamboree.zzl.org/qi/seek.html

The src:
https://github.com/jamboree/boost-jamboree-spirit/blob/master/boost/spirit/repository/home/qi/directive/seek.hpp

Example:
https://github.com/jamboree/boost-jamboree-spirit/blob/master/libs/spirit/repository/example/qi/seek.cpp

If you find any problem in the impl or the doc (the dead links will be fixed once it's in boost), please tell me.

If the developers agree, please give me further instructions, I'll make a patch ASAP.

Thanks.

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

Remove Ads

teajay

Re: Proposal for qi::seek[] directive

Le 21/09/2011 16:59, TONGARI a écrit :

> Hi there,
>
> I've made this component for months, and I'm now ready for a review.
>
> The doc:
> http://jamboree.zzl.org/qi/seek.html
>
> The src:
> https://github.com/jamboree/boost-jamboree-spirit/blob/master/boost/spirit/repository/home/qi/directive/seek.hpp
>
> Example:
> https://github.com/jamboree/boost-jamboree-spirit/blob/master/libs/spirit/repository/example/qi/seek.cpp
>
>
> If you find any problem in the impl or the doc (the dead links will be
> fixed once it's in boost), please tell me.
>
> If the developers agree, please give me further instructions, I'll make
> a patch ASAP.
>
>
> Thanks.
>
>
>
> ------------------------------------------------------------------------------
> All the data continuously generated in your IT infrastructure contains a
> definitive record of customers, application performance, security
> threats, fraudulent activity and more. Splunk takes this data and makes
> sense of it. Business sense. IT sense. Common sense.
> http://p.sf.net/sfu/splunk-d2dcopy1
>
>
>
> _______________________________________________
> Spirit-general mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/spirit-general

I've just looked at the docs and the code, and it looks just fine. Did
you consider generalizing this idea to inject or switch the skipper
during parsing ?

If we use to following notation : seek[a]

what you actually do with this directive is change the skipper to "!a"
and expect 'a' to match after skipping.

You could achieve just the same thing with way much more flexibilty by
adding an argument to select which skipper to inject in the parsing loop
: use_skipper[!a,a]

I don't know if this idea is any good. Up to you to decide.

Regards,

Thomas Bernard

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

TONGARI

Re: Proposal for qi::seek[] directive

2011/9/22 teajay <[hidden email]>

I've just looked at the docs and the code, and it looks just fine. Did
you consider generalizing this idea to inject or switch the skipper
during parsing ?

Not sure what you mean. There's already skip[] directive.

If we use to following notation : seek[a]

what you actually do with this directive is change the skipper to "!a"
and expect 'a' to match after skipping.

Not exactly, "!a" itself has to be passed a skipper.
Actually seek[a] is semantically equal to *!a >> a, but I believe it is more efficient.

You could achieve just the same thing with way much more flexibilty by
adding an argument to select which skipper to inject in the parsing loop
: use_skipper[!a,a]

Not sure what this syntax means.

I don't know if this idea is any good. Up to you to decide.

If you could elaborate... I just can't get your idea.

Regards,

Thomas Bernard

Thanks for your feedback.

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

TONGARI

Re: Proposal for qi::seek[] directive

2011/9/22 TONGARI <[hidden email]>

2011/9/22 teajay <[hidden email]>
If we use to following notation : seek[a]

what you actually do with this directive is change the skipper to "!a"
and expect 'a' to match after skipping.

Not exactly, "!a" itself has to be passed a skipper.
Actually seek[a] is semantically equal to *!a >> a, but I believe it is more efficient.

Sorry, the explanation is wrong, it equals to "omit[*(char_ - a)] >> a".
Note that "!a" doesn't consume input, so it's another reason that "!a" can't be a skipper.

Dainis Polis

Re: [?? Probable Spam] Proposal for qi::seek[] directive

In reply to this post by TONGARI

In docs maybe somebody interested what "line" contains.

On 21.09.2011 17:59, TONGARI wrote:
> Hi there,
>
> I've made this component for months, and I'm now ready for a review.
>
> The doc:
> http://jamboree.zzl.org/qi/seek.html

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

Dainis Polis

Re: [?? Probable Spam] Proposal for qi::seek[] directive

Sorry , i miss :

Input:

1 will not be outputted while #2, ##3 and # 4 will.

On 22.09.2011 8:06, Dainis Polis wrote:
> In docs maybe somebody interested what "line" contains.
>
>

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

Joel de Guzman-2

Re: Proposal for qi::seek[] directive

In reply to this post by TONGARI

On 9/21/2011 10:59 PM, TONGARI wrote:

I like it!

Regards,
--
Joel de Guzman
http://www.boostpro.com
http://boost-spirit.com

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

TONGARI

Re: Proposal for qi::seek[] directive

2011/9/22 Joel de Guzman <[hidden email]>

On 9/21/2011 10:59 PM, TONGARI wrote:
> Hi there,
>
> I've made this component for months, and I'm now ready for a review.
>
> The doc:
> http://jamboree.zzl.org/qi/seek.html
>
> The src:
> https://github.com/jamboree/boost-jamboree-spirit/blob/master/boost/spirit/repository/home/qi/directive/seek.hpp
>
> Example:
> https://github.com/jamboree/boost-jamboree-spirit/blob/master/libs/spirit/repository/example/qi/seek.cpp
>
>
> If you find any problem in the impl or the doc (the dead links will be fixed once it's in
> boost), please tell me.
>
> If the developers agree, please give me further instructions, I'll make a patch ASAP.

I like it!

OK to submit?

Anyway, I attach the patches in this mail.
One contains the headers, the other contains the docs, example and test.

seek_src.patch (9K) Download Attachment

seek_doc.patch (18K) Download Attachment

Stewart, Robert

Re: Proposal for qi::seek[] directive

In reply to this post by TONGARI

TONGARI [mailto:[hidden email]] wrote:
>
> I've made this component for months, and I'm now ready for a
> review.

That will be a very nice addition!

> The doc:
> http://jamboree.zzl.org/qi/seek.html

The description definitely needs help. The layout doesn't quite match exist parser directive sections. My suggestion:

================
Parser Directive Seek a Match (seek[])

Description

The seek[] directive skips all input until the subject parser matches. On failure, the current position is the end of the input.
================

The Notation section is malformed. The heading is too small and the contents should be on a single line.

The first line of the second column of the table in the Attributes section has an extraneous parenthesis.

s/for the full example code, see seek.cpp/For the full source of the example, see seek.cpp./, though there are no similar links in the existing documentation (PDF, anyway).

I'd think you should claim copyright to that page.

_____
Rob Stewart [hidden email]
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com

________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

TONGARI

Re: Proposal for qi::seek[] directive

2011/9/23 Stewart, Robert <[hidden email]>

TONGARI [mailto:[hidden email]] wrote:
>
> I've made this component for months, and I'm now ready for a
> review.

That will be a very nice addition!

> The doc:
> http://jamboree.zzl.org/qi/seek.html

The description definitely needs help. The layout doesn't quite match exist parser directive sections. My suggestion:

================
Parser Directive Seek a Match (seek[])

Well, it's a plague that Spirit and Spirit Repository use different naming convention and content layout.

I chose to follow the naming convention in Spirit Repository, while following the content layout in Spirit.

Description

The seek[] directive skips all input until the subject parser matches. On failure, the current position is the end of the input.

================

I'll take it, thanks.

The Notation section is malformed. The heading is too small and the contents should be on a single line.

It's generated by qbk, and the contents are 2 lines in other Spirit docs as well.

The first line of the second column of the table in the Attributes section has an extraneous parenthesis.

I'll fix it.

s/for the full example code, see seek.cpp/For the full source of the example, see seek.cpp./, though there are no similar links in the existing documentation (PDF, anyway).

The wording is actually (IIRC) stolen from other doc, but I'll change it if that makes it better.

I'd think you should claim copyright to that page.

I've seen no other contributors in Spirit Repository do this, I have no idea.

Thanks for your feedback, Rob.

teajay

Re: Proposal for qi::seek[] directive

In reply to this post by TONGARI

When I looked at the code I though it would be possible to use an
additional skipper to do the skipping until the parser embedded in the
directive matches. But this would have been equivalent to writing

"omit[*(char_ - a)] >> a".

Thinking about it again, using a skipper to skip to the correct position
completely misses the point you are trying to address.

Now I realize that what I was actually trying to suggest, is to provide
a way of modifying the way the iterator is incremented inside the for
loop until the internal parser matches. This could in some scenarios be
helpful to seek more rapidly to the location of a potential match.

If for example I know that valid records that need to be parsed are
aligned on some specific width ( for example 4 byte aligned data) then I
don't need to test the success of the embedded parser on every single
byte position.

This could even be more useful, if the seek directive would accept a
lazy skip step size argument. This could help in parsing chunk oriented
formats where the chunk size would be read and passed to the sleek
directive to skip unnecessary chunks.

I think I got my suggestion right this time, and I hope you can make
sense of it :)

Regards,
Thomas Bernard

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

TONGARI

Re: Proposal for qi::seek[] directive

2011/9/23 teajay <[hidden email]>

When I looked at the code I though it would be possible to use an
additional skipper to do the skipping until the parser embedded in the
directive matches. But this would have been equivalent to writing

"omit[*(char_ - a)] >> a".

Thinking about it again, using a skipper to skip to the correct position
completely misses the point you are trying to address.

Now I realize that what I was actually trying to suggest, is to provide
a way of modifying the way the iterator is incremented inside the for
loop until the internal parser matches. This could in some scenarios be
helpful to seek more rapidly to the location of a potential match.

So you're suggesting "seek(step)[a]"?

That's an interesting idea, but here's a question:

Where should it (re)start the matching?

1/ fixed position. Keeps the start pos (note: non-skipped) and adds step to it as next start pos.

2/ relative position. Restarts at the skipped (by the subject parser) pos + step.

I think only 1 is useful in practice, and is most probably what you had in mind.

If for example I know that valid records that need to be parsed are
aligned on some specific width ( for example 4 byte aligned data) then I
don't need to test the success of the embedded parser on every single
byte position.

This could even be more useful, if the seek directive would accept a
lazy skip step size argument. This could help in parsing chunk oriented
formats where the chunk size would be read and passed to the sleek
directive to skip unnecessary chunks.

I think they're all doable.

Do you have any real-world example at this point?

I think I got my suggestion right this time, and I hope you can make
sense of it :)

Yeah, I got it, I'll take some time to make a prototype.

Stewart, Robert

Re: Proposal for qi::seek[] directive

In reply to this post by TONGARI

TONGARI [mailto:[hidden email]] wrote:
> 2011/9/23 Stewart, Robert <[hidden email]>
>
> > The Notation section is malformed. The heading is too small
> > and the contents should be on a single line.
>
> It's generated by qbk, and the contents are 2 lines in other
> Spirit docs as well.

I didn't see that in the PDF for skip[], etc. It may be a PDF vs. HTML rendering issue.

_____
Rob Stewart [hidden email]
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com

________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

------------------------------------------------------------------------------
All of the data generated in your IT infrastructure is seriously valuable.
Why? It contains a definitive record of application performance, security
threats, fraudulent activity, and more. Splunk takes this data and makes
sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-d2dcopy2
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

teajay

Re: Proposal for qi::seek[] directive

In reply to this post by TONGARI

Le 22/09/2011 22:35, TONGARI a écrit :

> 2011/9/23 teajay <[hidden email] <mailto:[hidden email]>>
>
> When I looked at the code I though it would be possible to use an
> additional skipper to do the skipping until the parser embedded in the
> directive matches. But this would have been equivalent to writing
>
> "omit[*(char_ - a)] >> a".
>
> Thinking about it again, using a skipper to skip to the correct position
> completely misses the point you are trying to address.
>
> Now I realize that what I was actually trying to suggest, is to provide
> a way of modifying the way the iterator is incremented inside the for
> loop until the internal parser matches. This could in some scenarios be
> helpful to seek more rapidly to the location of a potential match.
>
>
> So you're suggesting "seek(step)[a]"?
> That's an interesting idea, but here's a question:
>
> Where should it (re)start the matching?
> 1/ fixed position. Keeps the start pos (note: non-skipped) and adds step
> to it as next start pos.
> 2/ relative position. Restarts at the skipped (by the subject parser)
> pos + step.

I think it would make more sense to restart at the skipped position. If
the step size is smaller than the number of characters skipped then the
next call to the internal parser will skip the same characters again
which is unecessary. Therefor I think solution 2) make more sense.

>
> I think only 1 is useful in practice, and is most probably what you had
> in mind.
>
> If for example I know that valid records that need to be parsed are
> aligned on some specific width ( for example 4 byte aligned data) then I
> don't need to test the success of the embedded parser on every single
> byte position.
>
> This could even be more useful, if the seek directive would accept a
> lazy skip step size argument. This could help in parsing chunk oriented
> formats where the chunk size would be read and passed to the sleek
> directive to skip unnecessary chunks.
>
>
> I think they're all doable.
> Do you have any real-world example at this point?
>

One example I can think of the elf/dwarf debug format. But there most
probably many other such formats out there.

> I think I got my suggestion right this time, and I hope you can make
> sense of it :)
>
> Yeah, I got it, I'll take some time to make a prototype.
>
>
>
>
>
> ------------------------------------------------------------------------------
> All the data continuously generated in your IT infrastructure contains a
> definitive record of customers, application performance, security
> threats, fraudulent activity and more. Splunk takes this data and makes
> sense of it. Business sense. IT sense. Common sense.
> http://p.sf.net/sfu/splunk-d2dcopy1
>
>
>
> _______________________________________________
> Spirit-general mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/spirit-general

------------------------------------------------------------------------------
All of the data generated in your IT infrastructure is seriously valuable.
Why? It contains a definitive record of application performance, security
threats, fraudulent activity, and more. Splunk takes this data and makes
sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-d2dcopy2
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

TONGARI

Re: Proposal for qi::seek[] directive

2011/9/24 teajay <[hidden email]>

> Where should it (re)start the matching?
> 1/ fixed position. Keeps the start pos (note: non-skipped) and adds step
> to it as next start pos.
> 2/ relative position. Restarts at the skipped (by the subject parser)
> pos + step.

I think it would make more sense to restart at the skipped position. If
the step size is smaller than the number of characters skipped then the
next call to the internal parser will skip the same characters again
which is unecessary. Therefor I think solution 2) make more sense.

Sure? Consider this example:

Parser: seek(4)['@']
Skipper: qi::digit
Input: "12X4@678"

1/ fails at X, restarts at @ -> bingo!
2/ fails at X, restarts at 7 -> alas!

BTW, 'step', 'stride', 'align', or something else, which is better to describe this?

Stewart, Robert

Re: Proposal for qi::seek[] directive

TONGARI [mailto:[hidden email]] wrote:

> 2011/9/24 teajay <[hidden email]>
>
> > > Where should it (re)start the matching?
> > > 1/ fixed position. Keeps the start pos (note: non-skipped)
> > > and adds step to it as next start pos.
> > > 2/ relative position. Restarts at the skipped (by the
> > > subject parser) pos + step.
> >
> > I think it would make more sense to restart at the skipped
> > position. If the step size is smaller than the number of
> > characters skipped then the next call to the internal parser
> > will skip the same characters again which is unecessary.
> > Therefor I think solution 2) make more sense.
>
> Sure? Consider this example:
>
> Parser: seek(4)['@']
> Skipper: qi::digit
> Input: "12X4@678"
>
> 1/ fails at X, restarts at @ -> bingo!
> 2/ fails at X, restarts at 7 -> alas!

FWIW, since the failure position is not deterministic based upon the starting position, it seems like there would be little control over what is parsed when skipping after failures.

However, must you choose? Why not provide an option for how it restarts, or just provide two directives?

> BTW, 'step', 'stride', 'align', or something else, which is
> better to describe this?

"Step" is used with loops, which this uses but isn't.

"Align" is not unreasonable for 1/, though I'd call it "alignment".

"Stride" is quite good for both 1/ and 2/.

_____
Rob Stewart [hidden email]
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com

________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

------------------------------------------------------------------------------
All of the data generated in your IT infrastructure is seriously valuable.
Why? It contains a definitive record of application performance, security
threats, fraudulent activity, and more. Splunk takes this data and makes
sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-d2dcopy2
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

TONGARI

Re: Proposal for qi::seek[] directive

2011/9/24 Stewart, Robert <[hidden email]>

TONGARI [mailto:[hidden email]] wrote:

> 2011/9/24 teajay <[hidden email]>
>
> > > Where should it (re)start the matching?
> > > 1/ fixed position. Keeps the start pos (note: non-skipped)
> > > and adds step to it as next start pos.
> > > 2/ relative position. Restarts at the skipped (by the
> > > subject parser) pos + step.
> >
> > I think it would make more sense to restart at the skipped
> > position. If the step size is smaller than the number of
> > characters skipped then the next call to the internal parser
> > will skip the same characters again which is unecessary.
> > Therefor I think solution 2) make more sense.
>
> Sure? Consider this example:
>
> Parser: seek(4)['@']
> Skipper: qi::digit
> Input: "12X4@678"
>
> 1/ fails at X, restarts at @ -> bingo!
> 2/ fails at X, restarts at 7 -> alas!

FWIW, since the failure position is not deterministic based upon the starting position, it seems like there would be little control over what is parsed when skipping after failures.

However, must you choose? Why not provide an option for how it restarts, or just provide two directives?

Does 2/ has any practical use case? I just can't come up with one.

Actually, it's the use of skipper that differentiates the 2 polices.
However, I think skipper is needless for any reasonable format that could parsed this way.

> BTW, 'step', 'stride', 'align', or something else, which is
> better to describe this?

"Step" is used with loops, which this uses but isn't.

"Align" is not unreasonable for 1/, though I'd call it "alignment".

"Stride" is quite good for both 1/ and 2/.

I'll go with 'stride'.

TONGARI

Re: Proposal for qi::seek[] directive

A quick heads-up:

I just implemented the "strided-seek" (for case 1), here's the src:

https://github.com/jamboree/boost-jamboree-spirit/blob/ex/boost/spirit/repository/home/qi/directive/seek.hpp

and the test:

https://github.com/jamboree/boost-jamboree-spirit/blob/ex/libs/spirit/repository/test/qi/strided_seek.cpp

Comments are welcome.