\input texinfo @setfilename manual.texi @settitle Homura @titlepage @title Homura @subtitle Replay recorded text @end titlepage @contents @ifnottex @node Top @top Homura @end ifnottex Replay recorded text. @menu * Usage:: Command line help * Input:: Input format * Output:: Output format and usage * Tools:: Helper tools and scripts * Implementation:: Gory implementation details @end menu @c ---------------------------------------------------------------------- @c {{{ @node Usage @chapter 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. @example ./homura @var{input.log} @var{output.html} @end example If second argument is omitted, output is written to stdout: @example ./homura @var{input.log} > @var{output.html} @end example If the first argument is omitted, or if first argument is "-", input is read from stdin: @example ./homura < @var{input.log} > @var{output.html} cat @var{input.log} | ./homura - @var{output.html} @end example @xref{Tools} for scripts to produce the input logs. @c }}} @c ---------------------------------------------------------------------- @c {{{ @node Input @chapter Input Input files are line-based text files. Two types of input lines are accepted (all other lines are ignored): @menu * Snapshot cursor:: @code{Y@var{row}X@var{column}F@var{frame}T@var{time}} * Snapshot line:: @code{L@var{line}E@var{size}=@var{text}} @end menu @c {{{ @node Snapshot cursor @section Snapshot cursor @example @code{Y}@var{row}@code{X}@var{column}@code{F}@var{frame}@code{T}@var{time} @end example Set the cursor position to (@var{row}, @var{column}), and set timestamp for all subsequent events to @var{frame} at @var{time}. @itemize @bullet @item @var{row} - vertical position of cursor. First row starts at row 1. @item @var{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 @code{e3 81 be e3 81 a9 e3 81 8b}, a column value of @code{7} means the cursor points at the 3rd character. @item @var{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. @item @var{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 @var{frame} count but different @var{time} values. @end itemize @c }}} @c {{{ @node Snapshot line @section Snapshot line @example @code{L}@var{line}@code{E}@var{size}=@var{text} @end example @itemize @bullet @item @var{line} - line number. This specifies the line that is currently being snapshotted. First line starts at 1. @item @var{size} - file size, or the line number of the last line in the file. It is an error to have @var{line} be larger than @var{size}. @item @var{text} - current contents of line at @var{line}, in UTF-8 bytes. @end itemize @c }}} @c }}} @c ---------------------------------------------------------------------- @c {{{ @node Output @chapter Output Homura outputs stand-alone HTML files with all the playback information packaged together. @menu * Controls:: How to operate output controls * Compatibility:: Supported browsers @end menu @c {{{ @node Controls @section Controls @itemize @item 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. @item Pause - pause current playback. @item Rewind - stop playback and rewind to beginning of the recording. @item 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. @item 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. @item 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. @item Slider bar - control for skipping to a particular point in time. Requires HTML5 (@xref{Compatibility}). @end itemize 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 @code{realtime_step} to a smaller value, which will make the playback smoother at the expense of more CPU. @c }}} @c {{{ @node Compatibility @section Compatibility Output of Homura is officially supported on two browsers: @itemize @item Google Chrome 12 and above (tested on 12.0.742.112 and 14.0.803.0). @item Firefox 3 and above (tested on 3.6.18, 4.01, and 5.0) @end itemize 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 @code{position} and @code{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. @c }}} @c }}} @c ---------------------------------------------------------------------- @c {{{ @node Tools @chapter Tools Two scripts are included in the package: @itemize @bullet @item @code{record.vim} - VIM script for generating input logs. See script for usage instructions (summary: source the script, call @code{RecordStart @var{output.log}} to record, and @code{RecordStop} when you are done) @item @code{optimize_log.pl} - Perl script for reducing the size of the record logs produced by @code{record.vim}. Homura is guaranteed to produce identical output for logs filtered by @code{optimize_log.pl} @end itemize @c }}} @c ---------------------------------------------------------------------- @c {{{ @node Implementation @chapter Implementation Gory implementation details and design rationales. @menu * Input format:: Designing a low overhead recording format * Event list:: Optimizing for fast fast-forwards * Output slots:: Structuring output for fast line operations * Cursor layer:: Drawing cursor without modifying text * String table:: Minimizing output text * Optimizations:: Reduce output size and decrease entropy * Testing:: Using Homura for production use * Miscellaneous:: Other trivia bits @end menu @c {{{ @node Input format @section 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. @itemize @bullet @item @code{L}@var{line number} @item @code{=}@var{text} @end itemize 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. @itemize @bullet @item @code{Y}@var{row} @item @code{X}@var{column} @item @code{T}@var{time} @end itemize 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: @itemize @bullet @item @code{F}@var{frame} @item @code{E}@var{size} @end itemize 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. @c }}} @c {{{ @node Event list @section Event list Animation events are encoded in a long array of 6-tuples. Five formats are possible: @itemize @bullet @item @code{@var{start},@var{end},0,0,@var{row},@var{column}} - cursor movement. @item @code{@var{start},@var{end},1,@var{slot},@var{index},@var{length}} - replace output slot with text. @item @code{@var{start},@var{end},2,@var{slot},@var{index},@var{length}} - append text to output slot. @item @code{@var{start},@var{end},3,@var{slot},0,0} - delete output slot. @item @code{@var{start},@var{end},@var{size},@var{slot},@var{offset},@var{column}} - slow cursor movement. @end itemize 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 @emph{event type}. Types @code{1}, @code{2}, and @code{3} are text editing events. All of these operate on output slots (@xref{Output slots}). For replace and append events, @var{index} and @var{length} refers to string index and prefix length in the string table (@xref{String table}). Cursor events (type @code{0}) positions the cursor to some (@var{row}, @var{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 @var{type} fields is overloaded to encode cursor size. The fields are: @itemize @bullet @item @var{size} - cursor block size (bytes) + 3. @item @var{slot} - read base string from text at this output slot. @item @var{offset} - treat this number of leading bytes from base string as whitespace. @item @var{column} - original cursor column number (bytes). @end itemize @xref{Cursor layer} for more details on cursor rendering. @c }}} @c {{{ @node Output slots @section 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 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 @emph{output slots}. That is: @itemize @bullet @item 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. @item 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. @item When a line is deleted, the output slot becomes invisible. @end itemize 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: @example Line 1 Line 3 @end example When "Line 2" is inserted later: @example Line 1 Line 2 Line 3 @end example 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. @c }}} @c {{{ @node Cursor layer @section 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: @example 

   



@end example

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:

@example

AA
ｱｱ
あ


@end example

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 
, 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 @emph{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.
@c }}}

@c {{{
@node String table
@section 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 @emph{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.
@c }}}

@c {{{
@node Optimizations
@section Optimizations

Event list value encodings employs a few optimizations:

@itemize @bullet
@item Start time and end time are stored as relative timestamps on
disk, and converted to absolute times on load.  This greatly reduces
output size.
@item Infinite end time (events that persist until end of recording)
are stored as @code{0} to reduce entropy.  This is possible because
the output will not have any transient event that starts and ends in
the same frame.
@item Strings that are more frequently referenced as assigned lower
index numbers, so they take fewer bytes in output.
@item Because cursor movements are the most common events, they are
assigned event type @code{0}.  Similarly, unused fields for delete
events are also filled with @code{0}.  These are all measures to
reduce entropy.
@end itemize

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.
@c }}}

@c {{{
@node Testing
@section Testing

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

@code{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.

@code{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.
@c }}}

@c {{{
@node Miscellaneous
@section 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.
@c }}}

@c }}}