diff --git a/android/rule_builder.go b/android/rule_builder.go
index 72c0d10..06e82c8 100644
--- a/android/rule_builder.go
+++ b/android/rule_builder.go
@@ -793,13 +793,6 @@
 	return path.String()
 }
 
-// SboxPathForTool takes a path to a tool, which may be an output file or a source file, and returns
-// the corresponding path for the tool in the sbox sandbox.  It assumes that sandboxing and tool
-// sandboxing are enabled.
-func SboxPathForTool(ctx BuilderContext, path Path) string {
-	return filepath.Join(sboxSandboxBaseDir, sboxPathForToolRel(ctx, path))
-}
-
 func sboxPathForToolRel(ctx BuilderContext, path Path) string {
 	// Errors will be handled in RuleBuilder.Build where we have a context to report them
 	relOut, isRelOut, _ := maybeRelErr(PathForOutput(ctx, "host", ctx.Config().PrebuiltOS()).String(), path.String())
@@ -842,17 +835,21 @@
 	return ret
 }
 
-// SboxPathForPackagedTool takes a PackageSpec for a tool and returns the corresponding path for the
-// tool after copying it into the sandbox.  This can be used  on the RuleBuilder command line to
-// reference the tool.
-func SboxPathForPackagedTool(spec PackagingSpec) string {
-	return filepath.Join(sboxSandboxBaseDir, sboxPathForPackagedToolRel(spec))
-}
-
 func sboxPathForPackagedToolRel(spec PackagingSpec) string {
 	return filepath.Join(sboxToolsSubDir, "out", spec.relPathInPackage)
 }
 
+// PathForPackagedTool takes a PackageSpec for a tool and returns the corresponding path for the
+// tool after copying it into the sandbox.  This can be used  on the RuleBuilder command line to
+// reference the tool.
+func (c *RuleBuilderCommand) PathForPackagedTool(spec PackagingSpec) string {
+	if !c.rule.sboxTools {
+		panic("PathForPackagedTool() requires SandboxTools()")
+	}
+
+	return filepath.Join(sboxSandboxBaseDir, sboxPathForPackagedToolRel(spec))
+}
+
 // PathForTool takes a path to a tool, which may be an output file or a source file, and returns
 // the corresponding path for the tool in the sbox sandbox if sbox is enabled, or the original path
 // if it is not.  This can be used  on the RuleBuilder command line to reference the tool.
@@ -863,6 +860,20 @@
 	return path.String()
 }
 
+// PathsForTools takes a list of paths to tools, which may be output files or source files, and
+// returns the corresponding paths for the tools in the sbox sandbox if sbox is enabled, or the
+// original paths if it is not.  This can be used  on the RuleBuilder command line to reference the tool.
+func (c *RuleBuilderCommand) PathsForTools(paths Paths) []string {
+	if c.rule.sbox && c.rule.sboxTools {
+		var ret []string
+		for _, path := range paths {
+			ret = append(ret, filepath.Join(sboxSandboxBaseDir, sboxPathForToolRel(c.rule.ctx, path)))
+		}
+		return ret
+	}
+	return paths.Strings()
+}
+
 // PackagedTool adds the specified tool path to the command line.  It can only be used with tool
 // sandboxing enabled by SandboxTools(), and will copy the tool into the sandbox.
 func (c *RuleBuilderCommand) PackagedTool(spec PackagingSpec) *RuleBuilderCommand {
diff --git a/genrule/Android.bp b/genrule/Android.bp
index 214940d..8fb5c40 100644
--- a/genrule/Android.bp
+++ b/genrule/Android.bp
@@ -16,6 +16,7 @@
     ],
     srcs: [
         "genrule.go",
+        "locations.go",
     ],
     testSrcs: [
         "genrule_test.go",
diff --git a/genrule/genrule.go b/genrule/genrule.go
index cb841ed..9019a83 100644
--- a/genrule/genrule.go
+++ b/genrule/genrule.go
@@ -91,7 +91,6 @@
 
 func init() {
 	pctx.Import("android/soong/android")
-	pctx.HostBinToolVariable("sboxCmd", "sbox")
 
 	pctx.HostBinToolVariable("soongZip", "soong_zip")
 	pctx.HostBinToolVariable("zipSync", "zipsync")
@@ -254,18 +253,18 @@
 		g.exportedIncludeDirs = append(g.exportedIncludeDirs, android.PathForModuleGen(ctx, g.subDir))
 	}
 
-	locationLabels := map[string][]string{}
+	locationLabels := map[string]location{}
 	firstLabel := ""
 
-	addLocationLabel := func(label string, paths []string) {
+	addLocationLabel := func(label string, loc location) {
 		if firstLabel == "" {
 			firstLabel = label
 		}
 		if _, exists := locationLabels[label]; !exists {
-			locationLabels[label] = paths
+			locationLabels[label] = loc
 		} else {
 			ctx.ModuleErrorf("multiple labels for %q, %q and %q",
-				label, strings.Join(locationLabels[label], " "), strings.Join(paths, " "))
+				label, locationLabels[label], loc)
 		}
 	}
 
@@ -303,17 +302,17 @@
 						// sandbox.
 						packagedTools = append(packagedTools, specs...)
 						// Assume that the first PackagingSpec of the module is the tool.
-						addLocationLabel(tag.label, []string{android.SboxPathForPackagedTool(specs[0])})
+						addLocationLabel(tag.label, packagedToolLocation{specs[0]})
 					} else {
 						tools = append(tools, path.Path())
-						addLocationLabel(tag.label, []string{android.SboxPathForTool(ctx, path.Path())})
+						addLocationLabel(tag.label, toolLocation{android.Paths{path.Path()}})
 					}
 				case bootstrap.GoBinaryTool:
 					// A GoBinaryTool provides the install path to a tool, which will be copied.
 					if s, err := filepath.Rel(android.PathForOutput(ctx).String(), t.InstallPath()); err == nil {
 						toolPath := android.PathForOutput(ctx, s)
 						tools = append(tools, toolPath)
-						addLocationLabel(tag.label, []string{android.SboxPathForTool(ctx, toolPath)})
+						addLocationLabel(tag.label, toolLocation{android.Paths{toolPath}})
 					} else {
 						ctx.ModuleErrorf("cannot find path for %q: %v", tool, err)
 						return
@@ -335,7 +334,7 @@
 		if ctx.Config().AllowMissingDependencies() {
 			for _, tool := range g.properties.Tools {
 				if !seenTools[tool] {
-					addLocationLabel(tool, []string{"***missing tool " + tool + "***"})
+					addLocationLabel(tool, errorLocation{"***missing tool " + tool + "***"})
 				}
 			}
 		}
@@ -348,11 +347,7 @@
 	for _, toolFile := range g.properties.Tool_files {
 		paths := android.PathsForModuleSrc(ctx, []string{toolFile})
 		tools = append(tools, paths...)
-		var sandboxPaths []string
-		for _, path := range paths {
-			sandboxPaths = append(sandboxPaths, android.SboxPathForTool(ctx, path))
-		}
-		addLocationLabel(toolFile, sandboxPaths)
+		addLocationLabel(toolFile, toolLocation{paths})
 	}
 
 	var srcFiles android.Paths
@@ -370,10 +365,10 @@
 			// The command that uses this placeholder file will never be executed because the rule will be
 			// replaced with an android.Error rule reporting the missing dependencies.
 			ctx.AddMissingDependencies(missingDeps)
-			addLocationLabel(in, []string{"***missing srcs " + in + "***"})
+			addLocationLabel(in, errorLocation{"***missing srcs " + in + "***"})
 		} else {
 			srcFiles = append(srcFiles, paths...)
-			addLocationLabel(in, paths.Strings())
+			addLocationLabel(in, inputLocation{paths})
 		}
 	}
 
@@ -408,7 +403,7 @@
 		cmd := rule.Command()
 
 		for _, out := range task.out {
-			addLocationLabel(out.Rel(), []string{cmd.PathForOutput(out)})
+			addLocationLabel(out.Rel(), outputLocation{out})
 		}
 
 		referencedDepfile := false
@@ -426,16 +421,17 @@
 				if len(g.properties.Tools) == 0 && len(g.properties.Tool_files) == 0 {
 					return reportError("at least one `tools` or `tool_files` is required if $(location) is used")
 				}
-				paths := locationLabels[firstLabel]
+				loc := locationLabels[firstLabel]
+				paths := loc.Paths(cmd)
 				if len(paths) == 0 {
 					return reportError("default label %q has no files", firstLabel)
 				} else if len(paths) > 1 {
 					return reportError("default label %q has multiple files, use $(locations %s) to reference it",
 						firstLabel, firstLabel)
 				}
-				return locationLabels[firstLabel][0], nil
+				return paths[0], nil
 			case "in":
-				return strings.Join(srcFiles.Strings(), " "), nil
+				return strings.Join(cmd.PathsForInputs(srcFiles), " "), nil
 			case "out":
 				var sandboxOuts []string
 				for _, out := range task.out {
@@ -453,7 +449,8 @@
 			default:
 				if strings.HasPrefix(name, "location ") {
 					label := strings.TrimSpace(strings.TrimPrefix(name, "location "))
-					if paths, ok := locationLabels[label]; ok {
+					if loc, ok := locationLabels[label]; ok {
+						paths := loc.Paths(cmd)
 						if len(paths) == 0 {
 							return reportError("label %q has no files", label)
 						} else if len(paths) > 1 {
@@ -466,7 +463,8 @@
 					}
 				} else if strings.HasPrefix(name, "locations ") {
 					label := strings.TrimSpace(strings.TrimPrefix(name, "locations "))
-					if paths, ok := locationLabels[label]; ok {
+					if loc, ok := locationLabels[label]; ok {
+						paths := loc.Paths(cmd)
 						if len(paths) == 0 {
 							return reportError("label %q has no files", label)
 						}
@@ -719,7 +717,7 @@
 				outputDepfile = android.PathForModuleGen(ctx, genSubDir, "gensrcs.d")
 				depFixerTool := ctx.Config().HostToolPath(ctx, "dep_fixer")
 				fullCommand += fmt.Sprintf(" && %s -o $(depfile) %s",
-					android.SboxPathForTool(ctx, depFixerTool),
+					rule.Command().PathForTool(depFixerTool),
 					strings.Join(commandDepFiles, " "))
 				extraTools = append(extraTools, depFixerTool)
 			}
diff --git a/genrule/locations.go b/genrule/locations.go
new file mode 100644
index 0000000..2978b91
--- /dev/null
+++ b/genrule/locations.go
@@ -0,0 +1,104 @@
+// Copyright 2021 Google Inc. 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 genrule
+
+import (
+	"strings"
+
+	"android/soong/android"
+)
+
+// location is used to service $(location) and $(locations) entries in genrule commands.
+type location interface {
+	Paths(cmd *android.RuleBuilderCommand) []string
+	String() string
+}
+
+// inputLocation is a $(location) result for an entry in the srcs property.
+type inputLocation struct {
+	paths android.Paths
+}
+
+func (l inputLocation) String() string {
+	return strings.Join(l.paths.Strings(), " ")
+}
+
+func (l inputLocation) Paths(cmd *android.RuleBuilderCommand) []string {
+	return cmd.PathsForInputs(l.paths)
+}
+
+var _ location = inputLocation{}
+
+// outputLocation is a $(location) result for an entry in the out property.
+type outputLocation struct {
+	path android.WritablePath
+}
+
+func (l outputLocation) String() string {
+	return l.path.String()
+}
+
+func (l outputLocation) Paths(cmd *android.RuleBuilderCommand) []string {
+	return []string{cmd.PathForOutput(l.path)}
+}
+
+var _ location = outputLocation{}
+
+// toolLocation is a $(location) result for an entry in the tools or tool_files property.
+type toolLocation struct {
+	paths android.Paths
+}
+
+func (l toolLocation) String() string {
+	return strings.Join(l.paths.Strings(), " ")
+}
+
+func (l toolLocation) Paths(cmd *android.RuleBuilderCommand) []string {
+	return cmd.PathsForTools(l.paths)
+}
+
+var _ location = toolLocation{}
+
+// packagedToolLocation is a $(location) result for an entry in the tools or tool_files property
+// that has PackagingSpecs.
+type packagedToolLocation struct {
+	spec android.PackagingSpec
+}
+
+func (l packagedToolLocation) String() string {
+	return l.spec.FileName()
+}
+
+func (l packagedToolLocation) Paths(cmd *android.RuleBuilderCommand) []string {
+	return []string{cmd.PathForPackagedTool(l.spec)}
+}
+
+var _ location = packagedToolLocation{}
+
+// errorLocation is a placeholder for a $(location) result that returns garbage to break the command
+// when error reporting is delayed by ALLOW_MISSING_DEPENDENCIES=true.
+type errorLocation struct {
+	err string
+}
+
+func (l errorLocation) String() string {
+	return l.err
+}
+
+func (l errorLocation) Paths(cmd *android.RuleBuilderCommand) []string {
+	return []string{l.err}
+}
+
+var _ location = errorLocation{}