Index: src/ResolvExpr/TypeMap.h =================================================================== --- src/ResolvExpr/TypeMap.h (revision 4067aa896fa95717c23b7b70fff9f35b7375392f) +++ src/ResolvExpr/TypeMap.h (revision 4067aa896fa95717c23b7b70fff9f35b7375392f) @@ -0,0 +1,212 @@ +// +// 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 +#include +#include +#include + +#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 &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 &typeMap; ///< map storage + Value *found; ///< Value found (NULL if none yet) + Value *toInsert; ///< Value to insert (NULL if a lookup) + }; // class Lookup + friend class 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: //