Locking

In general, sequencing of operations can be enforced using typestate APIs. The broad idea is that the earlier operation returns a thing (which can be zero-size, i.e. nonexistent at runtime) which is consumed (or borrowed, depending on the desired semantics) by the next operation in the sequence. Technically, lock guards are an example of this pattern, since you cannot access the underlying data without going through the Mutex, and you cannot unlock the Mutex without dropping the guard. So it is impossible to access data without locking the Mutex.

The more difficult problem is preventing deadlock (which has never been an explicit goal of Rust's safety guarantees). Here's a simple way to at least prevent a lock from being recursively acquired:

* Invent a move-only wrapper (i.e. a type that is not Copy or Clone) for &Mutex. Each thread has this wrapper instead of the actual &Mutex, and the &Mutex is private so you can't directly get it out again.
* The wrapper has methods to lock the underlying Mutex as usual, but those methods borrow the wrapper mutably to ensure they cannot be called more than once.
* The wrapper is also !Send (otherwise, one thread could end up owning two of them and break the rules).

But this is unideal for at least two reasons:

1. The whole point of Mutexes is to allow shared access to mutable data. A move-only wrapper is just undoing all of that hard work. Yes, it's per-thread, but that's still painful.
2. It does not solve the broader lock hierarchy problem.

So I thought some more, and came up with a more elaborate idea, which works as follows:

* Each distinct lock in the lock hierarchy gets its own &Mutex wrapper (but those wrappers are Clone and Copy, so you can do all the same things you can do with &Mutex now). You can maybe use macros to make the wrappers less tedious to write.
* Each wrapper impls a generic trait that indicates its relationship with other locks in the hierarchy. For example, impl LockAfter<A> for B{} would mean "you may lock B after you have locked A."
* There's an empty struct (actually it has a PhantomData, but it's "empty" in the sense that it takes up zero bytes and gets constant-folded out of existence) which can only be constructed by these wrappers, or by some private initialization function that is callable from whatever "management" or runtime code is directly responsible for spawning threads. The struct has a generic type parameter which can either be one of the wrapper types, or it can be (). It also has a lifetime parameter, which it may not outlive (as constrained with PhantomData) To avoid having to write "the struct" over and over again, let's just say this struct is called LockHierarchy<'a, T>.
* LockHierarchy is not Clone. You have to pass it by value everywhere (but at runtime, it vanishes, so you can pass it around as much as you want without incurring any overhead).
* LockHierarchy is also !Send, so that no thread can ever own more than one.
* When a thread is created, the caller gives it a LockHierarchy<'static, ()> instance (created using the private initialization function). This construction must be done in the callee thread's startup code and not on the main thread, because it is !Send and can't be transferred, but this is not really much of a problem since the thread-spawning code can simply arrange for the thread to construct this object before it calls into the application code.
* Each wrapper takes a &'b mut LockHierarchy<'a, T> argument to lock(), and returns both a lock guard and a new LockHierarchy<'b, U> instance, where U is the type of the wrapper, T is trait-constrained to come before U in the lock hierarchy (or T = () is allowed unconditionally), 'b is the lifetime parameter of the lock guard, and 'a must outlive 'b. The latter constraint does not need to be spelled out, since it is implied by the validity of the type &'b mut LockHierarchy<'a, T>.
* At any given time, each thread should have exactly one LockHierarchy object (which is not borrowed mutably), that object is required in order to take any locks, and the type of the LockHierarchy object determines which locks you are still allowed to acquire. Each LockHierarchy's lifetime parameter stops it from outliving its associated lock guard.
* A thread can e.g. std::mem::forget() the LockHierarchy, or drop it, but oh well, that just means you can't lock anything. It doesn't cause unsafety or other problems, because LockHierarchy is just a trivial opaque object with no internal machinery.

I *think* this comprehensively prohibits any lock inversions from happening, statically, with zero overhead, provided that all mutexes in the system participate and your hierarchy really is acyclic. I also think you can probably use dyn as an "escape hatch" to check lock ordering at runtime instead of compile time, if it turns out that it's too hard to prove that some code is sound.

But I have not actually tried to implement this, so there might be some problem with it that I cannot see. For example, I'm not sure that Rust's trait solver is smart enough to materialize the whole DAG of an arbitrary lock hierarchy, so you might need to use macros for the hierarchy traits as well as the wrappers. Or you might tell everyone to manually write out the individual hierarchy traits they need, and check for cycles with some sort of linter or static analysis tool.