---
title: Deppy Phase 0
authors:
- "@oceanc80"
- "@perdasilva"
reviewers:
- "@joelanford"
- "@bparees"
- "@timflannagan"
- "@benluddy"
- "@dmesser"
approvers:
- "@joelanford"
- "@bparees"
creation-date: 2022-09-19
last-updated: 2022-09-19
tags: deppy
---

# Deppy Phase 0

## Summary

Deppy is envisioned to be a general purpose on/off-cluster dependency and constraint resolver. In this initial phase, we are targetting on-cluster resolution of `CatalogSource` content based on hard-coded constraints that enable the Platform Operators and OLM use-cases (i.e. package management). Users will be able to state which packages they want and inform the resolver of what is already installed on the cluster. Based on the content made available through the `CatalogSource`s, Deppy will calculate which bundles are required and where to find them, or an error as to why the system of constraints is not solvable.

## Motivation

The motivation for Deppy Phase 0 is to develop a minimum viable product (MVP) that satisfies the Platform Operators Phase 1 requirements. Through this exercise, we aim to define the interfaces between Deppy, catalog content (CatalogSources), and a client that defines constraints over the content and consumes Deppy's output. This will prove out the model of using an external dependency resolver as a core component of an on-cluster package manager, in this case Platform Operators, paving the way for OLM v1.x.

### Requirements

### User Stories

* As a user, I would like to tell Deppy the list of packages I want and have it tell me the bundles I need for those packages, including any dependencies. I should be able to input version constraints for those packages: always latest, latest within x-version, latest within y-version, latest within z-version, versions to ignore, and version ranges to consider. The solution will meet the constraints, or fail.
* As a user, I would like to tell Deppy the list of bundles that are installed on my cluster, such that I can know when there are upgrades and also to constrain the solution space based on the current state of the cluster.
* As a user, I would like to arbitrarily restrict the bundles that can be installed on my cluster based on property values exposed by those bundles (i.e. maxOpenShiftVersion or minKubeVersion) to ensure only software for which the cluster meets the requirements will be installed.

### Goals

* Define Deppy APIs for solution generation
* Define Deppy interfaces for content collection (bundles and constraints)
* Get experience with constraint authoring
* Meet the Platform Operators Phase 1 goal by resolving the bundles of the required platform operators
* Allow OLM users to have access to the resolver (through Deppy) to aid in "what-if" and debug analysis

### Non-Goals

* Be a generic sat solver for any kind of sat problem
* Allow users to define arbitrary/custom constraints
* Go beyond `CatalogSources` for content sourcing
* Have a completely decoupled architecture (i.e. for this iteration Deppy will be a monolith - but internal interfaces need to exist within the implementation)

## Terminology

* *constraint*: a high level constraint, e.g. bundle x has a dependency on bundles y and z
* *solver constraint*: a boolean expressions made of literals that represent entities in the solution space (e.g. bundles or other constraints). Solver constraints are generated from the (highlevel) constraints and fed to the solver

## Proposal

### Problem Statement

Given:
* a list of packages with optional version range and channel constraints
* a list of bundles (package versions) currently installed
* the list of all possible bundles
* the cluster OCP version
* the cluster Kubernetes version

Return a set of bundles that fulfill the given criteria:
* all bundles meet the cluster runtime constraints (OCP/K8s version)
* all bundles are at their highest possible version within the constraints set by the channel, update graph (given the currently installed version) and package version range constraints set by the user
* all bundles are either stated as required by the user, or have a dependency chain that starts from a bundle stated as required by the user (i.e. the minimum set of bundles needed to fullfil the user's intent)

Or, if no such set exists, an error that can help the user understand why.

### Architecture

Deppy will be a monolith in phase 0. Clients will communicate with Deppy through an `ActiveResolution` resource where they define constraints (e.g. package requirement, packages installed, etc.), trigger resolution by the solver, and collect results. The results will be a list of references to the resolved content. Deppy will convert `CatalogSource` bundles into entities. Entities are simple objects with IDs and properties. These entities, `ActiveResolution` constraints (AR constraints), and internally defined constraints, are used to produce the complete list of constraints fed to the solver.


Deppy will be composed of 4 major components: controller, solver, constraint builder, and `DeppySource`s:


#### Controller

The controller manages the state of `ActiveResolution` resources. It executes the main algorithm of producing solver constraints from constraint definitions and entities, triggers resolution, converts results to something consumable by users and writes results out to the particular `ActiveResolution` resource.

Though not the final definition for this resource, the following provides an example of what it might look like:

apiVersion: deppy.io/v1alpha1
kind: ActiveResolution
metadata:
  name: po-resolution
spec:
  # optionally restrict the solution space
  # to only entities coming from specific sources
  sources:
  - "redhat-operators"
  - "certified-operators"
  constraints:
  - required("odf-operator", ">= 3.1.0", "stable")
  - installed("devspaces", "1.0.2", "alpha")
  # or
  - required:
      name: "cluster-logging"
      versionRange: ">= 2.0.0 < 3.0.0"
      # optionally
      channel: "stable"
  - installed:
      name: "fuse-online"
      version: "5.26.7"
      channel: "fast"
status:
  conditions: # source conditions
  ...
  selection:
  - redhat-operators:odf-operator:3.5.7:stable
  - ...

#### Solver

In broad terms, the `Solver` can be visualised in the following function definition:

func Solve(constraints []Constraints) ([]EntityIds, error) {
    cnfFormula := convertToCNF(constraints)
    solution, err := solve(cnfFormula)
    if err != nil {
        return nil, err
    }
    
    // reduce solution to only required literals
    // resolving dependencies and atMost with literals with
    // the highest precedence
    // Note: superfluous literals can appear in the solution
    // so long as all defined constraints are met. For instance,
    // in the domain of package management, you might say to the 
    // resolver: I want package A. The resolver could answer: [package A, package B]
    // since it could constitute a valid solution to the boolean formula, even through
    // you never asked for it
    solution := reduce(solution)
    
    // convert literals back to Entity IDs
    // remove any entity that does not represent 
    // something that should be in the solution (e.g. bundles).
    // Note: some entities can be added only to further restrict 
    // the solution space, but shouldn't be included in the solution
    // themselves.
    selection := getSelection(solution)
    return selection, nil
}

It converts a set of constraints into a CNF formula, which is subsequently solved and further refined to ensure the solution respects the precedence inherent in the ordering of literals supplied to `dependency` and `atMost` constraints. It then translates the literals in the solution back to `Entity ID`s and returns this set to the user.

#### Deppy Source

A `DeppySource` is an adapter interface that can convert arbitrary domain-specific concepts into `Entity`s. For instance, translating `CatalogSource` bundles into `Entity`s with globally unique IDs and properties, which can later be used by a constraint definition for generating solver constraints.

type interface DeppySource {
    GetEntities() []Entity
}

The interface is rather simple, currently. However, it may grow to support other functions, e.g. search or content acquisition (i.e. getting the content associated with an id).

#### Entity

An `Entity` represents a literal and its relationship to other literals (constraints). It is composed of a globally unique identifier, and arbitrary properties. Given a set of all `Entity`s (universe) and a constraint definition, one or more solver constraints can be generated.

type Entity struct {
    Id string  // required
    Properties map[string]string  // optional
}

#### Constraint Builder

The constraint builder will contain a library of constraint generators that create the solver constraints over which the solver will operate. A constraint generator is an optionally parameterized function that, together with the universe of entities, produces one or more solver constraints. Here are a few (contrived) examples:

// Required generates the required solverConstraints
// to indicate that a bundle from packageName, within versionRange,
// from channel is required by the system
func Required(universe []Entity, packageName string, versionRange range, channel string) []SolverConstraint {
    subject := fmt.Sprintf("%s-required", packageName)
    ...
    return []SolverConstraint{Mandatory(subject), DependsOn(subject, dependencyIds...)}
}

// BundleDependencyConstraints returns a list of solver constraints
// that represent the dependency constraints for each of the bundles
// in the universe of bundles
func BundleDependencyConstraints(universe []Entity) []SolverConstraint {
    solverConstraints := make([]SolverConstraint, 0)
    for _, entity := range universe {
        pkgDeps = collectPKGDeps(universe, entity)
        gvkDeps = collectGVKDeps(universe, entity)
        solverConstraint = append(solverConstraints, pkgDeps..., gvkDeps...)
    }
    return solverConstraints
}

// GVKUniqueness returns a list of solver constraints
// that restrict the solution by at most 1 bundle / gvk
func GVKUniqueness(universe[] Entity) []SolverConstraint {
    gvkToIds map[string][]EntityId := groupByGVK(universe)
    solverConstraints := make([]SolverConstraint, 0)
    for gvk, ids := range gvkToIds {
        solverConstraints = append(solverConstraints, AtMost(gvk, 1, ids...))
    }
    return solverConstraints
}

The constraints specified in the `ActiveResolution` resource will relate to the library of constraint generators hard-coded in the `Constraint Builder` component.

#### Required Constraints

In this section we attempt to formally define the constraints that will be modeled in this iteration of Deppy, reminding the reader that they will be hard-coded for this phase. In subsequent phases we aim to create a `Constraints` API that afford users the ability to define their own constraints.

The Universe $U$ of entities $e$ is defined by all entities in the union of all sets of entities provided by the deppy sources $S_i$:

$$
U = \{e : e \in \bigcup\limits_{i}^{n} S_i \}
$$

##### GVK uniqueness: At most 1 bundle / gvk

$$
G = \bigwedge\limits_{}^{gvk} AtMost(1, \{ e : e \in U \land e.gvk = gvk\})
$$

##### Package uniqueness: At most 1 bundle / package

$$
P = \bigwedge\limits_{}^{pkg} AtMost(1, \{ e : e \in U \land e.packageName = pkg\})
$$

##### Runtime Constraints: Only bundles that respect runtime constraints should be considered

A conflict constraint between two literals $a$ and $b$ is expressed as: $\neg a \lor \neg b$

$$
R(v) = \bigwedge\limits_{e \in U \land e.maxOCPVersion < v}^{e} \neg c \lor \neg e.Id,
$$

where $v$ is the OCP version and $c$ is the literal representing the *ocpMaxVersion* constraint

##### Dependency:

In boolean terms, a dependency is modeled as an implication: $a \implies b$, which translates to the boolean formula $b \lor \neg a$

##### Package Dependency:

$$
D(p,v,c,d) = \bigvee\limits_{e \in U \land e.version \in v \land e.pkg = p \land e.channel = c}^{e} e.Id \lor \neg d,
$$
where $p$ is the package name, $v$ is the package version range, $c$ is the channel, and $d$ is the literal that represents the bundle that has the dependency

The expression expands to:

$$
D(p,v,c,d) = e_1 \lor \neg d \lor e_2 \lor \neg d \lor ... \lor e_n \lor \neg d
\\ = e_1 \lor e_2 \lor ... \lor e_n \lor \neg d \lor ... \lor \neg d
$$

Which can be reduced to:

$$
= e_1 \lor e_2 \lor ... \lor e_n \lor \neg d
$$

##### GVK Dependency:

$$
G(g, d) = \bigvee\limits_{e \in U \land g \in e.gvk}^{e} e.Id \lor \neg d,
$$

Where $g$ is the required gvk and $d$ is the literal that represents the bundle that has the dependency

Note: The order in which the arguments are given to the constraint defines a precedence between the dependencies (earlier in the order -> higher precedence).

##### Upgrade Constraints:

$$
P(p,v,c,i) = \bigvee\limits_{e \in U \land e.pkgName = p \land e.UpgradableFrom(v,c)}^{e} e.Id \lor \neg i,
$$

where $i$ is the literal that represents package $p$ at version $v$ from channel $c$ is installed.

For each bundle in a channel, a dependency constraint is created between the bundle and every other bundle reacheable that it can reach via an upgrade edge. The particular constraint needs to be activated when the bundle is installed. This will narrow the choice of bundles for the package to just those to which it can be upgraded.

### Open Questions
- Is the ActiveResolution a cluster singleton or can there be multiple copies on the cluster?
- Are there alternatives to the name ActiveResolution?

### Answered Questions

### Implementation Details

### Workflow Description

### API Extensions

### Risks and Mitigations

#### Risks

#### Mitigations

### Drawbacks

## Appendix I. Background

While it is a high level goal to keep Deppy as generic as possible, for this phase, the focus will be on dependency management, particularly, against the package model proposed by OLM:

* A package has one or more channels
* A channel has one or more bundles (a version of the package)
* A channel specifies an update graph for the bundles it contains. This is done with a combination of [three methods](https://olm.operatorframework.io/docs/concepts/olm-architecture/operator-catalog/creating-an-update-graph/):
* **replaces**: which version the bundles replaces
* **skips**: intermediate versions that can be skipped
* **skipsRange**: a semver version range of intermediate versions that can be skipped
* A bundle can declare dependencies on:
* Other packages in a version range
* Packages that provide a certain GroupVersionKind (GVK)
* A bundle can declare arbitrary (key/value) properties

### Solver

The solver takes as input a set of constraints over boolean *literals*. The constraints are reduced to a conjunctive normal form (CNF) boolean statement, which the solver can use to deduce whether there exists a model (a true or false assignment to each of the literals) that can satisfy the boolean statement (i.e. in which the statement will evaluate to true), and what such a model is. The solver can also elucidate _why_, there is no such model.

The constraints are initially modeled as a boolean circuit, which is then converted to CNF. The solution, if any, comes by sequentially assuming the constraints hold. For instance, given literals A and B and a constraint that they both must be true (A *AND* B), the *AND* constraint will be converted to its CNF form: (~A or ~B or O) and (A or ~O) and (B or ~O), where *O* is the literal representing the output of A *AND* B, and ~ is the logical *not*. If we instruct the solver to assume the constraint holds, that is, we assume O = true, the only viable solution would be A = true, B = true.

#### Constraint Types

| Constraint | CNF | Meaning
| ------------------ | -------------------- | --------
| Mandatory(A) | $A$ | A = true in solution
| Prohibited(A) | $\neg A$ | A = false in solution
| Conflicts(A,B) | $\neg A \lor \neg B$ | if either A or B is in the solution, the other cannot also be
| DependsOn(A, B..n) | $B \lor C \lor ... \lor \neg A$ | either A is false, or at least one of B..n is true
| AtMost(k, A...n) | see [this](https://www.it.uu.se/research/group/astra/ModRef10/papers/Alan%20M.%20Frisch%20and%20Paul%20A.%20Giannoros.%20SAT%20Encodings%20of%20the%20At-Most-k%20Constraint%20-%20ModRef%202010.pdf) | at most 'k' of A..n must be true in the solution
| And(C1, C2) | see [appendix](#Appendix-I-Formulas-for-Simple-Gates) | both constraints C1 and C2 must be true
| Or(C1, C2) | see [appendix](#Appendix-I-Formulas-for-Simple-Gates) | either constraints C1, C2 or both must be true
| Not(C1) | see [appendix](#Appendix-II-Formulas-for-Simple-Gates) | constraint C1 must be false

#### Dependencies

In OLM, dependencies can be declared in two forms:
* Package + Version Range: the dependency can be met by any bundle of the given package that is in the version range
* GVK: the dependency can be met by any bundle that provides the necessary GVK

This means that dependency corresponds to an individual `DependsOn` constraint, rather than a single constraint over all possible bundles that can fulfill any of the dependencies. The package and gvk uniqueness constraints then force the solver to only pick a single bundle to fulfill a given dependency.

#### Precedence

The solver will attempt to resolve `DependsOn` and `AtMost` constraints by preferring solutions that include literals that come earlier in the order given in the constraint definition. For instance, given `DependesOn(A, D1, D2, D3)`, and assuming only one of those dependencies can be picked, the solver will choose solution `{A, D1}` for as long as `D1` can be selected, that is, when `D1` isn't "blocked" by another constraint. If it cannot pick `D1`, then it will try `D2`, then finally `D3`. Thus, when defining `DependsOn` and `AtMost` constraints, it is important to decide whether there is any precendence in the order in which the dependency is fulfilled, e.g. a preference for the highest allowable version of a package.

#### Error Messages

If the solver determines there is no existing solution to the boolean statement, i.e. there are one or more constraints that cannot be met, it can be queried to determine the offending constraints. This means there is a direct relationship between the choice of how to model a particular constraint and the types (and usefulness) of error messages that will be returned to the user.

## Appendix II. Formulas for Simple Gates

| Gate | CNF
| -------- | --------
| $A \space AND \space B = O$ | $(\neg A \lor \neg B \lor O) \land (A \lor \neg O) \land (B \lor \neg O)$
| $A \space OR \space B = O$ | $(A \lor B \lor \neg O) \land (\neg A \lor O) \land (\neg B \lor O)$
| $NOT \space A = O$ | $(A \lor O) \land (\neg A \lor \neg O)$

## Appendix III. Deppy as a Framework

An alternative way to frame deppy would be as a framework, with other on/off-cluster components being built as implementations of the interfaces made available through this framework. For instance, in the [diagram](https://lucid.app/lucidchart/2c1f674d-db4e-494e-a76f-ab358b439639/edit?viewport_loc=-877%2C-31%2C3622%2C1250%2C0_0&invitationId=inv_9864da53-7f2e-445f-87cd-55dcfc72f467) below:


we have the following components:

#### Deppy

Deppy is a set of programmatic APIs:
- `Solver API`: interacts with the other components and the solver to produce entity selections and acquire the underlying content of those entities, e.g. from entities to bundles or CSVs
- `EntitySource API`: gives an interface for querying entities provided by different sources and acquiring their content (if any)
- `Constraint API`: provides an API for generating solver constraints based on the results of the queries provided by the `EntitySource` API
- `Solver`: which collects all of the constraints and provides a selection of entities that respect the constraints (or failure). Note: we could factor out our solver into a `DeppySolver` project and have the solver itself be swappable

##### Solver API

package deppy
type DeppySolver interface {
    // sync/blocking method
    Solve() (Solution, error)
    
    // the following methods allow users to 
    // mutate the configuration of the underlying solver
    // e.g. select particular entity sources, add additional
    // entity sources or constraint generators
    
    // reduces the scope of the problem
    // to entity sources that match a specific query
    WithEntitySourceSelector(query EntitySourceSelector) DeppySolver
    
    // Note: alternatively we could use the concept of 
    // selectors for constraint generators as well
    
    // additional entity sources to consider
    WithEntitySources(entitySources ...EntitySource) DeppySolver
    
    // additional constraint generators to consider
    WithConstraintGenerators(constraintGenerators ...ConstraintGenerator) DeppySolver
    
    // possible future methods/behaviours
    // async/non-blocking/reactive method
    // alternatively, the process could listen for
    // entity source / constraint generator state changes
    // and then proactively call Solver()
    // though we should still have the ability to hook into 
    // solver events - then watcher, async patterns could just
    // go around the solver
    SolveAsync(fn func(Solution, error))
}

type Options struct {
    entitySources []EntitySource
    constraintGenerators []ConstraintGenerator
    
    // the solver has life-cycle hooks
    // e.g. pre-resolution, post-resolution
    // Plug-ins can bind to those hooks to provide
    // additional functionality, e.g. metrics, 
    // keeping resolution history, tracers, etc.
    plugIns []DeppySolverLifecyclePlugIn
}

func NewDeppySolver(options Options) (DeppySolver, error) {}

##### Usage

Deppy would therefore be a library where components in need of a solver can build their own by composing `EntitySource`s and `Constraint Generators`. These can either be homegrown or use specific implementations as libraries.

The `Solver API` could be designed to be proactive as well as reactive. E.g. if there is a change in the constraints or the entity sources the new solution could either be provided automatically via listener or deliberately via API call.

#### DeppySource API

The `DeppySource API` is a library that is an implementation of an on-cluster `EntitySource`. It provides users with a server-side API as well as a client. The server-side API is an adapter that converts arbitrary data into `Entity`s and provides a way to get all, query, and watch for changes. One implementation of this API will be for OLM `CatalogSource`s.

Note: this is where we can decide whether the entities should be replicated and queries locally or the queries should be executed server-side. For simplicity we can start locally and when/if we start to see bottlenecks, we can start to shift the query computation off the client and onto the server.

#### Constraint API Implementations

The constraint API can be used to define concrete implementation that can be used as plug-ins to the solver. For instance:
- `Runtime Constraints`: a constraint generator that is able to query the cluster and provide the solver with runtime constraints, such as, `maxOpenShiftVersion`, or `minKubeVersion`, and others.
- `Declarative Constraints`: a constraint generator that is defined via kubernetes resources
- `Domain Constraints`: provides domain specific constraints (hard-coded). Could also be a library of constraint generators, e.g. gvkUniqueness, packageUniqueness, packageRequired, etc.

### Projects up/down-stream

| Project | Description | Stream |
| -------- | ----------- | -------- |
| Deppy | Framework for creating solvers | upstream |
| DeppySolver | Solver library | upstream |
| DeppySource | Framework for on-cluster entity sources | upstream |
| CSDS | CatalogSource DeppySource implementation | ? |
| RuntimeConstraints | Deppy plug-in for rt constraints | downstream |
| Declarative Constraints | K8S API extension and Deppy constraint plug-in | ? |
| OLM Constraints | Deppy plug-in with OLM constraint generators | upstream |

### Phase Zero Stategy

For Phase 0 we only care about: the deppy framework, the solver, runtime constraints, DeppySource and CatalogSourceDeppySource. PO would use the `Solver API` to create a solver with hard-coded constraint generators (e.g. `OLM constraints`) and `CatalogSourceDeppySource`s to resolve its content. We can build out these components off the same code-base (initially), then in subsequent phases, as the components reach a certain level of maturity, split them out to their own repositories and take a dependency on them.

## Appendix IV. Deppy as a Framework (Reloaded)

Building upon the [Deppy as a Framework](#Appendix-III-Deppy-as-a-Framework) idea, I've been experimenting with golang generics to try to solve the problem of the `EntitySource` interface. An `EntitySource` should provide a set of methods to query a source for entities. It may be difficult to find a "one-size-fits-all" set of methods that translate easily into the different possibilities of backing storage that could be used, e.g. SQL, in-memory, or graph databases, among others. Below, is a description of the Deppy Framework using generics. It is followed by a concrete example of its implementation in an OLM like application. In this iteration, we have renamed the old `ConstraintGenerator` to a `VariableSource`.

### Generics Infused Deppy API

type EntityID string
type EntitySourceID string

type Entity interface {
	ID() EntityID
}

type EntitySource[E Entity] interface {
	ID() EntitySourceID
	Get(context.Context, EntityID) (E, error)
}

type VariableSource[E Entity, V sat.Variable, Q EntitySource[E]] interface {
	GetVariables(ctx context.Context, source Q) ([]V, error)
}

type Solution []sat.Variable

type Solver[V sat.Variable] interface {
	Solve(ctx context.Context) (Solution, error)
}

### Concrete Implementation (OLMCLI)

OLMCLI is a command-line interface for OLM. It allows users to add/remove catalogs, search for packages and bundles, and install catalog operators to a kubernetes cluster. It implements the Deppy API in order to facilitate resolution of the required bundles during an install. [BoltDB](https://github.com/boltdb/bolt) is used as the backing store for the repository/package/bundle information. A `PackageDatabase` is used for interaction with the backing store. Below is the `PackageDatabase` interface:

type PackageDatabase interface {
	HasRepository(ctx context.Context, repo string) (bool, error)
	ListRepositories(ctx context.Context) ([]CachedRepository, error)
	ListPackages(ctx context.Context) ([]CachedPackage, error)
	ListBundles(ctx context.Context) ([]CachedBundle, error)
	ListBundlesForGVK(ctx context.Context, group string, version string, kind string) ([]CachedBundle, error)
	ListGVKs(ctx context.Context) (map[string][]CachedBundle, error)
	SearchPackages(ctx context.Context, searchTerm string) ([]CachedPackage, error)
	SearchBundles(ctx context.Context, searchTerm string) ([]CachedBundle, error)
	CacheRepository(ctx context.Context, repository repository.Repository) error
	RemoveRepository(ctx context.Context, repoName string) error
	GetPackage(ctx context.Context, packageID string) (*CachedPackage, error)
	GetBundle(ctx context.Context, bundleID string) (*CachedBundle, error)
	IterateBundles(ctx context.Context, fn func(bundle *CachedBundle) error) error
	GetBundlesForPackage(ctx context.Context, packageName string, options ...PackageSearchOption) ([]CachedBundle, error)
	Close() error
}

A `CachedBundle` represents a bundle from a package in a repository. From the resolver, we'd like the list of bundles we must install given the required packages and associated version ranges and channels. `CachedBundle` is defined as follows:

type CachedBundle struct {
	*api.Bundle         // from operator-repostiory
	BundleID            string             `json:"id"`
	Repository          string             `json:"repository"`
	DefaultChannelName  string             `json:"defaultChannelName"`
	PackageDependencies []property.Package `json:"packageDependencies"`
}

// Makes CachedBundle usable as an Entity in the Deppy Framework
func (c CachedBundle) ID() v2.EntityID {
	return v2.EntityID(c.BundleID)
}

The `EntitySource` can then be defined as a wrapper around the `PackageDatabase` and to operator over `CachedBundle`s as the `Entity`s:

var _ deppy.EntitySource[store.CachedBundle] = &OLMEntitySource{}

type OLMEntitySource struct {
	store.PackageDatabase
}

func (s *OLMEntitySource) ID() v2.EntitySourceID {
	return "packageManager"
}

func (s *OLMEntitySource) Get(ctx context.Context, id v2.EntityID) (*store.CachedBundle, error) {
	bundle, err := s.GetBundle(ctx, string(id))
	if err != nil {
		return nil, err
	}
	return bundle, nil
}

Several `VariableSource`s can be created to convert the `CachedBundle`s/`Entity`s into `Variables`. For instance, the following `VariableSource` generates variables for requried packages:

var _ v2.VariableSource[store.CachedBundle, OLMVariable, *OLMEntitySource] = &RequiredPackage{}

type RequiredPackage struct {
	repositoryName string
	packageName    string
	channelName    string
	versionRange   string
	searchOptions  []store.PackageSearchOption
}

func NewRequiredPackage(packageName string, options ...Option) (*RequiredPackage, error) {
	requiredPackage := &RequiredPackage{
		repositoryName: packageName,
		packageName:    anyValue,
		channelName:    anyValue,
		versionRange:   anyValue,
	}
	for _, opt := range options {
		if err := opt(requiredPackage); err != nil {
			return nil, err
		}
	}
	return requiredPackage, nil
}

func (r *RequiredPackage) GetVariables(ctx context.Context, source *OLMEntitySource) ([]OLMVariable, error) {
	bundles, err := source.GetBundlesForPackage(ctx, r.packageName, r.searchOptions...)
	if err != nil {
		return nil, err
	}
	Sort(bundles, ByChannelAndVersion)
	return []OLMVariable{NewRequiredPackageVariable(r.getVariableID(), bundles...)}, nil
}

func (r *RequiredPackage) getVariableID() sat.Identifier {
	return sat.Identifier(fmt.Sprintf("required package %s from repository %s, channel %s, in semver range %s", r.packageName, r.repositoryName, r.channelName, r.versionRange))
}

The `UniquenessVariableSource` generates variables to express GVK and Package uniqueness constraints:

type uniqueness struct{}

func NewUniquenessVariableSource() v2.VariableSource[*store.CachedBundle, OLMVariable, IterableOLMEntitySource] {
	return &uniqueness{}
}

func (r *uniqueness) GetVariables(ctx context.Context, source IterableOLMEntitySource) ([]OLMVariable, error) {
	pkgMap := map[string][]store.CachedBundle{}
	gvkMap := map[string][]store.CachedBundle{}

	err := source.Iterate(ctx, func(entity *store.CachedBundle) error {
		pkgMap[entity.PackageName] = append(pkgMap[entity.PackageName], *entity)
		for _, gvk := range entity.ProvidedApis {
			gvkMap[gvk.String()] = append(gvkMap[gvk.String()], *entity)
		}
		return nil
	})
	if err != nil {
		return nil, err
	}

	var uniquenessVariables = make([]OLMVariable, 0, len(pkgMap)+len(gvkMap))
	for pkgName, entities := range pkgMap {
		Sort(entities, ByChannelAndVersion)
		uniquenessVariables = append(uniquenessVariables, NewUniquenessVariable(pkgUniquenessVariableID(pkgName), entities...))
	}
	for gvk, entities := range gvkMap {
		Sort(entities, ByChannelAndVersion)
		uniquenessVariables = append(uniquenessVariables, NewUniquenessVariable(gvkUniquenessVariableID(gvk), entities...))
	}
	return uniquenessVariables, nil
}

func pkgUniquenessVariableID(packageName string) sat.Identifier {
	return sat.Identifier(fmt.Sprintf("package (%s) uniqueness", packageName))
}

func gvkUniquenessVariableID(gvk string) sat.Identifier {
	return sat.Identifier(fmt.Sprintf("gvk (%s) uniqueness", gvk))
}

The `BundleVariableSource` produces bundle variables for all bundles and their dependencies:

var _ v2.VariableSource[*store.CachedBundle, OLMVariable, *OLMEntitySource] = &DependenciesVariableSource{}

type DependenciesVariableSource struct {
	queue []store.CachedBundle
}

func NewBundleVariableSource(seedEntities ...store.CachedBundle) *DependenciesVariableSource {
	return &DependenciesVariableSource{
		queue: seedEntities,
	}
}

func (r *DependenciesVariableSource) GetVariables(ctx context.Context, source *OLMEntitySource) ([]OLMVariable, error) {
	processedEntities := map[v2.EntityID]struct{}{}
	var variables []OLMVariable

	for len(r.queue) > 0 {
		var head store.CachedBundle
		head, r.queue = r.queue[0], r.queue[1:]
		if _, ok := processedEntities[head.ID()]; ok {
			continue
		}
		processedEntities[head.ID()] = struct{}{}

		// extract package and gvk dependencies
		var dependencyEntities []store.CachedBundle
		for _, packageDependency := range head.PackageDependencies {
			bundles, err := source.GetBundlesForPackage(ctx, packageDependency.PackageName, store.InVersionRange(semver.MustParseRange(packageDependency.Version)))
			if err != nil {
				return nil, err
			}
			dependencyEntities = append(dependencyEntities, bundles...)
		}

		for _, gvkDependency := range head.RequiredApis {
			bundles, err := source.ListBundlesForGVK(ctx, gvkDependency.GetGroup(), gvkDependency.GetVersion(), gvkDependency.GetKind())
			if err != nil {
				return nil, err
			}
			dependencyEntities = append(dependencyEntities, bundles...)
		}
		Sort(dependencyEntities, ByChannelAndVersion)
		r.queue = append(r.queue, dependencyEntities...)
		variables = append(variables, NewBundleVariable(&head, dependencyEntities...))
	}
	return variables, nil
}

The `OLMVariableSource` returns all required variables for resolution given required packages:

var _ v2.VariableSource[*store.CachedBundle, OLMVariable, *OLMEntitySource] = &olmVariableSource{}

type olmVariableSource struct {
	requiredPackages []*RequiredPackage
	logger           *logrus.Logger
}

func OLMVariableSource(requiredPackages []*RequiredPackage, logger *logrus.Logger) (v2.VariableSource[*store.CachedBundle, OLMVariable, *OLMEntitySource], error) {
	olmVariableSource := &olmVariableSource{
		requiredPackages: requiredPackages,
		logger:           logger,
	}
	return olmVariableSource, nil
}

func (r *olmVariableSource) GetVariables(ctx context.Context, source *OLMEntitySource) ([]OLMVariable, error) {
	var variables []OLMVariable
	entitySet := OLMEntitySet{}

	var start time.Time
	var elapsed time.Duration

	// collect all required package variables
	r.logger.Info("Collecting required package variables")
	start = time.Now()
	for _, reqPkg := range r.requiredPackages {
		reqPkgVars, err := reqPkg.GetVariables(ctx, source)
		if err != nil {
			return nil, err
		}
		variables = append(variables, reqPkgVars...)
		for _, reqPkgVar := range reqPkgVars {
			for _, entity := range reqPkgVar.OrderedEntities() {
				if _, ok := entitySet[entity.ID()]; !ok {
					entitySet[entity.ID()] = entity
				}
			}
		}
	}
	elapsed = time.Since(start)
	r.logger.Infof("took %s", elapsed)

	// collect bundles and dependencies
	r.logger.Info("Collecting bundles and dependencies")
	start = time.Now()
	entities := make([]store.CachedBundle, 0, len(entitySet))
	for _, entity := range entitySet {
		entities = append(entities, entity)
	}
	bundleVariableSource := NewBundleVariableSource(entities...)
	bundleVariables, err := bundleVariableSource.GetVariables(ctx, source)
	if err != nil {
		return nil, err
	}
	variables = append(variables, bundleVariables...)
	for _, v := range bundleVariables {
		for _, entity := range v.OrderedEntities() {
			if _, ok := entitySet[entity.ID()]; !ok {
				entitySet[entity.ID()] = entity
			}
		}
	}
	elapsed = time.Since(start)
	r.logger.Infof("took %s", elapsed)

	// collect uniqueness variables
	r.logger.Info("Applying global constraints")
	start = time.Now()
	uniquenessVariableSource := NewUniquenessVariableSource()
	uniquenessVariables, err := uniquenessVariableSource.GetVariables(ctx, NewIterableEntitySource("packageSet", entitySet))
	if err != nil {
		return nil, err
	}
	variables = append(variables, uniquenessVariables...)
	elapsed = time.Since(start)
	r.logger.Infof("took %s", elapsed)
	return variables, nil
}

Finally, the `OLMSolver` puts it all together to produce a list of installables:

func (s *OLMSolver) Solve(ctx context.Context, requiredPackages ...*RequiredPackage) ([]Installable, error) {
	variableSource, err := OLMVariableSource(requiredPackages, s.logger)
	if err != nil {
		return nil, err
	}
	deppySolver, err := v2.NewDeppySolver[*store.CachedBundle, OLMVariable, *OLMEntitySource](s.olmEntitySource, variableSource)
	if err != nil {
		return nil, err
	}
	solution, err := deppySolver.Solve(ctx)
	if err != nil {
		return nil, err
	}

	selectedVariables := map[string]*BundleVariable{}
	for _, variable := range solution {
		switch v := variable.(type) {
		case *BundleVariable:
			selectedVariables[v.BundleID] = v
		}
	}
	var installables []Installable
	for _, variable := range selectedVariables {
		dependencies := map[string]store.CachedBundle{}
		for _, dependency := range variable.OrderedEntities() {
			if _, ok := selectedVariables[dependency.BundleID]; ok {
				dependencies[dependency.BundleID] = dependency
			}
		}
		installables = append(installables, Installable{
			CachedBundle: *variable.CachedBundle,
			Dependencies: dependencies,
		})
	}
	Sort(installables, byTopology)
	return installables, nil
}