Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Stuck in infinite internal loop, using mixins and recursive generic types #51960

Closed
DrafaKiller opened this issue Apr 5, 2023 · 3 comments
Closed

Stuck in infinite internal loop, using mixins and recursive generic types #51960

DrafaKiller opened this issue Apr 5, 2023 · 3 comments
Assignees
@alexmarkov
Labels
area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. P2 A bug or feature request we're likely to work on type-bug Incorrect behavior (everything from a crash to more subtle misbehavior)

Comments

@DrafaKiller
Copy link

DrafaKiller commented Apr 5, 2023 •
edited
Loading

I'm running into a problem, when using mixins and recursive generic types. The weird behavior is that it works fine with 3 generic types, but enters an infinite loop with 4 generic types.

Dart doesn't run.

  • Why does it get stuck with 4 generic types but not with 3?
  • Is there any work around?

It's difficult to explain, so it's easier to just show the examples.

How to reproduce

Simply import a file with the following code, or try to run it using an empty main function.

✅ Runs fine

  • 3 Classes & Mixins
  • 3 Generic types extending
Click to view example 
/* -= Classes =- */

class A<
  A1 extends A<A1, B1, C1>,
  B1 extends B<A1, B1, C1>,
  C1 extends C<A1, B1, C1>
> {}

class B<
  A1 extends A<A1, B1, C1>,
  B1 extends B<A1, B1, C1>,
  C1 extends C<A1, B1, C1>
> {}

class C<
  A1 extends A<A1, B1, C1>,
  B1 extends B<A1, B1, C1>,
  C1 extends C<A1, B1, C1>
> {}

/* -= Mixins =- */

mixin MixinA<
  A1 extends MixinA<A1, B1, C1>,
  B1 extends MixinB<A1, B1, C1>,
  C1 extends MixinC<A1, B1, C1>
> on A<
  MixinA<A1, B1, C1>,
  MixinB<A1, B1, C1>,
  MixinC<A1, B1, C1>
> {}

mixin MixinB<
  A1 extends MixinA<A1, B1, C1>,
  B1 extends MixinB<A1, B1, C1>,
  C1 extends MixinC<A1, B1, C1>
> on B<
  MixinA<A1, B1, C1>,
  MixinB<A1, B1, C1>,
  MixinC<A1, B1, C1>
> {}

mixin MixinC<
  A1 extends MixinA<A1, B1, C1>,
  B1 extends MixinB<A1, B1, C1>,
  C1 extends MixinC<A1, B1, C1>
> on C<
  MixinA<A1, B1, C1>,
  MixinB<A1, B1, C1>,
  MixinC<A1, B1, C1>
> {}

❌ Gets stuck

  • 4 Classes & Mixins
  • 4 Generic types extending
Click to view example 
/* -= Classes =- */

class A<
  A1 extends A<A1, B1, C1, D1>,
  B1 extends B<A1, B1, C1, D1>,
  C1 extends C<A1, B1, C1, D1>,
  D1 extends D<A1, B1, C1, D1>
> {}

class B<
  A1 extends A<A1, B1, C1, D1>,
  B1 extends B<A1, B1, C1, D1>,
  C1 extends C<A1, B1, C1, D1>,
  D1 extends D<A1, B1, C1, D1>
> {}

class C<
  A1 extends A<A1, B1, C1, D1>,
  B1 extends B<A1, B1, C1, D1>,
  C1 extends C<A1, B1, C1, D1>,
  D1 extends D<A1, B1, C1, D1>
> {}

class D<
  A1 extends A<A1, B1, C1, D1>,
  B1 extends B<A1, B1, C1, D1>,
  C1 extends C<A1, B1, C1, D1>,
  D1 extends D<A1, B1, C1, D1>
> {}

/* -= Mixins =- */

mixin MixinA<
  A1 extends MixinA<A1, B1, C1, D1>,
  B1 extends MixinB<A1, B1, C1, D1>,
  C1 extends MixinC<A1, B1, C1, D1>,
  D1 extends MixinD<A1, B1, C1, D1>
> on A<
  MixinA<A1, B1, C1, D1>,
  MixinB<A1, B1, C1, D1>,
  MixinC<A1, B1, C1, D1>,
  MixinD<A1, B1, C1, D1>
> {}

mixin MixinB<
  A1 extends MixinA<A1, B1, C1, D1>,
  B1 extends MixinB<A1, B1, C1, D1>,
  C1 extends MixinC<A1, B1, C1, D1>,
  D1 extends MixinD<A1, B1, C1, D1>
> on B<
  MixinA<A1, B1, C1, D1>,
  MixinB<A1, B1, C1, D1>,
  MixinC<A1, B1, C1, D1>,
  MixinD<A1, B1, C1, D1>
> {}

mixin MixinC<
  A1 extends MixinA<A1, B1, C1, D1>,
  B1 extends MixinB<A1, B1, C1, D1>,
  C1 extends MixinC<A1, B1, C1, D1>,
  D1 extends MixinD<A1, B1, C1, D1>
> on C<
  MixinA<A1, B1, C1, D1>,
  MixinB<A1, B1, C1, D1>,
  MixinC<A1, B1, C1, D1>,
  MixinD<A1, B1, C1, D1>
> {}

mixin MixinD<
  A1 extends MixinA<A1, B1, C1, D1>,
  B1 extends MixinB<A1, B1, C1, D1>,
  C1 extends MixinC<A1, B1, C1, D1>,
  D1 extends MixinD<A1, B1, C1, D1>
> on D<
  MixinA<A1, B1, C1, D1>,
  MixinB<A1, B1, C1, D1>,
  MixinC<A1, B1, C1, D1>,
  MixinD<A1, B1, C1, D1>
> {}

Environment

  • Dart SDK version: 2.19.2 & 3.0.0-edge
  • Operating system: Windows 11
@DrafaKiller DrafaKiller changed the title Stuck in infinite loop, using mixins and recursive generic types Stuck in infinite internal loop, using mixins and recursive generic types Apr 5, 2023
@DrafaKiller
Copy link
Author

I found a workaround, instead of declaring the Mixins like:

mixin MixinA<
  A1 extends MixinA<A1, B1, C1, D1>,
  B1 extends MixinB<A1, B1, C1, D1>,
  C1 extends MixinC<A1, B1, C1, D1>,
  D1 extends MixinD<A1, B1, C1, D1>
> on A<
  MixinA<A1, B1, C1, D1>,
  MixinB<A1, B1, C1, D1>,
  MixinC<A1, B1, C1, D1>,
  MixinD<A1, B1, C1, D1>
> {}

It works if I declare them like:

mixin MixinA<
  A1 extends MixinA<A1, B1, C1, D1>,
  B1 extends MixinB<A1, B1, C1, D1>,
  C1 extends MixinC<A1, B1, C1, D1>,
  D1 extends MixinD<A1, B1, C1, D1>
> on A<A1, B1, C1, D1> {}

But I still don't understand why it works with 3 Mixins but not with 4 Mixins.

@a-siva a-siva added area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) P2 A bug or feature request we're likely to work on labels Apr 5, 2023
@a-siva
Copy link
Contributor

a-siva commented Apr 5, 2023

We seem to get into an infinite loop in dart::TypeArguments::InstantiateFrom

#0  0x000055d86482ab69 in dart::VMHandles::IsZoneHandle (handle=94388435951120) at ../../out/DebugX64/../../runtime/vm/handles.cc:55
#1  0x000055d8649329e3 in dart::Object::IsZoneHandle (this=0x55d885321e10) at ../../out/DebugX64/../../runtime/vm/object.cc:2911
#2  dart::Object::IsNotTemporaryScopedHandle (this=0x55d885321e10) at ../../out/DebugX64/../../runtime/vm/object.cc:2919
#3  dart::AbstractType::OnlyBuddyInTrail (this=this@entry=0x55d885c72458, trail=trail@entry=0x7f73d6263228) at ../../out/DebugX64/../../runtime/vm/object.cc:20945
#4  0x000055d864939bec in dart::TypeRef::InstantiateFrom (this=0x55d885c72458, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:22651
#5  0x000055d8648cbd6e in dart::TypeArguments::InstantiateFrom (this=this@entry=0x55d885c71db0, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=num_free_fun_type_params@entry=0, space=space@entry=dart::Heap::kOld, trail=trail@entry=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:7360
#6  0x000055d864934fa7 in dart::Type::InstantiateFrom (this=0x55d885c71d68, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:21743
#7  0x000055d864939cc2 in dart::TypeRef::InstantiateFrom (this=<optimized out>, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:22661
#8  0x000055d8648cbd6e in dart::TypeArguments::InstantiateFrom (this=this@entry=0x55d885c71c00, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=num_free_fun_type_params@entry=0, space=space@entry=dart::Heap::kOld, trail=trail@entry=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:7360
#9  0x000055d864934fa7 in dart::Type::InstantiateFrom (this=0x55d885c71bb8, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:21743
#10 0x000055d864939cc2 in dart::TypeRef::InstantiateFrom (this=<optimized out>, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:22661
#11 0x000055d8648cbd6e in dart::TypeArguments::InstantiateFrom (this=this@entry=0x55d885c71ae0, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=num_free_fun_type_params@entry=0, space=space@entry=dart::Heap::kOld, trail=trail@entry=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:7360
#12 0x000055d864934fa7 in dart::Type::InstantiateFrom (this=0x55d885c71a98, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:21743
#13 0x000055d864939cc2 in dart::TypeRef::InstantiateFrom (this=<optimized out>, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:22661
#14 0x000055d8648cbd6e in dart::TypeArguments::InstantiateFrom (this=this@entry=0x55d885c71960, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=num_free_fun_type_params@entry=0, space=space@entry=dart::Heap::kOld, trail=trail@entry=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:7360
#15 0x000055d864934fa7 in dart::Type::InstantiateFrom (this=0x55d885c71918, instantiator_type_arguments=..., function_type_arguments=..., num_free_fun_type_params=0, space=dart::Heap::kOld, trail=0x7f73d6263228, num_parent_type_args_adjustment=0) at ../../out/DebugX64/../../runtime/vm/object.cc:21743

@alexmarkov
Copy link
Contributor

This example doesn't stuck in the infinite loop, it finishes in about 15m on my machine. However, it hits an edge case in the handling of recursive types in the VM, resulting in a huge number of TypeRef objects created and added/queried in a TrailPtr (> 10000), which quickly becomes a bottleneck.

I'm going to try to get rid of TypeRefs and simplify handling of recursive type, as outlined in #52022.

copybara-service bot pushed a commit that referenced this issue Apr 19, 2023
Revert "[vm] Avoid expanding/flattening type arguments vectors in Typ…
3e2d3bc 
…e objects"

This reverts commit 1354437.

Reason for revert: breaks many targets in G3, see b/278841863

Original change's description:
> [vm] Avoid expanding/flattening type arguments vectors in Type objects
>
> Previously, vectors of type arguments were expanded to include type
> arguments corresponding to superclasses both in the instances of
> generic classes and in Type objects (after type finalization).
> As a result, Type objects after finalization could be recursive and
> need to use extra TypeRef objects to break loops. The finalization of
> types was very complex and sometimes slow.
>
> This change simplifies the representation of Type objects: now they
> always have short type argument vectors, corresponding only to
> the type parameters of their own classes (both before and after
> finalization). Vectors of type arguments in the instances of generic
> classes are still expanded/flattened.
>
> This greatly simplifies type finalization, makes Type objects
> non-recursive and removes the need to create and handle excessive
> TypeRefs for type arguments corresponding to superclasses,
> as those type arguments are no longer included into types.
> The only remaining use of TypeRefs is for bounds of type parameters.
>
> In order to expand/flatten type arguments, new methods Type::GetInstanceTypeArguments / Class::GetInstanceTypeArguments
> are introduced. They build canonical declaration type arguments
> once (for each class), and then instantiate them as needed.
>
> There are also simple helper methods to shrink type arguments (TypeArguments::FromInstanceTypeArguments) and expand type arguments without filling type arguments corresponding to superclasses (TypeArguments::ToInstantiatorTypeArguments).
>
> Time of edge case 'regress_51960_test' 15min -> 300ms.
>
> TEST=ci, runtime/tests/vm/dart/regress_51960_test.dart
>
> Fixes #52022
> Fixes #51960
>
> Change-Id: I75b466b74698a33c0bb5e1dcbd29542e413812a1
> Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/295060
> Reviewed-by: Ryan Macnak <rmacnak@google.com>
> Commit-Queue: Alexander Markov <alexmarkov@google.com>

Change-Id: If0b2077305620593b8f03ebf6c135375c4086b1a
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/296182
Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
Reviewed-by: Alexander Thomas <athom@google.com>
Commit-Queue: Ilya Yanok <yanok@google.com>
copybara-service bot pushed a commit that referenced this issue Apr 19, 2023
@alexmarkov
Reland "[vm] Avoid expanding/flattening type arguments vectors in Typ…
7247a1b 
…e objects"

This is a reland of commit 1354437

Original change's description:
> [vm] Avoid expanding/flattening type arguments vectors in Type objects
>
> Previously, vectors of type arguments were expanded to include type
> arguments corresponding to superclasses both in the instances of
> generic classes and in Type objects (after type finalization).
> As a result, Type objects after finalization could be recursive and
> need to use extra TypeRef objects to break loops. The finalization of
> types was very complex and sometimes slow.
>
> This change simplifies the representation of Type objects: now they
> always have short type argument vectors, corresponding only to
> the type parameters of their own classes (both before and after
> finalization). Vectors of type arguments in the instances of generic
> classes are still expanded/flattened.
>
> This greatly simplifies type finalization, makes Type objects
> non-recursive and removes the need to create and handle excessive
> TypeRefs for type arguments corresponding to superclasses,
> as those type arguments are no longer included into types.
> The only remaining use of TypeRefs is for bounds of type parameters.
>
> In order to expand/flatten type arguments, new methods Type::GetInstanceTypeArguments / Class::GetInstanceTypeArguments
> are introduced. They build canonical declaration type arguments
> once (for each class), and then instantiate them as needed.
>
> There are also simple helper methods to shrink type arguments (TypeArguments::FromInstanceTypeArguments) and expand type arguments without filling type arguments corresponding to superclasses (TypeArguments::ToInstantiatorTypeArguments).
>
> Time of edge case 'regress_51960_test' 15min -> 300ms.
>
> TEST=ci, runtime/tests/vm/dart/regress_51960_test.dart
>
> Fixes #52022
> Fixes #51960
>
> Change-Id: I75b466b74698a33c0bb5e1dcbd29542e413812a1
> Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/295060
> Reviewed-by: Ryan Macnak <rmacnak@google.com>
> Commit-Queue: Alexander Markov <alexmarkov@google.com>

TEST=runtime/tests/vm/dart/regress_b_278841863_test.dart
Fixes b/278841863.

Change-Id: Ib1e20055bfb26e1df0a077300c69f0bec7152480
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/296300
Reviewed-by: Ryan Macnak <rmacnak@google.com>
Commit-Queue: Alexander Markov <alexmarkov@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@alexmarkov alexmarkov

Labels
area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. P2 A bug or feature request we're likely to work on type-bug Incorrect behavior (everything from a crash to more subtle misbehavior)
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@a-siva @alexmarkov @DrafaKiller