source: NonGTP/Boost/boost/spirit/tree/common.hpp @ 857

Revision 857, 42.8 KB checked in by igarcia, 19 years ago (diff)
Line 
1/*=============================================================================
2    Copyright (c) 2001-2003 Daniel Nuffer
3    http://spirit.sourceforge.net/
4
5    Use, modification and distribution is subject to the Boost Software
6    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7    http://www.boost.org/LICENSE_1_0.txt)
8=============================================================================*/
9#ifndef BOOST_SPIRIT_TREE_COMMON_HPP
10#define BOOST_SPIRIT_TREE_COMMON_HPP
11
12#include <vector>
13#include <algorithm>
14
15#include <boost/ref.hpp>
16#include <boost/call_traits.hpp>
17#include <boost/spirit/core.hpp>
18#include <boost/detail/iterator.hpp> // for boost::detail::iterator_traits
19
20#if defined(BOOST_SPIRIT_DEBUG) && \
21    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
22#include <iostream>
23#include <boost/spirit/debug/debug_node.hpp>
24#endif
25
26namespace boost { namespace spirit {
27
28template <typename T>
29struct tree_node;
30
31template <typename IteratorT = char const*, typename ValueT = nil_t>
32struct node_iter_data;
33
34template <typename T>
35void swap(tree_node<T>& a, tree_node<T>& b);
36
37template <typename T, typename V>
38void swap(node_iter_data<T, V>& a, node_iter_data<T, V>& b);
39
40namespace impl {
41    template <typename T>
42    inline void cp_swap(T& t1, T& t2);
43}
44
45template <typename T>
46struct tree_node
47{
48    typedef T parse_node_t;
49    typedef std::vector<tree_node<T> > children_t;
50    typedef typename children_t::iterator tree_iterator;
51    typedef typename children_t::const_iterator const_tree_iterator;
52
53    T value;
54    children_t children;
55
56    tree_node()
57        : value()
58        , children()
59    {}
60
61    explicit tree_node(T const& v)
62        : value(v)
63        , children()
64    {}
65
66    tree_node(T const& v, children_t const& c)
67        : value(v)
68        , children(c)
69    {}
70
71    void swap(tree_node<T>& x)
72    {
73        impl::cp_swap(value, x.value);
74        impl::cp_swap(children, x.children);
75    }
76
77// Intel V5.0.1 has a problem without this explicit operator=
78    tree_node &operator= (tree_node const &rhs)
79    {
80        tree_node(rhs).swap(*this);
81        return *this;
82    }
83};
84
85#if defined(BOOST_SPIRIT_DEBUG) && \
86    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
87template <typename T>
88inline std::ostream&
89operator<<(std::ostream& o, tree_node<T> const& n)
90{
91    static int depth = 0;
92    o << "\n";
93    for (int i = 0; i <= depth; ++i)
94    {
95        o << "\t";
96    }
97    o << "(depth = " << depth++ << " value = " << n.value;
98    int c = 0;
99    for (typename tree_node<T>::children_t::const_iterator it = n.children.begin();
100         it != n.children.end(); ++it)
101    {
102        o << " children[" << c++ << "] = " << *it;
103    }
104    o << ")";
105    --depth;
106    return o;
107}
108#endif
109
110//////////////////////////////////
111template <typename IteratorT, typename ValueT>
112struct node_iter_data
113{
114    typedef IteratorT iterator_t;
115    typedef IteratorT /*const*/ const_iterator_t;
116
117    node_iter_data()
118        : first(), last(), is_root_(false), parser_id_(), value_()
119        {}
120
121    node_iter_data(IteratorT const& _first, IteratorT const& _last)
122        : first(_first), last(_last), is_root_(false), parser_id_(), value_()
123        {}
124
125    void swap(node_iter_data& x)
126    {
127        impl::cp_swap(first, x.first);
128        impl::cp_swap(last, x.last);
129        impl::cp_swap(parser_id_, x.parser_id_);
130        impl::cp_swap(is_root_, x.is_root_);
131        impl::cp_swap(value_, x.value_);
132    }
133
134    IteratorT begin()
135    {
136        return first;
137    }
138
139    IteratorT const& begin() const
140    {
141        return first;
142    }
143
144    IteratorT end()
145    {
146        return last;
147    }
148
149    IteratorT const& end() const
150    {
151        return last;
152    }
153
154    bool is_root() const
155    {
156        return is_root_;
157    }
158
159    void is_root(bool b)
160    {
161        is_root_ = b;
162    }
163
164    parser_id id() const
165    {
166        return parser_id_;
167    }
168
169    void id(parser_id r)
170    {
171        parser_id_ = r;
172    }
173
174    ValueT const& value() const
175    {
176        return value_;
177    }
178
179    void value(ValueT const& v)
180    {
181        value_ = v;
182    }
183private:
184    IteratorT first, last;
185    bool is_root_;
186    parser_id parser_id_;
187    ValueT value_;
188
189public:
190};
191
192#if defined(BOOST_SPIRIT_DEBUG) && \
193    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
194// value is default nil_t, so provide an operator<< for nil_t
195inline std::ostream&
196operator<<(std::ostream& o, nil_t const&)
197{
198    return o;
199}
200
201template <typename IteratorT, typename ValueT>
202inline std::ostream&
203operator<<(std::ostream& o, node_iter_data<IteratorT, ValueT> const& n)
204{
205    o << "(id = " << n.id() << " text = \"";
206    typedef typename node_iter_data<IteratorT, ValueT>::const_iterator_t
207        iterator_t;
208    for (iterator_t it = n.begin(); it != n.end(); ++it)
209        impl::token_printer(o, *it);
210    o << "\" is_root = " << n.is_root()
211        << /*" value = " << n.value() << */")";
212    return o;
213}
214#endif
215
216//////////////////////////////////
217template <typename IteratorT = char const*, typename ValueT = nil_t>
218struct node_val_data
219{
220    typedef
221        typename boost::detail::iterator_traits<IteratorT>::value_type
222        value_type;
223    typedef std::vector<value_type> container_t;
224    typedef typename container_t::iterator iterator_t;
225    typedef typename container_t::const_iterator const_iterator_t;
226
227    node_val_data()
228        : text(), is_root_(false), parser_id_(), value_()
229        {}
230
231#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
232    node_val_data(IteratorT const& _first, IteratorT const& _last)
233        : text(), is_root_(false), parser_id_(), value_()
234        {
235            std::copy(_first, _last, std::inserter(text, text.end()));
236        }
237
238    // This constructor is for building text out of vector iterators
239    template <typename IteratorT2>
240    node_val_data(IteratorT2 const& _first, IteratorT2 const& _last)
241        : text(), is_root_(false), parser_id_(), value_()
242        {
243            std::copy(_first, _last, std::inserter(text, text.end()));
244        }
245#else
246    node_val_data(IteratorT const& _first, IteratorT const& _last)
247        : text(_first, _last), is_root_(false), parser_id_(), value_()
248        {}
249
250    // This constructor is for building text out of vector iterators
251    template <typename IteratorT2>
252    node_val_data(IteratorT2 const& _first, IteratorT2 const& _last)
253        : text(_first, _last), is_root_(false), parser_id_(), value_()
254        {}
255#endif
256
257    void swap(node_val_data& x)
258    {
259        impl::cp_swap(text, x.text);
260        impl::cp_swap(is_root_, x.is_root_);
261        impl::cp_swap(parser_id_, x.parser_id_);
262        impl::cp_swap(value_, x.value_);
263    }
264
265    typename container_t::iterator begin()
266    {
267        return text.begin();
268    }
269
270    typename container_t::const_iterator begin() const
271    {
272        return text.begin();
273    }
274
275    typename container_t::iterator end()
276    {
277        return text.end();
278    }
279
280    typename container_t::const_iterator end() const
281    {
282        return text.end();
283    }
284
285    bool is_root() const
286    {
287        return is_root_;
288    }
289
290    void is_root(bool b)
291    {
292        is_root_ = b;
293    }
294
295    parser_id id() const
296    {
297        return parser_id_;
298    }
299
300    void id(parser_id r)
301    {
302        parser_id_ = r;
303    }
304
305    ValueT const& value() const
306    {
307        return value_;
308    }
309
310    void value(ValueT const& v)
311    {
312        value_ = v;
313    }
314
315private:
316    container_t text;
317    bool is_root_;
318    parser_id parser_id_;
319    ValueT value_;
320};
321
322#if defined(BOOST_SPIRIT_DEBUG) && \
323    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
324template <typename IteratorT, typename ValueT>
325inline std::ostream&
326operator<<(std::ostream& o, node_val_data<IteratorT, ValueT> const& n)
327{
328    o << "(id = " << n.id() << " text = \"";
329    typedef typename node_val_data<IteratorT, ValueT>::const_iterator_t
330        iterator_t;
331    for (iterator_t it = n.begin(); it != n.end(); ++it)
332        impl::token_printer(o, *it);
333    o << "\" is_root = " << n.is_root()
334        << " value = " << n.value() << ")";
335    return o;
336}
337#endif
338
339template <typename T>
340inline void
341swap(tree_node<T>& a, tree_node<T>& b)
342{
343    a.swap(b);
344}
345
346template <typename T, typename V>
347inline void
348swap(node_iter_data<T, V>& a, node_iter_data<T, V>& b)
349{
350    a.swap(b);
351}
352
353//////////////////////////////////
354template <typename ValueT = nil_t>
355class node_iter_data_factory;
356
357//////////////////////////////////
358template <typename ValueT>
359class node_iter_data_factory
360{
361public:
362    // This inner class is so that node_iter_data_factory can simluate
363    // a template template parameter
364    template <typename IteratorT>
365    class factory
366    {
367    public:
368        typedef IteratorT iterator_t;
369        typedef node_iter_data<iterator_t, ValueT> node_t;
370
371        static node_t create_node(iterator_t const& first, iterator_t const& last,
372                bool /*is_leaf_node*/)
373        {
374            return node_t(first, last);
375        }
376
377        static node_t empty_node()
378        {
379            return node_t();
380        }
381
382        // precondition: ContainerT contains a tree_node<node_t>.  And all
383        // iterators in the container point to the same sequence.
384        template <typename ContainerT>
385        static node_t group_nodes(ContainerT const& nodes)
386        {
387            return node_t(nodes.begin()->value.begin(),
388                    nodes.back().value.end());
389        }
390    };
391};
392
393//////////////////////////////////
394template <typename ValueT = nil_t>
395class node_val_data_factory;
396
397//////////////////////////////////
398template <typename ValueT>
399class node_val_data_factory
400{
401public:
402    // This inner class is so that node_val_data_factory can simluate
403    // a template template parameter
404    template <typename IteratorT>
405    class factory
406    {
407    public:
408        typedef IteratorT iterator_t;
409        typedef node_val_data<iterator_t, ValueT> node_t;
410
411        static node_t create_node(iterator_t const& first, iterator_t const& last,
412                bool is_leaf_node)
413        {
414            if (is_leaf_node)
415                return node_t(first, last);
416            else
417                return node_t();
418        }
419
420        static node_t empty_node()
421        {
422            return node_t();
423        }
424
425        template <typename ContainerT>
426        static node_t group_nodes(ContainerT const& nodes)
427        {
428            typename node_t::container_t c;
429            typename ContainerT::const_iterator i_end = nodes.end();
430            // copy all the nodes text into a new one
431            for (typename ContainerT::const_iterator i = nodes.begin();
432                 i != i_end; ++i)
433            {
434                // See docs: token_node_d or leaf_node_d cannot be used with a
435                // rule inside the [].
436                assert(i->children.size() == 0);
437                c.insert(c.end(), i->value.begin(), i->value.end());
438            }
439            return node_t(c.begin(), c.end());
440        }
441    };
442};
443
444
445//////////////////////////////////
446template <typename ValueT = nil_t>
447class node_all_val_data_factory;
448
449//////////////////////////////////
450template <typename ValueT>
451class node_all_val_data_factory
452{
453public:
454    // This inner class is so that node_all_val_data_factory can simluate
455    // a template template parameter
456    template <typename IteratorT>
457    class factory
458    {
459    public:
460        typedef IteratorT iterator_t;
461        typedef node_val_data<iterator_t, ValueT> node_t;
462
463        static node_t create_node(iterator_t const& first, iterator_t const& last,
464                bool /*is_leaf_node*/)
465        {
466            return node_t(first, last);
467        }
468
469        static node_t empty_node()
470        {
471            return node_t();
472        }
473
474        template <typename ContainerT>
475        static node_t group_nodes(ContainerT const& nodes)
476        {
477            typename node_t::container_t c;
478            typename ContainerT::const_iterator i_end = nodes.end();
479            // copy all the nodes text into a new one
480            for (typename ContainerT::const_iterator i = nodes.begin();
481                    i != i_end; ++i)
482            {
483                // See docs: token_node_d or leaf_node_d cannot be used with a
484                // rule inside the [].
485                assert(i->children.size() == 0);
486                c.insert(c.end(), i->value.begin(), i->value.end());
487            }
488            return node_t(c.begin(), c.end());
489        }
490    };
491};
492
493//  forward declaration
494template <
495    typename IteratorT,
496    typename NodeFactoryT = node_val_data_factory<nil_t>,
497    typename T = nil_t
498>
499class tree_match;
500
501namespace impl {
502
503    ///////////////////////////////////////////////////////////////////////////
504    // can't call unqualified swap from within classname::swap
505    // as Koenig lookup rules will find only the classname::swap
506    // member function not the global declaration, so use cp_swap
507    // as a forwarding function (JM):
508#if __GNUC__ == 2
509    using ::std::swap;
510#endif
511    template <typename T>
512    inline void cp_swap(T& t1, T& t2)
513    {
514        using std::swap;
515        using boost::spirit::swap;
516        using boost::swap;
517        swap(t1, t2);
518    }
519}
520
521//////////////////////////////////
522template <typename IteratorT, typename NodeFactoryT, typename T>
523class tree_match : public match<T>
524{
525public:
526
527    typedef typename NodeFactoryT::template factory<IteratorT> node_factory_t;
528    typedef typename node_factory_t::node_t parse_node_t;
529    typedef tree_node<parse_node_t> node_t;
530    typedef typename node_t::children_t container_t;
531    typedef typename container_t::iterator tree_iterator;
532    typedef typename container_t::const_iterator const_tree_iterator;
533
534    typedef T attr_t;
535    typedef typename boost::call_traits<T>::param_type      param_type;
536    typedef typename boost::call_traits<T>::reference       reference;
537    typedef typename boost::call_traits<T>::const_reference const_reference;
538
539    tree_match()
540    : match<T>(), trees()
541    {}
542
543    explicit
544    tree_match(std::size_t length)
545    : match<T>(length), trees()
546    {}
547
548    tree_match(std::size_t length, parse_node_t const& n)
549    : match<T>(length), trees()
550    {
551        trees.reserve(10); // this is more or less an arbitraty number...
552        trees.push_back(node_t(n));
553    }
554
555    tree_match(std::size_t length, param_type val, parse_node_t const& n)
556    : match<T>(length, val), trees()
557    {
558        trees.reserve(10); // this is more or less an arbitraty number...
559        trees.push_back(node_t(n));
560    }
561
562    // attention, these constructors will change the second parameter!
563    tree_match(std::size_t length, container_t& c)
564    : match<T>(length), trees()
565    {
566        impl::cp_swap(trees, c);
567    }
568
569    tree_match(std::size_t length, param_type val, container_t& c)
570    : match<T>(length, val), trees()
571    {
572        impl::cp_swap(trees, c);
573    }
574
575    template <typename T2>
576    tree_match(match<T2> const& other)
577    : match<T>(other), trees()
578    {}
579
580    template <typename T2, typename T3, typename T4>
581    tree_match(tree_match<T2, T3, T4> const& other)
582    : match<T>(other), trees()
583    { impl::cp_swap(trees, other.trees); }
584
585    template <typename T2>
586    tree_match&
587    operator=(match<T2> const& other)
588    {
589        match<T>::operator=(other);
590        return *this;
591    }
592
593    template <typename T2, typename T3, typename T4>
594    tree_match&
595    operator=(tree_match<T2, T3, T4> const& other)
596    {
597        match<T>::operator=(other);
598        impl::cp_swap(trees, other.trees);
599        return *this;
600    }
601
602    tree_match(tree_match const& x)
603    : match<T>(x), trees()
604    {
605        // use auto_ptr like ownership for the trees data member
606        impl::cp_swap(trees, x.trees);
607    }
608
609    tree_match& operator=(tree_match const& x)
610    {
611        tree_match tmp(x);
612        this->swap(tmp);
613        return *this;
614    }
615
616    void swap(tree_match& x)
617    {
618        match<T>::swap(x);
619        impl::cp_swap(trees, x.trees);
620    }
621
622    mutable container_t trees;
623};
624
625#if defined(BOOST_SPIRIT_DEBUG) && \
626    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
627template <typename IteratorT, typename NodeFactoryT, typename T>
628inline std::ostream&
629operator<<(std::ostream& o, tree_match<IteratorT, NodeFactoryT, T> const& m)
630{
631    typedef
632        typename tree_match<IteratorT, NodeFactoryT, T>::container_t::iterator
633        iterator;
634
635    o << "(length = " << (int)m.length();
636    int c = 0;
637    for (iterator i = m.trees.begin(); i != m.trees.end(); ++i)
638    {
639        o << " trees[" << c++ << "] = " << *i;
640    }
641    o << "\n)";
642    return o;
643}
644#endif
645
646//////////////////////////////////
647struct tree_policy
648{
649    template <typename FunctorT, typename MatchT>
650    static void apply_op_to_match(FunctorT const& /*op*/, MatchT& /*m*/)
651    {}
652
653    template <typename MatchT, typename Iterator1T, typename Iterator2T>
654    static void group_match(MatchT& /*m*/, parser_id const& /*id*/,
655            Iterator1T const& /*first*/, Iterator2T const& /*last*/)
656    {}
657
658    template <typename MatchT>
659    static void concat(MatchT& /*a*/, MatchT const& /*b*/)
660    {}
661};
662
663//////////////////////////////////
664template <
665    typename MatchPolicyT,
666    typename IteratorT,
667    typename NodeFactoryT,
668    typename TreePolicyT
669>
670struct common_tree_match_policy : public match_policy
671{
672    template <typename T>
673    struct result { typedef tree_match<IteratorT, NodeFactoryT, T> type; };
674
675    typedef tree_match<IteratorT, NodeFactoryT> match_t;
676    typedef IteratorT iterator_t;
677    typedef TreePolicyT tree_policy_t;
678    typedef NodeFactoryT factory_t;
679
680    static const match_t no_match() { return match_t(); }
681    static const match_t empty_match()
682    { return match_t(0, tree_policy_t::empty_node()); }
683
684    template <typename AttrT, typename Iterator1T, typename Iterator2T>
685    static tree_match<IteratorT, NodeFactoryT, AttrT> create_match(
686        std::size_t length,
687        AttrT const& val,
688        Iterator1T const& first,
689        Iterator2T const& last)
690    {
691#if defined(BOOST_SPIRIT_DEBUG) && \
692    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
693
694        BOOST_SPIRIT_DEBUG_OUT << "\n>>> create_node(begin) <<<\n"
695            "creating node text: \"";
696        for (Iterator1T it = first; it != last; ++it)
697            impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
698        BOOST_SPIRIT_DEBUG_OUT << "\"\n";
699        BOOST_SPIRIT_DEBUG_OUT << ">>> create_node(end) <<<\n\n";
700#endif
701        return tree_match<IteratorT, NodeFactoryT, AttrT>(length, val,
702            tree_policy_t::create_node(length, first, last, true));
703    }
704
705    template <typename Match1T, typename Match2T>
706    static void concat_match(Match1T& a, Match2T const& b)
707    {
708#if defined(BOOST_SPIRIT_DEBUG) && \
709    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
710
711        BOOST_SPIRIT_DEBUG_OUT << "\n>>> concat_match(begin) <<<\n";
712        BOOST_SPIRIT_DEBUG_OUT << "tree a:\n" << a << "\n";
713        BOOST_SPIRIT_DEBUG_OUT << "tree b:\n" << b << "\n";
714        BOOST_SPIRIT_DEBUG_OUT << ">>> concat_match(end) <<<\n\n";
715#endif
716        BOOST_SPIRIT_ASSERT(a && b);
717        if (a.length() == 0)
718        {
719            a = b;
720            return;
721        }
722        else if (b.length() == 0
723#ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
724            && !b.trees.begin()->value.id().to_long()
725#endif
726            )
727        {
728            return;
729        }
730        a.concat(b);
731        tree_policy_t::concat(a, b);
732    }
733
734    template <typename MatchT, typename IteratorT2>
735    void
736    group_match(
737        MatchT&             m,
738        parser_id const&    id,
739        IteratorT2 const&   first,
740        IteratorT2 const&   last) const
741    {
742        if (!m) return;
743       
744#if defined(BOOST_SPIRIT_DEBUG) && \
745    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_TREES)
746
747        BOOST_SPIRIT_DEBUG_OUT << "\n>>> group_match(begin) <<<\n"
748            "new node(" << id << ") \"";
749        for (IteratorT2 it = first; it != last; ++it)
750            impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
751        BOOST_SPIRIT_DEBUG_OUT << "\"\n";
752        BOOST_SPIRIT_DEBUG_OUT << "new child tree (before grouping):\n" << m << "\n";
753
754        tree_policy_t::group_match(m, id, first, last);
755
756        BOOST_SPIRIT_DEBUG_OUT << "new child tree (after grouping):\n" << m << "\n";
757        BOOST_SPIRIT_DEBUG_OUT << ">>> group_match(end) <<<\n\n";
758#else
759        tree_policy_t::group_match(m, id, first, last);
760#endif
761    }
762};
763
764//////////////////////////////////
765template <typename MatchPolicyT, typename NodeFactoryT>
766struct common_tree_tree_policy
767{
768    typedef typename MatchPolicyT::iterator_t iterator_t;
769    typedef typename MatchPolicyT::match_t match_t;
770    typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
771    typedef typename factory_t::node_t node_t;
772
773    template <typename Iterator1T, typename Iterator2T>
774        static node_t
775        create_node(std::size_t /*length*/, Iterator1T const& first,
776            Iterator2T const& last, bool leaf_node)
777    {
778        return factory_t::create_node(first, last, leaf_node);
779    }
780
781    static node_t
782        empty_node()
783    {
784        return factory_t::empty_node();
785    }
786
787    template <typename FunctorT>
788        static void apply_op_to_match(FunctorT const& op, match_t& m)
789    {
790        op(m);
791    }
792};
793
794//////////////////////////////////
795// directives to modify how the parse tree is generated
796
797struct no_tree_gen_node_parser_gen;
798
799template <typename T>
800struct no_tree_gen_node_parser
801:   public unary<T, parser<no_tree_gen_node_parser<T> > >
802{
803    typedef no_tree_gen_node_parser<T> self_t;
804    typedef no_tree_gen_node_parser_gen parser_generator_t;
805    typedef unary_parser_category parser_category_t;
806//    typedef no_tree_gen_node_parser<T> const &embed_t;
807
808    no_tree_gen_node_parser(T const& a)
809    : unary<T, parser<no_tree_gen_node_parser<T> > >(a) {}
810
811    template <typename ScannerT>
812    typename parser_result<self_t, ScannerT>::type
813    parse(ScannerT const& scanner) const
814    {
815        typedef typename ScannerT::iteration_policy_t iteration_policy_t;
816        typedef match_policy match_policy_t;
817        typedef typename ScannerT::action_policy_t action_policy_t;
818        typedef scanner_policies<
819            iteration_policy_t,
820            match_policy_t,
821            action_policy_t
822        > policies_t;
823
824        return this->subject().parse(scanner.change_policies(policies_t(scanner)));
825    }
826};
827
828//////////////////////////////////
829struct no_tree_gen_node_parser_gen
830{
831    template <typename T>
832    struct result {
833
834        typedef no_tree_gen_node_parser<T> type;
835    };
836
837    template <typename T>
838    static no_tree_gen_node_parser<T>
839    generate(parser<T> const& s)
840    {
841        return no_tree_gen_node_parser<T>(s.derived());
842    }
843
844    template <typename T>
845    no_tree_gen_node_parser<T>
846    operator[](parser<T> const& s) const
847    {
848        return no_tree_gen_node_parser<T>(s.derived());
849    }
850};
851
852//////////////////////////////////
853const no_tree_gen_node_parser_gen no_node_d = no_tree_gen_node_parser_gen();
854
855
856//////////////////////////////////
857namespace impl {
858
859    template <typename MatchPolicyT>
860    struct tree_policy_selector
861    {
862        typedef tree_policy type;
863    };
864
865} // namespace impl
866
867//////////////////////////////////
868template <typename NodeParserT>
869struct node_parser_gen;
870
871template <typename T, typename NodeParserT>
872struct node_parser
873:   public unary<T, parser<node_parser<T, NodeParserT> > >
874{
875    typedef node_parser<T, NodeParserT> self_t;
876    typedef node_parser_gen<NodeParserT> parser_generator_t;
877    typedef unary_parser_category parser_category_t;
878//    typedef node_parser<T, NodeParserT> const &embed_t;
879
880    node_parser(T const& a)
881    : unary<T, parser<node_parser<T, NodeParserT> > >(a) {}
882
883    template <typename ScannerT>
884    typename parser_result<self_t, ScannerT>::type
885    parse(ScannerT const& scanner) const
886    {
887        typename parser_result<self_t, ScannerT>::type hit = this->subject().parse(scanner);
888        if (hit)
889        {
890            impl::tree_policy_selector<typename ScannerT::match_policy_t>::type::apply_op_to_match(NodeParserT(), hit);
891        }
892        return hit;
893    }
894};
895
896//////////////////////////////////
897template <typename NodeParserT>
898struct node_parser_gen
899{
900    template <typename T>
901    struct result {
902
903        typedef node_parser<T, NodeParserT> type;
904    };
905
906    template <typename T>
907    static node_parser<T, NodeParserT>
908    generate(parser<T> const& s)
909    {
910        return node_parser<T, NodeParserT>(s.derived());
911    }
912
913    template <typename T>
914    node_parser<T, NodeParserT>
915    operator[](parser<T> const& s) const
916    {
917        return node_parser<T, NodeParserT>(s.derived());
918    }
919};
920
921struct discard_node_op
922{
923    template <typename MatchT>
924    void operator()(MatchT& m) const
925    {
926        m.trees.clear();
927    }
928};
929
930const node_parser_gen<discard_node_op> discard_node_d =
931    node_parser_gen<discard_node_op>();
932
933struct leaf_node_op
934{
935    template <typename MatchT>
936    void operator()(MatchT& m) const
937    {
938        if (m.trees.size() == 1)
939        {
940            m.trees.begin()->children.clear();
941        }
942        else if (m.trees.size() > 1)
943        {
944            typedef typename MatchT::node_factory_t node_factory_t;
945            m = MatchT(m.length(), node_factory_t::group_nodes(m.trees));
946        }
947    }
948};
949
950const node_parser_gen<leaf_node_op> leaf_node_d =
951    node_parser_gen<leaf_node_op>();
952const node_parser_gen<leaf_node_op> token_node_d =
953    node_parser_gen<leaf_node_op>();
954
955struct infix_node_op
956{
957    template <typename MatchT>
958    void operator()(MatchT& m) const
959    {
960        typedef typename MatchT::container_t container_t;
961        typedef typename MatchT::container_t::iterator iter_t;
962        typedef typename MatchT::container_t::value_type value_t;
963
964        using std::swap;
965        using boost::swap;
966        using boost::spirit::swap;
967
968        // copying the tree nodes is expensive, since it may copy a whole
969        // tree.  swapping them is cheap, so swap the nodes we want into
970        // a new container of children.
971        container_t new_children;
972        std::size_t length = 0;
973        std::size_t tree_size = m.trees.size();
974
975        // the infix_node_d[] make no sense for nodes with no subnodes
976        BOOST_SPIRIT_ASSERT(tree_size >= 1);
977
978        bool keep = true;
979        new_children.reserve((tree_size+1)/2);
980        iter_t i_end = m.trees.end();
981        for (iter_t i = m.trees.begin(); i != i_end; ++i)
982        {
983            if (keep) {
984                // adjust the length
985                length += std::distance((*i).value.begin(), (*i).value.end());
986
987                // move the child node
988                new_children.push_back(value_t());
989                swap(new_children.back(), *i);
990                keep = false;
991            }
992            else {
993                // ignore this child node
994                keep = true;
995            }
996        }
997
998        m = MatchT(length, new_children);
999    }
1000};
1001
1002const node_parser_gen<infix_node_op> infix_node_d =
1003    node_parser_gen<infix_node_op>();
1004
1005struct discard_first_node_op
1006{
1007    template <typename MatchT>
1008    void operator()(MatchT& m) const
1009    {
1010        typedef typename MatchT::container_t container_t;
1011        typedef typename MatchT::container_t::iterator iter_t;
1012        typedef typename MatchT::container_t::value_type value_t;
1013
1014        using std::swap;
1015        using boost::swap;
1016        using boost::spirit::swap;
1017
1018        // copying the tree nodes is expensive, since it may copy a whole
1019        // tree.  swapping them is cheap, so swap the nodes we want into
1020        // a new container of children, instead of saying
1021        // m.trees.erase(m.trees.begin()) because, on a vector that will cause
1022        // all the nodes afterwards to be copied into the previous position.
1023        container_t new_children;
1024        std::size_t length = 0;
1025        std::size_t tree_size = m.trees.size();
1026
1027        // the discard_first_node_d[] make no sense for nodes with no subnodes
1028        BOOST_SPIRIT_ASSERT(tree_size >= 1);
1029
1030        if (tree_size > 1) {
1031            new_children.reserve(tree_size - 1);
1032            iter_t i = m.trees.begin(), i_end = m.trees.end();
1033            for (++i; i != i_end; ++i)
1034            {
1035                // adjust the length
1036                length += std::distance((*i).value.begin(), (*i).value.end());
1037
1038                // move the child node
1039                new_children.push_back(value_t());
1040                swap(new_children.back(), *i);
1041            }
1042        }
1043        else {
1044        // if there was a tree and now there isn't any, insert an empty node
1045            iter_t i = m.trees.begin();
1046
1047        // This isn't entirely correct, since the empty node will reference
1048        // the end of the discarded node, but I currently don't see any way to
1049        // get at the begin of the node following this subnode.
1050        // This should be safe anyway because the it shouldn't get dereferenced
1051        // under any circumstances.
1052            typedef typename value_t::parse_node_t::iterator_t iterator_type;
1053            iterator_type it = (*i).value.end();
1054           
1055            new_children.push_back(
1056                value_t(typename value_t::parse_node_t(it, it)));
1057        }
1058       
1059        m = MatchT(length, new_children);
1060    }
1061};
1062
1063const node_parser_gen<discard_first_node_op> discard_first_node_d =
1064    node_parser_gen<discard_first_node_op>();
1065
1066struct discard_last_node_op
1067{
1068    template <typename MatchT>
1069    void operator()(MatchT& m) const
1070    {
1071        typedef typename MatchT::container_t container_t;
1072        typedef typename MatchT::container_t::iterator iter_t;
1073        typedef typename MatchT::container_t::value_type value_t;
1074
1075        using std::swap;
1076        using boost::swap;
1077        using boost::spirit::swap;
1078
1079        // copying the tree nodes is expensive, since it may copy a whole
1080        // tree.  swapping them is cheap, so swap the nodes we want into
1081        // a new container of children, instead of saying
1082        // m.trees.erase(m.trees.begin()) because, on a vector that will cause
1083        // all the nodes afterwards to be copied into the previous position.
1084        container_t new_children;
1085        std::size_t length = 0;
1086        std::size_t tree_size = m.trees.size();
1087
1088        // the discard_last_node_d[] make no sense for nodes with no subnodes
1089        BOOST_SPIRIT_ASSERT(tree_size >= 1);
1090
1091        if (tree_size > 1) {
1092            m.trees.pop_back();
1093            new_children.reserve(tree_size - 1);
1094           
1095            iter_t i_end = m.trees.end();
1096            for (iter_t i = m.trees.begin(); i != i_end; ++i)
1097            {
1098                // adjust the length
1099                length += std::distance((*i).value.begin(), (*i).value.end());
1100
1101                // move the child node
1102                new_children.push_back(value_t());
1103                swap(new_children.back(), *i);
1104            }
1105        }
1106        else {
1107        // if there was a tree and now there isn't any, insert an empty node
1108            iter_t i = m.trees.begin();
1109
1110            typedef typename value_t::parse_node_t::iterator_t iterator_type;
1111            iterator_type it = (*i).value.begin();
1112           
1113            new_children.push_back(
1114                value_t(typename value_t::parse_node_t(it, it)));
1115        }
1116       
1117        m = MatchT(length, new_children);
1118    }
1119};
1120
1121const node_parser_gen<discard_last_node_op> discard_last_node_d =
1122    node_parser_gen<discard_last_node_op>();
1123
1124struct inner_node_op
1125{
1126    template <typename MatchT>
1127    void operator()(MatchT& m) const
1128    {
1129        typedef typename MatchT::container_t container_t;
1130        typedef typename MatchT::container_t::iterator iter_t;
1131        typedef typename MatchT::container_t::value_type value_t;
1132
1133        using std::swap;
1134        using boost::swap;
1135        using boost::spirit::swap;
1136
1137        // copying the tree nodes is expensive, since it may copy a whole
1138        // tree.  swapping them is cheap, so swap the nodes we want into
1139        // a new container of children, instead of saying
1140        // m.trees.erase(m.trees.begin()) because, on a vector that will cause
1141        // all the nodes afterwards to be copied into the previous position.
1142        container_t new_children;
1143        std::size_t length = 0;
1144        std::size_t tree_size = m.trees.size();
1145       
1146        // the inner_node_d[] make no sense for nodes with less then 2 subnodes
1147        BOOST_SPIRIT_ASSERT(tree_size >= 2);
1148
1149        if (tree_size > 2) {
1150            m.trees.pop_back(); // erase the last element
1151            new_children.reserve(tree_size - 1);
1152            iter_t i = m.trees.begin(); // skip over the first element
1153            iter_t i_end = m.trees.end();
1154            for (++i; i != i_end; ++i)
1155            {
1156                // adjust the length
1157                length += std::distance((*i).value.begin(), (*i).value.end());
1158               
1159                // move the child node
1160                new_children.push_back(value_t());
1161                swap(new_children.back(), *i);
1162            }
1163        }
1164        else {
1165        // if there was a tree and now there isn't any, insert an empty node
1166            iter_t i = m.trees.begin(); // skip over the first element
1167
1168            typedef typename value_t::parse_node_t::iterator_t iterator_type;
1169            iterator_type it = (*++i).value.begin();
1170           
1171            new_children.push_back(
1172                value_t(typename value_t::parse_node_t(it, it)));
1173        }
1174       
1175        m = MatchT(length, new_children);
1176    }
1177};
1178
1179const node_parser_gen<inner_node_op> inner_node_d =
1180    node_parser_gen<inner_node_op>();
1181
1182
1183//////////////////////////////////
1184// action_directive_parser and action_directive_parser_gen
1185// are meant to be used as a template to create directives that
1186// generate action classes.  For example access_match and
1187// access_node.  The ActionParserT template parameter must be
1188// a class that has an innter class called action that is templated
1189// on the parser type and the action type.
1190template <typename ActionParserT>
1191struct action_directive_parser_gen;
1192
1193template <typename T, typename ActionParserT>
1194struct action_directive_parser
1195:   public unary<T, parser<action_directive_parser<T, ActionParserT> > >
1196{
1197    typedef action_directive_parser<T, ActionParserT> self_t;
1198    typedef action_directive_parser_gen<ActionParserT> parser_generator_t;
1199    typedef unary_parser_category parser_category_t;
1200//    typedef action_directive_parser<T, ActionParserT> const &embed_t;
1201
1202    action_directive_parser(T const& a)
1203        : unary<T, parser<action_directive_parser<T, ActionParserT> > >(a) {}
1204
1205    template <typename ScannerT>
1206    typename parser_result<self_t, ScannerT>::type
1207    parse(ScannerT const& scanner) const
1208    {
1209        return this->subject().parse(scanner);
1210    }
1211
1212    template <typename ActionT>
1213    typename ActionParserT::template action<action_directive_parser<T, ActionParserT>, ActionT>
1214    operator[](ActionT const& actor) const
1215    {
1216        typedef typename
1217            ActionParserT::template action<action_directive_parser, ActionT>
1218            action_t;
1219        return action_t(*this, actor);
1220    }
1221};
1222
1223//////////////////////////////////
1224template <typename ActionParserT>
1225struct action_directive_parser_gen
1226{
1227    template <typename T>
1228    struct result {
1229
1230        typedef action_directive_parser<T, ActionParserT> type;
1231    };
1232
1233    template <typename T>
1234    static action_directive_parser<T, ActionParserT>
1235    generate(parser<T> const& s)
1236    {
1237        return action_directive_parser<T, ActionParserT>(s.derived());
1238    }
1239
1240    template <typename T>
1241    action_directive_parser<T, ActionParserT>
1242    operator[](parser<T> const& s) const
1243    {
1244        return action_directive_parser<T, ActionParserT>(s.derived());
1245    }
1246};
1247
1248//////////////////////////////////
1249// Calls the attached action passing it the match from the parser
1250// and the first and last iterators
1251struct access_match_action
1252{
1253    // inner template class to simulate template-template parameters
1254    template <typename ParserT, typename ActionT>
1255    struct action
1256    :   public unary<ParserT, parser<access_match_action::action<ParserT, ActionT> > >
1257    {
1258        typedef action_parser_category parser_category;
1259        typedef action<ParserT, ActionT> self_t;
1260
1261        action( ParserT const& subject,
1262                ActionT const& actor_);
1263
1264        template <typename ScannerT>
1265        typename parser_result<self_t, ScannerT>::type
1266        parse(ScannerT const& scanner) const;
1267
1268        ActionT const &predicate() const;
1269
1270        private:
1271        ActionT actor;
1272    };
1273};
1274
1275//////////////////////////////////
1276template <typename ParserT, typename ActionT>
1277access_match_action::action<ParserT, ActionT>::action(
1278    ParserT const& subject,
1279    ActionT const& actor_)
1280: unary<ParserT, parser<access_match_action::action<ParserT, ActionT> > >(subject)
1281, actor(actor_)
1282{}
1283
1284//////////////////////////////////
1285template <typename ParserT, typename ActionT>
1286template <typename ScannerT>
1287typename parser_result<access_match_action::action<ParserT, ActionT>, ScannerT>::type
1288access_match_action::action<ParserT, ActionT>::
1289parse(ScannerT const& scan) const
1290{
1291    typedef typename ScannerT::iterator_t iterator_t;
1292    typedef typename parser_result<self_t, ScannerT>::type result_t;
1293    if (!scan.at_end())
1294    {
1295        iterator_t save = scan.first;
1296        result_t hit = this->subject().parse(scan);
1297        actor(hit, save, scan.first);
1298        return hit;
1299    }
1300    return scan.no_match();
1301}
1302
1303//////////////////////////////////
1304template <typename ParserT, typename ActionT>
1305ActionT const &access_match_action::action<ParserT, ActionT>::predicate() const
1306{
1307    return actor;
1308}
1309
1310//////////////////////////////////
1311const action_directive_parser_gen<access_match_action> access_match_d
1312    = action_directive_parser_gen<access_match_action>();
1313
1314
1315
1316//////////////////////////////////
1317// Calls the attached action passing it the node from the parser
1318// and the first and last iterators
1319struct access_node_action
1320{
1321    // inner template class to simulate template-template parameters
1322    template <typename ParserT, typename ActionT>
1323    struct action
1324    :   public unary<ParserT, parser<access_node_action::action<ParserT, ActionT> > >
1325    {
1326        typedef action_parser_category parser_category;
1327        typedef action<ParserT, ActionT> self_t;
1328
1329        action( ParserT const& subject,
1330                ActionT const& actor_);
1331
1332        template <typename ScannerT>
1333        typename parser_result<self_t, ScannerT>::type
1334        parse(ScannerT const& scanner) const;
1335
1336        ActionT const &predicate() const;
1337
1338        private:
1339        ActionT actor;
1340    };
1341};
1342
1343//////////////////////////////////
1344template <typename ParserT, typename ActionT>
1345access_node_action::action<ParserT, ActionT>::action(
1346    ParserT const& subject,
1347    ActionT const& actor_)
1348: unary<ParserT, parser<access_node_action::action<ParserT, ActionT> > >(subject)
1349, actor(actor_)
1350{}
1351
1352//////////////////////////////////
1353template <typename ParserT, typename ActionT>
1354template <typename ScannerT>
1355typename parser_result<access_node_action::action<ParserT, ActionT>, ScannerT>::type
1356access_node_action::action<ParserT, ActionT>::
1357parse(ScannerT const& scan) const
1358{
1359    typedef typename ScannerT::iterator_t iterator_t;
1360    typedef typename parser_result<self_t, ScannerT>::type result_t;
1361    if (!scan.at_end())
1362    {
1363        iterator_t save = scan.first;
1364        result_t hit = this->subject().parse(scan);
1365        if (hit && hit.trees.size() > 0)
1366            actor(*hit.trees.begin(), save, scan.first);
1367        return hit;
1368    }
1369    return scan.no_match();
1370}
1371
1372//////////////////////////////////
1373template <typename ParserT, typename ActionT>
1374ActionT const &access_node_action::action<ParserT, ActionT>::predicate() const
1375{
1376    return actor;
1377}
1378
1379//////////////////////////////////
1380const action_directive_parser_gen<access_node_action> access_node_d
1381    = action_directive_parser_gen<access_node_action>();
1382
1383
1384
1385//////////////////////////////////
1386
1387///////////////////////////////////////////////////////////////////////////////
1388//
1389//  tree_parse_info
1390//
1391//      Results returned by the tree parse functions:
1392//
1393//      stop:   points to the final parse position (i.e parsing
1394//              processed the input up to this point).
1395//
1396//      match:  true if parsing is successful. This may be full:
1397//              the parser consumed all the input, or partial:
1398//              the parser consumed only a portion of the input.
1399//
1400//      full:   true when we have a full match (i.e the parser
1401//              consumed all the input.
1402//
1403//      length: The number of characters consumed by the parser.
1404//              This is valid only if we have a successful match
1405//              (either partial or full). A negative value means
1406//              that the match is unsucessful.
1407//
1408//     trees:   Contains the root node(s) of the tree.
1409//
1410///////////////////////////////////////////////////////////////////////////////
1411template <
1412    typename IteratorT = char const *,
1413    typename NodeFactoryT = node_val_data_factory<nil_t>,
1414    typename T = nil_t
1415>
1416struct tree_parse_info {
1417
1418    IteratorT   stop;
1419    bool        match;
1420    bool        full;
1421    std::size_t length;
1422    typename tree_match<IteratorT, NodeFactoryT, T>::container_t trees;
1423
1424    tree_parse_info()
1425        : stop()
1426        , match(false)
1427        , full(false)
1428        , length(0)
1429        , trees()
1430    {}
1431
1432    template <typename IteratorT2>
1433    tree_parse_info(tree_parse_info<IteratorT2> const& pi)
1434        : stop(pi.stop)
1435        , match(pi.match)
1436        , full(pi.full)
1437        , length(pi.length)
1438        , trees()
1439    {
1440        using std::swap;
1441        using boost::swap;
1442        using boost::spirit::swap;
1443
1444        // use auto_ptr like ownership for the trees data member
1445        swap(trees, pi.trees);
1446    }
1447
1448    tree_parse_info(
1449        IteratorT   stop_,
1450        bool        match_,
1451        bool        full_,
1452        std::size_t length_,
1453        typename tree_match<IteratorT, NodeFactoryT, T>::container_t trees_)
1454    :   stop(stop_)
1455        , match(match_)
1456        , full(full_)
1457        , length(length_)
1458        , trees()
1459    {
1460        using std::swap;
1461        using boost::swap;
1462        using boost::spirit::swap;
1463
1464        // use auto_ptr like ownership for the trees data member
1465        swap(trees, trees_);
1466    }
1467};
1468
1469}} // namespace boost::spirit
1470
1471#endif
1472
Note: See TracBrowser for help on using the repository browser.