- Timestamp:
- Jun 4, 2019, 2:03:25 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 1867c96, bc4bea8, de8dfac2
- Parents:
- 0e315a5 (diff), 4ae2364 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - Location:
- src
- Files:
-
- 17 edited
Legend:
- Unmodified
- Added
- Removed
-
src/AST/Decl.hpp
r0e315a5 r98a8290 102 102 ptr<Expr> bitfieldWidth; 103 103 104 ObjectDecl( const CodeLocation & loc, const std::string & name, const Type * type, Init * init = nullptr, 105 Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::C, Expr * bitWd = nullptr, 106 std::vector< ptr<Attribute> > && attrs = {}, Function::Specs fs = {}) 104 ObjectDecl( const CodeLocation & loc, const std::string & name, const Type * type, 105 Init * init = nullptr, Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::C, 106 Expr * bitWd = nullptr, std::vector< ptr<Attribute> > && attrs = {}, 107 Function::Specs fs = {} ) 107 108 : DeclWithType( loc, name, storage, linkage, std::move(attrs), fs ), type( type ), 108 109 init( init ), bitfieldWidth( bitWd ) {} -
src/AST/Node.hpp
r0e315a5 r98a8290 10 10 // Created On : Wed May 8 10:27:04 2019 11 11 // Last Modified By : Andrew Beach 12 // Last Modified On : Thu May 23 16:00:00 201913 // Update Count : 412 // Last Modified On : Mon Jun 3 13:26:00 2019 13 // Update Count : 5 14 14 // 15 15 … … 107 107 ptr_base() : node(nullptr) {} 108 108 ptr_base( const node_t * n ) : node(n) { if( node ) _inc(node); } 109 ~ptr_base() { if( node ) _dec(node);}109 ~ptr_base() { if( node ) { auto tmp = node; node = nullptr; _dec(tmp); } } 110 110 111 111 ptr_base( const ptr_base & o ) : node(o.node) { … … 127 127 template<typename o_node_t> 128 128 ptr_base & operator=( const o_node_t * node ) { 129 assign( node ? strict_dynamic_cast<const node_t *>(node) : nullptr);129 assign( strict_dynamic_cast<const node_t *, nullptr>(node) ); 130 130 return *this; 131 131 } -
src/AST/Type.hpp
r0e315a5 r98a8290 48 48 49 49 Type * set_const( bool v ) { qualifiers.is_const = v; return this; } 50 Type * set_volatile( bool v ) { qualifiers.is_volatile = v; return this; } 50 51 Type * set_restrict( bool v ) { qualifiers.is_restrict = v; return this; } 51 52 Type * set_lvalue( bool v ) { qualifiers.is_lvalue = v; return this; } -
src/AST/TypeEnvironment.cpp
r0e315a5 r98a8290 46 46 } 47 47 48 void print( std::ostream & out, const OpenVarSet & open Vars, Indenter indent ) {48 void print( std::ostream & out, const OpenVarSet & open, Indenter indent ) { 49 49 out << indent; 50 50 bool first = true; 51 for ( const auto & i : open Vars) {51 for ( const auto & i : open ) { 52 52 if ( first ) { first = false; } else { out << ' '; } 53 53 out << i.first << "(" << i.second << ")"; … … 166 166 167 167 bool TypeEnvironment::combine( 168 const TypeEnvironment & o, OpenVarSet & open Vars, const SymbolTable & symtab ) {168 const TypeEnvironment & o, OpenVarSet & open, const SymbolTable & symtab ) { 169 169 // short-circuit easy cases 170 170 if ( o.empty() ) return true; … … 189 189 EqvClass & r = *rt; 190 190 // merge bindings 191 if ( ! mergeBound( r, c, open Vars, symtab ) ) return false;191 if ( ! mergeBound( r, c, open, symtab ) ) return false; 192 192 // merge previous unbound variables into this class, checking occurs if needed 193 193 if ( r.bound ) for ( const auto & u : c.vars ) { … … 204 204 } else if ( st != rt ) { 205 205 // bound, but not to the same class 206 if ( ! mergeClasses( rt, st, open Vars, symtab ) ) return false;206 if ( ! mergeClasses( rt, st, open, symtab ) ) return false; 207 207 } // ignore bound into the same class 208 208 } … … 216 216 } 217 217 218 void TypeEnvironment::extractOpenVars( OpenVarSet & open Vars) const {218 void TypeEnvironment::extractOpenVars( OpenVarSet & open ) const { 219 219 for ( const auto & clz : env ) { 220 220 for ( const auto & var : clz.vars ) { 221 open Vars[ var ] = clz.data;222 } 223 } 224 } 225 226 void TypeEnvironment::addActual( const TypeEnvironment & actualEnv, OpenVarSet & open Vars) {221 open[ var ] = clz.data; 222 } 223 } 224 } 225 226 void TypeEnvironment::addActual( const TypeEnvironment & actualEnv, OpenVarSet & open ) { 227 227 for ( const auto & clz : actualEnv ) { 228 228 EqvClass c = clz; 229 229 c.allowWidening = false; 230 230 for ( const auto & var : c.vars ) { 231 open Vars[ var ] = c.data;231 open[ var ] = c.data; 232 232 } 233 233 env.emplace_back( std::move(c) ); … … 268 268 bool TypeEnvironment::bindVar( 269 269 const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, 270 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 271 WidenMode widenMode, const SymbolTable & symtab ) { 270 AssertionSet & need, AssertionSet & have, const OpenVarSet & open, WidenMode widen, 271 const SymbolTable & symtab 272 ) { 272 273 // remove references from bound type, so that type variables can only bind to value types 273 bindTo= bindTo->stripReferences();274 auto tyvar = open Vars.find( typeInst->name );275 assert( tyvar != open Vars.end() );276 if ( ! tyVarCompatible( tyvar->second, bindTo) ) return false;277 if ( occurs( bindTo, typeInst->name, *this ) ) return false;274 ptr<Type> target = bindTo->stripReferences(); 275 auto tyvar = open.find( typeInst->name ); 276 assert( tyvar != open.end() ); 277 if ( ! tyVarCompatible( tyvar->second, target ) ) return false; 278 if ( occurs( target, typeInst->name, *this ) ) return false; 278 279 279 280 auto it = internal_lookup( typeInst->name ); … … 282 283 // attempt to unify equivalence class type with type to bind to. 283 284 // equivalence class type has stripped qualifiers which must be restored 284 const Type * common = nullptr;285 ptr<Type> common; 285 286 ptr<Type> newType = it->bound; 286 287 newType.get_and_mutate()->qualifiers = typeInst->qualifiers; 287 288 if ( unifyInexact( 288 newType, bindTo, *this, need, have, openVars,289 widen Mode& WidenMode{ it->allowWidening, true }, symtab, common ) ) {289 newType, target, *this, need, have, open, 290 widen & WidenMode{ it->allowWidening, true }, symtab, common ) ) { 290 291 if ( common ) { 291 it->bound = common;292 it->bound = std::move(common); 292 293 clear_qualifiers( it->bound ); 293 294 } 294 295 } else return false; 295 296 } else { 296 it->bound = bindTo;297 it->bound = std::move(target); 297 298 clear_qualifiers( it->bound ); 298 it->allowWidening = widen Mode.widenFirst && widenMode.widenSecond;299 it->allowWidening = widen.first && widen.second; 299 300 } 300 301 } else { 301 302 env.emplace_back( 302 typeInst->name, bindTo, widenMode.widenFirst && widenMode.widenSecond, data );303 typeInst->name, target, widen.first && widen.second, data ); 303 304 } 304 305 return true; … … 307 308 bool TypeEnvironment::bindVarToVar( 308 309 const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, 309 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 310 WidenMode widenMode, const SymbolTable & symtab ) { 310 AssertionSet & need, AssertionSet & have, const OpenVarSet & open, 311 WidenMode widen, const SymbolTable & symtab 312 ) { 311 313 auto c1 = internal_lookup( var1->name ); 312 314 auto c2 = internal_lookup( var2->name ); … … 314 316 // exit early if variables already bound together 315 317 if ( c1 != env.end() && c1 == c2 ) { 316 c1->allowWidening &= widen Mode;318 c1->allowWidening &= widen; 317 319 return true; 318 320 } … … 327 329 type1 = c1->bound; 328 330 } 329 widen1 = widen Mode.widenFirst && c1->allowWidening;331 widen1 = widen.first && c1->allowWidening; 330 332 } 331 333 if ( c2 != env.end() ) { … … 334 336 type2 = c2->bound; 335 337 } 336 widen2 = widen Mode.widenSecond && c2->allowWidening;338 widen2 = widen.second && c2->allowWidening; 337 339 } 338 340 … … 341 343 ptr<Type> newType1{ type1 }, newType2{ type2 }; 342 344 WidenMode newWidenMode{ widen1, widen2 }; 343 const Type * common = nullptr;345 ptr<Type> common; 344 346 345 347 if ( unifyInexact( 346 newType1, newType2, *this, need, have, open Vars, newWidenMode, symtab, common ) ) {348 newType1, newType2, *this, need, have, open, newWidenMode, symtab, common ) ) { 347 349 c1->vars.insert( c2->vars.begin(), c2->vars.end() ); 348 350 c1->allowWidening = widen1 && widen2; 349 351 if ( common ) { 350 c1->bound = common;352 c1->bound = std::move(common); 351 353 clear_qualifiers( c1->bound ); 352 354 } … … 395 397 396 398 bool TypeEnvironment::mergeBound( 397 EqvClass & to, const EqvClass & from, OpenVarSet & open Vars, const SymbolTable & symtab ) {399 EqvClass & to, const EqvClass & from, OpenVarSet & open, const SymbolTable & symtab ) { 398 400 if ( from.bound ) { 399 401 if ( to.bound ) { 400 402 // attempt to unify bound types 401 403 ptr<Type> toType{ to.bound }, fromType{ from.bound }; 402 WidenMode widen Mode{ to.allowWidening, from.allowWidening };403 const Type * common = nullptr;404 WidenMode widen{ to.allowWidening, from.allowWidening }; 405 ptr<Type> common; 404 406 AssertionSet need, have; 405 407 406 408 if ( unifyInexact( 407 toType, fromType, *this, need, have, open Vars, widenMode, symtab, common ) ) {409 toType, fromType, *this, need, have, open, widen, symtab, common ) ) { 408 410 // unifies, set common type if necessary 409 411 if ( common ) { 410 to.bound = common;412 to.bound = std::move(common); 411 413 clear_qualifiers( to.bound ); 412 414 } … … 423 425 424 426 bool TypeEnvironment::mergeClasses( 425 ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars,426 const SymbolTable & symtab) {427 ClassList::iterator to, ClassList::iterator from, OpenVarSet & open, const SymbolTable & symtab 428 ) { 427 429 EqvClass & r = *to, & s = *from; 428 430 429 431 // ensure bounds match 430 if ( ! mergeBound( r, s, open Vars, symtab ) ) return false;432 if ( ! mergeBound( r, s, open, symtab ) ) return false; 431 433 432 434 // check safely bindable -
src/AST/TypeEnvironment.hpp
r0e315a5 r98a8290 178 178 const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, 179 179 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 180 ResolvExpr::WidenMode widen Mode, const SymbolTable & symtab );180 ResolvExpr::WidenMode widen, const SymbolTable & symtab ); 181 181 182 182 /// Binds the type classes represented by `var1` and `var2` together; will add one or both … … 185 185 const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, 186 186 AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, 187 ResolvExpr::WidenMode widen Mode, const SymbolTable & symtab );187 ResolvExpr::WidenMode widen, const SymbolTable & symtab ); 188 188 189 189 /// Disallows widening for all bindings in the environment -
src/AST/TypeSubstitution.cpp
r0e315a5 r98a8290 9 9 // Author : Richard C. Bilson 10 10 // Created On : Mon May 18 07:44:20 2015 11 // Last Modified By : Peter A. Buhr12 // Last Modified On : Thu Mar 16 15:54:35201713 // Update Count : 411 // Last Modified By : Andrew Beach 12 // Last Modified On : Mon Jun 3 13:26:00 2017 13 // Update Count : 5 14 14 // 15 15 … … 26 26 } 27 27 28 TypeSubstitution::~TypeSubstitution() { 29 for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) { 30 delete( i->second ); 31 } 32 for ( VarEnvType::iterator i = varEnv.begin(); i != varEnv.end(); ++i ) { 33 delete( i->second ); 34 } 35 } 28 TypeSubstitution::~TypeSubstitution() {} 36 29 37 30 TypeSubstitution &TypeSubstitution::operator=( const TypeSubstitution &other ) { -
src/AST/porting.md
r0e315a5 r98a8290 291 291 * moved to be helper function in `TypeEnvironment.cpp` (its only use) 292 292 293 `WidenMode` 294 * changed `widenFirst`, `widenSecond` => `first`, `second` 295 * changed `WidenMode widenMode` => `WidenMode widen` 296 293 297 [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes 294 298 -
src/ResolvExpr/CommonType.cc
r0e315a5 r98a8290 176 176 } 177 177 178 const ast::Type * commonType( 179 const ast::Type * type1, const ast::Type * type2, WidenMode widen, 180 const ast::SymbolTable & symtab, ast::TypeEnvironment & env, 181 const ast::OpenVarSet & open ) { 182 #warning unimplemented 183 (void)type1; (void)type2; (void)widen; (void)symtab; (void)env; (void)open; 184 assert(false); 185 return nullptr; 186 } 187 178 188 // GENERATED START, DO NOT EDIT 179 189 // GENERATED BY BasicTypes-gen.cc -
src/ResolvExpr/FindOpenVars.cc
r0e315a5 r98a8290 93 93 common_action( tupleType ); 94 94 } 95 96 void findOpenVars( 97 const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed, 98 ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen ) { 99 #warning unimplemented 100 (void)type; (void)open; (void)closed; (void)need; (void)have; (void)firstIsOpen; 101 assert(false); 102 } 95 103 } // namespace ResolvExpr 96 104 -
src/ResolvExpr/FindOpenVars.h
r0e315a5 r98a8290 16 16 #pragma once 17 17 18 #include "AST/TypeEnvironment.hpp" // for AssertionSet, OpenVarSet 18 19 #include "ResolvExpr/TypeEnvironment.h" // for AssertionSet, OpenVarSet 19 20 20 21 class Type; 22 namespace ast { 23 class Type; 24 } 21 25 22 26 namespace ResolvExpr { 23 27 // Updates open and closed variables and their associated assertions 24 28 void findOpenVars( Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); 29 30 enum FirstMode { FirstClosed, FirstOpen }; 31 32 // Updates open and closed variables and their associated assertions 33 void findOpenVars( 34 const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed, 35 ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen ); 25 36 } // namespace ResolvExpr 26 37 -
src/ResolvExpr/TypeEnvironment.cc
r0e315a5 r98a8290 205 205 // attempt to unify bound types 206 206 std::unique_ptr<Type> toType{ to.type->clone() }, fromType{ from.type->clone() }; 207 WidenMode widen Mode{ to.allowWidening, from.allowWidening };207 WidenMode widen{ to.allowWidening, from.allowWidening }; 208 208 Type* common = nullptr; 209 209 AssertionSet need, have; 210 if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widen Mode, indexer, common ) ) {210 if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widen, indexer, common ) ) { 211 211 // unifies, set common type if necessary 212 212 if ( common ) { … … 343 343 } 344 344 345 bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen Mode, const SymTab::Indexer &indexer ) {345 bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { 346 346 347 347 // remove references from other, so that type variables can only bind to value types … … 362 362 std::unique_ptr< Type > newType( curClass->type->clone() ); 363 363 newType->get_qualifiers() = typeInst->get_qualifiers(); 364 if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widen Mode& WidenMode( curClass->allowWidening, true ), indexer, common ) ) {364 if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widen & WidenMode( curClass->allowWidening, true ), indexer, common ) ) { 365 365 if ( common ) { 366 366 common->get_qualifiers() = Type::Qualifiers{}; … … 372 372 newType->get_qualifiers() = Type::Qualifiers{}; 373 373 curClass->set_type( newType ); 374 curClass->allowWidening = widen Mode.widenFirst && widenMode.widenSecond;374 curClass->allowWidening = widen.first && widen.second; 375 375 } // if 376 376 } else { … … 379 379 newClass.type = bindTo->clone(); 380 380 newClass.type->get_qualifiers() = Type::Qualifiers(); 381 newClass.allowWidening = widen Mode.widenFirst && widenMode.widenSecond;381 newClass.allowWidening = widen.first && widen.second; 382 382 newClass.data = data; 383 383 env.push_back( std::move(newClass) ); … … 388 388 bool TypeEnvironment::bindVarToVar( TypeInstType *var1, TypeInstType *var2, 389 389 TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, 390 const OpenVarSet &openVars, WidenMode widen Mode, const SymTab::Indexer &indexer ) {390 const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { 391 391 392 392 auto class1 = internal_lookup( var1->get_name() ); … … 395 395 // exit early if variables already bound together 396 396 if ( class1 != env.end() && class1 == class2 ) { 397 class1->allowWidening &= widen Mode;397 class1->allowWidening &= widen; 398 398 return true; 399 399 } … … 408 408 type1 = class1->type; 409 409 } // if 410 widen1 = widen Mode.widenFirst && class1->allowWidening;410 widen1 = widen.first && class1->allowWidening; 411 411 } // if 412 412 if ( class2 != env.end() ) { … … 415 415 type2 = class2->type; 416 416 } // if 417 widen2 = widen Mode.widenSecond && class2->allowWidening;417 widen2 = widen.second && class2->allowWidening; 418 418 } // if 419 419 -
src/ResolvExpr/TypeEnvironment.h
r0e315a5 r98a8290 136 136 /// Binds the type class represented by `typeInst` to the type `bindTo`; will add 137 137 /// the class if needed. Returns false on failure. 138 bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen Mode, const SymTab::Indexer &indexer );138 bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); 139 139 140 140 /// Binds the type classes represented by `var1` and `var2` together; will add 141 141 /// one or both classes if needed. Returns false on failure. 142 bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen Mode, const SymTab::Indexer &indexer );142 bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); 143 143 144 144 /// Disallows widening for all bindings in the environment -
src/ResolvExpr/Unify.cc
r0e315a5 r98a8290 14 14 // 15 15 16 #include "Unify.h" 17 16 18 #include <cassert> // for assertf, assert 17 19 #include <iterator> // for back_insert_iterator, back_inserter … … 23 25 #include <vector> 24 26 27 #include "AST/Decl.hpp" 25 28 #include "AST/Node.hpp" 29 #include "AST/Pass.hpp" 26 30 #include "AST/Type.hpp" 27 31 #include "AST/TypeEnvironment.hpp" … … 37 41 #include "Tuples/Tuples.h" // for isTtype 38 42 #include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet 39 #include "Unify.h"40 43 #include "typeops.h" // for flatten, occurs, commonType 44 45 namespace ast { 46 class SymbolTable; 47 } 41 48 42 49 namespace SymTab { … … 48 55 namespace ResolvExpr { 49 56 50 struct Unify : public WithShortCircuiting {51 Unify ( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );57 struct Unify_old : public WithShortCircuiting { 58 Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); 52 59 53 60 bool get_result() const { return result; } … … 81 88 AssertionSet &haveAssertions; 82 89 const OpenVarSet &openVars; 83 WidenMode widen Mode;90 WidenMode widen; 84 91 const SymTab::Indexer &indexer; 85 92 }; … … 87 94 /// Attempts an inexact unification of type1 and type2. 88 95 /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers) 89 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ); 90 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); 96 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ); 97 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); 98 99 bool unifyExact( 100 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 101 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 102 WidenMode widen, const ast::SymbolTable & symtab ); 91 103 92 104 bool typesCompatible( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) { … … 112 124 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, 113 125 const ast::TypeEnvironment & env ) { 114 #warning unimplemented 115 assert((first, second, symtab, env, false)); 116 return false; 126 ast::TypeEnvironment newEnv; 127 ast::OpenVarSet open, closed; 128 ast::AssertionSet need, have; 129 130 ast::ptr<ast::Type> newFirst{ first }, newSecond{ second }; 131 env.apply( newFirst ); 132 env.apply( newSecond ); 133 134 findOpenVars( newFirst, open, closed, need, have, FirstClosed ); 135 findOpenVars( newSecond, open, closed, need, have, FirstOpen ); 136 137 return unifyExact( 138 newFirst, newSecond, newEnv, need, have, open, WidenMode{ false, false }, symtab ); 117 139 } 118 140 … … 144 166 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, 145 167 const ast::TypeEnvironment & env ) { 146 #warning unimplemented 147 assert((first, second, symtab, env, false)); 148 return false; 168 ast::TypeEnvironment newEnv; 169 ast::OpenVarSet open; 170 ast::AssertionSet need, have; 171 172 ast::ptr<ast::Type> newFirst{ first }, newSecond{ second }; 173 env.apply( newFirst ); 174 env.apply( newSecond ); 175 clear_qualifiers( newFirst ); 176 clear_qualifiers( newSecond ); 177 178 return unifyExact( 179 newFirst, newSecond, newEnv, need, have, open, WidenMode{ false, false }, symtab ); 149 180 } 150 181 … … 171 202 } 172 203 173 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen Mode, const SymTab::Indexer &indexer ) {204 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { 174 205 #ifdef DEBUG 175 206 TypeEnvironment debugEnv( env ); … … 198 229 result = env.bindVarToVar( 199 230 var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions, 200 haveAssertions, openVars, widen Mode, indexer );231 haveAssertions, openVars, widen, indexer ); 201 232 } 202 233 } else if ( isopen1 ) { 203 result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen Mode, indexer );204 } else if ( isopen2 ) { // TODO: swap widen Modevalues in call, since type positions are flipped?205 result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen Mode, indexer );234 result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen, indexer ); 235 } else if ( isopen2 ) { // TODO: swap widen values in call, since type positions are flipped? 236 result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen, indexer ); 206 237 } else { 207 PassVisitor<Unify > comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer );238 PassVisitor<Unify_old> comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer ); 208 239 type1->accept( comparator ); 209 240 result = comparator.pass.get_result(); … … 230 261 } 231 262 232 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen Mode, const SymTab::Indexer &indexer, Type *&common ) {263 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) { 233 264 Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers(); 234 265 type1->get_qualifiers() = Type::Qualifiers(); … … 242 273 std::cerr << std::endl; 243 274 #endif 244 if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen Mode, indexer ) ) {275 if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) { 245 276 #ifdef DEBUG 246 277 std::cerr << "unifyInexact: no exact unification found" << std::endl; 247 278 #endif 248 if ( ( common = commonType( type1, type2, widen Mode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) {279 if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) { 249 280 common->get_qualifiers() = tq1 | tq2; 250 281 #ifdef DEBUG … … 262 293 } else { 263 294 if ( tq1 != tq2 ) { 264 if ( ( tq1 > tq2 || widen Mode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) {295 if ( ( tq1 > tq2 || widen.first ) && ( tq2 > tq1 || widen.second ) ) { 265 296 common = type1->clone(); 266 297 common->get_qualifiers() = tq1 | tq2; … … 280 311 } 281 312 282 bool unifyInexact( 283 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 284 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & openVars, 285 WidenMode widenMode, const ast::SymbolTable & symtab, const ast::Type *& common ) { 286 #warning unimplemented 287 assert((type1, type2, env, need, have, openVars, widenMode, symtab, common, false)); 288 return false; 289 } 290 291 Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) 292 : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) { 293 } 294 295 void Unify::postvisit( __attribute__((unused)) VoidType *voidType) { 313 Unify_old::Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) 314 : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widen( widen ), indexer( indexer ) { 315 } 316 317 void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) { 296 318 result = dynamic_cast< VoidType* >( type2 ); 297 319 } 298 320 299 void Unify ::postvisit(BasicType *basicType) {321 void Unify_old::postvisit(BasicType *basicType) { 300 322 if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) { 301 323 result = basicType->get_kind() == otherBasic->get_kind(); … … 325 347 } 326 348 327 void Unify ::postvisit(PointerType *pointerType) {349 void Unify_old::postvisit(PointerType *pointerType) { 328 350 if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) { 329 351 result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); … … 333 355 } 334 356 335 void Unify ::postvisit(ReferenceType *refType) {357 void Unify_old::postvisit(ReferenceType *refType) { 336 358 if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) { 337 359 result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); … … 341 363 } 342 364 343 void Unify ::postvisit(ArrayType *arrayType) {365 void Unify_old::postvisit(ArrayType *arrayType) { 344 366 ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 ); 345 367 // to unify, array types must both be VLA or both not VLA … … 421 443 /// If this isn't done then argument lists can have wildly different 422 444 /// size and structure, when they should be compatible. 423 struct TtypeExpander : public WithShortCircuiting {445 struct TtypeExpander_old : public WithShortCircuiting { 424 446 TypeEnvironment & tenv; 425 TtypeExpander ( TypeEnvironment & tenv ) : tenv( tenv ) {}447 TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {} 426 448 void premutate( TypeInstType * ) { visit_children = false; } 427 449 Type * postmutate( TypeInstType * typeInst ) { … … 442 464 dst.clear(); 443 465 for ( DeclarationWithType * dcl : src ) { 444 PassVisitor<TtypeExpander > expander( env );466 PassVisitor<TtypeExpander_old> expander( env ); 445 467 dcl->acceptMutator( expander ); 446 468 std::list< Type * > types; … … 457 479 } 458 480 459 void Unify ::postvisit(FunctionType *functionType) {481 void Unify_old::postvisit(FunctionType *functionType) { 460 482 FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 ); 461 483 if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) { … … 468 490 469 491 // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors 470 if ( (flatFunc->parameters.size() == flatOther->parameters.size() && flatFunc->returnVals.size() == flatOther->returnVals.size()) || flatFunc->isTtype() || flatOther->isTtype() ) { 492 if ( 493 (flatFunc->parameters.size() == flatOther->parameters.size() && 494 flatFunc->returnVals.size() == flatOther->returnVals.size()) 495 || flatFunc->isTtype() 496 || flatOther->isTtype() 497 ) { 471 498 if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { 472 499 if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { … … 484 511 485 512 template< typename RefType > 486 void Unify ::handleRefType( RefType *inst, Type *other ) {513 void Unify_old::handleRefType( RefType *inst, Type *other ) { 487 514 // check that other type is compatible and named the same 488 515 RefType *otherStruct = dynamic_cast< RefType* >( other ); … … 491 518 492 519 template< typename RefType > 493 void Unify ::handleGenericRefType( RefType *inst, Type *other ) {520 void Unify_old::handleGenericRefType( RefType *inst, Type *other ) { 494 521 // Check that other type is compatible and named the same 495 522 handleRefType( inst, other ); … … 559 586 } 560 587 561 void Unify ::postvisit(StructInstType *structInst) {588 void Unify_old::postvisit(StructInstType *structInst) { 562 589 handleGenericRefType( structInst, type2 ); 563 590 } 564 591 565 void Unify ::postvisit(UnionInstType *unionInst) {592 void Unify_old::postvisit(UnionInstType *unionInst) { 566 593 handleGenericRefType( unionInst, type2 ); 567 594 } 568 595 569 void Unify ::postvisit(EnumInstType *enumInst) {596 void Unify_old::postvisit(EnumInstType *enumInst) { 570 597 handleRefType( enumInst, type2 ); 571 598 } 572 599 573 void Unify ::postvisit(TraitInstType *contextInst) {600 void Unify_old::postvisit(TraitInstType *contextInst) { 574 601 handleRefType( contextInst, type2 ); 575 602 } 576 603 577 void Unify ::postvisit(TypeInstType *typeInst) {604 void Unify_old::postvisit(TypeInstType *typeInst) { 578 605 assert( openVars.find( typeInst->get_name() ) == openVars.end() ); 579 606 TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 ); … … 630 657 } 631 658 632 void Unify ::postvisit(TupleType *tupleType) {659 void Unify_old::postvisit(TupleType *tupleType) { 633 660 if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) { 634 661 std::unique_ptr<TupleType> flat1( tupleType->clone() ); … … 636 663 std::list<Type *> types1, types2; 637 664 638 PassVisitor<TtypeExpander > expander( env );665 PassVisitor<TtypeExpander_old> expander( env ); 639 666 flat1->acceptMutator( expander ); 640 667 flat2->acceptMutator( expander ); … … 647 674 } 648 675 649 void Unify ::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) {676 void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) { 650 677 result = dynamic_cast< VarArgsType* >( type2 ); 651 678 } 652 679 653 void Unify ::postvisit( __attribute__((unused)) ZeroType *zeroType ) {680 void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) { 654 681 result = dynamic_cast< ZeroType* >( type2 ); 655 682 } 656 683 657 void Unify ::postvisit( __attribute__((unused)) OneType *oneType ) {684 void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) { 658 685 result = dynamic_cast< OneType* >( type2 ); 659 686 } … … 673 700 } 674 701 702 class Unify_new : public ast::WithShortCircuiting { 703 const ast::Type * type2; 704 ast::TypeEnvironment & tenv; 705 ast::AssertionSet & need; 706 ast::AssertionSet & have; 707 const ast::OpenVarSet & open; 708 WidenMode widen; 709 const ast::SymbolTable & symtab; 710 public: 711 bool result; 712 713 Unify_new( 714 const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need, 715 ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen, 716 const ast::SymbolTable & symtab ) 717 : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen), 718 symtab(symtab), result(false) {} 719 720 void previsit( const ast::Node * ) { visit_children = false; } 721 722 void previsit( const ast::VoidType * ) { 723 visit_children = false; 724 result = dynamic_cast< const ast::VoidType * >( type2 ); 725 } 726 727 void previsit( const ast::BasicType * basic ) { 728 visit_children = false; 729 if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) { 730 result = basic->kind == basic2->kind; 731 } 732 } 733 734 void previsit( const ast::PointerType * pointer ) { 735 visit_children = false; 736 if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) { 737 result = unifyExact( 738 pointer->base, pointer2->base, tenv, need, have, open, 739 WidenMode{ false, false }, symtab ); 740 } 741 } 742 743 void previsit( const ast::ArrayType * array ) { 744 visit_children = false; 745 auto array2 = dynamic_cast< const ast::ArrayType * >( type2 ); 746 if ( ! array2 ) return; 747 748 // to unify, array types must both be VLA or both not VLA and both must have a 749 // dimension expression or not have a dimension 750 if ( array->isVarLen != array2->isVarLen ) return; 751 if ( ! array->isVarLen && ! array2->isVarLen 752 && array->dimension && array2->dimension ) { 753 auto ce1 = array->dimension.as< ast::ConstantExpr >(); 754 auto ce2 = array2->dimension.as< ast::ConstantExpr >(); 755 756 // see C11 Reference Manual 6.7.6.2.6 757 // two array types with size specifiers that are integer constant expressions are 758 // compatible if both size specifiers have the same constant value 759 if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return; 760 } 761 762 result = unifyExact( 763 array->base, array2->base, tenv, need, have, open, WidenMode{ false, false }, 764 symtab ); 765 } 766 767 void previsit( const ast::ReferenceType * ref ) { 768 visit_children = false; 769 if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) { 770 result = unifyExact( 771 ref->base, ref2->base, tenv, need, have, open, WidenMode{ false, false }, 772 symtab ); 773 } 774 } 775 776 private: 777 /// Replaces ttype variables with their bound types. 778 /// If this isn't done when satifying ttype assertions, then argument lists can have 779 /// different size and structure when they should be compatible. 780 struct TtypeExpander_new : public ast::WithShortCircuiting { 781 ast::TypeEnvironment & tenv; 782 783 TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {} 784 785 const ast::Type * postmutate( const ast::TypeInstType * typeInst ) { 786 if ( const ast::EqvClass * clz = tenv.lookup( typeInst->name ) ) { 787 // expand ttype parameter into its actual type 788 if ( clz->data.kind == ast::TypeVar::Ttype && clz->bound ) { 789 return clz->bound; 790 } 791 } 792 return typeInst; 793 } 794 }; 795 796 /// returns flattened version of `src` 797 static std::vector< ast::ptr< ast::DeclWithType > > flattenList( 798 const std::vector< ast::ptr< ast::DeclWithType > > & src, ast::TypeEnvironment & env 799 ) { 800 std::vector< ast::ptr< ast::DeclWithType > > dst; 801 dst.reserve( src.size() ); 802 for ( const ast::DeclWithType * d : src ) { 803 ast::Pass<TtypeExpander_new> expander{ env }; 804 d = d->accept( expander ); 805 auto types = flatten( d->get_type() ); 806 for ( ast::ptr< ast::Type > & t : types ) { 807 // outermost const, volatile, _Atomic qualifiers in parameters should not play 808 // a role in the unification of function types, since they do not determine 809 // whether a function is callable. 810 // NOTE: **must** consider at least mutex qualifier, since functions can be 811 // overloaded on outermost mutex and a mutex function has different 812 // requirements than a non-mutex function 813 t.get_and_mutate()->qualifiers 814 -= ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic; 815 dst.emplace_back( new ast::ObjectDecl{ d->location, "", t } ); 816 } 817 } 818 return dst; 819 } 820 821 /// Creates a tuple type based on a list of DeclWithType 822 template< typename Iter > 823 static ast::ptr< ast::Type > tupleFromDecls( Iter crnt, Iter end ) { 824 std::vector< ast::ptr< ast::Type > > types; 825 while ( crnt != end ) { 826 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure 827 // that this results in a flat tuple 828 flatten( (*crnt)->get_type(), types ); 829 830 ++crnt; 831 } 832 833 return { new ast::TupleType{ std::move(types) } }; 834 } 835 836 template< typename Iter > 837 static bool unifyDeclList( 838 Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env, 839 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 840 const ast::SymbolTable & symtab 841 ) { 842 while ( crnt1 != end1 && crnt2 != end2 ) { 843 const ast::Type * t1 = (*crnt1)->get_type(); 844 const ast::Type * t2 = (*crnt2)->get_type(); 845 bool isTuple1 = Tuples::isTtype( t1 ); 846 bool isTuple2 = Tuples::isTtype( t2 ); 847 848 // assumes here that ttype *must* be last parameter 849 if ( isTuple1 && ! isTuple2 ) { 850 // combine remainder of list2, then unify 851 return unifyExact( 852 t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, 853 WidenMode{ false, false }, symtab ); 854 } else if ( ! isTuple1 && isTuple2 ) { 855 // combine remainder of list1, then unify 856 return unifyExact( 857 tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, 858 WidenMode{ false, false }, symtab ); 859 } 860 861 if ( ! unifyExact( 862 t1, t2, env, need, have, open, WidenMode{ false, false }, symtab ) 863 ) return false; 864 865 ++crnt1; ++crnt2; 866 } 867 868 // May get to the end of one argument list before the other. This is only okay if the 869 // other is a ttype 870 if ( crnt1 != end1 ) { 871 // try unifying empty tuple with ttype 872 const ast::Type * t1 = (*crnt1)->get_type(); 873 if ( ! Tuples::isTtype( t1 ) ) return false; 874 return unifyExact( 875 t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, 876 WidenMode{ false, false }, symtab ); 877 } else if ( crnt2 != end2 ) { 878 // try unifying empty tuple with ttype 879 const ast::Type * t2 = (*crnt2)->get_type(); 880 if ( ! Tuples::isTtype( t2 ) ) return false; 881 return unifyExact( 882 tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, 883 WidenMode{ false, false }, symtab ); 884 } 885 886 return true; 887 } 888 889 static bool unifyDeclList( 890 const std::vector< ast::ptr< ast::DeclWithType > > & list1, 891 const std::vector< ast::ptr< ast::DeclWithType > > & list2, 892 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 893 const ast::OpenVarSet & open, const ast::SymbolTable & symtab 894 ) { 895 return unifyDeclList( 896 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open, 897 symtab ); 898 } 899 900 static void markAssertionSet( ast::AssertionSet & assns, const ast::DeclWithType * assn ) { 901 auto i = assns.find( assn ); 902 if ( i != assns.end() ) { 903 i->second.isUsed = true; 904 } 905 } 906 907 /// mark all assertions in `type` used in both `assn1` and `assn2` 908 static void markAssertions( 909 ast::AssertionSet & assn1, ast::AssertionSet & assn2, 910 const ast::ParameterizedType * type 911 ) { 912 for ( const auto & tyvar : type->forall ) { 913 for ( const ast::DeclWithType * assert : tyvar->assertions ) { 914 markAssertionSet( assn1, assert ); 915 markAssertionSet( assn2, assert ); 916 } 917 } 918 } 919 920 public: 921 void previsit( const ast::FunctionType * func ) { 922 visit_children = false; 923 auto func2 = dynamic_cast< const ast::FunctionType * >( type2 ); 924 if ( ! func2 ) return; 925 926 if ( func->isVarArgs != func2->isVarArgs ) return; 927 928 // Flatten the parameter lists for both functions so that tuple structure does not 929 // affect unification. Does not actually mutate function parameters. 930 auto params = flattenList( func->params, tenv ); 931 auto params2 = flattenList( func2->params, tenv ); 932 933 // sizes don't have to match if ttypes are involved; need to be more precise w.r.t. 934 // where the ttype is to prevent errors 935 if ( 936 ( params.size() != params2.size() || func->returns.size() != func2->returns.size() ) 937 && ! func->isTtype() 938 && ! func2->isTtype() 939 ) return; 940 941 if ( ! unifyDeclList( params, params2, tenv, need, have, open, symtab ) ) return; 942 if ( ! unifyDeclList( 943 func->returns, func2->returns, tenv, need, have, open, symtab ) ) return; 944 945 markAssertions( have, need, func ); 946 markAssertions( have, need, func2 ); 947 948 result = true; 949 } 950 951 private: 952 template< typename RefType > 953 const RefType * handleRefType( const RefType * inst, const ast::Type * other ) { 954 visit_children = false; 955 // check that the other type is compatible and named the same 956 auto otherInst = dynamic_cast< const RefType * >( other ); 957 result = otherInst && inst->name == otherInst->name; 958 return otherInst; 959 } 960 961 /// Creates a tuple type based on a list of TypeExpr 962 template< typename Iter > 963 static const ast::Type * tupleFromExprs( 964 const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs 965 ) { 966 std::vector< ast::ptr< ast::Type > > types; 967 do { 968 types.emplace_back( param->type ); 969 970 ++crnt; 971 if ( crnt == end ) break; 972 param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() ); 973 } while(true); 974 975 return new ast::TupleType{ std::move(types), qs }; 976 } 977 978 template< typename RefType > 979 void handleGenericRefType( const RefType * inst, const ast::Type * other ) { 980 // check that other type is compatible and named the same 981 const RefType * inst2 = handleRefType( inst, other ); 982 if ( ! inst2 ) return; 983 984 // check that parameters of types unify, if any 985 const std::vector< ast::ptr< ast::Expr > > & params = inst->params; 986 const std::vector< ast::ptr< ast::Expr > > & params2 = inst2->params; 987 988 auto it = params.begin(); 989 auto jt = params2.begin(); 990 for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) { 991 auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() ); 992 auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() ); 993 994 ast::ptr< ast::Type > pty = param->type; 995 ast::ptr< ast::Type > pty2 = param2->type; 996 997 bool isTuple = Tuples::isTtype( pty ); 998 bool isTuple2 = Tuples::isTtype( pty2 ); 999 1000 if ( isTuple && isTuple2 ) { 1001 ++it; ++jt; // skip ttype parameters before break 1002 } else if ( isTuple ) { 1003 // bundle remaining params into tuple 1004 pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers ); 1005 ++it; // skip ttype parameter for break 1006 } else if ( isTuple2 ) { 1007 // bundle remaining params into tuple 1008 pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers ); 1009 ++jt; // skip ttype parameter for break 1010 } 1011 1012 if ( ! unifyExact( 1013 pty, pty2, tenv, need, have, open, WidenMode{ false, false }, symtab ) ) { 1014 result = false; 1015 return; 1016 } 1017 1018 // ttype parameter should be last 1019 if ( isTuple || isTuple2 ) break; 1020 } 1021 result = it == params.end() && jt == params2.end(); 1022 } 1023 1024 public: 1025 void previsit( const ast::StructInstType * aggrType ) { 1026 handleGenericRefType( aggrType, type2 ); 1027 } 1028 1029 void previsit( const ast::UnionInstType * aggrType ) { 1030 handleGenericRefType( aggrType, type2 ); 1031 } 1032 1033 void previsit( const ast::EnumInstType * aggrType ) { 1034 handleRefType( aggrType, type2 ); 1035 } 1036 1037 void previsit( const ast::TraitInstType * aggrType ) { 1038 handleRefType( aggrType, type2 ); 1039 } 1040 1041 void previsit( const ast::TypeInstType * typeInst ) { 1042 assert( open.find( typeInst->name ) == open.end() ); 1043 handleRefType( typeInst, type2 ); 1044 } 1045 1046 private: 1047 /// Creates a tuple type based on a list of Type 1048 static ast::ptr< ast::Type > tupleFromTypes( 1049 const std::vector< ast::ptr< ast::Type > > & tys 1050 ) { 1051 std::vector< ast::ptr< ast::Type > > out; 1052 for ( const ast::Type * ty : tys ) { 1053 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure 1054 // that this results in a flat tuple 1055 flatten( ty, out ); 1056 } 1057 1058 return { new ast::TupleType{ std::move(out) } }; 1059 } 1060 1061 static bool unifyList( 1062 const std::vector< ast::ptr< ast::Type > > & list1, 1063 const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env, 1064 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 1065 const ast::SymbolTable & symtab 1066 ) { 1067 auto crnt1 = list1.begin(); 1068 auto crnt2 = list2.begin(); 1069 while ( crnt1 != list1.end() && crnt2 != list2.end() ) { 1070 const ast::Type * t1 = *crnt1; 1071 const ast::Type * t2 = *crnt2; 1072 bool isTuple1 = Tuples::isTtype( t1 ); 1073 bool isTuple2 = Tuples::isTtype( t2 ); 1074 1075 // assumes ttype must be last parameter 1076 if ( isTuple1 && ! isTuple2 ) { 1077 // combine entirety of list2, then unify 1078 return unifyExact( 1079 t1, tupleFromTypes( list2 ), env, need, have, open, 1080 WidenMode{ false, false }, symtab ); 1081 } else if ( ! isTuple1 && isTuple2 ) { 1082 // combine entirety of list1, then unify 1083 return unifyExact( 1084 tupleFromTypes( list1 ), t2, env, need, have, open, 1085 WidenMode{ false, false }, symtab ); 1086 } 1087 1088 if ( ! unifyExact( 1089 t1, t2, env, need, have, open, WidenMode{ false, false }, symtab ) 1090 ) return false; 1091 1092 ++crnt1; ++crnt2; 1093 } 1094 1095 if ( crnt1 != list1.end() ) { 1096 // try unifying empty tuple type with ttype 1097 const ast::Type * t1 = *crnt1; 1098 if ( ! Tuples::isTtype( t1 ) ) return false; 1099 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 1100 // from Rob's code 1101 return unifyExact( 1102 t1, tupleFromTypes( list2 ), env, need, have, open, 1103 WidenMode{ false, false }, symtab ); 1104 } else if ( crnt2 != list2.end() ) { 1105 // try unifying empty tuple with ttype 1106 const ast::Type * t2 = *crnt2; 1107 if ( ! Tuples::isTtype( t2 ) ) return false; 1108 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 1109 // from Rob's code 1110 return unifyExact( 1111 tupleFromTypes( list1 ), t2, env, need, have, open, 1112 WidenMode{ false, false }, symtab ); 1113 } 1114 1115 return true; 1116 } 1117 1118 public: 1119 void previsit( const ast::TupleType * tuple ) { 1120 visit_children = false; 1121 auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 ); 1122 if ( ! tuple2 ) return; 1123 1124 ast::Pass<TtypeExpander_new> expander{ tenv }; 1125 const ast::Type * flat = tuple->accept( expander ); 1126 const ast::Type * flat2 = tuple2->accept( expander ); 1127 1128 auto types = flatten( flat ); 1129 auto types2 = flatten( flat2 ); 1130 1131 result = unifyList( types, types2, tenv, need, have, open, symtab ); 1132 } 1133 1134 void previsit( const ast::VarArgsType * ) { 1135 visit_children = false; 1136 result = dynamic_cast< const ast::VarArgsType * >( type2 ); 1137 } 1138 1139 void previsit( const ast::ZeroType * ) { 1140 visit_children = false; 1141 result = dynamic_cast< const ast::ZeroType * >( type2 ); 1142 } 1143 1144 void previsit( const ast::OneType * ) { 1145 visit_children = false; 1146 result = dynamic_cast< const ast::OneType * >( type2 ); 1147 } 1148 1149 private: 1150 template< typename RefType > void handleRefType( RefType *inst, Type *other ); 1151 template< typename RefType > void handleGenericRefType( RefType *inst, Type *other ); 1152 }; 1153 1154 bool unifyExact( 1155 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 1156 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 1157 WidenMode widen, const ast::SymbolTable & symtab 1158 ) { 1159 if ( type1->qualifiers != type2->qualifiers ) return false; 1160 1161 auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 ); 1162 auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 ); 1163 ast::OpenVarSet::const_iterator 1164 entry1 = var1 ? open.find( var1->name ) : open.end(), 1165 entry2 = var2 ? open.find( var2->name ) : open.end(); 1166 bool isopen1 = entry1 != open.end(); 1167 bool isopen2 = entry2 != open.end(); 1168 1169 if ( isopen1 && isopen2 ) { 1170 if ( entry1->second.kind != entry2->second.kind ) return false; 1171 return env.bindVarToVar( 1172 var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have, 1173 open, widen, symtab ); 1174 } else if ( isopen1 ) { 1175 return env.bindVar( var1, type2, entry1->second, need, have, open, widen, symtab ); 1176 } else if ( isopen2 ) { 1177 return env.bindVar( var2, type1, entry2->second, need, have, open, widen, symtab ); 1178 } else { 1179 ast::Pass<Unify_new> comparator{ type2, env, need, have, open, widen, symtab }; 1180 type1->accept( comparator ); 1181 return comparator.pass.result; 1182 } 1183 } 1184 1185 bool unifyInexact( 1186 ast::ptr<ast::Type> & type1, ast::ptr<ast::Type> & type2, ast::TypeEnvironment & env, 1187 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 1188 WidenMode widen, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common 1189 ) { 1190 ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers; 1191 1192 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and 1193 // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1 1194 ast::ptr<ast::Type> t1{ type1 }, t2{ type2 }; 1195 clear_qualifiers( t1 ); 1196 clear_qualifiers( t2 ); 1197 1198 if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) { 1199 t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones 1200 1201 // if exact unification on unqualified types, try to merge qualifiers 1202 if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) { 1203 common.set_and_mutate( type1 )->qualifiers = q1 | q2; 1204 return true; 1205 } else { 1206 return false; 1207 } 1208 1209 } else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) { 1210 t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones 1211 1212 // no exact unification, but common type 1213 common.get_and_mutate()->qualifiers = q1 | q2; 1214 return true; 1215 } else { 1216 return false; 1217 } 1218 } 1219 675 1220 ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) { 676 1221 if ( func->returns.empty() ) return new ast::VoidType{}; -
src/ResolvExpr/Unify.h
r0e315a5 r98a8290 18 18 #include <list> // for list 19 19 20 #include "AST/Node.hpp" // for ptr 20 21 #include "AST/TypeEnvironment.hpp" // for TypeEnvironment, AssertionSet, OpenVarSet 21 22 #include "Common/utility.h" // for deleteAll … … 39 40 bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ); 40 41 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ); 41 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen Mode, const SymTab::Indexer &indexer, Type *&common );42 bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ); 42 43 43 44 template< typename Iterator1, typename Iterator2 > … … 68 69 } 69 70 71 bool unifyExact( 72 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 73 ast::AssertionSet & need, ast::AssertionSet & have, ast::OpenVarSet & open, 74 const ast::SymbolTable & symtab ); 75 70 76 bool unifyInexact( 71 const ast::Type * type1, const ast::Type *type2, ast::TypeEnvironment & env,72 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open Vars,73 WidenMode widen Mode, const ast::SymbolTable & symtab, const ast::Type *& common );77 ast::ptr<ast::Type> & type1, ast::ptr<ast::Type> & type2, ast::TypeEnvironment & env, 78 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 79 WidenMode widen, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common ); 74 80 75 81 } // namespace ResolvExpr -
src/ResolvExpr/WidenMode.h
r0e315a5 r98a8290 18 18 namespace ResolvExpr { 19 19 struct WidenMode { 20 WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {} 21 WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; } 22 WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; } 23 WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; } 24 WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; } 25 operator bool() { return widenFirst && widenSecond; } 20 WidenMode( bool first, bool second ): first( first ), second( second ) {} 21 22 WidenMode &operator|=( const WidenMode &other ) { 23 first |= other.first; second |= other.second; return *this; 24 } 26 25 27 bool widenFirst : 1, widenSecond : 1; 26 WidenMode &operator&=( const WidenMode &other ) { 27 first &= other.first; second &= other.second; return *this; 28 } 29 30 WidenMode operator|( const WidenMode &other ) { 31 WidenMode newWM( *this ); newWM |= other; return newWM; 32 } 33 34 WidenMode operator&( const WidenMode &other ) { 35 WidenMode newWM( *this ); newWM &= other; return newWM; 36 } 37 38 operator bool() { return first && second; } 39 40 bool first : 1, second : 1; 28 41 }; 29 42 } // namespace ResolvExpr -
src/ResolvExpr/typeops.h
r0e315a5 r98a8290 18 18 #include <vector> 19 19 20 #include "Cost.h" 21 #include "TypeEnvironment.h" 22 #include "WidenMode.h" 20 23 #include "AST/Fwd.hpp" 21 24 #include "AST/Node.hpp" … … 26 29 #include "SynTree/Type.h" 27 30 #include "SymTab/Indexer.h" 28 #include "Cost.h"29 #include "TypeEnvironment.h"30 31 31 32 namespace ResolvExpr { … … 117 118 // in CommonType.cc 118 119 Type * commonType( Type *type1, Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ); 120 const ast::Type * commonType( 121 const ast::Type * type1, const ast::Type * type2, WidenMode widen, 122 const ast::SymbolTable & symtab, ast::TypeEnvironment & env, const ast::OpenVarSet & open ); 119 123 120 124 // in PolyCost.cc … … 141 145 const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ); 142 146 143 // flatten tuple type into list of types147 /// flatten tuple type into list of types 144 148 template< typename OutputIterator > 145 149 void flatten( Type * type, OutputIterator out ) { … … 152 156 } 153 157 } 158 159 /// flatten tuple type into existing list of types 160 static inline void flatten( 161 const ast::Type * type, std::vector< ast::ptr< ast::Type > > & out 162 ) { 163 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( type ) ) { 164 for ( const ast::Type * t : tupleType->types ) { 165 flatten( t, out ); 166 } 167 } else { 168 out.emplace_back( type ); 169 } 170 } 171 172 /// flatten tuple type into list of types 173 static inline std::vector< ast::ptr< ast::Type > > flatten( const ast::Type * type ) { 174 std::vector< ast::ptr< ast::Type > > out; 175 out.reserve( type->size() ); 176 flatten( type, out ); 177 return out; 178 } 154 179 } // namespace ResolvExpr 155 180 -
src/include/cassert
r0e315a5 r98a8290 10 10 // Created On : Thu Aug 18 13:19:26 2016 11 11 // Last Modified By : Andrew Beach 12 // Last Modified On : Thu May 23 15:30:00 201713 // Update Count : 1 712 // Last Modified On : Mon Jun 3 13:11:00 2017 13 // Update Count : 18 14 14 // 15 15 … … 43 43 #endif 44 44 45 enum StrictAllowNull {NonNull, AllowNull}; 46 47 template<typename T, StrictAllowNull nullable = NonNull, typename U> 45 template<typename T, typename U> 48 46 static inline T strict_dynamic_cast( const U & src ) { 49 if (nullable == AllowNull && src == nullptr) {50 return nullptr;51 }52 47 assert(src); 53 48 T ret = dynamic_cast<T>(src); 54 49 assertf(ret, "%s", toString(src).c_str()); 55 50 return ret; 51 } 52 53 template<typename T, decltype(nullptr) null, typename U> 54 static inline T strict_dynamic_cast( const U & src ) { 55 return src ? strict_dynamic_cast<T, U>( src ) : nullptr; 56 56 } 57 57
Note: See TracChangeset
for help on using the changeset viewer.