Fix wrong indentation from Text.PrettyPrint.HughesPJ fill (fcat and fsep)

[thorkilnaur]

This program:

import Text.PrettyPrint.HughesPJ

f z doc = renderStyle
            (
              Style {
                mode = PageMode,
                lineLength = z,
                ribbonsPerLine = 1.0
              }
            )
            doc

l2 = f 6 $ nest 3 $
       fcat [nest 1 $ text "a", nest 2 $ text "b", text "c"]

main = putStr (l2 ++ "\n")

produces this output:

$ runghc pp2.hs | tr ' ' .
....ab
.c
$

The expected output is:

....ab
...c

where the c is placed below and 1 position to the left of the a.

As I understand the situation, the problem is that in a fill (used by fsep and fcat), the total indentation of all the documents placed on one line is used to determine the indentation of the next line where only the indentation of the first document should be used. Thus, in the example, the c is placed 1+2=3 positions to the left of the a which is 2 too many.

I have attached a patch with a suggested solution. I have also attached a patch that adds a suitable test case.

Note: This problem is also present in GHC's Pretty library and is the reason for the bad formatting reported in #1176. Once the present problem has been fixed, I intend to go back to #1176 and fix that in a similar manner.

[thorkilnaur]

Fix of wrong indentation from HughesPJ fill (fcat and fsep)

[thorkilnaur]

pp2: Test fix of wrong indentation from HughesPJ fill (fcat and fsep)

[thorkilnaur]

Please look at this when convenient and decide what should be done.

Best regards Thorkil

[simonpj]

Thank you very much for looking into this Thorkil. It is now several years since I wrote that code, and it is fully paged out of my cache. That makes you the current expert!

Suggestion:

• While it's still in your cache, make a dozen or so evil tests.
• Implement your fix in GHC's pretty-print module and check that it doesn't make GHC's current output go pear-shaped. (E.g. run the test suite and compare output.)

If it looks as if there are no regressions, then let us know and we'll commit your patches.

Incidentally, there's a comment in Text.PrettyPrint.HughesPJ:

-- Specification: 
--   fill []  = empty
--   fill [p] = p
--   fill (p1:p2:ps) = oneLiner p1 <#> nest (length p1) 
--                                          (fill (oneLiner p2 : ps))
--                     `union`
--                      p1 $$ fill ps

If you change the code, could you change the comment, if appropriate. And could you add a comment or two to explain the importance of your call to oneLinerNB instead of oneLiner. These things are all too easily forgotten!

Simon

[thorkilnaur]

Thank you, I'll try to do that. In view of the level of correctness of the comment that you quote (note the missing occurrence of p2 in the second operand of the `union`), I should have a fair chance of at least not making things worse (ho ho).

Unless otherwise directed, I will assume that it is OK to add test cases to testsuite/tests/ghc-regress/lib/PrettyPrint following the lead from trac #1062.

I would like to mention a consequence of correcting fill as suggested which may cause surprise and which I therefore better discuss early. As described, I understand the basic idea of fill to be such that

fill g [x0, x1, ..., xn] = ( ... (x0 `p1` x1) `p2` ... ) `pn` xn

where each pi is either one of <> and <+> (depending on g) or $$ so that the lines fill nicely. Thus, the example that I gave:

nest 3 $ fcat [nest 1 (text "a"), nest 2 (text "b"), text "c"]

evaluates to:

nest 3 $ (nest 1 (text "a") <> nest 2 (text "b")) $$ text "c"

leading to the c indented one position to the left of the a. Consider now:

nest 3 $ text "|" <> (fcat [nest 1 (text "a"), nest 2 (text "b"), text "c"])

where a | has been concatenated in front of the fcat. This, of course, causes the nest 1 of the a to be eliminated, but the relative position of the ab and the c on the next line is retained, leading to this output:

...|ab
...c

What may be surprising is that the c, part of the fcat list, doesn't stay to the right of the |. To avoid such surprises, nesting of things that get placed in fills should perhaps be avoided.

And nesting of things that are later filled is what causes the problematic behaviour reported in trac #1176: In compiler/hsSyn/HsExpr.lhs, we find:

    pp_infixly v
      = sep [nest 2 pp_e1, pprInfix v, nest 2 pp_e2]

for pretty-printing an expression with infix operator. When this is combined with the compiler/utils/Outputable.lhs code for pretty-printing lists of Outputable things (here is the fsep that calls the fill):

instance (Outputable a) => Outputable [a] where
    ppr xs = brackets (fsep (punctuate comma (map ppr xs)))

called from compiler/typecheck/TcExpr.lhs that says:

funAppCtxt fun arg arg_no
  = hang (hsep [ ptext SLIT("In the"), speakNth arg_no, ptext SLIT("argument of"),
                    quotes (ppr fun) <> text ", namely"])
         4 (quotes (ppr arg))

we get the filling of nested things.

The suggested correction of fill will prevent the incorrect wandering off of the left margin to minus infinity. But it will not prevent the (perhaps surprising) layout of filled things that start with something nested. In the case of compiler/hsSyn/HsExpr.lhs, the potential surprise may be prevented by writing:

    pp_infixly v
      = sep [pp_e1, nest (-2) $ pprInfix v, pp_e2]

instead of the code actually used, but that, of course, affects the result of using this code in circumstances that are nested to a level less than 2.

Best regards Thorkil

[thorkilnaur]

The attached patch extends the testsuite for the HughesPJ library, preparing for the actual change of the library. The extended testsuite uses a simple coverage analysis mechanism to automate some of the work needed to come up with a useful testsuite.

The patch has been tested on Mac OS X and x86 (SuSE) Linux. I have not been able to run successful validates in neither of these environments recently, but the present patch touches the HughesPJ testsuite only, so I consider the risk minimal.

This is only a partial step on the way to fix the actual issue, but I would be most grateful to get some comments to this testsuite patch.

Thanks a lot and best regards Thorkil

[thorkilnaur]

Patch with HughesPJ tests with automated high-level coverage check

[simonmar]

Thorkil - can you give us an update on this one? Is it clear what needs to be done and/or are you waiting for anything from us?

[thorkilnaur]

I discussed this briefly with Simon PJ at the ICFP, so I believe I know what to do next.

Best regards Thorkil

[benedikt]

Another simple testcase demonstrating the bug

[benedikt]

Thorkil's patch seems to be correct.

The patch bundle in #2393 achieves the same effect, namely eliding nests in the p2 argument of the left layout of fill:

fillIndent k (p1:p2:ps) =
    oneLiner p1 <g> fillIndent (k + length p1 + length g) (elide_nests (oneLiner p2) : ps)
     `Union`
   (p1 $*$ nest (-k) (fillIndent 0 ps)) 

The Bug1176a.hs attachment is yet another demonstration of the problem.

As thorkil noted above, a correct implementation shouldn't use (fsep . punctuate comma $ xs) if some elements of xs are such, that their first lines aren't leftmost in all layouts - this is a user error.

[igloo]

Fixed as part of #2393.