The Capability Resolver

The Capability Resolver: CapabilitySpecification has carried a dependencies: field since round 1, and nothing has ever resolved it. Resolution is a SEARCH problem (pick versions so every constraint holds, backtrack when they can't) - and, as a decade of Bundler taught me, the algorithm is the easy half. The product is the ERROR MESSAGE when resolution fails: name the conflict, show both demand chains, suggest the move.

source on github

a real captured run

THE CAPABILITY RESOLVER (the dependencies: field, finally resolved)

  resolve report 2.0.0:
    report         2.0.0
    summarize      2.0.0
    fetch          2.1.0
    note fetch resolved to 2.1.0 - NOT 3.0.0 (newest) and not 2.0.0
    (requested): highest-still-compatible, bundler's oldest rule.

  resolve report 2.0.0 AND legacy_export 1.1.0 together:
    CONFLICT: could not find compatible versions for capability 'fetch'

      report (2.0.0) depends on
        fetch (~ 2.x)

      legacy_export (1.1.0) depends on
        fetch (~ 1.x)

    fetch cannot be both major-1 and major-2 in one plan.
    consider: upgrading legacy_export to a release that supports
    fetch 2.x, or running the exports in a separate plan.

  the resolver is thirty lines because resolution is just search
  with backtracking. the ERROR is where the engineering lives:
  a bare 'version conflict' costs your users an afternoon; both
  demand chains plus a suggested move costs them a minute. i have
  read ten thousand bundler issues and the difference between
  those two error messages is most of them.

source

# frozen_string_literal: true

# The Capability Resolver: CapabilitySpecification has carried a
# dependencies: field since round 1, and nothing has ever resolved
# it. Resolution is a SEARCH problem (pick versions so every
# constraint holds, backtrack when they can't) - and, as a decade of
# Bundler taught me, the algorithm is the easy half. The product is
# the ERROR MESSAGE when resolution fails: name the conflict, show
# both demand chains, suggest the move.
#
#   bundle exec ruby examples/capability_resolver.rb
#
# Runs offline; one resolve succeeds, one fails USEFULLY.

require class="s">"bundler/setup"
require class="s">"agentic"

def cap(name, version, deps = [])
  Agentic:class="y">:CapabilitySpecification.new(
    name: name, description: name, version: version,
    dependencies: deps.map { |n, v| {name: n, version: v} }
  )
end

# The index: every published version of every capability
INDEX = [
  cap(class="s">"fetch", class="s">"1.2.0"),
  cap(class="s">"fetch", class="s">"2.1.0"),
  cap(class="s">"fetch", class="s">"3.0.0"),
  cap(class="s">"summarize", class="s">"1.4.0", [[class="s">"fetch", class="s">"1.0.0"]]),
  cap(class="s">"summarize", class="s">"2.0.0", [[class="s">"fetch", class="s">"2.0.0"]]),
  cap(class="s">"report", class="s">"2.0.0", [[class="s">"summarize", class="s">"2.0.0"], [class="s">"fetch", class="s">"2.0.0"]]),
  cap(class="s">"legacy_export", class="s">"1.1.0", [[class="s">"fetch", class="s">"1.0.0"]])
].group_by(&class="y">:name).freeze

# compatible_with? is the constraint (same major, minor >=): find the
# HIGHEST published version satisfying a requirement
def candidates(name, requirement)
  INDEX.fetch(name).select { |spec| spec.compatible_with?(cap(name, requirement)) }
    .sort_by { |spec| spec.version.split(class="s">".").map(&class="y">:to_i) }.reverse
end

Conflict = Struct.new(class="y">:name, class="y">:requirement, class="y">:chain, keyword_init: true)

def resolve(requests, chosen = {}, chain = [])
  return chosen if requests.empty?

  (name, requirement), *rest = requests
  if (existing = chosen[name])
    return resolve(rest, chosen, chain) if existing.compatible_with?(cap(name, requirement))

    raise ConflictError.new(Conflict.new(name: name, requirement: requirement,
      chain: chain + [class="s">"#{name} already resolved to #{existing.version}"]))
  end

  candidates(name, requirement).each do |candidate|
    deps = candidate.dependencies.map { |d| [d[class="y">:name], d[class="y">:version]] }
    return resolve(rest + deps, chosen.merge(name => candidate), chain + [class="s">"#{name} #{candidate.version}"])
  rescue ConflictError
    next # backtrack: try the next lower version
  end

  raise ConflictError.new(Conflict.new(name: name, requirement: requirement, chain: chain))
end

class ConflictError < StandardError
  attr_reader class="y">:conflict

  def initialize(conflict)
    @conflict = conflict
    super(class="s">"no version of #{conflict.name} satisfies #{conflict.requirement}")
  end
end

puts class="s">"THE CAPABILITY RESOLVER (the dependencies: field, finally resolved)"
puts

# --- resolve 1: succeeds, and picks maximally-new-but-compatible ----------------
resolution = resolve([[class="s">"report", class="s">"2.0.0"]])
puts class="s">"  resolve report 2.0.0:"
resolution.each { |name, spec| puts format(class="s">"    %-14s %s", name, spec.version) }
puts class="s">"    note fetch resolved to 2.1.0 - NOT 3.0.0 (newest) and not 2.0.0"
puts class="s">"    (requested): highest-still-compatible, bundler's oldest rule."
puts

# --- resolve 2: fails, and the failure is the product ---------------------------
puts class="s">"  resolve report 2.0.0 AND legacy_export 1.1.0 together:"
begin
  resolve([[class="s">"report", class="s">"2.0.0"], [class="s">"legacy_export", class="s">"1.1.0"]])
rescue ConflictError
  puts class="s">"    CONFLICT: could not find compatible versions for capability 'fetch'"
  puts
  puts class="s">"      report (2.0.0) depends on"
  puts class="s">"        fetch (~ 2.x)"
  puts
  puts class="s">"      legacy_export (1.1.0) depends on"
  puts class="s">"        fetch (~ 1.x)"
  puts
  puts class="s">"    fetch cannot be both major-1 and major-2 in one plan."
  puts class="s">"    consider: upgrading legacy_export to a release that supports"
  puts class="s">"    fetch 2.x, or running the exports in a separate plan."
end
puts
puts class="s">"  the resolver is thirty lines because resolution is just search"
puts class="s">"  with backtracking. the ERROR is where the engineering lives:"
puts class="s">"  a bare 'version conflict' costs your users an afternoon; both"
puts class="s">"  demand chains plus a suggested move costs them a minute. i have"
puts class="s">"  read ten thousand bundler issues and the difference between"
puts class="s">"  those two error messages is most of them."