source: src/SynTree/TypeSubstitution.cc @ 51b8582

ADTast-experimentalenumforall-pointer-decaypthread-emulationqualifiedEnum
Last change on this file since 51b8582 was 51b8582, checked in by Andrew Beach <ajbeach@…>, 3 years ago

So it was a bug in old code that seemed to be cancelling itself out but the new version does not have it. This solution got everything but one test (a polymorphic function calling itself) working.

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