source: src/SynTree/TypeSubstitution.cc @ ed52dd5

ADTast-experimental
Last change on this file since ed52dd5 was 172d9342, checked in by Michael Brooks <mlbrooks@…>, 5 years ago

added old-to-new conversion for TypeSubstitution?, within a framework for expressions

  • Property mode set to 100644
File size: 7.6 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
148Type * TypeSubstitution::Substituter::postmutate( TypeInstType *inst ) {
149        BoundVarsType::const_iterator bound = boundVars.find( inst->name );
150        if ( bound != boundVars.end() ) return inst;
151
152        TypeEnvType::const_iterator i = sub.typeEnv.find( inst->get_name() );
153        if ( i == sub.typeEnv.end() ) {
154                return inst;
155        } else {
156                // cut off infinite loop for the case where a type is bound to itself.
157                // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here.
158                // TODO: investigate preventing type variables from being bound to themselves in the first place.
159                if ( TypeInstType * replacement = dynamic_cast< TypeInstType * >( i->second ) ) {
160                        if ( inst->name == replacement->name ) {
161                                return inst;
162                        }
163                }
164                // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl;
165                subCount++;
166                Type * newtype = i->second->clone();
167                newtype->get_qualifiers() |= inst->get_qualifiers();
168                delete inst;
169                // 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.
170                return newtype->acceptMutator( *visitor );
171        } // if
172}
173
174Expression * TypeSubstitution::Substituter::postmutate( NameExpr * nameExpr ) {
175        VarEnvType::const_iterator i = sub.varEnv.find( nameExpr->name );
176        if ( i == sub.varEnv.end() ) {
177                return nameExpr;
178        } else {
179                subCount++;
180                delete nameExpr;
181                return i->second->clone();
182        } // if
183}
184
185void TypeSubstitution::Substituter::premutate( Type * type ) {
186        GuardValue( boundVars );
187        // bind type variables from forall-qualifiers
188        if ( freeOnly ) {
189                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
190                        boundVars.insert( (*tyvar)->name );
191                } // for
192        } // if
193}
194
195template< typename TypeClass >
196void TypeSubstitution::Substituter::handleAggregateType( TypeClass * type ) {
197        GuardValue( boundVars );
198        // bind type variables from forall-qualifiers
199        if ( freeOnly ) {
200                for ( Type::ForallList::const_iterator tyvar = type->forall.begin(); tyvar != type->forall.end(); ++tyvar ) {
201                        boundVars.insert( (*tyvar)->name );
202                } // for
203                // bind type variables from generic type instantiations
204                std::list< TypeDecl* > *baseParameters = type->get_baseParameters();
205                if ( baseParameters && ! type->parameters.empty() ) {
206                        for ( std::list< TypeDecl* >::const_iterator tyvar = baseParameters->begin(); tyvar != baseParameters->end(); ++tyvar ) {
207                                boundVars.insert( (*tyvar)->name );
208                        } // for
209                } // if
210        } // if
211}
212
213void TypeSubstitution::Substituter::premutate( StructInstType * aggregateUseType ) {
214        handleAggregateType( aggregateUseType );
215}
216
217void TypeSubstitution::Substituter::premutate( UnionInstType *aggregateUseType ) {
218        handleAggregateType( aggregateUseType );
219}
220
221void TypeSubstitution::print( std::ostream &os, Indenter indent ) const {
222        os << indent << "Types:" << std::endl;
223        for ( TypeEnvType::const_iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) {
224                os << indent+1 << i->first << " -> ";
225                i->second->print( os, indent+2 );
226                os << std::endl;
227        } // for
228        os << indent << "Non-types:" << std::endl;
229        for ( VarEnvType::const_iterator i = varEnv.begin(); i != varEnv.end(); ++i ) {
230                os << indent+1 << i->first << " -> ";
231                i->second->print( os, indent+2 );
232                os << std::endl;
233        } // for
234}
235
236std::ostream & operator<<( std::ostream & out, const TypeSubstitution & sub ) {
237        sub.print( out );
238        return out;
239}
240
241
242// Local Variables: //
243// tab-width: 4 //
244// mode: c++ //
245// compile-command: "make install" //
246// End: //
Note: See TracBrowser for help on using the repository browser.