GNU bug report logs - #61028
30.0.50; [PATCH] [FEATURE] Balanced fill mode

Previous Next

To reply to this bug, email your comments to 61028 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Andrew Kensler <andrew <at> eastfarthing.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 30.0.50; [PATCH] [FEATURE] Balanced fill mode
Date: Mon, 23 Jan 2023 01:40:40 -0800

[Message part 1 (text/plain, inline)]

Greetings all,

The proposed patch attached adds a new minor balanced-fill-mode with an 
alternate line breaking algorithm for paragraph filling.  When enabled, 
it will try to neatly balance line lengths to reduce raggedness, avoid 
widows, avoid starting a new sentence on the last word of a line, avoid 
ending a sentence on the first word of a line, and so forth.  It is 
heavily inspired by the Knuth-Plass line breaking algorithm and uses 
dynamic programming to try to choose line breaks to minimize a cost 
function.

For example, consider the following mock paragraph as filled by the 
current greedy algorithm with the fill-column set to 15:

Ccc ccc a bb
dddd bb bb a
ccc a
jjjjjjjjjj a
eeeee a
hhhhhhhh bb
dddd.

With the new minor mode enabled, it would instead be filled much more 
nicely as:

Ccc ccc a
bb dddd bb
bb a ccc a
jjjjjjjjjj
a eeeee a
hhhhhhhh
bb dddd.

Often, the result is similar to simply having used a particular slightly 
narrower fill-column with the current greedy algorithm.  The advantage, 
however, is that it figures out the correct column automatically and 
per-paragraph.

The main piece of implementation is in the new 
(balanced-fill-break-lines) function in fill.el, with a modification to 
(fill-region-as-paragraph) to optionally call this before its current 
line breaking loop.  If it runs successfully, then point will be set to 
the end of the paragraph and that loop skipped.

Note that (fill-region-as-paragraph) has no hooks and is too monolithic 
to advise for this kind of thing, hence my hoping to upstream this change.

This is my first time contributing anything significant to Emacs or 
writing here.  I believe that the proposed patch covers all the major 
needs: the code itself, commit message, info documentation, announcement 
in NEWS, and a basic ERT test.  If there's anything I've missed or 
suggestions for improvements, please let me know. (And I hope this is 
the correct mailing list and message format, too.)  I'll be happy to 
sign the copyright assignment paperwork if this looks like something 
you'd like to accept.

Cheers,
- Andrew

[Message part 2 (text/html, inline)]

[0001-Add-new-minor-balanced-fill-mode-to-filling.patch (text/x-patch, attachment)]

Message #8 received at 61028 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Andrew Kensler <andrew <at> eastfarthing.com>
Cc: 61028 <at> debbugs.gnu.org
Subject: Re: bug#61028: 30.0.50; [PATCH] [FEATURE] Balanced fill mode
Date: Mon, 23 Jan 2023 17:34:48 +0200

> Date: Mon, 23 Jan 2023 01:40:40 -0800
> From: Andrew Kensler <andrew <at> eastfarthing.com>
> 
> The proposed patch attached adds a new minor balanced-fill-mode with an alternate line breaking algorithm
> for paragraph filling.  When enabled, it will try to neatly balance line lengths to reduce raggedness, avoid
> widows, avoid starting a new sentence on the last word of a line, avoid ending a sentence on the first word
> of a line, and so forth.  It is heavily inspired by the Knuth-Plass line breaking algorithm and uses dynamic
> programming to try to choose line breaks to minimize a cost function.
> 
> For example, consider the following mock paragraph as filled by the current greedy algorithm with the
> fill-column set to 15:
> 
> Ccc ccc a bb
> dddd bb bb a
> ccc a
> jjjjjjjjjj a
> eeeee a
> hhhhhhhh bb
> dddd.
> 
> With the new minor mode enabled, it would instead be filled much more nicely as:
> 
> Ccc ccc a
> bb dddd bb
> bb a ccc a
> jjjjjjjjjj
> a eeeee a
> hhhhhhhh
> bb dddd.
> 
> Often, the result is similar to simply having used a particular slightly narrower fill-column with the current
> greedy algorithm.  The advantage, however, is that it figures out the correct column automatically and
> per-paragraph.
> 
> The main piece of implementation is in the new (balanced-fill-break-lines) function in fill.el, with a modification
> to (fill-region-as-paragraph) to optionally call this before its current line breaking loop.  If it runs successfully,
> then point will be set to the end of the paragraph and that loop skipped.
> 
> Note that (fill-region-as-paragraph) has no hooks and is too monolithic to advise for this kind of thing, hence
> my hoping to upstream this change.
> 
> This is my first time contributing anything significant to Emacs or writing here.  I believe that the proposed
> patch covers all the major needs: the code itself, commit message, info documentation, announcement in
> NEWS, and a basic ERT test.  If there's anything I've missed or suggestions for improvements, please let
> me know.  (And I hope this is the correct mailing list and message format, too.)  I'll be happy to sign the
> copyright assignment paperwork if this looks like something you'd like to accept.

Thanks, I think this is a welcome feature.  Please see a few comments
below.  I will send you the form for copyright assignment off-list.

> +@node Balanced Fill
> +@subsection Balanced Filling

I find this subsection too detailed and lengthy.  I'm not sure we want
to describe all the customizable options that users can customize,
just the main ones.  Assuming the default values are chosen well,
chances are that most users will not need to customize too many of
them, and therefore the manual doesn't have to describe them; we just
need to mention that several more options are available, and perhaps
have a special group for them for easier discoverability.  WDYT?

My other concern about the documentation is that it seems to describe
the feature in a way that is too technical and uses terminology from
the field of optimizations.  I'm afraid that users without background
in optimizations will have difficulty understanding some of the
options.  Can you try describing this in a less formal manner, so as
to make it easier to understand?

> +  For example, if @code{fill-column} is 60 and balanced filling is
> +disabled then the greedy algorithm will fill the following paragraph
> +like so:
> +
> +@smallexample
> +"It's not too far-fetched to say that the best programs are
> +the ones written when the programmer is supposed to be
> +working on something else...  Very good things happen when
> +management is enlightened enough to appreciate the
> +importance of allowing programmers some free time for
> +projects of this sort."  --Melinda Varian
> +@end smallexample
> +
> +@noindent
> +while enabling the balanced filling will instead produce the following
> +with slightly shorter but more even line lengths:
> +
> +@smallexample
> +"It's not too far-fetched to say that the best programs
> +are the ones written when the programmer is supposed to
> +be working on something else...  Very good things happen
> +when management is enlightened enough to appreciate the
> +importance of allowing programmers some free time for
> +projects of this sort."  -- Melinda Varian
> +@end smallexample

This example is too long.  I suggest to find a shorter one.  I think
an example with 3 lines should be enough to explain the feature.

> --- a/etc/NEWS
> +++ b/etc/NEWS
> @@ -53,6 +53,12 @@ trash when deleting.  Default is nil.
>  
>  * Editing Changes in Emacs 30.1
>  
> +** Filling can now try to break lines evenly.
> +The new user option 'balanced-fill-mode' can be set to non-nil to
> +make filling consider the entire paragraph at a time and try to
> +place line breaks optimally to look more neat and even, according
> +to a cost function.  This is inspired by the Knuth-Plass algorithm.

This should mention at least a few main options that control the
feature.

> +(define-minor-mode balanced-fill-mode
> +  "Toggle whether filling should try to neatly balance line lengths.
> +
> +When enabled, filling will consider the entire paragraph and
> +try to optimally choose a set of line breaks to minimize a
> +cost function that penalizes untidy paragraphs.  This may
> +place line breaks sooner than necessary if it improves later
> +lines.  When disabled, filling uses the traditional greedy line
> +breaking algorithm.

Likewise here: this doc string is too abstract and thus hard to grok.
Talking about minimization of a cost function that penalizes something
only helps if one has some background in that domain.  I'd instead try
to say something like "fills the entire paragraph avoiding too short
lines" or something similar.

> +(defcustom balanced-fill-maximum-words 500
> +  "Maximum limit on the number of words that the balanced fill
> +algorithm will attempt to process in a single paragraph.  If

The first line of a doc string should be a single complete sentence
(here and elsewhere in the patch).  This is important because the
various "apropos" commands show only the first line of the doc string.

> +(defcustom balanced-fill-length-exponent 3
> +  "Controls the penalty for lines that are shorter or longer than
> +the target length to the margin.  The difference between the
> +actual and target length will be raised to this power when
> +calculating the cost of a potential line break.  This is the
> +main control for the cost function."
> +  :version "30.1"
> +  :type 'integer
> +  :group 'fill)
> +
> +(defcustom balanced-fill-raggedness-penalty 40
> +  "Additional penalty for each column of difference in length
> +relative to the previous line, unless this is the last line
> +and longer than second to last.  Higher numbers make it try
> +harder to keep all lines as even as possible in length at the
> +expense of other factors."
> +  :version "30.1"
> +  :type 'integer
> +  :group 'fill)
> +
> +(defcustom balanced-fill-single-penalty 150
> +  "Additional penalty either for starting a new sentence with a
> +single word right at the end of a line, or else for ending a
> +sentence with a single word left at the start of a line."
> +  :version "30.1"
> +  :type 'integer
> +  :group 'fill)
> +
> +(defcustom balanced-fill-break-penalty 50
> +  "Additional penalty for each line break added.  The larger this
> +is, the more the algorithm will try to minimize the number of
> +lines despite the other penalties."
> +  :version "30.1"
> +  :type 'integer
> +  :group 'fill)

These options are probably related, in that changing one needs a
suitable change in others to make sense.  If this is indeed so, please
mention the relations in the doc strings.  You say "Additional", but
that is meaningless when each doc string is read separately
(additional to what?)

> +(defun balanced-fill-break-lines (from to justify)
> +  ;; Build a table of visible word widths, with and without any preceding
> +  ;; spaces, along with whether the word starts a new sentence.  We go by
> +  ;; columns and not chars to handle invisible text (especially invisible
> +  ;; spaces), etc.

If this is an internal function, please use our convention of naming
it with double dash, as in balanced-fill--break-lines.  If this is
supposed to be a public function, it should have a doc string.

Last, but not least: what about performance?  Is this performant
enough to apply to large enough paragraphs, including via
auto-fill-mode?  Can you provide some measurements?

Thanks.

Message #11 received at 61028 <at> debbugs.gnu.org (full text, mbox):

From: Andrew Kensler <andrew <at> eastfarthing.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 61028 <at> debbugs.gnu.org
Subject: Re: bug#61028: 30.0.50; [PATCH] [FEATURE] Balanced fill mode
Date: Mon, 13 Feb 2023 00:27:10 -0800

[Message part 1 (text/plain, inline)]

A revised patch is attached.  Replies follow inline.

On 1/23/23 7:34 AM, Eli Zaretskii wrote:
> Thanks, I think this is a welcome feature.  Please see a few comments
> below.  I will send you the form for copyright assignment off-list.
Signed and sent.
> I find this subsection too detailed and lengthy.  I'm not sure we want
> to describe all the customizable options that users can customize,
> just the main ones.  Assuming the default values are chosen well,
> chances are that most users will not need to customize too many of
> them, and therefore the manual doesn't have to describe them; we just
> need to mention that several more options are available, and perhaps
> have a special group for them for easier discoverability.  WDYT?

I have significantly trimmed this subsection of the manual.

I agree about the special group.  The options related to balanced fill 
mode have now been collected in their own 'balanced-fill customization 
group, which is a child of the main 'fill group. (Note that the other 
existing options in fill.el are now explicitly placed in the 'fill group 
rather than relying on implicit ordering relative to the last group 
definition.)  This subsection of the manual now tells how to customize 
the 'balanced-fill group, rather than listing all of the options 
individually.

I have also renamed several of the options to better imply their 
relation; the ones that directly contribute (or are an exponent on a 
value that contributes) to the total score being optimized now all end 
in -penalty, for example.

> My other concern about the documentation is that it seems to describe
> the feature in a way that is too technical and uses terminology from
> the field of optimizations.  I'm afraid that users without background
> in optimizations will have difficulty understanding some of the
> options.  Can you try describing this in a less formal manner, so as
> to make it easier to understand?

I have tried to move the focus of the documentation for this feature 
away from the technical details of the implementation and more towards a 
description of the effects.

> This example is too long.  I suggest to find a shorter one.  I think
> an example with 3 lines should be enough to explain the feature.

I have changed the manual subsection to use a much shorter example.  It 
is a bit longer than 3 lines, but that is because it uses a fill-width 
of 20.  However, this gave me room to put the examples with and without 
this feature side-by-side.

> This should mention at least a few main options that control the
> feature.

In the NEWS announcement, I have added a reference to the new 
customization group.

> Likewise here: this doc string is too abstract and thus hard to grok.
> Talking about minimization of a cost function that penalizes something
> only helps if one has some background in that domain.  I'd instead try
> to say something like "fills the entire paragraph avoiding too short
> lines" or something similar.

I have updated the doc string on the minor mode here, as well as the 
other doc strings to remove the mentions of minimizing a cost function.  
In this case, I went with "When enabled, filling will try to optimally 
choose a set of line breaks to make a paragraph look tidier by 
considering the entire paragraph at a time.  This may place line breaks 
sooner than necessary if it improves later lines."

> The first line of a doc string should be a single complete sentence
> (here and elsewhere in the patch).  This is important because the
> various "apropos" commands show only the first line of the doc string.
Good point!  This might be worth a reminder under the "Documenting your 
changes" section of the CONTRIBUTE guide where it mentions doc-strings.
> These options are probably related, in that changing one needs a
> suitable change in others to make sense.  If this is indeed so, please
> mention the relations in the doc strings.  You say "Additional", but
> that is meaningless when each doc string is read separately
> (additional to what?)

That's a fair point.  Each of the options now that contributes to the 
scoring now ends in -penalty and is a member of the 'balanced-fill 
customization group.  I have also updated the doc strings to mention 
that these values are about the prioritization of some aspect of the 
appearance of the paragraph relative to the other penalties.  Hopefully 
that is more clear now.  I have removed the "Additional" language.

> If this is an internal function, please use our convention of naming
> it with double dash, as in balanced-fill--break-lines.  If this is
> supposed to be a public function, it should have a doc string.

I have renamed it to use the double dash.  I had originally been trying 
to match it to the existing code in fill.el, which doesn't seem use that 
convention.  But I also realize that that code may predate that 
convention and you wouldn't have wanted to rename it and risk breaking 
any user code relying on it.  No need for new code to be bound by that, 
though.

> Last, but not least: what about performance?  Is this performant
> enough to apply to large enough paragraphs, including via
> auto-fill-mode?  Can you provide some measurements?

That's a fair question.  That is why I had added the 
balanced-fill-word-limit option to restrict this to small to medium 
paragraphs.  But to test the performance, I have written a small 
benchmark (see attached) that creates temporary buffers with 
successively larger copies of the common "Lorem ipsum" paragraph, all on 
on line, and measures the time to fill it.  Here are timings that I got 
from it on my 10-year old machine at a few key sizes, with and without 
nativecomp:

Without nativecomp:
  For 69 words:
    greedy fill   -- 0.000216s
    balanced fill -- 0.001203s
  For 483 words:
    greedy fill   -- 0.001201s
    balanced fill -- 0.023777s
  For 2001 words:
    greedy fill   -- 0.005144s
    balanced fill -- 0.341215s
With nativecomp:
  For 69 words:
    greedy fill   -- 0.000190s
    balanced fill -- 0.000991s
  For 483 words:
    greedy fill   -- 0.001086s
    balanced fill -- 0.021680s
  For 2001 words:
    greedy fill   -- 0.004645s
    balanced fill -- 0.316352s

Note that for this benchmark, I had raised the balanced-fill-word-limit 
option so that it would test the new balanced fill algorithm, even at 
larger sizes.  With its current default of the 500 word limit, the 
timings for the 2001 words tests when balanced fill mode was enabled 
were around ~0.5ms since it would fall back to the greedy fill 
algorithm.  Thus the maximum time with this minor mode enabled and the 
default word limit would be about ~2.5ms on this machine for a 500 word 
paragraph.

Hopefully this new revision addresses your major critiques from before.  
I'm happy to refine it further if you still have reservations or spot 
anything else.

[0001-Add-new-minor-balanced-fill-mode-to-filling.patch (text/x-patch, attachment)]

[benchmark-fill.el (text/x-emacs-lisp, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.