One way to solve this at the language level would be to require that each lock has a specified priority associated with it, and have the compiler enforce a cons

One way to solve this at the language level would be to require that each lock has a specified priority associated with it, and have the compiler enforce a constraint that locks can only be obtained in the order of their priority. For each statement, the compiler could keep track of the current "lock priority". If an attempt is made to obtain a new lock with a lower or equal priority, the compiler would reject this. Otherwise, the compiler would use the priority of the new lock as the lock priority for all statements within the scope of the block in which that lock is held. Aside from modifying the language, the same basic idea could be implemented at the library level by exposing a lock type which still requires a priority to be specified at creation time, but tracks the current lock priority (per thread) at runtime and panics when the constraint is violated. Since the panics would be deterministic, they and the book-keeping required to track the current lock priority could be enabled only in debug mode.