We define a pure shell history as an execution trace from a shell that only changes the shell's execution environment, that is, there are no external side-effects. In this article, we will reason about merging independent pure shell histories.
We can make a simplifying assumption that our shell executes commands on a readonly filesystem without any network connectivity. So for example, we could have the following script:
export DOWNLOAD_DIR=/home/bactrian/downloads
export PATH=/bin
exit () {
echo "Goodbye!"
}
trap exit EXIT
analyse $DOWNLOAD_DIR
The shell execution environment is state managed by the shell. It may be materialised concretely in the shell's runtime (e.g. a map of function names to function definitions) or managed by the kernel in the process state of the shell (e.g. open file descriptors).
Each pure shell command has a dynamic dependency cone. For simplicity, we will restrict this dependency cone to just the shell execution environment excluding resources like files or the network. When a command is run, we can evaluate that dependency cone using a custom eBPF program in addition to information provided by the shell (see Merry).
Only shell built-ins can modify the shell execution environment; therefore these operations are known by their constructor. For example, export FOO modifies the variable FOO to be marked as exported — in general it is not known statically what precise modifications are made due to, for example, word expansion or the dynamic lookup of functions. An executable cannot perform such a modification on the shell execution environment.
We can think of pure shell scripts in terms of a mergeable replicated data type.
Treating \tau as the shell execution environment and Op_{\tau } as pure shell commands we can reason about our shell using MRDTs.
There are some nice properties that fall out of algebraic properties of the operations that are allowed on your data type. For instance, commutative operations.