[c671112] | 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 |
---|
[b1f2007] | 11 | // Last Modified By : Peter A. Buhr |
---|
| 12 | // Last Modified On : Mon Dec 11 16:07:30 2023 |
---|
| 13 | // Update Count : 15 |
---|
[c671112] | 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" |
---|
[0b57626] | 27 | #include "Type.hpp" |
---|
[c671112] | 28 | #include "Common/SemanticError.h" // for SemanticError |
---|
| 29 | #include "Visitor.hpp" |
---|
| 30 | #include "Decl.hpp" |
---|
| 31 | #include "Expr.hpp" |
---|
[76ed81f] | 32 | #include "Node.hpp" |
---|
[c671112] | 33 | |
---|
| 34 | namespace ast { |
---|
| 35 | |
---|
| 36 | class TypeSubstitution : public Node { |
---|
| 37 | public: |
---|
| 38 | TypeSubstitution(); |
---|
[4f6dda0] | 39 | template< typename FormalContainer, typename ActualContainer > |
---|
| 40 | TypeSubstitution( FormalContainer formals, ActualContainer actuals ); |
---|
[c671112] | 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 | |
---|
[bccd70a] | 48 | template< typename node_t > |
---|
[2890212] | 49 | struct ApplyResult { |
---|
[bccd70a] | 50 | ast::ptr<node_t> node; |
---|
[2890212] | 51 | int count; |
---|
| 52 | }; |
---|
| 53 | |
---|
[bccd70a] | 54 | template< typename node_t > |
---|
| 55 | ApplyResult<node_t> apply( const node_t * input ) const { |
---|
| 56 | ApplyResult<Node> ret = applyBase( input, false ); |
---|
| 57 | return { ret.node.strict_as<node_t>(), ret.count }; |
---|
| 58 | } |
---|
[76ed81f] | 59 | |
---|
| 60 | template< typename node_t, enum Node::ref_type ref_t > |
---|
| 61 | int apply( ptr_base< node_t, ref_t > & input ) const { |
---|
[bccd70a] | 62 | ApplyResult<Node> ret = applyBase( input.get(), false ); |
---|
| 63 | input = ret.node.strict_as<node_t>(); |
---|
[2890212] | 64 | return ret.count; |
---|
[76ed81f] | 65 | } |
---|
| 66 | |
---|
[bccd70a] | 67 | template< typename node_t > |
---|
| 68 | ApplyResult<node_t> applyFree( const node_t * input ) const { |
---|
| 69 | ApplyResult<Node> ret = applyBase( input, true ); |
---|
| 70 | return { ret.node.strict_as<node_t>(), ret.count }; |
---|
| 71 | } |
---|
| 72 | |
---|
[76ed81f] | 73 | template< typename node_t, enum Node::ref_type ref_t > |
---|
| 74 | int applyFree( ptr_base< node_t, ref_t > & input ) const { |
---|
[bccd70a] | 75 | ApplyResult<Node> ret = applyBase( input.get(), true ); |
---|
| 76 | input = ret.node.strict_as<node_t>(); |
---|
[2890212] | 77 | return ret.count; |
---|
[76ed81f] | 78 | } |
---|
[c671112] | 79 | |
---|
[3e5dd913] | 80 | void add( const TypeInstType * formalType, const Type *actualType ); |
---|
[93c10de] | 81 | void add( const TypeEnvKey & key, const Type *actualType ); |
---|
[c671112] | 82 | void add( const TypeSubstitution &other ); |
---|
[3e5dd913] | 83 | void remove( const TypeInstType * formalType ); |
---|
[93c10de] | 84 | const Type *lookup( const TypeEnvKey & formalType ) const; |
---|
[3e5dd913] | 85 | const Type *lookup( const TypeInstType * formalType ) const; |
---|
[c671112] | 86 | bool empty() const; |
---|
| 87 | |
---|
[4f6dda0] | 88 | template< typename FormalContainer, typename ActualContainer > |
---|
| 89 | void addAll( FormalContainer formals, ActualContainer actuals ); |
---|
[c671112] | 90 | template< typename FormalIterator, typename ActualIterator > |
---|
[4f6dda0] | 91 | void addAll( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ); |
---|
[c671112] | 92 | |
---|
| 93 | /// create a new TypeSubstitution using bindings from env containing all of the type variables in expr |
---|
| 94 | static TypeSubstitution * newFromExpr( const Expr * expr, const TypeSubstitution * env ); |
---|
| 95 | |
---|
| 96 | void normalize(); |
---|
| 97 | |
---|
| 98 | const TypeSubstitution * accept( Visitor & v ) const override { return v.visit( this ); } |
---|
| 99 | |
---|
| 100 | TypeSubstitution * clone() const override { return new TypeSubstitution( *this ); } |
---|
| 101 | |
---|
| 102 | private: |
---|
| 103 | |
---|
| 104 | // Mutator that performs the substitution |
---|
| 105 | struct Substituter; |
---|
[bccd70a] | 106 | ApplyResult<Node> applyBase( const Node * input, bool isFree ) const; |
---|
[c671112] | 107 | |
---|
| 108 | // TODO: worry about traversing into a forall-qualified function type or type decl with assertions |
---|
| 109 | |
---|
| 110 | void initialize( const TypeSubstitution &src, TypeSubstitution &dest ); |
---|
| 111 | |
---|
[7ff3e522] | 112 | template<typename core_t> |
---|
[c671112] | 113 | friend class Pass; |
---|
| 114 | |
---|
[93c10de] | 115 | typedef std::unordered_map< TypeEnvKey, ptr<Type> > TypeMap; |
---|
[a8b87d3] | 116 | TypeMap typeMap; |
---|
[c671112] | 117 | |
---|
| 118 | public: |
---|
[a8b87d3] | 119 | // has to come after declaration of typeMap |
---|
| 120 | auto begin() -> decltype( typeMap.begin() ) { return typeMap.begin(); } |
---|
| 121 | auto end() -> decltype( typeMap. end() ) { return typeMap. end(); } |
---|
| 122 | auto begin() const -> decltype( typeMap.begin() ) { return typeMap.begin(); } |
---|
| 123 | auto end() const -> decltype( typeMap. end() ) { return typeMap. end(); } |
---|
[172d9342] | 124 | |
---|
[c671112] | 125 | }; |
---|
| 126 | |
---|
[4f6dda0] | 127 | template< typename FormalContainer, typename ActualContainer > |
---|
| 128 | TypeSubstitution::TypeSubstitution( FormalContainer formals, ActualContainer actuals ) { |
---|
| 129 | assert( formals.size() == actuals.size() ); |
---|
| 130 | addAll( formals.begin(), formals.end(), actuals.begin() ); |
---|
| 131 | } |
---|
| 132 | |
---|
| 133 | template< typename FormalIterator, typename ActualIterator > |
---|
| 134 | TypeSubstitution::TypeSubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) { |
---|
| 135 | addAll( formalBegin, formalEnd, actualBegin ); |
---|
| 136 | } |
---|
| 137 | |
---|
| 138 | template< typename FormalContainer, typename ActualContainer > |
---|
| 139 | void TypeSubstitution::addAll( FormalContainer formals, ActualContainer actuals ) { |
---|
| 140 | assert( formals.size() == actuals.size() ); |
---|
| 141 | addAll( formals.begin(), formals.end(), actuals.begin() ); |
---|
| 142 | } |
---|
| 143 | |
---|
[3e5dd913] | 144 | // this is the only place where type parameters outside a function formal may be substituted. |
---|
[c671112] | 145 | template< typename FormalIterator, typename ActualIterator > |
---|
[4f6dda0] | 146 | void TypeSubstitution::addAll( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) { |
---|
[c671112] | 147 | // FormalIterator points to a TypeDecl |
---|
| 148 | // ActualIterator points to a Type |
---|
| 149 | FormalIterator formalIt = formalBegin; |
---|
| 150 | ActualIterator actualIt = actualBegin; |
---|
| 151 | for ( ; formalIt != formalEnd; ++formalIt, ++actualIt ) { |
---|
| 152 | if ( const TypeDecl *formal = formalIt->template as<TypeDecl>() ) { |
---|
| 153 | if ( const TypeExpr *actual = actualIt->template as<TypeExpr>() ) { |
---|
| 154 | if ( formal->name != "" ) { |
---|
[a8b87d3] | 155 | typeMap[ formal ] = actual->type; |
---|
[c671112] | 156 | } // if |
---|
| 157 | } else { |
---|
[b1f2007] | 158 | SemanticError( formal->location, "Attempt to provide non-type parameter %s for type parameter %s", |
---|
| 159 | toString( *actualIt ).c_str(), formal->name.c_str() ); |
---|
[c671112] | 160 | } // if |
---|
| 161 | } else { |
---|
[4f6dda0] | 162 | // Is this an error? |
---|
[c671112] | 163 | } // if |
---|
| 164 | } // for |
---|
| 165 | } |
---|
| 166 | |
---|
| 167 | } // namespace ast |
---|
| 168 | |
---|
| 169 | // Local Variables: // |
---|
| 170 | // tab-width: 4 // |
---|
| 171 | // mode: c++ // |
---|
| 172 | // compile-command: "make install" // |
---|
| 173 | // End: // |
---|