find_minimal_failure

#!/usr/bin/ruby
CACHE = "find_minimal_failure.cache".freeze

def usage
  puts <<TXT
Usage: find_minimal_failure COMMAND [OPTIONS --] ARGUMENTS...
Finds the minimal ordered subsequence of ARGUMENTS that still
makes the command fail.
This is useful in place of "rspec --bisect"
when your extension library crashes without producing an exception.

It saves the last known failing arguments in '#{CACHE}'.
TXT
  exit 1
end

mode = :halving_find
if ARGV[0] == "-i"
  mode = :incremental_find
  ARGV.shift
elsif ARGV[0] == "-d"
  mode = :decremental_find
  ARGV.shift
elsif ARGV[0] == "-2"
  mode = :halving_find
  ARGV.shift
end

ddash = ARGV.index "--"
if ddash.nil?
  $command_w_options = ARGV[0..0]
  files = ARGV[1..-1]
else
  $command_w_options = ARGV[0.. ddash-1]
  files = ARGV[ddash+1 .. -1]
end

if files.empty?
  files = File.read(CACHE).split
end

def run(files)
  puts "Running with #{files.size} files"
  ok = system *$command_w_options, *files  
  puts " that was for #{files.join ' '}"
  ok
end

predicate = lambda do |files|
  !run(files)
end

# ["a", "b", "c"] -> [["b", "c"], ["a", "c"], ["a", "b"]]
def subtracted_candidates(files)
  files.map do |f|
    files - [f]
  end
end

def shuffled_candidates(files)
  cs = if files.size > 4
         10.times.map do
           files.shuffle    
         end
       else
         # exhaust all permutations
         files.permutation.to_a
       end

  cs.find_all do |fs|
    fs != files
  end
end

# modifies the argument, caches successful optimizations in the cache file
def decremental_find(files, predicate)
  loop do
    candidates = subtracted_candidates(files) + shuffled_candidates(files)
    better_files = candidates.find { |fs| predicate.call(fs) }

    break if better_files.nil?
    files.replace(better_files)
    File.write(CACHE + ".new", files.join(" "))
    system "mv", CACHE + ".new", CACHE
  end
  puts "Could not find an improvement for #{files.size} files: #{files.join ' '}"
end

def incremental_find(files, predicate)
  (1..10).each do |n|
    candidates = files.permutation(n)
    puts "Sets of size #{n} (#{candidates.size} of them)"

    min_failing = candidates.find {|fs| predicate.call(fs) }

    next if min_failing.nil?
    puts "YAY"
    return
  end
  puts "Will not try for bigger sets"
end

def halving_find(files, predicate)
  loop do
    tries = 10
    candidates = tries.times.map do
      sh = files.shuffle
      sh[sh.size/2 .. -1] # takes the bigger half
    end

    better_files = candidates.find { |fs| predicate.call(fs) }

    if better_files.nil?
      puts "Could not find a halved failure"
      exit 1
    end
    files.replace(better_files)
  end
end

puts "Verifying that the initial arguments DO fail"
if run(files)
  puts "WTF, it has succeeded"
#  exit 1
end

send(mode, files, predicate)