Description

Concrete implementation to apply structural changes to hierarchical data structures.

Together with the generic #DiffApplicator, this allows to receive linearised structural diff descriptions and apply them to a given target data structure, to effect the corresponding changes.

Design considerations

While – conceptually – our tree diff handling can be seen as an extension and generalisation of list diffing, the decision was not to embody this extension into the implementation technically, for sake of clarity. This would be implementation re-use, as opposed to building a new viable abstraction. No one outside the implementation realm would benefit from such an abstraction, so we prefer to understand the tree diff language as the abstraction, which needs to embodied into two distinct contexts of implementation. So the list diff application strategy can be seen as blueprint and demonstration of principles.

Use cases

Initially, we'd have to distinguish two usage situations

apply a diff to a generic tree representation, based on Record<GenNode>
apply a diff to some tree shaped implementation data structure. Conceptually we use the former as blueprint and base to define the semantics of our »tree-diff language«, while the latter is an extension and can be supported within the limits of precisely these tree-diff semantics. That is, we support diff application to all implementation data structures which are conceptually congruent to the generic tree representation. This extension happens in accordance to the goals of our "diff framework", since we want to allow collaboration between loosely coupled subsystems, without the need of a shared data structure.

Implementation

On the implementation level though, relations are the other way round: the framework and technique to enable applying a diff onto private implementation data is used also to apply the diff onto the (likewise private) implementation of our generic tree representation. Because the common goal is loose coupling, we strive at imposing as few requirements or limitations onto the implementation as possible.

Rather we require the implementation to provide a binding, which can then be used to execute the changes as dictated by the incoming diff. But since this binding has to consider intricate details of the diff language's semantics and implementation, we provide a Builder DSL, so the client may assemble the concrete binding from preconfigured building blocks for the most common cases

binding "attributes" to object fields
binding "children" to a STL collection of values
binding especially to a collection of GenNode elements, which basically covers also the generic tree representation.

State and nested scopes

For performance reasons, the diff is applied in place, directly mutating the target data structure. This makes the diff application statefull – and in case of a diff conflict, the target will be corrupted.

Our tree like data structures are conceived as a system of nested scopes. Within each scope, we have a list of elements, to which a list-diff is applied. When commencing diff application, a one time adapter and intermediary is constructed: the TreeMutator. This requires the help of the target data structure to set up the necessary bindings, since the diff applicator as such has no knowledge about the target data implementation. At this point, the existing (old) contents of the initial scope are moved away into an internal source sequence buffer, from where they may be "picked" and moved back into place step by step through the diff. After possibly establishing a new order, inserting or omitting content within a given "object" (Record), the tree diff language allows in a second step to open some of the child "objects" by entering nested scopes, to effect further changes within the selected child node. This is done within the mut(ID)....emu(ID) bracketing construct of the diff language. On the implementation side, this recursive descent and diff application is implemented with the help of a stack, where a new TreeMutator is constructed whenever we enter (push) a new nested scope.

Yet another indirection

Unfortunately this leads to yet another indirection layer: Implementing a language in itself is necessarily a double dispatch (we have to abstract the verbs and we have to abstract the implementation side). And now we're decoupling the implementation side from a concrete data structure. Which means, that the user will have to provide a set of closures (which might even partially be generated functors) to translate the implementation actions underlying the language into concrete actions working on local data.

Generic and variable parts

So there is a link between generic »tree diff language« interpretation and the concrete yet undisclosed private data structure, and most of this implementation is entirely generic, since the specifics are abstracted away behind the TreeMutator interface. For this reason, most of this delegating implementation can be emitted right here, within the library module. With the sole exception of the ctor, which needs to figure out a way how to "get" a suitable TreeMutator implementation for the given concrete target data.

the TreeMutator DSL

In the end, for each target structure, a concrete TreeMutator needs to be built or provided within the realm of the actual data implementation, so the knowledge about the actual data layout remains confined there. While this requires some understanding regarding structure and semantics of the diff language, most data implementation will rely on some very common representation techniques, like using object fields as "attributes" and a STL collection to hold the "children". Based on this insight, we provide a DSL with standard adapters and building blocks, to ease the task of generating ("binding") the actual TreeMutator. The usage site needs to supply only some functors or lambda expressions to specify how to deal with the actual representation data values:

how to construct a new entity
decide when the binding actually becomes active
how to determine a diff verb "matches" the actual data
how to set a value or how to recurse into a sub scope

See also: DiffTreeApplication_test; DiffComplexApplication_test; DiffListApplication_test; GenNode_test; tree-diff.hpp

Definition in file tree-diff-application.hpp.

#include "lib/diff/tree-diff.hpp"
#include "lib/diff/tree-mutator.hpp"
#include "lib/diff/diff-mutable.hpp"
#include "lib/diff/tree-diff-traits.hpp"
#include "lib/diff/gen-node.hpp"
#include "lib/format-string.hpp"
#include "lib/util.hpp"
#include <utility>
#include <stack>

Classes
class	DiffApplicationStrategy< TAR, enable_if< TreeDiffTraits< TAR > > >
	Interpreter for the tree-diff-language to work on arbitrary opaque target data structures. More...

class	ScopeManager
	Management interface to deal with storage for TreeMutators dedicated to nested scopes. More...

class	StackScopeManager< buffSiz >
	Typical standard implementation of the ScopeManager. More...

class	TreeDiffMutatorBinding
	Implementation of the tree-diff-language to work on arbitrary tree-like data. More...

Namespaces
	lib
	Implementation namespace for support and library code.