Inline singleton pieces in `NestedSet#splitIfExceedsMaximumSize`.

When splitting a `NestedSet` whose successor count is not evenly divisible
by `maxDegree`, the final piece would previously be stored as a single-element
`Object[]`. When added as a transitive member to a new `NestedSet`, this violated the invariant that non-leaf transitive arrays have length >= 2.

Fix by directly inlining singleton pieces into the pieces array.

PiperOrigin-RevId: 971463001
Change-Id: If49958361412fbe45a9e35b2670d310f6147b645

src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java

diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
index ce6fe3c..76daac3 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
@@ -685,15 +685,19 @@
     if (nsuccs <= maxDegree) {
       return this;
     }
-    Object[][] pieces = new Object[ceildiv(nsuccs, maxDegree)][];
+    Object[] pieces = new Object[ceildiv(nsuccs, maxDegree)];
     for (int i = 0; i < pieces.length; i++) {
-      int max = Math.min((i + 1) * maxDegree, succs.length);
-      pieces[i] = Arrays.copyOfRange(succs, i * maxDegree, max);
+      int start = i * maxDegree;
+      int end = Math.min(start + maxDegree, succs.length);
+      if (end - start == 1) {
+        // We cannot have non-leaves of size 1, so inline the singleton.
+        pieces[i] = succs[start];
+      } else {
+        pieces[i] = Arrays.copyOfRange(succs, start, end);
+      }
     }
     int depth = getApproxDepth() + 1; // may be an overapproximation
 
-    // TODO(adonovan): (preexisting): if the last piece is a singleton, it must be inlined.
-
     // Each piece is now smaller than maxDegree, but there may be many pieces.
     // Recursively split pieces. (The recursion affects only the root; it
     // does not traverse into successors.) In practice, maxDegree is large

src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
index a736e41..7fdde6a 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
@@ -168,6 +168,17 @@
     assertThat(s.getApproxDepth()).isEqualTo(4);
   }
 
+  @Test
+  public void split_singletonPieceInlined() {
+    NestedSet<String> set =
+        NestedSetBuilder.<String>stableOrder().addAll(Arrays.asList("a", "b", "c")).build();
+    NestedSet<String> split = set.splitIfExceedsMaximumSize(2);
+    Object[] children = (Object[]) split.getChildren();
+    assertThat(children).hasLength(2);
+    assertThat(children[0]).isEqualTo(new Object[] {"a", "b"});
+    assertThat(children[1]).isEqualTo("c"); // Singleton becomes a leaf.
+  }
+
   private static <T> List<T> collectCheckSize(NestedSet<T> set, int maxSize) {
     return collectCheckSize(new ArrayList<>(), set, maxSize);
   }