source: src/AST/TypeSubstitution.cpp @ c671112

arm-ehcleanup-dtorsenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since c671112 was c671112, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

AST for TypeSubstitution?

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