Index: src/GenPoly/Box.cc =================================================================== --- src/GenPoly/Box.cc (revision 43181074867ab6b19a3a764f8f4989f623670408) +++ src/GenPoly/Box.cc (revision dc124819c235617d272c2eee265317c408956362) @@ -25,5 +25,4 @@ #include "PolyMutator.h" #include "FindFunction.h" -#include "ScopedMap.h" #include "ScrubTyVars.h" @@ -38,4 +37,6 @@ #include "ResolvExpr/TypeEnvironment.h" +#include "ResolvExpr/TypeMap.h" +#include "ResolvExpr/typeops.h" #include "SymTab/Mangler.h" @@ -101,5 +102,5 @@ typedef std::map< std::string, DeclarationWithType *> AdapterMap; std::map< std::string, DeclarationWithType *> assignOps; - ScopedMap< std::string, DeclarationWithType *> scopedAssignOps; + ResolvExpr::TypeMap< DeclarationWithType > scopedAssignOps; std::stack< AdapterMap > adapters; DeclarationWithType *retval; @@ -248,12 +249,12 @@ } - /// returns T if the given declaration is: (*?=?)(T *, T) for some T (return not checked, but maybe should be), NULL otherwise - ReferenceToType *isAssignment( DeclarationWithType *decl ) { + /// Returns T if the given declaration is (*?=?)(T *, T) for some TypeInstType T (return not checked, but maybe should be), NULL otherwise + TypeInstType *isTypeInstAssignment( DeclarationWithType *decl ) { if ( decl->get_name() == "?=?" ) { if ( FunctionType *funType = getFunctionType( decl->get_type() ) ) { if ( funType->get_parameters().size() == 2 ) { if ( PointerType *pointer = dynamic_cast< PointerType *>( funType->get_parameters().front()->get_type() ) ) { - if ( ReferenceToType *refType = dynamic_cast< ReferenceToType *>( pointer->get_base() ) ) { - if ( ReferenceToType *refType2 = dynamic_cast< ReferenceToType *>( funType->get_parameters().back()->get_type() ) ) { + if ( TypeInstType *refType = dynamic_cast< TypeInstType *>( pointer->get_base() ) ) { + if ( TypeInstType *refType2 = dynamic_cast< TypeInstType *>( funType->get_parameters().back()->get_type() ) ) { if ( refType->get_name() == refType2->get_name() ) { return refType; @@ -267,4 +268,30 @@ return 0; } + + /// returns T if the given declaration is: (*?=?)(T *, T) for some type T (return not checked, but maybe should be), NULL otherwise + /// Only picks assignments where neither parameter is cv-qualified + Type *isAssignment( DeclarationWithType *decl ) { + if ( decl->get_name() == "?=?" ) { + if ( FunctionType *funType = getFunctionType( decl->get_type() ) ) { + if ( funType->get_parameters().size() == 2 ) { + Type::Qualifiers defaultQualifiers; + Type *paramType1 = funType->get_parameters().front()->get_type(); + if ( paramType1->get_qualifiers() != defaultQualifiers ) return 0; + Type *paramType2 = funType->get_parameters().back()->get_type(); + if ( paramType2->get_qualifiers() != defaultQualifiers ) return 0; + + if ( PointerType *pointerType = dynamic_cast< PointerType* >( paramType1 ) ) { + Type *baseType1 = pointerType->get_base(); + if ( baseType1->get_qualifiers() != defaultQualifiers ) return 0; + SymTab::Indexer dummy; + if ( ResolvExpr::typesCompatible( baseType1, paramType2, dummy ) ) { + return baseType1; + } // if + } // if + } // if + } // if + } // if + return 0; + } void Pass1::findAssignOps( const std::list< TypeDecl *> &forall ) { @@ -274,5 +301,5 @@ for ( std::list< DeclarationWithType *>::const_iterator assert = (*i)->get_assertions().begin(); assert != (*i)->get_assertions().end(); ++assert ) { std::string typeName; - if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( isAssignment( *assert ) ) ) { + if ( TypeInstType *typeInst = isTypeInstAssignment( *assert ) ) { assignOps[ typeInst->get_name() ] = *assert; } // if @@ -283,7 +310,7 @@ DeclarationWithType *Pass1::mutate( FunctionDecl *functionDecl ) { // if this is a polymorphic assignment function, put it in the map for this scope - if ( ReferenceToType *refType = isAssignment( functionDecl ) ) { - if ( ! dynamic_cast< TypeInstType* >( refType ) ) { - scopedAssignOps.insert( refType->get_name(), functionDecl ); + if ( Type *assignedType = isAssignment( functionDecl ) ) { + if ( ! dynamic_cast< TypeInstType* >( assignedType ) ) { + scopedAssignOps.insert( assignedType, functionDecl ); } } @@ -934,7 +961,7 @@ TyVarMap exprTyVars; makeTyVarMap( function, exprTyVars ); - ReferenceToType *polyRetType = 0; - - if ( polyRetType = isPolyRet( function ) ) { + ReferenceToType *polyRetType = isPolyRet( function ); + + if ( polyRetType ) { ret = addPolyRetParam( appExpr, function, polyRetType, arg ); } else if ( needsAdapter( function, scopeTyVars ) ) { @@ -1042,11 +1069,10 @@ } else if ( ReferenceToType *refType = dynamic_cast< ReferenceToType *>( retval->get_type() ) ) { // find assignment operator for generic type - ScopedMap< std::string, DeclarationWithType *>::const_iterator assignIter = scopedAssignOps.find( refType->get_name() ); - if ( assignIter == scopedAssignOps.end() ) { + DeclarationWithType *functionDecl = scopedAssignOps.find( refType ); + if ( ! functionDecl ) { throw SemanticError( "Attempt to return dtype or ftype generic object in ", returnStmt->get_expr() ); } // wrap it up in an application expression - DeclarationWithType *functionDecl = assignIter->second; assignExpr = new ApplicationExpr( wrapFunctionDecl( functionDecl ) ); assignExpr->set_env( env->clone() ); @@ -1063,5 +1089,5 @@ assert( ! asserts.empty() && "Type param needs assignment operator assertion" ); DeclarationWithType *actualDecl = asserts.front(); - ReferenceToType *actualType = isAssignment( actualDecl ); + TypeInstType *actualType = isTypeInstAssignment( actualDecl ); assert( actualType && "First assertion of type with assertions should be assignment operator" ); TypeExpr *formalTypeExpr = dynamic_cast< TypeExpr* >( *tyIt ); @@ -1077,12 +1103,10 @@ } assertAssign = assertAssignIt->second; - //assignExpr->get_env()->add( formalTypeInstType->get_name(), actualType ); - } else if ( ReferenceToType *formalReferenceType = dynamic_cast< ReferenceToType* >( formalType ) ) { - ScopedMap< std::string, DeclarationWithType *>::const_iterator assertAssignIt = scopedAssignOps.find( formalReferenceType->get_name() ); - if ( assertAssignIt == scopedAssignOps.end() ) { - throw SemanticError( "No assignment operation found for ", formalReferenceType ); + } else { + assertAssign = scopedAssignOps.find( formalType ); + if ( ! assertAssign ) { + throw SemanticError( "No assignment operation found for ", formalType ); } - assertAssign = assertAssignIt->second; - } else assert( false && "returning polymorphic types with non struct/polymorphic parameters not yet supported" ); + } Index: src/ResolvExpr/TypeMap.h =================================================================== --- src/ResolvExpr/TypeMap.h (revision dc124819c235617d272c2eee265317c408956362) +++ src/ResolvExpr/TypeMap.h (revision dc124819c235617d272c2eee265317c408956362) @@ -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: //