merge_base.rb

#!/usr/bin/env ruby

require "set"

class Merger
  def initialize(repo)
    @repo = repo
  end

  def merge_base(a, b)
    a = Ancestors.new(a)
    b = Ancestors.new(b)

    candidates = Set.new
    min_depth  = nil

    until a.stuck? and b.stuck?
      intersects = a.intersect(b) + b.intersect(a)

      intersects.each do |ref|
        depth = [a.depth(ref), b.depth(ref)].min

        if min_depth.nil? or depth < min_depth
          candidates = Set.new
          min_depth  = depth
        end

        candidates.add(ref) if depth == min_depth

        [a, b].each { |set| set.prune(ref) }
      end
      [a, b].each { |set| set.walk(@repo) }
    end

    candidates.to_a
  end
end

class Ancestors
  def initialize(ref)
    @depth = 0
    @found = { ref => @depth }
    @head  = Set.new([ref])
    @cache = {}
  end

  def ancestor?(ref)
    @found.has_key?(ref)
  end

  def depth(ref)
    @found[ref]
  end

  def stuck?
    @head.empty?
  end

  def intersect(other)
    matches = @head.select { |ref| other.ancestor?(ref) }
    Set.new(matches)
  end

  def prune(ref)
    @head.delete(ref)
    @cache.fetch(ref, []).each { |parent| prune(parent) }
  end

  def walk(repo)
    old_head = @head
    @head    = Set.new
    @depth  += 1

    old_head.each do |ref|
      @cache[ref] = repo.parents(ref)

      @cache[ref].each do |parent|
        next if ancestor?(parent)
        @found[parent] = @depth
        @head.add(parent)
      end
    end
  end
end

class Repo
  def initialize(pathname)
    @pathname = pathname
  end

  def resolve(ref)
    return ref if ref =~ /^[0-9a-f]{40}$/

    ["heads/#{ref}", "remotes/#{ref}"].each do |path|
      begin
        return File.read(File.join(@pathname, "refs", path)).strip
      rescue
      end
    end
  end

  def parents(ref)
    `git cat-file -p #{ref}`.lines.grep(/^parent /).map do |line|
      line.strip.split(/\s+/).last
    end
  end
end


repo   = Repo.new(File.expand_path(".git"))
merger = Merger.new(repo)
refs   = ARGV.map { |ref| repo.resolve(ref) }

puts merger.merge_base(*refs)