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

Revision 857, 11.3 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_AST_HPP
10#define BOOST_SPIRIT_TREE_AST_HPP
11
12#include <boost/spirit/tree/common.hpp>
13#include <boost/spirit/core/scanner/scanner.hpp>
14
15///////////////////////////////////////////////////////////////////////////////
16namespace boost { namespace spirit {
17
18template <typename MatchPolicyT, typename NodeFactoryT>
19struct ast_tree_policy;
20
21//////////////////////////////////
22//  ast_match_policy is simply an id so the correct specialization of
23//  tree_policy can be found.
24template <
25    typename IteratorT,
26    typename NodeFactoryT = node_val_data_factory<nil_t>
27>
28struct ast_match_policy :
29    public common_tree_match_policy<
30        ast_match_policy<IteratorT, NodeFactoryT>,
31        IteratorT,
32        NodeFactoryT,
33        ast_tree_policy<
34            ast_match_policy<IteratorT, NodeFactoryT>,
35            NodeFactoryT
36        >
37    >
38{
39};
40
41//////////////////////////////////
42template <typename MatchPolicyT, typename NodeFactoryT>
43struct ast_tree_policy :
44    public common_tree_tree_policy<MatchPolicyT, NodeFactoryT>
45{
46    typedef
47        typename common_tree_tree_policy<MatchPolicyT, NodeFactoryT>::match_t
48        match_t;
49    typedef typename MatchPolicyT::iterator_t iterator_t;
50
51    static void concat(match_t& a, match_t const& b)
52    {
53        BOOST_SPIRIT_ASSERT(a && b);
54
55#if defined(BOOST_SPIRIT_DEBUG) && \
56    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
57        BOOST_SPIRIT_DEBUG_OUT << "\n>>>AST concat. a = " << a <<
58            "\n\tb = " << b << "<<<\n";
59#endif
60        typedef typename tree_match<iterator_t, NodeFactoryT>::container_t
61            container_t;
62
63        // test for size() is nessecary, because no_tree_gen_node leaves a.trees
64        // and/or b.trees empty
65        if (0 != b.trees.size() && b.trees.begin()->value.is_root())
66        {
67            BOOST_SPIRIT_ASSERT(b.trees.size() == 1);
68
69            container_t tmp;
70            std::swap(a.trees, tmp); // save a into tmp
71            std::swap(b.trees, a.trees); // make b.trees[0] be new root (a.trees[0])
72            container_t* pnon_root_trees = &a.trees;
73            while (pnon_root_trees->size() > 0 &&
74                    pnon_root_trees->begin()->value.is_root())
75            {
76                pnon_root_trees = & pnon_root_trees->begin()->children;
77            }
78            pnon_root_trees->insert(pnon_root_trees->begin(),
79                    tmp.begin(), tmp.end());
80        }
81        else if (0 != a.trees.size() && a.trees.begin()->value.is_root())
82        {
83            BOOST_SPIRIT_ASSERT(a.trees.size() == 1);
84
85            a.trees.begin()->children.reserve(a.trees.begin()->children.size() + b.trees.size());
86            std::copy(b.trees.begin(),
87                 b.trees.end(),
88                 std::back_insert_iterator<container_t>(
89                     a.trees.begin()->children));
90        }
91        else
92        {
93            a.trees.reserve(a.trees.size() + b.trees.size());
94            std::copy(b.trees.begin(),
95                 b.trees.end(),
96                 std::back_insert_iterator<container_t>(a.trees));
97        }
98
99#if defined(BOOST_SPIRIT_DEBUG) && \
100    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
101        BOOST_SPIRIT_DEBUG_OUT << ">>>after AST concat. a = " << a << "<<<\n\n";
102#endif
103
104        return;
105    }
106
107    template <typename MatchT, typename Iterator1T, typename Iterator2T>
108    static void group_match(MatchT& m, parser_id const& id,
109            Iterator1T const& first, Iterator2T const& last)
110    {
111        if (!m)
112            return;
113
114        typedef typename tree_match<iterator_t, NodeFactoryT>::container_t
115            container_t;
116        typedef typename container_t::iterator cont_iterator_t;
117        typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
118
119        if (m.trees.size() == 1
120#ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
121            && !(id.to_long() && m.trees.begin()->value.id().to_long())
122#endif
123            )
124        {
125            // set rule_id's.  There may have been multiple nodes created.
126            // Because of root_node[] they may be left-most children of the top
127            // node.
128            container_t* punset_id = &m.trees;
129            while (punset_id->size() > 0 &&
130                    punset_id->begin()->value.id() == 0)
131            {
132                punset_id->begin()->value.id(id);
133                punset_id = &punset_id->begin()->children;
134            }
135
136            m.trees.begin()->value.is_root(false);
137        }
138        else
139        {
140            match_t newmatch(m.length(),
141                m.trees.empty() ?
142                    factory_t::empty_node() :
143                    factory_t::create_node(first, last, false));
144
145            std::swap(newmatch.trees.begin()->children, m.trees);
146            // set this node and all it's unset children's rule_id
147            newmatch.trees.begin()->value.id(id);
148            for (cont_iterator_t i = newmatch.trees.begin();
149                 i != newmatch.trees.end();
150                 ++i)
151            {
152                if (i->value.id() == 0)
153                    i->value.id(id);
154            }
155            m = newmatch;
156        }
157    }
158
159    template <typename FunctorT>
160    static void apply_op_to_match(FunctorT const& op, match_t& m)
161    {
162        op(m);
163    }
164};
165
166namespace impl {
167
168    template <typename IteratorT, typename NodeFactoryT>
169    struct tree_policy_selector<ast_match_policy<IteratorT, NodeFactoryT> >
170    {
171        typedef ast_tree_policy<
172            ast_match_policy<IteratorT, NodeFactoryT>, NodeFactoryT> type;
173    };
174
175} // namespace impl
176
177
178//////////////////////////////////
179struct gen_ast_node_parser_gen;
180
181template <typename T>
182struct gen_ast_node_parser
183:   public unary<T, parser<gen_ast_node_parser<T> > >
184{
185    typedef gen_ast_node_parser<T> self_t;
186    typedef gen_ast_node_parser_gen parser_generator_t;
187    typedef unary_parser_category parser_category_t;
188//    typedef gen_ast_node_parser<T> const &embed_t;
189
190    gen_ast_node_parser(T const& a)
191    : unary<T, parser<gen_ast_node_parser<T> > >(a) {}
192
193    template <typename ScannerT>
194    typename parser_result<self_t, ScannerT>::type
195    parse(ScannerT const& scan) const
196    {
197        typedef typename ScannerT::iteration_policy_t iteration_policy_t;
198        typedef typename ScannerT::match_policy_t::iterator_t iterator_t;
199        typedef typename ScannerT::match_policy_t::factory_t factory_t;
200        typedef ast_match_policy<iterator_t, factory_t> match_policy_t;
201        typedef typename ScannerT::action_policy_t action_policy_t;
202        typedef scanner_policies<
203            iteration_policy_t,
204            match_policy_t,
205            action_policy_t
206        > policies_t;
207
208        return this->subject().parse(scan.change_policies(policies_t(scan)));
209    }
210};
211
212//////////////////////////////////
213struct gen_ast_node_parser_gen
214{
215    template <typename T>
216    struct result {
217
218        typedef gen_ast_node_parser<T> type;
219    };
220
221    template <typename T>
222    static gen_ast_node_parser<T>
223    generate(parser<T> const& s)
224    {
225        return gen_ast_node_parser<T>(s.derived());
226    }
227
228    template <typename T>
229    gen_ast_node_parser<T>
230    operator[](parser<T> const& s) const
231    {
232        return gen_ast_node_parser<T>(s.derived());
233    }
234};
235
236//////////////////////////////////
237const gen_ast_node_parser_gen gen_ast_node_d = gen_ast_node_parser_gen();
238
239
240//////////////////////////////////
241struct root_node_op
242{
243    template <typename MatchT>
244    void operator()(MatchT& m) const
245    {
246        BOOST_SPIRIT_ASSERT(m.trees.size() > 0);
247        m.trees.begin()->value.is_root(true);
248    }
249};
250
251const node_parser_gen<root_node_op> root_node_d =
252    node_parser_gen<root_node_op>();
253
254///////////////////////////////////////////////////////////////////////////////
255//
256//  Parse functions for ASTs
257//
258///////////////////////////////////////////////////////////////////////////////
259template <
260    typename AstFactoryT, typename IteratorT, typename ParserT,
261    typename SkipT
262>
263inline tree_parse_info<IteratorT, AstFactoryT>
264ast_parse(
265    IteratorT const&        first_,
266    IteratorT const&        last_,
267    parser<ParserT> const&  parser,
268    SkipT const&            skip_,
269    AstFactoryT const &   /*dummy_*/ = AstFactoryT())
270{
271    typedef skip_parser_iteration_policy<SkipT> iter_policy_t;
272    typedef ast_match_policy<IteratorT, AstFactoryT> ast_match_policy_t;
273    typedef
274        scanner_policies<iter_policy_t, ast_match_policy_t>
275        scanner_policies_t;
276    typedef scanner<IteratorT, scanner_policies_t> scanner_t;
277
278    iter_policy_t iter_policy(skip_);
279    scanner_policies_t policies(iter_policy);
280    IteratorT first = first_;
281    scanner_t scan(first, last_, policies);
282    tree_match<IteratorT, AstFactoryT> hit = parser.derived().parse(scan);
283    scan.skip(scan);
284    return tree_parse_info<IteratorT, AstFactoryT>(
285        first, hit, hit && (first == last_), hit.length(), hit.trees);
286}
287
288//////////////////////////////////
289template <typename IteratorT, typename ParserT, typename SkipT>
290inline tree_parse_info<IteratorT>
291ast_parse(
292    IteratorT const&        first_,
293    IteratorT const&        last_,
294    parser<ParserT> const&  parser,
295    SkipT const&            skip_)
296{
297    typedef node_val_data_factory<nil_t> default_factory_t;
298    return ast_parse(first_, last_, parser, skip_, default_factory_t());
299}
300 
301//////////////////////////////////
302template <typename IteratorT, typename ParserT>
303inline tree_parse_info<IteratorT>
304ast_parse(
305    IteratorT const&        first_,
306    IteratorT const&        last,
307    parser<ParserT> const&  parser)
308{
309    typedef ast_match_policy<IteratorT> ast_match_policy_t;
310    IteratorT first = first_;
311    scanner<
312        IteratorT,
313        scanner_policies<iteration_policy, ast_match_policy_t>
314    > scan(first, last);
315    tree_match<IteratorT> hit = parser.derived().parse(scan);
316    return tree_parse_info<IteratorT>(
317        first, hit, hit && (first == last), hit.length(), hit.trees);
318}
319
320//////////////////////////////////
321template <typename CharT, typename ParserT, typename SkipT>
322inline tree_parse_info<CharT const*>
323ast_parse(
324    CharT const*            str,
325    parser<ParserT> const&  parser,
326    SkipT const&            skip)
327{
328    CharT const* last = str;
329    while (*last)
330        last++;
331    return ast_parse(str, last, parser, skip);
332}
333
334//////////////////////////////////
335template <typename CharT, typename ParserT>
336inline tree_parse_info<CharT const*>
337ast_parse(
338    CharT const*            str,
339    parser<ParserT> const&  parser)
340{
341    CharT const* last = str;
342    while (*last)
343    {
344        last++;
345    }
346    return ast_parse(str, last, parser);
347}
348
349///////////////////////////////////////////////////////////////////////////////
350}} // namespace boost::spirit
351
352#endif
353
Note: See TracBrowser for help on using the repository browser.