source: src/AST/TypeSubstitution.cpp@ 0240cd69

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 0240cd69 was 7ff3e522, checked in by Andrew Beach <ajbeach@…>, 5 years ago

{pass_t Pass::pass; => core_t Pass::core;} To avoid confusion about which pass we are talking about.

  • Property mode set to 100644
File size: 6.4 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
21
22// size_t TypeSubstitution::Substituter::traceId = Stats::Heap::new_stacktrace_id("TypeSubstitution");
23
24TypeSubstitution::TypeSubstitution() {
25}
26
27TypeSubstitution::TypeSubstitution( const TypeSubstitution &other ) : Node() {
28 initialize( other, *this );
29}
30
31TypeSubstitution::~TypeSubstitution() {}
32
33TypeSubstitution &TypeSubstitution::operator=( const TypeSubstitution &other ) {
34 if ( this == &other ) return *this;
35 initialize( other, *this );
36 return *this;
37}
38
39void TypeSubstitution::initialize( const TypeSubstitution &src, TypeSubstitution &dest ) {
40 dest.typeEnv.clear();
41 dest.varEnv.clear();
42 dest.add( src );
43}
44
45void TypeSubstitution::add( const TypeSubstitution &other ) {
46 for ( TypeEnvType::const_iterator i = other.typeEnv.begin(); i != other.typeEnv.end(); ++i ) {
47 typeEnv[ i->first ] = i->second;
48 } // for
49 for ( VarEnvType::const_iterator i = other.varEnv.begin(); i != other.varEnv.end(); ++i ) {
50 varEnv[ i->first ] = i->second;
51 } // for
52}
53
54void TypeSubstitution::add( std::string formalType, const Type *actualType ) {
55 typeEnv[ formalType ] = actualType;
56}
57
58void TypeSubstitution::addVar( std::string formalExpr, const Expr *actualExpr ) {
59 varEnv[ formalExpr ] = actualExpr;
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 const 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 Pass<EnvTrimmer> trimmer( env, newEnv );
114 expr->accept( trimmer );
115 return newEnv;
116 }
117 return nullptr;
118}
119
120void TypeSubstitution::normalize() {
121 Pass<Substituter> sub( *this, true );
122 do {
123 sub.core.subCount = 0;
124 sub.core.freeOnly = true;
125 for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) {
126 i->second = i->second->accept( sub );
127 }
128 } while ( sub.core.subCount );
129}
130
131const Type * TypeSubstitution::Substituter::postvisit( const TypeInstType *inst ) {
132 BoundVarsType::const_iterator bound = boundVars.find( inst->name );
133 if ( bound != boundVars.end() ) return inst;
134
135 TypeEnvType::const_iterator i = sub.typeEnv.find( inst->name );
136 if ( i == sub.typeEnv.end() ) {
137 return inst;
138 } else {
139 // cut off infinite loop for the case where a type is bound to itself.
140 // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here.
141 // TODO: investigate preventing type variables from being bound to themselves in the first place.
142 if ( const TypeInstType * replacement = i->second.as<TypeInstType>() ) {
143 if ( inst->name == replacement->name ) {
144 return inst;
145 }
146 }
147 // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl;
148 subCount++;
149 ptr<Type> newType = i->second; // force clone if needed
150 add_qualifiers( newType, inst->qualifiers );
151 // Note: need to recursively apply substitution to the new type because normalize does not
152 // substitute bound vars, but bound vars must be substituted when not in freeOnly mode.
153 newType = newType->accept( *visitor );
154 return newType.release();
155 } // if
156}
157
158const Expr * TypeSubstitution::Substituter::postvisit( const NameExpr * nameExpr ) {
159 VarEnvType::const_iterator i = sub.varEnv.find( nameExpr->name );
160 if ( i == sub.varEnv.end() ) {
161 return nameExpr;
162 } else {
163 subCount++;
164 return i->second;
165 } // if
166}
167
168void TypeSubstitution::Substituter::previsit( const ParameterizedType * ptype ) {
169 GuardValue( boundVars );
170 // bind type variables from forall-qualifiers
171 if ( freeOnly ) {
172 for ( const TypeDecl * tyvar : ptype->forall ) {
173 boundVars.insert( tyvar->name );
174 } // for
175 } // if
176}
177
178void TypeSubstitution::Substituter::handleAggregateType( const ReferenceToType * type ) {
179 GuardValue( boundVars );
180 // bind type variables from forall-qualifiers
181 if ( freeOnly ) {
182 for ( const TypeDecl * tyvar : type->forall ) {
183 boundVars.insert( tyvar->name );
184 } // for
185 // bind type variables from generic type instantiations
186 if ( auto decl = type->aggr() ) {
187 if ( ! type->params.empty() ) {
188 for ( const TypeDecl * tyvar : decl->params ) {
189 boundVars.insert( tyvar->name );
190 } // for
191 } // if
192 }
193 } // if
194}
195
196void TypeSubstitution::Substituter::previsit( const StructInstType * aggregateUseType ) {
197 handleAggregateType( aggregateUseType );
198}
199
200void TypeSubstitution::Substituter::previsit( const UnionInstType *aggregateUseType ) {
201 handleAggregateType( aggregateUseType );
202}
203
204} // namespace ast
205
206// Local Variables: //
207// tab-width: 4 //
208// mode: c++ //
209// compile-command: "make install" //
210// End: //
Note: See TracBrowser for help on using the repository browser.