Initial implementation of the bazel sandwich

The "bazel sandwich" is a mechanism for bazel to depend on make/soong
outputs. The name comes from the fact that bazel is now at the top
and bottom of the build graph. This is intended to allow us to work
on converting the partition builds to bazel while not all of the
dependencies of the partition have been converted.

It works by adding the bazel_sandwich_import_file rule, which emits a
dangling symlink that starts with bazel_sandwich:, and includes
information that the aquery handler in soong reads. The aquery handler
rewrites the symlink so that it points to a file generated by
make/soong, and adds a ninja dependency from the symlink to the file
it's targeting.

This allows us to depend on make-built files from bazel, but notably
it doesn't allow us to depend on analysis-time information from make.
This shouldn't be a problem for the partitions, but limits the use of
the bazel sandwich to similar, less complicated types of builds.

go/roboleaf-bazel-sandwich

Bug: 265127181
Test: m bazel_sandwich
Change-Id: Ic41bae7be0b55f251d04a6a95f846c50ce897adc
diff --git a/bazel/aquery.go b/bazel/aquery.go
index 3428328..563c531 100644
--- a/bazel/aquery.go
+++ b/bazel/aquery.go
@@ -17,15 +17,15 @@
 import (
 	"crypto/sha256"
 	"encoding/base64"
+	"encoding/json"
 	"fmt"
 	"path/filepath"
+	analysis_v2_proto "prebuilts/bazel/common/proto/analysis_v2"
 	"reflect"
 	"sort"
 	"strings"
 	"sync"
 
-	analysis_v2_proto "prebuilts/bazel/common/proto/analysis_v2"
-
 	"github.com/google/blueprint/metrics"
 	"github.com/google/blueprint/proptools"
 	"google.golang.org/protobuf/proto"
@@ -119,6 +119,10 @@
 	// If ShouldRunInSbox is true, Soong will use sbox to created an isolated environment
 	// and run the mixed build action there
 	ShouldRunInSbox bool
+	// A list of files to add as implicit deps to the outputs of this BuildStatement.
+	// Unlike most properties in BuildStatement, these paths must be relative to the root of
+	// the whole out/ folder, instead of relative to ctx.Config().BazelContext.OutputBase()
+	ImplicitDeps []string
 }
 
 // A helper type for aquery processing which facilitates retrieval of path IDs from their
@@ -581,6 +585,72 @@
 	}, nil
 }
 
+type bazelSandwichJson struct {
+	Target         string   `json:"target"`
+	DependOnTarget *bool    `json:"depend_on_target,omitempty"`
+	ImplicitDeps   []string `json:"implicit_deps"`
+}
+
+func (a *aqueryArtifactHandler) unresolvedSymlinkActionBuildStatement(actionEntry *analysis_v2_proto.Action) (*BuildStatement, error) {
+	outputPaths, depfile, err := a.getOutputPaths(actionEntry)
+	if err != nil {
+		return nil, err
+	}
+	if len(actionEntry.InputDepSetIds) != 0 || len(outputPaths) != 1 {
+		return nil, fmt.Errorf("expected 0 inputs and 1 output to symlink action, got: input %q, output %q", actionEntry.InputDepSetIds, outputPaths)
+	}
+	target := actionEntry.UnresolvedSymlinkTarget
+	if target == "" {
+		return nil, fmt.Errorf("expected an unresolved_symlink_target, but didn't get one")
+	}
+	if filepath.Clean(target) != target {
+		return nil, fmt.Errorf("expected %q, got %q", filepath.Clean(target), target)
+	}
+	if strings.HasPrefix(target, "/") {
+		return nil, fmt.Errorf("no absolute symlinks allowed: %s", target)
+	}
+
+	out := outputPaths[0]
+	outDir := filepath.Dir(out)
+	var implicitDeps []string
+	if strings.HasPrefix(target, "bazel_sandwich:") {
+		j := bazelSandwichJson{}
+		err := json.Unmarshal([]byte(target[len("bazel_sandwich:"):]), &j)
+		if err != nil {
+			return nil, err
+		}
+		if proptools.BoolDefault(j.DependOnTarget, true) {
+			implicitDeps = append(implicitDeps, j.Target)
+		}
+		implicitDeps = append(implicitDeps, j.ImplicitDeps...)
+		dotDotsToReachCwd := ""
+		if outDir != "." {
+			dotDotsToReachCwd = strings.Repeat("../", strings.Count(outDir, "/")+1)
+		}
+		target = proptools.ShellEscapeIncludingSpaces(j.Target)
+		target = "{DOTDOTS_TO_OUTPUT_ROOT}" + dotDotsToReachCwd + target
+	} else {
+		target = proptools.ShellEscapeIncludingSpaces(target)
+	}
+
+	outDir = proptools.ShellEscapeIncludingSpaces(outDir)
+	out = proptools.ShellEscapeIncludingSpaces(out)
+	// Use absolute paths, because some soong actions don't play well with relative paths (for example, `cp -d`).
+	command := fmt.Sprintf("mkdir -p %[1]s && rm -f %[2]s && ln -sf %[3]s %[2]s", outDir, out, target)
+	symlinkPaths := outputPaths[:]
+
+	buildStatement := &BuildStatement{
+		Command:      command,
+		Depfile:      depfile,
+		OutputPaths:  outputPaths,
+		Env:          actionEntry.EnvironmentVariables,
+		Mnemonic:     actionEntry.Mnemonic,
+		SymlinkPaths: symlinkPaths,
+		ImplicitDeps: implicitDeps,
+	}
+	return buildStatement, nil
+}
+
 func (a *aqueryArtifactHandler) symlinkActionBuildStatement(actionEntry *analysis_v2_proto.Action) (*BuildStatement, error) {
 	outputPaths, depfile, err := a.getOutputPaths(actionEntry)
 	if err != nil {
@@ -690,6 +760,8 @@
 		return a.fileWriteActionBuildStatement(actionEntry)
 	case "SymlinkTree":
 		return a.symlinkTreeActionBuildStatement(actionEntry)
+	case "UnresolvedSymlink":
+		return a.unresolvedSymlinkActionBuildStatement(actionEntry)
 	}
 
 	if len(actionEntry.Arguments) < 1 {