--- a/tools/tryselect/selectors/fuzzy.py
+++ b/tools/tryselect/selectors/fuzzy.py
@@ -9,17 +9,17 @@ import platform
 import subprocess
 import sys
 from distutils.spawn import find_executable
 
 from mozboot.util import get_state_dir
 
 from .. import preset as pset
 from ..cli import BaseTryParser
-from ..tasks import generate_tasks
+from ..tasks import get_taskgraph
 from ..vcs import VCSHelper
 
 try:
     import blessings
     terminal = blessings.Terminal()
 except ImportError:
     from mozlint.formatters.stylish import NullTerminal
     terminal = NullTerminal()
@@ -193,17 +193,18 @@ def run_fuzzy_try(update=False, query=No
 
     if not fzf:
         print(FZF_NOT_FOUND)
         return
 
     vcs = VCSHelper.create()
     vcs.check_working_directory(push)
 
-    all_tasks = generate_tasks(parameters, full)
+    tg = get_taskgraph(parameters, full)
+    all_tasks = [label for label in tg.graph.visit_postorder()]
 
     key_shortcuts = [k + ':' + v for k, v in fzf_shortcuts.iteritems()]
     cmd = [
         fzf, '-m',
         '--bind', ','.join(key_shortcuts),
         '--header', format_header(),
         # Using python to split the preview string is a bit convoluted,
         # but is guaranteed to be available on all platforms.

--- a/tools/tryselect/tasks.py
+++ b/tools/tryselect/tasks.py
@@ -1,26 +1,28 @@
 # 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 os
 import sys
 
 from mozboot.util import get_state_dir
 from mozbuild.base import MozbuildObject
 from mozpack.files import FileFinder
 
 from taskgraph.generator import TaskGraphGenerator
 from taskgraph.parameters import (
     ParameterMismatch,
     load_parameters_file,
 )
+from taskgraph.taskgraph import TaskGraph
 
 here = os.path.abspath(os.path.dirname(__file__))
 build = MozbuildObject.from_environment(cwd=here)
 
 
 PARAMETER_MISMATCH = """
 ERROR - The parameters being used to generate tasks differ from those defined
 in your working copy:
@@ -40,27 +42,26 @@ def invalidate(cache):
     tc_dir = os.path.join(build.topsrcdir, 'taskcluster')
     tmod = max(os.path.getmtime(os.path.join(tc_dir, p)) for p, _ in FileFinder(tc_dir))
     cmod = os.path.getmtime(cache)
 
     if tmod > cmod:
         os.remove(cache)
 
 
-def generate_tasks(params=None, full=False):
+def get_taskgraph(params=None, full=False):
     params = params or "project=mozilla-central"
-
     cache_dir = os.path.join(get_state_dir()[0], 'cache', 'taskgraph')
-    attr = 'full_task_set' if full else 'target_task_set'
+    attr = 'full_task_graph' if full else 'target_task_graph'
     cache = os.path.join(cache_dir, attr)
 
     invalidate(cache)
     if os.path.isfile(cache):
         with open(cache, 'r') as fh:
-            return fh.read().splitlines()
+            return TaskGraph.from_json(json.load(fh))[1]
 
     if not os.path.isdir(cache_dir):
         os.makedirs(cache_dir)
 
     print("Task configuration changed, generating {}".format(attr.replace('_', ' ')))
     try:
         params = load_parameters_file(params, strict=False)
         params.check()
@@ -68,15 +69,14 @@ def generate_tasks(params=None, full=Fal
         print(PARAMETER_MISMATCH.format(e.args[0]))
         sys.exit(1)
 
     cwd = os.getcwd()
     os.chdir(build.topsrcdir)
 
     root = os.path.join(build.topsrcdir, 'taskcluster', 'ci')
     tg = getattr(TaskGraphGenerator(root_dir=root, parameters=params), attr)
-    labels = [label for label in tg.graph.visit_postorder()]
 
     os.chdir(cwd)
 
     with open(cache, 'w') as fh:
-        fh.write('\n'.join(labels))
-    return labels
+        json.dump(tg.to_json(), fh)
+    return tg

--- a/tools/tryselect/test/setup.sh
+++ b/tools/tryselect/test/setup.sh
@@ -5,26 +5,86 @@ export MACHRC=$TMP/machrc
 cat > $MACHRC << EOF
 [try]
 default=syntax
 EOF
 
 cachedir=$MOZBUILD_STATE_PATH/cache/taskgraph
 mkdir -p $cachedir
 
-cat > $cachedir/target_task_set << EOF
-test/foo-opt
-test/foo-debug
-build-baz
+cat > $cachedir/target_task_graph << EOF
+{
+    "test/foo-opt": {
+        "kind": "test",
+        "label": "test/foo-opt",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    },
+    "test/foo-debug": {
+        "kind": "test",
+        "label": "test/foo-debug",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    },
+    "build-baz": {
+        "kind": "build",
+        "label": "build-baz",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    }
+}
 EOF
 
-cat > $cachedir/full_task_set << EOF
-test/foo-opt
-test/foo-debug
-test/bar-opt
-test/bar-debug
-build-baz
+cat > $cachedir/full_task_graph << EOF
+{
+    "test/foo-opt": {
+        "kind": "test",
+        "label": "test/foo-opt",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    },
+    "test/foo-debug": {
+        "kind": "test",
+        "label": "test/foo-debug",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    },
+    "test/bar-opt": {
+        "kind": "test",
+        "label": "test/bar-opt",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    },
+    "test/bar-debug": {
+        "kind": "test",
+        "label": "test/bar-debug",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    },
+    "build-baz": {
+        "kind": "build",
+        "label": "build-baz",
+        "task": {},
+        "attributes": {},
+        "dependencies": {},
+        "optimization": {}
+    }
+}
 EOF
 
 # set mtime to the future so we don't re-generate tasks
 find $cachedir -type f -exec touch -d "next day" {} +
 
 export testargs="--no-push --no-artifact"