<p>I've mentioned before that Swift evolution is somewhat limited by the fact that it is now ABI-stable. One recent example that caught my attention was <a href="https://forums.swift.org/t/permutablecollection-protocol/65314" rel="nofollow noreferrer">PermutableCollection</a>.</p>
<p>Currently, the Collection protocols create an inheritance tree that looks like this:</p>
<pre><code>                     Sequence
                    /        \
              Collection  LazySequenceProtocol
             /    |     \
MutableCollection | RangeReplaceableCollection
        BidirectionalCollection 
                  |
        RandomAccessCollection
</code></pre>
<p>The proposal is simple: add a new protocol <code>PermutableCollection</code> in this tree between <code>Collection</code> and <code>MutableCollection</code>. <code>PermutableCollection</code> doesn't require anything that <code>MutableCollection</code> doesn't already have, so it wouldn't break existing code.</p>
<p>The merits/drawbacks of the proposal aside, it cannot be implemented. Adding a new type to the middle of the inheritance tree is an ABI-breaking change in Swift, even if it doesn't break source in any way. There is some discussion on the forum thread about how it could be retrofitted into Swift's ABI, but my question is slightly different: <strong>How could the ABI have been designed that this is not an ABI break?</strong></p>

<swift><inheritance><abi-stability>
How could a language support adding new types to the middle of the inheritance tree in an ABI-stable way?
CC BY-SA 4.0
2023-06-30T16:15:10.830Z
Not really an answer, but some languages avoid this and some other problems by renouncing inheritance at all. Rust is the first example that comes to mind. There a corresponding change would've resulted in an introduction of a new trait and a modification of two inter-trait dependencies, which would've still been ABI-compatible (I believe)
abel1502
CC BY-SA 4.0
2023-06-30T16:35:36.380Z
@abel1502 Swift "protocols" are far more similar to Rust traits than to classes or Java interfaces; the name "protocol" is just historical baggage. The way Swift currently implements it is that for some type `T`, the vtable for `T:MutableCollection` contains a pointer to the vtable for `T:Collection`, so by inserting something new into the tree that pointer now points to the vtable for `T:PermutableCollection` and code that isn't prepared for that breaks.
Bbrk24
CC BY-SA 4.0
2024-03-23T02:36:07.293Z
@Bbrk24 The end-result of that is you're trading a predictable compile-time error for a nasty runtime surprise. I'm not a _Swiftie_ myself, so I'm genuinely curious if Swift users think that's a good thing or a bad thing; and/or if the new possibilities for flexibility that it introduces are worth the risks. I note this almost feels like Swift's answer to ObjectiveC's _Swizzling_.
Dai
<p>I have recently had an idea. For the purpose of this explanation, let's consider a simpler set of protocols, and a type that adopts both:</p>
<pre class="lang-swift prettyprint-override"><code>protocol P {
  func a()
}

protocol Q: P {
  func b()
  func c()
}

struct S: Q {
  func a() {}
  func b() {}
  func c() {}
}
</code></pre>
<p>Then, the vtables could look something like this:</p>
<pre><code>'vtable for S:P':
  - &amp;S.a
'vtable for S:Q':
  - &amp;'vtable for S:P'
  - &amp;S.b
  - &amp;S.c
</code></pre>
<p>In our hypothetical ABI, the functions are alphabetized in the vtable, and the first element is a pointer to the supertype vtable, if applicable. Because the more specific vtable includes the more generic one, you can have code like this:</p>
<pre class="lang-swift prettyprint-override"><code>func foo(_ x: any P) {}

func bar(_ x: any Q) {
  foo(x) // needs to grab the vtable for (typeof x):P from the vtable for (typeof x):Q
}
</code></pre>
<p>Now, say we restructure the protocols and add a new type, without recompiling the existing struct:</p>
<pre class="lang-swift prettyprint-override"><code>protocol P {
  func a()
}

protocol R: P {
  func c()
}

protocol Q: @introducedBefore R { // &lt;- Attribute that does not exist in actual Swift
  func b()
}

struct S2: Q {
  func a() {}
  func c() {}
  func b() {}
}
</code></pre>
<p>This <code>@introducedBefore</code> attribute is key. It tells the compiler to generate vtables for <code>Q</code> as if <code>R</code> were not there:</p>
<pre><code>'vtable for S2:P':
  - &amp;S2.a
'vtable for S2:R':
  - &amp;'vtable for S:P'
  - &amp;S2.c
'vtable for S2:Q':
  - &amp;'vtable for S:P'
  - &amp;S2.b
  - &amp;S2.c
</code></pre>
<p>Code that dynamically upcasts <code>any Q</code> to <code>any R</code> must construct the vtable for <code>(typeof x):R</code> at runtime, since there is no guarantee that one exists:</p>
<pre class="lang-swift prettyprint-override"><code>func foo(_ x: any R) {}

func bar(_ x: any Q) {
  // In source, this looks like:
  foo(x)
  // At runtime, this does:
  let x_as_R: any R = (value: x.value, vtable: (vtable_for_P: x.vtable.vtable_for_P, c: x.vtable.c))
  foo(x_as_R)
}
</code></pre>
<p>Depending on the size of the vtable, this may not actually be noticeably slower than if <code>Q</code> was not introducedBefore <code>R</code> -- it has to pull out the supertype vtable either way.</p>
<hr />
<p>I didn't intend to invent a solution backwards-compatible with Swift's current ABI, but this may actually work for that, too.</p>

CC BY-SA 4.0
2023-07-06T18:37:01.510Z
2023-07-06T18:37:01.510Z
Bbrk24
# How could a language support adding new types to the middle of the inheritance tree in an ABI-stable way?
Posted by: username_0 on 2023-06-30
I've mentioned before that Swift evolution is somewhat limited by the fact that it is now ABI-stable. One recent example that caught my attention was PermutableCollection.
Currently, the Collection protocols create an inheritance tree that looks like this:
                     Sequence
                    /        \
              Collection  LazySequenceProtocol
             /    |     \
MutableCollection | RangeReplaceableCollection
        BidirectionalCollection 
                  |
        RandomAccessCollection

The proposal is simple: add a new protocol PermutableCollection in this tree between Collection and MutableCollection. PermutableCollection doesn't require anything that MutableCollection doesn't already have, so it wouldn't break existing code.
The merits/drawbacks of the proposal aside, it cannot be implemented. Adding a new type to the middle of the inheritance tree is an ABI-breaking change in Swift, even if it doesn't break source in any way. There is some discussion on the forum thread about how it could be retrofitted into Swift's ABI, but my question is slightly different: How could the ABI have been designed that this is not an ABI break?
**Tags:** swift inheritance abi-stability
> **Comments:**
> **username_1**: Not really an answer, but some languages avoid this and some other problems by renouncing inheritance at all. Rust is the first example that comes to mind. There a corresponding change would've resulted in an introduction of a new trait and a modification of two inter-trait dependencies, which would've still been ABI-compatible (I believe)  
> **username_0**: @abel1502 Swift "protocols" are far more similar to Rust traits than to classes or Java interfaces; the name "protocol" is just historical baggage. The way Swift currently implements it is that for some type `T`, the vtable for `T:MutableCollection` contains a pointer to the vtable for `T:Collection`, so by inserting something new into the tree that pointer now points to the vtable for `T:PermutableCollection` and code that isn't prepared for that breaks.  
> **username_2**: @Bbrk24 The end-result of that is you're trading a predictable compile-time error for a nasty runtime surprise. I'm not a _Swiftie_ myself, so I'm genuinely curious if Swift users think that's a good thing or a bad thing; and/or if the new possibilities for flexibility that it introduces are worth the risks. I note this almost feels like Swift's answer to ObjectiveC's _Swizzling_.  
---
## 1 answers
### Answer by username_0 on 2023-07-06. Score: 1
I have recently had an idea. For the purpose of this explanation, let's consider a simpler set of protocols, and a type that adopts both:
protocol P {
  func a()
}

protocol Q: P {
  func b()
  func c()
}

struct S: Q {
  func a() {}
  func b() {}
  func c() {}
}

Then, the vtables could look something like this:
'vtable for S:P':
  - &S.a
'vtable for S:Q':
  - &'vtable for S:P'
  - &S.b
  - &S.c

In our hypothetical ABI, the functions are alphabetized in the vtable, and the first element is a pointer to the supertype vtable, if applicable. Because the more specific vtable includes the more generic one, you can have code like this:
func foo(_ x: any P) {}

func bar(_ x: any Q) {
  foo(x) // needs to grab the vtable for (typeof x):P from the vtable for (typeof x):Q
}

Now, say we restructure the protocols and add a new type, without recompiling the existing struct:
protocol P {
  func a()
}

protocol R: P {
  func c()
}

protocol Q: @introducedBefore R { // <- Attribute that does not exist in actual Swift
  func b()
}

struct S2: Q {
  func a() {}
  func c() {}
  func b() {}
}

This @introducedBefore attribute is key. It tells the compiler to generate vtables for Q as if R were not there:
'vtable for S2:P':
  - &S2.a
'vtable for S2:R':
  - &'vtable for S:P'
  - &S2.c
'vtable for S2:Q':
  - &'vtable for S:P'
  - &S2.b
  - &S2.c

Code that dynamically upcasts any Q to any R must construct the vtable for (typeof x):R at runtime, since there is no guarantee that one exists:
func foo(_ x: any R) {}

func bar(_ x: any Q) {
  // In source, this looks like:
  foo(x)
  // At runtime, this does:
  let x_as_R: any R = (value: x.value, vtable: (vtable_for_P: x.vtable.vtable_for_P, c: x.vtable.c))
  foo(x_as_R)
}

Depending on the size of the vtable, this may not actually be noticeably slower than if Q was not introducedBefore R -- it has to pull out the supertype vtable either way.

I didn't intend to invent a solution backwards-compatible with Swift's current ABI, but this may actually work for that, too.
---
