[SR-15254] Trunk snapshot compiler for linux x86_64 crashes with "Invalid type parameter in getCanonicalTypeInContext()" when compiling the swift-algorithms package

[finagolfin]

Previous ID	SR-15254
Radar	rdar://problem/84827656
Original Reporter	@buttaface
Type	Bug
Status	Resolved
Resolution	Done

Environment

Fedora Core 33 x86_64

Additional Detail from JIRA

Votes	0
Component/s	Compiler
Labels	Bug
Assignee	@jckarter
Priority	Medium

md5: 450612a3e0018954fb5fa001b9d1443e

is duplicated by:

• SR-15437 Compiler Crash when swift-alorithms is a Package Dependency

Issue Description:

The following command with the latest official trunk snapshot build ~/swift-DEVELOPMENT-SNAPSHOT-2021-09-27-a-centos8/usr/bin/swift build crashes the compiler with this long output:

error: emit-module command failed due to signal 6 (use -v to see invocation)
Invalid type parameter in getCanonicalTypeInContext()
Original type: Optional<τ_0_1.Element.Index>
Simplified term: τ_0_1.[Collection:Element].[Collection:Index]
Longest valid prefix: τ_0_1.[Collection:Element]
Prefix type: τ_0_1.Element

Requirement machine for <τ_0_0, τ_0_1 where τ_0_1 : Collection>
Rewrite system:
Unknown macro: { - [Collection].Element => [Collection}
Homotopy generators:
Unknown macro: { - [Collection].[Sequence}
Property map:
Unknown macro: { [Collection] => { conforms_to}
[Collection:Index] =>
Unknown macro: { conforms_to}
[Collection:Indices] =>
Unknown macro: { conforms_to}
[Collection:SubSequence] =>
Unknown macro: { conforms_to}
[Comparable] =>
Unknown macro: { conforms_to}
[Sequence:Iterator] =>
Unknown macro: { conforms_to}
τ_0_1 =>
Unknown macro: { conforms_to}
[Collection:Iterator] =>
Unknown macro: { conforms_to}
}

Conformance access paths:
Please submit a bug report (https://swift.org/contributing/#reporting-bugs) and include the project and the crash backtrace.
Stack dump:
0. Program arguments: /home/butta/swift-DEVELOPMENT-SNAPSHOT-2021-09-27-a-centos8/usr/bin/swift-frontend -frontend -emit-module -experimental-skip-non-inlinable-function-bodies-without-types /home/butta/src/swift-algorithms/Sources/Algorithms/AdjacentPairs.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Chain.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Chunked.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Combinations.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Compacted.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Cycle.swift /home/butta/src/swift-algorithms/Sources/Algorithms/EitherSequence.swift /home/butta/src/swift-algorithms/Sources/Algorithms/FirstNonNil.swift /home/butta/src/swift-algorithms/Sources/Algorithms/FlattenCollection.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Indexed.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Intersperse.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Joined.swift /home/butta/src/swift-algorithms/Sources/Algorithms/MinMax.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Partition.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Permutations.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Product.swift /home/butta/src/swift-algorithms/Sources/Algorithms/RandomSample.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Reductions.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Rotate.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Split.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Stride.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Suffix.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Trim.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Unique.swift /home/butta/src/swift-algorithms/Sources/Algorithms/Windows.swift -target x86_64-unknown-linux-gnu -disable-objc-interop -I /home/butta/src/swift-algorithms/.build/x86_64-unknown-linux-gnu/debug -enable-testing -g -module-cache-path /home/butta/src/swift-algorithms/.build/x86_64-unknown-linux-gnu/debug/ModuleCache -swift-version 5 -Onone -D SWIFT_PACKAGE -D DEBUG -new-driver-path /home/butta/swift-DEVELOPMENT-SNAPSHOT-2021-09-27-a-centos8/usr/bin/swift-driver -resource-dir /home/butta/swift-DEVELOPMENT-SNAPSHOT-2021-09-27-a-centos8/usr/lib/swift -enable-anonymous-context-mangled-names -Xcc -fmodule-map-file=/home/butta/src/swift-numerics/Sources/_NumericsShims/include/module.modulemap -Xcc -I -Xcc /home/butta/src/swift-numerics/Sources/_NumericsShims/include -module-name Algorithms -emit-module-doc-path /home/butta/src/swift-algorithms/.build/x86_64-unknown-linux-gnu/debug/Algorithms.swiftdoc -emit-module-source-info-path /home/butta/src/swift-algorithms/.build/x86_64-unknown-linux-gnu/debug/Algorithms.swiftsourceinfo -parse-as-library -o /home/butta/src/swift-algorithms/.build/x86_64-unknown-linux-gnu/debug/Algorithms.swiftmodule -emit-abi-descriptor-path /home/butta/src/swift-algorithms/.build/x86_64-unknown-linux-gnu/debug/Algorithms.abi.json

1. Swift version 5.6-dev (LLVM ae102eaadf2d38c, Swift e7342eb)
2. Compiling with the current language version
3. While evaluating request ASTLoweringRequest(Lowering AST to SIL for module Algorithms)
4. While silgen emitFunction SIL function "@$s10Algorithms17FlattenCollectionV13offsetForward_2by9limitedByAC5IndexVyx_GSgAI_SiAItF".
   for 'offsetForward(_:by:limitedBy:)' (at /home/butta/src/swift-algorithms/Sources/Algorithms/FlattenCollection.swift:157:12)
   Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var LLVM_SYMBOLIZER_PATH to point to it):
   It appears to have started crashing with the Sep. 25 snapshot, as everything works with the Sep. 24 snapshot. I first saw this on my Android CI, where I had to disable cross-compiling with the trunk snapshots because of this crasher.

[LucianoPAlmeida]

Maybe RequirementMachine changes in #39255
cc @slavapestov

[slavapestov]

Thanks for the bug report, I'll take a look. As a workaround, you can pass the "-Xfrontend -requirement-machine=off" compiler flag.

[slavapestov]

It's a bug in SIL type lowering that's exposed by stricter asserts in the requirement machine.

Here is a reduced test case:

protocol P1 {
  associatedtype Element
  associatedtype Index
}

struct S1<Base> where Base: P1, Base.Element: P1 {
  let x: Base.Element.Index
}

struct S2<Base> where Base : P1, Base.Element: P1 {
  func foo(index: S1<Base>?) {
    _ = index.map({ _ = $0 })
  }
}

[slavapestov]

@swift-ci create

[slavapestov]

Joe merged #40112 thanks Joe!

[finagolfin]

This is still crashing my Android CI when trying to cross-compile swift-algorithms trunk with the latest official Nov. 12 trunk snapshot build, which contains Joe's fix. I tried it on Fedora when natively compiling for linux x86-64 and I can reproduce.

I saw that Joe ran the source compatibility suite on his pull, so I checked and it builds a commit from last December, with which I could not reproduce this crash. So I bisected swift-algorithms on Fedora with the Nov. 12 snapshot toolchain and I first got it to crash with this June pull. Any subsequent swift-algorithms commit still crashes the compiler with the above error, if Slava's workaround flags are not applied.

[slavapestov]

Thanks for the update, we'll take a look.

[slavapestov]

Looks like SIL type lowering is still broken, here is the reduction:

protocol P1 {
  associatedtype Element
  associatedtype Index
}

struct S0<X> {} 

extension S0: P1 where X: P1 {
  typealias Element = X.Element
  typealias Index = S0<X.Index>
}

struct S1<X, Y>: P1 where X: P1 {
  typealias Element = Y
  typealias Index = X.Index
}

struct S2<X> where X: P1, X.Element: P1 {
  let field: X.Element.Index
}

struct S3<X> where X: P1 {
  func callee(_: S2<S1<X, S0<X>>>) {}

  func caller() {
    _ = { (x: S2<S1<X, S0<X>>>) in callee(x) }
  }
}

[slavapestov]

We don't record a "τ_0_4 : P1" requirement, and the type "S<τ_0_4>" appearing in the same-type requirement is therefore invalid because the conditional requirement that's needed to make "S<τ_0_4>" conform to P1 isn't satisfied:

Invalid type parameter in getCanonicalTypeInContext()
Original type: S0<τ_0_4.Index>
Simplified term: τ_0_4.[P1:Index]
Longest valid prefix: τ_0_4
Prefix type: τ_0_4

Requirement machine for <τ_0_0, τ_0_1, τ_0_2, τ_0_3, τ_0_4, τ_0_5 where τ_0_0 == S1<τ_0_1, S0<τ_0_4>>, τ_0_1 : P1, τ_0_1 == τ_0_3, τ_0_2 == S0<τ_0_4>, τ_0_4 == τ_0_5>

[slavapestov]

Looks like a GSB bug.

[slavapestov]

It appears that while Joe's fix was necessary, it was not sufficient, there was another bug. I have verified that #40256 builds the latest swift-algorithms version.