Snap for 4434599 from b6f596a78e52a50a224fd07e7a80f7541a133c9b to pi-release

Change-Id: I2f46ad71f0f9c090611cc3596f1947dec2b2aa3a

46 files changed, 1903 insertions, 918 deletions

diff --git a/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixer.java b/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixer.java
index 9b20c9d..1aaf0b6 100644
--- a/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixer.java
+++ b/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixer.java
@@ -43,6 +43,7 @@ public class DefaultMethodClassFixer extends ClassVisitor {
   private final ClassReaderFactory classpath;
   private final ClassReaderFactory bootclasspath;
   private final ClassLoader targetLoader;
+  private final DependencyCollector depsCollector;
   private final HashSet<String> instanceMethods = new HashSet<>();
 
   private boolean isInterface;
@@ -55,12 +56,14 @@ public class DefaultMethodClassFixer extends ClassVisitor {
   public DefaultMethodClassFixer(
       ClassVisitor dest,
       ClassReaderFactory classpath,
+      DependencyCollector depsCollector,
       ClassReaderFactory bootclasspath,
       ClassLoader targetLoader) {
     super(Opcodes.ASM6, dest);
     this.classpath = classpath;
     this.bootclasspath = bootclasspath;
     this.targetLoader = targetLoader;
+    this.depsCollector = depsCollector;
   }
 
   @Override
@@ -310,8 +313,17 @@ public class DefaultMethodClassFixer extends ClassVisitor {
    */
   private boolean defaultMethodsDefined(ImmutableList<String> interfaces) {
     for (String implemented : interfaces) {
+      if (bootclasspath.isKnown(implemented)) {
+        continue;
+      }
       ClassReader bytecode = classpath.readIfKnown(implemented);
-      if (bytecode != null && !bootclasspath.isKnown(implemented)) {
+      if (bytecode == null) {
+        // Interface isn't on the classpath, which indicates incomplete classpaths. Record missing
+        // dependency so we can check it later.  If we don't check then we may get runtime failures
+        // or wrong behavior from default methods that should've been stubbed in.
+        // TODO(kmb): Print a warning so people can start fixing their deps?
+        depsCollector.missingImplementedInterface(internalName, implemented);
+      } else {
         // Class in classpath and bootclasspath is a bad idea but in any event, assume the
         // bootclasspath will take precedence like in a classloader.
         // We can skip code attributes as we just need to find default methods to stub.
@@ -321,10 +333,6 @@ public class DefaultMethodClassFixer extends ClassVisitor {
           return true;
         }
       }
-      // Else interface isn't on the classpath, which indicates incomplete classpaths. For now
-      // we'll just assume the missing interfaces don't declare default methods but if they do
-      // we'll end up with concrete classes that don't implement an abstract method, which can
-      // cause runtime failures.  The classpath needs to be fixed in this case.
     }
     return false;
   }
@@ -377,7 +385,7 @@ public class DefaultMethodClassFixer extends ClassVisitor {
    */
   private class DefaultMethodStubber extends ClassVisitor {
 
-    private String interfaceName;
+    private String stubbedInterfaceName;
 
     public DefaultMethodStubber() {
       super(Opcodes.ASM6);
@@ -392,8 +400,8 @@ public class DefaultMethodClassFixer extends ClassVisitor {
         String superName,
         String[] interfaces) {
       checkArgument(BitFlags.isSet(access, Opcodes.ACC_INTERFACE));
-      checkState(interfaceName == null);
-      interfaceName = name;
+      checkState(stubbedInterfaceName == null);
+      stubbedInterfaceName = name;
     }
 
     @Override
@@ -405,6 +413,8 @@ public class DefaultMethodClassFixer extends ClassVisitor {
         // definitions conflict, but see stubMissingDefaultMethods() for how we deal with default
         // methods redefined in interfaces extending another.
         recordIfInstanceMethod(access, name, desc);
+        depsCollector.assumeCompanionClass(
+            internalName, InterfaceDesugaring.getCompanionClassName(stubbedInterfaceName));
 
         // Add this method to the class we're desugaring and stub in a body to call the default
         // implementation in the interface's companion class. ijar omits these methods when setting
@@ -423,9 +433,9 @@ public class DefaultMethodClassFixer extends ClassVisitor {
         }
         stubMethod.visitMethodInsn(
             Opcodes.INVOKESTATIC,
-            interfaceName + InterfaceDesugaring.COMPANION_SUFFIX,
+            InterfaceDesugaring.getCompanionClassName(stubbedInterfaceName),
             name,
-            InterfaceDesugaring.companionDefaultMethodDescriptor(interfaceName, desc),
+            InterfaceDesugaring.companionDefaultMethodDescriptor(stubbedInterfaceName, desc),
             /*itf*/ false);
         stubMethod.visitInsn(neededType.getReturnType().getOpcode(Opcodes.IRETURN));
 
@@ -439,8 +449,10 @@ public class DefaultMethodClassFixer extends ClassVisitor {
         // interface methods are correctly handled.
         return new InterfaceDesugaring.InterfaceInvocationRewriter(
             DefaultMethodClassFixer.this.visitMethod(access, name, desc, (String) null, exceptions),
-            interfaceName,
-            bootclasspath);
+            stubbedInterfaceName,
+            bootclasspath,
+            depsCollector,
+            internalName);
       } else {
         return null; // we don't care about the actual code in these methods
       }
diff --git a/java/com/google/devtools/build/android/desugar/DependencyCollector.java b/java/com/google/devtools/build/android/desugar/DependencyCollector.java
new file mode 100644
index 0000000..272a273
--- /dev/null
+++ b/java/com/google/devtools/build/android/desugar/DependencyCollector.java
@@ -0,0 +1,98 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar;
+
+import javax.annotation.Nullable;
+
+/**
+ * Interface for collecting desugaring metadata that we can use to double-check correct desugaring
+ * at the binary level by looking at the metadata written for all Jars on the runtime classpath
+ * (b/65645388). Use {@link NoWriteCollectors} for "no-op" collectors and {@link
+ * com.google.devtools.build.android.desugar.dependencies.MetadataCollector} for writing out
+ * metadata files.
+ */
+// TODO(kmb): There could conceivably be a "self-contained" version where we check at the end that
+// we actually saw all the companion classes (in recordDefaultMethods) that we "assumed"; useful
+// for one-shot runs over an entire binary.
+@SuppressWarnings("unused") // default implementations consist of empty method stubs
+public interface DependencyCollector {
+
+  /** Class name suffix used for interface companion classes. */
+  public String INTERFACE_COMPANION_SUFFIX = "$$CC";
+
+  /**
+   * Records that {@code origin} depends on companion class {@code target}.  For the resulting
+   * binary to be valid, {@code target} needs to exist, which isn't the case if the corresponding
+   * interface is only available as a compile-time ("neverlink") dependency.
+   */
+  default void assumeCompanionClass(String origin, String target) {}
+
+  /**
+   * Records that {@code origin} transitively implements {@code target} but {@code target} isn't
+   * in the classpath.  This can lead to wrong desugarings if {@code target} or an interface it
+   * extends defines default methods.
+   */
+  default void missingImplementedInterface(String origin, String target) {}
+
+  /**
+   * Records that the given interface extends the given interfaces.
+   *
+   * <p>This information is useful reference to double-check {@link #missingImplementedInterface}s
+   * without reading and parsing .class files, specifically if default methods are defined in
+   * interfaces that a missing interface transitively extends.
+   */
+  default void recordExtendedInterfaces(String origin, String... targets) {}
+
+  /**
+   * Records that the given interface has a companion class that includes the given number of
+   * default methods (0 if there were only static methods).  This method should not be called for
+   * purely abstract interfaces, to allow verifying available companion classes against this.
+   *
+   * <p>This information is useful reference to double-check {@link #missingImplementedInterface}s
+   * without reading and parsing .class files with better precision than just looking for
+   * companion classes on the runtime classpath (which may only contain static methods).
+   */
+  default void recordDefaultMethods(String origin, int count) {}
+
+  /**
+   * Returns metadata to include into the desugaring output or {@code null} if none.  Returning
+   * anything but {@code null} will cause an extra file to be written into the output, including
+   * an empty array.
+   */
+  @Nullable public byte[] toByteArray();
+
+  /** Simple collectors that don't collect any information. */
+  public enum NoWriteCollectors implements DependencyCollector {
+    /** Singleton instance that does nothing. */
+    NOOP,
+    /**
+     * Singleton instance that does nothing besides throwing if {@link #missingImplementedInterface}
+     * is called.
+     */
+    FAIL_ON_MISSING {
+      @Override
+      public void missingImplementedInterface(String origin, String target) {
+        throw new IllegalStateException(
+            String.format(
+                "Couldn't find interface %s on the classpath for desugaring %s", target, origin));
+      }
+    };
+
+    @Override
+    @Nullable
+    public final byte[] toByteArray() {
+      return null;
+    }
+  }
+}
diff --git a/java/com/google/devtools/build/android/desugar/Desugar.java b/java/com/google/devtools/build/android/desugar/Desugar.java
index 31c362e..87aa0d7 100644
--- a/java/com/google/devtools/build/android/desugar/Desugar.java
+++ b/java/com/google/devtools/build/android/desugar/Desugar.java
@@ -176,6 +176,26 @@ class Desugar {
     public int minSdkVersion;
 
     @Option(
+      name = "emit_dependency_metadata_as_needed",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      help = "Whether to emit META-INF/desugar_deps as needed for later consistency checking."
+    )
+    public boolean emitDependencyMetadata;
+
+    @Option(
+      name = "best_effort_tolerate_missing_deps",
+      defaultValue = "true",
+      category = "misc",
+      documentationCategory = OptionDocumentationCategory.UNCATEGORIZED,
+      effectTags = {OptionEffectTag.UNKNOWN},
+      help = "Whether to tolerate missing dependencies on the classpath in some cases.  You should "
+          + "strive to set this flag to false."
+    )
+    public boolean tolerateMissingDependencies;
+
+    @Option(
       name = "desugar_interface_method_bodies_if_needed",
       defaultValue = "true",
       category = "misc",
@@ -225,7 +245,6 @@ class Desugar {
       defaultValue = "false",
       documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
       effectTags = {OptionEffectTag.UNKNOWN},
-      implicitRequirements = "--allow_empty_bootclasspath",
       help = "Enables rewriting to desugar java.* classes."
     )
     public boolean coreLibrary;
@@ -316,6 +335,7 @@ class Desugar {
 
     try (OutputFileProvider outputFileProvider = toOutputFileProvider(outputPath);
         InputFileProvider inputFiles = toInputFileProvider(inputPath)) {
+      DependencyCollector depsCollector = createDepsCollector();
       IndexedInputs indexedInputFiles = new IndexedInputs(ImmutableList.of(inputFiles));
       // Prepend classpath with input file itself so LambdaDesugaring can load classes with
       // lambdas.
@@ -344,6 +364,7 @@ class Desugar {
           outputFileProvider,
           loader,
           classpathReader,
+          depsCollector,
           bootclasspathReader,
           interfaceLambdaMethodCollector);
 
@@ -351,12 +372,18 @@ class Desugar {
           outputFileProvider,
           loader,
           classpathReader,
+          depsCollector,
           bootclasspathReader,
           interfaceLambdaMethodCollector.build(),
           bridgeMethodReader);
 
-      desugarAndWriteGeneratedClasses(outputFileProvider);
+      desugarAndWriteGeneratedClasses(outputFileProvider, bootclasspathReader);
       copyThrowableExtensionClass(outputFileProvider);
+
+      byte[] depsInfo = depsCollector.toByteArray();
+      if (depsInfo != null) {
+        outputFileProvider.write(OutputFileProvider.DESUGAR_DEPS_FILENAME, depsInfo);
+      }
     }
 
     ImmutableMap<Path, LambdaInfo> lambdasLeftBehind = lambdas.drain();
@@ -365,6 +392,32 @@ class Desugar {
     checkState(generatedLeftBehind.isEmpty(), "Didn't process %s", generatedLeftBehind.keySet());
   }
 
+  /**
+   * Returns a dependency collector for use with a single input Jar.  If
+   * {@link DesugarOptions#emitDependencyMetadata} is set, this method instantiates the collector
+   * reflectively to allow compiling and using the desugar tool without this mechanism.
+   */
+  private DependencyCollector createDepsCollector() {
+    if (options.emitDependencyMetadata) {
+      try {
+        return (DependencyCollector)
+            Thread.currentThread()
+                .getContextClassLoader()
+                .loadClass(
+                    "com.google.devtools.build.android.desugar.dependencies.MetadataCollector")
+                .getConstructor(Boolean.TYPE)
+                .newInstance(options.tolerateMissingDependencies);
+      } catch (ReflectiveOperationException
+          | SecurityException e) {
+        throw new IllegalStateException("Can't emit desugaring metadata as requested");
+      }
+    } else if (options.tolerateMissingDependencies) {
+      return DependencyCollector.NoWriteCollectors.NOOP;
+    } else {
+      return DependencyCollector.NoWriteCollectors.FAIL_ON_MISSING;
+    }
+  }
+
   private void copyThrowableExtensionClass(OutputFileProvider outputFileProvider) {
     if (allowTryWithResources || options.desugarTryWithResourcesOmitRuntimeClasses) {
       // try-with-resources statements are okay in the output jar.
@@ -390,10 +443,15 @@ class Desugar {
       OutputFileProvider outputFileProvider,
       ClassLoader loader,
       @Nullable ClassReaderFactory classpathReader,
+      DependencyCollector depsCollector,
       ClassReaderFactory bootclasspathReader,
       Builder<String> interfaceLambdaMethodCollector)
       throws IOException {
     for (String filename : inputFiles) {
+      if (OutputFileProvider.DESUGAR_DEPS_FILENAME.equals(filename)) {
+        // TODO(kmb): rule out that this happens or merge input file with what's in depsCollector
+        continue;  // skip as we're writing a new file like this at the end or don't want it
+      }
       try (InputStream content = inputFiles.getInputStream(filename)) {
         // We can write classes uncompressed since they need to be converted to .dex format
         // for Android anyways. Resources are written as they were in the input jar to avoid
@@ -405,6 +463,7 @@ class Desugar {
               createClassVisitorsForClassesInInputs(
                   loader,
                   classpathReader,
+                  depsCollector,
                   bootclasspathReader,
                   interfaceLambdaMethodCollector,
                   writer,
@@ -431,6 +490,7 @@ class Desugar {
       OutputFileProvider outputFileProvider,
       ClassLoader loader,
       @Nullable ClassReaderFactory classpathReader,
+      DependencyCollector depsCollector,
       ClassReaderFactory bootclasspathReader,
       ImmutableSet<String> interfaceLambdaMethods,
       @Nullable ClassReaderFactory bridgeMethodReader)
@@ -460,6 +520,7 @@ class Desugar {
             createClassVisitorsForDumpedLambdaClasses(
                 loader,
                 classpathReader,
+                depsCollector,
                 bootclasspathReader,
                 interfaceLambdaMethods,
                 bridgeMethodReader,
@@ -473,7 +534,8 @@ class Desugar {
     }
   }
 
-  private void desugarAndWriteGeneratedClasses(OutputFileProvider outputFileProvider)
+  private void desugarAndWriteGeneratedClasses(
+      OutputFileProvider outputFileProvider, ClassReaderFactory bootclasspathReader)
       throws IOException {
     // Write out any classes we generated along the way
     ImmutableMap<String, ClassNode> generatedClasses = store.drain();
@@ -485,7 +547,8 @@ class Desugar {
       UnprefixingClassWriter writer = rewriter.writer(ClassWriter.COMPUTE_MAXS);
       // checkState above implies that we want Java 7 .class files, so send through that visitor.
       // Don't need a ClassReaderFactory b/c static interface methods should've been moved.
-      ClassVisitor visitor = new Java7Compatibility(writer, (ClassReaderFactory) null);
+      ClassVisitor visitor =
+          new Java7Compatibility(writer, (ClassReaderFactory) null, bootclasspathReader);
       generated.getValue().accept(visitor);
       String filename = rewriter.unprefix(generated.getKey()) + ".class";
       outputFileProvider.write(filename, writer.toByteArray());
@@ -499,6 +562,7 @@ class Desugar {
   private ClassVisitor createClassVisitorsForDumpedLambdaClasses(
       ClassLoader loader,
       @Nullable ClassReaderFactory classpathReader,
+      DependencyCollector depsCollector,
       ClassReaderFactory bootclasspathReader,
       ImmutableSet<String> interfaceLambdaMethods,
       @Nullable ClassReaderFactory bridgeMethodReader,
@@ -520,12 +584,14 @@ class Desugar {
     }
     if (outputJava7) {
       // null ClassReaderFactory b/c we don't expect to need it for lambda classes
-      visitor = new Java7Compatibility(visitor, (ClassReaderFactory) null);
+      visitor = new Java7Compatibility(visitor, (ClassReaderFactory) null, bootclasspathReader);
       if (options.desugarInterfaceMethodBodiesIfNeeded) {
         visitor =
-            new DefaultMethodClassFixer(visitor, classpathReader, bootclasspathReader, loader);
+            new DefaultMethodClassFixer(
+                visitor, classpathReader, depsCollector, bootclasspathReader, loader);
         visitor =
-            new InterfaceDesugaring(visitor, bootclasspathReader, store, options.legacyJacocoFix);
+            new InterfaceDesugaring(
+                visitor, depsCollector, bootclasspathReader, store, options.legacyJacocoFix);
       }
     }
     visitor =
@@ -553,6 +619,7 @@ class Desugar {
   private ClassVisitor createClassVisitorsForClassesInInputs(
       ClassLoader loader,
       @Nullable ClassReaderFactory classpathReader,
+      DependencyCollector depsCollector,
       ClassReaderFactory bootclasspathReader,
       Builder<String> interfaceLambdaMethodCollector,
       UnprefixingClassWriter writer,
@@ -571,12 +638,14 @@ class Desugar {
     }
     if (!options.onlyDesugarJavac9ForLint) {
       if (outputJava7) {
-        visitor = new Java7Compatibility(visitor, classpathReader);
+        visitor = new Java7Compatibility(visitor, classpathReader, bootclasspathReader);
         if (options.desugarInterfaceMethodBodiesIfNeeded) {
           visitor =
-              new DefaultMethodClassFixer(visitor, classpathReader, bootclasspathReader, loader);
+              new DefaultMethodClassFixer(
+                  visitor, classpathReader, depsCollector, bootclasspathReader, loader);
           visitor =
-              new InterfaceDesugaring(visitor, bootclasspathReader, store, options.legacyJacocoFix);
+              new InterfaceDesugaring(
+                  visitor, depsCollector, bootclasspathReader, store, options.legacyJacocoFix);
         }
       }
       // LambdaDesugaring is relatively expensive, so check first whether we need it.  Additionally,
diff --git a/java/com/google/devtools/build/android/desugar/InterfaceDesugaring.java b/java/com/google/devtools/build/android/desugar/InterfaceDesugaring.java
index 0d37a20..b93613c 100644
--- a/java/com/google/devtools/build/android/desugar/InterfaceDesugaring.java
+++ b/java/com/google/devtools/build/android/desugar/InterfaceDesugaring.java
@@ -42,9 +42,9 @@ class InterfaceDesugaring extends ClassVisitor {
   static final String COMPANION_METHOD_TO_TRIGGER_INTERFACE_CLINIT_NAME = "$$triggerInterfaceInit";
   static final String COMPANION_METHOD_TO_TRIGGER_INTERFACE_CLINIT_DESC = "()V";
 
-  static final String COMPANION_SUFFIX = "$$CC";
   static final String INTERFACE_STATIC_COMPANION_METHOD_SUFFIX = "$$STATIC$$";
 
+  private final DependencyCollector depsCollector;
   private final ClassReaderFactory bootclasspath;
   private final GeneratedClassStore store;
   private final boolean legacyJaCoCo;
@@ -52,13 +52,18 @@ class InterfaceDesugaring extends ClassVisitor {
   private String internalName;
   private int bytecodeVersion;
   private int accessFlags;
+  private int numberOfDefaultMethods;
   @Nullable private ClassVisitor companion;
   @Nullable private FieldInfo interfaceFieldToAccessInCompanionMethodToTriggerInterfaceClinit;
 
   public InterfaceDesugaring(
-      ClassVisitor dest, ClassReaderFactory bootclasspath, GeneratedClassStore store,
+      ClassVisitor dest,
+      DependencyCollector depsCollector,
+      ClassReaderFactory bootclasspath,
+      GeneratedClassStore store,
       boolean legacyJaCoCo) {
     super(Opcodes.ASM6, dest);
+    this.depsCollector = depsCollector;
     this.bootclasspath = bootclasspath;
     this.store = store;
     this.legacyJaCoCo = legacyJaCoCo;
@@ -73,15 +78,26 @@ class InterfaceDesugaring extends ClassVisitor {
       String superName,
       String[] interfaces) {
     companion = null;
+    numberOfDefaultMethods = 0;
     internalName = name;
     bytecodeVersion = version;
     accessFlags = access;
+    if (isInterface()) {
+      // Record interface hierarchy.  This helps avoid parsing .class files when double-checking
+      // desugaring results later using collected dependency information.
+      depsCollector.recordExtendedInterfaces(name, interfaces);
+    }
     super.visit(version, access, name, signature, superName, interfaces);
   }
 
   @Override
   public void visitEnd() {
     if (companion != null) {
+      // Record classes with default methods.  This increases precision when double-checking
+      // desugaring results later, without parsing .class files again, compared to just looking
+      // for companion classes in a given desugared Jar which may only contain static methods.
+      depsCollector.recordDefaultMethods(internalName, numberOfDefaultMethods);
+
       // Emit a method to access the fields of the interfaces that need initialization.
       emitInterfaceFieldAccessInCompanionMethodToTriggerInterfaceClinit();
       companion.visitEnd();
@@ -144,6 +160,7 @@ class InterfaceDesugaring extends ClassVisitor {
   @Override
   public MethodVisitor visitMethod(
       int access, String name, String desc, String signature, String[] exceptions) {
+    String codeOwner = internalName;
     MethodVisitor result;
     if (isInterface() && isStaticInitializer(name)) {
       result =
@@ -164,6 +181,8 @@ class InterfaceDesugaring extends ClassVisitor {
       name =
           normalizeInterfaceMethodName(
               name, isLambdaBody, BitFlags.isSet(access, Opcodes.ACC_STATIC));
+      codeOwner = getCompanionClassName(internalName);
+
       if (BitFlags.isSet(access, Opcodes.ACC_STATIC)) {
         // Completely move static interface methods, which requires rewriting call sites
         result =
@@ -185,6 +204,7 @@ class InterfaceDesugaring extends ClassVisitor {
               name,
               internalName,
               desc);
+          ++numberOfDefaultMethods;
           abstractDest =
               super.visitMethod(access | Opcodes.ACC_ABSTRACT, name, desc, signature, exceptions);
         }
@@ -209,7 +229,7 @@ class InterfaceDesugaring extends ClassVisitor {
     }
     return result != null
         ? new InterfaceInvocationRewriter(
-            result, isInterface() ? internalName : null, bootclasspath)
+            result, isInterface() ? internalName : null, bootclasspath, depsCollector, codeOwner)
         : null;
   }
 
@@ -228,7 +248,7 @@ class InterfaceDesugaring extends ClassVisitor {
       // Rename lambda method to reflect the new owner.  Not doing so confuses LambdaDesugaring
       // if it's run over this class again. LambdaDesugaring has already renamed the method from
       // its original name to include the interface name at this point.
-      suffix = COMPANION_SUFFIX;
+      suffix = DependencyCollector.INTERFACE_COMPANION_SUFFIX;
     } else if (isStatic) {
       suffix = INTERFACE_STATIC_COMPANION_METHOD_SUFFIX;
     } else {
@@ -238,7 +258,7 @@ class InterfaceDesugaring extends ClassVisitor {
   }
 
   static String getCompanionClassName(String interfaceName) {
-    return interfaceName + COMPANION_SUFFIX;
+    return interfaceName + DependencyCollector.INTERFACE_COMPANION_SUFFIX;
   }
 
   /**
@@ -313,25 +333,33 @@ class InterfaceDesugaring extends ClassVisitor {
     @Nullable private final String interfaceName;
 
     private final ClassReaderFactory bootclasspath;
+    private final DependencyCollector depsCollector;
+    /** Internal name that'll be used to record any dependencies on interface methods. */
+    private final String declaringClass;
 
     public InterfaceInvocationRewriter(
-        MethodVisitor dest, @Nullable String knownInterfaceName, ClassReaderFactory bootclasspath) {
+        MethodVisitor dest,
+        @Nullable String knownInterfaceName,
+        ClassReaderFactory bootclasspath,
+        DependencyCollector depsCollector,
+        String declaringClass) {
       super(Opcodes.ASM6, dest);
       this.interfaceName = knownInterfaceName;
       this.bootclasspath = bootclasspath;
+      this.depsCollector = depsCollector;
+      this.declaringClass = declaringClass;
     }
 
     @Override
     public void visitMethodInsn(int opcode, String owner, String name, String desc, boolean itf) {
       // Assume that any static interface methods on the classpath are moved
-      if (itf || owner.equals(interfaceName)) {
+      if ((itf || owner.equals(interfaceName)) && !bootclasspath.isKnown(owner)) {
         boolean isLambda = name.startsWith("lambda$");
         name = normalizeInterfaceMethodName(name, isLambda, opcode == Opcodes.INVOKESTATIC);
         if (isLambda) {
           // Redirect lambda invocations to completely remove all lambda methods from interfaces.
-          checkArgument(
-              !owner.endsWith(COMPANION_SUFFIX), "shouldn't consider %s an interface", owner);
-          checkArgument(!bootclasspath.isKnown(owner)); // must be in current input
+          checkArgument(!owner.endsWith(DependencyCollector.INTERFACE_COMPANION_SUFFIX),
+              "shouldn't consider %s an interface", owner);
           if (opcode == Opcodes.INVOKEINTERFACE) {
             opcode = Opcodes.INVOKESTATIC;
             desc = companionDefaultMethodDescriptor(owner, desc);
@@ -344,7 +372,11 @@ class InterfaceDesugaring extends ClassVisitor {
                 name);
           }
           // Reflect that InterfaceDesugaring moves and renames the lambda body method
-          owner += COMPANION_SUFFIX;
+          owner += DependencyCollector.INTERFACE_COMPANION_SUFFIX;
+          itf = false;
+          // Record dependency on companion class
+          depsCollector.assumeCompanionClass(declaringClass, owner);
+
           String expectedLambdaMethodName = LambdaDesugaring.uniqueInPackage(owner, name);
           checkState(
               name.equals(expectedLambdaMethodName),
@@ -352,18 +384,18 @@ class InterfaceDesugaring extends ClassVisitor {
               owner,
               name,
               expectedLambdaMethodName);
-          itf = false;
-        } else if ((opcode == Opcodes.INVOKESTATIC || opcode == Opcodes.INVOKESPECIAL)
-            && !bootclasspath.isKnown(owner)) {
-          checkArgument(
-              !owner.endsWith(COMPANION_SUFFIX), "shouldn't consider %s an interface", owner);
+        } else if ((opcode == Opcodes.INVOKESTATIC || opcode == Opcodes.INVOKESPECIAL)) {
+          checkArgument(!owner.endsWith(DependencyCollector.INTERFACE_COMPANION_SUFFIX),
+              "shouldn't consider %s an interface", owner);
           if (opcode == Opcodes.INVOKESPECIAL) {
             // Turn Interface.super.m() into Interface$$CC.m(receiver)
             opcode = Opcodes.INVOKESTATIC;
             desc = companionDefaultMethodDescriptor(owner, desc);
           }
-          owner += COMPANION_SUFFIX;
+          owner += DependencyCollector.INTERFACE_COMPANION_SUFFIX;
           itf = false;
+          // Record dependency on companion class
+          depsCollector.assumeCompanionClass(declaringClass, owner);
         }
       }
       super.visitMethodInsn(opcode, owner, name, desc, itf);
@@ -384,7 +416,8 @@ class InterfaceDesugaring extends ClassVisitor {
     @Override
     public void visitFieldInsn(int opcode, String owner, String name, String desc) {
       if ("$jacocoData".equals(name)) {
-        checkState(!owner.endsWith(COMPANION_SUFFIX), "Expected interface: %s", owner);
+        checkState(!owner.endsWith(DependencyCollector.INTERFACE_COMPANION_SUFFIX),
+            "Expected interface: %s", owner);
         owner = getCompanionClassName(owner);
       }
       super.visitFieldInsn(opcode, owner, name, desc);
diff --git a/java/com/google/devtools/build/android/desugar/Java7Compatibility.java b/java/com/google/devtools/build/android/desugar/Java7Compatibility.java
index 752227e..30de63d 100644
--- a/java/com/google/devtools/build/android/desugar/Java7Compatibility.java
+++ b/java/com/google/devtools/build/android/desugar/Java7Compatibility.java
@@ -17,6 +17,7 @@ import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;
 
+import javax.annotation.Nullable;
 import org.objectweb.asm.AnnotationVisitor;
 import org.objectweb.asm.Attribute;
 import org.objectweb.asm.ClassReader;
@@ -27,19 +28,28 @@ import org.objectweb.asm.Opcodes;
 import org.objectweb.asm.TypePath;
 
 /**
- * Visitor that ensures bytecode version <= 51 (Java 7) and that throws if it sees default or static
- * interface methods (i.e., non-abstract interface methods), which don't exist in Java 7.
+ * Visitor that tries to ensures bytecode version <= 51 (Java 7) and that throws if it sees default
+ * or static interface methods (i.e., non-abstract interface methods), which don't exist in Java 7.
+ * <p>The class version will 52 iff static interface method from the bootclasspath is invoked.
+ * This is mostly ensure that the generated bytecode is valid.
  */
 public class Java7Compatibility extends ClassVisitor {
 
-  private final ClassReaderFactory factory;
+  @Nullable private final ClassReaderFactory factory;
+  @Nullable private final ClassReaderFactory bootclasspathReader;
 
   private boolean isInterface;
   private String internalName;
+  private int access;
+  private String signature;
+  private String superName;
+  private String[] interfaces;
 
-  public Java7Compatibility(ClassVisitor cv, ClassReaderFactory factory) {
+  public Java7Compatibility(
+      ClassVisitor cv, ClassReaderFactory factory, ClassReaderFactory bootclasspathReader) {
     super(Opcodes.ASM6, cv);
     this.factory = factory;
+    this.bootclasspathReader = bootclasspathReader;
   }
 
   @Override
@@ -51,6 +61,10 @@ public class Java7Compatibility extends ClassVisitor {
       String superName,
       String[] interfaces) {
     internalName = name;
+    this.access = access;
+    this.signature = signature;
+    this.superName = superName;
+    this.interfaces = interfaces;
     isInterface = BitFlags.isSet(access, Opcodes.ACC_INTERFACE);
     super.visit(
         Math.min(version, Opcodes.V1_7),
@@ -83,7 +97,10 @@ public class Java7Compatibility extends ClassVisitor {
         || "<clinit>".equals(name),
         "Interface %s defines non-abstract method %s%s, which is not supported",
         internalName, name, desc);
-    MethodVisitor result = super.visitMethod(access, name, desc, signature, exceptions);
+    MethodVisitor result =
+        new UpdateBytecodeVersionIfNecessary(
+            super.visitMethod(access, name, desc, signature, exceptions));
+
     return (isInterface && "<clinit>".equals(name)) ? new InlineJacocoInit(result) : result;
   }
 
@@ -96,6 +113,42 @@ public class Java7Compatibility extends ClassVisitor {
     }
   }
 
+  /** This will rewrite class version to 52 if it sees invokestatic on an interface. */
+  private class UpdateBytecodeVersionIfNecessary extends MethodVisitor {
+
+    boolean updated = false;
+
+    public UpdateBytecodeVersionIfNecessary(MethodVisitor methodVisitor) {
+      super(Opcodes.ASM5, methodVisitor);
+    }
+
+    @Override
+    public void visitMethodInsn(int opcode, String owner, String name, String desc, boolean itf) {
+      if (itf && opcode == Opcodes.INVOKESTATIC) {
+        checkNotNull(bootclasspathReader);
+        checkState(
+            bootclasspathReader.isKnown(owner),
+            "%s contains invocation of static interface method that is "
+                + "not in the bootclasspath. Owner: %s, name: %s, desc: %s.",
+            Java7Compatibility.this.internalName,
+            owner,
+            name,
+            desc);
+        if (!updated) {
+          Java7Compatibility.this.cv.visit(
+              Opcodes.V1_8,
+              Java7Compatibility.this.access,
+              Java7Compatibility.this.internalName,
+              Java7Compatibility.this.signature,
+              Java7Compatibility.this.superName,
+              Java7Compatibility.this.interfaces);
+          updated = true;
+        }
+      }
+      super.visitMethodInsn(opcode, owner, name, desc, itf);
+    }
+  }
+
   private class InlineJacocoInit extends MethodVisitor {
     public InlineJacocoInit(MethodVisitor dest) {
       super(Opcodes.ASM6, dest);
@@ -106,6 +159,7 @@ public class Java7Compatibility extends ClassVisitor {
       if (opcode == Opcodes.INVOKESTATIC
           && "$jacocoInit".equals(name)
           && internalName.equals(owner)) {
+        checkNotNull(factory);
         ClassReader bytecode = checkNotNull(factory.readIfKnown(internalName),
             "Couldn't load interface %s to inline $jacocoInit()", internalName);
         InlineOneMethod copier = new InlineOneMethod("$jacocoInit", this);
diff --git a/java/com/google/devtools/build/android/desugar/OutputFileProvider.java b/java/com/google/devtools/build/android/desugar/OutputFileProvider.java
index bf3b710..7a590ef 100644
--- a/java/com/google/devtools/build/android/desugar/OutputFileProvider.java
+++ b/java/com/google/devtools/build/android/desugar/OutputFileProvider.java
@@ -18,6 +18,9 @@ import java.io.IOException;
 /** Output file provider allows to write files in directory or jar files. */
 interface OutputFileProvider extends AutoCloseable {
 
+  /** Filename to use to write out dependency metadata for later consistency checking. */
+  public static final String DESUGAR_DEPS_FILENAME = "META-INF/desugar_deps";
+
   /**
    * Copy {@code filename} from {@code inputFileProvider} to this output. If input file provider is
    * a {@link ZipInputFileProvider} then the metadata of the zip entry are kept.
diff --git a/java/com/google/devtools/build/android/desugar/ZipOutputFileProvider.java b/java/com/google/devtools/build/android/desugar/ZipOutputFileProvider.java
index 3f4f344..8d6501d 100644
--- a/java/com/google/devtools/build/android/desugar/ZipOutputFileProvider.java
+++ b/java/com/google/devtools/build/android/desugar/ZipOutputFileProvider.java
@@ -13,7 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.android.desugar;
 
-import com.google.common.base.Preconditions;
+import static com.google.common.base.Preconditions.checkArgument;
+
 import com.google.common.io.ByteStreams;
 import java.io.BufferedOutputStream;
 import java.io.IOException;
@@ -45,7 +46,8 @@ public class ZipOutputFileProvider implements OutputFileProvider {
 
   @Override
   public void write(String filename, byte[] content) throws IOException {
-    Preconditions.checkArgument(filename.endsWith(".class"));
+    checkArgument(filename.equals(DESUGAR_DEPS_FILENAME) || filename.endsWith(".class"),
+        "Expect file to be copied: %s", filename);
     writeStoredEntry(out, filename, content);
   }
 
diff --git a/java/com/google/devtools/common/options/ExpansionContext.java b/java/com/google/devtools/common/options/ExpansionContext.java
deleted file mode 100644
index c6aecc7..0000000
--- a/java/com/google/devtools/common/options/ExpansionContext.java
+++ /dev/null
@@ -1,56 +0,0 @@
-// Copyright 2017 The Bazel Authors. All rights reserved.
-//
-// 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.devtools.common.options;
-
-import java.lang.reflect.Field;
-import javax.annotation.Nullable;
-import javax.annotation.concurrent.ThreadSafe;
-
-/**
- * Encapsulates the data given to {@link ExpansionFunction} objects. This lets {@link
- * ExpansionFunction} objects change how it expands flags based on the arguments given to the {@link
- * OptionsParser}.
- */
-@ThreadSafe
-public final class ExpansionContext {
-  private final IsolatedOptionsData optionsData;
-  private final OptionDefinition optionDefinition;
-  @Nullable private final String unparsedValue;
-
-  public ExpansionContext(
-      IsolatedOptionsData optionsData,
-      OptionDefinition optionDefinition,
-      @Nullable String unparsedValue) {
-    this.optionsData = optionsData;
-    this.optionDefinition = optionDefinition;
-    this.unparsedValue = unparsedValue;
-  }
-
-  /** Metadata for the option that is being expanded. */
-  public IsolatedOptionsData getOptionsData() {
-    return optionsData;
-  }
-
-  /** {@link Field} object for option that is being expanded. */
-  public OptionDefinition getOptionDefinition() {
-    return optionDefinition;
-  }
-
-  /** Argument given to this flag during options parsing. Will be null if no argument was given. */
-  @Nullable
-  public String getUnparsedValue() {
-    return unparsedValue;
-  }
-}
diff --git a/java/com/google/devtools/common/options/ExpansionFunction.java b/java/com/google/devtools/common/options/ExpansionFunction.java
index 09119b2..d2c2693 100644
--- a/java/com/google/devtools/common/options/ExpansionFunction.java
+++ b/java/com/google/devtools/common/options/ExpansionFunction.java
@@ -30,5 +30,5 @@ public interface ExpansionFunction {
    *     information is computed
    * @return An expansion to use on an empty list
    */
-  ImmutableList<String> getExpansion(ExpansionContext context) throws OptionsParsingException;
+  ImmutableList<String> getExpansion(IsolatedOptionsData optionsData);
 }
diff --git a/java/com/google/devtools/common/options/InvocationPolicyEnforcer.java b/java/com/google/devtools/common/options/InvocationPolicyEnforcer.java
index 742acb6..a53ff5b 100644
--- a/java/com/google/devtools/common/options/InvocationPolicyEnforcer.java
+++ b/java/com/google/devtools/common/options/InvocationPolicyEnforcer.java
@@ -14,7 +14,6 @@
 package com.google.devtools.common.options;
 
 import com.google.common.base.Joiner;
-import com.google.common.base.Preconditions;
 import com.google.common.base.Verify;
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
@@ -27,6 +26,7 @@ import com.google.devtools.build.lib.runtime.proto.InvocationPolicyOuterClass.Fl
 import com.google.devtools.build.lib.runtime.proto.InvocationPolicyOuterClass.InvocationPolicy;
 import com.google.devtools.build.lib.runtime.proto.InvocationPolicyOuterClass.SetValue;
 import com.google.devtools.build.lib.runtime.proto.InvocationPolicyOuterClass.UseDefault;
+import com.google.devtools.common.options.OptionPriority.PriorityCategory;
 import com.google.devtools.common.options.OptionsParser.OptionDescription;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -35,15 +35,14 @@ import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import java.util.function.Function;
 import java.util.logging.Level;
 import java.util.logging.Logger;
+import java.util.stream.Collectors;
 import javax.annotation.Nullable;
 
 /**
- * Enforces the {@link FlagPolicy}s (from an {@link InvocationPolicy} proto) on an
- * {@link OptionsParser} by validating and changing the flag values in the given
- * {@link OptionsParser}.
+ * Enforces the {@link FlagPolicy}s (from an {@link InvocationPolicy} proto) on an {@link
+ * OptionsParser} by validating and changing the flag values in the given {@link OptionsParser}.
  *
  * <p>"Flag" and "Option" are used interchangeably in this file.
  */
@@ -52,9 +51,8 @@ public final class InvocationPolicyEnforcer {
   private static final Logger logger = Logger.getLogger(InvocationPolicyEnforcer.class.getName());
 
   private static final String INVOCATION_POLICY_SOURCE = "Invocation policy";
-  private static final Function<OptionDefinition, String> INVOCATION_POLICY_SOURCE_FUNCTION =
-      o -> INVOCATION_POLICY_SOURCE;
   @Nullable private final InvocationPolicy invocationPolicy;
+  private final Level loglevel;
 
   /**
    * Creates an InvocationPolicyEnforcer that enforces the given policy.
@@ -63,7 +61,33 @@ public final class InvocationPolicyEnforcer {
    *     nothing in calls to enforce().
    */
   public InvocationPolicyEnforcer(@Nullable InvocationPolicy invocationPolicy) {
+    this(invocationPolicy, Level.FINE);
+  }
+
+  /**
+   * Creates an InvocationPolicyEnforcer that enforces the given policy.
+   *
+   * @param invocationPolicy the policy to enforce. A null policy means this enforcer will do
+   *     nothing in calls to enforce().
+   * @param loglevel the level at which to log informational statements. Warnings and errors will
+   *     still be logged at the appropriate level.
+   */
+  public InvocationPolicyEnforcer(@Nullable InvocationPolicy invocationPolicy, Level loglevel) {
     this.invocationPolicy = invocationPolicy;
+    this.loglevel = loglevel;
+  }
+
+  private static final class FlagPolicyWithContext {
+    private final FlagPolicy policy;
+    private final OptionDescription description;
+    private final OptionInstanceOrigin origin;
+
+    public FlagPolicyWithContext(
+        FlagPolicy policy, OptionDescription description, OptionInstanceOrigin origin) {
+      this.policy = policy;
+      this.description = description;
+      this.origin = origin;
+    }
   }
 
   public InvocationPolicy getInvocationPolicy() {
@@ -97,10 +121,11 @@ public final class InvocationPolicyEnforcer {
 
     // The effective policy returned is expanded, filtered for applicable commands, and cleaned of
     // redundancies and conflicts.
-    List<FlagPolicy> effectivePolicies = getEffectivePolicies(invocationPolicy, parser, command);
+    List<FlagPolicyWithContext> effectivePolicies =
+        getEffectivePolicies(invocationPolicy, parser, command, loglevel);
 
-    for (FlagPolicy flagPolicy : effectivePolicies) {
-      String flagName = flagPolicy.getFlagName();
+    for (FlagPolicyWithContext flagPolicy : effectivePolicies) {
+      String flagName = flagPolicy.policy.getFlagName();
 
       OptionValueDescription valueDescription;
       try {
@@ -109,48 +134,53 @@ public final class InvocationPolicyEnforcer {
         // This flag doesn't exist. We are deliberately lenient if the flag policy has a flag
         // we don't know about. This is for better future proofing so that as new flags are added,
         // new policies can use the new flags without worrying about older versions of Bazel.
-        logger.info(
+        logger.log(
+            loglevel,
             String.format("Flag '%s' specified by invocation policy does not exist", flagName));
         continue;
       }
 
-      OptionDescription optionDescription =
-          parser.getOptionDescription(
-              flagName, OptionPriority.INVOCATION_POLICY, INVOCATION_POLICY_SOURCE);
       // getOptionDescription() will return null if the option does not exist, however
       // getOptionValueDescription() above would have thrown an IllegalArgumentException if that
       // were the case.
-      Verify.verifyNotNull(optionDescription);
+      Verify.verifyNotNull(flagPolicy.description);
 
-      switch (flagPolicy.getOperationCase()) {
+      switch (flagPolicy.policy.getOperationCase()) {
         case SET_VALUE:
-          applySetValueOperation(parser, flagPolicy, valueDescription, optionDescription);
+          applySetValueOperation(parser, flagPolicy, valueDescription, loglevel);
           break;
 
         case USE_DEFAULT:
-          applyUseDefaultOperation(parser, "UseDefault", optionDescription.getOptionDefinition());
+          applyUseDefaultOperation(
+              parser, "UseDefault", flagPolicy.description.getOptionDefinition(), loglevel);
           break;
 
         case ALLOW_VALUES:
-          AllowValues allowValues = flagPolicy.getAllowValues();
-          FilterValueOperation.ALLOW_VALUE_OPERATION.apply(
+          AllowValues allowValues = flagPolicy.policy.getAllowValues();
+          FilterValueOperation.AllowValueOperation allowValueOperation =
+              new FilterValueOperation.AllowValueOperation(loglevel);
+          allowValueOperation.apply(
               parser,
+              flagPolicy.origin,
               allowValues.getAllowedValuesList(),
               allowValues.hasNewValue() ? allowValues.getNewValue() : null,
               allowValues.hasUseDefault(),
               valueDescription,
-              optionDescription);
+              flagPolicy.description);
           break;
 
         case DISALLOW_VALUES:
-          DisallowValues disallowValues = flagPolicy.getDisallowValues();
-          FilterValueOperation.DISALLOW_VALUE_OPERATION.apply(
+          DisallowValues disallowValues = flagPolicy.policy.getDisallowValues();
+          FilterValueOperation.DisallowValueOperation disallowValueOperation =
+              new FilterValueOperation.DisallowValueOperation(loglevel);
+          disallowValueOperation.apply(
               parser,
+              flagPolicy.origin,
               disallowValues.getDisallowedValuesList(),
               disallowValues.hasNewValue() ? disallowValues.getNewValue() : null,
               disallowValues.hasUseDefault(),
               valueDescription,
-              optionDescription);
+              flagPolicy.description);
           break;
 
         case OPERATION_NOT_SET:
@@ -160,7 +190,7 @@ public final class InvocationPolicyEnforcer {
           logger.warning(
               String.format(
                   "Unknown operation '%s' from invocation policy for flag '%s'",
-                  flagPolicy.getOperationCase(), flagName));
+                  flagPolicy.policy.getOperationCase(), flagName));
           break;
       }
     }
@@ -182,13 +212,27 @@ public final class InvocationPolicyEnforcer {
     return !Collections.disjoint(policy.getCommandsList(), applicableCommands);
   }
 
+  /** Returns the expanded and filtered policy that would be enforced for the given command. */
+  public static InvocationPolicy getEffectiveInvocationPolicy(
+      InvocationPolicy invocationPolicy, OptionsParser parser, String command, Level loglevel)
+      throws OptionsParsingException {
+    ImmutableList<FlagPolicyWithContext> effectivePolicies =
+        getEffectivePolicies(invocationPolicy, parser, command, loglevel);
+
+    InvocationPolicy.Builder builder = InvocationPolicy.newBuilder();
+    for (FlagPolicyWithContext policyWithContext : effectivePolicies) {
+      builder.addFlagPolicies(policyWithContext.policy);
+    }
+    return builder.build();
+  }
+
   /**
    * Takes the provided policy and processes it to the form that can be used on the user options.
    *
    * <p>Expands any policies on expansion flags.
    */
-  public static ImmutableList<FlagPolicy> getEffectivePolicies(
-      InvocationPolicy invocationPolicy, OptionsParser parser, String command)
+  private static ImmutableList<FlagPolicyWithContext> getEffectivePolicies(
+      InvocationPolicy invocationPolicy, OptionsParser parser, String command, Level loglevel)
       throws OptionsParsingException {
     if (invocationPolicy == null) {
       return ImmutableList.of();
@@ -200,20 +244,42 @@ public final class InvocationPolicyEnforcer {
             : CommandNameCache.CommandNameCacheInstance.INSTANCE.get(command);
 
     // Expand all policies to transfer policies on expansion flags to policies on the child flags.
-    List<FlagPolicy> expandedPolicies = new ArrayList<>();
+    List<FlagPolicyWithContext> expandedPolicies = new ArrayList<>();
+    OptionPriority nextPriority =
+        OptionPriority.lowestOptionPriorityAtCategory(PriorityCategory.INVOCATION_POLICY);
     for (FlagPolicy policy : invocationPolicy.getFlagPoliciesList()) {
+      // These policies are high-level, before expansion, and so are not the implicitDependents or
+      // expansions of any other flag, other than in an obtuse sense from --invocation_policy.
+      OptionPriority currentPriority = nextPriority;
+      OptionInstanceOrigin origin =
+          new OptionInstanceOrigin(currentPriority, INVOCATION_POLICY_SOURCE, null, null);
+      nextPriority = OptionPriority.nextOptionPriority(currentPriority);
       if (!policyApplies(policy, commandAndParentCommands)) {
         // Only keep and expand policies that are applicable to the current command.
         continue;
       }
-      List<FlagPolicy> policies = expandPolicy(policy, parser);
+
+      OptionDescription optionDescription = parser.getOptionDescription(policy.getFlagName());
+      if (optionDescription == null) {
+        // InvocationPolicy ignores policy on non-existing flags by design, for version
+        // compatibility.
+        logger.log(
+            loglevel,
+            String.format(
+                "Flag '%s' specified by invocation policy does not exist, and will be ignored",
+                policy.getFlagName()));
+        continue;
+      }
+      FlagPolicyWithContext policyWithContext =
+          new FlagPolicyWithContext(policy, optionDescription, origin);
+      List<FlagPolicyWithContext> policies = expandPolicy(policyWithContext, parser, loglevel);
       expandedPolicies.addAll(policies);
     }
 
     // Only keep that last policy for each flag.
-    Map<String, FlagPolicy> effectivePolicy = new HashMap<>();
-    for (FlagPolicy expandedPolicy : expandedPolicies) {
-      String flagName = expandedPolicy.getFlagName();
+    Map<String, FlagPolicyWithContext> effectivePolicy = new HashMap<>();
+    for (FlagPolicyWithContext expandedPolicy : expandedPolicies) {
+      String flagName = expandedPolicy.policy.getFlagName();
       effectivePolicy.put(flagName, expandedPolicy);
     }
 
@@ -232,78 +298,6 @@ public final class InvocationPolicyEnforcer {
         String.format("Disallow_Values on expansion flags like %s is not allowed.", flagName));
   }
 
-  private static ImmutableList<ParsedOptionDescription> getExpansionsFromFlagPolicy(
-      FlagPolicy expansionPolicy, OptionDescription optionDescription, OptionsParser parser)
-      throws OptionsParsingException {
-    if (!optionDescription.isExpansion()) {
-      return ImmutableList.of();
-    }
-
-    Preconditions.checkArgument(
-        expansionPolicy
-            .getFlagName()
-            .equals(optionDescription.getOptionDefinition().getOptionName()),
-        String.format(
-            "The optionDescription provided (for flag %s) does not match the policy for flag %s.",
-            optionDescription.getOptionDefinition().getOptionName(),
-            expansionPolicy.getFlagName()));
-
-    ImmutableList.Builder<ParsedOptionDescription> resultsBuilder = ImmutableList.builder();
-    switch (expansionPolicy.getOperationCase()) {
-      case SET_VALUE:
-        {
-          SetValue setValue = expansionPolicy.getSetValue();
-          if (setValue.getFlagValueCount() > 0) {
-            for (String value : setValue.getFlagValueList()) {
-              resultsBuilder.addAll(
-                  parser.getExpansionOptionValueDescriptions(
-                      optionDescription.getOptionDefinition(),
-                      value,
-                      OptionPriority.INVOCATION_POLICY,
-                      INVOCATION_POLICY_SOURCE));
-            }
-          } else {
-            resultsBuilder.addAll(
-                parser.getExpansionOptionValueDescriptions(
-                    optionDescription.getOptionDefinition(),
-                    null,
-                    OptionPriority.INVOCATION_POLICY,
-                    INVOCATION_POLICY_SOURCE));
-          }
-        }
-        break;
-      case USE_DEFAULT:
-        resultsBuilder.addAll(
-            parser.getExpansionOptionValueDescriptions(
-                optionDescription.getOptionDefinition(),
-                null,
-                OptionPriority.INVOCATION_POLICY,
-                INVOCATION_POLICY_SOURCE));
-        break;
-      case ALLOW_VALUES:
-        // All expansions originally given to the parser have been expanded by now, so these two
-        // cases aren't necessary (the values given in the flag policy shouldn't need to be
-        // checked). If you care about blocking specific flag values you should block the behavior
-        // on the specific ones, not the expansion that contains them.
-        throwAllowValuesOnExpansionFlagException(expansionPolicy.getFlagName());
-        break;
-      case DISALLOW_VALUES:
-        throwDisallowValuesOnExpansionFlagException(expansionPolicy.getFlagName());
-        break;
-      case OPERATION_NOT_SET:
-        throw new PolicyOperationNotSetException(expansionPolicy.getFlagName());
-      default:
-        logger.warning(
-            String.format(
-                "Unknown operation '%s' from invocation policy for flag '%s'",
-                expansionPolicy.getOperationCase(),
-                optionDescription.getOptionDefinition().getOptionName()));
-        break;
-    }
-
-    return resultsBuilder.build();
-  }
-
   /**
    * Expand a single policy. If the policy is not about an expansion flag, this will simply return a
    * list with a single element, oneself. If the policy is for an expansion flag, the policy will
@@ -311,83 +305,95 @@ public final class InvocationPolicyEnforcer {
    *
    * <p>None of the flagPolicies returned should be on expansion flags.
    */
-  private static List<FlagPolicy> expandPolicy(
-      FlagPolicy originalPolicy,
-      OptionsParser parser)
+  private static List<FlagPolicyWithContext> expandPolicy(
+      FlagPolicyWithContext originalPolicy,
+      OptionsParser parser,
+      Level loglevel)
       throws OptionsParsingException {
-    List<FlagPolicy> expandedPolicies = new ArrayList<>();
-
-    OptionDescription originalOptionDescription =
-        parser.getOptionDescription(
-            originalPolicy.getFlagName(),
-            OptionPriority.INVOCATION_POLICY,
-            INVOCATION_POLICY_SOURCE);
-    if (originalOptionDescription == null) {
-      // InvocationPolicy ignores policy on non-existing flags by design, for version compatibility.
-      return expandedPolicies;
-    }
+    List<FlagPolicyWithContext> expandedPolicies = new ArrayList<>();
 
-    ImmutableList<ParsedOptionDescription> expansions =
-        getExpansionsFromFlagPolicy(originalPolicy, originalOptionDescription, parser);
-    ImmutableList.Builder<ParsedOptionDescription> subflagBuilder = ImmutableList.builder();
+    boolean isExpansion = originalPolicy.description.isExpansion();
     ImmutableList<ParsedOptionDescription> subflags =
-        subflagBuilder
-            .addAll(originalOptionDescription.getImplicitRequirements())
-            .addAll(expansions)
-            .build();
-    boolean isExpansion = originalOptionDescription.isExpansion();
-
-    if (!subflags.isEmpty() && logger.isLoggable(Level.FINE)) {
-      // Log the expansion. Since this is logged regardless of user provided command line, it is
-      // only really useful for understanding the invocation policy itself. Most of the time,
-      // invocation policy does not change, so this can be a log level fine.
+        parser.getExpansionValueDescriptions(
+            originalPolicy.description.getOptionDefinition(), originalPolicy.origin);
+
+    // If we have nothing to expand to, no need to do any further work.
+    if (subflags.isEmpty()) {
+      return ImmutableList.of(originalPolicy);
+    }
+
+    if (logger.isLoggable(loglevel)) {
+      // Log the expansion. This is only really useful for understanding the invocation policy
+      // itself.
       List<String> subflagNames = new ArrayList<>(subflags.size());
       for (ParsedOptionDescription subflag : subflags) {
         subflagNames.add("--" + subflag.getOptionDefinition().getOptionName());
       }
 
       logger.logp(
-          Level.FINE,
+          loglevel,
           "InvocationPolicyEnforcer",
           "expandPolicy",
           String.format(
               "Expanding %s on option %s to its %s: %s.",
-              originalPolicy.getOperationCase(),
-              originalPolicy.getFlagName(),
+              originalPolicy.policy.getOperationCase(),
+              originalPolicy.policy.getFlagName(),
               isExpansion ? "expansions" : "implied flags",
               Joiner.on("; ").join(subflagNames)));
     }
 
     // Repeated flags are special, and could set multiple times in an expansion, with the user
     // expecting both values to be valid. Collect these separately.
-    Multimap<OptionDefinition, ParsedOptionDescription> repeatableSubflagsInSetValues =
+    Multimap<OptionDescription, ParsedOptionDescription> repeatableSubflagsInSetValues =
         ArrayListMultimap.create();
 
     // Create a flag policy for the child that looks like the parent's policy "transferred" to its
     // child. Note that this only makes sense for SetValue, when setting an expansion flag, or
     // UseDefault, when preventing it from being set.
     for (ParsedOptionDescription currentSubflag : subflags) {
+      OptionDescription subflagOptionDescription =
+          parser.getOptionDescription(currentSubflag.getOptionDefinition().getOptionName());
+
       if (currentSubflag.getOptionDefinition().allowsMultiple()
-          && originalPolicy.getOperationCase().equals(OperationCase.SET_VALUE)) {
-        repeatableSubflagsInSetValues.put(currentSubflag.getOptionDefinition(), currentSubflag);
+          && originalPolicy.policy.getOperationCase().equals(OperationCase.SET_VALUE)) {
+        repeatableSubflagsInSetValues.put(subflagOptionDescription, currentSubflag);
       } else {
-        FlagPolicy subflagAsPolicy =
-            getSingleValueSubflagAsPolicy(currentSubflag, originalPolicy, isExpansion);
+        FlagPolicyWithContext subflagAsPolicy =
+            getSingleValueSubflagAsPolicy(
+                subflagOptionDescription, currentSubflag, originalPolicy, isExpansion);
         // In case any of the expanded flags are themselves expansions, recurse.
-        expandedPolicies.addAll(expandPolicy(subflagAsPolicy, parser));
+        expandedPolicies.addAll(expandPolicy(subflagAsPolicy, parser, loglevel));
       }
     }
 
     // If there are any repeatable flag SetValues, deal with them together now.
     // Note that expansion flags have no value, and so cannot have multiple values either.
     // Skipping the recursion above is fine.
-    for (OptionDefinition repeatableFlag : repeatableSubflagsInSetValues.keySet()) {
+    for (OptionDescription repeatableFlag : repeatableSubflagsInSetValues.keySet()) {
       int numValues = repeatableSubflagsInSetValues.get(repeatableFlag).size();
       ArrayList<String> newValues = new ArrayList<>(numValues);
+      ArrayList<OptionInstanceOrigin> origins = new ArrayList<>(numValues);
       for (ParsedOptionDescription setValue : repeatableSubflagsInSetValues.get(repeatableFlag)) {
         newValues.add(setValue.getUnconvertedValue());
+        origins.add(setValue.getOrigin());
       }
-      expandedPolicies.add(getSetValueSubflagAsPolicy(repeatableFlag, newValues, originalPolicy));
+      // These options come from expanding a single policy, so they have effectively the same
+      // priority. They could have come from different expansions or implicit requirements in the
+      // recursive resolving of the option list, so just pick the first one. Do collapse the source
+      // strings though, in case there are different sources.
+      OptionInstanceOrigin arbitraryFirstOptionOrigin = origins.get(0);
+      OptionInstanceOrigin originOfSubflags =
+          new OptionInstanceOrigin(
+              arbitraryFirstOptionOrigin.getPriority(),
+              origins
+                  .stream()
+                  .map(OptionInstanceOrigin::getSource)
+                  .distinct()
+                  .collect(Collectors.joining(", ")),
+              arbitraryFirstOptionOrigin.getImplicitDependent(),
+              arbitraryFirstOptionOrigin.getExpandedFrom());
+      expandedPolicies.add(
+          getSetValueSubflagAsPolicy(repeatableFlag, newValues, originOfSubflags, originalPolicy));
     }
 
     // Don't add the original policy if it was an expansion flag, which have no value, but do add
@@ -404,16 +410,20 @@ public final class InvocationPolicyEnforcer {
    * policies that set the flag, and so interact with repeatable flags, flags that can be set
    * multiple times, in subtle ways.
    *
-   * @param subflag, the definition of the flag the SetValue'd expansion flag expands to.
+   * @param subflagDesc, the description of the flag the SetValue'd expansion flag expands to.
    * @param subflagValue, the values that the SetValue'd expansion flag expands to for this flag.
    * @param originalPolicy, the original policy on the expansion flag.
    * @return the flag policy for the subflag given, this will be part of the expanded form of the
    *     SetValue policy on the original flag.
    */
-  private static FlagPolicy getSetValueSubflagAsPolicy(
-      OptionDefinition subflag, List<String> subflagValue, FlagPolicy originalPolicy) {
+  private static FlagPolicyWithContext getSetValueSubflagAsPolicy(
+      OptionDescription subflagDesc,
+      List<String> subflagValue,
+      OptionInstanceOrigin subflagOrigin,
+      FlagPolicyWithContext originalPolicy) {
     // Some sanity checks.
-    Verify.verify(originalPolicy.getOperationCase().equals(OperationCase.SET_VALUE));
+    OptionDefinition subflag = subflagDesc.getOptionDefinition();
+    Verify.verify(originalPolicy.policy.getOperationCase().equals(OperationCase.SET_VALUE));
     if (!subflag.allowsMultiple()) {
       Verify.verify(subflagValue.size() <= 1);
     }
@@ -425,28 +435,34 @@ public final class InvocationPolicyEnforcer {
       setValueExpansion.addFlagValue(value);
     }
     if (subflag.allowsMultiple()) {
-      setValueExpansion.setAppend(originalPolicy.getSetValue().getOverridable());
+      setValueExpansion.setAppend(originalPolicy.policy.getSetValue().getOverridable());
     } else {
-      setValueExpansion.setOverridable(originalPolicy.getSetValue().getOverridable());
+      setValueExpansion.setOverridable(originalPolicy.policy.getSetValue().getOverridable());
     }
 
     // Commands from the original policy, flag name of the expansion
-    return FlagPolicy.newBuilder()
-        .addAllCommands(originalPolicy.getCommandsList())
-        .setFlagName(subflag.getOptionName())
-        .setSetValue(setValueExpansion)
-        .build();
+    return new FlagPolicyWithContext(
+        FlagPolicy.newBuilder()
+            .addAllCommands(originalPolicy.policy.getCommandsList())
+            .setFlagName(subflag.getOptionName())
+            .setSetValue(setValueExpansion)
+            .build(),
+        subflagDesc,
+        subflagOrigin);
   }
 
   /**
    * For an expansion flag in an invocation policy, each flag it expands to must be given a
    * corresponding policy.
    */
-  private static FlagPolicy getSingleValueSubflagAsPolicy(
-      ParsedOptionDescription currentSubflag, FlagPolicy originalPolicy, boolean isExpansion)
+  private static FlagPolicyWithContext getSingleValueSubflagAsPolicy(
+      OptionDescription subflagContext,
+      ParsedOptionDescription currentSubflag,
+      FlagPolicyWithContext originalPolicy,
+      boolean isExpansion)
       throws OptionsParsingException {
-    FlagPolicy subflagAsPolicy = null;
-    switch (originalPolicy.getOperationCase()) {
+    FlagPolicyWithContext subflagAsPolicy = null;
+    switch (originalPolicy.policy.getOperationCase()) {
       case SET_VALUE:
         if (currentSubflag.getOptionDefinition().allowsMultiple()) {
           throw new AssertionError(
@@ -463,22 +479,25 @@ public final class InvocationPolicyEnforcer {
         }
         subflagAsPolicy =
             getSetValueSubflagAsPolicy(
-                currentSubflag.getOptionDefinition(), subflagValue, originalPolicy);
+                subflagContext, subflagValue, currentSubflag.getOrigin(), originalPolicy);
         break;
 
       case USE_DEFAULT:
         // Commands from the original policy, flag name of the expansion
         subflagAsPolicy =
-            FlagPolicy.newBuilder()
-                .addAllCommands(originalPolicy.getCommandsList())
-                .setFlagName(currentSubflag.getOptionDefinition().getOptionName())
-                .setUseDefault(UseDefault.getDefaultInstance())
-                .build();
+            new FlagPolicyWithContext(
+                FlagPolicy.newBuilder()
+                    .addAllCommands(originalPolicy.policy.getCommandsList())
+                    .setFlagName(currentSubflag.getOptionDefinition().getOptionName())
+                    .setUseDefault(UseDefault.getDefaultInstance())
+                    .build(),
+                subflagContext,
+                currentSubflag.getOrigin());
         break;
 
       case ALLOW_VALUES:
         if (isExpansion) {
-          throwAllowValuesOnExpansionFlagException(originalPolicy.getFlagName());
+          throwAllowValuesOnExpansionFlagException(originalPolicy.policy.getFlagName());
         }
         // If this flag is an implicitRequirement, and some values for the parent flag are
         // allowed, nothing needs to happen on the implicitRequirement that is set for all
@@ -487,7 +506,7 @@ public final class InvocationPolicyEnforcer {
 
       case DISALLOW_VALUES:
         if (isExpansion) {
-          throwDisallowValuesOnExpansionFlagException(originalPolicy.getFlagName());
+          throwDisallowValuesOnExpansionFlagException(originalPolicy.policy.getFlagName());
         }
         // If this flag is an implicitRequirement, and some values for the parent flag are
         // disallowed, that implies that all others are allowed, so nothing needs to happen
@@ -495,7 +514,7 @@ public final class InvocationPolicyEnforcer {
         break;
 
       case OPERATION_NOT_SET:
-        throw new PolicyOperationNotSetException(originalPolicy.getFlagName());
+        throw new PolicyOperationNotSetException(originalPolicy.policy.getFlagName());
 
       default:
         return null;
@@ -503,11 +522,12 @@ public final class InvocationPolicyEnforcer {
     return subflagAsPolicy;
   }
 
-  private static void logInApplySetValueOperation(String formattingString, Object... objects) {
+  private static void logInApplySetValueOperation(
+      Level loglevel, String formattingString, Object... objects) {
     // Finding the caller here is relatively expensive and shows up in profiling, so provide it
     // manually.
     logger.logp(
-        Level.INFO,
+        loglevel,
         "InvocationPolicyEnforcer",
         "applySetValueOperation",
         String.format(formattingString, objects));
@@ -515,85 +535,86 @@ public final class InvocationPolicyEnforcer {
 
   private static void applySetValueOperation(
       OptionsParser parser,
-      FlagPolicy flagPolicy,
+      FlagPolicyWithContext flagPolicy,
       OptionValueDescription valueDescription,
-      OptionDescription optionDescription)
+      Level loglevel)
       throws OptionsParsingException {
-    SetValue setValue = flagPolicy.getSetValue();
-    OptionDefinition optionDefinition = optionDescription.getOptionDefinition();
+    SetValue setValue = flagPolicy.policy.getSetValue();
+    OptionDefinition optionDefinition = flagPolicy.description.getOptionDefinition();
 
     // SetValue.flag_value must have at least 1 value.
     if (setValue.getFlagValueCount() == 0) {
       throw new OptionsParsingException(
           String.format(
-              "SetValue operation from invocation policy for flag '%s' does not have a value",
-              optionDefinition.getOptionName()));
+              "SetValue operation from invocation policy for %s does not have a value",
+              optionDefinition));
     }
 
     // Flag must allow multiple values if multiple values are specified by the policy.
     if (setValue.getFlagValueCount() > 1
-        && !optionDescription.getOptionDefinition().allowsMultiple()) {
+        && !flagPolicy.description.getOptionDefinition().allowsMultiple()) {
       throw new OptionsParsingException(
           String.format(
-              "SetValue operation from invocation policy sets multiple values for flag '%s' which "
+              "SetValue operation from invocation policy sets multiple values for %s which "
                   + "does not allow multiple values",
-              optionDefinition.getOptionName()));
+              optionDefinition));
     }
 
     if (setValue.getOverridable() && valueDescription != null) {
       // The user set the value for the flag but the flag policy is overridable, so keep the user's
       // value.
       logInApplySetValueOperation(
-          "Keeping value '%s' from source '%s' for flag '%s' "
-              + "because the invocation policy specifying the value(s) '%s' is overridable",
+          loglevel,
+          "Keeping value '%s' from source '%s' for %s because the invocation policy specifying "
+              + "the value(s) '%s' is overridable",
           valueDescription.getValue(),
           valueDescription.getSourceString(),
-          optionDefinition.getOptionName(),
+          optionDefinition,
           setValue.getFlagValueList());
     } else {
 
       if (!setValue.getAppend()) {
         // Clear the value in case the flag is a repeated flag so that values don't accumulate.
-        parser.clearValue(optionDescription.getOptionDefinition());
+        parser.clearValue(flagPolicy.description.getOptionDefinition());
       }
 
       // Set all the flag values from the policy.
       for (String flagValue : setValue.getFlagValueList()) {
         if (valueDescription == null) {
           logInApplySetValueOperation(
-              "Setting value for flag '%s' from invocation policy to '%s', overriding the "
-                  + "default value '%s'",
-              optionDefinition.getOptionName(), flagValue, optionDefinition.getDefaultValue());
+              loglevel,
+              "Setting value for %s from invocation policy to '%s', overriding the default value "
+                  + "'%s'",
+              optionDefinition,
+              flagValue,
+              optionDefinition.getDefaultValue());
         } else {
           logInApplySetValueOperation(
-              "Setting value for flag '%s' from invocation policy to '%s', overriding "
-                  + "value '%s' from '%s'",
-              optionDefinition.getOptionName(),
+              loglevel,
+              "Setting value for %s from invocation policy to '%s', overriding value '%s' from "
+                  + "'%s'",
+              optionDefinition,
               flagValue,
               valueDescription.getValue(),
               valueDescription.getSourceString());
         }
-        setFlagValue(parser, optionDefinition, flagValue);
+
+        parser.addOptionValueAtSpecificPriority(flagPolicy.origin, optionDefinition, flagValue);
       }
     }
   }
 
   private static void applyUseDefaultOperation(
-      OptionsParser parser, String policyType, OptionDefinition option)
+      OptionsParser parser, String policyType, OptionDefinition option, Level loglevel)
       throws OptionsParsingException {
     OptionValueDescription clearedValueDescription = parser.clearValue(option);
     if (clearedValueDescription != null) {
       // Log the removed value.
       String clearedFlagName = clearedValueDescription.getOptionDefinition().getOptionName();
-
-      OptionDescription desc =
-          parser.getOptionDescription(
-              clearedFlagName, OptionPriority.INVOCATION_POLICY, INVOCATION_POLICY_SOURCE);
-      Object clearedFlagDefaultValue = null;
-      if (desc != null) {
-        clearedFlagDefaultValue = desc.getOptionDefinition().getDefaultValue();
-      }
-      logger.info(
+      Object clearedFlagDefaultValue =
+          clearedValueDescription.getOptionDefinition().getDefaultValue();
+      logger.log(
+          loglevel,
           String.format(
               "Using default value '%s' for flag '%s' as specified by %s invocation policy, "
                   + "overriding original value '%s' from '%s'",
@@ -605,34 +626,40 @@ public final class InvocationPolicyEnforcer {
     }
   }
 
-  /**
-   * Checks the user's flag values against a filtering function.
-   */
+  /** Checks the user's flag values against a filtering function. */
   private abstract static class FilterValueOperation {
 
-    private static final FilterValueOperation ALLOW_VALUE_OPERATION =
-        new FilterValueOperation("Allow") {
-          @Override
-          boolean isFlagValueAllowed(Set<Object> convertedPolicyValues, Object value) {
-            return convertedPolicyValues.contains(value);
-          }
-        };
-
-    private static final FilterValueOperation DISALLOW_VALUE_OPERATION =
-        new FilterValueOperation("Disallow") {
-          @Override
-          boolean isFlagValueAllowed(Set<Object> convertedPolicyValues, Object value) {
-            // In a disallow operation, the values that the flag policy specifies are not allowed,
-            // so the value is allowed if the set of policy values does not contain the current
-            // flag value.
-            return !convertedPolicyValues.contains(value);
-          }
-        };
+    private static final class AllowValueOperation extends FilterValueOperation {
+      AllowValueOperation(Level loglevel) {
+        super("Allow", loglevel);
+      }
+
+      @Override
+      boolean isFlagValueAllowed(Set<Object> convertedPolicyValues, Object value) {
+        return convertedPolicyValues.contains(value);
+      }
+    }
+
+    private static final class DisallowValueOperation extends FilterValueOperation {
+      DisallowValueOperation(Level loglevel) {
+        super("Disalllow", loglevel);
+      }
+
+      @Override
+      boolean isFlagValueAllowed(Set<Object> convertedPolicyValues, Object value) {
+        // In a disallow operation, the values that the flag policy specifies are not allowed,
+        // so the value is allowed if the set of policy values does not contain the current
+        // flag value.
+        return !convertedPolicyValues.contains(value);
+      }
+    }
 
     private final String policyType;
+    private final Level loglevel;
 
-    FilterValueOperation(String policyType) {
+    FilterValueOperation(String policyType, Level loglevel) {
       this.policyType = policyType;
+      this.loglevel = loglevel;
     }
 
     /**
@@ -646,6 +673,7 @@ public final class InvocationPolicyEnforcer {
 
     void apply(
         OptionsParser parser,
+        OptionInstanceOrigin origin,
         List<String> policyValues,
         String newValue,
         boolean useDefault,
@@ -684,11 +712,9 @@ public final class InvocationPolicyEnforcer {
         if (!defaultValueAllowed && useDefault) {
           throw new OptionsParsingException(
               String.format(
-                  "%sValues policy disallows the default value '%s' for flag '%s' but also "
-                      + "specifies to use the default value",
-                  policyType,
-                  optionDefinition.getDefaultValue(),
-                  optionDefinition.getOptionName()));
+                  "%sValues policy disallows the default value '%s' for %s but also specifies to "
+                      + "use the default value",
+                  policyType, optionDefinition.getDefaultValue(), optionDefinition));
         }
       }
 
@@ -698,10 +724,12 @@ public final class InvocationPolicyEnforcer {
         // the flag allowing multiple values, however, flags that allow multiple values cannot have
         // default values, and their value is always the empty list if they haven't been specified,
         // which is why new_default_value is not a repeated field.
-        checkDefaultValue(parser, optionDescription, policyValues, newValue, convertedPolicyValues);
+        checkDefaultValue(
+            parser, origin, optionDescription, policyValues, newValue, convertedPolicyValues);
       } else {
         checkUserValue(
             parser,
+            origin,
             optionDescription,
             valueDescription,
             policyValues,
@@ -713,6 +741,7 @@ public final class InvocationPolicyEnforcer {
 
     void checkDefaultValue(
         OptionsParser parser,
+        OptionInstanceOrigin origin,
         OptionDescription optionDescription,
         List<String> policyValues,
         String newValue,
@@ -723,26 +752,27 @@ public final class InvocationPolicyEnforcer {
       if (!isFlagValueAllowed(
           convertedPolicyValues, optionDescription.getOptionDefinition().getDefaultValue())) {
         if (newValue != null) {
-          // Use the default value from the policy.
-          logger.info(
+          // Use the default value from the policy, since the original default is not allowed
+          logger.log(
+              loglevel,
               String.format(
-                  "Overriding default value '%s' for flag '%s' with value '%s' specified by "
-                      + "invocation policy. %sed values are: %s",
+                  "Overriding default value '%s' for %s with value '%s' specified by invocation "
+                      + "policy. %sed values are: %s",
                   optionDefinition.getDefaultValue(),
-                  optionDefinition.getOptionName(),
+                  optionDefinition,
                   newValue,
                   policyType,
                   policyValues));
           parser.clearValue(optionDefinition);
-          setFlagValue(parser, optionDefinition, newValue);
+          parser.addOptionValueAtSpecificPriority(origin, optionDefinition, newValue);
         } else {
           // The operation disallows the default value, but doesn't supply a new value.
           throw new OptionsParsingException(
               String.format(
-                  "Default flag value '%s' for flag '%s' is not allowed by invocation policy, but "
+                  "Default flag value '%s' for %s is not allowed by invocation policy, but "
                       + "the policy does not provide a new value. %sed values are: %s",
                   optionDescription.getOptionDefinition().getDefaultValue(),
-                  optionDefinition.getOptionName(),
+                  optionDefinition,
                   policyType,
                   policyValues));
         }
@@ -751,6 +781,7 @@ public final class InvocationPolicyEnforcer {
 
     void checkUserValue(
         OptionsParser parser,
+        OptionInstanceOrigin origin,
         OptionDescription optionDescription,
         OptionValueDescription valueDescription,
         List<String> policyValues,
@@ -766,13 +797,13 @@ public final class InvocationPolicyEnforcer {
         for (Object value : optionValues) {
           if (!isFlagValueAllowed(convertedPolicyValues, value)) {
             if (useDefault) {
-              applyUseDefaultOperation(parser, policyType + "Values", option);
+              applyUseDefaultOperation(parser, policyType + "Values", option, loglevel);
             } else {
               throw new OptionsParsingException(
                   String.format(
-                      "Flag value '%s' for flag '%s' is not allowed by invocation policy. "
-                          + "%sed values are: %s",
-                      value, option.getOptionName(), policyType, policyValues));
+                      "Flag value '%s' for %s is not allowed by invocation policy. %sed values "
+                          + "are: %s",
+                      value, option, policyType, policyValues));
             }
           }
         }
@@ -781,38 +812,25 @@ public final class InvocationPolicyEnforcer {
 
         if (!isFlagValueAllowed(convertedPolicyValues, valueDescription.getValue())) {
           if (newValue != null) {
-            logger.info(
+            logger.log(
+                loglevel,
                 String.format(
-                    "Overriding disallowed value '%s' for flag '%s' with value '%s' "
+                    "Overriding disallowed value '%s' for %s with value '%s' "
                         + "specified by invocation policy. %sed values are: %s",
-                    valueDescription.getValue(),
-                    option.getOptionName(),
-                    newValue,
-                    policyType,
-                    policyValues));
+                    valueDescription.getValue(), option, newValue, policyType, policyValues));
             parser.clearValue(option);
-            setFlagValue(parser, option, newValue);
+            parser.addOptionValueAtSpecificPriority(origin, option, newValue);
           } else if (useDefault) {
-            applyUseDefaultOperation(parser, policyType + "Values", option);
+            applyUseDefaultOperation(parser, policyType + "Values", option, loglevel);
           } else {
             throw new OptionsParsingException(
                 String.format(
-                    "Flag value '%s' for flag '%s' is not allowed by invocation policy and the "
+                    "Flag value '%s' for %s is not allowed by invocation policy and the "
                         + "policy does not specify a new value. %sed values are: %s",
-                    valueDescription.getValue(), option.getOptionName(), policyType, policyValues));
+                    valueDescription.getValue(), option, policyType, policyValues));
           }
         }
       }
     }
   }
-
-  private static void setFlagValue(OptionsParser parser, OptionDefinition flag, String flagValue)
-      throws OptionsParsingException {
-
-    parser.parseWithSourceFunction(
-        OptionPriority.INVOCATION_POLICY,
-        INVOCATION_POLICY_SOURCE_FUNCTION,
-        ImmutableList.of(String.format("--%s=%s", flag.getOptionName(), flagValue)));
-  }
 }
-
diff --git a/java/com/google/devtools/common/options/LegacyParamsFilePreProcessor.java b/java/com/google/devtools/common/options/LegacyParamsFilePreProcessor.java
index 9e8eeb0..56a7d2c 100644
--- a/java/com/google/devtools/common/options/LegacyParamsFilePreProcessor.java
+++ b/java/com/google/devtools/common/options/LegacyParamsFilePreProcessor.java
@@ -27,7 +27,11 @@ import java.util.NoSuchElementException;
  * A {@link ParamsFilePreProcessor} that processes a parameter file using a custom format. This
  * format assumes each parameter is separated by whitespace and allows arguments to use single and
  * double quotes and quote and whitespace escaping.
+ *
+ * <p><em>NOTE:</em> This class is deprecated; use either {@link ShellQuotedParamsFilePreProcessor}
+ * or {@link UnquotedParamsFilePreProcessor} depending on the format of the provided params file.
  */
+@Deprecated
 public class LegacyParamsFilePreProcessor extends ParamsFilePreProcessor {
 
   public LegacyParamsFilePreProcessor(FileSystem fs) {
diff --git a/java/com/google/devtools/common/options/Option.java b/java/com/google/devtools/common/options/Option.java
index 92436fd..45f320a 100644
--- a/java/com/google/devtools/common/options/Option.java
+++ b/java/com/google/devtools/common/options/Option.java
@@ -160,12 +160,17 @@ public @interface Option {
   Class<? extends ExpansionFunction> expansionFunction() default ExpansionFunction.class;
 
   /**
-   * If the option requires that additional options be implicitly appended, this field will contain
-   * the additional options. Implicit dependencies are parsed at the end of each {@link
-   * OptionsParser#parse} invocation, and override options specified in the same call. However, they
-   * can be overridden by options specified in a later call or by options with a higher priority.
+   * Additional options that need to be implicitly added for this option.
    *
-   * @see OptionPriority
+   * <p>Nothing guarantees that these options are not overridden by later or higher-priority values
+   * for the same options, so if this is truly a requirement, the user should check that the correct
+   * set of options is set.
+   *
+   * <p>These requirements are added for ANY mention of this option, so may not work as intended: in
+   * the case where a user is trying to explicitly turn off a flag (say, by setting a boolean flag
+   * to its default value of false), the mention will still turn on its requirements. For this
+   * reason, it is best not to use this feature, and rely on expansion flags if multi-flag groupings
+   * are needed.
    */
   String[] implicitRequirements() default {};
 
diff --git a/java/com/google/devtools/common/options/OptionDefinition.java b/java/com/google/devtools/common/options/OptionDefinition.java
index 40da044..1c01932 100644
--- a/java/com/google/devtools/common/options/OptionDefinition.java
+++ b/java/com/google/devtools/common/options/OptionDefinition.java
@@ -303,6 +303,11 @@ public class OptionDefinition {
     return field.hashCode();
   }
 
+  @Override
+  public String toString() {
+    return String.format("option '--%s'", getOptionName());
+  }
+
   static final Comparator<OptionDefinition> BY_OPTION_NAME =
       Comparator.comparing(OptionDefinition::getOptionName);
 
diff --git a/java/com/google/devtools/common/options/OptionDocumentationCategory.java b/java/com/google/devtools/common/options/OptionDocumentationCategory.java
index 1f27046..dd5420c 100644
--- a/java/com/google/devtools/common/options/OptionDocumentationCategory.java
+++ b/java/com/google/devtools/common/options/OptionDocumentationCategory.java
@@ -54,6 +54,12 @@ public enum OptionDocumentationCategory {
   /** This option's primary purpose is to affect the verbosity, format or location of logging. */
   LOGGING,
 
+  /**
+   * This option affects how strictly Bazel enforces valid build inputs (rule definitions,
+   * flag combinations, etc).
+   */
+  INPUT_STRICTNESS,
+
   /** This option deals with how to go about executing the build. */
   EXECUTION_STRATEGY,
 
diff --git a/java/com/google/devtools/common/options/OptionEffectTag.java b/java/com/google/devtools/common/options/OptionEffectTag.java
index 136929a..500643f 100644
--- a/java/com/google/devtools/common/options/OptionEffectTag.java
+++ b/java/com/google/devtools/common/options/OptionEffectTag.java
@@ -139,8 +139,12 @@ public enum OptionEffectTag {
 
   /**
    * This option is used to change command line arguments of one or more actions during the build.
+   *
+   * <p>Even though many options implicitly change command line arguments because they change
+   * configured target analysis, this setting is intended for options specifically meant for
+   * for that purpose.
    */
-  ACTION_OPTIONS(13),
+  ACTION_COMMAND_LINES(13),
 
   /** This option is used to change the testrunner environment of the build. */
   TEST_RUNNER(14);
diff --git a/java/com/google/devtools/common/options/OptionFilterDescriptions.java b/java/com/google/devtools/common/options/OptionFilterDescriptions.java
new file mode 100644
index 0000000..2a7999d
--- /dev/null
+++ b/java/com/google/devtools/common/options/OptionFilterDescriptions.java
@@ -0,0 +1,180 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.common.options;
+
+import com.google.common.collect.ImmutableMap;
+
+/**
+ * Provides descriptions of the options filters, for use in generated documentation and usage text.
+ */
+public class OptionFilterDescriptions {
+
+  /** The order that the categories should be listed in. */
+  static OptionDocumentationCategory[] documentationOrder = {
+      OptionDocumentationCategory.BAZEL_CLIENT_OPTIONS,
+      OptionDocumentationCategory.EXECUTION_STRATEGY,
+      OptionDocumentationCategory.TOOLCHAIN,
+      OptionDocumentationCategory.OUTPUT_SELECTION,
+      OptionDocumentationCategory.OUTPUT_PARAMETERS,
+      OptionDocumentationCategory.INPUT_STRICTNESS,
+      OptionDocumentationCategory.SIGNING,
+      OptionDocumentationCategory.TESTING,
+      OptionDocumentationCategory.QUERY,
+      OptionDocumentationCategory.BUILD_TIME_OPTIMIZATION,
+      OptionDocumentationCategory.LOGGING,
+      OptionDocumentationCategory.GENERIC_INPUTS,
+      OptionDocumentationCategory.UNCATEGORIZED
+  };
+
+  static ImmutableMap<OptionDocumentationCategory, String> getOptionCategoriesEnumDescription(
+      String productName) {
+    ImmutableMap.Builder<OptionDocumentationCategory, String> optionCategoriesBuilder =
+        ImmutableMap.builder();
+    optionCategoriesBuilder
+        .put(
+            OptionDocumentationCategory.UNCATEGORIZED,
+            "Miscellaneous options, not otherwise categorized.")
+        .put( // Here for completeness, the help output should not include this option.
+            OptionDocumentationCategory.UNDOCUMENTED,
+            "This feature should not be documented, as it is not meant for general use")
+        .put(
+            OptionDocumentationCategory.BAZEL_CLIENT_OPTIONS,
+            "Options that appear before the command and are parsed by the client")
+        .put(
+            OptionDocumentationCategory.LOGGING,
+            "Options that affect the verbosity, format or location of logging")
+        .put(OptionDocumentationCategory.EXECUTION_STRATEGY, "Options that control build execution")
+        .put(
+            OptionDocumentationCategory.BUILD_TIME_OPTIMIZATION,
+            "Options that trigger optimizations of the build time")
+        .put(
+            OptionDocumentationCategory.OUTPUT_SELECTION,
+            "Options that control the output of the command")
+        .put(
+            OptionDocumentationCategory.OUTPUT_PARAMETERS,
+            "Options that let the user configure the intended output, affecting its value, as "
+                + "opposed to its existence")
+        .put(
+            OptionDocumentationCategory.INPUT_STRICTNESS,
+            "Options that affect how strictly Bazel enforces valid build inputs (rule definitions, "
+                + " flag combinations, etc.)")
+        .put(
+            OptionDocumentationCategory.SIGNING,
+            "Options that affect the signing outputs of a build")
+        .put(
+            OptionDocumentationCategory.TESTING,
+            "Options that govern the behavior of the test environment or test runner")
+        .put(
+            OptionDocumentationCategory.TOOLCHAIN,
+            "Options that configure the toolchain used for action execution")
+        .put(OptionDocumentationCategory.QUERY, "Options relating to query output and semantics")
+        .put(
+            OptionDocumentationCategory.GENERIC_INPUTS,
+            "Options specifying or altering a generic input to a Bazel command that does not fall "
+                + "into other categories.");
+    return optionCategoriesBuilder.build();
+  }
+
+  public static ImmutableMap<OptionEffectTag, String> getOptionEffectTagDescription(
+      String productName) {
+    ImmutableMap.Builder<OptionEffectTag, String> effectTagDescriptionBuilder =
+        ImmutableMap.builder();
+    effectTagDescriptionBuilder
+        .put(OptionEffectTag.UNKNOWN, "This option has unknown, or undocumented, effect.")
+        .put(OptionEffectTag.NO_OP, "This option has literally no effect.")
+        .put(
+            OptionEffectTag.LOSES_INCREMENTAL_STATE,
+            "Changing the value of this option can cause significant loss of incremental "
+                + "state, which slows builds. State could be lost due to a server restart or to "
+                + "invalidation of a large part of the dependency graph.")
+        .put(
+            OptionEffectTag.CHANGES_INPUTS,
+            "This option actively changes the inputs that "
+                + productName
+                + " considers for the build, such as filesystem restrictions, repository versions, "
+                + "or other options.")
+        .put(
+            OptionEffectTag.AFFECTS_OUTPUTS,
+            "This option affects "
+                + productName
+                + "'s outputs. This tag is intentionally broad, can include transitive affects, "
+                + "and does not specify the type of output it affects.")
+        .put(
+            OptionEffectTag.BUILD_FILE_SEMANTICS,
+            "This option affects the semantics of BUILD or .bzl files.")
+        .put(
+            OptionEffectTag.BAZEL_INTERNAL_CONFIGURATION,
+            "This option affects settings of "
+                + productName
+                + "-internal machinery. This tag does not, on its own, mean that build artifacts "
+                + "are affected.")
+        .put(
+            OptionEffectTag.LOADING_AND_ANALYSIS,
+            "This option affects the loading and analysis of dependencies, and the building "
+                + "of the dependency graph.")
+        .put(
+            OptionEffectTag.EXECUTION,
+            "This option affects the execution phase, such as sandboxing or remote execution "
+                + "related options.")
+        .put(
+            OptionEffectTag.HOST_MACHINE_RESOURCE_OPTIMIZATIONS,
+            "This option triggers an optimization that may be machine specific and is not "
+                + "guaranteed to work on all machines. The optimization could include a tradeoff "
+                + "with other aspects of performance, such as memory or cpu cost.")
+        .put(
+            OptionEffectTag.EAGERNESS_TO_EXIT,
+            "This option changes how eagerly "
+                + productName
+                + " will exit from a failure, where a choice between continuing despite the "
+                + "failure and ending the invocation exists.")
+        .put(
+            OptionEffectTag.BAZEL_MONITORING,
+            "This option is used to monitor " + productName + "'s behavior and performance.")
+        .put(
+            OptionEffectTag.TERMINAL_OUTPUT,
+            "This option affects " + productName + "'s terminal output.")
+        .put(
+            OptionEffectTag.ACTION_COMMAND_LINES,
+            "This option changes the command line arguments of one or more build actions.")
+        .put(
+            OptionEffectTag.TEST_RUNNER,
+            "This option changes the testrunner environment of the build.");
+    return effectTagDescriptionBuilder.build();
+  }
+
+  public static ImmutableMap<OptionMetadataTag, String> getOptionMetadataTagDescription(
+      String productName) {
+    ImmutableMap.Builder<OptionMetadataTag, String> effectTagDescriptionBuilder =
+        ImmutableMap.builder();
+    effectTagDescriptionBuilder
+        .put(
+            OptionMetadataTag.EXPERIMENTAL,
+            "This option triggers an experimental feature with no guarantees of functionality.")
+        .put(
+            OptionMetadataTag.INCOMPATIBLE_CHANGE,
+            "This option triggers a breaking change. Use this option to test your migration "
+                + "readiness or get early access to the new feature")
+        .put(
+            OptionMetadataTag.DEPRECATED,
+            "This option is deprecated. It might be that the feature it affects is deprecated, "
+                + "or that another method of supplying the information is preferred.")
+        .put(
+            OptionMetadataTag.HIDDEN, // Here for completeness, these options are UNDOCUMENTED.
+            "This option should not be used by a user, and should not be logged.")
+        .put(
+            OptionMetadataTag.INTERNAL, // Here for completeness, these options are UNDOCUMENTED.
+            "This option isn't even a option, and should not be logged.");
+    return effectTagDescriptionBuilder.build();
+  }
+}
diff --git a/java/com/google/devtools/common/options/OptionPriority.java b/java/com/google/devtools/common/options/OptionPriority.java
index a28f012..96c471e 100644
--- a/java/com/google/devtools/common/options/OptionPriority.java
+++ b/java/com/google/devtools/common/options/OptionPriority.java
@@ -13,50 +13,98 @@
 // limitations under the License.
 package com.google.devtools.common.options;
 
+import java.util.Objects;
+
 /**
- * The priority of option values, in order of increasing priority.
- *
- * <p>In general, new values for options can only override values with a lower or
- * equal priority. Option values provided in annotations in an options class are
- * implicitly at the priority {@code DEFAULT}.
+ * The position of an option in the interpretation order. Options are interpreted using a
+ * last-option-wins system for single valued options, and are listed in that order for
+ * multiple-valued options.
  *
- * <p>The ordering of the priorities is the source-code order. This is consistent
- * with the automatically generated {@code compareTo} method as specified by the
- * Java Language Specification. DO NOT change the source-code order of these
- * values, or you will break code that relies on the ordering.
+ * <p>The position of the option is in category order, and within the priority category in index
+ * order.
  */
-public enum OptionPriority {
+public class OptionPriority implements Comparable<OptionPriority> {
+  private final PriorityCategory priorityCategory;
+  private final int index;
 
-  /**
-   * The priority of values specified in the {@link Option} annotation. This
-   * should never be specified in calls to {@link OptionsParser#parse}.
-   */
-  DEFAULT,
+  private OptionPriority(PriorityCategory priorityCategory, int index) {
+    this.priorityCategory = priorityCategory;
+    this.index = index;
+  }
 
-  /**
-   * Overrides default options at runtime, while still allowing the values to be
-   * overridden manually.
-   */
-  COMPUTED_DEFAULT,
+  public static OptionPriority lowestOptionPriorityAtCategory(PriorityCategory category) {
+    return new OptionPriority(category, 0);
+  }
 
-  /**
-   * For options coming from a configuration file or rc file.
-   */
-  RC_FILE,
+  public static OptionPriority nextOptionPriority(OptionPriority priority) {
+    return new OptionPriority(priority.priorityCategory, priority.index + 1);
+  }
 
-  /**
-   * For options coming from the command line.
-   */
-  COMMAND_LINE,
+  public PriorityCategory getPriorityCategory() {
+    return priorityCategory;
+  }
 
-  /**
-   * For options coming from invocation policy.
-   */
-  INVOCATION_POLICY,
+  @Override
+  public int compareTo(OptionPriority o) {
+    if (priorityCategory.equals(o.priorityCategory)) {
+      return index - o.index;
+    }
+    return 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 false;
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(priorityCategory, index);
+  }
 
   /**
-   * This priority can be used to unconditionally override any user-provided options.
-   * This should be used rarely and with caution!
+   * The priority of option values, in order of increasing priority.
+   *
+   * <p>In general, new values for options can only override values with a lower or equal priority.
+   * Option values provided in annotations in an options class are implicitly at the priority {@code
+   * DEFAULT}.
+   *
+   * <p>The ordering of the priorities is the source-code order. This is consistent with the
+   * automatically generated {@code compareTo} method as specified by the Java Language
+   * Specification. DO NOT change the source-code order of these values, or you will break code that
+   * relies on the ordering.
    */
-  SOFTWARE_REQUIREMENT;
+  public enum PriorityCategory {
+
+    /**
+     * The priority of values specified in the {@link Option} annotation. This should never be
+     * specified in calls to {@link OptionsParser#parse}.
+     */
+    DEFAULT,
+
+    /**
+     * Overrides default options at runtime, while still allowing the values to be overridden
+     * manually.
+     */
+    COMPUTED_DEFAULT,
+
+    /** For options coming from a configuration file or rc file. */
+    RC_FILE,
+
+    /** For options coming from the command line. */
+    COMMAND_LINE,
+
+    /** For options coming from invocation policy. */
+    INVOCATION_POLICY,
+
+    /**
+     * This priority can be used to unconditionally override any user-provided options. This should
+     * be used rarely and with caution!
+     */
+    SOFTWARE_REQUIREMENT
+  }
 }
diff --git a/java/com/google/devtools/common/options/OptionValueDescription.java b/java/com/google/devtools/common/options/OptionValueDescription.java
index 0d81d49..0d31137 100644
--- a/java/com/google/devtools/common/options/OptionValueDescription.java
+++ b/java/com/google/devtools/common/options/OptionValueDescription.java
@@ -15,12 +15,15 @@
 package com.google.devtools.common.options;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
 import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ListMultimap;
 import com.google.devtools.common.options.OptionsParser.ConstructionException;
-import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Comparator;
 import java.util.List;
+import java.util.Map.Entry;
 import java.util.stream.Collectors;
 
 /**
@@ -46,10 +49,29 @@ public abstract class OptionValueDescription {
   /** Returns the source(s) of this option, if there were multiple, duplicates are removed. */
   public abstract String getSourceString();
 
-  abstract void addOptionInstance(
-      ParsedOptionDescription parsedOption,
-      List<String> warnings)
-      throws OptionsParsingException;
+  /**
+   * Add an instance of the option to this value. The various types of options are in charge of
+   * making sure that the value is correctly stored, with proper tracking of its priority and
+   * placement amongst other options.
+   *
+   * @return a bundle containing arguments that need to be parsed further.
+   */
+  abstract ExpansionBundle addOptionInstance(
+      ParsedOptionDescription parsedOption, List<String> warnings) throws OptionsParsingException;
+
+  /**
+   * Grouping of convenience for the options that expand to other options, to attach an
+   * option-appropriate source string along with the options that need to be parsed.
+   */
+  public static class ExpansionBundle {
+    List<String> expansionArgs;
+    String sourceOfExpansionArgs;
+
+    public ExpansionBundle(List<String> args, String source) {
+      expansionArgs = args;
+      sourceOfExpansionArgs = source;
+    }
+  }
 
   /**
    * For the given option, returns the correct type of OptionValueDescription, to which unparsed
@@ -58,11 +80,12 @@ public abstract class OptionValueDescription {
    * <p>The categories of option types are non-overlapping, an invariant checked by the
    * OptionProcessor at compile time.
    */
-  public static OptionValueDescription createOptionValueDescription(OptionDefinition option) {
-    if (option.allowsMultiple()) {
+  public static OptionValueDescription createOptionValueDescription(
+      OptionDefinition option, OptionsData optionsData) {
+    if (option.isExpansionOption()) {
+      return new ExpansionOptionValueDescription(option, optionsData);
+    } else if (option.allowsMultiple()) {
       return new RepeatableOptionValueDescription(option);
-    } else if (option.isExpansionOption()) {
-      return new ExpansionOptionValueDescription(option);
     } else if (option.hasImplicitRequirements()) {
       return new OptionWithImplicitRequirementsValueDescription(option);
     } else if (option.isWrapperOption()) {
@@ -97,9 +120,7 @@ public abstract class OptionValueDescription {
     }
 
     @Override
-    void addOptionInstance(
-        ParsedOptionDescription parsedOption,
-        List<String> warnings) {
+    ExpansionBundle addOptionInstance(ParsedOptionDescription parsedOption, List<String> warnings) {
       throw new IllegalStateException(
           "Cannot add values to the default option value. Create a modifiable "
               + "OptionValueDescription using createOptionValueDescription() instead.");
@@ -138,15 +159,13 @@ public abstract class OptionValueDescription {
 
     // Warnings should not end with a '.' because the internal reporter adds one automatically.
     @Override
-    void addOptionInstance(
-        ParsedOptionDescription parsedOption,
-        List<String> warnings)
+    ExpansionBundle addOptionInstance(ParsedOptionDescription parsedOption, List<String> warnings)
         throws OptionsParsingException {
       // This might be the first value, in that case, just store it!
       if (effectiveOptionInstance == null) {
         effectiveOptionInstance = parsedOption;
         effectiveValue = effectiveOptionInstance.getConvertedValue();
-        return;
+        return null;
       }
 
       // If there was another value, check whether the new one will override it, and if so,
@@ -160,57 +179,52 @@ public abstract class OptionValueDescription {
         OptionDefinition optionThatExpandedToEffectiveValue =
             effectiveOptionInstance.getExpandedFrom();
 
-        // Output warnings:
-        if ((implicitDependent != null) && (optionThatDependsOnEffectiveValue != null)) {
-          if (!implicitDependent.equals(optionThatDependsOnEffectiveValue)) {
+        Object newValue = parsedOption.getConvertedValue();
+        // Output warnings if there is conflicting options set different values in a way that might
+        // not have been obvious to the user, such as through expansions and implicit requirements.
+        if (!effectiveValue.equals(newValue)) {
+          if ((implicitDependent != null) && (optionThatDependsOnEffectiveValue != null)) {
+            if (!implicitDependent.equals(optionThatDependsOnEffectiveValue)) {
+              warnings.add(
+                  String.format(
+                      "%s is implicitly defined by both %s and %s",
+                      optionDefinition, optionThatDependsOnEffectiveValue, implicitDependent));
+            }
+          } else if ((implicitDependent != null)
+              && parsedOption.getPriority().equals(effectiveOptionInstance.getPriority())) {
             warnings.add(
                 String.format(
-                    "Option '%s' is implicitly defined by both option '%s' and option '%s'",
-                    optionDefinition.getOptionName(),
-                    optionThatDependsOnEffectiveValue.getOptionName(),
-                    implicitDependent.getOptionName()));
+                    "%s is implicitly defined by %s; the implicitly set value "
+                        + "overrides the previous one",
+                    optionDefinition, implicitDependent));
+          } else if (optionThatDependsOnEffectiveValue != null) {
+            warnings.add(
+                String.format(
+                    "A new value for %s overrides a previous implicit setting of that "
+                        + "option by %s",
+                    optionDefinition, optionThatDependsOnEffectiveValue));
+          } else if ((parsedOption.getPriority().equals(effectiveOptionInstance.getPriority()))
+              && ((optionThatExpandedToEffectiveValue == null) && (expandedFrom != null))) {
+            // Create a warning if an expansion option overrides an explicit option:
+            warnings.add(
+                String.format(
+                    "%s was expanded and now overrides a previous explicitly specified %s with %s",
+                    expandedFrom,
+                    effectiveOptionInstance.getCommandLineForm(),
+                    parsedOption.getCommandLineForm()));
+          } else if ((optionThatExpandedToEffectiveValue != null) && (expandedFrom != null)) {
+            warnings.add(
+                String.format(
+                    "%s was expanded to from both %s and %s",
+                    optionDefinition, optionThatExpandedToEffectiveValue, expandedFrom));
           }
-        } else if ((implicitDependent != null)
-            && parsedOption.getPriority().equals(effectiveOptionInstance.getPriority())) {
-          warnings.add(
-              String.format(
-                  "Option '%s' is implicitly defined by option '%s'; the implicitly set value "
-                      + "overrides the previous one",
-                  optionDefinition.getOptionName(), implicitDependent.getOptionName()));
-        } else if (optionThatDependsOnEffectiveValue != null) {
-          warnings.add(
-              String.format(
-                  "A new value for option '%s' overrides a previous implicit setting of that "
-                      + "option by option '%s'",
-                  optionDefinition.getOptionName(),
-                  optionThatDependsOnEffectiveValue.getOptionName()));
-        } else if ((parsedOption.getPriority() == effectiveOptionInstance.getPriority())
-            && ((optionThatExpandedToEffectiveValue == null) && (expandedFrom != null))) {
-          // Create a warning if an expansion option overrides an explicit option:
-          warnings.add(
-              String.format(
-                  "The option '%s' was expanded and now overrides a previous explicitly specified "
-                      + "option '%s'",
-                  expandedFrom.getOptionName(), optionDefinition.getOptionName()));
-        } else if ((optionThatExpandedToEffectiveValue != null) && (expandedFrom != null)) {
-          warnings.add(
-              String.format(
-                  "The option '%s' was expanded to from both options '%s' and '%s'",
-                  optionDefinition.getOptionName(),
-                  optionThatExpandedToEffectiveValue.getOptionName(),
-                  expandedFrom.getOptionName()));
         }
 
         // Record the new value:
         effectiveOptionInstance = parsedOption;
-        effectiveValue = parsedOption.getConvertedValue();
-      } else {
-        // The new value does not override the old value, as it has lower priority.
-        warnings.add(
-            String.format(
-                "The lower priority option '%s' does not override the previous value '%s'",
-                parsedOption.getCommandLineForm(), effectiveOptionInstance.getCommandLineForm()));
+        effectiveValue = newValue;
       }
+      return null;
     }
 
     @VisibleForTesting
@@ -249,23 +263,19 @@ public abstract class OptionValueDescription {
     @Override
     public List<Object> getValue() {
       // Sort the results by option priority and return them in a new list. The generic type of
-      // the list is not known at runtime, so we can't use it here. It was already checked in
-      // the constructor, so this is type-safe.
-      List<Object> result = new ArrayList<>();
-      for (OptionPriority priority : OptionPriority.values()) {
-        // If there is no mapping for this key, this check avoids object creation (because
-        // ListMultimap has to return a new object on get) and also an unnecessary addAll call.
-        if (optionValues.containsKey(priority)) {
-          result.addAll(optionValues.get(priority));
-        }
-      }
-      return result;
+      // the list is not known at runtime, so we can't use it here.
+      return optionValues
+          .asMap()
+          .entrySet()
+          .stream()
+          .sorted(Comparator.comparing(Entry::getKey))
+          .map(Entry::getValue)
+          .flatMap(Collection::stream)
+          .collect(Collectors.toList());
     }
 
     @Override
-    void addOptionInstance(
-        ParsedOptionDescription parsedOption,
-        List<String> warnings)
+    ExpansionBundle addOptionInstance(ParsedOptionDescription parsedOption, List<String> warnings)
         throws OptionsParsingException {
       // For repeatable options, we allow flags that take both single values and multiple values,
       // potentially collapsing them down.
@@ -277,6 +287,7 @@ public abstract class OptionValueDescription {
       } else {
         optionValues.put(priority, convertedValue);
       }
+      return null;
     }
   }
 
@@ -286,9 +297,12 @@ public abstract class OptionValueDescription {
    * in {@link Option#expansion()} and flags with an {@link Option#expansionFunction()}.
    */
   static class ExpansionOptionValueDescription extends OptionValueDescription {
+    private final List<String> expansion;
 
-    private ExpansionOptionValueDescription(OptionDefinition optionDefinition) {
+    private ExpansionOptionValueDescription(
+        OptionDefinition optionDefinition, OptionsData optionsData) {
       super(optionDefinition);
+      this.expansion = optionsData.getEvaluatedExpansion(optionDefinition);
       if (!optionDefinition.isExpansionOption()) {
         throw new ConstructionException(
             "Options without expansions can't be tracked using ExpansionOptionValueDescription");
@@ -306,11 +320,22 @@ public abstract class OptionValueDescription {
     }
 
     @Override
-    void addOptionInstance(
-        ParsedOptionDescription parsedOption,
-        List<String> warnings) {
-      // TODO(b/65540004) Deal with expansion options here instead of in parse(), and track their
-      // link to the options they expanded to to.
+    ExpansionBundle addOptionInstance(ParsedOptionDescription parsedOption, List<String> warnings) {
+      if (parsedOption.getUnconvertedValue() != null
+          && !parsedOption.getUnconvertedValue().isEmpty()) {
+        warnings.add(
+            String.format(
+                "%s is an expansion option. It does not accept values, and does not change its "
+                    + "expansion based on the value provided. Value '%s' will be ignored.",
+                optionDefinition, parsedOption.getUnconvertedValue()));
+      }
+
+      return new ExpansionBundle(
+          expansion,
+          (parsedOption.getSource() == null)
+              ? String.format("expanded from %s", optionDefinition)
+              : String.format(
+                  "expanded from %s (source %s)", optionDefinition, parsedOption.getSource()));
     }
   }
 
@@ -327,17 +352,34 @@ public abstract class OptionValueDescription {
     }
 
     @Override
-    void addOptionInstance(
-        ParsedOptionDescription parsedOption,
-        List<String> warnings)
+    ExpansionBundle addOptionInstance(ParsedOptionDescription parsedOption, List<String> warnings)
         throws OptionsParsingException {
       // This is a valued flag, its value is handled the same way as a normal
-      // SingleOptionValueDescription.
-      super.addOptionInstance(parsedOption, warnings);
+      // SingleOptionValueDescription. (We check at compile time that these flags aren't
+      // "allowMultiple")
+      ExpansionBundle superExpansion = super.addOptionInstance(parsedOption, warnings);
+      Preconditions.checkArgument(
+          superExpansion == null, "SingleOptionValueDescription should not expand to anything.");
+      if (parsedOption.getConvertedValue().equals(optionDefinition.getDefaultValue())) {
+        warnings.add(
+            String.format(
+                "%s sets %s to its default value. Since this option has implicit requirements that "
+                    + "are set whenever the option is explicitly provided, regardless of the "
+                    + "value, this will behave differently than letting a default be a default. "
+                    + "Specifically, this options expands to {%s}.",
+                parsedOption.getCommandLineForm(),
+                optionDefinition,
+                String.join(" ", optionDefinition.getImplicitRequirements())));
+      }
 
       // Now deal with the implicit requirements.
-      // TODO(b/65540004) Deal with options with implicit requirements here instead of in parse(),
-      // and track their link to the options they implicitly expanded to to.
+      return new ExpansionBundle(
+          ImmutableList.copyOf(optionDefinition.getImplicitRequirements()),
+          (parsedOption.getSource() == null)
+              ? String.format("implicit requirement of %s", optionDefinition)
+              : String.format(
+                  "implicit requirement of %s (source %s)",
+                  optionDefinition, parsedOption.getSource()));
     }
   }
 
@@ -359,12 +401,22 @@ public abstract class OptionValueDescription {
     }
 
     @Override
-    void addOptionInstance(
-        ParsedOptionDescription parsedOption,
-        List<String> warnings)
+    ExpansionBundle addOptionInstance(ParsedOptionDescription parsedOption, List<String> warnings)
         throws OptionsParsingException {
-      // TODO(b/65540004) Deal with options with implicit requirements here instead of in parse(),
-      // and track their link to the options they implicitly expanded to to.
+      if (!parsedOption.getUnconvertedValue().startsWith("-")) {
+        throw new OptionsParsingException(
+            String.format(
+                "Invalid value format for %s. You may have meant --%s=--%s",
+                optionDefinition,
+                optionDefinition.getOptionName(),
+                parsedOption.getUnconvertedValue()));
+      }
+      return new ExpansionBundle(
+          ImmutableList.of(parsedOption.getUnconvertedValue()),
+          (parsedOption.getSource() == null)
+              ? String.format("unwrapped from %s", optionDefinition)
+              : String.format(
+                  "unwrapped from %s (source %s)", optionDefinition, parsedOption.getSource()));
     }
   }
 }
diff --git a/java/com/google/devtools/common/options/Options.java b/java/com/google/devtools/common/options/Options.java
index b636c09..0783480 100644
--- a/java/com/google/devtools/common/options/Options.java
+++ b/java/com/google/devtools/common/options/Options.java
@@ -51,7 +51,7 @@ public class Options<O extends OptionsBase> {
   public static <O extends OptionsBase> Options<O> parse(Class<O> optionsClass, String... args)
       throws OptionsParsingException {
     OptionsParser parser = OptionsParser.newOptionsParser(optionsClass);
-    parser.parse(OptionPriority.COMMAND_LINE, null, Arrays.asList(args));
+    parser.parse(OptionPriority.PriorityCategory.COMMAND_LINE, null, Arrays.asList(args));
     List<String> remainingArgs = parser.getResidue();
     return new Options<>(parser.getOptions(optionsClass), remainingArgs.toArray(new String[0]));
   }
diff --git a/java/com/google/devtools/common/options/OptionsData.java b/java/com/google/devtools/common/options/OptionsData.java
index 5b9a436..63cac24 100644
--- a/java/com/google/devtools/common/options/OptionsData.java
+++ b/java/com/google/devtools/common/options/OptionsData.java
@@ -14,14 +14,12 @@
 
 package com.google.devtools.common.options;
 
-import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import java.lang.reflect.Constructor;
 import java.lang.reflect.Modifier;
 import java.util.Collection;
 import java.util.Map;
-import javax.annotation.Nullable;
 import javax.annotation.concurrent.Immutable;
 
 /**
@@ -32,87 +30,26 @@ import javax.annotation.concurrent.Immutable;
 @Immutable
 final class OptionsData extends IsolatedOptionsData {
 
-  /**
-   * Keeps track of all the information needed to calculate expansion flags, whether they come from
-   * a static list or a @{link ExpansionFunction} object.
-   */
-  static class ExpansionData {
-    private final ImmutableList<String> staticExpansion;
-    @Nullable private final ExpansionFunction dynamicExpansions;
-
-    ExpansionData(ImmutableList<String> staticExpansion) {
-      Preconditions.checkArgument(staticExpansion != null);
-      this.staticExpansion = staticExpansion;
-      this.dynamicExpansions = null;
-    }
-
-    ExpansionData(ExpansionFunction dynamicExpansions) {
-      Preconditions.checkArgument(dynamicExpansions != null);
-      this.staticExpansion = EMPTY_EXPANSION;
-      this.dynamicExpansions = dynamicExpansions;
-    }
-
-    ImmutableList<String> getExpansion(ExpansionContext context) throws OptionsParsingException {
-      Preconditions.checkArgument(context != null);
-      if (dynamicExpansions != null) {
-        ImmutableList<String> result = dynamicExpansions.getExpansion(context);
-        if (result == null) {
-          String valueString =
-              context.getUnparsedValue() != null ? context.getUnparsedValue() : "(null)";
-          String name = context.getOptionDefinition().getOptionName();
-          throw new OptionsParsingException(
-              "Error expanding option '"
-                  + name
-                  + "': no expansions defined for value: "
-                  + valueString,
-              name);
-        }
-        return result;
-      } else {
-        return staticExpansion;
-      }
-    }
-
-    boolean isEmpty() {
-      return staticExpansion.isEmpty() && (dynamicExpansions == null);
-    }
-  }
-
-  /**
-   * Mapping from each Option-annotated field with expansion information to the {@link
-   * ExpansionData} needed to caclulate it.
-   */
-  private final ImmutableMap<OptionDefinition, ExpansionData> expansionDataForFields;
+  /** Mapping from each option to the (unparsed) options it expands to, if any. */
+  private final ImmutableMap<OptionDefinition, ImmutableList<String>> evaluatedExpansions;
 
   /** Construct {@link OptionsData} by extending an {@link IsolatedOptionsData} with new info. */
   private OptionsData(
-      IsolatedOptionsData base, Map<OptionDefinition, ExpansionData> expansionDataForFields) {
+      IsolatedOptionsData base, Map<OptionDefinition, ImmutableList<String>> evaluatedExpansions) {
     super(base);
-    this.expansionDataForFields = ImmutableMap.copyOf(expansionDataForFields);
+    this.evaluatedExpansions = ImmutableMap.copyOf(evaluatedExpansions);
   }
 
   private static final ImmutableList<String> EMPTY_EXPANSION = ImmutableList.<String>of();
-  private static final ExpansionData EMPTY_EXPANSION_DATA = new ExpansionData(EMPTY_EXPANSION);
 
   /**
    * Returns the expansion of an options field, regardless of whether it was defined using {@link
    * Option#expansion} or {@link Option#expansionFunction}. If the field is not an expansion option,
    * returns an empty array.
    */
-  public ImmutableList<String> getEvaluatedExpansion(
-      OptionDefinition optionDefinition, @Nullable String unparsedValue)
-      throws OptionsParsingException {
-    ExpansionData expansionData = expansionDataForFields.get(optionDefinition);
-    if (expansionData == null) {
-      return EMPTY_EXPANSION;
-    }
-
-    return expansionData.getExpansion(new ExpansionContext(this, optionDefinition, unparsedValue));
-  }
-
-  ExpansionData getExpansionDataForField(OptionDefinition optionDefinition) {
-    ExpansionData result = expansionDataForFields.get(optionDefinition);
-    return result != null ? result : EMPTY_EXPANSION_DATA;
+  public ImmutableList<String> getEvaluatedExpansion(OptionDefinition optionDefinition) {
+    ImmutableList<String> result = evaluatedExpansions.get(optionDefinition);
+    return result != null ? result : EMPTY_EXPANSION;
   }
 
   /**
@@ -126,8 +63,8 @@ final class OptionsData extends IsolatedOptionsData {
     IsolatedOptionsData isolatedData = IsolatedOptionsData.from(classes);
 
     // All that's left is to compute expansions.
-    ImmutableMap.Builder<OptionDefinition, ExpansionData> expansionDataBuilder =
-        ImmutableMap.<OptionDefinition, ExpansionData>builder();
+    ImmutableMap.Builder<OptionDefinition, ImmutableList<String>> evaluatedExpansionsBuilder =
+        ImmutableMap.builder();
     for (Map.Entry<String, OptionDefinition> entry : isolatedData.getAllOptionDefinitions()) {
       OptionDefinition optionDefinition = entry.getValue();
       // Determine either the hard-coded expansion, or the ExpansionFunction class. The
@@ -136,8 +73,7 @@ final class OptionsData extends IsolatedOptionsData {
       Class<? extends ExpansionFunction> expansionFunctionClass =
           optionDefinition.getExpansionFunction();
       if (constExpansion.length > 0) {
-        expansionDataBuilder.put(
-            optionDefinition, new ExpansionData(ImmutableList.copyOf(constExpansion)));
+        evaluatedExpansionsBuilder.put(optionDefinition, ImmutableList.copyOf(constExpansion));
       } else if (optionDefinition.usesExpansionFunction()) {
         if (Modifier.isAbstract(expansionFunctionClass.getModifiers())) {
           throw new AssertionError(
@@ -153,25 +89,10 @@ final class OptionsData extends IsolatedOptionsData {
           // time it is used.
           throw new AssertionError(e);
         }
-
-        ImmutableList<String> staticExpansion;
-        try {
-          staticExpansion =
-              instance.getExpansion(new ExpansionContext(isolatedData, optionDefinition, null));
-          Preconditions.checkState(
-              staticExpansion != null,
-              "Error calling expansion function for option: %s",
-              optionDefinition.getOptionName());
-          expansionDataBuilder.put(optionDefinition, new ExpansionData(staticExpansion));
-        } catch (ExpansionNeedsValueException e) {
-          // This expansion function needs data that isn't available yet. Save the instance and call
-          // it later.
-          expansionDataBuilder.put(optionDefinition, new ExpansionData(instance));
-        } catch (OptionsParsingException e) {
-          throw new IllegalStateException("Error expanding void expansion function: ", e);
-        }
+        ImmutableList<String> expansion = instance.getExpansion(isolatedData);
+        evaluatedExpansionsBuilder.put(optionDefinition, expansion);
       }
     }
-    return new OptionsData(isolatedData, expansionDataBuilder.build());
+    return new OptionsData(isolatedData, evaluatedExpansionsBuilder.build());
   }
 }
diff --git a/java/com/google/devtools/common/options/OptionsParser.java b/java/com/google/devtools/common/options/OptionsParser.java
index 28c2206..f84ee47 100644
--- a/java/com/google/devtools/common/options/OptionsParser.java
+++ b/java/com/google/devtools/common/options/OptionsParser.java
@@ -17,13 +17,14 @@ package com.google.devtools.common.options;
 import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Throwables;
+import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ListMultimap;
 import com.google.common.escape.Escaper;
 import com.google.devtools.common.options.OptionDefinition.NotAnOptionException;
 import java.lang.reflect.Constructor;
 import java.lang.reflect.Field;
-import java.nio.file.FileSystem;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
@@ -32,12 +33,12 @@ import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 import java.util.function.Consumer;
 import java.util.function.Function;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
-import javax.annotation.Nullable;
 
 /**
  * A parser for options. Typical use case in a main method:
@@ -53,9 +54,10 @@ import javax.annotation.Nullable;
  * <p>FooOptions and BarOptions would be options specification classes, derived from OptionsBase,
  * that contain fields annotated with @Option(...).
  *
- * <p>Alternatively, rather than calling {@link #parseAndExitUponError(OptionPriority, String,
- * String[])}, client code may call {@link #parse(OptionPriority,String,List)}, and handle parser
- * exceptions usage messages themselves.
+ * <p>Alternatively, rather than calling {@link
+ * #parseAndExitUponError(OptionPriority.PriorityCategory, String, String[])}, client code may call
+ * {@link #parse(OptionPriority.PriorityCategory,String,List)}, and handle parser exceptions usage
+ * messages themselves.
  *
  * <p>This options parsing implementation has (at least) one design flaw. It allows both '--foo=baz'
  * and '--foo baz' for all options except void, boolean and tristate options. For these, the 'baz'
@@ -150,11 +152,9 @@ public class OptionsParser implements OptionsProvider {
     return newOptionsParser(ImmutableList.<Class<? extends OptionsBase>>of(class1));
   }
 
-  /**
-   * @see #newOptionsParser(Iterable)
-   */
-  public static OptionsParser newOptionsParser(Class<? extends OptionsBase> class1,
-                                               Class<? extends OptionsBase> class2)
+  /** @see #newOptionsParser(Iterable) */
+  public static OptionsParser newOptionsParser(
+      Class<? extends OptionsBase> class1, Class<? extends OptionsBase> class2)
       throws ConstructionException {
     return newOptionsParser(ImmutableList.of(class1, class2));
   }
@@ -200,11 +200,6 @@ public class OptionsParser implements OptionsProvider {
     this.impl.setAllowSingleDashLongOptions(allowSingleDashLongOptions);
   }
 
-  /** Enables the Parser to handle params files located inside the provided {@link FileSystem}. */
-  public void enableParamsFileSupport(FileSystem fs) {
-    enableParamsFileSupport(new LegacyParamsFilePreProcessor(fs));
-  }
-
   /**
    * Enables the Parser to handle params files using the provided {@link ParamsFilePreProcessor}.
    */
@@ -213,18 +208,21 @@ public class OptionsParser implements OptionsProvider {
   }
 
   public void parseAndExitUponError(String[] args) {
-    parseAndExitUponError(OptionPriority.COMMAND_LINE, "unknown", args);
+    parseAndExitUponError(OptionPriority.PriorityCategory.COMMAND_LINE, "unknown", args);
   }
 
   /**
-   * A convenience function for use in main methods. Parses the command line
-   * parameters, and exits upon error. Also, prints out the usage message
-   * if "--help" appears anywhere within {@code args}.
+   * A convenience function for use in main methods. Parses the command line parameters, and exits
+   * upon error. Also, prints out the usage message if "--help" appears anywhere within {@code
+   * args}.
    */
-  public void parseAndExitUponError(OptionPriority priority, String source, String[] args) {
+  public void parseAndExitUponError(
+      OptionPriority.PriorityCategory priority, String source, String[] args) {
     for (String arg : args) {
       if (arg.equals("--help")) {
-        System.out.println(describeOptions(ImmutableMap.of(), HelpVerbosity.LONG));
+        System.out.println(
+            describeOptionsWithDeprecatedCategories(ImmutableMap.of(), HelpVerbosity.LONG));
+
         System.exit(0);
       }
     }
@@ -239,36 +237,41 @@ public class OptionsParser implements OptionsProvider {
 
   /** The metadata about an option, in the context of this options parser. */
   public static final class OptionDescription {
-
     private final OptionDefinition optionDefinition;
-    private final OptionsData.ExpansionData expansionData;
-    private final ImmutableList<ParsedOptionDescription> implicitRequirements;
+    private final ImmutableList<String> evaluatedExpansion;
 
-    OptionDescription(
-        OptionDefinition definition,
-        OptionsData.ExpansionData expansionData,
-        ImmutableList<ParsedOptionDescription> implicitRequirements) {
+    OptionDescription(OptionDefinition definition, OptionsData optionsData) {
       this.optionDefinition = definition;
-      this.expansionData = expansionData;
-      this.implicitRequirements = implicitRequirements;
+      this.evaluatedExpansion = optionsData.getEvaluatedExpansion(optionDefinition);
     }
 
     public OptionDefinition getOptionDefinition() {
       return optionDefinition;
     }
 
-    public ImmutableList<ParsedOptionDescription> getImplicitRequirements() {
-      return implicitRequirements;
-    }
-
     public boolean isExpansion() {
-      return !expansionData.isEmpty();
+      return optionDefinition.isExpansionOption();
     }
 
     /** Return a list of flags that this option expands to. */
-    public ImmutableList<String> getExpansion(ExpansionContext context)
-        throws OptionsParsingException {
-      return expansionData.getExpansion(context);
+    public ImmutableList<String> getExpansion() throws OptionsParsingException {
+      return evaluatedExpansion;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (obj instanceof OptionDescription) {
+        OptionDescription other = (OptionDescription) obj;
+        // Check that the option is the same, with the same expansion.
+        return other.optionDefinition.equals(optionDefinition)
+            && other.evaluatedExpansion.equals(evaluatedExpansion);
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      return optionDefinition.hashCode() + evaluatedExpansion.hashCode();
     }
   }
 
@@ -283,6 +286,78 @@ public class OptionsParser implements OptionsProvider {
    * Returns a description of all the options this parser can digest. In addition to {@link Option}
    * annotations, this method also interprets {@link OptionsUsage} annotations which give an
    * intuitive short description for the options. Options of the same category (see {@link
+   * OptionDocumentationCategory}) will be grouped together.
+   *
+   * @param productName the name of this product (blaze, bazel)
+   * @param helpVerbosity if {@code long}, the options will be described verbosely, including their
+   *     types, defaults and descriptions. If {@code medium}, the descriptions are omitted, and if
+   *     {@code short}, the options are just enumerated.
+   */
+  public String describeOptions(String productName, HelpVerbosity helpVerbosity) {
+    StringBuilder desc = new StringBuilder();
+    LinkedHashMap<OptionDocumentationCategory, List<OptionDefinition>> optionsByCategory =
+        getOptionsSortedByCategory();
+    ImmutableMap<OptionDocumentationCategory, String> optionCategoryDescriptions =
+        OptionFilterDescriptions.getOptionCategoriesEnumDescription(productName);
+    for (Entry<OptionDocumentationCategory, List<OptionDefinition>> e :
+        optionsByCategory.entrySet()) {
+      String categoryDescription = optionCategoryDescriptions.get(e.getKey());
+      List<OptionDefinition> categorizedOptionList = e.getValue();
+
+      // Describe the category if we're going to end up using it at all.
+      if (!categorizedOptionList.isEmpty()) {
+        desc.append("\n").append(categoryDescription).append(":\n");
+      }
+      // Describe the options in this category.
+      for (OptionDefinition optionDef : categorizedOptionList) {
+        OptionsUsage.getUsage(optionDef, desc, helpVerbosity, impl.getOptionsData(), true);
+      }
+    }
+
+    return desc.toString().trim();
+  }
+
+  /**
+   * @return all documented options loaded in this parser, grouped by categories in display order.
+   */
+  private LinkedHashMap<OptionDocumentationCategory, List<OptionDefinition>>
+      getOptionsSortedByCategory() {
+    OptionsData data = impl.getOptionsData();
+    if (data.getOptionsClasses().isEmpty()) {
+      return new LinkedHashMap<>();
+    }
+
+    // Get the documented options grouped by category.
+    ListMultimap<OptionDocumentationCategory, OptionDefinition> optionsByCategories =
+        ArrayListMultimap.create();
+    for (Class<? extends OptionsBase> optionsClass : data.getOptionsClasses()) {
+      for (OptionDefinition optionDefinition :
+          OptionsData.getAllOptionDefinitionsForClass(optionsClass)) {
+        // Only track documented options.
+        if (optionDefinition.getDocumentationCategory()
+            != OptionDocumentationCategory.UNDOCUMENTED) {
+          optionsByCategories.put(optionDefinition.getDocumentationCategory(), optionDefinition);
+        }
+      }
+    }
+
+    // Put the categories into display order and sort the options in each category.
+    LinkedHashMap<OptionDocumentationCategory, List<OptionDefinition>> sortedCategoriesToOptions =
+        new LinkedHashMap<>(OptionFilterDescriptions.documentationOrder.length, 1);
+    for (OptionDocumentationCategory category : OptionFilterDescriptions.documentationOrder) {
+      List<OptionDefinition> optionList = optionsByCategories.get(category);
+      if (optionList != null) {
+        optionList.sort(OptionDefinition.BY_OPTION_NAME);
+        sortedCategoriesToOptions.put(category, optionList);
+      }
+    }
+    return sortedCategoriesToOptions;
+  }
+
+  /**
+   * Returns a description of all the options this parser can digest. In addition to {@link Option}
+   * annotations, this method also interprets {@link OptionsUsage} annotations which give an
+   * intuitive short description for the options. Options of the same category (see {@link
    * Option#category}) will be grouped together.
    *
    * @param categoryDescriptions a mapping from category names to category descriptions.
@@ -291,7 +366,8 @@ public class OptionsParser implements OptionsProvider {
    *     types, defaults and descriptions. If {@code medium}, the descriptions are omitted, and if
    *     {@code short}, the options are just enumerated.
    */
-  public String describeOptions(
+  @Deprecated
+  public String describeOptionsWithDeprecatedCategories(
       Map<String, String> categoryDescriptions, HelpVerbosity helpVerbosity) {
     OptionsData data = impl.getOptionsData();
     StringBuilder desc = new StringBuilder();
@@ -318,7 +394,8 @@ public class OptionsParser implements OptionsProvider {
 
         if (optionDefinition.getDocumentationCategory()
             != OptionDocumentationCategory.UNDOCUMENTED) {
-          OptionsUsage.getUsage(optionDefinition, desc, helpVerbosity, impl.getOptionsData());
+          OptionsUsage.getUsage(
+              optionDefinition, desc, helpVerbosity, impl.getOptionsData(), false);
         }
       }
     }
@@ -326,17 +403,17 @@ public class OptionsParser implements OptionsProvider {
   }
 
   /**
-   * Returns a description of all the options this parser can digest.
-   * In addition to {@link Option} annotations, this method also
-   * interprets {@link OptionsUsage} annotations which give an intuitive short
-   * description for the options.
+   * Returns a description of all the options this parser can digest. In addition to {@link Option}
+   * annotations, this method also interprets {@link OptionsUsage} annotations which give an
+   * intuitive short description for the options.
    *
-   * @param categoryDescriptions a mapping from category names to category
-   *   descriptions.  Options of the same category (see {@link
-   *   Option#category}) will be grouped together, preceded by the description
-   *   of the category.
+   * @param categoryDescriptions a mapping from category names to category descriptions. Options of
+   *     the same category (see {@link Option#category}) will be grouped together, preceded by the
+   *     description of the category.
    */
-  public String describeOptionsHtml(Map<String, String> categoryDescriptions, Escaper escaper) {
+  @Deprecated
+  public String describeOptionsHtmlWithDeprecatedCategories(
+      Map<String, String> categoryDescriptions, Escaper escaper) {
     OptionsData data = impl.getOptionsData();
     StringBuilder desc = new StringBuilder();
     if (!data.getOptionsClasses().isEmpty()) {
@@ -366,7 +443,7 @@ public class OptionsParser implements OptionsProvider {
 
         if (optionDefinition.getDocumentationCategory()
             != OptionDocumentationCategory.UNDOCUMENTED) {
-          OptionsUsage.getUsageHtml(optionDefinition, desc, escaper, impl.getOptionsData());
+          OptionsUsage.getUsageHtml(optionDefinition, desc, escaper, impl.getOptionsData(), false);
         }
       }
       desc.append("</dl>\n");
@@ -375,6 +452,37 @@ public class OptionsParser implements OptionsProvider {
   }
 
   /**
+   * Returns a description of all the options this parser can digest. In addition to {@link Option}
+   * annotations, this method also interprets {@link OptionsUsage} annotations which give an
+   * intuitive short description for the options.
+   */
+  public String describeOptionsHtml(Escaper escaper, String productName) {
+    StringBuilder desc = new StringBuilder();
+    LinkedHashMap<OptionDocumentationCategory, List<OptionDefinition>> optionsByCategory =
+        getOptionsSortedByCategory();
+    ImmutableMap<OptionDocumentationCategory, String> optionCategoryDescriptions =
+        OptionFilterDescriptions.getOptionCategoriesEnumDescription(productName);
+
+    for (Entry<OptionDocumentationCategory, List<OptionDefinition>> e :
+        optionsByCategory.entrySet()) {
+      desc.append("<dl>");
+      String categoryDescription = optionCategoryDescriptions.get(e.getKey());
+      List<OptionDefinition> categorizedOptionsList = e.getValue();
+
+      // Describe the category if we're going to end up using it at all.
+      if (!categorizedOptionsList.isEmpty()) {
+        desc.append(escaper.escape(categoryDescription)).append(":\n");
+      }
+      // Describe the options in this category.
+      for (OptionDefinition optionDef : categorizedOptionsList) {
+        OptionsUsage.getUsageHtml(optionDef, desc, escaper, impl.getOptionsData(), true);
+      }
+      desc.append("</dl>\n");
+    }
+    return desc.toString();
+  }
+
+  /**
    * Returns a string listing the possible flag completion for this command along with the command
    * completion if any. See {@link OptionsUsage#getCompletion(OptionDefinition, StringBuilder)} for
    * more details on the format for the flag completion.
@@ -412,29 +520,30 @@ public class OptionsParser implements OptionsProvider {
    * @return The {@link OptionDescription} for the option, or null if there is no option by the
    *     given name.
    */
-  OptionDescription getOptionDescription(String name, OptionPriority priority, String source)
-      throws OptionsParsingException {
-    return impl.getOptionDescription(name, priority, source);
+  OptionDescription getOptionDescription(String name) throws OptionsParsingException {
+    return impl.getOptionDescription(name);
   }
 
   /**
-   * Returns a description of the options values that get expanded from this option with the given
-   * value.
+   * Returns the parsed options that get expanded from this option, whether it expands due to an
+   * implicit requirement or expansion.
    *
-   * @return The {@link com.google.devtools.common.options.OptionValueDescription>} for the option,
-   *     or null if there is no option by the given name.
+   * @param expansionOption the option that might need to be expanded. If this option does not
+   *     expand to other options, the empty list will be returned.
+   * @param originOfExpansionOption the origin of the option that's being expanded. This function
+   *     will take care of adjusting the source messages as necessary.
    */
-  ImmutableList<ParsedOptionDescription> getExpansionOptionValueDescriptions(
-      OptionDefinition option, @Nullable String optionValue, OptionPriority priority, String source)
+  ImmutableList<ParsedOptionDescription> getExpansionValueDescriptions(
+      OptionDefinition expansionOption, OptionInstanceOrigin originOfExpansionOption)
       throws OptionsParsingException {
-    return impl.getExpansionOptionValueDescriptions(option, optionValue, priority, source);
+    return impl.getExpansionValueDescriptions(expansionOption, originOfExpansionOption);
   }
 
   /**
    * Returns a description of the option value set by the last previous call to {@link
-   * #parse(OptionPriority, String, List)} that successfully set the given option. If the option is
-   * of type {@link List}, the description will correspond to any one of the calls, but not
-   * necessarily the last.
+   * #parse(OptionPriority.PriorityCategory, String, List)} that successfully set the given option.
+   * If the option is of type {@link List}, the description will correspond to any one of the calls,
+   * but not necessarily the last.
    *
    * @return The {@link com.google.devtools.common.options.OptionValueDescription} for the option,
    *     or null if the value has not been set.
@@ -445,48 +554,64 @@ public class OptionsParser implements OptionsProvider {
   }
 
   /**
-   * A convenience method, equivalent to
-   * {@code parse(OptionPriority.COMMAND_LINE, null, Arrays.asList(args))}.
+   * A convenience method, equivalent to {@code parse(PriorityCategory.COMMAND_LINE, null,
+   * Arrays.asList(args))}.
    */
   public void parse(String... args) throws OptionsParsingException {
-    parse(OptionPriority.COMMAND_LINE, null, Arrays.asList(args));
+    parse(OptionPriority.PriorityCategory.COMMAND_LINE, null, Arrays.asList(args));
   }
 
   /**
-   * A convenience method, equivalent to
-   * {@code parse(OptionPriority.COMMAND_LINE, null, args)}.
+   * A convenience method, equivalent to {@code parse(PriorityCategory.COMMAND_LINE, null, args)}.
    */
   public void parse(List<String> args) throws OptionsParsingException {
-    parse(OptionPriority.COMMAND_LINE, null, args);
+    parse(OptionPriority.PriorityCategory.COMMAND_LINE, null, args);
   }
 
   /**
-   * Parses {@code args}, using the classes registered with this parser.
-   * {@link #getOptions(Class)} and {@link #getResidue()} return the results.
-   * May be called multiple times; later options override existing ones if they
-   * have equal or higher priority. The source of options is a free-form string
-   * that can be used for debugging. Strings that cannot be parsed as options
-   * accumulates as residue, if this parser allows it.
+   * Parses {@code args}, using the classes registered with this parser, at the given priority.
+   *
+   * <p>May be called multiple times; later options override existing ones if they have equal or
+   * higher priority. Strings that cannot be parsed as options are accumulated as residue, if this
+   * parser allows it.
    *
-   * @see OptionPriority
+   * <p>{@link #getOptions(Class)} and {@link #getResidue()} will return the results.
+   *
+   * @param priority the priority at which to parse these options. Within this priority category,
+   *     each option will be given an index to track its position. If parse() has already been
+   *     called at this priority, the indexing will continue where it left off, to keep ordering.
+   * @param source the source to track for each option parsed.
+   * @param args the arg list to parse. Each element might be an option, a value linked to an
+   *     option, or residue.
    */
-  public void parse(OptionPriority priority, String source,
-      List<String> args) throws OptionsParsingException {
+  public void parse(OptionPriority.PriorityCategory priority, String source, List<String> args)
+      throws OptionsParsingException {
     parseWithSourceFunction(priority, o -> source, args);
   }
 
   /**
-   * Parses {@code args}, using the classes registered with this parser. {@link #getOptions(Class)}
-   * and {@link #getResidue()} return the results. May be called multiple times; later options
-   * override existing ones if they have equal or higher priority. The source of options is given as
-   * a function that maps option names to the source of the option. Strings that cannot be parsed as
-   * options accumulates as* residue, if this parser allows it.
+   * Parses {@code args}, using the classes registered with this parser, at the given priority.
+   *
+   * <p>May be called multiple times; later options override existing ones if they have equal or
+   * higher priority. Strings that cannot be parsed as options are accumulated as residue, if this
+   * parser allows it.
+   *
+   * <p>{@link #getOptions(Class)} and {@link #getResidue()} will return the results.
+   *
+   * @param priority the priority at which to parse these options. Within this priority category,
+   *     each option will be given an index to track its position. If parse() has already been
+   *     called at this priority, the indexing will continue where it left off, to keep ordering.
+   * @param sourceFunction a function that maps option names to the source of the option.
+   * @param args the arg list to parse. Each element might be an option, a value linked to an
+   *     option, or residue.
    */
   public void parseWithSourceFunction(
-      OptionPriority priority, Function<OptionDefinition, String> sourceFunction, List<String> args)
+      OptionPriority.PriorityCategory priority,
+      Function<OptionDefinition, String> sourceFunction,
+      List<String> args)
       throws OptionsParsingException {
     Preconditions.checkNotNull(priority);
-    Preconditions.checkArgument(priority != OptionPriority.DEFAULT);
+    Preconditions.checkArgument(priority != OptionPriority.PriorityCategory.DEFAULT);
     residue.addAll(impl.parse(priority, sourceFunction, args));
     if (!allowResidue && !residue.isEmpty()) {
       String errorMsg = "Unrecognized arguments: " + Joiner.on(' ').join(residue);
@@ -495,6 +620,20 @@ public class OptionsParser implements OptionsProvider {
   }
 
   /**
+   * @param origin the origin of this option instance, it includes the priority of the value. If
+   *     other values have already been or will be parsed at a higher priority, they might override
+   *     the provided value. If this option already has a value at this priority, this value will
+   *     have precedence, but this should be avoided, as it breaks order tracking.
+   * @param option the option to add the value for.
+   * @param value the value to add at the given priority.
+   */
+  void addOptionValueAtSpecificPriority(
+      OptionInstanceOrigin origin, OptionDefinition option, String value)
+      throws OptionsParsingException {
+    impl.addOptionValueAtSpecificPriority(origin, option, value);
+  }
+
+  /**
    * Clears the given option.
    *
    * <p>This will not affect options objects that have already been retrieved from this parser
@@ -693,4 +832,3 @@ public class OptionsParser implements OptionsProvider {
             + "}");
   }
 }
-
diff --git a/java/com/google/devtools/common/options/OptionsParserImpl.java b/java/com/google/devtools/common/options/OptionsParserImpl.java
index 176d51e..b543328 100644
--- a/java/com/google/devtools/common/options/OptionsParserImpl.java
+++ b/java/com/google/devtools/common/options/OptionsParserImpl.java
@@ -23,13 +23,13 @@ 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.Arrays;
 import java.util.HashMap;
 import java.util.Iterator;
-import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.function.Function;
@@ -54,7 +54,8 @@ class OptionsParserImpl {
    *   OptionDefinition("--port") -> 80
    * </pre>
    *
-   * This map is modified by repeated calls to {@link #parse(OptionPriority,Function,List)}.
+   * This map is modified by repeated calls to {@link #parse(OptionPriority.PriorityCategory,
+   * Function,List)}.
    */
   private final Map<OptionDefinition, OptionValueDescription> optionValues = new HashMap<>();
 
@@ -90,10 +91,9 @@ class OptionsParserImpl {
         }
       };
 
-  /**
-   * Create a new parser object
-   */
+  /** Create a new parser object. Do not accept a null OptionsData object. */
   OptionsParserImpl(OptionsData optionsData) {
+    Preconditions.checkNotNull(optionsData);
     this.optionsData = optionsData;
   }
 
@@ -158,12 +158,7 @@ class OptionsParserImpl {
             })
         // Ignore expansion options.
         .filter(value -> !value.getOptionDefinition().isExpansionOption())
-        .map(
-            value ->
-                "--"
-                    + value.getOptionDefinition().getOptionName()
-                    + "="
-                    + value.getUnconvertedValue())
+        .map(ParsedOptionDescription::getDeprecatedCanonicalForm)
         .collect(toCollection(ArrayList::new));
   }
 
@@ -193,8 +188,9 @@ class OptionsParserImpl {
   }
 
   private void addDeprecationWarning(String optionName, String warning) {
-    warnings.add("Option '" + optionName + "' is deprecated"
-        + (warning.isEmpty() ? "" : ": " + warning));
+    warnings.add(
+        String.format(
+            "Option '%s' is deprecated%s", optionName, (warning.isEmpty() ? "" : ": " + warning)));
   }
 
 
@@ -213,79 +209,58 @@ class OptionsParserImpl {
     return optionValues.get(optionDefinition);
   }
 
-  OptionDescription getOptionDescription(String name, OptionPriority priority, String source)
-      throws OptionsParsingException {
+  OptionDescription getOptionDescription(String name) throws OptionsParsingException {
     OptionDefinition optionDefinition = optionsData.getOptionDefinitionFromName(name);
     if (optionDefinition == null) {
       return null;
     }
-
-    return new OptionDescription(
-        optionDefinition,
-        optionsData.getExpansionDataForField(optionDefinition),
-        getImplicitDependentDescriptions(
-            ImmutableList.copyOf(optionDefinition.getImplicitRequirements()),
-            optionDefinition,
-            priority,
-            source));
-  }
-
-  /** @return A list of the descriptions corresponding to the implicit dependent flags passed in. */
-  private ImmutableList<ParsedOptionDescription> getImplicitDependentDescriptions(
-      ImmutableList<String> options,
-      OptionDefinition implicitDependent,
-      OptionPriority priority,
-      String source)
-      throws OptionsParsingException {
-    ImmutableList.Builder<ParsedOptionDescription> builder = ImmutableList.builder();
-    Iterator<String> optionsIterator = options.iterator();
-
-    Function<OptionDefinition, String> sourceFunction =
-        o ->
-            String.format(
-                "implicitely required for option %s (source: %s)",
-                implicitDependent.getOptionName(), source);
-    while (optionsIterator.hasNext()) {
-      String unparsedFlagExpression = optionsIterator.next();
-      ParsedOptionDescription parsedOption =
-          identifyOptionAndPossibleArgument(
-              unparsedFlagExpression,
-              optionsIterator,
-              priority,
-              sourceFunction,
-              implicitDependent,
-              null);
-      builder.add(parsedOption);
-    }
-    return builder.build();
+    return new OptionDescription(optionDefinition, optionsData);
   }
 
   /**
-   * @return A list of the descriptions corresponding to options expanded from the flag for the
-   *     given value. The value itself is a string, no conversion has taken place.
+   * Implementation of {@link OptionsParser#getExpansionValueDescriptions(OptionDefinition,
+   * OptionInstanceOrigin)}
    */
-  ImmutableList<ParsedOptionDescription> getExpansionOptionValueDescriptions(
-      OptionDefinition expansionFlag,
-      @Nullable String flagValue,
-      OptionPriority priority,
-      String source)
+  ImmutableList<ParsedOptionDescription> getExpansionValueDescriptions(
+      OptionDefinition expansionFlag, OptionInstanceOrigin originOfExpansionFlag)
       throws OptionsParsingException {
     ImmutableList.Builder<ParsedOptionDescription> builder = ImmutableList.builder();
+    OptionInstanceOrigin originOfSubflags;
+    ImmutableList<String> options;
+    if (expansionFlag.hasImplicitRequirements()) {
+      options = ImmutableList.copyOf(expansionFlag.getImplicitRequirements());
+      originOfSubflags =
+          new OptionInstanceOrigin(
+              originOfExpansionFlag.getPriority(),
+              String.format(
+                  "implicitly required by %s (source: %s)",
+                  expansionFlag, originOfExpansionFlag.getSource()),
+              expansionFlag,
+              null);
+    } else if (expansionFlag.isExpansionOption()) {
+      options = optionsData.getEvaluatedExpansion(expansionFlag);
+      originOfSubflags =
+          new OptionInstanceOrigin(
+              originOfExpansionFlag.getPriority(),
+              String.format(
+                  "expanded by %s (source: %s)", expansionFlag, originOfExpansionFlag.getSource()),
+              null,
+              expansionFlag);
+    } else {
+      return ImmutableList.of();
+    }
 
-    ImmutableList<String> options = optionsData.getEvaluatedExpansion(expansionFlag, flagValue);
     Iterator<String> optionsIterator = options.iterator();
-    Function<OptionDefinition, String> sourceFunction =
-        o -> String.format("expanded from %s (source: %s)", expansionFlag.getOptionName(), source);
     while (optionsIterator.hasNext()) {
       String unparsedFlagExpression = optionsIterator.next();
       ParsedOptionDescription parsedOption =
           identifyOptionAndPossibleArgument(
               unparsedFlagExpression,
               optionsIterator,
-              priority,
-              sourceFunction,
-              null,
-              expansionFlag);
+              originOfSubflags.getPriority(),
+              o -> originOfSubflags.getSource(),
+              originOfSubflags.getImplicitDependent(),
+              originOfSubflags.getExpandedFrom());
       builder.add(parsedOption);
     }
     return builder.build();
@@ -301,13 +276,18 @@ class OptionsParserImpl {
 
   /**
    * Parses the args, and returns what it doesn't parse. May be called multiple times, and may be
-   * called recursively. In each call, there may be no duplicates, but separate calls may contain
-   * intersecting sets of options; in that case, the arg seen last takes precedence.
+   * called recursively. The option's definition dictates how it reacts to multiple settings. By
+   * default, the arg seen last at the highest priority takes precedence, overriding the early
+   * values. Options that accumulate multiple values will track them in priority and appearance
+   * order.
    */
   List<String> parse(
-      OptionPriority priority, Function<OptionDefinition, String> sourceFunction, List<String> args)
+      OptionPriority.PriorityCategory priority,
+      Function<OptionDefinition, String> sourceFunction,
+      List<String> args)
       throws OptionsParsingException {
-    return parse(priority, sourceFunction, null, null, args);
+    return parse(
+        OptionPriority.lowestOptionPriorityAtCategory(priority), sourceFunction, null, null, args);
   }
 
   /**
@@ -315,8 +295,8 @@ class OptionsParserImpl {
    * called recursively. Calls may contain intersecting sets of options; in that case, the arg seen
    * last takes precedence.
    *
-   * <p>The method uses the invariant that if an option has neither an implicit dependent nor an
-   * expanded from value, then it must have been explicitly set.
+   * <p>The method treats options that have neither an implicitDependent nor an expandedFrom value
+   * as explicitly set.
    */
   private List<String> parse(
       OptionPriority priority,
@@ -326,7 +306,6 @@ class OptionsParserImpl {
       List<String> args)
       throws OptionsParsingException {
     List<String> unparsedArgs = new ArrayList<>();
-    LinkedHashMap<OptionDefinition, List<String>> implicitRequirements = new LinkedHashMap<>();
 
     Iterator<String> argsIterator = argsPreProcessor.preProcess(args).iterator();
     while (argsIterator.hasNext()) {
@@ -345,134 +324,116 @@ class OptionsParserImpl {
       ParsedOptionDescription parsedOption =
           identifyOptionAndPossibleArgument(
               arg, argsIterator, priority, sourceFunction, implicitDependent, expandedFrom);
-      OptionDefinition optionDefinition = parsedOption.getOptionDefinition();
-      // All options can be deprecated; check and warn before doing any option-type specific work.
-      maybeAddDeprecationWarning(optionDefinition);
-
-      // Track the value, before any remaining option-type specific work that is done outside of
-      // the OptionValueDescription.
-      OptionValueDescription entry =
-          optionValues.computeIfAbsent(
-              optionDefinition, OptionValueDescription::createOptionValueDescription);
-      entry.addOptionInstance(parsedOption, warnings);
-
-      @Nullable String unconvertedValue = parsedOption.getUnconvertedValue();
-      if (optionDefinition.isWrapperOption()) {
-        if (unconvertedValue.startsWith("-")) {
-          String sourceMessage =
-              "Unwrapped from wrapper option --" + optionDefinition.getOptionName();
-          List<String> unparsed =
-              parse(
-                  priority,
-                  o -> sourceMessage,
-                  null, // implicitDependent
-                  null, // expandedFrom
-                  ImmutableList.of(unconvertedValue));
-
-          if (!unparsed.isEmpty()) {
-            throw new OptionsParsingException(
-                "Unparsed options remain after unwrapping "
-                    + arg
-                    + ": "
-                    + Joiner.on(' ').join(unparsed));
-          }
+      handleNewParsedOption(parsedOption);
+    }
 
-          // Don't process implicitRequirements or expansions for wrapper options. In particular,
-          // don't record this option in parsedOptions, so that only the wrapped option shows
-          // up in canonicalized options.
-          continue;
+    // Go through the final values and make sure they are valid values for their option. Unlike any
+    // checks that happened above, this also checks that flags that were not set have a valid
+    // default value. getValue() will throw if the value is invalid.
+    for (OptionValueDescription valueDescription : asListOfEffectiveOptions()) {
+      valueDescription.getValue();
+    }
 
-        } else {
-          throw new OptionsParsingException(
-              "Invalid --"
-                  + optionDefinition.getOptionName()
-                  + " value format. "
-                  + "You may have meant --"
-                  + optionDefinition.getOptionName()
-                  + "=--"
-                  + unconvertedValue);
-        }
-      }
+    return unparsedArgs;
+  }
 
-      if (implicitDependent == null) {
-        // Log explicit options and expanded options in the order they are parsed (can be sorted
-        // later). Also remember whether they were expanded or not. 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));
-        }
+  /**
+   * Implementation of {@link OptionsParser#addOptionValueAtSpecificPriority(OptionInstanceOrigin,
+   * OptionDefinition, String)}
+   */
+  void addOptionValueAtSpecificPriority(
+      OptionInstanceOrigin origin, OptionDefinition option, String unconvertedValue)
+      throws OptionsParsingException {
+    Preconditions.checkNotNull(option);
+    Preconditions.checkNotNull(
+        unconvertedValue,
+        "Cannot set %s to a null value. Pass \"\" if an empty value is required.",
+        option);
+    Preconditions.checkNotNull(
+        origin,
+        "Cannot assign value \'%s\' to %s without a clear origin for this value.",
+        unconvertedValue,
+        option);
+    PriorityCategory priorityCategory = origin.getPriority().getPriorityCategory();
+    boolean isNotDefault = priorityCategory != OptionPriority.PriorityCategory.DEFAULT;
+    Preconditions.checkArgument(
+        isNotDefault,
+        "Attempt to assign value \'%s\' to %s at priority %s failed. Cannot set options at "
+            + "default priority - by definition, that means the option is unset.",
+        unconvertedValue,
+        option,
+        priorityCategory);
+
+    handleNewParsedOption(
+        new ParsedOptionDescription(
+            option,
+            String.format("--%s=%s", option.getOptionName(), unconvertedValue),
+            unconvertedValue,
+            origin));
+  }
+
+  /** Takes care of tracking the parsed option's value in relation to other options. */
+  private void handleNewParsedOption(ParsedOptionDescription parsedOption)
+      throws OptionsParsingException {
+    OptionDefinition optionDefinition = parsedOption.getOptionDefinition();
+    // All options can be deprecated; check and warn before doing any option-type specific work.
+    maybeAddDeprecationWarning(optionDefinition);
+    // Track the value, before any remaining option-type specific work that is done outside of
+    // the OptionValueDescription.
+    OptionValueDescription entry =
+        optionValues.computeIfAbsent(
+            optionDefinition,
+            def -> OptionValueDescription.createOptionValueDescription(def, optionsData));
+    ExpansionBundle expansionBundle = entry.addOptionInstance(parsedOption, warnings);
+    @Nullable String unconvertedValue = parsedOption.getUnconvertedValue();
+
+    // There are 3 types of flags that expand to other flag values. Expansion flags are the
+    // accepted way to do this, but two legacy features remain: implicit requirements and wrapper
+    // options. We rely on the OptionProcessor compile-time check's guarantee that no option sets
+    // multiple of these behaviors. (In Bazel, --config is another such flag, but that expansion
+    // is not controlled within the options parser, so we ignore it here)
+
+    // As much as possible, we want the behaviors of these different types of flags to be
+    // identical, as this minimizes the number of edge cases, but we do not yet track these values
+    // in the same way. Wrapper options are replaced by their value and implicit requirements are
+    // hidden from the reported lists of parsed options.
+    if (parsedOption.getImplicitDependent() == null && !optionDefinition.isWrapperOption()) {
+      // 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));
       }
+    }
 
-      // Handle expansion options.
-      if (optionDefinition.isExpansionOption()) {
-        ImmutableList<String> expansion =
-            optionsData.getEvaluatedExpansion(optionDefinition, unconvertedValue);
-
-        String sourceFunctionApplication = sourceFunction.apply(optionDefinition);
-        String sourceMessage =
-            (sourceFunctionApplication == null)
-                ? String.format("expanded from option --%s", optionDefinition.getOptionName())
-                : String.format(
-                    "expanded from option --%s from %s",
-                    optionDefinition.getOptionName(), sourceFunctionApplication);
-        Function<OptionDefinition, String> expansionSourceFunction = o -> sourceMessage;
-        List<String> unparsed =
-            parse(priority, expansionSourceFunction, null, optionDefinition, expansion);
-        if (!unparsed.isEmpty()) {
-          // Throw an assertion, because this indicates an error in the definition of this
-          // option's expansion, not with the input as provided by the user.
+    if (expansionBundle != null) {
+      List<String> unparsed =
+          parse(
+              parsedOption.getPriority(),
+              o -> expansionBundle.sourceOfExpansionArgs,
+              optionDefinition.hasImplicitRequirements() ? optionDefinition : null,
+              optionDefinition.isExpansionOption() ? optionDefinition : null,
+              expansionBundle.expansionArgs);
+      if (!unparsed.isEmpty()) {
+        if (optionDefinition.isWrapperOption()) {
+          throw new OptionsParsingException(
+              "Unparsed options remain after unwrapping "
+                  + unconvertedValue
+                  + ": "
+                  + Joiner.on(' ').join(unparsed));
+        } else {
+          // Throw an assertion here, because this indicates an error in the definition of this
+          // option's expansion or requirements, not with the input as provided by the user.
           throw new AssertionError(
-              "Unparsed options remain after parsing expansion of "
-                  + arg
+              "Unparsed options remain after processing "
+                  + unconvertedValue
                   + ": "
                   + Joiner.on(' ').join(unparsed));
         }
       }
-
-      // Collect any implicit requirements.
-      if (optionDefinition.hasImplicitRequirements()) {
-        implicitRequirements.put(
-            optionDefinition, Arrays.asList(optionDefinition.getImplicitRequirements()));
-      }
-    }
-
-    // Now parse any implicit requirements that were collected.
-    // TODO(bazel-team): this should happen when the option is encountered.
-    if (!implicitRequirements.isEmpty()) {
-      for (Map.Entry<OptionDefinition, List<String>> entry : implicitRequirements.entrySet()) {
-        OptionDefinition optionDefinition = entry.getKey();
-        String sourceFunctionApplication = sourceFunction.apply(optionDefinition);
-        String sourceMessage =
-            (sourceFunctionApplication == null)
-                ? String.format(
-                    "implicit requirement of option --%s", optionDefinition.getOptionName())
-                : String.format(
-                    "implicit requirement of option --%s from %s",
-                    optionDefinition.getOptionName(), sourceFunctionApplication);
-        Function<OptionDefinition, String> requirementSourceFunction = o -> sourceMessage;
-
-        List<String> unparsed = parse(priority, requirementSourceFunction, entry.getKey(), null,
-            entry.getValue());
-        if (!unparsed.isEmpty()) {
-          // Throw an assertion, because this indicates an error in the code that specified in the
-          // implicit requirements for the option(s).
-          throw new AssertionError("Unparsed options remain after parsing implicit options: "
-              + Joiner.on(' ').join(unparsed));
-        }
-      }
     }
-
-    // Go through the final values and make sure they are valid values for their option. Unlike any
-    // checks that happened above, this also checks that flags that were not set have a valid
-    // default value. getValue() will throw if the value is invalid.
-    for (OptionValueDescription valueDescription : asListOfEffectiveOptions()) {
-      valueDescription.getValue();
-    }
-
-    return unparsedArgs;
   }
 
   private ParsedOptionDescription identifyOptionAndPossibleArgument(
@@ -596,10 +557,7 @@ class OptionsParserImpl {
         optionDefinition.getField().set(optionsInstance, value);
       } catch (IllegalArgumentException e) {
         throw new IllegalStateException(
-            String.format(
-                "Unable to set option '%s' to value '%s'.",
-                optionDefinition.getOptionName(), value),
-            e);
+            String.format("Unable to set %s to value '%s'.", optionDefinition, value), e);
       } catch (IllegalAccessException e) {
         throw new IllegalStateException(
             "Could not set the field due to access issues. This is impossible, as the "
diff --git a/java/com/google/devtools/common/options/OptionsParsingException.java b/java/com/google/devtools/common/options/OptionsParsingException.java
index 73b48a0..6b82366 100644
--- a/java/com/google/devtools/common/options/OptionsParsingException.java
+++ b/java/com/google/devtools/common/options/OptionsParsingException.java
@@ -17,7 +17,7 @@ package com.google.devtools.common.options;
 /**
  * An exception that's thrown when the {@link OptionsParser} fails.
  *
- * @see OptionsParser#parse(OptionPriority,String,java.util.List)
+ * @see OptionsParser#parse(OptionPriority.PriorityCategory,String,java.util.List)
  */
 public class OptionsParsingException extends Exception {
   private final String invalidArgument;
diff --git a/java/com/google/devtools/common/options/OptionsProvider.java b/java/com/google/devtools/common/options/OptionsProvider.java
index 1c7737f..5fd8ac0 100644
--- a/java/com/google/devtools/common/options/OptionsProvider.java
+++ b/java/com/google/devtools/common/options/OptionsProvider.java
@@ -39,8 +39,10 @@ public interface OptionsProvider extends OptionsClassProvider {
    * specified. If an option was specified multiple times, it is included in the result multiple
    * times. Does not include the residue.
    *
-   * <p>The returned list can be filtered if undocumented, hidden or implicit options should not be
-   * displayed.
+   * <p>The returned list includes undocumented, hidden or implicit options, and should be filtered
+   * as needed. Since it includes all options parsed, it will also include both an expansion option
+   * and the options it expanded to, and so blindly using this list for a new invocation will cause
+   * double-application of these options.
    */
   List<ParsedOptionDescription> asCompleteListOfParsedOptions();
 
diff --git a/java/com/google/devtools/common/options/OptionsUsage.java b/java/com/google/devtools/common/options/OptionsUsage.java
index 68a460e..6dee0eb 100644
--- a/java/com/google/devtools/common/options/OptionsUsage.java
+++ b/java/com/google/devtools/common/options/OptionsUsage.java
@@ -21,7 +21,11 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.escape.Escaper;
 import java.text.BreakIterator;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.List;
+import java.util.Locale;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
 import javax.annotation.Nullable;
 
 /** A renderer for usage messages for any combination of options classes. */
@@ -42,7 +46,7 @@ class OptionsUsage {
         new ArrayList<>(OptionsData.getAllOptionDefinitionsForClass(optionsClass));
     optionDefinitions.sort(OptionDefinition.BY_OPTION_NAME);
     for (OptionDefinition optionDefinition : optionDefinitions) {
-      getUsage(optionDefinition, usage, OptionsParser.HelpVerbosity.LONG, data);
+      getUsage(optionDefinition, usage, OptionsParser.HelpVerbosity.LONG, data, false);
     }
   }
 
@@ -85,14 +89,18 @@ class OptionsUsage {
   private static @Nullable ImmutableList<String> getExpansionIfKnown(
       OptionDefinition optionDefinition, OptionsData optionsData) {
     Preconditions.checkNotNull(optionDefinition);
-    try {
-      return optionsData.getEvaluatedExpansion(optionDefinition, null);
-    } catch (ExpansionNeedsValueException e) {
-      return null;
-    } catch (OptionsParsingException e) {
-      throw new IllegalStateException("Error expanding void expansion function: ", e);
-    }
+    return optionsData.getEvaluatedExpansion(optionDefinition);
+  }
+
+  // Placeholder tag "UNKNOWN" is ignored.
+  private static boolean shouldEffectTagBeListed(OptionEffectTag effectTag) {
+    return !effectTag.equals(OptionEffectTag.UNKNOWN);
+  }
 
+  // Tags that only apply to undocumented options are excluded.
+  private static boolean shouldMetadataTagBeListed(OptionMetadataTag metadataTag) {
+    return !metadataTag.equals(OptionMetadataTag.HIDDEN)
+        && !metadataTag.equals(OptionMetadataTag.INTERNAL);
   }
 
   /** Appends the usage message for a single option-field message to 'usage'. */
@@ -100,14 +108,17 @@ class OptionsUsage {
       OptionDefinition optionDefinition,
       StringBuilder usage,
       OptionsParser.HelpVerbosity helpVerbosity,
-      OptionsData optionsData) {
+      OptionsData optionsData,
+      boolean includeTags) {
     String flagName = getFlagName(optionDefinition);
     String typeDescription = getTypeDescription(optionDefinition);
     usage.append("  --").append(flagName);
-    if (helpVerbosity == OptionsParser.HelpVerbosity.SHORT) { // just the name
+    if (helpVerbosity == OptionsParser.HelpVerbosity.SHORT) {
       usage.append('\n');
       return;
     }
+
+    // Add the option's type and default information. Stop there for "medium" verbosity.
     if (optionDefinition.getAbbreviation() != '\0') {
       usage.append(" [-").append(optionDefinition.getAbbreviation()).append(']');
     }
@@ -127,9 +138,12 @@ class OptionsUsage {
       usage.append(")");
     }
     usage.append("\n");
-    if (helpVerbosity == OptionsParser.HelpVerbosity.MEDIUM) { // just the name and type.
+    if (helpVerbosity == OptionsParser.HelpVerbosity.MEDIUM) {
       return;
     }
+
+    // For verbosity "long," add the full description and expansion, along with the tag
+    // information if requested.
     if (!optionDefinition.getHelpText().isEmpty()) {
       usage.append(paragraphFill(optionDefinition.getHelpText(), /*indent=*/ 4, /*width=*/ 80));
       usage.append('\n');
@@ -151,9 +165,28 @@ class OptionsUsage {
       for (String req : optionDefinition.getImplicitRequirements()) {
         requiredMsg.append(req).append(" ");
       }
-      usage.append(paragraphFill(requiredMsg.toString(), /*indent=*/ 6, /*width=*/ 80));
+      usage.append(paragraphFill(requiredMsg.toString(), 6, 80)); // (indent, width)
       usage.append('\n');
     }
+    if (!includeTags) {
+      return;
+    }
+
+    // If we are expected to include the tags, add them for high verbosity.
+    Stream<OptionEffectTag> effectTagStream =
+        Arrays.stream(optionDefinition.getOptionEffectTags())
+            .filter(OptionsUsage::shouldEffectTagBeListed);
+    Stream<OptionMetadataTag> metadataTagStream =
+        Arrays.stream(optionDefinition.getOptionMetadataTags())
+            .filter(OptionsUsage::shouldMetadataTagBeListed);
+    String tagList =
+        Stream.concat(effectTagStream, metadataTagStream)
+            .map(tag -> tag.toString().toLowerCase())
+            .collect(Collectors.joining(", "));
+    if (!tagList.isEmpty()) {
+      usage.append(paragraphFill("Tags: " + tagList, 6, 80)); // (indent, width)
+      usage.append("\n");
+    }
   }
 
   /** Append the usage message for a single option-field message to 'usage'. */
@@ -161,7 +194,8 @@ class OptionsUsage {
       OptionDefinition optionDefinition,
       StringBuilder usage,
       Escaper escaper,
-      OptionsData optionsData) {
+      OptionsData optionsData,
+      boolean includeTags) {
     String plainFlagName = optionDefinition.getOptionName();
     String flagName = getFlagName(optionDefinition);
     String valueDescription = optionDefinition.getValueTypeHelpText();
@@ -203,7 +237,7 @@ class OptionsUsage {
       usage.append('\n');
     }
 
-    if (!optionsData.getExpansionDataForField(optionDefinition).isEmpty()) {
+    if (!optionsData.getEvaluatedExpansion(optionDefinition).isEmpty()) {
       // If this is an expansion option, list the expansion if known, or at least specify that we
       // don't know.
       usage.append("<br/>\n");
@@ -215,7 +249,10 @@ class OptionsUsage {
         Preconditions.checkArgument(!expansion.isEmpty());
         expandsMsg = new StringBuilder("Expands to:<br/>\n");
         for (String exp : expansion) {
-          // TODO(ulfjack): Can we link to the expanded flags here?
+          // TODO(ulfjack): We should link to the expanded flags, but unfortunately we don't
+          // currently guarantee that all flags are only printed once. A flag in an OptionBase that
+          // is included by 2 different commands, but not inherited through a parent command, will
+          // be printed multiple times.
           expandsMsg
               .append("&nbsp;&nbsp;<code>")
               .append(escaper.escape(exp))
@@ -225,6 +262,32 @@ class OptionsUsage {
       usage.append(expandsMsg.toString());
     }
 
+    // Add effect tags, if not UNKNOWN, and metadata tags, if not empty.
+    if (includeTags) {
+      Stream<OptionEffectTag> effectTagStream =
+          Arrays.stream(optionDefinition.getOptionEffectTags())
+              .filter(OptionsUsage::shouldEffectTagBeListed);
+      Stream<OptionMetadataTag> metadataTagStream =
+          Arrays.stream(optionDefinition.getOptionMetadataTags())
+              .filter(OptionsUsage::shouldMetadataTagBeListed);
+      String tagList =
+          Stream.concat(
+                  effectTagStream.map(
+                      tag ->
+                          String.format(
+                              "<a href=\"#effect_tag_%s\"><code>%s</code></a>",
+                              tag, tag.name().toLowerCase())),
+                  metadataTagStream.map(
+                      tag ->
+                          String.format(
+                              "<a href=\"#metadata_tag_%s\"><code>%s</code></a>",
+                              tag, tag.name().toLowerCase())))
+              .collect(Collectors.joining(", "));
+      if (!tagList.isEmpty()) {
+        usage.append("<br>Tags: \n").append(tagList);
+      }
+    }
+
     usage.append("</dd>\n");
   }
 
@@ -263,8 +326,10 @@ class OptionsUsage {
       builder.append("={auto,yes,no}\n");
       builder.append("--no").append(flagName).append("\n");
     } else if (fieldType.isEnum()) {
-      builder.append("={")
-          .append(COMMA_JOINER.join(fieldType.getEnumConstants()).toLowerCase()).append("}\n");
+      builder
+          .append("={")
+          .append(COMMA_JOINER.join(fieldType.getEnumConstants()).toLowerCase(Locale.ENGLISH))
+          .append("}\n");
     } else if (fieldType.getSimpleName().equals("Label")) {
       // String comparison so we don't introduce a dependency to com.google.devtools.build.lib.
       builder.append("=label\n");
diff --git a/java/com/google/devtools/common/options/ParsedOptionDescription.java b/java/com/google/devtools/common/options/ParsedOptionDescription.java
index 0910579..f55f8ad 100644
--- a/java/com/google/devtools/common/options/ParsedOptionDescription.java
+++ b/java/com/google/devtools/common/options/ParsedOptionDescription.java
@@ -15,6 +15,7 @@
 package com.google.devtools.common.options;
 
 import com.google.common.collect.ImmutableList;
+import java.util.function.Function;
 import javax.annotation.Nullable;
 
 /**
@@ -49,6 +50,46 @@ public final class ParsedOptionDescription {
     return commandLineForm;
   }
 
+  public String getCanonicalForm() {
+    return getCanonicalFormWithValueEscaper(s -> s);
+  }
+
+  public String getCanonicalFormWithValueEscaper(Function<String, String> escapingFunction) {
+    // For boolean flags (note that here we do not check for TriState flags, only flags with actual
+    // boolean values, so that we know the return type of getConvertedValue), use the --[no]flag
+    // form for the canonical value.
+    if (optionDefinition.getType().equals(boolean.class)) {
+      try {
+        return ((boolean) getConvertedValue() ? "--" : "--no") + optionDefinition.getOptionName();
+      } catch (OptionsParsingException e) {
+        throw new RuntimeException("Unexpected parsing exception", e);
+      }
+    } else {
+      String optionString = "--" + optionDefinition.getOptionName();
+      if (unconvertedValue != null) { // Can be null for Void options.
+        optionString += "=" + escapingFunction.apply(unconvertedValue);
+      }
+      return optionString;
+    }
+  }
+
+  @Deprecated
+  // TODO(b/65646296) Once external dependencies are cleaned up, use getCanonicalForm()
+  String getDeprecatedCanonicalForm() {
+    String value = unconvertedValue;
+    // For boolean flags (note that here we do not check for TriState flags, only flags with actual
+    // boolean values, so that we know the return type of getConvertedValue), set them all to 1 or
+    // 0, instead of keeping the wide variety of values we accept in their original form.
+    if (optionDefinition.getType().equals(boolean.class)) {
+      try {
+        value = (boolean) getConvertedValue() ? "1" : "0";
+      } catch (OptionsParsingException e) {
+        throw new RuntimeException("Unexpected parsing exception", e);
+      }
+    }
+    return String.format("--%s=%s", optionDefinition.getOptionName(), value);
+  }
+
   public boolean isBooleanOption() {
     return optionDefinition.getType().equals(boolean.class);
   }
@@ -74,7 +115,11 @@ public final class ParsedOptionDescription {
     return unconvertedValue;
   }
 
-  OptionPriority getPriority() {
+  public OptionInstanceOrigin getOrigin() {
+    return origin;
+  }
+
+  public OptionPriority getPriority() {
     return origin.getPriority();
   }
 
@@ -108,7 +153,7 @@ public final class ParsedOptionDescription {
   @Override
   public String toString() {
     StringBuilder result = new StringBuilder();
-    result.append("option '").append(optionDefinition.getOptionName()).append("' ");
+    result.append(optionDefinition);
     result.append("set to '").append(unconvertedValue).append("' ");
     result.append("with priority ").append(origin.getPriority());
     if (origin.getSource() != null) {
diff --git a/test/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixerTest.java b/test/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixerTest.java
index cdc3263..c74febb 100644
--- a/test/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixerTest.java
+++ b/test/java/com/google/devtools/build/android/desugar/DefaultMethodClassFixerTest.java
@@ -98,7 +98,12 @@ public class DefaultMethodClassFixerTest {
   private byte[] desugar(ClassReader reader) {
     ClassWriter writer = new ClassWriter(ClassWriter.COMPUTE_MAXS);
     DefaultMethodClassFixer fixer =
-        new DefaultMethodClassFixer(writer, classpathReader, bootclassPath, classLoader);
+        new DefaultMethodClassFixer(
+            writer,
+            classpathReader,
+            DependencyCollector.NoWriteCollectors.FAIL_ON_MISSING,
+            bootclassPath,
+            classLoader);
     reader.accept(fixer, 0);
     return writer.toByteArray();
   }
diff --git a/test/java/com/google/devtools/build/android/desugar/DesugarJava8FunctionalTest.java b/test/java/com/google/devtools/build/android/desugar/DesugarJava8FunctionalTest.java
index 8321d75..20e6028 100644
--- a/test/java/com/google/devtools/build/android/desugar/DesugarJava8FunctionalTest.java
+++ b/test/java/com/google/devtools/build/android/desugar/DesugarJava8FunctionalTest.java
@@ -23,6 +23,9 @@ import com.google.devtools.build.android.desugar.testdata.java8.ConcreteDefaultI
 import com.google.devtools.build.android.desugar.testdata.java8.ConcreteOverridesDefaultWithLambda;
 import com.google.devtools.build.android.desugar.testdata.java8.DefaultInterfaceMethodWithStaticInitializer;
 import com.google.devtools.build.android.desugar.testdata.java8.DefaultInterfaceWithBridges;
+import com.google.devtools.build.android.desugar.testdata.java8.DefaultMethodFromSeparateJava8Target;
+import com.google.devtools.build.android.desugar.testdata.java8.DefaultMethodFromSeparateJava8TargetOverridden;
+import com.google.devtools.build.android.desugar.testdata.java8.DefaultMethodTransitivelyFromSeparateJava8Target;
 import com.google.devtools.build.android.desugar.testdata.java8.FunctionWithDefaultMethod;
 import com.google.devtools.build.android.desugar.testdata.java8.FunctionalInterfaceWithInitializerAndDefaultMethods;
 import com.google.devtools.build.android.desugar.testdata.java8.GenericDefaultInterfaceWithLambda;
@@ -111,6 +114,12 @@ public class DesugarJava8FunctionalTest extends DesugarFunctionalTest {
   }
 
   @Test
+  public void testBootclasspathMethodInvocations() {
+    InterfaceMethod concrete = new InterfaceMethod.Concrete();
+    assertThat(concrete.defaultInvokingBootclasspathMethods("Larry")).isEqualTo("Larry");
+  }
+
+  @Test
   public void testStaticMethodsInInterface_explicitAndLambdaBody() {
     List<Long> result = FunctionWithDefaultMethod.DoubleInts.add(ImmutableList.of(7, 39, 8), 3);
     assertThat(result).containsExactly(10L, 42L, 11L).inOrder();
@@ -394,4 +403,16 @@ public class DesugarJava8FunctionalTest extends DesugarFunctionalTest {
                   .getExpectedInitializationOrder());
     }
   }
+
+  /**
+   * Tests that default methods on the classpath are correctly handled. We'll also verify the
+   * metadata that's emitted for this case to make sure the binary-wide double-check for correct
+   * desugaring of default and static interface methods keeps working (b/65645388).
+   */
+  @Test
+  public void testDefaultMethodsInSeparateTarget() {
+    assertThat(new DefaultMethodFromSeparateJava8Target().dflt()).isEqualTo("dflt");
+    assertThat(new DefaultMethodTransitivelyFromSeparateJava8Target().dflt()).isEqualTo("dflt");
+    assertThat(new DefaultMethodFromSeparateJava8TargetOverridden().dflt()).isEqualTo("override");
+  }
 }
diff --git a/test/java/com/google/devtools/build/android/desugar/Java7CompatibilityTest.java b/test/java/com/google/devtools/build/android/desugar/Java7CompatibilityTest.java
index b8c8b54..2eab943 100644
--- a/test/java/com/google/devtools/build/android/desugar/Java7CompatibilityTest.java
+++ b/test/java/com/google/devtools/build/android/desugar/Java7CompatibilityTest.java
@@ -31,7 +31,7 @@ public class Java7CompatibilityTest {
   public void testJava7CompatibleInterface() throws Exception {
     ClassReader reader = new ClassReader(ExtendsDefault.class.getName());
     ClassTester tester = new ClassTester();
-    reader.accept(new Java7Compatibility(tester, null), 0);
+    reader.accept(new Java7Compatibility(tester, null, null), 0);
     assertThat(tester.version).isEqualTo(Opcodes.V1_7);
     assertThat(tester.bridgeMethods).isEqualTo(0); // make sure we strip bridge methods
     assertThat(tester.clinitMethods).isEqualTo(1); // make sure we don't strip <clinit>
@@ -41,7 +41,7 @@ public class Java7CompatibilityTest {
   public void testDefaultMethodFails() throws Exception {
     ClassReader reader = new ClassReader(WithDefault.class.getName());
     try {
-      reader.accept(new Java7Compatibility(null, null), 0);
+      reader.accept(new Java7Compatibility(null, null, null), 0);
       fail("IllegalArgumentException expected");
     } catch (IllegalArgumentException expected) {
       assertThat(expected).hasMessageThat().contains("getVersion()I");
@@ -56,7 +56,7 @@ public class Java7CompatibilityTest {
   public void testConcreteClassRedeclaresBridges() throws Exception {
     ClassReader reader = new ClassReader(Impl.class.getName());
     ClassTester tester = new ClassTester();
-    reader.accept(new Java7Compatibility(tester, null), 0);
+    reader.accept(new Java7Compatibility(tester, null, null), 0);
     assertThat(tester.version).isEqualTo(Opcodes.V1_7);
     assertThat(tester.bridgeMethods).isEqualTo(2);
   }
diff --git a/test/java/com/google/devtools/build/android/desugar/class_with_lambdas_in_implemented_interface_disassembled_golden.txt b/test/java/com/google/devtools/build/android/desugar/class_with_lambdas_in_implemented_interface_disassembled_golden.txt
index 48a8632..73a563a 100644
--- a/test/java/com/google/devtools/build/android/desugar/class_with_lambdas_in_implemented_interface_disassembled_golden.txt
+++ b/test/java/com/google/devtools/build/android/desugar/class_with_lambdas_in_implemented_interface_disassembled_golden.txt
@@ -2,6 +2,7 @@ Compiled from "InterfaceMethod.java"
 public class com.google.devtools.build.android.desugar.testdata.java8.InterfaceMethod$Concrete implements com.google.devtools.build.android.desugar.testdata.java8.InterfaceMethod {
   public com.google.devtools.build.android.desugar.testdata.java8.InterfaceMethod$Concrete();
   public java.util.List defaultMethodReference(java.util.List);
+  public java.lang.String defaultInvokingBootclasspathMethods(java.lang.String);
   public java.util.List staticMethodReference(java.util.List);
   public java.util.List lambdaCallsDefaultMethod(java.util.List);
   public boolean startsWithS(java.lang.String);
diff --git a/test/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollectorTest.java b/test/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollectorTest.java
new file mode 100644
index 0000000..e99abc4
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/dependencies/MetadataCollectorTest.java
@@ -0,0 +1,113 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar.dependencies;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.android.desugar.proto.DesugarDeps.Dependency;
+import com.google.devtools.build.android.desugar.proto.DesugarDeps.DesugarDepsInfo;
+import com.google.devtools.build.android.desugar.proto.DesugarDeps.InterfaceDetails;
+import com.google.devtools.build.android.desugar.proto.DesugarDeps.InterfaceWithCompanion;
+import com.google.devtools.build.android.desugar.proto.DesugarDeps.Type;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Unit tests for {@link MetadataCollector}. */
+@RunWith(JUnit4.class)
+public class MetadataCollectorTest {
+
+  @Test
+  public void testEmptyAvoidsOutput() {
+    assertThat(new MetadataCollector(false).toByteArray()).isNull();
+  }
+
+  @Test
+  public void testAssumeCompanionClass() throws Exception {
+    MetadataCollector collector = new MetadataCollector(false);
+    collector.assumeCompanionClass("a", "b$$CC");
+    collector.assumeCompanionClass("b", "b$$CC");
+    collector.assumeCompanionClass("a", "a$$CC");
+
+    DesugarDepsInfo info = extractProto(collector);
+    assertThat(info.getAssumePresentList())
+        .containsExactly(
+            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("b$$CC")).build(),
+            Dependency.newBuilder().setOrigin(wrapType("b")).setTarget(wrapType("b$$CC")).build(),
+            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("a$$CC")).build());
+  }
+
+  @Test
+  public void testMissingImplementedInterface() throws Exception {
+    MetadataCollector collector = new MetadataCollector(true);
+    collector.missingImplementedInterface("a", "b");
+    collector.missingImplementedInterface("a", "c");
+    collector.missingImplementedInterface("c", "b");
+
+    DesugarDepsInfo info = extractProto(collector);
+    assertThat(info.getMissingInterfaceList())
+        .containsExactly(
+            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("b")).build(),
+            Dependency.newBuilder().setOrigin(wrapType("a")).setTarget(wrapType("c")).build(),
+            Dependency.newBuilder().setOrigin(wrapType("c")).setTarget(wrapType("b")).build());
+  }
+
+  @Test
+  public void testRecordExtendedInterfaces() throws Exception {
+    MetadataCollector collector = new MetadataCollector(false);
+    collector.recordExtendedInterfaces("a", "b", "c");
+    collector.recordExtendedInterfaces("b");
+    collector.recordExtendedInterfaces("c", "d");
+
+    DesugarDepsInfo info = extractProto(collector);
+    assertThat(info.getInterfaceWithSupertypesList())
+        .containsExactly(
+            InterfaceDetails.newBuilder()
+                .setOrigin(wrapType("a"))
+                .addAllExtendedInterface(ImmutableList.of(wrapType("b"), wrapType("c")))
+                .build(),
+            InterfaceDetails.newBuilder()
+                .setOrigin(wrapType("c"))
+                .addAllExtendedInterface(ImmutableList.of(wrapType("d")))
+                .build());
+  }
+
+  @Test
+  public void testRecordDefaultMethods() throws Exception {
+    MetadataCollector collector = new MetadataCollector(false);
+    collector.recordDefaultMethods("a", 0);
+    collector.recordDefaultMethods("b", 1);
+
+    DesugarDepsInfo info = extractProto(collector);
+    assertThat(info.getInterfaceWithCompanionList())
+        .containsExactly(
+            InterfaceWithCompanion.newBuilder()
+                .setOrigin(wrapType("a"))
+                .setNumDefaultMethods(0)
+                .build(),
+            InterfaceWithCompanion.newBuilder()
+                .setOrigin(wrapType("b"))
+                .setNumDefaultMethods(1)
+                .build());
+  }
+
+  private static Type wrapType(String name) {
+    return Type.newBuilder().setBinaryName(name).build();
+  }
+
+  private DesugarDepsInfo extractProto(MetadataCollector collector) throws Exception {
+    return DesugarDepsInfo.parseFrom(collector.toByteArray());
+  }
+}
diff --git a/test/java/com/google/devtools/build/android/desugar/desugar_deps_consistency_test.sh b/test/java/com/google/devtools/build/android/desugar/desugar_deps_consistency_test.sh
new file mode 100755
index 0000000..e8e7e23
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/desugar_deps_consistency_test.sh
@@ -0,0 +1,38 @@
+#!/bin/bash
+#
+# Copyright 2016 The Bazel Authors. All rights reserved.
+#
+# 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.
+set -eu
+
+out="$(mktemp)"
+if ! "devtools/blaze/singlejar/singlejar" --output "${out}" --check_desugar_deps --sources "$@"; then
+  rm "${out}"
+  case "$0" in
+    *_fail_test) echo "Singlejar failed as expected!"; exit 0;;
+  esac
+  echo "Singlejar unexpectedly failed"
+  exit 1
+fi
+
+case "$0" in
+  *_fail_test) rm "${out}"; echo "Singlejar unexpectedly succeeded :("; exit 1;;
+esac
+
+if third_party/java/jdk/jar/jar tf "${out}" | grep 'desugar_deps'; then
+  rm "${out}"
+  echo "Singlejar output unexpectedly contains desugaring metadata"
+  exit 2
+fi  # else grep didn't find anything -> pass
+rm "${out}"
+exit 0
diff --git a/test/java/com/google/devtools/build/android/desugar/interface_with_desugared_method_bodies_disassembled_golden.txt b/test/java/com/google/devtools/build/android/desugar/interface_with_desugared_method_bodies_disassembled_golden.txt
index 828cee4..2d993a6 100644
--- a/test/java/com/google/devtools/build/android/desugar/interface_with_desugared_method_bodies_disassembled_golden.txt
+++ b/test/java/com/google/devtools/build/android/desugar/interface_with_desugared_method_bodies_disassembled_golden.txt
@@ -1,6 +1,7 @@
 Compiled from "InterfaceMethod.java"
 public interface com.google.devtools.build.android.desugar.testdata.java8.InterfaceMethod {
   public abstract java.util.List<java.lang.String> defaultMethodReference(java.util.List<java.lang.String>);
+  public abstract java.lang.String defaultInvokingBootclasspathMethods(java.lang.String);
   public abstract java.util.List<java.lang.String> staticMethodReference(java.util.List<java.lang.String>);
   public abstract java.util.List<java.lang.String> lambdaCallsDefaultMethod(java.util.List<java.lang.String>);
   public abstract boolean startsWithS(java.lang.String);
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/InterfaceWithLambda.java b/test/java/com/google/devtools/build/android/desugar/testdata/InterfaceWithLambda.java
index 47d8ab6..420ac15 100644
--- a/test/java/com/google/devtools/build/android/desugar/testdata/InterfaceWithLambda.java
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/InterfaceWithLambda.java
@@ -14,12 +14,14 @@
 package com.google.devtools.build.android.desugar.testdata;
 
 import com.google.common.collect.ImmutableList;
+import java.util.List;
+import java.util.stream.Collectors;
 
 public interface InterfaceWithLambda {
   String ZERO = String.valueOf(0);
-  ImmutableList<String> DIGITS =
+  List<String> DIGITS =
       ImmutableList.of(0, 1)
           .stream()
           .map(i -> i == 0 ? ZERO : String.valueOf(i))
-          .collect(ImmutableList.toImmutableList());
+          .collect(Collectors.toList());
 }
diff --git a/java/com/google/devtools/common/options/ExpansionNeedsValueException.java b/test/java/com/google/devtools/build/android/desugar/testdata/b68049457/StaticInterfaceMethod.java
index d63b988..7815a73 100644
--- a/java/com/google/devtools/common/options/ExpansionNeedsValueException.java
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/b68049457/StaticInterfaceMethod.java
@@ -11,15 +11,11 @@
 // 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.devtools.common.options;
+package com.google.devtools.build.android.desugar.testdata.b68049457;
 
-/**
- * Exception specific to evaluating {@link ExpansionFunction} objects. Used when expansion isn't
- * possible because of a missing input.
- */
-public final class ExpansionNeedsValueException extends OptionsParsingException {
-
-  public ExpansionNeedsValueException(String message) {
-    super(message);
+/** Interface declaring a static method for regression test for b/68049457. */
+public interface StaticInterfaceMethod {
+  static String never() {
+    throw new IllegalStateException("can't get here");
   }
 }
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/b68049457/StaticInterfaceMethodCaller.java b/test/java/com/google/devtools/build/android/desugar/testdata/b68049457/StaticInterfaceMethodCaller.java
new file mode 100644
index 0000000..f961d96
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/b68049457/StaticInterfaceMethodCaller.java
@@ -0,0 +1,21 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar.testdata.b68049457;
+
+/** Class calling static interface method for regression test for b/68049457. */
+public class StaticInterfaceMethodCaller {
+  public String callIt() {
+    return StaticInterfaceMethod.never();
+  }
+}
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteDefaultInterfaceWithLambda.java b/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteDefaultInterfaceWithLambda.java
index 0d9f70a..30a5200 100644
--- a/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteDefaultInterfaceWithLambda.java
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteDefaultInterfaceWithLambda.java
@@ -14,15 +14,17 @@
 package com.google.devtools.build.android.desugar.testdata.java8;
 
 import com.google.common.collect.ImmutableList;
+import java.util.List;
+import java.util.stream.Collectors;
 
 public class ConcreteDefaultInterfaceWithLambda implements DefaultInterfaceWithLambda {
   static final String ONE = String.valueOf(1);
 
   @Override
-  public ImmutableList<String> digits() {
+  public List<String> digits() {
     return ImmutableList.of(0, 2)
         .stream()
         .map(i -> i == 0 ? ONE : String.valueOf(i))
-        .collect(ImmutableList.toImmutableList());
+        .collect(Collectors.toList());
   }
 }
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteOverridesDefaultWithLambda.java b/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteOverridesDefaultWithLambda.java
index cdcc5e9..5998f41 100644
--- a/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteOverridesDefaultWithLambda.java
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/java8/ConcreteOverridesDefaultWithLambda.java
@@ -14,24 +14,26 @@
 package com.google.devtools.build.android.desugar.testdata.java8;
 
 import com.google.common.collect.ImmutableList;
+import java.util.List;
+import java.util.stream.Collectors;
 
 public class ConcreteOverridesDefaultWithLambda implements DefaultInterfaceWithLambda {
   static final String TWO = String.valueOf(2);
   static final String THREE = String.valueOf(3);
 
   @Override
-  public ImmutableList<String> defaultWithLambda() {
+  public List<String> defaultWithLambda() {
     return ImmutableList.of(0, 3)
         .stream()
         .map(i -> i == 0 ? TWO : String.valueOf(i))
-        .collect(ImmutableList.toImmutableList());
+        .collect(Collectors.toList());
   }
 
   @Override
-  public ImmutableList<String> digits() {
+  public List<String> digits() {
     return ImmutableList.of(0, 4)
         .stream()
         .map(i -> i == 0 ? THREE : String.valueOf(i))
-        .collect(ImmutableList.toImmutableList());
+        .collect(Collectors.toList());
   }
 }
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceWithLambda.java b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceWithLambda.java
index e97cae9..ce5fca7 100644
--- a/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceWithLambda.java
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceWithLambda.java
@@ -14,20 +14,22 @@
 package com.google.devtools.build.android.desugar.testdata.java8;
 
 import com.google.common.collect.ImmutableList;
+import java.util.List;
+import java.util.stream.Collectors;
 
 public interface DefaultInterfaceWithLambda {
   String ZERO = String.valueOf(0);
 
-  public default ImmutableList<String> defaultWithLambda() {
+  public default List<String> defaultWithLambda() {
     return ImmutableList.of(0, 1)
         .stream()
         .map(i -> i == 0 ? ZERO : String.valueOf(i))
-        .collect(ImmutableList.toImmutableList());
+        .collect(Collectors.toList());
   }
 
-  public default ImmutableList<String> defaultCallsInterfaceMethod() {
+  public default List<String> defaultCallsInterfaceMethod() {
     return digits();
   }
 
-  public ImmutableList<String> digits();
+  public List<String> digits();
 }
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8Target.java b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8Target.java
new file mode 100644
index 0000000..e0e8703
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8Target.java
@@ -0,0 +1,20 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar.testdata.java8;
+
+import com.google.devtools.build.android.desugar.testdata.separate8.SeparateInterfaceWithDefaultMethod;
+
+/** Test class that inherits default method defined in separate target for testing b/65645388. */
+public class DefaultMethodFromSeparateJava8Target
+    implements SeparateInterfaceWithDefaultMethod {}
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8TargetOverridden.java b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8TargetOverridden.java
new file mode 100644
index 0000000..1613f8e
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8TargetOverridden.java
@@ -0,0 +1,25 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar.testdata.java8;
+
+import com.google.devtools.build.android.desugar.testdata.separate8.SeparateInterfaceThatInheritsDefaultMethod;
+
+/** Test class that overrides default method defined in separate target for testing b/65645388. */
+public class DefaultMethodFromSeparateJava8TargetOverridden
+    implements SeparateInterfaceThatInheritsDefaultMethod {
+  @Override
+  public String dflt() {
+    return "override";
+  }
+}
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodTransitivelyFromSeparateJava8Target.java b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodTransitivelyFromSeparateJava8Target.java
new file mode 100644
index 0000000..693eaf7
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodTransitivelyFromSeparateJava8Target.java
@@ -0,0 +1,23 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar.testdata.java8;
+
+import com.google.devtools.build.android.desugar.testdata.separate8.SeparateInterfaceThatInheritsDefaultMethod;
+
+/**
+ * Test class that transitively inherits default method defined in separate target for testing
+ * b/65645388.
+ */
+public class DefaultMethodTransitivelyFromSeparateJava8Target
+    implements SeparateInterfaceThatInheritsDefaultMethod {}
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/java8/InterfaceMethod.java b/test/java/com/google/devtools/build/android/desugar/testdata/java8/InterfaceMethod.java
index 622e6e5..ae2b6e1 100644
--- a/test/java/com/google/devtools/build/android/desugar/testdata/java8/InterfaceMethod.java
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/java8/InterfaceMethod.java
@@ -15,6 +15,7 @@ package com.google.devtools.build.android.desugar.testdata.java8;
 
 import java.util.List;
 import java.util.stream.Collectors;
+import java.util.stream.Stream;
 
 /**
  * Desugar test input interface that declares lambdas and method references in default and static
@@ -25,6 +26,10 @@ public interface InterfaceMethod {
     return names.stream().filter(this::startsWithS).collect(Collectors.toList());
   }
 
+  public default String defaultInvokingBootclasspathMethods(String expectedValue) {
+    return Stream.of(expectedValue).findFirst().orElse("unexpected");
+  }
+
   public default List<String> staticMethodReference(List<String> names) {
     return names.stream().filter(InterfaceMethod::startsWithA).collect(Collectors.toList());
   }
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/separate8/SeparateInterfaceThatInheritsDefaultMethod.java b/test/java/com/google/devtools/build/android/desugar/testdata/separate8/SeparateInterfaceThatInheritsDefaultMethod.java
new file mode 100644
index 0000000..400a6f1
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/separate8/SeparateInterfaceThatInheritsDefaultMethod.java
@@ -0,0 +1,18 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar.testdata.separate8;
+
+/** Interface that inherits default method in separate compilation target for testing b/65645388. */
+public interface SeparateInterfaceThatInheritsDefaultMethod
+    extends SeparateInterfaceWithDefaultMethod {}
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata/separate8/SeparateInterfaceWithDefaultMethod.java b/test/java/com/google/devtools/build/android/desugar/testdata/separate8/SeparateInterfaceWithDefaultMethod.java
new file mode 100644
index 0000000..b3c04c8
--- /dev/null
+++ b/test/java/com/google/devtools/build/android/desugar/testdata/separate8/SeparateInterfaceWithDefaultMethod.java
@@ -0,0 +1,21 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.android.desugar.testdata.separate8;
+
+/** Interface with default method in separate compilation target for testing b/65645388. */
+public interface SeparateInterfaceWithDefaultMethod {
+  default String dflt() {
+    return "dflt";
+  }
+}
diff --git a/test/java/com/google/devtools/build/android/desugar/testdata_desugared_java8_jar_toc_golden.txt b/test/java/com/google/devtools/build/android/desugar/testdata_desugared_java8_jar_toc_golden.txt
index 8664932..907edd0 100644
--- a/test/java/com/google/devtools/build/android/desugar/testdata_desugared_java8_jar_toc_golden.txt
+++ b/test/java/com/google/devtools/build/android/desugar/testdata_desugared_java8_jar_toc_golden.txt
@@ -56,6 +56,9 @@ com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceMethodW
 com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceMethodWithStaticInitializer.class
 com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceWithBridges.class
 com/google/devtools/build/android/desugar/testdata/java8/DefaultInterfaceWithLambda.class
+com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8Target.class
+com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodFromSeparateJava8TargetOverridden.class
+com/google/devtools/build/android/desugar/testdata/java8/DefaultMethodTransitivelyFromSeparateJava8Target.class
 com/google/devtools/build/android/desugar/testdata/java8/FunctionWithDefaultMethod$DoubleInts.class
 com/google/devtools/build/android/desugar/testdata/java8/FunctionWithDefaultMethod$DoubleInts2.class
 com/google/devtools/build/android/desugar/testdata/java8/FunctionWithDefaultMethod.class