Opened 16 months ago

Last modified 6 weeks ago

#15495 new task

Handling Source Locations via TTG

Reported by: Shayan-Najd Owned by:
Priority: normal Milestone:
Component: Compiler Version:
Keywords: Cc: alanz, simonpj, bgamari
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D5036
Wiki Page:

Description

Problem

The current implementation of TTG HsSyn AST in GHC stores source locations for terms of a datatype Exp in a separate wrapper datatype LExp which is mutually recursive with Exp such that every recursive reference to Exp is done indirectly, via a reference to the wrapper datatype LExp (see the example code below). We refer to this style of storing source locations as the ping-pong style.

Besides the indirection and the resulting complications of the ping-pong style, there are two key problems with it:

  1. It bakes-in the source locations in the base TTG AST, forcing all instances to store source locations, even if they don't need them.For example, TH AST does not carry source locations, or even within GHC, there are generated terms without source locations.
  1. It results in a form of conceptual redundancy: source locations are tree decorations and they belong in the extension points. (see https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow/TreesThatGrowGuidance TTG Guidance])

Solution

We can move the source location decorations to a wrapper constructor and remove the ping-pong style. This can be done smoothly, mechanically, and gradually by using a getter/setter methods for source locations. More details can be found at the related wiki page.

Change History (7)

comment:1 Changed 16 months ago by simonpj

Branch wip/az-D5036 I believe.

comment:2 Changed 16 months ago by alanz

I am still looking for the haddock changes though.

comment:3 Changed 14 months ago by simonpj

Differential Rev(s): Phab:D5036

comment:4 Changed 14 months ago by alanz

The buildable version, with haddock changes, is at wip/az-D5036-2. It has also been rebased to master of 2 days ago.

comment:5 Changed 13 months ago by Shayan-Najd

The latest validated version is at wip/shnajd-TTG-SrcLocs in both https://github.com/shayan-najd/ghc and https://github.com/shayan-najd/haddock

comment:6 Changed 13 months ago by Alan Zimmerman <alan.zimm@…>

In 509d5be6/ghc:

[TTG: Handling Source Locations] Foundation and Pat

This patch removes the ping-pong style from HsPat (only, for now),
using the plan laid out at
https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow/HandlingSourceLocations (solution
A).

- the class `HasSrcSpan`, and its functions (e.g., `cL` and `dL`), are introduced
- some instances of `HasSrcSpan` are introduced
- some constructors `L` are replaced with `cL`
- some patterns `L` are replaced with `dL->L` view pattern
- some type annotation are necessarily updated (e.g., `Pat p` --> `Pat (GhcPass p)`)

Phab diff: D5036
Trac Issues #15495

Updates haddock submodule

comment:7 Changed 6 weeks ago by Marge Bot <ben+marge-bot@…>

In 182b1199/ghc:

Separate `LPat` from `Pat` on the type-level

Since the Trees That Grow effort started, we had `type LPat = Pat`.
This is so that `SrcLoc`s would only be annotated in GHC's AST, which is
the reason why all GHC passes use the extension constructor `XPat` to
attach source locations. See #15495 for the design discussion behind
that.

But now suddenly there are `XPat`s everywhere!
There are several functions which dont't cope with `XPat`s by either
crashing (`hsPatType`) or simply returning incorrect results
(`collectEvVarsPat`).

This issue was raised in #17330. I also came up with a rather clean and
type-safe solution to the problem: We define

```haskell
type family XRec p (f :: * -> *) = r | r -> p f
type instance XRec (GhcPass p) f = Located (f (GhcPass p))
type instance XRec TH          f =          f p
type LPat p = XRec p Pat
```

This is a rather modular embedding of the old "ping-pong" style, while
we only pay for the `Located` wrapper within GHC. No ping-ponging in
a potential Template Haskell AST, for example. Yet, we miss no case
where we should've handled a `SrcLoc`: `hsPatType` and
`collectEvVarsPat` are not callable at an `LPat`.

Also, this gets rid of one indirection in `Located` variants:
Previously, we'd have to go through `XPat` and `Located` to get from
`LPat` to the wrapped `Pat`. Now it's just `Located` again.

Thus we fix #17330.
Note: See TracTickets for help on using tickets.