OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/class_finalizer.h" | 5 #include "vm/class_finalizer.h" |
6 | 6 |
7 #include "vm/code_generator.h" | 7 #include "vm/code_generator.h" |
8 #include "vm/flags.h" | 8 #include "vm/flags.h" |
9 #include "vm/hash_table.h" | 9 #include "vm/hash_table.h" |
10 #include "vm/heap.h" | 10 #include "vm/heap.h" |
(...skipping 656 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
667 const intptr_t num_type_params = type_cls.NumTypeParameters(); | 667 const intptr_t num_type_params = type_cls.NumTypeParameters(); |
668 const intptr_t first_type_param = num_type_args - num_type_params; | 668 const intptr_t first_type_param = num_type_args - num_type_params; |
669 // If the type is not generic (num_type_params == 0) or if its type parameters | 669 // If the type is not generic (num_type_params == 0) or if its type parameters |
670 // are instantiated, no divergence can occur. Note that if the type parameters | 670 // are instantiated, no divergence can occur. Note that if the type parameters |
671 // are null, i.e. if the generic type is raw, they are considered | 671 // are null, i.e. if the generic type is raw, they are considered |
672 // instantiated and no divergence can occur. | 672 // instantiated and no divergence can occur. |
673 if ((num_type_params == 0) || | 673 if ((num_type_params == 0) || |
674 arguments.IsSubvectorInstantiated(first_type_param, num_type_params)) { | 674 arguments.IsSubvectorInstantiated(first_type_param, num_type_params)) { |
675 return; | 675 return; |
676 } | 676 } |
677 // The type parameters are not instantiated. Verify that there is no other | 677 // Consider mutually recursive and uninstantiated types pending finalization |
678 // type pending finalization with the same type class, but different | 678 // with the same type class and report an error if they are not equal in their |
679 // uninstantiated type parameters. | 679 // raw form, i.e. where each type parameter is substituted with dynamic. |
| 680 // This test eliminates divergent types without restricting recursive types |
| 681 // typically found in the wild. |
680 TypeArguments& pending_arguments = TypeArguments::Handle(zone); | 682 TypeArguments& pending_arguments = TypeArguments::Handle(zone); |
681 const intptr_t num_pending_types = pending_types->length(); | 683 const intptr_t num_pending_types = pending_types->length(); |
682 for (intptr_t i = num_pending_types - 1; i >= 0; i--) { | 684 for (intptr_t i = num_pending_types - 1; i >= 0; i--) { |
683 const AbstractType& pending_type = pending_types->At(i); | 685 const AbstractType& pending_type = pending_types->At(i); |
684 if (FLAG_trace_type_finalization) { | 686 if (FLAG_trace_type_finalization) { |
685 THR_Print(" Comparing with pending type '%s': %s\n", | 687 THR_Print(" Comparing with pending type '%s': %s\n", |
686 String::Handle(pending_type.Name()).ToCString(), | 688 String::Handle(pending_type.Name()).ToCString(), |
687 pending_type.ToCString()); | 689 pending_type.ToCString()); |
688 } | 690 } |
689 if ((pending_type.raw() != type.raw()) && pending_type.IsType() && | 691 if ((pending_type.raw() != type.raw()) && pending_type.IsType() && |
690 (pending_type.type_class() == type_cls.raw())) { | 692 (pending_type.type_class() == type_cls.raw())) { |
691 pending_arguments = pending_type.arguments(); | 693 pending_arguments = pending_type.arguments(); |
692 if (!pending_arguments.IsSubvectorEquivalent(arguments, first_type_param, | 694 if (!pending_arguments.IsSubvectorEquivalent(arguments, first_type_param, |
693 num_type_params) && | 695 num_type_params) && |
694 !pending_arguments.IsSubvectorInstantiated(first_type_param, | 696 !pending_arguments.IsSubvectorInstantiated(first_type_param, |
695 num_type_params)) { | 697 num_type_params)) { |
696 // Reject the non-contractive recursive type. | 698 const TypeArguments& instantiated_arguments = TypeArguments::Handle( |
697 const String& type_name = String::Handle(zone, type.Name()); | 699 zone, arguments.InstantiateFrom(Object::null_type_arguments(), |
698 ReportError(cls, type.token_pos(), "illegal recursive type '%s'", | 700 Object::null_type_arguments(), NULL, |
699 type_name.ToCString()); | 701 NULL, NULL, Heap::kNew)); |
| 702 const TypeArguments& instantiated_pending_arguments = |
| 703 TypeArguments::Handle(zone, pending_arguments.InstantiateFrom( |
| 704 Object::null_type_arguments(), |
| 705 Object::null_type_arguments(), NULL, |
| 706 NULL, NULL, Heap::kNew)); |
| 707 if (!instantiated_pending_arguments.IsSubvectorEquivalent( |
| 708 instantiated_arguments, first_type_param, num_type_params)) { |
| 709 const String& type_name = String::Handle(zone, type.Name()); |
| 710 ReportError(cls, type.token_pos(), "illegal recursive type '%s'", |
| 711 type_name.ToCString()); |
| 712 } |
700 } | 713 } |
701 } | 714 } |
702 } | 715 } |
703 } | 716 } |
704 | 717 |
705 | 718 |
706 // Expand the type arguments of the given type and finalize its full type | 719 // Expand the type arguments of the given type and finalize its full type |
707 // argument vector. Return the number of type arguments (0 for a raw type). | 720 // argument vector. Return the number of type arguments (0 for a raw type). |
708 intptr_t ClassFinalizer::ExpandAndFinalizeTypeArguments( | 721 intptr_t ClassFinalizer::ExpandAndFinalizeTypeArguments( |
709 const Class& cls, | 722 const Class& cls, |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
747 // Make the type raw and continue without reporting any error. | 760 // Make the type raw and continue without reporting any error. |
748 // A static warning should have been reported. | 761 // A static warning should have been reported. |
749 arguments = TypeArguments::null(); | 762 arguments = TypeArguments::null(); |
750 type.set_arguments(arguments); | 763 type.set_arguments(arguments); |
751 } | 764 } |
752 | 765 |
753 // Mark the type as being finalized in order to detect self reference and | 766 // Mark the type as being finalized in order to detect self reference and |
754 // postpone bound checking (if required) until after all types in the graph of | 767 // postpone bound checking (if required) until after all types in the graph of |
755 // mutually recursive types are finalized. | 768 // mutually recursive types are finalized. |
756 type.SetIsBeingFinalized(); | 769 type.SetIsBeingFinalized(); |
757 if (pending_types != NULL) { | 770 ASSERT(pending_types != NULL); |
758 pending_types->Add(type); | 771 pending_types->Add(type); |
759 } | |
760 | 772 |
761 // The full type argument vector consists of the type arguments of the | 773 // The full type argument vector consists of the type arguments of the |
762 // super types of type_class, which are initialized from the parsed | 774 // super types of type_class, which are initialized from the parsed |
763 // type arguments, followed by the parsed type arguments. | 775 // type arguments, followed by the parsed type arguments. |
764 TypeArguments& full_arguments = TypeArguments::Handle(zone); | 776 TypeArguments& full_arguments = TypeArguments::Handle(zone); |
765 if (FLAG_reify && (num_type_arguments > 0)) { | 777 if (FLAG_reify && (num_type_arguments > 0)) { |
766 // If no type arguments were parsed and if the super types do not prepend | 778 // If no type arguments were parsed and if the super types do not prepend |
767 // type arguments to the vector, we can leave the vector as null. | 779 // type arguments to the vector, we can leave the vector as null. |
768 if (!arguments.IsNull() || (num_type_arguments > num_type_parameters)) { | 780 if (!arguments.IsNull() || (num_type_arguments > num_type_parameters)) { |
769 full_arguments = TypeArguments::New(num_type_arguments); | 781 full_arguments = TypeArguments::New(num_type_arguments); |
(...skipping 148 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
918 "Instantiating TypeRef '%s': '%s'\n" | 930 "Instantiating TypeRef '%s': '%s'\n" |
919 " instantiator: '%s'\n", | 931 " instantiator: '%s'\n", |
920 String::Handle(super_type_arg.Name()).ToCString(), | 932 String::Handle(super_type_arg.Name()).ToCString(), |
921 ref_type.ToCString(), arguments.ToCString()); | 933 ref_type.ToCString(), arguments.ToCString()); |
922 } | 934 } |
923 // In the typical case of an F-bounded type, the instantiation of the | 935 // In the typical case of an F-bounded type, the instantiation of the |
924 // super_type_arg from arguments is a fixpoint. Take the shortcut. | 936 // super_type_arg from arguments is a fixpoint. Take the shortcut. |
925 // Example: class B<T>; class D<T> extends B<D<T>>; | 937 // Example: class B<T>; class D<T> extends B<D<T>>; |
926 // While finalizing D<T>, the super type arg D<T> (a typeref) gets | 938 // While finalizing D<T>, the super type arg D<T> (a typeref) gets |
927 // instantiated from vector [T], yielding itself. | 939 // instantiated from vector [T], yielding itself. |
928 if (super_type_arg.IsTypeRef() && super_type_arg.IsBeingFinalized() && | 940 if (super_type_arg.IsTypeRef() && |
929 (super_type_arg.arguments() == arguments.raw())) { | 941 (super_type_arg.arguments() == arguments.raw())) { |
| 942 ASSERT(super_type_arg.IsBeingFinalized()); |
930 arguments.SetTypeAt(i, super_type_arg); | 943 arguments.SetTypeAt(i, super_type_arg); |
931 continue; | 944 continue; |
932 } | 945 } |
933 Error& error = Error::Handle(); | 946 Error& error = Error::Handle(); |
934 super_type_arg = super_type_arg.InstantiateFrom( | 947 super_type_arg = super_type_arg.InstantiateFrom( |
935 arguments, Object::null_type_arguments(), &error, | 948 arguments, Object::null_type_arguments(), &error, |
936 instantiation_trail, NULL, Heap::kOld); | 949 instantiation_trail, NULL, Heap::kOld); |
937 if (!error.IsNull()) { | 950 if (!error.IsNull()) { |
938 // InstantiateFrom does not report an error if the type is still | 951 // InstantiateFrom does not report an error if the type is still |
939 // uninstantiated. Instead, it will return a new BoundedType so | 952 // uninstantiated. Instead, it will return a new BoundedType so |
940 // that the check is postponed to run time. | 953 // that the check is postponed to run time. |
941 ASSERT(super_type_arg.IsInstantiated()); | 954 ASSERT(super_type_arg.IsInstantiated()); |
942 // Keep only the first bound error. | 955 // Keep only the first bound error. |
943 if (bound_error->IsNull()) { | 956 if (bound_error->IsNull()) { |
944 *bound_error = error.raw(); | 957 *bound_error = error.raw(); |
945 } | 958 } |
946 } | 959 } |
947 if (super_type_arg.IsBeingFinalized()) { | 960 if (super_type_arg.IsBeingFinalized()) { |
948 // The super_type_arg was instantiated from a type being finalized. | 961 // The super_type_arg was instantiated from a type being finalized. |
949 // We need to finish finalizing its type arguments. | 962 // We need to finish finalizing its type arguments. |
950 ASSERT(super_type_arg.IsTypeRef()); | 963 ASSERT(super_type_arg.IsTypeRef()); |
951 AbstractType& ref_super_type_arg = | 964 AbstractType& ref_super_type_arg = |
952 AbstractType::Handle(TypeRef::Cast(super_type_arg).type()); | 965 AbstractType::Handle(TypeRef::Cast(super_type_arg).type()); |
| 966 if (FLAG_trace_type_finalization) { |
| 967 THR_Print("Instantiated TypeRef '%s': '%s'\n", |
| 968 String::Handle(super_type_arg.Name()).ToCString(), |
| 969 ref_super_type_arg.ToCString()); |
| 970 } |
| 971 CheckRecursiveType(cls, ref_super_type_arg, pending_types); |
| 972 pending_types->Add(ref_super_type_arg); |
| 973 const Class& super_cls = |
| 974 Class::Handle(ref_super_type_arg.type_class()); |
| 975 const TypeArguments& super_args = |
| 976 TypeArguments::Handle(ref_super_type_arg.arguments()); |
| 977 // Mark as finalized before finalizing to avoid cycles. |
953 ref_super_type_arg.SetIsFinalized(); | 978 ref_super_type_arg.SetIsFinalized(); |
954 const Class& cls = Class::Handle(ref_super_type_arg.type_class()); | 979 // Since the instantiator is different, do not pass the current |
| 980 // instantiation trail, but create a new one by passing NULL. |
955 FinalizeTypeArguments( | 981 FinalizeTypeArguments( |
956 cls, TypeArguments::Handle(ref_super_type_arg.arguments()), | 982 super_cls, super_args, |
957 cls.NumTypeArguments() - cls.NumTypeParameters(), bound_error, | 983 super_cls.NumTypeArguments() - super_cls.NumTypeParameters(), |
958 pending_types, instantiation_trail); | 984 bound_error, pending_types, NULL); |
| 985 if (FLAG_trace_type_finalization) { |
| 986 THR_Print("Finalized instantiated TypeRef '%s': '%s'\n", |
| 987 String::Handle(super_type_arg.Name()).ToCString(), |
| 988 ref_super_type_arg.ToCString()); |
| 989 } |
959 } | 990 } |
960 } | 991 } |
961 } | 992 } |
962 arguments.SetTypeAt(i, super_type_arg); | 993 arguments.SetTypeAt(i, super_type_arg); |
963 } | 994 } |
964 FinalizeTypeArguments(super_class, arguments, super_offset, bound_error, | 995 FinalizeTypeArguments(super_class, arguments, super_offset, bound_error, |
965 pending_types, instantiation_trail); | 996 pending_types, instantiation_trail); |
966 } | 997 } |
967 } | 998 } |
968 | 999 |
(...skipping 235 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1204 } | 1235 } |
1205 | 1236 |
1206 // We do not canonicalize type parameters. | 1237 // We do not canonicalize type parameters. |
1207 return type_parameter.raw(); | 1238 return type_parameter.raw(); |
1208 } | 1239 } |
1209 | 1240 |
1210 // At this point, we can only have a Type. | 1241 // At this point, we can only have a Type. |
1211 ASSERT(type.IsType()); | 1242 ASSERT(type.IsType()); |
1212 | 1243 |
1213 // This type is the root type of the type graph if no pending types queue is | 1244 // This type is the root type of the type graph if no pending types queue is |
1214 // allocated yet, and if canonicalization is required. | 1245 // allocated yet. |
1215 const bool is_root_type = | 1246 const bool is_root_type = pending_types == NULL; |
1216 (pending_types == NULL) && (finalization >= kCanonicalize); | |
1217 if (is_root_type) { | 1247 if (is_root_type) { |
1218 pending_types = new PendingTypes(zone, 4); | 1248 pending_types = new PendingTypes(zone, 4); |
1219 } | 1249 } |
1220 | 1250 |
1221 const intptr_t num_expanded_type_arguments = | 1251 const intptr_t num_expanded_type_arguments = |
1222 ExpandAndFinalizeTypeArguments(cls, type, pending_types); | 1252 ExpandAndFinalizeTypeArguments(cls, type, pending_types); |
1223 | 1253 |
1224 // Self referencing types may get finalized indirectly. | 1254 // Self referencing types may get finalized indirectly. |
1225 if (!type.IsFinalized()) { | 1255 if (!type.IsFinalized()) { |
1226 // If the type is a function type, we also need to finalize the types in its | 1256 // If the type is a function type, we also need to finalize the types in its |
(...skipping 2543 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3770 ProgramVisitor::VisitFunctions(&function_visitor); | 3800 ProgramVisitor::VisitFunctions(&function_visitor); |
3771 | 3801 |
3772 class ClearCodeClassVisitor : public ClassVisitor { | 3802 class ClearCodeClassVisitor : public ClassVisitor { |
3773 void Visit(const Class& cls) { cls.DisableAllocationStub(); } | 3803 void Visit(const Class& cls) { cls.DisableAllocationStub(); } |
3774 }; | 3804 }; |
3775 ClearCodeClassVisitor class_visitor; | 3805 ClearCodeClassVisitor class_visitor; |
3776 ProgramVisitor::VisitClasses(&class_visitor); | 3806 ProgramVisitor::VisitClasses(&class_visitor); |
3777 } | 3807 } |
3778 | 3808 |
3779 } // namespace dart | 3809 } // namespace dart |
OLD | NEW |