sort-refgraph-api.md

AST.Expression.Canonical

We add the Facts type and field. freeVariables stores all variables which the given definitions right-hand-side references, which are not themselves defined somewhere in the RHS. Recursive values should note that they refer to themselves.

data Def
    = Definition Facts Pattern.CanonicalPattern Expr (Maybe (A.Located Type.Canonical))
    deriving (Show)


data Facts =
  Facts
    { freeVariables :: [Var.Canonical]
    } deriving (Eq, Ord, Show)

Canonicalize.Sort

Our nodes are just variables. We define a type MaybeLambda, which determines whether a variable x refers to y across a lambda boundary, or directly.

data MaybeLambda = Lambda | Direct

type Node = Var.Canonical

We can use the existing reorder function, though we need to keep two context arguments.

The Let case of reorder is also where we'll add the referenced nodes to the Facts for a Def.

The var set "context" argument is the set of variables which were defined since the last time we entered a Lambda expression, whose references we will mark as Direct.

Instead of a set of strings, in our state we store a map containing the variables we refer to as keys, with the values being whether the reference is over a Lambda or not. If any references are direct, we store Direct in the Map.

Since we also want information about external references, we store Var.Canonicals instead of Strings.

We also add [(String, Region)] to our state, so that error information about infinite recursion can make its way up to a function which is in the Result monad.

reorder :: (Set.Set Var.Canonical) -> Canonical.Expr -> State (Data.Map Var.Canonical MaybeLambda, [(String, Region)]) (Canonical.Expr

buildDefGraph
    :: [Canonical.Def]
    -> State (Data.Map Var.Canonical MaybeLambda, [(String, Region)]) [(Canonical.Def, Int, [Int])]
    
reorderAndGetDependencies
    :: Canonical.Def
    -> State (Data.Map Var.Canonical MaybeLambda, [(String, Region)]) (Canonical.Def, [Var.Canonical])

Once we have reordered a Let statement, we want to check if there are any nodes which refer to themselves, not through funtions.

findCycles returns a list of variable-dependence cycles. When generating error messages, we only want the variable names, and their region in the code.

removeFunctionEdges :: Graph -> Graph

findCycles :: Graph -> [[(String, Region)]]

addCycleErrors 
  :: [[(String, Region)]] 
  -> State (Data.Map Var.Canonical MaybeLambda, [(String, Region)]) ()

--Called from Canonicalize.hs
doCycleErrors
  :: [(String, Region)]
  -> R.Result Warning.Warning Error.Error ()  

The values stored in Canonical.Def can be used for dead-code elimination, and unused top-level warnings, later on.

In the future, more types of nodes could be added to the Node type, allowing for unused variable warnings, inlining, etc.