Changeset 7870799 for src/ResolvExpr/Unify.cc
- Timestamp:
- Jul 12, 2019, 10:49:02 AM (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:
- ef5b828
- Parents:
- ee6dbae
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/Unify.cc
ree6dbae r7870799 97 97 bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); 98 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, 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 102 WidenMode widen, const ast::SymbolTable & symtab ); 103 103 … … 121 121 } 122 122 123 bool typesCompatible( 124 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, 123 bool typesCompatible( 124 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, 125 125 const ast::TypeEnvironment & env ) { 126 126 ast::TypeEnvironment newEnv; … … 135 135 findOpenVars( newSecond, open, closed, need, have, FirstOpen ); 136 136 137 return unifyExact( 137 return unifyExact( 138 138 newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab ); 139 139 } 140 140 141 bool typesCompatibleIgnoreQualifiers( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) {141 bool typesCompatibleIgnoreQualifiers( const Type * first, const Type * second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) { 142 142 TypeEnvironment newEnv; 143 143 OpenVarSet openVars; … … 163 163 } 164 164 165 bool typesCompatibleIgnoreQualifiers( 166 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, 165 bool typesCompatibleIgnoreQualifiers( 166 const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, 167 167 const ast::TypeEnvironment & env ) { 168 168 ast::TypeEnvironment newEnv; 169 169 ast::OpenVarSet open; 170 170 ast::AssertionSet need, have; 171 171 172 172 ast::ptr<ast::Type> newFirst{ first }, newSecond{ second }; 173 173 env.apply( newFirst ); … … 176 176 reset_qualifiers( newSecond ); 177 177 178 return unifyExact( 178 return unifyExact( 179 179 newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab ); 180 180 } … … 490 490 491 491 // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors 492 if ( 493 (flatFunc->parameters.size() == flatOther->parameters.size() && 494 flatFunc->returnVals.size() == flatOther->returnVals.size()) 495 || flatFunc->isTtype() 496 || 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 497 ) { 498 498 if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { … … 711 711 bool result; 712 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, 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 716 const ast::SymbolTable & symtab ) 717 : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen), 717 : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen), 718 718 symtab(symtab), result(false) {} 719 719 720 720 void previsit( const ast::Node * ) { visit_children = false; } 721 721 722 722 void postvisit( const ast::VoidType * ) { 723 723 result = dynamic_cast< const ast::VoidType * >( type2 ); … … 732 732 void postvisit( const ast::PointerType * pointer ) { 733 733 if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) { 734 result = unifyExact( 735 pointer->base, pointer2->base, tenv, need, have, open, 734 result = unifyExact( 735 pointer->base, pointer2->base, tenv, need, have, open, 736 736 noWiden(), symtab ); 737 737 } … … 742 742 if ( ! array2 ) return; 743 743 744 // to unify, array types must both be VLA or both not VLA and both must have a 744 // to unify, array types must both be VLA or both not VLA and both must have a 745 745 // dimension expression or not have a dimension 746 746 if ( array->isVarLen != array2->isVarLen ) return; 747 if ( ! array->isVarLen && ! array2->isVarLen 747 if ( ! array->isVarLen && ! array2->isVarLen 748 748 && array->dimension && array2->dimension ) { 749 749 auto ce1 = array->dimension.as< ast::ConstantExpr >(); … … 751 751 752 752 // see C11 Reference Manual 6.7.6.2.6 753 // two array types with size specifiers that are integer constant expressions are 753 // two array types with size specifiers that are integer constant expressions are 754 754 // compatible if both size specifiers have the same constant value 755 755 if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return; 756 756 } 757 757 758 result = unifyExact( 759 array->base, array2->base, tenv, need, have, open, noWiden(), 758 result = unifyExact( 759 array->base, array2->base, tenv, need, have, open, noWiden(), 760 760 symtab ); 761 761 } … … 763 763 void postvisit( const ast::ReferenceType * ref ) { 764 764 if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) { 765 result = unifyExact( 766 ref->base, ref2->base, tenv, need, have, open, noWiden(), 765 result = unifyExact( 766 ref->base, ref2->base, tenv, need, have, open, noWiden(), 767 767 symtab ); 768 768 } … … 771 771 private: 772 772 /// Replaces ttype variables with their bound types. 773 /// If this isn't done when satifying ttype assertions, then argument lists can have 773 /// If this isn't done when satifying ttype assertions, then argument lists can have 774 774 /// different size and structure when they should be compatible. 775 775 struct TtypeExpander_new : public ast::WithShortCircuiting { … … 800 800 auto types = flatten( d->get_type() ); 801 801 for ( ast::ptr< ast::Type > & t : types ) { 802 // outermost const, volatile, _Atomic qualifiers in parameters should not play 803 // a role in the unification of function types, since they do not determine 802 // outermost const, volatile, _Atomic qualifiers in parameters should not play 803 // a role in the unification of function types, since they do not determine 804 804 // whether a function is callable. 805 // NOTE: **must** consider at least mutex qualifier, since functions can be 806 // overloaded on outermost mutex and a mutex function has different 805 // NOTE: **must** consider at least mutex qualifier, since functions can be 806 // overloaded on outermost mutex and a mutex function has different 807 807 // requirements than a non-mutex function 808 808 remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic ); … … 818 818 std::vector< ast::ptr< ast::Type > > types; 819 819 while ( crnt != end ) { 820 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure 820 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure 821 821 // that this results in a flat tuple 822 822 flatten( (*crnt)->get_type(), types ); … … 829 829 830 830 template< typename Iter > 831 static bool unifyDeclList( 832 Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env, 833 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 831 static bool unifyDeclList( 832 Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env, 833 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 834 834 const ast::SymbolTable & symtab 835 835 ) { … … 843 843 if ( isTuple1 && ! isTuple2 ) { 844 844 // combine remainder of list2, then unify 845 return unifyExact( 846 t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, 845 return unifyExact( 846 t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, 847 847 noWiden(), symtab ); 848 848 } else if ( ! isTuple1 && isTuple2 ) { 849 849 // combine remainder of list1, then unify 850 return unifyExact( 851 tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, 850 return unifyExact( 851 tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, 852 852 noWiden(), symtab ); 853 853 } 854 854 855 if ( ! unifyExact( 856 t1, t2, env, need, have, open, noWiden(), symtab ) 855 if ( ! unifyExact( 856 t1, t2, env, need, have, open, noWiden(), symtab ) 857 857 ) return false; 858 858 … … 860 860 } 861 861 862 // May get to the end of one argument list before the other. This is only okay if the 862 // May get to the end of one argument list before the other. This is only okay if the 863 863 // other is a ttype 864 864 if ( crnt1 != end1 ) { … … 866 866 const ast::Type * t1 = (*crnt1)->get_type(); 867 867 if ( ! Tuples::isTtype( t1 ) ) return false; 868 return unifyExact( 869 t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, 868 return unifyExact( 869 t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, 870 870 noWiden(), symtab ); 871 871 } else if ( crnt2 != end2 ) { … … 873 873 const ast::Type * t2 = (*crnt2)->get_type(); 874 874 if ( ! Tuples::isTtype( t2 ) ) return false; 875 return unifyExact( 876 tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, 875 return unifyExact( 876 tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, 877 877 noWiden(), symtab ); 878 878 } … … 881 881 } 882 882 883 static bool unifyDeclList( 884 const std::vector< ast::ptr< ast::DeclWithType > > & list1, 885 const std::vector< ast::ptr< ast::DeclWithType > > & list2, 886 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 883 static bool unifyDeclList( 884 const std::vector< ast::ptr< ast::DeclWithType > > & list1, 885 const std::vector< ast::ptr< ast::DeclWithType > > & list2, 886 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 887 887 const ast::OpenVarSet & open, const ast::SymbolTable & symtab 888 888 ) { 889 return unifyDeclList( 890 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open, 889 return unifyDeclList( 890 list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open, 891 891 symtab ); 892 892 } … … 900 900 901 901 /// mark all assertions in `type` used in both `assn1` and `assn2` 902 static void markAssertions( 903 ast::AssertionSet & assn1, ast::AssertionSet & assn2, 904 const ast::ParameterizedType * type 902 static void markAssertions( 903 ast::AssertionSet & assn1, ast::AssertionSet & assn2, 904 const ast::ParameterizedType * type 905 905 ) { 906 906 for ( const auto & tyvar : type->forall ) { … … 918 918 919 919 if ( func->isVarArgs != func2->isVarArgs ) return; 920 921 // Flatten the parameter lists for both functions so that tuple structure does not 920 921 // Flatten the parameter lists for both functions so that tuple structure does not 922 922 // affect unification. Does not actually mutate function parameters. 923 923 auto params = flattenList( func->params, tenv ); 924 924 auto params2 = flattenList( func2->params, tenv ); 925 925 926 // sizes don't have to match if ttypes are involved; need to be more precise w.r.t. 926 // sizes don't have to match if ttypes are involved; need to be more precise w.r.t. 927 927 // where the ttype is to prevent errors 928 if ( 928 if ( 929 929 ( params.size() != params2.size() || func->returns.size() != func2->returns.size() ) 930 930 && ! func->isTtype() … … 933 933 934 934 if ( ! unifyDeclList( params, params2, tenv, need, have, open, symtab ) ) return; 935 if ( ! unifyDeclList( 935 if ( ! unifyDeclList( 936 936 func->returns, func2->returns, tenv, need, have, open, symtab ) ) return; 937 937 938 938 markAssertions( have, need, func ); 939 939 markAssertions( have, need, func2 ); … … 941 941 result = true; 942 942 } 943 943 944 944 private: 945 945 template< typename RefType > … … 953 953 /// Creates a tuple type based on a list of TypeExpr 954 954 template< typename Iter > 955 static const ast::Type * tupleFromExprs( 955 static const ast::Type * tupleFromExprs( 956 956 const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs 957 957 ) { … … 973 973 const RefType * inst2 = handleRefType( inst, other ); 974 974 if ( ! inst2 ) return; 975 975 976 976 // check that parameters of types unify, if any 977 977 const std::vector< ast::ptr< ast::Expr > > & params = inst->params; … … 1002 1002 } 1003 1003 1004 if ( ! unifyExact( 1004 if ( ! unifyExact( 1005 1005 pty, pty2, tenv, need, have, open, noWiden(), symtab ) ) { 1006 1006 result = false; … … 1038 1038 private: 1039 1039 /// Creates a tuple type based on a list of Type 1040 static ast::ptr< ast::Type > tupleFromTypes( 1040 static ast::ptr< ast::Type > tupleFromTypes( 1041 1041 const std::vector< ast::ptr< ast::Type > > & tys 1042 1042 ) { 1043 1043 std::vector< ast::ptr< ast::Type > > out; 1044 1044 for ( const ast::Type * ty : tys ) { 1045 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure 1045 // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure 1046 1046 // that this results in a flat tuple 1047 1047 flatten( ty, out ); … … 1051 1051 } 1052 1052 1053 static bool unifyList( 1054 const std::vector< ast::ptr< ast::Type > > & list1, 1055 const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env, 1056 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 1053 static bool unifyList( 1054 const std::vector< ast::ptr< ast::Type > > & list1, 1055 const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env, 1056 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 1057 1057 const ast::SymbolTable & symtab 1058 1058 ) { … … 1068 1068 if ( isTuple1 && ! isTuple2 ) { 1069 1069 // combine entirety of list2, then unify 1070 return unifyExact( 1071 t1, tupleFromTypes( list2 ), env, need, have, open, 1070 return unifyExact( 1071 t1, tupleFromTypes( list2 ), env, need, have, open, 1072 1072 noWiden(), symtab ); 1073 1073 } else if ( ! isTuple1 && isTuple2 ) { 1074 1074 // combine entirety of list1, then unify 1075 1075 return unifyExact( 1076 tupleFromTypes( list1 ), t2, env, need, have, open, 1076 tupleFromTypes( list1 ), t2, env, need, have, open, 1077 1077 noWiden(), symtab ); 1078 1078 } 1079 1079 1080 if ( ! unifyExact( 1081 t1, t2, env, need, have, open, noWiden(), symtab ) 1080 if ( ! unifyExact( 1081 t1, t2, env, need, have, open, noWiden(), symtab ) 1082 1082 ) return false; 1083 1083 … … 1089 1089 const ast::Type * t1 = *crnt1; 1090 1090 if ( ! Tuples::isTtype( t1 ) ) return false; 1091 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 1091 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 1092 1092 // from Rob's code 1093 return unifyExact( 1094 t1, tupleFromTypes( list2 ), env, need, have, open, 1093 return unifyExact( 1094 t1, tupleFromTypes( list2 ), env, need, have, open, 1095 1095 noWiden(), symtab ); 1096 1096 } else if ( crnt2 != list2.end() ) { … … 1098 1098 const ast::Type * t2 = *crnt2; 1099 1099 if ( ! Tuples::isTtype( t2 ) ) return false; 1100 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 1100 // xxx - this doesn't generate an empty tuple, contrary to comment; both ported 1101 1101 // from Rob's code 1102 1102 return unifyExact( 1103 tupleFromTypes( list1 ), t2, env, need, have, open, 1103 tupleFromTypes( list1 ), t2, env, need, have, open, 1104 1104 noWiden(), symtab ); 1105 1105 } … … 1133 1133 void postvisit( const ast::OneType * ) { 1134 1134 result = dynamic_cast< const ast::OneType * >( type2 ); 1135 } 1135 } 1136 1136 1137 1137 private: … … 1140 1140 }; 1141 1141 1142 bool unify( 1143 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1144 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1142 bool unify( 1143 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1144 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1145 1145 ast::OpenVarSet & open, const ast::SymbolTable & symtab 1146 1146 ) { … … 1149 1149 } 1150 1150 1151 bool unify( 1152 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1153 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1154 ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common 1151 bool unify( 1152 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1153 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1154 ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common 1155 1155 ) { 1156 1156 ast::OpenVarSet closed; 1157 1157 findOpenVars( type1, open, closed, need, have, FirstClosed ); 1158 1158 findOpenVars( type2, open, closed, need, have, FirstOpen ); 1159 return unifyInexact( 1159 return unifyInexact( 1160 1160 type1, type2, env, need, have, open, WidenMode{ true, true }, symtab, common ); 1161 1161 } 1162 1162 1163 bool unifyExact( 1164 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 1165 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 1163 bool unifyExact( 1164 const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, 1165 ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, 1166 1166 WidenMode widen, const ast::SymbolTable & symtab 1167 1167 ) { … … 1170 1170 auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 ); 1171 1171 auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 ); 1172 ast::OpenVarSet::const_iterator 1173 entry1 = var1 ? open.find( var1->name ) : open.end(), 1172 ast::OpenVarSet::const_iterator 1173 entry1 = var1 ? open.find( var1->name ) : open.end(), 1174 1174 entry2 = var2 ? open.find( var2->name ) : open.end(); 1175 1175 bool isopen1 = entry1 != open.end(); … … 1178 1178 if ( isopen1 && isopen2 ) { 1179 1179 if ( entry1->second.kind != entry2->second.kind ) return false; 1180 return env.bindVarToVar( 1181 var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have, 1180 return env.bindVarToVar( 1181 var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have, 1182 1182 open, widen, symtab ); 1183 1183 } else if ( isopen1 ) { … … 1192 1192 } 1193 1193 1194 bool unifyInexact( 1195 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1196 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1197 const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab, 1198 ast::ptr<ast::Type> & common 1194 bool unifyInexact( 1195 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1196 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1197 const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab, 1198 ast::ptr<ast::Type> & common 1199 1199 ) { 1200 1200 ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers; 1201 1202 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and 1201 1202 // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and 1203 1203 // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1 1204 1204 ast::ptr<ast::Type> t1{ type1 }, t2{ type2 }; 1205 1205 reset_qualifiers( t1 ); 1206 1206 reset_qualifiers( t2 ); 1207 1207 1208 1208 if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) { 1209 1209 t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones
Note: See TracChangeset
for help on using the changeset viewer.