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 297716 c3e24e94ab5148ad92a3f137d6cab9d8bebdd6a7
parent 297715 997ae5a6386621b88513bf5322cd4c82a63862bb
child 297717 c17e66a20cb3e167420df885f94c6c010d1f6089
push id19263
push userkwierso@gmail.com
push dateTue, 17 May 2016 21:18:17 +0000
treeherderfx-team@67eb2faeb2ab [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgps
bugs1258497
milestone49.0a1
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: