In builders, track unset primitive properties with bitmasks rather than boxing.

Previously, an AutoValue property of type `int` was tracked by a field of type `Integer` in the builder. This was solely so that we could use `null` to indicate that the property had not been set. It meant that the memory footprint of a builder that sets primitive properties was bigger than you would expect.

AutoValue actually used a bitset for the same purposes in early versions. That was changed because GWT doesn't support `java.util.BitSet`. It does now, but anyway we now use primitive integer fields for the bitset since that is faster and more compact.

RELNOTES=AutoValue and AutoBuilder builders now use bitmasks to track unset primitive properties, which will typically lead to smaller builder objects and faster build times.
PiperOrigin-RevId: 420374999

7 files changed, 260 insertions, 40 deletions

diff --git a/value/src/main/java/com/google/auto/value/processor/AutoBuilderProcessor.java b/value/src/main/java/com/google/auto/value/processor/AutoBuilderProcessor.java
index fc0d8b3e..546da4ca 100644
--- a/value/src/main/java/com/google/auto/value/processor/AutoBuilderProcessor.java
+++ b/value/src/main/java/com/google/auto/value/processor/AutoBuilderProcessor.java
@@ -132,7 +132,6 @@ public class AutoBuilderProcessor extends AutoValueishProcessor {
     vars.builderName = TypeSimplifier.simpleNameOf(generatedClassName);
     vars.builtType = TypeEncoder.encode(builtType);
     vars.build = build(executable);
-    vars.types = typeUtils();
     vars.toBuilderConstructor = false;
     vars.toBuilderMethods = ImmutableList.of();
     defineSharedVarsForType(autoBuilderType, ImmutableSet.of(), vars);
diff --git a/value/src/main/java/com/google/auto/value/processor/AutoValueOrBuilderTemplateVars.java b/value/src/main/java/com/google/auto/value/processor/AutoValueOrBuilderTemplateVars.java
index 9fbc1652..eddb9ae2 100644
--- a/value/src/main/java/com/google/auto/value/processor/AutoValueOrBuilderTemplateVars.java
+++ b/value/src/main/java/com/google/auto/value/processor/AutoValueOrBuilderTemplateVars.java
@@ -22,8 +22,6 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
 import java.util.Optional;
-import javax.annotation.processing.ProcessingEnvironment;
-import javax.lang.model.util.Types;
 
 /**
  * Variables to substitute into the autovalue.vm or builder.vm template.
@@ -114,7 +112,7 @@ abstract class AutoValueOrBuilderTemplateVars extends AutoValueishTemplateVars {
    *   <li>it has a property-builder method (in which case it defaults to empty).
    * </ul>
    */
-  ImmutableSet<Property> builderRequiredProperties = ImmutableSet.of();
+  BuilderRequiredProperties builderRequiredProperties = BuilderRequiredProperties.EMPTY;
 
   /**
    * A map from property names to information about the associated property getter. A property
@@ -150,7 +148,4 @@ abstract class AutoValueOrBuilderTemplateVars extends AutoValueishTemplateVars {
    * subclasses)
    */
   Boolean isFinal = false;
-
-  /** The type utilities returned by {@link ProcessingEnvironment#getTypeUtils()}. */
-  Types types;
 }
diff --git a/value/src/main/java/com/google/auto/value/processor/AutoValueProcessor.java b/value/src/main/java/com/google/auto/value/processor/AutoValueProcessor.java
index 4479a056..7619db32 100644
--- a/value/src/main/java/com/google/auto/value/processor/AutoValueProcessor.java
+++ b/value/src/main/java/com/google/auto/value/processor/AutoValueProcessor.java
@@ -243,7 +243,6 @@ public class AutoValueProcessor extends AutoValueishProcessor {
 
     String finalSubclass = TypeSimplifier.simpleNameOf(generatedSubclassName(type, 0));
     AutoValueTemplateVars vars = new AutoValueTemplateVars();
-    vars.types = processingEnv.getTypeUtils();
     vars.identifiers = !processingEnv.getOptions().containsKey(OMIT_IDENTIFIERS_OPTION);
     defineSharedVarsForType(type, methods, vars);
     defineVarsForType(type, vars, toBuilderMethods, propertyMethodsAndTypes, builder);
diff --git a/value/src/main/java/com/google/auto/value/processor/AutoValueishProcessor.java b/value/src/main/java/com/google/auto/value/processor/AutoValueishProcessor.java
index 31f1ec1c..35f0fe5c 100644
--- a/value/src/main/java/com/google/auto/value/processor/AutoValueishProcessor.java
+++ b/value/src/main/java/com/google/auto/value/processor/AutoValueishProcessor.java
@@ -154,7 +154,7 @@ abstract class AutoValueishProcessor extends AbstractProcessor {
   }
 
   /**
-   * A property of an {@code @AutoValue} or {@code @AutoOneOf} class, defined by one of its abstract
+   * A property of an {@code @AutoValue} (etc) class, defined by one of its abstract
    * methods. An instance of this class is made available to the Velocity template engine for each
    * property. The public methods of this class define JavaBeans-style properties that are
    * accessible from templates. For example {@link #getType()} means we can write {@code $p.type}
@@ -231,7 +231,7 @@ abstract class AutoValueishProcessor extends AbstractProcessor {
       return name;
     }
 
-    public TypeMirror getTypeMirror() {
+    TypeMirror getTypeMirror() {
       return typeMirror;
     }
 
diff --git a/value/src/main/java/com/google/auto/value/processor/BuilderRequiredProperties.java b/value/src/main/java/com/google/auto/value/processor/BuilderRequiredProperties.java
new file mode 100644
index 00000000..ca1fd5ce
--- /dev/null
+++ b/value/src/main/java/com/google/auto/value/processor/BuilderRequiredProperties.java
@@ -0,0 +1,226 @@
+/*
+ * Copyright 2022 Google LLC
+ *
+ * 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 com.google.auto.value.processor;
+
+import static com.google.auto.common.MoreStreams.toImmutableList;
+import static com.google.auto.common.MoreStreams.toImmutableMap;
+import static java.util.stream.Collectors.joining;
+
+import com.google.auto.value.processor.AutoValueishProcessor.Property;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import java.util.stream.IntStream;
+import java.util.stream.Stream;
+
+/**
+ * Code generation to track which properties have been set in a builder.
+ *
+ * <p>Every property in an {@code @AutoValue} or {@code @AutoBuilder} builder must be set before the
+ * {@code build()} method is called, with a few exceptions like {@code @Nullable} and {@code
+ * Optional} properties. That means we must keep track of which ones have in fact been set. We do
+ * that in two ways: for reference (non-primitive) types, we use {@code null} to indicate that the
+ * value has not been set, while for primitive types we use a bitmask where each bit indicates
+ * whether a certain primitive property has been set.
+ *
+ * <p>The public methods in this class are accessed reflectively from the {@code builder.vm}
+ * template. In that template, {@code $builderRequiredProperties} references an instance of this
+ * class corresponding to the builder being generated. A reference like {@code
+ * $builderRequiredProperties.markAsSet($p)} calls the method {@link #markAsSet} with the given
+ * parameter. A reference like {@code $builderRequiredProperties.properties} is shorthand for {@link
+ * #getProperties() $builderRequiredProperties.getProperties()}.
+ */
+public final class BuilderRequiredProperties {
+  static final BuilderRequiredProperties EMPTY = new BuilderRequiredProperties(ImmutableSet.of());
+
+  /** All required properties. */
+  private final ImmutableSet<Property> properties;
+
+  /**
+   * The bit index for each primitive property. Primitive properties are numbered consecutively from
+   * 0. Non-primitive properties do not appear in this map.
+   */
+  private final ImmutableMap<Property, Integer> primitivePropertyToIndex;
+
+  /**
+   * The integer fields that store the bitmask. In the usual case, where there are ≤32 primitive
+   * properties, we can pack the bitmask into one integer field. Its type is the smallest one that
+   * fits the required number of bits, for example {@code byte} if there are ≤8 primitive
+   * properties.
+   *
+   * <p>If there are {@literal >32} primitive properties, we will pack them into as few integer
+   * fields as possible. For example if there are 75 primitive properties (this can happen) then we
+   * will put numbers 0 to 31 in an {@code int}, 32 to 63 in a second {@code int}, and 64 to 75 in a
+   * {@code short}.
+   *
+   * <p>When there are {@literal >32} primitive properties, we could potentially pack them better if
+   * we used {@code long}. But sometimes AutoValue code gets translated into JavaScript, which
+   * doesn't handle long values natively. By the time you have that many properties you are probably
+   * not going to notice the difference between 5 ints or 2 longs plus an int.
+   */
+  private final ImmutableList<BitmaskField> bitmaskFields;
+
+  /**
+   * Represents a field in which we will record which primitive properties from a certain set have
+   * been given a value.
+   */
+  private static class BitmaskField {
+    final Class<?> type;
+    final String name;
+    /**
+     * The source representation of the value this field has when all properties have been given a
+     * value.
+     */
+    final String allOnes;
+
+    BitmaskField(Class<?> type, String name, String allOnes) {
+      this.type = type;
+      this.name = name;
+      this.allOnes = allOnes;
+    }
+  }
+
+  BuilderRequiredProperties(ImmutableSet<Property> properties) {
+    this.properties = properties;
+
+    ImmutableList<Property> primitiveProperties =
+        properties.stream().filter(p -> p.getKind().isPrimitive()).collect(toImmutableList());
+    int primitiveCount = primitiveProperties.size();
+    this.primitivePropertyToIndex =
+        IntStream.range(0, primitiveCount)
+            .boxed()
+            .collect(toImmutableMap(primitiveProperties::get, i -> i));
+
+    this.bitmaskFields =
+        IntStream.range(0, (primitiveCount + 31) / 32)
+            .mapToObj(
+                i -> {
+                  int remain = primitiveCount - i * 32;
+                  Class<?> type = classForBits(remain);
+                  String name = "set$" + i;
+                  // We have to be a bit careful with sign-extension. If we're using a byte and the
+                  // mask is 0xff, then we'll write -1 instead. The comparison set$0 == 0xff would
+                  // always fail since the byte value gets sign-extended to 0xffff_ffff. We should
+                  // also write -1 if this is not the last field.
+                  boolean minusOne = remain >= 32 || remain == 16 || remain == 8;
+                  String allOnes = minusOne ? "-1" : hex((1 << remain) - 1);
+                  return new BitmaskField(type, name, allOnes);
+                })
+            .collect(toImmutableList());
+  }
+
+  public ImmutableSet<Property> getProperties() {
+    return properties;
+  }
+
+  /**
+   * Returns code to declare any fields needed to track which properties have been set. Each line in
+   * the returned list should appear on a line of its own.
+   */
+  public ImmutableList<String> getFieldDeclarations() {
+    return bitmaskFields.stream()
+        .map(field -> "private " + field.type + " " + field.name + ";")
+        .collect(toImmutableList());
+  }
+
+  /**
+   * Returns code to indicate that all primitive properties have received a value. This is needed in
+   * the {@code toBuilder()} constructor, since it assigns to the corresponding fields directly
+   * without going through their setters.
+   */
+  public ImmutableList<String> getInitToAllSet() {
+    return bitmaskFields.stream()
+        .map(field -> field.name + " = " + cast(field.type, field.allOnes) + ";")
+        .collect(toImmutableList());
+  }
+
+  /**
+   * Returns code to indicate that the given property has been set, if assigning to the property
+   * field is not enough. For reference (non-primitive) properties, assignment <i>is</i> enough, but
+   * for primitive properties we also need to set a bit in the bitmask.
+   */
+  public String markAsSet(Property p) {
+    Integer index = primitivePropertyToIndex.get(p);
+    if (index == null) {
+      return "";
+    }
+    BitmaskField field = bitmaskFields.get(index / 32);
+    // This use-case is why Java reduces int shift amounts mod 32. :-)
+    return field.name + " |= " + hex(1 << index) + ";";
+  }
+
+  /**
+   * Returns an expression that is true if the given property is required but has not been set.
+   * Returns null if the property is not required.
+   */
+  public String missingRequiredProperty(Property p) {
+    if (!properties.contains(p)) {
+      return null;
+    }
+    Integer index = primitivePropertyToIndex.get(p);
+    if (index == null) {
+      return "this." + p + " == null";
+    }
+    BitmaskField field = bitmaskFields.get(index / 32);
+    return "(" + field.name + " & " + hex(1 << index) + ") == 0";
+  }
+
+  /**
+   * Returns an expression that is true if any required properties have not been set. Should not be
+   * called if there are no required properties.
+   */
+  public String getAnyMissing() {
+    Stream<String> primitiveConditions =
+        bitmaskFields.stream().map(field -> field.name + " != " + field.allOnes);
+    Stream<String> nonPrimitiveConditions =
+        properties.stream()
+            .filter(p -> !primitivePropertyToIndex.containsKey(p))
+            .map(this::missingRequiredProperty);
+    return Stream.concat(primitiveConditions, nonPrimitiveConditions).collect(joining("\n|| "));
+  }
+
+  /**
+   * The smallest primitive integer type that has at least this many bits, or {@code int} if the
+   * number of bits is more than 32.
+   */
+  private static Class<?> classForBits(int bits) {
+    return bits <= 8
+        ? byte.class
+        : bits <= 16
+            ? short.class : int.class;
+  }
+
+  private static String cast(Class<?> type, String number) {
+    return (type == int.class) ? number : ("(" + type + ") " + number);
+  }
+
+  @VisibleForTesting
+  static String hex(int number) {
+    if (number >= 0) {
+      if (number < 10) {
+        return Integer.toHexString(number);
+      }
+      if (number <= 0xffff) {
+        return "0x" + Integer.toHexString(number);
+      }
+    }
+    // It's harder to tell 0x7fffffff from 0x7ffffff than to tell 0x7fff_ffff from 0x7ff_ffff.
+    String lowNybble = Integer.toHexString(number & 0xffff);
+    String pad = "000".substring(lowNybble.length() - 1);
+    return "0x" + Integer.toHexString(number >>> 16) + "_" + pad + lowNybble;
+  }
+}
diff --git a/value/src/main/java/com/google/auto/value/processor/BuilderSpec.java b/value/src/main/java/com/google/auto/value/processor/BuilderSpec.java
index b612c104..326e557e 100644
--- a/value/src/main/java/com/google/auto/value/processor/BuilderSpec.java
+++ b/value/src/main/java/com/google/auto/value/processor/BuilderSpec.java
@@ -342,12 +342,13 @@ class BuilderSpec {
       vars.builderPropertyBuilders =
           ImmutableMap.copyOf(classifier.propertyNameToPropertyBuilder());
 
-      vars.builderRequiredProperties =
+      ImmutableSet<Property> requiredProperties =
           vars.props.stream()
               .filter(p -> !p.isNullable())
               .filter(p -> p.getBuilderInitializer().isEmpty())
               .filter(p -> !vars.builderPropertyBuilders.containsKey(p.getName()))
               .collect(toImmutableSet());
+      vars.builderRequiredProperties = new BuilderRequiredProperties(requiredProperties);
     }
   }
 
diff --git a/value/src/main/java/com/google/auto/value/processor/builder.vm b/value/src/main/java/com/google/auto/value/processor/builder.vm
index b1787f25..608f5666 100644
--- a/value/src/main/java/com/google/auto/value/processor/builder.vm
+++ b/value/src/main/java/com/google/auto/value/processor/builder.vm
@@ -37,14 +37,7 @@ class ${builderName}${builderFormalTypes} ##
     ${builderTypeName}${builderActualTypes} {
 
 #foreach ($p in $props)
-
-  #if ($p.kind.primitive)
-
-  private $types.boxedClass($p.typeMirror).simpleName $p $p.builderInitializer;
-
-  #else
-
-    #if ($builderPropertyBuilders[$p.name])
+  #if ($builderPropertyBuilders[$p.name])
     ## If you have ImmutableList.Builder<String> stringsBuilder() then we define two fields:
     ## private ImmutableList.Builder<String> stringsBuilder$;
     ## private ImmutableList<String> strings;
@@ -56,7 +49,10 @@ class ${builderName}${builderFormalTypes} ##
 
   private $p.type $p $p.builderInitializer;
 
-  #end
+#end
+
+#foreach ($decl in $builderRequiredProperties.fieldDeclarations)
+  $decl
 #end
 
   ${builderName}() {
@@ -72,6 +68,10 @@ class ${builderName}${builderFormalTypes} ##
 
   #end
 
+  #foreach ($init in $builderRequiredProperties.initToAllSet)
+    $init
+  #end
+
   }
 
 #end
@@ -112,6 +112,9 @@ class ${builderName}${builderFormalTypes} ##
     #end
 
     this.$p = ${setter.copy($p)};
+
+    $builderRequiredProperties.markAsSet($p)
+
     return this;
   }
 
@@ -177,21 +180,25 @@ class ${builderName}${builderFormalTypes} ##
 
   @`java.lang.Override`
   ${p.nullableAnnotation}${builderGetters[$p.name].access}$builderGetters[$p.name].type ${p.getter}() {
-    #if ($builderGetters[$p.name].optional)
+    #set ($missingPropertyCondition = $builderRequiredProperties.missingRequiredProperty($p))
 
+    #if ($builderGetters[$p.name].optional)
+      #if ($missingPropertyCondition)
+    if ($missingPropertyCondition) {
+      return $builderGetters[$p.name].optional.empty;
+    }
+      #elseif ($p.nullable)
     if ($p == null) {
       return $builderGetters[$p.name].optional.empty;
-    } else {
-      return ${builderGetters[$p.name].optional.rawType}.of($p);
     }
+      #end
+    return ${builderGetters[$p.name].optional.rawType}.of($p);
 
     #else
-      #if ($builderRequiredProperties.contains($p))
-
-    if ($p == null) {
+      #if ($missingPropertyCondition)
+    if ($missingPropertyCondition) {
       throw new IllegalStateException(#if ($identifiers)"Property \"$p.name\" has not been set"#end);
     }
-
       #end
 
       #if ($propertyBuilder)
@@ -234,29 +241,22 @@ class ${builderName}${builderFormalTypes} ##
   #end
 #end
 
-#if (!$builderRequiredProperties.empty)
-    if (#foreach ($p in $builderRequiredProperties)##
-        this.$p == null##
-          #if ($foreach.hasNext)
-
-        || #end
-        #end) {
+#if (!$builderRequiredProperties.properties.empty)
+    if ($builderRequiredProperties.anyMissing) {
 
   #if ($identifiers)  ## build a friendly message showing all missing properties
-    #if ($builderRequiredProperties.size() == 1)
+    #if ($builderRequiredProperties.properties.size() == 1)
 
-    `java.lang.String` missing = " $builderRequiredProperties.iterator().next()";
+    `java.lang.String` missing = " $builderRequiredProperties.properties.iterator().next()";
 
     #else
 
     `java.lang.StringBuilder` missing = new `java.lang.StringBuilder`();
 
-      #foreach ($p in $builderRequiredProperties)
-
-    if (this.$p == null) {
+      #foreach ($p in $builderRequiredProperties.properties)
+    if ($builderRequiredProperties.missingRequiredProperty($p)) {
       missing.append(" $p.name");
     }
-
       #end
     #end