graph_algs.txt

-- Pseudocode for collapsing a syntax graph.

-- New stateful algorithm

-- Note: Node refers to the FGL node, which is just an integer. The node label has to be looked up separately in the graph.
-- The node label has all of the information about the node such as what SyntaxNode it represents.

collapseRoots treeRoots = foldl' (collapseTree treeRoots)

collapseNodes :: SyntaxGrrah -> SyntaxGraph
collapseNodes originalGraph = finalGraph where
  -- findTreeRoots returns a list of nodes that will embed other nodes, but are not embedded themselves.
  -- These nodes are thus each a root of a collapsed node tree.
  treeRoots = findTreeRoots originalGraph
  -- Now collapse each tree of nodes
  finalGraph = collapseRoots treeRoots originalGraph treeRoots

-- |findTreeRoots returns a list of nodes that might embed other nodes, but are not embedded themselves.
-- These nodes are thus each a root of a collapsed node tree.
-- A node is a treeRoot if all of these conditions are true:
-- 1. The SyntaxNode can embed other nodes (i.e. nodeCanEmbed is true)
-- 2. The node has at least one parent that can not embed (i.e. the node has a parent where nodeCanEmbed is false.)
-- Note: A treeRoot may not actually have any embeddable children, since collapseTree will do nothing in that case.
findTreeRoots :: SyntaxGraph -> [Node]
-- filterNodes is a library function that returns a list of the nodes in the graph
-- where the filter function is true.
-- filterNodes :: (Node -> Bool) -> Graph -> [Node]
findTreeRoots graph = filterNodes (isTreeRoot graph) graph

isTreeRoot :: SyntaxGraph -> Node -> Bool
isTreeRoot graph node = graphNodeCanEmbed graph node && hasAParentThatCannotEmbed where
  hasAParentThatCannotEmbed = not $ null parentsThatCannotEmbed
  parentsThatCannotEmbed = filter (graphNodeCanEmbed graph) (findParents graph node)

findParents :: Graph -> Node -> [Node]
findParents = _ -- TODO

graphNodeCanEmbed :: Graph -> Node -> Bool
graphNodeCanEmbed graph node = syntaxNodeCanEmbed $ lookupSyntaxNode graph node

lookupSyntaxNode :: SyntaxGraph -> Node -> SyntaxNode

collapseTree :: [Node] -> SyntaxGraph -> Node -> SyntaxGraph
collapseTree treeRoots oldGraph rootNode = case childrenToEmbed of
  [] -> oldGraph
  _ -> finalGraph
  where
    -- TODO Write pseudocode for subfunctions
    childrenToEmbed = findChildrenToEmbed treeRoots rootNode oldGraph
    -- Recursively collapse the children nodes
    graphWithCollapsedChildren = collapseRoots treeRoots oldGraph childrenToEmbed
    -- Transfer the edges of the children to rootNode
    childEdgesToTransfer = findChildEdgesToTransfer childrenToEmbed graphWithCollapsedChildren
    graphWithChildEdgesDeleted = deleteChildEdges childEdgesToTransfer graphWithCollapsedChildren
    graphWithEdgesTransferred = addChildEdges rootNode childEdgesToTransfer graphWithChildEdgesDeleted
    -- Modify the rootNode label (i.e. SyntaxNode) to incorporate the children it is embedding
    graphWithChildrenCollapsed = embedChildSyntaxNodes rootNode childrenToEmbed graphWithEdgesTransferred
    -- Delete the children that have been embedded
    finalGraph = deleteChildren childrenToEmbed graphWithChildrenCollapsed


-- | findChildrenToEmbed returns a list of the node's children that can be embedded
-- A child can be embedded iff all of these conditions are true:
-- 1. The node is not a treeRoot (otherwise a cycle of embedding could occur)
-- 2. The SyntaxNode is embeddable (i.e. nodeIsEmbeddable is True)
-- 3. The node has exactly one parent that can embed (i.e. nodeCanEmbed is True for one parent)
findChildrenToEmbed :: Node -> SyntaxGraph -> [Node]
findChildrenToEmbed treeRoots node graph = if graphNodeCanEmbed node graph
  then childrenToEmbed
  else []
  where
    childrenToEmbed = _ -- TODO

-- | graphNodeCanEmbed returns true if the label (SyntaxNode) associated with the
-- node can be embedded in other SyntaxNodes (i.e. nodeCanEmbed is True)
graphNodeCanEmbed :: Node -> SyntaxGraph -> Bool
graphNodeCanEmbed node graph = _


-- OLD ALGORITHM
-- To make the problem simpler, collapseNodes just cares about the
collapseNodes :: SyntaxGraph -> SyntaxGraph
collapseNodes inGraph = graphFold foldFunc initialOutputGraph inGraph where
  initialOutputGraph = emptyGraph

  foldFunc :: SyntaxGraph -> Context -> SyntaxGraph
  foldFunc oldGraph context = let node = nodeInContext context in
    -- The node can not be embedded, and can not embed other nodes, so it is by itself.
    -- We thus just add it to the accumulator graph.
    -- willEmbed is true iff the current node will embed other nodes in the graph
    | not (willBeEmbedded context inGraph) && not (willEmbed context inGraph) = context & oldGraph
    -- willBeEmbedded checks to see if the parent of the current node will embed the current node
    -- In this case the current node will be embedded, and does not embed other node.
    -- We do not add the current node since it will be embedded in its parent.
    -- This case is not necessary. If the current node were to be added, it would simply be
    -- removed again from the accumulation graph.
    | willBeEmbedded context inGraph && not (willEmbed context) = oldGraph
    -- This node will embed other nodes.
    -- First we find our children that will be embedded. If the child is in the
    -- oldGraph, then we also need to remove the child from the oldGraph.
    -- If the child is not yet in the oldGraph, then we just embed it.
    | willEmbed context inGraph =
      newGraph where
        (oldGraphChildren, oldGraphWithChildrenRemoved) = findAndRemoveChildren oldGraph context
        remainingChildrem = getRemainingChildren oldGraphChildren inGraph context
        embeddedNode = makeEmbeddedNode context oldGraphChildren remainingChildren
        newGarph = embeddedNode & oldGraphWithChildrenRemoved