Changeset 3606fe4 for src/GenPoly

Timestamp:

Sep 14, 2022, 9:46:19 AM (2 years ago)

Author:

Andrew Beach <ajbeach@…>

Branches:

ADT, ast-experimental, master, pthread-emulation

Children:

1c0657a

Parents:

fc96890

Message:

Translated Instantiate Generic to the new AST. This includes various utilities and some assorted clean-up.

Location:

src/GenPoly

Files:

• GenPoly.cc (modified) (7 diffs)
• GenPoly.h (modified) (4 diffs)
• InstantiateGeneric.h (modified) (1 diff)
• ScrubTyVars.cc (modified) (2 diffs)
• ScrubTyVars.h (modified) (3 diffs)
• module.mk (modified) (1 diff)

src/GenPoly/GenPoly.cc

@@ -9 +9 @@
 // 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 +83 @@
                 }
 
+                bool hasDynParams( const std::vector<ast::ptr<ast::Expr>> & params, const TyVarMap &tyVars, const ast::TypeSubstitution *typeSubs ) {
+                        for ( ast::ptr<ast::Expr> const & param : params ) {
+                                auto paramType = param.as<ast::TypeExpr>();
+                                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 +209 @@
                 }
                 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<ast::TypeInstType const *>( type ) ) {
+                        auto var = tyVars.find( inst->name );
+                        if ( var != tyVars.end() && var->second.isComplete ) {
+                                return inst;
+                        }
+                } else if ( auto inst = dynamic_cast<ast::StructInstType const *>( type ) ) {
+                        if ( hasDynParams( inst->params, tyVars, typeSubs ) ) {
+                                return inst;
+                        }
+                } else if ( auto inst = dynamic_cast<ast::UnionInstType const *>( type ) ) {
+                        if ( hasDynParams( inst->params, tyVars, typeSubs ) ) {
+                                return inst;
+                        }
+                }
+                return nullptr;
         }
 
@@ -378 +409 @@
                 inline D* as( B* p ) { return reinterpret_cast<D*>(p); }
 
+                template<typename D, typename B>
+                inline D const * as( B const * p ) {
+                        return reinterpret_cast<D const *>( p );
+                }
+
                 /// Flattens a declaration list
                 template<typename Output>
@@ -391 +427 @@
                         for ( Type* ty : src ) {
                                 ResolvExpr::flatten( ty, out );
+                        }
+                }
+
+                void flattenList( vector<ast::ptr<ast::Type>> const & src,
+                                vector<ast::ptr<ast::Type>> & out ) {
+                        for ( auto const & type : src ) {
+                                ResolvExpr::flatten( type, out );
                         }
                 }
@@ -409 +452 @@
                                 // 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 paramListsPolyCompatible(
+                                std::vector<ast::ptr<ast::Expr>> const & lparams,
+                                std::vector<ast::ptr<ast::Expr>> 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<ast::TypeExpr>();
+                                assertf( lexpr, "Aggregate parameters should be type expressions" );
+                                ast::TypeExpr const * rexpr = rparam->as<ast::TypeExpr>();
+                                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<VoidType>( lexpr->type() ) || is<VoidType>( bparam->get_type() ) ) continue;
+                                if ( !typesPolyCompatible( lexpr->type, rexpr->type ) ) {
+                                        return false;
+                                }
                         }
 
@@ -505 +573 @@
         }
 
+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<ast::BasicType>(lhs)->kind == as<ast::BasicType>(rhs)->kind;
+        } else if ( type_index(typeid(ast::PointerType)) == lid ) {
+                ast::PointerType const * l = as<ast::PointerType>(lhs);
+                ast::PointerType const * r = as<ast::PointerType>(rhs);
+
+                // void pointers should match any other pointer type.
+                return is<ast::VoidType>( l->base.get() )
+                        || is<ast::VoidType>( r->base.get() )
+                        || typesPolyCompatible( l->base.get(), r->base.get() );
+        } else if ( type_index(typeid(ast::ReferenceType)) == lid ) {
+                ast::ReferenceType const * l = as<ast::ReferenceType>(lhs);
+                ast::ReferenceType const * r = as<ast::ReferenceType>(rhs);
+
+                // void references should match any other reference type.
+                return is<ast::VoidType>( l->base.get() )
+                        || is<ast::VoidType>( r->base.get() )
+                        || typesPolyCompatible( l->base.get(), r->base.get() );
+        } else if ( type_index(typeid(ast::ArrayType)) == lid ) {
+                ast::ArrayType const * l = as<ast::ArrayType>(lhs);
+                ast::ArrayType const * r = as<ast::ArrayType>(rhs);
+
+                if ( l->isVarLen ) {
+                        if ( !r->isVarLen ) return false;
+                } else {
+                        if ( r->isVarLen ) return false;
+
+                        auto lc = l->dimension.as<ast::ConstantExpr>();
+                        auto rc = r->dimension.as<ast::ConstantExpr>();
+                        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<ast::FunctionType>(lhs);
+                ast::FunctionType const * r = as<ast::FunctionType>(rhs);
+
+                std::vector<ast::ptr<ast::Type>> 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<ast::ptr<ast::Type>> 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<ast::StructInstType>(lhs);
+                ast::StructInstType const * r = as<ast::StructInstType>(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<ast::UnionInstType>(lhs);
+                ast::UnionInstType const * r = as<ast::UnionInstType>(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<ast::EnumInstType>(lhs);
+                ast::EnumInstType const * r = as<ast::EnumInstType>(rhs);
+
+                return l->name == r->name;
+        } else if ( type_index(typeid(ast::TraitInstType)) == lid ) {
+                ast::TraitInstType const * l = as<ast::TraitInstType>(lhs);
+                ast::TraitInstType const * r = as<ast::TraitInstType>(rhs);
+
+                return l->name == r->name;
+        } else if ( type_index(typeid(ast::TupleType)) == lid ) {
+                ast::TupleType const * l = as<ast::TupleType>(lhs);
+                ast::TupleType const * r = as<ast::TupleType>(rhs);
+
+                std::vector<ast::ptr<ast::Type>> 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

src/GenPoly/GenPoly.h

@@ -9 +9 @@
 // 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 +27 @@
 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 +43 @@
         /// 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 +86 @@
         /// 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

src/GenPoly/InstantiateGeneric.h

@@ -19 +19 @@
 
 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
 

src/GenPoly/ScrubTyVars.cc

@@ -9 +9 @@
 // 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 <utility>                      // 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 +114 @@
                 return pointer;
         }
+
+namespace {
+
+enum class ScrubMode {
+        FromMap,
+        DynamicFromMap,
+        All,
+};
+
+struct ScrubTypeVars :
+        public ast::WithGuards,
+        public ast::WithShortCircuiting,
+        public ast::WithVisitorRef<ScrubTypeVars> {
+
+        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<ScrubTypeVars> visitor( mode, typeVars );
+        return target->accept( visitor );
+}
+
+} // namespace
+
+template<>
+ast::Node const * scrubAllTypeVars<ast::Node>( const ast::Node * target ) {
+        return scrubTypeVarsBase( target, ScrubMode::All, nullptr );
+}
+
 } // namespace GenPoly
 

src/GenPoly/ScrubTyVars.h

@@ -9 +9 @@
 // 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 +18 @@
 #include <cassert>            // for assert
 
+#include "AST/Fwd.hpp"        // for Node
 #include "Common/PassVisitor.h"
 #include "GenPoly.h"          // for TyVarMap, isPolyType, isDynType
@@ -108 +109 @@
         }
 
+/// For all polymorphic types, replaces generic types, with the appropriate
+/// void type, and sizeof/alignof expressions with the proper variable.
+template<typename node_t>
+node_t const * scrubAllTypeVars( node_t const * target ) {
+        return strict_dynamic_cast<node_t const *>( scrubAllTypeVars<ast::Node>( target ) );
+}
+
+template<>
+ast::Node const * scrubAllTypeVars<ast::Node>( const ast::Node * target );
+
 } // namespace GenPoly
 

src/GenPoly/module.mk

@@ -27 +27 @@
         GenPoly/FindFunction.cc \
         GenPoly/FindFunction.h \
+        GenPoly/InstantiateGenericNew.cpp \
         GenPoly/InstantiateGeneric.cc \
         GenPoly/InstantiateGeneric.h \