[Boost-users] [Spirit] Stack overflow, suspect infinite recursion

Subject: [Boost-users] [Spirit] Stack overflow, suspect infinite recursion
From: Simon (turner25_at_[hidden])
Date: 2013-06-03 10:26:14

Hi,

  I'm writing a math string parser with boost::spirit and I'm stuck on this
stack overflow.  I've seen this before when I wrote a rule that was
misleading.

  It's the second time I get these and I'm really not sure how I can
troubleshoot this kind of problem.  Help would be greatly appreciated.

  I have no issues parsing the forms "A?B" (where A,B are floats and ? is
an arithmetic operator +,-,*,/).  No issues parsing "(A)" either...  At the
moment of writing this, I haven't tried but I will be trying to parse
simpler forms like "(A)?B" and "A?(B)",  "(A?B)",  "(A?B)?C" and
"A?(B?C)"...  I suspect going through them will eventually help me fix the
bug with the form below...

  Below is the final output of my program through valgrind and the rules I
have are at the end of my post.  I suspect the prob is in the definition
for start, operation or operand  (an operand may be the result of an
operation and an operation is performed on operands).  There may be a nasty
infinite recursion between operand and operation...  The resulting objects
are polymorphic and they are correct (as seen when used without spirit).

Simon

   Parsing operations such as ( A?B ) ? ( C?D )
Parsing: (0.1+1.9)+(4.2+6.1)  ->  (AB=2.000000, CD=10.300000,
ABCD=12.300000)
==17013== Stack overflow in thread 1: can't grow stack to 0xb907cfbc
==17013==
==17013== Process terminating with default action of signal 11 (SIGSEGV)
==17013==  Access not within mapped region at address 0xB907CFBC
==17013==    at 0x13487A: bool
boost::spirit::qi::action<boost::spirit::qi::reference<boost::spirit::qi::rule<__gnu_cxx::__normal_iterator<char
const*, std::string>, std::string ()(), boost::spirit::unused_type,
boost::spirit::unused_type, boost::spirit::unused_type> const>,
boost::phoenix::actor<boost::phoenix::composite<boost::phoenix::assign_eval,
boost::fusion::vector<boost::spirit::attribute<0>,
boost::phoenix::composite<boost::phoenix::detail::new_eval<HS::Language::axIdentifier>,
boost::fusion::vector<boost::spirit::argument<0>, boost::fusion::void_,
boost::fusion::void_, boost::fusion::void_, boost::fusion::void_,
boost::fusion::void_, boost::fusion::void_, boost::fusion::void_,
boost::fusion::void_, boost::fusion::void_> >, boost::fusion::void_,
boost::fusion::void_, boost::fusion::void_, boost::fusion::void_,
boost::fusion::void_, boost::fusion::void_, boost::fusion::void_,
boost::fusion::void_> > > >::parse<__gnu_cxx::__normal_iterator<char
const*, std::string>,
boost::spirit::context<boost::fusion::cons<HS::Language::axIdentifier*&,
boost::fusion::nil>, boost::fusion::vector0<void> >,
boost::spirit::unused_type, boost::spirit::unused_type
const>(__gnu_cxx::__normal_iterator<char const*, std::string>&,
__gnu_cxx::__normal_iterator<char const*, std::string> const&,
boost::spirit::context<boost::fusion::cons<HS::Language::axIdentifier*&,
boost::fusion::nil>, boost::fusion::vector0<void> >&,
boost::spirit::unused_type const&, boost::spirit::unused_type const&) const
(action.hpp:50)
==17013==  If you believe this happened as a result of a stack
==17013==  overflow in your program's main thread (unlikely but
==17013==  possible), you can try to increase the size of the
==17013==  main thread stack using the --main-stacksize= flag.
==17013==  The main thread stack size used in this run was 96002048.
==17013== Stack overflow in thread 1: can't grow stack to 0xb907cfb8
==17013==
==17013== Process terminating with default action of signal 11 (SIGSEGV)
==17013==  Access not within mapped region at address 0xB907CFB8
==17013==    at 0x48224AC: _vgnU_freeres (vg_preloaded.c:58)
==17013==  If you believe this happened as a result of a stack
==17013==  overflow in your program's main thread (unlikely but
==17013==  possible), you can try to increase the size of the
==17013==  main thread stack using the --main-stacksize= flag.
==17013==  The main thread stack size used in this run was 96002048.
==17013==
==17013== HEAP SUMMARY:
==17013==     in use at exit: 410,754 bytes in 25,628 blocks
==17013==   total heap usage: 25,847 allocs, 219 frees, 437,192 bytes
allocated
==17013==
==17013== LEAK SUMMARY:
==17013==    definitely lost: 409,080 bytes in 25,571 blocks
==17013==    indirectly lost: 432 bytes in 27 blocks
==17013==      possibly lost: 1,050 bytes in 20 blocks
==17013==    still reachable: 192 bytes in 10 blocks
==17013==         suppressed: 0 bytes in 0 blocks
==17013== Rerun with --leak-check=full to see details of leaked memory
==17013==
==17013== For counts of detected and suppressed errors, rerun with: -v
==17013== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Segmentation fault

Extract of the grammar:

constnum =
  double_
  [_val = new_<axConstant>(_1)];

alpha_numeric =
  alpha >> +(alnum);
 ident =
  alpha_numeric
  [_val = new_<axIdentifier>(_1)];
 operand =
  ident | constnum | operation;

addition =
  (operand >> lit('+') >> operand)
  [_val = new_<axAddition>(_1,_2)];

substraction =
  (operand >> lit('-') >> operand)
  [_val = new_<axSubstraction>(_1,_2)];

multiplication =
  (operand >> lit('*') >> operand)
  [_val = new_<axMultiplication>(_1,_2)];

division =
  (operand >> lit('/') >> operand)
  [_val = new_<axDivision>(_1,_2)];
 precedence =
  (lit('(') >> operand >> lit(')'))
  [_val = new_<axPrecedence>(_1)];
 operation =
  precedence | multiplication | division | addition | substraction;

start =
  operation | operand;

      }

      boost::spirit::qi::rule<Iterator, AX*()>  start;

      boost::spirit::qi::rule<Iterator, std::string()>   alpha_numeric;
      boost::spirit::qi::rule<Iterator, axIdentifier*()>    ident;
      boost::spirit::qi::rule<Iterator, axConstant*()>   constnum;
      boost::spirit::qi::rule<Iterator, axOperand*()>    operand;

      boost::spirit::qi::rule<Iterator, axOperation*()>      operation;

      boost::spirit::qi::rule<Iterator, axAddition*()>       addition;
      boost::spirit::qi::rule<Iterator, axSubstraction*()>   substraction;
      boost::spirit::qi::rule<Iterator, axMultiplication*()> multiplication;
      boost::spirit::qi::rule<Iterator, axDivision*()>       division;
      boost::spirit::qi::rule<Iterator, axPrecedence*()>     precedence;

    };