source: src/ResolvExpr/TypeMap.h @ 17e0dc9

//
// 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.
//
// ScopedMap.h --
//
// Author           : Aaron B. Moss
// Created On       : Fri Feb 19 13:55:00 2016
// Last Modified By : Aaron B. Moss
// Last Modified On : Fri Feb 19 13:55:00 2016
// Update Count     : 1
//

#ifndef _TYPEMAP_H
#define _TYPEMAP_H

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

#include "SynTree/Type.h"
#include "SynTree/Visitor.h"

namespace ResolvExpr {

        /// A map from types to some value; lookup is done by structural decomposition on types.
        /// The TypeMap stores its values by reference, so stored objects should be kept alive by the caller.
        /// The scoping mechanism essentially by keeping a list of changes to roll back, then rolling them back
        /// WARNING: This map is only incompletely and approximately consistent with the resolution rules in Unify.cc;
        /// it has potential, if extended, to form the basis of a resolver that is more performant than the current
        /// linear-search-by-unification approach, but is only currently used for finding assignment operators in GenPoly::box.
        template< typename Value >
        class TypeMap {
                /// Map of names to types
                typedef typename std::map< std::string, Value* > ValueMap;
                typedef typename ValueMap::iterator ValueMapIterator;

                Value *voidValue;                                     ///< Value for void type
                Value *basicValue[BasicType::NUMBER_OF_BASIC_TYPES];  ///< Values for basic types
                Value *pointerValue;                                  ///< Value for all pointer types
                Value *voidPointerValue;                              ///< Value for void* types
                Value *functionPointerValue;                          ///< Value for all function pointer types
                ValueMap structValue;                                 ///< Values for struct types, indexed by name
                ValueMap unionValue;                                  ///< Values for struct types, indexed by name
                ValueMap enumValue;                                   ///< Values for struct types, indexed by name

                /// Information needed to roll back one scope change
                struct Rollback {
                        /// One scope of pointer rollbacks
                        typedef std::vector< std::pair< Value **, Value* > > PointerScope;
                        /// One scope of map rollbacks
                        typedef std::vector< std::pair< ValueMapIterator, Value* > > MapScope;

                        PointerScope pointers;  ///< Value pointers to roll back to their previous state
                        MapScope mapNodes;      ///< Value map iterators to roll back to their previous state

                        void addRollback( Value **loc, Value *old ) {
                                pointers.push_back( std::make_pair( loc, old ) );
                        }

                        void addRollback( ValueMapIterator loc, Value *old ) {
                                mapNodes.push_back( std::make_pair( loc, old ) );
                        }
                };

                std::vector< Rollback > scopes;  ///< Scope rollback information

                struct Lookup : public Visitor {
                        Lookup( TypeMap<Value> &typeMap ) : typeMap( typeMap ), found( 0 ), toInsert( 0 ) {}

                        /// Inserts a new value into the map; returns the old value (if set, NULL otherwise).
                        /// key must be non-null.
                        Value *insert( Type *key, Value *val ) {
                                toInsert = val;
                                key->accept( *this );
                                return found;
                        }

                        /// Looks up a value in the map.
                        /// key must be non-null.
                        Value *find( Type *key ) {
                                //toInsert = 0;
                                key->accept( *this );
                                return found;
                        }

                        void findAndReplace( Value *&loc ) {
                                found = loc;
                                if ( toInsert ) {
                                        typeMap.scopes.back().addRollback( &loc, found );
                                        loc = toInsert;
                                }
                        }

                        void findAndReplace( ValueMap &map, const std::string &name ) {
                                ValueMapIterator loc = map.find( name );
                                if ( loc != map.end() ) {
                                        found = loc->second;
                                        if ( toInsert ) {
                                                typeMap.scopes.back().addRollback( loc, found );
                                                loc->second = toInsert;
                                        }
                                } else if ( toInsert ) {
                                        loc = map.insert( loc, std::make_pair( name, toInsert ) );
                                        typeMap.scopes.back().addRollback( loc, found );
                                }
                        }

                        virtual void visit( VoidType *voidType ) {
                                findAndReplace( typeMap.voidValue );
                        }

                        virtual void visit( BasicType *basicType ) {
                                findAndReplace( typeMap.basicValue[basicType->get_kind()] );
                        }

                        virtual void visit( PointerType *pointerType ) {
                                // NOTE This is one of the places where the apporoximation of the resolver is (deliberately) poor;
                                // A better version would likely not equate all pointer types to a match.
                                if ( dynamic_cast< FunctionType* >( pointerType->get_base() ) ) {
                                        findAndReplace( typeMap.functionPointerValue );
                                } else if ( dynamic_cast< VoidType* >( pointerType->get_base() ) ) {
                                        findAndReplace( typeMap.voidPointerValue );
                                } else {
                                        findAndReplace( typeMap.pointerValue );
                                }
                        }

                        virtual void visit( ArrayType *arrayType ) {
                                if ( dynamic_cast< FunctionType* >( arrayType->get_base() ) ) {
                                        findAndReplace( typeMap.functionPointerValue );
                                } else {
                                        findAndReplace( typeMap.pointerValue );
                                }
                        }

                        virtual void visit( FunctionType *functionType ) {
                                findAndReplace( typeMap.functionPointerValue );
                        }

                        virtual void visit( StructInstType *structType ) {
                                findAndReplace( typeMap.structValue, structType->get_name() );
                        }

                        virtual void visit( UnionInstType *unionType ) {
                                findAndReplace( typeMap.unionValue, unionType->get_name() );
                        }

                        virtual void visit( EnumInstType *enumType ) {
                                findAndReplace( typeMap.enumValue, enumType->get_name() );
                        }

                        TypeMap<Value> &typeMap;  ///< map storage
                        Value *found;             ///< Value found (NULL if none yet)
                        Value *toInsert;          ///< Value to insert (NULL if a lookup)
                };  // struct Lookup
                friend struct Lookup;

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

                /// Ends a scope; rolls back any changes made during that scope
                void endScope() {
                        Rollback &scope = scopes.back();
                        /// Roll back pointer changes
                        for (unsigned i = 0; i < scope.pointers.size(); ++i) {
                                *scope.pointers[i].first = scope.pointers[i].second;
                        }
                        /// Roll back map changes
                        for (unsigned i = 0; i < scope.mapNodes.size(); ++i) {
                                scope.mapNodes[i].first->second = scope.mapNodes[i].second;
                        }
                        scopes.pop_back();
                }

                TypeMap() : voidValue( 0 ), pointerValue( 0 ), voidPointerValue( 0 ), functionPointerValue( 0 ), structValue(), unionValue(), enumValue(), scopes() {
                        beginScope();
                        for (int i = 0; i < BasicType::NUMBER_OF_BASIC_TYPES; ++i) { basicValue[i] = 0; }
                }

                /// Inserts a new value into the map; returns the old value (if set, NULL otherwise).
                /// key, val must be non-null.
                Value *insert( Type *key, Value *val ) {
                        Lookup searcher( *this );
                        return searcher.insert( key, val );
                }

                /// Looks up a value in the map.
                /// key must be non-null
                Value *find( Type *key ) {
                        Lookup searcher( *this );
                        return searcher.find( key );
                }

        }; // class TypeMap

}  // namespace ResolvExpr

#endif // _TYPEMAP_H

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