Index: src/AST/Decl.hpp =================================================================== --- src/AST/Decl.hpp (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/AST/Decl.hpp (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -217,5 +217,5 @@ /// convenience accessor to match Type::isComplete() - bool isComplete() { return sized; } + bool isComplete() const { return sized; } const Decl * accept( Visitor & v ) const override { return v.visit( this ); } Index: src/AST/Type.hpp =================================================================== --- src/AST/Type.hpp (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/AST/Type.hpp (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -83,5 +83,5 @@ template< enum Node::ref_type ref_t > void reset_qualifiers( ptr_base< Type, ref_t > & p, CV::Qualifiers q = {} ) { - if ( p->qualifiers.val != q.val ) p.get_and_mutate()->qualifiers = q; + if ( p->qualifiers != q ) p.get_and_mutate()->qualifiers = q; } @@ -89,5 +89,5 @@ template< enum Node::ref_type ref_t > void add_qualifiers( ptr_base< Type, ref_t > & p, CV::Qualifiers q ) { - if ( ( p->qualifiers.val & q.val ) != q.val ) p.get_and_mutate()->qualifiers |= q; + if ( ( p->qualifiers & q ) != q ) p.get_and_mutate()->qualifiers |= q; } @@ -95,5 +95,5 @@ template< enum Node::ref_type ref_t > void remove_qualifiers( ptr_base< Type, ref_t > & p, CV::Qualifiers q ) { - if ( ( p->qualifiers.val & q.val ) != 0 ) p.get_and_mutate()->qualifiers -= q; + if ( ( p->qualifiers & q ) != 0 ) p.get_and_mutate()->qualifiers -= q; } Index: src/GenPoly/GenPoly.cc =================================================================== --- src/GenPoly/GenPoly.cc (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/GenPoly/GenPoly.cc (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Wed Jun 29 21:45:53 2016 -// Update Count : 14 +// Last Modified By : Andrew Beach +// Last Modified On : Wed Sep 14 9:24:00 2022 +// Update Count : 15 // @@ -83,4 +83,15 @@ } + bool hasDynParams( const std::vector> & params, const TyVarMap &tyVars, const ast::TypeSubstitution *typeSubs ) { + for ( ast::ptr const & param : params ) { + auto paramType = param.as(); + assertf( paramType, "Aggregate parameters should be type expressions." ); + if ( isDynType( paramType->type, tyVars, typeSubs ) ) { + 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 ) { @@ -198,4 +209,24 @@ } return 0; + } + + const ast::BaseInstType *isDynType( const ast::Type *type, const TyVarMap &tyVars, const ast::TypeSubstitution *typeSubs ) { + type = replaceTypeInst( type, typeSubs ); + + if ( auto inst = dynamic_cast( type ) ) { + auto var = tyVars.find( inst->name ); + if ( var != tyVars.end() && var->second.isComplete ) { + return inst; + } + } else if ( auto inst = dynamic_cast( type ) ) { + if ( hasDynParams( inst->params, tyVars, typeSubs ) ) { + return inst; + } + } else if ( auto inst = dynamic_cast( type ) ) { + if ( hasDynParams( inst->params, tyVars, typeSubs ) ) { + return inst; + } + } + return nullptr; } @@ -378,4 +409,9 @@ inline D* as( B* p ) { return reinterpret_cast(p); } + template + inline D const * as( B const * p ) { + return reinterpret_cast( p ); + } + /// Flattens a declaration list template @@ -391,4 +427,11 @@ for ( Type* ty : src ) { ResolvExpr::flatten( ty, out ); + } + } + + void flattenList( vector> const & src, + vector> & out ) { + for ( auto const & type : src ) { + ResolvExpr::flatten( type, out ); } } @@ -409,4 +452,29 @@ // if ( is( aparam->get_type() ) || is( bparam->get_type() ) ) continue; if ( ! typesPolyCompatible( aparam->get_type(), bparam->get_type() ) ) return false; + } + + return true; + } + + bool paramListsPolyCompatible( + std::vector> const & lparams, + std::vector> const & rparams ) { + if ( lparams.size() != rparams.size() ) { + return false; + } + + for ( auto lparam = lparams.begin(), rparam = rparams.begin() ; + lparam != lparams.end() ; ++lparam, ++rparam ) { + ast::TypeExpr const * lexpr = lparam->as(); + assertf( lexpr, "Aggregate parameters should be type expressions" ); + ast::TypeExpr const * rexpr = rparam->as(); + assertf( rexpr, "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( lexpr->type() ) || is( bparam->get_type() ) ) continue; + if ( !typesPolyCompatible( lexpr->type, rexpr->type ) ) { + return false; + } } @@ -505,4 +573,116 @@ } +bool typesPolyCompatible( ast::Type const * lhs, ast::Type const * rhs ) { + type_index const lid = typeid(*lhs); + + // Polymorphic types always match: + if ( type_index(typeid(ast::TypeInstType)) == lid ) return true; + + type_index const rid = typeid(*rhs); + if ( type_index(typeid(ast::TypeInstType)) == rid ) return true; + + // All other types only match if they are the same type: + if ( lid != rid ) return false; + + // So remaining types can be examined case by case. + // Recurse through type structure (conditions borrowed from Unify.cc). + + if ( type_index(typeid(ast::BasicType)) == lid ) { + return as(lhs)->kind == as(rhs)->kind; + } else if ( type_index(typeid(ast::PointerType)) == lid ) { + ast::PointerType const * l = as(lhs); + ast::PointerType const * r = as(rhs); + + // void pointers should match any other pointer type. + return is( l->base.get() ) + || is( r->base.get() ) + || typesPolyCompatible( l->base.get(), r->base.get() ); + } else if ( type_index(typeid(ast::ReferenceType)) == lid ) { + ast::ReferenceType const * l = as(lhs); + ast::ReferenceType const * r = as(rhs); + + // void references should match any other reference type. + return is( l->base.get() ) + || is( r->base.get() ) + || typesPolyCompatible( l->base.get(), r->base.get() ); + } else if ( type_index(typeid(ast::ArrayType)) == lid ) { + ast::ArrayType const * l = as(lhs); + ast::ArrayType const * r = as(rhs); + + if ( l->isVarLen ) { + if ( !r->isVarLen ) return false; + } else { + if ( r->isVarLen ) return false; + + auto lc = l->dimension.as(); + auto rc = r->dimension.as(); + if ( lc && rc && lc->intValue() != rc->intValue() ) { + return false; + } + } + + return typesPolyCompatible( l->base.get(), r->base.get() ); + } else if ( type_index(typeid(ast::FunctionType)) == lid ) { + ast::FunctionType const * l = as(lhs); + ast::FunctionType const * r = as(rhs); + + std::vector> lparams, rparams; + flattenList( l->params, lparams ); + flattenList( r->params, rparams ); + if ( lparams.size() != rparams.size() ) return false; + for ( unsigned i = 0; i < lparams.size(); ++i ) { + if ( !typesPolyCompatible( lparams[i], rparams[i] ) ) return false; + } + + std::vector> lrets, rrets; + flattenList( l->returns, lrets ); + flattenList( r->returns, rrets ); + if ( lrets.size() != rrets.size() ) return false; + for ( unsigned i = 0; i < lrets.size(); ++i ) { + if ( !typesPolyCompatible( lrets[i], rrets[i] ) ) return false; + } + return true; + } else if ( type_index(typeid(ast::StructInstType)) == lid ) { + ast::StructInstType const * l = as(lhs); + ast::StructInstType const * r = as(rhs); + + if ( l->name != r->name ) return false; + return paramListsPolyCompatible( l->params, r->params ); + } else if ( type_index(typeid(ast::UnionInstType)) == lid ) { + ast::UnionInstType const * l = as(lhs); + ast::UnionInstType const * r = as(rhs); + + if ( l->name != r->name ) return false; + return paramListsPolyCompatible( l->params, r->params ); + } else if ( type_index(typeid(ast::EnumInstType)) == lid ) { + ast::EnumInstType const * l = as(lhs); + ast::EnumInstType const * r = as(rhs); + + return l->name == r->name; + } else if ( type_index(typeid(ast::TraitInstType)) == lid ) { + ast::TraitInstType const * l = as(lhs); + ast::TraitInstType const * r = as(rhs); + + return l->name == r->name; + } else if ( type_index(typeid(ast::TupleType)) == lid ) { + ast::TupleType const * l = as(lhs); + ast::TupleType const * r = as(rhs); + + std::vector> ltypes, rtypes; + flattenList( l->types, ( ltypes ) ); + flattenList( r->types, ( rtypes ) ); + if ( ltypes.size() != rtypes.size() ) return false; + + for ( unsigned i = 0 ; i < ltypes.size() ; ++i ) { + if ( !typesPolyCompatible( ltypes[i], rtypes[i] ) ) return false; + } + return true; + // The remaining types (VoidType, VarArgsType, ZeroType & OneType) + // have no variation so will always be equal. + } else { + return true; + } +} + namespace { // temporary hack to avoid re-implementing anything related to TyVarMap Index: src/GenPoly/GenPoly.h =================================================================== --- src/GenPoly/GenPoly.h (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/GenPoly/GenPoly.h (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:22:57 2017 -// Update Count : 7 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Aug 19 16:03:00 2022 +// Update Count : 8 // @@ -27,5 +27,7 @@ namespace GenPoly { + // TODO Via some tricks this works for ast::TypeDecl::Data as well. typedef ErasableScopedMap< std::string, TypeDecl::Data > TyVarMap; + /// Replaces a TypeInstType by its referrent in the environment, if applicable Type* replaceTypeInst( Type* type, const TypeSubstitution* env ); @@ -41,4 +43,5 @@ /// returns dynamic-layout type if is dynamic-layout type in tyVars, NULL otherwise; will look up substitution in env if provided ReferenceToType *isDynType( Type *type, const TyVarMap &tyVars, const TypeSubstitution *env = 0 ); + const ast::BaseInstType *isDynType( const ast::Type *type, const TyVarMap &tyVars, const ast::TypeSubstitution *typeSubs = 0 ); /// true iff function has dynamic-layout return type under the given type variable map @@ -83,4 +86,5 @@ /// true iff types are structurally identical, where TypeInstType's match any type. bool typesPolyCompatible( Type *aty, Type *bty ); + bool typesPolyCompatible( ast::Type const * lhs, ast::Type const * rhs ); /// true if arg requires boxing given exprTyVars Index: src/GenPoly/InstantiateGeneric.h =================================================================== --- src/GenPoly/InstantiateGeneric.h (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/GenPoly/InstantiateGeneric.h (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -19,10 +19,15 @@ class Declaration; +namespace ast { + class TranslationUnit; +} namespace GenPoly { - /// Replaces all generic types that have static layout with concrete instantiations. - /// Types with concrete values for otype parameters will be template-expanded, while - /// dtype and ftype parameters will be replaced by the appropriate void type. - void instantiateGeneric( std::list< Declaration* > &translationUnit ); +/// Replaces all generic types that have static layout with concrete +/// instantiations. Types with concrete values for otype parameters will be +/// template-expanded, while dtype and ftype parameters will be replaced by +/// the appropriate void type. +void instantiateGeneric( std::list< Declaration* > &translationUnit ); +void instantiateGeneric( ast::TranslationUnit & translationUnit ); } // namespace GenPoly Index: src/GenPoly/ScrubTyVars.cc =================================================================== --- src/GenPoly/ScrubTyVars.cc (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/GenPoly/ScrubTyVars.cc (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -9,14 +9,16 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Mar 16 15:44:27 2017 -// Update Count : 3 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Aug 19 16:10:00 2022 +// Update Count : 4 // #include // for pair +#include "AST/Pass.hpp" #include "GenPoly.h" // for mangleType, TyVarMap, alignof... #include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::const_it... #include "ScrubTyVars.h" +#include "SymTab/Mangler.h" // for mangle, typeMode #include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Typ... #include "SynTree/Expression.h" // for Expression (ptr only), NameExpr @@ -112,4 +114,162 @@ return pointer; } + +namespace { + +enum class ScrubMode { + FromMap, + DynamicFromMap, + All, +}; + +struct ScrubTypeVars : + public ast::WithGuards, + public ast::WithShortCircuiting, + public ast::WithVisitorRef { + + ScrubTypeVars( ScrubMode m, TyVarMap const * tv ) : + mode ( m ), typeVars( tv ) {} + + void previsit( ast::TypeInstType const * ) { visit_children = false; } + void previsit( ast::StructInstType const * ) { visit_children = false; } + void previsit( ast::UnionInstType const * ) { visit_children = false; } + void previsit( ast::SizeofExpr const * expr ) { primeBaseScrub( expr->type ); } + void previsit( ast::AlignofExpr const * expr ) { primeBaseScrub( expr->type ); } + void previsit( ast::PointerType const * type ) { primeBaseScrub( type->base ); } + + ast::Type const * postvisit( ast::TypeInstType const * type ); + ast::Type const * postvisit( ast::StructInstType const * type ); + ast::Type const * postvisit( ast::UnionInstType const * type ); + ast::Expr const * postvisit( ast::SizeofExpr const * expr ); + ast::Expr const * postvisit( ast::AlignofExpr const * expr ); + ast::Type const * postvisit( ast::PointerType const * type ); + +private: + ScrubMode const mode; + /// Type varriables to scrub. + TyVarMap const * const typeVars; + /// Value cached by primeBaseScrub. + ast::Type const * dynType = nullptr; + + /// Returns the type if it should be scrubbed, nullptr otherwise. + ast::Type const * shouldScrub( ast::Type const * type ) { + switch ( mode ) { + case ScrubMode::FromMap: + return isPolyType( type, *typeVars ); + case ScrubMode::DynamicFromMap: + return isDynType( type, *typeVars ); + case ScrubMode::All: + return isPolyType( type ); + default: + assertf( false, "Invalid ScrubMode in shouldScrub." ); + throw; + } + } + + void primeBaseScrub( ast::Type const * type ) { + // Need to determine whether type needs to be scrubbed to + // determine whether automatic recursion is necessary. + if ( ast::Type const * t = shouldScrub( type ) ) { + visit_children = false; + GuardValue( dynType ) = t; + } + } + + ast::Type const * postvisitAggregateType( + ast::BaseInstType const * type ) { + if ( !shouldScrub( type ) ) return type; + return new ast::PointerType( new ast::VoidType( type->qualifiers ) ); + } +}; + +ast::Type const * ScrubTypeVars::postvisit( ast::TypeInstType const * type ) { + // This implies that mode == ScrubMode::All. + if ( !typeVars ) { + if ( ast::TypeDecl::Ftype == type->kind ) { + return new ast::PointerType( + new ast::FunctionType( ast::FixedArgs ) ); + } else { + return new ast::PointerType( + new ast::VoidType( type->qualifiers ) ); + } + } + + auto typeVar = typeVars->find( type->name ); + if ( typeVar == typeVars->end() ) { + return type; + } + + switch ( typeVar->second.kind ) { + case ast::TypeDecl::Dtype: + case ast::TypeDecl::Ttype: + return new ast::PointerType( + new ast::VoidType( type->qualifiers ) ); + case ast::TypeDecl::Ftype: + return new ast::PointerType( + new ast::FunctionType( ast::VariableArgs ) ); + default: + assertf( false, + "Unhandled type variable kind: %d", typeVar->second.kind ); + throw; // Just in case the assert is removed, stop here. + } +} + +ast::Type const * ScrubTypeVars::postvisit( ast::StructInstType const * type ) { + return postvisitAggregateType( type ); +} + +ast::Type const * ScrubTypeVars::postvisit( ast::UnionInstType const * type ) { + return postvisitAggregateType( type ); +} + +ast::Expr const * ScrubTypeVars::postvisit( ast::SizeofExpr const * expr ) { + // sizeof( T ) becomes the _sizeof_T parameter. + if ( dynType ) { + return new ast::NameExpr( expr->location, + sizeofName( Mangle::mangle( dynType, Mangle::typeMode() ) ) ); + } else { + return expr; + } +} + +ast::Expr const * ScrubTypeVars::postvisit( ast::AlignofExpr const * expr ) { + // alignof( T ) becomes the _alignof_T parameter. + if ( dynType ) { + return new ast::NameExpr( expr->location, + alignofName( Mangle::mangle( dynType, Mangle::typeMode() ) ) ); + } else { + return expr; + } +} + +ast::Type const * ScrubTypeVars::postvisit( ast::PointerType const * type ) { + if ( dynType ) { + ast::Type * ret = ast::mutate( dynType->accept( *visitor ) ); + ret->qualifiers |= type->qualifiers; + return ret; + } else { + return type; + } +} + +const ast::Node * scrubTypeVarsBase( + const ast::Node * target, + ScrubMode mode, const TyVarMap * typeVars ) { + if ( ScrubMode::All == mode ) { + assert( nullptr == typeVars ); + } else { + assert( nullptr != typeVars ); + } + ast::Pass visitor( mode, typeVars ); + return target->accept( visitor ); +} + +} // namespace + +template<> +ast::Node const * scrubAllTypeVars( const ast::Node * target ) { + return scrubTypeVarsBase( target, ScrubMode::All, nullptr ); +} + } // namespace GenPoly Index: src/GenPoly/ScrubTyVars.h =================================================================== --- src/GenPoly/ScrubTyVars.h (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/GenPoly/ScrubTyVars.h (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:21:47 2017 -// Update Count : 2 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Aug 19 14:14:00 2022 +// Update Count : 3 // @@ -18,4 +18,5 @@ #include // for assert +#include "AST/Fwd.hpp" // for Node #include "Common/PassVisitor.h" #include "GenPoly.h" // for TyVarMap, isPolyType, isDynType @@ -108,4 +109,14 @@ } +/// For all polymorphic types, replaces generic types, with the appropriate +/// void type, and sizeof/alignof expressions with the proper variable. +template +node_t const * scrubAllTypeVars( node_t const * target ) { + return strict_dynamic_cast( scrubAllTypeVars( target ) ); +} + +template<> +ast::Node const * scrubAllTypeVars( const ast::Node * target ); + } // namespace GenPoly Index: src/GenPoly/module.mk =================================================================== --- src/GenPoly/module.mk (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/GenPoly/module.mk (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -27,4 +27,5 @@ GenPoly/FindFunction.cc \ GenPoly/FindFunction.h \ + GenPoly/InstantiateGenericNew.cpp \ GenPoly/InstantiateGeneric.cc \ GenPoly/InstantiateGeneric.h \ Index: src/Virtual/ExpandCasts.cc =================================================================== --- src/Virtual/ExpandCasts.cc (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/Virtual/ExpandCasts.cc (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -362,4 +362,5 @@ } +/// Copy newType, but give the copy the params of the oldType. ast::StructInstType * polyCopy( ast::StructInstType const * oldType, Index: src/main.cc =================================================================== --- src/main.cc (revision ed9a1ae9fd2dfee0f1af522273e707b0ae29b439) +++ src/main.cc (revision 3606fe4fcb57ddc626e19a892c71e8e351bda641) @@ -453,4 +453,6 @@ PASS( "Virtual Expand Casts", Virtual::expandCasts( transUnit ) ); + PASS( "Instantiate Generics", GenPoly::instantiateGeneric( transUnit ) ); + translationUnit = convert( move( transUnit ) ); } else { @@ -535,7 +537,8 @@ PASS( "Virtual Expand Casts", Virtual::expandCasts( translationUnit ) ); // Must come after translateEHM + + PASS( "Instantiate Generics", GenPoly::instantiateGeneric( translationUnit ) ); } - PASS( "Instantiate Generics", GenPoly::instantiateGeneric( translationUnit ) ); if ( genericsp ) { dump( translationUnit );