Skip to content

List of Operational Transforms

Jump to bottom
Graham Wakefield edited this page Jun 4, 2020 · 5 revisions

This was copied directly from the old cards repo wiki page. Note that it might be out of date relative to our current OT spec.

Minimal set of deltas / inverted deltas:

  • [] a list of operations defines a sequence / inverse is reverse order and invert each item
  • newnode (path, properties) / delnode (path, properties)
  • connect (paths) / disconnect (paths)
  • repath { oldpath, newpath }
  • propchange (path, from, to)
  • REMOVED: movenode (transformation of position, orientation, scale?) / movenode (inverse transformation) (same as propchange)

System deltas:

  • REMOVED (repath does this job): uniquify used names consistently (e.g. when pasting a copy of a scene)
  • snapshot { copy of current graph, previous history ref? } -- this is keyframing. but maybe it should not be part of the delta stream.

More edit deltas to implement later:

  • obj: attr change / change back [runtime vs. static attrs?]
  • REMOVED -- propchange does this. add to numeric value attr (e.g. knob twiddle)
  • expose-outside-patcher (attr?) / hide
  • new abstraction-fundef [from card?] / del abstraction
  • group [group? group+comment?] / deencapsulate-ungroup
  • collapse-squish (turn group into single obj) / unsquish
  • enable connection / disable
  • enable obj (like comment out) / disable
  • replace (tries to maintain connections)?
  • import library / remove library
  • annotate-link
  • connection attr change

Personal history data

  • user pose
  • selection
  • is copy/paste an OT? (does rebasing a copy change the copy?)
  • database of copies
  • thinking-process-edits, e.g. browsing library

For every new operation added to the list, it needs to supply:

  • how to apply the operation to a graph
  • how to invert the operation
  • how to rebase the operation with respect all existing operations

References:

Schema of a graph:

  • tree of nodes
    • each node is a set of child nodes, plus a set of properties
  • set of arcs
    • each arc is a pair of [from-path, to-path]
graph = {
  nodes: {
    a: { 
      _props: { pos:[10,10], kind:"noise", }, 
      signal: { _kind:"outlet", _props:{} } 
    },
    b: { 
      _props: { pos:[10,50], kind:"dac", }, 
      source: { _kind:"inlet", _props:{} } 
    },
    child: {
      _props: { pos: [10, 10], kind: "group", /*arcs: [],*/ },
      a: { 
        _props: { pos:[10,10], kind:"noise" },
        signal: { _kind:"outlet", _props:{} } 
      },
    },
  },
  arcs: [  
    ["a.signal", "b.source" ],
    ["child.a.signal", "b.source" ],
  ]
  ...
}

child.a.signal -> (unchanged)
loop over child.nodes has to avoid "_props"
is child.a.signal an outlet? check child.a.signal._props.kind == "outlet"

Can translate from/to the above and below:

// list of delta (edit) operations (in order) to create a graph
// each delta is potentially rebase-able (mainly in terms of path changes)
deltas = [
  [
    { op:"newnode", path:"a", kind:"noise", pos:[10,10] }, 
    { op:"newnode", path:"a.signal", kind:"outlet" }, 
  ],
  [
    { op:"newnode", path:"b", kind:"dac", pos:[10,50] },
    { op:"newnode", path:"b.source", kind:"inlet" }, 
  ],
  { op:"connect", paths: ["a.signal", "b.source"] },
  { op:"newnode", path:"child", kind:"group", pos:[50,50] },
  [
    { op:"newnode", path:"child.a", kind:"beep", pos:[10,10] },
    { op:"newnode", path:"child.a.signal", kind:"outlet" }
  ], 
  { op:"connect", paths: ["child.a.signal", "b"] }
];

Notes:

  • Rebasing by path, rather than character position, so that graph structure changes can be captured.
  • Every op should be invertible (this means, del needs an argument for what is being deleted)
  • When two people make simultaneous edits, these need to be merged; one must be rebased against the other first to make it compatible for merge -- i.e. to resolve conflicts automatically as much as possible
  • may want to add hash or some kind of unique id to each delta?
  • may want to add last-edit timecode to each object?

Conflicts that the system should never allow to happen:

  • use of a path that doesn't exist (except for creating new objects)
  • similar: leaving a path reference dangling (leaving a ref after deleting what is referenced)
  • duplicate path (new object with existing name (not a replace))
  • newconnect to path that doesn't exist

Conflicts that the system should properly resolve:

  • a repath in one would need to repath the other delta to match before merging

  • if we both add objects with the same path, one will need to be repathed

  • a del-node in one might need to del-arc in the other

  • both import same lib (just keep one)

  • remove lib might invalidate use of ops in another

  • redefine abstraction may invalidate use of abstraction in another

  • repath arcs when changing what the root of the graph is (e.g. copying a section of a subgroup)

  • A compose() of two or more deltas might also perform compression, to reduce the overall delta count, rather like a snapshot (though the original history may still be stored elsewhere)

Other structures we considered

// data representation of a graph for the sake of rendering etc. convenience
graph = {
  nodes: {
    a: { pos:[10, 10], kind:"noise", attrs:{}, nodes:{ signal:{ kind:"outlet" } } },
    b: { pos:[10, 50], kind:"dac", attrs:{}, nodes:{ source:{ kind:"inlet" } } },
    // sub-group:
    child: {
      pos: [50, 50], 
      kind:"group", 
      attrs: {},
      nodes: {
        a: { pos:[10, 10], kind:"beep", attrs:{}, nodes:{ signal:{ kind:"outlet" } } },
      },
      /*arcs: [],*/
    }
  },
  arcs: [
    // from, to (, attrs?)
    ["a.signal", "b.source"],
    ["child.a.signal", "b.source"]
  ]
};

child.a.signal -> child.nodes.a.nodes.signal
loop over child.nodes
is child.a.signal an outlet? check child.nodes.a.nodes.signal.kind == "outlet"
graph = {
  nodes: {
    a: { 
      _kind:"noise", 
      _attrs: { pos:[10,10], }, 
      signal: { _kind:"outlet", _attrs:{} } 
    },
    b: { 
      _kind:"dac", 
      _attrs: { pos:[10,50], }, 
      source: { _kind:"inlet", _attrs:{} } 
    },
    g: {
      _kind: "group",
      _attrs: { pos: [10, 10], },
      /*_arcs: [],*/
      a: { 
        _kind:"noise", 
        _attrs: { pos:[10,10], _attrs:{} },
        signal: { _kind:"outlet", _attrs:{} } 
      },
    },
  },
  arcs: [  
    ["a.signal", "b.source" ],
    ["g.a.signal", "b.source" ],
  ]
  ...
}


child.a.signal -> (unchanged)
loop over child.nodes has to avoid anything starting with "_"
is g.a.signal an outlet? check g.a.signal._kind == "outlet"
Clone this wiki locally