Vuo
1.2.3
|
Data structure used for performing graph analysis on a composition in order to compile it or check its validity.
Like a composition, VuoCompilerGraph is a graph structure consisting of vertices and edges. However, the vertices in VuoCompilerGraph represent edges (sets of cables) in the composition. Although counterintuitive, this turns out to make the graph analysis smoother, since the rules about feedback and event blocking are more simply expressed in terms of VuoCompilerGraph vertices and edges.
Public Member Functions | |
VuoCompilerGraph (VuoCompilerComposition *composition, set< VuoCompilerCable * > potentialCables=set< VuoCompilerCable * >()) | |
Creates a graph representation of the (current state of) the composition, to be used for checking the validity of the composition. | |
VuoCompilerGraph (VuoCompilerComposition *composition, VuoCompilerNode *publishedInputNode, VuoCompilerNode *publishedOutputNode) | |
Creates a graph representation of the (current state of) the composition, to be used for generating code for the composition. | |
bool | mayTransmit (VuoCompilerNode *fromNode, VuoCompilerNode *toNode, VuoCompilerTriggerPort *trigger) |
Returns true if an event from trigger may transmit along cables that directly connect fromNode to toNode. | |
bool | mayTransmitEventlessly (VuoCompilerNode *node) |
Returns true if node belongs to a node class that can transmit data through output cables without an event. | |
vector< VuoCompilerTriggerPort * > | getTriggerPorts (void) |
Returns all trigger ports, including those for published input ports. | |
map< VuoCompilerTriggerPort *, VuoCompilerNode * > | getNodesForTriggerPorts (void) |
Returns a mapping of each trigger port to the node that contains it. | |
map< VuoCompilerTriggerPort *, vector< VuoCompilerChain * > > | getChains (void) |
Returns a data structure that divides the graph up into linear chains of nodes. | |
vector< VuoCompilerNode * > | getNodesImmediatelyDownstream (VuoCompilerTriggerPort *trigger) |
Returns the nodes that are directly connected to trigger through its outgoing cables. | |
vector< VuoCompilerNode * > | getNodesImmediatelyDownstream (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger) |
Returns the nodes that are directly connected to node through its outgoing cables and are reachable from trigger. | |
vector< VuoCompilerNode * > | getNodesDownstream (VuoCompilerTriggerPort *trigger) |
Returns the nodes that can be reached by an event from trigger. | |
vector< VuoCompilerNode * > | getNodesDownstream (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger) |
Returns the nodes that can be reached by an event from trigger that has passed through node. | |
vector< VuoCompilerNode * > | getNodesEventlesslyDownstream (VuoCompilerNode *node) |
Returns the nodes that can be reached by data eventlessly transmitted from the output cables of node, in topological order. | |
set< VuoCompilerCable * > | getCablesImmediatelyDownstream (VuoCompilerPort *outputPort) |
Returns the outgoing cables from outputPort, including any that were created by this class (but not added to the composition) for published ports. | |
set< VuoCompilerCable * > | getCablesImmediatelyEventlesslyDownstream (VuoCompilerPort *outputPort) |
Returns the outgoing cables from outputPort that can transmit data eventlessly. | |
VuoPortClass::EventBlocking | getPublishedInputEventBlocking (void) |
Returns the type of event blocking for the published input ports, based on whether an event from the published input trigger always (none), never (wall), or sometimes (door) reaches the published output ports. | |
set< string > | getPublishedOutputTriggers (void) |
Returns the name of each published output port that may be reached by an event from a trigger other than the published input trigger. | |
bool | isRepeatedInFeedbackLoop (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger) |
Returns true if node is the one repeated node in a feedback loop downstream of trigger. | |
bool | hasGatherDownstream (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger) |
Returns true if trigger has a gather (node with multiple incoming vertices) somewhere downstream. | |
bool | hasGatherOverlappedByAnotherTrigger (VuoCompilerTriggerPort *trigger) |
Returns true if there's a scatter originating at trigger, a gather downstream of the scatter, and another trigger's path overlapping some nodes downstream of the scatter and upstream of a gather. | |
bool | hasGatherOverlappedByAnotherTrigger (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger) |
Returns true if there's a scatter originating at node for events from trigger, a gather downstream of the scatter, and another trigger's path overlapping some nodes downstream of the scatter and upstream of a gather. | |
void | checkForInfiniteFeedback (void) |
Checks that the composition does not have any infinite feedback loops. | |
void | checkForDeadlockedFeedback (void) |
Checks that the compositon does not have any deadlocked feedback loops. | |
Static Public Member Functions | |
static long | getHash (VuoCompilerComposition *composition) |
Generates a unique, consistent hash value for the elements of composition structure analyzed by this class. | |
Friends | |
class | TestVuoCompilerBitcodeGenerator |
bool | operator== (const Vertex &lhs, const Vertex &rhs) |
Returns true if the vertices represent the same trigger-to-node or node-to-node connection. | |
bool | operator!= (const Vertex &lhs, const Vertex &rhs) |
Returns true if the vertices represent different trigger-to-node or node-to-node connections. | |
bool | operator< (const Vertex &lhs, const Vertex &rhs) |
Needed so this type can be used in STL containers. | |
bool | operator< (const Edge &lhs, const Edge &rhs) |
Needed so this type can be used in STL containers. | |
VuoCompilerGraph::VuoCompilerGraph | ( | VuoCompilerComposition * | composition, |
set< VuoCompilerCable * > | potentialCables = set<VuoCompilerCable *>() |
||
) |
Creates a graph representation of the (current state of) the composition, to be used for checking the validity of the composition.
composition | The composition to represent. The graph representation is a snapshot of the composition passed into this constructor, and does not update if the composition is modified. |
potentialCables | Cables that are not yet in composition but should be added to the graph representation. |
VuoCompilerGraph::VuoCompilerGraph | ( | VuoCompilerComposition * | composition, |
VuoCompilerNode * | publishedInputNode, | ||
VuoCompilerNode * | publishedOutputNode | ||
) |
Creates a graph representation of the (current state of) the composition, to be used for generating code for the composition.
composition | The composition to represent. The graph representation is a snapshot of the composition passed into this constructor, and does not update if the composition is modified. |
publishedInputNode | A node instantiated from VuoCompilerPublishedInputNodeClass, used to add a representation of the composition's published input ports and published input trigger to the graph representation. |
publishedOutputNode | A node instantiated from VuoCompilerPublishedOutputNodeClass, used to add a representation of the composition's published output ports to the graph representation. |
void VuoCompilerGraph::checkForDeadlockedFeedback | ( | void | ) |
Checks that the compositon does not have any deadlocked feedback loops.
A deadlocked feedback loop makes it impossible to put the composition's nodes into an order in which they can be executed. It's a situation where node A must execute before node B, but node B must execute before node A.
VuoCompilerException | The composition contains a pair of nodes that are downstream of each other. |
void VuoCompilerGraph::checkForInfiniteFeedback | ( | void | ) |
Checks that the composition does not have any infinite feedback loops.
An infinite feedback loop is detected whenever an event may go through a feedback loop more than once. To avoid this possibility, a feedback loop must use a walled port on the feedback loop's final (and only repeated) node to block the event.
VuoCompilerException | An event may travel through the same cable more than once. |
set< VuoCompilerCable * > VuoCompilerGraph::getCablesImmediatelyDownstream | ( | VuoCompilerPort * | outputPort | ) |
Returns the outgoing cables from outputPort, including any that were created by this class (but not added to the composition) for published ports.
set< VuoCompilerCable * > VuoCompilerGraph::getCablesImmediatelyEventlesslyDownstream | ( | VuoCompilerPort * | outputPort | ) |
Returns the outgoing cables from outputPort that can transmit data eventlessly.
map< VuoCompilerTriggerPort *, vector< VuoCompilerChain * > > VuoCompilerGraph::getChains | ( | void | ) |
Returns a data structure that divides the graph up into linear chains of nodes.
A chain is a list of nodes where each is connected to the next by a single vertex (set of cables). There is no scattering/branching or gathering/joining within a chain.
If the graph has a feedback loop, then the one repeated node in the feedback loop appears in two chains (the second chain consisting of just that node).
For each trigger, the chains are listed in topological order.
|
static |
Generates a unique, consistent hash value for the elements of composition structure analyzed by this class.
vector< VuoCompilerNode * > VuoCompilerGraph::getNodesDownstream | ( | VuoCompilerTriggerPort * | trigger | ) |
Returns the nodes that can be reached by an event from trigger.
vector< VuoCompilerNode * > VuoCompilerGraph::getNodesDownstream | ( | VuoCompilerNode * | node, |
VuoCompilerTriggerPort * | trigger | ||
) |
Returns the nodes that can be reached by an event from trigger that has passed through node.
vector< VuoCompilerNode * > VuoCompilerGraph::getNodesEventlesslyDownstream | ( | VuoCompilerNode * | node | ) |
Returns the nodes that can be reached by data eventlessly transmitted from the output cables of node, in topological order.
map< VuoCompilerTriggerPort *, VuoCompilerNode * > VuoCompilerGraph::getNodesForTriggerPorts | ( | void | ) |
Returns a mapping of each trigger port to the node that contains it.
vector< VuoCompilerNode * > VuoCompilerGraph::getNodesImmediatelyDownstream | ( | VuoCompilerTriggerPort * | trigger | ) |
Returns the nodes that are directly connected to trigger through its outgoing cables.
vector< VuoCompilerNode * > VuoCompilerGraph::getNodesImmediatelyDownstream | ( | VuoCompilerNode * | node, |
VuoCompilerTriggerPort * | trigger | ||
) |
Returns the nodes that are directly connected to node through its outgoing cables and are reachable from trigger.
VuoPortClass::EventBlocking VuoCompilerGraph::getPublishedInputEventBlocking | ( | void | ) |
Returns the type of event blocking for the published input ports, based on whether an event from the published input trigger always (none), never (wall), or sometimes (door) reaches the published output ports.
If there are no event-only or data-and-event published output ports to reach, returns "none".
For certain compositions that contain nodes with door input ports, the analysis is imprecise. For example, if both the False Option and True Option outputs of a Select Output
node have cables to published output ports, then all events into the node will reach the published output ports. But this function can't reason about the implementation of the node. It can only reason about the fact that the node's input ports are marked as doors. So it returns "door" instead of "none".
set< string > VuoCompilerGraph::getPublishedOutputTriggers | ( | void | ) |
Returns the name of each published output port that may be reached by an event from a trigger other than the published input trigger.
vector< VuoCompilerTriggerPort * > VuoCompilerGraph::getTriggerPorts | ( | void | ) |
Returns all trigger ports, including those for published input ports.
bool VuoCompilerGraph::hasGatherDownstream | ( | VuoCompilerNode * | node, |
VuoCompilerTriggerPort * | trigger | ||
) |
Returns true if trigger has a gather (node with multiple incoming vertices) somewhere downstream.
bool VuoCompilerGraph::hasGatherOverlappedByAnotherTrigger | ( | VuoCompilerTriggerPort * | trigger | ) |
Returns true if there's a scatter originating at trigger, a gather downstream of the scatter, and another trigger's path overlapping some nodes downstream of the scatter and upstream of a gather.
bool VuoCompilerGraph::hasGatherOverlappedByAnotherTrigger | ( | VuoCompilerNode * | node, |
VuoCompilerTriggerPort * | trigger | ||
) |
Returns true if there's a scatter originating at node for events from trigger, a gather downstream of the scatter, and another trigger's path overlapping some nodes downstream of the scatter and upstream of a gather.
bool VuoCompilerGraph::isRepeatedInFeedbackLoop | ( | VuoCompilerNode * | node, |
VuoCompilerTriggerPort * | trigger | ||
) |
Returns true if node is the one repeated node in a feedback loop downstream of trigger.
bool VuoCompilerGraph::mayTransmit | ( | VuoCompilerNode * | fromNode, |
VuoCompilerNode * | toNode, | ||
VuoCompilerTriggerPort * | trigger | ||
) |
Returns true if an event from trigger may transmit along cables that directly connect fromNode to toNode.
bool VuoCompilerGraph::mayTransmitEventlessly | ( | VuoCompilerNode * | node | ) |
Returns true if node belongs to a node class that can transmit data through output cables without an event.
|
friend |
Returns true if the vertices represent different trigger-to-node or node-to-node connections.
|
friend |
Needed so this type can be used in STL containers.
|
friend |
Needed so this type can be used in STL containers.
|
friend |
Returns true if the vertices represent the same trigger-to-node or node-to-node connection.