Valter's work addressing basho/riak_dt#99

[russelldb]

I've opened this pull request to keep track of comments/feedback as I work through the code.

[balegas]

The current version of the map clears deferred operations when an entry is removed (and no dot survives), allowing some dots that should be deleted by a deferred operation to remain in the state:

• OpA removed "b -> 1" in replica A with the context of B;
• A's context does not descend from B, deferring OpA;
• OpA1 removes entry b, clears the entry and the deferred op in replica A;
• A and B merge, "b -> 1" is added back to A and not cleared by OpA as intended because the deferred operation was cleared by OpA1

In a nutshell, i've changed the Map data-type to avoid losing these deferred operations. I added some form of tombstone in the state that tells that an entry is removed, but keeps the value while it has deferred operations that are not covered by the object's clock. Changes were made in the remove operation to fill this tombstone when an entry with deferred operations is deleted. Merge() was modified to clear tombstones Value() was changed to hide elements that are removed but the tombstone is not covered by the map clock yet.

The remove operation now calls a propagate_remove() function that recursively checks if any child of the current map entry has any deferred operations. All deferred operations are merged into the object clock and propagated to the root element that was deleted, filling the tombstone of the map entries on the way. While an element has a tombstone, the entry and its subtree are kept (immediately remove dots that are covered by the clock). When the merge occurs and the deferred operations arrive, clear_tombstones() checks what entries can be deleted: if any child received a new dot, that entry is kept; If no new dot was added the entry can be deleted (also checks empty entry) --- the tombstone is only erased when covered by the map clock. To read the object, similar rules are applied: if an entry has a tombstone, check if any child has dots that are not covered by the tombstone to show/hide the entry.

Since the amount of meta-data in the object state was growing, i decided to separate the meta-data from the actual value so a map entry is now {{Dots, Seen, Tombstone},CRDT}.