tracking bug for known issues with the "strictly more complex" rule for impl termination

[zygoloid]

trafficstars

This issue tracks known cases where the termination rule for impl selection rejects code that would not encounter a cycle. At some point we will need to check whether the rule is behaving as we expect, and these cases will help us refine the rule or select a new one.

[zygoloid]

Given a single impl that performs all builtin conversions:

impl forall [template U:! type, template T:! __builtin_implicit_as(U)] T as ImplicitAs(U);

... if we specify that a builtin conversion from (T1, T2, ..., Tn) to [T; n] first performs an implicit conversion from (T1, T2, ..., Tn) to (T, T, ..., T), then we find this false positive:

• outer query: ((i32, i32, i32), (i32, i32, i32)) as ImplicitAs([[i32; 3]; 2]) has {i32: 7, ints: 5, (): 3, []: 2, ImplicitAs: 1}
• inner query: ((i32, i32, i32), (i32, i32, i32)) as ImplicitAs([i32; 3], [i32; 3]) has {i32: 8, ints: 6, (): 3, []: 2, ImplicitAs: 1}

The problem here is that we have expanded the query to a larger one by expanding the array to its elements, but haven't removed a [] label because the array element is also an array.

Possible fixes:

1. Split this impl into separate impls for tuple -> tuple and for tuple -> array.
2. Don't perform an implicit conversion from (T1, T2, ..., Tn) to (T, T, ..., T) at all; instead only implicitly convert T1 to T, T2 to T, ..., Tn to T.
3. Make use of depth information in some way; the outer query is deeper than the inner one, and its deepest [] and i32 labels are deeper. The inner query is simpler in terms of tree depth.