source: src/SynTree/TypeSubstitution.cc @ eff03a94

new-env
Last change on this file since eff03a94 was eff03a94, checked in by Aaron Moss <a3moss@…>, 5 years ago

Fixed infinite loop bugs

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