diff --git a/android/Android.bp b/android/Android.bp
index 4bd272d..f8c1d55 100644
--- a/android/Android.bp
+++ b/android/Android.bp
@@ -23,7 +23,8 @@
         "csuite_config.go",
         "defaults.go",
         "defs.go",
-        "depset.go",
+        "depset_generic.go",
+        "depset_paths.go",
         "deptag.go",
         "expand.go",
         "filegroup.go",
diff --git a/android/depset.go b/android/depset.go
deleted file mode 100644
index 60ebcac..0000000
--- a/android/depset.go
+++ /dev/null
@@ -1,194 +0,0 @@
-// Copyright 2020 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 android
-
-import "fmt"
-
-// DepSet is designed to be conceptually compatible with Bazel's depsets:
-// https://docs.bazel.build/versions/master/skylark/depsets.html
-
-// A DepSet efficiently stores Paths from transitive dependencies without copying. It is stored
-// as a DAG of DepSet nodes, each of which has some direct contents and a list of dependency
-// DepSet nodes.
-//
-// A DepSet has an order that will be used to walk the DAG when ToList() is called.  The order
-// can be POSTORDER, PREORDER, or TOPOLOGICAL.  POSTORDER and PREORDER orders return a postordered
-// or preordered left to right flattened list.  TOPOLOGICAL returns a list that guarantees that
-// elements of children are listed after all of their parents (unless there are duplicate direct
-// elements in the DepSet or any of its transitive dependencies, in which case the ordering of the
-// duplicated element is not guaranteed).
-//
-// A DepSet is created by NewDepSet or NewDepSetBuilder.Build from the Paths for direct contents
-// and the *DepSets of dependencies. A DepSet is immutable once created.
-type DepSet struct {
-	preorder   bool
-	reverse    bool
-	order      DepSetOrder
-	direct     Paths
-	transitive []*DepSet
-}
-
-// DepSetBuilder is used to create an immutable DepSet.
-type DepSetBuilder struct {
-	order      DepSetOrder
-	direct     Paths
-	transitive []*DepSet
-}
-
-type DepSetOrder int
-
-const (
-	PREORDER DepSetOrder = iota
-	POSTORDER
-	TOPOLOGICAL
-)
-
-func (o DepSetOrder) String() string {
-	switch o {
-	case PREORDER:
-		return "PREORDER"
-	case POSTORDER:
-		return "POSTORDER"
-	case TOPOLOGICAL:
-		return "TOPOLOGICAL"
-	default:
-		panic(fmt.Errorf("Invalid DepSetOrder %d", o))
-	}
-}
-
-// NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
-func NewDepSet(order DepSetOrder, direct Paths, transitive []*DepSet) *DepSet {
-	var directCopy Paths
-	transitiveCopy := make([]*DepSet, 0, len(transitive))
-
-	for _, dep := range transitive {
-		if dep != nil {
-			if dep.order != order {
-				panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
-					order, dep.order))
-			}
-			transitiveCopy = append(transitiveCopy, dep)
-		}
-	}
-
-	if order == TOPOLOGICAL {
-		directCopy = ReversePaths(direct)
-		reverseDepSetsInPlace(transitiveCopy)
-	} else {
-		// Use copy instead of append(nil, ...) to make a slice that is exactly the size of the input
-		// slice.  The DepSet is immutable, there is no need for additional capacity.
-		directCopy = make(Paths, len(direct))
-		copy(directCopy, direct)
-	}
-
-	return &DepSet{
-		preorder:   order == PREORDER,
-		reverse:    order == TOPOLOGICAL,
-		order:      order,
-		direct:     directCopy,
-		transitive: transitiveCopy,
-	}
-}
-
-// NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order.
-func NewDepSetBuilder(order DepSetOrder) *DepSetBuilder {
-	return &DepSetBuilder{order: order}
-}
-
-// Direct adds direct contents to the DepSet being built by a DepSetBuilder. Newly added direct
-// contents are to the right of any existing direct contents.
-func (b *DepSetBuilder) Direct(direct ...Path) *DepSetBuilder {
-	b.direct = append(b.direct, direct...)
-	return b
-}
-
-// Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added
-// transitive contents are to the right of any existing transitive contents.
-func (b *DepSetBuilder) Transitive(transitive ...*DepSet) *DepSetBuilder {
-	b.transitive = append(b.transitive, transitive...)
-	return b
-}
-
-// Returns the DepSet being built by this DepSetBuilder.  The DepSetBuilder retains its contents
-// for creating more DepSets.
-func (b *DepSetBuilder) Build() *DepSet {
-	return NewDepSet(b.order, b.direct, b.transitive)
-}
-
-// walk calls the visit method in depth-first order on a DepSet, preordered if d.preorder is set,
-// otherwise postordered.
-func (d *DepSet) walk(visit func(Paths)) {
-	visited := make(map[*DepSet]bool)
-
-	var dfs func(d *DepSet)
-	dfs = func(d *DepSet) {
-		visited[d] = true
-		if d.preorder {
-			visit(d.direct)
-		}
-		for _, dep := range d.transitive {
-			if !visited[dep] {
-				dfs(dep)
-			}
-		}
-
-		if !d.preorder {
-			visit(d.direct)
-		}
-	}
-
-	dfs(d)
-}
-
-// ToList returns the DepSet flattened to a list.  The order in the list is based on the order
-// of the DepSet.  POSTORDER and PREORDER orders return a postordered or preordered left to right
-// flattened list.  TOPOLOGICAL returns a list that guarantees that elements of children are listed
-// after all of their parents (unless there are duplicate direct elements in the DepSet or any of
-// its transitive dependencies, in which case the ordering of the duplicated element is not
-// guaranteed).
-func (d *DepSet) ToList() Paths {
-	if d == nil {
-		return nil
-	}
-	var list Paths
-	d.walk(func(paths Paths) {
-		list = append(list, paths...)
-	})
-	list = FirstUniquePaths(list)
-	if d.reverse {
-		reversePathsInPlace(list)
-	}
-	return list
-}
-
-// ToSortedList returns the direct and transitive contents of a DepSet in lexically sorted order
-// with duplicates removed.
-func (d *DepSet) ToSortedList() Paths {
-	list := d.ToList()
-	return SortedUniquePaths(list)
-}
-
-func reversePathsInPlace(list Paths) {
-	for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
-		list[i], list[j] = list[j], list[i]
-	}
-}
-
-func reverseDepSetsInPlace(list []*DepSet) {
-	for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
-		list[i], list[j] = list[j], list[i]
-	}
-
-}
diff --git a/android/depset_generic.go b/android/depset_generic.go
new file mode 100644
index 0000000..f00e462
--- /dev/null
+++ b/android/depset_generic.go
@@ -0,0 +1,351 @@
+// Copyright 2020 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 android
+
+import (
+	"fmt"
+	"reflect"
+)
+
+// depSet is designed to be conceptually compatible with Bazel's depsets:
+// https://docs.bazel.build/versions/master/skylark/depsets.html
+
+type DepSetOrder int
+
+const (
+	PREORDER DepSetOrder = iota
+	POSTORDER
+	TOPOLOGICAL
+)
+
+func (o DepSetOrder) String() string {
+	switch o {
+	case PREORDER:
+		return "PREORDER"
+	case POSTORDER:
+		return "POSTORDER"
+	case TOPOLOGICAL:
+		return "TOPOLOGICAL"
+	default:
+		panic(fmt.Errorf("Invalid DepSetOrder %d", o))
+	}
+}
+
+// A depSet efficiently stores a slice of an arbitrary type from transitive dependencies without
+// copying. It is stored as a DAG of depSet nodes, each of which has some direct contents and a list
+// of dependency depSet nodes.
+//
+// A depSet has an order that will be used to walk the DAG when ToList() is called.  The order
+// can be POSTORDER, PREORDER, or TOPOLOGICAL.  POSTORDER and PREORDER orders return a postordered
+// or preordered left to right flattened list.  TOPOLOGICAL returns a list that guarantees that
+// elements of children are listed after all of their parents (unless there are duplicate direct
+// elements in the depSet or any of its transitive dependencies, in which case the ordering of the
+// duplicated element is not guaranteed).
+//
+// A depSet is created by newDepSet or newDepSetBuilder.Build from the slice for direct contents
+// and the *depSets of dependencies. A depSet is immutable once created.
+//
+// This object uses reflection to remain agnostic to the type it contains.  It should be replaced
+// with generics once those exist in Go.  Callers should generally use a thin wrapper around depSet
+// that provides type-safe methods like DepSet for Paths.
+type depSet struct {
+	preorder   bool
+	reverse    bool
+	order      DepSetOrder
+	direct     interface{}
+	transitive []*depSet
+}
+
+type depSetInterface interface {
+	embeddedDepSet() *depSet
+}
+
+func (d *depSet) embeddedDepSet() *depSet {
+	return d
+}
+
+var _ depSetInterface = (*depSet)(nil)
+
+// newDepSet returns an immutable depSet with the given order, direct and transitive contents.
+// direct must be a slice, but is not type-safe due to the lack of generics in Go.  It can be a
+// nil slice, but not a nil interface{}, i.e. []string(nil) but not nil.
+func newDepSet(order DepSetOrder, direct interface{}, transitive interface{}) *depSet {
+	var directCopy interface{}
+	transitiveDepSet := sliceToDepSets(transitive, order)
+
+	if order == TOPOLOGICAL {
+		directCopy = reverseSlice(direct)
+		reverseSliceInPlace(transitiveDepSet)
+	} else {
+		directCopy = copySlice(direct)
+	}
+
+	return &depSet{
+		preorder:   order == PREORDER,
+		reverse:    order == TOPOLOGICAL,
+		order:      order,
+		direct:     directCopy,
+		transitive: transitiveDepSet,
+	}
+}
+
+// depSetBuilder is used to create an immutable depSet.
+type depSetBuilder struct {
+	order      DepSetOrder
+	direct     reflect.Value
+	transitive []*depSet
+}
+
+// newDepSetBuilder returns a depSetBuilder to create an immutable depSet with the given order and
+// type, represented by a slice of type that will be in the depSet.
+func newDepSetBuilder(order DepSetOrder, typ interface{}) *depSetBuilder {
+	empty := reflect.Zero(reflect.TypeOf(typ))
+	return &depSetBuilder{
+		order:  order,
+		direct: empty,
+	}
+}
+
+// sliceToDepSets converts a slice of any type that implements depSetInterface (by having a depSet
+// embedded in it) into a []*depSet.
+func sliceToDepSets(in interface{}, order DepSetOrder) []*depSet {
+	slice := reflect.ValueOf(in)
+	length := slice.Len()
+	out := make([]*depSet, length)
+	for i := 0; i < length; i++ {
+		vi := slice.Index(i)
+		depSetIntf, ok := vi.Interface().(depSetInterface)
+		if !ok {
+			panic(fmt.Errorf("element %d is a %s, not a depSetInterface", i, vi.Type()))
+		}
+		depSet := depSetIntf.embeddedDepSet()
+		if depSet.order != order {
+			panic(fmt.Errorf("incompatible order, new depSet is %s but transitive depSet is %s",
+				order, depSet.order))
+		}
+		out[i] = depSet
+	}
+	return out
+}
+
+// DirectSlice adds direct contents to the depSet being built by a depSetBuilder. Newly added direct
+// contents are to the right of any existing direct contents.  The argument must be a slice, but
+// is not type-safe due to the lack of generics in Go.
+func (b *depSetBuilder) DirectSlice(direct interface{}) *depSetBuilder {
+	b.direct = reflect.AppendSlice(b.direct, reflect.ValueOf(direct))
+	return b
+}
+
+// Direct adds direct contents to the depSet being built by a depSetBuilder. Newly added direct
+// contents are to the right of any existing direct contents.  The argument must be the same type
+// as the element of the slice passed to newDepSetBuilder, but is not type-safe due to the lack of
+// generics in Go.
+func (b *depSetBuilder) Direct(direct interface{}) *depSetBuilder {
+	b.direct = reflect.Append(b.direct, reflect.ValueOf(direct))
+	return b
+}
+
+// Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added
+// transitive contents are to the right of any existing transitive contents.  The argument can
+// be any slice of type that has depSet embedded in it.
+func (b *depSetBuilder) Transitive(transitive interface{}) *depSetBuilder {
+	depSets := sliceToDepSets(transitive, b.order)
+	b.transitive = append(b.transitive, depSets...)
+	return b
+}
+
+// Returns the depSet being built by this depSetBuilder.  The depSetBuilder retains its contents
+// for creating more depSets.
+func (b *depSetBuilder) Build() *depSet {
+	return newDepSet(b.order, b.direct.Interface(), b.transitive)
+}
+
+// walk calls the visit method in depth-first order on a DepSet, preordered if d.preorder is set,
+// otherwise postordered.
+func (d *depSet) walk(visit func(interface{})) {
+	visited := make(map[*depSet]bool)
+
+	var dfs func(d *depSet)
+	dfs = func(d *depSet) {
+		visited[d] = true
+		if d.preorder {
+			visit(d.direct)
+		}
+		for _, dep := range d.transitive {
+			if !visited[dep] {
+				dfs(dep)
+			}
+		}
+
+		if !d.preorder {
+			visit(d.direct)
+		}
+	}
+
+	dfs(d)
+}
+
+// ToList returns the depSet flattened to a list.  The order in the list is based on the order
+// of the depSet.  POSTORDER and PREORDER orders return a postordered or preordered left to right
+// flattened list.  TOPOLOGICAL returns a list that guarantees that elements of children are listed
+// after all of their parents (unless there are duplicate direct elements in the DepSet or any of
+// its transitive dependencies, in which case the ordering of the duplicated element is not
+// guaranteed).
+//
+// This method uses a reflection-based implementation to find the unique elements in slice, which
+// is around 3x slower than a concrete implementation.  Type-safe wrappers around depSet can
+// provide their own implementation of ToList that calls depSet.toList with a method that
+// uses a concrete implementation.
+func (d *depSet) ToList() interface{} {
+	return d.toList(firstUnique)
+}
+
+// toList returns the depSet flattened to a list.  The order in the list is based on the order
+// of the depSet.  POSTORDER and PREORDER orders return a postordered or preordered left to right
+// flattened list.  TOPOLOGICAL returns a list that guarantees that elements of children are listed
+// after all of their parents (unless there are duplicate direct elements in the DepSet or any of
+// its transitive dependencies, in which case the ordering of the duplicated element is not
+// guaranteed).  The firstUniqueFunc is used to remove duplicates from the list.
+func (d *depSet) toList(firstUniqueFunc func(interface{}) interface{}) interface{} {
+	if d == nil {
+		return nil
+	}
+	slice := reflect.Zero(reflect.TypeOf(d.direct))
+	d.walk(func(paths interface{}) {
+		slice = reflect.AppendSlice(slice, reflect.ValueOf(paths))
+	})
+	list := slice.Interface()
+	list = firstUniqueFunc(list)
+	if d.reverse {
+		reverseSliceInPlace(list)
+	}
+	return list
+}
+
+// firstUnique returns all unique elements of a slice, keeping the first copy of each.  It
+// modifies the slice contents in place, and returns a subslice of the original slice.  The
+// argument must be a slice, but is not type-safe due to the lack of reflection in Go.
+//
+// Performance of the reflection-based firstUnique is up to 3x slower than a concrete type
+// version such as FirstUniqueStrings.
+func firstUnique(slice interface{}) interface{} {
+	// 4 was chosen based on Benchmark_firstUnique results.
+	if reflect.ValueOf(slice).Len() > 4 {
+		return firstUniqueMap(slice)
+	}
+	return firstUniqueList(slice)
+}
+
+// firstUniqueList is an implementation of firstUnique using an O(N^2) list comparison to look for
+// duplicates.
+func firstUniqueList(in interface{}) interface{} {
+	writeIndex := 0
+	slice := reflect.ValueOf(in)
+	length := slice.Len()
+outer:
+	for readIndex := 0; readIndex < length; readIndex++ {
+		readValue := slice.Index(readIndex)
+		for compareIndex := 0; compareIndex < writeIndex; compareIndex++ {
+			compareValue := slice.Index(compareIndex)
+			// These two Interface() calls seem to cause an allocation and significantly
+			// slow down this list-based implementation.  The map implementation below doesn't
+			// have this issue because reflect.Value.MapIndex takes a Value and appears to be
+			// able to do the map lookup without an allocation.
+			if readValue.Interface() == compareValue.Interface() {
+				// The value at readIndex already exists somewhere in the output region
+				// of the slice before writeIndex, skip it.
+				continue outer
+			}
+		}
+		if readIndex != writeIndex {
+			writeValue := slice.Index(writeIndex)
+			writeValue.Set(readValue)
+		}
+		writeIndex++
+	}
+	return slice.Slice(0, writeIndex).Interface()
+}
+
+var trueValue = reflect.ValueOf(true)
+
+// firstUniqueList is an implementation of firstUnique using an O(N) hash set lookup to look for
+// duplicates.
+func firstUniqueMap(in interface{}) interface{} {
+	writeIndex := 0
+	slice := reflect.ValueOf(in)
+	length := slice.Len()
+	seen := reflect.MakeMapWithSize(reflect.MapOf(slice.Type().Elem(), trueValue.Type()), slice.Len())
+	for readIndex := 0; readIndex < length; readIndex++ {
+		readValue := slice.Index(readIndex)
+		if seen.MapIndex(readValue).IsValid() {
+			continue
+		}
+		seen.SetMapIndex(readValue, trueValue)
+		if readIndex != writeIndex {
+			writeValue := slice.Index(writeIndex)
+			writeValue.Set(readValue)
+		}
+		writeIndex++
+	}
+	return slice.Slice(0, writeIndex).Interface()
+}
+
+// reverseSliceInPlace reverses the elements of a slice in place.  The argument must be a slice, but
+// is not type-safe due to the lack of reflection in Go.
+func reverseSliceInPlace(in interface{}) {
+	swapper := reflect.Swapper(in)
+	slice := reflect.ValueOf(in)
+	length := slice.Len()
+	for i, j := 0, length-1; i < j; i, j = i+1, j-1 {
+		swapper(i, j)
+	}
+}
+
+// reverseSlice returns a copy of a slice in reverse order.  The argument must be a slice, but is
+// not type-safe due to the lack of reflection in Go.
+func reverseSlice(in interface{}) interface{} {
+	slice := reflect.ValueOf(in)
+	if !slice.IsValid() || slice.IsNil() {
+		return in
+	}
+	if slice.Kind() != reflect.Slice {
+		panic(fmt.Errorf("%t is not a slice", in))
+	}
+	length := slice.Len()
+	if length == 0 {
+		return in
+	}
+	out := reflect.MakeSlice(slice.Type(), length, length)
+	for i := 0; i < length; i++ {
+		out.Index(i).Set(slice.Index(length - 1 - i))
+	}
+	return out.Interface()
+}
+
+// copySlice returns a copy of a slice.  The argument must be a slice, but is not type-safe due to
+// the lack of reflection in Go.
+func copySlice(in interface{}) interface{} {
+	slice := reflect.ValueOf(in)
+	if !slice.IsValid() || slice.IsNil() {
+		return in
+	}
+	length := slice.Len()
+	if length == 0 {
+		return in
+	}
+	out := reflect.MakeSlice(slice.Type(), length, length)
+	reflect.Copy(out, slice)
+	return out.Interface()
+}
diff --git a/android/depset_paths.go b/android/depset_paths.go
new file mode 100644
index 0000000..ed561ba
--- /dev/null
+++ b/android/depset_paths.go
@@ -0,0 +1,94 @@
+// Copyright 2020 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 android
+
+// This file implements DepSet, a thin type-safe wrapper around depSet that contains Paths.
+
+// A DepSet efficiently stores Paths from transitive dependencies without copying. It is stored
+// as a DAG of DepSet nodes, each of which has some direct contents and a list of dependency
+// DepSet nodes.
+//
+// A DepSet has an order that will be used to walk the DAG when ToList() is called.  The order
+// can be POSTORDER, PREORDER, or TOPOLOGICAL.  POSTORDER and PREORDER orders return a postordered
+// or preordered left to right flattened list.  TOPOLOGICAL returns a list that guarantees that
+// elements of children are listed after all of their parents (unless there are duplicate direct
+// elements in the DepSet or any of its transitive dependencies, in which case the ordering of the
+// duplicated element is not guaranteed).
+//
+// A DepSet is created by NewDepSet or NewDepSetBuilder.Build from the Paths for direct contents
+// and the *DepSets of dependencies. A DepSet is immutable once created.
+type DepSet struct {
+	depSet
+}
+
+// DepSetBuilder is used to create an immutable DepSet.
+type DepSetBuilder struct {
+	depSetBuilder
+}
+
+// NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
+func NewDepSet(order DepSetOrder, direct Paths, transitive []*DepSet) *DepSet {
+	return &DepSet{*newDepSet(order, direct, transitive)}
+}
+
+// NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order.
+func NewDepSetBuilder(order DepSetOrder) *DepSetBuilder {
+	return &DepSetBuilder{*newDepSetBuilder(order, Paths(nil))}
+}
+
+// Direct adds direct contents to the DepSet being built by a DepSetBuilder. Newly added direct
+// contents are to the right of any existing direct contents.
+func (b *DepSetBuilder) Direct(direct ...Path) *DepSetBuilder {
+	b.depSetBuilder.DirectSlice(direct)
+	return b
+}
+
+// Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added
+// transitive contents are to the right of any existing transitive contents.
+func (b *DepSetBuilder) Transitive(transitive ...*DepSet) *DepSetBuilder {
+	b.depSetBuilder.Transitive(transitive)
+	return b
+}
+
+// Returns the DepSet being built by this DepSetBuilder.  The DepSetBuilder retains its contents
+// for creating more DepSets.
+func (b *DepSetBuilder) Build() *DepSet {
+	return &DepSet{*b.depSetBuilder.Build()}
+}
+
+// ToList returns the DepSet flattened to a list.  The order in the list is based on the order
+// of the DepSet.  POSTORDER and PREORDER orders return a postordered or preordered left to right
+// flattened list.  TOPOLOGICAL returns a list that guarantees that elements of children are listed
+// after all of their parents (unless there are duplicate direct elements in the DepSet or any of
+// its transitive dependencies, in which case the ordering of the duplicated element is not
+// guaranteed).
+func (d *DepSet) ToList() Paths {
+	if d == nil {
+		return nil
+	}
+	return d.toList(func(paths interface{}) interface{} {
+		return FirstUniquePaths(paths.(Paths))
+	}).(Paths)
+}
+
+// ToSortedList returns the direct and transitive contents of a DepSet in lexically sorted order
+// with duplicates removed.
+func (d *DepSet) ToSortedList() Paths {
+	if d == nil {
+		return nil
+	}
+	paths := d.ToList()
+	return SortedUniquePaths(paths)
+}
diff --git a/android/depset_test.go b/android/depset_test.go
index c328127..955ccb0 100644
--- a/android/depset_test.go
+++ b/android/depset_test.go
@@ -17,6 +17,7 @@
 import (
 	"fmt"
 	"reflect"
+	"strconv"
 	"strings"
 	"testing"
 )
@@ -108,6 +109,7 @@
 			name: "builderReuse",
 			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
 				assertEquals := func(t *testing.T, w, g Paths) {
+					t.Helper()
 					if !reflect.DeepEqual(w, g) {
 						t.Errorf("want %q, got %q", w, g)
 					}
@@ -302,3 +304,87 @@
 		})
 	}
 }
+
+func Test_firstUnique(t *testing.T) {
+	f := func(t *testing.T, imp func([]string) []string, in, want []string) {
+		t.Helper()
+		out := imp(in)
+		if !reflect.DeepEqual(out, want) {
+			t.Errorf("incorrect output:")
+			t.Errorf("     input: %#v", in)
+			t.Errorf("  expected: %#v", want)
+			t.Errorf("       got: %#v", out)
+		}
+	}
+
+	for _, testCase := range firstUniqueStringsTestCases {
+		t.Run("list", func(t *testing.T) {
+			f(t, func(s []string) []string {
+				return firstUniqueList(s).([]string)
+			}, testCase.in, testCase.out)
+		})
+		t.Run("map", func(t *testing.T) {
+			f(t, func(s []string) []string {
+				return firstUniqueMap(s).([]string)
+			}, testCase.in, testCase.out)
+		})
+	}
+}
+
+func Benchmark_firstUnique(b *testing.B) {
+	implementations := []struct {
+		name string
+		f    func([]string) []string
+	}{
+		{
+			name: "list",
+			f: func(slice []string) []string {
+				return firstUniqueList(slice).([]string)
+			},
+		},
+		{
+			name: "map",
+			f: func(slice []string) []string {
+				return firstUniqueMap(slice).([]string)
+			},
+		},
+		{
+			name: "optimal",
+			f: func(slice []string) []string {
+				return firstUnique(slice).([]string)
+			},
+		},
+	}
+	const maxSize = 1024
+	uniqueStrings := make([]string, maxSize)
+	for i := range uniqueStrings {
+		uniqueStrings[i] = strconv.Itoa(i)
+	}
+	sameString := make([]string, maxSize)
+	for i := range sameString {
+		sameString[i] = uniqueStrings[0]
+	}
+
+	f := func(b *testing.B, imp func([]string) []string, s []string) {
+		for i := 0; i < b.N; i++ {
+			b.ReportAllocs()
+			s = append([]string(nil), s...)
+			imp(s)
+		}
+	}
+
+	for n := 1; n <= maxSize; n <<= 1 {
+		b.Run(strconv.Itoa(n), func(b *testing.B) {
+			for _, implementation := range implementations {
+				b.Run(implementation.name, func(b *testing.B) {
+					b.Run("same", func(b *testing.B) {
+						f(b, implementation.f, sameString[:n])
+					})
+					b.Run("unique", func(b *testing.B) {
+						f(b, implementation.f, uniqueStrings[:n])
+					})
+				})
+			}
+		})
+	}
+}
diff --git a/android/util_test.go b/android/util_test.go
index 25b52ca..fa26c77 100644
--- a/android/util_test.go
+++ b/android/util_test.go
@@ -593,6 +593,10 @@
 			name: "map",
 			f:    firstUniqueStringsMap,
 		},
+		{
+			name: "optimal",
+			f:    FirstUniqueStrings,
+		},
 	}
 	const maxSize = 1024
 	uniqueStrings := make([]string, maxSize)
diff --git a/androidmk/parser/make_strings.go b/androidmk/parser/make_strings.go
index 4b782a2..3c4815e 100644
--- a/androidmk/parser/make_strings.go
+++ b/androidmk/parser/make_strings.go
@@ -15,8 +15,10 @@
 package parser
 
 import (
+	"fmt"
 	"strings"
 	"unicode"
+	"unicode/utf8"
 )
 
 // A MakeString is a string that may contain variable substitutions in it.
@@ -130,8 +132,85 @@
 	})
 }
 
+// Words splits MakeString into multiple makeStrings separated by whitespace.
+// Thus, " a $(X)b  c " will be split into ["a", "$(X)b", "c"].
+// Splitting a MakeString consisting solely of whitespace yields empty array.
 func (ms *MakeString) Words() []*MakeString {
-	return ms.splitNFunc(-1, splitWords)
+	var ch rune    // current character
+	const EOF = -1 // no more characters
+	const EOS = -2 // at the end of a string chunk
+
+	// Next character's chunk and position
+	iString := 0
+	iChar := 0
+
+	var words []*MakeString
+	word := SimpleMakeString("", ms.Pos())
+
+	nextChar := func() {
+		if iString >= len(ms.Strings) {
+			ch = EOF
+		} else if iChar >= len(ms.Strings[iString]) {
+			iString++
+			iChar = 0
+			ch = EOS
+		} else {
+			var w int
+			ch, w = utf8.DecodeRuneInString(ms.Strings[iString][iChar:])
+			iChar += w
+		}
+	}
+
+	appendVariableAndAdvance := func() {
+		if iString-1 < len(ms.Variables) {
+			word.appendVariable(ms.Variables[iString-1])
+		}
+		nextChar()
+	}
+
+	appendCharAndAdvance := func(c rune) {
+		if c != EOF {
+			word.appendString(string(c))
+		}
+		nextChar()
+	}
+
+	nextChar()
+	for ch != EOF {
+		// Skip whitespace
+		for ch == ' ' || ch == '\t' {
+			nextChar()
+		}
+		if ch == EOS {
+			// "... $(X)... " case. The current word should be empty.
+			if !word.Empty() {
+				panic(fmt.Errorf("%q: EOS while current word %q is not empty, iString=%d",
+					ms.Dump(), word.Dump(), iString))
+			}
+			appendVariableAndAdvance()
+		}
+		// Copy word
+		for ch != EOF {
+			if ch == ' ' || ch == '\t' {
+				words = append(words, word)
+				word = SimpleMakeString("", ms.Pos())
+				break
+			}
+			if ch == EOS {
+				// "...a$(X)..." case. Append variable to the current word
+				appendVariableAndAdvance()
+			} else {
+				if ch == '\\' {
+					appendCharAndAdvance('\\')
+				}
+				appendCharAndAdvance(ch)
+			}
+		}
+	}
+	if !word.Empty() {
+		words = append(words, word)
+	}
+	return words
 }
 
 func (ms *MakeString) splitNFunc(n int, splitFunc func(s string, n int) []string) []*MakeString {
@@ -166,9 +245,7 @@
 		}
 	}
 
-	if !curMs.Empty() {
-		ret = append(ret, curMs)
-	}
+	ret = append(ret, curMs)
 	return ret
 }
 
@@ -219,44 +296,6 @@
 	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 {
diff --git a/androidmk/parser/make_strings_test.go b/androidmk/parser/make_strings_test.go
index 6995e89..fbb289b 100644
--- a/androidmk/parser/make_strings_test.go
+++ b/androidmk/parser/make_strings_test.go
@@ -26,64 +26,53 @@
 	n        int
 }{
 	{
-		in: &MakeString{
-			Strings: []string{
-				"a b c",
-				"d e f",
-				" h i j",
-			},
-			Variables: []Variable{
-				Variable{Name: SimpleMakeString("var1", NoPos)},
-				Variable{Name: SimpleMakeString("var2", NoPos)},
-			},
-		},
+		// "a b c$(var1)d e f$(var2) h i j"
+		in:  genMakeString("a b c", "var1", "d e f", "var2", " h i j"),
 		sep: " ",
 		n:   -1,
 		expected: []*MakeString{
-			SimpleMakeString("a", NoPos),
-			SimpleMakeString("b", NoPos),
-			&MakeString{
-				Strings: []string{"c", "d"},
-				Variables: []Variable{
-					Variable{Name: SimpleMakeString("var1", NoPos)},
-				},
-			},
-			SimpleMakeString("e", NoPos),
-			&MakeString{
-				Strings: []string{"f", ""},
-				Variables: []Variable{
-					Variable{Name: SimpleMakeString("var2", NoPos)},
-				},
-			},
-			SimpleMakeString("h", NoPos),
-			SimpleMakeString("i", NoPos),
-			SimpleMakeString("j", NoPos),
+			genMakeString("a"),
+			genMakeString("b"),
+			genMakeString("c", "var1", "d"),
+			genMakeString("e"),
+			genMakeString("f", "var2", ""),
+			genMakeString("h"),
+			genMakeString("i"),
+			genMakeString("j"),
 		},
 	},
 	{
-		in: &MakeString{
-			Strings: []string{
-				"a b c",
-				"d e f",
-				" h i j",
-			},
-			Variables: []Variable{
-				Variable{Name: SimpleMakeString("var1", NoPos)},
-				Variable{Name: SimpleMakeString("var2", NoPos)},
-			},
-		},
+		// "a b c$(var1)d e f$(var2) h i j"
+		in:  genMakeString("a b c", "var1", "d e f", "var2", " h i j"),
 		sep: " ",
 		n:   3,
 		expected: []*MakeString{
-			SimpleMakeString("a", NoPos),
-			SimpleMakeString("b", NoPos),
-			&MakeString{
-				Strings: []string{"c", "d e f", " h i j"},
-				Variables: []Variable{
-					Variable{Name: SimpleMakeString("var1", NoPos)},
-					Variable{Name: SimpleMakeString("var2", NoPos)},
-				},
-			},
+			genMakeString("a"),
+			genMakeString("b"),
+			genMakeString("c", "var1", "d e f", "var2", " h i j"),
+		},
+	},
+	{
+		// "$(var1) $(var2)"
+		in:  genMakeString("", "var1", " ", "var2", ""),
+		sep: " ",
+		n:   -1,
+		expected: []*MakeString{
+			genMakeString("", "var1", ""),
+			genMakeString("", "var2", ""),
+		},
+	},
+	{
+		// "a,,b,c,"
+		in:  genMakeString("a,,b,c,"),
+		sep: ",",
+		n:   -1,
+		expected: []*MakeString{
+			genMakeString("a"),
+			genMakeString(""),
+			genMakeString("b"),
+			genMakeString("c"),
+			genMakeString(""),
 		},
 	},
 }
@@ -104,15 +93,15 @@
 	expected string
 }{
 	{
-		in:       SimpleMakeString("a b", NoPos),
+		in:       genMakeString("a b"),
 		expected: "a b",
 	},
 	{
-		in:       SimpleMakeString("a\\ \\\tb\\\\", NoPos),
+		in:       genMakeString("a\\ \\\tb\\\\"),
 		expected: "a \tb\\",
 	},
 	{
-		in:       SimpleMakeString("a\\b\\", NoPos),
+		in:       genMakeString("a\\b\\"),
 		expected: "a\\b\\",
 	},
 }
@@ -131,31 +120,88 @@
 	expected []*MakeString
 }{
 	{
-		in:       SimpleMakeString("", NoPos),
+		in:       genMakeString(""),
 		expected: []*MakeString{},
 	},
 	{
-		in: SimpleMakeString(" a b\\ c d", NoPos),
+		in: genMakeString(` a b\ c d`),
 		expected: []*MakeString{
-			SimpleMakeString("a", NoPos),
-			SimpleMakeString("b\\ c", NoPos),
-			SimpleMakeString("d", NoPos),
+			genMakeString("a"),
+			genMakeString(`b\ c`),
+			genMakeString("d"),
 		},
 	},
 	{
-		in: SimpleMakeString("  a\tb\\\t\\ c d  ", NoPos),
+		in: SimpleMakeString("  a\tb"+`\`+"\t"+`\ c d  `, NoPos),
 		expected: []*MakeString{
-			SimpleMakeString("a", NoPos),
-			SimpleMakeString("b\\\t\\ c", NoPos),
-			SimpleMakeString("d", NoPos),
+			genMakeString("a"),
+			genMakeString("b" + `\` + "\t" + `\ c`),
+			genMakeString("d"),
 		},
 	},
 	{
-		in: SimpleMakeString(`a\\ b\\\ c d`, NoPos),
+		in: genMakeString(`a\\ b\\\ c d`),
 		expected: []*MakeString{
-			SimpleMakeString(`a\\`, NoPos),
-			SimpleMakeString(`b\\\ c`, NoPos),
-			SimpleMakeString("d", NoPos),
+			genMakeString(`a\\`),
+			genMakeString(`b\\\ c`),
+			genMakeString("d"),
+		},
+	},
+	{
+		in: genMakeString(`\\ a`),
+		expected: []*MakeString{
+			genMakeString(`\\`),
+			genMakeString("a"),
+		},
+	},
+	{
+		// "  "
+		in: &MakeString{
+			Strings:   []string{" \t \t"},
+			Variables: nil,
+		},
+		expected: []*MakeString{},
+	},
+	{
+		// " a $(X)b c "
+		in: genMakeString(" a ", "X", "b c "),
+		expected: []*MakeString{
+			genMakeString("a"),
+			genMakeString("", "X", "b"),
+			genMakeString("c"),
+		},
+	},
+	{
+		// " a b$(X)c d"
+		in: genMakeString(" a b", "X", "c d"),
+		expected: []*MakeString{
+			genMakeString("a"),
+			genMakeString("b", "X", "c"),
+			genMakeString("d"),
+		},
+	},
+	{
+		// "$(X) $(Y)"
+		in: genMakeString("", "X", " ", "Y", ""),
+		expected: []*MakeString{
+			genMakeString("", "X", ""),
+			genMakeString("", "Y", ""),
+		},
+	},
+	{
+		// " a$(X) b"
+		in: genMakeString(" a", "X", " b"),
+		expected: []*MakeString{
+			genMakeString("a", "X", ""),
+			genMakeString("b"),
+		},
+	},
+	{
+		// "a$(X) b$(Y) "
+		in: genMakeString("a", "X", " b", "Y", " "),
+		expected: []*MakeString{
+			genMakeString("a", "X", ""),
+			genMakeString("b", "Y", ""),
 		},
 	},
 }
@@ -180,3 +226,20 @@
 
 	return strings.Join(ret, "|||")
 }
+
+// generates MakeString from alternating string chunks and variable names,
+// e.g., genMakeString("a", "X", "b") returns MakeString for "a$(X)b"
+func genMakeString(items ...string) *MakeString {
+	n := len(items) / 2
+	if len(items) != (2*n + 1) {
+		panic("genMakeString expects odd number of arguments")
+	}
+
+	ms := &MakeString{Strings: make([]string, n+1), Variables: make([]Variable, n)}
+	ms.Strings[0] = items[0]
+	for i := 1; i <= n; i++ {
+		ms.Variables[i-1] = Variable{Name: SimpleMakeString(items[2*i-1], NoPos)}
+		ms.Strings[i] = items[2*i]
+	}
+	return ms
+}
diff --git a/apex/allowed_deps.txt b/apex/allowed_deps.txt
index 5b8563d..b416d31 100644
--- a/apex/allowed_deps.txt
+++ b/apex/allowed_deps.txt
@@ -333,6 +333,7 @@
 libminijail_gen_syscall_obj(minSdkVersion:29)
 libminijail_generated(minSdkVersion:29)
 libmkvextractor(minSdkVersion:29)
+libmodules-utils-build(minSdkVersion:29)
 libmp3extractor(minSdkVersion:29)
 libmp4extractor(minSdkVersion:29)
 libmpeg2dec(minSdkVersion:29)
diff --git a/cmd/soong_build/writedocs.go b/cmd/soong_build/writedocs.go
index 5fb6e6b..253979e 100644
--- a/cmd/soong_build/writedocs.go
+++ b/cmd/soong_build/writedocs.go
@@ -44,9 +44,10 @@
 	"name":             0,
 	"src":              1,
 	"srcs":             2,
-	"defaults":         3,
-	"host_supported":   4,
-	"device_supported": 5,
+	"exclude_srcs":     3,
+	"defaults":         4,
+	"host_supported":   5,
+	"device_supported": 6,
 }
 
 // For each module type, extract its documentation and convert it to the template data.
diff --git a/java/dexpreopt_bootjars.go b/java/dexpreopt_bootjars.go
index da7f291..062005b 100644
--- a/java/dexpreopt_bootjars.go
+++ b/java/dexpreopt_bootjars.go
@@ -418,43 +418,53 @@
 	dumpOatRules(ctx, d.defaultBootImage)
 }
 
-func isHostdex(module android.Module) bool {
-	if lib, ok := module.(*Library); ok {
-		return Bool(lib.deviceProperties.Hostdex)
-	}
-	return false
-}
-
 // Inspect this module to see if it contains a bootclasspath dex jar.
 // Note that the same jar may occur in multiple modules.
 // This logic is tested in the apex package to avoid import cycle apex <-> java.
 func getBootImageJar(ctx android.SingletonContext, image *bootImageConfig, module android.Module) (int, android.Path) {
-	// All apex Java libraries have non-installable platform variants, skip them.
-	if module.IsSkipInstall() {
-		return -1, nil
-	}
-
-	jar, hasJar := module.(interface{ DexJarBuildPath() android.Path })
-	if !hasJar {
-		return -1, nil
-	}
-
+	// Ignore any module that is not listed in the boot image configuration.
 	name := ctx.ModuleName(module)
 	index := image.modules.IndexOfJar(name)
 	if index == -1 {
 		return -1, nil
 	}
 
-	// Check that this module satisfies constraints for a particular boot image.
-	_, isApexModule := module.(android.ApexModule)
+	// It is an error if a module configured in the boot image does not support
+	// accessing the dex jar. This is safe because every module that has the same
+	// name has to have the same module type.
+	jar, hasJar := module.(interface{ DexJarBuildPath() android.Path })
+	if !hasJar {
+		ctx.Errorf("module %q configured in boot image %q does not support accessing dex jar", module, image.name)
+		return -1, nil
+	}
+
+	// It is also an error if the module is not an ApexModule.
+	if _, ok := module.(android.ApexModule); !ok {
+		ctx.Errorf("module %q configured in boot image %q does not support being added to an apex", module, image.name)
+		return -1, nil
+	}
+
 	apexInfo := ctx.ModuleProvider(module, android.ApexInfoProvider).(android.ApexInfo)
-	fromUpdatableApex := isApexModule && apexInfo.Updatable
-	if image.name == artBootImageName {
-		if isApexModule && len(apexInfo.InApexes) > 0 && allHavePrefix(apexInfo.InApexes, "com.android.art") {
-			// ok: found the jar in the ART apex
-		} else if isApexModule && apexInfo.IsForPlatform() && isHostdex(module) {
-			// exception (skip and continue): special "hostdex" platform variant
+
+	// Now match the apex part of the boot image configuration.
+	requiredApex := image.modules.Apex(index)
+	if requiredApex == "platform" {
+		if len(apexInfo.InApexes) != 0 {
+			// A platform variant is required but this is for an apex so ignore it.
 			return -1, nil
+		}
+	} else if !android.InList(requiredApex, apexInfo.InApexes) {
+		// An apex variant for a specific apex is required but this is the wrong apex.
+		return -1, nil
+	}
+
+	// Check that this module satisfies any boot image specific constraints.
+	fromUpdatableApex := apexInfo.Updatable
+
+	switch image.name {
+	case artBootImageName:
+		if len(apexInfo.InApexes) > 0 && allHavePrefix(apexInfo.InApexes, "com.android.art") {
+			// ok: found the jar in the ART apex
 		} else if name == "jacocoagent" && ctx.Config().IsEnvTrue("EMMA_INSTRUMENT_FRAMEWORK") {
 			// exception (skip and continue): Jacoco platform variant for a coverage build
 			return -1, nil
@@ -465,14 +475,15 @@
 			// error: this jar is part of the platform or a non-updatable apex
 			ctx.Errorf("module %q is not allowed in the ART boot image", name)
 		}
-	} else if image.name == frameworkBootImageName {
+
+	case frameworkBootImageName:
 		if !fromUpdatableApex {
 			// ok: this jar is part of the platform or a non-updatable apex
 		} else {
 			// error: this jar is part of an updatable apex
 			ctx.Errorf("module %q from updatable apexes %q is not allowed in the framework boot image", name, apexInfo.InApexes)
 		}
-	} else {
+	default:
 		panic("unknown boot image: " + image.name)
 	}
 
@@ -495,6 +506,12 @@
 	bootDexJars := make(android.Paths, image.modules.Len())
 	ctx.VisitAllModules(func(module android.Module) {
 		if i, j := getBootImageJar(ctx, image, module); i != -1 {
+			if existing := bootDexJars[i]; existing != nil {
+				ctx.Errorf("Multiple dex jars found for %s:%s - %s and %s",
+					image.modules.Apex(i), image.modules.Jar(i), existing, j)
+				return
+			}
+
 			bootDexJars[i] = j
 		}
 	})
diff --git a/rust/project_json.go b/rust/project_json.go
index c4d60ad..32ce6f4 100644
--- a/rust/project_json.go
+++ b/rust/project_json.go
@@ -45,10 +45,11 @@
 }
 
 type rustProjectCrate struct {
-	RootModule string           `json:"root_module"`
-	Edition    string           `json:"edition,omitempty"`
-	Deps       []rustProjectDep `json:"deps"`
-	Cfgs       []string         `json:"cfgs"`
+	DisplayName string           `json:"display_name"`
+	RootModule  string           `json:"root_module"`
+	Edition     string           `json:"edition,omitempty"`
+	Deps        []rustProjectDep `json:"deps"`
+	Cfgs        []string         `json:"cfgs"`
 }
 
 type rustProjectJson struct {
@@ -58,13 +59,13 @@
 
 // crateInfo is used during the processing to keep track of the known crates.
 type crateInfo struct {
-	ID   int
-	Deps map[string]int
+	Idx  int            // Index of the crate in rustProjectJson.Crates slice.
+	Deps map[string]int // The keys are the module names and not the crate names.
 }
 
 type projectGeneratorSingleton struct {
 	project     rustProjectJson
-	knownCrates map[string]crateInfo
+	knownCrates map[string]crateInfo // Keys are module names.
 }
 
 func rustProjectGeneratorSingleton() android.Singleton {
@@ -75,66 +76,129 @@
 	android.RegisterSingletonType("rust_project_generator", rustProjectGeneratorSingleton)
 }
 
-// crateSource finds the main source file (.rs) for a crate.
-func crateSource(ctx android.SingletonContext, rModule *Module, comp *baseCompiler) (string, bool) {
-	srcs := comp.Properties.Srcs
-	if len(srcs) != 0 {
-		return path.Join(ctx.ModuleDir(rModule), srcs[0]), true
-	}
+// sourceProviderVariantSource returns the path to the source file if this
+// module variant should be used as a priority.
+//
+// SourceProvider modules may have multiple variants considered as source
+// (e.g., x86_64 and armv8). For a module available on device, use the source
+// generated for the target. For a host-only module, use the source generated
+// for the host.
+func sourceProviderVariantSource(ctx android.SingletonContext, rModule *Module) (string, bool) {
 	rustLib, ok := rModule.compiler.(*libraryDecorator)
 	if !ok {
 		return "", false
 	}
-	if !rustLib.source() {
-		return "", false
-	}
-	// It is a SourceProvider module. If this module is host only, uses the variation for the host.
-	// Otherwise, use the variation for the primary target.
-	switch rModule.hod {
-	case android.HostSupported:
-	case android.HostSupportedNoCross:
-		if rModule.Target().String() != ctx.Config().BuildOSTarget.String() {
-			return "", false
-		}
-	default:
-		if rModule.Target().String() != ctx.Config().AndroidFirstDeviceTarget.String() {
-			return "", false
+	if rustLib.source() {
+		switch rModule.hod {
+		case android.HostSupported, android.HostSupportedNoCross:
+			if rModule.Target().String() == ctx.Config().BuildOSTarget.String() {
+				src := rustLib.sourceProvider.Srcs()[0]
+				return src.String(), true
+			}
+		default:
+			if rModule.Target().String() == ctx.Config().AndroidFirstDeviceTarget.String() {
+				src := rustLib.sourceProvider.Srcs()[0]
+				return src.String(), true
+			}
 		}
 	}
-	src := rustLib.sourceProvider.Srcs()[0]
-	return src.String(), true
+	return "", false
 }
 
-func (singleton *projectGeneratorSingleton) mergeDependencies(ctx android.SingletonContext,
-	module android.Module, crate *rustProjectCrate, deps map[string]int) {
-
-	ctx.VisitDirectDeps(module, func(child android.Module) {
-		childId, childCrateName, ok := singleton.appendLibraryAndDeps(ctx, child)
-		if !ok {
+// sourceProviderSource finds the main source file of a source-provider crate.
+func sourceProviderSource(ctx android.SingletonContext, rModule *Module) (string, bool) {
+	rustLib, ok := rModule.compiler.(*libraryDecorator)
+	if !ok {
+		return "", false
+	}
+	if rustLib.source() {
+		// This is a source-variant, check if we are the right variant
+		// depending on the module configuration.
+		if src, ok := sourceProviderVariantSource(ctx, rModule); ok {
+			return src, true
+		}
+	}
+	foundSource := false
+	sourceSrc := ""
+	// Find the variant with the source and return its.
+	ctx.VisitAllModuleVariants(rModule, func(variant android.Module) {
+		if foundSource {
 			return
 		}
+		// All variants of a source provider library are libraries.
+		rVariant, _ := variant.(*Module)
+		variantLib, _ := rVariant.compiler.(*libraryDecorator)
+		if variantLib.source() {
+			sourceSrc, ok = sourceProviderVariantSource(ctx, rVariant)
+			if ok {
+				foundSource = true
+			}
+		}
+	})
+	if !foundSource {
+		fmt.Errorf("No valid source for source provider found: %v\n", rModule)
+	}
+	return sourceSrc, foundSource
+}
+
+// crateSource finds the main source file (.rs) for a crate.
+func crateSource(ctx android.SingletonContext, rModule *Module, comp *baseCompiler) (string, bool) {
+	// Basic libraries, executables and tests.
+	srcs := comp.Properties.Srcs
+	if len(srcs) != 0 {
+		return path.Join(ctx.ModuleDir(rModule), srcs[0]), true
+	}
+	// SourceProvider libraries.
+	if rModule.sourceProvider != nil {
+		return sourceProviderSource(ctx, rModule)
+	}
+	return "", false
+}
+
+// mergeDependencies visits all the dependencies for module and updates crate and deps
+// with any new dependency.
+func (singleton *projectGeneratorSingleton) mergeDependencies(ctx android.SingletonContext,
+	module *Module, crate *rustProjectCrate, deps map[string]int) {
+
+	ctx.VisitDirectDeps(module, func(child android.Module) {
 		// Skip intra-module dependencies (i.e., generated-source library depending on the source variant).
 		if module.Name() == child.Name() {
 			return
 		}
-		if _, ok = deps[ctx.ModuleName(child)]; ok {
+		// Skip unsupported modules.
+		rChild, compChild, ok := isModuleSupported(ctx, child)
+		if !ok {
 			return
 		}
-		crate.Deps = append(crate.Deps, rustProjectDep{Crate: childId, Name: childCrateName})
-		deps[ctx.ModuleName(child)] = childId
+		// For unknown dependency, add it first.
+		var childId int
+		cInfo, known := singleton.knownCrates[rChild.Name()]
+		if !known {
+			childId, ok = singleton.addCrate(ctx, rChild, compChild)
+			if !ok {
+				return
+			}
+		} else {
+			childId = cInfo.Idx
+		}
+		// Is this dependency known already?
+		if _, ok = deps[child.Name()]; ok {
+			return
+		}
+		crate.Deps = append(crate.Deps, rustProjectDep{Crate: childId, Name: rChild.CrateName()})
+		deps[child.Name()] = childId
 	})
 }
 
-// appendLibraryAndDeps creates a rustProjectCrate for the module argument and appends it to singleton.project.
-// It visits the dependencies of the module depth-first so the dependency ID can be added to the current module. If the
-// current module is already in singleton.knownCrates, its dependencies are merged. Returns a tuple (id, crate_name, ok).
-func (singleton *projectGeneratorSingleton) appendLibraryAndDeps(ctx android.SingletonContext, module android.Module) (int, string, bool) {
+// isModuleSupported returns the RustModule and baseCompiler if the module
+// should be considered for inclusion in rust-project.json.
+func isModuleSupported(ctx android.SingletonContext, module android.Module) (*Module, *baseCompiler, bool) {
 	rModule, ok := module.(*Module)
 	if !ok {
-		return 0, "", false
+		return nil, nil, false
 	}
 	if rModule.compiler == nil {
-		return 0, "", false
+		return nil, nil, false
 	}
 	var comp *baseCompiler
 	switch c := rModule.compiler.(type) {
@@ -145,35 +209,57 @@
 	case *testDecorator:
 		comp = c.binaryDecorator.baseCompiler
 	default:
-		return 0, "", false
+		return nil, nil, false
 	}
-	moduleName := ctx.ModuleName(module)
-	crateName := rModule.CrateName()
-	if cInfo, ok := singleton.knownCrates[moduleName]; ok {
-		// We have seen this crate already; merge any new dependencies.
-		crate := singleton.project.Crates[cInfo.ID]
-		singleton.mergeDependencies(ctx, module, &crate, cInfo.Deps)
-		singleton.project.Crates[cInfo.ID] = crate
-		return cInfo.ID, crateName, true
-	}
-	crate := rustProjectCrate{Deps: make([]rustProjectDep, 0), Cfgs: make([]string, 0)}
+	return rModule, comp, true
+}
+
+// addCrate adds a crate to singleton.project.Crates ensuring that required
+// dependencies are also added. It returns the index of the new crate in
+// singleton.project.Crates
+func (singleton *projectGeneratorSingleton) addCrate(ctx android.SingletonContext, rModule *Module, comp *baseCompiler) (int, bool) {
 	rootModule, ok := crateSource(ctx, rModule, comp)
 	if !ok {
-		return 0, "", false
+		fmt.Errorf("Unable to find source for valid module: %v", rModule)
+		return 0, false
 	}
-	crate.RootModule = rootModule
-	crate.Edition = comp.edition()
+
+	crate := rustProjectCrate{
+		DisplayName: rModule.Name(),
+		RootModule:  rootModule,
+		Edition:     comp.edition(),
+		Deps:        make([]rustProjectDep, 0),
+		Cfgs:        make([]string, 0),
+	}
 
 	deps := make(map[string]int)
-	singleton.mergeDependencies(ctx, module, &crate, deps)
+	singleton.mergeDependencies(ctx, rModule, &crate, deps)
 
-	id := len(singleton.project.Crates)
-	singleton.knownCrates[moduleName] = crateInfo{ID: id, Deps: deps}
+	idx := len(singleton.project.Crates)
+	singleton.knownCrates[rModule.Name()] = crateInfo{Idx: idx, Deps: deps}
 	singleton.project.Crates = append(singleton.project.Crates, crate)
 	// rust-analyzer requires that all crates belong to at least one root:
 	// https://github.com/rust-analyzer/rust-analyzer/issues/4735.
 	singleton.project.Roots = append(singleton.project.Roots, path.Dir(crate.RootModule))
-	return id, crateName, true
+	return idx, true
+}
+
+// appendCrateAndDependencies creates a rustProjectCrate for the module argument and appends it to singleton.project.
+// It visits the dependencies of the module depth-first so the dependency ID can be added to the current module. If the
+// current module is already in singleton.knownCrates, its dependencies are merged.
+func (singleton *projectGeneratorSingleton) appendCrateAndDependencies(ctx android.SingletonContext, module android.Module) {
+	rModule, comp, ok := isModuleSupported(ctx, module)
+	if !ok {
+		return
+	}
+	// If we have seen this crate already; merge any new dependencies.
+	if cInfo, ok := singleton.knownCrates[module.Name()]; ok {
+		crate := singleton.project.Crates[cInfo.Idx]
+		singleton.mergeDependencies(ctx, rModule, &crate, cInfo.Deps)
+		singleton.project.Crates[cInfo.Idx] = crate
+		return
+	}
+	singleton.addCrate(ctx, rModule, comp)
 }
 
 func (singleton *projectGeneratorSingleton) GenerateBuildActions(ctx android.SingletonContext) {
@@ -183,7 +269,7 @@
 
 	singleton.knownCrates = make(map[string]crateInfo)
 	ctx.VisitAllModules(func(module android.Module) {
-		singleton.appendLibraryAndDeps(ctx, module)
+		singleton.appendCrateAndDependencies(ctx, module)
 	})
 
 	path := android.PathForOutput(ctx, rustProjectJsonFileName)
diff --git a/rust/project_json_test.go b/rust/project_json_test.go
index aff1697..ba66215 100644
--- a/rust/project_json_test.go
+++ b/rust/project_json_test.go
@@ -119,9 +119,9 @@
 func TestProjectJsonBinary(t *testing.T) {
 	bp := `
 	rust_binary {
-		name: "liba",
-		srcs: ["a/src/lib.rs"],
-		crate_name: "a"
+		name: "libz",
+		srcs: ["z/src/lib.rs"],
+		crate_name: "z"
 	}
 	`
 	jsonContent := testProjectJson(t, bp)
@@ -132,7 +132,7 @@
 		if !ok {
 			t.Fatalf("Unexpected type for root_module: %v", crate["root_module"])
 		}
-		if rootModule == "a/src/lib.rs" {
+		if rootModule == "z/src/lib.rs" {
 			return
 		}
 	}
@@ -142,10 +142,10 @@
 func TestProjectJsonBindGen(t *testing.T) {
 	bp := `
 	rust_library {
-		name: "liba",
-		srcs: ["src/lib.rs"],
+		name: "libd",
+		srcs: ["d/src/lib.rs"],
 		rlibs: ["libbindings1"],
-		crate_name: "a"
+		crate_name: "d"
 	}
 	rust_bindgen {
 		name: "libbindings1",
@@ -155,10 +155,10 @@
 		wrapper_src: "src/any.h",
 	}
 	rust_library_host {
-		name: "libb",
-		srcs: ["src/lib.rs"],
+		name: "libe",
+		srcs: ["e/src/lib.rs"],
 		rustlibs: ["libbindings2"],
-		crate_name: "b"
+		crate_name: "e"
 	}
 	rust_bindgen_host {
 		name: "libbindings2",
@@ -190,6 +190,19 @@
 				}
 			}
 		}
+		// Check that liba depends on libbindings1
+		if strings.Contains(rootModule, "d/src/lib.rs") {
+			found := false
+			for _, depName := range validateDependencies(t, crate) {
+				if depName == "bindings1" {
+					found = true
+					break
+				}
+			}
+			if !found {
+				t.Errorf("liba does not depend on libbindings1: %v", crate)
+			}
+		}
 	}
 }