Introduce an atomic mutation command

[xiaq]

There are two motivations for such a command:

• Make it possible to mutate a variable without race condition (#888).

• Introduce a shorthand for mutating $x[deeply][nested][element] (#242).

The design is to introduce a mutate special command that takes a variable reference and a mutation callback. Examples:

# assuming $a contains a number
mutate a [x]{ + $x 1 }
# assuming x[deeply][nested][element] exists
mutate x[deeply][nested][element] [v]{ + $v 1 }

The mutate command works by holding the mutex of the mutated variable during its execution. This has a notable consequence: access to the variable being mutated in the mutation callback will deadlock. A full-fledged STM system can fix this, but more lightweight solutions may also be possible.

[krader1961]

While this is useful in its own right it doesn't address other situations that require serializing an operation. I recently debugged two bugs in @zzamboni's prompt chain module due to the left and right prompts being run in parallel. Neither bug could be fixed by using the proposed mutate command. Both need a critical-section mutex (at least not without a major rewrite of the module).

[xiaq]

Yes, this is not a replacement for general-purpose synchronization primitives.

[krader1961]

Given that this is now targeted for the 0.16.0 release I feel compelled to point out that more discussion is warranted. For example, why not provide a way to annotate that using and assigning to a var in the same statement should be guarded by a mutex? Something like var &mutex x perhaps. Then I can write x = (+ 1 $x) without having to use the cumbersome mutate command.

I'm also extremely worried by the map var example. How would the mutate command allow me to atomically add an entry to a map if it doesn't exist and atomically mutate the entry if it does exist?

[xiaq]

Given that this is now targeted for the 0.16.0 release I feel compelled to point out that more discussion is warranted.

I used the milestone a prioritization signal on what to look at next; it doesn't mean that the issue is ready to be implemented.

For example, why not provide a way to annotate that using and assigning to a var in the same statement should be guarded by a mutex? Something like var &mutex x perhaps. Then I can write x = (+ 1 $x) without having to use the cumbersome mutate command.

Variables in Elvish are already guarded by mutexes, with each single read or write operation being a critical section.

The problem is knowing when to replace the individual small critical sections with a large one that includes multiple read or write operations. It's easy in simple cases like set x = (+ 1 $x): $x appears statically on the right hand side, so you know that the entire command should be a single critical section on $x's mutex.

But if the right-hand-side contains anything more complex (say a function call, like set x = (f)) in general it's not possible to know whether f will access $x beforehand. To be safe, you'd have to guard the entire assignment with $x's mutex, even if f turns out to not access $x. In fact, essentially every assignment, except the simplest ones, will have to hold the mutex for all the left-hand variables while the right-hand side is being evaluated, blocking all concurrent accesses to these variables. This is a major limitation on concurrency; I haven't explored the full implications, but it feels like a dead end at this point.

FWIW, the mutate command is supposed to be a low-level building block. Elvish variables are atoms and this is a pretty natural operation on atoms (this page on Clojure's atoms is relevant; mutate is Clojure's swap!). Having this command does not inhibit high-level, easier-to-use constructs from being built.

I'm also extremely worried by the map var example. How would the mutate command allow me to atomically add an entry to a map if it doesn't exist and atomically mutate the entry if it does exist?

Assuming $m contains a map

mutate m [x]{ assoc $x key value }

Or if you prefer the assignment syntax sugar,

mutate m [x]{ x[key] = value; put $x }