feat(tvix/build): add refscanning interface r/8742

This provides a generic interface to let the builder search for needles
 in the output, as described in the notes at `docs/src/build/index.md`.

Change-Id: Ic2c5bd563e9aa2e766c157f2b13cdb19aede12f8
Reviewed-on: https://cl.tvl.fyi/c/depot/+/12531
Autosubmit: yuka <yuka@yuka.dev>
Tested-by: BuildkiteCI
Reviewed-by: flokli <flokli@flokli.de>
Reviewed-by: Brian Olsen <me@griff.name>

3 files changed, 153 insertions, 42 deletions

diff --git a/tvix/build-go/build.pb.go b/tvix/build-go/build.pb.go
index c1fbf28b547a..ef9caf2ea6ab 100644
--- a/tvix/build-go/build.pb.go
+++ b/tvix/build-go/build.pb.go
@@ -115,6 +115,11 @@ type BuildRequest struct {
 	// build environment, but outside inputs_dir.
 	// Used for passAsFile and structuredAttrs in Nix.
 	AdditionalFiles []*BuildRequest_AdditionalFile `protobuf:"bytes,9,rep,name=additional_files,json=additionalFiles,proto3" json:"additional_files,omitempty"`
+	// If this is an non-empty list, all paths in `outputs` are scanned for these.
+	// For Nix, `refscan_needles` would be populated with the nixbase32 hash parts of
+	// every input store path and output store path. The latter is necessary to scan
+	// for references between multi-output derivations.
+	RefscanNeedles []string `protobuf:"bytes,10,rep,name=refscan_needles,json=refscanNeedles,proto3" json:"refscan_needles,omitempty"`
 }
 
 func (x *BuildRequest) Reset() {
@@ -212,6 +217,13 @@ func (x *BuildRequest) GetAdditionalFiles() []*BuildRequest_AdditionalFile {
 	return nil
 }
 
+func (x *BuildRequest) GetRefscanNeedles() []string {
+	if x != nil {
+		return x.RefscanNeedles
+	}
+	return nil
+}
+
 // A Build is (one possible) outcome of executing a [BuildRequest].
 type Build struct {
 	state         protoimpl.MessageState
@@ -223,6 +235,8 @@ type Build struct {
 	// The outputs that were produced after successfully building.
 	// They are sorted by their names.
 	Outputs []*castore_go.Node `protobuf:"bytes,2,rep,name=outputs,proto3" json:"outputs,omitempty"`
+	// Contains the same number of elements as the `outputs` field.
+	OutputsNeedles []*Build_OutputNeedles `protobuf:"bytes,3,rep,name=outputs_needles,json=outputsNeedles,proto3" json:"outputs_needles,omitempty"`
 }
 
 func (x *Build) Reset() {
@@ -271,6 +285,13 @@ func (x *Build) GetOutputs() []*castore_go.Node {
 	return nil
 }
 
+func (x *Build) GetOutputsNeedles() []*Build_OutputNeedles {
+	if x != nil {
+		return x.OutputsNeedles
+	}
+	return nil
+}
+
 type BuildRequest_EnvVar struct {
 	state         protoimpl.MessageState
 	sizeCache     protoimpl.SizeCache
@@ -477,6 +498,54 @@ func (x *BuildRequest_AdditionalFile) GetContents() []byte {
 	return nil
 }
 
+type Build_OutputNeedles struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	// The numbers are indexing into `refscan_needles` originally specified in the BuildRequest.
+	Needles []uint64 `protobuf:"varint,1,rep,packed,name=needles,proto3" json:"needles,omitempty"`
+}
+
+func (x *Build_OutputNeedles) Reset() {
+	*x = Build_OutputNeedles{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_tvix_build_protos_build_proto_msgTypes[5]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *Build_OutputNeedles) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*Build_OutputNeedles) ProtoMessage() {}
+
+func (x *Build_OutputNeedles) ProtoReflect() protoreflect.Message {
+	mi := &file_tvix_build_protos_build_proto_msgTypes[5]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use Build_OutputNeedles.ProtoReflect.Descriptor instead.
+func (*Build_OutputNeedles) Descriptor() ([]byte, []int) {
+	return file_tvix_build_protos_build_proto_rawDescGZIP(), []int{1, 0}
+}
+
+func (x *Build_OutputNeedles) GetNeedles() []uint64 {
+	if x != nil {
+		return x.Needles
+	}
+	return nil
+}
+
 var File_tvix_build_protos_build_proto protoreflect.FileDescriptor
 
 var file_tvix_build_protos_build_proto_rawDesc = []byte{
@@ -485,7 +554,7 @@ var file_tvix_build_protos_build_proto_rawDesc = []byte{
 	0x0d, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x2e, 0x76, 0x31, 0x1a, 0x21,
 	0x74, 0x76, 0x69, 0x78, 0x2f, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2f, 0x70, 0x72, 0x6f,
 	0x74, 0x6f, 0x73, 0x2f, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x70, 0x72, 0x6f, 0x74,
-	0x6f, 0x22, 0x90, 0x06, 0x0a, 0x0c, 0x42, 0x75, 0x69, 0x6c, 0x64, 0x52, 0x65, 0x71, 0x75, 0x65,
+	0x6f, 0x22, 0xb9, 0x06, 0x0a, 0x0c, 0x42, 0x75, 0x69, 0x6c, 0x64, 0x52, 0x65, 0x71, 0x75, 0x65,
 	0x73, 0x74, 0x12, 0x2d, 0x0a, 0x06, 0x69, 0x6e, 0x70, 0x75, 0x74, 0x73, 0x18, 0x01, 0x20, 0x03,
 	0x28, 0x0b, 0x32, 0x15, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72,
 	0x65, 0x2e, 0x76, 0x31, 0x2e, 0x4e, 0x6f, 0x64, 0x65, 0x52, 0x06, 0x69, 0x6e, 0x70, 0x75, 0x74,
@@ -514,37 +583,47 @@ var file_tvix_build_protos_build_proto_rawDesc = []byte{
 	0x76, 0x69, 0x78, 0x2e, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x2e, 0x76, 0x31, 0x2e, 0x42, 0x75, 0x69,
 	0x6c, 0x64, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x2e, 0x41, 0x64, 0x64, 0x69, 0x74, 0x69,
 	0x6f, 0x6e, 0x61, 0x6c, 0x46, 0x69, 0x6c, 0x65, 0x52, 0x0f, 0x61, 0x64, 0x64, 0x69, 0x74, 0x69,
-	0x6f, 0x6e, 0x61, 0x6c, 0x46, 0x69, 0x6c, 0x65, 0x73, 0x1a, 0x30, 0x0a, 0x06, 0x45, 0x6e, 0x76,
-	0x56, 0x61, 0x72, 0x12, 0x10, 0x0a, 0x03, 0x6b, 0x65, 0x79, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09,
-	0x52, 0x03, 0x6b, 0x65, 0x79, 0x12, 0x14, 0x0a, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x18, 0x02,
-	0x20, 0x01, 0x28, 0x0c, 0x52, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x1a, 0xc4, 0x01, 0x0a, 0x10,
-	0x42, 0x75, 0x69, 0x6c, 0x64, 0x43, 0x6f, 0x6e, 0x73, 0x74, 0x72, 0x61, 0x69, 0x6e, 0x74, 0x73,
-	0x12, 0x16, 0x0a, 0x06, 0x73, 0x79, 0x73, 0x74, 0x65, 0x6d, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09,
-	0x52, 0x06, 0x73, 0x79, 0x73, 0x74, 0x65, 0x6d, 0x12, 0x1d, 0x0a, 0x0a, 0x6d, 0x69, 0x6e, 0x5f,
-	0x6d, 0x65, 0x6d, 0x6f, 0x72, 0x79, 0x18, 0x02, 0x20, 0x01, 0x28, 0x04, 0x52, 0x09, 0x6d, 0x69,
-	0x6e, 0x4d, 0x65, 0x6d, 0x6f, 0x72, 0x79, 0x12, 0x2c, 0x0a, 0x12, 0x61, 0x76, 0x61, 0x69, 0x6c,
-	0x61, 0x62, 0x6c, 0x65, 0x5f, 0x72, 0x6f, 0x5f, 0x70, 0x61, 0x74, 0x68, 0x73, 0x18, 0x03, 0x20,
-	0x03, 0x28, 0x09, 0x52, 0x10, 0x61, 0x76, 0x61, 0x69, 0x6c, 0x61, 0x62, 0x6c, 0x65, 0x52, 0x6f,
-	0x50, 0x61, 0x74, 0x68, 0x73, 0x12, 0x25, 0x0a, 0x0e, 0x6e, 0x65, 0x74, 0x77, 0x6f, 0x72, 0x6b,
-	0x5f, 0x61, 0x63, 0x63, 0x65, 0x73, 0x73, 0x18, 0x04, 0x20, 0x01, 0x28, 0x08, 0x52, 0x0d, 0x6e,
-	0x65, 0x74, 0x77, 0x6f, 0x72, 0x6b, 0x41, 0x63, 0x63, 0x65, 0x73, 0x73, 0x12, 0x24, 0x0a, 0x0e,
-	0x70, 0x72, 0x6f, 0x76, 0x69, 0x64, 0x65, 0x5f, 0x62, 0x69, 0x6e, 0x5f, 0x73, 0x68, 0x18, 0x05,
-	0x20, 0x01, 0x28, 0x08, 0x52, 0x0c, 0x70, 0x72, 0x6f, 0x76, 0x69, 0x64, 0x65, 0x42, 0x69, 0x6e,
-	0x53, 0x68, 0x1a, 0x40, 0x0a, 0x0e, 0x41, 0x64, 0x64, 0x69, 0x74, 0x69, 0x6f, 0x6e, 0x61, 0x6c,
-	0x46, 0x69, 0x6c, 0x65, 0x12, 0x12, 0x0a, 0x04, 0x70, 0x61, 0x74, 0x68, 0x18, 0x01, 0x20, 0x01,
-	0x28, 0x09, 0x52, 0x04, 0x70, 0x61, 0x74, 0x68, 0x12, 0x1a, 0x0a, 0x08, 0x63, 0x6f, 0x6e, 0x74,
-	0x65, 0x6e, 0x74, 0x73, 0x18, 0x02, 0x20, 0x01, 0x28, 0x0c, 0x52, 0x08, 0x63, 0x6f, 0x6e, 0x74,
-	0x65, 0x6e, 0x74, 0x73, 0x22, 0x7a, 0x0a, 0x05, 0x42, 0x75, 0x69, 0x6c, 0x64, 0x12, 0x40, 0x0a,
-	0x0d, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x5f, 0x72, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x18, 0x01,
-	0x20, 0x01, 0x28, 0x0b, 0x32, 0x1b, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x62, 0x75, 0x69, 0x6c,
-	0x64, 0x2e, 0x76, 0x31, 0x2e, 0x42, 0x75, 0x69, 0x6c, 0x64, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73,
-	0x74, 0x52, 0x0c, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x12,
-	0x2f, 0x0a, 0x07, 0x6f, 0x75, 0x74, 0x70, 0x75, 0x74, 0x73, 0x18, 0x02, 0x20, 0x03, 0x28, 0x0b,
-	0x32, 0x15, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e,
-	0x76, 0x31, 0x2e, 0x4e, 0x6f, 0x64, 0x65, 0x52, 0x07, 0x6f, 0x75, 0x74, 0x70, 0x75, 0x74, 0x73,
-	0x42, 0x24, 0x5a, 0x22, 0x63, 0x6f, 0x64, 0x65, 0x2e, 0x74, 0x76, 0x6c, 0x2e, 0x66, 0x79, 0x69,
-	0x2f, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x2d, 0x67, 0x6f, 0x3b, 0x62,
-	0x75, 0x69, 0x6c, 0x64, 0x76, 0x31, 0x62, 0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x33,
+	0x6f, 0x6e, 0x61, 0x6c, 0x46, 0x69, 0x6c, 0x65, 0x73, 0x12, 0x27, 0x0a, 0x0f, 0x72, 0x65, 0x66,
+	0x73, 0x63, 0x61, 0x6e, 0x5f, 0x6e, 0x65, 0x65, 0x64, 0x6c, 0x65, 0x73, 0x18, 0x0a, 0x20, 0x03,
+	0x28, 0x09, 0x52, 0x0e, 0x72, 0x65, 0x66, 0x73, 0x63, 0x61, 0x6e, 0x4e, 0x65, 0x65, 0x64, 0x6c,
+	0x65, 0x73, 0x1a, 0x30, 0x0a, 0x06, 0x45, 0x6e, 0x76, 0x56, 0x61, 0x72, 0x12, 0x10, 0x0a, 0x03,
+	0x6b, 0x65, 0x79, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x03, 0x6b, 0x65, 0x79, 0x12, 0x14,
+	0x0a, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x18, 0x02, 0x20, 0x01, 0x28, 0x0c, 0x52, 0x05, 0x76,
+	0x61, 0x6c, 0x75, 0x65, 0x1a, 0xc4, 0x01, 0x0a, 0x10, 0x42, 0x75, 0x69, 0x6c, 0x64, 0x43, 0x6f,
+	0x6e, 0x73, 0x74, 0x72, 0x61, 0x69, 0x6e, 0x74, 0x73, 0x12, 0x16, 0x0a, 0x06, 0x73, 0x79, 0x73,
+	0x74, 0x65, 0x6d, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x06, 0x73, 0x79, 0x73, 0x74, 0x65,
+	0x6d, 0x12, 0x1d, 0x0a, 0x0a, 0x6d, 0x69, 0x6e, 0x5f, 0x6d, 0x65, 0x6d, 0x6f, 0x72, 0x79, 0x18,
+	0x02, 0x20, 0x01, 0x28, 0x04, 0x52, 0x09, 0x6d, 0x69, 0x6e, 0x4d, 0x65, 0x6d, 0x6f, 0x72, 0x79,
+	0x12, 0x2c, 0x0a, 0x12, 0x61, 0x76, 0x61, 0x69, 0x6c, 0x61, 0x62, 0x6c, 0x65, 0x5f, 0x72, 0x6f,
+	0x5f, 0x70, 0x61, 0x74, 0x68, 0x73, 0x18, 0x03, 0x20, 0x03, 0x28, 0x09, 0x52, 0x10, 0x61, 0x76,
+	0x61, 0x69, 0x6c, 0x61, 0x62, 0x6c, 0x65, 0x52, 0x6f, 0x50, 0x61, 0x74, 0x68, 0x73, 0x12, 0x25,
+	0x0a, 0x0e, 0x6e, 0x65, 0x74, 0x77, 0x6f, 0x72, 0x6b, 0x5f, 0x61, 0x63, 0x63, 0x65, 0x73, 0x73,
+	0x18, 0x04, 0x20, 0x01, 0x28, 0x08, 0x52, 0x0d, 0x6e, 0x65, 0x74, 0x77, 0x6f, 0x72, 0x6b, 0x41,
+	0x63, 0x63, 0x65, 0x73, 0x73, 0x12, 0x24, 0x0a, 0x0e, 0x70, 0x72, 0x6f, 0x76, 0x69, 0x64, 0x65,
+	0x5f, 0x62, 0x69, 0x6e, 0x5f, 0x73, 0x68, 0x18, 0x05, 0x20, 0x01, 0x28, 0x08, 0x52, 0x0c, 0x70,
+	0x72, 0x6f, 0x76, 0x69, 0x64, 0x65, 0x42, 0x69, 0x6e, 0x53, 0x68, 0x1a, 0x40, 0x0a, 0x0e, 0x41,
+	0x64, 0x64, 0x69, 0x74, 0x69, 0x6f, 0x6e, 0x61, 0x6c, 0x46, 0x69, 0x6c, 0x65, 0x12, 0x12, 0x0a,
+	0x04, 0x70, 0x61, 0x74, 0x68, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x04, 0x70, 0x61, 0x74,
+	0x68, 0x12, 0x1a, 0x0a, 0x08, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x73, 0x18, 0x02, 0x20,
+	0x01, 0x28, 0x0c, 0x52, 0x08, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x73, 0x22, 0xf2, 0x01,
+	0x0a, 0x05, 0x42, 0x75, 0x69, 0x6c, 0x64, 0x12, 0x40, 0x0a, 0x0d, 0x62, 0x75, 0x69, 0x6c, 0x64,
+	0x5f, 0x72, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x18, 0x01, 0x20, 0x01, 0x28, 0x0b, 0x32, 0x1b,
+	0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x2e, 0x76, 0x31, 0x2e, 0x42,
+	0x75, 0x69, 0x6c, 0x64, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x52, 0x0c, 0x62, 0x75, 0x69,
+	0x6c, 0x64, 0x52, 0x65, 0x71, 0x75, 0x65, 0x73, 0x74, 0x12, 0x2f, 0x0a, 0x07, 0x6f, 0x75, 0x74,
+	0x70, 0x75, 0x74, 0x73, 0x18, 0x02, 0x20, 0x03, 0x28, 0x0b, 0x32, 0x15, 0x2e, 0x74, 0x76, 0x69,
+	0x78, 0x2e, 0x63, 0x61, 0x73, 0x74, 0x6f, 0x72, 0x65, 0x2e, 0x76, 0x31, 0x2e, 0x4e, 0x6f, 0x64,
+	0x65, 0x52, 0x07, 0x6f, 0x75, 0x74, 0x70, 0x75, 0x74, 0x73, 0x12, 0x4b, 0x0a, 0x0f, 0x6f, 0x75,
+	0x74, 0x70, 0x75, 0x74, 0x73, 0x5f, 0x6e, 0x65, 0x65, 0x64, 0x6c, 0x65, 0x73, 0x18, 0x03, 0x20,
+	0x03, 0x28, 0x0b, 0x32, 0x22, 0x2e, 0x74, 0x76, 0x69, 0x78, 0x2e, 0x62, 0x75, 0x69, 0x6c, 0x64,
+	0x2e, 0x76, 0x31, 0x2e, 0x42, 0x75, 0x69, 0x6c, 0x64, 0x2e, 0x4f, 0x75, 0x74, 0x70, 0x75, 0x74,
+	0x4e, 0x65, 0x65, 0x64, 0x6c, 0x65, 0x73, 0x52, 0x0e, 0x6f, 0x75, 0x74, 0x70, 0x75, 0x74, 0x73,
+	0x4e, 0x65, 0x65, 0x64, 0x6c, 0x65, 0x73, 0x1a, 0x29, 0x0a, 0x0d, 0x4f, 0x75, 0x74, 0x70, 0x75,
+	0x74, 0x4e, 0x65, 0x65, 0x64, 0x6c, 0x65, 0x73, 0x12, 0x18, 0x0a, 0x07, 0x6e, 0x65, 0x65, 0x64,
+	0x6c, 0x65, 0x73, 0x18, 0x01, 0x20, 0x03, 0x28, 0x04, 0x52, 0x07, 0x6e, 0x65, 0x65, 0x64, 0x6c,
+	0x65, 0x73, 0x42, 0x24, 0x5a, 0x22, 0x63, 0x6f, 0x64, 0x65, 0x2e, 0x74, 0x76, 0x6c, 0x2e, 0x66,
+	0x79, 0x69, 0x2f, 0x74, 0x76, 0x69, 0x78, 0x2f, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x2d, 0x67, 0x6f,
+	0x3b, 0x62, 0x75, 0x69, 0x6c, 0x64, 0x76, 0x31, 0x62, 0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x33,
 }
 
 var (
@@ -559,27 +638,29 @@ func file_tvix_build_protos_build_proto_rawDescGZIP() []byte {
 	return file_tvix_build_protos_build_proto_rawDescData
 }
 
-var file_tvix_build_protos_build_proto_msgTypes = make([]protoimpl.MessageInfo, 5)
+var file_tvix_build_protos_build_proto_msgTypes = make([]protoimpl.MessageInfo, 6)
 var file_tvix_build_protos_build_proto_goTypes = []any{
 	(*BuildRequest)(nil),                  // 0: tvix.build.v1.BuildRequest
 	(*Build)(nil),                         // 1: tvix.build.v1.Build
 	(*BuildRequest_EnvVar)(nil),           // 2: tvix.build.v1.BuildRequest.EnvVar
 	(*BuildRequest_BuildConstraints)(nil), // 3: tvix.build.v1.BuildRequest.BuildConstraints
 	(*BuildRequest_AdditionalFile)(nil),   // 4: tvix.build.v1.BuildRequest.AdditionalFile
-	(*castore_go.Node)(nil),               // 5: tvix.castore.v1.Node
+	(*Build_OutputNeedles)(nil),           // 5: tvix.build.v1.Build.OutputNeedles
+	(*castore_go.Node)(nil),               // 6: tvix.castore.v1.Node
 }
 var file_tvix_build_protos_build_proto_depIdxs = []int32{
-	5, // 0: tvix.build.v1.BuildRequest.inputs:type_name -> tvix.castore.v1.Node
+	6, // 0: tvix.build.v1.BuildRequest.inputs:type_name -> tvix.castore.v1.Node
 	2, // 1: tvix.build.v1.BuildRequest.environment_vars:type_name -> tvix.build.v1.BuildRequest.EnvVar
 	3, // 2: tvix.build.v1.BuildRequest.constraints:type_name -> tvix.build.v1.BuildRequest.BuildConstraints
 	4, // 3: tvix.build.v1.BuildRequest.additional_files:type_name -> tvix.build.v1.BuildRequest.AdditionalFile
 	0, // 4: tvix.build.v1.Build.build_request:type_name -> tvix.build.v1.BuildRequest
-	5, // 5: tvix.build.v1.Build.outputs:type_name -> tvix.castore.v1.Node
-	6, // [6:6] is the sub-list for method output_type
-	6, // [6:6] is the sub-list for method input_type
-	6, // [6:6] is the sub-list for extension type_name
-	6, // [6:6] is the sub-list for extension extendee
-	0, // [0:6] is the sub-list for field type_name
+	6, // 5: tvix.build.v1.Build.outputs:type_name -> tvix.castore.v1.Node
+	5, // 6: tvix.build.v1.Build.outputs_needles:type_name -> tvix.build.v1.Build.OutputNeedles
+	7, // [7:7] is the sub-list for method output_type
+	7, // [7:7] is the sub-list for method input_type
+	7, // [7:7] is the sub-list for extension type_name
+	7, // [7:7] is the sub-list for extension extendee
+	0, // [0:7] is the sub-list for field type_name
 }
 
 func init() { file_tvix_build_protos_build_proto_init() }
@@ -648,6 +729,18 @@ func file_tvix_build_protos_build_proto_init() {
 				return nil
 			}
 		}
+		file_tvix_build_protos_build_proto_msgTypes[5].Exporter = func(v any, i int) any {
+			switch v := v.(*Build_OutputNeedles); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
 	}
 	type x struct{}
 	out := protoimpl.TypeBuilder{
@@ -655,7 +748,7 @@ func file_tvix_build_protos_build_proto_init() {
 			GoPackagePath: reflect.TypeOf(x{}).PkgPath(),
 			RawDescriptor: file_tvix_build_protos_build_proto_rawDesc,
 			NumEnums:      0,
-			NumMessages:   5,
+			NumMessages:   6,
 			NumExtensions: 0,
 			NumServices:   0,
 		},
diff --git a/tvix/build/protos/build.proto b/tvix/build/protos/build.proto
index 7a3c49db4873..1d6f8690c58c 100644
--- a/tvix/build/protos/build.proto
+++ b/tvix/build/protos/build.proto
@@ -144,6 +144,12 @@ message BuildRequest {
     bytes contents = 2;
   }
 
+  // If this is an non-empty list, all paths in `outputs` are scanned for these.
+  // For Nix, `refscan_needles` would be populated with the nixbase32 hash parts of
+  // every input store path and output store path. The latter is necessary to scan
+  // for references between multi-output derivations.
+  repeated string refscan_needles = 10;
+
   // TODO: allow describing something like "preferLocal", to influence composition?
 }
 
@@ -156,6 +162,14 @@ message Build {
   // They are sorted by their names.
   repeated tvix.castore.v1.Node outputs = 2;
 
+  message OutputNeedles {
+    // The numbers are indexing into `refscan_needles` originally specified in the BuildRequest.
+    repeated uint64 needles = 1;
+  }
+
+  // Contains the same number of elements as the `outputs` field.
+  repeated OutputNeedles outputs_needles = 3;
+
   // TODO: where did this run, how long, logs, …
 }
 
diff --git a/tvix/glue/src/tvix_build.rs b/tvix/glue/src/tvix_build.rs
index ae01351503f2..5187a76d48e5 100644
--- a/tvix/glue/src/tvix_build.rs
+++ b/tvix/glue/src/tvix_build.rs
@@ -100,6 +100,7 @@ pub(crate) fn derivation_to_build_request(
     });
 
     let build_request = BuildRequest {
+        refscan_needles: vec![], // TODO refscan
         command_args,
         outputs: output_paths,
 
@@ -276,6 +277,7 @@ mod test {
                 additional_files: vec![],
                 working_dir: "build".into(),
                 scratch_paths: vec!["build".into(), "nix/store".into()],
+                refscan_needles: vec![],
             },
             build_request
         );
@@ -345,6 +347,7 @@ mod test {
                 additional_files: vec![],
                 working_dir: "build".into(),
                 scratch_paths: vec!["build".into(), "nix/store".into()],
+                refscan_needles: vec![],
             },
             build_request
         );
@@ -431,6 +434,7 @@ mod test {
                 ],
                 working_dir: "build".into(),
                 scratch_paths: vec!["build".into(), "nix/store".into()],
+                refscan_needles: vec![],
             },
             build_request
         );