Dependent types... of some sorts?

[idubrov]

I have a need for an API which I cannot really articulate, but can give an example.

Let's say, I have the following trait:

enum Value<'a> {
  Object(&'a dyn Object),
  List(&'a dyn List),
}
trait Object: 'static {
  fn field<'a>(&'a self, name: &str) -> Value<'a>;
}
trait List: 'static {
  fn get(&self, pos: usize) -> Option<&dyn Object>;
}

The common usage would be the following match statement:

fn traverse(value: Value) -> Value {
    let parent = match value {
        Value::Object(obj) => obj,
        Value::List(list) => panic!("cannot traverse lists"),
    };
    parent.field("some_field")
}

This enum unifies all possible value "kinds" (Object, List) into one single data structure.

Now, I want to put original object behind an ArcRef, so I don't have to worry about lifetimes:

// Everything is owned with some `Arc<dyn Object>` at the top, so the first type parameter
// for `ArcRef` is `dyn Object`.
enum ArcValue {
  Object(owning_ref::ArcRef<dyn Object, dyn Object>),
  List(owning_ref::ArcRef<dyn Object, dyn List>),
}

The challenge is how do I write traverse function for this case? map function requires me to return a reference. However, in my case, I need to return an enum having a reference inside it (Value). One way is to do a double-match: first, we do match outside to figure out which case we are handling, then we do an inside-match in which we panic if we get into a "wrong" branch:

fn arc_traverse(value: ArcValue) -> ArcValue {
    let parent = match value {
        ArcValue::Object(obj) => obj,
        ArcValue::List(list) => panic!("cannot traverse lists"),
    };
    match parent.field("some_field") {
        Value::Object(_obj) => {
            ArcValue::Object(
                parent
                    .clone()
                    .map(|owner| match owner.field("some_field") {
                        Value::Object(obj) => obj,
                        _ => unreachable!(),
                    }),
            )
        }
        Value::List(_list) => {
            ArcValue::List(
                parent
                    .clone()
                    .map(|owner| match owner.field("some_field") {
                        Value::List(list) => list,
                        _ => unreachable!(),
                    }),
            )
        }
    }

This, however, looks very unwieldy & also does work twice (for example, it navigates field some_field twice). An alternative I came with uses unsafe:

fn unsafe_arc_traverse(value: ArcValue) -> ArcValue {
    let parent = match value {
        ArcValue::Object(obj) => obj,
        ArcValue::List(list) => panic!("cannot traverse lists"),
    };
    match parent.field("some_field") {
        Value::Object(obj) => {
            let obj_ptr = obj as *const _;
            unsafe { ArcValue::Object(parent.map(|_owner| &*obj_ptr)) }
        }
        Value::List(list) => {
            let list_ptr = list as *const _;
            unsafe { ArcValue::List(parent.map(|_owner| &*list_ptr)) }
        }
    }
}

The idea here is to "smuggle" reference inside the .map() closure by casting it to the pointer. First, we "erase" the lifetime, making it an unbounded lifetime. Then, we convert it back to the reference inside the closure, pretending that we obtained this reference inside the closure.

Since we obtained this reference from the same parent, it looks like this is okay to do, however, would be nice if there was some specific API to do that.

I'm not sure what this API should look like, though. I don't think it is possible with current Rust type system (it feels that it needs to generalize over output types in a way that is currently not possible in Rust), but maybe I'm missing something.