Currently `tables.sort()` does not always sort mutations into the required order

[hyanwong]

Taken from #3212 (comment)

Currently I can add and delete mutations so as to create a tree sequence in which compute_mutation_parents() fails, even after sorting (code below). Given the upcoming requirement for mutations to be sorted correctly to make a valid tree sequence, I think we need to fix tables.sort() to also sort mutations into a valid order? The tricky part is, I think, the order to use for mutations that occur on the same node at the same site. We can use time, but in the case of identical times (or if times are unknown) we can presumably use the existing mutation order?

import msprime
import tskit
import numpy as np

ts = msprime.sim_mutations(msprime.sim_ancestry(10, sequence_length=100, random_seed=1, recombination_rate=0.01), rate=1, random_seed=1)
print("Simulated", ts.num_mutations, "mutations")

# Add some random mutations, and delete some others
tables = ts.dump_tables()
tables.mutations.time = np.full_like(tables.mutations.time, tskit.UNKNOWN_TIME)
np.random.seed(10)
for s in ts.sites():
    tables.mutations.add_row(site=s.id, node=np.random.randint(ts.num_nodes), derived_state="A")
keep = np.ones(tables.mutations.num_rows, dtype=bool)
keep[0:100] = False
tables.mutations.replace_with(tables.mutations[keep])
# Zap all the parent IDs
tables.mutations.parent = np.full_like(tables.mutations.parent, tskit.NULL)
assert np.all(tables.mutations.parent == tskit.NULL)
tables.sort()
tables.build_index()
tables.compute_mutation_parents()
tables.tree_sequence()  # Fails

[benjeffery]

Great catch @hyanwong - I think your suggested sort order makes sense, would have to get my head back into the exact requirements. As you say we'd have to maintain the order of mutations where there are no distinguishing criteria.

This needs doing before we merge #3212

[petrelharp]

We can use time, but in the case of identical times (or if times are unknown) we can presumably use the existing mutation order?

I thought this is what we already did, in fact. I'm quite surprised this is failing.

[molpopgen]

I agree with @petrelharp -- this is very surprising to me.

[hyanwong]

It says somewhere in the docs "The TableCollection.sort() method ensures that mutations are sorted according site ID, but does not at present enforce that mutations occur after their parent mutations."

So perhaps it's not surprising, but once we fix this, we can remove that sentence.

The code I posted above would be a reasonable higher-level test case, I guess.

[petrelharp]

It says somewhere in the docs "The TableCollection.sort() method ensures that mutations are sorted according site ID, but does not at present enforce that mutations occur after their parent mutations."

Sure - but you have set all mutation parents to NULL, so that's not the issue? Hm, but maybe it is. My guess at what's happening: mutations at a site should (could?) be sorted by time to ensure parent order; however these mutations don't have a time; so the correct thing is to take their node's time, resolving ties by existing order. I have some memory of doing this, maybe in canonicalize.

[hyanwong]

Yes, I think that's probably what's happening here. They are not being sorted by time (or a proxy for it), and the node they are associated with enforces a time requirement which is not being met. This is only revealed when we try to calculate mutation parents.