Vuo  2.3.2
Classes | Public Member Functions | Static Public Member Functions | Friends | List of all members
VuoCompilerGraph Class Reference

Description

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.

Definition at line 37 of file VuoCompilerGraph.hh.

Public Member Functions

 VuoCompilerGraph (VuoCompilerComposition *composition, VuoCompiler *compiler=nullptr, 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. More...
 
 ~VuoCompilerGraph (void)
 Destructor. More...
 
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. More...
 
bool mayTransmitDataOnly (VuoCompilerNode *node)
 Returns true if node belongs to a node class that can transmit data through output cables without an event. More...
 
vector< VuoCompilerTriggerPort * > getTriggerPorts (void)
 Returns all trigger ports, including those for published input ports. More...
 
VuoCompilerNodegetNodeForTriggerPort (VuoCompilerTriggerPort *trigger)
 Returns the node that contains trigger. More...
 
set< VuoCompilerNode * > getNodes (void)
 Returns the nodes in the graph, which may exclude some in the composition (those with an unknown node class) and include some nodes that were not in the composition (e.g. More...
 
VuoCompilerNodegetPublishedInputNode (void)
 Returns the published input node. More...
 
VuoCompilerNodegetPublishedOutputNode (void)
 Returns the published output node. More...
 
VuoCompilerTriggerPortgetPublishedInputTrigger (void)
 Returns the trigger port that fires into the published input node's input ports. More...
 
VuoPortgetInputPortOnPublishedInputNode (size_t publishedInputPortIndex)
 Returns the input port on the published input node that corresponds to the published input port. More...
 
VuoPortgetInputPortOnPublishedOutputNode (size_t publishedOutputPortIndex)
 Returns the input port on the published output node that corresponds to the published output port. More...
 
VuoPortgetGatherPortOnPublishedOutputNode (void)
 Returns the gather input port on the published output node. More...
 
VuoCompilerTriggerPortgetManuallyFirableTrigger (void)
 Returns the trigger port that fires into VuoCompilerComposition's manually firable input port. More...
 
map< VuoCompilerTriggerPort *, vector< VuoCompilerChain * > > getChains (void)
 Returns a data structure that divides the graph up into linear chains of nodes. More...
 
vector< VuoCompilerNode * > getNodesImmediatelyDownstream (VuoCompilerTriggerPort *trigger)
 Returns the nodes that are directly connected to trigger through its outgoing cables. More...
 
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. More...
 
vector< VuoCompilerNode * > getNodesDownstream (VuoCompilerTriggerPort *trigger)
 Returns the nodes that can be reached by an event from trigger. More...
 
vector< VuoCompilerNode * > getNodesDownstream (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
 Returns the nodes that can be reached by an event from trigger that has passed through node. More...
 
vector< VuoCompilerNode * > getNodesDownstreamViaDataOnlyTransmission (VuoCompilerNode *node)
 Returns the nodes that can be reached by data-only transmission from the output cables of node, in topological order. More...
 
set< VuoCompilerCable * > getOutgoingCables (VuoCompilerPort *outputPort)
 Returns the outgoing cables from outputPort. More...
 
set< VuoCompilerNode * > getSourceNodesOfDataOnlyTransmission (void)
 Returns the nodes that can transmit data without an event and don't have any incoming data-only transmissions. More...
 
void getWorkerThreadsNeeded (VuoCompilerChain *chain, int &minThreadsNeeded, int &maxThreadsNeeded)
 Calculates the minimum and maximum number of threads that may be simultaneously waiting on dispatch semaphores, queues, or groups (i.e., counted toward the Dispatch Thread Soft Limit) while executing the chain of nodes. More...
 
void getWorkerThreadsNeeded (VuoCompilerTriggerPort *trigger, int &minThreadsNeeded, int &maxThreadsNeeded)
 Calculates the minimum and maximum number of threads that may be simultaneously waiting on dispatch semaphores, queues, or groups (i.e., counted toward the Dispatch Thread Soft Limit) while an event fired from this trigger is propagating through the composition. More...
 
VuoCompilerTriggerPortfindNearestUpstreamTrigger (VuoCompilerNode *node)
 Returns the trigger port that is nearest upstream to node, or null if no trigger is upstream. More...
 
VuoPortClass::EventBlocking getPublishedInputEventBlocking (size_t publishedInputPortIndex)
 Returns the type of event blocking for the published input port, based on whether an event through that port always (none), never (wall), or sometimes (door) reaches at least one published output port. More...
 
set< string > getPublishedOutputTriggers (void)
 Returns the name of each published output port that may be reached by an event from a trigger within the composition and may not be reached by an event from the published input trigger. More...
 
set< string > getPublishedOutputTriggersDownstream (VuoCompilerTriggerPort *trigger)
 Returns the name of each published output port that may be reached by an event from trigger and may not be reached by an event from the published input trigger. More...
 
set< string > getPublishedOutputPortsDownstream (VuoCompilerTriggerPort *trigger)
 Returns the name of each published output port that may be reached by an event from trigger. More...
 
bool mayEventsReachPublishedOutputPorts (void)
 Returns true if at least one published output port is downstream of the published input trigger or a trigger within the composition. More...
 
bool isRepeatedInFeedbackLoop (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
 Returns true if node is the one repeated node in a feedback loop downstream of trigger. More...
 
bool hasGatherDownstream (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
 Returns true if trigger has a gather (node with multiple incoming vertices) somewhere downstream. More...
 
bool hasScatterPartiallyOverlappedByAnotherTrigger (VuoCompilerTriggerPort *trigger)
 Returns true if there's a scatter originating at trigger, and some but not all nodes downstream of trigger are also downstream of another trigger. More...
 
bool hasScatterPartiallyOverlappedByAnotherTrigger (VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
 Returns true if there's a scatter originating at node for events from trigger, and some but not all nodes downstream of node are also downstream of another trigger. More...
 
bool hasOverlapWithSpinOff (VuoCompilerTriggerPort *trigger)
 Returns true if this trigger port causes a Spin Off node to fire, and this trigger and the Spin Off trigger have downstream nodes in common. More...
 
void checkForInfiniteFeedback (VuoCompilerIssues *issues)
 Checks that the composition does not have any infinite feedback loops. More...
 
void checkForDeadlockedFeedback (VuoCompilerIssues *issues)
 Checks that the compositon does not have any deadlocked feedback loops. More...
 

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. More...
 
static string getPublishedInputTriggerNodeIdentifier (void)
 Returns the node identifier assigned to the node containing the published input trigger. More...
 
static string getManuallyFirableTriggerNodeIdentifier (void)
 Returns the node identifier assigned to the node containing the trigger for manually firing events. More...
 

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. More...
 
bool operator!= (const Vertex &lhs, const Vertex &rhs)
 Returns true if the vertices represent different trigger-to-node or node-to-node connections. More...
 
bool operator< (const Vertex &lhs, const Vertex &rhs)
 Needed so this type can be used in STL containers. More...
 
bool operator< (const Edge &lhs, const Edge &rhs)
 Needed so this type can be used in STL containers. More...
 

Constructor & Destructor Documentation

◆ VuoCompilerGraph()

VuoCompilerGraph::VuoCompilerGraph ( VuoCompilerComposition composition,
VuoCompiler compiler = nullptr,
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.

Parameters
compositionThe 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.
compilerA compiler that may be used to generate published input and output nodes.
potentialCablesCables that are not yet in composition but should be added to the graph representation. If they would displace existing cables, the potentially displaced cables are omitted from the graph representation.

Definition at line 42 of file VuoCompilerGraph.cc.

◆ ~VuoCompilerGraph()

VuoCompilerGraph::~VuoCompilerGraph ( void  )

Destructor.

Definition at line 267 of file VuoCompilerGraph.cc.

Member Function Documentation

◆ checkForDeadlockedFeedback()

void VuoCompilerGraph::checkForDeadlockedFeedback ( VuoCompilerIssues issues)

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.

Exceptions
VuoCompilerExceptionThe composition contains a pair of nodes that are downstream of each other.

Definition at line 1936 of file VuoCompilerGraph.cc.

◆ checkForInfiniteFeedback()

void VuoCompilerGraph::checkForInfiniteFeedback ( VuoCompilerIssues issues)

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.

Exceptions
VuoCompilerExceptionAn event may travel through the same cable more than once.

Definition at line 1836 of file VuoCompilerGraph.cc.

◆ findNearestUpstreamTrigger()

VuoCompilerTriggerPort * VuoCompilerGraph::findNearestUpstreamTrigger ( VuoCompilerNode node)

Returns the trigger port that is nearest upstream to node, or null if no trigger is upstream.

The "nearest" trigger is based on two criteria: How many cables are between the trigger and the node, and are there any intervening doors? If there are any triggers that must always transmit to the node (no intervening doors), then the one with the fewest intervening cables is chosen. Otherwise, the trigger (with intervening doors) with the fewest intervening cables is chosen.

If there's a tie between two nearest triggers, the one returned is consistent across calls of this function.

Definition at line 1422 of file VuoCompilerGraph.cc.

◆ getChains()

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.

Definition at line 1016 of file VuoCompilerGraph.cc.

◆ getGatherPortOnPublishedOutputNode()

VuoPort * VuoCompilerGraph::getGatherPortOnPublishedOutputNode ( void  )

Returns the gather input port on the published output node.

Definition at line 955 of file VuoCompilerGraph.cc.

◆ getHash()

long VuoCompilerGraph::getHash ( VuoCompilerComposition composition)
static

Generates a unique, consistent hash value for the elements of composition structure analyzed by this class.

Definition at line 2037 of file VuoCompilerGraph.cc.

◆ getInputPortOnPublishedInputNode()

VuoPort * VuoCompilerGraph::getInputPortOnPublishedInputNode ( size_t  publishedInputPortIndex)

Returns the input port on the published input node that corresponds to the published input port.

Definition at line 925 of file VuoCompilerGraph.cc.

◆ getInputPortOnPublishedOutputNode()

VuoPort * VuoCompilerGraph::getInputPortOnPublishedOutputNode ( size_t  publishedOutputPortIndex)

Returns the input port on the published output node that corresponds to the published output port.

Definition at line 945 of file VuoCompilerGraph.cc.

◆ getManuallyFirableTrigger()

VuoCompilerTriggerPort * VuoCompilerGraph::getManuallyFirableTrigger ( void  )

Returns the trigger port that fires into VuoCompilerComposition's manually firable input port.

Definition at line 965 of file VuoCompilerGraph.cc.

◆ getManuallyFirableTriggerNodeIdentifier()

string VuoCompilerGraph::getManuallyFirableTriggerNodeIdentifier ( void  )
static

Returns the node identifier assigned to the node containing the trigger for manually firing events.

Definition at line 2103 of file VuoCompilerGraph.cc.

◆ getNodeForTriggerPort()

VuoCompilerNode * VuoCompilerGraph::getNodeForTriggerPort ( VuoCompilerTriggerPort trigger)

Returns the node that contains trigger.

Definition at line 876 of file VuoCompilerGraph.cc.

◆ getNodes()

set< VuoCompilerNode * > VuoCompilerGraph::getNodes ( void  )

Returns the nodes in the graph, which may exclude some in the composition (those with an unknown node class) and include some nodes that were not in the composition (e.g.

published input and output nodes).

Definition at line 889 of file VuoCompilerGraph.cc.

◆ getNodesDownstream() [1/2]

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.

Definition at line 1157 of file VuoCompilerGraph.cc.

◆ getNodesDownstream() [2/2]

vector< VuoCompilerNode * > VuoCompilerGraph::getNodesDownstream ( VuoCompilerTriggerPort trigger)

Returns the nodes that can be reached by an event from trigger.

Definition at line 1133 of file VuoCompilerGraph.cc.

◆ getNodesDownstreamViaDataOnlyTransmission()

vector< VuoCompilerNode * > VuoCompilerGraph::getNodesDownstreamViaDataOnlyTransmission ( VuoCompilerNode node)

Returns the nodes that can be reached by data-only transmission from the output cables of node, in topological order.

Definition at line 1192 of file VuoCompilerGraph.cc.

◆ getNodesImmediatelyDownstream() [1/2]

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.

Definition at line 1120 of file VuoCompilerGraph.cc.

◆ getNodesImmediatelyDownstream() [2/2]

vector< VuoCompilerNode * > VuoCompilerGraph::getNodesImmediatelyDownstream ( VuoCompilerTriggerPort trigger)

Returns the nodes that are directly connected to trigger through its outgoing cables.

Definition at line 1107 of file VuoCompilerGraph.cc.

◆ getOutgoingCables()

set< VuoCompilerCable * > VuoCompilerGraph::getOutgoingCables ( VuoCompilerPort outputPort)

Returns the outgoing cables from outputPort.

This includes cables downstream via an event from any trigger, cables downstream via data-only transmission, cables created for graph analysis, and any other cables from output ports of the node to input ports on a node with a compiler detail.

Definition at line 1202 of file VuoCompilerGraph.cc.

◆ getPublishedInputEventBlocking()

VuoPortClass::EventBlocking VuoCompilerGraph::getPublishedInputEventBlocking ( size_t  publishedInputPortIndex)

Returns the type of event blocking for the published input port, based on whether an event through that port always (none), never (wall), or sometimes (door) reaches at least one published output port.

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".

Definition at line 1483 of file VuoCompilerGraph.cc.

◆ getPublishedInputNode()

VuoCompilerNode * VuoCompilerGraph::getPublishedInputNode ( void  )

Returns the published input node.

See also
VuoCompilerPublishedInputNodeClass

Definition at line 899 of file VuoCompilerGraph.cc.

◆ getPublishedInputTrigger()

VuoCompilerTriggerPort * VuoCompilerGraph::getPublishedInputTrigger ( void  )

Returns the trigger port that fires into the published input node's input ports.

Definition at line 917 of file VuoCompilerGraph.cc.

◆ getPublishedInputTriggerNodeIdentifier()

string VuoCompilerGraph::getPublishedInputTriggerNodeIdentifier ( void  )
static

Returns the node identifier assigned to the node containing the published input trigger.

Definition at line 2095 of file VuoCompilerGraph.cc.

◆ getPublishedOutputNode()

VuoCompilerNode * VuoCompilerGraph::getPublishedOutputNode ( void  )

Returns the published output node.

See also
VuoCompilerPublishedOutputNodeClass

Definition at line 909 of file VuoCompilerGraph.cc.

◆ getPublishedOutputPortsDownstream()

set< string > VuoCompilerGraph::getPublishedOutputPortsDownstream ( VuoCompilerTriggerPort trigger)

Returns the name of each published output port that may be reached by an event from trigger.

Definition at line 1655 of file VuoCompilerGraph.cc.

◆ getPublishedOutputTriggers()

set< string > VuoCompilerGraph::getPublishedOutputTriggers ( void  )

Returns the name of each published output port that may be reached by an event from a trigger within the composition and may not be reached by an event from the published input trigger.

Definition at line 1620 of file VuoCompilerGraph.cc.

◆ getPublishedOutputTriggersDownstream()

set< string > VuoCompilerGraph::getPublishedOutputTriggersDownstream ( VuoCompilerTriggerPort trigger)

Returns the name of each published output port that may be reached by an event from trigger and may not be reached by an event from the published input trigger.

Definition at line 1636 of file VuoCompilerGraph.cc.

◆ getSourceNodesOfDataOnlyTransmission()

set< VuoCompilerNode * > VuoCompilerGraph::getSourceNodesOfDataOnlyTransmission ( void  )

Returns the nodes that can transmit data without an event and don't have any incoming data-only transmissions.

Definition at line 1226 of file VuoCompilerGraph.cc.

◆ getTriggerPorts()

vector< VuoCompilerTriggerPort * > VuoCompilerGraph::getTriggerPorts ( void  )

Returns all trigger ports, including those for published input ports.

Definition at line 868 of file VuoCompilerGraph.cc.

◆ getWorkerThreadsNeeded() [1/2]

void VuoCompilerGraph::getWorkerThreadsNeeded ( VuoCompilerChain chain,
int &  minThreadsNeeded,
int &  maxThreadsNeeded 
)

Calculates the minimum and maximum number of threads that may be simultaneously waiting on dispatch semaphores, queues, or groups (i.e., counted toward the Dispatch Thread Soft Limit) while executing the chain of nodes.

Definition at line 1248 of file VuoCompilerGraph.cc.

◆ getWorkerThreadsNeeded() [2/2]

void VuoCompilerGraph::getWorkerThreadsNeeded ( VuoCompilerTriggerPort trigger,
int &  minThreadsNeeded,
int &  maxThreadsNeeded 
)

Calculates the minimum and maximum number of threads that may be simultaneously waiting on dispatch semaphores, queues, or groups (i.e., counted toward the Dispatch Thread Soft Limit) while an event fired from this trigger is propagating through the composition.

Definition at line 1279 of file VuoCompilerGraph.cc.

◆ hasGatherDownstream()

bool VuoCompilerGraph::hasGatherDownstream ( VuoCompilerNode node,
VuoCompilerTriggerPort trigger 
)

Returns true if trigger has a gather (node with multiple incoming vertices) somewhere downstream.

Definition at line 1704 of file VuoCompilerGraph.cc.

◆ hasOverlapWithSpinOff()

bool VuoCompilerGraph::hasOverlapWithSpinOff ( VuoCompilerTriggerPort trigger)

Returns true if this trigger port causes a Spin Off node to fire, and this trigger and the Spin Off trigger have downstream nodes in common.

Definition at line 1783 of file VuoCompilerGraph.cc.

◆ hasScatterPartiallyOverlappedByAnotherTrigger() [1/2]

bool VuoCompilerGraph::hasScatterPartiallyOverlappedByAnotherTrigger ( VuoCompilerNode node,
VuoCompilerTriggerPort trigger 
)

Returns true if there's a scatter originating at node for events from trigger, and some but not all nodes downstream of node are also downstream of another trigger.

Definition at line 1734 of file VuoCompilerGraph.cc.

◆ hasScatterPartiallyOverlappedByAnotherTrigger() [2/2]

bool VuoCompilerGraph::hasScatterPartiallyOverlappedByAnotherTrigger ( VuoCompilerTriggerPort trigger)

Returns true if there's a scatter originating at trigger, and some but not all nodes downstream of trigger are also downstream of another trigger.

Definition at line 1718 of file VuoCompilerGraph.cc.

◆ isRepeatedInFeedbackLoop()

bool VuoCompilerGraph::isRepeatedInFeedbackLoop ( VuoCompilerNode node,
VuoCompilerTriggerPort trigger 
)

Returns true if node is the one repeated node in a feedback loop downstream of trigger.

Definition at line 1695 of file VuoCompilerGraph.cc.

◆ mayEventsReachPublishedOutputPorts()

bool VuoCompilerGraph::mayEventsReachPublishedOutputPorts ( void  )

Returns true if at least one published output port is downstream of the published input trigger or a trigger within the composition.

Definition at line 1683 of file VuoCompilerGraph.cc.

◆ mayTransmit()

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.

Definition at line 848 of file VuoCompilerGraph.cc.

◆ mayTransmitDataOnly()

bool VuoCompilerGraph::mayTransmitDataOnly ( VuoCompilerNode node)

Returns true if node belongs to a node class that can transmit data through output cables without an event.

Definition at line 860 of file VuoCompilerGraph.cc.

Friends And Related Function Documentation

◆ operator!=

bool operator!= ( const Vertex &  lhs,
const Vertex &  rhs 
)
friend

Returns true if the vertices represent different trigger-to-node or node-to-node connections.

Definition at line 2164 of file VuoCompilerGraph.cc.

◆ operator< [1/2]

bool operator< ( const Edge &  lhs,
const Edge &  rhs 
)
friend

Needed so this type can be used in STL containers.

Definition at line 2184 of file VuoCompilerGraph.cc.

◆ operator< [2/2]

bool operator< ( const Vertex &  lhs,
const Vertex &  rhs 
)
friend

Needed so this type can be used in STL containers.

Definition at line 2172 of file VuoCompilerGraph.cc.

◆ operator==

bool operator== ( const Vertex &  lhs,
const Vertex &  rhs 
)
friend

Returns true if the vertices represent the same trigger-to-node or node-to-node connection.

Definition at line 2156 of file VuoCompilerGraph.cc.


The documentation for this class was generated from the following files: