diff --git a/android/depset_generic.go b/android/depset_generic.go
index d04f88b..6dab3b3 100644
--- a/android/depset_generic.go
+++ b/android/depset_generic.go
@@ -16,6 +16,8 @@
 
 import (
 	"fmt"
+	"iter"
+	"slices"
 
 	"github.com/google/blueprint"
 )
@@ -60,11 +62,24 @@
 // 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.
 type DepSet[T depSettableType] struct {
+	handle *depSet[T]
+}
+
+type depSet[T depSettableType] struct {
 	preorder   bool
 	reverse    bool
 	order      DepSetOrder
 	direct     []T
-	transitive []*DepSet[T]
+	transitive []DepSet[T]
+}
+
+func (d DepSet[T]) impl() *depSet[T] {
+	return d.handle
+}
+
+func (d DepSet[T]) order() DepSetOrder {
+	impl := d.impl()
+	return impl.order
 }
 
 type depSetGob[T depSettableType] struct {
@@ -72,25 +87,28 @@
 	Reverse    bool
 	Order      DepSetOrder
 	Direct     []T
-	Transitive []*DepSet[T]
+	Transitive []DepSet[T]
 }
 
 func (d *DepSet[T]) ToGob() *depSetGob[T] {
+	impl := d.impl()
 	return &depSetGob[T]{
-		Preorder:   d.preorder,
-		Reverse:    d.reverse,
-		Order:      d.order,
-		Direct:     d.direct,
-		Transitive: d.transitive,
+		Preorder:   impl.preorder,
+		Reverse:    impl.reverse,
+		Order:      impl.order,
+		Direct:     impl.direct,
+		Transitive: impl.transitive,
 	}
 }
 
 func (d *DepSet[T]) FromGob(data *depSetGob[T]) {
-	d.preorder = data.Preorder
-	d.reverse = data.Reverse
-	d.order = data.Order
-	d.direct = data.Direct
-	d.transitive = data.Transitive
+	d.handle = &depSet[T]{
+		preorder:   data.Preorder,
+		reverse:    data.Reverse,
+		order:      data.Order,
+		direct:     data.Direct,
+		transitive: data.Transitive,
+	}
 }
 
 func (d *DepSet[T]) GobEncode() ([]byte, error) {
@@ -102,40 +120,59 @@
 }
 
 // NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
-func NewDepSet[T depSettableType](order DepSetOrder, direct []T, transitive []*DepSet[T]) *DepSet[T] {
+func NewDepSet[T depSettableType](order DepSetOrder, direct []T, transitive []DepSet[T]) DepSet[T] {
 	var directCopy []T
-	var transitiveCopy []*DepSet[T]
+	var transitiveCopy []DepSet[T]
+	nonEmptyTransitiveCount := 0
 	for _, t := range transitive {
-		if t.order != order {
-			panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
-				order, t.order))
+		if t.handle != nil {
+			if t.order() != order {
+				panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
+					order, t.order()))
+			}
+			nonEmptyTransitiveCount++
 		}
 	}
 
+	if nonEmptyTransitiveCount > 0 {
+		transitiveCopy = make([]DepSet[T], 0, nonEmptyTransitiveCount)
+	}
+	var transitiveIter iter.Seq2[int, DepSet[T]]
 	if order == TOPOLOGICAL {
 		// TOPOLOGICAL is implemented as a postorder traversal followed by reversing the output.
 		// Pre-reverse the inputs here so their order is maintained in the output.
 		directCopy = ReverseSlice(direct)
-		transitiveCopy = ReverseSlice(transitive)
+		transitiveIter = slices.Backward(transitive)
 	} else {
-		directCopy = append([]T(nil), direct...)
-		transitiveCopy = append([]*DepSet[T](nil), transitive...)
+		directCopy = slices.Clone(direct)
+		transitiveIter = slices.All(transitive)
+	}
+	for _, t := range transitiveIter {
+		if t.handle != nil {
+			transitiveCopy = append(transitiveCopy, t)
+		}
 	}
 
-	return &DepSet[T]{
+	if len(directCopy) == 0 && len(transitive) == 0 {
+		return DepSet[T]{nil}
+	}
+
+	depSet := &depSet[T]{
 		preorder:   order == PREORDER,
 		reverse:    order == TOPOLOGICAL,
 		order:      order,
 		direct:     directCopy,
 		transitive: transitiveCopy,
 	}
+
+	return DepSet[T]{depSet}
 }
 
 // DepSetBuilder is used to create an immutable DepSet.
 type DepSetBuilder[T depSettableType] struct {
 	order      DepSetOrder
 	direct     []T
-	transitive []*DepSet[T]
+	transitive []DepSet[T]
 }
 
 // NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order and
@@ -162,11 +199,11 @@
 
 // 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[T]) Transitive(transitive ...*DepSet[T]) *DepSetBuilder[T] {
+func (b *DepSetBuilder[T]) Transitive(transitive ...DepSet[T]) *DepSetBuilder[T] {
 	for _, t := range transitive {
-		if t.order != b.order {
+		if t.handle != nil && t.order() != b.order {
 			panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
-				b.order, t.order))
+				b.order, t.order()))
 		}
 	}
 	b.transitive = append(b.transitive, transitive...)
@@ -175,29 +212,30 @@
 
 // Returns the DepSet being built by this DepSetBuilder.  The DepSetBuilder retains its contents
 // for creating more depSets.
-func (b *DepSetBuilder[T]) Build() *DepSet[T] {
+func (b *DepSetBuilder[T]) Build() DepSet[T] {
 	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[T]) walk(visit func([]T)) {
-	visited := make(map[*DepSet[T]]bool)
+func (d DepSet[T]) walk(visit func([]T)) {
+	visited := make(map[DepSet[T]]bool)
 
-	var dfs func(d *DepSet[T])
-	dfs = func(d *DepSet[T]) {
+	var dfs func(d DepSet[T])
+	dfs = func(d DepSet[T]) {
+		impl := d.impl()
 		visited[d] = true
-		if d.preorder {
-			visit(d.direct)
+		if impl.preorder {
+			visit(impl.direct)
 		}
-		for _, dep := range d.transitive {
+		for _, dep := range impl.transitive {
 			if !visited[dep] {
 				dfs(dep)
 			}
 		}
 
-		if !d.preorder {
-			visit(d.direct)
+		if !impl.preorder {
+			visit(impl.direct)
 		}
 	}
 
@@ -210,16 +248,17 @@
 // 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[T]) ToList() []T {
-	if d == nil {
+func (d DepSet[T]) ToList() []T {
+	if d.handle == nil {
 		return nil
 	}
+	impl := d.impl()
 	var list []T
 	d.walk(func(paths []T) {
 		list = append(list, paths...)
 	})
 	list = firstUniqueInPlace(list)
-	if d.reverse {
+	if impl.reverse {
 		ReverseSliceInPlace(list)
 	}
 	return list
diff --git a/android/depset_test.go b/android/depset_test.go
index 376dffa..46c5b99 100644
--- a/android/depset_test.go
+++ b/android/depset_test.go
@@ -63,12 +63,12 @@
 
 	tests := []struct {
 		name                             string
-		depSet                           func(t *testing.T, order DepSetOrder) *DepSet[Path]
+		depSet                           func(t *testing.T, order DepSetOrder) DepSet[Path]
 		postorder, preorder, topological []string
 	}{
 		{
 			name: "simple",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				return NewDepSet[Path](order, Paths{c, a, b}, nil)
 			},
 			postorder:   []string{"c", "a", "b"},
@@ -77,7 +77,7 @@
 		},
 		{
 			name: "simpleNoDuplicates",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				return NewDepSet[Path](order, Paths{c, a, a, a, b}, nil)
 			},
 			postorder:   []string{"c", "a", "b"},
@@ -86,9 +86,9 @@
 		},
 		{
 			name: "nesting",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				subset := NewDepSet[Path](order, Paths{c, a, e}, nil)
-				return NewDepSet[Path](order, Paths{b, d}, []*DepSet[Path]{subset})
+				return NewDepSet[Path](order, Paths{b, d}, []DepSet[Path]{subset})
 			},
 			postorder:   []string{"c", "a", "e", "b", "d"},
 			preorder:    []string{"b", "d", "c", "a", "e"},
@@ -96,7 +96,7 @@
 		},
 		{
 			name: "builderReuse",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				assertEquals := func(t *testing.T, w, g Paths) {
 					t.Helper()
 					if !reflect.DeepEqual(w, g) {
@@ -122,7 +122,7 @@
 		},
 		{
 			name: "builderChaining",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				return NewDepSetBuilder[Path](order).Direct(b).Direct(d).
 					Transitive(NewDepSetBuilder[Path](order).Direct(c, a, e).Build()).Build()
 			},
@@ -132,7 +132,7 @@
 		},
 		{
 			name: "transitiveDepsHandledSeparately",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				subset := NewDepSetBuilder[Path](order).Direct(c, a, e).Build()
 				builder := NewDepSetBuilder[Path](order)
 				// The fact that we add the transitive subset between the Direct(b) and Direct(d)
@@ -148,7 +148,7 @@
 		},
 		{
 			name: "nestingNoDuplicates",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				subset := NewDepSetBuilder[Path](order).Direct(c, a, e).Build()
 				return NewDepSetBuilder[Path](order).Direct(b, d, e).Transitive(subset).Build()
 			},
@@ -158,7 +158,7 @@
 		},
 		{
 			name: "chain",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				c := NewDepSetBuilder[Path](order).Direct(c).Build()
 				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(c).Build()
 				a := NewDepSetBuilder[Path](order).Direct(a).Transitive(b).Build()
@@ -171,7 +171,7 @@
 		},
 		{
 			name: "diamond",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				d := NewDepSetBuilder[Path](order).Direct(d).Build()
 				c := NewDepSetBuilder[Path](order).Direct(c).Transitive(d).Build()
 				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Build()
@@ -185,7 +185,7 @@
 		},
 		{
 			name: "extendedDiamond",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				d := NewDepSetBuilder[Path](order).Direct(d).Build()
 				e := NewDepSetBuilder[Path](order).Direct(e).Build()
 				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Transitive(e).Build()
@@ -199,7 +199,7 @@
 		},
 		{
 			name: "extendedDiamondRightArm",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				d := NewDepSetBuilder[Path](order).Direct(d).Build()
 				e := NewDepSetBuilder[Path](order).Direct(e).Build()
 				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Transitive(e).Build()
@@ -214,7 +214,7 @@
 		},
 		{
 			name: "orderConflict",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				child1 := NewDepSetBuilder[Path](order).Direct(a, b).Build()
 				child2 := NewDepSetBuilder[Path](order).Direct(b, a).Build()
 				parent := NewDepSetBuilder[Path](order).Transitive(child1).Transitive(child2).Build()
@@ -226,7 +226,7 @@
 		},
 		{
 			name: "orderConflictNested",
-			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
 				a := NewDepSetBuilder[Path](order).Direct(a).Build()
 				b := NewDepSetBuilder[Path](order).Direct(b).Build()
 				child1 := NewDepSetBuilder[Path](order).Transitive(a).Transitive(b).Build()
@@ -238,6 +238,18 @@
 			preorder:    []string{"a", "b"},
 			topological: []string{"b", "a"},
 		},
+		{
+			name: "zeroDepSet",
+			depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
+				a := NewDepSetBuilder[Path](order).Build()
+				var b DepSet[Path]
+				c := NewDepSetBuilder[Path](order).Direct(c).Transitive(a, b).Build()
+				return c
+			},
+			postorder:   []string{"c"},
+			preorder:    []string{"c"},
+			topological: []string{"c"},
+		},
 	}
 
 	for _, tt := range tests {
@@ -277,7 +289,7 @@
 				}
 			}
 		}()
-		NewDepSet(order1, nil, []*DepSet[Path]{NewDepSet[Path](order2, nil, nil)})
+		NewDepSet(order1, nil, []DepSet[Path]{NewDepSet[Path](order2, Paths{PathForTesting("a")}, nil)})
 		t.Fatal("expected panic")
 	}