internal/pkg: optional dependency graph size limit

This provides a quick check against cyclic dependencies without hurting cure performance.

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

1 files changed, 56 insertions, 2 deletions

diff --git a/internal/pkg/pkg.go b/internal/pkg/pkg.go
index 3c9fbdbc..a9e9d18a 100644
--- a/internal/pkg/pkg.go
+++ b/internal/pkg/pkg.go
@@ -11,6 +11,7 @@ import (
 	"fmt"
 	"io"
 	"io/fs"
+	"iter"
 	"os"
 	"path"
 	"path/filepath"
@@ -217,6 +218,23 @@ type FloodArtifact interface {
 	Artifact
 }
 
+// Flood returns an iterator over the dependency tree of an [Artifact].
+func Flood(a Artifact) iter.Seq[Artifact] {
+	return func(yield func(Artifact) bool) {
+		for _, d := range a.Dependencies() {
+			if !yield(d) {
+				return
+			}
+
+			for d0 := range Flood(d) {
+				if !yield(d0) {
+					return
+				}
+			}
+		}
+	}
+}
+
 // TrivialArtifact refers to an [Artifact] that cures without requiring that
 // any other [Artifact] is cured before it. Its dependency tree is ignored after
 // computing its identifier.
@@ -405,9 +423,11 @@ type Cache struct {
 	// Directory where all [Cache] related files are placed.
 	base *check.Absolute
 
-	// Whether to validate [File.Data] for a [KnownChecksum] file. This
+	// Whether to validate [File.Cure] for a [KnownChecksum] file. This
 	// significantly reduces performance.
 	strict bool
+	// Maximum size of a dependency graph.
+	threshold uintptr
 
 	// Synchronises access to dirChecksum.
 	checksumMu sync.RWMutex
@@ -432,6 +452,12 @@ func (c *Cache) IsStrict() bool { return c.strict }
 // This method is not safe for concurrent use with any other method.
 func (c *Cache) SetStrict(strict bool) { c.strict = strict }
 
+// SetThreshold imposes a maximum size on the dependency graph, checked on every
+// call to Cure. The zero value disables this check entirely.
+//
+// This method is not safe for concurrent use with any other method.
+func (c *Cache) SetThreshold(threshold uintptr) { c.threshold = threshold }
+
 // A ChecksumMismatchError describes an [Artifact] with unexpected content.
 type ChecksumMismatchError struct {
 	// Actual and expected checksums.
@@ -894,6 +920,14 @@ func (e InvalidArtifactError) Error() string {
 	return "artifact " + Encode(e) + " cannot be cured"
 }
 
+// DependencyError refers to an artifact with a dependency tree larger than the
+// threshold specified by a previous call to [Cache.SetThreshold].
+type DependencyError struct{ A Artifact }
+
+func (e DependencyError) Error() string {
+	return "artifact has too many dependencies"
+}
+
 // Cure cures the [Artifact] and returns its pathname and [Checksum]. Direct
 // calls to Cure are not subject to the cures limit.
 func (c *Cache) Cure(a Artifact) (
@@ -901,6 +935,26 @@ func (c *Cache) Cure(a Artifact) (
 	checksum Checksum,
 	err error,
 ) {
+	if c.threshold > 0 {
+		var n uintptr
+		for range Flood(a) {
+			if n == c.threshold {
+				err = DependencyError{a}
+				return
+			}
+			n++
+		}
+	}
+
+	return c.cure(a)
+}
+
+// cure implements Cure without checking the full dependency graph.
+func (c *Cache) cure(a Artifact) (
+	pathname *check.Absolute,
+	checksum Checksum,
+	err error,
+) {
 	id := Ident(a)
 	ids := Encode(id)
 	pathname = c.base.Append(
@@ -1190,7 +1244,7 @@ func (c *Cache) Cure(a Artifact) (
 func (pending *pendingArtifactDep) cure(c *Cache) {
 	defer pending.Done()
 
-	pathname, _, err := c.Cure(pending.a)
+	pathname, _, err := c.cure(pending.a)
 	if err == nil {
 		*pending.resP = pathname
 		return