source: src/SynTree/TypeSubstitution.h @ 1cdfa82

new-envwith_gc
Last change on this file since 1cdfa82 was 1cdfa82, checked in by Aaron Moss <a3moss@…>, 6 years ago

Merge remote-tracking branch 'origin/master' into with_gc

  • Property mode set to 100644
File size: 7.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 : Sat Jul 22 09:52:24 2017
13// Update Count     : 3
14//
15
16#pragma once
17
18#include <cassert>                 // for assert
19#include <iosfwd>                  // for ostream
20#include <list>                    // for list<>::iterator, _List_iterator
21#include <map>                     // for _Rb_tree_iterator, map, map<>::val...
22#include <set>                     // for set
23#include <string>                  // for string, operator!=
24#include <utility>                 // for pair
25
26#include "Common/SemanticError.h"  // for SemanticError
27#include "SynTree/Declaration.h"   // for TypeDecl, Declaration (ptr only)
28#include "SynTree/Expression.h"    // for Expression (ptr only), NameExpr (p...
29#include "SynTree/Type.h"          // for Type, ArrayType (ptr only), BasicT...
30
31class TypeSubstitution {
32  public:
33        TypeSubstitution();
34        template< typename FormalIterator, typename ActualIterator >
35        TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
36        TypeSubstitution( const TypeSubstitution &other );
37
38        TypeSubstitution &operator=( const TypeSubstitution &other );
39
40        template< typename SynTreeClass > int apply( SynTreeClass *&input );
41        template< typename SynTreeClass > int applyFree( SynTreeClass *&input );
42
43        void add( std::string formalType, Type *actualType );
44        void add( const TypeSubstitution &other );
45        void remove( std::string formalType );
46        Type *lookup( std::string formalType ) const;
47        bool empty() const;
48
49        template< typename FormalIterator, typename ActualIterator >
50        void add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
51
52        /// this function is unused...
53        template< typename TypeInstListIterator >
54        void extract( TypeInstListIterator begin, TypeInstListIterator end, TypeSubstitution &result );
55
56        /// create a new TypeSubstitution using bindings from env containing all of the type variables in expr
57        static TypeSubstitution * newFromExpr( Expression * expr, TypeSubstitution * env );
58
59        void normalize();
60
61        void accept( Visitor& v ) { v.visit( this ); }
62        TypeSubstitution * acceptMutator( Mutator & m ) { return m.mutate( this ); }
63
64        void print( std::ostream &os, Indenter indent = {} ) const;
65        TypeSubstitution *clone() const { return new TypeSubstitution( *this ); }
66  private:
67
68        // Mutator that performs the substitution
69        struct Substituter;
70
71        // TODO: worry about traversing into a forall-qualified function type or type decl with assertions
72
73        void initialize( const TypeSubstitution &src, TypeSubstitution &dest );
74
75        friend class Mutator;
76
77        template<typename pass_type>
78        friend class PassVisitor;
79
80        typedef std::map< std::string, Type* > TypeEnvType;
81        typedef std::map< std::string, Expression* > VarEnvType;
82        TypeEnvType typeEnv;
83        VarEnvType varEnv;
84
85  public:
86        // has to come after declaration of typeEnv
87        auto begin()       -> decltype( typeEnv.begin() ) { return typeEnv.begin(); }
88        auto   end()       -> decltype( typeEnv.  end() ) { return typeEnv.  end(); }
89        auto begin() const -> decltype( typeEnv.begin() ) { return typeEnv.begin(); }
90        auto   end() const -> decltype( typeEnv.  end() ) { return typeEnv.  end(); }
91};
92
93template< typename FormalIterator, typename ActualIterator >
94void TypeSubstitution::add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
95        // FormalIterator points to a TypeDecl
96        // ActualIterator points to a Type
97        FormalIterator formalIt = formalBegin;
98        ActualIterator actualIt = actualBegin;
99        for ( ; formalIt != formalEnd; ++formalIt, ++actualIt ) {
100                if ( TypeDecl *formal = dynamic_cast< TypeDecl* >( *formalIt ) ) {
101                        if ( TypeExpr *actual = dynamic_cast< TypeExpr* >( *actualIt ) ) {
102                                if ( formal->get_name() != "" ) {
103                                        typeEnv[ formal->get_name() ] = actual->get_type()->clone();
104                                } // if
105                        } else {
106                                SemanticError( formal, toString( "Attempt to provide non-type parameter: ", toString( *actualIt ).c_str(), " for type parameter " ) );
107                        } // if
108                } else {
109                        // TODO: type check the formal and actual parameters
110                        if ( (*formalIt)->get_name() != "" ) {
111                                varEnv[ (*formalIt)->get_name() ] = (*actualIt)->clone();
112                        } // if
113                } // if
114        } // for
115}
116
117template< typename FormalIterator, typename ActualIterator >
118TypeSubstitution::TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
119        add( formalBegin, formalEnd, actualBegin );
120}
121
122// include needs to happen after TypeSubstitution is defined so that both TypeSubstitution and
123// PassVisitor are defined before PassVisitor implementation accesses TypeSubstitution internals.
124#include "Common/PassVisitor.h"
125
126// definitition must happen after PassVisitor is included so that WithGuards can be used
127struct TypeSubstitution::Substituter : public WithGuards, public WithVisitorRef<Substituter> {
128                Substituter( TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {}
129
130                Type * postmutate( TypeInstType * aggregateUseType );
131                Expression * postmutate( NameExpr * nameExpr );
132
133                /// Records type variable bindings from forall-statements
134                void premutate( Type * type );
135                /// Records type variable bindings from forall-statements and instantiations of generic types
136                template< typename TypeClass > void handleAggregateType( TypeClass * type );
137
138                void premutate( StructInstType * aggregateUseType );
139                void premutate( UnionInstType * aggregateUseType );
140
141                TypeSubstitution & sub;
142                int subCount = 0;
143                bool freeOnly;
144                typedef std::set< std::string > BoundVarsType;
145                BoundVarsType boundVars;
146};
147
148template< typename SynTreeClass >
149int TypeSubstitution::apply( SynTreeClass *&input ) {
150        assert( input );
151        PassVisitor<Substituter> sub( *this, false );
152        input = dynamic_cast< SynTreeClass * >( input->acceptMutator( sub ) );
153        assert( input );
154///     std::cerr << "substitution result is: ";
155///     newType->print( std::cerr );
156///     std::cerr << std::endl;
157        return sub.pass.subCount;
158}
159
160template< typename SynTreeClass >
161int TypeSubstitution::applyFree( SynTreeClass *&input ) {
162        assert( input );
163        PassVisitor<Substituter> sub( *this, true );
164        input = dynamic_cast< SynTreeClass * >( input->acceptMutator( sub ) );
165        assert( input );
166///     std::cerr << "substitution result is: ";
167///     newType->print( std::cerr );
168///     std::cerr << std::endl;
169        return sub.pass.subCount;
170}
171
172template< typename TypeInstListIterator >
173void TypeSubstitution::extract( TypeInstListIterator begin, TypeInstListIterator end, TypeSubstitution &result ) {
174        // xxx - this function doesn't extract varEnv - is this intentional?
175        while ( begin != end ) {
176                TypeEnvType::iterator cur = typeEnv.find( (*begin++)->get_name() );
177                if ( cur != typeEnv.end() ) {
178                        result.typeEnv[ cur->first ] = cur->second;
179                        typeEnv.erase( cur );
180                } // if
181        } // while
182}
183
184/// Instantiate each member of the context given the actual parameters specified, and store the
185/// instantiations for use by the indexer
186template< typename FormalIterator, typename ActualIterator, typename MemberIterator, typename OutputIterator >
187void applySubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actual, MemberIterator memberBegin, MemberIterator memberEnd, OutputIterator out ) {
188        TypeSubstitution sub = TypeSubstitution( formalBegin, formalEnd, actual );
189        for ( auto i = memberBegin; i != memberEnd; ++i ) {
190                sub.apply( *i );
191                *out++ = *i;
192        } // for
193}
194
195std::ostream & operator<<( std::ostream & out, const TypeSubstitution & sub );
196
197// Local Variables: //
198// tab-width: 4 //
199// mode: c++ //
200// compile-command: "make install" //
201// End: //
Note: See TracBrowser for help on using the repository browser.