Initial implementation of a Skylark debug server API.

I've pulled out the API for separate review. It includes all
hooks from blaze/skylark used by the debugger.

Debuggable thread contexts are currently declared in 3 places:
- BuildFileAST (top-level evaluation of BUILD files)
- SkylarkRuleConfiguredTargetUtil (rules)
- SkylarkAspectFactory (aspects)

The purpose of declaring these contexts is so that the debugger
can track currently-active threads (and stop tracking them when
the task is completed).

Details of the actual debugging server are in unknown commit.

PiperOrigin-RevId: 197770547
diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index 3704699..ada11c9 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -59,6 +59,7 @@
         "//src/main/java/com/google/devtools/build/lib/skylarkbuildapi:srcs",
         "//src/main/java/com/google/devtools/build/lib/skylarkbuildapi/cpp:srcs",
         "//src/main/java/com/google/devtools/build/lib/skylarkbuildapi/java:srcs",
+        "//src/main/java/com/google/devtools/build/lib/skylarkdebug/module:srcs",
         "//src/main/java/com/google/devtools/build/lib/skylarkdebug/proto:srcs",
         "//src/main/java/com/google/devtools/build/lib/skylarkdebug/server:srcs",
         "//src/main/java/com/google/devtools/build/lib/skylarkinterface/processor:srcs",
@@ -710,6 +711,7 @@
         "//src/main/java/com/google/devtools/build/lib/profiler/memory:allocationtracker_module",
         "//src/main/java/com/google/devtools/build/lib/remote",
         "//src/main/java/com/google/devtools/build/lib/sandbox",
+        "//src/main/java/com/google/devtools/build/lib/skylarkdebug/module",
         "//src/main/java/com/google/devtools/build/lib/ssd",
         "//src/main/java/com/google/devtools/build/lib/standalone",
         "//src/main/java/com/google/devtools/build/lib/worker",
@@ -1289,6 +1291,7 @@
         "//src/main/java/com/google/devtools/build/lib/query2:query-engine",
         "//src/main/java/com/google/devtools/build/lib/query2:query-output",
         "//src/main/java/com/google/devtools/build/lib/shell",
+        "//src/main/java/com/google/devtools/build/lib/skylarkdebug/module:options",
         "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/main/java/com/google/devtools/build/lib/windows",
         "//src/main/java/com/google/devtools/build/skyframe",
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleConfiguredTargetUtil.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleConfiguredTargetUtil.java
index 1cc7543..5dd1479 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleConfiguredTargetUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleConfiguredTargetUtil.java
@@ -43,6 +43,7 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 import com.google.devtools.build.lib.syntax.BaseFunction;
 import com.google.devtools.build.lib.syntax.ClassObject;
+import com.google.devtools.build.lib.syntax.DebugServerUtils;
 import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalExceptionWithStackTrace;
@@ -92,12 +93,19 @@
               .setEventHandler(ruleContext.getAnalysisEnvironment().getEventHandler())
               .build(); // NB: loading phase functions are not available: this is analysis already,
       // so we do *not* setLoadingPhase().
+
+      final SkylarkRuleContext finalContext = skylarkRuleContext;
       Object target =
-          ruleImplementation.call(
-              /*args=*/ ImmutableList.of(skylarkRuleContext),
-              /*kwargs*/ ImmutableMap.of(),
-              /*ast=*/ null,
-              env);
+          DebugServerUtils.runWithDebuggingIfEnabled(
+              env,
+              () ->
+                  String.format("Target %s", ruleContext.getTarget().getLabel().getCanonicalForm()),
+              () ->
+                  ruleImplementation.call(
+                      /*args=*/ ImmutableList.of(finalContext),
+                      /*kwargs*/ ImmutableMap.of(),
+                      /*ast=*/ null,
+                      env));
 
       if (ruleContext.hasErrors()) {
         return null;
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/Bazel.java b/src/main/java/com/google/devtools/build/lib/bazel/Bazel.java
index 6c3e1d7..c6cabaa 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/Bazel.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/Bazel.java
@@ -43,6 +43,7 @@
           com.google.devtools.build.lib.bazel.BazelWorkspaceStatusModule.class,
           com.google.devtools.build.lib.bazel.BazelDiffAwarenessModule.class,
           com.google.devtools.build.lib.bazel.BazelRepositoryModule.class,
+          com.google.devtools.build.lib.skylarkdebug.module.SkylarkDebuggerModule.class,
           com.google.devtools.build.lib.bazel.repository.RepositoryResolvedModule.class,
           com.google.devtools.build.lib.bazel.SpawnLogModule.class,
           com.google.devtools.build.lib.ssd.SsdModule.class,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkAspectFactory.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkAspectFactory.java
index a01560e..fad7c84 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkAspectFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkAspectFactory.java
@@ -29,6 +29,7 @@
 import com.google.devtools.build.lib.packages.SkylarkDefinedAspect;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.DebugServerUtils;
 import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalExceptionWithStackTrace;
@@ -37,9 +38,7 @@
 import com.google.devtools.build.lib.syntax.SkylarkType;
 import java.util.Map;
 
-/**
- * A factory for aspects that are defined in Skylark.
- */
+/** A factory for aspects that are defined in Skylark. */
 public class SkylarkAspectFactory implements ConfiguredAspectFactory {
 
   private final SkylarkDefinedAspect skylarkAspect;
@@ -54,12 +53,13 @@
       throws InterruptedException {
     SkylarkRuleContext skylarkRuleContext = null;
     try (Mutability mutability = Mutability.create("aspect")) {
-      AspectDescriptor aspectDescriptor = new AspectDescriptor(
-          skylarkAspect.getAspectClass(), parameters);
+      AspectDescriptor aspectDescriptor =
+          new AspectDescriptor(skylarkAspect.getAspectClass(), parameters);
       AnalysisEnvironment analysisEnv = ruleContext.getAnalysisEnvironment();
       try {
-        skylarkRuleContext = new SkylarkRuleContext(
-            ruleContext, aspectDescriptor, analysisEnv.getSkylarkSemantics());
+        skylarkRuleContext =
+            new SkylarkRuleContext(
+                ruleContext, aspectDescriptor, analysisEnv.getSkylarkSemantics());
       } catch (EvalException e) {
         ruleContext.ruleError(e.getMessage());
         return null;
@@ -71,16 +71,25 @@
               // NB: loading phase functions are not available: this is analysis already, so we do
               // *not* setLoadingPhase().
               .build();
-      Object aspectSkylarkObject;
       try {
-        aspectSkylarkObject =
-            skylarkAspect
-                .getImplementation()
-                .call(
-                    /*args=*/ ImmutableList.of(ctadBase.getConfiguredTarget(), skylarkRuleContext),
-                    /* kwargs= */ ImmutableMap.of(),
-                    /*ast=*/ null,
-                    env);
+        final SkylarkRuleContext finalRuleContext = skylarkRuleContext;
+        Object aspectSkylarkObject =
+            DebugServerUtils.runWithDebuggingIfEnabled(
+                env,
+                () ->
+                    String.format(
+                        "Aspect %s on %s",
+                        skylarkAspect.getName(),
+                        ruleContext.getTarget().getLabel().getCanonicalForm()),
+                () ->
+                    skylarkAspect
+                        .getImplementation()
+                        .call(
+                            /*args=*/ ImmutableList.of(
+                                ctadBase.getConfiguredTarget(), finalRuleContext),
+                            /* kwargs= */ ImmutableMap.of(),
+                            /*ast=*/ null,
+                            env));
 
         if (ruleContext.hasErrors()) {
           return null;
@@ -99,9 +108,9 @@
         return null;
       }
     } finally {
-       if (skylarkRuleContext != null) {
-         skylarkRuleContext.nullify();
-       }
+      if (skylarkRuleContext != null) {
+        skylarkRuleContext.nullify();
+      }
     }
   }
 
@@ -160,8 +169,7 @@
     }
   }
 
-  private static void addOutputGroups(Object value, Location loc,
-      ConfiguredAspect.Builder builder)
+  private static void addOutputGroups(Object value, Location loc, ConfiguredAspect.Builder builder)
       throws EvalException {
     Map<String, SkylarkValue> outputGroups =
         SkylarkType.castMap(value, String.class, SkylarkValue.class, "output_groups");
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/BUILD b/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/BUILD
new file mode 100644
index 0000000..00fae16
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/BUILD
@@ -0,0 +1,25 @@
+package(default_visibility = ["//src:__subpackages__"])
+
+filegroup(
+    name = "srcs",
+    srcs = glob(["**"]),
+    visibility = ["//src/main/java/com/google/devtools/build/lib:__pkg__"],
+)
+
+java_library(
+    name = "module",
+    srcs = ["SkylarkDebuggerModule.java"],
+    deps = [
+        ":options",
+        "//src/main/java/com/google/devtools/build/lib:events",
+        "//src/main/java/com/google/devtools/build/lib:runtime",
+    ],
+)
+
+java_library(
+    name = "options",
+    srcs = ["SkylarkDebuggerOptions.java"],
+    deps = [
+        "//src/main/java/com/google/devtools/common/options",
+    ],
+)
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/SkylarkDebuggerModule.java b/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/SkylarkDebuggerModule.java
new file mode 100644
index 0000000..167d3c8
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/SkylarkDebuggerModule.java
@@ -0,0 +1,47 @@
+// Copyright 2018 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.skylarkdebug.module;
+
+import com.google.devtools.build.lib.events.Reporter;
+import com.google.devtools.build.lib.runtime.BlazeModule;
+import com.google.devtools.build.lib.runtime.CommandEnvironment;
+
+/** Blaze module for setting up Skylark debugging. */
+public final class SkylarkDebuggerModule extends BlazeModule {
+  @Override
+  public void beforeCommand(CommandEnvironment env) {
+    // Conditionally enable debugging
+    SkylarkDebuggerOptions buildOptions = env.getOptions().getOptions(SkylarkDebuggerOptions.class);
+    boolean enabled = buildOptions != null && buildOptions.debugSkylark;
+    if (enabled) {
+      initializeDebugging(env.getReporter(), buildOptions.debugServerPort);
+    } else {
+      disableDebugging();
+    }
+  }
+
+  @Override
+  public void afterCommand() {
+    disableDebugging();
+  }
+
+  private static void initializeDebugging(Reporter reporter, int debugPort) {
+    // TODO(brendandouglas): implement a debug server
+  }
+
+  private static void disableDebugging() {
+    // TODO(brendandouglas): implement a debug server
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/SkylarkDebuggerOptions.java b/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/SkylarkDebuggerOptions.java
new file mode 100644
index 0000000..831a777
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skylarkdebug/module/SkylarkDebuggerOptions.java
@@ -0,0 +1,45 @@
+// Copyright 2018 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.skylarkdebug.module;
+
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionDocumentationCategory;
+import com.google.devtools.common.options.OptionEffectTag;
+import com.google.devtools.common.options.OptionMetadataTag;
+import com.google.devtools.common.options.OptionsBase;
+
+/** Configuration options for Skylark debugging. */
+public final class SkylarkDebuggerOptions extends OptionsBase {
+  @Option(
+      name = "experimental_skylark_debug",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
+      effectTags = {OptionEffectTag.EXECUTION},
+      metadataTags = {OptionMetadataTag.EXPERIMENTAL},
+      help =
+          "If true, Blaze will open the Skylark debug server at the start of the build "
+              + "invocation, and wait for a debugger to attach before running the build.")
+  public boolean debugSkylark;
+
+  @Option(
+      name = "experimental_debug_server_port",
+      defaultValue = "7300",
+      category = "server startup",
+      documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
+      effectTags = {OptionEffectTag.EXECUTION},
+      metadataTags = {OptionMetadataTag.EXPERIMENTAL},
+      help = "The port on which the Skylark debug server will listen for connections.")
+  public int debugServerPort;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java b/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java
index 439e4c5..ca6307f 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BuildFileAST.java
@@ -193,6 +193,18 @@
    * @return true if no error occurred during execution.
    */
   public boolean exec(Environment env, EventHandler eventHandler) throws InterruptedException {
+    try {
+      // Handles debugging BUILD file evaluation
+      // TODO(bazel-team): add support for debugging skylark file evaluation
+      return DebugServerUtils.runWithDebuggingIfEnabled(
+          env, () -> Thread.currentThread().getName(), () -> doExec(env, eventHandler));
+    } catch (EvalException e) {
+      // runWithDebuggingIfEnabled() shouldn't throw EvalException, since doExec() does not
+      throw new AssertionError("Unexpected EvalException", e);
+    }
+  }
+
+  private boolean doExec(Environment env, EventHandler eventHandler) throws InterruptedException {
     boolean ok = true;
     for (Statement stmt : statements) {
       if (!execTopLevelStatement(stmt, env, eventHandler)) {
@@ -222,7 +234,7 @@
   public boolean execTopLevelStatement(Statement stmt, Environment env,
       EventHandler eventHandler) throws InterruptedException {
     try {
-      new Eval(env).exec(stmt);
+      Eval.fromEnvironment(env).exec(stmt);
       return true;
     } catch (EvalException e) {
       // Do not report errors caused by a previous parsing error, as it has already been
@@ -367,7 +379,7 @@
    */
   @Nullable public Object eval(Environment env) throws EvalException, InterruptedException {
     Object last = null;
-    Eval evaluator = new Eval(env);
+    Eval evaluator = Eval.fromEnvironment(env);
     for (Statement statement : statements) {
       if (statement instanceof ExpressionStatement) {
         last = ((ExpressionStatement) statement).getExpression().eval(env);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DebugFrame.java b/src/main/java/com/google/devtools/build/lib/syntax/DebugFrame.java
new file mode 100644
index 0000000..362739c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DebugFrame.java
@@ -0,0 +1,58 @@
+// Copyright 2018 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.syntax;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.events.Location;
+import javax.annotation.Nullable;
+
+/** The information about a single frame in a thread's stack trace relevant to the debugger. */
+@AutoValue
+public abstract class DebugFrame {
+  /** The source location where the frame is currently paused. */
+  @Nullable
+  public abstract Location location();
+
+  /** The name of the function that this frame represents. */
+  public abstract String functionName();
+
+  /**
+   * The local bindings associated with the current lexical frame. For the outer-most scope this
+   * will be empty.
+   */
+  public abstract ImmutableMap<String, Object> lexicalFrameBindings();
+
+  /** The global vars and builtins for this frame. May be shadowed by the lexical frame bindings. */
+  public abstract ImmutableMap<String, Object> globalBindings();
+
+  public static Builder builder() {
+    return new AutoValue_DebugFrame.Builder().setLexicalFrameBindings(ImmutableMap.of());
+  }
+
+  /** Builder class for {@link DebugFrame}. */
+  @AutoValue.Builder
+  public abstract static class Builder {
+    public abstract Builder setLocation(@Nullable Location location);
+
+    public abstract Builder setFunctionName(String functionName);
+
+    public abstract Builder setLexicalFrameBindings(ImmutableMap<String, Object> bindings);
+
+    public abstract Builder setGlobalBindings(ImmutableMap<String, Object> bindings);
+
+    public abstract DebugFrame build();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DebugServer.java b/src/main/java/com/google/devtools/build/lib/syntax/DebugServer.java
new file mode 100644
index 0000000..f462550
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DebugServer.java
@@ -0,0 +1,42 @@
+// Copyright 2018 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.syntax;
+
+/** A debug server interface, called from core skylark code. */
+public interface DebugServer {
+
+  /**
+   * Tracks the execution of the given callable object in the debug server.
+   *
+   * @param env the Skylark execution environment
+   * @param threadName the descriptive name of the thread
+   * @param callable the callable object whose execution will be tracked
+   * @param <T> the result type of the callable
+   * @return the value returned by the callable
+   */
+  <T> T runWithDebugging(Environment env, String threadName, DebugCallable<T> callable)
+      throws EvalException, InterruptedException;
+
+  /** Represents an invocation that will be tracked as a thread by the Skylark debug server. */
+  interface DebugCallable<T> {
+
+    /**
+     * The invocation that will be tracked.
+     *
+     * @return the result
+     */
+    T call() throws EvalException, InterruptedException;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DebugServerUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/DebugServerUtils.java
new file mode 100644
index 0000000..f653cd9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DebugServerUtils.java
@@ -0,0 +1,64 @@
+// Copyright 2018 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.syntax;
+
+import com.google.devtools.build.lib.syntax.DebugServer.DebugCallable;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.function.Function;
+import java.util.function.Supplier;
+
+/** A helper class for enabling/disabling skylark debugging. */
+public final class DebugServerUtils {
+
+  private DebugServerUtils() {}
+
+  private static final AtomicReference<DebugServer> instance = new AtomicReference<>();
+
+  /**
+   * Called at the start of a debuggable skylark session to enable debugging. The custom {@link
+   * Eval} supplier provided should intercept statement execution to check for breakpoints.
+   */
+  public static void initializeDebugServer(
+      DebugServer server, Function<Environment, Eval> evalOverride) {
+    instance.set(server);
+    Eval.setEvalSupplier(evalOverride);
+  }
+
+  /** Called at the end of a debuggable skylark session to disable debugging. */
+  public static void disableDebugging() {
+    instance.set(null);
+    Eval.removeCustomEval();
+  }
+
+  /**
+   * Tracks the execution of the given callable object in the debug server.
+   *
+   * <p>If the skylark debugger is not enabled, runs {@code callable} directly.
+   *
+   * @param env the Skylark execution environment
+   * @param threadName the descriptive name of the thread
+   * @param callable the callable object whose execution will be tracked
+   * @param <T> the result type of the callable
+   * @return the value returned by the callable
+   */
+  public static <T> T runWithDebuggingIfEnabled(
+      Environment env, Supplier<String> threadName, DebugCallable<T> callable)
+      throws EvalException, InterruptedException {
+    DebugServer server = instance.get();
+    return server != null
+        ? server.runWithDebugging(env, threadName.get(), callable)
+        : callable.call();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Debuggable.java b/src/main/java/com/google/devtools/build/lib/syntax/Debuggable.java
new file mode 100644
index 0000000..4540f55
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Debuggable.java
@@ -0,0 +1,80 @@
+// Copyright 2018 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.syntax;
+
+import com.google.devtools.build.lib.events.Location;
+import java.util.Collection;
+import java.util.function.Predicate;
+import javax.annotation.Nullable;
+
+/** A context in which debugging can occur. Implemented by Skylark environments. */
+public interface Debuggable {
+
+  /** Evaluates a Skylark expression in the adapter's environment. */
+  Object evaluate(String expression) throws EvalException, InterruptedException;
+
+  /**
+   * Returns the stack frames corresponding of the context's current (paused) state.
+   *
+   * <p>For all stack frames except the innermost, location information is retrieved from the
+   * current context. The innermost frame's location must be supplied as {@code currentLocation} by
+   * the caller.
+   */
+  Collection<DebugFrame> listFrames(Location currentLocation);
+
+  /**
+   * Given a requested stepping behavior, returns a predicate over the context that tells the
+   * debugger when to pause.
+   *
+   * <p>The predicate will return true if we are at the next statement where execution should pause,
+   * and it will return false if we are not yet at that statement. No guarantee is made about the
+   * predicate's return value after we have reached the desired statement.
+   *
+   * <p>A null return value indicates that no further pausing should occur.
+   */
+  @Nullable
+  ReadyToPause stepControl(Stepping stepping);
+
+  /**
+   * When stepping, this determines whether or not the context has yet reached a state for which
+   * execution should be paused.
+   *
+   * <p>A single instance is only useful for advancing by one pause. A new instance may be required
+   * after that.
+   */
+  interface ReadyToPause extends Predicate<Environment> {}
+
+  /** Describes the stepping behavior that should occur when execution of a thread is continued. */
+  enum Stepping {
+    /** Continue execution without stepping. */
+    NONE,
+    /**
+     * If the thread is paused on a statement that contains a function call, step into that
+     * function. Otherwise, this is the same as OVER.
+     */
+    INTO,
+    /**
+     * Step over the current statement and any functions that it may call, stopping at the next
+     * statement in the same frame. If no more statements are available in the current frame, same
+     * as OUT.
+     */
+    OVER,
+    /**
+     * Continue execution until the current frame has been exited and then pause. If we are
+     * currently in the outer-most frame, same as NONE.
+     */
+    OUT,
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
index c536a68..6f84188 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -16,6 +16,7 @@
 
 import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -31,10 +32,12 @@
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.SpellChecker;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
+import java.util.List;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Set;
@@ -75,7 +78,7 @@
  * that the words "dynamic" and "static" refer to the point of view of the source code, and here we
  * have a dual point of view.
  */
-public final class Environment implements Freezable {
+public final class Environment implements Freezable, Debuggable {
 
   /**
    * A phase for enabling or disabling certain builtin functions
@@ -1150,6 +1153,91 @@
     return vars;
   }
 
+  private static final class EvalEventHandler implements EventHandler {
+    List<String> messages = new ArrayList<>();
+
+    @Override
+    public void handle(Event event) {
+      if (event.getKind() == EventKind.ERROR) {
+        messages.add(event.getMessage());
+      }
+    }
+  }
+
+  @Override
+  public Object evaluate(String expression) throws EvalException, InterruptedException {
+    ParserInputSource inputSource =
+        ParserInputSource.create(expression, PathFragment.create("<debug eval>"));
+    EvalEventHandler eventHandler = new EvalEventHandler();
+    Expression expr = Parser.parseExpression(inputSource, eventHandler);
+    if (!eventHandler.messages.isEmpty()) {
+      throw new EvalException(expr.getLocation(), eventHandler.messages.get(0));
+    }
+    return expr.eval(this);
+  }
+
+  @Override
+  public ImmutableList<DebugFrame> listFrames(Location currentLocation) {
+    ImmutableList.Builder<DebugFrame> frameListBuilder = ImmutableList.builder();
+
+    Continuation currentContinuation = continuation;
+    Frame currentFrame = currentFrame();
+
+    // if there's a continuation then the current frame is a lexical frame
+    while (currentContinuation != null) {
+      frameListBuilder.add(
+          DebugFrame.builder()
+              .setLexicalFrameBindings(ImmutableMap.copyOf(currentFrame.getTransitiveBindings()))
+              .setGlobalBindings(ImmutableMap.copyOf(getGlobals().getTransitiveBindings()))
+              .setFunctionName(currentContinuation.function.getFullName())
+              .setLocation(currentLocation)
+              .build());
+
+      currentFrame = currentContinuation.lexicalFrame;
+      currentLocation = currentContinuation.caller.getLocation();
+      currentContinuation = currentContinuation.continuation;
+    }
+
+    frameListBuilder.add(
+        DebugFrame.builder()
+            .setGlobalBindings(ImmutableMap.copyOf(getGlobals().getTransitiveBindings()))
+            .setFunctionName("<top level>")
+            .setLocation(currentLocation)
+            .build());
+
+    return frameListBuilder.build();
+  }
+
+  @Override
+  @Nullable
+  public ReadyToPause stepControl(Stepping stepping) {
+    final Continuation pausedContinuation = continuation;
+
+    switch (stepping) {
+      case NONE:
+        return null;
+      case INTO:
+        // pause at the very next statement
+        return env -> true;
+      case OVER:
+        return env -> isAt(env, pausedContinuation) || isOutside(env, pausedContinuation);
+      case OUT:
+        // if we're at the outer-most frame, same as NONE
+        return pausedContinuation == null ? null : env -> isOutside(env, pausedContinuation);
+    }
+    throw new IllegalArgumentException("Unsupported stepping type: " + stepping);
+  }
+
+  /** Returns true if {@code env} is in a parent frame of {@code pausedContinuation}. */
+  private static boolean isOutside(Environment env, @Nullable Continuation pausedContinuation) {
+    return pausedContinuation != null && env.continuation == pausedContinuation.continuation;
+  }
+
+  /** Returns true if {@code env} is at the same frame as {@code pausedContinuation. */
+  private static boolean isAt(Environment env, @Nullable Continuation pausedContinuation) {
+    return env.continuation == pausedContinuation;
+  }
+
   @Override
   public int hashCode() {
     throw new UnsupportedOperationException(); // avoid nondeterminism
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
index 98130ae..56c98a7 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
@@ -18,13 +18,14 @@
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
+import java.util.function.Function;
 
 /**
  * Evaluation code for the Skylark AST. At the moment, it can execute only statements (and defers to
  * Expression.eval for evaluating expressions).
  */
 public class Eval {
-  private final Environment env;
+  protected final Environment env;
 
   /** An exception that signals changes in the control flow (e.g. break or continue) */
   private static class FlowException extends EvalException {
@@ -38,11 +39,31 @@
     }
   }
 
+  public static Eval fromEnvironment(Environment env) {
+    return evalSupplier.apply(env);
+  }
+
+  public static void setEvalSupplier(Function<Environment, Eval> evalSupplier) {
+    Eval.evalSupplier = evalSupplier;
+  }
+
+  /** Reset Eval supplier to the default. */
+  public static void removeCustomEval() {
+    evalSupplier = Eval::new;
+  }
+
+  // TODO(bazel-team): remove this static state in favor of storing Eval instances in Environment
+  private static Function<Environment, Eval> evalSupplier = Eval::new;
+
   private static final FlowException breakException = new FlowException("FlowException - break");
   private static final FlowException continueException =
       new FlowException("FlowException - continue");
 
-  public Eval(Environment env) {
+  /**
+   * This constructor should never be called directly. Call {@link #fromEnvironment(Environment)}
+   * instead.
+   */
+  protected Eval(Environment env) {
     this.env = env;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
index eda6c3d..4db184e 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
@@ -76,7 +76,7 @@
         env.update(name, arguments[i++]);
       }
 
-      Eval eval = new Eval(env);
+      Eval eval = Eval.fromEnvironment(env);
       try {
         for (Statement stmt : statements) {
           if (stmt instanceof ReturnStatement) {