History API

History API

This refers to the following issues:

• Change API

• Persistent Undo

• Have an interface for the history tree, document it

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

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

history_id (integer)

The index of the active history node. When setting history data, we need to know which node is supposed to refer to the current buffer contents for purpose of validation, so we need it to be part of the data we are setting.

parent<n> (integer)

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

timepoint<n> (ISO-8601 timestamp)

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 1 2018-12-31T11:15:56Z '+|1.2|hello world' '-|2.7|foo'
0 2 2018-12-31T11:16:12Z '+|2.2|bar'
1 -1 2018-12-31T11:16:46Z '+|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 history ID must refer to a valid node.

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

3. Node 0 must not have any modifications.

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

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

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

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

8. 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.

9. 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.