2010-09-20

Technical study: multi-page HTML rendering

What we need

How hard would that be to render a single Novelang document over multiple HTML pages? Better ask: how cool would that be? Think about Novelang documentation taking one single huge page. This makes non-linear reading quite uncomfortable. Of course, multi-page rendering should work for both batch and interactive mode.

Technical implications

For batch rendering, there can be a simple approach. Xalan (XSLT rendering engine) offers the redirect extension for redirecting output into a given file.

<xsl:template match="/doc/foo">
  <redirect:write select="@file">
    <foo-out>
      <xsl:apply-templates/>
    </foo-out>
  </redirect:write>
</xsl:template>

Unfortunately, this is not suitable for interactive rendering. For interactive rendering, the endering process must known both:

  • The requested page, through a URL aware of the page (as sub-part of the whole document).
  • The whole document, because we may need to render links to other chapters or whatever.

The same need arises for batch rendering but with Xalan’s Redirect extension mentioned above, the whole logic gets buried inside the XSLT (which probably makes it quite complex).

Obviously, we need a Renderer to work the same way for batch and interactive rendering, e. g. there should be no special handling of interactive or batch rendering in the XSL stylesheet. (But multi-page rendering would require a special stylesheet anyways, at least for generating navigation.)

While XSLT-based rendering is the most common case in Novelang, it’s better to think about the general contract of a org.novelang.rendering.Renderer. As it already does, the Renderer should spit bytes into a java.io.OutputStream with no knowledge wether it is a file or a socket. The job of creating the output (which means chosing a file name in the case of batch rendering) is left to some upstream object opening the OutputStream. Currently, this is done by org.novelang.batch.DocumentGenerator or org.novelang.daemon.DocumentHandler which both end by calling DocumentProducer, passing it the OutputStream.

So rendering stage needs additional logic. Interactive rendering implies to extract the requested page from the URL. Batch rendering implies to find the list of pages to create corresponding files on the filesystem.

New Renderer contract

There can’t be unique way to split a document into pages, so we have new responsabilties for our Renderer:Given a document tree (as a org.novelang.common.SyntacticTree) it calculates a list of page identifiers.Given the same document tree, plus a page identifier, it renders the corresponding page to an OutputStream.With something like a single empty page identifier, we should get the same single-page rendering as we have now.

For an XSLT-based Renderer, we should embed page identifiers generation in the same XSL stylesheet (as a part of already-discussed stylesheet metadata ):

<xsl:stylesheet [namespaces blah blah] >

  <nlm:multipage>
    <!-- 
      Some XSL tranformations here,
      starting from  element. 
    -->
  </nlm:multipage>

  ...

Before page rendering occurs, Novelang asks the Renderer for page identifiers. The default XSL-based Renderer applies the content of the element (if there is one) as a stylesheet on the whole document tree. Then it obtains a list of page identifiers as follows:

<pages>
  <page name="Home" >/n:opus
  <page name="ChapterOne" >/n:opus/n:level[1]
  <page name="ChapterTwo" >/n:opus/n:level[2]
<pages>

Of course each page name is unique. In order to achieve this with no tweak, the document tree may embed unique identifiers by extending the semantic of n:implicit-identifier or by adding a new n:unique-identifier element. Node paths seem easy to generate .

Now for each page, Novelang creates the corresponding file out of the page name. If the stylesheet in the did chose filesystem-friendly names, those will be used verbatim (otherwise we may apply some variant of URL encoding). And, for each page, Novelang calls the Renderer with the whole document tree again, and passes additional metadata elements to tell the Renderer which page it is rendering. Input XML looks like this:

<n:opus>
  <n:meta>
    <n:page-name>ChapterOne
    <n:page-path>/n:opus/n:level[1]
  </n:meta>
</n:opus>

This should be enough for the Renderer to figure how to render only the page of interest. It might need to peek elsewhere in the document tree (like for a footer with a copyright notice, or find other chapter names for a navigation bar).

Mix with other features (present or future)

There is an additional role for node identifiers: they might help to “enhance” internal links by adding the prefix corresponding to the target page. (The internal link feature is yet in inception phase. It just seems easier to implement it right after multipage rendering.)

Unique page names

Novelang’s Fragment Identifier is the perfect candidate to generate page identifers. Unfortunately, composite identifier contain the \ character. Should we escape it, or mix it with some weird pseudo-directory feature? But maybe it’s time to remove relative identifiers which never proved useful, and don’t guarantee identifer uniqueness, anyways.

It’s easy to create a new element by adding a simple counter to a colliding identifier. The value for some given document fragment may change across several generations, when adding fragments with colliding identifiers. This won’t be a problem for internal links (links defined by the document itself) prohibit usage of unique identifier. Remember: unique identifiers are only for pure HTML links.

If there is a chance that a foreign HTML documents links to the HTML anchor defined by the unique identifier (in a pure WWWW – World Wide Web Way) then document author should use explicit identifiers.

New URL scheme

With single-page rendering, the rendered document has the same name as the source document (with the difference of the extension). Multi-page adds a new “dimension”. Because the name of the page may collide with another document’s name, the name of the originating document prefixes the page name. Let’s look at different options:

/main/documentation~syntax.html
/main/documentation!syntax.html
/main/documentation,syntax.html
/main/documentation^syntax.html
/main/documentation--syntax.html

Let’s see which character we could use (only checked on Mac OS X, to do: check on Windows):

Character Escaped? Comments
~ No Already used for Novelang meta pages.
- No Already used for Novelang identifiers.
^ No Meaningless in that context.
# No Fragment in URL.
, No Hard to distinguish from full stop . character.
! No Hard to read.
_ No Too common in file names.
+ No Used in URL encoding. Usage unrelated to “plus” meaning.
% No Used in URL encoding.
= Yes Used in URL encoding. Usage unrelated to “equality” meaning.
$ Yes Overused.
; Yes Hard to read.
| Yes Hard to read.
' Yes Hard to read.
& Yes Already used for URL parameters.
? Yes Already used for URL parameters, DOS wildcard.
@ Yes Inverted meaning if page name appears second.
{ Yes Weird because unpaired. Meaningful otherwise.
§ Yes Mac OS X console doesn’t like it.
: - Path separator on Unix.

The “Escaped?” column means, it requires escaping on Mac OS X console.

Finally, it turns out that -- looks the best, especially with a variable-width font like in Mac OS X Finder or Windows Explorer.

Special case: if the page identifier was blank, the page separator doesn’t appear so we would still have:

/main/documentation.html

This naming scheme also implies that all pages appear flatly in the same directory. This should help when resolving resource names.

2010-09-04

Novelang-0.46.1 released!

Just released Novelang-0.46.1!

Summary of changes:

  • Added source packaging for Novelang-attirail subproject.

Download it from here.

Enjoy!

2010-08-29

Novelang-0.46.0 released!

Just released Novelang-0.46.0!

Summary of changes:

New experimental features for code reuse:

  • Novelang-attirail subproject aggregating various tools. It’s not part of standard distribution, by now it requires separate rebuild.
  • Pluggable logging implementation.
  • Java code all under org.novelang package (was novelang).

Download it from here.

Enjoy!

2010-08-27

Novelang-0.45.0 released!

Just released Novelang-0.45.0!

Summary of changes:

  • Added Greek and Polish characters to the grammar.

Download it from here.

Enjoy!

2010-08-08

Novelang-0.44.5 released!

Just released Novelang-0.44.5!

Summary of changes:

  • Fixed release notes generation.

Download it from here.

Enjoy!

Novelang-0.44.4 released!

Just released Novelang-0.44.4!

Summary of changes:

  • Fixed a few references to old "Part" and "Book" terms, and file suffixes as well.

Download it from here.

Enjoy!

Script for renaming to new extensions

Here is a Bash script (tested on Mac OS X) that renames every .nlp into .novella and .nlb into .opus. It also changes file content. Use with care.

#!/bin/sh

SED='s/\.nlp/\.novella/g;s/\.nlb/\.opus/g'
for file in `find src modules \( -name *.nlp -o -name *.nlb \) `
do
  newfile=` echo "$file" | sed $SED `
  echo "$file -> $newfile"
  sed $SED < $file > $newfile
  rm $file
done

2010-08-07

Novelang-0.44.3 released!

Just released Novelang-0.44.3!

Summary of changes:

  • Fixed Nhovestone report generation.

Download it from here.

Enjoy!

2010-07-25

Maven cheat sheet (0.44.2)

There is an updated version of this post.

This is a list of useful Maven commands. They work with Novelang-0.44.2. Later version will probably make some of them less verbose, using some default parameters.

Convention: the Novelang/$ represents the command prompt, with working directory being Novelang’s home directory. Subdirectories appear when needed.

Plugin versions

Stay up-to-date by listing more recent plugins (there is another goal for dependencies):

Novelang/$ mvn versions:display-plugin-updates

Show dependency tree:

Novelang/$ mvn dependency:tree

Feed local repository with fresh artifacts

Novelang/$ mvn clean install 

Force child modules version

Force the version of every child module to the one of the parent:

Novelang/$ mvn -N versions:update-child-modules

Performing a release (may be specific to Novelang-0.44.2)

First, clean previous POM backup files:

Novelang/$ mvn release:clean

Then prepare the release. This does the following:

  • Check VCS state. Includes: no uncommitted file; remote repository sync’ed with local.
  • Change the POM versions to release version (shown as M.m.f in the snippet below).
  • Run the build, using declared .
  • Commit changed POMs to local SCM.
  • Tag the SCM locally.
  • Pushes the changes on remote repository, including tags (failing on a conflict).
  • Revert SCM versions to development version.

Novelang/$ mvn -e --batch-mode release:prepare -Drelease=false -DlocalCheckout=true -DreleaseVersion=M.m.f -DdevelopmentVersion=SNAPSHOT -Dtag=release-M.m.f > build-release-prepare.log

This part is likely to fail. If something goes wrong:

  • Reset git in the --hard way, to the version immediately before Maven’s changes.
  • Delete release-M.m.f tag local git repository.
  • Delete release-M.m.f tag on remote git repository: git push -v github :refs/tags/release-M.m.f
  • Force synchronization between local git repository and remote one. This may be done by committing an innocuous change, then pushing it with --force option (better idea, anyone?).
  • Call again: Novelang/$ mvn release:cleanGet sure that’s everything OK with gitk.

Might be useful to reset all POM version (like after some POM or branch hacking): set root pom.xml version to SNAPSHOT and run mvn versions:update-child-modules.

Once this is done, our git repositories contain good, tagged stuff. Last step is to perform the final build.

Novelang/$ mvn release:perform > build-release-perform.log

(There is no additional parameter to pass; the release.prepare did create some POM copies with relevant information.)

The release.perform goal performs a fresh checkout in Novelang/target/checkout where all the pom.xml contain expected M.m.f version. The build calls the deploy:deploy on Novelang-documentation and Novelang-distribution which upload relevant files on SourceForge and send email notifications.

Useful links

Using master password.

Mini-guide about Maven release plugin.

Untested

Resume from a give module folder instead of restarting the build since the beginning:

Novelang/$ mvn reactor:resume -Dfrom=bar 

Novelang-0.44.2 released!

Just released Novelang-0.44.2!

Summary of changes:

  • Another fix for a build problem. Now the deploy:deploy goal should work properly when called from release:perform.

Download it from here.

Enjoy!

Novelang-0.44.1 released!

Just released Novelang-0.44.1!

Summary of changes:

  • Fixed build problem when deploying files and sending annoucements.

Download it from here.

Enjoy!

2010-07-24

Novelang-0.44.0 released!

Just released Novelang-0.44.0!

Summary of changes:

  • Renamed Part into Novella and Book into Opus. Nicer, clearer. New recommended file suffixes are .novella and .opus. Old .nlp and .nlb suffixes still supported.
  • Switched build system from Ant to Maven. This should be transparent for users.

Download it from here.

Enjoy!

2010-06-26

Syntax highlighter for HTML

The SyntaxHighlighter project looks nice. It has a "copy to clipboard" feature (implemented in Flash). With some additional hacking, this would save from keeping Novelang's nasty zero-width spaces added for correct line wrapping.

2010-06-19

Zipper for faster tree modifications

Novelang uses immutable trees to represent a document and transform it. While immutable data structure have well-known advantages, Novelang's tree library requires to update every parent node on each change on any child node. Clever guys found how to save those changes when performing multiple local modifications. This relies on a tree structure called Zipper. Here is a very clear explaination, the original paper (site currently down), the Scala implementation and the Clojure one.

2010-05-30

Google's font directory

This is an amazing initiative from Google: a directory for Web fonts. Fonts are available under SIL Open Font License 1.1. There are some beautiful fonts available, with a nice and clear browsing interface. One can download font sources from here.

2010-04-26

Novelang-0.43.0 released!

Download Novelang-0.43.0 here !
  • Added nohead option to insert command.
  • Fixed some bugs around identifiers.
  • Introduced detection of colliding explicit identifiers. This has no useful purpose for now but will serve as a basis for implementing internal links.
  • Small performance enhancement on HTML document rendering in a Web browser: don’t use JavaScript to set collapsible descriptors hidden.

2010-04-25

MinorThird's Mixup

Could this be useful in Novelang? The Mixup language performs complex queries on pure text. It's "like a regex query, but while regex operates at character level, Mixup operates at token level." Mixup is part of the MinorThird suite and available under BSD license.

2010-04-22

Novelang-0.42.0 released!

Download Novelang-0.42.0 here !
  • Now requires Java 6.
  • New Nhovestone report: Novelang has its own benchmark!
  • Added stylesheet html-FR.xsl for French punctuation.
  • Performance enhancement on rendered HTML page: when containing many tags it should load faster. Instead of dynamically computing styles on the Web browser, HTML rendered by the server directly includes those styles.
  • Various performance enhancements on document generation. With the same amount of memory (-Xmx parameter), Novelang handles documents twice bigger and serves them 20 % faster than previous version. Benchmark ran against version 0.41.0 and 0.38.1. This includes buffered reading of Part files, multithreaded Part rendering, and reduced memory consumption when dealing with AST (Abstract Syntax Tree).

2010-04-05

Nhovestone

“Nhovestone” is the name of Novelang’s dedicated benchmark tool, and also a geeky pun .

Nhovestone aims to highlight performance variations across versions using only a few (carefully selected) measurements:How does response time evolve when increasing the number of documents aggregated in a single Book?How does response time evolve when increasing the size of one single document?

Nhovestone doesn’t try to generate an absolute performance index. This is because such an index makes sense only when computed from always the same source documents and the same hardware.

How it works

Nhovestone focuses on HTML generation using default stylesheet, because HTML is great for fast edit-and-review roundtrips. It uses the Novelist to generate pseudo-random text with a realistic structure. For each benchmarked Novelang version, Nhovestone starts a JVM with a small amount of memory (currently -Xmx32M). With few memory the breaking point appears sooner. Nhovestone increases the size of the source document(s) in a linear fashion, and after each increasing, measures how long takes the call of a Novelang instance.

Performance degradation

Response time start to increase exponentially as document becomes fairly big in regard of available memory. This triggers a lot of CPU-intensive garbage collection consuming a lot of time. Nhovestone detects that a running Novelang HTTP daemon gets “strained” when response time gets above a dynamically-computed threshold. The threshold comes from the straight line drawn from a linear regression on the first half of the measurements, with a slope made steeper by a fixed coefficient. When a response time appears above this straight line, the Novelang HTTP daemon got strained and it’s not worth any further measurement.

Adding Parts

This is the first scenario: for each new measurement, there is an additional Part file. All Parts are more or less equal in size and complexity (including level depth). The graph below shows that performance degradation stays linear until the 300th call. Then, version 0.41.0 starts suffering before older versions. It’s likely that new features require additional memory so starvation occurs sooner.

Increasing the size of the same Part

This is the second scenario: the generated document comes from a single Part file of a size increasing before each call. Each fragment added to the Part has the same size and structure as in the previous test, but all 3 versions show fatigue much sooner (at least 7.5 times). This shows that creating a Part takes much more temporary memory than the finished Part itself.

Tuning

These figures are strongly connected to the volume and the structure of underlying document. Experience shows that small increments generate more measurements (before the fatal strain) and therefore show a more readable trend. They also reduce measurement artefacts that could fool strain detection.

Report generation

JFreeChart generates those graphs. JFreeChart is probably the best charting library for Java at this time, at least on the OSS marketplace. It is stable and highly configurable.

The next step: embed those graphs in a Novelang-generated PDF and publish it as a complement of existing documentation.

2010-03-20

The Novelist: random text generation

Novelang already does all the typesetting for you. What’s next? Writing text, of course! The just-started Novelist subproject, which aims to generate big documents for Novelang testing under heavy load.

Based on French metrics, random text looks like this:

Uomuecto eaufues xuner ig ocanerr, ebanu otpaa. Uuse, on eian aibtd, rttaintlufe elvettarrh, yrn enemlcmlun, ebcazepuer madscg, êiiovemtt teeost eseeerde? Fetn eearréetcs emrseoss icia ntmvesrud. Aoasro cênit ctainetda aèugedet css eali, unero aaie eneoden, nrortio. Oovlod; tfsmenco méttsna, eesdis uoeaeanao rcuent, desungtt av au oneerao, dxuaste umeinétniu lccdeiilne rliùearde veyiritisac yàslu. Iinmseuo odiapqied cmiiapearlo ebnjtus uauueis, libginmasa edrc emaèi sllieyr sode!

It bases on simplistic distribution algorithm. Word count and letter count from uniform distribution in a pre-defined range (something like 5-20 for words and 2-12 for letters). Letters come from a frequency table giving the percentage of appearance for each letter.

While the result doesn’t look much like real text, it’s good enough to stress basic parsing and typesetting.

There has been a lot of research about text analysis, first for cryptography, next for natural language analysis and Web crawling. Among all of them, there is a nifty one: the n-grams , which describe all the different letter sequences of a fixed length in a given text. The demo on Wolfram Alpha is gorgeous. It shows how combinations grow fast: a simple sentence like “ceramics come from” contains 69 3-grams. Google’s n-grams database (ranging from 1-grams to 5-grams) weights 24 GiB gzip’ed and contains near 1 billion of 3-grams. Amazingly, this number doesn’t increase so much for 4-grams and 5-grams.