Add a builder for triggering tryjobs automatically.

This builder scans for new CLs and launches tryjobs to test them.

Once these automatic trybots have been tested for a while, I am planning
on updating it to remove the commit ready bit from CLs. I will also
update the commit queue to favor CLs that have been tested by trybots.

Currently, this launcher is referred to in the code as the "pre-cq", but
I'm planning a followup CL to rename it to "trybot", since that's easier
to understand.

BUG=chromium:229101
TEST=Launch sample run with a bunch of CLs.
TEST=Launch Paladin runs.

Change-Id: Ie7cbacf4030e70cc487a246c1e3e00eb4bd0665b
Reviewed-on: https://gerrit.chromium.org/gerrit/47975
Commit-Queue: David James <davidjames@chromium.org>
Reviewed-by: David James <davidjames@chromium.org>
Tested-by: David James <davidjames@chromium.org>

1 files changed, 67 insertions, 0 deletions

diff --git a/third_party/digraph.py b/third_party/digraph.py
new file mode 100644
index 000000000..4fafcbd46
--- /dev/null
+++ b/third_party/digraph.py
@@ -0,0 +1,67 @@
+# Copyright (c) 2013 Mark Dickinson
+#
+# The above copyright notice and this permission notice shall be included in
+# all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+
+def StronglyConnectedComponents(vertices, edges):
+  """Find the strongly connected components of a directed graph.
+
+  Uses a non-recursive version of Gabow's linear-time algorithm [1] to find
+  all strongly connected components of a directed graph.
+
+  A "strongly connected component" of a directed graph is a maximal subgraph
+  such that any vertex in the subgraph is reachable from any other; any
+  directed graph can be decomposed into its strongly connected components.
+
+  Written by Mark Dickinson and licensed under the MIT license [2].
+
+  [1] Harold N. Gabow, "Path-based depth-first search for strong and
+      biconnected components," Inf. Process. Lett. 74 (2000) 107--114.
+  [2] From code.activestate.com: http://goo.gl/X0z4C
+
+  Args:
+    vertices: A list of vertices. Each vertex should be hashable.
+    edges: Dictionary that maps each vertex v to a set of the vertices w
+           that are linked to v by a directed edge (v, w).
+
+  Returns:
+    A list of sets of vertices.
+  """
+  identified = set()
+  stack = []
+  index = {}
+  boundaries = []
+
+  for v in vertices:
+    if v not in index:
+      to_do = [('VISIT', v)]
+      while to_do:
+        operation_type, v = to_do.pop()
+        if operation_type == 'VISIT':
+          index[v] = len(stack)
+          stack.append(v)
+          boundaries.append(index[v])
+          to_do.append(('POSTVISIT', v))
+          to_do.extend([('VISITEDGE', w) for w in edges[v]])
+        elif operation_type == 'VISITEDGE':
+          if v not in index:
+            to_do.append(('VISIT', v))
+          elif v not in identified:
+            while index[v] < boundaries[-1]:
+              boundaries.pop()
+        else:
+          # operation_type == 'POSTVISIT'
+          if boundaries[-1] == index[v]:
+            boundaries.pop()
+            scc = set(stack[index[v]:])
+            del stack[index[v]:]
+            identified.update(scc)
+            yield scc