Homura
******

Replay recorded text.

Usage
*****

Homura takes text logs and produces HTML files that allows interactive playback.  Homura accepts up to two arguments, first argument is the input file, and second argument is the output file.

     ./homura INPUT.LOG OUTPUT.HTML

If second argument is omitted, output is written to stdout:

     ./homura INPUT.LOG > OUTPUT.HTML

If the first argument is omitted, or if first argument is "-", input is read from stdin:

     ./homura < INPUT.LOG > OUTPUT.HTML
     cat INPUT.LOG | ./homura - OUTPUT.HTML

See Tools for scripts to produce the input logs.

Input
*****

Input files are line-based text files.  Two types of input lines are accepted (all other lines are ignored):

Snapshot cursor
===============

     YROWXCOLUMNFFRAMETTIME

Set the cursor position to (ROW, COLUMN), and set timestamp for all subsequent events to FRAME at TIME.

  * ROW - vertical position of cursor.  First row starts at row 1.

  * COLUMN - horizontal position of cursor (bytes).  First column starts at column 1.  The unit is in bytes and not characters. For example, given a line with three UTF-8 characters e3 81 be e3 81 a9 e3 81 8b, a column value of 7 means the cursor points at the 3rd character.

  * FRAME - frame counter, used to differentiate events that happened in the same second.  Frame counters start at zero, and can roll over if the input log was recorded across multiple sessions.

  * TIME - number of seconds that elapsed since the beginning of the recording.  Timestamps start at zero and can rollover for multi-session logs.  It is an error to have two events with the same FRAME count but different TIME values.

Snapshot line
=============

     LLINEESIZE=TEXT

  * LINE - line number.  This specifies the line that is currently being snapshotted.  First line starts at 1.

  * SIZE - file size, or the line number of the last line in the file.  It is an error to have LINE be larger than SIZE.

  * TEXT - current contents of line at LINE, in UTF-8 bytes.

Output
******

Homura outputs stand-alone HTML files with all the playback information packaged together.

Controls
========

  * Play - multiple buttons to start replaying text.  "play 1x" replays the text at the rate which they were originally recorded (if your machine can keep up), "play 3x" replays at 3 times the original speed, and so on.

  * Pause - pause current playback.

  * Rewind - stop playback and rewind to beginning of the recording.

  * Follow cursor - show current cursor position in (row, column) values.  If the checkbox is checked, the window will automatically scroll to follow the cursor's row position when playback is not paused.

  * Fast scroll - if cursor moved outside of current viewport, scroll to new cursor position immediately.  If not checked, scroll toward new cursor position slowly.  Enabling fast scroll means the cursor is always within sight, which usually works better for following source code edits since the cursor tend to jump all over the place.  For other types files, disabling fast scroll imposes a speed limit on how fast the viewport can scroll, and tend to go better on the eyes.

  * Highlight transient lines - highlight lines that will be replaced or deleted later in a different color.  Homura knows what pieces of text will remain constant until the end of the replay log, and will color all other lines differently if this box is checked. Note that if a line is only appended to before end of time, the line will be considered non-transient.  This is useful for visualizing how a file converges to its final state.

  * Slider bar - control for skipping to a particular point in time. Requires HTML5 (see Compatibility).

Regarding playback speed: most of the events match the original speed which they were originally recorded, except long periods of idleness are compressed.  For example, if you were away from keyboard for an hour, Homura will inject about 3 seconds of non-activity into the output log as opposed to the full hour.  If your system is fast, you can try decreasing realtime_step to a smaller value, which will make the playback smoother at the expense of more CPU.

Compatibility
=============

Output of Homura is officially supported on two browsers:

  * Google Chrome 12 and above (tested on 12.0.742.112 and 14.0.803.0).

  * Firefox 3 and above (tested on 3.6.18, 4.01, and 5.0)

Homura requires JavaScript, HTML5, and CSS2.

Regarding HTML5: Output uses HTML5's range inputs.  On browsers that supports this (e.g. Chrome), you will see a slider bar for fast forward and rewind controls.  On browsers that don't support it (e.g. Firefox 5.0 and earlier), you will see a text box instead.  Note that it's still possible to fast forward or rewind using the text box, just enter the millisecond timestamp values into the box.

Regarding CSS2: Output uses position and z-index attributes for positioning.  If your browser supports CSS Color Model Level 3, the controls will fade out to make the underlying text more visible.  Moving the mouse cursor into the control area will bring the controls into foreground again.

Regarding JavaScript: Output uses mostly very simple JavaScript features, but the scripting engines must process quite a bit of data to be able to replay the text in real time (target refresh rate is ~12 frames per second).

On some systems, despite having a fast HTML renderer and layout engine, you may see some text being dropped when the text is being replayed at a high speed, or the timestamp might not be updated for a few seconds.  Pausing the replay appears to force everything to render correctly again.

Output of Homura passes HTML validation.  If the output doesn't work with your browser, it's time to get a different browser.  In particular, the output is not compatible with Internet Explorer 8 and its atrocious CSS support.

Tools
*****

Two scripts are included in the package:

  * record.vim - VIM script for generating input logs.  See script for usage instructions (summary: source the script, call RecordStart OUTPUT.LOG to record, and RecordStop when you are done)

  * optimize_log.pl - Perl script for reducing the size of the record logs produced by record.vim.  Homura is guaranteed to produce identical output for logs filtered by optimize_log.pl

Implementation
**************

Gory implementation details and design rationales.

Input format
============

Initially, I had just wanted this simple VIM script for recording text editing sessions.  And I had intended it to be really simple, like taking a full snapshot of the file every second or so.  At this point, the input format would contain only two things: line number of the line that is currently being snapshotted, and the contents of that line.  This would be half of the input format.

  * LLINE NUMBER

  * =TEXT

As it turns out, taking a snapshot every second would be expensive, and still doesn't capture enough text.  I look for autocommands that are built into VIM, and I found that the best one to use was to hook onto cursor movements: every time a CursorMoved or CursorMovedI event was fired, I would snapshot the file.  Since the snapshots are hooked onto cursor movements, I figured I would capture the cursor position at the same time.  This determined the other half of the input format.

  * YROW

  * XCOLUMN

  * TTIME

Capturing the cursor position turns out to be a very good idea, since a significant portion of the events recorded will in fact be cursor movement events.  Since the cursor events are fairly compact (one line per event, as opposed to multiple lines for text snapshot events), I have decided to store the timestamps with only the cursor events.

Two extra bits of detail that was added later to the input format to finalize it:

  * FFRAME

  * ESIZE

These were not immediately obvious, but as it turns out: VIM can not record sub-second timestamps, even though multiple editing events usually happen in the same second.  To differentiate sub-second events, a frame counter is used.  The sub-second events will be spaced evenly in replay, as opposed to having actual sub-second accuracy. This is good enough for most people.

The file size field for the line snapshots was the other non-obvious bit.  Without which, it's not possible to tell when lines are deleted from a file (since the last lines of the snapshot persists forever). There are other ways for representing this data as opposed to having to store the file size on every line, but this turns out to be the most robust encoding.

Event list
==========

Animation events are encoded in a long array of 6-tuples.  Five formats are possible:

  * START,END,0,0,ROW,COLUMN - cursor movement.

  * START,END,1,SLOT,INDEX,LENGTH - replace output slot with text.

  * START,END,2,SLOT,INDEX,LENGTH - append text to output slot.

  * START,END,3,SLOT,0,0 - delete output slot.

  * START,END,SIZE,SLOT,OFFSET,COLUMN - slow cursor movement.

The first two entries of every event are always the start and end times.  Start time is when the event should appear, and end time is when the event will be obsoleted by another event (e.g. a replace or event on a particular slot will be obsoleted by a replace or delete event on the same slot).

End time is strictly an optimization to make fast forwards efficient: when user seeks to a particular point in time, all events with end times less than the target will be ignored.  This worked so well that I didn't have to define other event types for "keyframes".  As a side benefit, Homura knows which lines will remain constant (or only appended to later) by looking at these end times, so it was possible to add the functionality to differentiate the transient/constant lines.

Third number indicates the event type.  Types 1, 2, and 3 are text editing events.  All of these operate on output slots (see Output slots).  For replace and append events, INDEX and LENGTH refers to string index and prefix length in the string table (see String table).

Cursor events (type 0) positions the cursor to some (ROW, COLUMN) position.  Note that column position unit is in bytes and not characters, same as what's in the input.  Cursor can be outside the bounds of all currently visible text, and actually this is the common case since the text editor usually records cursor positions to be just past the end of the last character.

Slow cursor events (all remaining types) serves the same purpose as cursor events, but is needed to deal with Unicode characters and tabs. It also needs 4 pieces of data instead of 3, so the TYPE fields is overloaded to encode cursor size.  The fields are:

  * SIZE - cursor block size (bytes) + 3.

  * SLOT - read base string from text at this output slot.

  * OFFSET - treat this number of leading bytes from base string as whitespace.

  * COLUMN - original cursor column number (bytes).

See Cursor layer for more details on cursor rendering.

Output slots
============

Since most text operations are line-based, it made sense that the output would also be line-based.  One way to implement line-based output in HTML is to have lots of <SPAN>s, one per line.  This is very straightforward if we only ever append lines to a file, or if inserting a single line means shifting all the lines after it. Neither is very efficient.

To make line-based operations efficient with JavaScript, Homura use the concept of output slots.  That is:

  * Every time a line is observed, it's assigned a slot for output. These output slots remain fixed -- once a line is assigned to a slot, its position is fixed until the line is deleted.

  * When a line is inserted, the corresponding output slot is inserted.  These output slots are initially invisible, so the viewer does not see any gaps between lines, even if there exists some gaps to accommodate the later lines.

  * When a line is deleted, the output slot becomes invisible.

For example, if we have a file with "line 1" and "line 3", and "line 2" is inserted in between at some later point in time, the output slots will be initialized to be the following:

     <span id="slot0">Line 1
     </span><span id="slot1"></span><span id="slot2">Line 3
     </span>

When "Line 2" is inserted later:

     <span id="slot0">Line 1
     </span><span id="slot1">Line 2
     </span><span id="slot2">Line 3
     </span>

The slot numbers are assigned serially.  Output slots are recycled where possible.  For example, if "Line 2" above is deleted and a different line is inserted later, the new line will likely share the same output slot.

Cursor layer
============

While editing text, it's quite common for the cursor to be located outside of all currently visible text (e.g. just past the last character).  It's also more common to see cursor movements than actual text edits.  For these reasons, we want to be able to handle the cursor independently from all text events, and be able to render the cursor without disturbing all existing text.  Fortunately, this is quite easy with CSS2:

     <div style="position:relative">
        <pre style="position:absolute; top:0px; left:0px; z-index:1" id="cursor"></pre>
        <pre style="position:absolute; top:0px; left:0px; z-index:2" id="text"></pre>
     </div>

All the cursor drawing will be done inside the "cursor" block, and all the text drawing happens in the "text" block.  Both blocks use absolute positioning relative to the parent div, so they are rendered on top of each other.  Text will be drawn in front of the cursor because it has a greater z-index.

This works great for inputs containing only ASCII characters.  For generic Unicode, it becomes a mess because it's impossible to get the cursor to line up with the text.  Try the following snippet:

     <pre>
     <span style="background-color:#f00">AA</span>
     <span style="background-color:#0f0">&#xFF71;&#xFF71;</span>
     <span style="background-color:#00f">&#x3042;</span>
     </pre>

The first line contains two ASCII "A" characters, which are each half-width.  The second line contains two half-width Katakana "A" characters, and the last line contains a single full-width Hiragana "A".  All of these are inside a <pre>, so monospace font should be used.  Per Unicode standards, all 3 lines should have widths that add up to exactly 1em of space, so all 3 lines should be equally wide.  In practice, the first line is 16 pixels wide, the second line is 14 pixels, and the last line is 12 pixels.  Same observation on both Chrome and Firefox, both Windows and Linux.

As it turns out, knowing exactly how wide non-ASCII characters are is a total mess, so we can't use the naive cursor positioning code to draw the cursor block (plus, it probably wouldn't be the right width anyways).  This is why there is a slow cursor event, which basically renders the cursor by duplicating the foreground text in the cursor layer, but do it in different colors.  This technique guarantees that the cursor will be at the right position with the right width.

Without any Unicode, using tabs alone would be enough to cause slow cursor events to be inserted.  While we could make some effort to expand tabs to spaces and translate cursor positions accordingly, doing slow loses information about the original cursor positions, so slow cursor events are used for tabs as well.

String table
============

It's likely the case that the same set of strings appear multiple times in the file.  This is especially true for editing ASCII files, where there are only so many characters, and they are appended one at a time.  To avoid redundant definitions of the same strings, Homura maintains a string table that keeps track of all strings, so that the event list references them by index instead having to embed the full string in each event.

To further reduce output size, strings that are prefixes of other strings are not stored separately.  For example, given two strings "hogepiyo" and "hoge", only the "hogepiyo" string will be stored in the string table.  This requires all string table references to include an extra "prefix length" field, but it's a good tradeoff, and made encoding line truncations more efficient.

Optimizations
=============

Event list value encodings employs a few optimizations:

  * Start time and end time are stored as relative timestamps on disk, and converted to absolute times on load.  This greatly reduces output size.

  * Infinite end time (events that persist until end of recording) are stored as 0 to reduce entropy.  This is possible because the output will not have any transient event that starts and ends in the same frame.

  * Strings that are more frequently referenced as assigned lower index numbers, so they take fewer bytes in output.

  * Because cursor movements are the most common events, they are assigned event type 0.  Similarly, unused fields for delete events are also filled with 0.  These are all measures to reduce entropy.

The primary goal is to reduce output size without obfuscating the output too much.  The secondary goal is to decrease entropy so that output files compress better.  And as we all know, reduced entropy helps the entire universe.

Testing
=======

Homura has been fairly well tested, using unit testing and fuzz testing techniques, passes valgrind, and has been tested using real world data.

record.vim introduces negligible overhead in terms of RAM and CPU, but takes up quite a bit of space.  A full recording of the editing session for this manual (~2 hours of editing) takes up ~30MB of space, and full recording of my entry for ICFP 2011 (~1500 lines of C++ code, edited for ~8 hours) takes up ~330MB of space.  Homura is able to process both in less than a minute, and produce HTML files less than ~4MB.

record.vim and Homura combined are ready for every day use. Homura is not meant to replace version control systems, but fills a gap that has very practical uses -- you can now see versions of a file at very fine time granularities, all without having to explicitly commit changes to source control systems.

Miscellaneous
=============

I had intended to create just a simple script to capture some ASCII art editing sessions, the initial goal was just enough to produce animated GIFs or something.  As usual, I have underestimated the scope of the project, and the end result was ~3K lines of C++.  Oh well.

I also did not plan to spend more than a month working on this when I started, but I just got too busy with my full time job and couldn't find enough free time.  For real.  The fact that I also re-watched Mahou Shoujo Madoka Magika about 3 times in the last month had nothing to do with it.

I am most proud of the fact that Homura works with UTF-8.  I think most of the grief was spent on getting the cursor right with Unicode.

Homura is named after Akemi Homura, from "Mahou Shoujo Madoka Magika". So named for her ability to rewind time.