Strong typing for IDs

[hyanwong]

@MomoLangenstein suggested that it might be a good idea to enforce strong typing on integer IDs in the Rust API, so that you don't, for example accidentally pass an individual ID to a function that expects a node ID. There was some discussion in the Slack channel about this: apparently some similar type constraints were previously implemented in the tskit C API but then removed because it required typing too much boilerplate, for not much discernible benefit. But @molpopgen has just said:

Interestingly (because you can't do this in C), you seem to be able to do this in rust in a way that may not break API and would still allow the plain tsk_id_t to be passed to functions.

Perhaps @MomoLangenstein could weigh in here with what they were thinking about?

ID types needed for this to be closed:

• Node, done via Add strong ID type infrastructure + NodeID #129
• Individual, done via add IndividualId #133
• Population, done via add population id #135
• Edge, via add EdgeId #138
• Site, via add mutation and site id #136
• Mutation, via add mutation and site id #136
• Provenance, via add migration provenance ids #137
• Migration, via add migration provenance ids #137

[hyanwong]

The main concern that we have come across in the Python API is people confusing Individual IDs with Node IDs (see e.g. tskit-dev/tskit#464), so a minimal implementation might be to require Individual IDs to be strongly typed, but allow plain integers for all the other ideas. Possibly a half-baked idea, but I mention it here anyway :)

[molpopgen]

The main concern that we have come across in the Python API is people confusing Individual IDs with Node IDs (see e.g. tskit-dev/tskit#464), so a minimal implementation might be to require Individual IDs to be strongly typed, but allow plain integers for all the other ideas. Possibly a half-baked idea, but I mention it here anyway :)

Here, I am of the (weak-to-modestly-strong) opinion that an API addition to return node IDs somehow may be the solution, but that's a bit of a digression.

[molpopgen]

My comment re: can do this nicely in rust has primarily to do with scalars and not vectors nor with slices.
We require/desire to support stronger typing without breaking the current API. The question of strong types then becomes a matter of traits rather than of types.

For example, this works, in the sense that all existing tests still pass:

pub trait NodeId {
    fn id(&self) -> tsk_id_t;
}

// create a strong type
// This should derive Copy, Clone, Eq, and PartialEq,
// and should impl From for tsk_id_t
pub struct NodeIdType(tsk_id_t);

impl NodeId for NodeIdType {
    fn id(&self) -> tsk_id_t {
        self.0
    }
}

impl NodeId for tsk_id_t {
    fn id(&self) -> tsk_id_t {
        *self
    }
}

// Update our member functions as such

    /// Add a row to the edge table
    pub fn add_edge(
        &mut self,
        left: f64,
        right: f64,
        parent: impl NodeId,
        child: impl NodeId,
    ) -> TskReturnValue {
        self.add_edge_with_metadata(left, right, parent, child, None)
    }

    /// Add a row with metadata to the edge table
    pub fn add_edge_with_metadata(
        &mut self,
        left: f64,
        right: f64,
        parent: impl NodeId,
        child: impl NodeId,
        metadata: Option<&dyn MetadataRoundtrip>,
    ) -> TskReturnValue {
        let md = EncodedMetadata::new(metadata)?;
        let rv = unsafe {
            ll_bindings::tsk_edge_table_add_row(
                &mut (*self.as_mut_ptr()).edges,
                left,
                right,
                parent.id(),
                child.id(),
                md.as_ptr(),
                md.len(),
            )
        };

        handle_tsk_return_value!(rv)
    }

So, the right set of macros can handle all the boiler plate for scalars.
The trick is to also allow Vec<NodeId> and &[NodeId] transparently.
Doing so may be possible, but is not nearly as easy, I think.

[juntyr]

What I was thinking about is going down the entirely idiomatic route and defining:

#[repr(transparent)]
struct IndividualId(tsk_id_t);
#[repr(transparent)]
struct NodeId(tsk_id_t);
#[repr(transparent)]
struct EdgeId(tsk_id_t);

All non-ffi functions would return and take these types. You could then implement From<tsk_id_t> and Into<tsk_id_t> to still allow rogue conversions (or you could even make them unsafe as you should conceptually only use identifiers you got from the API).

This would only be a change to tskit-rust but break its current API, i.e. require a major version change. If you would like to maintain backwards compatibility for now, you could also make the API methods generic:

fn use_node<N: Into<NodeId>>(node_id: N) { … }

This might be what @molpopgen meant and would allow still passing around the original typedef.

[molpopgen]

This would only be a change to tskit-rust but break its current API, i.e. require a major version change. If you would like to maintain backwards compatibility for now, you could also make the API methods generic:

So, we'd still be at major version 0, and update the minor version here. I don't envision a 1.0 until (well) after the C API hits 1.0.

How do you envision this working for sample lists, e.g. where Vec<tsk_id_t> is currently used, but one may be dealing with Vec<NodeId>?

[juntyr]

Mhm, let me think about that. I don’t like the idea of vectors of trait objects.

So, we'd still be at major version 0, and update the minor version here. I don't envision a 1.0 until (well) after the C API hits 1.0.

The major version update would have only been needed if the API had been changed without backwards compatibility.

[molpopgen]

The major version update would have only been needed if the API had been changed without backwards compatibility.

I'm following semver guidelines here: with major version < 1.0, we are saying we are not guaranteeing backwards compatibililty. Specifically, point 8:

Major version X (X.y.z | X > 0) MUST be incremented if any backwards incompatible changes are introduced to the public API. It MAY also include minor and patch level changes. Patch and minor version MUST be reset to 0 when major version is incremented

And 4:

Major version zero (0.y.z) is for initial development. Anything MAY change at any time. The public API SHOULD NOT be considered stable.

Here, X = 0. I'm not going to bump to 1.0 for a API-breaking change at this point. This is still research in progress.

[juntyr]

You could always implement Deref on the new type as well. Then auto-deref might take care of most if not all use cases where existing code expects the u32. For vecs, I’d therefore just change the type so it returns a vec of new types.

[molpopgen]

You could always implement Deref on the new type as well. Then auto-deref might take care of most if not all use cases where existing code expects the u32. For vecs, I’d therefore just change the type so it returns a vec of new types.

I'd have to see a concrete example.

[molpopgen]

For vecs, I’d therefore just change the type so it returns a vec of new types

This is likely the sticking point, as we lose performance. For example, the simplification algorithm takes a vector of sample IDs, meaning node IDs. We'd be imposing an extra copy.

[juntyr]

The major version update would have only been needed if the API had been changed without backwards compatibility.

I'm following semver guidelines here: with major version < 1.0, we are saying we are not guaranteeing backwards compatibililty. Specifically, point 8:

Major version X (X.y.z | X > 0) MUST be incremented if any backwards incompatible changes are introduced to the public API. It MAY also include minor and patch level changes. Patch and minor version MUST be reset to 0 when major version is incremented

Here, X = 0. I'm not going to bump to 1.0 for a API-breaking change at this point. This is still research in progress.

Ah, thanks for pointing that out - I didn’t know about the special case of 0.x

[molpopgen]

Ah, thanks for pointing that out - I didn’t know about the special case of 0.x

It is my favorite major version number for this very reason. All of my previous ideas are bad, except the new one, which is great until is is bad.

[juntyr]

For vecs, I’d therefore just change the type so it returns a vec of new types

This is likely the sticking point, as we lose performance. For example, the simplification algorithm takes a vector of sample IDs, meaning node IDs. We'd be imposing an extra copy.

Where would that copy occur? If it’s inside your library code, you could write a safe helper function that transmutes the vector type (compiles down to no code at all). Since the ffi just takes pointers, a simple pointer cast will suffice as well (you can safely give the C api a vec of new types as a ptr to the typedef iff you use the transparent representation).

[molpopgen]

Where would that copy occur? If it’s inside your library code, you could write a safe helper function that transmutes the vector type (compiles down to no code at all). Since the ffi just takes pointers, a simple pointer cast will suffice as well (you can safely give the C api a vec of new types as a ptr to the typedef iff you use the transparent representation).

So, I am semi-new to rust. The definition of a NodeID is a tuple (unless the transparent macro changes that?), not an i32, so I assume that the vector pointer is to tuple, and thus assume that its sizeof is invalid. Do I understand that you are saying that this is not the case?

[molpopgen]

Here's a concrete example of a function taking a sample node vector as input:

    /// Simplify tables in place.
    ///
    /// # Parameters
    ///
    /// * `samples`: a slice containing non-null node ids.
    ///   The tables are simplified with respect to the ancestry
    ///   of these nodes.
    /// * `options`: A [`SimplificationOptions`] bit field controlling
    ///   the behavior of simplification.
    /// * `idmap`: if `true`, the return value contains a vector equal
    ///   in length to the input node table.  For each input node,
    ///   this vector either contains the node's new index or [`TSK_NULL`]
    ///   if the input node is not part of the simplified history.
    pub fn simplify(
        &mut self,
        samples: &[tsk_id_t],
        options: SimplificationOptions,
        idmap: bool,
    ) -> Result<Option<Vec<tsk_id_t>>, TskitError> {
        let mut output_node_map: Vec<tsk_id_t> = vec![];
        if idmap {
            output_node_map.resize(self.nodes().num_rows() as usize, TSK_NULL);
        }
        let rv = unsafe {
            ll_bindings::tsk_table_collection_simplify(
                self.as_mut_ptr(),
                samples.as_ptr(),
                samples.len() as tsk_size_t,
                options.bits(),
                match idmap {
                    true => output_node_map.as_mut_ptr(),
                    false => std::ptr::null_mut(),
                },
            )
        };
        handle_tsk_return_value!(
            rv,
            match idmap {
                true => Some(output_node_map),
                false => None,
            }
        )