source: src/GenPoly/InstantiateGeneric.cc @ a2eda27

//
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// InstantiateGeneric.h --
//
// Author           : Aaron B. Moss
// Created On       : Wed Nov 11 14:55:01 2015
// Last Modified By : Aaron B. Moss
// Last Modified On : Wed Nov 11 14:55:01 2015
// Update Count     : 1
//

#include <list>
#include <map>
#include <string>
#include <utility>
#include <vector>

#include "InstantiateGeneric.h"
#include "PolyMutator.h"

#include "ResolvExpr/typeops.h"
#include "SymTab/Indexer.h"
#include "SynTree/Declaration.h"
#include "SynTree/Mutator.h"
#include "SynTree/Statement.h"
#include "SynTree/Type.h"
#include "SynTree/TypeSubstitution.h"

#include "UniqueName.h"
#include "utility.h"

namespace GenPoly {

        class Instantiate : public PolyMutator {
        public:
                /// Key for a unique concrete type; generic base type paired with type parameter list
                struct ConcreteType {
                        ConcreteType() : base(NULL), params() {}

                        ConcreteType(AggregateDecl *_base, const std::list< Type* >& _params) : base(_base), params() { cloneAll(_params, params); }

                        ConcreteType(const ConcreteType& that) : base(that.base), params() { cloneAll(that.params, params); }

                        /// Extracts types from a list of Expression* (which should be TypeExpr*)
                        ConcreteType(AggregateDecl *_base, const std::list< Expression* >& _params) : base(_base), params() {
                                for ( std::list< Expression* >::const_iterator it = _params.begin(); it != _params.end(); ++it ) {
                                        TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
                                        assert(param && "Aggregate parameters should be type expressions");
                                        params.push_back( param->get_type()->clone() );
                                }
                        }

                        ConcreteType& operator= (const ConcreteType& that) {
                                deleteAll( params );
                                params.clear();
                                
                                base = that.base;
                                cloneAll( that.params, params );

                                return *this;
                        }

                        ~ConcreteType() { deleteAll( params ); }
                        
                        bool operator== (const ConcreteType& that) const {
                                SymTab::Indexer dummy;
                                
                                if ( base != that.base ) return false;
                                if ( params.size() != that.params.size() ) return false;
                                for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
                                        if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
                                }
                                return true;
                        }

                        AggregateDecl *base;        ///< Base generic type
                        std::list< Type* > params;  ///< Instantiation parameters
                };
                
                /// Maps a concrete type to the instantiated struct type, accounting for scope
                class InstantiationMap {
                        /// Pair of concrete type and declaration that instantiates it
                        typedef std::pair< ConcreteType, AggregateDecl* > Instantiation;
                        /// Map of generic types to instantiations of them
                        typedef std::map< AggregateDecl*, std::vector< Instantiation > > Scope;

                        std::vector< Scope > scopes;  ///< list of scopes, from outermost to innermost

                public:
                        /// Starts a new scope
                        void beginScope() {
                                Scope scope;
                                scopes.push_back(scope);
                        }

                        /// Ends a scope
                        void endScope() {
                                scopes.pop_back();
                        }
                        
                        /// Default constructor initializes with one scope
                        InstantiationMap() { beginScope(); }

                private:
                        /// Gets the declaration for the concrete instantiation of this type, assuming it has already been instantiated in the current scope.
                        /// Returns NULL on none such.
                        AggregateDecl* lookup( AggregateDecl *generic, std::list< Expression* >& params ) {
                                ConcreteType key(generic, params);
                                // scan scopes from innermost out
                                for ( std::vector< Scope >::const_reverse_iterator scope = scopes.rbegin(); scope != scopes.rend(); ++scope ) {
                                        // skip scope if no instantiations of this generic type
                                        Scope::const_iterator insts = scope->find( generic );
                                        if ( insts == scope->end() ) continue;
                                        // look through instantiations for matches to concrete type
                                        for ( std::vector< Instantiation >::const_iterator inst = insts->second.begin(); inst != insts->second.end(); ++inst ) {
                                                if ( inst->first == key ) return inst->second;
                                        }
                                }
                                // no matching instantiation found
                                return NULL;
                        }
                public:
                        StructDecl* lookup( StructInstType *inst ) { return (StructDecl*)lookup( inst->get_baseStruct(), inst->get_parameters() ); }
                        UnionDecl* lookup( UnionInstType *inst ) { return (UnionDecl*)lookup( inst->get_baseUnion(), inst->get_parameters() ); }

                private:
                        /// Adds a declaration for a concrete type to the current scope
                        void insert( AggregateDecl *generic, std::list< Expression* >& params, AggregateDecl *decl ) {
                                ConcreteType key(generic, params);
                                scopes.back()[generic].push_back( std::make_pair( key, decl ) );
                        }
                public:
                        void insert( StructInstType *inst, StructDecl *decl ) { insert( inst->get_baseStruct(), inst->get_parameters(), decl ); }
                        void insert( UnionInstType *inst, UnionDecl *decl ) { insert( inst->get_baseUnion(), inst->get_parameters(), decl ); }
                };

                virtual Type* mutate( StructInstType *inst );
                virtual Type* mutate( UnionInstType *inst );
                
                virtual void doBeginScope();
                virtual void doEndScope();

        private:
                /// Adds a declaration to the current environment and the statements to add
                void addDeclaration( AggregateDecl *decl ) {
                        std::list< Label > labels;
                        DeclStmt *stmt = new DeclStmt( labels, decl );
                        PolyMutator::stmtsToAdd.push_back( stmt );
                }
                
                InstantiationMap instantiations;
                UniqueName typeNamer;
        };
        
        void instantiateGeneric( std::list< Declaration* >& translationUnit ) {
                Instantiate instantiator;
                mutateAll( translationUnit, instantiator );
        }

        /// Substitutes types of members of in according to baseParams => params, appending the result to out
        void substituteMembers( const std::list< Declaration* >& in,
                                                        const std::list< TypeDecl * >& baseParams, const std::list< Expression* >& params,
                                                    std::list< Declaration* >& out ) {
                // substitute types into new members
                TypeSubstitution subs( baseParams.begin(), baseParams.end(), params.begin() );
                for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) {
                        Declaration *newMember = (*member)->clone();
                        subs.apply(newMember);
                        out.push_back( newMember );
                }
        }

        Type* Instantiate::mutate( StructInstType *inst ) {
                // mutate subtypes
                Type *mutated = Mutator::mutate( inst );
                inst = dynamic_cast< StructInstType* >( mutated );
                if ( ! inst ) return mutated;

                // exit early if no need for further mutation
                if ( inst->get_parameters().empty() ) return inst;
                
                // make concrete instantiation of generic type
                StructDecl *concDecl = instantiations.lookup( inst );
                if ( ! concDecl ) {
                        // set concDecl to new type, insert type declaration into statements to add
                        concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
                        substituteMembers( inst->get_baseStruct()->get_members(),
                                                                inst->get_baseParameters(), inst->get_parameters(),
                                                                concDecl->get_members() );
                        addDeclaration( concDecl );
                        instantiations.insert( inst, concDecl );
                }
                StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() );
                newInst->set_baseStruct( concDecl );
                delete inst;
                return newInst;
        }
        
        Type* Instantiate::mutate( UnionInstType *inst ) {
                // mutate subtypes
                Type *mutated = Mutator::mutate( inst );
                inst = dynamic_cast< UnionInstType* >( mutated );
                if ( ! inst ) return mutated;

                // exit early if no need for further mutation
                if ( inst->get_parameters().empty() ) return inst;

                // make concrete instantiation of generic type
                UnionDecl *concDecl = instantiations.lookup( inst );
                if ( ! concDecl ) {
                        // set concDecl to new type, insert type declaration into statements to add
                        concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) );
                        substituteMembers( inst->get_baseUnion()->get_members(),
                                                                inst->get_baseParameters(), inst->get_parameters(),
                                                                concDecl->get_members() );
                        addDeclaration( concDecl );
                        instantiations.insert( inst, concDecl );
                }
                UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() );
                newInst->set_baseUnion( concDecl );
                delete inst;
                return newInst;
        }
        
        void Instantiate::doBeginScope() {
                // push a new concrete type scope
                instantiations.beginScope();
        }

        void Instantiate::doEndScope() {
                // pop the last concrete type scope
                instantiations.endScope();
        }
        
}  // namespace GenPoly

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //