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 |
|
---|
19 | namespace ast {
|
---|
20 |
|
---|
21 |
|
---|
22 | // size_t TypeSubstitution::Substituter::traceId = Stats::Heap::new_stacktrace_id("TypeSubstitution");
|
---|
23 |
|
---|
24 | TypeSubstitution::TypeSubstitution() {
|
---|
25 | }
|
---|
26 |
|
---|
27 | TypeSubstitution::TypeSubstitution( const TypeSubstitution &other ) : Node() {
|
---|
28 | initialize( other, *this );
|
---|
29 | }
|
---|
30 |
|
---|
31 | TypeSubstitution::~TypeSubstitution() {}
|
---|
32 |
|
---|
33 | TypeSubstitution &TypeSubstitution::operator=( const TypeSubstitution &other ) {
|
---|
34 | if ( this == &other ) return *this;
|
---|
35 | initialize( other, *this );
|
---|
36 | return *this;
|
---|
37 | }
|
---|
38 |
|
---|
39 | void TypeSubstitution::initialize( const TypeSubstitution &src, TypeSubstitution &dest ) {
|
---|
40 | dest.typeEnv.clear();
|
---|
41 | dest.varEnv.clear();
|
---|
42 | dest.add( src );
|
---|
43 | }
|
---|
44 |
|
---|
45 | void 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 |
|
---|
54 | void TypeSubstitution::add( std::string formalType, const Type *actualType ) {
|
---|
55 | typeEnv[ formalType ] = actualType;
|
---|
56 | }
|
---|
57 |
|
---|
58 | void TypeSubstitution::addVar( std::string formalExpr, const Expr *actualExpr ) {
|
---|
59 | varEnv[ formalExpr ] = actualExpr;
|
---|
60 | }
|
---|
61 |
|
---|
62 | void 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 |
|
---|
69 | const 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 |
|
---|
91 | bool TypeSubstitution::empty() const {
|
---|
92 | return typeEnv.empty() && varEnv.empty();
|
---|
93 | }
|
---|
94 |
|
---|
95 | namespace {
|
---|
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
|
---|
110 | TypeSubstitution * 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 |
|
---|
120 | void 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 |
|
---|
131 | const 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 |
|
---|
158 | const 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 |
|
---|
168 | void 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 |
|
---|
178 | void 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 |
|
---|
196 | void TypeSubstitution::Substituter::previsit( const StructInstType * aggregateUseType ) {
|
---|
197 | handleAggregateType( aggregateUseType );
|
---|
198 | }
|
---|
199 |
|
---|
200 | void 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: //
|
---|