Changeset eef8dfb for src/ResolvExpr/Unify.cc
- Timestamp:
- Jan 7, 2021, 2:55:57 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 58fe85a
- Parents:
- bdfc032 (diff), 44e37ef (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. - File:
-
- 1 edited
-
src/ResolvExpr/Unify.cc (modified) (30 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/Unify.cc
rbdfc032 reef8dfb 25 25 #include <vector> 26 26 27 #include "AST/Copy.hpp" 27 28 #include "AST/Decl.hpp" 28 29 #include "AST/Node.hpp" 29 30 #include "AST/Pass.hpp" 31 #include "AST/Print.hpp" 30 32 #include "AST/Type.hpp" 31 33 #include "AST/TypeEnvironment.hpp" … … 135 137 findOpenVars( newSecond, open, closed, need, have, FirstOpen ); 136 138 137 return unifyExact( 138 newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab ); 139 return unifyExact(newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab ); 139 140 } 140 141 … … 148 149 newFirst->get_qualifiers() = Type::Qualifiers(); 149 150 newSecond->get_qualifiers() = Type::Qualifiers(); 150 /// std::cerr << "first is "; 151 /// first->print( std::cerr ); 152 /// std::cerr << std::endl << "second is "; 153 /// second->print( std::cerr ); 154 /// std::cerr << std::endl << "newFirst is "; 155 /// newFirst->print( std::cerr ); 156 /// std::cerr << std::endl << "newSecond is "; 157 /// newSecond->print( std::cerr ); 158 /// std::cerr << std::endl; 151 159 152 bool result = unifyExact( newFirst, newSecond, newEnv, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); 160 153 delete newFirst; … … 170 163 ast::AssertionSet need, have; 171 164 172 ast::ptr<ast::Type> newFirst{ first }, newSecond{ second }; 173 env.apply( newFirst ); 174 env.apply( newSecond ); 175 reset_qualifiers( newFirst ); 176 reset_qualifiers( newSecond ); 165 ast::Type * newFirst = shallowCopy( first ); 166 ast::Type * newSecond = shallowCopy( second ); 167 newFirst ->qualifiers = {}; 168 newSecond->qualifiers = {}; 169 ast::ptr< ast::Type > t1_(newFirst ); 170 ast::ptr< ast::Type > t2_(newSecond); 171 172 ast::ptr< ast::Type > subFirst = env.apply(newFirst).node; 173 ast::ptr< ast::Type > subSecond = env.apply(newSecond).node; 177 174 178 175 return unifyExact( 179 newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab ); 176 subFirst, 177 subSecond, 178 newEnv, need, have, open, noWiden(), symtab ); 180 179 } 181 180 … … 326 325 327 326 void markAssertionSet( AssertionSet &assertions, DeclarationWithType *assert ) { 328 /// std::cerr << "assertion set is" << std::endl;329 /// printAssertionSet( assertions, std::cerr, 8 );330 /// std::cerr << "looking for ";331 /// assert->print( std::cerr );332 /// std::cerr << std::endl;333 327 AssertionSet::iterator i = assertions.find( assert ); 334 328 if ( i != assertions.end() ) { 335 /// std::cerr << "found it!" << std::endl;336 329 i->second.isUsed = true; 337 330 } // if … … 402 395 403 396 template< typename Iterator1, typename Iterator2 > 404 bool unify DeclList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) {397 bool unifyTypeList( Iterator1 list1Begin, Iterator1 list1End, Iterator2 list2Begin, Iterator2 list2End, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, const SymTab::Indexer &indexer ) { 405 398 auto get_type = [](DeclarationWithType * dwt){ return dwt->get_type(); }; 406 399 for ( ; list1Begin != list1End && list2Begin != list2End; ++list1Begin, ++list2Begin ) { … … 496 489 || flatOther->isTtype() 497 490 ) { 498 if ( unify DeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {499 if ( unify DeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) {491 if ( unifyTypeList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { 492 if ( unifyTypeList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { 500 493 501 494 // the original types must be used in mark assertions, since pointer comparisons are used … … 709 702 const ast::SymbolTable & symtab; 710 703 public: 704 static size_t traceId; 711 705 bool result; 712 706 … … 773 767 /// If this isn't done when satifying ttype assertions, then argument lists can have 774 768 /// different size and structure when they should be compatible. 775 struct TtypeExpander_new : public ast::WithShortCircuiting {769 struct TtypeExpander_new : public ast::WithShortCircuiting, public ast::PureVisitor { 776 770 ast::TypeEnvironment & tenv; 777 771 … … 779 773 780 774 const ast::Type * postvisit( const ast::TypeInstType * typeInst ) { 781 if ( const ast::EqvClass * clz = tenv.lookup( typeInst->name) ) {775 if ( const ast::EqvClass * clz = tenv.lookup( *typeInst ) ) { 782 776 // expand ttype parameter into its actual type 783 777 if ( clz->data.kind == ast::TypeDecl::Ttype && clz->bound ) { … … 790 784 791 785 /// returns flattened version of `src` 792 static std::vector< ast::ptr< ast:: DeclWithType > > flattenList(793 const std::vector< ast::ptr< ast:: DeclWithType > > & src, ast::TypeEnvironment & env786 static std::vector< ast::ptr< ast::Type > > flattenList( 787 const std::vector< ast::ptr< ast::Type > > & src, ast::TypeEnvironment & env 794 788 ) { 795 std::vector< ast::ptr< ast:: DeclWithType > > dst;789 std::vector< ast::ptr< ast::Type > > dst; 796 790 dst.reserve( src.size() ); 797 for ( const a st::DeclWithType *d : src ) {791 for ( const auto & d : src ) { 798 792 ast::Pass<TtypeExpander_new> expander{ env }; 799 d = d->accept( expander ); 800 auto types = flatten( d->get_type() ); 793 // TtypeExpander pass is impure (may mutate nodes in place) 794 // need to make nodes shared to prevent accidental mutation 795 ast::ptr<ast::Type> dc = d->accept(expander); 796 auto types = flatten( dc ); 801 797 for ( ast::ptr< ast::Type > & t : types ) { 802 798 // outermost const, volatile, _Atomic qualifiers in parameters should not play … … 807 803 // requirements than a non-mutex function 808 804 remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic ); 809 dst.emplace_back( new ast::ObjectDecl{ d->location, "", t });805 dst.emplace_back( t ); 810 806 } 811 807 } … … 815 811 /// Creates a tuple type based on a list of DeclWithType 816 812 template< typename Iter > 817 static ast::ptr< ast::Type > tupleFromDecls( Iter crnt, Iter end ) {813 static const ast::Type * tupleFromTypes( Iter crnt, Iter end ) { 818 814 std::vector< ast::ptr< ast::Type > > types; 819 815 while ( crnt != end ) { 820 816 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure 821 817 // that this results in a flat tuple 822 flatten( (*crnt)->get_type(), types );818 flatten( *crnt, types ); 823 819 824 820 ++crnt; 825 821 } 826 822 827 return { new ast::TupleType{ std::move(types) }};823 return new ast::TupleType{ std::move(types) }; 828 824 } 829 825 830 826 template< typename Iter > 831 static bool unify DeclList(827 static bool unifyTypeList( 832 828 Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env, 833 829 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, … … 835 831 ) { 836 832 while ( crnt1 != end1 && crnt2 != end2 ) { 837 const ast::Type * t1 = (*crnt1)->get_type();838 const ast::Type * t2 = (*crnt2)->get_type();833 const ast::Type * t1 = *crnt1; 834 const ast::Type * t2 = *crnt2; 839 835 bool isTuple1 = Tuples::isTtype( t1 ); 840 836 bool isTuple2 = Tuples::isTtype( t2 ); … … 844 840 // combine remainder of list2, then unify 845 841 return unifyExact( 846 t1, tupleFrom Decls( crnt2, end2 ), env, need, have, open,842 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open, 847 843 noWiden(), symtab ); 848 844 } else if ( ! isTuple1 && isTuple2 ) { 849 845 // combine remainder of list1, then unify 850 846 return unifyExact( 851 tupleFrom Decls( crnt1, end1 ), t2, env, need, have, open,847 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open, 852 848 noWiden(), symtab ); 853 849 } … … 864 860 if ( crnt1 != end1 ) { 865 861 // try unifying empty tuple with ttype 866 const ast::Type * t1 = (*crnt1)->get_type();862 const ast::Type * t1 = *crnt1; 867 863 if ( ! Tuples::isTtype( t1 ) ) return false; 868 864 return unifyExact( 869 t1, tupleFrom Decls( crnt2, end2 ), env, need, have, open,865 t1, tupleFromTypes( crnt2, end2 ), env, need, have, open, 870 866 noWiden(), symtab ); 871 867 } else if ( crnt2 != end2 ) { 872 868 // try unifying empty tuple with ttype 873 const ast::Type * t2 = (*crnt2)->get_type();869 const ast::Type * t2 = *crnt2; 874 870 if ( ! Tuples::isTtype( t2 ) ) return false; 875 871 return unifyExact( 876 tupleFrom Decls( crnt1, end1 ), t2, env, need, have, open,872 tupleFromTypes( crnt1, end1 ), t2, env, need, have, open, 877 873 noWiden(), symtab ); 878 874 } … … 881 877 } 882 878 883 static bool unify DeclList(884 const std::vector< ast::ptr< ast:: DeclWithType > > & list1,885 const std::vector< ast::ptr< ast:: DeclWithType > > & list2,879 static bool unifyTypeList( 880 const std::vector< ast::ptr< ast::Type > > & list1, 881 const std::vector< ast::ptr< ast::Type > > & list2, 886 882 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 887 883 const ast::OpenVarSet & open, const ast::SymbolTable & symtab 888 884 ) { 889 return unify DeclList(885 return unifyTypeList( 890 886 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open, 891 887 symtab ); 892 888 } 893 889 894 static void markAssertionSet( ast::AssertionSet & assns, const ast:: DeclWithType* assn ) {890 static void markAssertionSet( ast::AssertionSet & assns, const ast::VariableExpr * assn ) { 895 891 auto i = assns.find( assn ); 896 892 if ( i != assns.end() ) { … … 902 898 static void markAssertions( 903 899 ast::AssertionSet & assn1, ast::AssertionSet & assn2, 904 const ast:: ParameterizedType * type900 const ast::FunctionType * type 905 901 ) { 906 for ( const auto & tyvar : type->forall ) { 907 for ( const ast::DeclWithType * assert : tyvar->assertions ) { 908 markAssertionSet( assn1, assert ); 909 markAssertionSet( assn2, assert ); 910 } 902 for ( auto & assert : type->assertions ) { 903 markAssertionSet( assn1, assert ); 904 markAssertionSet( assn2, assert ); 911 905 } 912 906 } … … 932 926 ) return; 933 927 934 if ( ! unify DeclList( params, params2, tenv, need, have, open, symtab ) ) return;935 if ( ! unify DeclList(928 if ( ! unifyTypeList( params, params2, tenv, need, have, open, symtab ) ) return; 929 if ( ! unifyTypeList( 936 930 func->returns, func2->returns, tenv, need, have, open, symtab ) ) return; 937 931 … … 943 937 944 938 private: 945 template< typename RefType > 946 const RefType * handleRefType( const RefType * inst, const ast::Type * other ) { 939 // Returns: other, cast as XInstType 940 // Assigns this->result: whether types are compatible (up to generic parameters) 941 template< typename XInstType > 942 const XInstType * handleRefType( const XInstType * inst, const ast::Type * other ) { 947 943 // check that the other type is compatible and named the same 948 auto otherInst = dynamic_cast< const RefType * >( other );949 result = otherInst && inst->name == otherInst->name;944 auto otherInst = dynamic_cast< const XInstType * >( other ); 945 this->result = otherInst && inst->name == otherInst->name; 950 946 return otherInst; 951 947 } … … 968 964 } 969 965 970 template< typename RefType >971 void handleGenericRefType( const RefType * inst, const ast::Type * other ) {966 template< typename XInstType > 967 void handleGenericRefType( const XInstType * inst, const ast::Type * other ) { 972 968 // check that other type is compatible and named the same 973 const RefType * inst2= handleRefType( inst, other );974 if ( ! inst2) return;969 const XInstType * otherInst = handleRefType( inst, other ); 970 if ( ! this->result ) return; 975 971 976 972 // check that parameters of types unify, if any 977 973 const std::vector< ast::ptr< ast::Expr > > & params = inst->params; 978 const std::vector< ast::ptr< ast::Expr > > & params2 = inst2->params;974 const std::vector< ast::ptr< ast::Expr > > & params2 = otherInst->params; 979 975 980 976 auto it = params.begin(); … … 1032 1028 1033 1029 void postvisit( const ast::TypeInstType * typeInst ) { 1034 assert( open.find( typeInst->name) == open.end() );1030 assert( open.find( *typeInst ) == open.end() ); 1035 1031 handleRefType( typeInst, type2 ); 1036 1032 } … … 1038 1034 private: 1039 1035 /// Creates a tuple type based on a list of Type 1040 static ast::ptr< ast::Type >tupleFromTypes(1036 static const ast::Type * tupleFromTypes( 1041 1037 const std::vector< ast::ptr< ast::Type > > & tys 1042 1038 ) { … … 1114 1110 1115 1111 ast::Pass<TtypeExpander_new> expander{ tenv }; 1112 1116 1113 const ast::Type * flat = tuple->accept( expander ); 1117 1114 const ast::Type * flat2 = tuple2->accept( expander ); … … 1140 1137 }; 1141 1138 1139 // size_t Unify_new::traceId = Stats::Heap::new_stacktrace_id("Unify_new"); 1142 1140 bool unify( 1143 1141 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, … … 1171 1169 auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 ); 1172 1170 ast::OpenVarSet::const_iterator 1173 entry1 = var1 ? open.find( var1->name) : open.end(),1174 entry2 = var2 ? open.find( var2->name) : open.end();1171 entry1 = var1 ? open.find( *var1 ) : open.end(), 1172 entry2 = var2 ? open.find( *var2 ) : open.end(); 1175 1173 bool isopen1 = entry1 != open.end(); 1176 1174 bool isopen2 = entry2 != open.end(); … … 1188 1186 ast::Pass<Unify_new> comparator{ type2, env, need, have, open, widen, symtab }; 1189 1187 type1->accept( comparator ); 1190 return comparator. pass.result;1188 return comparator.core.result; 1191 1189 } 1192 1190 } … … 1202 1200 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and 1203 1201 // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1 1204 ast::ptr<ast::Type> t1{ type1 }, t2{ type2 }; 1205 reset_qualifiers( t1 ); 1206 reset_qualifiers( t2 ); 1202 ast::Type * t1 = shallowCopy(type1.get()); 1203 ast::Type * t2 = shallowCopy(type2.get()); 1204 t1->qualifiers = {}; 1205 t2->qualifiers = {}; 1206 ast::ptr< ast::Type > t1_(t1); 1207 ast::ptr< ast::Type > t2_(t2); 1207 1208 1208 1209 if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) { 1209 t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones1210 1211 1210 // if exact unification on unqualified types, try to merge qualifiers 1212 1211 if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) { 1213 common = type1;1214 reset_qualifiers( common, q1 | q2 );1212 t1->qualifiers = q1 | q2; 1213 common = t1; 1215 1214 return true; 1216 1215 } else { … … 1219 1218 1220 1219 } else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) { 1221 t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones1222 1223 1220 // no exact unification, but common type 1224 reset_qualifiers( common, q1 | q2 ); 1221 auto c = shallowCopy(common.get()); 1222 c->qualifiers = q1 | q2; 1223 common = c; 1225 1224 return true; 1226 1225 } else { … … 1231 1230 ast::ptr<ast::Type> extractResultType( const ast::FunctionType * func ) { 1232 1231 if ( func->returns.empty() ) return new ast::VoidType{}; 1233 if ( func->returns.size() == 1 ) return func->returns[0] ->get_type();1232 if ( func->returns.size() == 1 ) return func->returns[0]; 1234 1233 1235 1234 std::vector<ast::ptr<ast::Type>> tys; 1236 for ( const a st::DeclWithType *decl : func->returns ) {1237 tys.emplace_back( decl ->get_type());1235 for ( const auto & decl : func->returns ) { 1236 tys.emplace_back( decl ); 1238 1237 } 1239 1238 return new ast::TupleType{ std::move(tys) };
Note:
See TracChangeset
for help on using the changeset viewer.
