Wednesday, March 16, 2011

Khayyam architecture: libthera

For a quick overview of all Khayyam subcomponents, look at the introduction.


Libthera is the backbone of Khayyam document system. It is very simple DOM-like tree of XML nodes, implementing file IO, transactions (think undo and redo) and property, tree and content mutation events.
The schematic layout of Thera object tree
All properties inside libthera tree are simple text strings. Thera nodes do not know anything about the semantics of attributes, content or child nodes. They only serve as the containers of base state for more semantic-aware objects in libmiletos.


The basic building block of Thera tree is Thera::Node - an object encapsulating XML node (either element, text or cdata). It has the following properties:
  • Name (only for element nodes) 
  • Backlink to containing document 
  • One or more attributes (key/value pairs, only for element nodes)
  • Optional text content
  • Linked list of children
  • Linked list of eventlisteners
The tree is modified by atomic methods of nodes - content change, attribute change, child insertion, child removal and child reordering. The API is kept as simple as possible - setting attribute to NULL deletes it, using NULL as ref value during child insertion prepends child and so on. The result is true if the action succeeds, false if not.

bool Node::setAttribute (const char *key, const char *value);
bool Node::setTextContent (const char *newcontent);
bool Node::addChild (Node *child, Node *ref);
bool Node::removeChild (Node *child);
bool Node::relocateChild (Node *child, Node *ref);

By default all methods above are allowed on all proper nodes (no attribute change or child management on text and cdata nodes). Actions can be vetoed by event listeners. The idea here is, that thera tree is not typed - all element nodes are similar and do not know anything about the semantic meaning of themselves or attributes. To implement semantic checks, another structure has to be added to thera tree, that can interpret the property changes and veto/allow these. In case of Khayyam, that additional layer is libmiletos scene graph library.

Event system 

For each property change (attribute or content change, child insertion and so on) node first invokes query events from linked EventVector list.
EventVector is list of function pointers, which - if not NULL - will be called during mutation events. I did not implement real signalling system for two reasons. First - to keep things simple. Second - normally single Thera::Node is tracked by single Miletos::Object and thus having all listeners in one structure makes perfect sense.

For example, if one tries to change the attribute of Thera::Node, the following happens:
  1. Old and new attribute are compared. True is returned immediately, if they are identical.
  2. change_attribute listeners are called by function pointers from all linked EventVectors. If any of these returns false, attribute is left intact and false returned.
  3. Actual attribute value of Thera::Node is set to new value
  4. attribute_changed listeners are called by function pointers from all linked EventVectors. This is post-mutation callback and thus cannot veto the change anymore.
  5. If no attribute_changed event was installed, downstream_attribute_changed listeners are called from parent node EventVector list.
  6. Containing Thera::Document is notified about attribute change
Normally the libmiletos scene graph objects (subclasses of Miletos::Object) listen to attribute_changed, content_changed, child_inserted and other post-mutation events and update their internal state whenever something changes. The exceptions are two special attributes id and xmlns. As each object in scene graph has to have unique id for reference system to work, the uniqueness of the value of id attribute is checked in change_attribute handler and mutation blocked if new value is not unique. All xmlns changes are blocked, as those change the semantics of object, and would require replacing one scene graph node with another one.

The reason for downstream listeners is to reduce the number of objects, that libmiletos has to implement. For example <color> nodes in Collada tree do not build their of objects (i.e. there is no Miletos::Collada::Color objects) but instead the containing nodes (ambient, diffuse, light nodes and so on) get signalled of color content changes by downstream propagation.


The untyped nature of thera tree makes it ideal place to handle generic editing functions, that have to be consistent for all scene graph nodes - undo, redo, cut, copy, paste, load and save. The invariant in Khayyam document system is, that the properties of Miletos::Object are determined only by the attributes and children of Thera::Node. So restoring the Thera::Node properties to previous value, also restores scene graph to previous state.
Thera::Node has very few properties, so to implement undo and redo, we have to only record 5 different types of mutation events (attribute change, content change, child insertion, child removal and child relocation). This is managed by Thera::Document container.

For each mutation event, a new record is appended in document undo list.
  • For attribute changes keep node location, key and old value
  • For content changes keep node location and old content
  • For child insertion keep the location of new node
  • For child deletion keep the copy of child node and it's previous location
  • For child relocation keep the old and new locations of child
Undo works by rolling back the record, and moving it from the top of undo list to the top of redo list.

Transaction logging can be turned on and off. Normally it has to be always on for editable document, but in certain cases - like during ensuring unique id attributes to all objects during document creation, it is turned off (id uniqueness is required feature, so this procedure cannot be undone).
In addition to transaction logging, there is transaction collation. If this is turned on, subsequent changes of the same attribute do not create new records, but only update the last record. It is used for tracking continuous numerical attribute changes - like the ones controlled by spinbutton or slider.

Similarly cut, copy and paste are implemented by storing the clone of copied node(s). During paste, the clone is re-cloned into document tree - and libmiletos objects will be built and updated automatically by event listeners.

Some concerns

While the untyped nature of thera tree makes editing functions simple and consistent throughout document, it has one drawback. As objects are often referenced by id values, and id has to be unique in document, copying reference pair does not work as intended. The id of new referee will be changed to some unique value, but the referencing attribute of referer will be not. So the referer will link back to the original object, instead of the new object.
I have some ideas, how to handle it - by keeping a dictionary of id overwrites during libmiletos object building phase, but at moment it has to be adjusted by hand.

Also, as libthera keeps all values as text, updating parsing these may take more time than is reasonable to spend during interactive editing. To dealt with this, many interactive functions work in two-stage way.
  • When input is grabbed (mouse button pressed), the initial state of object is recorded
  • During editing (normally dragging) libthera is skipped and editing function applied directly to scene graph nodes
  • When editing is finished, the last state is written to libthera
  • If editing is canceled, object state is read back from libthera (which has the initial value) 
Thus interactive functions do not constantly update text attributes, but instead the state of scene nodes directly. As an extra bonus the single editing action (click-drag-release) is recorded as single document transaction, because the libthera values are updated only during release.

That's all for now. Libthera can be donwloaded as part of khayyam source from SourceForge page. Or the latest version can be fetched from Sodipodi SVN:

Have fun!

No comments:

Post a Comment