3*This document represents our discussions and plans at early stages of
4development, it is no longer being updated.*
6* [Analysis of the existing solutions](#analysis-of-the-existing-solutions)
7 * [Brittany](#brittany)
9 * [Stylish Haskell](#stylish-haskell)
10 * [Haskell formatter](#haskell-formatter)
11* [Proposed design](#proposed-design)
14 * [Printing](#printing)
15 * [Configuration](#configuration)
16 * [Handling of language extensions](#handling-of-language-extensions)
18 * [Functionality of executable](#functionality-of-executable)
19 * [Why not contribute to/fork Hindent or Brittany?](#why-not-contribute-tofork-hindent-or-brittany)
20* [Examples](#examples)
22This document describes design of a new formatter for Haskell source code.
23It also includes recommendations for future implementers.
25We set for the following goals (mostly taken from
26[brittany](https://github.com/lspitzner/brittany)):
27* Preserve the meaning of the formatted functions when no CPP is used;
28* Make reasonable use of screen space;
29* Use linear space and computation time on the size of the input;
33## Analysis of the existing solutions
35In order to design a new formatter we need to study the existing solutions
36so we can borrow the good bits and avoid making the same mistakes.
40[Brittany][brittany] builds on top of [`ghc-exactprint`][ghc-exactprint]—a
41library that uses parser of GHC itself for parsing and thus it guarantees
42that at least parsing phase is bug-free (which is admittedly the cause of
43majority of bugs in other projects, see below).
45After parsing, Haskell AST and a collection of annotations are available.
46The annotations are there because Haskell AST doesn't provide enough
47information to reconstruct source code (for example it doesn't include
48comments). The AST and the annotations are converted into a `BriDoc` value.
49A `BriDoc` value is a document representation like the `Doc` from the
50[pretty][pretty-doc] or the [wl-pprint][wl-pprint-doc] libraries.
52Brittany implements its own document type in an attempt to find a
53satisfactory rendering of the source code that fits a page-width
54constraint. Because of this, a `BriDoc` value represents a collection
55of many candidate layouts (i.e. renderings) of the source code.
57This collection is pruned until it contains a single layout. The
58structure of the chosen layout is then adjusted to leave it in a
59form which can be easily traversed to produce the final rendering.
61Brittany invests the majority of its implementation to manage
62the `BriDoc` values. Given that the amount of possible layouts is
63exponential, the representation is clever enough to fit them in
64linear space. There are multiple ways to build a `BriDoc`, not all
65of which fit in linear space. So care is necessary to keep memory
68The compexities of the `BriDoc` structure, together with the lack of
69documentation, make Brittany at least challenging to maintain.
73[Hindent][hindent] uses [`haskell-src-exts`][haskell-src-exts] for parsing
74like all older projects. `haskell-src-exts` does not use parser of GHC
75itself, and is a source of endless parsing bugs. `Hindent` is affected by
76these upstream issues as well as Stylish Haskell and Haskell formatter (see
77below). This already makes all these projects unusable with some valid
78Haskell source code, but let's continue studying Hindent anyway.
80Hindent is quite different from Brittany in the sense that it does not
81attempt to build a document representation to render
82afterwards, instead it just prints the parsed code straight away. This means
83that the 70-80% of what the code does is a printing traversal.
85Hindent code is easier to read and debug. Pretty-printing functions are
86very straightforward. If there is a bug (in pretty-printer, not in parser
87which Hindent cannot control), it's easy to fix AFAIU.
89Hindent is also notable for its ability to handle CPP and inputs that do not
90constitute complete modules. It splits input stream into so-called “code
91blocks” recognizing CPP macros and then only pretty-prints “normal code”
92without touching CPP directives. After that CPP is inserted between
93pretty-printed blocks of source code. The approach fails when CPP breaks
94code in such a way that separate blocks do not form valid Haskell
96[this](https://github.com/commercialhaskell/hindent/issues/383) for example.
98Looking at the bug tracker there are many bugs. Part of them is because of
99the use of `haskell-src-exts`, the other part is because the maintainer
100doesn't care (anymore?) and doesn't fix them. Well it's as simple as that,
101with any sort of commercial backing the bugs in pretty printer would be
106[Stylish Haskell][stylish-haskell] also uses `haskell-src-exts` and suffers
107from the same upstream problems. I haven't studied the transformations it
108performs, but it looks like it transforms the parsed source code partially
109by manipulating AST and partially by manipulating raw text (e.g. to drop
110trailing whitspace from each line). CPP Macros are just filtered out
111silently as a preprocessing step before feeding the code to
114Stylish Haskell is not so invasive as the other formatters and most reported
115bugs are about parsing issues and CPP. As I understand it, people mostly use
116it to screw their import lists.
120[Haskell formatter][haskell-formatter] is an older project that didn't get
121much traction. It also uses `haskell-src-ext` and also tries to do
122manipulations on the parsed AST. The issue tracker doesn't have many issues
123probably because it never got popular enough (only 15 stars on GitHub). All
124the issues are about upstream problems with `haskell-src-exts`.
128This section describes a solution that combines all the good things from the
133It is clear that `ghc-exactprint` is better than `haskell-src-exts`, so we
134should use that. If we go with `ghc-exactprint` though, we'll need to
135specify which parser to use, e.g. the parser that parses whole module or the
136one which parsers declarations/expressions/etc. It seems that in general
137it's better to use the parser for modules because it should work with all
138input files containing complete modules, while with other parsers it's
139impossible to guess what they'll be called on.
143We allow CPP directives in the input, but we forgo the goal to preserve the
144meaning of the formatted functions in that case.
145Instead of supporting CPP better, we hope for a solution to replace CPP to
146do conditional compilation.
148There are the following challenges when formatting a module with CPP:
150* GHC parser won't accept anything but a valid, complete module. Therefore,
151 formatting the Haskell code between CPP directives is not an option.
153* Ignoring the CPP directives and formatting the Haskell code can change
154 its meaning. An example follows.
156Let's suppose that we want to format the following program:
161main = print (g && f1)
184At the time of this writing, formatting this program with Hindent
185or Ormolu produces the same output we would get if the CPP directives
186were considered comments:
190ormolu 0.0.5.0 HEAD fc64eada5c4da7a5b07d2872e253671b48aec115
191using ghc-lib-parser 8.10.1.20200412
193$ ormolu --mode inplace test.hs
198main = print (g && f1)
221Running the formatter causes the output of the program to change
222from `True` to `False` when `C1` is not defined.
224A solution could be to make the formatter more careful with CPP
225directives, constraining how directives can be inserted in Haskell
226code to avoid changing the meaning by reformatting. But
227this would introduce additional complexity, and the problem would
228need to be solved repeteadly for every tool out there which wants
229to parse Haskell modules. If CPP is replaced with some language
230extension or mechanism to do conditional compilation, all tools
235Just pretty-printing code (following the approach of Hindent) seems sane. It
236is straightforward and when complemented with enough tests (see the section
237about testing below), it should work all right.
239Implementation can be just a `Reader` monad producing something like text
240builder. The context of `Reader` can store current indentation and
241configuration options.
243As the pretty-printing library we can use [`Outputable`][outputable] (and
244`SDoc`) from the [`ghc`][ghc] package itself (at least for pretty-printing
245basic things like floating point literals and the like). The benefit is that
246AST components that we'll want to print are already instances of
247`Outputable`, so we'll get correct renderings for free.
249In order to keep the output of the formatter simple, fast and correct,
250we introduce the following rule. The pretty-printing code can be in
251control of every formatting choice, except for two, which are left to
2541. location of comments (comments are going to be attached to specific
255 syntactic entities, so moving an entity will move its comment too),
258Regarding (2), the idea is that given any syntactic entity, the programmer
2611. write it on one line, or
2622. write it on two lines or more.
264If (1), then everything is kept in one line. If (2), i.e. a line break appears
265somewhere in the concrete syntax tree (CST), then additional line breaks are
266introduced everywhere possible in parent nodes, *but not in any sibling or
283map :: (a -> b) -> [a] -> [b]
285foldr :: (a -> b -> b) ->
306Crucially, no effort is made to fit within reasonable line lengths. That's
307up to the programmer. Style will still be consistent for everyone in every
308other aspect, and that's what counts.
312We are not allowing to configure any aspect of the formatter. A module
313might be used in multiple projects, and we prefer to have it formatted
314the same in all of them.
317post][hindent-5-blog] by Chris Done (the author of Hindent) which says that
318as long as the default style is conventional and good it doesn't really
319matter how code gets formatted. Consistency is more important.
321### Handling of language extensions
323Some language extensions affect how parsing is done. We are going to deal
324with those in two ways:
326* When language pragmas are present in source file, we must parse them
327 before we run the main parser (I guess) and they should determine how the
328 main parsing will be done.
329* There also should be configuration file that may enable other language
330 extensions to be used on all files.
331* Later we could try to locate Cabal files and fetch the list of extensions
332 that are enabled by default from there.
336It should be possible to add tests incrementally as we develop
337pretty-printing code and new issues are discovered. For each Haskell
338module that we want to test, we perform the following steps:
3401. Given input snippet of source code parse it and pretty print it.
3412. Parse the result of pretty-printing again and make sure that AST is the
342 same as AST of original snippet module span positions. We could make
343 this part of a self-check in the formatter.
3443. Check the output against expected output. Thus all tests should include
345 two files: input and expected output.
3464. Check that running the formatter on the output produces the same output
347 again (the transformation is idempotent).
349In order to grow our testsuite, we would borrow test cases from test
350suites of existing libraries like Brittany and Hindent.
351Then we may add test cases for opened issues that Brittany and Hindent have.
353When we're confident enough, we can start “mining” new issues by running
354the program on real source code from Hackage till we don't get new issues
355anymore. For every issue that we find this way, a test case should be added.
357### Functionality of executable
359* In all cases the program should test if the produced AST is the same as
360 the one we originally parsed and if it differs, an error should be
361 displayed suggesting reporting this on our issue tracker.
362* Check mode: return non-zero exit code if any transformations would be
364* Modification in place and printing of formatted code to stdout.
365* A flag for version/commit information.
366* An option to specify location of config file.
367* Options to specify parameters that come from config files on command line
368 instead (currently this is just dynamic options enabled by default, such
369 as langauge extensions).
371### Why not contribute to/fork HIndent or Brittany?
373We want to simultaneously optimize three goals:
3751. simplicity of implementation,
3773. predictable and readable output that doesn't overuse vertical spacing.
379Hindent aims for (1) and (2) by still producing something palatable in (3).
381(1) but goes a long way towards (3) and presumably does OK on (2). Ormolu
382goes for (1), (2) and (3), by outsourcing the hard part of (3) to the user.
383Ormolu is less normative than Brittany, and less normative than Hindent,
384but arguably stills achieves consistent style.
386Forking or contributing to Hindent is not an option because if we replace
387`haskell-src-exts` with `ghc` (or `ghc-exact-print`) then we'll have to work
388with a different AST type and all the code in Hindent will become
389incompatible and there won't be much code to be re-used in that case. It is
390also possible that we'll find a nicer way to write pretty-printer.
394A list of formatting examples can be found [here](data/examples).
396[brittany]: https://hackage.haskell.org/package/brittany
397[hindent]: https://hackage.haskell.org/package/hindent
398[hindent-5-blog]: https://chrisdone.com/posts/hindent-5
399[stylish-haskell]: https://hackage.haskell.org/package/stylish-haskell
400[haskell-formatter]: https://hackage.haskell.org/package/haskell-formatter
401[ghc]: https://hackage.haskell.org/package/ghc
402[outputable]: https://hackage.haskell.org/package/ghc-8.4.3/docs/Outputable.html
403[haskell-src-exts]: https://hackage.haskell.org/package/haskell-src-exts
404[ghc-exactprint]: https://hackage.haskell.org/package/ghc-exactprint
405[hindent-printer]: https://github.com/commercialhaskell/hindent/blob/master/src/HIndent/Pretty.hs
406[pretty-doc]: http://hackage.haskell.org/package/pretty-1.1.3.6/docs/Text-PrettyPrint.html#t:Doc
407[wl-pprint-doc]: http://hackage.haskell.org/package/wl-pprint-1.2.1/docs/Text-PrettyPrint-Leijen.html#t:Doc
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list