Index: src/AST/Pass.impl.hpp =================================================================== --- src/AST/Pass.impl.hpp (revision b336af9cd762a8814b9d7682b1d48071815407d1) +++ src/AST/Pass.impl.hpp (revision c6711120c5f8e17f44aec4ae077a07f86e65a178) @@ -19,4 +19,6 @@ #include #include + +#include "AST/TypeSubstitution.hpp" #define VISIT_START( node ) \ Index: src/AST/TypeSubstitution.cpp =================================================================== --- src/AST/TypeSubstitution.cpp (revision c6711120c5f8e17f44aec4ae077a07f86e65a178) +++ src/AST/TypeSubstitution.cpp (revision c6711120c5f8e17f44aec4ae077a07f86e65a178) @@ -0,0 +1,221 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// TypeSubstitution.cc -- +// +// 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:54:35 2017 +// Update Count : 4 +// + +#include "Type.hpp" // for TypeInstType, Type, StructInstType, UnionInstType +#include "TypeSubstitution.hpp" + +namespace ast { + +TypeSubstitution::TypeSubstitution() { +} + +TypeSubstitution::TypeSubstitution( const TypeSubstitution &other ) : Node() { + initialize( other, *this ); +} + +TypeSubstitution::~TypeSubstitution() { + for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) { + delete( i->second ); + } + for ( VarEnvType::iterator i = varEnv.begin(); i != varEnv.end(); ++i ) { + delete( i->second ); + } +} + +TypeSubstitution &TypeSubstitution::operator=( const TypeSubstitution &other ) { + if ( this == &other ) return *this; + initialize( other, *this ); + return *this; +} + +void TypeSubstitution::initialize( const TypeSubstitution &src, TypeSubstitution &dest ) { + dest.typeEnv.clear(); + dest.varEnv.clear(); + dest.add( src ); +} + +void TypeSubstitution::add( const TypeSubstitution &other ) { + for ( TypeEnvType::const_iterator i = other.typeEnv.begin(); i != other.typeEnv.end(); ++i ) { + typeEnv[ i->first ] = i->second; + } // for + for ( VarEnvType::const_iterator i = other.varEnv.begin(); i != other.varEnv.end(); ++i ) { + varEnv[ i->first ] = i->second; + } // for +} + +void TypeSubstitution::add( std::string formalType, const Type *actualType ) { + typeEnv[ formalType ] = actualType; +} + +void TypeSubstitution::remove( std::string formalType ) { + TypeEnvType::iterator i = typeEnv.find( formalType ); + if ( i != typeEnv.end() ) { + typeEnv.erase( formalType ); + } // if +} + +const Type *TypeSubstitution::lookup( std::string formalType ) const { + TypeEnvType::const_iterator i = typeEnv.find( formalType ); + + // break on not in substitution set + if ( i == typeEnv.end() ) return 0; + + // attempt to transitively follow TypeInstType links. + while ( const TypeInstType *actualType = i->second.as()) { + const std::string& typeName = actualType->name; + + // break cycles in the transitive follow + if ( formalType == typeName ) break; + + // Look for the type this maps to, returning previous mapping if none-such + i = typeEnv.find( typeName ); + if ( i == typeEnv.end() ) return actualType; + } + + // return type from substitution set + return i->second; +} + +bool TypeSubstitution::empty() const { + return typeEnv.empty() && varEnv.empty(); +} + +namespace { + struct EnvTrimmer { + ptr env; + TypeSubstitution * newEnv; + EnvTrimmer( const TypeSubstitution * env, TypeSubstitution * newEnv ) : env( env ), newEnv( newEnv ){} + void previsit( TypeDecl * tyDecl ) { + // transfer known bindings for seen type variables + if ( const 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( const Expr * expr, const TypeSubstitution * env ) { + if ( env ) { + TypeSubstitution * newEnv = new TypeSubstitution(); +#if TIME_TO_CONVERT_PASSES + Pass trimmer( env, newEnv ); + expr->accept( trimmer ); +#else + (void)expr; + (void)env; +#endif + return newEnv; + } + return nullptr; +} + +void TypeSubstitution::normalize() { +#if TIME_TO_CONVERT_PASSES + PassVisitor sub( *this, true ); + do { + sub.pass.subCount = 0; + sub.pass.freeOnly = true; + for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) { + i->second = i->second->acceptMutator( sub ); + } + } while ( sub.pass.subCount ); +#endif +} + +#if TIME_TO_CONVERT_PASSES + +Type * TypeSubstitution::Substituter::postmutate( TypeInstType *inst ) { + BoundVarsType::const_iterator bound = boundVars.find( inst->name ); + if ( bound != boundVars.end() ) return inst; + + TypeEnvType::const_iterator i = sub.typeEnv.find( inst->name ); + if ( i == sub.typeEnv.end() ) { + return inst; + } else { + // 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 = i->second.as() ) { + if ( inst->name == replacement->name ) { + return inst; + } + } + // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl; + subCount++; + Type * newtype = i->second->clone(); + newtype->get_qualifiers() |= inst->get_qualifiers(); + delete inst; + // 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 { + subCount++; + delete nameExpr; + return i->second->clone(); + } // if +} + +void TypeSubstitution::Substituter::premutate( Type * type ) { + GuardValue( boundVars ); + // bind type variables from forall-qualifiers + if ( freeOnly ) { + for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) { + boundVars.insert( (*tyvar)->name ); + } // for + } // if +} + +template< typename TypeClass > +void TypeSubstitution::Substituter::handleAggregateType( TypeClass * type ) { + GuardValue( boundVars ); + // bind type variables from forall-qualifiers + if ( freeOnly ) { + 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->parameters.empty() ) { + for ( std::list< TypeDecl* >::const_iterator tyvar = baseParameters->begin(); tyvar != baseParameters->end(); ++tyvar ) { + boundVars.insert( (*tyvar)->name ); + } // for + } // if + } // if +} + +void TypeSubstitution::Substituter::premutate( StructInstType * aggregateUseType ) { + handleAggregateType( aggregateUseType ); +} + +void TypeSubstitution::Substituter::premutate( UnionInstType *aggregateUseType ) { + handleAggregateType( aggregateUseType ); +} + +#endif + +} // namespace ast + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/TypeSubstitution.hpp =================================================================== --- src/AST/TypeSubstitution.hpp (revision c6711120c5f8e17f44aec4ae077a07f86e65a178) +++ src/AST/TypeSubstitution.hpp (revision c6711120c5f8e17f44aec4ae077a07f86e65a178) @@ -0,0 +1,205 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// TypeSubstitution.h -- +// +// Author : Richard C. Bilson +// Created On : Mon May 18 07:44:20 2015 +// Last Modified By : Peter A. Buhr +// Last Modified On : Tue Apr 30 22:52:47 2019 +// Update Count : 9 +// + +#pragma once + +#include // for assert +#include // for list<>::iterator, _List_iterator +#include +#include +#include // for string, operator!= +#include // for pair + +#include "Fwd.hpp" // for UniqueId +#include "ParseNode.hpp" +#include "Type.hpp" // for ptr +#include "Common/SemanticError.h" // for SemanticError +#include "Visitor.hpp" +#include "Decl.hpp" +#include "Expr.hpp" + +namespace ast { + +class TypeSubstitution : public Node { + public: + TypeSubstitution(); + template< typename FormalIterator, typename ActualIterator > + TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ); + TypeSubstitution( const TypeSubstitution &other ); + virtual ~TypeSubstitution(); + + TypeSubstitution &operator=( const TypeSubstitution &other ); + + template< typename SynTreeClass > int apply( SynTreeClass *&input ) const; + template< typename SynTreeClass > int applyFree( SynTreeClass *&input ) const; + + void add( std::string formalType, const Type *actualType ); + void add( const TypeSubstitution &other ); + void remove( std::string formalType ); + const Type *lookup( std::string formalType ) const; + bool empty() const; + + template< typename FormalIterator, typename ActualIterator > + void add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ); + + /// create a new TypeSubstitution using bindings from env containing all of the type variables in expr + static TypeSubstitution * newFromExpr( const Expr * expr, const TypeSubstitution * env ); + + void normalize(); + + const TypeSubstitution * accept( Visitor & v ) const override { return v.visit( this ); } + + TypeSubstitution * clone() const override { return new TypeSubstitution( *this ); } + + private: + + // Mutator that performs the substitution + struct Substituter; + + // TODO: worry about traversing into a forall-qualified function type or type decl with assertions + + void initialize( const TypeSubstitution &src, TypeSubstitution &dest ); + + template + friend class Pass; + + typedef std::unordered_map< std::string, ptr > TypeEnvType; + typedef std::unordered_map< std::string, ptr > VarEnvType; + TypeEnvType typeEnv; + VarEnvType varEnv; + + public: + // has to come after declaration of typeEnv + auto begin() -> decltype( typeEnv.begin() ) { return typeEnv.begin(); } + auto end() -> decltype( typeEnv. end() ) { return typeEnv. end(); } + auto begin() const -> decltype( typeEnv.begin() ) { return typeEnv.begin(); } + auto end() const -> decltype( typeEnv. end() ) { return typeEnv. end(); } +}; + +template< typename FormalIterator, typename ActualIterator > +void TypeSubstitution::add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) { + // FormalIterator points to a TypeDecl + // ActualIterator points to a Type + FormalIterator formalIt = formalBegin; + ActualIterator actualIt = actualBegin; + for ( ; formalIt != formalEnd; ++formalIt, ++actualIt ) { + if ( const TypeDecl *formal = formalIt->template as() ) { + if ( const TypeExpr *actual = actualIt->template as() ) { + if ( formal->name != "" ) { + typeEnv[ formal->name ] = actual->type; + } // if + } else { + SemanticError( formal, toString( "Attempt to provide non-type parameter: ", toString( *actualIt ).c_str(), " for type parameter " ) ); + } // if + } else { + // TODO: type check the formal and actual parameters + if ( (*formalIt)->name != "" ) { + varEnv[ (*formalIt)->name ] = *actualIt; + } // if + } // if + } // for +} + +template< typename FormalIterator, typename ActualIterator > +TypeSubstitution::TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) { + add( formalBegin, formalEnd, actualBegin ); +} + +} // namespace ast + +// include needs to happen after TypeSubstitution is defined so that both TypeSubstitution and +// PassVisitor are defined before PassVisitor implementation accesses TypeSubstitution internals. +#include "Pass.hpp" + +namespace ast { + +// definitition must happen after PassVisitor is included so that WithGuards can be used +struct TypeSubstitution::Substituter : public WithGuards, public WithVisitorRef { + + Substituter( const TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {} + +#if TIME_TO_CONVERT_PASSES + + Type * postmutate( TypeInstType * aggregateUseType ); + Expression * postmutate( NameExpr * nameExpr ); + + /// Records type variable bindings from forall-statements + void premutate( Type * type ); + /// Records type variable bindings from forall-statements and instantiations of generic types + template< typename TypeClass > void handleAggregateType( TypeClass * type ); + + void premutate( StructInstType * aggregateUseType ); + void premutate( UnionInstType * aggregateUseType ); + +#endif + + const TypeSubstitution & sub; + int subCount = 0; + bool freeOnly; + typedef std::unordered_set< std::string > BoundVarsType; + BoundVarsType boundVars; + +}; + +template< typename SynTreeClass > +int TypeSubstitution::apply( SynTreeClass *&input ) const { + assert( input ); + Pass sub( *this, false ); + input = dynamic_cast< SynTreeClass * >( input->acceptMutator( sub ) ); + assert( input ); +/// std::cerr << "substitution result is: "; +/// newType->print( std::cerr ); +/// std::cerr << std::endl; + return sub.pass.subCount; +} + +template< typename SynTreeClass > +int TypeSubstitution::applyFree( SynTreeClass *&input ) const { + assert( input ); + Pass sub( *this, true ); + input = dynamic_cast< SynTreeClass * >( input->acceptMutator( sub ) ); + assert( input ); +/// std::cerr << "substitution result is: "; +/// newType->print( std::cerr ); +/// std::cerr << std::endl; + return sub.pass.subCount; +} + +/// Instantiate each member of the context given the actual parameters specified, and store the +/// instantiations for use by the indexer +template< typename FormalIterator, typename ActualIterator, typename MemberIterator, typename OutputIterator > +void applySubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actual, MemberIterator memberBegin, MemberIterator memberEnd, OutputIterator out ) { + TypeSubstitution sub = TypeSubstitution( formalBegin, formalEnd, actual ); + for ( auto i = memberBegin; i != memberEnd; ++i ) { + sub.apply( *i ); + *out++ = *i; + } // for +} + +//================================================================================================= +/// This disgusting and giant piece of boiler-plate is here to solve a cyclic dependency +/// remove only if there is a better solution +/// The problem is that ast::ptr< ... > uses increment/decrement which won't work well with +/// forward declarations +inline void increment( const class TypeSubstitution * node, Node::ref_type ref ) { node->increment(ref); } +inline void decrement( const class TypeSubstitution * node, Node::ref_type ref ) { node->decrement(ref); } + +} // namespace ast + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: //