Challenge: Finding base type of nested optionals

Following on from my last challenge, this one is somewhat trickier:

Given an arbitrarily-nested Optional, the goal is to programmatically identify the inner-most Wrapped type (aka. its base type). Note that the optional may be nil at any depth, and it may be wrapped in further layers of Any and/or Optional.

For example, an Int??? has a base type of Int, regardless of its value. Moreover, casting an Optional to Any, and/or wrapping it in additional layers of Optional, does not change its base type.

Can you write such a function?

The signature should be:

extension Optional {
  func baseType() -> Any.Type
}
fileprivate protocol Wrapper {
  static func baseType() -> Any.Type
  func baseType() -> Any.Type
}

extension Optional: Wrapper {
  static func baseType() -> Any.Type {
    var type: Any.Type = Wrapped.self
    while let wrapper = type as? Wrapper.Type {
      type = wrapper.baseType()
    }
    return type
  }

  func baseType() -> Any.Type {
    var base: Any.Type
    switch self {
    case .some(let value):
      if let wrapper = value as? Wrapper {
        base = wrapper.baseType()
      } else {
        base = Wrapped.self
      }
    case .none:
      base = Wrapped.self
    }
    if let wrapper = base as? Wrapper.Type {
      base = wrapper.baseType()
    }
    return base
  }
}

I think this works now. It will unwrap the value as much as possible and at the end we will also try to check the wrapper type if needed.

3 Likes

@Nevin please do more challenges :slight_smile: Also we need a way to verify the solutions (I‘m not sure if I covered all possible cases).

Well done! That is rather more elegant than the solution I had in mind, which involved two procotols.

Here’s what I’ve been using to test:

Testing for base type
// Creating obnoxiously-wrapped optionals for testing

func deeplyWrap<T>(_ x: T?) -> Any? {
  switch Int.random(in: 0..<10) {
  case 0: return x as Any
  case 1..<4: return deeplyWrap(x as Any)
  default: return deeplyWrap(Optional(x))
  }
}


// Testing the implementation of Optional.baseType

func testBaseType<T>(_ x: T?) -> [Any.Type] {
  let a: T? = x
  let b: T?? = Optional(a)
  let c: T??? = Optional(b)
  let d: Any? = Optional(c as Any)
  let e: Any? = Optional(d as Any)
  let f: Any??? = Optional(Optional(e))
  let g: Any? = Optional(f as Any)
  
  // Do not try to use `map` here like this:
  //
  //   let results = [a, b, c, d, e, f, g].map{ $0.baseType() }
  //
  // It will not work because the types of a...g are different
  // and weird things happen when eg. T?? is coerced to Any???
  
  let results = [a.baseType(),
                 b.baseType(),
                 c.baseType(),
                 d.baseType(),
                 e.baseType(),
                 f.baseType(),
                 g.baseType()]
  
  print(results.map{"\($0)"}.joined(separator: " "))
  
  return results
}


// Actually calling the tests

do {
  testBaseType(nil as Int?)
  testBaseType("2" as String???)
  testBaseType(nil as Int??)
  testBaseType("a")
  testBaseType(2)
  
  let q = deeplyWrap(nil as String????)
  print()
  print(type(of: q))
  print(q.debugDescription)
  testBaseType(q)
  
  let q2 = deeplyWrap(4 as Int????)
  print()
  print(type(of: q2))
  print(q2.debugDescription)
  testBaseType(q2)
}

I was able to simplify your second function a bit:

  func baseType() -> Any.Type {
    if case .some(let value as Wrapper) = self {
      return value.baseType()
    }
    if let wrapper = Wrapped.self as? Wrapper.Type {
      return wrapper.baseType()
    }
    return Wrapped.self
  }

And, not sure if it counts as “simpler”, but I also shortened your static function by one line:

  static func baseType() -> Any.Type {
    if let wrapper = Wrapped.self as? Wrapper.Type {
      return wrapper.baseType()
    }
    return Wrapped.self
  }

• • •

Edit:

Actually, they can be reduced even further with optional chaining and nil-coalescing:

extension Optional: Wrapper {
  static func baseType() -> Any.Type {
    return (Wrapped.self as? Wrapper.Type)?.baseType() ?? Wrapped.self
  }
  
  func baseType() -> Any.Type {
    if case .some(let value as Wrapper) = self {
      return value.baseType()
    }
    return Wrapped?.baseType()
  }
}

This is way nicer than the solution I had come up with on my own!

• • •

Edit 2:

Shortened the last line of the non-static method, for DRYness. (It had been identical to the body of the static method.) Once SE–68 is available (in Swift 5.1), it can even become “return Self.baseType()”.

2 Likes

So while reading through and experimenting with this code to truly understand how it works, I came across what (to me) was some surprising behavior.

Consider the following sample code, which uses @Nevin's concise extension from above:

let wrappedInt: Int? = 7
let doublyWrappedInt: Any?? = Optional(wrappedInt as Any)

type(of: doublyWrappedInt) // Optional<Optional<Any>>.Type

doublyWrappedInt.baseType() // Int.Type

No real surprises here. Now let's just change that second line slightly…

let wrappedInt: Int? = 7
let doublyWrappedInt: Any?? = wrappedInt

type(of: doublyWrappedInt) // Optional<Optional<Any>>.Type

doublyWrappedInt.baseType() // Any.Protocol

Why is it that even though type(of: doublyWrappedInt) still returns Optional<Optional<Any>>, baseType() now returns Any.Protocol instead of Int.Type?

If you take my original example and put some print logs to trace where the algorithm goes you can find out the issue here:

extension Optional: Wrapper {
  static func baseType() -> Any.Type {
    print("6")
    var type: Any.Type = Wrapped.self
    while let wrapper = type as? Wrapper.Type {
      print("7")
      type = wrapper.baseType()
    }
    return type
  }

  func baseType() -> Any.Type {
    var base: Any.Type
    switch self {
    case .some(let value):
      print("1", type(of: value), value)
      if let wrapper = value as? Wrapper {
        print("2")
        base = wrapper.baseType()
      } else {
        print("3")
        base = Wrapped.self // should be `type(of: value)`
      }
    case .none:
      print("4")
      base = Wrapped.self 
    }
    if let wrapper = base as? Wrapper.Type {
      print("5")
      base = wrapper.baseType()
    }
    return base
  }
}

The result is:

1 Optional<Any> Optional(7)
2
1 Any 7 // this could be a compiler bug?
3

That means that in the line let doublyWrappedInt: Any?? = wrappedInt there is an implicit conversion from Optional<Int> to Optional<Any>. At this case I think the algorithm must be adjusted. Instead of base = Wrapped.self we should use base = type(of: value). If we do that the result remains the same as already noted above type(of: value) does not return Int but Any which feels like a bug.

@Nevin I would rewrite my original solution to this:

fileprivate protocol Wrapper {
  static func baseType() -> Any.Type
  func baseType() -> Any.Type
}

extension Optional: Wrapper {
  fileprivate static func baseType() -> Any.Type {
    switch Wrapped.self {
    case let wrapper as Wrapper.Type:
      return wrapper.baseType()
    default:
      return Wrapped.self
    }
  }

  func baseType() -> Any.Type {
    switch self {
    case .some(let wrapper as Wrapper):
      return wrapper.baseType()
    case .some(let wrapped):
      return type(of: wrapped)
    case .none:
      return Optional.baseType()
    }
  }
}
1 Like

Interesting. If that's the case, why doesn't Optional(wrappedInt as Any) also involve a conversion from Optional<Int> to Optional<Any>?

I can only guess, but I'd think that this example is a little different. Optional(wrappedInt as Any) creates an Optional<Any> while that inner Any is by itself Optional<Int>. Then you pass Optional<Any> (hidden Optional<Optional<Int>>) to be stored by an Optional<Optional<Any>. I'd guess that the compiler just does something like this:

let _: Any?? = Optional.some(/* our `Optional<Any> (or: Int??)`*/`)

If I'm correct this is an optional with three levels.

While in the other weird case we only get an optional with two levels and for some weird reason type(of:) can't extract the type of the most wrapped value.

I hope this is somehow understandable. :smiley:

1 Like

Well, I'd be lying if I said that I completely understand what's going on now, but this probably isn't the time or the place for a full primer on how type erasure with Any works. Still, it's good to know that I'm not the only one who's a bit surprised by the behavior I encountered earlier. :)

We can quickly test it.

fileprivate protocol Wrapper {
  static func baseType(level: inout Int) -> Any.Type
  func baseType(level: inout Int) -> Any.Type
}

extension Optional: Wrapper {
  fileprivate static func baseType(level: inout Int) -> Any.Type {
    level += 1
    switch Wrapped.self {
    case let wrapper as Wrapper.Type:
      return wrapper.baseType(level: &level)
    default:
      return Wrapped.self
    }
  }

  func baseType(level: inout Int) -> Any.Type {
    level += 1
    switch self {
    case .some(let wrapper as Wrapper):
      return wrapper.baseType(level: &level)
    case .some(let wrapped):
      return type(of: wrapped)
    case .none:
      return Optional.baseType(level: &level)
    }
  }
}

let wrappedValue: String? = "Swift"
let test_1: Any?? = wrappedValue
let test_2: Any?? = Optional(wrappedValue as Any)

var level = 0
print(test_1.baseType(level: &level), level) // prints `Any 2`

level = 0
print(test_2.baseType(level: &level), level) // prints `String 3`

This verifies my assumption.


Filed a bug report: [SR-10823] `type(of:)` cannot extract the type erased with `Any` · Issue #53213 · apple/swift · GitHub

Oh, now I think I see what you mean! test_2 is declared as Any??, but it's actually an Any???. For some reason I didn't realize that Any could be hiding any number of layers of optionality behind it, but in hindsight I guess that makes sense—Any really does mean anything, optional or not.

2 Likes

Yep test_2 in reality is String???, but is erased as Any??, while test_1 is String?? erased as Any??. However type(of:) seems bugged or there is an issue with implicit existentials here, I really don't know.

1 Like

Well here's a challenge that I still haven't found an answer too:
How do you unwrap an arbitrarily nested optional to a single-wrapped optional while preserving the base type?. All the solutions in this post and all the other posts on this topic I've seen either type-erase the result to Any? or don't truly support arbitrarily nested optionals.

Finding yourself in a situation where you think you need this is a code smell IMO.

Could you specify a signature for the solution?

Something like

extension Optional {
  func singleWrapped: Optional<SomeUnspecifiableBaseType> { ... }
}

?

I mean, if the type of the input (the "arbitrarily nested optional") is unknowable at compile time (a user could have specified it at runtime), then by definition, it is impossible to represent both the input type and the output (singleWrapped) type as anything other than Optional<Any> or Any.


If you do know what the final Wrapped type is, then it might be possible, but that's not how I understood the challenge.

You're probably right that there is no solution to my question. I was hoping it could be solved with generics, but this is probably not something the type system can handle.

How would any type system be able to magically guess what type eg a user or some truly random process result in at runtime?

And how would you represent, textually, for the compiler (ie at compile-time), a type that is only knowable at runtime?

This is what type erasing, Any etc is for.

Sorry, I should have been more specific: I didn't mean to suggest that the type would be unknownable at compile time. What I had in mind was a function that used generic types in such a way that it could accept any arbitrarily-nested optional type. The type system would still know at compile time exactly how many levels of optionality the type has and what the base type is.

If you can accept an upper limit of say 10 levels of optionality, then I guess you could use something like the following (which is the same as this):

postfix operator …?
/// Unwraps 1 to 10 layers of `Optional`ity.
postfix func …?<T>(v: T??????????) -> T? { (v as? T?) ?? nil }

// Demo:
for _ in 0 ..< 3 {
  let a: Int?????? = Bool.random() ? 123 : nil
  let b: Bool? = Bool.random() ? true : nil
  let c: String???????? = Bool.random() ? "Hello" : nil
  let d: Float??? = Bool.random() ? 1.23 : nil
  let ua = a…?
  let ub = b…?
  let uc = c…?
  let ud = d…?
  print("--")
  print(type(of: ua), " | ", ua ?? "nil")
  print(type(of: ub), " | ", ub ?? "nil")
  print(type(of: uc), " | ", uc ?? "nil")
  print(type(of: ud), " | ", ud ?? "nil")
}

Not sure if it would be possible to express in some recursive way that would lift the upper limit.


I maintain that if you feel the need for something like this, then it is an indication of some deeper problem of your design.