Compute canonical list of options using OptionValueDescription's tracking of instances.

Stop storing the canonical list of arguments separately. For the canonicalize-flags command, we want to avoid showing options that either have no values in their own right (such as expansion options and wrapper options) and instances of options that did not make it to the final value. This is work we already do in OptionValueDescription, so we can generate the canonical form from the values tracked there, instead of tracking it separately.

This means the canonical list is more correct where implicit requirements are concerned: implicit requirements are not listed in the canonical form, but now the values they overwrote will be correctly absent as well.

Use this improved list for the effective command line published to the BEP.

RELNOTES: Published command lines should have improved lists of effective options.
PiperOrigin-RevId: 173873154

8 files changed, 122 insertions, 77 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CommandLineEvent.java b/src/main/java/com/google/devtools/build/lib/runtime/CommandLineEvent.java
index 154a6172fe..6c7fdcc570 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CommandLineEvent.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CommandLineEvent.java
@@ -357,7 +357,7 @@ public abstract class CommandLineEvent implements BuildEventWithOrderConstraint
               OptionList.newBuilder()
                   .addAllOption(
                       getOptionListFromParsedOptionDescriptions(
-                          commandOptions.asCompleteListOfParsedOptions())))
+                          commandOptions.asListOfCanonicalOptions())))
           .build();
     }
 
diff --git a/src/main/java/com/google/devtools/common/options/OptionDefinition.java b/src/main/java/com/google/devtools/common/options/OptionDefinition.java
index 1c01932ff3..84a9d2d353 100644
--- a/src/main/java/com/google/devtools/common/options/OptionDefinition.java
+++ b/src/main/java/com/google/devtools/common/options/OptionDefinition.java
@@ -29,7 +29,7 @@ import java.util.Comparator;
  * the {@link Field} that is annotated, and should contain all logic about default settings and
  * behavior.
  */
-public class OptionDefinition {
+public class OptionDefinition implements Comparable<OptionDefinition> {
 
   // TODO(b/65049598) make ConstructionException checked, which will make this checked as well.
   static class NotAnOptionException extends ConstructionException {
@@ -304,6 +304,11 @@ public class OptionDefinition {
   }
 
   @Override
+  public int compareTo(OptionDefinition o) {
+    return getOptionName().compareTo(o.getOptionName());
+  }
+
+  @Override
   public String toString() {
     return String.format("option '--%s'", getOptionName());
   }
diff --git a/src/main/java/com/google/devtools/common/options/OptionValueDescription.java b/src/main/java/com/google/devtools/common/options/OptionValueDescription.java
index 0d31137fa4..30c4377b00 100644
--- a/src/main/java/com/google/devtools/common/options/OptionValueDescription.java
+++ b/src/main/java/com/google/devtools/common/options/OptionValueDescription.java
@@ -25,6 +25,7 @@ import java.util.Comparator;
 import java.util.List;
 import java.util.Map.Entry;
 import java.util.stream.Collectors;
+import javax.annotation.Nullable;
 
 /**
  * The value of an option.
@@ -74,6 +75,16 @@ public abstract class OptionValueDescription {
   }
 
   /**
+   * Returns the canonical instances of this option - the instances that affect the current value.
+   *
+   * <p>For options that do not have values in their own right, this should be the empty list. In
+   * contrast, the DefaultOptionValue does not have a canonical form at all, since it was never set,
+   * and is null.
+   */
+  @Nullable
+  abstract List<ParsedOptionDescription> getCanonicalInstances();
+
+  /**
    * For the given option, returns the correct type of OptionValueDescription, to which unparsed
    * values can be added.
    *
@@ -125,6 +136,11 @@ public abstract class OptionValueDescription {
           "Cannot add values to the default option value. Create a modifiable "
               + "OptionValueDescription using createOptionValueDescription() instead.");
     }
+
+    @Override
+    ImmutableList<ParsedOptionDescription> getCanonicalInstances() {
+      return null;
+    }
   }
 
   /**
@@ -227,6 +243,16 @@ public abstract class OptionValueDescription {
       return null;
     }
 
+    @Override
+    ImmutableList<ParsedOptionDescription> getCanonicalInstances() {
+      // If the current option is an implicit requirement, we don't need to list this value since
+      // the parent implies it. In this case, it is sufficient to not list this value at all.
+      if (effectiveOptionInstance.getImplicitDependent() == null) {
+        return ImmutableList.of(effectiveOptionInstance);
+      }
+      return ImmutableList.of();
+    }
+
     @VisibleForTesting
     ParsedOptionDescription getEffectiveOptionInstance() {
       return effectiveOptionInstance;
@@ -289,6 +315,18 @@ public abstract class OptionValueDescription {
       }
       return null;
     }
+
+    @Override
+    ImmutableList<ParsedOptionDescription> getCanonicalInstances() {
+      return parsedOptions
+          .asMap()
+          .entrySet()
+          .stream()
+          .sorted(Comparator.comparing(Entry::getKey))
+          .map(Entry::getValue)
+          .flatMap(Collection::stream)
+          .collect(ImmutableList.toImmutableList());
+    }
   }
 
   /**
@@ -337,6 +375,13 @@ public abstract class OptionValueDescription {
               : String.format(
                   "expanded from %s (source %s)", optionDefinition, parsedOption.getSource()));
     }
+
+    @Override
+    ImmutableList<ParsedOptionDescription> getCanonicalInstances() {
+      // The options this expands to are incorporated in their own right - this option does
+      // not have a canonical form.
+      return ImmutableList.of();
+    }
   }
 
   /** The form of a value for a flag with implicit requirements. */
@@ -418,6 +463,13 @@ public abstract class OptionValueDescription {
               : String.format(
                   "unwrapped from %s (source %s)", optionDefinition, parsedOption.getSource()));
     }
+
+    @Override
+    ImmutableList<ParsedOptionDescription> getCanonicalInstances() {
+      // No wrapper options get listed in the canonical form - the options they are wrapping will
+      // be in the right place.
+      return ImmutableList.of();
+    }
   }
 }
 
diff --git a/src/main/java/com/google/devtools/common/options/OptionsParser.java b/src/main/java/com/google/devtools/common/options/OptionsParser.java
index f84ee474a2..4164e7c755 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsParser.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsParser.java
@@ -680,7 +680,12 @@ public class OptionsParser implements OptionsProvider {
   }
 
   @Override
-  public List<OptionValueDescription> asListOfEffectiveOptions() {
+  public List<ParsedOptionDescription> asListOfCanonicalOptions() {
+    return impl.asCanonicalizedListOfParsedOptions();
+  }
+
+  @Override
+  public List<OptionValueDescription> asListOfOptionValues() {
     return impl.asListOfEffectiveOptions();
   }
 
diff --git a/src/main/java/com/google/devtools/common/options/OptionsParserImpl.java b/src/main/java/com/google/devtools/common/options/OptionsParserImpl.java
index b543328c5c..e8086c0680 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsParserImpl.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsParserImpl.java
@@ -21,18 +21,18 @@ import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterators;
-import com.google.common.collect.LinkedHashMultimap;
-import com.google.common.collect.Multimap;
 import com.google.devtools.common.options.OptionPriority.PriorityCategory;
 import com.google.devtools.common.options.OptionValueDescription.ExpansionBundle;
 import com.google.devtools.common.options.OptionsParser.OptionDescription;
 import java.lang.reflect.Constructor;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.function.Function;
+import java.util.stream.Stream;
 import javax.annotation.Nullable;
 
 /**
@@ -68,17 +68,6 @@ class OptionsParserImpl {
    */
   private final List<ParsedOptionDescription> parsedOptions = new ArrayList<>();
 
-  /**
-   * The options for use with the canonicalize command are stored separately from parsedOptions so
-   * that invocation policy can modify the values for canonicalization (e.g. override user-specified
-   * values with default values) without corrupting the data used to represent the user's original
-   * invocation for {@link #asListOfExplicitOptions()} and {@link #asCompleteListOfParsedOptions()}.
-   * A LinkedHashMultimap is used so that canonicalization happens in the correct order and multiple
-   * values can be stored for flags that allow multiple values.
-   */
-  private final Multimap<OptionDefinition, ParsedOptionDescription> canonicalizeValues =
-      LinkedHashMultimap.create();
-
   private final List<String> warnings = new ArrayList<>();
 
   private boolean allowSingleDashLongOptions = false;
@@ -135,36 +124,28 @@ class OptionsParserImpl {
         .collect(toCollection(ArrayList::new));
   }
 
-  /**
-   * Implements {@link OptionsParser#canonicalize}.
-   */
-  List<String> asCanonicalizedList() {
-    return canonicalizeValues
-        .values()
+  private Stream<ParsedOptionDescription> asStreamOfCanonicalParsedOptions() {
+    return optionValues
+        .keySet()
         .stream()
-        // Sort implicit requirement options to the end, keeping their existing order, and sort
-        // the other options alphabetically.
-        .sorted(
-            (v1, v2) -> {
-              if (v1.getOptionDefinition().hasImplicitRequirements()) {
-                return v2.getOptionDefinition().hasImplicitRequirements() ? 0 : 1;
-              }
-              if (v2.getOptionDefinition().hasImplicitRequirements()) {
-                return -1;
-              }
-              return v1.getOptionDefinition()
-                  .getOptionName()
-                  .compareTo(v2.getOptionDefinition().getOptionName());
-            })
-        // Ignore expansion options.
-        .filter(value -> !value.getOptionDefinition().isExpansionOption())
+        .sorted()
+        .map(optionDefinition -> optionValues.get(optionDefinition).getCanonicalInstances())
+        .flatMap(Collection::stream);
+  }
+
+  /** Implements {@link OptionsParser#canonicalize}. */
+  List<String> asCanonicalizedList() {
+    return asStreamOfCanonicalParsedOptions()
         .map(ParsedOptionDescription::getDeprecatedCanonicalForm)
-        .collect(toCollection(ArrayList::new));
+        .collect(ImmutableList.toImmutableList());
   }
 
-  /**
-   * Implements {@link OptionsParser#asListOfEffectiveOptions()}.
-   */
+  /** Implements {@link OptionsParser#canonicalize}. */
+  List<ParsedOptionDescription> asCanonicalizedListOfParsedOptions() {
+    return asStreamOfCanonicalParsedOptions().collect(ImmutableList.toImmutableList());
+  }
+
+  /** Implements {@link OptionsParser#asListOfOptionValues()}. */
   List<OptionValueDescription> asListOfEffectiveOptions() {
     List<OptionValueDescription> result = new ArrayList<>();
     for (Map.Entry<String, OptionDefinition> mapEntry : optionsData.getAllOptionDefinitions()) {
@@ -196,8 +177,6 @@ class OptionsParserImpl {
 
   OptionValueDescription clearValue(OptionDefinition optionDefinition)
       throws OptionsParsingException {
-    // Actually remove the value from various lists tracking effective options.
-    canonicalizeValues.removeAll(optionDefinition);
     return optionValues.remove(optionDefinition);
   }
 
@@ -401,11 +380,6 @@ class OptionsParserImpl {
       // Log explicit options and expanded options in the order they are parsed (can be sorted
       // later). This information is needed to correctly canonicalize flags.
       parsedOptions.add(parsedOption);
-      if (optionDefinition.allowsMultiple()) {
-        canonicalizeValues.put(optionDefinition, parsedOption);
-      } else {
-        canonicalizeValues.replaceValues(optionDefinition, ImmutableList.of(parsedOption));
-      }
     }
 
     if (expansionBundle != null) {
diff --git a/src/main/java/com/google/devtools/common/options/OptionsProvider.java b/src/main/java/com/google/devtools/common/options/OptionsProvider.java
index 5fd8ac00c1..d467fe5d98 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsProvider.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsProvider.java
@@ -57,10 +57,20 @@ public interface OptionsProvider extends OptionsClassProvider {
   List<ParsedOptionDescription> asListOfExplicitOptions();
 
   /**
-   * Returns a list of all options, including undocumented ones, and their
-   * effective values. There is no guaranteed ordering for the result.
+   * Returns a list of the parsed options whose values are in the final value of the option, i.e.
+   * the options that were added explicitly, expanded if necessary to the valued options they
+   * affect. This will not include values that were set and then overridden by a later value of the
+   * same option.
+   *
+   * <p>The list includes undocumented options.
+   */
+  List<ParsedOptionDescription> asListOfCanonicalOptions();
+
+  /**
+   * Returns a list of all options, including undocumented ones, and their effective values. There
+   * is no guaranteed ordering for the result.
    */
-  List<OptionValueDescription> asListOfEffectiveOptions();
+  List<OptionValueDescription> asListOfOptionValues();
 
   /**
    * Canonicalizes the list of options that this OptionsParser has parsed. The
diff --git a/src/test/java/com/google/devtools/build/lib/runtime/CommandLineEventTest.java b/src/test/java/com/google/devtools/build/lib/runtime/CommandLineEventTest.java
index aaeec5b094..fc51f94f9a 100644
--- a/src/test/java/com/google/devtools/build/lib/runtime/CommandLineEventTest.java
+++ b/src/test/java/com/google/devtools/build/lib/runtime/CommandLineEventTest.java
@@ -283,17 +283,16 @@ public class CommandLineEventTest {
     assertThat(line.getSections(0).getChunkList().getChunk(0)).isEqualTo("testblaze");
     assertThat(line.getSections(1).getOptionList().getOptionCount()).isEqualTo(2);
     assertThat(line.getSections(2).getChunkList().getChunk(0)).isEqualTo("someCommandName");
-    // In the canonical line, expect the rc option to show up before the higher priority options.
+    // In the canonical line, expect the options in alphabetical order.
     assertThat(line.getSections(3).getOptionList().getOptionCount()).isEqualTo(4);
     assertThat(line.getSections(3).getOptionList().getOption(0).getCombinedForm())
-        .isEqualTo("--test_multiple_string=baz");
+        .isEqualTo("--expanded_c=2");
     assertThat(line.getSections(3).getOptionList().getOption(1).getCombinedForm())
-        .isEqualTo("--test_string=foo");
+        .isEqualTo("--test_multiple_string=baz");
     assertThat(line.getSections(3).getOptionList().getOption(2).getCombinedForm())
         .isEqualTo("--test_multiple_string=bar");
     assertThat(line.getSections(3).getOptionList().getOption(3).getCombinedForm())
-        .isEqualTo("--expanded_c=2");
-
+        .isEqualTo("--test_string=foo");
     assertThat(line.getSections(4).getChunkList().getChunkCount()).isEqualTo(0);
   }
 
@@ -351,19 +350,14 @@ public class CommandLineEventTest {
     assertThat(line.getSections(1).getOptionList().getOptionCount()).isEqualTo(2);
     assertThat(line.getSections(2).getChunkList().getChunk(0)).isEqualTo("someCommandName");
 
-    // TODO(b/19881919) Expansion options shouldn't be listed along with their expansions, this
-    // could cause duplicate values for repeatable flags. There should be 4 flags here, without
-    // test_expansion listed.
-    assertThat(line.getSections(3).getOptionList().getOptionCount()).isEqualTo(5);
+    assertThat(line.getSections(3).getOptionList().getOptionCount()).isEqualTo(4);
     assertThat(line.getSections(3).getOptionList().getOption(0).getCombinedForm())
-        .isEqualTo("--test_expansion");
-    assertThat(line.getSections(3).getOptionList().getOption(1).getCombinedForm())
         .isEqualTo("--noexpanded_a");
-    assertThat(line.getSections(3).getOptionList().getOption(2).getCombinedForm())
+    assertThat(line.getSections(3).getOptionList().getOption(1).getCombinedForm())
         .isEqualTo("--expanded_b=false");
-    assertThat(line.getSections(3).getOptionList().getOption(3).getCombinedForm())
+    assertThat(line.getSections(3).getOptionList().getOption(2).getCombinedForm())
         .isEqualTo("--expanded_c 42");
-    assertThat(line.getSections(3).getOptionList().getOption(4).getCombinedForm())
+    assertThat(line.getSections(3).getOptionList().getOption(3).getCombinedForm())
         .isEqualTo("--expanded_d bar");
     assertThat(line.getSections(4).getChunkList().getChunkCount()).isEqualTo(0);
   }
diff --git a/src/test/java/com/google/devtools/common/options/OptionsParserTest.java b/src/test/java/com/google/devtools/common/options/OptionsParserTest.java
index b2e98cdc93..dc986d4d41 100644
--- a/src/test/java/com/google/devtools/common/options/OptionsParserTest.java
+++ b/src/test/java/com/google/devtools/common/options/OptionsParserTest.java
@@ -1697,7 +1697,7 @@ public class OptionsParserTest {
         OptionPriority.PriorityCategory.COMMAND_LINE,
         "command line source",
         Arrays.asList("--alpha=alphaValueSetOnCommandLine", "--gamma=gammaValueSetOnCommandLine"));
-    List<OptionValueDescription> result = parser.asListOfEffectiveOptions();
+    List<OptionValueDescription> result = parser.asListOfOptionValues();
     assertThat(result).isNotNull();
     assertThat(result).hasSize(5);
     HashMap<String,OptionValueDescription> map = new HashMap<String,OptionValueDescription>();
@@ -1889,7 +1889,7 @@ public class OptionsParserTest {
       documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
       effectTags = {OptionEffectTag.NO_OP},
       defaultValue = "null",
-      expansion = {"--a=0"}
+      expansion = {"--a=cExpansion"}
     )
     public Void c;
 
@@ -1907,7 +1907,7 @@ public class OptionsParserTest {
       documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
       effectTags = {OptionEffectTag.NO_OP},
       defaultValue = "null",
-      implicitRequirements = {"--a==1"}
+      implicitRequirements = {"--a=eRequirement"}
     )
     public String e;
 
@@ -1916,7 +1916,7 @@ public class OptionsParserTest {
       documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
       effectTags = {OptionEffectTag.NO_OP},
       defaultValue = "null",
-      implicitRequirements = {"--b==1"}
+      implicitRequirements = {"--b=fRequirement"}
     )
     public String f;
 
@@ -1952,12 +1952,12 @@ public class OptionsParserTest {
 
   @Test
   public void canonicalizeExpands() throws Exception {
-    assertThat(canonicalize(Yesterday.class, "--c")).containsExactly("--a=0");
+    assertThat(canonicalize(Yesterday.class, "--c")).containsExactly("--a=cExpansion");
   }
 
   @Test
   public void canonicalizeExpansionOverridesExplicit() throws Exception {
-    assertThat(canonicalize(Yesterday.class, "--a=x", "--c")).containsExactly("--a=0");
+    assertThat(canonicalize(Yesterday.class, "--a=x", "--c")).containsExactly("--a=cExpansion");
   }
 
   @Test
@@ -1972,9 +1972,11 @@ public class OptionsParserTest {
   }
 
   @Test
-  public void canonicalizeImplicitDepsAtEnd() throws Exception {
-    assertThat(canonicalize(Yesterday.class, "--e=y", "--a=x"))
-        .isEqualTo(Arrays.asList("--a=x", "--e=y"));
+  public void canonicalizeImplicitDepsNotListed() throws Exception {
+    // e's requirement overrides the explicit "a" here, so the "a" value is not in the canonical
+    // form - the effective value is implied and the overridden value is lost.
+    assertThat(canonicalize(Yesterday.class, "--a=x", "--e=y"))
+        .isEqualTo(Arrays.asList("--e=y"));
   }
 
   @Test
@@ -1983,9 +1985,12 @@ public class OptionsParserTest {
   }
 
   @Test
-  public void canonicalizeDoesNotSortImplicitDeps() throws Exception {
+  public void implicitDepsDoNotAffectCanonicalOrder() throws Exception {
+    // e requires a value of a that is overridden and should therefore be absent.
+    // f requires a value of b, that is absent because it is implied. Neither of these affects
+    // the order of the canonical list.
     assertThat(canonicalize(Yesterday.class, "--f=z", "--e=y", "--a=x"))
-        .containsExactly("--a=x", "--f=z", "--e=y").inOrder();
+        .containsExactly("--a=x", "--e=y", "--f=z").inOrder();
   }
 
   @Test