#!/usr/bin/env ruby
 
# git-find, version 1.0
#
# by John Wiegley <johnw@newartisans.com>
#
# usage: git find <commit or tag>...
#
# Performs an exhaustive search of your object database to inform you exactly
# how the given commit or tag fits in your repository.  It tells you all the
# parents and children of the commit/tag, and every name it can be referenced
# by.  It will tell you if it can be reached only by a reflog entry, or the
# stash, or if it's descendend from a dangling commit.
#
# TODO: Add support for searching for blobs and trees as well.
#
# NOTE: This script can be very slow.
 
class GitObject
  attr_reader :ident
 
  def initialize(ident)
    @ident = ident
  end
end
 
class Blob < GitObject
  attr_reader :names
 
  def initialize(ident)
    super ident
    @names = []
  end
 
  def add_name(name)
    @names.push(name)
  end
end
 
class Tree < GitObject
  attr_reader :names
 
  def initialize(ident)
    super ident
    @names = []
  end
 
  def add_name(name)
    @names.push(name)
  end
end
 
class Commit < GitObject
  attr_reader :names
  attr_reader :parents
  attr_reader :children
 
  def initialize(ident, *parents)
    super ident
    @names    = []
    @parents  = parents
    @children = []
  end
 
  def add_name(name)
    @names.push(name)
  end
 
  def add_parent(parent)
    unless @parents.include?(parent)
      @parents.push(parent)
      parent.add_child(self)
    end
  end
 
  def add_child(child)
    unless @children.include?(child)
      @children.push(child)
    end
  end
 
  def assign_name(name)
    if @names.include?(name)
      return
    end
    add_name(name)
 
    offset = 0
    @parents.each do |parent|
      if offset == 0
        if name =~ /(.+?)~([0-9]+)$/
          child_name = $1 + "~" + ($2.to_i + 1).to_s
        else
          child_name = name + "~1"
        end
      else
        child_name = name + "^" + (offset + 1).to_s
      end
      parent.assign_name(child_name)
      offset += 1
    end
  end
end
 
class Tag < GitObject
  attr_reader :name
  attr_reader :commit
 
  def initialize(ident, name, commit)
    super ident
    @name = name
    @commit = commit
  end
end
 
class Ref
  attr_reader :name
  attr_reader :commit
 
  def initialize(name, commit)
    @name   = name
    @commit = commit
  end
end
 
$objects = {}
 
# Build up a full commit history for every ref, and each reflog entry for each
# ref.
 
def get_ref_history(ref)
  first_obj = true
 
  `git rev-list --parents #{ref}`.split("\n").each do |entry|
    commit, *parents = entry.split(' ')
 
    if $objects.has_key?(commit)
      obj = $objects[commit]
    else
      obj = Commit.new(commit)
      $objects[commit] = obj
    end
 
    if first_obj and ref =~ /\/tags\//
      id = `git rev-parse #{ref}`.chomp
      $objects[id] = Tag.new(id, ref, obj)
      first_obj = false
    end
 
    if obj.parents.size == 0
      parents.each do |parent|
        if $objects.has_key?(parent)
          parent_obj = $objects[parent]
        else
          parent_obj = Commit.new(parent)
          $objects[parent] = parent_obj
        end
        obj.add_parent(parent_obj)
      end
    end
  end
end
 
def process_names(ref, name = nil, hash = nil)
  # Assign symbolic names to each commit
  if not hash
    hash = `git rev-parse #{ref}`.chomp
  end
  raise "Cannot locate object #{ref} => #{hash}" if not $objects.has_key?(hash)
  obj = $objects[hash]
  if obj.is_a? Tag
    obj.commit.assign_name(name ? name : ref)
  else
    obj.assign_name(name ? name : ref)
  end
end
 
$refs = `git rev-parse --symbolic --all`.split
$refs.push("HEAD")
 
puts "Processing refs history ..."
$refs.each { |ref| get_ref_history(ref) }
$refs.each { |ref| process_names(ref) }
 
$hashes = ARGV[0].map { |ref| `git rev-parse #{ref}`.chomp }
 
$search_reflogs = false
$hashes.each do |hash|
  unless $objects.has_key?(hash)
    $search_reflogs = true
  end
end
 
if $search_reflogs
  puts "Processing reflogs ..."
  $refs.each do |ref| 
    unless ref == "refs/stash"
      # Handle each reflog entry
      `git reflog show --abbrev=40 #{ref}`.split("\n").each do |line|
        if line =~ /^([0-9a-f]{40}) ([^@]+@\{[0-9]+\}): /
          hash = $1
          unless $objects.has_key?(hash)
            puts "  unreachable reflog #{$2}"
            get_ref_history $2
            process_names $2, nil, hash
          end
        end
      end
    end
  end
end
 
$search_dangling = false
$hashes.each do |hash|
  unless $objects.has_key?(hash)
    $search_dangling = true
  end
end
 
if $search_dangling
  puts "Finding unreachable objects ..."
  `git fsck --full --unreachable`.split("\n").each do |item|
    if item =~ /unreachable (blob|tag|commit|tree) ([a-f0-9]{40})/
      puts "  " + item
      if $1 == "blob"
        $objects[$2] = Blob.new($2)
      elsif $1 == "tag"
        commit = Commit.new(`git rev-list -1 #{$2}`.chomp)
        $objects[$2] = Tag.new($2, "<dangling>", commit)
        get_ref_history $2
        process_names $2, "dangling-tag-#{$2}"
      elsif $1 == "commit"
        get_ref_history $2
        process_names $2, "dangling-commit-#{$2}"
      elsif $1 == "tree"
        $objects[$2] = Tree.new($2)
      end
    end
  end
end
 
ARGV[0].each do |ref|
  hash = `git rev-parse #{ref}`.chomp
 
  object = $objects[hash]
 
  puts ""
  if object.is_a? Tag
    puts "Tag #{ref} => #{hash}"
    object = object.commit
    puts "  commit #{object.ident}"
  else
    puts "Commit #{ref} => #{hash}"
  end
 
  object.parents.each  { |parent| puts "  parent #{parent.ident}" }
  object.children.each { |child|  puts "   child #{child.ident}" }
  object.names.each    { |name|   puts "    name #{name}" }
end