Thread1: takes lock A, ..., tries to take lock B
Thread2: takes lock B, ..., tries to take lock A
Looks like you should be able to pass Mutex<A> and Mutex<B> to both threads otherwise what's the point of mutex if there's no way to share data protected by it, so it doesn't look like it prevents you from hitting this scenario.
In the trivial example you gave, one strategy just insists we take locks in alphabetical order. Thread 2 can't take lock A, because it already has lock B and that's not the correct order.
The common method for deadlock-free code is roughly that when a thread is required to wait on a lock owned by a second thread, it checks to see if the second thread is waiting on a lock already owned by the first thread. This requires that the lock graph essentially be a high-performance and concurrent global structure.
Locks like this can be expensive, particularly under high concurrency or contention, so they aren't used for most software. If you can fit your software in a simpler model e.g. where locks are singular or only acquired as a DAG, then much higher performance options are available that don't require deadlock detection.
I wonder if it is similar to the halting problem. Can deadlocks even be prevented in theory?
The mechanism is costly but elegant. If a lock you are trying to acquire is owned by another thread, you inspect the locks you own to determine if that thread is waiting on one of your locks. When a deadlock is detected, there are several strategies to automatically resolve it e.g. rolling back one of the threads to a point where forward progress can be safely serialized.
No one wants to use these mechanics for ordinary code, due to their cost. For the fashionable thread-per-core software architectures, deadlocks aren't something you commonly have to worry about.
In terms of shared-memory threading concurrency, Send and Sync, and the distinction between &T and &Mutex<T> and &mut T, were a revelation when I first learned them. It was a principled approach to shared-memory threading, with Send/Sync banning nearly all of the confusing and buggy entangled-state codebases I've seen and continue to see in C++ (much to my frustration and exasperation), and &Mutex<T> providing a cleaner alternative design (there's an excellent article on its design at http://cliffle.com/blog/rust-mutexes/).
My favorite simple concurrent data structure is https://docs.rs/triple_buffer/latest/triple_buffer/struct.Tr.... It beautifully demonstrates how you can achieve principled shared mutability, by defining two "handle" types (living on different threads), each carrying thread-local state (not TLS) and a pointer to shared memory, and only allowing each handle to access shared memory in a particular way. This statically prevents one thread from calling a method intended to run on another thread, or accessing fields local to another thread (since the methods and fields now live on the other handle). It also demonstrates the complexity of reasoning about lock-free algorithms (https://github.com/HadrienG2/triple-buffer/issues/14).
I find that writing C++ code the Rust way eliminates data races practically as effectively as writing Rust code upfront, but C++ makes the Rust way of thread-safe code extra work (no Mutex<T> unless you make one yourself, and you have to simulate &(T: Sync) yourself using T const* coupled with mutable atomic/mutex fields), whereas the happy path of threaded C++ (raw non-Arc pointers to shared mutable memory) leads to pervasive data races caused by missing or incorrect mutex locking or atomic synchronization.