tree-diff.hpp File Reference

Go to the source code of this file.

Description

A token language to represent structural changes in a tree like hierarchical data structure.

In combination with the #DiffLanguage framework, this building block defines the set of operations to express both structural and content changes in a given data structure.

This »tree diff language« does not rely on any concrete data structure or layout, just on some general assumptions regarding the ordering and structure of the data.

• top level is a root record
• a record has a type, a collection of named attributes, and a collection of children
• all elements within a record are conceived as elements in ordered sequence, with the attributes first, followed by the children. The end of the attribute scope is marked by the the first emerging unnamed entry, i.e the first child.
• the individual elements in these sequences have a distinguishable identity and optionally a name (and a named element counts as attribute).
• moreover, the elements carry a typed payload data element, which possibly is a nested record ("nested child object"). In case of value elements, however, the element itself is identified with this value payload.
• the typing of the elements is outside the scope of the diff language; it is assumed that the receiver of the diff knows what types to expect and how to deal with them.
• there is a notion of changing or mutating the data content, while retaining the identity of the element. Of course this requires the data content to be assignable, which makes content mutation an optional feature.
• beyond that, like in list diff, elements might be changed through a sequence of deletion and insertion of a changed element with the same identity.
• since the tree like data structure is recursive, mutation of nested records is represented by "opening" the nested record, followed by a recursive diff. By implementing the #TreeDiffInterpreter interface (visitor), a concrete usage can receive a diff description and possibly apply it to suitable target data.

  Remarks

  the standard usage is to create a DiffApplicator(target) and fed a diff sequence to it. We provide a standard implementation of the DiffApplicator + DiffApplicationStrategy, based on a custimisable intermediary, the TreeMutator. This allows to apply a given tree to any suitably compatible target data structure; notably there is a preconfigured setup for our _"generic tree representation"_, diff::Record<GenNode>.

  See also

  diff-language.cpp

  tree-diff-application.cpp

  DiffTreeApplication_test

  list-diff.cpp

  diff::GenNode

Definition in file tree-diff.hpp.

#include "lib/diff/diff-language.hpp"
#include "lib/diff/list-diff.hpp"
#include "lib/diff/gen-node.hpp"

Classes
class	TreeDiffInterpreter
	Interpreter interface to define the operations ("verbs"), which describe differences or changes in hierarchical data structure. More...
struct	TreeDiffLanguage

Namespaces
	lib
	Implementation namespace for support and library code.