Repository: pointfreeco/swift-case-paths
Pull request #37 (2021-07-08 18:17:30)

eliminate the use of Mirror
This branch is not ready for merging. I'm creating this pull request only to make it available for discussion.

I found example uses of `swift_getTypeByMangledNameInContext` in [the Reflect package](https://github.com/wickwirew/Runtime) and have made some progress toward using it to replace the use of `Mirror`.

In its current state, this branch has several failing tests, all related to associated value labels. I've outlined what's wrong and what needs to be done in the commit message and code comments.

mayoff: The new version ([7cab867](https://github.com/pointfreeco/swift-case-paths/pull/37/commits/7cab86738ddb2be55561a91241a54085a534981b)) fixes the existential bug and passes all the tests (including some new ones).

Code coverage of `EnumReflection.swift` indicates the tests cover everything except an “impossible” case where some metadata is missing, and a mangled type name encoding that I don't know how to trigger.

It also runs faster.

Main branch ([90e4e67e](https://github.com/pointfreeco/swift-case-paths/commit/90e4e67ee18f72f2b1251211214ffc1fba60e540)):

```
name               time       std        iterations
---------------------------------------------------
Success.Manual      34.000 ns ± 146.77 %    1000000
Success.Reflection 151.000 ns ± 121.01 %    1000000
Failure.Manual      35.000 ns ± 231.80 %    1000000
Failure.Reflection  65.000 ns ± 191.00 %    1000000
```

New version:

```
name               time       std        iterations
---------------------------------------------------
Success.Manual      33.000 ns ± 226.73 %    1000000
Success.Reflection 128.000 ns ±  85.30 %    1000000
Failure.Manual      37.000 ns ± 149.48 %    1000000
Failure.Reflection  73.000 ns ± 140.36 %    1000000
```



mayoff: Surprisingly, unwrapping just the cached tag first to reject non-matching values (instead of unwrapping the whole cached extractor) consistently saves a few seconds in the Failure.Reflection benchmark.

```
name               time       std        iterations
---------------------------------------------------
Success.Manual      34.000 ns ± 261.66 %    1000000
Success.Reflection 135.000 ns ± 116.75 %    1000000
Failure.Manual      36.000 ns ± 221.68 %    1000000
Failure.Reflection  66.000 ns ± 174.90 %    1000000
```

mayoff: I think I'm done dinking this.

I've tried a few variations to knock nanoseconds off the Failure.Reflection benchmark without success, like storing -1 for cachedTag instead of using an optional, but was unable to make it consistently faster. I suspect it's consistently slower than the main branch by ~3 nanos because the closure captures two words (the cached tag and the strategy) instead of just one (the cached tag).

I thought the whole private helpers section of the file was kind of jumbled so I reorganized it. The code is all the same, but hopefully it's in a more logical order now so it should be easier to read from top to bottom.

iampatbrown: Really awesome work @mayoff! Thanks heaps for the informative comments and commits :) it's looking pretty close to optimal.

Patch:
diff --git a/.swiftpm/xcode/xcshareddata/xcschemes/CasePaths.xcscheme b/.swiftpm/xcode/xcshareddata/xcschemes/CasePaths.xcscheme
index 70d92f8..af6d1b1 100644
--- a/.swiftpm/xcode/xcshareddata/xcschemes/CasePaths.xcscheme
+++ b/.swiftpm/xcode/xcshareddata/xcschemes/CasePaths.xcscheme
@@ -27,6 +27,7 @@
       selectedDebuggerIdentifier = "Xcode.DebuggerFoundation.Debugger.LLDB"
       selectedLauncherIdentifier = "Xcode.DebuggerFoundation.Launcher.LLDB"
       shouldUseLaunchSchemeArgsEnv = "YES"
+      disableMainThreadChecker = "YES"
       codeCoverageEnabled = "YES">
       <Testables>
          <TestableReference
diff --git a/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-Package.xcscheme b/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-Package.xcscheme
index bbfec9f..f79f239 100644
--- a/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-Package.xcscheme
+++ b/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-Package.xcscheme
@@ -48,20 +48,6 @@
                ReferencedContainer = "container:">
             </BuildableReference>
          </BuildActionEntry>
-         <BuildActionEntry
-            buildForTesting = "YES"
-            buildForRunning = "YES"
-            buildForProfiling = "YES"
-            buildForArchiving = "YES"
-            buildForAnalyzing = "YES">
-            <BuildableReference
-               BuildableIdentifier = "primary"
-               BlueprintIdentifier = "CCasePaths"
-               BuildableName = "CCasePaths"
-               BlueprintName = "CCasePaths"
-               ReferencedContainer = "container:">
-            </BuildableReference>
-         </BuildActionEntry>
       </BuildActionEntries>
    </BuildAction>
    <TestAction
diff --git a/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-benchmark.xcscheme b/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-benchmark.xcscheme
index d9e5e00..2ff1dd6 100644
--- a/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-benchmark.xcscheme
+++ b/.swiftpm/xcode/xcshareddata/xcschemes/swift-case-paths-benchmark.xcscheme
@@ -40,8 +40,22 @@
       buildConfiguration = "Debug"
       selectedDebuggerIdentifier = "Xcode.DebuggerFoundation.Debugger.LLDB"
       selectedLauncherIdentifier = "Xcode.DebuggerFoundation.Launcher.LLDB"
-      shouldUseLaunchSchemeArgsEnv = "YES">
+      shouldUseLaunchSchemeArgsEnv = "YES"
+      disableMainThreadChecker = "YES"
+      codeCoverageEnabled = "YES">
       <Testables>
+         <TestableReference
+            skipped = "NO"
+            parallelizable = "YES"
+            testExecutionOrdering = "random">
+            <BuildableReference
+               BuildableIdentifier = "primary"
+               BlueprintIdentifier = "CasePathsTests"
+               BuildableName = "CasePathsTests"
+               BlueprintName = "CasePathsTests"
+               ReferencedContainer = "container:">
+            </BuildableReference>
+         </TestableReference>
       </Testables>
    </TestAction>
    <LaunchAction
diff --git a/Package.swift b/Package.swift
index 0d8ceb5..16bf992 100644
--- a/Package.swift
+++ b/Package.swift
@@ -15,16 +15,12 @@ let package = Package(
   ],
   targets: [
     .target(
-      name: "CasePaths",
-      dependencies: ["CCasePaths"]
+      name: "CasePaths"
     ),
     .testTarget(
       name: "CasePathsTests",
       dependencies: ["CasePaths"]
     ),
-    .target(
-      name: "CCasePaths"
-    ),
     .target(
       name: "swift-case-paths-benchmark",
       dependencies: [
diff --git a/Package@swift-5.1.swift b/Package@swift-5.1.swift
index d5007d2..996ce04 100644
--- a/Package@swift-5.1.swift
+++ b/Package@swift-5.1.swift
@@ -12,15 +12,11 @@ let package = Package(
   ],
   targets: [
     .target(
-      name: "CasePaths",
-      dependencies: ["CCasePaths"]
+      name: "CasePaths"
     ),
     .testTarget(
       name: "CasePathsTests",
       dependencies: ["CasePaths"]
     ),
-    .target(
-      name: "CCasePaths"
-    ),
   ]
 )
diff --git a/Sources/CCasePaths/Builtin_NativeObject_metadata.c b/Sources/CCasePaths/Builtin_NativeObject_metadata.c
deleted file mode 100644
index 0c761b8..0000000
--- a/Sources/CCasePaths/Builtin_NativeObject_metadata.c
+++ /dev/null
@@ -1,8 +0,0 @@
-#include "Builtin_NativeObject_metadata.h"
-
-// This is the mangled name of Builtin.NativeObject's metadata.
-extern void $sBoN;
-
-void const *getBuiltinNativeObjectFullMetadata() {
-    return &$sBoN;
-}
diff --git a/Sources/CCasePaths/include/Builtin_NativeObject_metadata.h b/Sources/CCasePaths/include/Builtin_NativeObject_metadata.h
deleted file mode 100644
index 739b003..0000000
--- a/Sources/CCasePaths/include/Builtin_NativeObject_metadata.h
+++ /dev/null
@@ -1,9 +0,0 @@
-#ifndef Builtin_NativeObject_metadata_H
-#define Builtin_NativeObject_metadata_H
-
-/// Return the address of the “full” metadata for Builtin.NativeObject. A pointer to metadata usually points to the `kind` field of the metadata, which is not the first field of the metadata. The value witness table pointer precedes the `kind` field.
-///
-/// Ideally this would be declared `__nonnull`, but the Linux compiler doesn't like that.
-void const *getBuiltinNativeObjectFullMetadata();
-
-#endif /* Builtin_NativeObject_metadata_H */
diff --git a/Sources/CasePaths/EnumReflection.swift b/Sources/CasePaths/EnumReflection.swift
index 7e3e43d..f3d0863 100644
--- a/Sources/CasePaths/EnumReflection.swift
+++ b/Sources/CasePaths/EnumReflection.swift
@@ -1,4 +1,3 @@
-import CCasePaths
 
 extension CasePath {
   /// Returns a case path that extracts values associated with a given enum case initializer.
@@ -69,112 +68,286 @@ public func extract<Root, Value>(case embed: @escaping (Value) -> Root, from roo
 /// - Parameter embed: An enum case initializer.
 /// - Returns: A function that can attempt to extract associated values from an enum.
 public func extract<Root, Value>(_ embed: @escaping (Value) -> Root) -> (Root) -> (Value?) {
-  var cachedTag: UInt32?
+  guard let metadata = EnumMetadata(Root.self) else {
+    #if DEBUG
+    print("\(#function) can never extract values from \(Root.self) because \(Root.self) isn't an enum!")
+    #endif
+    return { _ in nil }
+  }
+
+  guard metadata.typeDescriptor.fieldDescriptor != nil else {
+    #if DEBUG
+    print("\(#function) can never extract values from \(Root.self) because the metadata for \(Root.self) is incomplete!")
+    #endif
+    return { _ in nil }
+  }
+
+  var cachedTag: UInt32? = nil
+  var cachedStrategy: Strategy<Root, Value> = .unimplemented
   return { root in
-    guard let metadata = EnumMetadata(Root.self) else { return nil }
+    let metadata = EnumMetadata(assumingEnum: Root.self)
     let rootTag = metadata.tag(of: root)
 
     if let cachedTag = cachedTag {
-      guard cachedTag == rootTag else { return nil }
-      return .some(
-        metadata.typeDescriptor.fieldDescriptor.field(atIndex: rootTag).isIndirectCase
-          ? metadata.indirectAssociatedValue(of: root, as: Value.self)
-          : metadata.directAssociatedValue(of: root, as: Value.self))
+      guard rootTag == cachedTag else { return nil }
+      return cachedStrategy.extract(from: root, tag: rootTag)
     }
 
     guard
-      let value = (Mirror(reflecting: root).children.first?.value)
-        .flatMap({ $0 as? Value ?? Mirror(reflecting: $0).children.first?.value as? Value })
-        ?? workaroundForSR12044(Value.self)
+      let rootStrategy = Strategy<Root, Value>(tag: rootTag),
+      let value = rootStrategy.extract(from: root, tag: rootTag)
     else {
       return nil
     }
-    let embedTag = metadata.tag(of: embed(value))
+
+    let embeddedValue = embed(value)
+    let embedTag = metadata.tag(of: embeddedValue)
     cachedTag = embedTag
-    if rootTag == embedTag { return value }
-    return nil
+
+    guard cachedTag == rootTag else {
+      // I have the correct tag now, so I can now pick the correct strategy, even if I won't use it this time.
+      if let embedStrategy = Strategy<Root, Value>(tag: embedTag) {
+        cachedStrategy = embedStrategy
+      } else {
+        #if DEBUG
+        print("\(#function) can never extract values from a \(Root.self) case like \(embeddedValue) because I don't know how to convert its associated value to \(Value.self)!")
+        #endif
+        cachedStrategy = .unimplemented
+      }
+
+      return nil
+    }
+
+    cachedStrategy = rootStrategy
+    return value
   }
 }
 
 // MARK: - Private Helpers
 
-// This is the size of any Unsafe*Pointer and also the size of Int and UInt.
-private let pointerSize = MemoryLayout<UnsafeRawPointer>.size
+/// A `Strategy` is a way of extracting an associated value from an enum case.
+enum Strategy<Enum, Value> {
+  case unimplemented
 
-private typealias OpaqueExistentialContainer = (
-  UnsafeMutableRawPointer?, UnsafeMutableRawPointer?, UnsafeMutableRawPointer?,
-  metadata: UnsafeMutableRawPointer?
-)
+  /// The case's associated type is a zero-size inhabited type, so it only has a single possible inhabitant, which I can synthesize.
+  case void
 
-private typealias BoxPair = (heapObject: UnsafeMutableRawPointer, buffer: UnsafeMutableRawPointer)
+  /// The case is layout-compatible with `Value`, after tag-stripping (aka projection).
+  case direct
 
-extension UnsafeRawPointer {
-  fileprivate func loadInferredType<Type>() -> Type {
-    return load(as: Type.self)
-  }
+  /// The case stores its associated value indirectly. The case payload is a pointer to a heap object. The heap object's payload is layout-compatible with `Value`.
+  case indirect
 
-  fileprivate func loadRelativePointer() -> UnsafeRawPointer {
-    return self + Int(load(as: Int32.self))
-  }
+  /// The case stores a protocol existential, either directly or indirectly. This strategy is used when the enum case's associated value type is a protocol existential and the `CasePath`'s `Value` is a type that conforms to the protocol (but is not itself the protocol existential).
+  case existential(get: (Enum) -> Any?)
 }
 
-private struct ValueWitnessTable {
-  let ptr: UnsafeRawPointer
+extension Strategy {
+  /// Choose the appropriate `Strategy` to extract a `Value` from an `Enum` if that `Enum`'s case tag is `tag`. If `assumedAssociatedValueType` is nil, I'll look up the associated value type in the `Enum` metadata.
+  init?(tag: UInt32, assumedAssociatedValueType: Any.Type? = nil) {
+    let metadata = EnumMetadata(assumingEnum: Enum.self)
+    let avType = assumedAssociatedValueType ?? metadata.associatedValueType(forTag: tag)
+
+    var shouldWorkAroundSR12044: Bool {
+      #if compiler(<5.2)
+      return true
+      #else
+      return false
+      #endif
+    }
 
-  var flags: Flags {
-    return Flags(rawValue: ptr.advanced(by: 10 * pointerSize).load(as: UInt32.self))
-  }
+    var isUninhabitedEnum: Bool {
+      // If it lacks enum metadata, it's definitely not an uninhabited enum.
+      return metadata.typeDescriptor.emptyCaseCount == 0
+        && metadata.typeDescriptor.payloadCaseCount == 0
+    }
 
-  var initializeWithCopy:
-    @convention(c) (
-      _ dest: UnsafeMutableRawPointer, _ source: UnsafeMutableRawPointer,
-      _ metadata: UnsafeRawPointer
-    ) -> UnsafeMutableRawPointer
-  {
-    return ptr.advanced(by: 2 * pointerSize).loadInferredType()
-  }
+    if avType == Value.self {
+      // The `CasePath`'s `Value` type is exactly the case's associated value type.
+      self = .init(nonExistentialTag: tag)
+    }
 
-  var initializeWithTake:
-    @convention(c) (
-      _ dest: UnsafeMutableRawPointer, _ source: UnsafeMutableRawPointer,
-      _ metadata: UnsafeRawPointer
-    ) -> UnsafeMutableRawPointer
-  {
-    return ptr.advanced(by: 4 * pointerSize).loadInferredType()
-  }
+    // If `Value` is an inhabited type with size zero, it has a single inhabitant which I can synthesize by bit-casting `()`.
+    //
+    // I handle this specially because it works around a Swift 5.1 bug:
+    // https://bugs.swift.org/browse/SR-12044
+    //
+    // When the payload is a size-zero type, Swift 5.1 omits the typeName in the metadata describing the `tag` case, and `associatedValueType(forTag:)` returns `Void.self` in that case. This bug was corrected in Swift 5.2.
+    //
+    // An uninhabited type like Never also has a size of zero. I have to be careful not to create a value of an uninhabited type.
+    //
+    // If you do something like `enum E { case c(Never, Never) }`, I don't detect that it's an uninhabited tuple and I'll end up creating a bogus value of type `(Never, Never)` and it'll get passed to the `E.c` initializer. Remarkably, the initializer doesn't care! It creates the `E` value anyway. Since there is no safe way to create an `E.c` value, the `E.c` tag can't match the tag of the actual `E` value being checked by the `CasePath`. So the `CasePath` won't end up extracting a bogus value.
+    else if
+      shouldWorkAroundSR12044,
+      MemoryLayout<Value>.size == 0,
+      !isUninhabitedEnum {
+      self = .void
+    }
 
-  var getEnumTag: @convention(c) (_ value: UnsafeRawPointer, _ metadata: UnsafeRawPointer) -> UInt32
-  {
-    return ptr.advanced(by: 10 * pointerSize + 2 * 4).loadInferredType()
+    // Consider this: `enum E { case c(l: Int) }`
+    //
+    // At the metadata level, c's associated value has type `(l: Int)`, which is a single-element tuple.
+    //
+    // But Swift doesn't support single-element tuples in Swift source code, so `CasePath<E, (l: Int)>` isn't allowed.
+    //
+    // The case path for `c` therefore has type `CasePath<E, Int>`.
+    //
+    // The types `(l: Int)` and `Int` use the same memory layout.
+    //
+    // So if `avType` is a single-element tuple and `Value` is the type of that tuple's single element, I can extract a `Value` from `root`.
+    else if
+      let avMetadata = TupleMetadata(avType),
+      avMetadata.elementCount == 1
+    {
+      self.init(tag: tag, assumedAssociatedValueType: avMetadata.element(at: 0).type)
+    }
+
+    // Consider this: `enum F { case d(a: Int, b: String) }`
+    //
+    // Certainly we should allow `CasePath<F, (a: Int, b: String)>` to match this.
+    //
+    // We would also like `CasePath<F, (Int, String)> to match this.
+    //
+    // So if `avType` is a tuple, and `Value` is a tuple with no labels, and the two types have identical elements types, I can extract a `Value` from `root`.
+    //
+    // If `Value` has labels, that doesn't change its memory layout. But I don't want to silently transform a tuple that was created as `(x: 1, y: 2)` into a differently-labeled tuple `(y: 1, x: 2)`.
+    else if
+      let avMetadata = TupleMetadata(avType),
+      let valueMetadata = TupleMetadata(Value.self),
+      valueMetadata.labels == nil
+    {
+      // Consider this:
+      //
+      // ```
+      // protocol P { }
+      // extension Int: P { }
+      // enum Enum {
+      //     case c(P, Int)
+      // }
+      // let (i: Int, j: Int)? = (/E.c).extract(E.c(34, 12))
+      // ```
+      //
+      // See the handling of existentials later in this method for a simpler scenario that I do handle. But here, avType and Value are tuples with the same element count but different memory layout, because avType has a P existential where Value has an Int.
+      //
+      // This is an extremely rare scenario and I think it's too much work to try to handle it.
+      guard avMetadata.hasSameLayout(as: valueMetadata) else {
+        #if DEBUG
+        print("CasePath<\(Enum.self), \(Value.self)> has not been programmed to convert an \(avType) to a \(Value.self).")
+        #endif
+        self = .unimplemented
+        return
+      }
+
+      self.init(tag: tag, assumedAssociatedValueType: Value.self)
+    }
+
+    // Consider this:
+    //
+    // ```
+    // protocol P { }
+    // extension Int: P { }
+    // enum E { case c(P) }
+    //
+    // let i: Int? = (/E.c).extract(E.c(100))
+    // ```
+    //
+    // Even though the associated value type is `P`, and `E.c(_:)`'s type is `(P) -> E`, this constructs a `CasePath<E, Int>`, not a `CasePath<E, P>`. Here's why:
+    //
+    // - The context requires the `CasePath`'s `Value` type to be `Int`.
+    //
+    // - Therefore the `/` prefix operator requires its argument to have type `(Int) -> E`.
+    //
+    // - `(P) -> E` is a subtype of `(Int) -> E`, because `P` is in contravariant position and `Int` is a subtype of `P`.
+    //
+    // - Therefore Swift converts `E.c(_:)` to the supertype `(Int) -> E` automatically to make the expression type-check.
+    //
+    // This circumstance is unfortunate, but I don't know how to diagnose it at compile-time. So I want to handle it in a reasonable way.
+    //
+    // If `avType` is a protocol existential (a “box”), then I can extract the box from `root` and look at the boxed type. If the boxed type is `Value`, then I can extract `Value` from the box.
+    //
+    // Ideally I would check that Value actually conforms to avType's protocol. Unfortunately, the metedata doesn't include conformance information. I'd have to dig through the conformance sections of the executable file and shared libraries. It's not worth the trouble.
+    else if
+      ExistentialMetadata(avType) != nil
+    {
+      // I can use `Any` as the value type because it's compatible with any protocol existential.
+      let anyStrategy = Strategy<Enum, Any>(nonExistentialTag: tag)
+      self = .existential { anyStrategy.extract(from: $0, tag: tag) }
+    }
+
+    else {
+      // I can't extract a `Value` from the case for `tag`. Presumably it's because the case's associated value is a completely different, unrelated type.
+      return nil
+    }
   }
 
-  // This witness transforms an enum value into its associated value, in place.
-  var destructiveProjectEnumData:
-    @convention(c) (_ value: UnsafeMutableRawPointer, _ metadata: UnsafeRawPointer) -> Void
-  {
-    return ptr.advanced(by: 11 * pointerSize + 2 * 4).loadInferredType()
+  init(nonExistentialTag tag: UInt32) {
+    self = EnumMetadata(assumingEnum: Enum.self)
+      .typeDescriptor
+      .fieldDescriptor!
+      .field(atIndex: tag)
+      .flags
+      .contains(.isIndirectCase)
+      ? .indirect
+      : .direct
   }
-}
 
-extension ValueWitnessTable {
-  struct Flags: OptionSet {
-    var rawValue: UInt32
+  func extract(from root: Enum, tag: UInt32) -> Value? {
+    switch self {
+    case .unimplemented:
+      return nil
 
-    static var isNonInline: Self { .init(rawValue: 0x020000) }
+    case .void:
+      return .some(unsafeBitCast((), to: Value.self))
+
+    case .direct:
+      return withProjectedPayload(of: root, tag: tag) { .some($0.load(as: Value.self)) }
+
+    case .indirect:
+      return withProjectedPayload(of: root, tag: tag) {
+        // In an indirect enum case, the payload is a pointer to a heap object. The heap object's payload is the associated value.
+        return $0
+          .load(as: UnsafeRawPointer.self) // Load the heap object pointer.
+          .advanced(by: 2 * pointerSize) // Skip the heap object header.
+          .load(as: Value.self)
+      }
+
+    case .existential(get: let get):
+      guard
+        let any = get(root),
+        let value = any as? Value
+      else { return nil }
+      return .some(value)
+    }
   }
-}
 
-private struct MetadataKind: Equatable {
-  var rawValue: UInt
+  private func withProjectedPayload<Enum, Answer>(
+    of root: Enum,
+    tag: UInt32,
+    do body: (UnsafeRawPointer) -> Answer
+  ) -> Answer {
+    var root = root
+    let answer: Answer = withUnsafeMutableBytes(of: &root) { rawBuffer in
+      let pointer = rawBuffer.baseAddress!
+      let metadata = EnumMetadata(assumingEnum: Enum.self)
 
-  // https://github.com/apple/swift/blob/master/include/swift/ABI/MetadataValues.h
-  // https://github.com/apple/swift/blob/master/include/swift/ABI/MetadataKind.def
-  // 0x201 = MetadataKind::Enum
-  // 0x202 = MetadataKind::Optional
-  static var enumeration: Self { .init(rawValue: 0x201) }
-  static var optional: Self { .init(rawValue: 0x202) }
+      // On entry, pointer points to some `Enum` value known to the Swift compiler. So on exit, it still needs to point to that `Enum` value, because the compiler wants to destroy the value in the usual way.
+
+      metadata.destructivelyProjectPayload(of: pointer)
+      // `pointer` now points to an `Enum` case payload. Tag bits have been set to zero as needed.
+
+      let answer = body(pointer)
+
+      metadata.destructivelyInjectTag(tag, intoPayload: pointer)
+      // `pointer` now points to an `Enum` again.
+
+      return answer
+    }
+    return answer
+  }
 }
 
+// MARK: -
+
 private protocol Metadata {
   var ptr: UnsafeRawPointer { get }
 }
@@ -186,28 +359,42 @@ extension Metadata {
   }
 
   var kind: MetadataKind { ptr.load(as: MetadataKind.self) }
+}
 
-  func initialize(_ dest: UnsafeMutableRawPointer, byCopying source: UnsafeMutableRawPointer) {
-    _ = valueWitnessTable.initializeWithCopy(dest, source, ptr)
-  }
+private struct MetadataKind: Equatable {
+  var rawValue: UInt
 
-  func initialize(_ dest: UnsafeMutableRawPointer, byTaking source: UnsafeMutableRawPointer) {
-    _ = valueWitnessTable.initializeWithTake(dest, source, ptr)
-  }
+  // https://github.com/apple/swift/blob/main/include/swift/ABI/MetadataValues.h
+  // https://github.com/apple/swift/blob/main/include/swift/ABI/MetadataKind.def
+  // 0x201 = MetadataKind::Enum
+  // 0x202 = MetadataKind::Optional
+  // 0x301 = MetadataKind::Tuple
+  // 0x303 = MetadataKind::Existential
+  static var enumeration: Self { .init(rawValue: 0x201) }
+  static var optional: Self { .init(rawValue: 0x202) }
+  static var tuple: Self { .init(rawValue: 0x301) }
+  static var existential: Self { .init(rawValue: 0x303) }
 }
 
-private struct NativeObjectMetadata: Metadata {
-  let ptr: UnsafeRawPointer
-}
+// MARK: -
 
 private struct EnumMetadata: Metadata {
   let ptr: UnsafeRawPointer
 
-  init?(_ type: Any.Type) {
+  init(assumingEnum type: Any.Type) {
     ptr = unsafeBitCast(type, to: UnsafeRawPointer.self)
+  }
+
+  init?(_ type: Any.Type) {
+    self.init(assumingEnum: type)
     guard kind == .enumeration || kind == .optional else { return nil }
   }
 
+  var genericArguments: GenericArgumentVector? {
+    guard typeDescriptor.flags.contains(.isGeneric) else { return nil }
+    return .init(ptr: ptr.advanced(by: 2 * pointerSize))
+  }
+
   var typeDescriptor: EnumTypeDescriptor {
     return EnumTypeDescriptor(
       ptr: ptr.advanced(by: pointerSize).load(as: UnsafeRawPointer.self))
@@ -218,98 +405,136 @@ private struct EnumMetadata: Metadata {
       valueWitnessTable.getEnumTag($0, self.ptr)
     }
   }
+}
 
-  func directAssociatedValue<Enum, Value>(of enumCase: Enum, as type: Value.Type) -> Value {
-    let enumPtr = UnsafeMutablePointer<Enum>.allocate(capacity: 1)
-    enumPtr.initialize(to: enumCase)
-
-    let untypedPtr = UnsafeMutableRawPointer(enumPtr)
-    valueWitnessTable.destructiveProjectEnumData(untypedPtr, ptr)
+extension EnumMetadata {
+  func associatedValueType(forTag tag: UInt32) -> Any.Type {
+    guard
+      let typeName = typeDescriptor.fieldDescriptor?.field(atIndex: tag).typeName,
+      let type = swift_getTypeByMangledNameInContext(
+        typeName.ptr, typeName.length,
+        genericContext: typeDescriptor.ptr,
+        genericArguments: genericArguments?.ptr)
+    else {
+      // There's not really a good answer for this. Void is a safe answer since it's zero-size.
+      return Void.self
+    }
 
-    let valuesPtr = untypedPtr.assumingMemoryBound(to: Value.self)
-    let values = valuesPtr.pointee
+    return type
+  }
+}
 
-    valuesPtr.deinitialize(count: 1)
-    valuesPtr.deallocate()
+@_silgen_name("swift_getTypeByMangledNameInContext")
+private func swift_getTypeByMangledNameInContext(
+  _ name: UnsafePointer<UInt8>,
+  _ nameLength: UInt,
+  genericContext: UnsafeRawPointer?,
+  genericArguments: UnsafeRawPointer?)
+-> Any.Type?
+
+extension EnumMetadata {
+  func destructivelyProjectPayload(of value: UnsafeMutableRawPointer) {
+    valueWitnessTable.destructiveProjectEnumData(value, ptr)
+  }
 
-    return values
+  func destructivelyInjectTag(_ tag: UInt32, intoPayload payload: UnsafeMutableRawPointer) {
+    valueWitnessTable.destructiveInjectEnumData(payload, tag, ptr)
   }
+}
+
+// MARK: -
 
-  func indirectAssociatedValue<Enum, Value>(of enumCase: Enum, as type: Value.Type) -> Value {
-    // This is closely based on EnumImpl::subscript.
-    // https://github.com/apple/swift/blob/master/stdlib/public/runtime/ReflectionMirror.cpp
+private struct EnumTypeDescriptor {
+  let ptr: UnsafeRawPointer
 
-    // I'll need access to this thing's bytes, which means it has to be a var.
-    var enumCase = enumCase
+  var flags: Flags { Flags(rawValue: ptr.load(as: UInt32.self)) }
 
-    // Storage for an existential container with no conformances. In the C++ code, this is declared `Any enumCopy`, but `Any` is a `using` alias for `OpaqueExistentialContainer`.
-    var enumCopy = OpaqueExistentialContainer(nil, nil, nil, metadata: nil)
+  var fieldDescriptor: FieldDescriptor? {
+    return ptr
+      .advanced(by: 4 * 4)
+      .loadRelativePointer()
+      .map(FieldDescriptor.init)
+  }
 
-    let answer: Value = withUnsafeMutablePointer(to: &enumCopy) { enumCopy in
-      // A “box” here means a value stored as the payload of a HeapObject.
+  var payloadCaseCount: UInt32 { ptr.advanced(by: 5 * 4).load(as: UInt32.self) & 0xffffff }
 
-      let enumCopyContainer = allocateBoxForExistential(in: enumCopy)
-      initialize(enumCopyContainer, byCopying: &enumCase)
+  var emptyCaseCount: UInt32 { ptr.advanced(by: 6 * 4).load(as: UInt32.self) }
+}
 
-      valueWitnessTable.destructiveProjectEnumData(enumCopyContainer, ptr)
+extension EnumTypeDescriptor {
+  struct Flags: OptionSet {
+    let rawValue: UInt32
 
-      // Note that this getter returns the pointer to the “full” metadata, which must be advanced by a word to become a normal metadata pointer.
-      let boxType = NativeObjectMetadata(
-        ptr: getBuiltinNativeObjectFullMetadata()!.advanced(by: pointerSize))
-      let pair = swift_allocBox(for: boxType.ptr)
-      boxType.initialize(pair.buffer, byTaking: enumCopyContainer)
-      deallocateBoxForExistential(in: enumCopy)
+    static var isGeneric: Self { .init(rawValue: 0x80) }
+  }
+}
 
-      var valuePtr = pair.buffer
-      // The payload is always indirect in this method, so we have to open the box.
-      valuePtr = valuePtr.load(as: UnsafeMutableRawPointer.self)
-      valuePtr = swift_projectBox(valuePtr)
+// MARK: -
 
-      let value = valuePtr.load(as: type)
-      swift_release(pair.heapObject)
-      return value
-    }
+private struct TupleMetadata: Metadata {
+  let ptr: UnsafeRawPointer
 
-    return answer
+  init?(_ type: Any.Type) {
+    ptr = unsafeBitCast(type, to: UnsafeRawPointer.self)
+    guard kind == .tuple else { return nil }
   }
 
-  func allocateBoxForExistential(in buffer: UnsafeMutableRawPointer) -> UnsafeMutableRawPointer {
-    guard valueWitnessTable.flags.contains(.isNonInline) else {
-      return buffer
-    }
+  var elementCount: UInt {
+    return ptr
+      .advanced(by: pointerSize) // kind
+      .load(as: UInt.self)
+  }
 
-    let (heapObject:heapObject, buffer:boxBuffer) = swift_allocBox(for: ptr)
-    buffer.storeBytes(of: heapObject, as: UnsafeMutableRawPointer.self)
-    return boxBuffer
+  var labels: UnsafePointer<UInt8>? {
+    return ptr
+      .advanced(by: pointerSize) // kind
+      .advanced(by: pointerSize) // elementCount
+      .load(as: UnsafePointer<UInt8>?.self)
   }
 
-  func deallocateBoxForExistential(in buffer: UnsafeMutableRawPointer) {
-    guard valueWitnessTable.flags.contains(.isNonInline) else { return }
-    swift_deallocBox(buffer.load(as: UnsafeMutableRawPointer.self))
+  func element(at i: Int) -> Element {
+    return Element(
+      ptr: ptr
+        .advanced(by: pointerSize) // kind
+        .advanced(by: pointerSize) // elementCount
+        .advanced(by: pointerSize) // labels pointer
+        .advanced(by: i * 2 * pointerSize))
   }
 }
 
-@_silgen_name("swift_allocBox")
-private func swift_allocBox(for metadata: UnsafeRawPointer) -> BoxPair
+extension TupleMetadata {
+  struct Element: Equatable {
+    let ptr: UnsafeRawPointer
 
-@_silgen_name("swift_deallocBox")
-private func swift_deallocBox(_ heapObject: UnsafeMutableRawPointer)
+    var type: Any.Type { ptr.load(as: Any.Type.self) }
+    var offset: UInt { ptr.advanced(by: pointerSize).load(as: UInt.self) }
 
-@_silgen_name("swift_projectBox")
-private func swift_projectBox(_ heapObject: UnsafeMutableRawPointer) -> UnsafeMutableRawPointer
+    static func ==(lhs: Element, rhs: Element) -> Bool {
+      return lhs.type == rhs.type && lhs.offset == rhs.offset
+    }
+  }
+}
 
-@_silgen_name("swift_release")
-private func swift_release(_ heapObject: UnsafeMutableRawPointer)
+extension TupleMetadata {
+  func hasSameLayout(as other: TupleMetadata) -> Bool {
+    return self.elementCount == other.elementCount &&
+      (0 ..< Int(elementCount)).allSatisfy { self.element(at: $0) == other.element(at: $0) }
+  }
+}
 
-private struct EnumTypeDescriptor {
+// MARK: -
+
+private struct ExistentialMetadata: Metadata {
   let ptr: UnsafeRawPointer
 
-  var fieldDescriptor: FieldDescriptor {
-    return FieldDescriptor(
-      ptr: ptr.advanced(by: 4 * 4).loadRelativePointer())
+  init?(_ type: Any.Type?) {
+    ptr = unsafeBitCast(type, to: UnsafeRawPointer.self)
+    guard kind == .existential else { return nil }
   }
 }
 
+// MARK: -
+
 private struct FieldDescriptor {
   let ptr: UnsafeRawPointer
 
@@ -327,7 +552,12 @@ private struct FieldRecord {
 
   var flags: Flags { Flags(rawValue: ptr.load(as: UInt32.self)) }
 
-  var isIndirectCase: Bool { flags.contains(.isIndirectCase) }
+  var typeName: MangledTypeName? {
+    return ptr
+      .advanced(by: 4)
+      .loadRelativePointer()
+      .map { MangledTypeName(ptr: $0.assumingMemoryBound(to: UInt8.self)) }
+  }
 }
 
 extension FieldRecord {
@@ -338,44 +568,76 @@ extension FieldRecord {
   }
 }
 
-#if compiler(<5.2)
+private struct MangledTypeName {
+  let ptr: UnsafePointer<UInt8>
+
+  var length: UInt {
+    // Type name mangling is described here:
+    // https://github.com/apple/swift/blob/main/docs/ABI/Mangling.rst
+    // Since a mangled name can contain NUL bytes, I can't just use `strlen` or equivalent.
+
+    var p = ptr
+    while true {
+      switch p.pointee {
+      case 0:
+        return UInt(bitPattern: p - ptr)
+      case 0x01...0x17:
+        // Relative symbolic reference.
+        p = p.advanced(by: 5)
+      case 0x18...0x1f:
+        // Absolute symbolic reference
+        p = p.advanced(by: 1 + pointerSize)
+      default:
+        // Just a humble character.
+        p = p.advanced(by: 1)
+      }
+    }
+  }
+}
 
-  // https://bugs.swift.org/browse/SR-12044
-  private func workaroundForSR12044<Value>(_ type: Value.Type) -> Value? {
-    // If Value is an inhabited type with a size of zero, Mirror doesn't notice it as the associated value of an enum case due to incorrect metadata. But, being inhabited with a size of zero, it has only one possible inhabitant, so I create the inhabitant here using unsafeBitCast.
+// MARK: -
 
-    // An uninhabited type like Never also has a size of zero, and I have to be careful not to create a value of an uninhabited type.
+private struct ValueWitnessTable {
+  let ptr: UnsafeRawPointer
 
-    // It's possible for a tuple, struct, or class to be uninhabited by having an uninhabited stored property. But detecting such a type is difficult as I'd have to scrounge through even more metadata. So instead I'm just checking for the common case of an uninhabited enum. If you do something like `enum E { case c(Never, Never) }`... you have my sincere apology.
+  var getEnumTag: @convention(c) (_ value: UnsafeRawPointer, _ metadata: UnsafeRawPointer) -> UInt32
+  {
+    return ptr.advanced(by: 10 * pointerSize + 2 * 4).loadInferredType()
+  }
 
-    if MemoryLayout<Value>.size == 0,
-      !isUninhabitedEnum(Value.self)
-    {
-      return unsafeBitCast((), to: Value.self)
-    }
-    return nil
+  // This witness transforms an enum value into its associated value, in place.
+  var destructiveProjectEnumData:
+    @convention(c) (_ value: UnsafeMutableRawPointer, _ metadata: UnsafeRawPointer) -> Void
+  {
+    return ptr.advanced(by: 11 * pointerSize + 2 * 4).loadInferredType()
   }
 
-  private func isUninhabitedEnum(_ type: Any.Type) -> Bool {
-    // If it lacks enum metadata, it's definitely not an uninhabited enum.
-    guard let metadata = EnumMetadata(type) else { return false }
-    return !metadata.typeDescriptor.isInhabited
+  // This witness transforms an associated value into its enum value, in place.
+  var destructiveInjectEnumData:
+    @convention(c) (_ value: UnsafeMutableRawPointer, _ tag: UInt32, _ metadata: UnsafeRawPointer) -> Void
+  {
+    return ptr.advanced(by: 12 * pointerSize + 2 * 4).loadInferredType()
   }
+}
 
-  extension EnumTypeDescriptor {
-    var numPayloadCases: Int32 {
-      return ptr.advanced(by: 5 * 4).load(as: Int32.self) & 0xFFFFFF
-    }
+// MARK: -
 
-    var numEmptyCases: Int32 {
-      return ptr.advanced(by: 6 * 4).load(as: Int32.self)
-    }
+private struct GenericArgumentVector {
+  let ptr: UnsafeRawPointer
+}
 
-    var isInhabited: Bool { numPayloadCases + numEmptyCases > 0 }
-  }
+// MARK: -
 
-#else
+extension UnsafeRawPointer {
+  fileprivate func loadInferredType<Type>() -> Type {
+    return load(as: Type.self)
+  }
 
-  private func workaroundForSR12044<Value>(_ type: Value.Type) -> Value? { nil }
+  fileprivate func loadRelativePointer() -> UnsafeRawPointer? {
+    let offset = Int(load(as: Int32.self))
+    return offset == 0 ? nil : self + offset
+  }
+}
 
-#endif
+// This is the size of any Unsafe*Pointer and also the size of Int and UInt.
+private let pointerSize = MemoryLayout<UnsafeRawPointer>.size


Test patch:
diff --git a/Tests/CasePathsTests/CasePathsTests.swift b/Tests/CasePathsTests/CasePathsTests.swift
index 97b004e..79ff783 100644
--- a/Tests/CasePathsTests/CasePathsTests.swift
+++ b/Tests/CasePathsTests/CasePathsTests.swift
@@ -8,6 +8,9 @@ private func unwrap<Wrapped>(_ optional: Wrapped?) throws -> Wrapped {
 }
 private struct UnexpectedNil: Error {}
 
+protocol TestProtocol { }
+extension Int: TestProtocol { }
+
 final class CasePathsTests: XCTestCase {
   func testSimplePayload() {
     enum Enum { case payload(Int) }
@@ -337,6 +340,113 @@ final class CasePathsTests: XCTestCase {
     }
   }
 
+  func testAssociatedValueIsExistential() {
+    enum Enum {
+        case proto(TestProtocol)
+        case int(Int)
+    }
+
+    let protoPath = /Enum.proto
+    let intPath = /Enum.int
+
+    for _ in 1...2 {
+        XCTAssertNil(protoPath.extract(from: .int(100)))
+        XCTAssertEqual(protoPath.extract(from: .proto(100)) as? Int, 100)
+
+        XCTAssertNil(intPath.extract(from: .proto(100)))
+        XCTAssertEqual(intPath.extract(from: .int(100)), 100)
+    }
+  }
+
+  func testContravariantEmbed() {
+    enum Enum {
+      // associated value type is TestProtocol existential
+      case directExistential(TestProtocol)
+
+      // associated value type is single-element tuple (TestProtocol existential)
+      case directTuple(label: TestProtocol)
+
+      indirect case indirectExistential(TestProtocol)
+
+      indirect case indirectTuple(label: TestProtocol)
+
+      static let cdeCase = Enum.directExistential(Conformer())
+      static let cdtCase = Enum.directTuple(label: Conformer())
+      static let cieCase = Enum.indirectExistential(Conformer())
+      static let citCase = Enum.indirectTuple(label: Conformer())
+
+      static let ideCase = Enum.directExistential(100)
+      static let idtCase = Enum.directTuple(label: 100)
+      static let iieCase = Enum.indirectExistential(100)
+      static let iitCase = Enum.indirectTuple(label: 100)
+    }
+
+    // This is intentionally too big to fit in the three-word buffer of a protocol existential, so that it is stored indirectly.
+    struct Conformer: TestProtocol, Equatable {
+      var a, b, c, d: Int
+      init() {
+        (a, b, c, d) = (100, 300, 200, 400)
+      }
+    }
+
+    let dePath: CasePath<Enum, Conformer> = /Enum.directExistential
+    let dtPath: CasePath<Enum, Conformer> = /Enum.directTuple
+    let iePath: CasePath<Enum, Conformer> = /Enum.indirectExistential
+    let itPath: CasePath<Enum, Conformer> = /Enum.indirectTuple
+
+    for _ in 1...2 {
+
+      XCTAssertNil(dePath.extract(from: .cdtCase))
+      XCTAssertNil(dePath.extract(from: .cieCase))
+      XCTAssertNil(dePath.extract(from: .citCase))
+      XCTAssertNil(dePath.extract(from: .ideCase))
+      XCTAssertNil(dePath.extract(from: .idtCase))
+      XCTAssertNil(dePath.extract(from: .iieCase))
+      XCTAssertNil(dePath.extract(from: .iitCase))
+      XCTAssertEqual(dePath.extract(from: .cdeCase), .some(Conformer()))
+
+      XCTAssertNil(dtPath.extract(from: .cdeCase))
+      XCTAssertNil(dtPath.extract(from: .cieCase))
+      XCTAssertNil(dtPath.extract(from: .citCase))
+      XCTAssertNil(dtPath.extract(from: .ideCase))
+      XCTAssertNil(dtPath.extract(from: .idtCase))
+      XCTAssertNil(dtPath.extract(from: .iieCase))
+      XCTAssertNil(dtPath.extract(from: .iitCase))
+      XCTAssertEqual(dtPath.extract(from: .cdtCase), .some(Conformer()))
+
+      XCTAssertNil(iePath.extract(from: .cdeCase))
+      XCTAssertNil(iePath.extract(from: .cdtCase))
+      XCTAssertNil(iePath.extract(from: .citCase))
+      XCTAssertNil(iePath.extract(from: .ideCase))
+      XCTAssertNil(iePath.extract(from: .idtCase))
+      XCTAssertNil(iePath.extract(from: .iieCase))
+      XCTAssertNil(iePath.extract(from: .iitCase))
+      XCTAssertEqual(iePath.extract(from: .cieCase), .some(Conformer()))
+
+      XCTAssertNil(itPath.extract(from: .cdeCase))
+      XCTAssertNil(itPath.extract(from: .cdtCase))
+      XCTAssertNil(itPath.extract(from: .cieCase))
+      XCTAssertNil(itPath.extract(from: .ideCase))
+      XCTAssertNil(itPath.extract(from: .idtCase))
+      XCTAssertNil(itPath.extract(from: .iieCase))
+      XCTAssertNil(itPath.extract(from: .iitCase))
+      XCTAssertEqual(itPath.extract(from: .citCase), .some(Conformer()))
+    }
+  }
+
+  func testUnreasonableContravariantEmbed() {
+    enum Enum {
+      case c(TestProtocol, Int)
+    }
+
+    // The library doesn't handle this crazy esoteric case, but it detects it and returns nil instead of garbage.
+    let path: CasePath<Enum, (Int, Int)> = /Enum.c
+
+    for _ in 1...2 {
+      XCTAssertNil(path.extract(from: .c(34, 12)))
+    }
+  }
+
   func testEmbed() {
     enum Foo: Equatable { case bar(Int) }
 
@@ -489,6 +599,21 @@ final class CasePathsTests: XCTestCase {
     )
   }
 
+  func testCompoundUninhabitedType() {
+    // Under Swift 5.1 (Xcode 11.3), this test creates a bogus instance of the tuple `(Never, Never)`, but remarkably, doesn't cause a crash and extracts the correct answer (nil).
+
+    enum Enum {
+      case nevers(Never, Never)
+      case something(Void)
+    }
+
+    let path: CasePath<Enum, (Never, Never)> = /Enum.nevers(_:_:)
+
+    for _ in 1...2 {
+      XCTAssertNil(path.extract(from: Enum.something(())))
+    }
+  }
+
   func testNestedUninhabitedTypes() {
     enum Uninhabited {}