source: src/AST/TypeSubstitution.cpp @ 9a19608

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 9a19608 was dafe9e1, checked in by Andrew Beach <ajbeach@…>, 6 years ago

Fixed broken destructor cycles. Cleaned up strict_dynamic_cast.

  • Property mode set to 100644
File size: 6.6 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// TypeSubstitution.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Mon May 18 07:44:20 2015
11// Last Modified By : Andrew Beach
12// Last Modified On : Mon Jun  3 13:26:00 2017
13// Update Count     : 5
14//
15
16#include "Type.hpp"   // for TypeInstType, Type, StructInstType, UnionInstType
17#include "TypeSubstitution.hpp"
18
19namespace ast {
20
21TypeSubstitution::TypeSubstitution() {
22}
23
24TypeSubstitution::TypeSubstitution( const TypeSubstitution &other ) : Node() {
25        initialize( other, *this );
26}
27
28TypeSubstitution::~TypeSubstitution() {}
29
30TypeSubstitution &TypeSubstitution::operator=( const TypeSubstitution &other ) {
31        if ( this == &other ) return *this;
32        initialize( other, *this );
33        return *this;
34}
35
36void TypeSubstitution::initialize( const TypeSubstitution &src, TypeSubstitution &dest ) {
37        dest.typeEnv.clear();
38        dest.varEnv.clear();
39        dest.add( src );
40}
41
42void TypeSubstitution::add( const TypeSubstitution &other ) {
43        for ( TypeEnvType::const_iterator i = other.typeEnv.begin(); i != other.typeEnv.end(); ++i ) {
44                typeEnv[ i->first ] = i->second;
45        } // for
46        for ( VarEnvType::const_iterator i = other.varEnv.begin(); i != other.varEnv.end(); ++i ) {
47                varEnv[ i->first ] = i->second;
48        } // for
49}
50
51void TypeSubstitution::add( std::string formalType, const Type *actualType ) {
52        typeEnv[ formalType ] = actualType;
53}
54
55void TypeSubstitution::addVar( std::string formalExpr, const Expr *actualExpr ) {
56        varEnv[ formalExpr ] = actualExpr;
57}
58
59void TypeSubstitution::remove( std::string formalType ) {
60        TypeEnvType::iterator i = typeEnv.find( formalType );
61        if ( i != typeEnv.end() ) {
62                typeEnv.erase( formalType );
63        } // if
64}
65
66const Type *TypeSubstitution::lookup( std::string formalType ) const {
67        TypeEnvType::const_iterator i = typeEnv.find( formalType );
68
69        // break on not in substitution set
70        if ( i == typeEnv.end() ) return 0;
71
72        // attempt to transitively follow TypeInstType links.
73        while ( const TypeInstType *actualType = i->second.as<TypeInstType>()) {
74                const std::string& typeName = actualType->name;
75
76                // break cycles in the transitive follow
77                if ( formalType == typeName ) break;
78
79                // Look for the type this maps to, returning previous mapping if none-such
80                i = typeEnv.find( typeName );
81                if ( i == typeEnv.end() ) return actualType;
82        }
83
84        // return type from substitution set
85        return i->second;
86}
87
88bool TypeSubstitution::empty() const {
89        return typeEnv.empty() && varEnv.empty();
90}
91
92namespace {
93        struct EnvTrimmer {
94                ptr<TypeSubstitution> env;
95                TypeSubstitution * newEnv;
96                EnvTrimmer( const TypeSubstitution * env, TypeSubstitution * newEnv ) : env( env ), newEnv( newEnv ){}
97                void previsit( TypeDecl * tyDecl ) {
98                        // transfer known bindings for seen type variables
99                        if ( const Type * t = env->lookup( tyDecl->name ) ) {
100                                newEnv->add( tyDecl->name, t );
101                        }
102                }
103        };
104} // namespace
105
106/// reduce environment to just the parts that are referenced in a given expression
107TypeSubstitution * TypeSubstitution::newFromExpr( const Expr * expr, const TypeSubstitution * env ) {
108        if ( env ) {
109                TypeSubstitution * newEnv = new TypeSubstitution();
110#if TIME_TO_CONVERT_PASSES
111                Pass<EnvTrimmer> trimmer( env, newEnv );
112                expr->accept( trimmer );
113#else
114                (void)expr;
115                (void)env;
116#endif
117                return newEnv;
118        }
119        return nullptr;
120}
121
122void TypeSubstitution::normalize() {
123#if TIME_TO_CONVERT_PASSES
124        PassVisitor<Substituter> sub( *this, true );
125        do {
126                sub.pass.subCount = 0;
127                sub.pass.freeOnly = true;
128                for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) {
129                        i->second = i->second->acceptMutator( sub );
130                }
131        } while ( sub.pass.subCount );
132#endif
133}
134
135#if TIME_TO_CONVERT_PASSES
136
137Type * TypeSubstitution::Substituter::postmutate( TypeInstType *inst ) {
138        BoundVarsType::const_iterator bound = boundVars.find( inst->name );
139        if ( bound != boundVars.end() ) return inst;
140
141        TypeEnvType::const_iterator i = sub.typeEnv.find( inst->name );
142        if ( i == sub.typeEnv.end() ) {
143                return inst;
144        } else {
145                // cut off infinite loop for the case where a type is bound to itself.
146                // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here.
147                // TODO: investigate preventing type variables from being bound to themselves in the first place.
148                if ( TypeInstType * replacement = i->second.as<TypeInstType>() ) {
149                        if ( inst->name == replacement->name ) {
150                                return inst;
151                        }
152                }
153                // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl;
154                subCount++;
155                Type * newtype = i->second->clone();
156                newtype->get_qualifiers() |= inst->get_qualifiers();
157                delete inst;
158                // 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.
159                return newtype->acceptMutator( *visitor );
160        } // if
161}
162
163Expression * TypeSubstitution::Substituter::postmutate( NameExpr * nameExpr ) {
164        VarEnvType::const_iterator i = sub.varEnv.find( nameExpr->name );
165        if ( i == sub.varEnv.end() ) {
166                return nameExpr;
167        } else {
168                subCount++;
169                delete nameExpr;
170                return i->second->clone();
171        } // if
172}
173
174void TypeSubstitution::Substituter::premutate( Type * type ) {
175        GuardValue( boundVars );
176        // bind type variables from forall-qualifiers
177        if ( freeOnly ) {
178                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
179                        boundVars.insert( (*tyvar)->name );
180                } // for
181        } // if
182}
183
184template< typename TypeClass >
185void TypeSubstitution::Substituter::handleAggregateType( TypeClass * type ) {
186        GuardValue( boundVars );
187        // bind type variables from forall-qualifiers
188        if ( freeOnly ) {
189                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
190                        boundVars.insert( (*tyvar)->name );
191                } // for
192                // bind type variables from generic type instantiations
193                std::list< TypeDecl* > *baseParameters = type->get_baseParameters();
194                if ( baseParameters && ! type->parameters.empty() ) {
195                        for ( std::list< TypeDecl* >::const_iterator tyvar = baseParameters->begin(); tyvar != baseParameters->end(); ++tyvar ) {
196                                boundVars.insert( (*tyvar)->name );
197                        } // for
198                } // if
199        } // if
200}
201
202void TypeSubstitution::Substituter::premutate( StructInstType * aggregateUseType ) {
203        handleAggregateType( aggregateUseType );
204}
205
206void TypeSubstitution::Substituter::premutate( UnionInstType *aggregateUseType ) {
207        handleAggregateType( aggregateUseType );
208}
209
210#endif
211
212} // namespace ast
213
214// Local Variables: //
215// tab-width: 4 //
216// mode: c++ //
217// compile-command: "make install" //
218// End: //
Note: See TracBrowser for help on using the repository browser.