GHC.Iface.Ext.Utils

One must contain the other. Leaf nodes cannot contain anything

Insert an AST in a sorted list of disjoint Asts

Merge two nodes together.

Precondition and postcondition: elements in nodeType are ordered.

Merge two sorted, disjoint lists of ASTs, combining when necessary.

In the absence of position-altering pragmas (ex: # line "file.hs" 3), different nodes in an AST tree should either have disjoint spans (in which case you can say for sure which one comes first) or one span should be completely contained in the other (in which case the contained span corresponds to some child node).

However, since Haskell does have position-altering pragmas it is possible for spans to be overlapping. Here is an example of a source file in which foozball and quuuuuux have overlapping spans:

module Baz where

# line 3 "Baz.hs"
foozball :: Int
foozball = 0

# line 3 "Baz.hs"
bar, quuuuuux :: Int
bar = 1
quuuuuux = 2

In these cases, we just do our best to produce sensible HieAST's. The blame should be laid at the feet of whoever wrote the line pragmas in the first place (usually the C preprocessor...).

combines and sorts ASTs using a merge sort