nip/docs/dependency-resolution.md

Dependency Resolution in NIP

Audience: Package maintainers migrating packages from other distributions
Purpose: Understand how NIP resolves dependencies and handles conflicts
Last Updated: November 23, 2025

---

Overview

NIP uses a PubGrub-style CDCL (Conflict-Driven Clause Learning) solver for dependency resolution. This is the same algorithm family used by Dart's pub and Rust's Cargo, adapted for NexusOS's unique requirements including variant unification and multi-source package management.

Why this matters for package maintainers:

• Understand why certain dependency combinations fail
• Learn how to write portable package definitions
• Avoid common pitfalls when migrating from Arch, Gentoo, Nix, or PKGSRC
• Debug dependency conflicts effectively

---

Key Concepts

1. Package Terms

A package term is the fundamental unit in dependency resolution:

PackageTerm = Package Name + Version + Variant Profile + Source

Example:

nginx-1.24.0-{+ssl,+http2,libc=musl}-pacman

This represents:

• Package: nginx
• Version: 1.24.0
• Variants: SSL enabled, HTTP/2 enabled, musl libc
• Source: Grafted from Arch Linux (pacman)

2. Variant Profiles

Unlike traditional package managers, NIP tracks build variants as part of package identity. This is crucial when migrating packages:

Gentoo USE flags → NIP variants:

# Gentoo
USE="ssl http2 -ipv6" emerge nginx

# NIP equivalent
nip install nginx +ssl +http2 -ipv6

Nix package variants → NIP variants:

# Nix
nginx.override { openssl = openssl_3; http2Support = true; }

# NIP equivalent
nip install nginx +ssl +http2 --with-openssl=3

3. Dependency Graph

NIP builds a complete dependency graph before attempting resolution:

nginx-1.24.0
├── openssl-3.0.0 (+ssl)
│   └── zlib-1.2.13
├── pcre-8.45
└── zlib-1.2.13

Key insight: The graph is built BEFORE solving, allowing NIP to detect circular dependencies early.

---

The Resolution Pipeline

Phase 1: Graph Construction

What happens:

1. Parse package manifest (from .npk, PKGBUILD, ebuild, or Nix expression)
2. Recursively fetch dependencies
3. Build complete dependency graph
4. Detect circular dependencies

For package maintainers:

• Ensure your package manifest lists ALL dependencies
• Include build-time AND runtime dependencies
• Specify version constraints clearly

Example manifest (KDL format):

package "nginx" {
  version "1.24.0"
  
  dependencies {
    openssl {
      version ">=3.0.0"
      variants "+ssl"
      required true
    }
    pcre {
      version ">=8.0"
      required true
    }
    zlib {
      version ">=1.2.0"
      required true
    }
  }
}

Phase 2: Variant Unification

What happens: NIP attempts to merge variant requirements from multiple packages:

Package A requires: openssl +ssl +ipv6
Package B requires: openssl +ssl +http2
Result: openssl +ssl +ipv6 +http2  ✅ Success

Conflict example:

Package A requires: openssl libc=musl
Package B requires: openssl libc=glibc
Result: CONFLICT ❌ (exclusive domain)

For package maintainers:

• Use non-exclusive variants for features (ssl, ipv6, http2)
• Use exclusive variants for fundamental choices (libc, init system)
• Document variant requirements clearly

Phase 3: CNF Translation

What happens: The dependency graph is translated into a boolean satisfiability (SAT) problem:

Dependencies become implications:
  nginx → openssl  (if nginx then openssl)
  
Conflicts become exclusions:
  ¬(openssl-musl ∧ openssl-glibc)  (not both)

For package maintainers:

• This is automatic, but understanding it helps debug conflicts
• Each package+version+variant becomes a boolean variable
• Dependencies become logical implications

Phase 4: CDCL Solving

What happens: The CDCL solver finds a satisfying assignment:

1. Unit Propagation: Derive forced choices
2. Decision: Make a choice when no forced moves
3. Conflict Detection: Detect unsatisfiable constraints
4. Conflict Analysis: Learn why the conflict occurred
5. Backjumping: Jump back to the decision that caused the conflict
6. Clause Learning: Remember this conflict to avoid it in the future

For package maintainers:

• The solver is very efficient (50 packages in ~14ms)
• Conflicts are reported with clear explanations
• The solver learns from conflicts, making subsequent attempts faster

Phase 5: Topological Sort

What happens: Once a solution is found, packages are sorted for installation:

Installation order:
1. zlib-1.2.13      (no dependencies)
2. pcre-8.45        (no dependencies)
3. openssl-3.0.0    (depends on zlib)
4. nginx-1.24.0     (depends on openssl, pcre, zlib)

For package maintainers:

• Dependencies are ALWAYS installed before dependents
• Circular dependencies are detected and rejected
• Installation order is deterministic

---

Common Migration Scenarios

Scenario 1: Migrating from Arch Linux (PKGBUILD)

Arch PKGBUILD:

pkgname=nginx
pkgver=1.24.0
depends=('pcre' 'zlib' 'openssl')
makedepends=('cmake')

NIP manifest:

package "nginx" {
  version "1.24.0"
  
  dependencies {
    pcre { version ">=8.0"; required true }
    zlib { version ">=1.2.0"; required true }
    openssl { version ">=3.0.0"; required true }
  }
  
  build_dependencies {
    cmake { version ">=3.20"; required true }
  }
}

Key differences:

• NIP separates runtime and build dependencies
• Version constraints are explicit
• Variants can be specified per-dependency

Scenario 2: Migrating from Gentoo (ebuild)

Gentoo ebuild:

DEPEND="
    ssl? ( dev-libs/openssl:= )
    http2? ( net-libs/nghttp2 )
"

NIP manifest:

package "nginx" {
  version "1.24.0"
  
  dependencies {
    openssl {
      version ">=3.0.0"
      variants "+ssl"
      required true
      condition "ssl"  // Only if +ssl variant enabled
    }
    nghttp2 {
      version ">=1.50.0"
      required true
      condition "http2"  // Only if +http2 variant enabled
    }
  }
}

Key differences:

• USE flags become variant conditions
• Conditional dependencies are explicit
• Slot dependencies (:=) become version constraints

Scenario 3: Migrating from Nix

Nix expression:

{ stdenv, fetchurl, openssl, pcre, zlib
, http2Support ? true
, sslSupport ? true
}:

stdenv.mkDerivation {
  pname = "nginx";
  version = "1.24.0";
  
  buildInputs = [ pcre zlib ]
    ++ lib.optional sslSupport openssl
    ++ lib.optional http2Support nghttp2;
}

NIP manifest:

package "nginx" {
  version "1.24.0"
  
  dependencies {
    pcre { version ">=8.0"; required true }
    zlib { version ">=1.2.0"; required true }
    openssl {
      version ">=3.0.0"
      required true
      condition "ssl"
    }
    nghttp2 {
      version ">=1.50.0"
      required true
      condition "http2"
    }
  }
  
  variants {
    ssl { default true; description "Enable SSL support" }
    http2 { default true; description "Enable HTTP/2 support" }
  }
}

Key differences:

• Nix's optional dependencies become conditional dependencies
• Build inputs are separated by type
• Variants are explicitly declared

---

Debugging Dependency Conflicts

Conflict Type 1: Version Conflict

Error message:

❌ [VersionConflict] Cannot satisfy conflicting version requirements
🔍 Context: 
  - Package A requires openssl >=3.0.0
  - Package B requires openssl <2.0.0
💡 Suggestions:
  • Update Package B to support openssl 3.x
  • Use NipCells to isolate conflicting packages
  • Check if Package B has a newer version available

Solution for package maintainers:

1. Update version constraints to be more flexible
2. Test with multiple versions of dependencies
3. Document minimum and maximum supported versions

Conflict Type 2: Variant Conflict

Error message:

❌ [VariantConflict] Cannot unify conflicting variant demands
🔍 Context:
  - Package A requires openssl libc=musl
  - Package B requires openssl libc=glibc
💡 Suggestions:
  • These packages cannot coexist in the same environment
  • Use NipCells to create separate environments
  • Consider building one package with compatible variants

Solution for package maintainers:

1. Make libc choice configurable if possible
2. Document which libc your package requires
3. Test with both musl and glibc

Conflict Type 3: Circular Dependency

Error message:

❌ [CircularDependency] Circular dependency detected
🔍 Context: A → B → C → A
💡 Suggestions:
  • Break the circular dependency by making one dependency optional
  • Check if this is a bug in package metadata
  • Consider splitting packages to break the cycle

Solution for package maintainers:

1. Review your dependency tree
2. Make build-time dependencies optional where possible
3. Consider splitting large packages into smaller components

---

Best Practices for Package Maintainers

1. Write Flexible Version Constraints

❌ Bad:

openssl { version "=3.0.0"; required true }  // Too strict

✅ Good:

openssl { version ">=3.0.0 <4.0.0"; required true }  // Flexible

2. Document Variant Requirements

❌ Bad:

// No documentation about what variants do
variants {
  ssl { default true }
  http2 { default true }
}

✅ Good:

variants {
  ssl {
    default true
    description "Enable SSL/TLS support via OpenSSL"
    requires "openssl >=3.0.0"
  }
  http2 {
    default true
    description "Enable HTTP/2 protocol support"
    requires "nghttp2 >=1.50.0"
  }
}

3. Separate Build and Runtime Dependencies

❌ Bad:

dependencies {
  cmake { version ">=3.20"; required true }  // Build tool
  openssl { version ">=3.0.0"; required true }  // Runtime
}

✅ Good:

build_dependencies {
  cmake { version ">=3.20"; required true }
}

dependencies {
  openssl { version ">=3.0.0"; required true }
}

4. Test with Multiple Dependency Versions

# Test with minimum supported version
nip install --test mypackage openssl=3.0.0

# Test with latest version
nip install --test mypackage openssl=3.2.0

# Test with different variants
nip install --test mypackage +ssl -ipv6
nip install --test mypackage +ssl +ipv6

5. Use Conditional Dependencies Wisely

❌ Bad:

dependencies {
  openssl { version ">=3.0.0"; required true }
  // Always required, even if SSL is disabled
}

✅ Good:

dependencies {
  openssl {
    version ">=3.0.0"
    required true
    condition "ssl"  // Only when +ssl variant enabled
  }
}

---

Performance Considerations

Resolution Speed

NIP's resolver is designed for speed:

• Small packages (5-10 deps): < 10ms
• Medium packages (20-50 deps): < 50ms
• Large packages (100+ deps): < 200ms

For package maintainers:

• Keep dependency trees shallow when possible
• Avoid unnecessary dependencies
• Use optional dependencies for features

Caching

NIP caches resolution results:

# First resolution (cold cache)
nip install nginx  # ~50ms

# Second resolution (warm cache)
nip install nginx  # ~5ms

For package maintainers:

• Resolution results are cached per variant combination
• Changing variants invalidates the cache
• Cache is shared across all packages

---

Advanced Topics

Variant Unification Algorithm

NIP uses a sophisticated variant unification algorithm:

1. Group demands by package: Collect all variant requirements for each package
2. Check exclusivity: Detect conflicting exclusive variants (e.g., libc)
3. Merge non-exclusive: Combine non-exclusive variants (e.g., +ssl +http2)
4. Calculate hash: Generate deterministic variant hash
5. Return result: Unified profile or conflict report

Example:

Input:
  Package A wants: nginx +ssl +ipv6
  Package B wants: nginx +ssl +http2
  
Process:
  1. Group: nginx {+ssl, +ipv6} and nginx {+ssl, +http2}
  2. Check exclusivity: None (all non-exclusive)
  3. Merge: nginx {+ssl, +ipv6, +http2}
  4. Hash: xxh3-abc123...
  
Output: nginx-1.24.0-{+ssl,+ipv6,+http2}

Multi-Source Resolution

NIP can resolve dependencies from multiple sources:

nginx (native .npk)
├── openssl (grafted from Nix)
├── pcre (grafted from Arch)
└── zlib (native .npk)

For package maintainers:

• Specify preferred sources in package metadata
• Test with packages from different sources
• Document source compatibility

---

Troubleshooting Guide

Problem: "Package not found"

Cause: Package doesn't exist in any configured repository

Solution:

1. Check repository configuration: nip repo list
2. Update repository metadata: nip update
3. Search for similar packages: nip search <name>

Problem: "Circular dependency detected"

Cause: Package A depends on B, B depends on C, C depends on A

Solution:

1. Review dependency tree: nip show --tree <package>
2. Make one dependency optional
3. Split packages to break the cycle

Problem: "Variant conflict"

Cause: Two packages require incompatible variants

Solution:

1. Use NipCells to isolate: nip cell create env1
2. Build one package with compatible variants
3. Update package to support both variants

Problem: "Version conflict"

Cause: Two packages require incompatible versions

Solution:

1. Update version constraints to be more flexible
2. Check for newer package versions
3. Use NipCells for isolation

---

References

Academic Papers

• PubGrub Algorithm: Dart's pub solver
• CDCL Solving: Conflict-Driven Clause Learning

Related Documentation

• Variant System Guide
• Package Format Specification
• Grafting External Packages
• NipCells for Isolation

Source Code

• nip/src/nip/resolver/cdcl_solver.nim - CDCL solver implementation
• nip/src/nip/resolver/cnf_translator.nim - CNF translation
• nip/src/nip/resolver/dependency_graph.nim - Graph construction
• nip/src/nip/resolver/resolver_integration.nim - End-to-end pipeline

---

Glossary

• CDCL: Conflict-Driven Clause Learning - SAT solving technique
• CNF: Conjunctive Normal Form - Boolean logic representation
• PubGrub: Modern dependency resolution algorithm
• SAT: Boolean Satisfiability Problem
• Term: Package + Version + Variant combination
• Variant: Build configuration option (like Gentoo USE flags)
• Unification: Merging compatible variant requirements

---

Document Version: 1.0
Last Updated: November 23, 2025
Maintainer: NexusOS Core Team
Feedback: Submit issues to the NIP repository