# FixedWidth cannot build rewrite system for protocol

**URL:** <https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285>\
**Category:** Compiler\
**Tags:** stdlib, protocol\
**Created:** [April 9, 2023, 7:31pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285 "2023-04-09T19:31:24Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![carlos42421](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/carlos42421/32/4585_2.png) [@carlos42421](https://forums.swift.org/u/carlos42421)\
**Post date:** [April 9, 2023, 7:31pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/1 "2023-04-09T19:31:24Z")

</div>

Hiya, I've upgraded the compiler to release/5.8 and rebased my changes on top. I'm getting errors compiling my standard library...

```swift
FixedWidth.swift:5:17: error: cannot build rewrite system for protocol; rule length limit exceeded
public protocol FixedWidthInteger : BinaryInteger
                ^
FixedWidth.swift:5:17: note: failed rewrite rule is [FixedWidthInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Magnitude].[FixedWidthInteger] => [FixedWidthInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Stride].[SignedInteger:Magnitude]
public protocol FixedWidthInteger : BinaryInteger

```

My standard library is more like a derivation of the swift 5.3 standard library, so I was expecting some friction with suddenly jumping forward a couple of years worth of compiler tech. I'm assuming the error comes from something like the new "Requirement Machine" ([The "Requirement Machine", a new generics implementation based on term rewriting](https://forums.swift.org/t/the-requirement-machine-a-new-generics-implementation-based-on-term-rewriting/55601)) ...but it's quite opaque to me what the actual problem might be, what swift is finding undecidable.

My core protocols around numerics and integers are pretty much unchanged from vanilla 5.3 (just some things like string conversions removed and some minor tweaks).

Here's an excerpt (edited to be as concise as possible) from my standard library...

```swift
public protocol Equatable {
  static func == (lhs: Self, rhs: Self) -> Bool
}
public protocol Comparable : Equatable {
  static func < (lhs: Self, rhs: Self) -> Bool
  static func <= (lhs: Self, rhs: Self) -> Bool
  static func >= (lhs: Self, rhs: Self) -> Bool
  static func > (lhs: Self, rhs: Self) -> Bool
}
public protocol AdditiveArithmetic : Equatable {
  static var zero: Self { get }
  static func +=(lhs: inout Self, rhs: Self)
  static func -(lhs: Self, rhs: Self) -> Self
  static func -=(lhs: inout Self, rhs: Self)
  static func +(lhs: Self, rhs: Self) -> Self
}
public protocol Numeric : AdditiveArithmetic, Comparable, ExpressibleByIntegerLiteral {
  associatedtype Magnitude : Numeric
  var magnitude: Magnitude { get }
  static func *(lhs: Self, rhs: Self) -> Self
  static func *=(lhs: inout Self, rhs: Self)
}
public protocol SignedNumeric : Numeric {
  static prefix func - (_ operand: Self) -> Self
  mutating func negate()
}
public protocol Strideable : Comparable {
  associatedtype Stride : SignedNumeric
  func distance(to other: Self) -> Stride
  func advanced(by n: Stride) -> Self
  static func _step(
    after current: (index: Int?, value: Self),
    from start: Self, by distance: Self.Stride
  ) -> (index: Int?, value: Self)
}
public protocol BinaryInteger : Numeric, Hashable, Strideable
  where Magnitude : BinaryInteger, Magnitude.Magnitude == Magnitude
{
  // init<T : BinaryFloatingPoint>(_ source: T)
  init<T : BinaryInteger>(_ source: T)
  init<T : BinaryInteger>(truncatingIfNeeded source: T)
  static var isSigned: Bool { get }
  var _lowWord: UInt { get }
  var bitWidth: Int { get }
  associatedtype Words : RandomAccessCollection
    where Words.Element == UInt, Words.Index == Int
  var words: Words { get }
...etc...
}
public protocol SignedInteger : BinaryInteger, SignedNumeric {}
public protocol UnsignedInteger : BinaryInteger {}
public protocol FixedWidthInteger : BinaryInteger
// , LosslessStringConvertible
where Magnitude : FixedWidthInteger & UnsignedInteger,
      Stride : FixedWidthInteger & SignedInteger
{
  static var bitWidth: Int { get }
  static var max: Self { get }
  static var min: Self { get }
  init(_truncatingBits bits: UInt)
  var nonzeroBitCount: Int { get }
  var leadingZeroBitCount: Int { get }
...etc...
}

```

...when I look at the modern release/5.8 standard library, all these protocols look to be basically pretty much unchanged. So I'm wondering how the new compiler is getting upset by my simpler versions?

Can anyone offer insight or a path for how I can debug what the compiler is actually unhappy about? Where it can't decide and that's changed?

Thanks for any help or advice you can give!

Carl

---

<div class="post-metadata">

**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\
**Post date:** [April 9, 2023, 9:46pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/2 "2023-04-09T21:46:21Z")

</div>

> [@carlos42421](#):
>
> My core protocols around numerics and integers are pretty much unchanged from vanilla 5.3 (just some things like string conversions removed and some minor tweaks).

> [@carlos42421](#):
>
> basically pretty much unchanged.

It would seem logical to conclude that it’s the “minor tweaks” that are causing the problem, i.e., something that doesn’t fall into the “basically pretty much unchanged” bucket.

Can you detail as precisely as possible what the tweaks and changes are?

---

<div class="post-metadata">

**Author:** ![Slava\_Pestov](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/slava_pestov/32/30204_2.png) [@Slava\_Pestov](https://forums.swift.org/u/Slava_Pestov)\
**Post date:** [April 9, 2023, 11:10pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/3 "2023-04-09T23:10:33Z")

</div>

What happens if you make FixedWidthInteger inherit two protocols instead of one? Eg, by uncommenting the LosslessStringConvertible line:

> [@carlos42421](#):
>
> ```swift
> public protocol FixedWidthInteger : BinaryInteger
> // , LosslessStringConvertible
> 
> ```

This might seem really arbitrary but I’ll explain what’s going on if this is indeed the problem.

---

<div class="post-metadata">

**Author:** ![randomeizer](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/randomeizer/32/25231_2.png) [@randomeizer](https://forums.swift.org/u/randomeizer)\
**Post date:** [April 10, 2023, 12:04am UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/4 "2023-04-10T00:04:21Z")

</div>

I'll let @carlos42421 elaborate, but `String` doesn't currently exist in his library, due to its complexity eating up resources in constrained hardware environments (eg. Arduino boards).

---

<div class="post-metadata">

**Author:** ![carlos42421](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/carlos42421/32/4585_2.png) [@carlos42421](https://forums.swift.org/u/carlos42421)\
**Post date:** [April 10, 2023, 7:38am UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/5 "2023-04-10T07:38:12Z")

</div>

@Slava_Pestov progress I think?

I added...

```swift
public protocol CustomStringConvertible {}
public protocol LosslessStringConvertible: CustomStringConvertible {}
public protocol FixedWidthInteger : BinaryInteger, LosslessStringConvertible
where Magnitude : FixedWidthInteger & UnsignedInteger,
      Stride : FixedWidthInteger & SignedInteger
{

```

...now the compiler 'crashes'....

```swift
Argument list does not match parameters in ApplyExpr:
Argument list: (argument_list implicit
  (argument
    (string_literal_expr implicit type='StaticString' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] encoding=utf8 value="Swift._IteratorBox" builtin_initializer=Swift.(file).StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)@StaticString.swift:169:10 initializer= **NULL** ))
  (argument
    (magic_identifier_literal_expr implicit type='StaticString' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#function encoding=utf8 builtin_initializer=Swift.(file).StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)@StaticString.swift:169:10 initializer= **NULL** ))
  (argument
    (magic_identifier_literal_expr implicit type='StaticString' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#fileID encoding=utf8 builtin_initializer=Swift.(file).StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)@StaticString.swift:169:10 initializer= **NULL** ))
  (argument
    (magic_identifier_literal_expr implicit type='UInt' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#line builtin_initializer=Swift.(file).UInt.init(_builtinIntegerLiteral:)@Integer-16.swift:178:10 initializer= **NULL** ))
  (argument
    (magic_identifier_literal_expr implicit type='UInt' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#column builtin_initializer=Swift.(file).UInt.init(_builtinIntegerLiteral:)@Integer-16.swift:178:10 initializer= **NULL** )))

Parameter types: ()
(call_expr implicit type='Never' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] nothrow
  (declref_expr implicit type='() -> Never' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] decl=Swift.(file)._unimplementedInitializer()@TopLevelFunctions.swift:149:6 function_ref=unapplied)
  (argument_list implicit
    (argument
      (string_literal_expr implicit type='StaticString' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] encoding=utf8 value="Swift._IteratorBox" builtin_initializer=Swift.(file).StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)@StaticString.swift:169:10 initializer= **NULL** ))
    (argument
      (magic_identifier_literal_expr implicit type='StaticString' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#function encoding=utf8 builtin_initializer=Swift.(file).StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)@StaticString.swift:169:10 initializer= **NULL** ))
    (argument
      (magic_identifier_literal_expr implicit type='StaticString' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#fileID encoding=utf8 builtin_initializer=Swift.(file).StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)@StaticString.swift:169:10 initializer= **NULL** ))
    (argument
      (magic_identifier_literal_expr implicit type='UInt' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#line builtin_initializer=Swift.(file).UInt.init(_builtinIntegerLiteral:)@Integer-16.swift:178:10 initializer= **NULL** ))
    (argument
      (magic_identifier_literal_expr implicit type='UInt' location=Existential.swift:68:22 range=[Existential.swift:68:22 - line:68:22] kind=#column builtin_initializer=Swift.(file).UInt.init(_builtinIntegerLiteral:)@Integer-16.swift:178:10 initializer= **NULL** ))))
Please submit a bug report (https://swift.org/contributing/#reporting-bugs) and include the crash backtrace.
Stack dump:
0.	Program arguments: /Users/petoc01/Documents/Code/swift/build/Ninja-ReleaseAssert/swift-macosx-x86_64/bin/swift-frontend -frontend -emit-module CoreOperators.swift CoreAliases.swift RawRepresentable.swift LiteralProtocols.swift TopLevelFunctions.swift CoreProtocols.swift CoreFloatingPoint.swift CoreBinaryFloatingPoint.swift Float.swift Float16.swift CoreFloatingPointFunctions.swift Optional.swift Bridging.swift CoreNumericProtocols.swift BinaryInteger.swift CoreIntegers.swift ErrorType.swift Bool.swift Integers.swift Ranges.swift Sequence.swift Stride.swift Slice.swift Collection.swift BidirectionalCollection.swift RandomAccessCollection.swift ClosedRange.swift MutableCollection.swift Hash.swift Pointer.swift UnsafeBufferPointer.swift UnsafeRawBufferPointer.swift UnsafeRawPointer.swift Indices.swift Existential.swift Algorithm.swift FixedWidth.swift IntegerMath.swift CTypes.swift UnsafePointer.swift ObjectIdentifier.swift CollectionAlgorithms.swift WriteBackMutableSlice.swift Random.swift RangeReplaceableCollection.swift MemoryLayout.swift Tuple.swift SequenceAlgorithms.swift LifetimeManager.swift Repeat.swift EmptyCollection.swift CollectionOfOne.swift StringLiterals.swift StaticString.swift StringInterpolation.swift Unicode.swift UnicodeScalar.swift UnicodeEncoding.swift UTF8.swift UTF16.swift ValidUTF8Buffer.swift UnicodeParser.swift UIntBuffer.swift UTFEncoding.swift UTF32.swift ArrayType.swift ArrayBufferProtocol.swift ArrayLiterals.swift ArrayShared.swift ContiguousArray.swift SliceBuffer.swift ArraySlice.swift Array.swift ArrayBody.swift ArrayCast.swift AnyHashable.swift ManagedBuffer.swift AVRArrayBuffer.swift Reverse.swift Map.swift Zip.swift LazySequence.swift LazyCollection.swift Filter.swift FlatMap.swift Flatten.swift DropWhile.swift Volatile.swift uSwift.swift Integer-16.swift IntegerMath-16.swift CTypes-16.swift Progmem.swift version.swift -supplementary-output-file-map /var/folders/p9/dy3nmf315svbkqpz9z78jxmc0000gn/T/TemporaryDirectory.2IHrFt/supplementaryOutputs-1 -disable-objc-attr-requires-foundation-module -target avr-atmel-linux-gnueabihf -warn-on-potentially-unavailable-enum-case -disable-objc-interop -I uSwiftShims -I AVR -I "/Applications/Swift For Arduino.app/Contents/XPCServices/BuildEngine.xpc/Contents/Resources/gpl-tools-avr/lib/avr-libgcc/include" -I "/Applications/Swift For Arduino.app/Contents/XPCServices/BuildEngine.xpc/Contents/Resources/gpl-tools-avr/lib/avr-libc/include" -color-diagnostics -enable-library-evolution -nostdimport -parse-stdlib -Osize -D AVR_LIBC_DEFINED_SWIFT -new-driver-path /Users/petoc01/Documents/Code/swift/build/Ninja-ReleaseAssert/swift-macosx-x86_64/bin/swift-driver -disable-reflection-metadata -resource-dir /Users/petoc01/Documents/Code/swift/build/Ninja-ReleaseAssert/swift-macosx-x86_64/lib/swift -Xcc -DAVR_LIBC_DEFINED -Xcc -DLIBC_DEFINED -module-name Swift -parse-as-library -o bin/AVR/Swift.swiftmodule
1.	Swift version 5.8-dev (LLVM e3b42af9113eeac, Swift 872089ba4992fc5)
2.	Compiling with the current language version
3.	While walking into '_IteratorBox' (at Existential.swift:68:16)
4.	While walking into body of 'init()' (at Existential.swift:70:39)
5.	While verifying ApplyExpr expression at [Existential.swift:68:22 - line:68:22] RangeText=""
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):
0 swift-frontend 0x0000000107acdfa7 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 39
1 swift-frontend 0x0000000107acce28 llvm::sys::RunSignalHandlers() + 248
2 swift-frontend 0x0000000107ace600 SignalHandler(int) + 288
3 libsystem_platform.dylib 0x00007ff80fa76dfd _sigtramp + 29
4 libsystem_platform.dylib 0x70253f253b25353b _sigtramp + 8080793832133609307
5 libsystem_c.dylib 0x00007ff80f9acd24 abort + 123
6 swift-frontend 0x0000000103f9e9fc (anonymous namespace)::Verifier::verifyChecked(swift::ApplyExpr*) + 828
7 swift-frontend 0x0000000103f943c2 (anonymous namespace)::Verifier::walkToExprPost(swift::Expr*) + 15250
8 swift-frontend 0x0000000103fa1ec9 (anonymous namespace)::Traversal::doIt(swift::Expr*) + 137
9 swift-frontend 0x0000000103fa3913 swift::ASTVisitor<(anonymous namespace)::Traversal, swift::Expr*, swift::Stmt*, bool, swift::Pattern*, bool, void>::visit(swift::Stmt*) + 147
10 swift-frontend 0x0000000103fa1fbd (anonymous namespace)::Traversal::doIt(swift::Stmt*) + 109
11 swift-frontend 0x0000000103fa6448 (anonymous namespace)::Traversal::visitAbstractFunctionDecl(swift::AbstractFunctionDecl*) + 712
12 swift-frontend 0x0000000103fa252b (anonymous namespace)::Traversal::doIt(swift::Decl*) + 235
13 swift-frontend 0x0000000103fa5e7d (anonymous namespace)::Traversal::visitNominalTypeDecl(swift::NominalTypeDecl*) + 653
14 swift-frontend 0x0000000103fa252b (anonymous namespace)::Traversal::doIt(swift::Decl*) + 235
15 swift-frontend 0x0000000103fa242b swift::Decl::walk(swift::ASTWalker&) + 27
16 swift-frontend 0x00000001041494c0 swift::SourceFile::walk(swift::ASTWalker&) + 304
17 swift-frontend 0x0000000103f8f4e0 swift::verify(swift::SourceFile&) + 80
18 swift-frontend 0x000000010425b82a swift::TypeCheckSourceFileRequest::cacheResult(std::__1::tuple<>) const + 74
19 swift-frontend 0x0000000103d7cd90 llvm::Expected<swift::TypeCheckSourceFileRequest::OutputType> swift::Evaluator::getResultCached<swift::TypeCheckSourceFileRequest, (void*)0>(swift::TypeCheckSourceFileRequest const&) + 96
20 swift-frontend 0x0000000103d7ac6f swift::TypeCheckSourceFileRequest::OutputType swift::evaluateOrDefault<swift::TypeCheckSourceFileRequest>(swift::Evaluator&, swift::TypeCheckSourceFileRequest, swift::TypeCheckSourceFileRequest::OutputType) + 31
21 swift-frontend 0x0000000102cf355c bool llvm::function_ref<bool (swift::SourceFile&)>::callback_fn<swift::CompilerInstance::performSema()::$_7>(long, swift::SourceFile&) + 12
22 swift-frontend 0x0000000102ceb27e swift::CompilerInstance::forEachFileToTypeCheck(llvm::function_ref<bool (swift::SourceFile&)>) + 174
23 swift-frontend 0x0000000102ceb1ab swift::CompilerInstance::performSema() + 75
24 swift-frontend 0x0000000102afb9df swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 3615
25 swift-frontend 0x0000000102ac0e82 swift::mainEntry(int, char const**) + 722
26 dyld 0x000000020fa5452e start + 462
27 dyld 0x000000020fa4f000 start + 18446744073709530272
make[1]: *** [bin/AVR/Swift.swiftmodule] Abort trap: 6
rm version.swift
make: *** [uSwift] Error 2

```

I'll build a debug version of the compiler then track into this stack trace to see if I can get some more colour on the issue.

p.s. @randomeizer works on our team, he's right, we don't have String, which is why I made the protocols `CustomStringConvertible`, `LosslessStringConvertible` empty here.

---

<div class="post-metadata">

**Author:** ![carlos42421](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/carlos42421/32/4585_2.png) [@carlos42421](https://forums.swift.org/u/carlos42421)\
**Post date:** [April 10, 2023, 3:16pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/6 "2023-04-10T15:16:38Z")

</div>

@Slava_Pestov actually your trick did work!

I just had a different problem in my standard library, which caused the crash, unrelated to this issue!

So adding another inherited protocol to `FixedWidthInteger` "magically" fixed the issue!

---

<div class="post-metadata">

**Author:** ![Slava\_Pestov](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/slava_pestov/32/30204_2.png) [@Slava\_Pestov](https://forums.swift.org/u/Slava_Pestov)\
**Post date:** [April 10, 2023, 4:42pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/7 "2023-04-10T16:42:51Z")

</div>

> [@carlos42421](#):
>
> So adding another inherited protocol to `FixedWidthInteger` "magically" fixed the issue!

Yep, and the reason is that there are some limitations with infinitely-recursive associated types. You can have an associated type that recursively conforms to a single protocol, generating infinitely many nested types:

```swift
protocol P {
  associatedtype A: P
}

```

The above is the SwiftUI View protocol essentially.

You can also inherit from P in a new protocol Q and impose an additional conformance requirement on A, which is then applied to this infinite set of type parameters:

```swift
protocol Q: P where A: Q {
  // (that re-stating an associated type has no effect on generic signatures)
  // associatedtype A: ... 
}

```

This works because protocol Q is "more specific" than P (technically, it precedes P in the reduction order because it inherits from P). The above pattern comes up in the standard library Collection protocol hierarchy.

You can do more complicated things if the recursion ends after a finite number of steps with a same-type requirement:

```swift
protocol P {
  associatedtype A: P
}

protocol Q {
  associatedtype A: P & Q where Self == A.A.A.A
}

```

If the set of type parameters is finite then we can always build a rewrite system in a finite number of steps (it's still undecidable if a rewrite system has finitely many irreducible terms, so technically the completion procedure might hit a cutoff before discovering all the rules, but it's unlikely that any reasonable protocol hierarchy will impose requirements on unique type parameters of length 10. The limit can be increased with a frontend flag.)

What _doesn't_ always work is a recursive associated type with arbitrary conformance requirements involving unrelated protocols -- the below is the same as the previous example, just without `Self == A.A.A.A`:

```swift
protocol P {
  associatedtype A: P
}

protocol Q {
  associatedtype A: P & Q
}

```

```swift
error: cannot build rewrite system for protocol; rule length limit exceeded
protocol Q {
         ^
note: failed rewrite rule is [Q:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[Q] => [Q:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A].[P:A]
protocol Q {
         ^

```

Here, P precedes Q in the reduction order because both inherit from the same number of protocols (this concept will be important shortly) and P \< Q in lexicographic order on identifiers. Completion then blows up with an error because a convergent presentation of this protocol needs infinitely many conformance requirements.

If you rename `protocol Q` to `protocol M` or something, then it works! Now, M \< P, and we get away with just adding finitely many additional rules.

Also, if protocol Q were to inherit from more protocols than P (if you consider the transitive closure of the inheritance graph) then it also works. And note, it doesn't have to inherit from _P_ itself, just from _more protocols_ than P! (For if A inherits from B, then _it is also true_ that A inherits from more protocols than B, but the converse isn't always true).

```swift
protocol Other {}

protocol P {
  associatedtype A: P
}

protocol Q: Other {
  associatedtype A: P & Q
}

```

And it is this latter case that is triggered by FixedWidthInteger. The inherited Magnitude and Stride associated types receive a rather complex set of requirements, and they are themselves recursive in the base protocol:

```swift
public protocol FixedWidthInteger: BinaryInteger, LosslessStringConvertible
where Magnitude: FixedWidthInteger & UnsignedInteger,
      Stride: FixedWidthInteger & SignedInteger {

```

It works in the stdlib as written because FixedWidthInteger precedes BinaryInteger, SignedInteger and UnsignedInteger in the reduction order. The reduction order is designed to ensure that `FixedWidthInteger < BinaryInteger` but the other too were only true by luck. In your case, your luck ran out and the relationship changed so that FixedWidthInteger succeeded SignedInteger, because you removed the LosslessStringConvertible protocol.

You can make a good case that independent of implementation limitation, FixedWidthInteger should probably have also had same-type requirements like `Stride.Stride == Stride` and `Magnitude.Magnitude == Magnitude` from the start, since in practice those relations should hold. Adding those requirements would avoid the possibility of this issue completely. But technically it would be an ABI break if someone had a conforming type which did not satisfy them.

Interestingly, Rust cannot even represent the "recursive conformance imposed on inherited associated type" case that comes up in Swift with, eg, BidirectionalCollection and RandomAccessCollection, which require that the Indices and SubSequence associated types conform to the same protocol. However, they have generic associated types, which are even more difficult to reason about for the type checker.

---

<div class="post-metadata">

**Author:** ![carlos42421](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/carlos42421/32/4585_2.png) [@carlos42421](https://forums.swift.org/u/carlos42421)\
**Post date:** [April 10, 2023, 5:21pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/8 "2023-04-10T17:21:35Z")

</div>

I'm not going to claim I 100% understand the full explanation, although I love it and it will be very helpful and useful for people who are a bit deeper in the weeds than me! I'd guess the answer would essentially be in some sense "bad luck", or said another way, the people writing stdlib and the compiler were generally intricately intertwined, hence those two parts are also intricately intertwined. 🙂

p.s. I've changed our version of stdlib to...

```swift
// I'm not sure why this is needed but Slava says it is, and compiling borks otherwise!
public protocol _FakeIntegerProtocol {}

public protocol FixedWidthInteger : BinaryInteger, _FakeIntegerProtocol
where Magnitude : FixedWidthInteger & UnsignedInteger,
      Stride : FixedWidthInteger & SignedInteger
{
  static var bitWidth: Int { get }
...

```

...and it works perfectly. Thank you so much (yet again) Slava! 🙂

---

<div class="post-metadata">

**Author:** ![carlos42421](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/carlos42421/32/4585_2.png) [@carlos42421](https://forums.swift.org/u/carlos42421)\
**Post date:** [April 10, 2023, 5:28pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/9 "2023-04-10T17:28:01Z")

</div>

Sidebar: sorry to not reply to you earlier. I was working on the replies to Slava. I think the easiest summary or how our version of the protocols are was the code I put in the original post (that was literally copy/pasted from our version of stdlib)... Generally the core numeric protocols are completely unchanged in my version (maybe one initialiser commented out). The only changes are the removal of anything to do with `String`. In this interesting case that caused a miscompile but by total coincidence really (see above!) The only other changes in these protocols really are moving things around into slightly different filenames and stripping comments out, both are to make it easier (for me) to read the code, nothing else! It's just funny (ha ha) that removing one seemingly irrelevant protocol caused the type system to be unable to reason... and it worked OK with exactly the same code on the old (5.3) compiler. It's all really just "good luck" or "bad luck". I'm up and running again now so I'm super grateful to you guys and it's a huge milestone forward for me, my "microswift" stdlib compiling with a 5.8 compiler, yay! 😃

---

<div class="post-metadata">

**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\
**Post date:** [April 10, 2023, 5:29pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/10 "2023-04-10T17:29:15Z")

</div>

I'm glad it got figured out!

---

<div class="post-metadata">

**Author:** ![Quedlinbug](https://avatars.discourse-cdn.com/v4/letter/q/77aa72/32.png) [@Quedlinbug](https://forums.swift.org/u/Quedlinbug)\
**Post date:** [July 30, 2024, 6:30pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/11 "2024-07-30T18:30:26Z")

</div>

> [@Slava\_Pestov](#):
>
> The limit can be increased with a frontend flag.

I am trying to figure out which [`requirement_machine_max`](https://github.com/swiftlang/swift/blob/main/include/swift/Option/FrontendOptions.td) this is…

---

<div class="post-metadata">

**Author:** ![Slava\_Pestov](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/slava_pestov/32/30204_2.png) [@Slava\_Pestov](https://forums.swift.org/u/Slava_Pestov)\
**Post date:** [July 30, 2024, 6:54pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/12 "2024-07-30T18:54:16Z")

</div>

> [@Quedlinbug](#):
>
> I am trying to figure out which [`requirement_machine_max`](https://github.com/swiftlang/swift/blob/main/include/swift/Option/FrontendOptions.td) this is…

Are you seeing one of these errors again with a different example? The diagnostic will say which limit was hit (rule count, rule length, concrete nesting), and each one has a flag.

But again, it’s unlikely that the set of rules is finite but large; it’s probably just infinite.

---

<div class="post-metadata">

**Author:** ![Quedlinbug](https://avatars.discourse-cdn.com/v4/letter/q/77aa72/32.png) [@Quedlinbug](https://forums.swift.org/u/Quedlinbug)\
**Post date:** [July 30, 2024, 7:56pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/13 "2024-07-30T19:56:18Z")

</div>

_It was too hard to track this syntax down! Is it documented?_

```swift
.unsafeFlags(["-Xfrontend", "-requirement-machine-max-rule-count=6000"])

```

> [@Slava\_Pestov](#):
>
> it’s unlikely that the set of rules is finite but large; it’s probably just infinite.

6,000 did it for me. What is the default? I thought you were saying 10, but it must actually be way above that—somewhere in the lower thousands matches what I see without the flag set.

---

<div class="post-metadata">

**Author:** ![Slava\_Pestov](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/slava_pestov/32/30204_2.png) [@Slava\_Pestov](https://forums.swift.org/u/Slava_Pestov)\
**Post date:** [July 30, 2024, 10:27pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/14 "2024-07-30T22:27:53Z")

</div>

> [@Quedlinbug](#):
>
> It was too hard to track this syntax down! Is it documented?

Yes, in [swift/docs/Generics at main · swiftlang/swift · GitHub](https://github.com/swiftlang/swift/tree/main/docs/Generics). You need to install a TeX distribution and run `make` to generate a PDF.

> [@Quedlinbug](#):
>
> 6,000 did it for me. What is the default? I thought you were saying 10, but it must actually be way above that—somewhere in the lower thousands matches what I see without the flag set.

From Chapter 19 in the above, except now I see a typo (the second flag name should read rule-length not rule-count 🙂 I’ll also change it to mention that the flag name is followed by = and the value.)

 ![IMG_2133](https://global.discourse-cdn.com/swift/original/3X/f/b/fb206aaa4e8514d55778a08df021dc3b498a123b.jpeg)

There is also an index of command line flags at the very end of the book.

---

<div class="post-metadata">

**Author:** ![oscbyspro](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/oscbyspro/32/23689_2.png) [@oscbyspro](https://forums.swift.org/u/oscbyspro)\
**Post date:** [July 31, 2024, 4:29pm UTC](https://forums.swift.org/t/fixedwidth-cannot-build-rewrite-system-for-protocol/64285/15 "2024-07-31T16:29:51Z")

</div>

Wow. ✨ The fake protocol trick is magic ✨

I have a somewhat complex protocol hierarchy in one of my projects:

```swift
           +-----------+-----------+
           | Systems | Arbitrary |
+----------+-----------+-----------+
| Signed | B,E,F,S,X | A,B,F,X |
+----------+-----------+-----------+
| Unsigned | B,E,F,S,Y | A,B,E,Y |
+----------+-----------+-----------+
 A) ArbitraryInteger: B
 B) BinaryInteger: -
 E) EdgyInteger: B
 F) FiniteInteger: B
 S) SystemsInteger: E, F // uh-oh!
 X) SignedInteger: F // needed to inherit 1 more protocol(s)
 Y) UnsignedInteger: E // needed to inherit 2 more protocol(s)

```

I couldn't figure out how to resolve this silly [issue](https://github.com/oscbyspro/Ultimathnum/issues/52) until now. Thanks!