Repo API: Change-based event notifications

[enikao]

Aka delta protocol

Use cases

• Editor sends fine-grained updates to repo
• Editor receives fine-grained updates from repo
  • Might want to inform user about "foreign" changes (e.g. highlight)
• Trigger processor recalculation (e.g. typesystem, checker)
• Trigger processor recalculation + update (e.g. bi-directional link processor: a processor that simulates bi-directional links by automatically updating two inverse "regular" references)

Scenarios:

• Dumb repo: No delta support at all
• Unsynchronized repo: Whatever written last wins, conflicts blow up
  • Useful for single-user, or in combination with pessimistic locking
• Conflict-detecting repo (optimistic locking): Repo detects conflicting writes, but doesn't resolve them on its own. Might give client additional info to decide.
• Conflict-avoiding repo: Automatically resolves conflicts
  • Refuses conflicting change
  • OT-based
  • CRDT-based

Requirements / wishes

• Independent of concrete conflict resolution approach
  • BUT: according to Sascha, only works if every client uses the same OT library

Aspects

• Connected to locking
• Connected to versioning
• Connected to live collaboration
• Do clients send the same messages as the repo?
• Do clients update their own model, or send update request to server and only recieve update?

Additional info

• draft-toomim-httpbis-braid-http-02 describes a generic protocol with similar properties

Delta messages in different systems

Comparison

	MPS			EMF	Modelix			LIonCore-MPS	Automerge	Tree CRDT 1	Tree CRDT 2
Operation	OpenAPI	SModel	VCS diff		server API	model operations	model area
set reference	SReferenceChangeEvent	SModelReferenceEvent	SetReferenceChange		SetReferenceOpData	SetReferenceOp	ReferenceChangeEvent	ChangeLinkDelta	PutMap		rename
set property	SPropertyChangeEvent	SModelPropertyEvent	SetPropertyChange	SET	SetPropertyOpData	SetPropertyOp	PropertyChangeEvent	ChangePropertyDelta	PutMap		rename
move node			NodeGroupMoveChange	MOVE	MoveNodeOpData	MoveNodeOp	ChildrenChangeEvent	MoveModelDelta		move	move
			NodeGroupNotMoveChange					MoveParentDelta
wrap node			NodeGroupWrapChange
add node	SNodeAddEvent	SModelChildEvent		ADD	AddNewChildNodeOpData	AddNewChildOp		AddDelta	Insert	add	add
remove node	SNodeRemoveEvent			REMOVE	DeleteNodeOpData	DeleteNodeOp		RemoveDelta	DeleteList	remove	remove
add subtree				ADD_MANY		AddNewChildSubtreeOp
add partition		SModelRootEvent	AddRootChange
remove partition			DeleteRootChange
change concept			SetConceptChange					ChangeConceptDelta
change id			NodeIdChange
dependencies		SModelImportEvent	ImportedModelChange
		SModelDevKitEvent	ModuleDependencyChange
		SModelLanguageEvent	UsedLanguageChange
			EngagedLanguageChange
create node				CREATE
unset property				UNSET
remove subtree				REMOVE_MANY
resolve reference				RESOLVE
no-op						NoOp
revert						RevertToOp
undo						UndoOp
replace		SModelReplacedEvent
change persistence		SModelFileChangedEvent
change metainfo		SModelRenamedEvent	ModelAttributeChange
change metastructure	SModuleAddedEvent
	SModuleChangedEvent
	SModuleRemovedEvent
	SModuleRemovingEvent

MPS

OpenAPI

• SModuleAddedEvent(@NotNull SModule module)
• SModuleChangedEvent(@NotNull SModule module)
• SModuleRemovedEvent(@NotNull SModuleReference mRef, SRepository repository)
• SModuleRemovingEvent(@NotNull SModule module)
• SReferenceReadEvent(@NotNull SNode node, @NotNull SReferenceLink link)
• SPropertyReadEvent(@NotNull SNode node, @NotNull SProperty property)
• SNodeReadEvent(@NotNull SNode node)
• SReferenceChangeEvent(@NotNull SModel model, @NotNull SNode node, @NotNull SReferenceLink link, SReference oldValue, SReference newValue)
• SNodeAddEvent(@NotNull SModel model, @NotNull SNode parent, @NotNull SNode child, @NotNull SContainmentLink link)
• SNodeRemoveEvent(@NotNull SModel model, @NotNull SNode parent, @NotNull SNode child, @NotNull SContainmentLink link)
• SPropertyChangeEvent(@NotNull SModel model, @NotNull SNode node, @NotNull SProperty property, String oldValue, String newValue)

SModel

• SModelDevKitEvent(SModel model, SModuleReference devKit, boolean added)
• SModelChildEvent(SModel model, boolean added, SNode parent, SContainmentLink role, int childIndex, SNode child)
• SModelReplacedEvent(SModel model)
• SModelFileChangedEvent(SModel model, IFile oldFile, IFile newFile)
• SModelRootEvent(SModel model, SNode root, boolean added)
• SModelLanguageEvent(@NotNull SModel model, @NotNull SLanguage ref, boolean added)
• SModelPropertyEvent(SModel model, SProperty property, SNode node, String oldPropertyValue, String newPropertyValue)
• SModelRenamedEvent(SModel model, String oldName, String newName)
• SModelImportEvent(SModel model, SModelReference modelReference, boolean added)
• SModelReferenceEvent(SModel model, @NotNull SReference reference, boolean added)

VCS diff

• EngagedLanguageChange(ChangeSet cs, boolean delete, SLanguage lang)
• ImportedModelChange(@NotNull() ChangeSet changeSet, @NotNull() SModelReference modelReference, boolean delete)
• ModuleDependencyChange(@NotNull() ChangeSet changeSet, @NotNull() SModuleReference moduleReference, @NotNull() DependencyType type, boolean delete)
• ModelAttributeChange(@NotNull() ChangeSet changeSet, @NotNull() String key, String newValue)
• UsedLanguageChange(@NotNull() ChangeSet changeSet, @NotNull() SLanguage language, int version, ChangeType changeType)
  • ChangeType:
    • ADD()
    • DELETE()
    • CHANGE()
    • CONFLICTED()
    • MOVE()
• AddRootChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId nodeId)
• DeleteRootChange(ChangeSet changeSet, SNodeId nodeId)
• NodeGroupMoveChange(ChangeSet changeSet, ModifiedNodesGroup oldGroup, ModifiedNodesGroup newGroup, SContainmentLink oldLink, SContainmentLink newLink)
• NodeGroupNotMoveChange(ChangeSet changeSet, ModifiedNodesGroup oldGroup, ModifiedNodesGroup newGroup)
• NodeGroupWrapChange(@NotNull() ChangeSet changeSet, ModifiedNodesGroup oldGroup, ModifiedNodesGroup newMovedGroup, ModifiedNodesGroup newInsertedGroup, boolean isWrap)
• SetConceptChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId nodeId, SConcept newValue)
• SetPropertyChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId nodeId, SNodeId oppositeNodeId, SProperty property, string newValue)
• SetPropertyStructChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId oldNodeId, @NotNull() SNodeId newNodeId, SProperty property, string newValue)
• SetReferenceChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId sourceNodeId, SNodeId oppositeNodeId, @NotNull() SReferenceLink role, @Nullable() SModelReference targetModelReference, @Nullable() SNodeId targetNodeId, @Nullable() string resolveInfo, boolean resolveInfoOnly)
• SetReferenceStructChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId sourceNodeId, SNodeId newSourceNodeId, @NotNull() SReferenceLink role, @Nullable() SModelReference targetModelReference, @Nullable() SNodeId targetNodeId, @Nullable() string resolveInfo)
• NodeGroupChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId oldParentNodeId, @NotNull() SNodeId newParentNodeId, @NotNull() SContainmentLink role, int begin, int end, int resultBegin, int resultEnd)
• NodeGroupStructChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId parentNodeId, @NotNull() SNodeId newParentNodeId, @NotNull() SContainmentLink role, int begin, int end, int resultBegin, int resultEnd)
• NodeIdChange(@NotNull() ChangeSet changeSet, @NotNull() SNodeId oldParentNodeId, @NotNull() SNodeId newParentNodeId, @NotNull() SContainmentLink role, @NotNull() SNodeId oldNodeId, @NotNull() SNodeId newNodeId)

EMF

• CREATE @Deprecated indicating that the notifier has been created.
• SET indicating that a feature of the notifier has been set. This applies for simple features.
• UNSET indicating that a feature of the notifier has been unset. This applies for unsettable features.
• ADD indicating that a value has been inserted into a list-based feature of the notifier.
• REMOVE indicating that a value has been removed from a list-based feature of the notifier.
• ADD_MANY indicating that a several values have been added into a list-based feature of the notifier.
• REMOVE_MANY indicating that a several values have been removed from a list-based feature of the notifier.
• MOVE indicating that a value has been moved within a list-based feature of the notifier.
• REMOVING_ADAPTER indicating that an adapter is being removed from the notifier.
• RESOLVE indicating that a feature of the notifier has been resolved from a proxy.

Modelix

server API

• SetPropertyOpData(val node: NodeId, val role: String, val value: String?)
• SetReferenceOpData(val node: NodeId, val role: String, val target: NodeId?)
• AddNewChildNodeOpData(val parentNode: NodeId, val role: String?, val index: Int = -1, val concept: String?, val childId: NodeId)
• MoveNodeOpData(val newParentNode: NodeId, val newRole: String?, val newIndex: Int = -1, val childId: NodeId)
• DeleteNodeOpData(val nodeId: NodeId)

model operations

• AddNewChildOp(val position: PositionInRole, val childId: Long, val concept: IConceptReference?)
• AddNewChildSubtreeOp(val resultTreeHash: KVEntryReference<CPTree>, val position: PositionInRole, val childId: Long, val concept: IConceptReference?)
• DeleteNodeOp(val childId: Long)
• MoveNodeOp(val childId: Long, val targetPosition: PositionInRole)
• NoOp
• RevertToOp(val latestKnownVersionRef: KVEntryReference<CPVersion>, val versionToRevertToRef: KVEntryReference<CPVersion>)
• SetPropertyOp(val nodeId: Long, val role: String, val value: String?)
• SetReferenceOp(val sourceId: Long, val role: String, val target: INodeReference?)
• UndoOp(val versionHash: KVEntryReference<CPVersion>)

model area

• ChildrenChangeEvent(val node: INode, val role: String)
• PropertyChangeEvent(val node: INode, val role: String)
• ReferenceChangeEvent(val node: INode, val role: String)

LIonCore-MPS

• RenameLanguageDelta(@NotNull() SLanguage changedLanguage, @NotNull() string oldName, @NotNull() string newName)
• AddDelta(@NotNull() SNode newNode, @Nullable() SNode parent, @Nullable() SContainmentLink changedLink)
• RemoveDelta(@NotNull() node<> removedNode, @Nullable() node<> parent, @Nullable() SContainmentLink changedLink)
• ChangeConceptDelta(@NotNull() SNode changedNode, @NotNull() SAbstractConcept oldConcept, @NotNull() SAbstractConcept newConcept)
• ChangeLinkDelta(@NotNull() SNode changedNode, @NotNull() SAbstractLink changedLink, @Nullable() SNode oldValue, @Nullable() SNode newValue)
• ChangePropertyDelta(@NotNull() SNode changedNode, @NotNull() SProperty changedProperty, @Nullable() string oldValue, @Nullable() string newValue)
• MoveModelDelta(@NotNull() SNode changedNode, @NotNull() SModel oldModel, @Nullable() SNode oldParent, @NotNull() SModel newModel)
• MoveParentDelta(@NotNull() SNode changedNode, @NotNull() SNode oldParent, @NotNull() SNode newParent)

Automerge

• PutMap(String key, AmValue value, boolean conflict) A property was set in a map
• PutList(long index, AmValue value, boolean conflict) A property was set in a list
• Insert(long index, AmValue[] values, boolean conflict) A valule was inserted into a list
• SpliceText(long index, java.lang.String text) Values were spliced into a text object
• Increment(Prop property, long value) A counter was incremented
• DeleteMap(String key) A key was deleted from a map
• DeleteList(long index, long length) One or more values were deleted from a list
• Mark(org.automerge.Mark[] marks) One or more marks were created in a text object

Tree CRDT paper 1

• add(node, newParent)
• remove(node)
• move(node, newParent)

Tree CRDT paper 2

• move(newParent, metadata, node)
• delete == move(trashNode, metadata, node)
• add = move(newParent, metadata, newNode)
• rename = move(sameParent, metadata with new name, sameNode)

[enikao]

Main open questions:

• Which messages do we support?
  For example, is move a child from position 2 to position 5 in the same list the same as move a child from parent A to parent B the same message kind?

• Is the protocol the same for client -> repository updates vs. repository -> client updates?
  That's especially relevant for (web-based) editors.

• How strong do we couple the protocol to an implementation?
  Both operational transformation and CRDTs can be used to implement consistent clients.
  For both of them, several implementations are available.
  Additionally, we might support simpler clients that assume no conflicts or missing updates at all.

• Can we find a sensible common denominator to both implementation (OT, CRDT)?

[dslmeinte]

W.r.t. the first two questions:

• The more finegrained(ly-typed) the messages are, the better, IMHO.
• Keeping the protocol symmetric is practical (not doubling the effort), and conceptually cleaner and simpler.