diff --git a/androidmk/Android.bp b/androidmk/Android.bp
index 442452f..1d939b0 100644
--- a/androidmk/Android.bp
+++ b/androidmk/Android.bp
@@ -44,6 +44,6 @@
     ],
     testSrcs: [
         "parser/make_strings_test.go",
+        "parser/parser_test.go",
     ],
 }
-
diff --git a/androidmk/parser/make_strings.go b/androidmk/parser/make_strings.go
index e6885a8..4b782a2 100644
--- a/androidmk/parser/make_strings.go
+++ b/androidmk/parser/make_strings.go
@@ -90,10 +90,10 @@
 	if len(ms.Strings) == 0 {
 		return ""
 	} else {
-		ret := ms.Strings[0]
+		ret := unescape(ms.Strings[0])
 		for i := range ms.Strings[1:] {
 			ret += ms.Variables[i].Value(scope)
-			ret += ms.Strings[i+1]
+			ret += unescape(ms.Strings[i+1])
 		}
 		return ret
 	}
@@ -125,6 +125,16 @@
 }
 
 func (ms *MakeString) SplitN(sep string, n int) []*MakeString {
+	return ms.splitNFunc(n, func(s string, n int) []string {
+		return splitAnyN(s, sep, n)
+	})
+}
+
+func (ms *MakeString) Words() []*MakeString {
+	return ms.splitNFunc(-1, splitWords)
+}
+
+func (ms *MakeString) splitNFunc(n int, splitFunc func(s string, n int) []string) []*MakeString {
 	ret := []*MakeString{}
 
 	curMs := SimpleMakeString("", ms.Pos())
@@ -133,7 +143,7 @@
 	var s string
 	for i, s = range ms.Strings {
 		if n != 0 {
-			split := splitAnyN(s, sep, n)
+			split := splitFunc(s, n)
 			if n != -1 {
 				if len(split) > n {
 					panic("oops!")
@@ -156,7 +166,9 @@
 		}
 	}
 
-	ret = append(ret, curMs)
+	if !curMs.Empty() {
+		ret = append(ret, curMs)
+	}
 	return ret
 }
 
@@ -206,3 +218,64 @@
 	ret = append(ret, s)
 	return ret
 }
+
+func splitWords(s string, n int) []string {
+	ret := []string{}
+	preserve := ""
+	for n == -1 || n > 1 {
+		index := strings.IndexAny(s, " \t")
+		if index == 0 && len(preserve) == 0 {
+			s = s[1:]
+		} else if index >= 0 {
+			escapeCount := 0
+			for i := index - 1; i >= 0; i-- {
+				if s[i] != '\\' {
+					break
+				}
+				escapeCount += 1
+			}
+
+			if escapeCount%2 == 1 {
+				preserve += s[0 : index+1]
+				s = s[index+1:]
+				continue
+			}
+
+			ret = append(ret, preserve+s[0:index])
+			s = s[index+1:]
+			preserve = ""
+			if n > 0 {
+				n--
+			}
+		} else {
+			break
+		}
+	}
+	if preserve != "" || s != "" || len(ret) == 0 {
+		ret = append(ret, preserve+s)
+	}
+	return ret
+}
+
+func unescape(s string) string {
+	ret := ""
+	for {
+		index := strings.IndexByte(s, '\\')
+		if index < 0 {
+			break
+		}
+
+		if index+1 == len(s) {
+			break
+		}
+
+		switch s[index+1] {
+		case ' ', '\\', '#', ':', '*', '[', '|', '\t', '\n', '\r':
+			ret += s[:index] + s[index+1:index+2]
+		default:
+			ret += s[:index+2]
+		}
+		s = s[index+2:]
+	}
+	return ret + s
+}
diff --git a/androidmk/parser/make_strings_test.go b/androidmk/parser/make_strings_test.go
index 8ad3d74..6995e89 100644
--- a/androidmk/parser/make_strings_test.go
+++ b/androidmk/parser/make_strings_test.go
@@ -99,6 +99,78 @@
 	}
 }
 
+var valueTestCases = []struct {
+	in       *MakeString
+	expected string
+}{
+	{
+		in:       SimpleMakeString("a b", NoPos),
+		expected: "a b",
+	},
+	{
+		in:       SimpleMakeString("a\\ \\\tb\\\\", NoPos),
+		expected: "a \tb\\",
+	},
+	{
+		in:       SimpleMakeString("a\\b\\", NoPos),
+		expected: "a\\b\\",
+	},
+}
+
+func TestMakeStringValue(t *testing.T) {
+	for _, test := range valueTestCases {
+		got := test.in.Value(nil)
+		if got != test.expected {
+			t.Errorf("\nwith: %q\nwant: %q\n got: %q", test.in.Dump(), test.expected, got)
+		}
+	}
+}
+
+var splitWordsTestCases = []struct {
+	in       *MakeString
+	expected []*MakeString
+}{
+	{
+		in:       SimpleMakeString("", NoPos),
+		expected: []*MakeString{},
+	},
+	{
+		in: SimpleMakeString(" a b\\ c d", NoPos),
+		expected: []*MakeString{
+			SimpleMakeString("a", NoPos),
+			SimpleMakeString("b\\ c", NoPos),
+			SimpleMakeString("d", NoPos),
+		},
+	},
+	{
+		in: SimpleMakeString("  a\tb\\\t\\ c d  ", NoPos),
+		expected: []*MakeString{
+			SimpleMakeString("a", NoPos),
+			SimpleMakeString("b\\\t\\ c", NoPos),
+			SimpleMakeString("d", NoPos),
+		},
+	},
+	{
+		in: SimpleMakeString(`a\\ b\\\ c d`, NoPos),
+		expected: []*MakeString{
+			SimpleMakeString(`a\\`, NoPos),
+			SimpleMakeString(`b\\\ c`, NoPos),
+			SimpleMakeString("d", NoPos),
+		},
+	},
+}
+
+func TestMakeStringWords(t *testing.T) {
+	for _, test := range splitWordsTestCases {
+		got := test.in.Words()
+		gotString := dumpArray(got)
+		expectedString := dumpArray(test.expected)
+		if gotString != expectedString {
+			t.Errorf("with:\n%q\nexpected:\n%s\ngot:\n%s", test.in.Dump(), expectedString, gotString)
+		}
+	}
+}
+
 func dumpArray(a []*MakeString) string {
 	ret := make([]string, len(a))
 
diff --git a/androidmk/parser/parser.go b/androidmk/parser/parser.go
index 89ee308..89c1af9 100644
--- a/androidmk/parser/parser.go
+++ b/androidmk/parser/parser.go
@@ -35,6 +35,10 @@
 	return fmt.Sprintf("%s: %s", e.Pos, e.Err)
 }
 
+const builtinDollar = "__builtin_dollar"
+
+var builtinDollarName = SimpleMakeString(builtinDollar, NoPos)
+
 func (p *parser) Parse() ([]Node, []error) {
 	defer func() {
 		if r := recover(); r != nil {
@@ -326,7 +330,11 @@
 		case '$':
 			var variable Variable
 			variable = p.parseVariable()
-			value.appendVariable(variable)
+			if variable.Name == builtinDollarName {
+				value.appendString("$")
+			} else {
+				value.appendVariable(variable)
+			}
 		case scanner.EOF:
 			break loop
 		case '(':
@@ -357,7 +365,8 @@
 	case '{':
 		return p.parseBracketedVariable('{', '}', pos)
 	case '$':
-		name = SimpleMakeString("__builtin_dollar", NoPos)
+		name = builtinDollarName
+		p.accept(p.tok)
 	case scanner.EOF:
 		p.errorf("expected variable name, found %s",
 			scanner.TokenString(p.tok))
@@ -457,6 +466,8 @@
 	case '=':
 		p.parseAssignment("=", target, prerequisites)
 		return nil, true
+	case scanner.EOF:
+		// do nothing
 	default:
 		p.errorf("unexpected token %s after rule prerequisites", scanner.TokenString(p.tok))
 	}
diff --git a/androidmk/parser/parser_test.go b/androidmk/parser/parser_test.go
new file mode 100644
index 0000000..f562c29
--- /dev/null
+++ b/androidmk/parser/parser_test.go
@@ -0,0 +1,61 @@
+// Copyright 2018 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package parser
+
+import (
+	"bytes"
+	"testing"
+)
+
+var parserTestCases = []struct {
+	name string
+	in   string
+	out  []Node
+}{
+	{
+		name: "Escaped $",
+		in:   `a$$ b: c`,
+		out: []Node{
+			&Rule{
+				Target:        SimpleMakeString("a$ b", NoPos),
+				Prerequisites: SimpleMakeString("c", NoPos),
+			},
+		},
+	},
+}
+
+func TestParse(t *testing.T) {
+	for _, test := range parserTestCases {
+		t.Run(test.name, func(t *testing.T) {
+			p := NewParser(test.name, bytes.NewBufferString(test.in))
+			got, errs := p.Parse()
+
+			if len(errs) != 0 {
+				t.Fatalf("Unexpected errors while parsing: %v", errs)
+			}
+
+			if len(got) != len(test.out) {
+				t.Fatalf("length mismatch, expected %d nodes, got %d", len(test.out), len(got))
+			}
+
+			for i := range got {
+				if got[i].Dump() != test.out[i].Dump() {
+					t.Errorf("incorrect node %d:\nexpected: %#v (%s)\n     got: %#v (%s)",
+						i, test.out[i], test.out[i].Dump(), got[i], got[i].Dump())
+				}
+			}
+		})
+	}
+}
diff --git a/androidmk/parser/scope.go b/androidmk/parser/scope.go
index 7a514fa..167e470 100644
--- a/androidmk/parser/scope.go
+++ b/androidmk/parser/scope.go
@@ -71,7 +71,7 @@
 
 func init() {
 	builtinScope := make(map[string]string)
-	builtinScope["__builtin_dollar"] = "$"
+	builtinScope[builtinDollar] = "$"
 }
 
 func (v Variable) EvalFunction(scope Scope) (string, bool) {
diff --git a/bpfix/cmd/bpfix.go b/bpfix/cmd/bpfix.go
index 2fde383..ccdae16 100644
--- a/bpfix/cmd/bpfix.go
+++ b/bpfix/cmd/bpfix.go
@@ -65,7 +65,7 @@
 	if err != nil {
 		return err
 	}
-	r := bytes.NewBuffer(src)
+	r := bytes.NewBuffer(append([]byte(nil), src...))
 	file, errs := parser.Parse(filename, r, parser.NewScope(nil))
 	if len(errs) > 0 {
 		for _, err := range errs {
diff --git a/cc/proto.go b/cc/proto.go
index 22e50ab..6e6f95e 100644
--- a/cc/proto.go
+++ b/cc/proto.go
@@ -25,13 +25,17 @@
 
 func init() {
 	pctx.HostBinToolVariable("protocCmd", "aprotoc")
+	pctx.HostBinToolVariable("depFixCmd", "dep_fixer")
 }
 
 var (
 	proto = pctx.AndroidStaticRule("protoc",
 		blueprint.RuleParams{
-			Command:     "$protocCmd --cpp_out=$protoOutParams:$outDir -I $protoBase $protoFlags $in",
-			CommandDeps: []string{"$protocCmd"},
+			Command: "$protocCmd --cpp_out=$protoOutParams:$outDir --dependency_out=$out.d -I $protoBase $protoFlags $in && " +
+				`$depFixCmd $out.d`,
+			CommandDeps: []string{"$protocCmd", "$depFixCmd"},
+			Depfile:     "${out}.d",
+			Deps:        blueprint.DepsGCC,
 		}, "protoFlags", "protoOutParams", "protoBase", "outDir")
 )
 
@@ -53,10 +57,11 @@
 	}
 
 	ctx.Build(pctx, android.BuildParams{
-		Rule:        proto,
-		Description: "protoc " + protoFile.Rel(),
-		Outputs:     android.WritablePaths{ccFile, headerFile},
-		Input:       protoFile,
+		Rule:           proto,
+		Description:    "protoc " + protoFile.Rel(),
+		Output:         ccFile,
+		ImplicitOutput: headerFile,
+		Input:          protoFile,
 		Args: map[string]string{
 			"outDir":         android.ProtoDir(ctx).String(),
 			"protoFlags":     protoFlags,
diff --git a/cmd/dep_fixer/Android.bp b/cmd/dep_fixer/Android.bp
new file mode 100644
index 0000000..d2d1113
--- /dev/null
+++ b/cmd/dep_fixer/Android.bp
@@ -0,0 +1,23 @@
+// Copyright 2018 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+blueprint_go_binary {
+    name: "dep_fixer",
+    deps: ["androidmk-parser"],
+    srcs: [
+        "main.go",
+        "deps.go",
+    ],
+    testSrcs: ["deps_test.go"],
+}
diff --git a/cmd/dep_fixer/deps.go b/cmd/dep_fixer/deps.go
new file mode 100644
index 0000000..64c97f5
--- /dev/null
+++ b/cmd/dep_fixer/deps.go
@@ -0,0 +1,95 @@
+// Copyright 2018 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package main
+
+import (
+	"bytes"
+	"fmt"
+	"io"
+	"strings"
+
+	"android/soong/androidmk/parser"
+)
+
+type Deps struct {
+	Output string
+	Inputs []string
+}
+
+func Parse(filename string, r io.Reader) (*Deps, error) {
+	p := parser.NewParser(filename, r)
+	nodes, errs := p.Parse()
+
+	if len(errs) == 1 {
+		return nil, errs[0]
+	} else if len(errs) > 1 {
+		return nil, fmt.Errorf("many errors: %v", errs)
+	}
+
+	pos := func(node parser.Node) string {
+		return p.Unpack(node.Pos()).String() + ": "
+	}
+
+	ret := &Deps{}
+
+	for _, node := range nodes {
+		switch x := node.(type) {
+		case *parser.Comment:
+			// Do nothing
+		case *parser.Rule:
+			if x.Recipe != "" {
+				return nil, fmt.Errorf("%sunexpected recipe in rule: %v", pos(node), x)
+			}
+
+			if !x.Target.Const() {
+				return nil, fmt.Errorf("%sunsupported variable expansion: %v", pos(node), x.Target.Dump())
+			}
+			outputs := x.Target.Words()
+			if len(outputs) == 0 {
+				return nil, fmt.Errorf("%smissing output: %v", pos(node), x)
+			}
+			ret.Output = outputs[0].Value(nil)
+
+			if !x.Prerequisites.Const() {
+				return nil, fmt.Errorf("%sunsupported variable expansion: %v", pos(node), x.Prerequisites.Dump())
+			}
+			for _, input := range x.Prerequisites.Words() {
+				ret.Inputs = append(ret.Inputs, input.Value(nil))
+			}
+		default:
+			return nil, fmt.Errorf("%sunexpected line: %#v", pos(node), node)
+		}
+	}
+
+	return ret, nil
+}
+
+func (d *Deps) Print() []byte {
+	// We don't really have to escape every \, but it's simpler,
+	// and ninja will handle it.
+	replacer := strings.NewReplacer(" ", "\\ ",
+		":", "\\:",
+		"#", "\\#",
+		"$", "$$",
+		"\\", "\\\\")
+
+	b := &bytes.Buffer{}
+	fmt.Fprintf(b, "%s:", replacer.Replace(d.Output))
+	for _, input := range d.Inputs {
+		fmt.Fprintf(b, " %s", replacer.Replace(input))
+	}
+	fmt.Fprintln(b)
+	return b.Bytes()
+}
diff --git a/cmd/dep_fixer/deps_test.go b/cmd/dep_fixer/deps_test.go
new file mode 100644
index 0000000..0a779b7
--- /dev/null
+++ b/cmd/dep_fixer/deps_test.go
@@ -0,0 +1,389 @@
+// Copyright 2018 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package main
+
+import (
+	"bytes"
+	"io"
+	"io/ioutil"
+	"os"
+	"testing"
+)
+
+func TestParse(t *testing.T) {
+	testCases := []struct {
+		name   string
+		input  string
+		output Deps
+		err    error
+	}{
+		// These come from the ninja test suite
+		{
+			name:  "Basic",
+			input: "build/ninja.o: ninja.cc ninja.h eval_env.h manifest_parser.h",
+			output: Deps{
+				Output: "build/ninja.o",
+				Inputs: []string{
+					"ninja.cc",
+					"ninja.h",
+					"eval_env.h",
+					"manifest_parser.h",
+				},
+			},
+		},
+		{
+			name: "EarlyNewlineAndWhitespace",
+			input: ` \
+  out: in`,
+			output: Deps{
+				Output: "out",
+				Inputs: []string{"in"},
+			},
+		},
+		{
+			name: "Continuation",
+			input: `foo.o: \
+  bar.h baz.h
+`,
+			output: Deps{
+				Output: "foo.o",
+				Inputs: []string{"bar.h", "baz.h"},
+			},
+		},
+		{
+			name:  "CarriageReturnContinuation",
+			input: "foo.o: \\\r\n  bar.h baz.h\r\n",
+			output: Deps{
+				Output: "foo.o",
+				Inputs: []string{"bar.h", "baz.h"},
+			},
+		},
+		{
+			name: "BackSlashes",
+			input: `Project\Dir\Build\Release8\Foo\Foo.res : \
+  Dir\Library\Foo.rc \
+  Dir\Library\Version\Bar.h \
+  Dir\Library\Foo.ico \
+  Project\Thing\Bar.tlb \
+`,
+			output: Deps{
+				Output: `Project\Dir\Build\Release8\Foo\Foo.res`,
+				Inputs: []string{
+					`Dir\Library\Foo.rc`,
+					`Dir\Library\Version\Bar.h`,
+					`Dir\Library\Foo.ico`,
+					`Project\Thing\Bar.tlb`,
+				},
+			},
+		},
+		{
+			name:  "Spaces",
+			input: `a\ bc\ def:   a\ b c d`,
+			output: Deps{
+				Output: `a bc def`,
+				Inputs: []string{"a b", "c", "d"},
+			},
+		},
+		{
+			name:  "Escapes",
+			input: `\!\@\#$$\%\^\&\\:`,
+			output: Deps{
+				Output: `\!\@#$\%\^\&\`,
+			},
+		},
+		{
+			name: "SpecialChars",
+			// Ninja includes a number of '=', but our parser can't handle that,
+			// since it sees the equals and switches over to assuming it's an
+			// assignment.
+			//
+			// We don't have any files in our tree that contain an '=' character,
+			// and Kati can't handle parsing this either, so for now I'm just
+			// going to remove all the '=' characters below.
+			//
+			// It looks like make will only do this for the first
+			// dependency, but not later dependencies.
+			input: `C\:/Program\ Files\ (x86)/Microsoft\ crtdefs.h: \
+ en@quot.header~ t+t-x!1 \
+ openldap/slapd.d/cnconfig/cnschema/cn{0}core.ldif \
+ Fu` + "\303\244ball",
+			output: Deps{
+				Output: "C:/Program Files (x86)/Microsoft crtdefs.h",
+				Inputs: []string{
+					"en@quot.header~",
+					"t+t-x!1",
+					"openldap/slapd.d/cnconfig/cnschema/cn{0}core.ldif",
+					"Fu\303\244ball",
+				},
+			},
+		},
+		// Ninja's UnifyMultipleOutputs and RejectMultipleDifferentOutputs tests have been omitted,
+		// since we don't want the same behavior.
+
+		// Our own tests
+		{
+			name: "Multiple outputs",
+			input: `a b: c
+a: d
+b: e`,
+			output: Deps{
+				Output: "b",
+				Inputs: []string{
+					"c",
+					"d",
+					"e",
+				},
+			},
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			out, err := Parse("test.d", bytes.NewBufferString(tc.input))
+			if err != tc.err {
+				t.Fatalf("Unexpected error: %v (expected %v)", err, tc.err)
+			}
+
+			if out.Output != tc.output.Output {
+				t.Errorf("output file doesn't match:\n"+
+					" str: %#v\n"+
+					"want: %#v\n"+
+					" got: %#v", tc.input, tc.output.Output, out.Output)
+			}
+
+			matches := true
+			if len(out.Inputs) != len(tc.output.Inputs) {
+				matches = false
+			} else {
+				for i := range out.Inputs {
+					if out.Inputs[i] != tc.output.Inputs[i] {
+						matches = false
+					}
+				}
+			}
+			if !matches {
+				t.Errorf("input files don't match:\n"+
+					" str: %#v\n"+
+					"want: %#v\n"+
+					" got: %#v", tc.input, tc.output.Inputs, out.Inputs)
+			}
+		})
+	}
+}
+
+func BenchmarkParsing(b *testing.B) {
+	// Write it out to a file to most closely match ninja's perftest
+	tmpfile, err := ioutil.TempFile("", "depfile")
+	if err != nil {
+		b.Fatal("Failed to create temp file:", err)
+	}
+	defer os.Remove(tmpfile.Name())
+	_, err = io.WriteString(tmpfile, `out/soong/.intermediates/external/ninja/ninja/linux_glibc_x86_64/obj/external/ninja/src/ninja.o: \
+  external/ninja/src/ninja.cc external/libcxx/include/errno.h \
+  external/libcxx/include/__config \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/features.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/predefs.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/sys/cdefs.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/wordsize.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/gnu/stubs.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/gnu/stubs-64.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/errno.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/errno.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/linux/errno.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/asm/errno.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/asm-generic/errno.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/asm-generic/errno-base.h \
+  external/libcxx/include/limits.h \
+  prebuilts/clang/host/linux-x86/clang-4639204/lib64/clang/6.0.1/include/limits.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/limits.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/posix1_lim.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/local_lim.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/linux/limits.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/posix2_lim.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/xopen_lim.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/stdio_lim.h \
+  external/libcxx/include/stdio.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/stdio.h \
+  external/libcxx/include/stddef.h \
+  prebuilts/clang/host/linux-x86/clang-4639204/lib64/clang/6.0.1/include/stddef.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/types.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/typesizes.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/libio.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/_G_config.h \
+  external/libcxx/include/wchar.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/wchar.h \
+  prebuilts/clang/host/linux-x86/clang-4639204/lib64/clang/6.0.1/include/stdarg.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/sys_errlist.h \
+  external/libcxx/include/stdlib.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/stdlib.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/waitflags.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/waitstatus.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/endian.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/endian.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/byteswap.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/xlocale.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/sys/types.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/time.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/sys/select.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/select.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/sigset.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/time.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/select2.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/sys/sysmacros.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/pthreadtypes.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/alloca.h \
+  external/libcxx/include/string.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/string.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/getopt.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/unistd.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/posix_opt.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/environments.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/confname.h \
+  external/ninja/src/browse.h external/ninja/src/build.h \
+  external/libcxx/include/cstdio external/libcxx/include/map \
+  external/libcxx/include/__tree external/libcxx/include/iterator \
+  external/libcxx/include/iosfwd \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/wchar.h \
+  external/libcxx/include/__functional_base \
+  external/libcxx/include/type_traits external/libcxx/include/cstddef \
+  prebuilts/clang/host/linux-x86/clang-4639204/lib64/clang/6.0.1/include/__stddef_max_align_t.h \
+  external/libcxx/include/__nullptr external/libcxx/include/typeinfo \
+  external/libcxx/include/exception external/libcxx/include/cstdlib \
+  external/libcxx/include/cstdint external/libcxx/include/stdint.h \
+  prebuilts/clang/host/linux-x86/clang-4639204/lib64/clang/6.0.1/include/stdint.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/stdint.h \
+  external/libcxx/include/new external/libcxx/include/utility \
+  external/libcxx/include/__tuple \
+  external/libcxx/include/initializer_list \
+  external/libcxx/include/cstring external/libcxx/include/__debug \
+  external/libcxx/include/memory external/libcxx/include/limits \
+  external/libcxx/include/__undef_macros external/libcxx/include/tuple \
+  external/libcxx/include/stdexcept external/libcxx/include/cassert \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/assert.h \
+  external/libcxx/include/atomic external/libcxx/include/algorithm \
+  external/libcxx/include/functional external/libcxx/include/queue \
+  external/libcxx/include/deque external/libcxx/include/__split_buffer \
+  external/libcxx/include/vector external/libcxx/include/__bit_reference \
+  external/libcxx/include/climits external/libcxx/include/set \
+  external/libcxx/include/string external/libcxx/include/string_view \
+  external/libcxx/include/__string external/libcxx/include/cwchar \
+  external/libcxx/include/cwctype external/libcxx/include/cctype \
+  external/libcxx/include/ctype.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/ctype.h \
+  external/libcxx/include/wctype.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/wctype.h \
+  external/ninja/src/graph.h external/ninja/src/eval_env.h \
+  external/ninja/src/string_piece.h external/ninja/src/timestamp.h \
+  external/ninja/src/util.h external/ninja/src/exit_status.h \
+  external/ninja/src/line_printer.h external/ninja/src/metrics.h \
+  external/ninja/src/build_log.h external/ninja/src/hash_map.h \
+  external/libcxx/include/unordered_map \
+  external/libcxx/include/__hash_table external/libcxx/include/cmath \
+  external/libcxx/include/math.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/math.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/huge_val.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/huge_valf.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/huge_vall.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/inf.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/nan.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/mathdef.h \
+  prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8/sysroot/usr/include/x86_64-linux-gnu/bits/mathcalls.h \
+  external/ninja/src/deps_log.h external/ninja/src/clean.h \
+  external/ninja/src/debug_flags.h external/ninja/src/disk_interface.h \
+  external/ninja/src/graphviz.h external/ninja/src/manifest_parser.h \
+  external/ninja/src/lexer.h external/ninja/src/state.h \
+  external/ninja/src/version.h`)
+	tmpfile.Close()
+	if err != nil {
+		b.Fatal("Failed to write dep file:", err)
+	}
+	b.ResetTimer()
+
+	for n := 0; n < b.N; n++ {
+		depfile, err := ioutil.ReadFile(tmpfile.Name())
+		if err != nil {
+			b.Fatal("Failed to read dep file:", err)
+		}
+
+		_, err = Parse(tmpfile.Name(), bytes.NewBuffer(depfile))
+		if err != nil {
+			b.Fatal("Failed to parse:", err)
+		}
+	}
+}
+
+func TestDepPrint(t *testing.T) {
+	testCases := []struct {
+		name   string
+		input  Deps
+		output string
+	}{
+		{
+			name: "Empty",
+			input: Deps{
+				Output: "a",
+			},
+			output: "a:",
+		},
+		{
+			name: "Basic",
+			input: Deps{
+				Output: "a",
+				Inputs: []string{"b", "c"},
+			},
+			output: "a: b c",
+		},
+		{
+			name: "Escapes",
+			input: Deps{
+				Output: `\!\@#$\%\^\&\`,
+			},
+			output: `\\!\\@\#$$\\%\\^\\&\\:`,
+		},
+		{
+			name: "Spaces",
+			input: Deps{
+				Output: "a b",
+				Inputs: []string{"c d", "e f "},
+			},
+			output: `a\ b: c\ d e\ f\ `,
+		},
+		{
+			name: "SpecialChars",
+			input: Deps{
+				Output: "C:/Program Files (x86)/Microsoft crtdefs.h",
+				Inputs: []string{
+					"en@quot.header~",
+					"t+t-x!1",
+					"openldap/slapd.d/cnconfig/cnschema/cn{0}core.ldif",
+					"Fu\303\244ball",
+				},
+			},
+			output: `C\:/Program\ Files\ (x86)/Microsoft\ crtdefs.h: en@quot.header~ t+t-x!1 openldap/slapd.d/cnconfig/cnschema/cn{0}core.ldif Fu` + "\303\244ball",
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			out := tc.input.Print()
+			outStr := string(out)
+			want := tc.output + "\n"
+
+			if outStr != want {
+				t.Errorf("output doesn't match:\nwant:%q\n got:%q", want, outStr)
+			}
+		})
+	}
+}
diff --git a/cmd/dep_fixer/main.go b/cmd/dep_fixer/main.go
new file mode 100644
index 0000000..bac3772
--- /dev/null
+++ b/cmd/dep_fixer/main.go
@@ -0,0 +1,67 @@
+// Copyright 2018 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// This tool reads "make"-like dependency files, and outputs a canonical version
+// that can be used by ninja. Ninja doesn't support multiple output files (even
+// though it doesn't care what the output file is, or whether it matches what is
+// expected).
+package main
+
+import (
+	"bytes"
+	"flag"
+	"fmt"
+	"io/ioutil"
+	"log"
+	"os"
+)
+
+func main() {
+	flag.Usage = func() {
+		fmt.Fprintf(os.Stderr, "Usage: %s <depfile.d>")
+		flag.PrintDefaults()
+	}
+	output := flag.String("o", "", "Optional output file (defaults to rewriting source if necessary)")
+	flag.Parse()
+
+	if flag.NArg() != 1 {
+		log.Fatal("Expected a single file as an argument")
+	}
+
+	old, err := ioutil.ReadFile(flag.Arg(0))
+	if err != nil {
+		log.Fatalf("Error opening %q: %v", flag.Arg(0), err)
+	}
+
+	deps, err := Parse(flag.Arg(0), bytes.NewBuffer(append([]byte(nil), old...)))
+	if err != nil {
+		log.Fatalf("Failed to parse: %v", err)
+	}
+
+	new := deps.Print()
+
+	if *output == "" || *output == flag.Arg(0) {
+		if !bytes.Equal(old, new) {
+			err := ioutil.WriteFile(flag.Arg(0), new, 0666)
+			if err != nil {
+				log.Fatalf("Failed to write: %v", err)
+			}
+		}
+	} else {
+		err := ioutil.WriteFile(*output, new, 0666)
+		if err != nil {
+			log.Fatalf("Failed to write to %q: %v", *output, err)
+		}
+	}
+}
diff --git a/java/proto.go b/java/proto.go
index cfd733a..3ec2e8a 100644
--- a/java/proto.go
+++ b/java/proto.go
@@ -30,12 +30,14 @@
 	proto = pctx.AndroidStaticRule("protoc",
 		blueprint.RuleParams{
 			Command: `rm -rf $out.tmp && mkdir -p $out.tmp && ` +
-				`$protocCmd $protoOut=$protoOutParams:$out.tmp -I $protoBase $protoFlags $in && ` +
+				`$protocCmd $protoOut=$protoOutParams:$out.tmp --dependency_out=$out.d -I $protoBase $protoFlags $in && ` +
 				`${config.SoongZipCmd} -jar -o $out -C $out.tmp -D $out.tmp && rm -rf $out.tmp`,
 			CommandDeps: []string{
 				"$protocCmd",
 				"${config.SoongZipCmd}",
 			},
+			Depfile: "${out}.d",
+			Deps:    blueprint.DepsGCC,
 		}, "protoBase", "protoFlags", "protoOut", "protoOutParams")
 )
 
diff --git a/python/proto.go b/python/proto.go
index 82ee3cb..42987fa 100644
--- a/python/proto.go
+++ b/python/proto.go
@@ -29,12 +29,14 @@
 	proto = pctx.AndroidStaticRule("protoc",
 		blueprint.RuleParams{
 			Command: `rm -rf $out.tmp && mkdir -p $out.tmp && ` +
-				`$protocCmd --python_out=$out.tmp -I $protoBase $protoFlags $in && ` +
+				`$protocCmd --python_out=$out.tmp --dependency_out=$out.d -I $protoBase $protoFlags $in && ` +
 				`$parCmd -o $out -P $pkgPath -C $out.tmp -D $out.tmp && rm -rf $out.tmp`,
 			CommandDeps: []string{
 				"$protocCmd",
 				"$parCmd",
 			},
+			Depfile: "${out}.d",
+			Deps:    blueprint.DepsGCC,
 		}, "protoBase", "protoFlags", "pkgPath")
 )