Vuo  1.2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
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.

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.
 
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.
 
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.
 
VuoCompilerTriggerPortfindNearestUpstreamTrigger (VuoCompilerNode *node)
 Returns the trigger port that is nearest upstream to node, or null if no trigger is upstream.
 
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 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.
 
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.
 
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.
 
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.
 

Constructor & Destructor Documentation

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.

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

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.
publishedInputNodeA node instantiated from VuoCompilerPublishedInputNodeClass, used to add a representation of the composition's published input ports and published input trigger to the graph representation.
publishedOutputNodeA node instantiated from VuoCompilerPublishedOutputNodeClass, used to add a representation of the composition's published output ports to the graph representation.

Member Function Documentation

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.

Exceptions
VuoCompilerExceptionThe 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.

Exceptions
VuoCompilerExceptionAn event may travel through the same cable more than once.
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.

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.

long VuoCompilerGraph::getHash ( VuoCompilerComposition composition)
static

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

Todo:
Check for change in to-port's event blocking (https://b33p.net/kosada/node/8197)
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.

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.

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.

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

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

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.

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.

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.

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.

Friends And Related Function Documentation

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

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

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

Needed so this type can be used in STL containers.

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

Needed so this type can be used in STL containers.

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.


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