Bug 1258497: Implement a new taskgraph generation system; r=gps
authorDustin J. Mitchell <dustin@mozilla.com>
Mon, 16 May 2016 22:53:22 +0000
changeset 297659 c3e24e94ab5148ad92a3f137d6cab9d8bebdd6a7
parent 297658 997ae5a6386621b88513bf5322cd4c82a63862bb
child 297660 c17e66a20cb3e167420df885f94c6c010d1f6089
push id30264
push userkwierso@gmail.com
push dateTue, 17 May 2016 20:52:53 +0000
treeherdermozilla-central@991f249a6ffa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgps
bugs1258497
milestone49.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1258497: Implement a new taskgraph generation system; r=gps The `taskgraph` package generates TaskCluster task graphs based on collections of task "kinds". Initially, there is only one kind, the "legacy" kind, which reads the YAML files from `testing/taskcluster/tasks` to generate the task graph. Try syntax is implemented by filtering the tasks in the taskgraph after it has been created, then extending the result to include any prerequisite tasks. A collection of `mach taskgraph` subcommands are provided for developers to extend or debug the task-graph generation process. MozReview-Commit-ID: 1TJCns4XxZ8
build/mach_bootstrap.py
moz.build
taskcluster/ci/legacy/kind.yml
taskcluster/docs/attributes.rst
taskcluster/docs/index.rst
taskcluster/docs/old.rst
taskcluster/docs/parameters.rst
taskcluster/docs/taskgraph.rst
taskcluster/mach_commands.py
taskcluster/moz.build
taskcluster/taskgraph/__init__.py
taskcluster/taskgraph/create.py
taskcluster/taskgraph/decision.py
taskcluster/taskgraph/generator.py
taskcluster/taskgraph/graph.py
taskcluster/taskgraph/kind/__init__.py
taskcluster/taskgraph/kind/base.py
taskcluster/taskgraph/kind/legacy.py
taskcluster/taskgraph/parameters.py
taskcluster/taskgraph/target_tasks.py
taskcluster/taskgraph/test/__init__.py
taskcluster/taskgraph/test/test_create.py
taskcluster/taskgraph/test/test_decision.py
taskcluster/taskgraph/test/test_generator.py
taskcluster/taskgraph/test/test_graph.py
taskcluster/taskgraph/test/test_kind_legacy.py
taskcluster/taskgraph/test/test_parameters.py
taskcluster/taskgraph/test/test_target_tasks.py
taskcluster/taskgraph/test/test_try_option_syntax.py
taskcluster/taskgraph/try_option_syntax.py
taskcluster/taskgraph/types.py
testing/moz.build
testing/taskcluster/docs/index.rst
testing/taskcluster/taskcluster_graph/commit_parser.py
testing/taskcluster/tasks/branches/base_jobs.yml
--- a/build/mach_bootstrap.py
+++ b/build/mach_bootstrap.py
@@ -72,16 +72,17 @@ SEARCH_PATHS = [
     'python/slugid',
     'build',
     'config',
     'dom/bindings',
     'dom/bindings/parser',
     'dom/media/test/external',
     'layout/tools/reftest',
     'other-licenses/ply',
+    'taskcluster',
     'testing',
     'testing/firefox-ui/harness',
     'testing/firefox-ui/tests',
     'testing/luciddream',
     'testing/marionette/harness',
     'testing/marionette/harness/marionette/runner/mixins/browsermob-proxy-py',
     'testing/marionette/client',
     'testing/mozbase/mozcrash',
@@ -124,16 +125,17 @@ MACH_MODULES = [
     'python/mach/mach/commands/settings.py',
     'python/compare-locales/mach_commands.py',
     'python/mozboot/mozboot/mach_commands.py',
     'python/mozbuild/mozbuild/mach_commands.py',
     'python/mozbuild/mozbuild/backend/mach_commands.py',
     'python/mozbuild/mozbuild/compilation/codecomplete.py',
     'python/mozbuild/mozbuild/frontend/mach_commands.py',
     'services/common/tests/mach_commands.py',
+    'taskcluster/mach_commands.py',
     'testing/firefox-ui/mach_commands.py',
     'testing/luciddream/mach_commands.py',
     'testing/mach_commands.py',
     'testing/marionette/mach_commands.py',
     'testing/mochitest/mach_commands.py',
     'testing/mozharness/mach_commands.py',
     'testing/talos/mach_commands.py',
     'testing/taskcluster/mach_commands.py',
--- a/moz.build
+++ b/moz.build
@@ -16,17 +16,17 @@ CONFIGURE_SUBST_FILES += [
 ]
 
 if CONFIG['ENABLE_CLANG_PLUGIN']:
     DIRS += ['build/clang-plugin']
 
 DIRS += [
     'config',
     'python',
-    'testing',
+    'taskcluster',
 ]
 
 if not CONFIG['JS_STANDALONE']:
     CONFIGURE_SUBST_FILES += [
         'tools/update-packaging/Makefile',
     ]
     CONFIGURE_DEFINE_FILES += [
         'mozilla-config.h',
new file mode 100644
--- /dev/null
+++ b/taskcluster/ci/legacy/kind.yml
@@ -0,0 +1,6 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+implementation: 'taskgraph.kind.legacy:LegacyKind'
+legacy_path: '../../../testing/taskcluster'
new file mode 100644
--- /dev/null
+++ b/taskcluster/docs/attributes.rst
@@ -0,0 +1,90 @@
+===============
+Task Attributes
+===============
+
+Tasks can be filtered, for example to support "try" pushes which only perform a
+subset of the task graph or to link dependent tasks.  This filtering is the
+difference between a full task graph and a target task graph.
+
+Filtering takes place on the basis of attributes.  Each task has a dictionary
+of attributes (all strings), and a filter is an arbitrary expression over those
+attributes.  A task may not have a value for every attribute.
+
+The attributes, and acceptable values, are defined here.  In general, attribute
+names and values are the short, lower-case form, with underscores.
+
+kind
+====
+
+A task's ``kind`` attribute gives the name of the kind that generated it, e.g.,
+``build`` or ``legacy``.
+
+build_platform
+==============
+
+The build platform defines the platform for which the binary was built.  It is
+set for both build and test jobs, although test jobs may have a different
+``test_platform``.
+
+test_platform
+=============
+
+The test platform defines the platform on which tests are run.  It is only
+defined for test jobs and may differ from ``build_platform`` when the same binary
+is tested on several platforms (for example, on several versions of Windows).
+This applies for both talos and unit tests.
+
+build_type
+==========
+
+The type of build being performed.  This is a subdivision of ``build_platform``,
+used for different kinds of builds that target the same platform.  Values are
+
+ * ``debug``
+ * ``opt``
+
+unittest_suite
+==============
+
+This is the unit test suite being run in a unit test task.  For example,
+``mochitest`` or ``cppunittest``.
+
+unittest_flavor
+===============
+
+If a unittest suite has subdivisions, those are represented as flavors.  Not
+all suites have flavors, in which case this attribute should be omitted (but is
+sometimes set to match the suite).  Examples:
+``mochitest-devtools-chrome-chunked`` or ``a11y``.
+
+unittest_try_name
+=================
+
+(deprecated) This is the name used to refer to a unit test via try syntax.  It
+may not match either of ``unittest_suite`` or ``unittest_flavor``.
+
+test_chunk
+==========
+
+This is the chunk number of a chunked test suite (talos or unittest).  Note
+that this is a string!
+
+legacy_kind
+===========
+
+(deprecated) The kind of task as created by the legacy kind.  This is valid
+only for the ``legacy`` kind.  One of ``build``, ``unittest,`` ``post_build``,
+or ``job``.
+
+job
+===
+
+(deprecated) The name of the job (corresponding to a ``-j`` option or the name
+of a post-build job).  This is valid only for the ``legacy`` kind.
+
+post_build
+==========
+
+(deprecated) The name of the post-build activity.  This is valid only for the
+``legacy`` kind.
+
rename from testing/taskcluster/docs/index.rst
rename to taskcluster/docs/index.rst
--- a/testing/taskcluster/docs/index.rst
+++ b/taskcluster/docs/index.rst
@@ -1,232 +1,20 @@
 .. taskcluster_index:
 
-======================
-TaskCluster Automation
-======================
-
-Directory structure
-===================
-
-tasks/
-   All task definitions
-
-tests/
-   Tests for the mach target internals related to task graph
-   generation
-
-scripts/
-   Various scripts used by taskcluster docker images and
-   utilities these exist in tree primarily to avoid rebuilding
-   docker images.
-
-Task Conventions
-================
-
-In order to properly enable task reuse there are a small number of
-conventions and parameters that are specialized for build tasks vs test
-tasks. The goal here should be to provide as much of the power as
-taskcluster but not at the cost of making it easy to support the current
-model of build/test.
-
-All tasks are in the YAML format and are also processed via mustache to
-allow for greater customizations. All tasks have the following
-templates variables:
-
-``docker_image``
-----------------
-Helper for always using the latest version of a docker image that exist
-in tree::
-
-   {{#docker_image}}base{{/docker_image}}
-
-Will produce something like (see the docker folder):
-
-   quay.io/mozilla.com/base:0.11
-
-
-``from_now``
-------------
-
-Helper for crafting a JSON date in the future.::
-
-
-   {{#from_now}}1 year{{/from_now}}
-
-Will produce::
-
-   2014-10-19T22:45:45.655Z
-
+TaskCluster Task-Graph Generation
+=================================
 
-``now``
--------
-
-Current time as a json formatted date.
-
-Build tasks
-===========
-
-By convention build tasks are stored in ``tasks/builds/`` the location of
-each particular type of build is specified in ``job_flags.yml`` (and more
-locations in the future), which is located in the appropriate subdirectory
-of ``branches/``.
-
-Task format
------------
-
-To facilitate better reuse of tasks there are some expectations of the
-build tasks. These are required for the test tasks to interact with the
-builds correctly but may not effect the builds or indexing services.
-
-.. code-block:: yaml
-
-    # This is an example of just the special fields. Other fields that are
-    # required by taskcluster are omitted and documented on http://docs.taskcluster.net/
-    task:
-
-      payload:
-        # Builders usually create at least two important artifacts the build
-        # and the tests these can be anywhere in the task and also may have
-        # different path names to include things like arch and extension
-        artifacts:
-          # The build this can be anything as long as its referenced in
-          # locations.
-          'public/name_i_made_up.tar.gz': '/path/to/build'
-          'public/some_tests.zip': '/path/to/tests'
-
-      extra:
-        # Build tasks may put their artifacts anywhere but there are common
-        # resources that test tasks need to do their job correctly so we
-        # need to provide an easy way to lookup the correct aritfact path.
-        locations:
-          build: 'public/name_i_made_up.tar.gz'
-          tests: 'public/some_tests.zip' or test_packages: 'public/target.test_packages.json'
-
-
-Templates properties
---------------------
-
-``repository``
-   Target HG repository (e.g.: ``https://hg.mozilla.org/mozilla-central``)
-
-``revision``
-   Target HG revision for gecko
-
-``owner``
-   Email address of the committer
+The ``taskcluster`` directory contains support for defining the graph of tasks
+that must be executed to build and test the Gecko tree.  This is more complex
+than you might suppose!  This implementation supports:
 
-Test Tasks
-==========
-
-By convention test tasks are stored in ``tasks/tests/`` the location of
-each particular type of build is specified in ``job_flags.yml`` (and more
-locations in the future)
-
-Template properties
--------------------
-
-repository
-   Target HG repository (e.g.: ``https://hg.mozilla.org/mozilla-central``)
-
-revision
-   Target HG revision for gecko
-
-owner
-   Email address of the committer
-
-build_url
-   Location of the build
-
-tests_url
-   Location of the tests.zip package
-
-chunk
-   Current chunk
-
-total_chunks
-   Total number of chunks
-
-Generic Tasks
-=============
-
-Generic tasks are neither build tasks nor test tasks. They are intended for
-tasks that don't fit into either category.
-
-.. important::
-
-   Generic tasks are a new feature and still under development. The
-   conventions will likely change significantly.
-
-Generic tasks are defined under a top-level ``tasks`` dictionary in the
-YAML. Keys in the dictionary are the unique task name. Values are
-dictionaries of task attributes. The following attributes can be defined:
-
-task
-   *required* Path to the YAML file declaring the task.
-
-root
-   *optional* Boolean indicating whether this is a *root* task. Root
-   tasks are scheduled immediately, if scheduled to run.
-
-additional-parameters
-   *optional* Dictionary of additional parameters to pass to template
-   expansion.
+ * A huge array of tasks
+ * Different behavior for different repositories
+ * "Try" pushes, with special means to select a subset of the graph for execution
+ * Optimization -- skipping tasks that have already been performed
 
-when
-   *optional* Dictionary of conditions that must be met for this task
-   to run. See the section below for more details.
-
-tags
-   *optional* List of string labels attached to the task. Multiple tasks
-   with the same tag can all be scheduled at once by specifying the tag
-   with the ``-j <tag>`` try syntax.
-
-Conditional Execution
----------------------
-
-The ``when`` generic task dictionary entry can declare conditions that
-must be true for a task to run. Valid entries in this dictionary are
-described below.
-
-file_patterns
-   List of path patterns that will be matched against all files changed.
-
-   The set of changed files is obtained from version control. If the changed
-   files could not be determined, this condition is ignored and no filtering
-   occurs.
-
-   Values use the ``mozpack`` matching code. ``*`` is a wildcard for
-   all path characters except ``/``. ``**`` matches all directories. To
-   e.g. match against all ``.js`` files, one would use ``**/*.js``.
-
-   If a single pattern matches a single changed file, the task will be
-   scheduled.
+.. toctree::
 
-Developing
-==========
-
-Running commands via mach is the best way to invoke commands testing
-works a little differently (I have not figured out how to invoke
-python-test without running install steps first)::
-
-   mach python-test tests/
-
-Examples
---------
-
-Requires `taskcluster-cli <https://github.com/taskcluster/taskcluster-cli>`_::
-
-    mach taskcluster-trygraph --message 'try: -b do -p all' \
-     --head-rev=33c0181c4a25 \
-     --head-repository=http://hg.mozilla.org/mozilla-central \
-     --owner=jlal@mozilla.com | taskcluster run-graph
-
-Creating only a build task and submitting to taskcluster::
-
-    mach taskcluster-build \
-      --head-revision=33c0181c4a25 \
-      --head-repository=http://hg.mozilla.org/mozilla-central \
-      --owner=user@domain.com tasks/builds/b2g_desktop.yml | taskcluster run-task --verbose
-
-    mach taskcluster-tests --task-id=Mcnvz7wUR_SEMhmWb7cGdQ  \
-     --owner=user@domain.com tasks/tests/b2g_mochitest.yml | taskcluster run-task --verbose
-
+    taskgraph
+    parameters
+    attributes
+    old
new file mode 100644
--- /dev/null
+++ b/taskcluster/docs/old.rst
@@ -0,0 +1,234 @@
+==================================
+Legacy TaskCluster Task Definition
+==================================
+
+The "legacy" task definitions are in ``testing/taskcluster``.
+
+These are being replaced by a more flexible system in ``taskcluster``.
+
+Directory structure
+===================
+
+tasks/
+   All task definitions
+
+tests/
+   Tests for the mach target internals related to task graph
+   generation
+
+scripts/
+   Various scripts used by taskcluster docker images and
+   utilities these exist in tree primarily to avoid rebuilding
+   docker images.
+
+Task Conventions
+================
+
+In order to properly enable task reuse there are a few
+conventions and parameters that are specialized for build tasks vs test
+tasks. The goal here should be to provide as much of the power of
+taskcluster while still making it easy to support the current
+model of build/test.
+
+All tasks are in the YAML format and are also processed via mustache to
+allow for greater customizations. All tasks have the following
+templates variables:
+
+``docker_image``
+----------------
+Helper for always using the latest version of a docker image that exists
+in the tree::
+
+   {{#docker_image}}base{{/docker_image}}
+
+Will produce something like (see the docker folder):
+
+   quay.io/mozilla.com/base:0.11
+
+
+``from_now``
+------------
+
+Helper for crafting a JSON date in the future.::
+
+
+   {{#from_now}}1 year{{/from_now}}
+
+Will produce::
+
+   2014-10-19T22:45:45.655Z
+
+
+``now``
+-------
+
+Current time as a json formatted date.
+
+Build tasks
+===========
+
+By convention build tasks are stored in ``tasks/builds/`` the location of
+each particular type of build is specified in ``job_flags.yml`` (and more
+locations in the future), which is located in the appropriate subdirectory
+of ``branches/``.
+
+Task format
+-----------
+
+To facilitate better reuse of tasks there are some expectations of the
+build tasks. These are required for the test tasks to interact with the
+builds correctly but may not affect the builds or indexing services.
+
+.. code-block:: yaml
+
+    # This is an example of just the special fields. Other fields that are
+    # required by taskcluster are omitted and documented on http://docs.taskcluster.net/
+    task:
+
+      payload:
+        # Builders usually create at least two important artifacts: the build
+        # and the tests. These can be anywhere in the task and may have
+        # different path names to include things like arch and extension
+        artifacts:
+          # The build this can be anything as long as its referenced in
+          # locations.
+          'public/name_i_made_up.tar.gz': '/path/to/build'
+          'public/some_tests.zip': '/path/to/tests'
+
+      extra:
+        # Build tasks may name their artifacts anything, but there are common
+        # resources that test tasks need to do their job correctly so we
+        # need to provide an easy way to lookup the correct aritfact path.
+        locations:
+          build: 'public/name_i_made_up.tar.gz'
+          tests: 'public/some_tests.zip' or test_packages: 'public/target.test_packages.json'
+
+
+Templates properties
+--------------------
+
+``repository``
+   Target HG repository (e.g.: ``https://hg.mozilla.org/mozilla-central``)
+
+``revision``
+   Target HG revision for gecko
+
+``owner``
+   Email address of the committer
+
+Test Tasks
+==========
+
+By convention test tasks are stored in ``tasks/tests/`` the location of
+each particular type of build is specified in ``job_flags.yml`` (and more
+locations in the future)
+
+Template properties
+-------------------
+
+repository
+   Target HG repository (e.g.: ``https://hg.mozilla.org/mozilla-central``)
+
+revision
+   Target HG revision for gecko
+
+owner
+   Email address of the committer
+
+build_url
+   Location of the build
+
+tests_url
+   Location of the tests.zip package
+
+chunk
+   Current chunk
+
+total_chunks
+   Total number of chunks
+
+Generic Tasks
+=============
+
+Generic tasks are neither build tasks nor test tasks. They are intended for
+tasks that don't fit into either category.
+
+.. important::
+
+   Generic tasks are a new feature and still under development. The
+   conventions will likely change significantly.
+
+Generic tasks are defined under a top-level ``tasks`` dictionary in the
+YAML. Keys in the dictionary are the unique task name. Values are
+dictionaries of task attributes. The following attributes can be defined:
+
+task
+   *required* Path to the YAML file declaring the task.
+
+root
+   *optional* Boolean indicating whether this is a *root* task. Root
+   tasks are scheduled immediately, if scheduled to run.
+
+additional-parameters
+   *optional* Dictionary of additional parameters to pass to template
+   expansion.
+
+when
+   *optional* Dictionary of conditions that must be met for this task
+   to run. See the section below for more details.
+
+tags
+   *optional* List of string labels attached to the task. Multiple tasks
+   with the same tag can all be scheduled at once by specifying the tag
+   with the ``-j <tag>`` try syntax.
+
+Conditional Execution
+---------------------
+
+The ``when`` generic task dictionary entry can declare conditions that
+must be true for a task to run. Valid entries in this dictionary are
+described below.
+
+file_patterns
+   List of path patterns that will be matched against all files changed.
+
+   The set of changed files is obtained from version control. If the changed
+   files could not be determined, this condition is ignored and no filtering
+   occurs.
+
+   Values use the ``mozpack`` matching code. ``*`` is a wildcard for
+   all path characters except ``/``. ``**`` matches all directories. To
+   e.g. match against all ``.js`` files, one would use ``**/*.js``.
+
+   If a single pattern matches a single changed file, the task will be
+   scheduled.
+
+Developing
+==========
+
+Running commands via mach is the best way to invoke commands testing
+works a little differently (I have not figured out how to invoke
+python-test without running install steps first)::
+
+   mach python-test tests/
+
+Examples
+--------
+
+Requires `taskcluster-cli <https://github.com/taskcluster/taskcluster-cli>`_::
+
+    mach taskcluster-trygraph --message 'try: -b do -p all' \
+     --head-rev=33c0181c4a25 \
+     --head-repository=http://hg.mozilla.org/mozilla-central \
+     --owner=jlal@mozilla.com | taskcluster run-graph
+
+Creating only a build task and submitting to taskcluster::
+
+    mach taskcluster-build \
+      --head-revision=33c0181c4a25 \
+      --head-repository=http://hg.mozilla.org/mozilla-central \
+      --owner=user@domain.com tasks/builds/b2g_desktop.yml | taskcluster run-task --verbose
+
+    mach taskcluster-tests --task-id=Mcnvz7wUR_SEMhmWb7cGdQ  \
+     --owner=user@domain.com tasks/tests/b2g_mochitest.yml | taskcluster run-task --verbose
+
new file mode 100644
--- /dev/null
+++ b/taskcluster/docs/parameters.rst
@@ -0,0 +1,85 @@
+==========
+Parameters
+==========
+
+Task-graph generation takes a collection of parameters as input, in the form of
+a JSON or YAML file.
+
+During decision-task processing, some of these parameters are supplied on the
+command line or by environment variables.  The decision task helpfully produces
+a full parameters file as one of its output artifacts.  The other ``mach
+taskgraph`` commands can take this file as input.  This can be very helpful
+when working on a change to the task graph.
+
+The properties of the parameters object are described here, divided rougly by
+topic.
+
+Push Information
+----------------
+
+``base_repository``
+   The repository from which to do an initial clone, utilizing any available
+   caching.
+
+``head_repository``
+   The repository containing the changeset to be built.  This may differ from
+   ``base_repository`` in cases where ``base_repository`` is likely to be cached
+   and only a few additional commits are needed from ``head_repository``.
+
+``head_rev``
+   The revision to check out; this can be a short revision string
+
+``head_ref``
+   For Mercurial repositories, this is the same as ``head_rev``.  For
+   git repositories, which do not allow pulling explicit revisions, this gives
+   the symbolic ref containing ``head_rev`` that should be pulled from
+   ``head_repository``.
+
+``revision_hash``
+   The full-length revision string
+
+``owner``
+   Email address indicating the person who made the push.  Note that this
+   value may be forged and *must not* be relied on for authentication.
+
+``message``
+   The commit message
+
+``pushlog_id``
+   The ID from the ``hg.mozilla.org`` pushlog
+
+Tree Information
+----------------
+
+``project``
+   Another name for what may otherwise be called tree or branch or
+   repository.  This is the unqualified name, such as ``mozilla-central`` or
+   ``cedar``.
+
+``level``
+   The SCM level associated with this tree.  This dictates the names
+   of resources used in the generated tasks, and those tasks will fail if it
+   is incorrect.
+
+Target Set
+----------
+
+The "target set" is the set of task labels which must be included in a task
+graph.  The task graph generation process will include any tasks required by
+those in the target set, recursively.  In a decision task, this set can be
+specified programmatically using one of a variety of methods (e.g., parsing try
+syntax or reading a project-specific configuration file).
+
+The decision task writes its task set to the ``target_tasks.json`` artifact,
+and this can be copied into ``parameters.target_tasks`` and
+``parameters.target_tasks_method`` set to ``"from_parameters"`` for debugging
+with other ``mach taskgraph`` commands.
+
+``target_tasks_method``
+   (optional) The method to use to determine the target task set.  This is the
+   suffix of one of the functions in ``tascluster/taskgraph/target_tasks.py``.
+   If omitted, all tasks are targeted.
+
+``target_tasks``
+   (optional) The target set method ``from_parameters`` reads the target set, as
+   a list of task labels, from this parameter.
new file mode 100644
--- /dev/null
+++ b/taskcluster/docs/taskgraph.rst
@@ -0,0 +1,122 @@
+======================
+TaskGraph Mach Command
+======================
+
+The task graph is built by linking different kinds of tasks together, pruning
+out tasks that are not required, then optimizing by replacing subgraphs with
+links to already-completed tasks.
+
+Concepts
+--------
+
+* *Task Kind* - Tasks are grouped by kind, where tasks of the same kind do not
+  have interdependencies but have substantial similarities, and may depend on
+  tasks of other kinds.  Kinds are the primary means of supporting diversity,
+  in that a developer can add a new kind to do just about anything without
+  impacting other kinds.
+
+* *Task Attributes* - Tasks have string attributes by which can be used for
+  filtering.  Attributes are documented in :doc:`attributes`.
+
+* *Task Labels* - Each task has a unique identifier within the graph that is
+  stable across runs of the graph generation algorithm.  Labels are replaced
+  with TaskCluster TaskIds at the latest time possible, facilitating analysis
+  of graphs without distracting noise from randomly-generated taskIds.
+
+* *Optimization* - replacement of a task in a graph with an equivalent,
+  already-completed task, or a null task, avoiding repetition of work.
+
+Kinds
+-----
+
+Kinds are the focal point of this system.  They provide an interface between
+the large-scale graph-generation process and the small-scale task-definition
+needs of different kinds of tasks.  Each kind may implement task generation
+differently.  Some kinds may generate task definitions entirely internally (for
+example, symbol-upload tasks are all alike, and very simple), while other kinds
+may do little more than parse a directory of YAML files.
+
+A `kind.yml` file contains data about the kind, as well as referring to a
+Python class implementing the kind in its ``implementation`` key.  That
+implementation may rely on lots of code shared with other kinds, or contain a
+completely unique implementation of some functionality.
+
+The result is a nice segmentation of implementation so that the more esoteric
+in-tree projects can do their crazy stuff in an isolated kind without making
+the bread-and-butter build and test configuration more complicated.
+
+Dependencies
+------------
+
+Dependency links between tasks are always between different kinds(*).  At a
+large scale, you can think of the dependency graph as one between kinds, rather
+than between tasks.  For example, the unittest kind depends on the build kind.
+The details of *which* tasks of the two kinds are linked is left to the kind
+definition.
+
+(*) A kind can depend on itself, though.  You can safely ignore that detail.
+Tasks can also be linked within a kind using explicit dependencies.
+
+Decision Task
+-------------
+
+The decision task is the first task created when a new graph begins.  It is
+responsible for creating the rest of the task graph.
+
+The decision task for pushes is defined in-tree, currently at
+``testing/taskcluster/tasks/decision``.  The task description invokes ``mach
+taskcluster decision`` with some metadata about the push.  That mach command
+determines the optimized task graph, then calls the TaskCluster API to create
+the tasks.
+
+Graph Generation
+----------------
+
+Graph generation, as run via ``mach taskgraph decision``, proceeds as follows:
+
+#. For all kinds, generate all tasks.  The result is the "full task set"
+#. Create links between tasks using kind-specific mechanisms.  The result is
+   the "full task graph".
+#. Select the target tasks (based on try syntax or a tree-specific
+   specification).  The result is the "target task set".
+#. Based on the full task graph, calculate the transitive closure of the target
+   task set.  That is, the target tasks and all requirements of those tasks.
+   The result is the "target task graph".
+#. Optimize the target task graph based on kind-specific optimization methods.
+   The result is the "optimized task graph" with fewer nodes than the target
+   task graph.
+#. Create tasks for all tasks in the optimized task graph.
+
+Mach commands
+-------------
+
+A number of mach subcommands are available aside from ``mach taskgraph
+decision`` to make this complex system more accesssible to those trying to
+understand or modify it.  They allow you to run portions of the
+graph-generation process and output the results.
+
+``mach taskgraph tasks``
+   Get the full task set
+
+``mach taskgraph full``
+   Get the full task graph
+
+``mach taskgraph target``
+   Get the target task set
+
+``mach taskgraph target-graph``
+   Get the target task graph
+
+``mach taskgraph optimized``
+   Get the optimized task graph
+
+Each of these commands taskes a ``--parameters`` option giving a file with
+parameters to guide the graph generation.  The decision task helpfully produces
+such a file on every run, and that is generally the easiest way to get a
+parameter file.  The parameter keys and values are described in
+:doc:`parameters`.
+
+Finally, the ``mach taskgraph decision`` subcommand performs the entire
+task-graph generation process, then creates the tasks.  This command should
+only be used within a decision task, as it assumes it is running in that
+context.
new file mode 100644
--- /dev/null
+++ b/taskcluster/mach_commands.py
@@ -0,0 +1,160 @@
+# -*- coding: utf-8 -*-
+
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import sys
+import textwrap
+
+from mach.decorators import (
+    CommandArgument,
+    CommandProvider,
+    Command,
+    SubCommand,
+)
+
+from mozbuild.base import MachCommandBase
+
+
+class ShowTaskGraphSubCommand(SubCommand):
+    """A SubCommand with TaskGraph-specific arguments"""
+
+    def __call__(self, func):
+        after = SubCommand.__call__(self, func)
+        args = [
+            CommandArgument('--root', '-r', default='taskcluster/ci',
+                            help="root of the taskgraph definition relative to topsrcdir"),
+            CommandArgument('--parameters', '-p', required=True,
+                            help="parameters file (.yml or .json; see "
+                                 "`taskcluster/docs/parameters.rst`)`"),
+            CommandArgument('--no-optimize', dest="optimize", action="store_false",
+                            default="true",
+                            help="do not remove tasks from the graph that are found in the "
+                            "index (a.k.a. optimize the graph)"),
+        ]
+        for arg in args:
+            after = arg(after)
+        return after
+
+
+@CommandProvider
+class MachCommands(MachCommandBase):
+
+    @Command('taskgraph', category="ci",
+             description="Manipulate TaskCluster task graphs defined in-tree")
+    def taskgraph(self):
+        """The taskgraph subcommands all relate to the generation of task graphs
+        for Gecko continuous integration.  A task graph is a set of tasks linked
+        by dependencies: for example, a binary must be built before it is tested,
+        and that build may further depend on various toolchains, libraries, etc.
+        """
+
+    @SubCommand('taskgraph', 'python-tests',
+                description='Run the taskgraph unit tests')
+    def taskgraph_python_tests(self, **options):
+        import unittest
+        import mozunit
+        suite = unittest.defaultTestLoader.discover('taskgraph.test')
+        runner = mozunit.MozTestRunner(verbosity=2)
+        result = runner.run(suite)
+        if not result.wasSuccessful:
+            sys.exit(1)
+
+    @ShowTaskGraphSubCommand('taskgraph', 'tasks',
+                         description="Show all tasks in the taskgraph")
+    def taskgraph_tasks(self, **options):
+        return self.show_taskgraph('full_task_set', options)
+
+    @ShowTaskGraphSubCommand('taskgraph', 'full',
+                         description="Show the full taskgraph")
+    def taskgraph_full(self, **options):
+        return self.show_taskgraph('full_task_graph', options)
+
+    @ShowTaskGraphSubCommand('taskgraph', 'target',
+                         description="Show the target task set")
+    def taskgraph_target(self, **options):
+        return self.show_taskgraph('target_task_set', options)
+
+    @ShowTaskGraphSubCommand('taskgraph', 'target-graph',
+                         description="Show the target taskgraph")
+    def taskgraph_target_taskgraph(self, **options):
+        return self.show_taskgraph('target_task_graph', options)
+
+    @ShowTaskGraphSubCommand('taskgraph', 'optimized',
+                         description="Show the optimized taskgraph")
+    def taskgraph_optimized(self, **options):
+        return self.show_taskgraph('optimized_task_graph', options)
+
+    @SubCommand('taskgraph', 'decision',
+                description="Run the decision task")
+    @CommandArgument('--root', '-r',
+        default='taskcluster/ci',
+        help="root of the taskgraph definition relative to topsrcdir")
+    @CommandArgument('--base-repository',
+        required=True,
+        help='URL for "base" repository to clone')
+    @CommandArgument('--head-repository',
+        required=True,
+        help='URL for "head" repository to fetch revision from')
+    @CommandArgument('--head-ref',
+        required=True,
+        help='Reference (this is same as rev usually for hg)')
+    @CommandArgument('--head-rev',
+        required=True,
+        help='Commit revision to use from head repository')
+    @CommandArgument('--message',
+        required=True,
+        help='Commit message to be parsed. Example: "try: -b do -p all -u all"')
+    @CommandArgument('--revision-hash',
+        required=True,
+        help='Treeherder revision hash (long revision id) to attach results to')
+    @CommandArgument('--project',
+        required=True,
+        help='Project to use for creating task graph. Example: --project=try')
+    @CommandArgument('--pushlog-id',
+        dest='pushlog_id',
+        required=True,
+        default=0)
+    @CommandArgument('--owner',
+        required=True,
+        help='email address of who owns this graph')
+    @CommandArgument('--level',
+        required=True,
+        help='SCM level of this repository')
+    @CommandArgument('--target-tasks-method',
+        required=False,
+        help='Method to use to determine the target task (e.g., `try_option_syntax`); '
+             'default is to run the full task graph')
+    def taskgraph_decision(self, **options):
+        """Run the decision task: generate a task graph and submit to
+        TaskCluster.  This is only meant to be called within decision tasks,
+        and requires a great many arguments.  Commands like `mach taskgraph
+        optimized` are better suited to use on the command line, and can take
+        the parameters file generated by a decision task.  """
+
+        import taskgraph.decision
+        return taskgraph.decision.taskgraph_decision(self.log, options)
+
+    def show_taskgraph(self, graph_attr, options):
+        import taskgraph.parameters
+        import taskgraph.target_tasks
+        import taskgraph.generator
+
+        parameters = taskgraph.parameters.load_parameters_file(options)
+
+        target_tasks_method = parameters.get('target_tasks_method', 'all_tasks')
+        target_tasks_method = taskgraph.target_tasks.get_method(target_tasks_method)
+        tgg = taskgraph.generator.TaskGraphGenerator(
+            root_dir=options['root'],
+            log=self.log,
+            parameters=parameters,
+            target_tasks_method=target_tasks_method)
+
+        tg = getattr(tgg, graph_attr)
+
+        for label in tg.graph.visit_postorder():
+            print(tg.tasks[label])
+
new file mode 100644
--- /dev/null
+++ b/taskcluster/moz.build
@@ -0,0 +1,7 @@
+# -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
+# vim: set filetype=python:
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+SPHINX_TREES['taskcluster'] = 'docs'
new file mode 100644
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/create.py
@@ -0,0 +1,43 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import requests
+import json
+import collections
+
+from slugid import nice as slugid
+
+def create_tasks(taskgraph):
+    # TODO: use the taskGroupId of the decision task
+    task_group_id = slugid()
+    label_to_taskid = collections.defaultdict(slugid)
+
+    session = requests.Session()
+
+    for label in taskgraph.graph.visit_postorder():
+        task = taskgraph.tasks[label]
+        deps_by_name = {
+            n: label_to_taskid[r]
+            for (l, r, n) in taskgraph.graph.edges
+            if l == label}
+        task_def = task.kind.get_task_definition(task, deps_by_name)
+        task_def['taskGroupId'] = task_group_id
+        task_def['dependencies'] = deps_by_name.values()
+        task_def['requires'] = 'all-completed'
+
+        _create_task(session, label_to_taskid[label], label, task_def)
+
+def _create_task(session, task_id, label, task_def):
+    # create the task using 'http://taskcluster/queue', which is proxied to the queue service
+    # with credentials appropriate to this job.
+    print("Creating task with taskId {} for {}".format(task_id, label))
+    res = session.put('http://taskcluster/queue/v1/task/{}'.format(task_id), data=json.dumps(task_def))
+    if res.status_code != 200:
+        try:
+            print(res.json()['message'])
+        except:
+            print(res.text)
+        res.raise_for_status()
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/decision.py
@@ -0,0 +1,99 @@
+# -*- coding: utf-8 -*-
+
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import os
+import json
+import logging
+import yaml
+
+from .generator import TaskGraphGenerator
+from .create import create_tasks
+from .parameters import get_decision_parameters
+from .target_tasks import get_method
+
+ARTIFACTS_DIR = 'artifacts'
+
+
+def taskgraph_decision(log, options):
+    """
+    Run the decision task.  This function implements `mach taskgraph decision`,
+    and is responsible for
+
+     * processing decision task command-line options into parameters
+     * running task-graph generation exactly the same way the other `mach
+       taskgraph` commands do
+     * generating a set of artifacts to memorialize the graph
+     * calling TaskCluster APIs to create the graph
+    """
+
+    parameters = get_decision_parameters(options)
+
+    # create a TaskGraphGenerator instance
+    target_tasks_method = parameters.get('target_tasks_method', 'all_tasks')
+    target_tasks_method = get_method(target_tasks_method)
+    tgg = TaskGraphGenerator(
+        root_dir=options['root'],
+        log=log,
+        parameters=parameters,
+        target_tasks_method=target_tasks_method)
+
+    # write out the parameters used to generate this graph
+    write_artifact('parameters.yml', dict(**parameters), log)
+
+    # write out the full graph for reference
+    write_artifact('full-task-graph.json',
+                   taskgraph_to_json(tgg.full_task_graph),
+                   log)
+
+    # write out the target task set to allow reproducing this as input
+    write_artifact('target_tasks.json',
+                   tgg.target_task_set.tasks.keys(),
+                   log)
+
+    # write out the optimized task graph to describe what will happen
+    write_artifact('task-graph.json',
+                   taskgraph_to_json(tgg.optimized_task_graph),
+                   log)
+
+    # actually create the graph
+    create_tasks(tgg.optimized_task_graph)
+
+
+def taskgraph_to_json(taskgraph):
+    tasks = taskgraph.tasks
+
+    def tojson(task):
+        return {
+            'task': task.task,
+            'attributes': task.attributes,
+            'dependencies': []
+        }
+    rv = {label: tojson(tasks[label]) for label in taskgraph.graph.nodes}
+
+    # add dependencies with one trip through the graph edges
+    for (left, right, name) in taskgraph.graph.edges:
+        rv[left]['dependencies'].append((name, right))
+
+    return rv
+
+
+def write_artifact(filename, data, log):
+    log(logging.INFO, 'writing-artifact', {
+        'filename': filename,
+    }, 'writing artifact file `{filename}`')
+    if not os.path.isdir(ARTIFACTS_DIR):
+        os.mkdir(ARTIFACTS_DIR)
+    path = os.path.join(ARTIFACTS_DIR, filename)
+    if filename.endswith('.yml'):
+        with open(path, 'w') as f:
+            yaml.safe_dump(data, f, allow_unicode=True, default_flow_style=False)
+    elif filename.endswith('.json'):
+        with open(path, 'w') as f:
+            json.dump(data, f, sort_keys=True, indent=2, separators=(',', ': '))
+    else:
+        raise TypeError("Don't know how to write to {}".format(filename))
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/generator.py
@@ -0,0 +1,179 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+import logging
+import os
+import yaml
+
+from .graph import Graph
+from .types import TaskGraph
+
+class TaskGraphGenerator(object):
+    """
+    The central controller for taskgraph.  This handles all phases of graph
+    generation.  The task is generated from all of the kinds defined in
+    subdirectories of the generator's root directory.
+
+    Access to the results of this generation, as well as intermediate values at
+    various phases of generation, is available via properties.  This encourages
+    the provision of all generation inputs at instance construction time.
+    """
+
+    # Task-graph generation is implemented as a Python generator that yields
+    # each "phase" of generation.  This allows some mach subcommands to short-
+    # circuit generation of the entire graph by never completing the generator.
+
+    def __init__(self, root_dir, log, parameters,
+                 target_tasks_method):
+        """
+        @param root_dir: root directory, with subdirectories for each kind
+        @param log: Mach log function
+        @param parameters: parameters for this task-graph generation
+        @type parameters: dict
+        @param target_tasks_method: function to determine the target_task_set;
+                see `./target_tasks.py`.
+        @type target_tasks_method: function
+        """
+
+        self.root_dir = root_dir
+        self.log = log
+        self.parameters = parameters
+        self.target_tasks_method = target_tasks_method
+
+        # this can be set up until the time the target task set is generated;
+        # it defaults to parameters['target_tasks']
+        self._target_tasks = parameters.get('target_tasks')
+
+        # start the generator
+        self._run = self._run()
+        self._run_results = {}
+
+    @property
+    def full_task_set(self):
+        """
+        The full task set: all tasks defined by any kind (a graph without edges)
+
+        @type: TaskGraph
+        """
+        return self._run_until('full_task_set')
+
+
+    @property
+    def full_task_graph(self):
+        """
+        The full task graph: the full task set, with edges representing
+        dependencies.
+
+        @type: TaskGraph
+        """
+        return self._run_until('full_task_graph')
+
+    @property
+    def target_task_set(self):
+        """
+        The set of targetted tasks (a graph without edges)
+
+        @type: TaskGraph
+        """
+        return self._run_until('target_task_set')
+
+    @property
+    def target_task_graph(self):
+        """
+        The set of targetted tasks and all of their dependencies
+
+        @type: TaskGraph
+        """
+        return self._run_until('target_task_graph')
+
+    @property
+    def optimized_task_graph(self):
+        """
+        The set of targetted tasks and all of their dependencies; tasks that
+        have been optimized out are either omitted or replaced with a Task
+        instance containing only a task_id.
+
+        @type: TaskGraph
+        """
+        return self._run_until('optimized_task_graph')
+
+    def _load_kinds(self):
+        for path in os.listdir(self.root_dir):
+            path = os.path.join(self.root_dir, path)
+            if not os.path.isdir(path):
+                continue
+            name = os.path.basename(path)
+            self.log(logging.DEBUG, 'loading-kind', {
+                'name': name,
+                'path': path,
+            }, "loading kind `{name}` from {path}")
+
+            kind_yml = os.path.join(path, 'kind.yml')
+            with open(kind_yml) as f:
+                config = yaml.load(f)
+
+            # load the class defined by implementation
+            try:
+                impl = config['implementation']
+            except KeyError:
+                raise KeyError("{!r} does not define implementation".format(kind_yml))
+            if impl.count(':') != 1:
+                raise TypeError('{!r} implementation does not have the form "module:object"'
+                                .format(kind_yml))
+
+            impl_module, impl_object = impl.split(':')
+            impl_class = __import__(impl_module)
+            for a in impl_module.split('.')[1:]:
+                impl_class = getattr(impl_class, a)
+            for a in impl_object.split('.'):
+                impl_class = getattr(impl_class, a)
+
+            yield impl_class(path, config, self.log)
+
+    def _run(self):
+        all_tasks = {}
+        for kind in self._load_kinds():
+            for task in kind.load_tasks(self.parameters):
+                if task.label in all_tasks:
+                    raise Exception("duplicate tasks with label " + task.label)
+                all_tasks[task.label] = task
+
+        full_task_set = TaskGraph(all_tasks, Graph(set(all_tasks), set()))
+        yield 'full_task_set', full_task_set
+
+        edges = set()
+        for t in full_task_set:
+            for dep, depname in t.kind.get_task_dependencies(t, full_task_set):
+                edges.add((t.label, dep, depname))
+
+        full_task_graph = TaskGraph(all_tasks,
+                                    Graph(full_task_set.graph.nodes, edges))
+        yield 'full_task_graph', full_task_graph
+
+        target_tasks = set(self.target_tasks_method(full_task_graph, self.parameters))
+
+        target_task_set = TaskGraph(
+            {l: all_tasks[l] for l in target_tasks},
+            Graph(target_tasks, set()))
+        yield 'target_task_set', target_task_set
+
+        target_graph = full_task_graph.graph.transitive_closure(target_tasks)
+        target_task_graph = TaskGraph(
+            {l: all_tasks[l] for l in target_graph.nodes},
+            target_graph)
+        yield 'target_task_graph', target_task_graph
+
+        # optimization is not yet implemented
+
+        yield 'optimized_task_graph', target_task_graph
+
+    def _run_until(self, name):
+        while name not in self._run_results:
+            try:
+                k, v = self._run.next()
+            except StopIteration:
+                raise AttributeError("No such run result {}".format(name))
+            self._run_results[k] = v
+        return self._run_results[name]
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/graph.py
@@ -0,0 +1,104 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import collections
+
+class Graph(object):
+    """
+    Generic representation of a directed acyclic graph with labeled edges
+    connecting the nodes.  Graph operations are implemented in a functional
+    manner, so the data structure is immutable.
+
+    It permits at most one edge of a given name between any set of nodes.  The
+    graph is not checked for cycles, and methods may hang or otherwise fail if
+    given a cyclic graph.
+
+    The `nodes` and `edges` attributes may be accessed in a read-only fashion.
+    The `nodes` attribute is a set of node names, while `edges` is a set of
+    `(left, right, name)` tuples representing an edge named `name` going from
+    node `left` to node `right..
+    """
+
+    def __init__(self, nodes, edges):
+        """
+        Create a graph.  Nodes and edges are both as described in the class
+        documentation.  Both values are used by reference, and should not be
+        modified after building a graph.
+        """
+        assert isinstance(nodes, set)
+        assert isinstance(edges, set)
+        self.nodes = nodes
+        self.edges = edges
+
+    def __eq__(self, other):
+        return self.nodes == other.nodes and self.edges == other.edges
+
+    def __repr__(self):
+        return "<Graph nodes={!r} edges={!r}>".format(self.nodes, self.edges)
+
+    def transitive_closure(self, nodes):
+        """
+        Return the transitive closure of <nodes>: the graph containing all
+        specified nodes as well as any nodes reachable from them, and any
+        intervening edges.
+        """
+        assert isinstance(nodes, set)
+        assert nodes <= self.nodes
+
+        # generate a new graph by expanding along edges until reaching a fixed
+        # point
+        new_nodes, new_edges = nodes, set()
+        nodes, edges = set(), set()
+        while (new_nodes, new_edges) != (nodes, edges):
+            nodes, edges = new_nodes, new_edges
+            add_edges = set((left, right, name) for (left, right, name) in self.edges if left in nodes)
+            add_nodes = set(right for (_, right, _) in add_edges)
+            new_nodes = nodes | add_nodes
+            new_edges = edges | add_edges
+        return Graph(new_nodes, new_edges)
+
+    def visit_postorder(self):
+        """
+        Generate a sequence of nodes in postorder, such that every node is
+        visited *after* any nodes it links to.
+
+        Behavior is undefined (read: it will hang) if the graph contains a
+        cycle.
+        """
+        queue = collections.deque(sorted(self.nodes))
+        links_by_node = self.links_dict()
+        seen = set()
+        while queue:
+            node = queue.popleft()
+            if node in seen:
+                continue
+            links = links_by_node[node]
+            if all((n in seen) for n in links):
+                seen.add(node)
+                yield node
+            else:
+                queue.extend(n for n in links if n not in seen)
+                queue.append(node)
+
+    def links_dict(self):
+        """
+        Return a dictionary mapping each node to a set of its downstream
+        nodes (omitting edge names)
+        """
+        links = collections.defaultdict(set)
+        for left, right, _ in self.edges:
+            links[left].add(right)
+        return links
+
+    def reverse_links_dict(self):
+        """
+        Return a dictionary mapping each node to a set of its upstream
+        nodes (omitting edge names)
+        """
+        links = collections.defaultdict(set)
+        for left, right, _ in self.edges:
+            links[right].add(left)
+        return links
new file mode 100644
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/kind/base.py
@@ -0,0 +1,76 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import os
+import abc
+
+class Kind(object):
+    """
+    A kind represents a collection of tasks that share common characteristics.
+    For example, all build jobs.  Each instance of a kind is intialized with a
+    path from which it draws its task configuration.  The instance is free to
+    store as much local state as it needs.
+    """
+    __metaclass__ = abc.ABCMeta
+
+    def __init__(self, path, config, log):
+        self.name = os.path.basename(path)
+        self.path = path
+        self.config = config
+        self.log = log
+
+    @abc.abstractmethod
+    def load_tasks(self, parameters):
+        """
+        Get the set of tasks of this kind.
+
+        The `parameters` give details on which to base the task generation.
+        See `taskcluster/docs/parameters.rst` for details.
+
+        The return value is a list of Task instances.
+        """
+
+    @abc.abstractmethod
+    def get_task_dependencies(self, task, taskgraph):
+        """
+        Get the set of task labels this task depends on, by querying the task graph.
+
+        Returns a list of (task_label, dependency_name) pairs describing the
+        dependencies.
+        """
+
+    @abc.abstractmethod
+    def get_task_optimization_key(self, task, taskgraph):
+        """
+        Get the *optimization key* for the given task.  When called, all
+        dependencies of this task will already have their `optimization_key`
+        attribute set.
+
+        The optimization key is a unique identifier covering all inputs to this
+        task.  If another task with the same optimization key has already been
+        performed, it will be used directly instead of executing the task
+        again.
+
+        Returns a string suitable for inclusion in a TaskCluster index
+        namespace (generally of the form `<optimizationName>.<hash>`), or None
+        if this task cannot be optimized.
+        """
+
+    @abc.abstractmethod
+    def get_task_definition(self, task, dependent_taskids):
+        """
+        Get the final task definition for the given task.  This is the time to
+        substitute actual taskIds for dependent tasks into the task definition.
+        Note that this method is only used in the decision tasks, so it should
+        not perform any processing that users might want to test or see in
+        other `mach taskgraph` commands.
+
+        The `dependent_taskids` parameter is a dictionary mapping dependency
+        name to assigned taskId.
+
+        The returned task definition will be modified before being passed to
+        `queue.createTask`.
+        """
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/kind/legacy.py
@@ -0,0 +1,456 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import time
+import os
+import sys
+import json
+import copy
+import re
+import logging
+
+from . import base
+from ..types import Task
+from functools import partial
+from mozpack.path import match as mozpackmatch
+from slugid import nice as slugid
+from taskcluster_graph.mach_util import (
+    merge_dicts,
+    gaia_info,
+    configure_dependent_task,
+    set_interactive_task,
+    remove_caches_from_task,
+    query_vcs_info
+)
+import taskcluster_graph.transform.routes as routes_transform
+import taskcluster_graph.transform.treeherder as treeherder_transform
+from taskcluster_graph.commit_parser import parse_commit
+from taskcluster_graph.image_builder import (
+    docker_image,
+    normalize_image_details,
+    task_id_for_image
+)
+from taskcluster_graph.from_now import (
+    json_time_from_now,
+    current_json_time,
+)
+from taskcluster_graph.templates import Templates
+import taskcluster_graph.build_task
+
+# TASKID_PLACEHOLDER is the "internal" form of a taskid; it is substituted with
+# actual taskIds at the very last minute, in get_task_definition
+TASKID_PLACEHOLDER = 'TaskLabel=={}'
+
+ARTIFACT_URL = 'https://queue.taskcluster.net/v1/task/{}/artifacts/{}'
+DEFINE_TASK = 'queue:define-task:aws-provisioner-v1/{}'
+DEFAULT_TRY = 'try: -b do -p all -u all -t all'
+DEFAULT_JOB_PATH = os.path.join(
+    'tasks', 'branches', 'base_jobs.yml'
+)
+
+# time after which a try build's results will expire
+TRY_EXPIRATION = "14 days"
+
+def mklabel():
+    return TASKID_PLACEHOLDER.format(slugid())
+
+def set_expiration(task, timestamp):
+    task_def = task['task']
+    task_def['expires'] = timestamp
+    if task_def.get('deadline', timestamp) > timestamp:
+        task_def['deadline'] = timestamp
+
+    try:
+        artifacts = task_def['payload']['artifacts']
+    except KeyError:
+        return
+
+    for artifact in artifacts.values():
+        artifact['expires'] = timestamp
+
+class LegacyKind(base.Kind):
+    """
+    This kind generates a full task graph from the old YAML files in
+    `testing/taskcluster/tasks`.  The tasks already have dependency links.
+
+    The existing task-graph generation generates slugids for tasks during task
+    generation, so this kind labels tasks using those slugids, with a prefix of
+    "TaskLabel==".  These labels are unfortunately not stable from run to run.
+    """
+
+    def load_tasks(self, params):
+        root = os.path.abspath(os.path.join(self.path, self.config['legacy_path']))
+
+        project = params['project']
+        # NOTE: message is ignored here; we always use DEFAULT_TRY, then filter the
+        # resulting task graph later
+        message = DEFAULT_TRY
+
+        templates = Templates(root)
+
+        job_path = os.path.join(root, 'tasks', 'branches', project, 'job_flags.yml')
+        job_path = job_path if os.path.exists(job_path) else \
+            os.path.join(root, DEFAULT_JOB_PATH)
+
+        jobs = templates.load(job_path, {})
+
+        job_graph, trigger_tests = parse_commit(message, jobs)
+
+        cmdline_interactive = params.get('interactive', False)
+
+        # Default to current time if querying the head rev fails
+        pushdate = time.strftime('%Y%m%d%H%M%S', time.gmtime())
+        vcs_info = query_vcs_info(params['head_repository'], params['head_rev'])
+        changed_files = set()
+        if vcs_info:
+            pushdate = time.strftime('%Y%m%d%H%M%S', time.gmtime(vcs_info.pushdate))
+
+            self.log(logging.DEBUG, 'vcs-info', {},
+                     '%d commits influencing task scheduling:\n' % len(vcs_info.changesets))
+            for c in vcs_info.changesets:
+                self.log(logging.DEBUG, 'vcs-relevant-commit', {
+                    'cset': c['node'][0:12],
+                    'desc': c['desc'].splitlines()[0].encode('ascii', 'ignore'),
+                }, "{cset} {desc}")
+                changed_files |= set(c['files'])
+
+        # Template parameters used when expanding the graph
+        seen_images = {}
+        parameters = dict(gaia_info().items() + {
+            'index': 'index',
+            'project': project,
+            'pushlog_id': params.get('pushlog_id', 0),
+            'docker_image': docker_image,
+            'task_id_for_image': partial(task_id_for_image, seen_images, project),
+            'base_repository': params['base_repository'] or
+            params['head_repository'],
+            'head_repository': params['head_repository'],
+            'head_ref': params['head_ref'] or params['head_rev'],
+            'head_rev': params['head_rev'],
+            'pushdate': pushdate,
+            'pushtime': pushdate[8:],
+            'year': pushdate[0:4],
+            'month': pushdate[4:6],
+            'day': pushdate[6:8],
+            'owner': params['owner'],
+            'level': params['level'],
+            'from_now': json_time_from_now,
+            'now': current_json_time(),
+            'revision_hash': params['revision_hash']
+        }.items())
+
+        treeherder_route = '{}.{}'.format(
+            params['project'],
+            params.get('revision_hash', '')
+        )
+
+        routes_file = os.path.join(root, 'routes.json')
+        with open(routes_file) as f:
+            contents = json.load(f)
+            json_routes = contents['routes']
+            # TODO: Nightly and/or l10n routes
+
+        # Task graph we are generating for taskcluster...
+        graph = {
+            'tasks': [],
+            'scopes': set(),
+        }
+
+        if params['revision_hash']:
+            for env in routes_transform.TREEHERDER_ROUTES:
+                route = 'queue:route:{}.{}'.format(
+                    routes_transform.TREEHERDER_ROUTES[env],
+                    treeherder_route)
+                graph['scopes'].add(route)
+
+        graph['metadata'] = {
+            'source': '{repo}file/{rev}/testing/taskcluster/mach_commands.py'.format(repo=params['head_repository'], rev=params['head_rev']),
+            'owner': params['owner'],
+            # TODO: Add full mach commands to this example?
+            'description': 'Task graph generated via ./mach taskcluster-graph',
+            'name': 'task graph local'
+        }
+
+        # Filter the job graph according to conditions met by this invocation run.
+        def should_run(task):
+            # Old style build or test task that doesn't define conditions. Always runs.
+            if 'when' not in task:
+                return True
+
+            when = task['when']
+
+            # If the task defines file patterns and we have a set of changed
+            # files to compare against, only run if a file pattern matches one
+            # of the changed files.
+            file_patterns = when.get('file_patterns', None)
+            if file_patterns and changed_files:
+                for pattern in file_patterns:
+                    for path in changed_files:
+                        if mozpackmatch(path, pattern):
+                            self.log(logging.DEBUG, 'schedule-task', {
+                                'schedule': True,
+                                'task': task['task'],
+                                'pattern': pattern,
+                                'path': path,
+                            }, 'scheduling {task} because pattern {pattern} '
+                                'matches {path}')
+                            return True
+
+                # No file patterns matched. Discard task.
+                self.log(logging.DEBUG, 'schedule-task', {
+                    'schedule': False,
+                    'task': task['task'],
+                }, 'discarding {task} because no relevant files changed')
+                return False
+
+            return True
+
+        job_graph = filter(should_run, job_graph)
+
+        all_routes = {}
+
+        for build in job_graph:
+            self.log(logging.DEBUG, 'load-task', {
+                'task': build['task'],
+            }, 'loading task {task}')
+            interactive = cmdline_interactive or build["interactive"]
+            build_parameters = merge_dicts(parameters, build['additional-parameters'])
+            build_parameters['build_slugid'] = mklabel()
+            build_parameters['source'] = '{repo}file/{rev}/testing/taskcluster/{file}'.format(repo=params['head_repository'], rev=params['head_rev'], file=build['task'])
+            build_task = templates.load(build['task'], build_parameters)
+
+            # Copy build_* attributes to expose them to post-build tasks
+            # as well as json routes and tests
+            task_extra = build_task['task']['extra']
+            build_parameters['build_name'] = task_extra['build_name']
+            build_parameters['build_type'] = task_extra['build_type']
+            build_parameters['build_product'] = task_extra['build_product']
+
+            normalize_image_details(graph,
+                                    build_task,
+                                    seen_images,
+                                    build_parameters,
+                                    os.environ.get('TASK_ID', None))
+            set_interactive_task(build_task, interactive)
+
+            # try builds don't use cache
+            if project == "try":
+                remove_caches_from_task(build_task)
+                set_expiration(build_task, json_time_from_now(TRY_EXPIRATION))
+
+            if params['revision_hash']:
+                treeherder_transform.add_treeherder_revision_info(build_task['task'],
+                                                                  params['head_rev'],
+                                                                  params['revision_hash'])
+                routes_transform.decorate_task_treeherder_routes(build_task['task'],
+                                                                 treeherder_route)
+                routes_transform.decorate_task_json_routes(build_task['task'],
+                                                           json_routes,
+                                                           build_parameters)
+
+            # Ensure each build graph is valid after construction.
+            taskcluster_graph.build_task.validate(build_task)
+            attributes = build_task['attributes'] = {'kind':'legacy', 'legacy_kind': 'build'}
+            if 'build_name' in build:
+                attributes['build_platform'] = build['build_name']
+            if 'build_type' in task_extra:
+                attributes['build_type'] = {'dbg': 'debug'}.get(task_extra['build_type'],
+                                                                task_extra['build_type'])
+            if build.get('is_job'):
+                attributes['job'] = build['build_name']
+                attributes['legacy_kind'] = 'job'
+            graph['tasks'].append(build_task)
+
+            for location in build_task['task']['extra'].get('locations', {}):
+                build_parameters['{}_url'.format(location)] = ARTIFACT_URL.format(
+                    build_parameters['build_slugid'],
+                    build_task['task']['extra']['locations'][location]
+                )
+
+            for url in build_task['task']['extra'].get('url', {}):
+                build_parameters['{}_url'.format(url)] = \
+                    build_task['task']['extra']['url'][url]
+
+            define_task = DEFINE_TASK.format(build_task['task']['workerType'])
+
+            for route in build_task['task'].get('routes', []):
+                if route.startswith('index.gecko.v2') and route in all_routes:
+                    raise Exception("Error: route '%s' is in use by multiple tasks: '%s' and '%s'" % (
+                        route,
+                        build_task['task']['metadata']['name'],
+                        all_routes[route],
+                    ))
+                all_routes[route] = build_task['task']['metadata']['name']
+
+            graph['scopes'].add(define_task)
+            graph['scopes'] |= set(build_task['task'].get('scopes', []))
+            route_scopes = map(lambda route: 'queue:route:' + route, build_task['task'].get('routes', []))
+            graph['scopes'] |= set(route_scopes)
+
+            # Treeherder symbol configuration for the graph required for each
+            # build so tests know which platform they belong to.
+            build_treeherder_config = build_task['task']['extra']['treeherder']
+
+            if 'machine' not in build_treeherder_config:
+                message = '({}), extra.treeherder.machine required for all builds'
+                raise ValueError(message.format(build['task']))
+
+            if 'build' not in build_treeherder_config:
+                build_treeherder_config['build'] = \
+                    build_treeherder_config['machine']
+
+            if 'collection' not in build_treeherder_config:
+                build_treeherder_config['collection'] = {'opt': True}
+
+            if len(build_treeherder_config['collection'].keys()) != 1:
+                message = '({}), extra.treeherder.collection must contain one type'
+                raise ValueError(message.fomrat(build['task']))
+
+            for post_build in build['post-build']:
+                # copy over the old parameters to update the template
+                # TODO additional-parameters is currently not an option, only
+                # enabled for build tasks
+                post_parameters = merge_dicts(build_parameters,
+                                              post_build.get('additional-parameters', {}))
+                post_task = configure_dependent_task(post_build['task'],
+                                                     post_parameters,
+                                                     mklabel(),
+                                                     templates,
+                                                     build_treeherder_config)
+                normalize_image_details(graph,
+                                        post_task,
+                                        seen_images,
+                                        build_parameters,
+                                        os.environ.get('TASK_ID', None))
+                set_interactive_task(post_task, interactive)
+                treeherder_transform.add_treeherder_revision_info(post_task['task'],
+                                                                  params['head_rev'],
+                                                                  params['revision_hash'])
+
+                if project == "try":
+                    set_expiration(post_task, json_time_from_now(TRY_EXPIRATION))
+
+                post_task['attributes'] = attributes.copy()
+                post_task['attributes']['legacy_kind'] = 'post_build'
+                post_task['attributes']['post_build'] = post_build['job_flag']
+                graph['tasks'].append(post_task)
+
+            for test in build['dependents']:
+                test = test['allowed_build_tasks'][build['task']]
+                # TODO additional-parameters is currently not an option, only
+                # enabled for build tasks
+                test_parameters = merge_dicts(build_parameters,
+                                              test.get('additional-parameters', {}))
+                test_parameters = copy.copy(build_parameters)
+
+                test_definition = templates.load(test['task'], {})['task']
+                chunk_config = test_definition['extra'].get('chunks', {})
+
+                # Allow branch configs to override task level chunking...
+                if 'chunks' in test:
+                    chunk_config['total'] = test['chunks']
+
+                chunked = 'total' in chunk_config
+                if chunked:
+                    test_parameters['total_chunks'] = chunk_config['total']
+
+                if 'suite' in test_definition['extra']:
+                    suite_config = test_definition['extra']['suite']
+                    test_parameters['suite'] = suite_config['name']
+                    test_parameters['flavor'] = suite_config.get('flavor', '')
+
+                for chunk in range(1, chunk_config.get('total', 1) + 1):
+                    if 'only_chunks' in test and chunked and \
+                            chunk not in test['only_chunks']:
+                        continue
+
+                    if chunked:
+                        test_parameters['chunk'] = chunk
+                    test_task = configure_dependent_task(test['task'],
+                                                         test_parameters,
+                                                         mklabel(),
+                                                         templates,
+                                                         build_treeherder_config)
+                    normalize_image_details(graph,
+                                            test_task,
+                                            seen_images,
+                                            build_parameters,
+                                            os.environ.get('TASK_ID', None))
+                    set_interactive_task(test_task, interactive)
+
+                    if params['revision_hash']:
+                        treeherder_transform.add_treeherder_revision_info(test_task['task'],
+                                                                          params['head_rev'],
+                                                                          params['revision_hash'])
+                        routes_transform.decorate_task_treeherder_routes(
+                            test_task['task'],
+                            treeherder_route
+                        )
+
+                    if project == "try":
+                        set_expiration(test_task, json_time_from_now(TRY_EXPIRATION))
+
+                    test_task['attributes'] = attributes.copy()
+                    test_task['attributes']['legacy_kind'] = 'unittest'
+                    test_task['attributes']['test_platform'] = attributes['build_platform']
+                    test_task['attributes']['unittest_try_name'] = test['unittest_try_name']
+                    for param, attr in [
+                            ('suite', 'unittest_suite'),
+                            ('flavor', 'unittest_flavor'),
+                            ('chunk', 'test_chunk')]:
+                        if param in test_parameters:
+                            test_task['attributes'][attr] = str(test_parameters[param])
+
+                    # This will schedule test jobs N times
+                    for i in range(0, trigger_tests):
+                        graph['tasks'].append(test_task)
+                        # If we're scheduling more tasks each have to be unique
+                        test_task = copy.deepcopy(test_task)
+                        test_task['taskId'] = mklabel()
+
+                    define_task = DEFINE_TASK.format(
+                        test_task['task']['workerType']
+                    )
+
+                    graph['scopes'].add(define_task)
+                    graph['scopes'] |= set(test_task['task'].get('scopes', []))
+
+        graph['scopes'] = sorted(graph['scopes'])
+
+        # save the graph for later, when taskgraph asks for additional information
+        # such as dependencies
+        self.graph = graph
+        self.tasks_by_label = {t['taskId']: t for t in self.graph['tasks']}
+
+        # Convert to a dictionary of tasks.  The process above has invented a
+        # taskId for each task, and we use those as the *labels* for the tasks;
+        # taskgraph will later assign them new taskIds.
+        return [Task(self, t['taskId'], task=t['task'], attributes=t['attributes'])
+                for t in self.graph['tasks']]
+
+    def get_task_dependencies(self, task, taskgraph):
+        # fetch dependency information from the cached graph
+        taskdict = self.tasks_by_label[task.label]
+        return [(label, label) for label in taskdict.get('requires', [])]
+
+    def get_task_optimization_key(self, task, taskgraph):
+        pass
+
+    def get_task_definition(self, task, dependent_taskids):
+        # Note that the keys for `dependent_taskids` are task labels in this
+        # case, since that's how get_task_dependencies set it up.
+        placeholder_pattern = re.compile(r'TaskLabel==[a-zA-Z0-9-_]{22}')
+        def repl(mo):
+            return dependent_taskids[mo.group(0)]
+
+        # this is a cheap but easy way to replace all placeholders with
+        # actual real taskIds now that they are known.  The placeholder
+        # may be embedded in a longer string, so traversing the data structure
+        # would still require regexp matching each string and not be
+        # appreciably faster.
+        task_def = json.dumps(task.task)
+        task_def = placeholder_pattern.sub(repl, task_def)
+        return json.loads(task_def)
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/parameters.py
@@ -0,0 +1,55 @@
+# -*- coding: utf-8 -*-
+
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import json
+import sys
+import yaml
+from mozbuild.util import ReadOnlyDict
+
+class Parameters(ReadOnlyDict):
+    """An immutable dictionary with nicer KeyError messages on failure"""
+    def __getitem__(self, k):
+        try:
+            return super(Parameters, self).__getitem__(k)
+        except KeyError:
+            raise KeyError("taskgraph parameter {!r} not found".format(k))
+
+
+def load_parameters_file(options):
+    """
+    Load parameters from the --parameters option
+    """
+    filename = options['parameters']
+    if not filename:
+        return Parameters()
+    with open(filename) as f:
+        if filename.endswith('.yml'):
+            return Parameters(**yaml.safe_load(f))
+        elif filename.endswith('.json'):
+            return Parameters(**json.load(f))
+        else:
+            print("Parameters file `{}` is not JSON or YAML".format(filename))
+            sys.exit(1)
+
+def get_decision_parameters(options):
+    """
+    Load parameters from the command-line options for 'taskgraph decision'.
+    """
+    return Parameters({n: options[n] for n in [
+        'base_repository',
+        'head_repository',
+        'head_rev',
+        'head_ref',
+        'revision_hash',
+        'message',
+        'project',
+        'pushlog_id',
+        'owner',
+        'level',
+        'target_tasks_method',
+    ] if n in options})
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/target_tasks.py
@@ -0,0 +1,40 @@
+# -*- coding: utf-8 -*-
+
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+_target_task_methods = {}
+def _target_task(name):
+    def wrap(func):
+        _target_task_methods[name] = func
+        return func
+    return wrap
+
+def get_method(method):
+    """Get a target_task_method to pass to a TaskGraphGenerator."""
+    return _target_task_methods[method]
+
+@_target_task('from_parameters')
+def target_tasks_from_parameters(full_task_graph, parameters):
+    """Get the target task set from parameters['target_tasks'].  This is
+    useful for re-running a decision task with the same target set as in an
+    earlier run, by copying `target_tasks.json` into `parameters.yml`."""
+    return parameters['target_tasks']
+
+@_target_task('try_option_syntax')
+def target_tasks_try_option_syntax(full_task_graph, parameters):
+    """Generate a list of target tasks based on try syntax in
+    parameters['message'] and, for context, the full task graph."""
+    from taskgraph.try_option_syntax import TryOptionSyntax
+    options = TryOptionSyntax(parameters['message'], full_task_graph)
+    return [t.label for t in full_task_graph.tasks.itervalues()
+            if options.task_matches(t.attributes)]
+
+@_target_task('all_tasks')
+def target_tasks_all_tasks(full_task_graph, parameters):
+    """Trivially target all tasks."""
+    return full_task_graph.tasks.keys()
+
new file mode 100644
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_create.py
@@ -0,0 +1,57 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from .. import create
+from ..graph import Graph
+from ..types import Task, TaskGraph
+
+from mozunit import main
+
+class FakeKind(object):
+
+    def get_task_definition(self, task, deps_by_name):
+        # sanity-check the deps_by_name
+        for k, v in deps_by_name.iteritems():
+            assert k == 'edge'
+        return {'payload': 'hello world'}
+
+
+class TestCreate(unittest.TestCase):
+
+    def setUp(self):
+        self.created_tasks = {}
+        self.old_create_task = create._create_task
+        create._create_task = self.fake_create_task
+
+    def tearDown(self):
+        create._create_task = self.old_create_task
+
+    def fake_create_task(self, session, task_id, label, task_def):
+        self.created_tasks[task_id] = task_def
+
+    def test_create_tasks(self):
+        kind = FakeKind()
+        tasks = {
+            'a': Task(kind=kind, label='a'),
+            'b': Task(kind=kind, label='b'),
+        }
+        graph = Graph(nodes=set('ab'), edges={('a', 'b', 'edge')})
+        taskgraph = TaskGraph(tasks, graph)
+
+        create.create_tasks(taskgraph)
+
+        for tid, task in self.created_tasks.iteritems():
+            self.assertEqual(task['payload'], 'hello world')
+            # make sure the dependencies exist, at least
+            for depid in task['dependencies']:
+                self.assertIn(depid, self.created_tasks)
+
+
+if __name__ == '__main__':
+    main()
+
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_decision.py
@@ -0,0 +1,76 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import os
+import json
+import yaml
+import shutil
+import unittest
+import tempfile
+
+from .. import decision
+from ..graph import Graph
+from ..types import Task, TaskGraph
+from mozunit import main
+
+class TestDecision(unittest.TestCase):
+
+    def test_taskgraph_to_json(self):
+        tasks = {
+            'a': Task(kind=None, label='a', attributes={'attr': 'a-task'}),
+            'b': Task(kind=None, label='b', task={'task': 'def'}),
+        }
+        graph = Graph(nodes=set('ab'), edges={('a', 'b', 'edgelabel')})
+        taskgraph = TaskGraph(tasks, graph)
+
+        res = decision.taskgraph_to_json(taskgraph)
+
+        self.assertEqual(res, {
+            'a': {
+                'attributes': {'attr': 'a-task'},
+                'task': {},
+                'dependencies': [('edgelabel', 'b')],
+            },
+            'b': {
+                'attributes': {},
+                'task': {'task': 'def'},
+                'dependencies': [],
+            }
+        })
+
+
+    def test_write_artifact_json(self):
+        data = [{'some': 'data'}]
+        tmpdir = tempfile.mkdtemp()
+        try:
+            decision.ARTIFACTS_DIR = os.path.join(tmpdir, "artifacts")
+            decision.write_artifact("artifact.json", data, lambda *args: None)
+            with open(os.path.join(decision.ARTIFACTS_DIR, "artifact.json")) as f:
+                self.assertEqual(json.load(f), data)
+        finally:
+            if os.path.exists(tmpdir):
+                shutil.rmtree(tmpdir)
+            decision.ARTIFACTS_DIR = 'artifacts'
+
+
+    def test_write_artifact_yml(self):
+        data = [{'some': 'data'}]
+        tmpdir = tempfile.mkdtemp()
+        try:
+            decision.ARTIFACTS_DIR = os.path.join(tmpdir, "artifacts")
+            decision.write_artifact("artifact.yml", data, lambda *args: None)
+            with open(os.path.join(decision.ARTIFACTS_DIR, "artifact.yml")) as f:
+                self.assertEqual(yaml.safe_load(f), data)
+        finally:
+            if os.path.exists(tmpdir):
+                shutil.rmtree(tmpdir)
+            decision.ARTIFACTS_DIR = 'artifacts'
+
+
+if __name__ == '__main__':
+    main()
+
+
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_generator.py
@@ -0,0 +1,96 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from ..generator import TaskGraphGenerator
+from .. import types
+from .. import graph
+from mozunit import main
+
+
+class FakeKind(object):
+
+    def maketask(self, i):
+        return types.Task(
+            self,
+            label='t-{}'.format(i),
+            attributes={'tasknum': str(i)},
+            task={},
+            i=i)
+
+    def load_tasks(self, parameters):
+        self.tasks = [self.maketask(i) for i in range(3)]
+        return self.tasks
+
+    def get_task_dependencies(self, task, full_task_set):
+        i = task.extra['i']
+        if i > 0:
+            return [('t-{}'.format(i - 1), 'prev')]
+        else:
+            return []
+
+
+class WithFakeKind(TaskGraphGenerator):
+
+    def _load_kinds(self):
+        yield FakeKind()
+
+
+class TestGenerator(unittest.TestCase):
+
+    def setUp(self):
+        def log(level, name, data, message):
+            pass
+        self.target_tasks = []
+
+        def target_tasks_method(full_task_graph, parameters):
+            return self.target_tasks
+        self.tgg = WithFakeKind('/root', log, {}, target_tasks_method)
+
+    def test_full_task_set(self):
+        "The full_task_set property has all tasks"
+        self.assertEqual(self.tgg.full_task_set.graph,
+                         graph.Graph({'t-0', 't-1', 't-2'}, set()))
+        self.assertEqual(self.tgg.full_task_set.tasks.keys(),
+                         ['t-0', 't-1', 't-2'])
+
+    def test_full_task_graph(self):
+        "The full_task_graph property has all tasks, and links"
+        self.assertEqual(self.tgg.full_task_graph.graph,
+                         graph.Graph({'t-0', 't-1', 't-2'},
+                                     {
+                                         ('t-1', 't-0', 'prev'),
+                                         ('t-2', 't-1', 'prev'),
+                         }))
+        self.assertEqual(self.tgg.full_task_graph.tasks.keys(),
+                         ['t-0', 't-1', 't-2'])
+
+    def test_target_task_set(self):
+        "The target_task_set property has the targeted tasks"
+        self.target_tasks = ['t-1']
+        self.assertEqual(self.tgg.target_task_set.graph,
+                         graph.Graph({'t-1'}, set()))
+        self.assertEqual(self.tgg.target_task_set.tasks.keys(),
+                         ['t-1'])
+
+    def test_target_task_graph(self):
+        "The target_task_graph property has the targeted tasks and deps"
+        self.target_tasks = ['t-1']
+        self.assertEqual(self.tgg.target_task_graph.graph,
+                         graph.Graph({'t-0', 't-1'},
+                                     {('t-1', 't-0', 'prev')}))
+        self.assertEqual(sorted(self.tgg.target_task_graph.tasks.keys()),
+                         sorted(['t-0', 't-1']))
+
+    def test_optimized_task_graph(self):
+        "The optimized task graph is the target task graph (for now)"
+        self.target_tasks = ['t-1']
+        self.assertEqual(self.tgg.optimized_task_graph.graph,
+                         self.tgg.target_task_graph.graph)
+
+if __name__ == '__main__':
+    main()
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_graph.py
@@ -0,0 +1,149 @@
+# -*- coding: utf-8 -*-
+
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from ..graph import Graph
+from mozunit import main
+
+
+class TestGraph(unittest.TestCase):
+
+    tree = Graph(set(['a', 'b', 'c', 'd', 'e', 'f', 'g']), {
+        ('a', 'b', 'L'),
+        ('a', 'c', 'L'),
+        ('b', 'd', 'K'),
+        ('b', 'e', 'K'),
+        ('c', 'f', 'N'),
+        ('c', 'g', 'N'),
+    })
+
+    linear = Graph(set(['1', '2', '3', '4']), {
+        ('1', '2', 'L'),
+        ('2', '3', 'L'),
+        ('3', '4', 'L'),
+    })
+
+    diamonds = Graph(set(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']),
+                     set(tuple(x) for x in
+                         'AFL ADL BDL BEL CEL CHL DFL DGL EGL EHL FIL GIL GJL HJL'.split()
+                         ))
+
+    multi_edges = Graph(set(['1', '2', '3', '4']), {
+        ('2', '1', 'red'),
+        ('2', '1', 'blue'),
+        ('3', '1', 'red'),
+        ('3', '2', 'blue'),
+        ('3', '2', 'green'),
+        ('4', '3', 'green'),
+    })
+
+    disjoint = Graph(set(['1', '2', '3', '4', 'α', 'β', 'γ']), {
+        ('2', '1', 'red'),
+        ('3', '1', 'red'),
+        ('3', '2', 'green'),
+        ('4', '3', 'green'),
+        ('α', 'β', 'πράσινο'),
+        ('β', 'γ', 'κόκκινο'),
+        ('α', 'γ', 'μπλε'),
+    })
+
+    def test_transitive_closure_empty(self):
+        "transitive closure of an empty set is an empty graph"
+        g = Graph(set(['a', 'b', 'c']), {('a', 'b', 'L'), ('a', 'c', 'L')})
+        self.assertEqual(g.transitive_closure(set()),
+                         Graph(set(), set()))
+
+    def test_transitive_closure_disjoint(self):
+        "transitive closure of a disjoint set is a subset"
+        g = Graph(set(['a', 'b', 'c']), set())
+        self.assertEqual(g.transitive_closure(set(['a', 'c'])),
+                         Graph(set(['a', 'c']), set()))
+
+    def test_transitive_closure_trees(self):
+        "transitive closure of a tree, at two non-root nodes, is the two subtrees"
+        self.assertEqual(self.tree.transitive_closure(set(['b', 'c'])),
+                         Graph(set(['b', 'c', 'd', 'e', 'f', 'g']), {
+                             ('b', 'd', 'K'),
+                             ('b', 'e', 'K'),
+                             ('c', 'f', 'N'),
+                             ('c', 'g', 'N'),
+                         }))
+
+    def test_transitive_closure_multi_edges(self):
+        "transitive closure of a tree with multiple edges between nodes keeps those edges"
+        self.assertEqual(self.multi_edges.transitive_closure(set(['3'])),
+                         Graph(set(['1', '2', '3']), {
+                             ('2', '1', 'red'),
+                             ('2', '1', 'blue'),
+                             ('3', '1', 'red'),
+                             ('3', '2', 'blue'),
+                             ('3', '2', 'green'),
+                         }))
+
+    def test_transitive_closure_disjoint(self):
+        "transitive closure of a disjoint graph keeps those edges"
+        self.assertEqual(self.disjoint.transitive_closure(set(['3', 'β'])),
+                         Graph(set(['1', '2', '3', 'β', 'γ']), {
+                             ('2', '1', 'red'),
+                             ('3', '1', 'red'),
+                             ('3', '2', 'green'),
+                             ('β', 'γ', 'κόκκινο'),
+                         }))
+
+    def test_transitive_closure_linear(self):
+        "transitive closure of a linear graph includes all nodes in the line"
+        self.assertEqual(self.linear.transitive_closure(set(['1'])), self.linear)
+
+    def test_visit_postorder_empty(self):
+        "postorder visit of an empty graph is empty"
+        self.assertEqual(list(Graph(set(), set()).visit_postorder()), [])
+
+    def assert_postorder(self, seq, all_nodes):
+        seen = set()
+        for e in seq:
+            for l, r, n in self.tree.edges:
+                if l == e:
+                    self.failUnless(r in seen)
+            seen.add(e)
+        self.assertEqual(seen, all_nodes)
+
+    def test_visit_postorder_tree(self):
+        "postorder visit of a tree satisfies invariant"
+        self.assert_postorder(self.tree.visit_postorder(), self.tree.nodes)
+
+    def test_visit_postorder_diamonds(self):
+        "postorder visit of a graph full of diamonds satisfies invariant"
+        self.assert_postorder(self.diamonds.visit_postorder(), self.diamonds.nodes)
+
+    def test_visit_postorder_multi_edges(self):
+        "postorder visit of a graph with duplicate edges satisfies invariant"
+        self.assert_postorder(self.multi_edges.visit_postorder(), self.multi_edges.nodes)
+
+    def test_visit_postorder_disjoint(self):
+        "postorder visit of a disjoint graph satisfies invariant"
+        self.assert_postorder(self.disjoint.visit_postorder(), self.disjoint.nodes)
+
+    def test_links_dict(self):
+        "link dict for a graph with multiple edges is correct"
+        self.assertEqual(self.multi_edges.links_dict(), {
+            '2': set(['1']),
+            '3': set(['1', '2']),
+            '4': set(['3']),
+        })
+
+    def test_reverse_links_dict(self):
+        "reverse link dict for a graph with multiple edges is correct"
+        self.assertEqual(self.multi_edges.reverse_links_dict(), {
+            '1': set(['2', '3']),
+            '2': set(['3']),
+            '3': set(['4']),
+        })
+
+if __name__ == '__main__':
+    main()
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_kind_legacy.py
@@ -0,0 +1,41 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from ..kind.legacy import LegacyKind, TASKID_PLACEHOLDER
+from ..types import Task
+from mozunit import main
+
+
+class TestLegacyKind(unittest.TestCase):
+    # NOTE: much of LegacyKind is copy-pasted from the old legacy code, which
+    # is emphatically *not* designed for testing, so this test class does not
+    # attempt to test the entire class.
+
+    def setUp(self):
+        def log(level, name, data, message):
+            pass
+        self.kind = LegacyKind('/root', {}, log)
+
+    def test_get_task_definition_artifact_sub(self):
+        "get_task_definition correctly substiatutes artifact URLs"
+        task_def = {
+            'input_file': TASKID_PLACEHOLDER.format("G5BoWlCBTqOIhn3K3HyvWg"),
+            'embedded': 'TASK={} FETCH=lazy'.format(
+                TASKID_PLACEHOLDER.format('G5BoWlCBTqOIhn3K3HyvWg')),
+        }
+        task = Task(self.kind, 'label', task=task_def)
+        dep_taskids = {TASKID_PLACEHOLDER.format('G5BoWlCBTqOIhn3K3HyvWg'): 'parent-taskid'}
+        task_def = self.kind.get_task_definition(task, dep_taskids)
+        self.assertEqual(task_def, {
+            'input_file': 'parent-taskid',
+            'embedded': 'TASK=parent-taskid FETCH=lazy',
+        })
+
+
+if __name__ == '__main__':
+    main()
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_parameters.py
@@ -0,0 +1,41 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from ..parameters import Parameters, load_parameters_file
+from mozunit import main, MockedOpen
+
+class TestParameters(unittest.TestCase):
+
+    def test_Parameters_immutable(self):
+        p = Parameters(x=10, y=20)
+        def assign():
+            p['x'] = 20
+        self.assertRaises(Exception, assign)
+
+    def test_Parameters_KeyError(self):
+        p = Parameters(x=10, y=20)
+        self.assertRaises(KeyError, lambda: p['z'])
+
+    def test_Parameters_get(self):
+        p = Parameters(x=10, y=20)
+        self.assertEqual(p['x'], 10)
+
+    def test_load_parameters_file_yaml(self):
+        with MockedOpen({"params.yml": "some: data\n"}):
+            self.assertEqual(
+                    load_parameters_file({'parameters': 'params.yml'}),
+                    {'some': 'data'})
+
+    def test_load_parameters_file_json(self):
+        with MockedOpen({"params.json": '{"some": "data"}'}):
+            self.assertEqual(
+                    load_parameters_file({'parameters': 'params.json'}),
+                    {'some': 'data'})
+
+if __name__ == '__main__':
+    main()
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_target_tasks.py
@@ -0,0 +1,56 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from .. import target_tasks
+from .. import try_option_syntax
+from ..graph import Graph
+from ..types import Task, TaskGraph
+from mozunit import main
+
+
+class FakeTryOptionSyntax(object):
+
+    def __init__(self, message, task_graph):
+        pass
+
+    def task_matches(self, attributes):
+        return 'at-at' in attributes
+
+
+class TestTargetTasks(unittest.TestCase):
+
+    def test_from_parameters(self):
+        method = target_tasks.get_method('from_parameters')
+        self.assertEqual(method(None, {'target_tasks': ['a', 'b']}),
+                         ['a', 'b'])
+
+    def test_all_tasks(self):
+        method = target_tasks.get_method('all_tasks')
+        graph = TaskGraph(tasks={'a': Task(kind=None, label='a')},
+                          graph=Graph(nodes={'a'}, edges=set()))
+        self.assertEqual(method(graph, {}), ['a'])
+
+    def test_try_option_syntax(self):
+        tasks = {
+            'a': Task(kind=None, label='a'),
+            'b': Task(kind=None, label='b', attributes={'at-at': 'yep'}),
+        }
+        graph = Graph(nodes=set('ab'), edges=set())
+        tg = TaskGraph(tasks, graph)
+        params = {'message': 'try me'}
+
+        orig_TryOptionSyntax = try_option_syntax.TryOptionSyntax
+        try:
+            try_option_syntax.TryOptionSyntax = FakeTryOptionSyntax
+            method = target_tasks.get_method('try_option_syntax')
+            self.assertEqual(method(tg, params), ['b'])
+        finally:
+            try_option_syntax.TryOptionSyntax = orig_TryOptionSyntax
+
+if __name__ == '__main__':
+    main()
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_try_option_syntax.py
@@ -0,0 +1,235 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from ..try_option_syntax import TryOptionSyntax
+from ..graph import Graph
+from ..types import TaskGraph, Task
+from mozunit import main
+
+# an empty graph, for things that don't look at it
+empty_graph = TaskGraph({}, Graph(set(), set()))
+
+def unittest_task(n, tp):
+    return (n, Task('test', n, {
+        'unittest_try_name': n,
+        'test_platform': tp,
+    }))
+
+tasks = {k: v for k,v in [
+    unittest_task('mochitest-browser-chrome', 'linux'),
+    unittest_task('mochitest-browser-chrome-e10s', 'linux64'),
+    unittest_task('mochitest-chrome', 'linux'),
+    unittest_task('mochitest-webgl', 'linux'),
+    unittest_task('crashtest-e10s', 'linux'),
+    unittest_task('gtest', 'linux64'),
+]}
+graph_with_jobs = TaskGraph(tasks, Graph(set(tasks), set()))
+
+
+class TestTryOptionSyntax(unittest.TestCase):
+
+    def test_empty_message(self):
+        "Given an empty message, it should return an empty value"
+        tos = TryOptionSyntax('', empty_graph)
+        self.assertEqual(tos.build_types, [])
+        self.assertEqual(tos.jobs, [])
+        self.assertEqual(tos.unittests, [])
+        self.assertEqual(tos.platforms, [])
+
+    def test_message_without_try(self):
+        "Given a non-try message, it should return an empty value"
+        tos = TryOptionSyntax('Bug 1234: frobnicte the foo', empty_graph)
+        self.assertEqual(tos.build_types, [])
+        self.assertEqual(tos.jobs, [])
+        self.assertEqual(tos.unittests, [])
+        self.assertEqual(tos.platforms, [])
+
+    def test_unknown_args(self):
+        "unknown arguments are ignored"
+        tos = TryOptionSyntax('try: --doubledash -z extra', empty_graph)
+        # equilvant to "try:"..
+        self.assertEqual(tos.build_types, [])
+        self.assertEqual(tos.jobs, None)
+
+    def test_b_do(self):
+        "-b do should produce both build_types"
+        tos = TryOptionSyntax('try: -b do', empty_graph)
+        self.assertEqual(sorted(tos.build_types), ['debug', 'opt'])
+
+    def test_b_d(self):
+        "-b d should produce build_types=['debug']"
+        tos = TryOptionSyntax('try: -b d', empty_graph)
+        self.assertEqual(sorted(tos.build_types), ['debug'])
+
+    def test_b_o(self):
+        "-b o should produce build_types=['opt']"
+        tos = TryOptionSyntax('try: -b o', empty_graph)
+        self.assertEqual(sorted(tos.build_types), ['opt'])
+
+    def test_build_o(self):
+        "--build o should produce build_types=['opt']"
+        tos = TryOptionSyntax('try: --build o', empty_graph)
+        self.assertEqual(sorted(tos.build_types), ['opt'])
+
+    def test_b_dx(self):
+        "-b dx should produce build_types=['debug'], silently ignoring the x"
+        tos = TryOptionSyntax('try: -b dx', empty_graph)
+        self.assertEqual(sorted(tos.build_types), ['debug'])
+
+    def test_j_job(self):
+        "-j somejob sets jobs=['somejob']"
+        tos = TryOptionSyntax('try: -j somejob', empty_graph)
+        self.assertEqual(sorted(tos.jobs), ['somejob'])
+
+    def test_j_jobs(self):
+        "-j job1,job2 sets jobs=['job1', 'job2']"
+        tos = TryOptionSyntax('try: -j job1,job2', empty_graph)
+        self.assertEqual(sorted(tos.jobs), ['job1', 'job2'])
+
+    def test_j_all(self):
+        "-j all sets jobs=None"
+        tos = TryOptionSyntax('try: -j all', empty_graph)
+        self.assertEqual(tos.jobs, None)
+
+    def test_j_twice(self):
+        "-j job1 -j job2 sets jobs=job1, job2"
+        tos = TryOptionSyntax('try: -j job1 -j job2', empty_graph)
+        self.assertEqual(sorted(tos.jobs), sorted(['job1', 'job2']))
+
+    def test_p_all(self):
+        "-p all sets platforms=None"
+        tos = TryOptionSyntax('try: -p all', empty_graph)
+        self.assertEqual(tos.platforms, None)
+
+    def test_p_linux(self):
+        "-p linux sets platforms=['linux']"
+        tos = TryOptionSyntax('try: -p linux', empty_graph)
+        self.assertEqual(tos.platforms, ['linux'])
+
+    def test_p_linux_win32(self):
+        "-p linux,win32 sets platforms=['linux', 'win32']"
+        tos = TryOptionSyntax('try: -p linux,win32', empty_graph)
+        self.assertEqual(sorted(tos.platforms), ['linux', 'win32'])
+
+    def test_p_expands_ridealongs(self):
+        "-p linux,linux64 includes the RIDEALONG_BUILDS"
+        tos = TryOptionSyntax('try: -p linux,linux64', empty_graph)
+        self.assertEqual(sorted(tos.platforms), [
+            'linux',
+            'linux64',
+            'sm-arm-sim',
+            'sm-arm64-sim',
+            'sm-compacting',
+            'sm-plain',
+            'sm-rootanalysis',
+        ])
+
+    def test_u_none(self):
+        "-u none sets unittests=[]"
+        tos = TryOptionSyntax('try: -u none', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), [])
+
+    def test_u_all(self):
+        "-u all sets unittests=[..whole list..]"
+        tos = TryOptionSyntax('try: -u all', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([{'test': t} for t in tasks]))
+
+    def test_u_single(self):
+        "-u mochitest-webgl sets unittests=[mochitest-webgl]"
+        tos = TryOptionSyntax('try: -u mochitest-webgl', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([{'test': 'mochitest-webgl'}]))
+
+    def test_u_alias(self):
+        "-u mochitest-gl sets unittests=[mochitest-webgl]"
+        tos = TryOptionSyntax('try: -u mochitest-gl', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([{'test': 'mochitest-webgl'}]))
+
+    def test_u_multi_alias(self):
+        "-u e10s sets unittests=[all e10s unittests]"
+        tos = TryOptionSyntax('try: -u e10s', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': t} for t in tasks if 'e10s' in t
+        ]))
+
+    def test_u_commas(self):
+        "-u mochitest-webgl,gtest sets unittests=both"
+        tos = TryOptionSyntax('try: -u mochitest-webgl,gtest', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'mochitest-webgl'},
+            {'test': 'gtest'},
+        ]))
+
+    def test_u_chunks(self):
+        "-u gtest-3,gtest-4 selects the third and fourth chunk of gtest"
+        tos = TryOptionSyntax('try: -u gtest-3,gtest-4', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'gtest', 'only_chunks': set('34')},
+        ]))
+
+    def test_u_platform(self):
+        "-u gtest[linux] selects the linux platform for gtest"
+        tos = TryOptionSyntax('try: -u gtest[linux]', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'gtest', 'platforms': ['linux']},
+        ]))
+
+    def test_u_platforms(self):
+        "-u gtest[linux,win32] selects the linux and win32 platforms for gtest"
+        tos = TryOptionSyntax('try: -u gtest[linux,win32]', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'gtest', 'platforms': ['linux', 'win32']},
+        ]))
+
+    def test_u_platforms_pretty(self):
+        "-u gtest[Ubuntu] selects the linux and linux64 platforms for gtest"
+        tos = TryOptionSyntax('try: -u gtest[Ubuntu]', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'gtest', 'platforms': ['linux', 'linux64']},
+        ]))
+
+    def test_u_platforms_negated(self):
+        "-u gtest[-linux] selects all platforms but linux for gtest"
+        tos = TryOptionSyntax('try: -u gtest[-linux]', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'gtest', 'platforms': ['linux64']},
+        ]))
+
+    def test_u_platforms_negated_pretty(self):
+        "-u gtest[Ubuntu,-x64] selects just linux for gtest"
+        tos = TryOptionSyntax('try: -u gtest[Ubuntu,-x64]', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'gtest', 'platforms': ['linux']},
+        ]))
+
+    def test_u_chunks_platforms(self):
+        "-u gtest-1[linux,win32] selects the linux and win32 platforms for chunk 1 of gtest"
+        tos = TryOptionSyntax('try: -u gtest-1[linux,win32]', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': 'gtest', 'platforms': ['linux', 'win32'], 'only_chunks': set('1')},
+        ]))
+
+    def test_u_chunks_platform_alias(self):
+        "-u e10s-1[linux] selects the first chunk of every e10s test on linux"
+        tos = TryOptionSyntax('try: -u e10s-1[linux]', graph_with_jobs)
+        self.assertEqual(sorted(tos.unittests), sorted([
+            {'test': t, 'platforms': ['linux'], 'only_chunks': set('1')}
+            for t in tasks if 'e10s' in t
+        ]))
+
+    def test_trigger_tests(self):
+        "--trigger-tests 10 sets trigger_tests"
+        tos = TryOptionSyntax('try: --trigger-tests 10', empty_graph)
+        self.assertEqual(tos.trigger_tests, 10)
+
+    def test_interactive(self):
+        "--interactive sets interactive"
+        tos = TryOptionSyntax('try: --interactive', empty_graph)
+        self.assertEqual(tos.interactive, True)
+
+if __name__ == '__main__':
+    main()
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/try_option_syntax.py
@@ -0,0 +1,483 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import argparse
+import copy
+import re
+import shlex
+
+TRY_DELIMITER = 'try:'
+
+# The build type aliases are very cryptic and only used in try flags these are
+# mappings from the single char alias to a longer more recognizable form.
+BUILD_TYPE_ALIASES = {
+    'o': 'opt',
+    'd': 'debug'
+}
+
+# mapping from shortcut name (usable with -u) to a boolean function identifying
+# matching test names
+def alias_prefix(prefix):
+    return lambda name: name.startswith(prefix)
+
+def alias_contains(infix):
+    return lambda name: infix in name
+
+def alias_matches(pattern):
+    pattern = re.compile(pattern)
+    return lambda name: pattern.match(name)
+
+UNITTEST_ALIASES = {
+    'cppunit': alias_prefix('cppunit'),
+    'crashtest': alias_prefix('crashtest'),
+    'crashtest-e10s': alias_prefix('crashtest-e10s'),
+    'e10s': alias_contains('e10s'),
+    'firefox-ui-functional': alias_prefix('firefox-ui-functional'),
+    'firefox-ui-functional-e10s': alias_prefix('firefox-ui-functional-e10s'),
+    'gaia-js-integration': alias_contains('gaia-js-integration'),
+    'gtest': alias_prefix('gtest'),
+    'jittest': alias_prefix('jittest'),
+    'jittests': alias_prefix('jittest'),
+    'jsreftest': alias_prefix('jsreftest'),
+    'jsreftest-e10s': alias_prefix('jsreftest-e10s'),
+    'luciddream': alias_prefix('luciddream'),
+    'marionette': alias_prefix('marionette'),
+    'marionette-e10s': alias_prefix('marionette-e10s'),
+    'mochitest': alias_prefix('mochitest'),
+    'mochitests': alias_prefix('mochitest'),
+    'mochitest-e10s': alias_prefix('mochitest-e10s'),
+    'mochitests-e10s': alias_prefix('mochitest-e10s'),
+    'mochitest-debug': alias_prefix('mochitest-debug-'),
+    'mochitest-a11y': alias_contains('mochitest-a11y'),
+    'mochitest-bc': alias_prefix('mochitest-browser-chrome'),
+    'mochitest-bc-e10s': alias_prefix('mochitest-browser-chrome-e10s'),
+    'mochitest-browser-chrome': alias_prefix('mochitest-browser-chrome'),
+    'mochitest-browser-chrome-e10s': alias_prefix('mochitest-browser-chrome-e10s'),
+    'mochitest-chrome': alias_contains('mochitest-chrome'),
+    'mochitest-dt': alias_prefix('mochitest-devtools-chrome'),
+    'mochitest-dt-e10s': alias_prefix('mochitest-devtools-chrome-e10s'),
+    'mochitest-gl': alias_prefix('mochitest-webgl'),
+    'mochitest-gl-e10s': alias_prefix('mochitest-webgl-e10s'),
+    'mochitest-jetpack': alias_prefix('mochitest-jetpack'),
+    'mochitest-media': alias_prefix('mochitest-media'),
+    'mochitest-media-e10s': alias_prefix('mochitest-media-e10s'),
+    'mochitest-vg': alias_prefix('mochitest-valgrind'),
+    'reftest': alias_matches(r'^(plain-)?reftest.*$'),
+    'reftest-no-accel': alias_matches(r'^(plain-)?reftest-no-accel.*$'),
+    'reftests': alias_matches(r'^(plain-)?reftest.*$'),
+    'reftests-e10s': alias_matches(r'^(plain-)?reftest-e10s.*$'),
+    'robocop': alias_prefix('robocop'),
+    'web-platform-test': alias_prefix('web-platform-tests'),
+    'web-platform-tests': alias_prefix('web-platform-tests'),
+    'web-platform-tests-e10s': alias_prefix('web-platform-tests-e10s'),
+    'web-platform-tests-reftests': alias_prefix('web-platform-tests-reftests'),
+    'web-platform-tests-reftests-e10s': alias_prefix('web-platform-tests-reftests-e10s'),
+    'xpcshell': alias_prefix('xpcshell'),
+}
+
+# unittest platforms can be specified by substring of the "pretty name", which
+# is basically the old Buildbot builder name.  This dict has {pretty name,
+# [test_platforms]} translations, This includes only the most commonly-used
+# substrings.  This is intended only for backward-compatibility.  New test
+# platforms should have their `test_platform` spelled out fully in try syntax.
+UNITTEST_PLATFORM_PRETTY_NAMES = {
+    'Ubuntu': ['linux', 'linux64'],
+    'x64': ['linux64'],
+    # other commonly-used substrings for platforms not yet supported with
+    # in-tree taskgraphs:
+    #'10.10': [..TODO..],
+    #'10.10.5': [..TODO..],
+    #'10.6': [..TODO..],
+    #'10.8': [..TODO..],
+    #'Android 2.3 API9': [..TODO..],
+    #'Android 4.3 API15+': [..TODO..],
+    #'Windows 7':  [..TODO..],
+    #'Windows 7 VM': [..TODO..],
+    #'Windows 8':  [..TODO..],
+    #'Windows XP': [..TODO..],
+    #'win32': [..TODO..],
+    #'win64': [..TODO..],
+}
+
+# We have a few platforms for which we want to do some "extra" builds, or at
+# least build-ish things.  Sort of.  Anyway, these other things are implemented
+# as different "platforms".
+RIDEALONG_BUILDS = {
+    'linux64': [
+        'sm-plain',
+        'sm-arm-sim',
+        'sm-arm64-sim',
+        'sm-compacting',
+        'sm-rootanalysis',
+    ],
+}
+
+TEST_CHUNK_SUFFIX = re.compile('(.*)-([0-9]+)$')
+
+class TryOptionSyntax(object):
+
+    def __init__(self, message, full_task_graph):
+        """
+        Parse a "try syntax" formatted commit message.  This is the old "-b do -p
+        win32 -u all" format.  Aliases are applied to map short names to full
+        names.
+
+        The resulting object has attributes:
+
+        - build_types: a list containing zero or more of 'opt' and 'debug'
+        - platforms: a list of selected platform names, or None for all
+        - unittests: a list of tests, of the form given below, or None for all
+        - jobs: a list of requested job names, or None for all
+        - trigger_tests: the number of times tests should be triggered
+        - interactive; true if --interactive
+
+        Note that -t is currently completely ignored.
+
+        The unittests and talos lists contain dictionaries of the form:
+
+        {
+            'test': '<suite name>',
+            'platforms': [..platform names..], # to limit to only certain platforms
+            'only_chunks': set([..chunk numbers..]), # to limit only to certain chunks
+        }
+        """
+        self.jobs = []
+        self.build_types = []
+        self.platforms = []
+        self.unittests = []
+        self.trigger_tests = 0
+        self.interactive = False
+
+        # shlex used to ensure we split correctly when giving values to argparse.
+        parts = shlex.split(self.escape_whitespace_in_brackets(message))
+        try_idx = None
+        for idx, part in enumerate(parts):
+            if part == TRY_DELIMITER:
+                try_idx = idx
+                break
+
+        if try_idx is None:
+            return
+
+        # Argument parser based on try flag flags
+        parser = argparse.ArgumentParser()
+        parser.add_argument('-b', '--build', dest='build_types')
+        parser.add_argument('-p', '--platform', nargs='?', dest='platforms', const='all', default='all')
+        parser.add_argument('-u', '--unittests', nargs='?', dest='unittests', const='all', default='all')
+        parser.add_argument('-i', '--interactive', dest='interactive', action='store_true', default=False)
+        parser.add_argument('-j', '--job', dest='jobs', action='append')
+        # In order to run test jobs multiple times
+        parser.add_argument('--trigger-tests', dest='trigger_tests', type=int, default=1)
+        args, _ = parser.parse_known_args(parts[try_idx:])
+
+        self.jobs = self.parse_jobs(args.jobs)
+        self.build_types = self.parse_build_types(args.build_types)
+        self.platforms = self.parse_platforms(args.platforms)
+        self.unittests = self.parse_unittests(args.unittests, full_task_graph)
+        self.trigger_tests = args.trigger_tests
+        self.interactive = args.interactive
+
+    def parse_jobs(self, jobs_arg):
+        if not jobs_arg or jobs_arg == ['all']:
+            return None
+        expanded = []
+        for job in jobs_arg:
+            expanded.extend(j.strip() for j in job.split(','))
+        return expanded
+
+    def parse_build_types(self, build_types_arg):
+        if build_types_arg is None:
+            build_types_arg = []
+        build_types = filter(None, [ BUILD_TYPE_ALIASES.get(build_type) for
+                build_type in build_types_arg ])
+        return build_types
+
+    def parse_platforms(self, platform_arg):
+        if platform_arg == 'all':
+            return None
+
+        results = []
+        for build in platform_arg.split(','):
+            results.append(build)
+            if build in RIDEALONG_BUILDS:
+                results.extend(RIDEALONG_BUILDS[build])
+
+        return results
+
+    def parse_unittests(self, unittest_arg, full_task_graph):
+        '''
+        Parse a unittest (-u) option, in the context of a full task graph containing
+        available `unittest_try_name` attributes.  There are three cases:
+
+            - unittest_arg is == 'none' (meaning an empty list)
+            - unittest_arg is == 'all' (meaning use the list of jobs for that job type)
+            - unittest_arg is comma string which needs to be parsed
+        '''
+
+        # Empty job list case...
+        if unittest_arg is None or unittest_arg == 'none':
+            return []
+
+        all_platforms = set(t.attributes['test_platform']
+                            for t in full_task_graph.tasks.itervalues()
+                            if 'test_platform' in t.attributes)
+
+        tests = self.parse_test_opts(unittest_arg, all_platforms)
+
+        if not tests:
+            return []
+
+        all_tests = set(t.attributes['unittest_try_name']
+                        for t in full_task_graph.tasks.itervalues()
+                        if 'unittest_try_name' in t.attributes)
+
+        # Special case where tests is 'all' and must be expanded
+        if tests[0]['test'] == 'all':
+            results = []
+            all_entry = tests[0]
+            for test in all_tests:
+                entry = {'test': test}
+                # If there are platform restrictions copy them across the list.
+                if 'platforms' in all_entry:
+                    entry['platforms'] = list(all_entry['platforms'])
+                results.append(entry)
+            return self.parse_test_chunks(all_tests, results)
+        else:
+            return self.parse_test_chunks(all_tests, tests)
+
+    def parse_test_opts(self, input_str, all_platforms):
+        '''
+        Parse `testspec,testspec,..`, where each testspec is a test name
+        optionally followed by a list of test platforms or negated platforms in
+        `[]`.
+
+        No brackets indicates that tests should run on all platforms for which
+        builds are available.  If testspecs are provided, then each is treated,
+        from left to right, as an instruction to include or (if negated)
+        exclude a set of test platforms.  A single spec may expand to multiple
+        test platforms via UNITTEST_PLATFORM_PRETTY_NAMES.  If the first test
+        spec is negated, processing begins with the full set of available test
+        platforms; otherwise, processing begins with an empty set of test
+        platforms.
+        '''
+
+        # Final results which we will return.
+        tests = []
+
+        cur_test = {}
+        token = ''
+        in_platforms = False
+
+        def normalize_platforms():
+            if 'platforms' not in cur_test:
+                return
+            # if the first spec is a negation, start with all platforms
+            if cur_test['platforms'][0][0] == '-':
+                platforms = all_platforms.copy()
+            else:
+                platforms = []
+            for platform in cur_test['platforms']:
+                if platform[0] == '-':
+                    platforms = [p for p in platforms if p != platform[1:]]
+                else:
+                    platforms.append(platform)
+            cur_test['platforms'] = platforms
+
+        def add_test(value):
+            normalize_platforms()
+            cur_test['test'] = value.strip()
+            tests.insert(0, cur_test)
+
+        def add_platform(value):
+            platform = value.strip()
+            if platform[0] == '-':
+                negated = True
+                platform = platform[1:]
+            else:
+                negated = False
+            platforms = UNITTEST_PLATFORM_PRETTY_NAMES.get(platform, [platform])
+            if negated:
+                platforms = ["-" + p for p in platforms]
+            cur_test['platforms'] = platforms + cur_test.get('platforms', [])
+
+        # This might be somewhat confusing but we parse the string _backwards_ so
+        # there is no ambiguity over what state we are in.
+        for char in reversed(input_str):
+
+            # , indicates exiting a state
+            if char == ',':
+
+                # Exit a particular platform.
+                if in_platforms:
+                    add_platform(token)
+
+                # Exit a particular test.
+                else:
+                    add_test(token)
+                    cur_test = {}
+
+                # Token must always be reset after we exit a state
+                token = ''
+            elif char == '[':
+                # Exiting platform state entering test state.
+                add_platform(token)
+                token = ''
+                in_platforms = False
+            elif char == ']':
+                # Entering platform state.
+                in_platforms = True
+            else:
+                # Accumulator.
+                token = char + token
+
+        # Handle any left over tokens.
+        if token:
+            add_test(token)
+
+        return tests
+
+    def handle_alias(self, test, all_tests):
+        '''
+        Expand a test if its name refers to an alias, returning a list of test
+        dictionaries cloned from the first (to maintain any metadata).
+        '''
+        if test['test'] not in UNITTEST_ALIASES:
+            return [test]
+
+        alias = UNITTEST_ALIASES[test['test']]
+        def mktest(name):
+            newtest = copy.deepcopy(test)
+            newtest['test'] = name
+            return newtest
+
+        def exprmatch(alias):
+            return [t for t in all_tests if alias(t)]
+
+        return [mktest(t) for t in exprmatch(alias)]
+
+
+    def parse_test_chunks(self, all_tests, tests):
+        '''
+        Test flags may include parameters to narrow down the number of chunks in a
+        given push. We don't model 1 chunk = 1 job in taskcluster so we must check
+        each test flag to see if it is actually specifying a chunk.
+        '''
+        results = []
+        seen_chunks = {}
+        for test in tests:
+            matches = TEST_CHUNK_SUFFIX.match(test['test'])
+
+            if not matches:
+                results.extend(self.handle_alias(test, all_tests))
+                continue
+
+            name = matches.group(1)
+            chunk = matches.group(2)
+            test['test'] = name
+
+            for test in self.handle_alias(test, all_tests):
+                name = test['test']
+                if name in seen_chunks:
+                    seen_chunks[name].add(chunk)
+                else:
+                    seen_chunks[name] = {chunk}
+                    test['test'] = name
+                    test['only_chunks'] = seen_chunks[name]
+                    results.append(test)
+
+        # uniquify the results over the test names
+        results = {test['test']: test for test in results}.values()
+        return results
+
+    def find_all_attribute_suffixes(self, graph, prefix):
+        rv = set()
+        for t in graph.tasks.itervalues():
+            for a in t.attributes:
+                if a.startswith(prefix):
+                    rv.add(a[len(prefix):])
+        return sorted(rv)
+
+    def escape_whitespace_in_brackets(self, input_str):
+        '''
+        In tests you may restrict them by platform [] inside of the brackets
+        whitespace may occur this is typically invalid shell syntax so we escape it
+        with backslash sequences    .
+        '''
+        result = ""
+        in_brackets = False
+        for char in input_str:
+            if char == '[':
+                in_brackets = True
+                result += char
+                continue
+
+            if char == ']':
+                in_brackets = False
+                result += char
+                continue
+
+            if char == ' ' and in_brackets:
+                result += '\ '
+                continue
+
+            result += char
+
+        return result
+
+    def task_matches(self, attributes):
+        attr = attributes.get
+        if attr('kind') == 'legacy':
+            if attr('legacy_kind') in ('build', 'post_build'):
+                if attr('build_type') not in self.build_types:
+                    return False
+                if self.platforms is not None:
+                    if attr('build_platform') not in self.platforms:
+                        return False
+                return True
+            elif attr('legacy_kind') == 'job':
+                if self.jobs is not None:
+                    if attr('job') not in self.jobs:
+                        return False
+                return True
+            elif attr('legacy_kind') == 'unittest':
+                if attr('build_type') not in self.build_types:
+                    return False
+                if self.platforms is not None:
+                    if attr('build_platform') not in self.platforms:
+                        return False
+                if self.unittests is not None:
+                    # TODO: optimize this search a bit
+                    for ut in self.unittests:
+                        if attr('unittest_try_name') == ut['test']:
+                            break
+                    else:
+                        return False
+                    if 'platforms' in ut and attr('test_platform') not in ut['platforms']:
+                        return False
+                    if 'only_chunks' in ut and attr('test_chunk') not in ut['only_chunks']:
+                        return False
+                    return True
+                return True
+            return False
+        else:
+            # TODO: match other kinds
+            return False
+
+    def __str__(self):
+        def none_for_all(list):
+            if list is None:
+                return '<all>'
+            return ', '.join(str (e) for e in list)
+
+        return "\n".join([
+            "build_types: " + ", ".join(self.build_types),
+            "platforms: " + none_for_all(self.platforms),
+            "unittests: " + none_for_all(self.unittests),
+            "jobs: " + none_for_all(self.jobs),
+            "trigger_tests: " + str(self.trigger_tests),
+            "interactive: " + str(self.interactive),
+        ])
+
new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/types.py
@@ -0,0 +1,69 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+class Task(object):
+    """
+    Representation of a task in a TaskGraph.
+
+    Each has, at creation:
+
+    - kind: Kind instance that created this task
+    - label; the label for this task
+    - attributes: a dictionary of attributes for this task (used for filtering)
+    - task: the task definition (JSON-able dictionary)
+    - extra: extra kind-specific metadata
+
+    And later, as the task-graph processing proceeds:
+
+    - optimization_key -- key for finding equivalent tasks in the TC index
+    - task_id -- TC taskId under which this task will be created
+    """
+
+    def __init__(self, kind, label, attributes=None, task=None, **extra):
+        self.kind = kind
+        self.label = label
+        self.attributes = attributes or {}
+        self.task = task or {}
+        self.extra = extra
+
+        self.optimization_key = None
+        self.task_id = None
+
+        if not (all(isinstance(x, basestring) for x in self.attributes.iterkeys()) and
+                all(isinstance(x, basestring) for x in self.attributes.itervalues())):
+            raise TypeError("attribute names and values must be strings")
+
+    def __str__(self):
+        return "{} ({})".format(self.task_id or self.label,
+                                self.task['metadata']['description'].strip())
+
+
+class TaskGraph(object):
+    """
+    Representation of a task graph.
+
+    A task graph is a combination of a Graph and a dictionary of tasks indexed
+    by label.  TaskGraph instances should be treated as immutable.
+    """
+
+    def __init__(self, tasks, graph):
+        assert set(tasks) == graph.nodes
+        self.tasks = tasks
+        self.graph = graph
+
+    def __getitem__(self, label):
+        "Get a task by label"
+        return self.tasks[label]
+
+    def __iter__(self):
+        "Iterate over tasks in undefined order"
+        return self.tasks.itervalues()
+
+    def __repr__(self):
+        return "<TaskGraph graph={!r} tasks={!r}>".format(self.graph, self.tasks)
+
+    def __eq__(self, other):
+        return self.tasks == other.tasks and self.graph == other.graph
deleted file mode 100644
--- a/testing/moz.build
+++ /dev/null
@@ -1,7 +0,0 @@
-# -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
-# vim: set filetype=python:
-# This Source Code Form is subject to the terms of the Mozilla Public
-# License, v. 2.0. If a copy of the MPL was not distributed with this
-# file, You can obtain one at http://mozilla.org/MPL/2.0/.
-
-SPHINX_TREES['taskcluster'] = 'taskcluster/docs'
\ No newline at end of file
--- a/testing/taskcluster/taskcluster_graph/commit_parser.py
+++ b/testing/taskcluster/taskcluster_graph/commit_parser.py
@@ -1,16 +1,15 @@
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this file,
 # You can obtain one at http://mozilla.org/MPL/2.0/.
 
 
 import argparse
 import copy
-import functools
 import re
 import shlex
 from try_test_parser import parse_test_opts
 
 TRY_DELIMITER = 'try:'
 TEST_CHUNK_SUFFIX = re.compile('(.*)-([0-9]+)$')
 
 # The build type aliases are very cryptic and only used in try flags these are
@@ -148,17 +147,17 @@ def parse_test_chunks(aliases, all_tests
         chunk = int(matches.group(2))
         test['test'] = name
 
         for test in handle_alias(test, aliases, all_tests):
             name = test['test']
             if name in seen_chunks:
                 seen_chunks[name].add(chunk)
             else:
-                seen_chunks[name] = set([chunk])
+                seen_chunks[name] = {chunk}
                 test['test'] = name
                 test['only_chunks'] = seen_chunks[name]
                 results.append(test)
 
     # uniquify the results over the test names
     results = {test['test']: test for test in results}.values()
     return results
 
@@ -202,18 +201,21 @@ def extract_tests_from_platform(test_job
                 continue
 
         # Add the job to the list and ensure to copy it so we don't accidentally
         # mutate the state of the test job in the future...
         specific_test_job = copy.deepcopy(test_job)
 
         # Update the task configuration for all tests in the matrix...
         for build_name in specific_test_job:
+            # NOTE: build_name is always "allowed_build_tasks"
             for test_task_name in specific_test_job[build_name]:
+                # NOTE: test_task_name is always "task"
                 test_task = specific_test_job[build_name][test_task_name]
+                test_task['unittest_try_name'] = test_entry['test']
                 # Copy over the chunk restrictions if given...
                 if 'only_chunks' in test_entry:
                     test_task['only_chunks'] = \
                             copy.copy(test_entry['only_chunks'])
 
         results.append(specific_test_job)
 
     return results
@@ -302,17 +304,19 @@ def parse_commit(message, jobs):
 
             # Generate list of post build tasks that run on this build
             post_build_jobs = []
             for job_flag in jobs['flags'].get('post-build', []):
                 job = jobs['post-build'][job_flag]
                 if ('allowed_build_tasks' in job and
                         build_task not in job['allowed_build_tasks']):
                     continue
-                post_build_jobs.append(copy.deepcopy(job))
+                job = copy.deepcopy(job)
+                job['job_flag'] = job_flag
+                post_build_jobs.append(job)
 
             # Node for this particular build type
             result.append({
                 'task': build_task,
                 'post-build': post_build_jobs,
                 'dependents': extract_tests_from_platform(
                     jobs['tests'], platform_builds, build_task, tests
                 ),
@@ -350,16 +354,17 @@ def parse_commit(message, jobs):
         result.append({
             'task': task['task'],
             'post-build': [],
             'dependents': [],
             'additional-parameters': task.get('additional-parameters', {}),
             'build_name': name,
             # TODO support declaring a different build type
             'build_type': name,
+            'is_job': True,
             'interactive': args.interactive,
             'when': task.get('when', {})
         })
 
     # Times that test jobs will be scheduled
     trigger_tests = args.trigger_tests
 
     return result, trigger_tests
--- a/testing/taskcluster/tasks/branches/base_jobs.yml
+++ b/testing/taskcluster/tasks/branches/base_jobs.yml
@@ -42,17 +42,17 @@ builds:
     types:
       opt:
         task: tasks/builds/opt_linux32.yml
       debug:
         task: tasks/builds/dbg_linux32.yml
   linux64:
     platforms:
       - Linux64
-    extra-builds:
+    extra-builds:  # see RIDEALONG_BUILDS in `mach taskgraph`
       - sm-plain
       - sm-arm-sim
       - sm-compacting
       - sm-rootanalysis
     types:
       opt:
         task: tasks/builds/opt_linux64.yml
       debug: