Remove alphabetical sorting of options in the canonical list.

This was broken for --config. Doing this properly requires keeping the order in which the options were given, which could be done either by filtering the ordered list according to which values affect the final outcome or by tracking the order correctly. I picked the later: the option order was not explicitly tracked for expansions before but now it is.

RELNOTES: canonicalize-flags no longer reorders the flags
PiperOrigin-RevId: 192132260

4 files changed, 90 insertions, 57 deletions

diff --git a/src/main/java/com/google/devtools/common/options/OptionPriority.java b/src/main/java/com/google/devtools/common/options/OptionPriority.java
index ec5d0d8f32..53f0d75b8d 100644
--- a/src/main/java/com/google/devtools/common/options/OptionPriority.java
+++ b/src/main/java/com/google/devtools/common/options/OptionPriority.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.common.options;
 
+import com.google.common.collect.ImmutableList;
 import java.util.Objects;
 
 /**
@@ -25,43 +26,63 @@ import java.util.Objects;
  */
 public class OptionPriority implements Comparable<OptionPriority> {
   private final PriorityCategory priorityCategory;
-  private final int index;
-  private final boolean locked;
+  /**
+   * Each option that is passed explicitly has 0 ancestors, so it only has its command line index
+   * (or rc index, etc., depending on the category), but expanded options have the command line
+   * index of its parent and then its position within the options that were expanded at that point.
+   * Since options can expand to expanding options, and --config can expand to expansion options as
+   * well, this can technically go arbitrarily deep, but in practice this is very short, of length <
+   * 5, most commonly of length 1.
+   */
+  private final ImmutableList<Integer> priorityIndices;
+
+  private boolean alreadyExpanded = false;
 
-  private OptionPriority(PriorityCategory priorityCategory, int index, boolean locked) {
+  private OptionPriority(
+      PriorityCategory priorityCategory, ImmutableList<Integer> priorityIndices) {
     this.priorityCategory = priorityCategory;
-    this.index = index;
-    this.locked = locked;
+    this.priorityIndices = priorityIndices;
   }
 
   /** Get the first OptionPriority for that category. */
   static OptionPriority lowestOptionPriorityAtCategory(PriorityCategory category) {
-    return new OptionPriority(category, 0, false);
+    return new OptionPriority(category, ImmutableList.of(0));
   }
 
   /**
    * Get the priority for the option following this one. In normal, incremental option parsing, the
-   * returned priority would compareTo as after the current one. Does not increment locked
+   * returned priority would compareTo as after the current one. Does not increment ancestor
    * priorities.
    */
   static OptionPriority nextOptionPriority(OptionPriority priority) {
-    if (priority.locked) {
-      return priority;
-    }
-    return new OptionPriority(priority.priorityCategory, priority.index + 1, false);
+    int lastElementPosition = priority.priorityIndices.size() - 1;
+    return new OptionPriority(
+        priority.priorityCategory,
+        ImmutableList.<Integer>builder()
+            .addAll(priority.priorityIndices.subList(0, lastElementPosition))
+            .add(priority.priorityIndices.get(lastElementPosition) + 1)
+            .build());
   }
 
   /**
-   * Return a priority for this option that will avoid priority increases by calls to
-   * nextOptionPriority.
+   * Some options are expanded to other options, and the children options need to have their order
+   * preserved while maintaining their position between the options that flank the parent option.
    *
-   * <p>Some options are expanded in-place, and need to be all parsed at the priority of the
-   * original option. In this case, parsing one of these after another should not cause the option
-   * to be considered as higher priority than the ones before it (this would cause overlap between
-   * the expansion of --expansion_flag and a option following it in the same list of options).
+   * @return the priority for the first child of the passed priority. This child's ordering can be
+   *     tracked the same way that the parent's was.
    */
-  public static OptionPriority getLockedPriority(OptionPriority priority) {
-    return new OptionPriority(priority.priorityCategory, priority.index, true);
+  public static OptionPriority getChildPriority(OptionPriority parentPriority)
+      throws OptionsParsingException {
+    if (parentPriority.alreadyExpanded) {
+      throw new OptionsParsingException("Tried to expand option too many times");
+    }
+    // Prevent this option from being re-expanded.
+    parentPriority.alreadyExpanded = true;
+
+    // The child priority has 1 more level of nesting than its parent.
+    return new OptionPriority(
+        parentPriority.priorityCategory,
+        ImmutableList.<Integer>builder().addAll(parentPriority.priorityIndices).add(0).build());
   }
 
   public PriorityCategory getPriorityCategory() {
@@ -71,28 +92,36 @@ public class OptionPriority implements Comparable<OptionPriority> {
   @Override
   public int compareTo(OptionPriority o) {
     if (priorityCategory.equals(o.priorityCategory)) {
-      return index - o.index;
+      for (int i = 0; i < priorityIndices.size() && i < o.priorityIndices.size(); ++i) {
+        if (!priorityIndices.get(i).equals(o.priorityIndices.get(i))) {
+          return priorityIndices.get(i).compareTo(o.priorityIndices.get(i));
+        }
+      }
+      // The values are up to the shorter one's length are the same, so the shorter one is a direct
+      // ancestor and comes first.
+      return Integer.compare(priorityIndices.size(), o.priorityIndices.size());
     }
-    return priorityCategory.ordinal() - o.priorityCategory.ordinal();
+    return Integer.compare(priorityCategory.ordinal(), o.priorityCategory.ordinal());
   }
 
   @Override
   public boolean equals(Object o) {
     if (o instanceof OptionPriority) {
       OptionPriority other = (OptionPriority) o;
-      return other.priorityCategory.equals(priorityCategory) && other.index == index;
+      return priorityCategory.equals(other.priorityCategory)
+          && priorityIndices.equals(other.priorityIndices);
     }
     return false;
   }
 
   @Override
   public int hashCode() {
-    return Objects.hash(priorityCategory, index);
+    return Objects.hash(priorityCategory, priorityIndices);
   }
 
   @Override
   public String toString() {
-    return String.format("OptionPriority(%s,%s)", priorityCategory, index);
+    return String.format("OptionPriority(%s,%s)", priorityCategory, priorityIndices);
   }
 
   /**
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 b7da00466e..e75f0e1c67 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsParser.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsParser.java
@@ -629,7 +629,7 @@ public class OptionsParser implements OptionsProvider {
    * @param args the arguments to parse as the expansion. Order matters, as the value of a flag may
    *     be in the following argument.
    */
-  public void parseArgsFixedAsExpansionOfOption(
+  public void parseArgsAsExpansionOfOption(
       ParsedOptionDescription optionToExpand, String source, List<String> args)
       throws OptionsParsingException {
     Preconditions.checkNotNull(
@@ -638,7 +638,7 @@ public class OptionsParser implements OptionsProvider {
         optionToExpand.getPriority().getPriorityCategory()
             != OptionPriority.PriorityCategory.DEFAULT,
         "Priority cannot be default, which was specified for arglist " + args);
-    residue.addAll(impl.parseArgsFixedAsExpansionOfOption(optionToExpand, o -> source, args));
+    residue.addAll(impl.parseArgsAsExpansionOfOption(optionToExpand, o -> source, args));
     if (!allowResidue && !residue.isEmpty()) {
       String errorMsg = "Unrecognized arguments: " + Joiner.on(' ').join(residue);
       throw new OptionsParsingException(errorMsg);
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 bc66cc38f8..2c154303a9 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsParserImpl.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsParserImpl.java
@@ -142,9 +142,10 @@ class OptionsParserImpl {
     return optionValues
         .keySet()
         .stream()
-        .sorted()
         .map(optionDefinition -> optionValues.get(optionDefinition).getCanonicalInstances())
         .flatMap(Collection::stream)
+        // Return the effective (canonical) options in the order they were applied.
+        .sorted(comparing(ParsedOptionDescription::getPriority))
         .collect(ImmutableList.toImmutableList());
   }
 
@@ -207,30 +208,30 @@ class OptionsParserImpl {
       OptionDefinition expansionFlagDef, OptionInstanceOrigin originOfExpansionFlag)
       throws OptionsParsingException {
     ImmutableList.Builder<ParsedOptionDescription> builder = ImmutableList.builder();
-    OptionInstanceOrigin originOfSubflags;
+
+    // Values needed to correctly track the origin of the expanded options.
+    OptionPriority nextOptionPriority =
+        OptionPriority.getChildPriority(originOfExpansionFlag.getPriority());
+    String source;
+    ParsedOptionDescription implicitDependent = null;
+    ParsedOptionDescription expandedFrom = null;
+
     ImmutableList<String> options;
     ParsedOptionDescription expansionFlagParsedDummy =
         ParsedOptionDescription.newDummyInstance(expansionFlagDef, originOfExpansionFlag);
     if (expansionFlagDef.hasImplicitRequirements()) {
       options = ImmutableList.copyOf(expansionFlagDef.getImplicitRequirements());
-      originOfSubflags =
-          new OptionInstanceOrigin(
-              originOfExpansionFlag.getPriority(),
-              String.format(
-                  "implicitly required by %s (source: %s)",
-                  expansionFlagDef, originOfExpansionFlag.getSource()),
-              expansionFlagParsedDummy,
-              null);
+      source =
+          String.format(
+              "implicitly required by %s (source: %s)",
+              expansionFlagDef, originOfExpansionFlag.getSource());
+      implicitDependent = expansionFlagParsedDummy;
     } else if (expansionFlagDef.isExpansionOption()) {
       options = optionsData.getEvaluatedExpansion(expansionFlagDef);
-      originOfSubflags =
-          new OptionInstanceOrigin(
-              originOfExpansionFlag.getPriority(),
-              String.format(
-                  "expanded by %s (source: %s)",
-                  expansionFlagDef, originOfExpansionFlag.getSource()),
-              null,
-              expansionFlagParsedDummy);
+      source =
+          String.format(
+              "expanded by %s (source: %s)", expansionFlagDef, originOfExpansionFlag.getSource());
+      expandedFrom = expansionFlagParsedDummy;
     } else {
       return ImmutableList.of();
     }
@@ -242,11 +243,12 @@ class OptionsParserImpl {
           identifyOptionAndPossibleArgument(
               unparsedFlagExpression,
               optionsIterator,
-              originOfSubflags.getPriority(),
-              o -> originOfSubflags.getSource(),
-              originOfSubflags.getImplicitDependent(),
-              originOfSubflags.getExpandedFrom());
+              nextOptionPriority,
+              o -> source,
+              implicitDependent,
+              expandedFrom);
       builder.add(parsedOption);
+      nextOptionPriority = OptionPriority.nextOptionPriority(nextOptionPriority);
     }
     return builder.build();
   }
@@ -287,15 +289,15 @@ class OptionsParserImpl {
     }
   }
 
-  /** Implements {@link OptionsParser#parseArgsFixedAsExpansionOfOption} */
-  List<String> parseArgsFixedAsExpansionOfOption(
+  /** Implements {@link OptionsParser#parseArgsAsExpansionOfOption} */
+  List<String> parseArgsAsExpansionOfOption(
       ParsedOptionDescription optionToExpand,
       Function<OptionDefinition, String> sourceFunction,
       List<String> args)
       throws OptionsParsingException {
     ResidueAndPriority residueAndPriority =
         parse(
-            OptionPriority.getLockedPriority(optionToExpand.getPriority()),
+            OptionPriority.getChildPriority(optionToExpand.getPriority()),
             sourceFunction,
             null,
             optionToExpand,
@@ -419,7 +421,7 @@ class OptionsParserImpl {
     if (expansionBundle != null) {
       ResidueAndPriority residueAndPriority =
           parse(
-              OptionPriority.getLockedPriority(parsedOption.getPriority()),
+              OptionPriority.getChildPriority(parsedOption.getPriority()),
               o -> expansionBundle.sourceOfExpansionArgs,
               optionDefinition.hasImplicitRequirements() ? parsedOption : null,
               optionDefinition.isExpansionOption() ? parsedOption : 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 d467fe5d98..ece5d5d2ed 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsProvider.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsProvider.java
@@ -73,11 +73,13 @@ public interface OptionsProvider extends OptionsClassProvider {
   List<OptionValueDescription> asListOfOptionValues();
 
   /**
-   * Canonicalizes the list of options that this OptionsParser has parsed. The
-   * contract is that if the returned set of options is passed to an options
-   * parser with the same options classes, then that will have the same effect
-   * as using the original args (which are passed in here), except for cosmetic
-   * differences.
+   * Canonicalizes the list of options that this OptionsParser has parsed.
+   *
+   * <p>The contract is that if the returned set of options is passed to an options parser with the
+   * same options classes, then that will have the same effect as using the original args (which are
+   * passed in here), except for cosmetic differences. We do not guarantee that the 'canonical' list
+   * is unique, since some flags may have effects unknown to the parser (--config, for Bazel), so we
+   * do not reorder flags to further simplify the list.
    */
   List<String> canonicalize();
 }