java.lang.Object
- soot.toolkits.graph.DominatorTree<N>

All Implemented Interfaces:

Iterable<DominatorNode<N>>

Direct Known Subclasses:

MHGDominatorTree
```
public class DominatorTree<N>
extends Object
implements Iterable<DominatorNode<N>>
```
Constructs a dominator tree structure from the given DominatorsFinder. The nodes in DominatorTree are of type DominatorNode.
Note: DominatorTree does not currently implement DirectedGraph since it provides 4 methods of navigating the nodes where the meaning of getPredsOf and getSuccsOf diverge from the usual meaning in a DirectedGraph implementation.
If you need a DirectedGraph implementation, see DominatorTreeAdapter.

Author:

Navindra Umanee

Field Summary

Fields
Modifier and Type	Field	Description
`protected DominatorsFinder<N>`	`dominators`
`protected Map<N,DominatorNode<N>>`	`godeToDode`	"gode" is a node in the original graph, "dode" is a node in the dominator tree.
`protected DirectedGraph<N>`	`graph`
`protected List<DominatorNode<N>>`	`heads`
`protected List<DominatorNode<N>>`	`tails`

Constructor Summary

Constructors
Constructor Description

DominatorTree(DominatorsFinder<N> dominators)

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`protected void`	`buildTree()`	Add all the necessary links between nodes to form a meaningful tree structure.
`protected DominatorNode<N>`	`fetchDode(N gode)`	Convenience method, ensures we don't create more than one DominatorNode for a given block.
`protected DominatorNode<N>`	`fetchParent(N gode)`
`List<DominatorNode<N>>`	`getChildrenOf(DominatorNode<N> node)`
`DominatorNode<N>`	`getDode(N gode)`
`DirectedGraph<N>`	`getGraph()`
`DominatorNode<N>`	`getHead()`	Gets the first head of the dominator tree.
`List<DominatorNode<N>>`	`getHeads()`
`DominatorNode<N>`	`getParentOf(DominatorNode<N> node)`
`List<DominatorNode<N>>`	`getPredsOf(DominatorNode<N> node)`
`List<DominatorNode<N>>`	`getSuccsOf(DominatorNode<N> node)`
`List<DominatorNode<N>>`	`getTails()`
`boolean`	`isDominatorOf(DominatorNode<N> dom, DominatorNode<N> node)`
`boolean`	`isImmediateDominatorOf(DominatorNode<N> idom, DominatorNode<N> node)`
`Iterator<DominatorNode<N>>`	`iterator()`
`int`	`size()`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Iterable
forEach, spliterator

- Field Detail
  - dominators
```
protected final DominatorsFinder<N> dominators
```
  - graph
```
protected final DirectedGraph<N> graph
```
  - heads
```
protected final List<DominatorNode<N>> heads
```
  - tails
```
protected final List<DominatorNode<N>> tails
```
  - godeToDode
```
protected final Map<N,DominatorNode<N>> godeToDode
```
    "gode" is a node in the original graph, "dode" is a node in the dominator tree.
- Constructor Detail
  - DominatorTree
```
public DominatorTree(DominatorsFinder<N> dominators)
```
- Method Detail
  - getGraph
```
public DirectedGraph<N> getGraph()
```
    Returns:
    
    the original graph to which the DominatorTree pertains
  - getHeads
```
public List<DominatorNode<N>> getHeads()
```
    Returns:
    
    the root of the dominator tree.
  - getHead
```
public DominatorNode<N> getHead()
```
    Gets the first head of the dominator tree. This function is implemented for single-headed trees and mainly for backwards compatibility.
    
    Returns:
    
    The first head of the dominator tree
  - getTails
```
public List<DominatorNode<N>> getTails()
```
    Returns:
    
    list of the tails of the dominator tree.
  - getParentOf
```
public DominatorNode<N> getParentOf(DominatorNode<N> node)
```
    Returns:
    
    the parent of node in the tree, null if the node is at the root.
  - getChildrenOf
```
public List<DominatorNode<N>> getChildrenOf(DominatorNode<N> node)
```
    Returns:
    
    the children of node in the tree.
  - getPredsOf
```
public List<DominatorNode<N>> getPredsOf(DominatorNode<N> node)
```
    Returns:
    
    list of the DominatorNodes corresponding to the predecessors of node in the original DirectedGraph
  - getSuccsOf
```
public List<DominatorNode<N>> getSuccsOf(DominatorNode<N> node)
```
    Returns:
    
    list of the DominatorNodes corresponding to the successors of node in the original DirectedGraph
  - isImmediateDominatorOf
```
public boolean isImmediateDominatorOf(DominatorNode<N> idom,
                                      DominatorNode<N> node)
```
    Returns:
    
    true if idom immediately dominates node.
  - isDominatorOf
```
public boolean isDominatorOf(DominatorNode<N> dom,
                             DominatorNode<N> node)
```
    Returns:
    
    true if dom dominates node.
  - getDode
```
public DominatorNode<N> getDode(N gode)
```
    Returns:
    
    DominatorNode for a given node in the original DirectedGraph.
  - iterator
```
public Iterator<DominatorNode<N>> iterator()
```
    Specified by:
    
    iterator in interface Iterable<N>
    
    Returns:
    
    iterator over the nodes in the tree. No ordering is implied.
  - size
```
public int size()
```
    Returns:
    
    the number of nodes in the tree
  - buildTree
```
protected void buildTree()
```
    Add all the necessary links between nodes to form a meaningful tree structure.
  - fetchDode
```
protected DominatorNode<N> fetchDode(N gode)
```
    Convenience method, ensures we don't create more than one DominatorNode for a given block.
  - fetchParent
```
protected DominatorNode<N> fetchParent(N gode)
```

Class DominatorTree<N>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.lang.Iterable

Field Detail

dominators

graph

heads

tails

godeToDode

Constructor Detail

DominatorTree

Method Detail

getGraph

getHeads

getHead

getTails

getParentOf

getChildrenOf

getPredsOf

getSuccsOf

isImmediateDominatorOf

isDominatorOf

getDode

iterator

size

buildTree

fetchDode

fetchParent