source: src/AST/TypeSubstitution.hpp @ 97c215f

ADTast-experimentalenumpthread-emulationqualifiedEnum
Last change on this file since 97c215f was 3e5dd913, checked in by Fangren Yu <f37yu@…>, 4 years ago

reimplement function type and eliminate deep copy

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