Changeset 90152a4 for src/SynTree/TypeSubstitution.cc

Timestamp:

Aug 27, 2018, 4:40:34 PM (7 years ago)

Author:

Rob Schluntz <rschlunt@…>

Branches:

ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

b7c89aa

Parents:

f9feab8 (diff), 305581d (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.

Message:

Merge branch 'master' into cleanup-dtors

File:

• src/SynTree/TypeSubstitution.cc (modified) (2 diffs)

src/SynTree/TypeSubstitution.cc

@@ -106 +106 @@
 }
 
+namespace {
+        struct EnvTrimmer {
+                TypeSubstitution * env, * newEnv;
+                EnvTrimmer( TypeSubstitution * env, TypeSubstitution * newEnv ) : env( env ), newEnv( newEnv ){}
+                void previsit( TypeDecl * tyDecl ) {
+                        // transfer known bindings for seen type variables
+                        if ( Type * t = env->lookup( tyDecl->name ) ) {
+                                newEnv->add( tyDecl->name, t );
+                        }
+                }
+        };
+} // namespace
+
+/// reduce environment to just the parts that are referenced in a given expression
+TypeSubstitution * TypeSubstitution::newFromExpr( Expression * expr, TypeSubstitution * env ) {
+        if ( env ) {
+                TypeSubstitution * newEnv = new TypeSubstitution();
+                PassVisitor<EnvTrimmer> trimmer( env, newEnv );
+                expr->accept( trimmer );
+                return newEnv;
+        }
+        return nullptr;
+}
+
 void TypeSubstitution::normalize() {
+        PassVisitor<Substituter> sub( *this, true );
         do {
-                subCount = 0;
-                freeOnly = true;
+                sub.pass.subCount = 0;
+                sub.pass.freeOnly = true;
                 for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) {
-                        i->second = i->second->acceptMutator( *this );
+                        i->second = i->second->acceptMutator( sub );
                 }
-        } while ( subCount );
-}
-
-Type * TypeSubstitution::mutate( TypeInstType *inst ) {
-        BoundVarsType::const_iterator bound = boundVars.find( inst->get_name() );
+        } while ( sub.pass.subCount );
+}
+
+Type * TypeSubstitution::Substituter::postmutate( TypeInstType *inst ) {
+        BoundVarsType::const_iterator bound = boundVars.find( inst->name );
         if ( bound != boundVars.end() ) return inst;
 
-        TypeEnvType::const_iterator i = typeEnv.find( inst->get_name() );
-        if ( i == typeEnv.end() ) {
+        TypeEnvType::const_iterator i = sub.typeEnv.find( inst->get_name() );
+        if ( i == sub.typeEnv.end() ) {
                 return inst;
         } else {
-///         std::cout << "found " << inst->get_name() << ", replacing with ";
-///         i->second->print( std::cout );
-///         std::cout << std::endl;
+                // cut off infinite loop for the case where a type is bound to itself.
+                // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here.
+                // TODO: investigate preventing type variables from being bound to themselves in the first place.
+                if ( TypeInstType * replacement = dynamic_cast< TypeInstType * >( i->second ) ) {
+                        if ( inst->name == replacement->name ) {
+                                return inst;
+                        }
+                }
+                // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl;
                 subCount++;
-                Type *newtype = i->second->clone();
+                Type * newtype = i->second->clone();
                 newtype->get_qualifiers() |= inst->get_qualifiers();
                 delete inst;
-                return newtype;
-        } // if
-}
-
-Expression * TypeSubstitution::mutate( NameExpr *nameExpr ) {
-        VarEnvType::const_iterator i = varEnv.find( nameExpr->get_name() );
-        if ( i == varEnv.end() ) {
+                // Note: need to recursively apply substitution to the new type because normalize does not substitute bound vars, but bound vars must be substituted when not in freeOnly mode.
+                return newtype->acceptMutator( *visitor );
+        } // if
+}
+
+Expression * TypeSubstitution::Substituter::postmutate( NameExpr * nameExpr ) {
+        VarEnvType::const_iterator i = sub.varEnv.find( nameExpr->name );
+        if ( i == sub.varEnv.end() ) {
                 return nameExpr;
         } else {
@@ -146 +178 @@
 }
 
-template< typename TypeClass >
-Type *TypeSubstitution::handleType( TypeClass *type ) {
-        ValueGuard<BoundVarsType> oldBoundVars( boundVars );
+void TypeSubstitution::Substituter::premutate( Type * type ) {
+        GuardValue( boundVars );
         // bind type variables from forall-qualifiers
         if ( freeOnly ) {
-                for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
-                        boundVars.insert( (*tyvar )->get_name() );
+                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
+                        boundVars.insert( (*tyvar)->name );
                 } // for
         } // if
-        Type *ret = Mutator::mutate( type );
-        return ret;
 }
 
 template< typename TypeClass >
-Type *TypeSubstitution::handleAggregateType( TypeClass *type ) {
-        ValueGuard<BoundVarsType> oldBoundVars( boundVars );
+void TypeSubstitution::Substituter::handleAggregateType( TypeClass * type ) {
+        GuardValue( boundVars );
         // bind type variables from forall-qualifiers
         if ( freeOnly ) {
-                for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) {
-                        boundVars.insert( (*tyvar )->get_name() );
+                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
+                        boundVars.insert( (*tyvar)->name );
                 } // for
                 // bind type variables from generic type instantiations
                 std::list< TypeDecl* > *baseParameters = type->get_baseParameters();
-                if ( baseParameters && ! type->get_parameters().empty() ) {
+                if ( baseParameters && ! type->parameters.empty() ) {
                         for ( std::list< TypeDecl* >::const_iterator tyvar = baseParameters->begin(); tyvar != baseParameters->end(); ++tyvar ) {
-                                boundVars.insert( (*tyvar)->get_name() );
+                                boundVars.insert( (*tyvar)->name );
                         } // for
                 } // if
         } // if
-        Type *ret = Mutator::mutate( type );
-        return ret;
-}
-
-Type * TypeSubstitution::mutate( VoidType *voidType ) {
-        return handleType( voidType );
-}
-
-Type * TypeSubstitution::mutate( BasicType *basicType ) {
-        return handleType( basicType );
-}
-
-Type * TypeSubstitution::mutate( PointerType *pointerType ) {
-        return handleType( pointerType );
-}
-
-Type * TypeSubstitution::mutate( ArrayType *arrayType ) {
-        return handleType( arrayType );
-}
-
-Type * TypeSubstitution::mutate( FunctionType *functionType ) {
-        return handleType( functionType );
-}
-
-Type * TypeSubstitution::mutate( StructInstType *aggregateUseType ) {
-        return handleAggregateType( aggregateUseType );
-}
-
-Type * TypeSubstitution::mutate( UnionInstType *aggregateUseType ) {
-        return handleAggregateType( aggregateUseType );
-}
-
-Type * TypeSubstitution::mutate( EnumInstType *aggregateUseType ) {
-        return handleType( aggregateUseType );
-}
-
-Type * TypeSubstitution::mutate( TraitInstType *aggregateUseType ) {
-        return handleType( aggregateUseType );
-}
-
-Type * TypeSubstitution::mutate( TupleType *tupleType ) {
-        return handleType( tupleType );
-}
-
-Type * TypeSubstitution::mutate( VarArgsType *varArgsType ) {
-        return handleType( varArgsType );
-}
-
-Type * TypeSubstitution::mutate( ZeroType *zeroType ) {
-        return handleType( zeroType );
-}
-
-Type * TypeSubstitution::mutate( OneType *oneType ) {
-        return handleType( oneType );
+}
+
+void TypeSubstitution::Substituter::premutate( StructInstType * aggregateUseType ) {
+        handleAggregateType( aggregateUseType );
+}
+
+void TypeSubstitution::Substituter::premutate( UnionInstType *aggregateUseType ) {
+        handleAggregateType( aggregateUseType );
 }