[Groff] Knuth-Plass Algorithm

[Bertrand Garrigues]

Hi all,

(changing the title, was: It is time to modernise "groff")

On Wed, Nov 08 2017 at 06:39:03 PM, Ingo Schwarze <address@hidden> wrote:
> Gour wrote on Wed, Nov 08, 2017 at 05:57:00PM +0100:
>
>> Here I'd like to ask what has happened in the meantime in regard to
>> the groff's features and plans stated in the mission statement like
>> Knuth-Plass algorithmy for paragraph-based linebreaks, native support
>> for TrueType, Open Type, and other non-Type1 PostScript fonts, and
>> improving Unicode support ?  
>
> Nothing.  Setting up a mission statement has little practical effect
> when no working time is available.

Hmm... Bug #40716 "UPGRADE: format a paragraph as a whole rather than
line by line" is assigned to me, it's time to publish some of my work...

I've started to work on Knuth-Plass algorithm last year, I've written
some code to implement this algorithm but for the moment it's not
connected yet to the rest of the `troff' code.  The core files of
`troff' (node.cpp, div.cpp, env.cpp) are quite large with some
inconsistencies that need to be cleaned (for example vertical_size_node
methods are not in node.cpp but in div.cpp -- presumably due to header
inclusion issues).  A part from the formatting algorithm there are other
complications, for example on a diversion the current partially filled
line is included into the diversion, which will confuse a
paragraph-oriented algorithm when you end the diversion.  I've made
several tries but for the moment it's inconclusive (I haven't worked on
it recently).

I've just pushed a dev branch `format_knuth_plass' with part of my work,
it includes a standalone test that uses my code with Knuth's original
example from "Digital Topography" (If you are interested by the
algorithm but don't have a copy of this book you can check this link
http://defoe.sourceforge.net/folio/knuth-plass.html -- although there
are a few mistakes in the demerits calculation).

To use this dev branch and play with the test:

  git clone https://git.savannah.gnu.org/git/groff.git
  cd groff
  git checkout --track origin/format_knuth_plass
  ./bootstrap
  mkdir build
  cd build
  ../configure
  make -j
  make check
  ./test_paragraph

Attached the result of `./test_paragraph -s 1 -t 1' which run only the
test 1 of suite1 -- the original Knuth example.  It shows, for each
line, the candidate breakpoints (with a `^' sign) and the calculation
of adjustement ratio and total demerits (which all correspond to the
numbers in the example from Knuth's paper).

I've also added a few things:

- Support of C++ unit test framework cppunit.

- An implementation of doubled linked list in "linux kernel" style (to
  stay in the style of "C with classes" rather than real C++, and
  because, well, they are familiar to me).

Of course there is still a lot of work, and these changes are not for
the next release (Still not ready to really work on it as people from
GNU haven't granted me the rights to upload tarballs into the GNU ftp
yet, but I hope this release will be completed before the end of the
year).

Regards,

Bertrand Garrigues

suite1_test1.txt
Description: Text document