DIFFH - A diff frontend for output in HTML format.

Copyright (C) 2006 Matt Giuca <http://codestar.lidonet.net>

This program is free software; you can redistribute it and/or 
modify it under the terms of the GNU General Public License 
as published by the Free Software Foundation; either 
version 2 of the License, or (at your option) any later 
version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

DESCRIPTION
The program takes unified diff output (output with a -U argument) and
converts it into fully valid XHTML format. The output matches the history
pages in the MediaWiki (Wikipedia) software.

PROGRAM ACTIVITY
The program has two separate diff features:
1. Line-by-line diff - diffs are separated into lines with color-coded
    backgrounds.
2. Word-by-word diff - within each chunk of changes, individual words
    are color-coded if they were added or removed.

The LBL diff is done by the diff program and will be present in the incoming
file. The CBC diff must be performed by diffh.

The WBW cannot be done on a per-line basis because sometimes the line spacing
is altered but the characters are not. Therefore, the WBW must be done on a
per-"chunk" basis.

The WBW diff only has a single color-coding scheme - words are
*highlighted* if they do not appear in the other version.

PROCESS - UNIFIED I/O
1. Parse the diff file into a structure containing all of the file's
    information. This structure is similar to the original diff, and stores
    an array of strings for lines, and for each line, whether it is
    unchanged, + or -.
2. Write the HTML file.
    1. Write the generic header.
    2. Write the page header with filename and timestamp information.
    3. Process each hunk, writing it to HTML.
    4. Write the HTML footer and close.

SPECIAL FEATURE
The program has another special feature which is taking a CVS history file
and producing an entire folder of HTMLs which lets the user browse its
entire history, including a main links page with all of the edits and log
notes taken from the log.

This will be added later since it will require a very different input engine.
(And only slight changes to output). It will contain a replacement for step 1
above, but call the same step 2 for each revision, with minor changes.

It may need to construct the unified diff manually from the CVS log, to avoid
having to call CVS functions from a workspace directory (since I'm planning
to let you simply run it on a ,v file. Also there should be another feature
which lets you call it from a workspace as you do with regular CVS - this
would look in the subdirectory of the current directory for information on
where the ,v file is located).

The way to do this is probably to start with the head version and lay out
each line as a string in an array. Then, as well as following the
instructions of the CVS to transform it into the previous version, create a
hunk structure, copy some context lines in around the changes, and then add +
and - lines for the changed lines.

This should end up with 2 things - a string array of the previous version -
ready to iterate backwards, and a finished udiff structure ready to run
through the output routines of diffh.

The only difference in the output HTML is an extra row(s) which contains the
version log notes.

Also we'd need to be writing a special "history index" html file containing
links to all the other files and serving as a complete version log.

DEFINITIONS
A "hunk" as defined in the manual is a section of unified diff preceded by
the ranges heading. A hunk contains one or more chunks of changed lines.
A "chunk" is one or more concurrent changed lines (with a + or -). Chunks
are separated by unchanged lines.
A "word" is strictly defined as a contiguous set of either alphanumeric
characters or spaces (but not both). Thus, any non-alphanumeric/space symbols
are considered to be 1 word per character. Any non-alphanumeric symbol
will separate words, and also form a single-character word by itself.
Multiple spaces are grouped into the same word for ease of converting to
&nbsp;s in the HTML representation.

Note that in the final HTML, each hunk has a special line introducing its
line number - paralelling the hunk header line in the diff output.

PROGRAM MODULES

main
    - input (reads into udiff structure)
    - cvs (implements special cvs parsing into udiff)
        - cvs_history (writes history index html)
    - output (writes html)
        - hunk (writes unchangeds to html and passes groups of lines to
            chunk module)
        - chunk (forms chunks, parses them, and writes them to html)

DATA STRUCTURES

-UDIFF
Very similar to the original diff file.
struct UDiff {
    char* from_filename;
    TIME from_time_stamp;
    char* to_filename;
    TIME to_time_stamp;
    hunk* Hunk;
    int numhunks;
}

From the diff manual:
"The time stamp looks like 2002-02-21 23:30:39.942229878 -0800 to indicate
the date, time with fractional seconds, and time zone."
Contains an array of hunks - see below.

-HUNK
Very similar to a hunk of the original diff file (part of UDIFF structure)
struct Hunk {
    int from_line_start;
    int to_line_start;
    char** line;
    char* line_type;
    int numlines;
}
from/to_line_start contain the starting lines from the given range.
    - Note that the end line is dropped, as we don't use it.
line is simply a string array of each line.
line_type is a char to save space - with one of three values -
LINE_UNCHANGED, LINE_DELETED or LINE_ADDED.

-CHUNK
(Note that this structure stores only a half-chunk - one side)
struct Chunk {
    int* line_index;
    char** word;
    char* word_changed; /* boolean */
    int numlines;
    int numwords;
}
(Note: word and word_changed correspond)

Only two half-chunks is processed at a time, so space concerns aren't really
an issue - all memory is freed at the end for the next chunk pair.

A chunk is parsed from one side of the full chunk, which is simply an array
of string lines. Line boundaries are ignored in the final list of words. The
array word contains each word of the chunk as a string. The line_index array
has one element per line, and contains the index of the word array where each
line begins. The word_changed array is initially initialised to 0. This array
specifies whether a word should be highlighted.

The chunk data structure is then read directly into the HTML or a near-HTML
form, simply by writing each word, printing the appropriate HTML tags to turn
on and off highlighting, and writing new table rows as necessary.

ALGORITHMS

HUNK PARSING

The hunk is stored simply in lines of strings. It is parsed and written
directly to HTML.

For each line:
- If unchanged, it is written straight to HTML as per the design below.
- If changed, the program then reads all of the lines up until the next
    unchanged one, and sorts them into special arrays - one for deleted and
    one for added.
    - Each of these special arrays forms a half-chunk. It parses the
        half-chunks into proper chunk data types. (this is done by the chunk
        module).
    - It then passes the two half-chunks to the chunk parser which does
        nothing but modify the chunk structures.
    - Each half-chunk is then parsed into HTML using another function
        outlined below. It doesn't write tables yet, just the HTML code
        within each cell, stored in string arrays.
    - Finally, the two half-chunks are passed to a function which interlaces
        them and writes them to the final HTML file.

Note that at the beginning of the program's major step 2, a global variable
is set up with the output stream. All writing goes directly to this.

The processes outlined above are described in more detail below.

CHUNK PARSING

This details the process of taking two fully-formed chunk structures (as
described above) and simply figuring out the values of the word_changed
arrays.
(Note that this compares two separate chunk structures, two half-chunks,
representing a full chunk).

The word_changes arrays default to 0 for all words. This uses the longest-
common subsequence algorithm described here:
http://en.wikipedia.org/wiki/Longest-common_subsequence_problem
The chunks are parsed word-for-word for an LCS. The recursive function begins
with a scope of the entire chunk (in both sides). If one is found, it does
nothing but recurse to either side of the LCS, reducing the scope in
recursion. If no LCS is found, then all of the words in the current scope on
both sides have their word_changed set to 1. That's it.

(This works because all common words will eventually be identified as LCSs
and then be taken out of recursion scope. When no LCS is found, all the words
there must be unique to either side, and so are highlighted).

HTML WRITING - FROM CHUNKS

We convert from the chunk (half side) data type into an array of strings.
This array contains one element for each line of the half-chunk, and within
the array, properly-formed HTML code - the line itself is complete.

By writing each side to a separate array, the full chunk is complete. When
writing the full chunk to the final HTML code, the sides must be interlaced,
and combined with other table columns such as the - and + columns, and other
HTML syntax. In short, however, it is a simple matter of interlacing each
side and writing empty tables when one side of the chunk runs out of lines.

HTML DESIGN
The HTML will be properly-formed XHTML with embedded CSS. The main display
will be a table of 4 columns. Each hunk begins with a special row with only
two columns with a colspan of "2", containing the start line for this hunk.

On regular lines, columns 1 and 3 contain the - and + symbols, and columns
2 and 4 contain the line data. Each line has its own row, and there are two
possibilities:
- If the line is an unchanged line, then both sides will be identical.
Columns 1 and 3 will have no content. Columns 2 and 4 will have the
"diff-context" class.
- If the line is part of a chunk, then column 2 will have the
"diff-deletedline" class and column 4, "diff-addedline"
(Or at least, that's what MediaWiki calls it).
    - "highlighted" text is given a span class "diffchange"
    - Often a line from one side or the other will be missing. In this case,
        the two columns for that side are replaced with a single column of
        colspan 2 containing nothing or &nbsp;.
    - Column 1 will contain "-" and column 3, "+", unless empty.
