source: src/AST/TypeSubstitution.cpp @ a8b87d3

pthread-emulationqualifiedEnum
Last change on this file since a8b87d3 was a8b87d3, checked in by Andrew Beach <ajbeach@…>, 6 months ago

Various bits of clean-up. The big one was some renaming inside TypeSubstitution? (typeEnv was not a TypeEnvironment?).

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