Differ

MiniLatex uses a number of optimizations. One of these is to re-parse and re-render only paragraphs which have changed. This is optimization is important for the editing process, since instantaneous feedback is essential for a satisfying user experience. Such differential transformations are more important for parsing than for rendering, since parsing is by far the most expensive process in terms of execution time.

The strategy is as follows. Let u and v be two lists of strings. Write them as u = a x b, v = u y b, where a is the greatest common prefix and b is the greatest common suffix. Supposed that we have in hand u' = render u = a' x' b', where a' = render a, etc. Let y' = render y. Then v' = diff u = a' y' b'.

The strategy just outlined is far from optimal for arbitrary changes to the list v. However, a real human editor generally makes small, localized changes to v, so in "real life," the strategy is near-optimal.

NOTE. I would like to thank Ilias van Peer, who recommended using a diffing strategy for performance optimization.

Implementing the diff stategy

The stuctures u = a x b, v = u y b map directly onto the DiffRecord type:

type alias DiffRecord =
    { commonInitialSegment : List String
    , commonTerminalSegment : List String
    , middleSegmentInSource : List String
    , middleSegmentInTarget : List String
    }

The implementation of

diff : List String -> List String -> DiffRecord

is straightforward.

Edit records

The function diff carries out the transformation a x b => a y b. To effect the transformation a' x' b' => a' y' b', one needs the notion of an EditRecord, which carries the needed state:

type alias EditRecord a =
    { paragraphs : List String
    , renderedParagraphs : List a
    , latexState : LatexState
    , idList : List String
    }

The rendering function applied to an EditRecord takes paragraphs and LatexState as arguments and returns renderedParagraphs. The idList is a list of ids, one for each rendered paragraph. When an updated EditRecord is formed, the ids of the changed paragraphs are changed. This is done in order to help both the Elm renderer and MathJax to be as efficient as possible. Again: speed optimizations. The initial ids are like this p.0.1, p.0.2, p.0.3, etc. That is, they are sequential in the third component. Suppose that the paragraphs with ids p.0.17 and p.0.18 are changed. The corresponding ids in the new rendered text are something like p.3785.17 and p.3785.18, where 3785 is randomly generated.

Differential rendering

Below is the definition of differentialRender. It takes a rendering function, a DiffRecord, and an EditRecord as input and produces a list of rendered paragraphs as output.

Differ.differentialRender : (String -> a) -> DiffRecord -> EditRecord a -> List a
Differ.differentialRender renderer diffRecord editRecord =
    let
        ii =
            List.length diffRecord.commonInitialSegment

        it =
            List.length diffRecord.commonTerminalSegment

        initialSegmentRendered =
            List.take ii editRecord.renderedParagraphs

        terminalSegmentRendered =
            takeLast it editRecord.renderedParagraphs

        middleSegmentRendered =
            List.map renderer diffRecord.middleSegmentInTarget
    in
    initialSegmentRendered ++ middleSegmentRendered ++ terminalSegmentRendered

Updating an EditRecord

Updating an EditRecord is a multistep process. The Differ.update function takes as input a random number seed, a rendering function, and EditRecord, and a string of source text. The output is an updated EditRecord. Here are the steps:

1. Apply logicalParagraphify to transform the input source text string into a list of logical paragraphs.

2. Apply diff to the "old paragraphs" in the EditRecord and the "new paragraphs" from (1) to produce a DiffRecord.

3. Apply differentialRender to the DiffRecord from step (2) and the list of logical paragraphs frome step (1) to producn updated list of rendererd paragraphs.

4. Apply differentialIdList to the random seed, the DiffRecord, and "old" idList from the EditRecord to create a new list of paragraph ids.

The final step is to used the information harvested in 1--4 to create a new EditRecord.

Differ.update : Int -> (String -> a) -> EditRecord a -> String -> EditRecord a
Differ.update seed transformer editRecord text =
    let
        newParagraphs =
            Paragraph.logicalParagraphify text

        diffRecord =
            diff editRecord.paragraphs newParagraphs

        newRenderedParagraphs =
            differentialRender transformer diffRecord editRecord

        p =
            differentialIdList seed diffRecord editRecord
    in
    EditRecord newParagraphs newRenderedParagraphs emptyLatexState p.idList