internal/pkg: content-based dependency substitution

This change introduces a new fast path for FloodArtifact. It is taken when a curing artifact has identical-by-content controlled relevant inputs and are otherwise identical to an already-cured artifact.

Signed-off-by: Ophestra <cat@gensokyo.uk>

8 files changed, 347 insertions, 57 deletions

diff --git a/internal/pkg/exec_test.go b/internal/pkg/exec_test.go
index 73249a56..6e436cae 100644
--- a/internal/pkg/exec_test.go
+++ b/internal/pkg/exec_test.go
@@ -52,7 +52,7 @@ func TestExec(t *testing.T) {
 	wantOfflineEncode := pkg.Encode(wantOffline.hash())
 
 	checkWithCache(t, []cacheTestCase{
-		{"offline", pkg.CValidateKnown, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
+		{"offline", pkg.CValidateKnown | checkDestroySubstitutes, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
 			testtool, testtoolDestroy := newTesttool()
 
 			cureMany(t, c, []cureStep{
@@ -141,11 +141,13 @@ func TestExec(t *testing.T) {
 			"identifier/" + expected.Offline:                                              {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantOfflineEncode)},
 			"identifier/vjz1MHPcGBKV7sjcs8jQP3cqxJ1hgPTiQBMCEHP9BGXjGxd-tJmEmXKaStObo5gK": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/MGWmEfjut2QE2xPJwTsmUzpff4BN_FEnQ7T0j7gvUCCiugJQNwqt9m151fm9D1yU")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
-		{"net", pkg.CValidateKnown, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
+		{"net", pkg.CValidateKnown | checkDestroySubstitutes, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
 			testtool, testtoolDestroy := newTesttool()
 
 			wantNet := expectsFS{
@@ -193,11 +195,13 @@ func TestExec(t *testing.T) {
 			"identifier/_gAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/OLBgp1GsljhM2TJ-sbHjaiH9txEUvgdDTAzHv2P24donTt6_529l-9Ua0vFImLlb")},
 			"identifier/vjz1MHPcGBKV7sjcs8jQP3cqxJ1hgPTiQBMCEHP9BGXjGxd-tJmEmXKaStObo5gK": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/MGWmEfjut2QE2xPJwTsmUzpff4BN_FEnQ7T0j7gvUCCiugJQNwqt9m151fm9D1yU")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
-		{"overlay root", pkg.CValidateKnown, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
+		{"overlay root", pkg.CValidateKnown | checkDestroySubstitutes, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
 			testtool, testtoolDestroy := newTesttool()
 
 			cureMany(t, c, []cureStep{
@@ -232,11 +236,13 @@ func TestExec(t *testing.T) {
 			"identifier/" + expected.OvlRoot: {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantOfflineEncode)},
 			"identifier/vjz1MHPcGBKV7sjcs8jQP3cqxJ1hgPTiQBMCEHP9BGXjGxd-tJmEmXKaStObo5gK": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/MGWmEfjut2QE2xPJwTsmUzpff4BN_FEnQ7T0j7gvUCCiugJQNwqt9m151fm9D1yU")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
-		{"overlay work", pkg.CValidateKnown, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
+		{"overlay work", pkg.CValidateKnown | checkDestroySubstitutes, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
 			testtool, testtoolDestroy := newTesttool()
 
 			cureMany(t, c, []cureStep{
@@ -276,11 +282,13 @@ func TestExec(t *testing.T) {
 			"identifier/" + expected.Work: {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantOfflineEncode)},
 			"identifier/vjz1MHPcGBKV7sjcs8jQP3cqxJ1hgPTiQBMCEHP9BGXjGxd-tJmEmXKaStObo5gK": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/MGWmEfjut2QE2xPJwTsmUzpff4BN_FEnQ7T0j7gvUCCiugJQNwqt9m151fm9D1yU")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
-		{"multiple layers", pkg.CValidateKnown, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
+		{"multiple layers", pkg.CValidateKnown | checkDestroySubstitutes, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
 			testtool, testtoolDestroy := newTesttool()
 
 			cureMany(t, c, []cureStep{
@@ -347,11 +355,13 @@ func TestExec(t *testing.T) {
 			"identifier/" + expected.Layers:                                               {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantOfflineEncode)},
 			"identifier/vjz1MHPcGBKV7sjcs8jQP3cqxJ1hgPTiQBMCEHP9BGXjGxd-tJmEmXKaStObo5gK": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/MGWmEfjut2QE2xPJwTsmUzpff4BN_FEnQ7T0j7gvUCCiugJQNwqt9m151fm9D1yU")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
-		{"overlay layer promotion", pkg.CValidateKnown, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
+		{"overlay layer promotion", pkg.CValidateKnown | checkDestroySubstitutes, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
 			testtool, testtoolDestroy := newTesttool()
 
 			cureMany(t, c, []cureStep{
@@ -393,11 +403,13 @@ func TestExec(t *testing.T) {
 			"identifier/vjz1MHPcGBKV7sjcs8jQP3cqxJ1hgPTiQBMCEHP9BGXjGxd-tJmEmXKaStObo5gK": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/MGWmEfjut2QE2xPJwTsmUzpff4BN_FEnQ7T0j7gvUCCiugJQNwqt9m151fm9D1yU")},
 			"identifier/" + expected.Promote:                                              {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantOfflineEncode)},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
-		{"binfmt", pkg.CValidateKnown, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
+		{"binfmt", pkg.CValidateKnown | checkDestroySubstitutes, nil, func(t *testing.T, base *check.Absolute, c *pkg.Cache) {
 			if info.CanDegrade && os.Getenv("ROSA_SKIP_BINFMT") != "" {
 				t.Skip("binfmt_misc test explicitly skipped")
 			}
@@ -456,6 +468,8 @@ func TestExec(t *testing.T) {
 			"identifier/_v8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/5aevg3YpDxjqQZ-pdvXK7YqgkL5JKqcoStYQxeD96kuYar6K2mRQWMHib6NQRnpV")},
 			"identifier/vjz1MHPcGBKV7sjcs8jQP3cqxJ1hgPTiQBMCEHP9BGXjGxd-tJmEmXKaStObo5gK": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/MGWmEfjut2QE2xPJwTsmUzpff4BN_FEnQ7T0j7gvUCCiugJQNwqt9m151fm9D1yU")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
diff --git a/internal/pkg/file_test.go b/internal/pkg/file_test.go
index 187ad7a0..9b326453 100644
--- a/internal/pkg/file_test.go
+++ b/internal/pkg/file_test.go
@@ -29,6 +29,8 @@ func TestFile(t *testing.T) {
 			"identifier": {Mode: fs.ModeDir | 0700},
 			"identifier/3376ALA7hIUm2LbzH2fDvRezgzod1eTK_G6XjyOgbM2u-6swvkFaF0BOwSl_juBi": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/vsAhtPNo4waRNOASwrQwcIPTqb3SBuJOXw2G4T1mNmVZM-wrQTRllmgXqcIIoRcX")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 	})
diff --git a/internal/pkg/ir.go b/internal/pkg/ir.go
index c93abc9e..72a2c90c 100644
--- a/internal/pkg/ir.go
+++ b/internal/pkg/ir.go
@@ -76,6 +76,9 @@ type IContext struct {
 	// Written to by various methods, should be zeroed after [Artifact.Params]
 	// returns and must not be exposed directly.
 	w io.Writer
+	// Optional [Artifact] to cureRes cache, replaces [IRKindIdent] with
+	// checksum values if non-nil.
+	inputs map[Artifact]cureRes
 }
 
 // irZero is a zero IR word.
@@ -163,7 +166,15 @@ func (i *IContext) WriteIdent(a Artifact) {
 	defer i.ic.putIdentBuf(buf)
 
 	IRKindIdent.encodeHeader(0).put(buf[:])
-	*(*ID)(buf[wordSize:]) = i.ic.Ident(a).Value()
+	if i.inputs != nil {
+		res, ok := i.inputs[a]
+		if !ok {
+			panic(InvalidLookupError(i.ic.Ident(a).Value()))
+		}
+		*(*ID)(buf[wordSize:]) = res.checksum.Value()
+	} else {
+		*(*ID)(buf[wordSize:]) = i.ic.Ident(a).Value()
+	}
 	i.mustWrite(buf[:])
 }
 
@@ -207,19 +218,44 @@ func (i *IContext) WriteString(s string) {
 // Encode writes a deterministic, efficient representation of a to w and returns
 // the first non-nil error encountered while writing to w.
 func (ic *irCache) Encode(w io.Writer, a Artifact) (err error) {
+	return ic.encode(w, a, nil)
+}
+
+// encode implements Encode but replaces identifiers with their cured checksums
+// for a non-nil ident. Caller must acquire Cache.identMu.
+func (ic *irCache) encode(
+	w io.Writer,
+	a Artifact,
+	inputs map[Artifact]cureRes,
+) (err error) {
 	deps := a.Dependencies()
 	idents := make([]*extIdent, len(deps))
-	for i, d := range deps {
-		dbuf, did := ic.unsafeIdent(d, true)
-		if dbuf == nil {
-			dbuf = ic.getIdentBuf()
+	if inputs == nil {
+		for i, d := range deps {
+			dbuf, did := ic.unsafeIdent(d, true)
+			if dbuf == nil {
+				dbuf = ic.getIdentBuf()
+				binary.LittleEndian.PutUint64(dbuf[:], uint64(d.Kind()))
+				*(*ID)(dbuf[wordSize:]) = did.Value()
+			} else {
+				ic.storeIdent(d, dbuf)
+			}
+			defer ic.putIdentBuf(dbuf)
+			idents[i] = dbuf
+		}
+	} else {
+		for i, d := range deps {
+			res, ok := inputs[d]
+			if !ok {
+				return InvalidLookupError(ic.Ident(d).Value())
+			}
+
+			dbuf := ic.getIdentBuf()
 			binary.LittleEndian.PutUint64(dbuf[:], uint64(d.Kind()))
-			*(*ID)(dbuf[wordSize:]) = did.Value()
-		} else {
-			ic.storeIdent(d, dbuf)
+			*(*ID)(dbuf[wordSize:]) = res.checksum.Value()
+			defer ic.putIdentBuf(dbuf)
+			idents[i] = dbuf
 		}
-		defer ic.putIdentBuf(dbuf)
-		idents[i] = dbuf
 	}
 	slices.SortFunc(idents, func(a, b *extIdent) int {
 		return bytes.Compare(a[:], b[:])
@@ -244,7 +280,7 @@ func (ic *irCache) Encode(w io.Writer, a Artifact) (err error) {
 	}
 
 	func() {
-		i := IContext{ic, w}
+		i := IContext{ic, w, inputs}
 
 		defer panicToError(&err)
 		defer func() { i.ic, i.w = nil, nil }()
diff --git a/internal/pkg/ir_test.go b/internal/pkg/ir_test.go
index 15c8b634..ad895471 100644
--- a/internal/pkg/ir_test.go
+++ b/internal/pkg/ir_test.go
@@ -110,6 +110,7 @@ func TestIRRoundtrip(t *testing.T) {
 				".":          {Mode: fs.ModeDir | 0700},
 				"checksum":   {Mode: fs.ModeDir | 0700},
 				"identifier": {Mode: fs.ModeDir | 0700},
+				"substitute": {Mode: fs.ModeDir | 0700},
 				"work":       {Mode: fs.ModeDir | 0700},
 			},
 		}
diff --git a/internal/pkg/net_test.go b/internal/pkg/net_test.go
index 4f9a072c..3728f8cb 100644
--- a/internal/pkg/net_test.go
+++ b/internal/pkg/net_test.go
@@ -90,6 +90,7 @@ func TestHTTPGet(t *testing.T) {
 			".":          {Mode: fs.ModeDir | 0700},
 			"checksum":   {Mode: fs.ModeDir | 0700},
 			"identifier": {Mode: fs.ModeDir | 0700},
+			"substitute": {Mode: fs.ModeDir | 0700},
 			"work":       {Mode: fs.ModeDir | 0700},
 		}},
 
@@ -159,6 +160,8 @@ func TestHTTPGet(t *testing.T) {
 			"identifier": {Mode: fs.ModeDir | 0700},
 			"identifier/oM-2pUlk-mOxK1t3aMWZer69UdOQlAXiAgMrpZ1476VoOqpYVP1aGFS9_HYy-D8_": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/fLYGIMHgN1louE-JzITJZJo2SDniPu-IHBXubtvQWFO-hXnDVKNuscV7-zlyr5fU")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 	})
diff --git a/internal/pkg/pkg.go b/internal/pkg/pkg.go
index 9e641df7..38bd550d 100644
--- a/internal/pkg/pkg.go
+++ b/internal/pkg/pkg.go
@@ -515,6 +515,9 @@ const (
 	// identification string set by a prior call to [SetExtension].
 	fileVariant = "variant"
 
+	// dirSubstitute is the directory name appended to Cache.base for linking
+	// artifacts named after their substitute identifier.
+	dirSubstitute = "substitute"
 	// dirIdentifier is the directory name appended to Cache.base for storing
 	// artifacts named after their [ID].
 	dirIdentifier = "identifier"
@@ -621,6 +624,9 @@ const (
 	// CSuppressInit arranges for verbose output of the container init to be
 	// suppressed regardless of [message.Msg] state.
 	CSuppressInit
+
+	// CIgnoreSubstitutes disables content-based dependency substitution.
+	CIgnoreSubstitutes
 )
 
 // toplevel holds [context.WithCancel] over caller-supplied context, where all
@@ -676,6 +682,11 @@ type Cache struct {
 	// Synchronises access to dirChecksum.
 	checksumMu sync.RWMutex
 
+	// Presence of an alternative in the cache. Keys are not valid identifiers
+	// and must not be used as such.
+	substitute map[unique.Handle[ID]]unique.Handle[Checksum]
+	// Synchronises access to substitute and corresponding filesystem entries.
+	substituteMu sync.RWMutex
 	// Identifier to content pair cache.
 	ident map[unique.Handle[ID]]unique.Handle[Checksum]
 	// Identifier to error pair for unrecoverably faulted [Artifact].
@@ -886,11 +897,14 @@ func (c *Cache) Scrub(checks int) error {
 		checks = runtime.NumCPU()
 	}
 
+	c.substituteMu.Lock()
+	defer c.substituteMu.Unlock()
 	c.identMu.Lock()
 	defer c.identMu.Unlock()
 	c.checksumMu.Lock()
 	defer c.checksumMu.Unlock()
 
+	c.substitute = make(map[unique.Handle[ID]]unique.Handle[Checksum])
 	c.ident = make(map[unique.Handle[ID]]unique.Handle[Checksum])
 	c.identErr = make(map[unique.Handle[ID]]error)
 	c.artifact.Clear()
@@ -998,47 +1012,52 @@ func (c *Cache) Scrub(checks int) error {
 		wg.Wait()
 	}
 
-	dir = c.base.Append(dirIdentifier)
-	if entries, readdirErr := os.ReadDir(dir.String()); readdirErr != nil {
-		addErr(dir, readdirErr)
-	} else {
-		wg.Add(len(entries))
-		for _, ent := range entries {
-			w <- checkEntry{ent, func(ent os.DirEntry, want *Checksum) bool {
-				got := p.Get().(*Checksum)
-				defer p.Put(got)
+	for _, suffix := range []string{
+		dirSubstitute,
+		dirIdentifier,
+	} {
+		dir = c.base.Append(suffix)
+		if entries, readdirErr := os.ReadDir(dir.String()); readdirErr != nil {
+			addErr(dir, readdirErr)
+		} else {
+			wg.Add(len(entries))
+			for _, ent := range entries {
+				w <- checkEntry{ent, func(ent os.DirEntry, want *Checksum) bool {
+					got := p.Get().(*Checksum)
+					defer p.Put(got)
 
-				pathname := dir.Append(ent.Name())
-				if linkname, err := os.Readlink(
-					pathname.String(),
-				); err != nil {
-					seMu.Lock()
-					se.Errs[pathname.Handle()] = append(se.Errs[pathname.Handle()], err)
-					se.DanglingIdentifiers = append(se.DanglingIdentifiers, *want)
-					seMu.Unlock()
-					return false
-				} else if err = Decode(got, filepath.Base(linkname)); err != nil {
-					seMu.Lock()
-					lnp := dir.Append(linkname)
-					se.Errs[lnp.Handle()] = append(se.Errs[lnp.Handle()], err)
-					se.DanglingIdentifiers = append(se.DanglingIdentifiers, *want)
-					seMu.Unlock()
-					return false
-				}
+					pathname := dir.Append(ent.Name())
+					if linkname, err := os.Readlink(
+						pathname.String(),
+					); err != nil {
+						seMu.Lock()
+						se.Errs[pathname.Handle()] = append(se.Errs[pathname.Handle()], err)
+						se.DanglingIdentifiers = append(se.DanglingIdentifiers, *want)
+						seMu.Unlock()
+						return false
+					} else if err = Decode(got, filepath.Base(linkname)); err != nil {
+						seMu.Lock()
+						lnp := dir.Append(linkname)
+						se.Errs[lnp.Handle()] = append(se.Errs[lnp.Handle()], err)
+						se.DanglingIdentifiers = append(se.DanglingIdentifiers, *want)
+						seMu.Unlock()
+						return false
+					}
 
-				if _, err := os.Stat(pathname.String()); err != nil {
-					if !errors.Is(err, os.ErrNotExist) {
-						addErr(pathname, err)
+					if _, err := os.Stat(pathname.String()); err != nil {
+						if !errors.Is(err, os.ErrNotExist) {
+							addErr(pathname, err)
+						}
+						seMu.Lock()
+						se.DanglingIdentifiers = append(se.DanglingIdentifiers, *want)
+						seMu.Unlock()
+						return false
 					}
-					seMu.Lock()
-					se.DanglingIdentifiers = append(se.DanglingIdentifiers, *want)
-					seMu.Unlock()
-					return false
-				}
-				return true
-			}}
+					return true
+				}}
+			}
+			wg.Wait()
 		}
-		wg.Wait()
 	}
 
 	dir = c.base.Append(dirStatus)
@@ -1186,6 +1205,52 @@ func (c *Cache) finaliseIdent(
 	close(done)
 }
 
+// zeroChecksum is a zero [Checksum] handle, used for comparison only.
+var zeroChecksum unique.Handle[Checksum]
+
+// loadSubstitute returns a checksum corresponding to a substitute identifier,
+// or zeroChecksum if an alternative is not available.
+func (c *Cache) loadSubstitute(
+	substitute unique.Handle[ID],
+) (unique.Handle[Checksum], error) {
+	c.substituteMu.RLock()
+	if checksum, ok := c.substitute[substitute]; ok {
+		c.substituteMu.RUnlock()
+		return checksum, nil
+	}
+
+	linkname, err := os.Readlink(c.base.Append(
+		dirSubstitute,
+		Encode(substitute.Value()),
+	).String())
+	c.substituteMu.RUnlock()
+
+	if err != nil {
+		if !errors.Is(err, os.ErrNotExist) {
+			return zeroChecksum, err
+		}
+
+		c.substituteMu.Lock()
+		c.substitute[substitute] = zeroChecksum
+		c.substituteMu.Unlock()
+		return zeroChecksum, nil
+	}
+
+	var checksum unique.Handle[Checksum]
+	buf := c.getIdentBuf()
+	err = Decode((*Checksum)(buf[:]), filepath.Base(linkname))
+	if err == nil {
+		checksum = unique.Make(Checksum(buf[:]))
+
+		c.substituteMu.Lock()
+		c.substitute[substitute] = checksum
+		c.substituteMu.Unlock()
+	}
+	c.putIdentBuf(buf)
+
+	return checksum, err
+}
+
 // Done returns a channel that is closed when the ongoing cure of an [Artifact]
 // referred to by the specified identifier completes. Done may return nil if
 // no ongoing cure of the specified identifier exists.
@@ -1654,16 +1719,44 @@ func (c *Cache) cure(a Artifact, curesExempt bool) (
 		return
 	}
 
-	var checksums string
+	var (
+		checksums   string
+		substitute  unique.Handle[ID]
+		alternative *check.Absolute
+	)
 	defer func() {
 		if err == nil && checksums != "" {
+			linkname := checksumLinknamePrefix + checksums
+
 			err = os.Symlink(
-				checksumLinknamePrefix+checksums,
+				linkname,
 				pathname.String(),
 			)
 			if err == nil {
 				err = zeroTimes(pathname.String())
 			}
+
+			if err == nil && alternative != nil {
+				c.substituteMu.Lock()
+				err = os.Symlink(
+					linkname,
+					alternative.String(),
+				)
+				if errors.Is(err, os.ErrExist) {
+					c.msg.Verbosef(
+						"creating alternative over %s for artifact %s",
+						Encode(substitute.Value()), ids,
+					)
+					err = nil
+				}
+				if err == nil {
+					err = zeroTimes(alternative.String())
+				}
+				if err == nil && checksum != zeroChecksum {
+					c.substitute[substitute] = checksum
+				}
+				c.substituteMu.Unlock()
+			}
 		}
 	}()
 
@@ -1860,6 +1953,38 @@ func (c *Cache) cure(a Artifact, curesExempt bool) (
 			f.deps[deps[i]] = p
 		}
 
+		sh := sha512.New384()
+		err = c.encode(sh, a, f.deps)
+		if err != nil {
+			return
+		}
+
+		buf := c.getIdentBuf()
+		sh.Sum(buf[wordSize:wordSize])
+		substitute = unique.Make(ID(buf[wordSize:]))
+		c.putIdentBuf(buf)
+		alternative = c.base.Append(
+			dirSubstitute,
+			Encode(substitute.Value()),
+		)
+
+		if c.flags&CIgnoreSubstitutes == 0 {
+			var substituteChecksum unique.Handle[Checksum]
+			substituteChecksum, err = c.loadSubstitute(substitute)
+			if err != nil {
+				return
+			}
+			if substituteChecksum != zeroChecksum {
+				checksum = substituteChecksum
+				checksums = Encode(checksum.Value())
+				checksumPathname = c.base.Append(
+					dirChecksum,
+					checksums,
+				)
+				return
+			}
+		}
+
 		defer f.destroy(&err)
 		if err = c.enterCure(a, curesExempt); err != nil {
 			return
@@ -2072,6 +2197,7 @@ func open(
 	}
 
 	for _, name := range []string{
+		dirSubstitute,
 		dirIdentifier,
 		dirChecksum,
 		dirStatus,
@@ -2097,6 +2223,7 @@ func open(
 
 		irCache: zeroIRCache(),
 
+		substitute:   make(map[unique.Handle[ID]]unique.Handle[Checksum]),
 		ident:        make(map[unique.Handle[ID]]unique.Handle[Checksum]),
 		identErr:     make(map[unique.Handle[ID]]error),
 		identPending: make(map[unique.Handle[ID]]*pendingCure),
diff --git a/internal/pkg/pkg_test.go b/internal/pkg/pkg_test.go
index 75f14a0e..060dea6d 100644
--- a/internal/pkg/pkg_test.go
+++ b/internal/pkg/pkg_test.go
@@ -392,6 +392,12 @@ type cacheTestCase struct {
 	want  expectsFS
 }
 
+const (
+	// checkDestroySubstitutes arranges for substitutes to be destroyed before
+	// measurement during checkWithCache.
+	checkDestroySubstitutes = 1 << (iota + 32)
+)
+
 // checkWithCache runs a slice of cacheTestCase.
 func checkWithCache(t *testing.T, testCases []cacheTestCase) {
 	t.Helper()
@@ -472,6 +478,16 @@ func checkWithCache(t *testing.T, testCases []cacheTestCase) {
 				}
 			}
 
+			// destroy non-deterministic substitutes
+			if tc.flags&checkDestroySubstitutes != 0 {
+				substitute := base.Append("substitute")
+				if err := os.RemoveAll(substitute.String()); err != nil {
+					t.Fatal(err)
+				} else if err = os.Mkdir(substitute.String(), 0700); err != nil {
+					t.Fatal(err)
+				}
+			}
+
 			// destroy non-deterministic status files
 			if err := os.RemoveAll(base.Append("status").String()); err != nil {
 				t.Fatal(err)
@@ -788,6 +804,8 @@ func TestCache(t *testing.T) {
 			"identifier/cafebabecafebabecafebabecafebabecafebabecafebabecafebabecafebabe": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/0bSFPu5Tnd-2Jj0Mv6co23PW2t3BmHc7eLFj9TgY3eIBg8zislo7xZYNBqovVLcq")},
 			"identifier/deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/0bSFPu5Tnd-2Jj0Mv6co23PW2t3BmHc7eLFj9TgY3eIBg8zislo7xZYNBqovVLcq")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
@@ -972,11 +990,81 @@ func TestCache(t *testing.T) {
 				}}, nil, nil, pkg.InvalidFileModeError(
 					fs.ModeSymlink | 0777,
 				)},
+
+				{"alternative", &stubArtifactF{
+					kind:   pkg.KindExec,
+					params: []byte("substitutable artifact"),
+					deps: []pkg.Artifact{newStubFile(
+						pkg.KindHTTPGet,
+						pkg.ID{0xff, 8},
+						nil,
+						[]byte("substitutable dependency"),
+						nil,
+					)},
+
+					cure: func(f *pkg.FContext) error {
+						return makeSample(&f.TContext)
+					},
+				}, base.Append(
+					"identifier",
+					"xMDWovje7OfyIaDy_2VnjpKxRqSOQ_LoeD946t-3WsS2V2SeMJ7nDGrNfpa4Pbc-",
+				), want, nil},
+
+				{"substitutable", &stubArtifactF{
+					kind:   pkg.KindExec,
+					params: []byte("substitutable artifact"),
+					deps: []pkg.Artifact{newStubFile(
+						pkg.KindHTTPGet,
+						pkg.ID{0xff, 10},
+						nil,
+						[]byte("substitutable dependency"),
+						nil,
+					)},
+
+					cure: func(f *pkg.FContext) error {
+						panic("substitution missed")
+					},
+				}, base.Append(
+					"identifier",
+					"k2ilgG5KQ9NXnMoT2oB6NdwOnSPRn_H24oXQc4l6qOYIxIG9XfuEczeyrR8UEv_f",
+				), want, nil},
 			})
+
+			if c0, err := unsafeOpen(
+				t.Context(),
+				message.New(nil),
+				0, 0, 0, base, false,
+			); err != nil {
+				t.Fatalf("open: error = %v", err)
+			} else {
+				t.Cleanup(c.Close)
+				cureMany(t, c0, []cureStep{
+					{"substitutable", &stubArtifactF{
+						kind:   pkg.KindExec,
+						params: []byte("substitutable artifact"),
+						deps: []pkg.Artifact{newStubFile(
+							pkg.KindHTTPGet,
+							pkg.ID{0xff, 0xff, 0xfd, 0xfd},
+							nil,
+							[]byte("substitutable dependency"),
+							nil,
+						)},
+
+						cure: func(f *pkg.FContext) error {
+							panic("substitution missed")
+						},
+					}, base.Append(
+						"identifier",
+						"_EmV5nsYZ2UWHgRmLDMU8i-rJWDx-kv5_1pFrzQI7vMMCM5mAXivO8UZtVfOqMR_",
+					), want, nil},
+				})
+
+			}
 		}, expectsFS{
 			".": {Mode: fs.ModeDir | 0700},
 
 			"checksum": {Mode: fs.ModeDir | 0700},
+			"checksum/7lfQ4QwSpV8nw7IDh0JiQ_jqUPrPv3_Vfie034RxsSy-cy4vO8DVvxgpx2LW08oO":                {Mode: 0400, Data: []byte("substitutable dependency")},
 			"checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b":                {Mode: fs.ModeDir | 0500},
 			"checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b/check":          {Mode: 0400, Data: []byte{0, 0}},
 			"checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b/lib":            {Mode: fs.ModeDir | 0700},
@@ -986,6 +1074,15 @@ func TestCache(t *testing.T) {
 			"identifier": {Mode: fs.ModeDir | 0700},
 			"identifier/HnySzeLQvSBZuTUcvfmLEX_OmH4yJWWH788NxuLuv7kVn8_uPM6Ks4rqFWM2NZJY": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b")},
 			"identifier/Zx5ZG9BAwegNT3zQwCySuI2ktCXxNgxirkGLFjW4FW06PtojYVaCdtEw8yuntPLa": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b")},
+			"identifier/_EmV5nsYZ2UWHgRmLDMU8i-rJWDx-kv5_1pFrzQI7vMMCM5mAXivO8UZtVfOqMR_": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b")},
+			"identifier/___9_QAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/7lfQ4QwSpV8nw7IDh0JiQ_jqUPrPv3_Vfie034RxsSy-cy4vO8DVvxgpx2LW08oO")},
+			"identifier/_wgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/7lfQ4QwSpV8nw7IDh0JiQ_jqUPrPv3_Vfie034RxsSy-cy4vO8DVvxgpx2LW08oO")},
+			"identifier/_woAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/7lfQ4QwSpV8nw7IDh0JiQ_jqUPrPv3_Vfie034RxsSy-cy4vO8DVvxgpx2LW08oO")},
+			"identifier/k2ilgG5KQ9NXnMoT2oB6NdwOnSPRn_H24oXQc4l6qOYIxIG9XfuEczeyrR8UEv_f": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b")},
+			"identifier/xMDWovje7OfyIaDy_2VnjpKxRqSOQ_LoeD946t-3WsS2V2SeMJ7nDGrNfpa4Pbc-": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b")},
+
+			"substitute": {Mode: fs.ModeDir | 0700},
+			"substitute/OyBGorh72Z9kVw35JUa8FbqDbpR4DqT-MX1jic0uKN5PdYmUBiAF38BRsIRnBigf": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/qRN6in76LndiiOZJheHkwyW8UT1N5-f-bXvHfDvwrMw2fSkOoZdh8pWE1qhLk65b")},
 
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
@@ -1061,6 +1158,7 @@ func TestCache(t *testing.T) {
 			".":          {Mode: fs.ModeDir | 0700},
 			"checksum":   {Mode: fs.ModeDir | 0700},
 			"identifier": {Mode: fs.ModeDir | 0700},
+			"substitute": {Mode: fs.ModeDir | 0700},
 			"work":       {Mode: fs.ModeDir | 0700},
 		}},
 
@@ -1119,6 +1217,7 @@ func TestCache(t *testing.T) {
 			".":          {Mode: fs.ModeDir | 0700},
 			"checksum":   {Mode: fs.ModeDir | 0700},
 			"identifier": {Mode: fs.ModeDir | 0700},
+			"substitute": {Mode: fs.ModeDir | 0700},
 			"work":       {Mode: fs.ModeDir | 0700},
 		}},
 
@@ -1180,6 +1279,8 @@ func TestCache(t *testing.T) {
 			"identifier/_wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/Aubi5EG4_Y8DhL9bQ3Q4HFBhLRF7X5gt9D3CNCQfT-TeBtlRXc7Zi_JYZEMoCC7M")},
 			"identifier/_wEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/Aubi5EG4_Y8DhL9bQ3Q4HFBhLRF7X5gt9D3CNCQfT-TeBtlRXc7Zi_JYZEMoCC7M")},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
 
@@ -1230,6 +1331,7 @@ func TestCache(t *testing.T) {
 			".":          {Mode: fs.ModeDir | 0700},
 			"checksum":   {Mode: fs.ModeDir | 0700},
 			"identifier": {Mode: fs.ModeDir | 0700},
+			"substitute": {Mode: fs.ModeDir | 0700},
 			"work":       {Mode: fs.ModeDir | 0700},
 		}},
 	}
@@ -1514,6 +1616,7 @@ func TestDependencyCureErrorEarly(t *testing.T) {
 			".":          {Mode: fs.ModeDir | 0700},
 			"checksum":   {Mode: fs.ModeDir | 0700},
 			"identifier": {Mode: fs.ModeDir | 0700},
+			"substitute": {Mode: fs.ModeDir | 0700},
 			"work":       {Mode: fs.ModeDir | 0700},
 		}},
 	})
diff --git a/internal/pkg/tar_test.go b/internal/pkg/tar_test.go
index a805e941..c7f8fca5 100644
--- a/internal/pkg/tar_test.go
+++ b/internal/pkg/tar_test.go
@@ -83,6 +83,8 @@ func TestTar(t *testing.T) {
 			"identifier/W5S65DEhawz_WKaok5NjUKLmnD9dNl5RPauNJjcOVcB3VM4eGhSaLGmXbL8vZpiw": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantEncode)},
 			"identifier/rg7F1D5hwv6o4xctjD5zDq4i5MD0mArTsUIWfhUbik8xC6Bsyt3mjXXOm3goojTz": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantEncode)},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},
@@ -105,6 +107,8 @@ func TestTar(t *testing.T) {
 			"identifier/W5S65DEhawz_WKaok5NjUKLmnD9dNl5RPauNJjcOVcB3VM4eGhSaLGmXbL8vZpiw": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantExpandEncode)},
 			"identifier/_v1blm2h-_KA-dVaawdpLas6MjHc6rbhhFS8JWwx8iJxZGUu8EBbRrhr5AaZ9PJL": {Mode: fs.ModeSymlink | 0777, Data: []byte("../checksum/" + wantExpandEncode)},
 
+			"substitute": {Mode: fs.ModeDir | 0700},
+
 			"temp": {Mode: fs.ModeDir | 0700},
 			"work": {Mode: fs.ModeDir | 0700},
 		}},