Vuo  2.3.2
VuoCompilerGraph.cc
Go to the documentation of this file.
1 
10 #include "VuoCable.hh"
11 #include "VuoCompiler.hh"
12 #include "VuoCompilerGraph.hh"
13 #include "VuoCompilerCable.hh"
14 #include "VuoCompilerChain.hh"
15 #include "VuoCompilerComposition.hh"
16 #include "VuoCompilerException.hh"
17 #include "VuoCompilerInputEventPortClass.hh"
18 #include "VuoCompilerIssue.hh"
19 #include "VuoCompilerNode.hh"
20 #include "VuoCompilerPublishedInputNodeClass.hh"
21 #include "VuoCompilerPublishedOutputNodeClass.hh"
22 #include "VuoCompilerTriggerDescription.hh"
23 #include "VuoCompilerTriggerPort.hh"
24 #include "VuoCompilerTriggerPortClass.hh"
25 #include "VuoComposition.hh"
26 #include "VuoNode.hh"
27 #include "VuoNodeClass.hh"
28 #include "VuoPublishedPort.hh"
29 #include "VuoStringUtilities.hh"
30 #include <sstream>
31 
42 VuoCompilerGraph::VuoCompilerGraph(VuoCompilerComposition *composition, VuoCompiler *compiler, set<VuoCompilerCable *> potentialCables)
43 {
44  VuoCompilerNode *publishedInputNode = nullptr;
45  VuoCompilerNode *publishedOutputNode = nullptr;
46  VuoCompilerNode *publishedInputTriggerNode = nullptr;
47  bool ownsPublishedNodeClasses = false;
48 
49  VuoCompilerNodeClass *triggerNodeClass = nullptr;
50  if (compiler)
51  {
52  triggerNodeClass = compiler->getNodeClass("vuo.event.spinOffEvent2");
53  }
54  else
55  {
56  VuoPortClass *refreshPortClass = (new VuoCompilerInputEventPortClass("refresh"))->getBase();
57  VuoCompilerTriggerPortClass *triggerPortClass = new VuoCompilerTriggerPortClass("spunOff");
58  vector<VuoPortClass *> inputPortClasses;
59  vector<VuoPortClass *> outputPortClasses(1, triggerPortClass->getBase());
60  VuoNodeClass *baseNodeClass = new VuoNodeClass("vuo.event.spinOffEvent2", refreshPortClass, inputPortClasses, outputPortClasses);
61  triggerNodeClass = VuoCompilerNodeClass::newNodeClassWithoutImplementation(baseNodeClass)->getCompiler();
62  }
63 
64  vector<VuoPublishedPort *> publishedInputPorts = composition->getBase()->getPublishedInputPorts();
65  vector<VuoPublishedPort *> publishedOutputPorts = composition->getBase()->getPublishedOutputPorts();
66 
67  if (! (publishedInputPorts.empty() && publishedOutputPorts.empty()) )
68  {
69  if (compiler)
70  {
71  publishedInputNode = compiler->createPublishedInputNode(publishedInputPorts)->getCompiler();
72  publishedOutputNode = compiler->createPublishedOutputNode(publishedOutputPorts)->getCompiler();
73 
74  ownsPublishedNodeClasses = false;
75  }
76  else
77  {
78  VuoNodeClass *publishedInputNodeClass = VuoCompilerPublishedInputNodeClass::newNodeClass(publishedInputPorts);
79  VuoNodeClass *publishedOutputNodeClass = VuoCompilerPublishedOutputNodeClass::newNodeClass(publishedOutputPorts);
80  publishedInputNode = publishedInputNodeClass->getCompiler()->newNode()->getCompiler();
81  publishedOutputNode = publishedOutputNodeClass->getCompiler()->newNode()->getCompiler();
82 
83  ownsPublishedNodeClasses = true;
84  }
85 
86  publishedInputTriggerNode = triggerNodeClass->newNode()->getCompiler();
87  publishedInputTriggerNode->setGraphvizIdentifier(getPublishedInputTriggerNodeIdentifier());
88  }
89 
90  VuoCompilerNode *manuallyFirableTriggerNode = triggerNodeClass->newNode()->getCompiler();
91  manuallyFirableTriggerNode->setGraphvizIdentifier(getManuallyFirableTriggerNodeIdentifier());
92 
93  initializeInstance(composition, potentialCables, publishedInputNode, publishedOutputNode, publishedInputTriggerNode, ownsPublishedNodeClasses,
94  manuallyFirableTriggerNode);
95 }
96 
121 void VuoCompilerGraph::initializeInstance(VuoCompilerComposition *composition, set<VuoCompilerCable *> potentialCables,
122  VuoCompilerNode *publishedInputNode, VuoCompilerNode *publishedOutputNode,
123  VuoCompilerNode *publishedInputTriggerNode, bool ownsPublishedNodeClasses,
124  VuoCompilerNode *manuallyFirableTriggerNode)
125 {
126  this->publishedInputNode = publishedInputNode;
127  this->publishedOutputNode = publishedOutputNode;
128  this->ownsPublishedNodeClasses = ownsPublishedNodeClasses;
129  this->publishedInputTrigger = nullptr;
130 
131  // Nodes in the composition
132 
133  set<VuoNode *> nodesIncludingInvalid = composition->getBase()->getNodes();
134  set<VuoNode *> nodesToAnalyze;
135  for (VuoNode *node : nodesIncludingInvalid)
136  if (node->hasCompiler()) // Ignore nodes with missing node classes.
137  nodesToAnalyze.insert(node);
138 
139  if (publishedInputNode && publishedOutputNode)
140  {
141  // Published input/output nodes
142 
143  nodesToAnalyze.insert(publishedInputNode->getBase());
144  nodesToAnalyze.insert(publishedOutputNode->getBase());
145 
146  // `Spin Off Event` node for published inputs
147 
148  nodesToAnalyze.insert(publishedInputTriggerNode->getBase());
149 
150  VuoPort *publishedInputTriggerPort = publishedInputTriggerNode->getBase()->getOutputPorts().at(VuoNodeClass::unreservedOutputPortStartIndex);
151  this->publishedInputTrigger = static_cast<VuoCompilerTriggerPort *>(publishedInputTriggerPort->getCompiler());
152  }
153 
154  // `Spin Off Event` node for manually firable trigger
155 
156  nodesToAnalyze.insert(manuallyFirableTriggerNode->getBase());
157 
158  VuoPort *manuallyFirableTriggerPort = manuallyFirableTriggerNode->getBase()->getOutputPorts().at(VuoNodeClass::unreservedOutputPortStartIndex);
159  this->manuallyFirableTrigger = static_cast<VuoCompilerTriggerPort *>(manuallyFirableTriggerPort->getCompiler());
160 
161  // Internal cables in the composition
162 
163  set<VuoPort *> potentialCableInputs;
164  for (VuoCompilerCable *cable : potentialCables)
165  if (cable->carriesData())
166  potentialCableInputs.insert(cable->getBase()->getToPort());
167 
168  set<VuoCable *> cablesIncludingInvalidAndPublished = composition->getBase()->getCables();
169  set<VuoCable *> cablesToAnalyze;
170  for (VuoCable *cable : cablesIncludingInvalidAndPublished)
171  {
172  if ((cable->getFromPort() && cable->getToPort()) // Ignore disconnected cables.
173  && (cable->getFromPort()->hasCompiler() && cable->getToPort()->hasCompiler()) // Ignore cables on nodes with missing node classes.
174  && ! (cable->hasCompiler() && cable->getCompiler()->carriesData() &&
175  potentialCableInputs.find(cable->getToPort()) != potentialCableInputs.end()) ) // Ignore displaced cables.
176  {
177  if (cable->isPublished())
178  publishedCables.insert(cable);
179  else
180  cablesToAnalyze.insert(cable);
181  }
182  }
183 
184  // Potential internal cables
185 
186  for (VuoCompilerCable *cable : potentialCables)
187  {
188  if (cable->getBase()->isPublished())
189  publishedCables.insert(cable->getBase());
190  else
191  cablesToAnalyze.insert(cable->getBase());
192  }
193 
194  // Cables connected to published input/output nodes
195 
196  vector<VuoPublishedPort *> publishedInputPorts = composition->getBase()->getPublishedInputPorts();
197  vector<VuoPublishedPort *> publishedOutputPorts = composition->getBase()->getPublishedOutputPorts();
198  for (VuoCable *cable : publishedCables)
199  {
200  VuoNode *fromNode = nullptr;
201  VuoNode *toNode = nullptr;
202  VuoPort *fromPort = nullptr;
203  VuoPort *toPort = nullptr;
204 
205  if (cable->isPublishedInputCable())
206  {
207  size_t publishedPortIndex = std::distance(publishedInputPorts.begin(), std::find(publishedInputPorts.begin(), publishedInputPorts.end(), cable->getFromPort()));
208 
209  fromNode = publishedInputNode->getBase();
210  fromPort = getOutputPortOnPublishedInputNode(publishedPortIndex);
211  toNode = cable->getToNode();
212  toPort = cable->getToPort();
213  }
214  else
215  {
216  size_t publishedPortIndex = std::distance(publishedOutputPorts.begin(), std::find(publishedOutputPorts.begin(), publishedOutputPorts.end(), cable->getToPort()));
217 
218  fromNode = cable->getFromNode();
219  fromPort = cable->getFromPort();
220  toNode = publishedOutputNode->getBase();
221  toPort = getInputPortOnPublishedOutputNode(publishedPortIndex);
222  }
223 
224  VuoCompilerCable *replacement = new VuoCompilerCable(fromNode->getCompiler(), static_cast<VuoCompilerPort *>(fromPort->getCompiler()),
225  toNode->getCompiler(), static_cast<VuoCompilerPort *>(toPort->getCompiler()), false);
226  replacement->setAlwaysEventOnly(cable->getCompiler()->getAlwaysEventOnly());
227  cablesToAnalyze.insert(replacement->getBase());
228  }
229 
230  // Cable from `Spin Off Event` to published input node
231 
232  if (publishedInputTrigger)
233  {
234  VuoPort *toPort = publishedInputNode->getBase()->getInputPorts().at(0);
235  VuoCompilerCable *spinOffCable = new VuoCompilerCable(publishedInputTriggerNode, publishedInputTrigger,
236  publishedInputNode, static_cast<VuoCompilerPort *>(toPort->getCompiler()), false);
237  cablesToAnalyze.insert(spinOffCable->getBase());
238  }
239 
240  // Cable from `Spin Off Event` to manually firable input port
241 
242  {
243  VuoNode *toNode = composition->getManuallyFirableInputNode();
244  VuoPort *toPort = composition->getManuallyFirableInputPort();
245  if (toNode && toPort && toNode->hasCompiler() && toPort->hasCompiler())
246  {
247  VuoCompilerCable *spinOffCable = new VuoCompilerCable(manuallyFirableTriggerNode, manuallyFirableTrigger,
248  toNode->getCompiler(), static_cast<VuoCompilerPort *>(toPort->getCompiler()), false);
249  cablesToAnalyze.insert(spinOffCable->getBase());
250  }
251  }
252 
253  for (VuoNode *node : nodesToAnalyze)
254  nodes.insert(node->getCompiler());
255 
256  makeTriggers(nodesToAnalyze);
257  makeVerticesAndEdges(cablesToAnalyze);
258  makeDownstreamVertices();
259  sortVertices();
260  makeVertexDistances();
261  makeDownstreamNodesViaDataOnlyTransmission(nodesToAnalyze, cablesToAnalyze);
262 }
263 
267 VuoCompilerGraph::~VuoCompilerGraph(void)
268 {
269  VuoCompilerNode *publishedInputTriggerNode = nodeForTrigger[publishedInputTrigger];
270 
271  if (ownsPublishedNodeClasses)
272  {
273  delete publishedInputNode->getBase()->getNodeClass()->getCompiler();
274  delete publishedOutputNode->getBase()->getNodeClass()->getCompiler();
275  delete publishedInputTriggerNode->getBase()->getNodeClass()->getCompiler();
276  }
277 
278  delete publishedInputNode;
279  delete publishedOutputNode;
280  delete publishedInputTriggerNode;
281 }
282 
286 void VuoCompilerGraph::makeTriggers(set<VuoNode *> nodes)
287 {
288  for (VuoNode *node : nodes)
289  {
290  for (VuoPort *port : node->getOutputPorts())
291  {
292  VuoCompilerTriggerPort *trigger = dynamic_cast<VuoCompilerTriggerPort *>(port->getCompiler());
293  if (trigger)
294  {
295  nodeForTrigger[trigger] = node->getCompiler();
296  triggers.push_back(trigger);
297  }
298  }
299  }
300 }
301 
305 void VuoCompilerGraph::makeVerticesAndEdges(const set<VuoCable *> &cables)
306 {
307  // Create vertices to visit for all cables.
308 
309  set<Vertex> allVertices;
310  for (VuoCable *cable : cables)
311  {
312  VuoCompilerPort *fromPort = cable->getFromPort() ? static_cast<VuoCompilerPort *>(cable->getFromPort()->getCompiler()) : nullptr;
313  VuoCompilerTriggerPort *fromTrigger = dynamic_cast<VuoCompilerTriggerPort *>(fromPort);
314  VuoCompilerNode *fromNode = cable->getFromNode()->getCompiler();
315  VuoCompilerNode *toNode = cable->getToNode()->getCompiler();
316  Vertex vertex = (fromTrigger ? Vertex(fromTrigger, toNode) : Vertex(fromNode, toNode));
317 
318  set<Vertex>::iterator vertexIter = allVertices.find(vertex);
319  if (vertexIter != allVertices.end())
320  {
321  vertex.cableBundle = (*vertexIter).cableBundle;
322  allVertices.erase(vertexIter);
323  }
324  vertex.cableBundle.insert(cable->getCompiler());
325 
326  allVertices.insert(vertex);
327  }
328 
329  // For each trigger, add all vertices reachable from it.
330 
331  for (VuoCompilerTriggerPort *trigger : triggers)
332  {
333  set<Vertex> verticesToVisit;
334  set<Edge> edgesVisited;
335 
336  for (set<Vertex>::iterator j = allVertices.begin(); j != allVertices.end(); ++j)
337  if ((*j).fromTrigger == trigger)
338  verticesToVisit.insert(*j);
339 
340  map<VuoCompilerNode *, set<Vertex> > outgoingVerticesForNode; // Cached data to speed up search for outgoing vertices.
341  for (set<Vertex>::iterator j = allVertices.begin(); j != allVertices.end(); ++j)
342  outgoingVerticesForNode[(*j).fromNode].insert(*j);
343 
344  while (! verticesToVisit.empty())
345  {
346  Vertex vertex = *verticesToVisit.begin();
347  if (find(vertices[trigger].begin(), vertices[trigger].end(), vertex) == vertices[trigger].end())
348  vertices[trigger].push_back(vertex);
349  verticesToVisit.erase(verticesToVisit.begin());
350 
351  set<Vertex> potentialOutgoingVertices = outgoingVerticesForNode[vertex.toNode];
352  for (set<Vertex>::iterator j = potentialOutgoingVertices.begin(); j != potentialOutgoingVertices.end(); ++j)
353  {
354  Vertex outgoingVertex = *j;
355 
356  if (mayTransmit(vertex.cableBundle, outgoingVertex.cableBundle))
357  {
358  Edge outgoingEdge(vertex, outgoingVertex);
359  if (edgesVisited.find(outgoingEdge) == edgesVisited.end()) // Avoid infinite feedback loops.
360  {
361  edges[trigger].insert(outgoingEdge);
362  edgesVisited.insert(outgoingEdge);
363 
364  verticesToVisit.insert(outgoingVertex);
365  }
366  }
367  }
368  }
369  }
370 }
371 
376 void VuoCompilerGraph::makeDownstreamVerticesWithInclusionRule(VuoCompilerTriggerPort *trigger, std::function<bool(Edge)> includeEdge,
377  map<Vertex, set<Vertex> > &_downstreamVertices,
378  set<Vertex> &_repeatedVertices)
379 {
380  list<Vertex> verticesToVisit; // Used as a stack, except for a call to find().
381 
382  for (Vertex vertex : vertices[trigger])
383  if (vertex.fromTrigger == trigger)
384  verticesToVisit.push_back(vertex);
385 
386  map<Vertex, set<Vertex> > outgoingVerticesFromVertex; // Cached data to speed up search for outgoing vertices.
387  for (Edge edge : edges[trigger])
388  if (includeEdge(edge))
389  outgoingVerticesFromVertex[edge.fromVertex].insert(edge.toVertex);
390 
391  while (! verticesToVisit.empty())
392  {
393  // Visit the vertex at the top of the stack.
394  Vertex currentVertex = verticesToVisit.back();
395 
396  set<Vertex> currentDownstreamVertices;
397  bool areDownstreamVerticesComplete = true;
398 
399  // Consider each vertex immediately downstream of this vertex.
400  set<Vertex> outgoingVertices = outgoingVerticesFromVertex[currentVertex];
401  for (set<Vertex>::iterator j = outgoingVertices.begin(); j != outgoingVertices.end(); ++j)
402  {
403  Vertex outgoingVertex = *j;
404  currentDownstreamVertices.insert(outgoingVertex);
405 
406  if (_downstreamVertices.find(outgoingVertex) != _downstreamVertices.end())
407  {
408  // The downstream vertex has already been visited, so add its downstream vertices to this vertex's.
409  set<Vertex> furtherDownstreamVertices = _downstreamVertices[outgoingVertex];
410  currentDownstreamVertices.insert( furtherDownstreamVertices.begin(), furtherDownstreamVertices.end() );
411  }
412  else
413  {
414  if (find(verticesToVisit.begin(), verticesToVisit.end(), outgoingVertex) != verticesToVisit.end())
415  {
416  // The downstream vertex is already on the stack, so it's an infinite feedback loop.
417  _repeatedVertices.insert(outgoingVertex);
418  }
419  else
420  {
421  // The downstream vertex has not yet been visited, so add it to the stack.
422  verticesToVisit.push_back(outgoingVertex);
423  areDownstreamVerticesComplete = false;
424  }
425  }
426  }
427 
428  if (areDownstreamVerticesComplete)
429  {
430  _downstreamVertices[currentVertex] = currentDownstreamVertices;
431  verticesToVisit.pop_back();
432  }
433  }
434 
435  // Clean up repeatedVertices so that it only contains vertices within an infinite feedback loop,
436  // not other outgoing vertices from nodes in the infinite feedback loop.
437  set<Vertex> repeatedVerticesCopy = _repeatedVertices;
438  for (Vertex vertex : repeatedVerticesCopy)
439  if (_downstreamVertices[vertex].find(vertex) == _downstreamVertices[vertex].end())
440  _repeatedVertices.erase(vertex);
441 }
442 
446 void VuoCompilerGraph::makeDownstreamVertices(void)
447 {
448  auto includeAllEdges = [] (Edge edge) { return true; };
449 
450  for (VuoCompilerTriggerPort *trigger : triggers)
451  {
452  makeDownstreamVerticesWithInclusionRule(trigger, includeAllEdges, downstreamVertices[trigger], repeatedVertices[trigger]);
453 
454  if (repeatedVertices[trigger].empty())
455  repeatedVertices.erase(trigger);
456  }
457 
458  // For each trigger, add a cable and vertex from each leaf trigger/vertex to the published output node's gather port.
459  // - For the published input trigger and triggers that spin off events from it, this ensures that the
460  // composition doesn't notify its runner (for top-level compositions) or parent composition (for subcompositions)
461  // until the event has finished propagating through the composition.
462  // - For internal triggers that reach a published output, this ensures that published trigger doesn't fire
463  // until the event has finished propagating through the composition.
464 
465  if (publishedOutputNode)
466  {
467  for (VuoCompilerTriggerPort *trigger : triggers)
468  {
469  set< pair<VuoCompilerTriggerPort *, Vertex> > leaves;
470  if (trigger != publishedInputTrigger && trigger != manuallyFirableTrigger && downstreamVertices[trigger].empty())
471  leaves.insert({ trigger, Vertex() });
472  else
473  for (auto i : downstreamVertices[trigger])
474  if (i.first.toNode != publishedOutputNode && i.second.empty())
475  leaves.insert({ nullptr, i.first });
476 
477  for (auto &leaf : leaves)
478  {
479  VuoCompilerNode *fromNode = (leaf.first ? nodeForTrigger[leaf.first] : leaf.second.toNode);
480  VuoCompilerTriggerPort *fromPort = (leaf.first ? leaf.first : nullptr);
481  VuoPort *toPort = getGatherPortOnPublishedOutputNode();
482 
483  VuoCompilerCable *gather = new VuoCompilerCable(fromNode, fromPort,
484  publishedOutputNode, static_cast<VuoCompilerPort *>(toPort->getCompiler()), false);
485 
486  Vertex gatherVertex = (leaf.first ? Vertex(fromPort, publishedOutputNode) : Vertex(fromNode, publishedOutputNode));
487  gatherVertex.cableBundle.insert(gather);
488  vertices[trigger].push_back(gatherVertex);
489 
490  if (! leaf.first)
491  {
492  Vertex leafVertex = leaf.second;
493  Edge gatherEdge(leafVertex, gatherVertex);
494  edges[trigger].insert(gatherEdge);
495  downstreamVertices[trigger][leafVertex].insert(gatherVertex);
496  }
497  }
498  }
499  }
500 }
501 
505 void VuoCompilerGraph::sortVertices(void)
506 {
507  for (map<VuoCompilerTriggerPort *, vector<Vertex> >::iterator i = vertices.begin(); i != vertices.end(); ++i)
508  {
509  VuoCompilerTriggerPort *trigger = i->first;
510  vector<Vertex> verticesToSort = i->second;
511 
512  map<Vertex, set<Vertex> > dependentVertices;
513  list<Vertex> verticesToVisit; // Used as a stack, except for a call to find().
514  map<Vertex, bool> verticesCompleted;
515 
516  for (vector<Vertex>::iterator j = verticesToSort.begin(); j != verticesToSort.end(); ++j)
517  if ((*j).fromTrigger == trigger)
518  verticesToVisit.push_back(*j);
519 
520  map<VuoCompilerNode *, set<Vertex> > outgoingVerticesForNode; // Cached data to speed up topological sort.
521  for (vector<Vertex>::iterator j = verticesToSort.begin(); j != verticesToSort.end(); ++j)
522  outgoingVerticesForNode[(*j).fromNode].insert(*j);
523 
524  while (! verticesToVisit.empty())
525  {
526  // Visit the vertex at the top of the stack.
527  Vertex currentVertex = verticesToVisit.back();
528 
529  set<Vertex> currentDependentVertices;
530  bool areDependentVerticesComplete = true;
531 
532  // Form a list of vertices immediately dependent on this vertex's to-node.
533  // This includes vertices that are not downstream of this vertex because of a wall.
534  // But, if this vertex is at the end of a feedback loop, it doesn't include vertices
535  // beyond the end of the feedback loop.
536  set<Vertex> outgoingVertices;
537  set<Vertex> potentialOutgoingVertices = outgoingVerticesForNode[currentVertex.toNode];
538  for (set<Vertex>::iterator j = potentialOutgoingVertices.begin(); j != potentialOutgoingVertices.end(); ++j)
539  {
540  Vertex outgoingVertex = *j;
541  if (downstreamVertices[trigger][outgoingVertex].find(currentVertex) == downstreamVertices[trigger][outgoingVertex].end())
542  outgoingVertices.insert(outgoingVertex);
543  else
544  {
545  outgoingVertices.clear();
546  break;
547  }
548  }
549 
550  for (set<Vertex>::iterator j = outgoingVertices.begin(); j != outgoingVertices.end(); ++j)
551  {
552  Vertex outgoingVertex = *j;
553  currentDependentVertices.insert(outgoingVertex);
554 
555  if (verticesCompleted[outgoingVertex])
556  {
557  // The dependent vertex has already been visited, so add its dependent vertices to this vertex's.
558  currentDependentVertices.insert( dependentVertices[outgoingVertex].begin(), dependentVertices[outgoingVertex].end() );
559  }
560  else if (find(verticesToVisit.begin(), verticesToVisit.end(), outgoingVertex) == verticesToVisit.end())
561  {
562  // The dependent vertex has not yet been visited, so add it to the stack.
563  verticesToVisit.push_back(outgoingVertex);
564  areDependentVerticesComplete = false;
565  }
566  }
567 
568  if (areDependentVerticesComplete)
569  {
570  dependentVertices[currentVertex] = currentDependentVertices;
571  verticesToVisit.pop_back();
572  verticesCompleted[currentVertex] = true;
573  }
574  }
575 
576  // Put the vertices in descending order of the number of vertices that can't be reached until after the vertex.
577  vector< pair<size_t, Vertex> > verticesAndDependents;
578  for (map<Vertex, set<Vertex> >::iterator j = dependentVertices.begin(); j != dependentVertices.end(); ++j)
579  verticesAndDependents.push_back( make_pair(j->second.size(), j->first) );
580  sort(verticesAndDependents.begin(), verticesAndDependents.end());
581 
582  vector<Vertex> sortedVertices;
583  for (vector< pair<size_t, Vertex> >::reverse_iterator j = verticesAndDependents.rbegin(); j != verticesAndDependents.rend(); ++j)
584  sortedVertices.push_back((*j).second);
585 
586  vertices[trigger] = sortedVertices;
587  }
588 }
589 
593 void VuoCompilerGraph::makeVertexDistances(void)
594 {
595  for (map<VuoCompilerTriggerPort *, vector<Vertex> >::iterator i = vertices.begin(); i != vertices.end(); ++i)
596  {
597  VuoCompilerTriggerPort *trigger = i->first;
598  vector<Vertex> verticesDownstream = i->second;
599 
600  map<VuoCompilerNode *, set<Vertex> > incomingVerticesForNode; // Cached data to speed up search for incoming vertices.
601  for (vector<Vertex>::iterator j = verticesDownstream.begin(); j != verticesDownstream.end(); ++j)
602  incomingVerticesForNode[(*j).toNode].insert(*j);
603 
604  // Handle vertices immediately downstream of the trigger.
605  for (vector<Vertex>::iterator j = verticesDownstream.begin(); j != verticesDownstream.end(); ++j)
606  {
607  Vertex vertex = *j;
608  if (vertex.fromTrigger == trigger)
609  {
610  vertexDistanceFromTrigger[trigger][vertex] = 1;
611  triggerMustTransmitToVertex[trigger][vertex] = true;
612  }
613  }
614 
615  // Handle vertices further downstream.
616  for (vector<Vertex>::iterator j = verticesDownstream.begin(); j != verticesDownstream.end(); ++j)
617  {
618  Vertex vertex = *j;
619  if (vertex.fromTrigger != trigger)
620  {
621  size_t minDistance = verticesDownstream.size();
622  bool anyMustTransmit = false;
623  for (set<Vertex>::iterator k = incomingVerticesForNode[vertex.fromNode].begin(); k != incomingVerticesForNode[vertex.fromNode].end(); ++k)
624  {
625  Vertex upstreamVertex = *k;
626 
627  minDistance = min(vertexDistanceFromTrigger[trigger][upstreamVertex], minDistance);
628  bool currMustTransmit = triggerMustTransmitToVertex[trigger][upstreamVertex] && mustTransmit(upstreamVertex, trigger);
629  anyMustTransmit = currMustTransmit || anyMustTransmit;
630  }
631 
632  vertexDistanceFromTrigger[trigger][vertex] = minDistance + 1;
633  triggerMustTransmitToVertex[trigger][vertex] = anyMustTransmit;
634  }
635  }
636  }
637 }
638 
642 void VuoCompilerGraph::makeDownstreamNodesViaDataOnlyTransmission(set<VuoNode *> nodes, set<VuoCable *> cables)
643 {
644  // @todo Maybe this could be refactored to call makeDownstreamVerticesWithInclusionRule.
645 
646  // Find all nodes that can transmit through their output data cables, and put them in topological order.
647  // (Assumes the nodes don't have walled ports, so they can't have different topological orders for different triggers.)
648 
649  map<VuoCompilerNode *, set<VuoCompilerNode *> > remainingIncomingNodes;
650  map<VuoCompilerNode *, set<VuoCompilerNode *> > remainingOutgoingNodes;
651  for (VuoCable *cable : cables)
652  {
653  VuoCompilerPort *fromPort = cable->getFromPort() ? static_cast<VuoCompilerPort *>(cable->getFromPort()->getCompiler()) : nullptr;
654  VuoCompilerTriggerPort *fromTrigger = dynamic_cast<VuoCompilerTriggerPort *>(fromPort);
655  if (fromTrigger || ! cable->getCompiler()->carriesData())
656  continue; // Ignore cables that can't transmit without an event.
657 
658  VuoCompilerNode *fromNode = cable->getFromNode()->getCompiler();
659  VuoCompilerNode *toNode = cable->getToNode()->getCompiler();
660 
661  if (mayTransmitDataOnly(fromNode))
662  {
663  remainingOutgoingNodes[fromNode].insert(toNode);
664  if (mayTransmitDataOnly(toNode))
665  remainingIncomingNodes[toNode].insert(fromNode);
666  }
667  }
668  map<VuoCompilerNode *, set<VuoCompilerNode *> > outgoingNodes = remainingOutgoingNodes;
669 
670  set<VuoCompilerNode *> nodesToVisit;
671  for (VuoNode *node : nodes)
672  {
673  if (mayTransmitDataOnly(node->getCompiler()) &&
674  remainingIncomingNodes.find(node->getCompiler()) == remainingIncomingNodes.end() &&
675  remainingOutgoingNodes.find(node->getCompiler()) != remainingOutgoingNodes.end())
676  nodesToVisit.insert(node->getCompiler());
677  }
678 
679  vector<VuoCompilerNode *> sortedNodesAllowingDataOnlyTransmission;
680  while (! nodesToVisit.empty())
681  {
682  VuoCompilerNode *node = *nodesToVisit.begin();
683  nodesToVisit.erase(nodesToVisit.begin());
684 
685  sortedNodesAllowingDataOnlyTransmission.push_back(node);
686 
687  set<VuoCompilerNode *> outgoingNodesCopy = remainingOutgoingNodes[node];
688  for (VuoCompilerNode *outgoingNode : outgoingNodesCopy)
689  {
690  remainingIncomingNodes[outgoingNode].erase(node);
691  remainingOutgoingNodes[node].erase(outgoingNode);
692 
693  if (remainingIncomingNodes[outgoingNode].empty())
694  nodesToVisit.insert(outgoingNode);
695  }
696  }
697 
698  // For each of those nodes, find the nodes that are downstream of it via eventless transmission, in topological order.
699 
700  for (int firstIndex = sortedNodesAllowingDataOnlyTransmission.size() - 1; firstIndex >= 0; --firstIndex)
701  {
702  VuoCompilerNode *firstNode = sortedNodesAllowingDataOnlyTransmission[firstIndex];
703 
704  for (size_t possiblyDownstreamIndex = firstIndex + 1; possiblyDownstreamIndex < sortedNodesAllowingDataOnlyTransmission.size(); ++possiblyDownstreamIndex)
705  {
706  VuoCompilerNode *possiblyDownstreamNode = sortedNodesAllowingDataOnlyTransmission[possiblyDownstreamIndex];
707 
708  if (outgoingNodes[firstNode].find(possiblyDownstreamNode) != outgoingNodes[firstNode].end())
709  {
710  vector<VuoCompilerNode *> nodesToAdd = downstreamNodesViaDataOnlyTransmission[possiblyDownstreamNode];
711  nodesToAdd.insert(nodesToAdd.begin(), possiblyDownstreamNode);
712 
713  for (VuoCompilerNode *nodeToAdd : nodesToAdd)
714  if (find(downstreamNodesViaDataOnlyTransmission[firstNode].begin(), downstreamNodesViaDataOnlyTransmission[firstNode].end(), nodeToAdd) == downstreamNodesViaDataOnlyTransmission[firstNode].end())
715  downstreamNodesViaDataOnlyTransmission[firstNode].push_back(nodeToAdd);
716  }
717  }
718  }
719 }
720 
727 bool VuoCompilerGraph::mustTransmit(const set<VuoCompilerCable *> &fromCables, const set<VuoCompilerCable *> &toCables)
728 {
729  bool fromCablesMustTransmit = false;
730  for (VuoCompilerCable *cable : fromCables)
731  {
732  VuoPort *inputPort = cable->getBase()->getToPort();
733  if (inputPort->getClass()->getEventBlocking() == VuoPortClass::EventBlocking_None)
734  {
735  fromCablesMustTransmit = true;
736  break;
737  }
738  }
739 
740  bool toCablesMayTransmit = false;
741  for (VuoCompilerCable *cable : toCables)
742  {
743  VuoPort *outputPort = cable->getBase()->getFromPort();
744  if (! outputPort || outputPort->getClass()->getPortType() != VuoPortClass::triggerPort)
745  {
746  toCablesMayTransmit = true;
747  break;
748  }
749  }
750 
751  return fromCablesMustTransmit && toCablesMayTransmit;
752 }
753 
757 bool VuoCompilerGraph::mustTransmit(Vertex vertex, VuoCompilerTriggerPort *trigger)
758 {
759  set<VuoCompilerCable *> cablesBetweenFromNodeAndToNode = vertex.cableBundle;
760 
761  set<VuoCompilerCable *> cablesOutOfToNode;
762  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
763  {
764  Vertex otherVertex = *i;
765  if (vertex.toNode == otherVertex.fromNode)
766  cablesOutOfToNode.insert(otherVertex.cableBundle.begin(), otherVertex.cableBundle.end());
767  }
768 
769  return mustTransmit(cablesBetweenFromNodeAndToNode, cablesOutOfToNode);
770 }
771 
772 
779 bool VuoCompilerGraph::mayTransmit(const set<VuoCompilerCable *> &fromCables, const set<VuoCompilerCable *> &toCables)
780 {
781  bool fromCablesMayTransmit = false;
782  for (VuoCompilerCable *cable : fromCables)
783  {
784  VuoPort *inputPort = cable->getBase()->getToPort();
785  if (inputPort->getClass()->getEventBlocking() != VuoPortClass::EventBlocking_Wall)
786  {
787  fromCablesMayTransmit = true;
788  break;
789  }
790  }
791 
792  bool toCablesMayTransmit = false;
793  for (VuoCompilerCable *cable : toCables)
794  {
795  VuoPort *outputPort = cable->getBase()->getFromPort();
796  if (! outputPort || outputPort->getClass()->getPortType() != VuoPortClass::triggerPort)
797  {
798  toCablesMayTransmit = true;
799  break;
800  }
801  }
802 
803  return fromCablesMayTransmit && toCablesMayTransmit;
804 }
805 
809 bool VuoCompilerGraph::mayTransmit(Vertex vertex, VuoCompilerTriggerPort *trigger)
810 {
811  set<VuoCompilerCable *> cablesBetweenFromNodeAndToNode = vertex.cableBundle;
812 
813  set<VuoCompilerCable *> cablesOutOfToNode;
814  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
815  {
816  Vertex otherVertex = *i;
817  if (vertex.toNode == otherVertex.fromNode)
818  cablesOutOfToNode.insert(otherVertex.cableBundle.begin(), otherVertex.cableBundle.end());
819  }
820 
821  return mayTransmit(cablesBetweenFromNodeAndToNode, cablesOutOfToNode);
822 }
823 
827 bool VuoCompilerGraph::mayTransmit(VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
828 {
829  set<VuoCompilerCable *> incomingCables;
830  set<VuoCompilerCable *> outgoingCables;
831 
832  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
833  {
834  Vertex vertex = *i;
835 
836  if (vertex.toNode == node)
837  incomingCables.insert( vertex.cableBundle.begin(), vertex.cableBundle.end() );
838  if (vertex.fromNode == node)
839  outgoingCables.insert( vertex.cableBundle.begin(), vertex.cableBundle.end() );
840  }
841 
842  return mayTransmit(incomingCables, outgoingCables);
843 }
844 
848 bool VuoCompilerGraph::mayTransmit(VuoCompilerNode *fromNode, VuoCompilerNode *toNode, VuoCompilerTriggerPort *trigger)
849 {
850  if (vertexMayTransmit[trigger].empty() && ! vertices[trigger].empty())
851  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
852  vertexMayTransmit[trigger][(*i).fromNode][(*i).toNode] = true;
853 
854  return vertexMayTransmit[trigger][fromNode][toNode];
855 }
856 
860 bool VuoCompilerGraph::mayTransmitDataOnly(VuoCompilerNode *node)
861 {
862  return node->getBase()->getNodeClass()->isDrawerNodeClass() || node == publishedInputNode;
863 }
864 
868 vector<VuoCompilerTriggerPort *> VuoCompilerGraph::getTriggerPorts(void)
869 {
870  return triggers;
871 }
872 
876 VuoCompilerNode * VuoCompilerGraph::getNodeForTriggerPort(VuoCompilerTriggerPort *trigger)
877 {
878  auto foundIter = nodeForTrigger.find(trigger);
879  if (foundIter != nodeForTrigger.end())
880  return foundIter->second;
881 
882  return NULL;
883 }
884 
889 set<VuoCompilerNode *> VuoCompilerGraph::getNodes(void)
890 {
891  return nodes;
892 }
893 
899 VuoCompilerNode * VuoCompilerGraph::getPublishedInputNode(void)
900 {
901  return publishedInputNode;
902 }
903 
909 VuoCompilerNode * VuoCompilerGraph::getPublishedOutputNode(void)
910 {
911  return publishedOutputNode;
912 }
913 
917 VuoCompilerTriggerPort * VuoCompilerGraph::getPublishedInputTrigger(void)
918 {
919  return publishedInputTrigger;
920 }
921 
925 VuoPort * VuoCompilerGraph::getInputPortOnPublishedInputNode(size_t publishedInputPortIndex)
926 {
927  VuoCompilerPublishedInputNodeClass *publishedInputNodeClass = static_cast<VuoCompilerPublishedInputNodeClass *>(publishedInputNode->getBase()->getNodeClass()->getCompiler());
928  size_t portIndex = publishedInputNodeClass->getInputPortIndexForPublishedInputPort(publishedInputPortIndex);
929  return publishedInputNode->getBase()->getInputPorts().at(portIndex);
930 }
931 
935 VuoPort * VuoCompilerGraph::getOutputPortOnPublishedInputNode(size_t publishedInputPortIndex)
936 {
937  VuoCompilerPublishedInputNodeClass *publishedInputNodeClass = static_cast<VuoCompilerPublishedInputNodeClass *>(publishedInputNode->getBase()->getNodeClass()->getCompiler());
938  size_t portIndex = publishedInputNodeClass->getOutputPortIndexForPublishedInputPort(publishedInputPortIndex);
939  return publishedInputNode->getBase()->getOutputPorts().at(portIndex);
940 }
941 
945 VuoPort * VuoCompilerGraph::getInputPortOnPublishedOutputNode(size_t publishedOutputPortIndex)
946 {
947  VuoCompilerPublishedOutputNodeClass *publishedOutputNodeClass = static_cast<VuoCompilerPublishedOutputNodeClass *>(publishedOutputNode->getBase()->getNodeClass()->getCompiler());
948  size_t portIndex = publishedOutputNodeClass->getInputPortIndexForPublishedOutputPort(publishedOutputPortIndex);
949  return publishedOutputNode->getBase()->getInputPorts().at(portIndex);
950 }
951 
955 VuoPort * VuoCompilerGraph::getGatherPortOnPublishedOutputNode(void)
956 {
957  VuoCompilerPublishedOutputNodeClass *publishedOutputNodeClass = static_cast<VuoCompilerPublishedOutputNodeClass *>(publishedOutputNode->getBase()->getNodeClass()->getCompiler());
958  size_t portIndex = publishedOutputNodeClass->getGatherInputPortIndex();
959  return publishedOutputNode->getBase()->getInputPorts().at(portIndex);
960 }
961 
965 VuoCompilerTriggerPort * VuoCompilerGraph::getManuallyFirableTrigger(void)
966 {
967  return manuallyFirableTrigger;
968 }
969 
973 size_t VuoCompilerGraph::getNumVerticesWithFromNode(VuoCompilerNode *fromNode, VuoCompilerTriggerPort *trigger)
974 {
975  int numVertices = 0;
976  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
977  if ((*i).fromNode == fromNode)
978  ++numVertices;
979 
980  return numVertices;
981 }
982 
986 size_t VuoCompilerGraph::getNumVerticesWithToNode(VuoCompilerNode *toNode, VuoCompilerTriggerPort *trigger)
987 {
988  map<VuoCompilerTriggerPort *, map<VuoCompilerNode *, size_t> >::iterator triggerIter = numVerticesWithToNode.find(trigger);
989  if (triggerIter != numVerticesWithToNode.end())
990  {
991  map<VuoCompilerNode *, size_t>::iterator nodeIter = triggerIter->second.find(toNode);
992  if (nodeIter != triggerIter->second.end())
993  return nodeIter->second;
994  }
995 
996  size_t numVertices = 0;
997  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
998  if ((*i).toNode == toNode)
999  ++numVertices;
1000 
1001  numVerticesWithToNode[trigger][toNode] = numVertices;
1002  return numVertices;
1003 }
1004 
1016 map<VuoCompilerTriggerPort *, vector<VuoCompilerChain *> > VuoCompilerGraph::getChains(void)
1017 {
1018  if (! chains.empty())
1019  return chains;
1020 
1021  for (VuoCompilerTriggerPort *trigger : triggers)
1022  {
1023  // Visit the vertices in topological order, and put the nodes into lists (chains-in-progress).
1024  vector< vector<VuoCompilerNode *> > chainsInProgress;
1025  set<VuoCompilerNode *> nodesAdded;
1026  bool skippedPublishedOutputNode = false;
1027  for (vector<Vertex>::iterator j = vertices[trigger].begin(); j != vertices[trigger].end(); ++j)
1028  {
1029  Vertex vertex = *j;
1030  bool addedToChain = false;
1031 
1032  if (nodesAdded.find(vertex.toNode) != nodesAdded.end())
1033  continue; // Avoid creating duplicate chains for nodes with gathers (multiple incoming vertices).
1034 
1035  if (vertex.toNode == publishedOutputNode)
1036  {
1037  skippedPublishedOutputNode = true;
1038  continue; // Save the published output node for last.
1039  }
1040 
1041  nodesAdded.insert(vertex.toNode);
1042 
1043  if (vertex.fromNode)
1044  {
1045  if (getNumVerticesWithFromNode(vertex.fromNode, trigger) == 1 &&
1046  getNumVerticesWithToNode(vertex.toNode, trigger) == 1)
1047  {
1048  for (int k = 0; k < chainsInProgress.size(); ++k)
1049  {
1050  VuoCompilerNode *lastNodeInChain = chainsInProgress[k].back();
1051  if (lastNodeInChain == vertex.fromNode)
1052  {
1053  // Add vertex.toNode to an existing chain-in-progress.
1054  chainsInProgress[k].push_back(vertex.toNode);
1055  addedToChain = true;
1056  break;
1057  }
1058  }
1059  }
1060  }
1061 
1062  if (! addedToChain)
1063  {
1064  // Create a new chain-in-progress that starts with vertex.toNode.
1065  chainsInProgress.push_back( vector<VuoCompilerNode *>(1, vertex.toNode) );
1066  }
1067  }
1068 
1069  // Turn the chains-in-progress into actual chains.
1070  for (vector< vector<VuoCompilerNode *> >::iterator j = chainsInProgress.begin(); j != chainsInProgress.end(); ++j)
1071  {
1072  vector<VuoCompilerNode *> chainNodes = *j;
1073  VuoCompilerChain *chain = new VuoCompilerChain(chainNodes, false);
1074  chains[trigger].push_back(chain);
1075  }
1076 
1077  // Create a new chain for each node that is the repeated node in a feedback loop.
1078  map<VuoCompilerNode *, bool> nodesSeen;
1079  for (vector<Vertex>::iterator j = vertices[trigger].begin(); j != vertices[trigger].end(); ++j)
1080  {
1081  VuoCompilerNode *node = (*j).toNode;
1082  if (nodesSeen[node])
1083  continue;
1084  nodesSeen[node] = true;
1085 
1086  if (isRepeatedInFeedbackLoop(node, trigger))
1087  {
1088  VuoCompilerChain *chain = new VuoCompilerChain(vector<VuoCompilerNode *>(1, node), true);
1089  chains[trigger].push_back(chain);
1090  }
1091  }
1092 
1093  // Create a new chain for the published output node.
1094  if (skippedPublishedOutputNode)
1095  {
1096  VuoCompilerChain *chain = new VuoCompilerChain(vector<VuoCompilerNode *>(1, publishedOutputNode), false);
1097  chains[trigger].push_back(chain);
1098  }
1099  }
1100 
1101  return chains;
1102 }
1103 
1107 vector<VuoCompilerNode *> VuoCompilerGraph::getNodesImmediatelyDownstream(VuoCompilerTriggerPort *trigger)
1108 {
1109  set<VuoCompilerNode *> downstreamNodes;
1110  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
1111  if ((*i).fromTrigger == trigger)
1112  downstreamNodes.insert((*i).toNode);
1113 
1114  return vector<VuoCompilerNode *>(downstreamNodes.begin(), downstreamNodes.end());
1115 }
1116 
1120 vector<VuoCompilerNode *> VuoCompilerGraph::getNodesImmediatelyDownstream(VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
1121 {
1122  set<VuoCompilerNode *> downstreamNodes;
1123  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
1124  if ((*i).fromNode == node)
1125  downstreamNodes.insert((*i).toNode);
1126 
1127  return vector<VuoCompilerNode *>(downstreamNodes.begin(), downstreamNodes.end());
1128 }
1129 
1133 vector<VuoCompilerNode *> VuoCompilerGraph::getNodesDownstream(VuoCompilerTriggerPort *trigger)
1134 {
1135  map<VuoCompilerTriggerPort *, vector<VuoCompilerNode *> >::iterator triggerIter = downstreamNodesForTrigger.find(trigger);
1136  if (triggerIter != downstreamNodesForTrigger.end())
1137  return triggerIter->second;
1138 
1139  set<VuoCompilerNode *> downstreamNodes;
1140  vector<VuoCompilerNode *> immediatelyDownstreamNodes = getNodesImmediatelyDownstream(trigger);
1141  downstreamNodes.insert(immediatelyDownstreamNodes.begin(), immediatelyDownstreamNodes.end());
1142 
1143  for (vector<VuoCompilerNode *>::iterator i = immediatelyDownstreamNodes.begin(); i != immediatelyDownstreamNodes.end(); ++i)
1144  {
1145  vector<VuoCompilerNode *> furtherDownstreamNodes = getNodesDownstream(*i, trigger);
1146  downstreamNodes.insert(furtherDownstreamNodes.begin(), furtherDownstreamNodes.end());
1147  }
1148 
1149  vector<VuoCompilerNode *> downstreamNodesVector(downstreamNodes.begin(), downstreamNodes.end());
1150  downstreamNodesForTrigger[trigger] = downstreamNodesVector;
1151  return downstreamNodesVector;
1152 }
1153 
1157 vector<VuoCompilerNode *> VuoCompilerGraph::getNodesDownstream(VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
1158 {
1159  map<VuoCompilerTriggerPort *, map<VuoCompilerNode *, vector<VuoCompilerNode *> > >::iterator triggerIter = downstreamNodesForNode.find(trigger);
1160  if (triggerIter != downstreamNodesForNode.end())
1161  {
1162  map<VuoCompilerNode *, vector<VuoCompilerNode *> >::iterator nodeIter = triggerIter->second.find(node);
1163  if (nodeIter != triggerIter->second.end())
1164  return nodeIter->second;
1165  }
1166 
1167  set<Vertex> verticesWithDownstreamNodes;
1168  for (vector<Vertex>::iterator i = vertices[trigger].begin(); i != vertices[trigger].end(); ++i)
1169  {
1170  Vertex vertex = *i;
1171  if (vertex.fromNode == node)
1172  {
1173  verticesWithDownstreamNodes.insert(vertex);
1174  set<Vertex> downstream = downstreamVertices[trigger][vertex];
1175  verticesWithDownstreamNodes.insert(downstream.begin(), downstream.end());
1176  }
1177  }
1178 
1179  set<VuoCompilerNode *> downstreamNodes;
1180  for (set<Vertex>::iterator i = verticesWithDownstreamNodes.begin(); i != verticesWithDownstreamNodes.end(); ++i)
1181  downstreamNodes.insert((*i).toNode);
1182 
1183  vector<VuoCompilerNode *> downstreamNodesVector(downstreamNodes.begin(), downstreamNodes.end());
1184  downstreamNodesForNode[trigger][node] = downstreamNodesVector;
1185  return downstreamNodesVector;
1186 }
1187 
1192 vector<VuoCompilerNode *> VuoCompilerGraph::getNodesDownstreamViaDataOnlyTransmission(VuoCompilerNode *node)
1193 {
1194  return downstreamNodesViaDataOnlyTransmission[node];
1195 }
1196 
1202 set<VuoCompilerCable *> VuoCompilerGraph::getOutgoingCables(VuoCompilerPort *outputPort)
1203 {
1204  set<VuoCompilerCable *> outgoingCables;
1205 
1206  // Add cables from the original composition.
1207 
1208  for (VuoCable *cable : outputPort->getBase()->getConnectedCables())
1209  if (cable->getToNode() && cable->getToNode()->hasCompiler())
1210  outgoingCables.insert(cable->getCompiler());
1211 
1212  // Add any other cables created for graph analysis.
1213 
1214  for (map<VuoCompilerTriggerPort *, vector<Vertex> >::value_type kv : vertices)
1215  for (Vertex vertex : kv.second)
1216  for (VuoCompilerCable *cable : vertex.cableBundle)
1217  if (cable->getBase()->getFromPort() == outputPort->getBase())
1218  outgoingCables.insert(cable);
1219 
1220  return outgoingCables;
1221 }
1222 
1226 set<VuoCompilerNode *> VuoCompilerGraph::getSourceNodesOfDataOnlyTransmission(void)
1227 {
1228  set<VuoCompilerNode *> nodesTransmittingDataOnly;
1229  set<VuoCompilerNode *> nodesDownstreamOfAnother;
1230 
1231  for (const map<VuoCompilerNode *, vector<VuoCompilerNode *> >::value_type &i : downstreamNodesViaDataOnlyTransmission)
1232  {
1233  nodesTransmittingDataOnly.insert(i.first);
1234  nodesDownstreamOfAnother.insert(i.second.begin(), i.second.end());
1235  }
1236 
1237  set<VuoCompilerNode *> nodesNotDownstream;
1238  std::set_difference(nodesTransmittingDataOnly.begin(), nodesTransmittingDataOnly.end(),
1239  nodesDownstreamOfAnother.begin(), nodesDownstreamOfAnother.end(),
1240  std::inserter(nodesNotDownstream, nodesNotDownstream.end()));
1241  return nodesNotDownstream;
1242 }
1243 
1248 void VuoCompilerGraph::getWorkerThreadsNeeded(VuoCompilerChain *chain, int &minThreadsNeeded, int &maxThreadsNeeded)
1249 {
1250  // Non-subcomposition nodes need 1 thread.
1251  minThreadsNeeded = 1;
1252  maxThreadsNeeded = 1;
1253 
1254  for (VuoCompilerNode *node : chain->getNodes())
1255  {
1256  VuoCompilerNodeClass *nodeClass = node->getBase()->getNodeClass()->getCompiler();
1257  vector<VuoCompilerTriggerDescription *> triggerDescriptions = nodeClass->getTriggerDescriptions();
1258 
1259  for (vector<VuoCompilerTriggerDescription *>::iterator k = triggerDescriptions.begin(); k != triggerDescriptions.end(); ++k)
1260  {
1261  if ((*k)->getNodeIdentifier() == VuoNodeClass::publishedInputNodeIdentifier)
1262  {
1263  // Subcomposition nodes need 1 thread plus those needed within the subcomposition.
1264  int minThreadsNeededForSubcomposition, maxThreadsNeededForSubcomposition;
1265  (*k)->getWorkerThreadsNeeded(minThreadsNeededForSubcomposition, maxThreadsNeededForSubcomposition);
1266  minThreadsNeeded = max(minThreadsNeeded, minThreadsNeededForSubcomposition + 1);
1267  maxThreadsNeeded = max(maxThreadsNeeded, maxThreadsNeededForSubcomposition + 1);
1268  break;
1269  }
1270  }
1271  }
1272 }
1273 
1279 void VuoCompilerGraph::getWorkerThreadsNeeded(VuoCompilerTriggerPort *trigger, int &minThreadsNeeded, int &maxThreadsNeeded)
1280 {
1281  // Make a data structure of the number of threads needed for each chain.
1282  vector<VuoCompilerChain *> chainsForTrigger = getChains()[trigger];
1283  map<VuoCompilerChain *, pair<int, int> > threadsNeededForChain;
1284  for (vector<VuoCompilerChain *>::iterator i = chainsForTrigger.begin(); i != chainsForTrigger.end(); ++i)
1285  {
1286  VuoCompilerChain *chain = *i;
1287 
1288  int minThreadsNeededForChain, maxThreadsNeededForChain;
1289  getWorkerThreadsNeeded(chain, minThreadsNeededForChain, maxThreadsNeededForChain);
1290 
1291  threadsNeededForChain[chain] = make_pair(minThreadsNeededForChain, maxThreadsNeededForChain);
1292  }
1293 
1294  // Make a data structure of which chains are downstream of which.
1295  map<VuoCompilerChain *, set<VuoCompilerChain *> > chainsDownstream;
1296  for (vector<VuoCompilerChain *>::iterator i = chainsForTrigger.begin(); i != chainsForTrigger.end(); ++i)
1297  {
1298  VuoCompilerChain *chain = *i;
1299  VuoCompilerNode *lastNodeInThisChain = chain->getNodes().back();
1300 
1301  vector<VuoCompilerNode *> nodesDownstream = getNodesDownstream(lastNodeInThisChain, trigger);
1302 
1303  for (vector<VuoCompilerChain *>::iterator j = i+1; j != chainsForTrigger.end(); ++j)
1304  {
1305  VuoCompilerChain *otherChain = *j;
1306  VuoCompilerNode *firstNodeInOtherChain = otherChain->getNodes().front();
1307 
1308  if (find(nodesDownstream.begin(), nodesDownstream.end(), firstNodeInOtherChain) != nodesDownstream.end())
1309  chainsDownstream[chain].insert(otherChain);
1310  }
1311  }
1312 
1313  // Make a data structure of which chains are immediately downstream and upstream of which.
1314  map<VuoCompilerChain *, set<VuoCompilerChain *> > chainsImmediatelyDownstream;
1315  map<VuoCompilerChain *, set<VuoCompilerChain *> > chainsImmediatelyUpstream;
1316  for (vector<VuoCompilerChain *>::iterator i = chainsForTrigger.begin(); i != chainsForTrigger.end(); ++i)
1317  {
1318  VuoCompilerChain *chain = *i;
1319  VuoCompilerNode *lastNodeInThisChain = chain->getNodes().back();
1320 
1321  vector<VuoCompilerNode *> nodesDownstream = getNodesImmediatelyDownstream(lastNodeInThisChain, trigger);
1322 
1323  for (vector<VuoCompilerChain *>::iterator j = i+1; j != chainsForTrigger.end(); ++j)
1324  {
1325  VuoCompilerChain *otherChain = *j;
1326  VuoCompilerNode *firstNodeInOtherChain = otherChain->getNodes().front();
1327 
1328  if (find(nodesDownstream.begin(), nodesDownstream.end(), firstNodeInOtherChain) != nodesDownstream.end())
1329  {
1330  chainsImmediatelyDownstream[chain].insert(otherChain);
1331  chainsImmediatelyUpstream[otherChain].insert(chain);
1332  }
1333  }
1334  }
1335 
1336  // Every trigger worker needs at least 1 thread, since it waits on the trigger node's semaphore.
1337  minThreadsNeeded = 1;
1338  maxThreadsNeeded = 1;
1339 
1340 
1341  // Find the maximum number of threads required — an approximation. Ideally, this is the thread count if
1342  // all chains that can possibly execute concurrently do so. This is approximated by adding up the thread
1343  // count for all scatters, scatters of scatters, etc., without taking into account any gathers. It may
1344  // be an overestimate of the ideal thread count.
1345 
1346  // Collect the chains immediately downstream of the trigger.
1347  vector< pair<VuoCompilerChain *, vector<VuoCompilerChain *> > > potentialScatters;
1348  vector<VuoCompilerChain *> scatterForTrigger;
1349  for (vector<VuoCompilerChain *>::iterator i = chainsForTrigger.begin(); i != chainsForTrigger.end(); ++i)
1350  if (chainsImmediatelyUpstream.find(*i) == chainsImmediatelyUpstream.end())
1351  scatterForTrigger.push_back(*i);
1352  potentialScatters.push_back( make_pair((VuoCompilerChain *)NULL, scatterForTrigger) );
1353 
1354  // Add in the chains immediately downstream of each chain.
1355  for (vector<VuoCompilerChain *>::iterator i = chainsForTrigger.begin(); i != chainsForTrigger.end(); ++i)
1356  {
1357  vector<VuoCompilerChain *> scatterForChain(chainsImmediatelyDownstream[*i].begin(), chainsImmediatelyDownstream[*i].end());
1358  potentialScatters.push_back( make_pair(*i, scatterForChain) );
1359  }
1360 
1361  map<VuoCompilerChain *, int> threadsNeededForScatters;
1362  for (vector< pair<VuoCompilerChain *, vector<VuoCompilerChain *> > >::reverse_iterator i = potentialScatters.rbegin(); i != potentialScatters.rend(); ++i)
1363  {
1364  VuoCompilerChain *chain = (*i).first;
1365  vector<VuoCompilerChain *> scatterChains = (*i).second;
1366 
1367  // Discard any chains that are downstream of another in the collection,
1368  // leaving a group of chains that may all execute concurrently.
1369  for (size_t j = 0; j < scatterChains.size(); ++j)
1370  {
1371  VuoCompilerChain *outer = scatterChains[j];
1372 
1373  for (size_t k = j+1; k < scatterChains.size(); ++k)
1374  {
1375  VuoCompilerChain *inner = scatterChains[k];
1376 
1377  if (chainsDownstream[inner].find(outer) != chainsDownstream[inner].end())
1378  {
1379  scatterChains.erase( scatterChains.begin() + j-- );
1380  break;
1381  }
1382 
1383  if (chainsDownstream[outer].find(inner) != chainsDownstream[outer].end())
1384  scatterChains.erase( scatterChains.begin() + k-- );
1385  }
1386  }
1387 
1388  // Add up the threads needed for the chains in the scatter.
1389  int threadsNeededForScatter = 0;
1390  for (vector<VuoCompilerChain *>::iterator j = scatterChains.begin(); j != scatterChains.end(); ++j)
1391  threadsNeededForScatter += threadsNeededForScatters[*j];
1392 
1393  // Factor in the threads needed for this chain itself.
1394  threadsNeededForScatter = max(threadsNeededForScatter, threadsNeededForChain[chain].second);
1395 
1396  threadsNeededForScatters[chain] = threadsNeededForScatter;
1397  }
1398 
1399  // Find the maximum threads needed for any chain and its downstream scatters.
1400  for (map<VuoCompilerChain *, int>::iterator i = threadsNeededForScatters.begin(); i != threadsNeededForScatters.end(); ++i)
1401  maxThreadsNeeded = max(maxThreadsNeeded, i->second);
1402 
1403 
1404  // Find the minimum number of threads required. This is the thread count if all chains execute sequentially,
1405  // which is the maximum of the minimum threads needed across all chains in the composition. If the trigger
1406  // has no downstream chains, the trigger worker still needs 1 thread to wait on the trigger node's semaphore.
1407 
1408  for (map<VuoCompilerChain *, pair<int, int> >::iterator i = threadsNeededForChain.begin(); i != threadsNeededForChain.end(); ++i)
1409  minThreadsNeeded = max(minThreadsNeeded, i->second.first);
1410 }
1411 
1422 VuoCompilerTriggerPort * VuoCompilerGraph::findNearestUpstreamTrigger(VuoCompilerNode *node)
1423 {
1424  vector< pair<VuoCompilerTriggerPort *, size_t> > distancesForMusts;
1425  vector< pair<VuoCompilerTriggerPort *, size_t> > distancesForMays;
1426 
1427  for (map<VuoCompilerTriggerPort *, vector<Vertex> >::iterator i = vertices.begin(); i != vertices.end(); ++i)
1428  {
1429  VuoCompilerTriggerPort *trigger = i->first;
1430  vector<Vertex> verticesDownstream = i->second;
1431 
1432  for (vector<Vertex>::iterator j = verticesDownstream.begin(); j != verticesDownstream.end(); ++j)
1433  {
1434  Vertex vertex = *j;
1435  if (vertex.toNode == node)
1436  {
1437  pair<VuoCompilerTriggerPort *, size_t> p = make_pair(trigger, vertexDistanceFromTrigger[trigger][vertex]);
1438  if (triggerMustTransmitToVertex[trigger][vertex])
1439  distancesForMusts.push_back(p);
1440  else
1441  distancesForMays.push_back(p);
1442  }
1443  }
1444  }
1445 
1446  if (! distancesForMusts.empty())
1447  {
1448  sort(distancesForMusts.begin(), distancesForMusts.end(), compareTriggers);
1449  return distancesForMusts[0].first;
1450  }
1451  else if (! distancesForMays.empty())
1452  {
1453  sort(distancesForMays.begin(), distancesForMays.end(), compareTriggers);
1454  return distancesForMays[0].first;
1455  }
1456  else
1457  return NULL;
1458 }
1459 
1464 bool VuoCompilerGraph::compareTriggers(const pair<VuoCompilerTriggerPort *, size_t> &lhs, const pair<VuoCompilerTriggerPort *, size_t> &rhs)
1465 {
1466  if (lhs.second == rhs.second)
1467  return lhs.first->getIdentifier() < rhs.first->getIdentifier();
1468 
1469  return lhs.second < rhs.second;
1470 }
1471 
1483 VuoPortClass::EventBlocking VuoCompilerGraph::getPublishedInputEventBlocking(size_t publishedInputPortIndex)
1484 {
1485  if (! publishedInputTrigger)
1486  return VuoPortClass::EventBlocking_None;
1487 
1488  // If no event-only or data-and-event published output ports, return "none".
1489 
1490  VuoCompilerPublishedOutputNodeClass *publishedOutputNodeClass = static_cast<VuoCompilerPublishedOutputNodeClass *>(publishedOutputNode->getBase()->getNodeClass()->getCompiler());
1491  size_t publishedOutputCount = publishedOutputNodeClass->getGatherInputPortIndex() - VuoNodeClass::unreservedInputPortStartIndex;
1492  set<string> publishedOutputTriggers = getPublishedOutputTriggers();
1493  if (publishedOutputCount - publishedOutputTriggers.size() == 0)
1494  return VuoPortClass::EventBlocking_None;
1495 
1496  VuoPort *outputPort = getOutputPortOnPublishedInputNode(publishedInputPortIndex);
1497 
1498  set<Vertex> verticesFromPublishedInputNode;
1499  for (Vertex vertex : vertices[publishedInputTrigger])
1500  if (vertex.fromNode == publishedInputNode)
1501  verticesFromPublishedInputNode.insert(vertex);
1502 
1503  // Find the vertices downstream of the published input node with no intervening doors or walls.
1504 
1505  auto includeNonBlocking = [this] (Edge edge)
1506  {
1507  return (edge.fromVertex.fromTrigger == publishedInputTrigger ||
1508  mustTransmit(edge.fromVertex.cableBundle, edge.toVertex.cableBundle));
1509  };
1510 
1511  if (downstreamVerticesNonBlocking.empty())
1512  {
1513  set<Vertex> unused;
1514  makeDownstreamVerticesWithInclusionRule(publishedInputTrigger, includeNonBlocking, downstreamVerticesNonBlocking, unused);
1515  }
1516 
1517  // Find the vertices downstream of the published input node with no intervening walls.
1518 
1519  auto includeNonBlockingAndDoor = [this] (Edge edge)
1520  {
1521  return (edge.fromVertex.fromTrigger == publishedInputTrigger ||
1522  mayTransmit(edge.fromVertex.cableBundle, edge.toVertex.cableBundle));
1523  };
1524 
1525  if (downstreamVerticesNonBlockingOrDoor.empty())
1526  {
1527  set<Vertex> unused;
1528  makeDownstreamVerticesWithInclusionRule(publishedInputTrigger, includeNonBlockingAndDoor, downstreamVerticesNonBlockingOrDoor, unused);
1529  }
1530 
1531  auto minBlocking = [] (VuoPortClass::EventBlocking b1, VuoPortClass::EventBlocking b2)
1532  {
1533  // Returns the one that lets more events through.
1534  return min(b1, b2);
1535  };
1536 
1537  auto maxBlocking = [] (VuoPortClass::EventBlocking b1, VuoPortClass::EventBlocking b2)
1538  {
1539  // Returns the one that blocks more events.
1540  return max(b1, b2);
1541  };
1542 
1543  VuoPortClass::EventBlocking blocking = VuoPortClass::EventBlocking_Wall;
1544  vector<Vertex> verticesToPublishedOutputNode;
1545  for (Vertex vertex : verticesFromPublishedInputNode)
1546  {
1547  VuoPortClass::EventBlocking blockingForVertex = VuoPortClass::EventBlocking_Wall;
1548 
1549  // Check the event blocking for the exact cables connected to the output port on the published input node.
1550  for (VuoCompilerCable *cable : vertex.cableBundle)
1551  {
1552  if (cable->getBase()->getFromPort() == outputPort)
1553  {
1554  VuoPortClass::EventBlocking toPortBlocking = cable->getBase()->getToPort()->getClass()->getEventBlocking();
1555  blockingForVertex = minBlocking(blockingForVertex, toPortBlocking);
1556  }
1557  }
1558 
1559  if (blockingForVertex == VuoPortClass::EventBlocking_Wall)
1560  {
1561  // If the event is blocked at the cables from the published input node's output port, it's a wall.
1562  }
1563  else
1564  {
1565  auto isVertexToPublishedOutputNode = [this] (Vertex downstreamVertex) { return downstreamVertex.toNode == publishedOutputNode; };
1566 
1567  vector<Vertex> verticesNonBlocking;
1568  std::copy_if(downstreamVerticesNonBlocking[vertex].begin(), downstreamVerticesNonBlocking[vertex].end(),
1569  std::back_inserter(verticesNonBlocking), isVertexToPublishedOutputNode);
1570 
1571  verticesToPublishedOutputNode.insert(verticesToPublishedOutputNode.end(), verticesNonBlocking.begin(), verticesNonBlocking.end());
1572 
1573  if (! verticesNonBlocking.empty())
1574  {
1575  // If the event can reach the published outputs without any further blocking, it's whatever blocking
1576  // the cables from the published input node's output port have (none or door).
1577  }
1578  else
1579  {
1580  vector<Vertex> verticesNonBlockingOrDoor;
1581  std::copy_if(downstreamVerticesNonBlockingOrDoor[vertex].begin(), downstreamVerticesNonBlockingOrDoor[vertex].end(),
1582  std::back_inserter(verticesNonBlockingOrDoor), isVertexToPublishedOutputNode);
1583 
1584  verticesToPublishedOutputNode.insert(verticesToPublishedOutputNode.end(), verticesNonBlocking.begin(), verticesNonBlocking.end());
1585 
1586  if (! verticesNonBlockingOrDoor.empty())
1587  {
1588  // If the event can reach the published outputs via door blocking, it's a door.
1589  blockingForVertex = VuoPortClass::EventBlocking_Door;
1590  }
1591  else
1592  {
1593  // If the event can't reach the published outputs, it's a wall.
1594  blockingForVertex = VuoPortClass::EventBlocking_Wall;
1595  }
1596  }
1597  }
1598 
1599  blocking = minBlocking(blocking, blockingForVertex);
1600  }
1601 
1602  // If the event can reach some but not all of the non-trigger published outputs, it's a door.
1603 
1604  set<VuoPort *> publishedOutputPortsReached;
1605  for (Vertex vertex : verticesToPublishedOutputNode)
1606  for (VuoCompilerCable *cable : vertex.cableBundle)
1607  if (publishedOutputTriggers.find(cable->getBase()->getToPort()->getClass()->getName()) == publishedOutputTriggers.end())
1608  publishedOutputPortsReached.insert(cable->getBase()->getToPort());
1609 
1610  if (publishedOutputPortsReached.size() < publishedOutputCount - publishedOutputTriggers.size())
1611  blocking = maxBlocking(blocking, VuoPortClass::EventBlocking_Door);
1612 
1613  return blocking;
1614 }
1615 
1620 set<string> VuoCompilerGraph::getPublishedOutputTriggers(void)
1621 {
1622  set<string> triggerNames;
1623  for (VuoCompilerTriggerPort *trigger : triggers)
1624  {
1625  set<string> currTriggerNames = getPublishedOutputTriggersDownstream(trigger);
1626  triggerNames.insert(currTriggerNames.begin(), currTriggerNames.end());
1627  }
1628 
1629  return triggerNames;
1630 }
1631 
1636 set<string> VuoCompilerGraph::getPublishedOutputTriggersDownstream(VuoCompilerTriggerPort *trigger)
1637 {
1638  if (trigger == publishedInputTrigger)
1639  return set<string>();
1640 
1641  set<string> outputNames = getPublishedOutputPortsDownstream(trigger);
1642  set<string> outputNamesForPublishedInputTrigger = getPublishedOutputPortsDownstream(publishedInputTrigger);
1643 
1644  set<string> triggerNames;
1645  std::set_difference(outputNames.begin(), outputNames.end(),
1646  outputNamesForPublishedInputTrigger.begin(), outputNamesForPublishedInputTrigger.end(),
1647  std::inserter(triggerNames, triggerNames.begin()));
1648 
1649  return triggerNames;
1650 }
1651 
1655 set<string> VuoCompilerGraph::getPublishedOutputPortsDownstream(VuoCompilerTriggerPort *trigger)
1656 {
1657  auto iter = publishedOutputNames.find(trigger);
1658  if (iter != publishedOutputNames.end())
1659  return iter->second;
1660 
1661  set<string> names;
1662  for (Vertex vertex : vertices[trigger])
1663  {
1664  if (vertex.toNode == publishedOutputNode)
1665  {
1666  for (VuoCompilerCable *cable : vertex.cableBundle)
1667  {
1668  VuoPort *toPort = cable->getBase()->getToPort();
1669  if (toPort != getGatherPortOnPublishedOutputNode())
1670  names.insert(toPort->getClass()->getName());
1671  }
1672  }
1673  }
1674 
1675  publishedOutputNames[trigger] = names;
1676  return names;
1677 }
1678 
1683 bool VuoCompilerGraph::mayEventsReachPublishedOutputPorts(void)
1684 {
1685  for (VuoCompilerTriggerPort *trigger : triggers)
1686  if (! getPublishedOutputPortsDownstream(trigger).empty())
1687  return true;
1688 
1689  return false;
1690 }
1691 
1695 bool VuoCompilerGraph::isRepeatedInFeedbackLoop(VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
1696 {
1697  vector<VuoCompilerNode *> downstreamNodes = getNodesDownstream(node, trigger);
1698  return find(downstreamNodes.begin(), downstreamNodes.end(), node) != downstreamNodes.end();
1699 }
1700 
1704 bool VuoCompilerGraph::hasGatherDownstream(VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
1705 {
1706  vector<VuoCompilerNode *> downstreamNodes = getNodesDownstream(node, trigger);
1707  for (vector<VuoCompilerNode *>::iterator i = downstreamNodes.begin(); i != downstreamNodes.end(); ++i)
1708  if (getNumVerticesWithToNode(*i, trigger) > 1)
1709  return true;
1710 
1711  return false;
1712 }
1713 
1718 bool VuoCompilerGraph::hasScatterPartiallyOverlappedByAnotherTrigger(VuoCompilerTriggerPort *trigger)
1719 {
1720  bool isScatterAtTrigger = getNodesImmediatelyDownstream(trigger).size() > 1;
1721  if (isScatterAtTrigger)
1722  {
1723  vector<VuoCompilerNode *> downstreamNodes = getNodesDownstream(trigger);
1724  return areNodesPartiallyOverlappedByAnotherTrigger(downstreamNodes, trigger);
1725  }
1726 
1727  return false;
1728 }
1729 
1734 bool VuoCompilerGraph::hasScatterPartiallyOverlappedByAnotherTrigger(VuoCompilerNode *node, VuoCompilerTriggerPort *trigger)
1735 {
1736  bool isScatterAtNode = getNodesImmediatelyDownstream(node, trigger).size() > 1;
1737  if (isScatterAtNode)
1738  {
1739  vector<VuoCompilerNode *> downstreamNodes = getNodesDownstream(node, trigger);
1740  return areNodesPartiallyOverlappedByAnotherTrigger(downstreamNodes, trigger);
1741  }
1742 
1743  return false;
1744 }
1745 
1749 bool VuoCompilerGraph::areNodesPartiallyOverlappedByAnotherTrigger(const vector<VuoCompilerNode *> &nodes, VuoCompilerTriggerPort *trigger)
1750 {
1751  for (vector<VuoCompilerTriggerPort *>::iterator i = triggers.begin(); i != triggers.end(); ++i)
1752  {
1753  VuoCompilerTriggerPort *otherTrigger = *i;
1754  if (otherTrigger == trigger)
1755  continue;
1756 
1757  vector<VuoCompilerNode *> nodesDownstreamOfOtherTrigger = getNodesDownstream(otherTrigger);
1758  nodesDownstreamOfOtherTrigger.push_back(nodeForTrigger[otherTrigger]);
1759 
1760  bool hasOverlappedNode = false;
1761  bool hasNonOverlappedNode = false;
1762  for (vector<VuoCompilerNode *>::const_iterator j = nodes.begin(); j != nodes.end(); ++j)
1763  {
1764  VuoCompilerNode *downstreamNode = *j;
1765 
1766  if (find(nodesDownstreamOfOtherTrigger.begin(), nodesDownstreamOfOtherTrigger.end(), downstreamNode) != nodesDownstreamOfOtherTrigger.end())
1767  hasOverlappedNode = true;
1768  else
1769  hasNonOverlappedNode = true;
1770  }
1771 
1772  if (hasOverlappedNode && hasNonOverlappedNode)
1773  return true;
1774  }
1775 
1776  return false;
1777 }
1778 
1783 bool VuoCompilerGraph::hasOverlapWithSpinOff(VuoCompilerTriggerPort *trigger)
1784 {
1785  vector<VuoCompilerNode *> nodesDownstreamOfTrigger = getNodesDownstream(trigger);
1786  vector<VuoCompilerNode *> nodesDownstreamOfSpinOffs;
1787 
1788  // Collect all nodes downstream of Spin Off nodes downstream of this trigger
1789  // (including Spin Offs downstream of other Spin Offs downstream of this trigger).
1790  vector<VuoCompilerNode *> nodesToCheck = nodesDownstreamOfTrigger;
1791  map<VuoCompilerNode *, bool> nodesChecked;
1792  while (! nodesToCheck.empty())
1793  {
1794  VuoCompilerNode *node = nodesToCheck.back();
1795  nodesToCheck.pop_back();
1796 
1797  if (nodesChecked[node])
1798  continue;
1799  nodesChecked[node] = true;
1800 
1801  if (node == nodeForTrigger[publishedInputTrigger])
1802  continue;
1803 
1804  string nodeClassName = node->getBase()->getNodeClass()->getClassName();
1805  if (VuoStringUtilities::beginsWith(nodeClassName, "vuo.event.spinOff"))
1806  {
1807  VuoPort *spinOffOutput = node->getBase()->getOutputPorts().at(VuoNodeClass::unreservedOutputPortStartIndex);
1808  VuoCompilerTriggerPort *spinOffTrigger = static_cast<VuoCompilerTriggerPort *>( spinOffOutput->getCompiler() );
1809  vector<VuoCompilerNode *> nodesDownstream = getNodesDownstream(spinOffTrigger);
1810 
1811  nodesDownstreamOfSpinOffs.insert(nodesDownstreamOfSpinOffs.end(), nodesDownstream.begin(), nodesDownstream.end());
1812  nodesToCheck.insert(nodesToCheck.end(), nodesDownstream.begin(), nodesDownstream.end());
1813  }
1814  }
1815 
1816  sort(nodesDownstreamOfTrigger.begin(), nodesDownstreamOfTrigger.end());
1817  sort(nodesDownstreamOfSpinOffs.begin(), nodesDownstreamOfSpinOffs.end());
1818 
1819  // Do this trigger and the Spin Offs have any downstream nodes in common?
1820  set<VuoCompilerNode *> nodesDownstreamOfBoth;
1821  set_intersection(nodesDownstreamOfTrigger.begin(), nodesDownstreamOfTrigger.end(),
1822  nodesDownstreamOfSpinOffs.begin(), nodesDownstreamOfSpinOffs.end(),
1823  std::inserter(nodesDownstreamOfBoth, nodesDownstreamOfBoth.begin()));
1824  return ! nodesDownstreamOfBoth.empty();
1825 }
1826 
1836 void VuoCompilerGraph::checkForInfiniteFeedback(VuoCompilerIssues *issues)
1837 {
1838  if (! repeatedVertices.empty())
1839  {
1840  // Identify the nodes and cables involved in the infinite feedback loop.
1841  vector< set<VuoNode *> > nodesInLoops;
1842  vector< set<VuoCable *> > cablesInLoops;
1843  for (const auto &i : repeatedVertices)
1844  {
1845  VuoCompilerTriggerPort *trigger = i.first;
1846  for (const Vertex &repeatedVertex : i.second)
1847  {
1848  set<VuoNode *> nodesInLoop;
1849  set<VuoCable *> cablesInLoop;
1850  for (const Vertex &otherVertex : vertices[trigger])
1851  {
1852  if (downstreamVertices[trigger][repeatedVertex].find(otherVertex) != downstreamVertices[trigger][repeatedVertex].end() &&
1853  downstreamVertices[trigger][otherVertex].find(repeatedVertex) != downstreamVertices[trigger][otherVertex].end())
1854  {
1855  nodesInLoop.insert(otherVertex.fromNode->getBase());
1856  nodesInLoop.insert(otherVertex.toNode->getBase());
1857 
1858  for (set<VuoCompilerCable *>::iterator m = otherVertex.cableBundle.begin(); m != otherVertex.cableBundle.end(); ++m)
1859  cablesInLoop.insert((*m)->getBase());
1860  }
1861  }
1862  nodesInLoops.push_back(nodesInLoop);
1863  cablesInLoops.push_back(cablesInLoop);
1864  }
1865  }
1866 
1867  // Coalesce the lists of nodes and cables to avoid reporting the same ones multiple times.
1868  vector< set<VuoNode *> > coalescedNodesInLoops;
1869  vector< set<VuoCable *> > coalescedCablesInLoops;
1870  for (size_t i = 0; i < nodesInLoops.size(); ++i)
1871  {
1872  bool coalesced = false;
1873  for (size_t j = 0; j < coalescedNodesInLoops.size(); ++j)
1874  {
1875  set<VuoNode *> nodesInBoth;
1876  std::set_intersection(nodesInLoops[i].begin(), nodesInLoops[i].end(),
1877  coalescedNodesInLoops[j].begin(), coalescedNodesInLoops[j].end(),
1878  std::inserter(nodesInBoth, nodesInBoth.begin()));
1879 
1880  set<VuoCable *> cablesInBoth;
1881  std::set_intersection(cablesInLoops[i].begin(), cablesInLoops[i].end(),
1882  coalescedCablesInLoops[j].begin(), coalescedCablesInLoops[j].end(),
1883  std::inserter(cablesInBoth, cablesInBoth.begin()));
1884 
1885  if (nodesInBoth.size() == nodesInLoops[i].size() && cablesInBoth.size() == cablesInLoops[i].size())
1886  {
1887  // One of the coalesced items is a superset of nodesInLoops[i] and cablesInLoops[i]. Already taken care of.
1888  coalesced = true;
1889  break;
1890  }
1891  else if (nodesInBoth.size() == coalescedNodesInLoops[j].size() && cablesInBoth.size() == coalescedCablesInLoops[j].size())
1892  {
1893  // One of the coalesced items is a subset of nodesInLoops[i] and cablesInLoops[i]. Merge in the additional nodes and cables.
1894  coalescedNodesInLoops[j] = nodesInLoops[i];
1895  coalescedCablesInLoops[j] = cablesInLoops[i];
1896  coalesced = true;
1897  break;
1898  }
1899  }
1900 
1901  if (! coalesced)
1902  {
1903  // No existing items to coalesce with, so add a new one.
1904  coalescedNodesInLoops.push_back(nodesInLoops[i]);
1905  coalescedCablesInLoops.push_back(cablesInLoops[i]);
1906  }
1907  }
1908 
1909  auto exceptionIssues = new VuoCompilerIssues;
1910  for (size_t i = 0; i < coalescedNodesInLoops.size(); ++i)
1911  {
1912  VuoCompilerIssue issue(VuoCompilerIssue::Error, "compiling composition", "",
1913  "Infinite feedback loop",
1914  "An event is not allowed to travel through the same cable more than once.");
1915  issue.setHelpPath("errors-warnings-and-other-issues.html");
1916  issue.setNodes(coalescedNodesInLoops[i]);
1917  issue.setCables(coalescedCablesInLoops[i]);
1918  exceptionIssues->append(issue);
1919  if (issues)
1920  issues->append(issue);
1921  }
1922 
1923  throw VuoCompilerException(exceptionIssues, true);
1924  }
1925 }
1926 
1936 void VuoCompilerGraph::checkForDeadlockedFeedback(VuoCompilerIssues *issues)
1937 {
1938  auto exceptionIssues = new VuoCompilerIssues;
1939  for (VuoCompilerTriggerPort *trigger : triggers)
1940  {
1941  // For each node, find all nodes downstream of it.
1942  map<VuoCompilerNode *, set<VuoCompilerNode *> > downstreamNodes;
1943  for (map<Vertex, set<Vertex> >::iterator j = downstreamVertices[trigger].begin(); j != downstreamVertices[trigger].end(); ++j)
1944  {
1945  Vertex upstreamVertex = j->first;
1946  set<VuoCompilerNode *> downstreamNodesForVertex;
1947  bool isRepeated = false;
1948 
1949  for (set<Vertex>::iterator k = j->second.begin(); k != j->second.end(); ++k)
1950  {
1951  Vertex downstreamVertex = *k;
1952  if (upstreamVertex.toNode == downstreamVertex.toNode)
1953  {
1954  isRepeated = true;
1955  break;
1956  }
1957 
1958  downstreamNodesForVertex.insert(downstreamVertex.toNode);
1959  }
1960 
1961  if (! isRepeated)
1962  downstreamNodes[upstreamVertex.toNode].insert(downstreamNodesForVertex.begin(), downstreamNodesForVertex.end());
1963  }
1964 
1965  // Find any pairs of nodes that are mutually downstream.
1966  set< pair<VuoCompilerNode *, VuoCompilerNode *> > mutuallyDownstreamNodePairs;
1967  for (map<VuoCompilerNode *, set<VuoCompilerNode *> >::iterator j = downstreamNodes.begin(); j != downstreamNodes.end(); ++j)
1968  {
1969  VuoCompilerNode *upstreamNode = j->first;
1970  for (set<VuoCompilerNode *>::iterator k = j->second.begin(); k != j->second.end(); ++k)
1971  {
1972  VuoCompilerNode *downstreamNode = *k;
1973  if (downstreamNodes[downstreamNode].find(upstreamNode) != downstreamNodes[downstreamNode].end() &&
1974  mutuallyDownstreamNodePairs.find( make_pair(downstreamNode, upstreamNode) ) == mutuallyDownstreamNodePairs.end())
1975  {
1976  mutuallyDownstreamNodePairs.insert( make_pair(upstreamNode, downstreamNode) );
1977  }
1978  }
1979  }
1980 
1981  // Report any errors, with all nodes and cables involved in the deadlocked feedback loops.
1982  for (set< pair<VuoCompilerNode *, VuoCompilerNode *> >::iterator j = mutuallyDownstreamNodePairs.begin(); j != mutuallyDownstreamNodePairs.end(); ++j)
1983  {
1984  VuoCompilerNode *firstNode = j->first;
1985  VuoCompilerNode *secondNode = j->second;
1986 
1987  set<VuoNode *> nodesInLoop;
1988  set<VuoCable *> cablesInLoop;
1989  nodesInLoop.insert(firstNode->getBase());
1990  nodesInLoop.insert(secondNode->getBase());
1991 
1992  for (set<VuoCompilerNode *>::iterator k = downstreamNodes[firstNode].begin(); k != downstreamNodes[firstNode].end(); ++k)
1993  {
1994  VuoCompilerNode *otherNode = *k;
1995  if (downstreamNodes[otherNode].find(secondNode) != downstreamNodes[otherNode].end())
1996  nodesInLoop.insert(otherNode->getBase());
1997  }
1998  for (set<VuoCompilerNode *>::iterator k = downstreamNodes[secondNode].begin(); k != downstreamNodes[secondNode].end(); ++k)
1999  {
2000  VuoCompilerNode *otherNode = *k;
2001  if (downstreamNodes[otherNode].find(firstNode) != downstreamNodes[otherNode].end())
2002  nodesInLoop.insert(otherNode->getBase());
2003  }
2004 
2005  for (vector<Vertex>::iterator k = vertices[trigger].begin(); k != vertices[trigger].end(); ++k)
2006  {
2007  Vertex vertex = *k;
2008  if (vertex.fromNode &&
2009  nodesInLoop.find(vertex.fromNode->getBase()) != nodesInLoop.end() &&
2010  nodesInLoop.find(vertex.toNode->getBase()) != nodesInLoop.end())
2011  {
2012  for (set<VuoCompilerCable *>::iterator m = vertex.cableBundle.begin(); m != vertex.cableBundle.end(); ++m)
2013  cablesInLoop.insert((*m)->getBase());
2014  }
2015  }
2016 
2017  VuoCompilerIssue issue(VuoCompilerIssue::Error, "compiling composition", "",
2018  "Deadlocked feedback loop",
2019  "There's more than one possible path for events to travel through this composition. "
2020  "It's unclear which is the correct one.");
2021  issue.setHelpPath("errors-warnings-and-other-issues.html");
2022  issue.setNodes(nodesInLoop);
2023  issue.setCables(cablesInLoop);
2024  exceptionIssues->append(issue);
2025  if (issues)
2026  issues->append(issue);
2027  }
2028  }
2029 
2030  if (!exceptionIssues->isEmpty())
2031  throw VuoCompilerException(exceptionIssues, true);
2032 }
2033 
2037 long VuoCompilerGraph::getHash(VuoCompilerComposition *composition)
2038 {
2039  ostringstream s;
2040 
2041  // nodes — pointers, identifiers
2042  s << "[";
2043  for (VuoNode *node : composition->getBase()->getNodes())
2044  {
2045  VuoCompilerNode *compilerNode = NULL;
2046  string identifier;
2047  if (node->hasCompiler())
2048  {
2049  compilerNode = node->getCompiler();
2050  identifier = compilerNode->getIdentifier();
2051  }
2052  s << "{" << compilerNode << "," << identifier << "},";
2053  }
2054  s << "]";
2055 
2056  // cables — pointers, node identifiers, port identifiers
2057  s << "[";
2058  set<VuoCable *> cables = composition->getBase()->getCables();
2059  for (set<VuoCable *>::iterator i = cables.begin(); i != cables.end(); ++i)
2060  {
2062  string fromNode = ((*i)->getFromNode() && (*i)->getFromNode()->hasCompiler()) ? (*i)->getFromNode()->getCompiler()->getIdentifier() : "";
2063  string fromPort = (*i)->getFromPort() ? (*i)->getFromPort()->getClass()->getName() : "";
2064  string toNode = ((*i)->getToNode() && (*i)->getToNode()->hasCompiler()) ? (*i)->getToNode()->getCompiler()->getIdentifier() : "";
2065  string toPort = (*i)->getToPort() ? (*i)->getToPort()->getClass()->getName() : "";
2066  s << "{" << (*i)->getCompiler() << "," << fromNode << "," << fromPort << "," << toNode << "," << toPort << "},";
2067  }
2068  s << "]";
2069 
2070  // published ports — pointers, identifiers
2071  s << "[";
2072  vector<VuoPublishedPort *> publishedInputPorts = composition->getBase()->getPublishedInputPorts();
2073  for (vector<VuoPublishedPort *>::iterator i = publishedInputPorts.begin(); i != publishedInputPorts.end(); ++i)
2074  s << "{" << (*i)->getCompiler() << "," << (*i)->getClass()->getName() << "},";
2075  s << "]";
2076  s << "[";
2077  vector<VuoPublishedPort *> publishedOutputPorts = composition->getBase()->getPublishedOutputPorts();
2078  for (vector<VuoPublishedPort *>::iterator i = publishedOutputPorts.begin(); i != publishedOutputPorts.end(); ++i)
2079  s << "{" << (*i)->getCompiler() << "," << (*i)->getClass()->getName() << "},";
2080  s << "]";
2081 
2082  // manually firable input port — pointer, identifier
2083  s << "[";
2084  VuoPort *manuallyFirableInputPort = composition->getManuallyFirableInputPort();
2085  if (manuallyFirableInputPort)
2086  s << "{" << manuallyFirableInputPort->getCompiler() << "," << manuallyFirableInputPort->getClass()->getName() << "},";
2087  s << "]";
2088 
2089  return VuoStringUtilities::hash(s.str());
2090 }
2091 
2095 string VuoCompilerGraph::getPublishedInputTriggerNodeIdentifier(void)
2096 {
2097  return VuoNodeClass::publishedInputNodeIdentifier + "Trigger";
2098 }
2099 
2103 string VuoCompilerGraph::getManuallyFirableTriggerNodeIdentifier(void)
2104 {
2105  return "ManuallyFirableTrigger";
2106 }
2107 
2111 VuoCompilerGraph::Vertex::Vertex(VuoCompilerTriggerPort *fromTrigger, VuoCompilerNode *toNode)
2112 {
2113  this->fromNode = NULL;
2114  this->fromTrigger = fromTrigger;
2115  this->toNode = toNode;
2116 }
2117 
2121 VuoCompilerGraph::Vertex::Vertex(VuoCompilerNode *fromNode, VuoCompilerNode *toNode)
2122 {
2123  this->fromTrigger = NULL;
2124  this->fromNode = fromNode;
2125  this->toNode = toNode;
2126 }
2127 
2131 VuoCompilerGraph::Vertex::Vertex(void)
2132 {
2133  this->fromNode = NULL;
2134  this->fromTrigger = NULL;
2135  this->toNode = NULL;
2136 }
2137 
2141 VuoCompilerGraph::Edge::Edge(const VuoCompilerGraph::Vertex &fromVertex, const VuoCompilerGraph::Vertex &toVertex)
2142  : fromVertex(fromVertex), toVertex(toVertex)
2143 {
2144 }
2145 
2149 VuoCompilerGraph::Edge::Edge(void)
2150 {
2151 }
2152 
2156 bool operator==(const VuoCompilerGraph::Vertex &lhs, const VuoCompilerGraph::Vertex &rhs)
2157 {
2158  return (lhs.fromTrigger == rhs.fromTrigger && lhs.fromNode == rhs.fromNode && lhs.toNode == rhs.toNode);
2159 }
2160 
2164 bool operator!=(const VuoCompilerGraph::Vertex &lhs, const VuoCompilerGraph::Vertex &rhs)
2165 {
2166  return ! (lhs == rhs);
2167 }
2168 
2172 bool operator<(const VuoCompilerGraph::Vertex &lhs, const VuoCompilerGraph::Vertex &rhs)
2173 {
2174  return (lhs.fromTrigger != rhs.fromTrigger ?
2175  lhs.fromTrigger < rhs.fromTrigger :
2176  (lhs.fromNode != rhs.fromNode ?
2177  lhs.fromNode < rhs.fromNode :
2178  lhs.toNode < rhs.toNode));
2179 }
2180 
2184 bool operator<(const VuoCompilerGraph::Edge &lhs, const VuoCompilerGraph::Edge &rhs)
2185 {
2186  return (lhs.fromVertex != rhs.fromVertex ?
2187  lhs.fromVertex < rhs.fromVertex :
2188  lhs.toVertex < rhs.toVertex);
2189 }
2190 
2194 string VuoCompilerGraph::Vertex::toString(void) const
2195 {
2196  return (fromNode ?
2197  fromNode->getBase()->getTitle() :
2198  fromTrigger->getBase()->getClass()->getName()) +
2199  "->" + toNode->getBase()->getTitle();
2200 }
2201 
2205 string VuoCompilerGraph::Edge::toString(void) const
2206 {
2207  return fromVertex.toString() + " -> " + toVertex.toString();
2208 }
Generated on Sat Jun 19 2021 10:17:42 for Vuo by doxygen 1.9.1