source: src/SynTree/TypeSubstitution.cc @ 2472a19

new-envwith_gc
Last change on this file since 2472a19 was 1cdfa82, checked in by Aaron Moss <a3moss@…>, 7 years ago

Merge remote-tracking branch 'origin/master' into with_gc

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