diff --git a/bazel/aquery_test.go b/bazel/aquery_test.go
index 68e50c2..2328411 100644
--- a/bazel/aquery_test.go
+++ b/bazel/aquery_test.go
@@ -223,7 +223,7 @@
     "parentId": 13
   }]
 }`
-	actualbuildStatements, _ := AqueryBuildStatements([]byte(inputString))
+	actualbuildStatements, actualDepsets, _ := AqueryBuildStatements([]byte(inputString))
 	expectedBuildStatements := []BuildStatement{}
 	for _, arch := range []string{"arm", "arm64", "x86", "x86_64"} {
 		expectedBuildStatements = append(expectedBuildStatements,
@@ -234,11 +234,7 @@
 				OutputPaths: []string{
 					fmt.Sprintf("bazel-out/sourceroot/k8-fastbuild/bin/bionic/libc/syscalls-%s.S", arch),
 				},
-				InputPaths: []string{
-					"../sourceroot/bionic/libc/SYSCALLS.TXT",
-					"../sourceroot/bionic/libc/tools/gensyscalls.py",
-					"../bazel_tools/tools/genrule/genrule-setup.sh",
-				},
+				InputDepsetIds: []int{1},
 				Env: []KeyValuePair{
 					KeyValuePair{Key: "PATH", Value: "/bin:/usr/bin:/usr/local/bin"},
 				},
@@ -246,6 +242,16 @@
 			})
 	}
 	assertBuildStatements(t, expectedBuildStatements, actualbuildStatements)
+
+	expectedFlattenedInputs := []string{
+		"../sourceroot/bionic/libc/SYSCALLS.TXT",
+		"../sourceroot/bionic/libc/tools/gensyscalls.py",
+		"../bazel_tools/tools/genrule/genrule-setup.sh",
+	}
+	actualFlattenedInputs := flattenDepsets([]int{1}, actualDepsets)
+	if !reflect.DeepEqual(actualFlattenedInputs, expectedFlattenedInputs) {
+		t.Errorf("Expected flattened inputs %v, but got %v", expectedFlattenedInputs, actualFlattenedInputs)
+	}
 }
 
 func TestInvalidOutputId(t *testing.T) {
@@ -280,11 +286,11 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, "undefined outputId 3")
 }
 
-func TestInvalidInputDepsetId(t *testing.T) {
+func TestInvalidInputDepsetIdFromAction(t *testing.T) {
 	const inputString = `
 {
   "artifacts": [{
@@ -316,10 +322,47 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, "undefined input depsetId 2")
 }
 
+func TestInvalidInputDepsetIdFromDepset(t *testing.T) {
+	const inputString = `
+{
+  "artifacts": [{
+    "id": 1,
+    "pathFragmentId": 1
+  }, {
+    "id": 2,
+    "pathFragmentId": 2
+  }],
+  "actions": [{
+    "targetId": 1,
+    "actionKey": "x",
+    "mnemonic": "x",
+    "arguments": ["touch", "foo"],
+    "inputDepSetIds": [1],
+    "outputIds": [1],
+    "primaryOutputId": 1
+  }],
+  "depSetOfFiles": [{
+    "id": 1,
+    "directArtifactIds": [1, 2],
+    "transitiveDepSetIds": [42]
+  }],
+  "pathFragments": [{
+    "id": 1,
+    "label": "one"
+  }, {
+    "id": 2,
+    "label": "two"
+  }]
+}`
+
+	_, _, err := AqueryBuildStatements([]byte(inputString))
+	assertError(t, err, "undefined input depsetId 42 (referenced by depsetId 1)")
+}
+
 func TestInvalidInputArtifactId(t *testing.T) {
 	const inputString = `
 {
@@ -352,7 +395,7 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, "undefined input artifactId 3")
 }
 
@@ -389,7 +432,7 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, "undefined path fragment id 3")
 }
 
@@ -431,7 +474,7 @@
   }]
 }`
 
-	actual, err := AqueryBuildStatements([]byte(inputString))
+	actual, _, err := AqueryBuildStatements([]byte(inputString))
 	if err != nil {
 		t.Errorf("Unexpected error %q", err)
 	}
@@ -492,7 +535,7 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, `found multiple potential depfiles "two.d", "other.d"`)
 }
 
@@ -699,23 +742,31 @@
   }]
 }`
 
-	actualbuildStatements, _ := AqueryBuildStatements([]byte(inputString))
-	// Inputs for the action are test_{i} from 1 to 20, and test_root. These inputs
-	// are given via a deep depset, but the depset is flattened when returned as a
-	// BuildStatement slice.
-	inputPaths := []string{"bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_root"}
-	for i := 1; i < 20; i++ {
-		inputPaths = append(inputPaths, fmt.Sprintf("bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_%d", i))
-	}
+	actualbuildStatements, actualDepsets, _ := AqueryBuildStatements([]byte(inputString))
+
 	expectedBuildStatements := []BuildStatement{
 		BuildStatement{
-			Command:     "/bin/bash -c 'touch bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_out'",
-			OutputPaths: []string{"bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_out"},
-			InputPaths:  inputPaths,
-			Mnemonic:    "Action",
+			Command:        "/bin/bash -c 'touch bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_out'",
+			OutputPaths:    []string{"bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_out"},
+			InputDepsetIds: []int{1},
+			Mnemonic:       "Action",
 		},
 	}
 	assertBuildStatements(t, expectedBuildStatements, actualbuildStatements)
+
+	// Inputs for the action are test_{i} from 1 to 20, and test_root. These inputs
+	// are given via a deep depset, but the depset is flattened when returned as a
+	// BuildStatement slice.
+	expectedFlattenedInputs := []string{}
+	for i := 1; i < 20; i++ {
+		expectedFlattenedInputs = append(expectedFlattenedInputs, fmt.Sprintf("bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_%d", i))
+	}
+	expectedFlattenedInputs = append(expectedFlattenedInputs, "bazel-out/sourceroot/k8-fastbuild/bin/testpkg/test_root")
+
+	actualFlattenedInputs := flattenDepsets([]int{1}, actualDepsets)
+	if !reflect.DeepEqual(actualFlattenedInputs, expectedFlattenedInputs) {
+		t.Errorf("Expected flattened inputs %v, but got %v", expectedFlattenedInputs, actualFlattenedInputs)
+	}
 }
 
 func TestMiddlemenAction(t *testing.T) {
@@ -785,24 +836,74 @@
   }]
 }`
 
-	actual, err := AqueryBuildStatements([]byte(inputString))
+	actualBuildStatements, actualDepsets, err := AqueryBuildStatements([]byte(inputString))
 	if err != nil {
 		t.Errorf("Unexpected error %q", err)
 	}
-	if expected := 1; len(actual) != expected {
-		t.Fatalf("Expected %d build statements, got %d", expected, len(actual))
+	if expected := 1; len(actualBuildStatements) != expected {
+		t.Fatalf("Expected %d build statements, got %d", expected, len(actualBuildStatements))
 	}
 
-	bs := actual[0]
-	expectedInputs := []string{"middleinput_one", "middleinput_two", "maininput_one", "maininput_two"}
-	if !reflect.DeepEqual(bs.InputPaths, expectedInputs) {
-		t.Errorf("Expected main action inputs %q, but got %q", expectedInputs, bs.InputPaths)
+	bs := actualBuildStatements[0]
+	if len(bs.InputPaths) > 0 {
+		t.Errorf("Expected main action raw inputs to be empty, but got %q", bs.InputPaths)
+	}
+
+	expectedInputDepsets := []int{2}
+	if !reflect.DeepEqual(bs.InputDepsetIds, expectedInputDepsets) {
+		t.Errorf("Expected main action depset IDs %v, but got %v", expectedInputDepsets, bs.InputDepsetIds)
 	}
 
 	expectedOutputs := []string{"output"}
 	if !reflect.DeepEqual(bs.OutputPaths, expectedOutputs) {
 		t.Errorf("Expected main action outputs %q, but got %q", expectedOutputs, bs.OutputPaths)
 	}
+
+	expectedAllDepsets := []AqueryDepset{
+		{
+			Id:              1,
+			DirectArtifacts: []string{"middleinput_one", "middleinput_two"},
+		},
+		{
+			Id:                  2,
+			DirectArtifacts:     []string{"maininput_one", "maininput_two"},
+			TransitiveDepSetIds: []int{1},
+		},
+	}
+	if !reflect.DeepEqual(actualDepsets, expectedAllDepsets) {
+		t.Errorf("Expected depsets %v, but got %v", expectedAllDepsets, actualDepsets)
+	}
+
+	expectedFlattenedInputs := []string{"middleinput_one", "middleinput_two", "maininput_one", "maininput_two"}
+	actualFlattenedInputs := flattenDepsets(bs.InputDepsetIds, actualDepsets)
+
+	if !reflect.DeepEqual(actualFlattenedInputs, expectedFlattenedInputs) {
+		t.Errorf("Expected flattened inputs %v, but got %v", expectedFlattenedInputs, actualFlattenedInputs)
+	}
+}
+
+// Returns the contents of given depsets in concatenated post order.
+func flattenDepsets(depsetIdsToFlatten []int, allDepsets []AqueryDepset) []string {
+	depsetsById := map[int]AqueryDepset{}
+	for _, depset := range allDepsets {
+		depsetsById[depset.Id] = depset
+	}
+	result := []string{}
+	for _, depsetId := range depsetIdsToFlatten {
+		result = append(result, flattenDepset(depsetId, depsetsById)...)
+	}
+	return result
+}
+
+// Returns the contents of a given depset in post order.
+func flattenDepset(depsetIdToFlatten int, allDepsets map[int]AqueryDepset) []string {
+	depset := allDepsets[depsetIdToFlatten]
+	result := []string{}
+	for _, depsetId := range depset.TransitiveDepSetIds {
+		result = append(result, flattenDepset(depsetId, allDepsets)...)
+	}
+	result = append(result, depset.DirectArtifacts...)
+	return result
 }
 
 func TestSimpleSymlink(t *testing.T) {
@@ -849,7 +950,7 @@
   }]
 }`
 
-	actual, err := AqueryBuildStatements([]byte(inputString))
+	actual, _, err := AqueryBuildStatements([]byte(inputString))
 
 	if err != nil {
 		t.Errorf("Unexpected error %q", err)
@@ -913,7 +1014,7 @@
   }]
 }`
 
-	actual, err := AqueryBuildStatements([]byte(inputString))
+	actual, _, err := AqueryBuildStatements([]byte(inputString))
 
 	if err != nil {
 		t.Errorf("Unexpected error %q", err)
@@ -970,7 +1071,7 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, `Expect 1 input and 1 output to symlink action, got: input ["file" "other_file"], output ["symlink"]`)
 }
 
@@ -1011,7 +1112,7 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, `Expect 1 input and 1 output to symlink action, got: input ["file"], output ["symlink" "other_symlink"]`)
 }
 
@@ -1045,7 +1146,7 @@
   }]
 }`
 
-	actual, err := AqueryBuildStatements([]byte(inputString))
+	actual, _, err := AqueryBuildStatements([]byte(inputString))
 
 	if err != nil {
 		t.Errorf("Unexpected error %q", err)
@@ -1091,7 +1192,7 @@
   }]
 }`
 
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, `Expect 1 output to template expand action, got: output []`)
 }
 
@@ -1211,7 +1312,7 @@
     "label": "python_binary"
   }]
 }`
-	actual, err := AqueryBuildStatements([]byte(inputString))
+	actual, _, err := AqueryBuildStatements([]byte(inputString))
 
 	if err != nil {
 		t.Errorf("Unexpected error %q", err)
@@ -1264,7 +1365,7 @@
     "label": "python_binary.zip"
   }]
 }`
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, `Expect 1+ input and 1 output to python zipper action, got: input [], output ["python_binary.zip"]`)
 }
 
@@ -1360,7 +1461,7 @@
     "parentId": 11
   }]
 }`
-	_, err := AqueryBuildStatements([]byte(inputString))
+	_, _, err := AqueryBuildStatements([]byte(inputString))
 	assertError(t, err, `Expect 1+ input and 1 output to python zipper action, got: input ["../bazel_tools/tools/zip/zipper/zipper" "python_binary.py"], output []`)
 }