History API

History API

This refers to the following issues:

• Change API

• Persistent Undo

• Have an interface for the history tree, document it

Changes

• Re-removed history_id. Since we will need a separate command to set the history data, it can take the new history_id followed by the history node data, so this does not need to be part of the history node data.

Goals

1. Provide all information necessary for a "Persistent Undo" plugin.

2. Provide all information necessary for a tool like parinfer-rust to inspect all the changes to the buffer since it was last seen.

3. Enable for "undojoin"-like functionality: easily amend the current history node.

4. Be easy to parse from POSIX shell.

5. Allow for plugins to implement Vim’s :earlier.

Nice to have:

1. Use one variable, allowing history to be replaced with set-option.

2. Have the format be compact, to avoid environment variable limits.

3. Able to support cursor positions or timestamps for each node in the future.

Format

<parent0> <timepoint0> <redo_child0> <modification0.0> <modification0.1> <modification0.2>...
<parent1> <timepoint1> <redo_child1> <modification1.0> <modification1.1>...
...

parent<n> (integer)

Index of the parent of node <n>. The parent of node 0 is -1.

timepoint<n> (ISO-8601 timestamp in UTC)

The time the history node was first committed.

redo_child<n> (integer)

Index of the node to which we will move if the user types U. Leaf nodes should have -1.

modification<n>.<m> (modification)

The <m>th modification for node <n>.

Modifications are represented as `op|coord|text` strings.  `text` is at the
end so it can contain arbitrary text, including pipe symbols, and still be
easily parsed by shell.

For example:

-1 1 2018-12-31T11:15:56Z
0 2 2018-12-31T11:16:12Z '+|1.2|hello world' '-|2.7|foo'
1 -1 2018-12-31T11:16:46Z '+|2.2|bar'
1 -1 2018-12-31T11:17:03Z '+|7.16|x'

(Quotes are the quotes which might be added by shell expansion, not part of the format itself.)

Since each history node consists of a variable number of items, processors will need to detect the start of the next record by checking if the current item is a well-formed integer. We can parse the data in POSIX sh like so:

eval set -- "$kak_history"
node=-1
while [ $# -gt 0 ]; do
  node=$(( node + 1 ))
  parent=$1
  shift
  timepoint=$1
  shift
  redo_child=$1
  shift
  while [ $# -gt 0 ]; do
    case "$1" in
     [-+]\|*)
       op="${1%%|*}"
       tmp="${1#*|}"
       coord="${tmp%%|*}"
       text="${tmp#*|}"
       # Process the modification
       shift
       ;;
     *[!0-9]*)
       shift # Ignore something unknown
       ;;
     *)
       break # Start next record
       ;;
    esac
  done
done

Extending

Since modifications are tagged with + or - in their first field, we can add more tags. In the documentation, we warn existing processors to ignore unknown tags.

Validating

1. The parent of node 0 must be -1.

2. Node 0 must not have any modifications.

3. The graph must be acyclic with respect to parent pointers.

4. The graph must be fully connected; every node must be reachable from the root.

5. Every redo_child of an internal node must point to an immediate child node.

6. Every redo_child of a leaf node must be -1.

7. Working backward from the supplied history ID and the current buffer contents to the root, all modifications which are insertions should be deletable and all deletions should be insertable. This means that the coordinate for each exists and the supplied text for insertions is present at that coordinate.

8. Given the constructed buffer contents for node 0 created in the previous step, it should be possible to reach all leaves by applying the insertions or deletions in every node.