Changeset 5a3ac84 for src/GenPoly/GenPoly.cc

Timestamp:

Mar 15, 2017, 5:01:18 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

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:

9b443c7f

Parents:

17df48e

Message:

Fixed Box(T*) generic instantiation bug

File:

• src/GenPoly/GenPoly.cc (modified) (5 diffs)

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 };