Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

Arun Muralidharan
Hello Folks,
I have posted the question in SO as well ( http://stackoverflow.com/questions/43526708/optimizing-the-grammar ), but I believe I have better chance of getting an answer to my query here.

<Reposting the question here>

I am working on creating an xpath2.0 parser as per the RFC. It's basically a subproject of another project that I am working on.

After some initial success, I did the mistake of writing a bunch of grammar rules and AST instead of compiling and testing it at every point. After that I basically had a novel of template error messages to read (my fault actually).

I have then then tried to work my way up by trying to compile and test bits and pieces of the grammar rules individually and now I am stuck with the compilation process never ending.

I am attaching two files along with this post:
1. All the code in a single cpp file.
2. Broken up the code in multiple files as suggested before in the mailing list. (as per calc9 example)

Compiler - clang 3.8 on Mac (i7 processor 8 GB RAM)
template-depth - 1024
Boost Version - 1.59

rec_ex_orig.cc

rec_ex.tar
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

cppljevans
On 04/21/2017 01:44 AM, Arun Muralidharan wrote:

> Hello Folks,
> I have posted the question in SO as well (
> http://stackoverflow.com/questions/43526708/optimizing-the-grammar ), but I
> believe I have better chance of getting an answer to my query here.
>
> <Reposting the question here>
>
> I am working on creating an xpath2.0 parser as per the RFC. It's basically a
> subproject of another project that I am working on.
>
> After some initial success, I did the mistake of writing a bunch of grammar
> rules and AST instead of compiling and testing it at every point. After that
> I basically had a novel of template error messages to read (my fault
> actually).
>
> I have then then tried to work my way up by trying to compile and test bits
> and pieces of the grammar rules individually and now I am stuck with the
> compilation process never ending.
>
> I am attaching two files along with this post:
> 1. All the code in a single cpp file.
> 2. Broken up the code in multiple files as suggested before in the mailing
> list. (as per calc9 example)
>
> Compiler - clang 3.8 on Mac (i7 processor 8 GB RAM)
> template-depth - 1024
> Boost Version - 1.59
>
> rec_ex_orig.cc
> <http://boost.2283326.n4.nabble.com/file/n4693813/rec_ex_orig.cc>
>
> rec_ex.tar <http://boost.2283326.n4.nabble.com/file/n4693813/rec_ex.tar>
>
I suspect the problem is here:

https://github.com/cppljevans/spirit/blob/get_rhs/include/boost/spirit/home/x3/nonterminal/detail/rule.hpp#L215

When this code was compiled without -DBOOST_SPIRIT_GET_RHS_CRTP=1
it took several minutes, consuming 100% of CPU1, and steadily
increased memory consumption.  However, with
-DBOOST_SPIRIT_GET_RHS_CRTP=1, it compile in a flash, as
shown by the attached.

HTH.

-regards,
Larry




------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

rec_ex_orig.compilation (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

Arun Muralidharan
Thanks Larry. Awesome debugging!
Would be nice to learn to debug these stuff.

From the attachment you provided, it appears to me that you have applied some sort patch. Is that correct ? I could not get that to compile on my machine by just defining "BOOST_SPIRIT_GET_RHS_CRTP=1".

Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

sehe
On 21-04-17 20:25, Arun Muralidharan wrote:
> >From the attachment you provided, it appears to me that you have applied
> some sort patch. Is that correct ? I could not get that to compile on my
> machine by just defining "BOOST_SPIRIT_GET_RHS_CRTP=1".

Without further checking, I assume the "patch" is to use latest version
of X3

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

Arun Muralidharan
> Without further checking, I assume the "patch" is to use latest version of X3

Sorry, forgot to mention that. I have checked it with latest version of boost too (1.64).  Could not get it to compile using that as well.
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

cppljevans
This post has NOT been accepted by the mailing list yet.
This post was updated on .
Arun Muralidharan wrote
> Without further checking, I assume the "patch" is to use latest version of X3

Sorry, forgot to mention that. I have checked it with latest version of boost too (1.64).  Could not get it to compile using that as well.
The essence of this reply may be repeated.  I tried replying to the boost newsgroup; however,
that reply has not shown up in about 18hrs; hence, I replying here in hopes in will show up.

@Arun:

  You'll need to clone the repository:

https://github.com/cppljevans/spirit/tree/get_rhs

  to some folder, say $(get_rhs), on your hard drive.
  Then, assuming spirit is located at $(boost) on your hard drive,
  compile the source with:

g++ -std=c++14 -ftemplate-depth=1024 -I$(get_rhs)/include -I$(boost) -DBOOST_SPIRIT_GET_RHS_CRTP=1 -o rec_ex rec_ex.cc

@sehe

  I forked get_rhs from develop late last year.  Since then, as you can see from:

https://github.com/cppljevans/spirit/tree/get_rhs

  it's over 100 commits behind.

HTH.
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

Arun Muralidharan

Thanks a lot, Larry. I could compile it using the code from your branch.
So, the fix would be available now only in boost 1.65 ?


Thanks.
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

cppljevans
Arun Muralidharan wrote
Thanks a lot, Larry. I could compile it using the code from your branch.
So, the fix would be available now only in boost 1.65 ?


Thanks.
On 04/22/2017 09:19 AM, Arun Muralidharan wrote:
>
> Thanks a lot, Larry. I could compile it using the code from your branch.
> So, the fix would be available now only in boost 1.65 ?

Glad to help, Arun.

However, I'm not in charge of making changes to spirit;
hence, Sehe would be the person to ask.  

I could issue a pull request for get_rhs; however, get_rhs
is somewhat experimental.  It has a patch for another spirit
problem with attribute transforms:

https://github.com/cppljevans/spirit/blob/get_rhs/include/boost/spirit/home/x3/nonterminal/detail/rule.hpp#L383

and I'm guessing that the official maintainers want to keep
patches focused on a single problem.  I'm not even real
certain the attribute transform patch is completely
correct.  That patch may solve one problem but cause another
:(  I need better understanding of how x3 handles attributes
before I'm comfortable with the attribute transform patch.

The problem your code highlighted was that of a particular
rule recursion implementation.  The purpose of the code
linked-to in my OP:

https://github.com/cppljevans/spirit/blob/get_rhs/include/boost/spirit/home/x3/nonterminal/detail/rule.hpp#L215

(i.e. the call to make_rule_context) was to implement rule
recursion by lookup of the rhs of a rule in the context.
Apparently that method works in some cases; however, in
other cases, in particular, the case of your code, it
results in, what I would guess, is infinite template
instantiation.

I could make another branch which only solves this
make_rule_context problem, if someone who is responsible for
making changes to spirit would think that's the way to go.
However, that's gonna break some code.  In particular:

https://github.com/boostorg/spirit/blob/master/test/x3/rule1.cpp

The solution for those breaking cases would be using the
BOOST_SPIRIT_DEFINE method for implementing rule recursion
instead of the make_rule_context method.  This one-method
for rule recursion position was advocated in the .txt file
attachment to:

  http://boost.2283326.n4.nabble.com/x3-devel-why-2-methods-linking-rule-to-RHS-td4688021.html

However, that post got no interest.

So, there are pro's and con's to the patch, but, hopefully,
your code example may generate more interest in the
one-method rule recursion design.

Sorry I can't give a more definite answer :(

-Larry


Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

Arun Muralidharan
Thanks for the detailed information Larry.

So, I guess I am lucky to do what ever I am doing as a side project instead of directly doing it for my job.

@Sehe, can you shed some light on how the patch by Larry can be propagated to the mainline ? If there are any more tests to be done, I would be happy to do it.

Thanks.
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

sehe
In reply to this post by cppljevans
On 23-04-17 11:12, cppljevans wrote:
> However, I'm not in charge of making changes to spirit;
> hence, Sehe would be the person to ask.  

Just to correct the record, I like Spirit but I'm not an active
dev/maintainer. [In fact, I don't know how much of it is implemented]


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

cppljevans
Sorry for jumping to wrong conclusion, Sehe.

According to:

  https://github.com/boostorg/spirit

maybe djowel (Joel Guzman) is the person to ask.

Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

cppljevans
In reply to this post by Arun Muralidharan
On 04/23/2017 09:38 AM, Arun Muralidharan wrote:

> Thanks for the detailed information Larry.
>
> So, I guess I am lucky to do what ever I am doing as a side project instead
> of directly doing it for my job.
>
> @Sehe, can you shed some light on how the patch by Larry can be propagated
> to the mainline ? If there are any more tests to be done, I would be happy
> to do it.
>
> Thanks.
>
You're welcome.

I've tried to isolate the reason why the code fails.  See if the
following change doesn't avoid the problem:

//#define AS_WITH_ID
   auto as = [](auto p)
     {
     #ifdef AS_WITH_ID
       return x3::rule<struct _>{} = as_parser(p);
     #else
       return p;
     #endif
     };

In a much simplified version of your code, when this is run, compilation
succeeds; however, when defined(AS_WITH_ID), then the compilation does
*not* finish after 5 seconds.

HTH.

-regards,
Larry



------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

cppljevans
On 05/02/2017 03:12 PM, Larry Evans wrote:

> On 04/23/2017 09:38 AM, Arun Muralidharan wrote:
>> Thanks for the detailed information Larry.
>>
>> So, I guess I am lucky to do what ever I am doing as a side project instead
>> of directly doing it for my job.
>>
>> @Sehe, can you shed some light on how the patch by Larry can be propagated
>> to the mainline ? If there are any more tests to be done, I would be happy
>> to do it.
>>
>> Thanks.
>>
> You're welcome.
>
> I've tried to isolate the reason why the code fails.  See if the
> following change doesn't avoid the problem:
>
> //#define AS_WITH_ID
>    auto as = [](auto p)
>      {
>      #ifdef AS_WITH_ID
>        return x3::rule<struct _>{} = as_parser(p);
>      #else
>        return p;
>      #endif
>      };
>
> In a much simplified version of your code, when this is run, compilation
> succeeds; however, when defined(AS_WITH_ID), then the compilation does
> *not* finish after 5 seconds.
>
> HTH.
>
> -regards,
> Larry
Sorry, I should have been more specific.  The code here:

https://github.com/cppljevans/spirit/blob/get_rhs/workbench/x3/rec_ex_orig/rec_ex_orig.no_attr.cpp

compiles when !defined(AS_WITH_ID) but fails when defined(AS_WITH_ID).
I'm still trying to understand why :(




------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Spirit-X3 | Boost 1.59 | Compilation never finishes for a recursive grammar

cppljevans
In reply to this post by sehe
On 04/21/2017 02:29 PM, Seth wrote:
> On 21-04-17 20:25, Arun Muralidharan wrote:
>> >From the attachment you provided, it appears to me that you have applied
>> some sort patch. Is that correct ? I could not get that to compile on my
>> machine by just defining "BOOST_SPIRIT_GET_RHS_CRTP=1".
>
> Without further checking, I assume the "patch" is to use latest version
> of X3
>
As shown by:

   https://github.com/cppljevans/spirit/tree/get_rhs

it is now up-to-date with develop branch of:

   https://github.com/boostorg/spirit



------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general