diff --git a/src/main/java/com/google/devtools/build/lib/packages/CallStack.java b/src/main/java/com/google/devtools/build/lib/packages/CallStack.java
new file mode 100644
index 0000000..fd097cd
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/packages/CallStack.java
@@ -0,0 +1,176 @@
+// Copyright 2020 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.lib.packages;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.syntax.StarlarkThread;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.Nullable;
+
+/**
+ * A CallStack is an opaque immutable stack of Starlark call frames, outermost call first. Its
+ * representation is highly optimized for space. Call {@link #toArray} to access the frames.
+ *
+ * <p>A CallStack cannot be constructed directly, but must be created by calling the {@code of}
+ * method of a Builder, which should be shared across all the rules of a package.
+ */
+public final class CallStack {
+
+  // A naive implementation using a simple array of CallStackEntry was
+  // found to increase retained heap size for a large query by about 6%.
+  // We reduce this using two optimizations:
+  //
+  // 1) entry compression
+  // A CallStackEntry has size 2 (header) + 1 String + 1 Location = 4 words.
+  // A Location has size 2 (header) + 1 String + 1 (file/loc) = 4 words.
+  // By representing the two strings as small integers---indices into a shared
+  // table---we can represent the payload using 4 ints = 2 words.
+  // We reconstitute new Locations and CallStackEntries on request.
+  // Eliminating Java object overheads reduces the marginal
+  // space for an element by about a half.
+  //
+  // 2) prefix sharing
+  // We share common stack prefixes between successive entries.
+  // The stacks passed to successive of() calls display locality because
+  // within a package, many rules are created by a single macro or stack
+  // of macros. The Builder records the previous stack and creates a tree node
+  // for each prefix. When it sees a new stack, it finds the common prefix
+  // for the current and previous stacks, and only creates new nodes for
+  // the suffix of different entries.
+  // Avoiding storage of redundant prefixes reduces overall space by about
+  // two thirds.
+  //
+  // This class intentionally does not implement List
+  // because internally it is a linked list,
+  // so accidentally using List.get for sequential access
+  // would result in quadratic behavior.
+
+  public static final CallStack EMPTY = new CallStack(ImmutableList.of(), 0, null);
+
+  private final List<String> strings; // builder's string table, shared
+  private final int size; // depth of stack
+  @Nullable private final Node node; // tree node representing this stack
+
+  private CallStack(List<String> strings, int size, @Nullable Node node) {
+    this.strings = strings;
+    this.size = size;
+    this.node = node;
+  }
+
+  /** Returns the call stack as a list of frames, outermost call first. */
+  public ImmutableList<StarlarkThread.CallStackEntry> toList() {
+    return ImmutableList.copyOf(toArray());
+  }
+
+  /** Returns the call stack as a new array, outermost call first. */
+  public StarlarkThread.CallStackEntry[] toArray() {
+    StarlarkThread.CallStackEntry[] array = new StarlarkThread.CallStackEntry[size];
+    int i = size;
+    for (Node n = node; n != null; n = n.parent) {
+      String file = strings.get(n.file);
+      String name = strings.get(n.name);
+      Location loc = Location.fromFileLineColumn(file, n.line, n.col);
+      array[--i] = new StarlarkThread.CallStackEntry(name, loc);
+    }
+    return array;
+  }
+
+  // A Node is a node in a linked tree representing a prefix of the call stack.
+  // file and line are indices of strings in the builder's shared table.
+  private static class Node {
+    Node(int name, int file, int line, int col, Node parent) {
+      this.name = name;
+      this.file = file;
+      this.line = line;
+      this.col = col;
+      this.parent = parent;
+    }
+
+    final int name;
+    final int file;
+    final int line;
+    final int col;
+    @Nullable final Node parent;
+  }
+
+  /** A Builder is a stateful indexer of call stacks. */
+  static final class Builder {
+
+    // string table: strings[index[s]] == s
+    private final Map<String, Integer> index = new HashMap<>();
+    private final List<String> strings = new ArrayList<>();
+
+    // nodes[0:depth] is the previously encountered call stack.
+    // We avoid ArrayList because we need efficient truncation.
+    private Node[] nodes = new Node[10];
+    private int depth = 0;
+
+    /**
+     * Returns a compact representation of the specified call stack. <br>
+     * Space efficiency depends on the similarity of the list elements in successive calls.
+     * Reversing the stack before calling this function destroys the optimization, for instance.
+     */
+    CallStack of(List<StarlarkThread.CallStackEntry> stack) {
+      // We find and reuse the common ancestor node for the prefix common
+      // to the current stack and the stack passed to the previous call,
+      // then add child nodes for the different suffix, if any.
+
+      // Loop invariant: parent == (i > 0 ? nodes[i-1] : null)
+      Node parent = null;
+      int n = stack.size();
+      for (int i = 0; i < n; i++) {
+        StarlarkThread.CallStackEntry entry = stack.get(i);
+
+        int name = indexOf(entry.name);
+        int file = indexOf(entry.location.file());
+        int line = entry.location.line();
+        int column = entry.location.column();
+        if (i < depth
+            && name == nodes[i].name
+            && file == nodes[i].file
+            && line == nodes[i].line
+            && column == nodes[i].col) {
+          parent = nodes[i];
+          continue;
+        }
+        parent = new Node(name, file, line, column, parent);
+        if (i == nodes.length) {
+          nodes = Arrays.copyOf(nodes, nodes.length << 1); // grow by doubling
+        }
+        nodes[i] = parent;
+      }
+      this.depth = n; // truncate
+
+      // Use the same node for all empty stacks, to avoid allocations.
+      return parent != null ? new CallStack(strings, n, parent) : EMPTY;
+    }
+
+    private int indexOf(String s) {
+      int i = index.size();
+      Integer prev = index.putIfAbsent(s, i);
+      if (prev != null) {
+        i = prev;
+      } else {
+        strings.add(s);
+      }
+      return i;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index 5ae743e..9736d0f 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -45,6 +45,7 @@
 import com.google.devtools.build.lib.skyframe.serialization.SerializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics;
+import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.util.SpellChecker;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -759,12 +760,9 @@
       RootedPath workspacePath,
       String runfilesPrefix,
       StarlarkSemantics starlarkSemantics) {
-    Builder b =
-        new Builder(
-            helper.createFreshPackage(LabelConstants.EXTERNAL_PACKAGE_IDENTIFIER, runfilesPrefix),
-            starlarkSemantics);
-    b.setFilename(workspacePath);
-    return b;
+    return new Builder(
+            helper, LabelConstants.EXTERNAL_PACKAGE_IDENTIFIER, runfilesPrefix, starlarkSemantics)
+        .setFilename(workspacePath);
   }
 
   /**
@@ -821,6 +819,7 @@
     private final Package pkg;
 
     private final StarlarkSemantics starlarkSemantics;
+    private final CallStack.Builder callStackBuilder = new CallStack.Builder();
 
     // The map from each repository to that repository's remappings map.
     // This is only used in the //external package, it is an empty map for all other packages.
@@ -909,6 +908,7 @@
       }
     };
 
+    // low-level constructor
     Builder(Package pkg, StarlarkSemantics starlarkSemantics) {
       this.starlarkSemantics = starlarkSemantics;
       this.pkg = pkg;
@@ -917,6 +917,7 @@
       }
     }
 
+    // high-level constructor
     Builder(
         Helper helper,
         PackageIdentifier id,
@@ -1245,24 +1246,22 @@
         Label label,
         RuleClass ruleClass,
         Location location,
+        List<StarlarkThread.CallStackEntry> callstack,
         AttributeContainer attributeContainer) {
       return new Rule(
-          pkg,
-          label,
-          ruleClass,
-          location,
-          attributeContainer);
+          pkg, label, ruleClass, location, callStackBuilder.of(callstack), attributeContainer);
     }
 
     /**
-     * Same as {@link #createRule(Label, RuleClass, Location, AttributeContainer)}, except
-     * allows specifying an {@link ImplicitOutputsFunction} override. Only use if you know what
-     * you're doing.
+     * Same as {@link #createRule(Label, RuleClass, Location, List<StarlarkThread.CallStackEntry>,
+     * AttributeContainer)}, except allows specifying an {@link ImplicitOutputsFunction} override.
+     * Only use if you know what you're doing.
      */
     Rule createRule(
         Label label,
         RuleClass ruleClass,
         Location location,
+        List<StarlarkThread.CallStackEntry> callstack,
         AttributeContainer attributeContainer,
         ImplicitOutputsFunction implicitOutputsFunction) {
       return new Rule(
@@ -1270,6 +1269,7 @@
           label,
           ruleClass,
           location,
+          callStackBuilder.of(callstack),
           attributeContainer,
           implicitOutputsFunction);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Rule.java b/src/main/java/com/google/devtools/build/lib/packages/Rule.java
index 28f0df3..5e2c1b5 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Rule.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Rule.java
@@ -78,6 +78,8 @@
 
   private final Location location;
 
+  private final CallStack callstack;
+
   private final ImplicitOutputsFunction implicitOutputsFunction;
 
   // Initialized in the call to populateOutputFiles.
@@ -89,12 +91,14 @@
       Label label,
       RuleClass ruleClass,
       Location location,
+      CallStack callstack,
       AttributeContainer attributeContainer) {
     this(
         pkg,
         label,
         ruleClass,
         location,
+        callstack,
         attributeContainer,
         ruleClass.getDefaultImplicitOutputsFunction());
   }
@@ -104,12 +108,14 @@
       Label label,
       RuleClass ruleClass,
       Location location,
+      CallStack callstack,
       AttributeContainer attributeContainer,
       ImplicitOutputsFunction implicitOutputsFunction) {
     this.pkg = Preconditions.checkNotNull(pkg);
     this.label = label;
     this.ruleClass = Preconditions.checkNotNull(ruleClass);
     this.location = Preconditions.checkNotNull(location);
+    this.callstack = Preconditions.checkNotNull(callstack);
     this.attributes = attributeContainer;
     this.implicitOutputsFunction = implicitOutputsFunction;
     this.containsErrors = false;
@@ -270,6 +276,11 @@
     return location;
   }
 
+  /** Returns the stack of function calls active when this rule was instantiated. */
+  public CallStack getCallStack() {
+    return callstack;
+  }
+
   public String getDefinitionInformation() {
     return definitionInformation;
   }
@@ -611,7 +622,6 @@
   }
 
   @Override
-  @SuppressWarnings("unchecked")
   public Set<DistributionType> getDistributions() {
     if (isAttrDefined("distribs", BuildType.DISTRIBUTIONS)
         && isAttributeValueExplicitlySpecified("distribs")) {
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index 9b5504b..89b9edb 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -60,6 +60,7 @@
 import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkFunction;
+import com.google.devtools.build.lib.syntax.StarlarkThread;
 import com.google.devtools.build.lib.util.FileTypeSet;
 import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -1833,10 +1834,11 @@
       AttributeValues<T> attributeValues,
       EventHandler eventHandler,
       Location location,
+      List<StarlarkThread.CallStackEntry> callstack,
       AttributeContainer attributeContainer,
       boolean checkThirdPartyRulesHaveLicenses)
       throws LabelSyntaxException, InterruptedException, CannotPrecomputeDefaultsException {
-    Rule rule = pkgBuilder.createRule(ruleLabel, this, location, attributeContainer);
+    Rule rule = pkgBuilder.createRule(ruleLabel, this, location, callstack, attributeContainer);
     populateRuleAttributeValues(rule, pkgBuilder, attributeValues, eventHandler);
     checkAspectAllowedValues(rule, eventHandler);
     rule.populateOutputFiles(eventHandler, pkgBuilder);
@@ -1870,15 +1872,13 @@
       Label ruleLabel,
       AttributeValues<T> attributeValues,
       Location location,
+      List<StarlarkThread.CallStackEntry> callstack,
       AttributeContainer attributeContainer,
       ImplicitOutputsFunction implicitOutputsFunction)
       throws InterruptedException, CannotPrecomputeDefaultsException {
-    Rule rule = pkgBuilder.createRule(
-        ruleLabel,
-        this,
-        location,
-        attributeContainer,
-        implicitOutputsFunction);
+    Rule rule =
+        pkgBuilder.createRule(
+            ruleLabel, this, location, callstack, attributeContainer, implicitOutputsFunction);
     populateRuleAttributeValues(rule, pkgBuilder, attributeValues, NullEventHandler.INSTANCE);
     rule.populateOutputFilesUnchecked(NullEventHandler.INSTANCE, pkgBuilder);
     return rule;
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java b/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java
index b37bfe9..6043e28 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleFactory.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.packages;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
@@ -24,7 +25,6 @@
 import com.google.devtools.build.lib.packages.Package.NameConflictException;
 import com.google.devtools.build.lib.packages.PackageFactory.PackageContext;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import javax.annotation.Nullable;
@@ -106,11 +106,22 @@
           ruleClass + " cannot be in the WORKSPACE file " + "(used by " + label + ")");
     }
 
-    // TODO(adonovan): record thread.getCallStack() in the rule,
-    // and make 'bazel query --output=build' display it (b/36593041).
+    ImmutableList<StarlarkThread.CallStackEntry> callstack =
+        thread != null ? thread.getCallStack() : ImmutableList.of();
 
     AttributesAndLocation generator =
-        generatorAttributesForMacros(pkgBuilder, attributeValues, thread, location, label);
+        generatorAttributesForMacros(pkgBuilder, attributeValues, callstack, location, label);
+
+    if (thread != null) {
+      // The raw stack is of the form [<toplevel>@BUILD:1, macro@lib.bzl:1, cc_library@<builtin>].
+      // If we're recording it (--record_rule_instantiation_callstack),
+      // pop the innermost frame for the rule, since it's obvious.
+      callstack =
+          thread.getSemantics().recordRuleInstantiationCallstack()
+              ? callstack.subList(0, callstack.size() - 1) // pop
+              : ImmutableList.of(); // save space
+    }
+
     try {
       // Examines --incompatible_disable_third_party_license_checking to see if we should check
       // third party targets for license existence.
@@ -126,6 +137,7 @@
           generator.attributes,
           eventHandler,
           generator.location,
+          callstack,
           attributeContainer,
           checkThirdPartyLicenses);
     } catch (LabelSyntaxException | CannotPrecomputeDefaultsException e) {
@@ -306,14 +318,9 @@
   private static AttributesAndLocation generatorAttributesForMacros(
       Package.Builder pkgBuilder,
       BuildLangTypedAttributeValuesMap args,
-      @Nullable StarlarkThread thread,
+      ImmutableList<StarlarkThread.CallStackEntry> stack,
       Location location,
       Label label) {
-    // Returns the original arguments if a) there is only the rule itself on the stack
-    // trace (=> no macro) or b) the attributes have already been set by Python pre-processing.
-    if (thread == null) {
-      return new AttributesAndLocation(args, location);
-    }
     boolean hasName = args.containsAttributeNamed("generator_name");
     boolean hasFunc = args.containsAttributeNamed("generator_function");
     // TODO(bazel-team): resolve cases in our code where hasName && !hasFunc, or hasFunc && !hasName
@@ -326,7 +333,6 @@
     // The stack must contain at least two entries:
     // 0: the outermost function (e.g. a BUILD file),
     // 1: the function called by it (e.g. a "macro" in a .bzl file).
-    List<StarlarkThread.CallStackEntry> stack = thread.getCallStack();
     if (stack.size() < 2 || !stack.get(1).location.file().endsWith(".bzl")) {
       return new AttributesAndLocation(args, location); // macro is not a Starlark function
     }
@@ -368,6 +374,7 @@
    *
    * @return The workspace-relative path of the given location, or null if it could not be computed.
    */
+  // TODO(b/151151653): make Starlark file Locations relative from the outset.
   @Nullable
   private static String maybeGetRelativeLocation(@Nullable Location location, Label label) {
     if (location == null) {
@@ -379,6 +386,9 @@
     // rules created from function calls in a subincluded file, even if both files share a path
     // prefix (for example, when //a/package:BUILD subincludes //a/package/with/a/subpackage:BUILD).
     // We can revert to that approach once subincludes aren't supported anymore.
+    //
+    // TODO(b/151165647): this logic has always been wrong:
+    // it spuriously matches occurrences of the package name earlier in the path.
     String absolutePath = location.toString();
     int pos = absolutePath.indexOf(label.getPackageName());
     return (pos < 0) ? null : absolutePath.substring(pos);
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
index a6443a4..aec88df 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
@@ -654,6 +654,16 @@
               + "instead of linkopts to cc_toolchain_config")
   public boolean incompatibleLinkoptsToLinkLibs;
 
+  @Option(
+      name = "record_rule_instantiation_callstack",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
+      effectTags = {OptionEffectTag.BUILD_FILE_SEMANTICS},
+      help =
+          "Causes each rule to record the callstack at the moment of its instantiation, at a"
+              + " modest cost in memory. The stack is visible in some forms of query output.")
+  public boolean recordRuleInstantiationCallstack;
+
   /**
    * An interner to reduce the number of StarlarkSemantics instances. A single Blaze instance should
    * never accumulate a large number of these and being able to shortcut on object identity makes a
@@ -714,6 +724,7 @@
             .incompatibleRequireLinkerInputCcApi(incompatibleRequireLinkerInputCcApi)
             .incompatibleRestrictStringEscapes(incompatibleRestrictStringEscapes)
             .incompatibleLinkoptsToLinkLibs(incompatibleLinkoptsToLinkLibs)
+            .recordRuleInstantiationCallstack(recordRuleInstantiationCallstack)
             .build();
     return INTERNER.intern(semantics);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
index ad69a34..708eb65 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
@@ -240,11 +240,13 @@
       try {
         // The old rule references another Package instance and we wan't to keep the invariant that
         // every Rule references the Package it is contained within
-        Rule newRule = builder.createRule(
-            rule.getLabel(),
-            rule.getRuleClassObject(),
-            rule.getLocation(),
-            rule.getAttributeContainer());
+        Rule newRule =
+            builder.createRule(
+                rule.getLabel(),
+                rule.getRuleClassObject(),
+                rule.getLocation(),
+                rule.getCallStack().toList(),
+                rule.getAttributeContainer());
         newRule.populateOutputFiles(NullEventHandler.INSTANCE, builder);
         if (rule.containsErrors()) {
           newRule.setContainsErrors();
diff --git a/src/main/java/com/google/devtools/build/lib/query2/query/output/BuildOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/query/output/BuildOutputFormatter.java
index 5f43425..36a5bdc 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/query/output/BuildOutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/query/output/BuildOutputFormatter.java
@@ -31,6 +31,7 @@
 import com.google.devtools.build.lib.query2.engine.ThreadSafeOutputFormatterCallback;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
+import com.google.devtools.build.lib.syntax.StarlarkThread;
 import java.io.IOException;
 import java.io.OutputStream;
 import java.io.Writer;
@@ -93,6 +94,11 @@
     /** Outputs a given rule in BUILD-style syntax. */
     private void outputRule(Rule rule, AttributeReader attrReader, Writer writer)
         throws IOException {
+      // TODO(b/151151653): display the filenames in root-relative form.
+      // This is an incompatible change, but Blaze users (and their editors)
+      // must already be equipped to handle relative paths as all compiler
+      // error messages are execroot-relative.
+
       writer.append("# ").append(rule.getLocation().toString()).append(lineTerm);
       writer.append(rule.getRuleClass()).append("(").append(lineTerm);
       writer.append("  name = \"").append(rule.getName()).append("\",").append(lineTerm);
@@ -130,7 +136,33 @@
             .append(",")
             .append(lineTerm);
       }
-      writer.append(")\n").append(lineTerm);
+      writer.append(")").append(lineTerm);
+
+      // Display the instantiation stack, if any.
+      // For readability, ensure columns line up.
+      int maxLocLen = 0;
+      List<StarlarkThread.CallStackEntry> stack = rule.getCallStack().toList().reverse();
+      for (StarlarkThread.CallStackEntry fr : stack) {
+        maxLocLen = Math.max(maxLocLen, fr.location.toString().length());
+      }
+      if (maxLocLen > 0) {
+        writer.append("# Instantiation stack:\n");
+        for (StarlarkThread.CallStackEntry fr : stack) {
+          String loc = fr.location.toString(); // TODO(b/151151653): display root-relative
+          // Java's String.format doesn't support
+          // right-padding with %*s, so we must loop.
+          writer.append("#   ").append(loc);
+          for (int i = loc.length(); i < maxLocLen; i++) {
+            writer.append(' ');
+          }
+          writer.append(" called from ").append(fr.name).append("\n");
+        }
+      }
+
+      // TODO(adonovan): also record and show creation stack for rule.getRuleClassObject(),
+      // and list inputs and outputs of the rule.
+
+      writer.append(lineTerm);
     }
 
     /** Outputs the given attribute value BUILD-style. Does not support selects. */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
index 1aedd1fd..9d7786e 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
@@ -87,6 +87,8 @@
         "incompatible_require_linker_input_cc_api";
     public static final String INCOMPATIBLE_LINKOPTS_TO_LINKLIBS =
         "incompatible_linkopts_to_linklibs";
+    public static final String RECORD_RULE_INSTANTIATION_CALLSTACK =
+        "record_rule_instantiation_callstack";
   }
 
   // TODO(adonovan): replace the fields of StarlarkSemantics
@@ -139,6 +141,8 @@
         return incompatibleRequireLinkerInputCcApi();
       case FlagIdentifier.INCOMPATIBLE_LINKOPTS_TO_LINKLIBS:
         return incompatibleLinkoptsToLinkLibs();
+      case FlagIdentifier.RECORD_RULE_INSTANTIATION_CALLSTACK:
+        return recordRuleInstantiationCallstack();
       default:
         throw new IllegalArgumentException(flag);
     }
@@ -268,6 +272,8 @@
 
   public abstract boolean incompatibleLinkoptsToLinkLibs();
 
+  public abstract boolean recordRuleInstantiationCallstack();
+
   @Memoized
   @Override
   public abstract int hashCode();
@@ -345,6 +351,7 @@
           .incompatibleRestrictStringEscapes(false)
           .incompatibleUseCcConfigureFromRulesCc(false)
           .incompatibleLinkoptsToLinkLibs(false)
+          .recordRuleInstantiationCallstack(false)
           .build();
 
   /** Builder for {@link StarlarkSemantics}. All fields are mandatory. */
@@ -440,6 +447,8 @@
 
     public abstract Builder incompatibleLinkoptsToLinkLibs(boolean value);
 
+    public abstract Builder recordRuleInstantiationCallstack(boolean value);
+
     public abstract StarlarkSemantics build();
   }
 }