#!/usr/bin/ruby
# msmp "CMD" ARGS... - find a minimal set of ARGS to make shellscript CMD fail
#
def usage
  abort 'msmp: find a minimal set of arguments to make a shellscript fail

Usage: msmp [-v] [-s] [-l] [-1] "CMD..." ARGS...
   -v  verbose, print arguments before each run
   -s  randomly shuffle argument list in the beginning
   -l  line mode: read args as lines from stdin and feed to CMD on stdin
   -1  stop after finding a single argument that still fails

Requirement: CMD must fail with all ARGS, and be monotone:
  when CMD fails for a subset S, it also must fail for all supersets of S.
  ARGS are not reordered by msmp by default.'
end

# TODO
# x add verbose flag
# x add support for looking for exactly one argument (use binary search)
# x pass lines on stdin instead of arguments
# - parallelization? how...
# x run final test when full ARGS is computed

# Algorithm "QuickXPlain" from http://sat.inesc-id.pt/~mikolas/cav13.pdf by
# Joao Marques-Silva, Mikolas Janota, and Anton Belov:
# Minimal Sets over Monotone Predicates in Boolean Formulae

def qxp(b, t, has_set, &pred)
  return []  if has_set && pred.call(b)

  return t  if t.size <= 1

  m = t.size / 2
  t1, t2 = t[0...m], t[m..-1]

  m2 = qxp(b | t1, t2, !t1.empty?, &pred)
  return m2  if $single && m2.size == 1
  m1 = qxp(b | m2, t1, !m2.empty?, &pred)
  return m1  if $single && m1.size == 1

  if b.size == 0 && !pred.call(t)
    abort "msmp: requirement violation, command does not fail for all arguments"
  end

  m1 | m2
end

linemode = false
verbose = false
shuffle = false
$single = false
while ARGV.first =~ /^-/
  case ARGV.first
  when "-l"; linemode = true
  when "-v"; verbose = true
  when "-s"; shuffle = true
  when "-1"; $single = true
  else usage
  end
  ARGV.shift
end

shquote = lambda { |s|
  if s =~ %r"[\000-\040`^#*\[\]=|\\?${}()'\"<>&;\177]"
    "'#{s.gsub(/'/, '\\\'')}'"
  else
    s
  end
}

cmd = ARGV.shift || usage

if linemode
  args = STDIN.readlines
else
  args = ARGV
end
args.shuffle!  if shuffle

calls = 0
cost = 0
result = qxp([], args, false) { |args|
  calls += 1
  cost += args.size

  STDERR.puts "msmp: trying #{args.map(&shquote).join(" ")}"  if verbose

  if linemode
    IO.popen(["/bin/sh", "-c", cmd], "w") { |pipe|
      pipe.puts(args)
    }
  else
    system "/bin/sh", "-c", cmd, "/bin/sh", *args
  end

  STDERR.puts "msmp: try ##{calls} with #{args.size} args: " +
              ($?.signaled? ? "signal=#{$?.termsig}" : "status=#{$?.exitstatus}")
  $?.to_i != 0
}

puts result

STDERR.puts "msmp: found minimal set of #{result.size} elements "\
            "(took #{calls} calls with total of #{cost} arguments)."