source: src/AST/TypeSubstitution.hpp @ 93c10de

ADTast-experimental
Last change on this file since 93c10de was 93c10de, checked in by Andrew Beach <ajbeach@…>, 15 months ago

Minimal changes to pull out nested types, TypeInstType::TypeEnvKey? and TypeDecl::Data (now TypeData?) from there parent types. Although they do connect to the parent types they were nested in they are used on their own most of the time.

  • Property mode set to 100644
File size: 7.5 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.h --
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 : Tue Apr 30 22:52:47 2019
13// Update Count     : 9
14//
15
16#pragma once
17
18#include <cassert>                 // for assert
19#include <list>                    // for list<>::iterator, _List_iterator
20#include <unordered_map>
21#include <unordered_set>
22#include <string>                  // for string, operator!=
23#include <utility>                 // for pair
24
25#include "Fwd.hpp"        // for UniqueId
26#include "ParseNode.hpp"
27#include "Type.hpp"
28#include "Common/SemanticError.h"  // for SemanticError
29#include "Visitor.hpp"
30#include "Decl.hpp"
31#include "Expr.hpp"
32#include "Node.hpp"
33
34namespace ast {
35
36class TypeSubstitution : public Node {
37  public:
38        TypeSubstitution();
39        template< typename FormalContainer, typename ActualContainer >
40        TypeSubstitution( FormalContainer formals, ActualContainer actuals );
41        template< typename FormalIterator, typename ActualIterator >
42        TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
43        TypeSubstitution( const TypeSubstitution &other );
44        virtual ~TypeSubstitution();
45
46        TypeSubstitution &operator=( const TypeSubstitution &other );
47
48        template< typename SynTreeClass >
49        struct ApplyResult {
50                ast::ptr<SynTreeClass> node;
51                int count;
52        };
53
54        template< typename SynTreeClass > ApplyResult<SynTreeClass> apply( const SynTreeClass * input ) const;
55        template< typename SynTreeClass > ApplyResult<SynTreeClass> applyFree( const SynTreeClass * input ) const;
56
57        template< typename node_t, enum Node::ref_type ref_t >
58        int apply( ptr_base< node_t, ref_t > & input ) const {
59                const node_t * p = input.get();
60                auto ret = apply(p);
61                input = ret.node;
62                return ret.count;
63        }
64
65        template< typename node_t, enum Node::ref_type ref_t >
66        int applyFree( ptr_base< node_t, ref_t > & input ) const {
67                const node_t * p = input.get();
68                auto ret = applyFree(p);
69                input = ret.node;
70                return ret.count;
71        }
72
73        void add( const TypeInstType * formalType, const Type *actualType );
74        void add( const TypeEnvKey & key, const Type *actualType );
75        void add( const TypeSubstitution &other );
76        void remove( const TypeInstType * formalType );
77        const Type *lookup( const TypeEnvKey & formalType ) const;
78        const Type *lookup( const TypeInstType * formalType ) const;
79        bool empty() const;
80
81        template< typename FormalContainer, typename ActualContainer >
82        void addAll( FormalContainer formals, ActualContainer actuals );
83        template< typename FormalIterator, typename ActualIterator >
84        void addAll( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
85
86        /// create a new TypeSubstitution using bindings from env containing all of the type variables in expr
87        static TypeSubstitution * newFromExpr( const Expr * expr, const TypeSubstitution * env );
88
89        void normalize();
90
91        const TypeSubstitution * accept( Visitor & v ) const override { return v.visit( this ); }
92
93        TypeSubstitution * clone() const override { return new TypeSubstitution( *this ); }
94
95  private:
96
97        // Mutator that performs the substitution
98        struct Substituter;
99
100        // TODO: worry about traversing into a forall-qualified function type or type decl with assertions
101
102        void initialize( const TypeSubstitution &src, TypeSubstitution &dest );
103
104        template<typename core_t>
105        friend class Pass;
106
107        typedef std::unordered_map< TypeEnvKey, ptr<Type> > TypeMap;
108        TypeMap typeMap;
109
110  public:
111        // has to come after declaration of typeMap
112        auto begin()       -> decltype( typeMap.begin() ) { return typeMap.begin(); }
113        auto   end()       -> decltype( typeMap.  end() ) { return typeMap.  end(); }
114        auto begin() const -> decltype( typeMap.begin() ) { return typeMap.begin(); }
115        auto   end() const -> decltype( typeMap.  end() ) { return typeMap.  end(); }
116
117};
118
119template< typename FormalContainer, typename ActualContainer >
120TypeSubstitution::TypeSubstitution( FormalContainer formals, ActualContainer actuals ) {
121        assert( formals.size() == actuals.size() );
122        addAll( formals.begin(), formals.end(), actuals.begin() );
123}
124
125template< typename FormalIterator, typename ActualIterator >
126TypeSubstitution::TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
127        addAll( formalBegin, formalEnd, actualBegin );
128}
129
130template< typename FormalContainer, typename ActualContainer >
131void TypeSubstitution::addAll( FormalContainer formals, ActualContainer actuals ) {
132        assert( formals.size() == actuals.size() );
133        addAll( formals.begin(), formals.end(), actuals.begin() );
134}
135
136// this is the only place where type parameters outside a function formal may be substituted.
137template< typename FormalIterator, typename ActualIterator >
138void TypeSubstitution::addAll( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
139        // FormalIterator points to a TypeDecl
140        // ActualIterator points to a Type
141        FormalIterator formalIt = formalBegin;
142        ActualIterator actualIt = actualBegin;
143        for ( ; formalIt != formalEnd; ++formalIt, ++actualIt ) {
144                if ( const TypeDecl *formal = formalIt->template as<TypeDecl>() ) {
145                        if ( const TypeExpr *actual = actualIt->template as<TypeExpr>() ) {
146                                if ( formal->name != "" ) {
147                                        typeMap[ formal ] = actual->type;
148                                } // if
149                        } else {
150                                SemanticError( formal, toString( "Attempt to provide non-type parameter: ", toString( *actualIt ).c_str(), " for type parameter " ) );
151                        } // if
152                } else {
153                        // Is this an error?
154                } // if
155        } // for
156}
157
158} // namespace ast
159
160// include needs to happen after TypeSubstitution is defined so that both TypeSubstitution and
161// PassVisitor are defined before PassVisitor implementation accesses TypeSubstitution internals.
162#include "Pass.hpp"
163#include "Copy.hpp"
164
165namespace ast {
166
167// definitition must happen after PassVisitor is included so that WithGuards can be used
168struct TypeSubstitution::Substituter : public WithGuards, public WithVisitorRef<Substituter>, public PureVisitor {
169                static size_t traceId;
170
171                Substituter( const TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {}
172
173                const Type * postvisit( const TypeInstType * aggregateUseType );
174
175                /// Records type variable bindings from forall-statements
176                void previsit( const FunctionType * type );
177                /// Records type variable bindings from forall-statements and instantiations of generic types
178                // void handleAggregateType( const BaseInstType * type );
179
180                // void previsit( const StructInstType * aggregateUseType );
181                // void previsit( const UnionInstType * aggregateUseType );
182
183                const TypeSubstitution & sub;
184                int subCount = 0;
185                bool freeOnly;
186                typedef std::unordered_set< TypeEnvKey > BoundVarsType;
187                BoundVarsType boundVars;
188
189};
190
191template< typename SynTreeClass >
192TypeSubstitution::ApplyResult<SynTreeClass> TypeSubstitution::apply( const SynTreeClass * input ) const {
193        assert( input );
194        Pass<Substituter> sub( *this, false );
195        input = strict_dynamic_cast< const SynTreeClass * >( input->accept( sub ) );
196        return { input, sub.core.subCount };
197}
198
199template< typename SynTreeClass >
200TypeSubstitution::ApplyResult<SynTreeClass> TypeSubstitution::applyFree( const SynTreeClass * input ) const {
201        assert( input );
202        Pass<Substituter> sub( *this, true );
203        input = strict_dynamic_cast< const SynTreeClass * >( input->accept( sub ) );
204        return { input, sub.core.subCount };
205}
206
207} // namespace ast
208
209// Local Variables: //
210// tab-width: 4 //
211// mode: c++ //
212// compile-command: "make install" //
213// End: //
Note: See TracBrowser for help on using the repository browser.