How to parse a grammar into a `std::set` using `boost::spirit`?

Question

TL;DR

How to parse the result of a boost::spirit grammar into an std::set?

Full problem statement

As an exercise to learn how to use boost::spirit, I am designing a parser for X.500/LDAP Distinguished Names. The grammar can be found in a BNF format in the RFC-1779.

I "unrolled" it and translated it into boost::spirit rules. That's the first step. Basically, a DN is a set of RDN (Relative Distinguished Names) which themselves are tuples of (Key,Value) pairs.

I think about using

typedef std::unordered_map<std::string, std::string> rdn_type;

to represent each RDN. The RDNs are then gathered into a std::set<rdn_type>

My issue is that going through the (good) documentation of boost::spirit, I didn't find out how to populate the set.

My current code can be found on github and I'm trying to refine it whenever I can.

Starting a satanic dance to summon SO's most popular polar bear :p

Current code

In order to have an all-at-one-place question, I add a copy of the code here, it's a bit long so I put it at the end :)

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;

typedef std::unordered_map<std::string, std::string> dn_key_value_map;

template <typename Iterator>
struct dn_grammar_common : public qi::grammar<Iterator, std::multiset<dn_key_value_map>(), ascii::space_type> {
  struct dn_reserved_chars_ : public qi::symbols<char, char> {
    dn_reserved_chars_() {
      add
        ("\\", "\\")
        ("=" , "=")
        ("+" , "+")
        ("," , ",")
        (";" , ";")
        ("#" , "#")
        ("<" , "<")
        (">" , ">")
        ("\"", "\"")
        ("%" , "%");
    }
  } dn_reserved_chars;
  dn_grammar_common() : dn_grammar_common::base_type(dn) {
    // Useful using directives
    using namespace qi::labels;

    // Low level rules
    // Key can only contain alphanumerical characters and dashes
    key = ascii::no_case[qi::lexeme[(*qi::alnum) >> (*(qi::char_('-') >> qi::alnum))]];
    escaped_hex_char = qi::lexeme[(&qi::char_("\\")) >> qi::repeat(2)[qi::char_("0-9a-fA-F")]];
    escaped_sequence = escaped_hex_char |
                      qi::lexeme[(&qi::char_("\\")) >> dn_reserved_chars];
    // Rule for a fully escaped string (used as Attribute Value) => "..."
    quote_string = qi::lexeme[qi::lit('"') >>
      *(escaped_sequence | (qi::char_ - qi::char_("\\\""))) >>
      qi::lit('"')
    ];
    // Rule for an hexa string (used as Attribute Value) => #23AD5D...
    hex_string = (&qi::char_("#")) >> *qi::lexeme[(qi::repeat(2)[qi::char_("0-9a-fA-F")])];

    // Value is either:
    // - A regular string (that can contain escaped sequences)
    // - A fully escaped string (that can also contain escaped sequences)
    // - An hexadecimal string
    value = (qi::lexeme[*((qi::char_ - dn_reserved_chars) | escaped_sequence)]) |
            quote_string |
            hex_string;

    // Higher level rules
    rdn_pair = key >> '=' >> value;
    // A relative distinguished name consists of a sequence of pairs (Attribute = AttributeValue)
    // Separated with a +
    rdn = rdn_pair % qi::char_("+");
    // The DN is a set of RDNs separated by either a "," or a ";".
    // The two separators can coexist in a given DN, though it is not
    // recommended practice.
    dn = rdn % (qi::char_(",;"));
  }
  qi::rule<Iterator, std::set<dn_key_value_map>(), ascii::space_type> dn;
  qi::rule<Iterator, dn_key_value_map(), ascii::space_type> rdn;
  qi::rule<Iterator, std::pair<std::string, std::string>(), ascii::space_type> rdn_pair;
  qi::rule<Iterator, std::string(), ascii::space_type> key, value, hex_string, quote_string;
  qi::rule<Iterator, std::string(), ascii::space_type> escaped_hex_char, escaped_sequence;
};

Answer 1

I suspect you just need fusion/adapted/std_pair.hpp

Let me try to make it compile

Ok

1. your start rule was incompatible

    qi::rule<Iterator, std::multiset<dn_key_value_map>(), ascii::space_type> dn;
   

2. the symbol table should map to string, not char

   struct dn_reserved_chars_ : public qi::symbols<char, std::string> {
   

   or you should change the mapped values to char literals.

   Why do you use this, instead of char_("\\=+,;#<>\"%")?

Update

Have completed my review of the Grammar (purely from the implementation point-of-view, so I haven't actually read the RFC to check the assumptions).

I created a pull request here: https://github.com/Rerito/pkistore/pull/1

1. General Notes

   • unordered maps aren't sortable, so used map<string,string>
   • the outer set is technically not a set (?) in the RFC, made it a vector (also makes the output between relative domain names correspond more to input order)
   • removed superstitious includes (Fusion set/map are completely unrelated to std::set/map. Just need std_pair.hpp for maps to work)

2. Grammar rules:

   • symbols<char,char> requires char values (not "." but '.')

   • Many simplifications

     • remove &char_(...) instances (they don't match anything, it's just an assertion)
     • remove impotent no_case[]
     • removed unnecessary lexeme[] directives; most have been realized by removing the skipper from the rule declarations
     • removed some rule declarations at all (the rule def aren't complex enough to warrant the overhead incurred), e.g. hex_string

     • made key require at least one character (not checked the specs). Note how

       key = ascii::no_case[qi::lexeme[(*qi::alnum) >> (*(qi::char_('-') >> qi::alnum))]];
       

       became

       key = raw[ alnum >> *(alnum | '-') ];
       

       raw means that the input sequence will be reflected verbatim (instead of building a copy character by character)

     • reordered branches on value (not checked, but I wager unqouted strings would basically eat everything else)

     • made hexchar expose the actual data using qi::int_parser<char, 16, 2, 2>

3. Tests

   Added a test program test.cpp, based on the Examples section in the rfc (3.).

   Added some more complicated examples of my own devising.

4. Loose Ends

   To do: review the specs for actual rules and requirements on

   • escaping special characters

   • inclusion of whitespace (incl. newline characters) inside the various string flavours:

     • hex #xxxx strings might allow for newlines (makes sense to me)
     • unquoted strings might not (idem)

   Also enabled optional BOOST_SPIRIT_DEBUG

   Also made the skipper internal to the grammar (security!)

   Also made a convenience free function that makes the parser usable without leaking implementation details (Qi)

Live Demo

Live On Coliru

//#include "dn_parser.hpp"
//#define BOOST_SPIRIT_DEBUG
#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/spirit/include/qi.hpp>
#include <map>
#include <set>

namespace pkistore {
    namespace parsing {

    namespace qi      = boost::spirit::qi;
    namespace ascii   = boost::spirit::ascii;

    namespace ast {
        typedef std::map<std::string, std::string> rdn;
        typedef std::vector<rdn> dn;
    }

    template <typename Iterator>
    struct dn_grammar_common : public qi::grammar<Iterator, ast::dn()> {
        dn_grammar_common() : dn_grammar_common::base_type(start) {
            using namespace qi;

            // syntax as defined in rfc1779
            key          = raw[ alnum >> *(alnum | '-') ];

            char_escape  = '\\' >> (hexchar | dn_reserved_chars);
            quote_string = '"' >> *(char_escape | (char_ - dn_reserved_chars)) >> '"' ;

            value        =  quote_string 
                         | '#' >> *hexchar
                         | *(char_escape | (char_ - dn_reserved_chars))
                         ;

            rdn_pair     = key >> '=' >> value;

            rdn          = rdn_pair % qi::char_("+");
            dn           = rdn % qi::char_(",;");

            start        = skip(qi::ascii::space) [ dn ];

            BOOST_SPIRIT_DEBUG_NODES((start)(dn)(rdn)(rdn_pair)(key)(value)(quote_string)(char_escape))
        }

    private:
        qi::int_parser<char, 16, 2, 2> hexchar;

        qi::rule<Iterator, ast::dn()> start;

        qi::rule<Iterator, ast::dn(), ascii::space_type> dn;
        qi::rule<Iterator, ast::rdn(), ascii::space_type> rdn;
        qi::rule<Iterator, std::pair<std::string, std::string>(), ascii::space_type> rdn_pair;

        qi::rule<Iterator, std::string()> key, value, quote_string;
        qi::rule<Iterator, char()>        char_escape;

        struct dn_reserved_chars_ : public qi::symbols<char, char> {
            dn_reserved_chars_() {
                add ("\\", '\\') ("\"", '"')
                    ("=" , '=')  ("+" , '+')
                    ("," , ',')  (";" , ';')
                    ("#" , '#')  ("%" , '%')
                    ("<" , '<')  (">" , '>')
                    ;
            }
        } dn_reserved_chars;
    };

    } // namespace parsing

    static parsing::ast::dn parse(std::string const& input) {
        using It = std::string::const_iterator;

        pkistore::parsing::dn_grammar_common<It> const g;

        It f = input.begin(), l = input.end();
        pkistore::parsing::ast::dn parsed;

        bool ok = boost::spirit::qi::parse(f, l, g, parsed);

        if (!ok || (f!=l))
            throw std::runtime_error("dn_parse failure");

        return parsed;
    }
} // namespace pkistore

int main() {
    for (std::string const input : {
            "OU=Sales + CN=J. Smith, O=Widget Inc., C=US",
            "OU=#53616c6573",
            "OU=Sa\\+les + CN=J. Smi\\%th, O=Wid\\,\\;get In\\3bc., C=US",
            //"CN=Marshall T. Rose, O=Dover Beach Consulting, L=Santa Clara,\nST=California, C=US",
            //"CN=FTAM Service, CN=Bells, OU=Computer Science,\nO=University College London, C=GB",
            //"CN=Markus Kuhn, O=University of Erlangen, C=DE",
            //"CN=Steve Kille,\nO=ISODE Consortium,\nC=GB",
            //"CN=Steve Kille ,\n\nO =   ISODE Consortium,\nC=GB",
            //"CN=Steve Kille, O=ISODE Consortium, C=GB\n",
        })
    {
        auto parsed = pkistore::parse(input);

        std::cout << "===========\n" << input << "\n";
        for(auto const& dn : parsed) {
            std::cout << "-----------\n";
            for (auto const& kv : dn) {
                std::cout << "\t" << kv.first << "\t->\t" << kv.second << "\n";
            }
        }
    }
}

Prints:

===========
OU=Sales + CN=J. Smith, O=Widget Inc., C=US
-----------
    CN  ->  J. Smith
    OU  ->  Sales 
-----------
    O   ->  Widget Inc.
-----------
    C   ->  US
===========
OU=#53616c6573
-----------
    OU  ->  Sales
===========
OU=Sa\+les + CN=J. Smi\%th, O=Wid\,\;get In\3bc., C=US
-----------
    CN  ->  J. Smi%th
    OU  ->  Sa+les 
-----------
    O   ->  Wid,;get In;c.
-----------
    C   ->  US