Changeset f2e40a9f for src/GenPoly

Timestamp:

Mar 15, 2017, 9:43:15 PM (8 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

27fed7f1, 738e304

Parents:

bf4ac09 (diff), 9b443c7f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

git-author:

Peter A. Buhr <pabuhr@…> (03/15/17 21:25:49)

git-committer:

Peter A. Buhr <pabuhr@…> (03/15/17 21:43:15)

Message:

Merge branch 'master' of plg2:software/cfa/cfa-cc

Location:

src/GenPoly

Files:

• Box.cc (modified) (2 diffs)
• GenPoly.cc (modified) (5 diffs)
• GenPoly.h (modified) (2 diffs)
• InstantiateGeneric.cc (modified) (5 diffs)
• ScrubTyVars.cc (modified) (1 diff)
• ScrubTyVars.h (modified) (5 diffs)

src/GenPoly/Box.cc

@@ -381 +381 @@
                 // calculate struct layout in function body
 
-                // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size
+                // initialize size and alignment to 0 and 1 (will have at least one member to re-edit size)
                 addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( sizeParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "0" ) ) ) );
                 addExpr( layoutDecl->get_statements(), makeOp( "?=?", derefVar( alignParam ), new ConstantExpr( Constant( sizeAlignType->clone(), "1" ) ) ) );
@@ -1852 +1852 @@
 
                         DeclClass *ret = static_cast< DeclClass *>( Mutator::mutate( decl ) );
-                        ScrubTyVars::scrub( decl, scopeTyVars );
+                        // ScrubTyVars::scrub( decl, scopeTyVars );
+                        ScrubTyVars::scrubAll( decl );
 
                         scopeTyVars.endScope();

src/GenPoly/GenPoly.cc

@@ -15 +15 @@
 
 #include "GenPoly.h"
+#include "assert.h"
 
 #include "SynTree/Expression.h"
 #include "SynTree/Type.h"
+#include "ResolvExpr/typeops.h"
 
 #include <iostream>
+#include <iterator>
+#include <list>
+#include <typeindex>
+#include <typeinfo>
+#include <vector>
 using namespace std;
 
@@ -38 +45 @@
                         for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
                                 TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
-                                assert(paramType && "Aggregate parameters should be type expressions");
+                                assertf(paramType, "Aggregate parameters should be type expressions");
                                 if ( isPolyType( paramType->get_type(), tyVars, env ) ) return true;
                         }
@@ -48 +55 @@
                         for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
                                 TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
-                                assert(paramType && "Aggregate parameters should be type expressions");
+                                assertf(paramType, "Aggregate parameters should be type expressions");
                                 if ( isDynType( paramType->get_type(), tyVars, env ) ) return true;
+                        }
+                        return false;
+                }
+
+                /// Checks a parameter list for inclusion of polymorphic parameters; will substitute according to env if present
+                bool includesPolyParams( std::list< Expression* >& params, const TypeSubstitution *env ) {
+                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
+                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
+                                assertf(paramType, "Aggregate parameters should be type expressions");
+                                if ( includesPolyType( paramType->get_type(), env ) ) return true;
+                        }
+                        return false;
+                }
+
+                /// Checks a parameter list for inclusion of polymorphic parameters from tyVars; will substitute according to env if present
+                bool includesPolyParams( std::list< Expression* >& params, const TyVarMap &tyVars, const TypeSubstitution *env ) {
+                        for ( std::list< Expression* >::iterator param = params.begin(); param != params.end(); ++param ) {
+                                TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
+                                assertf(paramType, "Aggregate parameters should be type expressions");
+                                if ( includesPolyType( paramType->get_type(), tyVars, env ) ) return true;
                         }
                         return false;
@@ -187 +214 @@
 
                 return isPolyType( type, tyVars, env );
+        }
+
+        bool includesPolyType( Type *type, const TypeSubstitution *env ) {
+                type = replaceTypeInst( type, env );
+
+                if ( dynamic_cast< TypeInstType * >( type ) ) {
+                        return true;
+                } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) {
+                        if ( includesPolyType( pointerType->get_base(), env ) ) return true;
+                } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
+                        if ( includesPolyParams( structType->get_parameters(), env ) ) return true;
+                } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
+                        if ( includesPolyParams( unionType->get_parameters(), env ) ) return true;
+                }
+                return false;
+        }
+
+        bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env ) {
+                type = replaceTypeInst( type, env );
+
+                if ( TypeInstType *typeInstType = dynamic_cast< TypeInstType * >( type ) ) {
+                        if ( tyVars.find( typeInstType->get_name() ) != tyVars.end() ) {
+                                return true;
+                        }
+                } else if ( PointerType *pointerType = dynamic_cast< PointerType* >( type ) ) {
+                        if ( includesPolyType( pointerType->get_base(), tyVars, env ) ) return true;
+                } else if ( StructInstType *structType = dynamic_cast< StructInstType* >( type ) ) {
+                        if ( includesPolyParams( structType->get_parameters(), tyVars, env ) ) return true;
+                } else if ( UnionInstType *unionType = dynamic_cast< UnionInstType* >( type ) ) {
+                        if ( includesPolyParams( unionType->get_parameters(), tyVars, env ) ) return true;
+                }
+                return false;
         }
 
@@ -237 +296 @@
         }
 
+        namespace {
+                /// Checks if is a pointer to D
+                template<typename D, typename B>
+                bool is( const B* p ) { return type_index{typeid(D)} == type_index{typeid(*p)}; }
+
+                /// Converts to a pointer to D without checking for safety
+                template<typename D, typename B>
+                inline D* as( B* p ) { return reinterpret_cast<D*>(p); }
+
+                /// Flattens a declaration list
+                template<typename Output>
+                void flattenList( list< DeclarationWithType* > src, Output out ) {
+                        for ( DeclarationWithType* decl : src ) {
+                                ResolvExpr::flatten( decl->get_type(), out );
+                        }
+                }
+
+                /// Flattens a list of types
+                template<typename Output>
+                void flattenList( list< Type* > src, Output out ) {
+                        for ( Type* ty : src ) {
+                                ResolvExpr::flatten( ty, out );
+                        }
+                }
+
+                /// Checks if two lists of parameters are equal up to polymorphic substitution.
+                bool paramListsPolyCompatible( const list< Expression* >& aparams, const list< Expression* >& bparams ) {
+                        if ( aparams.size() != bparams.size() ) return false;
+
+                        for ( list< Expression* >::const_iterator at = aparams.begin(), bt = bparams.begin();
+                                        at != aparams.end(); ++at, ++bt ) {
+                                TypeExpr *aparam = dynamic_cast< TypeExpr* >(*at);
+                                assertf(aparam, "Aggregate parameters should be type expressions");
+                                TypeExpr *bparam = dynamic_cast< TypeExpr* >(*bt);
+                                assertf(bparam, "Aggregate parameters should be type expressions");
+
+                                // xxx - might need to let VoidType be a wildcard here too; could have some voids 
+                                // stuffed in for dtype-statics.
+                                // if ( is<VoidType>( aparam->get_type() ) || is<VoidType>( bparam->get_type() ) ) continue;
+                                if ( ! typesPolyCompatible( aparam->get_type(), bparam->get_type() ) ) return false;
+                        }
+                        
+                        return true;
+                }
+        }
+
+        bool typesPolyCompatible( Type *a, Type *b ) {
+                type_index aid{ typeid(*a) };
+                // polymorphic types always match
+                if ( aid == type_index{typeid(TypeInstType)} ) return true;
+                
+                type_index bid{ typeid(*b) };
+                // polymorphic types always match
+                if ( bid == type_index{typeid(TypeInstType)} ) return true;
+                
+                // can't match otherwise if different types
+                if ( aid != bid ) return false;
+
+                // recurse through type structure (conditions borrowed from Unify.cc)
+                if ( aid == type_index{typeid(BasicType)} ) {
+                        return as<BasicType>(a)->get_kind() == as<BasicType>(b)->get_kind();
+                } else if ( aid == type_index{typeid(PointerType)} ) {
+                        PointerType *ap = as<PointerType>(a), *bp = as<PointerType>(b);
+
+                        // void pointers should match any other pointer type
+                        return is<VoidType>( ap->get_base() ) || is<VoidType>( bp->get_base() )
+                                || typesPolyCompatible( ap->get_base(), bp->get_base() );
+                } else if ( aid == type_index{typeid(ArrayType)} ) {
+                        ArrayType *aa = as<ArrayType>(a), *ba = as<ArrayType>(b);
+
+                        if ( aa->get_isVarLen() ) {
+                                if ( ! ba->get_isVarLen() ) return false;
+                        } else {
+                                if ( ba->get_isVarLen() ) return false;
+
+                                ConstantExpr *ad = dynamic_cast<ConstantExpr*>( aa->get_dimension() );
+                                ConstantExpr *bd = dynamic_cast<ConstantExpr*>( ba->get_dimension() );
+                                if ( ad && bd 
+                                                && ad->get_constant()->get_value() != bd->get_constant()->get_value() )
+                                        return false;
+                        }
+
+                        return typesPolyCompatible( aa->get_base(), ba->get_base() );
+                } else if ( aid == type_index{typeid(FunctionType)} ) {
+                        FunctionType *af = as<FunctionType>(a), *bf = as<FunctionType>(b);
+
+                        vector<Type*> aparams, bparams;
+                        flattenList( af->get_parameters(), back_inserter( aparams ) );
+                        flattenList( bf->get_parameters(), back_inserter( bparams ) );
+                        if ( aparams.size() != bparams.size() ) return false;
+
+                        vector<Type*> areturns, breturns;
+                        flattenList( af->get_returnVals(), back_inserter( areturns ) );
+                        flattenList( bf->get_returnVals(), back_inserter( breturns ) );
+                        if ( areturns.size() != breturns.size() ) return false;
+
+                        for ( unsigned i = 0; i < aparams.size(); ++i ) {
+                                if ( ! typesPolyCompatible( aparams[i], bparams[i] ) ) return false;
+                        }
+                        for ( unsigned i = 0; i < areturns.size(); ++i ) {
+                                if ( ! typesPolyCompatible( areturns[i], breturns[i] ) ) return false;
+                        }
+                        return true;
+                } else if ( aid == type_index{typeid(StructInstType)} ) {
+                        StructInstType *aa = as<StructInstType>(a), *ba = as<StructInstType>(b);
+
+                        if ( aa->get_name() != ba->get_name() ) return false;
+                        return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
+                } else if ( aid == type_index{typeid(UnionInstType)} ) {
+                        UnionInstType *aa = as<UnionInstType>(a), *ba = as<UnionInstType>(b);
+
+                        if ( aa->get_name() != ba->get_name() ) return false;
+                        return paramListsPolyCompatible( aa->get_parameters(), ba->get_parameters() );
+                } else if ( aid == type_index{typeid(EnumInstType)} ) {
+                        return as<EnumInstType>(a)->get_name() == as<EnumInstType>(b)->get_name();
+                } else if ( aid == type_index{typeid(TraitInstType)} ) {
+                        return as<TraitInstType>(a)->get_name() == as<TraitInstType>(b)->get_name();
+                } else if ( aid == type_index{typeid(TupleType)} ) {
+                        TupleType *at = as<TupleType>(a), *bt = as<TupleType>(b);
+
+                        vector<Type*> atypes, btypes;
+                        flattenList( at->get_types(), back_inserter( atypes ) );
+                        flattenList( bt->get_types(), back_inserter( btypes ) );
+                        if ( atypes.size() != btypes.size() ) return false;
+
+                        for ( unsigned i = 0; i < atypes.size(); ++i ) {
+                                if ( ! typesPolyCompatible( atypes[i], btypes[i] ) ) return false;
+                        }
+                        return true;
+                } else return true; // VoidType, VarArgsType, ZeroType & OneType just need the same type
+        }
+
         void addToTyVarMap( TypeDecl * tyVar, TyVarMap &tyVarMap ) {
                 tyVarMap[ tyVar->get_name() ] = TypeDecl::Data{ tyVar };

src/GenPoly/GenPoly.h

@@ -67 +67 @@
         Type *hasPolyBase( Type *type, const TyVarMap &tyVars, int *levels = 0, const TypeSubstitution *env = 0 );
 
+        /// true iff this type or some base of this type after dereferencing pointers is either polymorphic or a generic type with at least one 
+        /// polymorphic parameter; will look up substitution in env if provided.
+        bool includesPolyType( Type *type, const TypeSubstitution *env = 0 );
+
+        /// true iff this type or some base of this type after dereferencing pointers is either polymorphic in tyVars, or a generic type with 
+        /// at least one polymorphic parameter in tyVars; will look up substitution in env if provided.
+        bool includesPolyType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 );
+
         /// Returns a pointer to the base FunctionType if ty is the type of a function (or pointer to one), NULL otherwise
         FunctionType *getFunctionType( Type *ty );
@@ -73 +81 @@
         /// N will be stored in levels, if provided
         VariableExpr *getBaseVar( Expression *expr, int *levels = 0 );
+
+        /// true iff types are structurally identical, where TypeInstType's match any type.
+        bool typesPolyCompatible( Type *aty, Type *bty );
 
         /// Adds the type variable `tyVar` to `tyVarMap`

src/GenPoly/InstantiateGeneric.cc

@@ -16 +16 @@
 #include <cassert>
 #include <list>
+#include <unordered_map>
 #include <utility>
 #include <vector>
-#include <unordered_map>
 
 #include "InstantiateGeneric.h"
@@ -25 +25 @@
 #include "GenPoly.h"
 #include "ScopedSet.h"
+#include "ScrubTyVars.h"
 #include "PolyMutator.h"
 
@@ -77 +78 @@
                         if ( params.size() != that.params.size() ) return false;
 
-                        SymTab::Indexer dummy;
                         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;
+                                if ( ! typesPolyCompatible( *it, *jt ) ) return false;
                         }
                         return true;
@@ -227 +227 @@
                         if ( (*baseParam)->isComplete() ) {
                                 // substitute parameter for complete (otype or sized dtype) type
-                                int pointerLevels = 0;
-                                if ( hasPolyBase( paramType->get_type(), &pointerLevels ) && pointerLevels > 0 ) {
-                                        // Make a void* with equivalent nesting
-                                        Type* voidPtr = new VoidType( Type::Qualifiers() );
-                                        while ( pointerLevels > 0 ) {
-                                                // Just about data layout, so qualifiers *shouldn't* matter
-                                                voidPtr = new PointerType( Type::Qualifiers(), voidPtr );
-                                                --pointerLevels;
-                                        }
-                                        out.push_back( new TypeExpr( voidPtr ) );
+                                if ( isPolyType( paramType->get_type() ) ) {
+                                        // substitute polymorphic parameter type in to generic type
+                                        out.push_back( paramType->clone() );
+                                        gt = genericType::dynamic;
                                 } else {
-                                        // Just clone parameter type
-                                        out.push_back( paramType->clone() );
+                                        // normalize possibly dtype-static parameter type
+                                        out.push_back( new TypeExpr{ 
+                                                ScrubTyVars::scrubAll( paramType->get_type()->clone() ) } );
+                                        gt |= genericType::concrete;
                                 }
-                                // make the struct concrete or dynamic depending on the parameter
-                                gt |= isPolyType( paramType->get_type() ) ? genericType::dynamic : genericType::concrete;
                         } else switch ( (*baseParam)->get_kind() ) {
                                 case TypeDecl::Dtype:
@@ -372 +366 @@
                                 concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
                                 concDecl->set_body( inst->get_baseStruct()->has_body() );
-                                substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs,        concDecl->get_members() );
+                                substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
                                 DeclMutator::addDeclaration( concDecl );
                                 insert( inst, typeSubs, concDecl );

src/GenPoly/ScrubTyVars.cc

@@ -26 +26 @@
 namespace GenPoly {
         Type * ScrubTyVars::mutate( TypeInstType *typeInst ) {
-                TyVarMap::const_iterator tyVar = tyVars.find( typeInst->get_name() );
-                if ( tyVar != tyVars.end() ) {
+                if ( ! tyVars ) {
+                        if ( typeInst->get_isFtype() ) {
+                                delete typeInst;
+                                return new PointerType( Type::Qualifiers(), new FunctionType( Type::Qualifiers(), true ) );
+                        } else {
+                                PointerType *ret = new PointerType( Type::Qualifiers(), new VoidType( typeInst->get_qualifiers() ) );
+                                delete typeInst;
+                                return ret;
+                        }
+                }
+
+                TyVarMap::const_iterator tyVar = tyVars->find( typeInst->get_name() );
+                if ( tyVar != tyVars->end() ) {
                         switch ( tyVar->second.kind ) {
                           case TypeDecl::Any:

src/GenPoly/ScrubTyVars.h

@@ -26 +26 @@
 namespace GenPoly {
         class ScrubTyVars : public Mutator {
-          public:
-                ScrubTyVars( const TyVarMap &tyVars, bool dynamicOnly = false ): tyVars( tyVars ), dynamicOnly( dynamicOnly ) {}
+                /// Whether to scrub all type variables from the provided map, dynamic type variables from the provided map, or all type variables
+                enum ScrubMode { FromMap, DynamicFromMap, All };
 
+                ScrubTyVars() : tyVars(nullptr), mode( All ) {}
+
+                ScrubTyVars( const TyVarMap &tyVars, ScrubMode mode = FromMap ): tyVars( &tyVars ), mode( mode ) {}
+
+        public:
                 /// For all polymorphic types with type variables in `tyVars`, replaces generic types, dtypes, and ftypes with the appropriate void type,
                 /// and sizeof/alignof expressions with the proper variable
@@ -38 +43 @@
                 template< typename SynTreeClass >
                 static SynTreeClass *scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars );
+
+                /// For all polymorphic types, replaces generic types, dtypes, and ftypes with the appropriate void type,
+                /// and sizeof/alignof expressions with the proper variable
+                template< typename SynTreeClass >
+                static SynTreeClass *scrubAll( SynTreeClass *target );
 
                 virtual Type* mutate( TypeInstType *typeInst );
@@ -49 +59 @@
                 /// Returns the type if it should be scrubbed, NULL otherwise.
                 Type* shouldScrub( Type *ty ) {
-                        return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars );
-//                      if ( ! dynamicOnly ) return isPolyType( ty, tyVars );
-// 
-//                      if ( TypeInstType *typeInst = dynamic_cast< TypeInstType* >( ty ) ) {
-//                              return tyVars.find( typeInst->get_name() ) != tyVars.end() ? ty : 0;
-//                      }
-// 
-//                      return isDynType( ty, tyVars );
+                        switch ( mode ) {
+                        case FromMap: return isPolyType( ty, *tyVars );
+                        case DynamicFromMap: return isDynType( ty, *tyVars );
+                        case All: return isPolyType( ty );
+                        }
+                        assert(false); return nullptr; // unreachable
+                        // return dynamicOnly ? isDynType( ty, tyVars ) : isPolyType( ty, tyVars );
                 }
                 
@@ -62 +71 @@
                 Type* mutateAggregateType( Type *ty );
                 
-                const TyVarMap &tyVars;  ///< Type variables to scrub
-                bool dynamicOnly;        ///< only scrub the types with dynamic layout? [false]
+                const TyVarMap *tyVars;  ///< Type variables to scrub
+                ScrubMode mode;          ///< which type variables to scrub? [FromMap]
         };
 
@@ -74 +83 @@
         template< typename SynTreeClass >
         SynTreeClass * ScrubTyVars::scrubDynamic( SynTreeClass *target, const TyVarMap &tyVars ) {
-                ScrubTyVars scrubber( tyVars, true );
+                ScrubTyVars scrubber( tyVars, ScrubTyVars::DynamicFromMap );
+                return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) );
+        }
+
+        template< typename SynTreeClass >
+        SynTreeClass * ScrubTyVars::scrubAll( SynTreeClass *target ) {
+                ScrubTyVars scrubber;
                 return static_cast< SynTreeClass * >( target->acceptMutator( scrubber ) );
         }