source: src/SynTree/TypeSubstitution.h @ 2ec65ad

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 2ec65ad was 2ec65ad, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Refactor trimEnv into TypeSubstitution::newFromExpr

  • Property mode set to 100644
File size: 7.4 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        virtual ~TypeSubstitution();
38
39        TypeSubstitution &operator=( const TypeSubstitution &other );
40
41        template< typename SynTreeClass > int apply( SynTreeClass *&input );
42        template< typename SynTreeClass > int applyFree( SynTreeClass *&input );
43
44        void add( std::string formalType, Type *actualType );
45        void add( const TypeSubstitution &other );
46        void remove( std::string formalType );
47        Type *lookup( std::string formalType ) const;
48        bool empty() const;
49
50        template< typename FormalIterator, typename ActualIterator >
51        void add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin );
52
53        /// this function is unused...
54        template< typename TypeInstListIterator >
55        void extract( TypeInstListIterator begin, TypeInstListIterator end, TypeSubstitution &result );
56
57        /// create a new TypeSubstitution using bindings from env containing all of the type variables in expr
58        static TypeSubstitution * newFromExpr( Expression * expr, TypeSubstitution * env );
59
60        void normalize();
61
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
86template< typename FormalIterator, typename ActualIterator >
87void TypeSubstitution::add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
88        // FormalIterator points to a TypeDecl
89        // ActualIterator points to a Type
90        FormalIterator formalIt = formalBegin;
91        ActualIterator actualIt = actualBegin;
92        for ( ; formalIt != formalEnd; ++formalIt, ++actualIt ) {
93                if ( TypeDecl *formal = dynamic_cast< TypeDecl* >( *formalIt ) ) {
94                        if ( TypeExpr *actual = dynamic_cast< TypeExpr* >( *actualIt ) ) {
95                                if ( formal->get_name() != "" ) {
96                                        TypeEnvType::iterator i = typeEnv.find( formal->get_name() );
97                                        if ( i != typeEnv.end() ) {
98                                                delete i->second;
99                                        } // if
100                                        typeEnv[ formal->get_name() ] = actual->get_type()->clone();
101                                } // if
102                        } else {
103                                SemanticError( formal, toString( "Attempt to provide non-type parameter: ", toString( *actualIt ).c_str(), " for type parameter " ) );
104                        } // if
105                } else {
106                        // TODO: type check the formal and actual parameters
107                        if ( (*formalIt)->get_name() != "" ) {
108                                varEnv[ (*formalIt)->get_name() ] = (*actualIt)->clone();
109                        } // if
110                } // if
111        } // for
112}
113
114template< typename FormalIterator, typename ActualIterator >
115TypeSubstitution::TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
116        add( formalBegin, formalEnd, actualBegin );
117}
118
119// include needs to happen after TypeSubstitution is defined so that both TypeSubstitution and
120// PassVisitor are defined before PassVisitor implementation accesses TypeSubstitution internals.
121#include "Common/PassVisitor.h"
122
123// definitition must happen after PassVisitor is included so that WithGuards can be used
124struct TypeSubstitution::Substituter : public WithGuards {
125                Substituter( TypeSubstitution & sub, bool freeOnly ) : sub( sub ), freeOnly( freeOnly ) {}
126
127                Type * postmutate( TypeInstType * aggregateUseType );
128                Expression * postmutate( NameExpr * nameExpr );
129
130                /// Records type variable bindings from forall-statements
131                void premutate( Type * type );
132                /// Records type variable bindings from forall-statements and instantiations of generic types
133                template< typename TypeClass > void handleAggregateType( TypeClass * type );
134
135                void premutate( StructInstType * aggregateUseType );
136                void premutate( UnionInstType * aggregateUseType );
137
138                TypeSubstitution & sub;
139                int subCount = 0;
140                bool freeOnly;
141                typedef std::set< std::string > BoundVarsType;
142                BoundVarsType boundVars;
143};
144
145template< typename SynTreeClass >
146int TypeSubstitution::apply( SynTreeClass *&input ) {
147        assert( input );
148        PassVisitor<Substituter> sub( *this, false );
149        input = dynamic_cast< SynTreeClass * >( input->acceptMutator( sub ) );
150        assert( input );
151///     std::cerr << "substitution result is: ";
152///     newType->print( std::cerr );
153///     std::cerr << std::endl;
154        return sub.pass.subCount;
155}
156
157template< typename SynTreeClass >
158int TypeSubstitution::applyFree( SynTreeClass *&input ) {
159        assert( input );
160        PassVisitor<Substituter> sub( *this, true );
161        input = dynamic_cast< SynTreeClass * >( input->acceptMutator( sub ) );
162        assert( input );
163///     std::cerr << "substitution result is: ";
164///     newType->print( std::cerr );
165///     std::cerr << std::endl;
166        return sub.pass.subCount;
167}
168
169template< typename TypeInstListIterator >
170void TypeSubstitution::extract( TypeInstListIterator begin, TypeInstListIterator end, TypeSubstitution &result ) {
171        // xxx - this function doesn't extract varEnv - is this intentional?
172        while ( begin != end ) {
173                TypeEnvType::iterator cur = typeEnv.find( (*begin++)->get_name() );
174                if ( cur != typeEnv.end() ) {
175                        result.typeEnv[ cur->first ] = cur->second;
176                        typeEnv.erase( cur );
177                } // if
178        } // while
179}
180
181/// Instantiate each member of the context given the actual parameters specified, and store the
182/// instantiations for use by the indexer
183template< typename FormalIterator, typename ActualIterator, typename MemberIterator, typename OutputIterator >
184void applySubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actual, MemberIterator memberBegin, MemberIterator memberEnd, OutputIterator out ) {
185        TypeSubstitution sub = TypeSubstitution( formalBegin, formalEnd, actual );
186        for ( auto i = memberBegin; i != memberEnd; ++i ) {
187                sub.apply( *i );
188                *out++ = *i;
189        } // for
190}
191
192std::ostream & operator<<( std::ostream & out, const TypeSubstitution & sub );
193
194// Local Variables: //
195// tab-width: 4 //
196// mode: c++ //
197// compile-command: "make install" //
198// End: //
Note: See TracBrowser for help on using the repository browser.