Lumiera  0.pre.03
diff-language.hpp File Reference

Go to the source code of this file.


Fundamental definitions for a representation of changes.

We describe differences in data structures or changes to be applied in the form of a "linearised diff language". Such a diff can be represented as a sequence of tokens of constant size. Using a linearised constant size representation allows to process diff generation and diff application in a pipeline, enabling maximum decoupling of sender and receiver. Changes sent as diff message serve as a generic meta-representation to keep separate and different representations of the same logical structure in sync. Such an architecture allows for tight cooperation between strictly separated components, without the need of a fixed, predefined and shared data structure.

Basic Assumptions

While the linearisation folds knowledge about the underlying data structure down into the actual diff, we deliberately assume that the data to be diffed is structured data. Moreover, we'll assume implicitly that this data is typed, and we'll assume explicitly that the atomic elements in the data structure have a well-defined identity and can be compared with the == operator. We treat those elements as values, which can be copied and moved cheaply. We include a copy of all content elements right within the tokens of the diff language, either to send the actual content data this way, or to serve as redundancy to verify proper application of the changes at the diff receiver downstream.

Solution Pattern

The representation of this linearised diff language relies on a specialised form of the visitor pattern: We assume the vocabulary of the diff language to be relatively fixed, while the actual effect when consuming the stream of diff tokens is provided as a private detail of the receiver, implemented as a concrete "Interpreter" (visitor) of the specific diff language flavour in use. Thus, our implementation relies on double-dispatch, based both on the type of the individual diff tokens and on the concrete implementation of the Interpreter. Typical usage will employ a DiffApplicator, so the "interpretation" of the language means to apply it to a target data structure in this standard case.

Due to the nature of double-dispatch, the interpretation of each token requires two indirections. The first indirection forwards to a handler function corresponding to the token, while the second indirection uses the VTable of the concrete Interpreter to pick the actual implementation of this handler function for this specific case. Basically the individual token ("verb") in the language is characterised by the handler function it corresponds to (thus the meaning of a verb, an operation). To support diagnostics, each token also bears a string id. And in addition, each token carries a single data content element as argument. The idea is, that the "verbs", the handler functions and the symbolic IDs are named alike (use the macro DiffStep_CTOR to define the tokens in accordance to that rule). Such a combination of verb and data argument is called a DiffStep, since it represents a single step in the process of describing changes or transforming a data structure. For example, a list diff language can be built using the following four verbs:

  • pick-next
  • insert-new
  • delete-next
  • find reordered element
See also

Definition in file diff-language.hpp.

#include "lib/error.hpp"
#include "lib/nocopy.hpp"
#include "lib/verb-token.hpp"
#include "lib/util.hpp"
#include <tuple>


class  DiffApplicationStrategy< TAR, SEL >
 Extension point: define how a specific diff language can be applied to elements in a concrete container. More...
class  DiffApplicator< TAR >
 generic builder to apply a diff description to a given target data structure. More...
struct  DiffLanguage< I, E >
 Definition frame for a language to describe differences in data structures. More...
struct  DiffLanguage< I, E >::DiffStep
struct  DiffStepBuilder< I >
 generator to produce specific language tokens More...
struct  InterpreterScheme< I >
 < base case is to expect typedef I::Val More...
struct  InterpreterScheme< HandlerFun< I, E > >
 < alternatively derive value and interpreter from a Handler binding More...
struct  InterpreterScheme< IP< E > >
 < alternatively, the interpreter value type can be templated More...


template<class I , typename E >
using HandlerFun = void(I::*)(E const &)


#define DiffStep_CTOR(_ID_)
 shortcut to define tokens of the diff language. More...


template<class H >
DiffStepBuilder< typename InterpreterScheme< H >::Interpreter > diffTokenBuilder (H handlerFun, Literal id)
 set up a diff language token generator, based on the specific handler function given. More...
 Invalid diff structure: implicit rules and assumptions violated. More...
 Collision in diff application: contents of target not as expected. More...


 Implementation namespace for support and library code.

Macro Definition Documentation

◆ DiffStep_CTOR

#define DiffStep_CTOR (   _ID_)

shortcut to define tokens of the diff language.

Use it to define namespace or class level function objects, which, when supplied with an argument value of type E, will generate a specific language token wrapping a copy of this element.

See also
ListDiffLanguage usage example
need a typedef Interpreter at usage site to refer to the actual language interpreter interface; the template parameters of the Language and the element type will be picked up from the given member function pointer.

Definition at line 241 of file diff-language.hpp.

Class Documentation

◆ lib::diff::DiffApplicationStrategy

class lib::diff::DiffApplicationStrategy
+ Inheritance diagram for DiffApplicationStrategy< TAR, SEL >:
+ Collaboration diagram for DiffApplicationStrategy< TAR, SEL >:

◆ lib::diff::InterpreterScheme

struct lib::diff::InterpreterScheme
Class Members
typedef I Interpreter
typedef typename Val Val
typedef HandlerFun< I, Val > Handler
+ Collaboration diagram for InterpreterScheme< I >:

◆ lib::diff::InterpreterScheme< HandlerFun< I, E > >

struct lib::diff::InterpreterScheme< HandlerFun< I, E > >
Class Members
typedef E Val
typedef I Interpreter
typedef HandlerFun< I, E > Handler
+ Collaboration diagram for InterpreterScheme< HandlerFun< I, E > >:

◆ lib::diff::InterpreterScheme< IP< E > >

struct lib::diff::InterpreterScheme< IP< E > >
Class Members
typedef E Val
typedef IP< E > Interpreter
typedef HandlerFun
< Interpreter, Val >
+ Collaboration diagram for InterpreterScheme< IP< E > >: