[SR-14776] Compilation of BigInt fails under 5.4.1, main and 5.5 nightlies

[tachyonics]

Previous ID	SR-14776
Radar	rdar://problem/79304885
Original Reporter	@tachyonics
Type	Bug
Status	Resolved
Resolution	Done

Environment

Swift: 5.4.1, main and 5.5 nightlies

Docker image: swift:5.4.1-amazonlinux2,

swiftlang/swift:nightly-main-amazonlinux2,

swiftlang/swift:nightly-5.5-amazonlinux2

Additional Detail from JIRA

Votes	0
Component/s
Labels	Bug
Assignee	@slavapestov
Priority	Medium

md5: 642755e51bec4543a09f9baea9c87a51

Issue Description:

Creating a package with just a copy of BigInt from https://github.com/apple/swift/blob/7123d2614b5f222d03b3762cb110d27a9dd98e24/test/Prototypes/BigInt.swift fails under Swift 5.4.1 and 5.5, main and 5.5 nightlies. It succeeds under 5.4.0.

```

1. Swift version 5.4.1 (swift-5.4.1-RELEASE)

2. While evaluating request TypeCheckSourceFileRequest(source_file "/workspace/Sources/SwiftCompilerCrashRepro/BigInt.swift")

3. While type-checking '_BigInt' (at /workspace/Sources/SwiftCompilerCrashRepro/BigInt.swift:78:8)

4. While evaluating request RequirementRequest(SwiftCompilerCrashRepro.(file)._BigInt@/workspace/Sources/SwiftCompilerCrashRepro/BigInt.swift:78:15, 0, interface)

5. While evaluating request ResolveTypeRequest(while resolving type , Word.Magnitude, (null))

6. While canonicalizing generic signature <τ_0_0 where τ_0_0 : FixedWidthInteger, τ_0_0 == τ_0_0.Magnitude, τ_0_0.Magnitude == τ_0_0.Magnitude.Magnitude.Magnitude> in requirement #2

```

Repro repository here: https://github.com/tachyonics/swift-compiler-crash-repro

[gottesmm]

@swift-ci create

[slavapestov]

The compiler is not supposed to accept this code because the current design of the type checker does not support it. When assertions are disabled, it will appear to work, but function symbol mangling might be incorrect.

A workaround is to change the BigInt library to avoid the problematic same-type constraint. I'm assuming your copy of BigInt.swift is identical to the one in test/Prototypes in the Swift repository. If so, it has a definition like this:

public struct _BigInt<Word: FixedWidthInteger & UnsignedInteger> :
  BinaryInteger, SignedInteger, CustomStringConvertible,
  CustomDebugStringConvertible
  where Word.Magnitude == Word

You'll need to remove the "where Word.Magnitude == Word" constraint and add a few forced casts now that the compiler no longer knows they're the same type. Here is the diff I used:

--- a/test/Prototypes/BigInt.swift
+++ b/test/Prototypes/BigInt.swift
@@ -16,11 +16,6 @@
 // REQUIRES: executable_test
 // REQUIRES: CPU=x86_64
 
 import StdlibUnittest
 #if canImport(Darwin)
   import Darwin
@@ -83,7 +78,6 @@ extension FixedWidthInteger {
 public struct _BigInt<Word: FixedWidthInteger & UnsignedInteger> :
   BinaryInteger, SignedInteger, CustomStringConvertible,
   CustomDebugStringConvertible
-  where Word.Magnitude == Word
 {
 
   /// The binary representation of the value's magnitude, with the least
@@ -331,7 +325,7 @@ public struct _BigInt<Word: FixedWidthInteger & UnsignedInteger> :
     var carry: Word = 0
     for i in 0..<_data.count {
       let product = _data[i].multipliedFullWidth(by: rhs)
-      (carry, _data[i]) = product.low.addingFullWidth(carry)
+      (carry, _data[i]) = product.low.addingFullWidth(carry as! Word.Magnitude) as! (Word, Word)
       carry = carry &+ product.high
     }
 
@@ -361,7 +355,7 @@ public struct _BigInt<Word: FixedWidthInteger & UnsignedInteger> :
 
     var carry: Word = 0
     for i in (0..<_data.count).reversed() {
-      let lhs = (high: carry, low: _data[i])
+      let lhs = (high: carry, low: _data[i] as! Word.Magnitude)
       (_data[i], carry) = rhs.dividingFullWidth(lhs)
     }
 
@@ -505,7 +499,7 @@ public struct _BigInt<Word: FixedWidthInteger & UnsignedInteger> :
         // `newData[ai + bi]` and any addition overflow in `carry`.
         let product = a[ai].multipliedFullWidth(by: b[bi])
         (carry, newData[ai + bi]) = Word.addingFullWidth(
-          newData[ai + bi], product.low, carry)
+          newData[ai + bi], product.low as! Word, carry)
 
         // Now we combine the high word of the multiplication with any addition
         // overflow. It is safe to add `product.high` and `carry` here without

The test file compiles and runs for me now, but I haven't done any further testing. I hope this helps!

[slavapestov]

#42113