/*=============================================================================

    Copyright (c) 2001-2003 Daniel Nuffer

    http://spirit.sourceforge.net/

    Use, modification and distribution is subject to the Boost Software

    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

    http://www.boost.org/LICENSE_1_0.txt)

=============================================================================*/

#ifndef BOOST_SPIRIT_TREE_AST_HPP

#define BOOST_SPIRIT_TREE_AST_HPP

#include <boost/spirit/tree/common.hpp>

#include <boost/spirit/core/scanner/scanner.hpp>

#include <boost/spirit/tree/ast_fwd.hpp>

///////////////////////////////////////////////////////////////////////////////

namespace boost { namespace spirit {

//////////////////////////////////

//  ast_match_policy is simply an id so the correct specialization of

//  tree_policy can be found.

template <

    typename IteratorT,

    typename NodeFactoryT

>

struct ast_match_policy :

    public common_tree_match_policy<

        ast_match_policy<IteratorT, NodeFactoryT>,

        IteratorT,

        NodeFactoryT,

        ast_tree_policy<

            ast_match_policy<IteratorT, NodeFactoryT>,

            NodeFactoryT

        >

    >

{

    typedef

        common_tree_match_policy<

            ast_match_policy<IteratorT, NodeFactoryT>,

            IteratorT,

            NodeFactoryT,

            ast_tree_policy<

                ast_match_policy<IteratorT, NodeFactoryT>,

                NodeFactoryT

            >

        >

    common_tree_match_policy_;

    ast_match_policy()

    {

    }

    template <typename PolicyT>

    ast_match_policy(PolicyT const & policies)

        : common_tree_match_policy_(policies)

    {

    }

};

//////////////////////////////////

template <typename MatchPolicyT, typename NodeFactoryT>

struct ast_tree_policy :

    public common_tree_tree_policy<MatchPolicyT, NodeFactoryT>

{

    typedef

        typename common_tree_tree_policy<MatchPolicyT, NodeFactoryT>::match_t

        match_t;

    typedef typename MatchPolicyT::iterator_t iterator_t;

    static void concat(match_t& a, match_t const& b)

    {

        BOOST_SPIRIT_ASSERT(a && b);

#if defined(BOOST_SPIRIT_DEBUG) && \

    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)

        BOOST_SPIRIT_DEBUG_OUT << "\n>>>AST concat. a = " << a <<

            "\n\tb = " << b << "<<<\n";

#endif

        typedef typename tree_match<iterator_t, NodeFactoryT>::container_t

            container_t;

        // test for size() is nessecary, because no_tree_gen_node leaves a.trees

        // and/or b.trees empty

        if (0 != b.trees.size() && b.trees.begin()->value.is_root())

        {

            BOOST_SPIRIT_ASSERT(b.trees.size() == 1);

            container_t tmp;

            std::swap(a.trees, tmp); // save a into tmp

            std::swap(b.trees, a.trees); // make b.trees[0] be new root (a.trees[0])

            container_t* pnon_root_trees = &a.trees;

            while (pnon_root_trees->size() > 0 &&

                    pnon_root_trees->begin()->value.is_root())

            {

                pnon_root_trees = & pnon_root_trees->begin()->children;

            }

            pnon_root_trees->insert(pnon_root_trees->begin(),

                    tmp.begin(), tmp.end());

        }

        else if (0 != a.trees.size() && a.trees.begin()->value.is_root())

        {

            BOOST_SPIRIT_ASSERT(a.trees.size() == 1);

#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)

            a.trees.begin()->children.reserve(a.trees.begin()->children.size() + b.trees.size());

#endif

            std::copy(b.trees.begin(),

                 b.trees.end(),

                 std::back_insert_iterator<container_t>(

                     a.trees.begin()->children));

        }

        else

        {

#if !defined(BOOST_SPIRIT_USE_LIST_FOR_TREES)

            a.trees.reserve(a.trees.size() + b.trees.size());

#endif

            std::copy(b.trees.begin(),

                 b.trees.end(),

                 std::back_insert_iterator<container_t>(a.trees));

        }

#if defined(BOOST_SPIRIT_DEBUG) && \

    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)

        BOOST_SPIRIT_DEBUG_OUT << ">>>after AST concat. a = " << a << "<<<\n\n";

#endif

        return;

    }

    template <typename MatchT, typename Iterator1T, typename Iterator2T>

    static void group_match(MatchT& m, parser_id const& id,

            Iterator1T const& first, Iterator2T const& last)

    {

        if (!m)

            return;

        typedef typename tree_match<iterator_t, NodeFactoryT>::container_t

            container_t;

        typedef typename container_t::iterator cont_iterator_t;

        typedef typename NodeFactoryT::template factory<iterator_t> factory_t;

        if (m.trees.size() == 1

#ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING

            && !(id.to_long() && m.trees.begin()->value.id().to_long())

#endif

            )

        {

            // set rule_id's.  There may have been multiple nodes created.

            // Because of root_node[] they may be left-most children of the top

            // node.

            container_t* punset_id = &m.trees;

            while (punset_id->size() > 0 &&

                    punset_id->begin()->value.id() == 0)

            {

                punset_id->begin()->value.id(id);

                punset_id = &punset_id->begin()->children;

            }

            m.trees.begin()->value.is_root(false);

        }

        else

        {

            match_t newmatch(m.length(),

                m.trees.empty() ? 

                    factory_t::empty_node() : 

                    factory_t::create_node(first, last, false));

            std::swap(newmatch.trees.begin()->children, m.trees);

            // set this node and all it's unset children's rule_id

            newmatch.trees.begin()->value.id(id);

            for (cont_iterator_t i = newmatch.trees.begin();

                 i != newmatch.trees.end();

                 ++i)

            {

                if (i->value.id() == 0)

                    i->value.id(id);

            }

            m = newmatch;

        }

    }

    template <typename FunctorT>

    static void apply_op_to_match(FunctorT const& op, match_t& m)

    {

        op(m);

    }

};

namespace impl {

    template <typename IteratorT, typename NodeFactoryT>

    struct tree_policy_selector<ast_match_policy<IteratorT, NodeFactoryT> >

    {

        typedef ast_tree_policy<

            ast_match_policy<IteratorT, NodeFactoryT>, NodeFactoryT> type;

    };

} // namespace impl

//////////////////////////////////

struct gen_ast_node_parser_gen;

template <typename T>

struct gen_ast_node_parser

:   public unary<T, parser<gen_ast_node_parser<T> > >

{

    typedef gen_ast_node_parser<T> self_t;

    typedef gen_ast_node_parser_gen parser_generator_t;

    typedef unary_parser_category parser_category_t;

//    typedef gen_ast_node_parser<T> const &embed_t;

    gen_ast_node_parser(T const& a)

    : unary<T, parser<gen_ast_node_parser<T> > >(a) {}

    template <typename ScannerT>

    typename parser_result<self_t, ScannerT>::type

    parse(ScannerT const& scan) const

    {

        typedef typename ScannerT::iteration_policy_t iteration_policy_t;

        typedef typename ScannerT::match_policy_t::iterator_t iterator_t;

        typedef typename ScannerT::match_policy_t::factory_t factory_t;

        typedef ast_match_policy<iterator_t, factory_t> match_policy_t;

        typedef typename ScannerT::action_policy_t action_policy_t;

        typedef scanner_policies<

            iteration_policy_t,

            match_policy_t,

            action_policy_t

        > policies_t;

        return this->subject().parse(scan.change_policies(policies_t(scan)));

    }

};

//////////////////////////////////

struct gen_ast_node_parser_gen

{

    template <typename T>

    struct result {

        typedef gen_ast_node_parser<T> type;

    };

    template <typename T>

    static gen_ast_node_parser<T>

    generate(parser<T> const& s)

    {

        return gen_ast_node_parser<T>(s.derived());

    }

    template <typename T>

    gen_ast_node_parser<T>

    operator[](parser<T> const& s) const

    {

        return gen_ast_node_parser<T>(s.derived());

    }

};

//////////////////////////////////

const gen_ast_node_parser_gen gen_ast_node_d = gen_ast_node_parser_gen();

//////////////////////////////////

struct root_node_op

{

    template <typename MatchT>

    void operator()(MatchT& m) const

    {

        BOOST_SPIRIT_ASSERT(m.trees.size() > 0);

        m.trees.begin()->value.is_root(true);

    }

};

const node_parser_gen<root_node_op> root_node_d =

    node_parser_gen<root_node_op>();

///////////////////////////////////////////////////////////////////////////////

//

//  Parse functions for ASTs

//

///////////////////////////////////////////////////////////////////////////////

template <

    typename AstFactoryT, typename IteratorT, typename ParserT, 

    typename SkipT

>

inline tree_parse_info<IteratorT, AstFactoryT>

ast_parse(

    IteratorT const&        first_,

    IteratorT const&        last_,

    parser<ParserT> const&  parser,

    SkipT const&            skip_,

    AstFactoryT const &   /*dummy_*/ = AstFactoryT())

{

    typedef skip_parser_iteration_policy<SkipT> iter_policy_t;

    typedef ast_match_policy<IteratorT, AstFactoryT> ast_match_policy_t;

    typedef

        scanner_policies<iter_policy_t, ast_match_policy_t>

        scanner_policies_t;

    typedef scanner<IteratorT, scanner_policies_t> scanner_t;

    iter_policy_t iter_policy(skip_);

    scanner_policies_t policies(iter_policy);

    IteratorT first = first_;

    scanner_t scan(first, last_, policies);

    tree_match<IteratorT, AstFactoryT> hit = parser.derived().parse(scan);

    scan.skip(scan);

    return tree_parse_info<IteratorT, AstFactoryT>(

        first, hit, hit && (first == last_), hit.length(), hit.trees);

}

//////////////////////////////////

template <typename IteratorT, typename ParserT, typename SkipT>

inline tree_parse_info<IteratorT>

ast_parse(

    IteratorT const&        first_,

    IteratorT const&        last_,

    parser<ParserT> const&  parser,

    SkipT const&            skip_)

{

    typedef node_val_data_factory<nil_t> default_factory_t;

    return ast_parse(first_, last_, parser, skip_, default_factory_t());

}

//////////////////////////////////

template <typename IteratorT, typename ParserT>

inline tree_parse_info<IteratorT>

ast_parse(

    IteratorT const&        first_,

    IteratorT const&        last,

    parser<ParserT> const&  parser)

{

    typedef ast_match_policy<IteratorT> ast_match_policy_t;

    IteratorT first = first_;

    scanner<

        IteratorT,

        scanner_policies<iteration_policy, ast_match_policy_t>

    > scan(first, last);

    tree_match<IteratorT> hit = parser.derived().parse(scan);

    return tree_parse_info<IteratorT>(

        first, hit, hit && (first == last), hit.length(), hit.trees);

}

//////////////////////////////////

template <typename CharT, typename ParserT, typename SkipT>

inline tree_parse_info<CharT const*>

ast_parse(

    CharT const*            str,

    parser<ParserT> const&  parser,

    SkipT const&            skip)

{

    CharT const* last = str;

    while (*last)

        last++;

    return ast_parse(str, last, parser, skip);

}

//////////////////////////////////

template <typename CharT, typename ParserT>

inline tree_parse_info<CharT const*>

ast_parse(

    CharT const*            str,

    parser<ParserT> const&  parser)

{

    CharT const* last = str;

    while (*last)

    {

        last++;

    }

    return ast_parse(str, last, parser);

}

///////////////////////////////////////////////////////////////////////////////

}} // namespace boost::spirit

#endif