uuagc

Knuth1

Synopsis

- traceST :: String -> ST s ()
- data AttrType
  - = Inh
  - | Syn
  - | Loc
- data Vertex
  - = VAttr AttrType Identifier Identifier
  - | VChild Identifier
  - | VRule Identifier
- isVertexAttr :: Vertex -> Bool
- getAttrChildName :: Vertex -> Identifier
- setAttrChildName :: Vertex -> Identifier -> Vertex
- getAttrType :: Vertex -> AttrType
- getAttrName :: Vertex -> Identifier
- type Edge = (Vertex, Vertex)
- type IVertex = Int
- type IEdge = (IVertex, IVertex)
- data DependencyGraph s = DependencyGraph {
  - vertexIMap :: Map Vertex IVertex
  - vertexOMap :: Array IVertex Vertex
  - successors :: Array IVertex (STRef s (Set IVertex))
  - predecessors :: Array IVertex (STRef s (Set IVertex))
  }
- graphConstruct :: [Vertex] -> ST s (DependencyGraph s)
- graphConstructTRC :: [Vertex] -> [Edge] -> ST s (DependencyGraph s)
- graphSuccessors :: DependencyGraph s -> Vertex -> ST s (Set Vertex)
- graphPredecessors :: DependencyGraph s -> Vertex -> ST s (Set Vertex)
- graphContainsEdge :: DependencyGraph s -> Edge -> ST s Bool
- graphInsert :: DependencyGraph s -> Edge -> ST s ()
- graphInsertTRC :: DependencyGraph s -> Edge -> ST s [(IVertex, Set IVertex)]
- graphVertices :: DependencyGraph s -> ST s [Vertex]
- graphEdges :: DependencyGraph s -> ST s [Edge]
- graphInsertEdges :: DependencyGraph s -> [Edge] -> ST s ()
- graphInsertEdgesTRC :: DependencyGraph s -> [Edge] -> ST s [Edge]
- graphIsCyclic :: DependencyGraph s -> ST s Bool
- graphCyclicVertices :: DependencyGraph s -> ST s (Set IVertex)
- graphCyclicVerticesExt :: DependencyGraph s -> ST s [Vertex]
- graphGetIVertex :: DependencyGraph s -> Vertex -> IVertex
- graphGetVertex :: DependencyGraph s -> IVertex -> Vertex
- graphGetEdge :: DependencyGraph s -> IEdge -> Edge
- graphIsTRC :: DependencyGraph s -> ST s Bool
- graphCheckConsistency :: DependencyGraph s -> ST s Bool
- graphTopSort :: DependencyGraph s -> ST s [Edge]
- graphTopSort' :: DependencyGraph s -> [IVertex] -> IVertex -> ST s [IVertex]
- data NontDependencyGraph = NontDependencyGraph {
  - ndgVertices :: [Vertex]
  - ndgEdges :: [Edge]
  }
- data ProdDependencyGraph = ProdDependencyGraph {
  - pdgVertices :: [Vertex]
  - pdgEdges :: [Edge]
  - pdgRules :: ERules
  - pdgChilds :: EChildren
  - pdgProduction :: Identifier
  - pdgChildMap :: [(Identifier, Identifier)]
  - pdgConstraints :: [Type]
  - pdgParams :: [Identifier]
  }
- data NontDependencyInformation = NontDependencyInformation {
  - ndiNonterminal :: Identifier
  - ndiParams :: [Identifier]
  - ndiInh :: [Identifier]
  - ndiSyn :: [Identifier]
  - ndiDepGraph :: NontDependencyGraph
  - ndiProds :: [ProdDependencyGraph]
  - ndiRecursive :: Bool
  - ndiHoInfo :: HigherOrderInfo
  - ndiClassCtxs :: ClassContext
  }
- data NontDependencyGraphM s = NontDependencyGraphM {
  - ndgmDepGraph :: DependencyGraph s
  - ndgmOrig :: NontDependencyGraph
  }
- data ProdDependencyGraphM s = ProdDependencyGraphM {
  - pdgmDepGraph :: DependencyGraph s
  - pdgmOrig :: ProdDependencyGraph
  }
- data NontDependencyInformationM s = NontDependencyInformationM {
  - ndimOrig :: NontDependencyInformation
  - ndimDepGraph :: NontDependencyGraphM s
  - ndimProds :: [ProdDependencyGraphM s]
  }
- mkNontDependencyGraphM :: NontDependencyGraph -> ST s (NontDependencyGraphM s)
- mkProdDependencyGraphM :: Bool -> ProdDependencyGraph -> ST s (ProdDependencyGraphM s)
- mkNontDependencyInformationM :: NontDependencyInformation -> ST s (NontDependencyInformationM s)
- undoTransitiveClosure :: [NontDependencyInformationM s] -> ST s [NontDependencyInformationM s]
- knuth1 :: [NontDependencyInformationM s] -> ST s ()
- knuth1' :: [([[Edge]], NontDependencyInformationM s)] -> ST s ()
- addProdNont :: ([[Edge]], NontDependencyInformationM s) -> ST s [Edge]
- addNontProd :: Bool -> ([Edge], NontDependencyInformationM s) -> ST s [[Edge]]
- addNontProd' :: Bool -> [Edge] -> ProdDependencyGraphM s -> ST s [Edge]
- addBackEdges :: [([[Edge]], NontDependencyInformationM s)] -> ST s [Edge]
- addTopSortEdges :: [Edge] -> ProdDependencyGraphM s -> ST s ()

# Documentation

traceST :: String -> ST s ()

Trace a message in the ST monad

data AttrType

Constructors

Inh |
Syn |
Loc |

Instances

Eq AttrType |
Ord AttrType |
Show AttrType |

data Vertex

Constructors

VAttr AttrType Identifier Identifier |
VChild Identifier |
VRule Identifier |

Instances

Eq Vertex |
Ord Vertex |
Show Vertex |

isVertexAttr :: Vertex -> Bool

Check if a vertex is an attribute

getAttrChildName :: Vertex -> Identifier

Get the child name of an attribute

setAttrChildName :: Vertex -> Identifier -> Vertex

Set the child name of an attribute

getAttrType :: Vertex -> AttrType

Get the type of an attribute

getAttrName :: Vertex -> Identifier

Get the name of an attribute

type Edge = (Vertex, Vertex)

type IVertex = Int

type IEdge = (IVertex, IVertex)

data DependencyGraph s

Constructors

DependencyGraph |
Fields vertexIMap :: Map Vertex IVertex vertexOMap :: Array IVertex Vertex successors :: Array IVertex (STRef s (Set IVertex)) predecessors :: Array IVertex (STRef s (Set IVertex))

graphConstruct :: [Vertex] -> ST s (DependencyGraph s)

Construct a dependency graph

graphConstructTRC :: [Vertex] -> [Edge] -> ST s (DependencyGraph s)

Construct a transitivelly closed graph

graphSuccessors :: DependencyGraph s -> Vertex -> ST s (Set Vertex)

Return all successors of a vertex

graphPredecessors :: DependencyGraph s -> Vertex -> ST s (Set Vertex)

Return all predecessors of a vertex

graphContainsEdge :: DependencyGraph s -> Edge -> ST s Bool

Check if the graph contains an edge

graphInsert :: DependencyGraph s -> Edge -> ST s ()

Insert an edge in the graph

graphInsertTRC :: DependencyGraph s -> Edge -> ST s [(IVertex, Set IVertex)]

Insert an edge in a transtive closed graph and return all other edges that were added due to transtivity

graphVertices :: DependencyGraph s -> ST s [Vertex]

Return all vertices of the graph

graphEdges :: DependencyGraph s -> ST s [Edge]

Return all edges of the graph

graphInsertEdges :: DependencyGraph s -> [Edge] -> ST s ()

Insert a list of edges in the graph

graphInsertEdgesTRC :: DependencyGraph s -> [Edge] -> ST s [Edge]

Insert a list of edges in the graph and return all other edges that were added due to transitivity

graphIsCyclic :: DependencyGraph s -> ST s Bool

Check whether the graph is cyclic

graphCyclicVertices :: DependencyGraph s -> ST s (Set IVertex)

graphCyclicVerticesExt :: DependencyGraph s -> ST s [Vertex]

graphGetIVertex :: DependencyGraph s -> Vertex -> IVertex

Get internal representation of a vertex

graphGetVertex :: DependencyGraph s -> IVertex -> Vertex

Get external representation of a vertex

graphGetEdge :: DependencyGraph s -> IEdge -> Edge

Get external representation of an edge

graphIsTRC :: DependencyGraph s -> ST s Bool

Check if the graph is transitively closed

graphCheckConsistency :: DependencyGraph s -> ST s Bool

Check consistency of the graph (successor and predecessor sets)

graphTopSort :: DependencyGraph s -> ST s [Edge]

Add edges to the graph so that it is topologically sorted (this will not work if graph is cyclic)

graphTopSort' :: DependencyGraph s -> [IVertex] -> IVertex -> ST s [IVertex]

Helper function for graphTopSort

data NontDependencyGraph

Special wrapper for nonterminal dependency graphs (so that we can easily add other meta-information)

Constructors

NontDependencyGraph |
Fields ndgVertices :: [Vertex] ndgEdges :: [Edge]

data ProdDependencyGraph

Special wrapper for production dependency graphs, including mapping between child names and nonterminals

Constructors

ProdDependencyGraph |
Fields pdgVertices :: [Vertex] pdgEdges :: [Edge] pdgRules :: ERules pdgChilds :: EChildren pdgProduction :: Identifier pdgChildMap :: [(Identifier, Identifier)] pdgConstraints :: [Type] pdgParams :: [Identifier]

data NontDependencyInformation

Represent all information from the dependency graphs for a nonterminal

Constructors

NontDependencyInformation |
Fields ndiNonterminal :: Identifier ndiParams :: [Identifier] ndiInh :: [Identifier] ndiSyn :: [Identifier] ndiDepGraph :: NontDependencyGraph ndiProds :: [ProdDependencyGraph] ndiRecursive :: Bool ndiHoInfo :: HigherOrderInfo ndiClassCtxs :: ClassContext

data NontDependencyGraphM s

Monadic wrapper of NontDependencyGraph

Constructors

NontDependencyGraphM |
Fields ndgmDepGraph :: DependencyGraph s ndgmOrig :: NontDependencyGraph

data ProdDependencyGraphM s

Monadic wrapper of ProdDependencyGraph

Constructors

ProdDependencyGraphM |
Fields pdgmDepGraph :: DependencyGraph s pdgmOrig :: ProdDependencyGraph

data NontDependencyInformationM s

Monadic wrapper of NontDependencyInformation

Constructors

NontDependencyInformationM |
Fields ndimOrig :: NontDependencyInformation ndimDepGraph :: NontDependencyGraphM s ndimProds :: [ProdDependencyGraphM s]

mkNontDependencyGraphM :: NontDependencyGraph -> ST s (NontDependencyGraphM s)

Convert a NontDependencyGraph to the corresponding monadic version

mkProdDependencyGraphM :: Bool -> ProdDependencyGraph -> ST s (ProdDependencyGraphM s)

Convert a ProdDependencyGraph to the corresponding monadic version

mkNontDependencyInformationM :: NontDependencyInformation -> ST s (NontDependencyInformationM s)

Convert a NontDependencyInformation to the corresponding monadic version

undoTransitiveClosure :: [NontDependencyInformationM s] -> ST s [NontDependencyInformationM s]

Construct the production graphs from the transitivelly closed graphs

knuth1 :: [NontDependencyInformationM s] -> ST s ()

Combine the dependency and nonterminal graphs using Knuth-1 this function assumes that the nonterminal graphs initially contains no edges

knuth1' :: [([[Edge]], NontDependencyInformationM s)] -> ST s ()

Helper function for |knuth1| which repeats the process until we are done

addProdNont :: ([[Edge]], NontDependencyInformationM s) -> ST s [Edge]

Add pending edges from the production graphs to the nonterminal graph and return the list of newly added nonterminal edges

addNontProd :: Bool -> ([Edge], NontDependencyInformationM s) -> ST s [[Edge]]

Add edges from the nonterminal graphs to the production graphs and return the list of newly added production edges and the updated graph

addNontProd' :: Bool -> [Edge] -> ProdDependencyGraphM s -> ST s [Edge]

Helper function for |addNontProd| for a single production

addBackEdges :: [([[Edge]], NontDependencyInformationM s)] -> ST s [Edge]

Add the back edges to the nonterminal graphs for creating a global ordering

addTopSortEdges :: [Edge] -> ProdDependencyGraphM s -> ST s ()

Add all resulting edges from a topsort on the nonterminal graph to the production graph this will ignore edges that will make the graph cyclic