diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeCommandDispatcher.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeCommandDispatcher.java
index 15f6905..3afc697 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeCommandDispatcher.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeCommandDispatcher.java
@@ -687,12 +687,7 @@
     OptionsParser parser =
         OptionsParser.builder()
             .optionsData(optionsData)
-            // for starlark options
-            .skippedPrefix("--//")
-            .skippedPrefix("--no//")
-            // for starlark options in other repos
-            .skippedPrefix("--@")
-            .skippedPrefix("--no@")
+            .skipStarlarkOptionPrefixes()
             .allowResidue(annotation.allowResidue())
             .build();
     return parser;
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/StarlarkOptionsParser.java b/src/main/java/com/google/devtools/build/lib/runtime/StarlarkOptionsParser.java
index cbf611a..cbaff9f 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/StarlarkOptionsParser.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/StarlarkOptionsParser.java
@@ -66,7 +66,7 @@
     this.nativeOptionsParser = nativeOptionsParser;
   }
 
-  static StarlarkOptionsParser newStarlarkOptionsParser(
+  public static StarlarkOptionsParser newStarlarkOptionsParser(
       CommandEnvironment env, OptionsParser optionsParser) {
     return new StarlarkOptionsParser(
         env.getSkyframeExecutor(),
@@ -75,6 +75,7 @@
         optionsParser);
   }
 
+  /** Parses all pre "--" residue for Starlark options. */
   // TODO(juliexxia): This method somewhat reinvents the wheel of
   // OptionsParserImpl.identifyOptionAndPossibleArgument. Consider combining. This would probably
   // require multiple rounds of parsing to fit starlark-defined options into native option format.
@@ -98,8 +99,10 @@
 
       parseArg(arg, unparsedArgs, unparsedOptions, eventHandler);
     }
-    residue.addAll(nativeOptionsParser.getPostDoubleDashResidue());
-    nativeOptionsParser.setResidue(residue.build());
+
+    List<String> postDoubleDashResidue = nativeOptionsParser.getPostDoubleDashResidue();
+    residue.addAll(postDoubleDashResidue);
+    nativeOptionsParser.setResidue(residue.build(), postDoubleDashResidue);
 
     if (unparsedOptions.isEmpty()) {
       return;
@@ -187,9 +190,7 @@
   }
 
   private Target loadBuildSetting(
-      String targetToBuild,
-      OptionsParser optionsParser,
-      ExtendedEventHandler eventHandler)
+      String targetToBuild, OptionsParser optionsParser, ExtendedEventHandler eventHandler)
       throws OptionsParsingException {
     Target buildSetting;
     try {
@@ -227,7 +228,7 @@
 
   @VisibleForTesting
   public void setResidueForTesting(List<String> residue) {
-    nativeOptionsParser.setResidue(residue);
+    nativeOptionsParser.setResidue(residue, ImmutableList.of());
   }
 
   @VisibleForTesting
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/commands/CanonicalizeCommand.java b/src/main/java/com/google/devtools/build/lib/runtime/commands/CanonicalizeCommand.java
index 0e47837..e035988 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/commands/CanonicalizeCommand.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/commands/CanonicalizeCommand.java
@@ -16,13 +16,16 @@
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.pkgcache.PackageCacheOptions;
 import com.google.devtools.build.lib.runtime.BlazeCommand;
 import com.google.devtools.build.lib.runtime.BlazeCommandResult;
 import com.google.devtools.build.lib.runtime.BlazeCommandUtils;
 import com.google.devtools.build.lib.runtime.BlazeRuntime;
 import com.google.devtools.build.lib.runtime.Command;
 import com.google.devtools.build.lib.runtime.CommandEnvironment;
+import com.google.devtools.build.lib.runtime.StarlarkOptionsParser;
 import com.google.devtools.build.lib.runtime.proto.InvocationPolicyOuterClass.InvocationPolicy;
+import com.google.devtools.build.lib.util.AbruptExitException;
 import com.google.devtools.build.lib.util.ExitCode;
 import com.google.devtools.common.options.InvocationPolicyEnforcer;
 import com.google.devtools.common.options.InvocationPolicyParser;
@@ -35,20 +38,20 @@
 import com.google.devtools.common.options.OptionsParsingResult;
 import java.util.Collection;
 import java.util.List;
+import java.util.Map;
 import java.util.logging.Level;
 
 /** The 'blaze canonicalize-flags' command. */
 @Command(
-  name = "canonicalize-flags",
-  options = {CanonicalizeCommand.Options.class},
-  allowResidue = true,
-  mustRunInWorkspace = false,
-  shortDescription = "Canonicalizes a list of %{product} options.",
-  help =
-      "This command canonicalizes a list of %{product} options. Don't forget to prepend "
-          + " '--' to end option parsing before the flags to canonicalize.\n"
-          + "%{options}"
-)
+    name = "canonicalize-flags",
+    options = {CanonicalizeCommand.Options.class, PackageCacheOptions.class},
+    allowResidue = true,
+    mustRunInWorkspace = false,
+    shortDescription = "Canonicalizes a list of %{product} options.",
+    help =
+        "This command canonicalizes a list of %{product} options. Don't forget to prepend "
+            + " '--' to end option parsing before the flags to canonicalize.\n"
+            + "%{options}")
 public final class CanonicalizeCommand implements BlazeCommand {
 
   public static class Options extends OptionsBase {
@@ -143,10 +146,31 @@
                 command.getClass(), runtime.getBlazeModules(), runtime.getRuleClassProvider()))
             .add(FlagClashCanaryOptions.class)
             .build();
+
+    // set up the package cache for starlark options parsing
+    try {
+      env.setupPackageCache(options);
+    } catch (InterruptedException e) {
+      env.getReporter().handle(Event.error("canonicalization interrupted"));
+      return BlazeCommandResult.exitCode(ExitCode.INTERRUPTED);
+    } catch (AbruptExitException e) {
+      env.getReporter().handle(Event.error(null, "Unknown error: " + e.getMessage()));
+      return BlazeCommandResult.exitCode(e.getExitCode());
+    }
+
     try {
       OptionsParser parser =
-          OptionsParser.builder().optionsClasses(optionsClasses).allowResidue(false).build();
+          OptionsParser.builder()
+              .optionsClasses(optionsClasses)
+              .skipStarlarkOptionPrefixes()
+              .allowResidue(true)
+              .build();
       parser.parse(options.getResidue());
+      StarlarkOptionsParser.newStarlarkOptionsParser(env, parser).parse(env.getReporter());
+      if (!parser.getResidue().isEmpty()) {
+        String errorMsg = "Unrecognized arguments: " + Joiner.on(' ').join(parser.getResidue());
+        throw new OptionsParsingException(errorMsg);
+      }
 
       InvocationPolicy policy =
           InvocationPolicyParser.parsePolicy(canonicalizeOptions.invocationPolicy);
@@ -166,11 +190,14 @@
             InvocationPolicyEnforcer.getEffectiveInvocationPolicy(
                 policy, parser, commandName, Level.INFO);
         env.getReporter().getOutErr().printOutLn(effectivePolicy.toString());
-
       } else {
         // Otherwise, print out the canonical command line
-        List<String> result = parser.canonicalize();
-        for (String piece : result) {
+        List<String> nativeResult = parser.canonicalize();
+        ImmutableList.Builder<String> result = ImmutableList.<String>builder().addAll(nativeResult);
+        for (Map.Entry<String, Object> starlarkOption : parser.getStarlarkOptions().entrySet()) {
+          result.add("--" + starlarkOption.getKey() + "=" + starlarkOption.getValue());
+        }
+        for (String piece : result.build()) {
           env.getReporter().getOutErr().printOutLn(piece);
         }
       }
diff --git a/src/main/java/com/google/devtools/common/options/OptionsParser.java b/src/main/java/com/google/devtools/common/options/OptionsParser.java
index 98fb74e..f47045b 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsParser.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsParser.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.MoreCollectors;
 import com.google.common.escape.Escaper;
@@ -188,6 +189,16 @@
       return this;
     }
 
+    /** Skip all the prefixes associated with Starlark options */
+    public Builder skipStarlarkOptionPrefixes() {
+      this.implBuilder
+          .skippedPrefix("--//")
+          .skippedPrefix("--no//")
+          .skippedPrefix("--@")
+          .skippedPrefix("--no@");
+      return this;
+    }
+
     /**
      * Indicates whether or not the parser will allow a non-empty residue; that is, iff this value
      * is true then a call to one of the {@code parse} methods will throw {@link
@@ -219,7 +230,7 @@
   private final List<String> residue = new ArrayList<>();
   private final List<String> postDoubleDashResidue = new ArrayList<>();
   private final boolean allowResidue;
-  private final Map<String, Object> starlarkOptions = new HashMap<>();
+  private ImmutableSortedMap<String, Object> starlarkOptions = ImmutableSortedMap.of();
 
   private OptionsParser(OptionsParserImpl impl, boolean allowResidue) {
     this.impl = impl;
@@ -227,13 +238,12 @@
   }
 
   @Override
-  public Map<String, Object> getStarlarkOptions() {
-    return ImmutableMap.copyOf(starlarkOptions);
+  public ImmutableSortedMap<String, Object> getStarlarkOptions() {
+    return starlarkOptions;
   }
 
   public void setStarlarkOptions(Map<String, Object> starlarkOptions) {
-    this.starlarkOptions.clear();
-    this.starlarkOptions.putAll(starlarkOptions);
+    this.starlarkOptions = ImmutableSortedMap.copyOf(starlarkOptions);
   }
 
   public void parseAndExitUponError(String[] args) {
@@ -724,9 +734,15 @@
     return ImmutableList.copyOf(postDoubleDashResidue);
   }
 
-  public void setResidue(List<String> residue) {
+  /* Sets the residue (all elements parsed as non-options) to {@code residue}, as well as the part
+   * of the residue that follows the double-dash on the command line, {@code postDoubleDashResidue}.
+   * {@code postDoubleDashResidue} must be a subset of {@code residue}. */
+  public void setResidue(List<String> residue, List<String> postDoubleDashResidue) {
+    Preconditions.checkArgument(residue.containsAll(postDoubleDashResidue));
     this.residue.clear();
     this.residue.addAll(residue);
+    this.postDoubleDashResidue.clear();
+    this.postDoubleDashResidue.addAll(postDoubleDashResidue);
   }
 
   /** Returns a list of warnings about problems encountered by previous parse calls. */
diff --git a/src/main/java/com/google/devtools/common/options/OptionsParsingResult.java b/src/main/java/com/google/devtools/common/options/OptionsParsingResult.java
index bdedc7f..b595a4b 100644
--- a/src/main/java/com/google/devtools/common/options/OptionsParsingResult.java
+++ b/src/main/java/com/google/devtools/common/options/OptionsParsingResult.java
@@ -58,6 +58,7 @@
    * and the options it expanded to, and so blindly using this list for a new invocation will cause
    * double-application of these options.
    */
+  // TODO(b/150222792): make this aware of starlark options.
   List<ParsedOptionDescription> asCompleteListOfParsedOptions();
 
   /**
@@ -68,6 +69,8 @@
    *
    * <p>The list includes undocumented options.
    */
+  // TODO(b/150222792): make this aware of Starlark options. This might be tricky because we don't
+  // store Starlark option values that are explicitly specified to the same value as the default.
   List<ParsedOptionDescription> asListOfExplicitOptions();
 
   /**
@@ -78,12 +81,14 @@
    *
    * <p>The list includes undocumented options.
    */
+  // TODO(b/150222792): make this aware of Starlark options.
   List<ParsedOptionDescription> asListOfCanonicalOptions();
 
   /**
    * Returns a list of all options, including undocumented ones, and their effective values. There
    * is no guaranteed ordering for the result.
    */
+  // TODO(b/150222792): make this aware of Starlark options
   List<OptionValueDescription> asListOfOptionValues();
 
   /**
@@ -95,5 +100,7 @@
    * is unique, since some flags may have effects unknown to the parser (--config, for Bazel), so we
    * do not reorder flags to further simplify the list.
    */
+  // TODO(b/150222792): make this aware of Starlark options. Note - `blaze canonicalize-flags`
+  // already emits Starlark options by doing some extra work on top of calling this method.
   List<String> canonicalize();
 }
diff --git a/src/test/java/com/google/devtools/build/lib/runtime/commands/TargetPatternsHelperTest.java b/src/test/java/com/google/devtools/build/lib/runtime/commands/TargetPatternsHelperTest.java
index 6a780cb..df7a071 100644
--- a/src/test/java/com/google/devtools/build/lib/runtime/commands/TargetPatternsHelperTest.java
+++ b/src/test/java/com/google/devtools/build/lib/runtime/commands/TargetPatternsHelperTest.java
@@ -82,7 +82,7 @@
   @Test
   public void testNoTargetPatternFile() throws TargetPatternsHelperException {
     ImmutableList<String> patterns = ImmutableList.of("//some/...", "//patterns");
-    options.setResidue(patterns);
+    options.setResidue(patterns, ImmutableList.of());
 
     assertThat(TargetPatternsHelper.readFrom(env, options)).isEqualTo(patterns);
   }
@@ -90,7 +90,7 @@
   @Test
   public void testSpecifyPatternAndFileThrows() throws OptionsParsingException {
     options.parse("--target_pattern_file=patterns.txt");
-    options.setResidue(ImmutableList.of("//some:pattern"));
+    options.setResidue(ImmutableList.of("//some:pattern"), ImmutableList.of());
 
     TargetPatternsHelperException expected =
         assertThrows(