manager.cc

Go to the documentation of this file.

/*
   The lestes compiler suite
   Copyright (C) 2002, 2003, 2004, 2005 Miroslav Tichy
   Copyright (C) 2002, 2003, 2004, 2005 Petr Zika
   Copyright (C) 2002, 2003, 2004, 2005 Vojtech Hala
   Copyright (C) 2002, 2003, 2004, 2005 Jiri Kosina
   Copyright (C) 2002, 2003, 2004, 2005 Pavel Sanda
   Copyright (C) 2002, 2003, 2004, 2005 Jan Zouhar
   Copyright (C) 2002, 2003, 2004, 2005 Rudolf Thomas

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   See the full text of the GNU General Public License version 2, and
   the limitations in the file doc/LICENSE.

   By accepting the license the licensee waives any and all claims
   against the copyright holder(s) related in whole or in part to the
   work, its use, and/or the inability to use it.
 
 */
#include <lestes/lang/cplus/lex/preprocessor.hh>
#include <lestes/lang/cplus/syn/errors.m.hh>
#include <lestes/lang/cplus/syn/hinter.hh>
#include <lestes/lang/cplus/syn/manager.hh>
#include <lestes/lang/cplus/syn/prefixer.hh>
#include <lestes/lang/cplus/syn/syn.hh>
#include <lestes/lang/cplus/syn/token.hh>
#include <lestes/msg/logger.hh>
#include <lestes/std/list.hh>
#include <lestes/std/objectize_macros.hh>
#include <lestes/std/source_location.hh>
#include <stack>
#include <map>
#include <set>
#include <iostream>

package(lestes);
package(lang);
package(cplus);
package(syn);

typedef list< srp<bison_token> >        token_list_type;
typedef token_list_type::iterator       token_list_iterator;
typedef list< srp<action> >             action_list_type;

end_package(syn);
end_package(cplus);
end_package(lang);
package(std);

specialize_objectize_nodump( ::lestes::lang::cplus::syn::token_list_iterator );

end_package(std);
package(lang);
package(cplus);
package(syn);

declare_logger( ml );
initialize_logger( ml, "manager", syn_logger );

initialize_event( manager::spawn_event );
initialize_event( manager::close_event );
initialize_event( manager::start_event );
initialize_event( manager::commit_event );
initialize_event( manager::rollback_event );

typedef list<token_list_iterator>       iter_list_type;

class streamer : public ::lestes::std::object {
public:
        virtual ptr<bison_token> first() abstract;
        virtual ptr<bison_token> next() abstract;
};

class source_streamer : public streamer {
private:
        static ptr<source_streamer> the_instance;
protected:
        source_streamer() : streamer()
        {}
public:
        static ptr<source_streamer> instance()
        {
                //XXX: the following line might get removed in the future :)
                lassert2( !the_instance, "We only allow calling this method once." );
                if (!the_instance)
                        the_instance = new source_streamer();
                return the_instance;
        }
        virtual ptr<bison_token> first()
        {
                return bison_madeup_token::create(
                        source_location::zero(), bison_token::TOK_START_PROGRAM );
        }
        virtual ptr<bison_token> next()
        {
                return prefixer::yylex();
        }
};

ptr<source_streamer> source_streamer::the_instance;

class pack_streamer : public streamer {
private:
        bool eof_sent;
        srp<bison_pack_token> tokpack;
        token_list_type::iterator it;
protected:
        pack_streamer( ptr<bison_pack_token> tp )
                : eof_sent(false), tokpack(checked(tp))
        {}
        void gc_mark()
        {
                tokpack.gc_mark();
                streamer::gc_mark();
        }
public:
        static ptr<pack_streamer> create( ptr<bison_pack_token> tp )
        {
                return new pack_streamer(tp);
        }
        virtual ptr<bison_token> first()
        {
                it = tokpack->pack_get()->begin();
                return tokpack;
        }
        virtual ptr<bison_token> next()
        {
                lassert2( !eof_sent, "Token requested, but EOF already sent." );
                if (it != tokpack->pack_get()->end())
                        return *it++;
                eof_sent = true;
                lassert2( tokpack->end_location_get(),
                                "The pack (token) does not have its end_location set." );
                return bison_madeup_token::create( tokpack->end_location_get(), bison_token::TOK_EOF );
        }
};

class transaction : public ::lestes::std::object {
protected:
        //! list of actions that need to be done when this transaction is rolled back
        srp<action_list_type>           undo_list;
        const token_list_iterator       start_pos;

        transaction( const token_list_iterator & spos ) : start_pos(spos)
        {
                undo_list = action_list_type::create();
        }
        void gc_mark()
        {
                undo_list.gc_mark();
                object::gc_mark();
        }
public:
        static ptr<transaction> create( const token_list_iterator & spos )
        {
                return new transaction(spos);
        }
        const token_list_iterator start_pos_get() const
        {
                return start_pos;
        }
        //! runs all the undo actions in LIFO (reverse) order, returns number of them
        ulint undo()
        {
                ulint result = 0;
                for (action_list_type::reverse_iterator it = undo_list->rbegin();
                                it != undo_list->rend();
                                ++it, ++result )
                        (*it)->run();
                return result;
        }
        //! just hand over own undo list to the enclosing transaction
        void submit_undo( ptr<transaction> enclosing_tx )
        {
                lassert( enclosing_tx );
                enclosing_tx->undo_list->splice( enclosing_tx->undo_list->end(), *undo_list );
        }

        void add_undo_action( ptr<action> action )
        {
                lassert( action );
                undo_list->push_back( action );
        }
};

class undo_delete_token : public action {
protected:
        srp<token_list_type>            token_list;
        const token_list_iterator       position;

        undo_delete_token( ptr<token_list_type> a_list, const token_list_iterator &pos )
                : token_list(a_list), position(pos)
        {}
public:
        static ptr<undo_delete_token> create( ptr<token_list_type> a_list,
                        const token_list_iterator &pos )
        {
                return new undo_delete_token( a_list, pos );
        }
        virtual void run()
        {
                token_list->erase(position);
        }
};

// unpacks a_pack inserting the result *before* given position in given list
class undo_unpack : public undo_delete_token {
protected:
        srp<token_list_type> pack;
        undo_unpack( ptr<token_list_type> a_list, const token_list_iterator &pos,
                        ptr<token_list_type> a_pack ) : undo_delete_token( a_list, pos ), pack(a_pack)
        {}
        void gc_mark()
        {
                pack.gc_mark();
                undo_delete_token::gc_mark();
        }
public:
        static ptr<undo_unpack> create( ptr<token_list_type> a_list, const token_list_iterator &pos,
                        ptr<token_list_type> a_pack )
        {
                return new undo_unpack( a_list, pos, a_pack );
        }
        virtual void run()
        {
                token_list->splice( position, *pack );
        }
};

class one_manager : public ::lestes::std::object {
private:
        srp<streamer> src;
        srp<bison_token> last_token;
protected:
        bool                            run_hinter;
        bool                            failing;
        srp<token_list_type>            token_list;
        token_list_iterator             token_list_pos;
        // open transactions stack; we push/pop to/from back :-)
        srp< list< srp<transaction> > > open_transactions;
protected:
        one_manager( const ptr<streamer> & );
        void gc_mark()
        {
                src.gc_mark();
                last_token.gc_mark();
                token_list.gc_mark();
                open_transactions.gc_mark();
                object::gc_mark();
        }
        //! Finds closing token (e.g. parenthesis); opening token must be specified too.
        void find_closing( int closing, int opening, const ptr<source_location> & loc );

        //! Contains a set of skeletal tokens used in error recovery.
        static ::std::set<int> error_stmt_end_set;
public:
        static ptr<one_manager> create( const ptr<streamer> & a_src )
        {
                return new one_manager(a_src);
        }
        //! Initializes the maps.
        static void init();

        ptr<bison_token> yylex();
        ptr<bison_token> prev_yylex();
        ptr<bison_token> peek();
        void back_up();
        void start( int );
        void commit( int );
        void rollback();
        ptr<bison_pack_token> pack( int, const ptr<source_location> & );
        void unpack();
        bool in_disambiguation() const;
        void install_undo_action( ptr<action> a );
        bool failing_get() const;
        void failing_set_true();
};

::std::set<int> one_manager::error_stmt_end_set;

void one_manager::init()
{
        error_stmt_end_set.insert( bison_token::TOK_BREAK );
        error_stmt_end_set.insert( bison_token::TOK_CATCH );
        error_stmt_end_set.insert( bison_token::TOK_CONTINUE );
        error_stmt_end_set.insert( bison_token::TOK_DO );
        error_stmt_end_set.insert( bison_token::TOK_ELSE );
        error_stmt_end_set.insert( bison_token::TOK_FOR );
        error_stmt_end_set.insert( bison_token::TOK_GOTO );
        error_stmt_end_set.insert( bison_token::TOK_IF );
        error_stmt_end_set.insert( bison_token::TOK_RETURN );
        error_stmt_end_set.insert( bison_token::TOK_SWITCH );
        error_stmt_end_set.insert( bison_token::TOK_TRY );
        error_stmt_end_set.insert( bison_token::TOK_WHILE );
        error_stmt_end_set.insert( bison_token::TOK_SEMICOLON );
        error_stmt_end_set.insert( bison_token::TOK_EOF );
        error_stmt_end_set.insert( bison_token::TOK_LEFT_BRACE );
        error_stmt_end_set.insert( bison_token::TOK_RIGHT_BRACE );
}

/*!
 *
 * Immediately adds first token from the tokeniser into token_list.
 */
one_manager::one_manager( const ptr<streamer> & s )
{
        src = s;
        last_token = NULL;
        run_hinter = true;
        failing = false;
        token_list = token_list_type::create();
        token_list->push_back( s->first() );
        token_list_pos = token_list->begin();
        open_transactions = list< srp<transaction> >::create();
}

bool one_manager::in_disambiguation() const
{
        return !open_transactions->empty();
}

ptr<bison_token> one_manager::yylex()
{
        ptr<bison_token> t = peek();
        // discard unneeded tokens; this only happens at top-level
        if (!in_disambiguation() && token_list_pos != token_list->begin())
                token_list->pop_front();
        ++token_list_pos;

        // run the hinter, if needed
        // note that the old (not-hinted) token is stored in token_list
        if (run_hinter && t->type_get() == bison_token::TOK_IDENT)
                t = hinter::hint( t, peek() );
        last_token = t;
        return t;
}

ptr<bison_token> one_manager::prev_yylex()
{
        lassert2( last_token, "yylex() was not called previously." );
        return last_token;
}

ptr<bison_token> one_manager::peek()
{
        ptr<bison_token> t;
        if (token_list_pos == token_list->end()) {
                t = src->next();
                token_list_pos = token_list->insert( token_list_pos, t );
        } else
                t = *token_list_pos;
        return t;
}

void one_manager::back_up()
{
        // make sure there is room to back up
        // this ensures that only one backing up is allowed between two successive calls to yylex()
        lassert( token_list_pos != token_list->begin() );
        // make sure we do not back up over current start token
        lassert( open_transactions->empty() ||
                        token_list_pos != open_transactions->back()->start_pos_get() );

        --token_list_pos;

        llog(ml) << "backing up " << ptr<bison_token>(*token_list_pos) << "\n";
}

void one_manager::start( int type )
{
        lassert( type > bison_token::_START_FIRST && type < bison_token::_START_LAST );

        ptr<bison_token> t = bison_madeup_token::create( peek()->location_get(), type );
        token_list_pos = token_list->insert( token_list_pos, t );
        open_transactions->push_back( transaction::create(token_list_pos) );
        llog(ml) << "starting with " << t << "\n";

        manager::start_event->trigger();
}

void one_manager::commit( int type )
{
        lassert( in_disambiguation() );
        lassert( type > bison_token::_PAD_FIRST && type < bison_token::_PAD_LAST );

        ptr<transaction> this_tx = open_transactions->back();
        open_transactions->pop_back();

        token_list_pos = this_tx->start_pos_get();

        // create the pad, take location from the start-token
        ptr<bison_token> pad = bison_madeup_token::create( (*token_list_pos)->location_get(), type );

        llog(ml) << "committing " << pad << " over " <<
                ptr<bison_token>(*this_tx->start_pos_get()) << "\n";

        // do overwrite (commit) the token
        *token_list_pos = pad;

        // hand over undo actions from nested diambiguation(s), if needed
        if (in_disambiguation()) {
                ptr<transaction> prev_tx = open_transactions->back();
                prev_tx->add_undo_action( undo_delete_token::create( token_list, token_list_pos ) );
                this_tx->submit_undo( prev_tx );
        }

        manager::commit_event->trigger();
}

void one_manager::rollback()
{
        lassert( in_disambiguation() );

        ptr<transaction> this_tx = open_transactions->back();
        open_transactions->pop_back();

        llog(ml) << "rolling back " << ptr<bison_token>(*this_tx->start_pos_get());
        ulint count = this_tx->undo();
        token_list_pos = token_list->erase( this_tx->start_pos_get() );

        llog_plain(ml) << " (" << count << " undo actions)\n";

        manager::rollback_event->trigger();
}

/*!
 * Packs tokens from the stream to form a pack token with given type. The
 * actual packing method used depends on the type of the desired token.
 *
 * Some packing methods need to report the error as being located before the
 * first token of the pack. It is passed in start_loc in these cases. Note that
 * we cannot rely on prev_yylex() here, because there may have been
 * no previous calls to yylex(). However, the parser (which usually calls us)
 * can be pretty sure.
 * 
 * \param pack_type  Type of desired token pack. Determines the packing method used.
 * \param start_loc  Location that is passed to some of the packing method for error reporting.
 */
ptr<bison_pack_token> one_manager::pack( int pack_type, const ptr<source_location> & start_loc )
{
        lassert( pack_type > bison_token::_PACK_FIRST && pack_type < bison_token::_PACK_LAST );
        // save state and disable running the hinter
        bool run_hinter_old = run_hinter;
        run_hinter = false;
        // insert a dommy token, it will be overwritten by a pack token in commit()
        start( bison_token::TOK_START_TO_BE_DISCARDED );
        // skip it
        yylex();
        switch (pack_type) {
                case bison_token::TOK_PACK_BODY:
                        find_closing( bison_token::TOK_RIGHT_BRACE,
                                        bison_token::TOK_LEFT_BRACE, start_loc );
                        break;
                case bison_token::TOK_PACK_ERROR_COND:
                        find_closing( bison_token::TOK_RIGHT_PAR,
                                        bison_token::TOK_LEFT_PAR, start_loc );
                        break;
                case bison_token::TOK_PACK_ERROR_FOR_COND:
                        find_closing( bison_token::TOK_SEMICOLON,
                                        bison_token::TOK_SEMICOLON, start_loc );
                        break;
                case bison_token::TOK_PACK_ERROR_STMT:
                        // skip all tokens until one in the terminator set is read
                        while (error_stmt_end_set.find( yylex()->type_get() ) == error_stmt_end_set.end())
                                ;
                        /* if the terminating token was ';', skip it too; this solves "if(1)int;else;" */
                        if (prev_yylex()->type_get() == bison_token::TOK_SEMICOLON)
                                yylex();
                        break;
                default:
                        lassert2( false, "This type of packing is not implemented yet." );
        }
        // 'to' will point just after the terminating token (which we do *not* want in the pack)
        token_list_iterator to = token_list_pos;
        commit( bison_token::TOK_PAD_TO_BE_DISCARDED );
        token_list_iterator from = token_list_pos;

        // remember not to pack the pack token nor the terminating token
        ++from;
        --to;

        // location of the pack token is the location of the first token in the pack
        // its end_location is the location of the token that terminated this pack
        //   (it is *not* included in the pack)
        ptr<bison_pack_token> pack_tok = bison_pack_token::create(
                        (*from)->location_get(), pack_type, (*to)->location_get() );
        // the actual packing:
        ptr<token_list_type> the_pack = pack_tok->pack_get();
        the_pack->splice( the_pack->end(), *token_list, from, to );
        // when rolling back, unpack the pack just before the terminating token
        ptr<action> unpack = undo_unpack::create( token_list, to, the_pack );
        if (in_disambiguation())
                open_transactions->back()->add_undo_action( unpack );

        llog(ml) << "replacing " << ptr<bison_token>(*token_list_pos) <<
                " with " << ptr<bison_token>(pack_tok) << "\n";
        *token_list_pos = pack_tok;
        // restore state
        run_hinter = run_hinter_old;

        return pack_tok;
}

void one_manager::unpack()
{
        const ptr<bison_token> & next_tok = *token_list_pos;
        lassert( next_tok->type_get() > bison_token::_PACK_FIRST &&
                        next_tok->type_get() < bison_token::_PACK_LAST );
        llog(ml) << "unpacking " << next_tok << "\n";

        const ptr<bison_pack_token> & pack_tok = next_tok.dncast<bison_pack_token>();

        // We cannot use token_list_pos, as splice "moves the iterator away"...
        token_list_iterator pos_after_pack = token_list_pos;
        ++pos_after_pack;
        token_list->splice( pos_after_pack, *(pack_tok->pack_get()) );
        // ...now pos_after_pack points to token following the last unpacked one, not to the first of the pack.
        token_list_pos = token_list->erase( token_list_pos );
}

void one_manager::install_undo_action( ptr<action> a )
{
        lassert( in_disambiguation() );
        open_transactions->back()->add_undo_action(a);
}

/*!
 * Reads tokens using yylex() to find closing parenthesis/bracket/brace.
 *
 * Tokens are read until one with closing type is found. Each occurence of
 * token with opening type requires its counterpart with closing type to be
 * read before a token with the closing type is considered to be terminating.
 *
 * When EOF is read before all occurences of opening tokens are closed, errors
 * are reported.
 *
 * The position in the stream is left to point just after the terminating
 * token. This is needed for pack() to work. This method is called exclusively
 * from there.
 *
 * When closing == opening nesting is not done and very first occurence of a
 * token with such value is considered closing.
 *
 * A location must be provided for cases when the unclosed opening token lies
 * before tokens read by the method. It is used for error reporting only.
 *
 * \param closing  type of token considered to be closing [parenthesis]
 * \param opening  type of token considered to be opening [parenthesis]
 * \param loc      location used to error reports that are out of "scope"
 *
 */
void one_manager::find_closing( int closing, int opening, const ptr<source_location> & loc )
{
        lassert( loc );
        typedef list< srp<bison_token> > stack_type;
        ptr<stack_type> st = stack_type::create();
        while (true) {
                ptr<bison_token> t = yylex();
                int ttype = t->type_get();
                if (ttype == bison_token::TOK_EOF) {
                        // BOOM
                        if (st->empty())
                                report << unmatched_open << loc;
                        else
                                report << unmatched_open << st->back()->location_get();
                        // do not report errors when we return back to the parser
                        failing_set_true();
                        break;
                }
                if (ttype == closing) {
                        if (st->empty())
                                break;  // closing one found
                        else
                                st->pop_back();
                } else if (ttype == opening)
                        st->push_back( t );
        }
}

bool one_manager::failing_get() const
{
        return failing;
}

void one_manager::failing_set_true()
{
        failing = true;
}

typedef list< srp<one_manager> >        mgr_stack_type;
static ptr<mgr_stack_type>              mgr_stack;

void manager::init()
{
        mgr_stack = mgr_stack_type::create();
        mgr_stack->push_back( one_manager::create( source_streamer::instance() ) );

        one_manager::init();
}

void manager::spawn( ptr<bison_pack_token> t )
{
        mgr_stack->push_back( one_manager::create( pack_streamer::create(t) ) );
        spawn_event->trigger();
}

void manager::close()
{
        mgr_stack->pop_back();
        lassert( !mgr_stack->empty() );
        close_event->trigger();
}

ptr<bison_token> manager::yylex()
{
        lassert( !mgr_stack->empty() );
        return mgr_stack->back()->yylex();
}

ptr<bison_token> manager::prev_yylex()
{
        lassert( !mgr_stack->empty() );
        return mgr_stack->back()->prev_yylex();
}

ptr<bison_token> manager::peek()
{
        lassert( !mgr_stack->empty() );
        return mgr_stack->back()->peek();
}

void manager::back_up()
{
        lassert( !mgr_stack->empty() );
        mgr_stack->back()->back_up();
}

void manager::start( int type )
{
        lassert( !mgr_stack->empty() );
        mgr_stack->back()->start( type );
}

void manager::commit( int type )
{
        lassert( !mgr_stack->empty() );
        mgr_stack->back()->commit( type );
}

void manager::rollback()
{
        lassert( !mgr_stack->empty() );
        mgr_stack->back()->rollback();
}

ptr<bison_pack_token> manager::pack( int pack_type, const ptr<source_location> & start_loc )
{
        lassert( !mgr_stack->empty() );
        return mgr_stack->back()->pack( pack_type, start_loc );
}

void manager::unpack()
{
        lassert( !mgr_stack->empty() );
        mgr_stack->back()->unpack();
}

bool manager::in_disambiguation()
{
        lassert( !mgr_stack->empty() );
        return mgr_stack->back()->in_disambiguation();
}

void manager::install_undo_action( ptr<action> a )
{
        lassert( !mgr_stack->empty() );
        mgr_stack->back()->install_undo_action(a);
}

bool manager::failing_get()
{
        lassert( !mgr_stack->empty() );
        return mgr_stack->back()->failing_get();
}

void manager::failing_set_true()
{
        lassert( !mgr_stack->empty() );
        return mgr_stack->back()->failing_set_true();
}

end_package(syn);
end_package(cplus);
end_package(lang);
end_package(lestes);

---