title: qi % operator consumes (1) delimiter attributes and (2) accepts a trailing delimiter
body: <p>Fiddling around to find out about some strange behaviours of my parsers I finally ended with the finding that qi % does not exactly behave as I expect.</p>
  
  <p>First issue: In the verbous documentation a % b gets described as a shortcut for a >> *(b >> a). But it is actually not. This holds only, if you accept the b's to  be discarded.</p>
  
  <p>Say simple_id was any parser. Then actually</p>
  
  <pre><code>simple_id % lit(";") 
  </code></pre>
  
  <p>is the same as</p>
  
  <pre><code>simple_id % some_sophisticated_attribute_emitting_parser_expression
  </code></pre>
  
  <p>because the right hand side expression will be discarded in any case (i.e. does not contribute to any attributes). In detail: The first expression behaves exactly as (for example):</p>
  
  <pre><code>simple_id % string(";")
  </code></pre>
  
  <p>So string() is semantically equivalent to lit() if certain constraints hold, i.e. both live in the domain of being rh-operands of %. Here is my first question: Do you consider this to be a bug? Or is it a feature? I discussed that on the mailing list and got the answer that it's a feature, because this behaviour is documented (if you go into the very details of the doc). If you do so you find they are right.</p>
  
  <p>I want to be a user of this library. I found that things go easy with qi on higher levels of grammar. But if you get down to bits and bytes and iterator positions, life gets hard. At a point I decided not to trust any longer and to track down into qi code.</p>
  
  <p>It took me just a few minutes to track down my issue inside qi. Once having the responsible code (list.hpp) on the screen, it was obvious to me, that qi % has another issue. This here is the exact semantic of qi %</p>
  
  <pre><code>a % b &lt;- a &gt;&gt; *(b &gt;&gt; a) &gt;&gt; -(b)
  </code></pre>
  
  <p>In words: It accepts a trailing b (and consumes it) even if it is not followed by an a. This is definitely not documented. Just for fun I looked into the X3 implementation of %. The bug has been migrated and occurs there as well.</p>
  
  <p>Here are my questions: Is my analysis correct? If so, what parser library do you use? Can you recommend one? If I am wrong, where did I fail?</p>
  
  <p>I post these questions because I am not the only one struggling. I hope the infos provided here are helpful. </p>
  
  <p>Below is a self-contained working example demonstrating the issue(s) and the solution for both problems. If you run the example, have a look at the second test in particular. It shows the % consuming the trailing ; (what it should not, I think).</p>
  
  <p>My env: MSVC 2015, Target: Win32 Console, Boost 1.6.1</p>
  
  <pre><code>///////////////////////////////////////////////////////////////////////////
  // This is a self-contained demo which compiles with MSVC 2015 to Win32
  // console. Therefore it should compile with any modern compiler. :)
  //
  //
  // This demo implements a new qi operator != which does the same as %
  // does but without eating up the delimiters (unless they are non-output
  // i.e. lit).
  //
  // The implementation also shows how to fix a bug which makes the current
  // qi % operator eat a trailing b. The current implementation accepts 
  // a &gt;&gt; *(b &gt;&gt; a) &gt;&gt; -(b).
  //
  //
  // I utilize the not_equal_to proto::tag for the alternative % operation
  // See the simple rules to compare both operators.
  ///////////////////////////////////////////////////////////////////////////
  
  //#define BOOST_SPIRIT_DEBUG
  #include &lt;io.h&gt;
  #include &lt;map&gt;
  #include &lt;boost/spirit/repository/include/qi_confix.hpp&gt;
  #include &lt;boost/spirit/include/qi.hpp&gt;
  
  // Change the result type to test containers etc.
  // You may need to provide an &lt;&lt; ostream operator to have output work
  using result_type = std::string;
  
  using iterator_type = std::string::const_iterator;
  
  namespace qi = boost::spirit::qi;
  namespace mpl = boost::mpl;
  namespace proto = boost::proto;
  
  namespace maxence { namespace parser {
  ///////////////////////////////////////////////////////////////////////////////
  //  The skipper grammar (just skip this section while reading ;)
  ///////////////////////////////////////////////////////////////////////////////
  template &lt;typename Iterator&gt;
  struct skipper : qi::grammar&lt;Iterator&gt;
  {
      skipper() : skipper::base_type(start)
      {
          qi::char_type char_;
          using boost::spirit::eol;
          using boost::spirit::repository::confix;
  
          ascii::space_type space;
  
          start =
              space                               // tab/space/cr/lf
              | confix("/*", "*/")[*(char_ - "*/")] // C-style comments
              | confix("//", eol)[*(char_ - eol)] // C++-style comments
              ;
      }
  
      qi::rule&lt;Iterator&gt; start;
  };
  }}
  
  namespace boost { namespace spirit {
          ///////////////////////////////////////////////////////////////////////////
          // Enablers
          ///////////////////////////////////////////////////////////////////////////
          template &lt;&gt;
          struct use_operator&lt;qi::domain, proto::tag::not_equal_to&gt; // enables p != d
              : mpl::true_ {};
  }}
  namespace ascii = boost::spirit::ascii;
  
  namespace boost { namespace spirit { namespace qi
  {
      template &lt;typename Left, typename Right&gt;
      struct list_ex : binary_parser&lt;list_ex&lt;Left, Right&gt; &gt;
      {
          typedef Left left_type;
          typedef Right right_type;
  
          template &lt;typename Context, typename Iterator&gt;
          struct attribute
          {
              // Build a std::vector from the LHS's attribute. Note
              // that build_std_vector may return unused_type if the
              // subject's attribute is an unused_type.
              typedef typename
                  traits::build_std_vector&lt;
                  typename traits::
                  attribute_of&lt;Left, Context, Iterator&gt;::type
                  &gt;::type
                  type;
          };
  
          list_ex(Left const&amp; left_, Right const&amp; right_)
              : left(left_), right(right_) {}
  
  
  /////////////////////////////////////////////////////////////////////////
  // code from qi % operator
  //
  // Note: The original qi code accepts a &gt;&gt; *(b &gt;&gt; a) &gt;&gt; -(b)
  //       That means a trailing delimiter gets consumed
  //
  //              template &lt;typename F&gt;
  //              bool parse_container(F f) const
  //              {
  //                  // in order to succeed we need to match at least one element 
  //                  if (f(left)) return false;
  //                  typename F::iterator_type save = f.f.first;
  //
  //                  // The while clause below is wrong
  //                  // To correct that (not eat trailing delimiters) it should read: 
  //                  //  while (!(!right.parse(f.f.first, f.f.last, f.f.context, f.f.skipper, unused) &amp;&amp; f(left)))
  //                  
  //                  while (right.parse(f.f.first, f.f.last, f.f.context, f.f.skipper, unused)   &lt;--- issue!
  //                      &amp;&amp; !f(left))
  //                  {
  //                      save = f.f.first;
  //                  }
  // 
  //                  f.f.first = save;
  //              return true;
  //
  /////////////////////////////////////////////////////////////////////////
  
  
  /////////////////////////////////////////////////////////////////////////
  // replacement to allow operator not to "eat up" the "delimiter"
  //
          template &lt;typename F&gt;
          bool parse_container(F f) const
          {
              // in order to succeed we need to match at least one element 
              if (f(left)) return false;
  
              while (!(f(right) &amp;&amp; f(left)));
  
              return true;
          }
  //
  /////////////////////////////////////////////////////////////////////////
  
          template &lt;typename Iterator, typename Context
              , typename Skipper, typename Attribute&gt;
              bool parse(Iterator&amp; first, Iterator const&amp; last
                  , Context&amp; context, Skipper const&amp; skipper
                  , Attribute&amp; attr_) const
          {
              typedef detail::fail_function&lt;Iterator, Context, Skipper&gt;
                  fail_function;
  
              // ensure the attribute is actually a container type
              traits::make_container(attr_);
  
              Iterator iter = first;
              fail_function f(iter, last, context, skipper);
              if (!parse_container(detail::make_pass_container(f, attr_)))
                  return false;
  
              first = f.first;
              return true;
          }
  
          template &lt;typename Context&gt;
          info what(Context&amp; context) const
          {
              return info("list_ex",
                  std::make_pair(left.what(context), right.what(context)));
          }
  
          Left left;
          Right right;
      };
  
      ///////////////////////////////////////////////////////////////////////////
      // Parser generators: make_xxx function (objects)
      ///////////////////////////////////////////////////////////////////////////
      template &lt;typename Elements, typename Modifiers&gt;
      struct make_composite&lt;proto::tag::not_equal_to, Elements, Modifiers&gt;
          : make_binary_composite&lt;Elements, list_ex&gt;
      {};
  }}}
  
  namespace boost {   namespace spirit {  namespace traits {
      ///////////////////////////////////////////////////////////////////////////
      template &lt;typename Left, typename Right&gt;
      struct has_semantic_action&lt;qi::list_ex&lt;Left, Right&gt; &gt;
          : binary_has_semantic_action&lt;Left, Right&gt; {};
  
      ///////////////////////////////////////////////////////////////////////////
      template &lt;typename Left, typename Right, typename Attribute
          , typename Context, typename Iterator&gt;
          struct handles_container&lt;qi::list_ex&lt;Left, Right&gt;, Attribute, Context
          , Iterator&gt;
          : mpl::true_ {};
  }}}
  
  using rule_type = qi::rule &lt;iterator_type, result_type(), maxence::parser::skipper&lt;iterator_type&gt;&gt;;
  
  namespace maxence { namespace parser {
  
      template &lt;typename Iterator&gt;
      struct ident : qi::grammar &lt; Iterator, result_type() , skipper&lt;Iterator &gt;&gt;
      {
          ident();
          rule_type not_equal_to, modulus, not_used;
      };
  
      // we actually don't need the start rule (see below)
      template &lt;typename Iterator&gt;
      ident&lt;Iterator&gt;::ident() : ident::base_type(not_equal_to)
      {
          not_equal_to = (qi::alpha | '_') &gt;&gt; *(qi::alnum | '_') != qi::char_(";");
          modulus = (qi::alpha | '_') &gt;&gt; *(qi::alnum | '_') % qi::char_(";");
          modulus.name("qi modulus operator");
  
          BOOST_SPIRIT_DEBUG_NODES(
              (not_equal_to)
          )
      }
  }}
  
  
  int main()
  {
      namespace parser = maxence::parser;
  
      using rule_map_type = std::map&lt;std::string, rule_type&amp;&gt;;
      using rule_iterator_type = std::map&lt;std::string, rule_type&amp;&gt;::const_iterator;
      using ss_map_type = std::map&lt;std::string, std::string&gt;;
      using ss_iterator_type = ss_map_type::const_iterator;
  
  
      parser::ident&lt;iterator_type&gt; ident;
      parser::skipper&lt;iterator_type&gt; skipper;
  
      ss_map_type parser_input =
      {
          { "; delimited list without trailing delimiter \n(expected result: success, EOI reached)", "willy; anton" },
          { "; delimited list with trailing delimiter \n(expected result: success, EOI not reached)", "willy; anton;" }
      };
      rule_map_type rules =
      {
          { "E1", ident.not_equal_to },
          { "E2", ident.modulus }
      };
  
      for (ss_iterator_type input = parser_input.begin(); input != parser_input.end(); input++) {
          for (rule_iterator_type example = rules.begin(); example != rules.end(); example++) {
              std::string to_parse = input-&gt;second;
              ::result_type result;
              std::string parser_name = (example-&gt;second).name();
              std::cout &lt;&lt; "--------------------------------------------" &lt;&lt; std::endl;
              std::cout &lt;&lt; "Description: " &lt;&lt; input-&gt;first &lt;&lt; std::endl;
              std::cout &lt;&lt; "Parser [" &lt;&lt; parser_name &lt;&lt; "] parsing [" &lt;&lt; to_parse &lt;&lt; "]" &lt;&lt; std::endl;
              auto b(to_parse.begin()), e(to_parse.end());
  
              bool success = qi::phrase_parse(b, e, (example)-&gt;second, skipper, result);
  
              // --- test for parser success
              if (success) std::cout &lt;&lt; "Parser succeeded. Result: " &lt;&lt; result &lt;&lt; std::endl;
              else std::cout &lt;&lt; " Parser failed. " &lt;&lt; std::endl;
  
              //--- test for EOI
              if (b == e) {
                  std::cout &lt;&lt; "EOI reached.";
              } else {
                  std::cout &lt;&lt; "Failure: EOI not reached. Remaining: [";
                  while (b != e) std::cout &lt;&lt; *b++; std::cout &lt;&lt; "]";
              }
              std::cout &lt;&lt; std::endl &lt;&lt; "--------------------------------------------" &lt;&lt; std::endl;
          }
      }
      return 0;
  }
  </code></pre>
  
  <p><strong>Extension:</strong> Because of the comments I extend my post:</p>
  
  <p>My != operator is different from the % operator . The != operator would add all the 'delimiters' found to the result vector. (a != qi::char_(";,")). To introduce my proposal to % would discard useful functionality.</p>
  
  <p>Maybe there is a justification to introduce an additional operator. I think I should use another operator for that, != hurts my eyes. Anyway, the != operator has nice applications also. For example:</p>
  
  <pre><code>settings_list = name != expression;
  </code></pre>
  
  <p>I thought it is wrong that % does not eat trailing 'delimiters'. My code example above seemed to demonstrate that. Anyway, I stripped the example down to focus on that issue only. Now I know that missing ; are sitting happily somewhere in the Carribean having a Caipirinha. Better than being eaten. :)</p>
  
  <p>The example below eats the trailing 'delimiter', because it's not really trailing. The issue was my test string. The Kleene star has a zero match after the last ;. Therefore it gets eaten which is correct behaviour.</p>
  
  <p>I learned much about qi during this 'trip'. More than from the docs. Most important lesson learned: Shape your test cases carefully. A did a quick copy&amp;paste from some example without thought. That introduced the problems.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;map&gt;
  #include &lt;boost/spirit/include/qi.hpp&gt;
  
  
  namespace qi = boost::spirit::qi;
  using iterator_type = std::string::const_iterator;
  using result_type = std::string;
  
  template &lt;typename Parser&gt;
  void parse(const std::string message, const std::string&amp; input, const Parser&amp; parser)
  {
      iterator_type iter = input.begin(), end = input.end();
  
      std::vector&lt;result_type&gt; parsed_result;
  
      std::cout &lt;&lt; "-------------------------\n";
      std::cout &lt;&lt; message &lt;&lt; "\n";
      std::cout &lt;&lt; "Parsing: \"" &lt;&lt; input &lt;&lt; "\"\n";
  
      bool result = qi::phrase_parse(iter, end, parser, qi::space, parsed_result);
      if (result)
      {
          std::cout &lt;&lt; "Parser succeeded.\n";
          std::cout &lt;&lt; "Parsed " &lt;&lt; parsed_result.size() &lt;&lt; " elements:";
          for (const auto&amp; str : parsed_result)
              std::cout &lt;&lt; "[" &lt;&lt; str &lt;&lt; "]";
          std::cout &lt;&lt; std::endl;
      }
      else
      {
          std::cout &lt;&lt; "Something failed. Unparsed: \"" &lt;&lt; std::string(iter, end) &lt;&lt; "\"" &lt;&lt; std::endl;
      }
      if (iter == end) {
          std::cout &lt;&lt; "EOI reached." &lt;&lt; std::endl;
      }
      else {
          std::cout &lt;&lt; "EOI not reached. Unparsed: \"" &lt;&lt; std::string(iter, end) &lt;&lt; "\"" &lt;&lt; std::endl;
      }
      std::cout &lt;&lt; "-------------------------\n";
  
  }
  
  int main()
  {
  
      auto r1 = (*(qi::alpha | '_')) % qi::char_(";");
      auto r2 = qi::as_string[*(qi::alpha | '_')] % qi::char_(";");
  
      parse("% eating the trailing delimiter 'delimiter'",  
          "willy; anton; 1234", r1);
      parse("% eating the trailing 'delimiter' (limited as_string edition)'",
          "willy; anton; 1234", r2);
  
      return 0;
  }
  </code></pre>