Safe Haskell | Safe-Infered |
---|
Knuth1
- traceST :: String -> ST s ()
- data AttrType
- data Vertex
- 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 {}
- data NontDependencyGraphM s = NontDependencyGraphM {}
- data ProdDependencyGraphM s = ProdDependencyGraphM {}
- data NontDependencyInformationM s = NontDependencyInformationM {}
- 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
data Vertex
Constructors
VAttr AttrType Identifier Identifier | |
VChild Identifier | |
VRule Identifier |
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
data DependencyGraph s
Constructors
DependencyGraph | |
Fields
|
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
|
data ProdDependencyGraph
Special wrapper for production dependency graphs, including mapping between child names and nonterminals
Constructors
ProdDependencyGraph | |
Fields
|
data NontDependencyInformation
Represent all information from the dependency graphs for a nonterminal
Constructors
NontDependencyInformation | |
Fields
|
data NontDependencyGraphM s
Monadic wrapper of NontDependencyGraph
Constructors
NontDependencyGraphM | |
Fields |
data ProdDependencyGraphM s
Monadic wrapper of ProdDependencyGraph
Constructors
ProdDependencyGraphM | |
Fields |
data NontDependencyInformationM s
Monadic wrapper of NontDependencyInformation
Constructors
NontDependencyInformationM | |
Fields |
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