source: src/AST/TypeSubstitution.cpp @ bccd70a

ast-experimental
Last change on this file since bccd70a was bccd70a, checked in by Andrew Beach <ajbeach@…>, 9 months ago

Removed internal code from TypeSubstitution? header. It caused a chain of include problems, which have been corrected.

  • 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 : Andrew Beach
12// Last Modified On : Thr May 25 11:24:00 2023
13// Update Count     : 6
14//
15
16#include "TypeSubstitution.hpp"
17
18#include "Type.hpp"   // for TypeInstType, Type, StructInstType, UnionInstType
19#include "Pass.hpp"   // for Pass, PureVisitor, WithGuards, WithVisitorRef
20
21namespace ast {
22
23TypeSubstitution::TypeSubstitution() {
24}
25
26TypeSubstitution::TypeSubstitution( const TypeSubstitution &other ) : Node() {
27        initialize( other, *this );
28}
29
30TypeSubstitution::~TypeSubstitution() {}
31
32TypeSubstitution &TypeSubstitution::operator=( const TypeSubstitution &other ) {
33        if ( this == &other ) return *this;
34        initialize( other, *this );
35        return *this;
36}
37
38void TypeSubstitution::initialize( const TypeSubstitution &src, TypeSubstitution &dest ) {
39        dest.typeMap.clear();
40        dest.add( src );
41}
42
43void TypeSubstitution::add( const TypeSubstitution &other ) {
44        for ( TypeMap::const_iterator i = other.typeMap.begin(); i != other.typeMap.end(); ++i ) {
45                typeMap[ i->first ] = i->second;
46        } // for
47}
48
49void TypeSubstitution::add( const TypeInstType * formalType, const Type *actualType ) {
50        typeMap[ *formalType ] = actualType;
51}
52
53void TypeSubstitution::add( const TypeEnvKey & key, const Type * actualType) {
54        typeMap[ key ] = actualType;
55}
56
57void TypeSubstitution::remove( const TypeInstType * formalType ) {
58        TypeMap::iterator i = typeMap.find( *formalType );
59        if ( i != typeMap.end() ) {
60                typeMap.erase( *formalType );
61        } // if
62}
63
64const Type *TypeSubstitution::lookup(
65                const TypeEnvKey & formalType ) const {
66        TypeMap::const_iterator i = typeMap.find( formalType );
67
68        // break on not in substitution set
69        if ( i == typeMap.end() ) return 0;
70
71        // attempt to transitively follow TypeInstType links.
72        while ( const TypeInstType *actualType = i->second.as<TypeInstType>()) {
73                // break cycles in the transitive follow
74                if ( formalType == *actualType ) break;
75
76                // Look for the type this maps to, returning previous mapping if none-such
77                i = typeMap.find( *actualType );
78                if ( i == typeMap.end() ) return actualType;
79        }
80
81        // return type from substitution set
82        return i->second;
83}
84
85const Type *TypeSubstitution::lookup( const TypeInstType * formalType ) const {
86        return lookup( ast::TypeEnvKey( *formalType ) );
87}
88
89bool TypeSubstitution::empty() const {
90        return typeMap.empty();
91}
92
93namespace {
94        struct EnvTrimmer {
95                const TypeSubstitution * env;
96                TypeSubstitution * newEnv;
97                EnvTrimmer( const TypeSubstitution * env, TypeSubstitution * newEnv ) : env( env ), newEnv( newEnv ){}
98                void previsit( const FunctionType * ftype ) {
99                        // transfer known bindings for seen type variables
100                        for (auto & formal : ftype->forall) {
101                                if ( const Type * t = env->lookup( formal ) ) {
102                                        newEnv->add( formal, t );
103                                }
104                        }
105                }
106        };
107} // namespace
108
109/// reduce environment to just the parts that are referenced in a given expression
110TypeSubstitution * 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// definitition must happen after PassVisitor is included so that WithGuards can be used
121struct TypeSubstitution::Substituter : public WithGuards, public WithVisitorRef<Substituter>, public PureVisitor {
122        //static size_t traceId;
123
124        Substituter( const TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {}
125
126        const Type * postvisit( const TypeInstType * aggregateUseType );
127
128        /// Records type variable bindings from forall-statements
129        void previsit( const FunctionType * type );
130        /// Records type variable bindings from forall-statements and instantiations of generic types
131        // void handleAggregateType( const BaseInstType * type );
132
133        // void previsit( const StructInstType * aggregateUseType );
134        // void previsit( const UnionInstType * aggregateUseType );
135
136        const TypeSubstitution & sub;
137        int subCount = 0;
138        bool freeOnly;
139        typedef std::unordered_set< TypeEnvKey > BoundVarsType;
140        BoundVarsType boundVars;
141};
142
143// size_t TypeSubstitution::Substituter::traceId = Stats::Heap::new_stacktrace_id("TypeSubstitution");
144
145void TypeSubstitution::normalize() {
146        Pass<Substituter> sub( *this, true );
147        do {
148                sub.core.subCount = 0;
149                sub.core.freeOnly = true;
150                for ( TypeMap::iterator i = typeMap.begin(); i != typeMap.end(); ++i ) {
151                        i->second = i->second->accept( sub );
152                }
153        } while ( sub.core.subCount );
154}
155
156TypeSubstitution::ApplyResult<Node> TypeSubstitution::applyBase(
157                const Node * input, bool isFree ) const {
158        assert( input );
159        Pass<Substituter> sub( *this, isFree );
160        const Node * output = input->accept( sub );
161        return { output, sub.core.subCount };
162}
163
164const Type * TypeSubstitution::Substituter::postvisit( const TypeInstType *inst ) {
165        BoundVarsType::const_iterator bound = boundVars.find( *inst );
166        if ( bound != boundVars.end() ) return inst;
167
168        TypeMap::const_iterator i = sub.typeMap.find( *inst );
169        if ( i == sub.typeMap.end() ) {
170                return inst;
171        } else {
172                // cut off infinite loop for the case where a type is bound to itself.
173                // Note: this does not prevent cycles in the general case, so it may be necessary to do something more sophisticated here.
174                // TODO: investigate preventing type variables from being bound to themselves in the first place.
175                if ( const TypeInstType * replacement = i->second.as<TypeInstType>() ) {
176                        if ( *inst == *replacement ) {
177                                return inst;
178                        }
179                }
180                // std::cerr << "found " << inst->name << ", replacing with " << i->second << std::endl;
181                subCount++;
182                ptr<Type> newType = i->second; // force clone if needed
183                add_qualifiers( newType, inst->qualifiers );
184                // Note: need to recursively apply substitution to the new type because normalize does not
185                // substitute bound vars, but bound vars must be substituted when not in freeOnly mode.
186                newType = newType->accept( *visitor );
187                return newType.release();
188        } // if
189}
190
191void TypeSubstitution::Substituter::previsit( const FunctionType * ptype ) {
192        GuardValue( boundVars );
193        // bind type variables from forall-qualifiers
194        if ( freeOnly ) {
195                for ( auto & tyvar : ptype->forall ) {
196                                boundVars.insert( *tyvar );
197                } // for
198        } // if
199}
200
201/*
202void TypeSubstitution::Substituter::handleAggregateType( const BaseInstType * type ) {
203        GuardValue( boundVars );
204        // bind type variables from forall-qualifiers
205        if ( freeOnly ) {
206                // bind type variables from generic type instantiations
207                if ( auto decl = type->aggr() ) {
208                        if ( ! type->params.empty() ) {
209                                for ( const TypeDecl * tyvar : decl->params ) {
210                                        boundVars.insert( *tyvar );
211                                } // for
212                        } // if
213                }
214        } // if
215}
216
217void TypeSubstitution::Substituter::previsit( const StructInstType * aggregateUseType ) {
218        handleAggregateType( aggregateUseType );
219}
220
221void TypeSubstitution::Substituter::previsit( const UnionInstType *aggregateUseType ) {
222        handleAggregateType( aggregateUseType );
223}
224*/
225
226} // namespace ast
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.