Changeset 13de4478 for src/ResolvExpr/Unify.cc
- Timestamp:
- Apr 23, 2024, 1:37:17 PM (3 months ago)
- Branches:
- master
- Children:
- 4a3eb1c
- Parents:
- 15215f02
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/Unify.cc
r15215f02 r13de4478 47 47 namespace ResolvExpr { 48 48 49 bool typesCompatible( 50 const ast::Type * first, const ast::Type * second, 51 const ast::TypeEnvironment & env ) { 52 ast::TypeEnvironment newEnv; 53 ast::OpenVarSet open, closed; 54 ast::AssertionSet need, have; 55 56 ast::ptr<ast::Type> newFirst{ first }, newSecond{ second }; 57 env.apply( newFirst ); 58 env.apply( newSecond ); 59 60 // findOpenVars( newFirst, open, closed, need, have, FirstClosed ); 61 findOpenVars( newSecond, open, closed, need, have, newEnv, FirstOpen ); 62 63 return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden() ); 64 } 65 66 bool typesCompatibleIgnoreQualifiers( 67 const ast::Type * first, const ast::Type * second, 68 const ast::TypeEnvironment & env ) { 69 ast::TypeEnvironment newEnv; 70 ast::OpenVarSet open; 71 ast::AssertionSet need, have; 72 73 ast::Type * newFirst = shallowCopy( first ); 74 ast::Type * newSecond = shallowCopy( second ); 75 76 newFirst ->qualifiers = {}; 77 newSecond->qualifiers = {}; 78 ast::ptr< ast::Type > t1_(newFirst ); 79 ast::ptr< ast::Type > t2_(newSecond); 80 81 ast::ptr< ast::Type > subFirst = env.apply(newFirst).node; 82 ast::ptr< ast::Type > subSecond = env.apply(newSecond).node; 83 84 return unifyExact( 85 subFirst, 86 subSecond, 87 newEnv, need, have, open, noWiden() ); 88 } 89 90 namespace { 91 /// Replaces ttype variables with their bound types. 92 /// If this isn't done when satifying ttype assertions, then argument lists can have 93 /// different size and structure when they should be compatible. 94 struct TtypeExpander : public ast::WithShortCircuiting, public ast::PureVisitor { 95 ast::TypeEnvironment & tenv; 96 97 TtypeExpander( ast::TypeEnvironment & env ) : tenv( env ) {} 98 99 const ast::Type * postvisit( const ast::TypeInstType * typeInst ) { 100 if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) { 101 // expand ttype parameter into its actual type 102 if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) { 103 return clz->bound; 104 } 49 bool typesCompatible( 50 const ast::Type * first, const ast::Type * second, 51 const ast::TypeEnvironment & env ) { 52 ast::TypeEnvironment newEnv; 53 ast::OpenVarSet open, closed; 54 ast::AssertionSet need, have; 55 56 ast::ptr<ast::Type> newFirst( first ), newSecond( second ); 57 env.apply( newFirst ); 58 env.apply( newSecond ); 59 60 // findOpenVars( newFirst, open, closed, need, have, FirstClosed ); 61 findOpenVars( newSecond, open, closed, need, have, newEnv, FirstOpen ); 62 63 return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden() ); 64 } 65 66 bool typesCompatibleIgnoreQualifiers( 67 const ast::Type * first, const ast::Type * second, 68 const ast::TypeEnvironment & env ) { 69 ast::TypeEnvironment newEnv; 70 ast::OpenVarSet open; 71 ast::AssertionSet need, have; 72 73 ast::Type * newFirst = shallowCopy( first ); 74 ast::Type * newSecond = shallowCopy( second ); 75 76 newFirst ->qualifiers = {}; 77 newSecond->qualifiers = {}; 78 ast::ptr< ast::Type > t1_(newFirst ); 79 ast::ptr< ast::Type > t2_(newSecond); 80 81 ast::ptr< ast::Type > subFirst = env.apply(newFirst).node; 82 ast::ptr< ast::Type > subSecond = env.apply(newSecond).node; 83 84 return unifyExact( 85 subFirst, 86 subSecond, 87 newEnv, need, have, open, noWiden() ); 88 } 89 90 namespace { 91 /// Replaces ttype variables with their bound types. 92 /// If this isn't done when satifying ttype assertions, then argument lists can have 93 /// different size and structure when they should be compatible. 94 struct TtypeExpander : public ast::WithShortCircuiting, public ast::PureVisitor { 95 ast::TypeEnvironment & tenv; 96 97 TtypeExpander( ast::TypeEnvironment & env ) : tenv( env ) {} 98 99 const ast::Type * postvisit( const ast::TypeInstType * typeInst ) { 100 if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) { 101 // expand ttype parameter into its actual type 102 if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) { 103 return clz->bound; 105 104 } 106 return typeInst;107 105 } 108 }; 109 } 110 111 std::vector< ast::ptr< ast::Type > > flattenList( 112 const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env 106 return typeInst; 107 } 108 }; 109 } 110 111 std::vector< ast::ptr< ast::Type > > flattenList( 112 const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env 113 ) { 114 std::vector< ast::ptr< ast::Type > > dst; 115 dst.reserve( src.size() ); 116 for ( const auto & d : src ) { 117 ast::Pass<TtypeExpander> expander( env ); 118 // TtypeExpander pass is impure (may mutate nodes in place) 119 // need to make nodes shared to prevent accidental mutation 120 ast::ptr<ast::Type> dc = d->accept(expander); 121 auto types = flatten( dc ); 122 for ( ast::ptr< ast::Type > & t : types ) { 123 // outermost const, volatile, _Atomic qualifiers in parameters should not play 124 // a role in the unification of function types, since they do not determine 125 // whether a function is callable. 126 // NOTE: **must** consider at least mutex qualifier, since functions can be 127 // overloaded on outermost mutex and a mutex function has different 128 // requirements than a non-mutex function 129 remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic ); 130 dst.emplace_back( t ); 131 } 132 } 133 return dst; 134 } 135 136 // Unification of Expressions 137 // 138 // Boolean outcome (obvious): Are they basically spelled the same? 139 // Side effect of binding variables (subtle): if `sizeof(int)` ===_expr `sizeof(T)` then `int` ===_ty `T` 140 // 141 // Context: if `float[VAREXPR1]` ===_ty `float[VAREXPR2]` then `VAREXPR1` ===_expr `VAREXPR2` 142 // where the VAREXPR are meant as notational metavariables representing the fact that unification always 143 // sees distinct ast::VariableExpr objects at these positions 144 145 static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env, 146 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 147 WidenMode widen ); 148 149 class UnifyExpr final : public ast::WithShortCircuiting { 150 const ast::Expr * e2; 151 ast::TypeEnvironment & tenv; 152 ast::AssertionSet & need; 153 ast::AssertionSet & have; 154 const ast::OpenVarSet & open; 155 WidenMode widen; 156 public: 157 bool result; 158 159 private: 160 161 void tryMatchOnStaticValue( const ast::Expr * e1 ) { 162 Evaluation r1 = eval(e1); 163 Evaluation r2 = eval(e2); 164 165 if ( !r1.hasKnownValue ) return; 166 if ( !r2.hasKnownValue ) return; 167 168 if ( r1.knownValue != r2.knownValue ) return; 169 170 visit_children = false; 171 result = true; 172 } 173 174 public: 175 176 void previsit( const ast::Node * ) { assert(false); } 177 178 void previsit( const ast::Expr * e1 ) { 179 tryMatchOnStaticValue( e1 ); 180 visit_children = false; 181 } 182 183 void previsit( const ast::CastExpr * e1 ) { 184 tryMatchOnStaticValue( e1 ); 185 186 if ( result ) { 187 assert( visit_children == false ); 188 } else { 189 assert( visit_children == true ); 190 visit_children = false; 191 192 auto e2c = dynamic_cast< const ast::CastExpr * >( e2 ); 193 if ( !e2c ) return; 194 195 // inspect casts' target types 196 if ( !unifyExact( 197 e1->result, e2c->result, tenv, need, have, open, widen ) ) return; 198 199 // inspect casts' inner expressions 200 result = unify( e1->arg, e2c->arg, tenv, need, have, open, widen ); 201 } 202 } 203 204 void previsit( const ast::VariableExpr * e1 ) { 205 tryMatchOnStaticValue( e1 ); 206 207 if ( result ) { 208 assert( visit_children == false ); 209 } else { 210 assert( visit_children == true ); 211 visit_children = false; 212 213 auto e2v = dynamic_cast< const ast::VariableExpr * >( e2 ); 214 if ( !e2v ) return; 215 216 assert(e1->var); 217 assert(e2v->var); 218 219 // conservative: variable exprs match if their declarations are represented by the same C++ AST object 220 result = (e1->var == e2v->var); 221 } 222 } 223 224 void previsit( const ast::SizeofExpr * e1 ) { 225 tryMatchOnStaticValue( e1 ); 226 227 if ( result ) { 228 assert( visit_children == false ); 229 } else { 230 assert( visit_children == true ); 231 visit_children = false; 232 233 auto e2so = dynamic_cast< const ast::SizeofExpr * >( e2 ); 234 if ( !e2so ) return; 235 236 assert((e1->type != nullptr) ^ (e1->expr != nullptr)); 237 assert((e2so->type != nullptr) ^ (e2so->expr != nullptr)); 238 if ( !(e1->type && e2so->type) ) return; 239 240 // expression unification calls type unification (mutual recursion) 241 result = unifyExact( e1->type, e2so->type, tenv, need, have, open, widen ); 242 } 243 } 244 245 UnifyExpr( const ast::Expr * e2, ast::TypeEnvironment & env, ast::AssertionSet & need, 246 ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen ) 247 : e2( e2 ), tenv(env), need(need), have(have), open(open), widen(widen), result(false) {} 248 }; 249 250 static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env, 251 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 252 WidenMode widen ) { 253 assert( e1 && e2 ); 254 return ast::Pass<UnifyExpr>::read( e1, e2, env, need, have, open, widen ); 255 } 256 257 class Unify final : public ast::WithShortCircuiting { 258 const ast::Type * type2; 259 ast::TypeEnvironment & tenv; 260 ast::AssertionSet & need; 261 ast::AssertionSet & have; 262 const ast::OpenVarSet & open; 263 WidenMode widen; 264 public: 265 static size_t traceId; 266 bool result; 267 268 Unify( 269 const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need, 270 ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen ) 271 : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen), 272 result(false) {} 273 274 void previsit( const ast::Node * ) { visit_children = false; } 275 276 void postvisit( const ast::VoidType * vt) { 277 result = dynamic_cast< const ast::VoidType * >( type2 ) 278 || tryToUnifyWithEnumValue(vt, type2, tenv, need, have, open, noWiden()); 279 ; 280 } 281 282 void postvisit( const ast::BasicType * basic ) { 283 if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) { 284 result = basic->kind == basic2->kind; 285 } 286 result = result || tryToUnifyWithEnumValue(basic, type2, tenv, need, have, open, noWiden()); 287 } 288 289 void postvisit( const ast::PointerType * pointer ) { 290 if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) { 291 result = unifyExact( 292 pointer->base, pointer2->base, tenv, need, have, open, 293 noWiden()); 294 } 295 result = result || tryToUnifyWithEnumValue(pointer, type2, tenv, need, have, open, noWiden()); 296 } 297 298 void postvisit( const ast::ArrayType * array ) { 299 auto array2 = dynamic_cast< const ast::ArrayType * >( type2 ); 300 if ( !array2 ) return; 301 302 if ( array->isVarLen != array2->isVarLen ) return; 303 if ( (array->dimension != nullptr) != (array2->dimension != nullptr) ) return; 304 305 if ( array->dimension ) { 306 assert( array2->dimension ); 307 // type unification calls expression unification (mutual recursion) 308 if ( !unify(array->dimension, array2->dimension, 309 tenv, need, have, open, widen) ) return; 310 } 311 312 result = unifyExact( 313 array->base, array2->base, tenv, need, have, open, noWiden()) 314 || tryToUnifyWithEnumValue(array, type2, tenv, need, have, open, noWiden()); 315 } 316 317 void postvisit( const ast::ReferenceType * ref ) { 318 if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) { 319 result = unifyExact( 320 ref->base, ref2->base, tenv, need, have, open, noWiden()); 321 } 322 } 323 324 private: 325 326 template< typename Iter > 327 static bool unifyTypeList( 328 Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env, 329 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open 113 330 ) { 114 std::vector< ast::ptr< ast::Type > > dst; 115 dst.reserve( src.size() ); 116 for ( const auto & d : src ) { 117 ast::Pass<TtypeExpander> expander{ env }; 118 // TtypeExpander pass is impure (may mutate nodes in place) 119 // need to make nodes shared to prevent accidental mutation 120 ast::ptr<ast::Type> dc = d->accept(expander); 121 auto types = flatten( dc ); 122 for ( ast::ptr< ast::Type > & t : types ) { 123 // outermost const, volatile, _Atomic qualifiers in parameters should not play 124 // a role in the unification of function types, since they do not determine 125 // whether a function is callable. 126 // NOTE: **must** consider at least mutex qualifier, since functions can be 127 // overloaded on outermost mutex and a mutex function has different 128 // requirements than a non-mutex function 129 remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic ); 130 dst.emplace_back( t ); 131 } 132 } 133 return dst; 134 } 135 136 // Unification of Expressions 137 // 138 // Boolean outcome (obvious): Are they basically spelled the same? 139 // Side effect of binding variables (subtle): if `sizeof(int)` ===_expr `sizeof(T)` then `int` ===_ty `T` 140 // 141 // Context: if `float[VAREXPR1]` ===_ty `float[VAREXPR2]` then `VAREXPR1` ===_expr `VAREXPR2` 142 // where the VAREXPR are meant as notational metavariables representing the fact that unification always 143 // sees distinct ast::VariableExpr objects at these positions 144 145 static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env, 146 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 147 WidenMode widen ); 148 149 class UnifyExpr final : public ast::WithShortCircuiting { 150 const ast::Expr * e2; 151 ast::TypeEnvironment & tenv; 152 ast::AssertionSet & need; 153 ast::AssertionSet & have; 154 const ast::OpenVarSet & open; 155 WidenMode widen; 156 public: 157 bool result; 158 159 private: 160 161 void tryMatchOnStaticValue( const ast::Expr * e1 ) { 162 Evaluation r1 = eval(e1); 163 Evaluation r2 = eval(e2); 164 165 if ( ! r1.hasKnownValue ) return; 166 if ( ! r2.hasKnownValue ) return; 167 168 if (r1.knownValue != r2.knownValue) return; 169 170 visit_children = false; 171 result = true; 172 } 173 174 public: 175 176 void previsit( const ast::Node * ) { assert(false); } 177 178 void previsit( const ast::Expr * e1 ) { 179 tryMatchOnStaticValue( e1 ); 180 visit_children = false; 181 } 182 183 void previsit( const ast::CastExpr * e1 ) { 184 tryMatchOnStaticValue( e1 ); 185 186 if (result) { 187 assert (visit_children == false); 188 } else { 189 assert (visit_children == true); 190 visit_children = false; 191 192 auto e2c = dynamic_cast< const ast::CastExpr * >( e2 ); 193 if ( ! e2c ) return; 194 195 // inspect casts' target types 196 if ( ! unifyExact( 197 e1->result, e2c->result, tenv, need, have, open, widen ) ) return; 198 199 // inspect casts' inner expressions 200 result = unify( e1->arg, e2c->arg, tenv, need, have, open, widen ); 201 } 202 } 203 204 void previsit( const ast::VariableExpr * e1 ) { 205 tryMatchOnStaticValue( e1 ); 206 207 if (result) { 208 assert (visit_children == false); 209 } else { 210 assert (visit_children == true); 211 visit_children = false; 212 213 auto e2v = dynamic_cast< const ast::VariableExpr * >( e2 ); 214 if ( ! e2v ) return; 215 216 assert(e1->var); 217 assert(e2v->var); 218 219 // conservative: variable exprs match if their declarations are represented by the same C++ AST object 220 result = (e1->var == e2v->var); 221 } 222 } 223 224 void previsit( const ast::SizeofExpr * e1 ) { 225 tryMatchOnStaticValue( e1 ); 226 227 if (result) { 228 assert (visit_children == false); 229 } else { 230 assert (visit_children == true); 231 visit_children = false; 232 233 auto e2so = dynamic_cast< const ast::SizeofExpr * >( e2 ); 234 if ( ! e2so ) return; 235 236 assert((e1->type != nullptr) ^ (e1->expr != nullptr)); 237 assert((e2so->type != nullptr) ^ (e2so->expr != nullptr)); 238 if ( ! (e1->type && e2so->type) ) return; 239 240 // expression unification calls type unification (mutual recursion) 241 result = unifyExact( e1->type, e2so->type, tenv, need, have, open, widen ); 242 } 243 } 244 245 UnifyExpr( const ast::Expr * e2, ast::TypeEnvironment & env, ast::AssertionSet & need, 246 ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen ) 247 : e2( e2 ), tenv(env), need(need), have(have), open(open), widen(widen), result(false) {} 248 }; 249 250 static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env, 251 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 252 WidenMode widen ) { 253 assert( e1 && e2 ); 254 return ast::Pass<UnifyExpr>::read( e1, e2, env, need, have, open, widen ); 255 } 256 257 class Unify final : public ast::WithShortCircuiting { 258 const ast::Type * type2; 259 ast::TypeEnvironment & tenv; 260 ast::AssertionSet & need; 261 ast::AssertionSet & have; 262 const ast::OpenVarSet & open; 263 WidenMode widen; 264 public: 265 static size_t traceId; 266 bool result; 267 268 Unify( 269 const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need, 270 ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen ) 271 : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen), 272 result(false) {} 273 274 void previsit( const ast::Node * ) { visit_children = false; } 275 276 void postvisit( const ast::VoidType * vt) { 277 result = dynamic_cast< const ast::VoidType * >( type2 ) 278 || tryToUnifyWithEnumValue(vt, type2, tenv, need, have, open, noWiden()); 279 ; 280 } 281 282 void postvisit( const ast::BasicType * basic ) { 283 if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) { 284 result = basic->kind == basic2->kind; 285 } 286 result = result || tryToUnifyWithEnumValue(basic, type2, tenv, need, have, open, noWiden()); 287 } 288 289 void postvisit( const ast::PointerType * pointer ) { 290 if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) { 291 result = unifyExact( 292 pointer->base, pointer2->base, tenv, need, have, open, 293 noWiden()); 294 } 295 result = result || tryToUnifyWithEnumValue(pointer, type2, tenv, need, have, open, noWiden()); 296 } 297 298 void postvisit( const ast::ArrayType * array ) { 299 auto array2 = dynamic_cast< const ast::ArrayType * >( type2 ); 300 if ( ! array2 ) return; 301 302 if ( array->isVarLen != array2->isVarLen ) return; 303 if ( (array->dimension != nullptr) != (array2->dimension != nullptr) ) return; 304 305 if ( array->dimension ) { 306 assert( array2->dimension ); 307 // type unification calls expression unification (mutual recursion) 308 if ( ! unify(array->dimension, array2->dimension, 309 tenv, need, have, open, widen) ) return; 310 } 311 312 result = unifyExact( 313 array->base, array2->base, tenv, need, have, open, noWiden()) 314 || tryToUnifyWithEnumValue(array, type2, tenv, need, have, open, noWiden()); 315 } 316 317 void postvisit( const ast::ReferenceType * ref ) { 318 if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) { 319 result = unifyExact( 320 ref->base, ref2->base, tenv, need, have, open, noWiden()); 321 } 322 } 323 324 private: 325 326 template< typename Iter > 327 static bool unifyTypeList( 328 Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env, 329 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open 330 ) { 331 while ( crnt1 != end1 && crnt2 != end2 ) { 332 const ast::Type * t1 = *crnt1; 333 const ast::Type * t2 = *crnt2; 334 bool isTuple1 = Tuples::isTtype( t1 ); 335 bool isTuple2 = Tuples::isTtype( t2 ); 336 337 // assumes here that ttype *must* be last parameter 338 if ( isTuple1 && ! isTuple2 ) { 339 // combine remainder of list2, then unify 340 return unifyExact( 341 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open, 342 noWiden() ); 343 } else if ( ! isTuple1 && isTuple2 ) { 344 // combine remainder of list1, then unify 345 return unifyExact( 346 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open, 347 noWiden() ); 348 } 349 350 if ( ! unifyExact( 351 t1, t2, env, need, have, open, noWiden() ) 352 ) return false; 353 354 ++crnt1; ++crnt2; 355 } 356 357 // May get to the end of one argument list before the other. This is only okay if the 358 // other is a ttype 359 if ( crnt1 != end1 ) { 360 // try unifying empty tuple with ttype 361 const ast::Type * t1 = *crnt1; 362 if ( ! Tuples::isTtype( t1 ) ) return false; 331 while ( crnt1 != end1 && crnt2 != end2 ) { 332 const ast::Type * t1 = *crnt1; 333 const ast::Type * t2 = *crnt2; 334 bool isTuple1 = Tuples::isTtype( t1 ); 335 bool isTuple2 = Tuples::isTtype( t2 ); 336 337 // assumes here that ttype *must* be last parameter 338 if ( isTuple1 && !isTuple2 ) { 339 // combine remainder of list2, then unify 363 340 return unifyExact( 364 341 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open, 365 342 noWiden() ); 366 } else if ( crnt2 != end2 ) { 367 // try unifying empty tuple with ttype 368 const ast::Type * t2 = *crnt2; 369 if ( ! Tuples::isTtype( t2 ) ) return false; 343 } else if ( !isTuple1 && isTuple2 ) { 344 // combine remainder of list1, then unify 370 345 return unifyExact( 371 346 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open, … … 373 348 } 374 349 375 return true; 376 } 377 378 static bool unifyTypeList( 379 const std::vector< ast::ptr< ast::Type > > & list1, 380 const std::vector< ast::ptr< ast::Type > > & list2, 381 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 382 const ast::OpenVarSet & open 383 ) { 384 return unifyTypeList( 385 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open); 386 } 387 388 static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) { 389 auto i = assns.find( assn ); 390 if ( i != assns.end() ) { 391 i->second.isUsed = true; 350 if ( !unifyExact( 351 t1, t2, env, need, have, open, noWiden() ) 352 ) return false; 353 354 ++crnt1; ++crnt2; 355 } 356 357 // May get to the end of one argument list before the other. This is only okay if the 358 // other is a ttype 359 if ( crnt1 != end1 ) { 360 // try unifying empty tuple with ttype 361 const ast::Type * t1 = *crnt1; 362 if ( !Tuples::isTtype( t1 ) ) return false; 363 return unifyExact( 364 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open, 365 noWiden() ); 366 } else if ( crnt2 != end2 ) { 367 // try unifying empty tuple with ttype 368 const ast::Type * t2 = *crnt2; 369 if ( !Tuples::isTtype( t2 ) ) return false; 370 return unifyExact( 371 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open, 372 noWiden() ); 373 } 374 375 return true; 376 } 377 378 static bool unifyTypeList( 379 const std::vector< ast::ptr< ast::Type > > & list1, 380 const std::vector< ast::ptr< ast::Type > > & list2, 381 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 382 const ast::OpenVarSet & open 383 ) { 384 return unifyTypeList( 385 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open); 386 } 387 388 static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) { 389 auto i = assns.find( assn ); 390 if ( i != assns.end() ) { 391 i->second.isUsed = true; 392 } 393 } 394 395 /// mark all assertions in `type` used in both `assn1` and `assn2` 396 static void markAssertions( 397 ast::AssertionSet & assn1, ast::AssertionSet & assn2, 398 const ast::FunctionType * type 399 ) { 400 for ( auto & assert : type->assertions ) { 401 markAssertionSet( assn1, assert ); 402 markAssertionSet( assn2, assert ); 403 } 404 } 405 406 bool tryToUnifyWithEnumValue( const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 407 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 408 WidenMode widen) { 409 if ( auto attrType2 = dynamic_cast<const ast::EnumAttrType *>(type2)) { 410 if (attrType2->attr == ast::EnumAttribute::Value) { 411 return unifyExact( type1, attrType2->instance->base->base, env, need, have, open, 412 widen); 413 } else if (attrType2->attr == ast::EnumAttribute::Posn) { 414 return unifyExact( type1, attrType2->instance, env, need, have, open, widen ); 392 415 } 393 416 } 394 395 /// mark all assertions in `type` used in both `assn1` and `assn2` 396 static void markAssertions( 397 ast::AssertionSet & assn1, ast::AssertionSet & assn2, 398 const ast::FunctionType * type 399 ) { 400 for ( auto & assert : type->assertions ) { 401 markAssertionSet( assn1, assert ); 402 markAssertionSet( assn2, assert ); 417 return false; 418 } 419 420 public: 421 void postvisit( const ast::FunctionType * func ) { 422 auto func2 = dynamic_cast< const ast::FunctionType * >( type2 ); 423 if ( !func2 ) return; 424 425 if ( func->isVarArgs != func2->isVarArgs ) return; 426 427 // Flatten the parameter lists for both functions so that tuple structure does not 428 // affect unification. Does not actually mutate function parameters. 429 auto params = flattenList( func->params, tenv ); 430 auto params2 = flattenList( func2->params, tenv ); 431 432 // sizes don't have to match if ttypes are involved; need to be more precise w.r.t. 433 // where the ttype is to prevent errors 434 if ( 435 ( params.size() != params2.size() || func->returns.size() != func2->returns.size() ) 436 && !func->isTtype() 437 && !func2->isTtype() 438 ) return; 439 440 if ( !unifyTypeList( params, params2, tenv, need, have, open ) ) return; 441 if ( !unifyTypeList( 442 func->returns, func2->returns, tenv, need, have, open ) ) return; 443 444 markAssertions( have, need, func ); 445 markAssertions( have, need, func2 ); 446 447 result = true; 448 } 449 450 private: 451 // Returns: other, cast as XInstType 452 // Assigns this->result: whether types are compatible (up to generic parameters) 453 template< typename XInstType > 454 const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) { 455 // check that the other type is compatible and named the same 456 auto otherInst = dynamic_cast< const XInstType * >( other ); 457 if ( otherInst && inst->name == otherInst->name ) { 458 this->result = otherInst; 459 } 460 return otherInst; 461 } 462 463 /// Creates a tuple type based on a list of TypeExpr 464 template< typename Iter > 465 static const ast::Type * tupleFromExprs( 466 const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs 467 ) { 468 std::vector< ast::ptr< ast::Type > > types; 469 do { 470 types.emplace_back( param->type ); 471 472 ++crnt; 473 if ( crnt == end ) break; 474 param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() ); 475 } while(true); 476 477 return new ast::TupleType( std::move(types), qs ); 478 } 479 480 template< typename XInstType > 481 void handleGenericRefType( const XInstType * inst, const ast::Type * other ) { 482 // check that other type is compatible and named the same 483 const XInstType * otherInst = handleRefType( inst, other ); 484 if ( !this->result ) return; 485 486 // check that parameters of types unify, if any 487 const std::vector< ast::ptr< ast::Expr > > & params = inst->params; 488 const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params; 489 490 auto it = params.begin(); 491 auto jt = params2.begin(); 492 for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) { 493 auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() ); 494 auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() ); 495 496 ast::ptr< ast::Type > pty = param->type; 497 ast::ptr< ast::Type > pty2 = param2->type; 498 499 bool isTuple = Tuples::isTtype( pty ); 500 bool isTuple2 = Tuples::isTtype( pty2 ); 501 502 if ( isTuple && isTuple2 ) { 503 ++it; ++jt; // skip ttype parameters before break 504 } else if ( isTuple ) { 505 // bundle remaining params into tuple 506 pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers ); 507 ++it; // skip ttype parameter for break 508 } else if ( isTuple2 ) { 509 // bundle remaining params into tuple 510 pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers ); 511 ++jt; // skip ttype parameter for break 403 512 } 404 } 405 406 bool tryToUnifyWithEnumValue( const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 407 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 408 WidenMode widen) { 409 if ( auto attrType2 = dynamic_cast<const ast::EnumAttrType *>(type2)) { 410 if (attrType2->attr == ast::EnumAttribute::Value) { 411 return unifyExact( type1, attrType2->instance->base->base, env, need, have, open, 412 widen); 413 } else if (attrType2->attr == ast::EnumAttribute::Posn) { 414 return unifyExact( type1, attrType2->instance, env, need, have, open, widen ); 415 } 513 514 if ( !unifyExact( 515 pty, pty2, tenv, need, have, open, noWiden() ) ) { 516 result = false; 517 return; 416 518 } 417 return false; 418 } 419 420 public: 421 void postvisit( const ast::FunctionType * func ) { 422 auto func2 = dynamic_cast< const ast::FunctionType * >( type2 ); 423 if ( ! func2 ) return; 424 425 if ( func->isVarArgs != func2->isVarArgs ) return; 426 427 // Flatten the parameter lists for both functions so that tuple structure does not 428 // affect unification. Does not actually mutate function parameters. 429 auto params = flattenList( func->params, tenv ); 430 auto params2 = flattenList( func2->params, tenv ); 431 432 // sizes don't have to match if ttypes are involved; need to be more precise w.r.t. 433 // where the ttype is to prevent errors 434 if ( 435 ( params.size() != params2.size() || func->returns.size() != func2->returns.size() ) 436 && ! func->isTtype() 437 && ! func2->isTtype() 438 ) return; 439 440 if ( ! unifyTypeList( params, params2, tenv, need, have, open ) ) return; 441 if ( ! unifyTypeList( 442 func->returns, func2->returns, tenv, need, have, open ) ) return; 443 444 markAssertions( have, need, func ); 445 markAssertions( have, need, func2 ); 446 447 result = true; 448 } 449 450 private: 451 // Returns: other, cast as XInstType 452 // Assigns this->result: whether types are compatible (up to generic parameters) 453 template< typename XInstType > 454 const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) { 455 // check that the other type is compatible and named the same 456 auto otherInst = dynamic_cast< const XInstType * >( other ); 457 if (otherInst && inst->name == otherInst->name) 458 this->result = otherInst; 459 return otherInst; 460 } 461 462 /// Creates a tuple type based on a list of TypeExpr 463 template< typename Iter > 464 static const ast::Type * tupleFromExprs( 465 const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs 466 ) { 467 std::vector< ast::ptr< ast::Type > > types; 468 do { 469 types.emplace_back( param->type ); 470 471 ++crnt; 472 if ( crnt == end ) break; 473 param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() ); 474 } while(true); 475 476 return new ast::TupleType{ std::move(types), qs }; 477 } 478 479 template< typename XInstType > 480 void handleGenericRefType( const XInstType * inst, const ast::Type * other ) { 481 // check that other type is compatible and named the same 482 const XInstType * otherInst = handleRefType( inst, other ); 483 if ( ! this->result ) return; 484 485 // check that parameters of types unify, if any 486 const std::vector< ast::ptr< ast::Expr > > & params = inst->params; 487 const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params; 488 489 auto it = params.begin(); 490 auto jt = params2.begin(); 491 for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) { 492 auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() ); 493 auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() ); 494 495 ast::ptr< ast::Type > pty = param->type; 496 ast::ptr< ast::Type > pty2 = param2->type; 497 498 bool isTuple = Tuples::isTtype( pty ); 499 bool isTuple2 = Tuples::isTtype( pty2 ); 500 501 if ( isTuple && isTuple2 ) { 502 ++it; ++jt; // skip ttype parameters before break 503 } else if ( isTuple ) { 504 // bundle remaining params into tuple 505 pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers ); 506 ++it; // skip ttype parameter for break 507 } else if ( isTuple2 ) { 508 // bundle remaining params into tuple 509 pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers ); 510 ++jt; // skip ttype parameter for break 511 } 512 513 if ( ! unifyExact( 514 pty, pty2, tenv, need, have, open, noWiden() ) ) { 515 result = false; 516 return; 517 } 518 519 // ttype parameter should be last 520 if ( isTuple || isTuple2 ) break; 519 520 // ttype parameter should be last 521 if ( isTuple || isTuple2 ) break; 522 } 523 result = it == params.end() && jt == params2.end(); 524 } 525 526 public: 527 void postvisit( const ast::StructInstType * aggrType ) { 528 handleGenericRefType( aggrType, type2 ); 529 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 530 } 531 532 void postvisit( const ast::UnionInstType * aggrType ) { 533 handleGenericRefType( aggrType, type2 ); 534 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 535 } 536 537 void postvisit( const ast::EnumInstType * aggrType ) { 538 handleRefType( aggrType, type2 ); 539 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 540 } 541 542 void postvisit( const ast::EnumAttrType * enumAttr ) { 543 // Lazy approach for now 544 if ( auto otherPos = dynamic_cast< const ast::EnumAttrType *>( type2 ) ) { 545 if ( enumAttr->match(otherPos) ) { 546 result = otherPos; 521 547 } 522 result = it == params.end() && jt == params2.end(); 523 } 524 525 public: 526 void postvisit( const ast::StructInstType * aggrType ) { 527 handleGenericRefType( aggrType, type2 ); 528 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 529 } 530 531 void postvisit( const ast::UnionInstType * aggrType ) { 532 handleGenericRefType( aggrType, type2 ); 533 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 534 } 535 536 void postvisit( const ast::EnumInstType * aggrType ) { 537 handleRefType( aggrType, type2 ); 538 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 539 } 540 541 void postvisit( const ast::EnumAttrType * enumAttr ) { 542 // Lazy approach for now 543 if ( auto otherPos = dynamic_cast< const ast::EnumAttrType *>(type2) ) { 544 if ( enumAttr->match(otherPos) ) { 545 result = otherPos; 546 } 548 } 549 } 550 551 void postvisit( const ast::TraitInstType * aggrType ) { 552 handleRefType( aggrType, type2 ); 553 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 554 } 555 556 void postvisit( const ast::TypeInstType * typeInst ) { 557 // assert( open.find( *typeInst ) == open.end() ); 558 auto otherInst = dynamic_cast< const ast::TypeInstType * >( type2 ); 559 if ( otherInst && typeInst->name == otherInst->name ) { 560 this->result = otherInst; 561 } 562 result = result || tryToUnifyWithEnumValue(typeInst, type2, tenv, need, have, open, noWiden()); 563 } 564 565 private: 566 /// Creates a tuple type based on a list of Type 567 static bool unifyList( 568 const std::vector< ast::ptr< ast::Type > > & list1, 569 const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env, 570 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open 571 ) { 572 auto crnt1 = list1.begin(); 573 auto crnt2 = list2.begin(); 574 while ( crnt1 != list1.end() && crnt2 != list2.end() ) { 575 const ast::Type * t1 = *crnt1; 576 const ast::Type * t2 = *crnt2; 577 bool isTuple1 = Tuples::isTtype( t1 ); 578 bool isTuple2 = Tuples::isTtype( t2 ); 579 580 // assumes ttype must be last parameter 581 if ( isTuple1 && !isTuple2 ) { 582 // combine entirety of list2, then unify 583 return unifyExact( 584 t1, tupleFromTypes( list2 ), env, need, have, open, 585 noWiden() ); 586 } else if ( !isTuple1 && isTuple2 ) { 587 // combine entirety of list1, then unify 588 return unifyExact( 589 tupleFromTypes( list1 ), t2, env, need, have, open, 590 noWiden() ); 547 591 } 548 } 549 550 void postvisit( const ast::TraitInstType * aggrType ) { 551 handleRefType( aggrType, type2 ); 552 result = result || tryToUnifyWithEnumValue(aggrType, type2, tenv, need, have, open, noWiden()); 553 } 554 555 void postvisit( const ast::TypeInstType * typeInst ) { 556 // assert( open.find( *typeInst ) == open.end() ); 557 auto otherInst = dynamic_cast< const ast::TypeInstType * >( type2 ); 558 if ( otherInst && typeInst->name == otherInst->name ) { 559 this->result = otherInst; 560 } 561 result = result || tryToUnifyWithEnumValue(typeInst, type2, tenv, need, have, open, noWiden()); 562 } 563 564 private: 565 /// Creates a tuple type based on a list of Type 566 567 static bool unifyList( 568 const std::vector< ast::ptr< ast::Type > > & list1, 569 const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env, 570 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open 571 ) { 572 auto crnt1 = list1.begin(); 573 auto crnt2 = list2.begin(); 574 while ( crnt1 != list1.end() && crnt2 != list2.end() ) { 575 const ast::Type * t1 = *crnt1; 576 const ast::Type * t2 = *crnt2; 577 bool isTuple1 = Tuples::isTtype( t1 ); 578 bool isTuple2 = Tuples::isTtype( t2 ); 579 580 // assumes ttype must be last parameter 581 if ( isTuple1 && ! isTuple2 ) { 582 // combine entirety of list2, then unify 583 return unifyExact( 584 t1, tupleFromTypes( list2 ), env, need, have, open, 585 noWiden() ); 586 } else if ( ! isTuple1 && isTuple2 ) { 587 // combine entirety of list1, then unify 588 return unifyExact( 589 tupleFromTypes( list1 ), t2, env, need, have, open, 590 noWiden() ); 591 } 592 593 if ( ! unifyExact( 594 t1, t2, env, need, have, open, noWiden() ) 595 ) return false; 596 597 ++crnt1; ++crnt2; 598 } 599 600 if ( crnt1 != list1.end() ) { 601 // try unifying empty tuple type with ttype 602 const ast::Type * t1 = *crnt1; 603 if ( ! Tuples::isTtype( t1 ) ) return false; 604 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 605 // from Rob's code 606 return unifyExact( 607 t1, tupleFromTypes( list2 ), env, need, have, open, 608 noWiden() ); 609 } else if ( crnt2 != list2.end() ) { 610 // try unifying empty tuple with ttype 611 const ast::Type * t2 = *crnt2; 612 if ( ! Tuples::isTtype( t2 ) ) return false; 613 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 614 // from Rob's code 615 return unifyExact( 616 tupleFromTypes( list1 ), t2, env, need, have, open, 617 noWiden() ); 618 } 619 620 return true; 621 } 622 623 public: 624 void postvisit( const ast::TupleType * tuple ) { 625 auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 ); 626 if ( ! tuple2 ) return; 627 628 ast::Pass<TtypeExpander> expander{ tenv }; 629 630 const ast::Type * flat = tuple->accept( expander ); 631 const ast::Type * flat2 = tuple2->accept( expander ); 632 633 auto types = flatten( flat ); 634 auto types2 = flatten( flat2 ); 635 636 result = unifyList( types, types2, tenv, need, have, open ) 637 || tryToUnifyWithEnumValue(tuple, type2, tenv, need, have, open, noWiden()); 638 } 639 640 void postvisit( const ast::VarArgsType * vat) { 641 result = dynamic_cast< const ast::VarArgsType * >( type2 ) 642 || tryToUnifyWithEnumValue(vat, type2, tenv, need, have, open, noWiden()); 643 } 644 645 void postvisit( const ast::ZeroType * zt) { 646 result = dynamic_cast< const ast::ZeroType * >( type2 ) 647 || tryToUnifyWithEnumValue(zt, type2, tenv, need, have, open, noWiden()); 648 } 649 650 void postvisit( const ast::OneType * ot) { 651 result = dynamic_cast< const ast::OneType * >( type2 ) 652 || tryToUnifyWithEnumValue(ot, type2, tenv, need, have, open, noWiden()); 653 } 654 }; 655 656 // size_t Unify::traceId = Stats::Heap::new_stacktrace_id("Unify"); 657 658 bool unify( 659 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 660 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 661 ast::OpenVarSet & open 662 ) { 663 ast::ptr<ast::Type> common; 664 return unify( type1, type2, env, need, have, open, common ); 665 } 666 667 bool unify( 668 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 669 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 670 ast::OpenVarSet & open, ast::ptr<ast::Type> & common 671 ) { 672 ast::OpenVarSet closed; 673 // findOpenVars( type1, open, closed, need, have, FirstClosed ); 674 findOpenVars( type2, open, closed, need, have, env, FirstOpen ); 675 return unifyInexact( 676 type1, type2, env, need, have, open, WidenMode{ true, true }, common ); 677 } 678 679 bool unifyExact( 680 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 681 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 682 WidenMode widen 683 ) { 684 if ( type1->qualifiers != type2->qualifiers ) return false; 685 686 auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 ); 687 auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 ); 688 bool isopen1 = var1 && env.lookup(*var1); 689 bool isopen2 = var2 && env.lookup(*var2); 690 691 if ( isopen1 && isopen2 ) { 692 if ( var1->base->kind != var2->base->kind ) return false; 693 return env.bindVarToVar( 694 var1, var2, ast::TypeData{ var1->base->kind, var1->base->sized||var2->base->sized }, need, have, 695 open, widen ); 696 } else if ( isopen1 ) { 697 return env.bindVar( var1, type2, ast::TypeData{var1->base}, need, have, open, widen ); 698 } else if ( isopen2 ) { 699 return env.bindVar( var2, type1, ast::TypeData{var2->base}, need, have, open, widen ); 700 } else { 701 return ast::Pass<Unify>::read( 702 type1, type2, env, need, have, open, widen ); 703 } 704 } 705 706 bool unifyInexact( 707 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 708 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 709 const ast::OpenVarSet & open, WidenMode widen, 710 ast::ptr<ast::Type> & common 711 ) { 712 ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers; 713 714 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and 715 // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1 716 ast::Type * t1 = shallowCopy(type1.get()); 717 ast::Type * t2 = shallowCopy(type2.get()); 718 t1->qualifiers = {}; 719 t2->qualifiers = {}; 720 ast::ptr< ast::Type > t1_(t1); 721 ast::ptr< ast::Type > t2_(t2); 722 723 if ( unifyExact( t1, t2, env, need, have, open, widen ) ) { 724 // if exact unification on unqualified types, try to merge qualifiers 725 if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) { 726 t1->qualifiers = q1 | q2; 727 common = t1; 728 return true; 729 } else { 730 return false; 731 } 732 733 } else if (( common = commonType( t1, t2, env, need, have, open, widen ))) { 734 // no exact unification, but common type 735 auto c = shallowCopy(common.get()); 736 c->qualifiers = q1 | q2; 737 common = c; 592 593 if ( !unifyExact( 594 t1, t2, env, need, have, open, noWiden() ) 595 ) return false; 596 597 ++crnt1; ++crnt2; 598 } 599 600 if ( crnt1 != list1.end() ) { 601 // try unifying empty tuple type with ttype 602 const ast::Type * t1 = *crnt1; 603 if ( !Tuples::isTtype( t1 ) ) return false; 604 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 605 // from Rob's code 606 return unifyExact( 607 t1, tupleFromTypes( list2 ), env, need, have, open, 608 noWiden() ); 609 } else if ( crnt2 != list2.end() ) { 610 // try unifying empty tuple with ttype 611 const ast::Type * t2 = *crnt2; 612 if ( !Tuples::isTtype( t2 ) ) return false; 613 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 614 // from Rob's code 615 return unifyExact( 616 tupleFromTypes( list1 ), t2, env, need, have, open, 617 noWiden() ); 618 } 619 620 return true; 621 } 622 623 public: 624 void postvisit( const ast::TupleType * tuple ) { 625 auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 ); 626 if ( ! tuple2 ) return; 627 628 ast::Pass<TtypeExpander> expander{ tenv }; 629 630 const ast::Type * flat = tuple->accept( expander ); 631 const ast::Type * flat2 = tuple2->accept( expander ); 632 633 auto types = flatten( flat ); 634 auto types2 = flatten( flat2 ); 635 636 result = unifyList( types, types2, tenv, need, have, open ) 637 || tryToUnifyWithEnumValue(tuple, type2, tenv, need, have, open, noWiden()); 638 } 639 640 void postvisit( const ast::VarArgsType * vat) { 641 result = dynamic_cast< const ast::VarArgsType * >( type2 ) 642 || tryToUnifyWithEnumValue(vat, type2, tenv, need, have, open, noWiden()); 643 } 644 645 void postvisit( const ast::ZeroType * zt) { 646 result = dynamic_cast< const ast::ZeroType * >( type2 ) 647 || tryToUnifyWithEnumValue(zt, type2, tenv, need, have, open, noWiden()); 648 } 649 650 void postvisit( const ast::OneType * ot) { 651 result = dynamic_cast< const ast::OneType * >( type2 ) 652 || tryToUnifyWithEnumValue(ot, type2, tenv, need, have, open, noWiden()); 653 } 654 }; 655 656 // size_t Unify::traceId = Stats::Heap::new_stacktrace_id("Unify"); 657 658 bool unify( 659 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 660 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 661 ast::OpenVarSet & open 662 ) { 663 ast::ptr<ast::Type> common; 664 return unify( type1, type2, env, need, have, open, common ); 665 } 666 667 bool unify( 668 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 669 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 670 ast::OpenVarSet & open, ast::ptr<ast::Type> & common 671 ) { 672 ast::OpenVarSet closed; 673 // findOpenVars( type1, open, closed, need, have, FirstClosed ); 674 findOpenVars( type2, open, closed, need, have, env, FirstOpen ); 675 return unifyInexact( 676 type1, type2, env, need, have, open, WidenMode{ true, true }, common ); 677 } 678 679 bool unifyExact( 680 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 681 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 682 WidenMode widen 683 ) { 684 if ( type1->qualifiers != type2->qualifiers ) return false; 685 686 auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 ); 687 auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 ); 688 bool isopen1 = var1 && env.lookup(*var1); 689 bool isopen2 = var2 && env.lookup(*var2); 690 691 if ( isopen1 && isopen2 ) { 692 if ( var1->base->kind != var2->base->kind ) return false; 693 return env.bindVarToVar( 694 var1, var2, ast::TypeData{ var1->base->kind, var1->base->sized||var2->base->sized }, need, have, 695 open, widen ); 696 } else if ( isopen1 ) { 697 return env.bindVar( var1, type2, ast::TypeData{var1->base}, need, have, open, widen ); 698 } else if ( isopen2 ) { 699 return env.bindVar( var2, type1, ast::TypeData{var2->base}, need, have, open, widen ); 700 } else { 701 return ast::Pass<Unify>::read( 702 type1, type2, env, need, have, open, widen ); 703 } 704 } 705 706 bool unifyInexact( 707 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 708 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 709 const ast::OpenVarSet & open, WidenMode widen, 710 ast::ptr<ast::Type> & common 711 ) { 712 ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers; 713 714 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and 715 // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1 716 ast::Type * t1 = shallowCopy(type1.get()); 717 ast::Type * t2 = shallowCopy(type2.get()); 718 t1->qualifiers = {}; 719 t2->qualifiers = {}; 720 ast::ptr< ast::Type > t1_(t1); 721 ast::ptr< ast::Type > t2_(t2); 722 723 if ( unifyExact( t1, t2, env, need, have, open, widen ) ) { 724 // if exact unification on unqualified types, try to merge qualifiers 725 if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) { 726 t1->qualifiers = q1 | q2; 727 common = t1; 738 728 return true; 739 729 } else { 740 730 return false; 741 731 } 742 } 743 744 ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) { 745 if ( func->returns.empty() ) return new ast::VoidType{}; 746 if ( func->returns.size() == 1 ) return func->returns[0]; 747 748 std::vector<ast::ptr<ast::Type>> tys; 749 for ( const auto & decl : func->returns ) { 750 tys.emplace_back( decl ); 751 } 752 return new ast::TupleType{ std::move(tys) }; 753 } 732 } else if (( common = commonType( t1, t2, env, need, have, open, widen ))) { 733 // no exact unification, but common type 734 auto c = shallowCopy(common.get()); 735 c->qualifiers = q1 | q2; 736 common = c; 737 return true; 738 } else { 739 return false; 740 } 741 } 742 743 ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) { 744 if ( func->returns.empty() ) return new ast::VoidType(); 745 if ( func->returns.size() == 1 ) return func->returns[0]; 746 747 std::vector<ast::ptr<ast::Type>> tys; 748 for ( const auto & decl : func->returns ) { 749 tys.emplace_back( decl ); 750 } 751 return new ast::TupleType( std::move(tys) ); 752 } 753 754 754 } // namespace ResolvExpr 755 755
Note: See TracChangeset
for help on using the changeset viewer.