#!/usr/bin/python3
#
#  Copyright (C) 2018 The Android Open Source Project
#
#  Licensed under the Apache License, Version 2.0 (the "License");
#  you may not use this file except in compliance with the License.
#  You may obtain a copy of the License at
#
#       http://www.apache.org/licenses/LICENSE-2.0
#
#  Unless required by applicable law or agreed to in writing, software
#  distributed under the License is distributed on an "AS IS" BASIS,
#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#  See the License for the specific language governing permissions and
#  limitations under the License.
#


import datetime, filecmp, math, multiprocessing, os, shutil, subprocess, stat, sys, time
from collections import OrderedDict

def usage():
  print("""Usage: diff-filterer.py [--assume-no-side-effects] [--assume-input-states-are-correct] [--work-path <workpath>] [--num-jobs <count>] [--timeout <seconds>] [--debug] <passingPath> <failingPath> <shellCommand>

diff-filterer.py attempts to transform (a copy of) the contents of <passingPath> into the contents of <failingPath> subject to the constraint that when <shellCommand> is run in that directory, it returns 0

OPTIONS
  --assume-no-side-effects
    Assume that the given shell command does not make any (relevant) changes to the given directory, and therefore don't wipe and repopulate the directory before each invocation of the command
  --assume-input-states-are-correct
    Assume that <shellCommand> passes in <passingPath> and fails in <failingPath> rather than re-verifying this
  --work-path <filepath>
    File path to use as the work directory for testing the shell command
    This file path will be overwritten and modified as needed for testing purposes, and will also be the working directory of the shell command when it is run
  --num-jobs <count>
    The maximum number of concurrent executions of <shellCommand> to spawn at once
    Specify 'auto' to have diff-filterer.py dynamically adjust the number of jobs based on system load
  --timeout <seconds>
    Approximate maximum amount of time to run. If diff-filterer.py expects that running a test would exceed this timeout, then it will skip running the test, terminate early, and report what it did find.
    diff-filterer.py doesn't terminate any child processes that have already started, so it is still possible that diff-filterer.py might exceed this timeout by the amount of time required to run one test.
  --debug
    Enable some debug checks in diff-filterer.py
""")
  sys.exit(1)

debug = False

# Miscellaneous file utilities
class FileIo(object):
  def __init__(self):
    return

  def ensureDirExists(self, filePath):
    if not os.path.isdir(filePath):
      if os.path.isfile(filePath) or os.path.islink(filePath):
        os.remove(filePath)
      os.makedirs(filePath)

  def copyFile(self, fromPath, toPath):
    self.ensureDirExists(os.path.dirname(toPath))
    self.removePath(toPath)
    if os.path.islink(fromPath):
      linkText = os.readlink(fromPath)
      os.symlink(linkText, toPath)
    else:
      shutil.copy2(fromPath, toPath)

  def hardLink(self, oldPath, newPath):
    self.ensureDirExists(os.path.dirname(newPath))
    self.removePath(newPath)
    os.link(oldPath, newPath)

  def writeFile(self, path, text):
    f = open(path, "w+")
    f.write(text)
    f.close()

  def writeScript(self, path, text):
    self.writeFile(path, text)
    os.chmod(path, stat.S_IRWXU)

  def removePath(self, filePath):
    if len(os.path.split(filePath)) < 2:
      raise Exception("Will not remove path at " + filePath + "; is too close to the root of the filesystem")
    if os.path.islink(filePath):
      os.remove(filePath)
    elif os.path.isdir(filePath):
      shutil.rmtree(filePath)
    elif os.path.isfile(filePath):
      os.remove(filePath)

  def join(self, path1, path2):
    return os.path.normpath(os.path.join(path1, path2))

  # tells whether <parent> either contains <child> or is <child>
  def contains(self, parent, child):
    if parent == child:
      return True
    return child.startswith(parent + "/")

  # returns the common prefix of two paths. For example, commonPrefixOf2("a/b/c", "a/b/cat") returns "a/b"
  def commonPrefixOf2(self, path1, path2):
    prefix = path2
    while True:
      if self.contains(prefix, path1):
        return prefix
      parent = os.path.dirname(prefix)
      if parent == prefix:
        return None
      prefix = parent

  # returns the common prefix of multiple paths
  def commonPrefix(self, paths):
    if len(paths) < 1:
      return None
    result = None
    for path in paths:
      if result is None:
        # first iteration
        result = path
      else:
        prev = result
        result = self.commonPrefixOf2(result, path)
        if result is None:
          # the common prefix of two paths was nothing
          return result
    return result

fileIo = FileIo()

# Returns cpu usage
class CpuStats(object):

  def cpu_times_percent(self):
    # We wait to attempt to import psutil in case we don't need it and it doesn't exist on this system
    import psutil
    return psutil.cpu_times_percent(interval=None)

cpuStats = CpuStats()

# Fast file copying
class FileCopyCache(object):
  def __init__(self):
    self.modificationTimes = {}

  # Puts a copy of <sourcePath> at <destPath>
  # If we already have an unmodified copy, we just hardlink our existing unmodified copy
  # If we don't have an unmodified copy, we first make a copy
  def copyFile(self, sourcePath, destPath, cachePath):
    if cachePath is None:
      fileIo.copyFile(sourcePath, destPath)
    else:
      shareable = self.getShareableFile(sourcePath, cachePath)
      fileIo.hardLink(shareable, destPath)

  # gets a shareable copy of <sourcePath> in <cachePath> and returns its path
  def getShareableFile(self, sourcePath, cachePath):
    # note that absolute sourcePath is supported
    path = os.path.abspath(cachePath + "/" + sourcePath)
    if path in self.modificationTimes:
      # we've already shared this file before; let's check whether it has been modified since then
      if self.modificationTimes[path] == self.getModificationTime(path):
        # this file hasn't been modified since we last shared it; we can just reuse it
        return path
    # we don't have an existing file that we can reuse, so we have to make one
    fileIo.copyFile(sourcePath, path)
    self.modificationTimes[path] = self.getModificationTime(path)
    return path

  # returns the time at which <path> was last modified
  def getModificationTime(self, path):
    if os.path.exists(path):
      return os.path.getmtime(path)
    return None


fileCopyCache = FileCopyCache()

# Runs a shell command
class ShellScript(object):
  def __init__(self, commandText, cwd):
    self.commandText = commandText
    self.cwd = cwd

  def process(self):
    cwd = self.cwd
    print("Running '" + self.commandText + "' in " + cwd)
    try:
      subprocess.check_call(["bash", "-c", "cd " + cwd + " && " + self.commandText])
      return 0
    except subprocess.CalledProcessError as e:
      return e.returncode

# Base class that can hold the state of a file
class FileContent(object):
  def apply(self, filePath, cachePath=None):
    pass

  def equals(self, other, checkWithFileSystem=False):
    pass

# A FileContent that refers to the content of a specific file
class FileBacked_FileContent(FileContent):
  def __init__(self, referencePath):
    super(FileBacked_FileContent, self).__init__()
    self.referencePath = referencePath
    self.isLink = os.path.islink(self.referencePath)

  def apply(self, filePath, cachePath=None):
    fileCopyCache.copyFile(self.referencePath, filePath, cachePath)

  def equals(self, other, checkWithFileSystem=False):
    if not isinstance(other, FileBacked_FileContent):
      return False
    if self.referencePath == other.referencePath:
      return True
    if not checkWithFileSystem:
      return False
    if self.isLink and other.isLink:
      return os.readlink(self.referencePath) == os.readlink(other.referencePath)
    if self.isLink != other.isLink:
      return False # symlink not equal to non-symlink
    return filecmp.cmp(self.referencePath, other.referencePath)

  def __str__(self):
    return self.referencePath

# A FileContent describing the nonexistence of a file
class MissingFile_FileContent(FileContent):
  def __init__(self):
    super(MissingFile_FileContent, self).__init__()

  def apply(self, filePath, cachePath=None):
    fileIo.removePath(filePath)

  def equals(self, other, checkWithFileSystem=False):
    return isinstance(other, MissingFile_FileContent)

  def __str__(self):
    return "Empty"

# A FileContent describing a directory
class Directory_FileContent(FileContent):
  def __init__(self):
    super(Directory_FileContent, self).__init__()

  def apply(self, filePath, cachePath=None):
    fileIo.ensureDirExists(filePath)

  def equals(self, other, checkWithFileSystem=False):
    return isinstance(other, Directory_FileContent)

  def __str__(self):
    return "[empty dir]"

# A collection of many FileContent objects
class FilesState(object):
  def __init__(self):
    self.fileStates = OrderedDict()

  def apply(self, filePath, cachePath=None):
    for relPath, state in self.fileStates.items():
      state.apply(fileIo.join(filePath, relPath), cachePath)

  def add(self, filePath, fileContent):
    self.fileStates[filePath] = fileContent

  def addAllFrom(self, other):
    for filePath in other.fileStates:
        self.add(filePath, other.fileStates[filePath])

  def getContent(self, filePath):
    if filePath in self.fileStates:
      return self.fileStates[filePath]
    return None

  def getKeys(self):
    return self.fileStates.keys()

  # returns a FilesState resembling <self> but without the keys for which other[key] == self[key]
  def withoutDuplicatesFrom(self, other, checkWithFileSystem=False):
    result = FilesState()
    for filePath, fileState in self.fileStates.items():
      otherContent = other.getContent(filePath)
      if not fileState.equals(otherContent, checkWithFileSystem):
        result.add(filePath, fileState)
    return result

  # returns self[fromIndex:toIndex]
  def slice(self, fromIndex, toIndex):
    result = FilesState()
    for filePath in list(self.fileStates.keys())[fromIndex:toIndex]:
      result.fileStates[filePath] = self.fileStates[filePath]
    return result

  def restrictedToKeysIn(self, other):
    result = FilesState()
    for filePath, fileState in self.fileStates.items():
      if filePath in other.fileStates:
        result.add(filePath, fileState)
    return result

  # returns a FilesState having the same keys as this FilesState, but with values taken from <other> when it has them, and <self> otherwise
  def withConflictsFrom(self, other, listEmptyDirs = False):
    result = FilesState()
    for filePath, fileContent in self.fileStates.items():
      if filePath in other.fileStates:
        result.add(filePath, other.fileStates[filePath])
      else:
        result.add(filePath, fileContent)
    if listEmptyDirs:
      oldImpliedDirs = self.listImpliedDirs()
      newImpliedDirs = result.listImpliedDirs()
      for impliedDir in oldImpliedDirs:
        if impliedDir not in newImpliedDirs and impliedDir not in result.fileStates:
          result.add(impliedDir, MissingFile_FileContent())
    return result

  def checkSameKeys(self, other):
    a = self.checkContainsKeys(other)
    b = other.checkContainsKeys(self)
    if a and b:
      return True
    if not a:
      print("a does not contain all of the keys from b")
    if not b:
      print("b does not contain all of the keys from a")
    return False

  def checkContainsKeys(self, other):
    contains = True
    for f in other.fileStates.keys():
      if f not in self.fileStates:
        print("Found in " + other.summarize() + " but not in " + self.summarize() + ": " + f)
        contains = False
    return contains

  # returns a set of paths to all of the dirs in <self> that are implied by any files in <self>
  def listImpliedDirs(self):
    dirs = set()
    empty = MissingFile_FileContent()
    keys = [key for (key, value) in self.fileStates.items() if not empty.equals(value)]
    i = 0
    while i < len(keys):
      path = keys[i]
      parent, child = os.path.split(path)
      if parent == "":
        parent = "."
      if not parent in dirs:
        dirs.add(parent)
        keys.append(parent)
      i += 1
    return dirs

  # returns a FilesState having all of the entries from <self>, plus empty entries for any keys in <other> not in <self>
  def expandedWithEmptyEntriesFor(self, other):
    impliedDirs = self.listImpliedDirs()
    # now look for entries in <other> not present in <self>
    result = self.clone()
    for filePath in other.fileStates:
      if filePath not in result.fileStates and filePath not in impliedDirs:
        result.fileStates[filePath] = MissingFile_FileContent()
    return result

  def clone(self):
    result = FilesState()
    for path, content in self.fileStates.items():
      result.add(path, content)
    return result

  def withoutEmptyEntries(self):
    result = FilesState()
    empty = MissingFile_FileContent()
    for path, state in self.fileStates.items():
      if not empty.equals(state):
        result.add(path, state)
    return result

  def getCommonDir(self):
    result = fileIo.commonPrefix(self.fileStates.keys())
    return result

  # Returns a list of FilesState objects each containing a different subdirectory of <self>
  # If groupDirectFilesTogether == True, then all files directly under self.getCommonDir() will be assigned to the same group
  def groupByDirs(self, groupDirectFilesTogether = False):
    if len(self.fileStates) <= 1:
      if len(self.fileStates) == 1:
        return [self]
      return []

    commonDir = self.getCommonDir()
    if commonDir is None:
      prefixLength = 0
    else:
      prefixLength = len(commonDir) + 1 # skip the following '/'
    groupsByDir = {}

    for filePath, fileContent in self.fileStates.items():
      subPath = filePath[prefixLength:]
      slashIndex = subPath.find("/")
      if slashIndex < 0:
        if groupDirectFilesTogether:
          firstDir = ""
        else:
          firstDir = subPath
      else:
        firstDir = subPath[:slashIndex]
      if not firstDir in groupsByDir:
        groupsByDir[firstDir] = FilesState()
      groupsByDir[firstDir].add(filePath, fileContent)
    return [group for group in groupsByDir.values()]

  # splits into multiple, smaller, FilesState objects
  def splitOnce(self, maxNumChildren = 2):
    if self.size() <= 1:
      return [self]
    children = self.groupByDirs(True)
    if len(children) == 1:
      children = children[0].groupByDirs(False)
    if len(children) > maxNumChildren:
      # If there are lots of child directories, we still want to test a smaller number of larger groups before testing smaller groups
      # So we arbitrarily recombine child directories to make a smaller number of children
      minIndex = 0
      mergedChildren = []
      for i in range(maxNumChildren):
        maxIndex = len(children) * (i + 1) // maxNumChildren
        merge = FilesState()
        for child in children[minIndex:maxIndex]:
          merge.addAllFrom(child)
        mergedChildren.append(merge)
        minIndex = maxIndex
      children = mergedChildren
    return children

  def summarize(self):
    numFiles = self.size()
    commonDir = self.getCommonDir()
    if numFiles <= 4:
      return str(self)
    if commonDir is not None:
      return str(numFiles) + " files under " + str(commonDir)
    return str(numFiles) + " files"

  def size(self):
    return len(self.fileStates)

  def __str__(self):
    if len(self.fileStates) == 0:
      return "[empty fileState]"
    entries = []
    for filePath, state in self.fileStates.items():
      entries.append(filePath + " -> " + str(state))
    if len(self.fileStates) > 1:
      prefix = str(len(entries)) + " entries:\n"
    else:
      prefix = "1 entry: "
    return prefix + "\n".join(entries)

# Creates a FilesState matching the state of a directory on disk
def filesStateFromTree(rootPath):
  rootPath = os.path.abspath(rootPath)

  paths = []
  states = {}

  for root, dirPaths, filePaths in os.walk(rootPath, topdown=True):
    if len(filePaths) == 0 and len(dirPaths) == 0:
      relPath = os.path.relpath(root, rootPath)
      paths.append(relPath)
      states[relPath] = Directory_FileContent()
    # include every file and every symlink (even if the symlink points to a dir)
    leaves = filePaths
    for dirPath in dirPaths:
      fullPath = os.path.join(root, dirPath)
      if os.path.islink(fullPath):
        leaves.append(dirPath)
    for filePath in leaves:
      fullPath = fileIo.join(root, filePath)
      relPath = os.path.relpath(fullPath, rootPath)
      paths.append(relPath)
      states[relPath] = FileBacked_FileContent(fullPath)

  paths = sorted(paths)
  state = FilesState()
  for path in paths:
    state.add(path, states[path])
  return state

# runs a Job in this process
def runJobInSameProcess(shellCommand, workPath, cachePath, originalState, assumeNoSideEffects, full_resetTo_state, testState, twoWayPipe):
  job = Job(shellCommand, workPath, cachePath, originalState, assumeNoSideEffects, full_resetTo_state, testState, twoWayPipe)
  job.runAndReport()

# starts a Job in a new process
def runJobInOtherProcess(shellCommand, workPath, cachePath, originalState, assumeNoSideEffects, full_resetTo_state, testState, queue, identifier):
  parentWriter, childReader = multiprocessing.Pipe()
  childInfo = TwoWayPipe(childReader, queue, identifier)
  process = multiprocessing.Process(target=runJobInSameProcess, args=(shellCommand, workPath, cachePath, originalState, assumeNoSideEffects, full_resetTo_state, testState, childInfo,))
  process.start()
  return parentWriter

class TwoWayPipe(object):
  def __init__(self, readerConnection, writerQueue, identifier):
    self.readerConnection = readerConnection
    self.writerQueue = writerQueue
    self.identifier = identifier

# Stores a subprocess for running tests and some information about which tests to run
class Job(object):
  def __init__(self, shellCommand, workPath, cachePath, originalState, assumeNoSideEffects, full_resetTo_state, testState, twoWayPipe):
    # the test to run
    self.shellCommand = shellCommand
    # directory to run the test in
    self.workPath = workPath
    # the state of our working directory
    self.originalState = originalState
    # whether to assume that the test won't change anything important
    self.assumeNoSideEffects = assumeNoSideEffects
    # the best accepted state
    self.full_resetTo_state = full_resetTo_state
    # the changes we're considering
    self.testState = testState
    self.pipe = twoWayPipe
    self.cachePath = cachePath

  def runAndReport(self):
    succeeded = False
    postState = None
    try:
      (succeeded, postState) = self.run()
    finally:
      print("^" * 100)
      self.pipe.writerQueue.put((self.pipe.identifier, succeeded, postState))

  def run(self):
    print("#" * 100)
    print("Checking " + self.testState.summarize() + " (job " + str(self.pipe.identifier) + ") in " + str(self.workPath) + " at " + str(datetime.datetime.now()))

    # compute the state that we want the files to be in before we start the test
    fullStateToTest = self.full_resetTo_state.expandedWithEmptyEntriesFor(self.testState).withConflictsFrom(self.testState, True)
    #print("Starting with original worker state of " + str(self.originalState))

    # update our files on disk to match the state we want to test
    fullStateToTest.expandedWithEmptyEntriesFor(self.originalState).withoutDuplicatesFrom(self.originalState).apply(self.workPath)

    # run test
    testStartSeconds = time.time()
    testStart = datetime.datetime.now()
    returnCode = ShellScript(self.shellCommand, self.workPath).process()
    testEnd = datetime.datetime.now()
    duration = (testEnd - testStart).total_seconds()

    if self.assumeNoSideEffects:
      # assume that no relevant files changed
      postState = fullStateToTest
    else:
      # determine which files weren't changed by the test command
      postState = filesStateFromTree(self.workPath)
      for key in postState.getKeys():
        modified = postState.getContent(key)
        if isinstance(modified, FileBacked_FileContent):
          # If any filepath wasn't modified since the start of the test, then its content matches the original
          # (If the content is known to match the original, we won't have to reset it next time)
          if os.path.getmtime(modified.referencePath) < testStartSeconds:
            original = fullStateToTest.getContent(key)
            if original is not None:
              if isinstance(original, FileBacked_FileContent):
                modified.referencePath = original.referencePath

    # report results
    if returnCode == 0:
      print("Passed: " + self.testState.summarize() + " (job " + str(self.pipe.identifier) + ") at " + str(datetime.datetime.now()) + " in " + str(duration))
      return (True, postState)
    else:
      print("Failed: " + self.testState.summarize() + " (job " + str(self.pipe.identifier) + ") at " + str(datetime.datetime.now()) + " in " + str(duration))
      return (False, postState)


# Runner class that determines which diffs between two directories cause the given shell command to fail
class DiffRunner(object):
  def __init__(self, failingPath, passingPath, shellCommand, workPath, assumeNoSideEffects, assumeInputStatesAreCorrect, maxNumJobsAtOnce, timeoutSeconds):
    # some simple params
    self.workPath = os.path.abspath(workPath)
    self.bestState_path = fileIo.join(self.workPath, "bestResults")
    self.sampleFailure_path = fileIo.join(self.workPath, "sampleFailure")
    self.testScript_path = fileIo.join(self.workPath, "test.sh")
    fileIo.ensureDirExists(os.path.dirname(self.testScript_path))
    fileIo.writeScript(self.testScript_path, shellCommand)
    self.originalPassingPath = os.path.abspath(passingPath)
    self.originalFailingPath = os.path.abspath(failingPath)
    self.assumeNoSideEffects = assumeNoSideEffects
    self.assumeInputStatesAreCorrect = assumeInputStatesAreCorrect
    self.timeoutSeconds = timeoutSeconds

    # lists of all the files under the two dirs
    print("Finding files in " + passingPath)
    self.originalPassingState = filesStateFromTree(passingPath)
    print("Found " + self.originalPassingState.summarize() + " in " + str(passingPath))
    print("")
    print("Finding files in " + failingPath)
    self.originalFailingState = filesStateFromTree(failingPath)
    print("Found " + self.originalFailingState.summarize() + " in " + str(failingPath))
    print("")
    print("Identifying duplicates")
    # list of the files in the state to reset to after each test
    self.full_resetTo_state = self.originalPassingState
    # minimal description of only the files that are supposed to need to be reset after each test
    self.resetTo_state = self.originalPassingState.expandedWithEmptyEntriesFor(self.originalFailingState).withoutDuplicatesFrom(self.originalFailingState, True)
    self.targetState = self.originalFailingState.expandedWithEmptyEntriesFor(self.originalPassingState).withoutDuplicatesFrom(self.originalPassingState, True)
    self.originalNumDifferences = self.resetTo_state.size()
    print("Processing " + str(self.originalNumDifferences) + " file differences")
    self.maxNumJobsAtOnce = maxNumJobsAtOnce

  def cleanupTempDirs(self):
    print("Clearing work directories")
    numAttempts = 3
    for attempt in range(numAttempts):
      if os.path.isdir(self.workPath):
        for child in os.listdir(self.workPath):
          if child.startswith("job-"):
            path = os.path.join(self.workPath, child)
            try:
              fileIo.removePath(path)
            except IOError as e:
              if attempt >= numAttempts - 1:
                raise Exception("Failed to remove " + path, e)
    fileIo.removePath(os.path.join(self.workPath, "caches"))

  def runnerTest(self, testState, timeout = None):
    workPath = self.getWorkPath(0)
    # reset state if needed
    fileIo.removePath(workPath)
    testState.apply(workPath)
    start = datetime.datetime.now()
    returnCode = ShellScript(self.testScript_path, workPath).process()
    duration = (datetime.datetime.now() - start).total_seconds()
    print("shell command completed in " + str(duration))
    if returnCode == 0:
      return (True, duration)
    else:
      if self.assumeNoSideEffects:
        # unapply changes so that the contents of workPath should match self.resetTo_state
        testState.withConflictsFrom(self.resetTo_state).apply(workPath)
      return (False, duration)

  def onSuccess(self, testState):
    #print("Runner received success of testState: " + str(testState.summarize()))
    if debug:
      if not filesStateFromTree(self.bestState_path).checkSameKeys(self.full_resetTo_state.withoutEmptyEntries()):
        print("Contents of " + self.bestState_path + " don't match self.full_resetTo_state at beginning of onSuccess")
        sys.exit(1)
    self.targetState = self.targetState.withoutDuplicatesFrom(testState)
    self.resetTo_state = self.resetTo_state.withConflictsFrom(testState).withoutDuplicatesFrom(testState)
    delta = self.full_resetTo_state.expandedWithEmptyEntriesFor(testState).withConflictsFrom(testState, True).withoutDuplicatesFrom(self.full_resetTo_state)
    delta.apply(self.bestState_path)
    self.full_resetTo_state = self.full_resetTo_state.expandedWithEmptyEntriesFor(delta).withConflictsFrom(delta)
    if debug:
      if not filesStateFromTree(self.bestState_path).checkSameKeys(self.full_resetTo_state.withoutEmptyEntries()):
        print("Contents of " + self.bestState_path + " don't match self.full_resetTo_state at end of onSuccess")
        print("Applied this delta: " + str(delta))
        sys.exit(1)

  def getWorkPath(self, jobId):
    return os.path.join(self.workPath, "job-" + str(jobId))

  def getFilesCachePath(self, jobId):
    return os.path.join(self.workPath, "caches", "job-" + str(jobId))

  def run(self):
    start = datetime.datetime.now()
    numIterationsCompleted = 0
    self.cleanupTempDirs()
    workPath = self.getWorkPath(0)
    if not self.assumeInputStatesAreCorrect:
      print("Testing that the given failing state actually fails")
      fileIo.removePath(workPath)
      if self.runnerTest(self.originalFailingState)[0]:
        print("\nGiven failing state at " + self.originalFailingPath + " does not actually fail!")
        return False
      # clean up temporary dirs in case any daemons remain running
      self.cleanupTempDirs()

      print("Testing that the given passing state actually passes")
      if not self.runnerTest(self.full_resetTo_state)[0]:
        print("\nGiven passing state at " + self.originalPassingPath + " does not actually pass!")
        return False
      # clean up temporary dirs in case any daemons remain running
      self.cleanupTempDirs()

    print("Saving best state found so far")
    fileIo.removePath(self.bestState_path)
    self.full_resetTo_state.apply(self.bestState_path)

    print("Starting")
    print("You can inspect " + self.bestState_path + " while this process runs, to observe the best state discovered so far")
    print("You can inspect " + self.sampleFailure_path + " while this process runs, to observe a state for which the test failed. If you delete this filepath, then it will be updated later to contain a new failing state")
    print("")
    # Now we search over groups of inodes (files or dirs) in the tree
    # Every time we encounter a group of inodes, we try replacing them and seeing if the replacement passes our test
    # If it does, we accept those changes and continue searching
    # If it doesn't, we split that group into smaller groups and continue
    jobId = 0
    workingDir = self.getWorkPath(jobId)
    queue = multiprocessing.Queue()
    activeTestStatesById = {}
    workerStatesById = {}
    initialSplitSize = 2
    if self.maxNumJobsAtOnce != "auto" and self.maxNumJobsAtOnce > 2:
      initialSplitSize = self.maxNumJobsAtOnce
    availableTestStates = self.targetState.splitOnce(initialSplitSize)
    numConsecutiveFailures = 0
    numFailuresSinceLastSplitOrSuccess = 0
    numCompletionsSinceLastPoolSizeChange = 0
    invalidatedIds = set()
    probablyAcceptableStates = []
    numCompletedTests = 2 # Already tested initial passing state and initial failing state
    numJobsAtFirstSuccessAfterMerge = None
    timedOut = False
    # continue until all files fail and no jobs are running
    while (numFailuresSinceLastSplitOrSuccess < self.resetTo_state.size() and not timedOut) or len(activeTestStatesById) > 0:
      # display status message
      now = datetime.datetime.now()
      elapsedDuration = now - start
      minNumTestsRemaining = sum([math.log(box.size(), 2) + 1 for box in availableTestStates + list(activeTestStatesById.values())]) - numFailuresSinceLastSplitOrSuccess
      estimatedNumTestsRemaining = max(minNumTestsRemaining, 1)
      if numConsecutiveFailures >= 4 and numFailuresSinceLastSplitOrSuccess < 1:
        # If we are splitting often and failing often, then we probably haven't yet
        # shrunken the individual boxes down to each contain only one failing file
        # During this phase, on average we've completed half of the work
        # So, we estimate that the total work remaining is double what we've completed
        estimatedNumTestsRemaining *= 2
      estimatedRemainingDuration = datetime.timedelta(seconds = elapsedDuration.total_seconds() * float(estimatedNumTestsRemaining) / float(numCompletedTests))
      message = "Elapsed duration: " + str(elapsedDuration) + ". Waiting for " + str(len(activeTestStatesById)) + " active subprocesses (" + str(len(availableTestStates) + len(activeTestStatesById)) + " total available jobs). " + str(self.resetTo_state.size()) + " changes left to test, should take about " + str(estimatedNumTestsRemaining) + " tests, about " + str(estimatedRemainingDuration)
      print(message)
      if self.timeoutSeconds is not None:
        # what fraction of the time is left
        remainingTimeFraction = 1.0 - (elapsedDuration.total_seconds() / self.timeoutSeconds)
        # how many jobs there will be if we add another one
        possibleNumPendingJobs = len(activeTestStatesById) + 1
        if possibleNumPendingJobs / (numCompletedTests + possibleNumPendingJobs) > remainingTimeFraction:
          # adding one more job would be likely to cause us to exceed our time limit
          timedOut = True

      if len(activeTestStatesById) > 0:
        # wait for a response from a worker
        identifier, didAcceptState, workerNewState = queue.get()
        box = activeTestStatesById[identifier]
        #print("main process received worker new state of " + str(workerNewState))
        workerStatesById[identifier] = workerNewState
        numCompletedTests += 1
        numCompletionsSinceLastPoolSizeChange += 1
        if didAcceptState:
          numConsecutiveFailures = 0
          numFailuresSinceLastSplitOrSuccess = 0
          acceptedState = box #.getAllFiles()
          #print("Succeeded : " + acceptedState.summarize() + " (job " + str(identifier) + ") at " + str(datetime.datetime.now()))
          maxRunningSize = max([state.size() for state in activeTestStatesById.values()])
          maxRelevantSize = maxRunningSize / len(activeTestStatesById)
          if acceptedState.size() < maxRelevantSize:
            print("Queuing a retest of response of size " + str(acceptedState.size()) + " from job " + str(identifier) + " because a much larger job of size " + str(maxRunningSize) + " is still running")
            probablyAcceptableStates.append(acceptedState)
          else:
            if identifier in invalidatedIds:
              # queue a retesting of this box
              print("Queuing a re-test of response from job " + str(identifier) + " due to previous invalidation. Successful state: " + str(acceptedState.summarize()))
              probablyAcceptableStates.append(acceptedState)
            else:
              # A worker discovered a nonempty change that can be made successfully; update our best accepted state
              self.onSuccess(acceptedState)
              if debug:
                # The files in self.bestState_path should exactly match what's in workPath[identifier], except for files that didn't originally exist
                if not filesStateFromTree(self.bestState_path).checkSameKeys(filesStateFromTree(self.getWorkPath(identifier)).restrictedToKeysIn(self.originalPassingState.expandedWithEmptyEntriesFor(self.originalFailingState))):
                  print("Successful state from work path " + str(identifier) + " wasn't correctly copied to bestState. Could the test command be deleting files that previously existed?")
                  sys.exit(1)
              # record that the results from any previously started process are no longer guaranteed to be valid
              for i in activeTestStatesById.keys():
                if i != identifier:
                  invalidatedIds.add(i)
              # record our first success
              if numJobsAtFirstSuccessAfterMerge is None:
                numJobsAtFirstSuccessAfterMerge = len(availableTestStates)
        else:
          if not os.path.isdir(self.sampleFailure_path):
            # save sample failure path where user can see it
            print("Saving sample failed state to " + str(self.sampleFailure_path))
            fileIo.ensureDirExists(self.sampleFailure_path)
            self.full_resetTo_state.expandedWithEmptyEntriesFor(box).withConflictsFrom(box, True).apply(self.sampleFailure_path)
          #print("Failed : " + box.summarize() + " (job " + str(identifier) + ") at " + str(datetime.datetime.now()))
          # count failures
          numConsecutiveFailures += 1
          numFailuresSinceLastSplitOrSuccess += 1
          # find any children that failed and queue a re-test of those children
          updatedChild = box.withoutDuplicatesFrom(box.withConflictsFrom(self.resetTo_state))
          if updatedChild.size() > 0:
            if numConsecutiveFailures >= 4:
              # Suppose we are trying to identify n single-file changes that cause failures
              # Suppose we have tried c changes of size s, each one of which failed
              # We conclude that n >= c
              # A mostly unbiased estimate of c as a function of n is that c = n / 2
              # Similarly, a mostly unbiased estimate of n is that n = c * 2
              # We want to choose a new number of changes to test, c2, such that running c2 tests results in efficiently identifying the relevant n changes
              # Let's set c2 = 2 * n = 2 * 2 * c
              splitFactor = 4
            else:
              # After we reach a sufficiently small change size such that some changes start passing,
              # Then we assume that we've probably narrowed down to each individual failing change,
              # And we can increase block sizes more slowly
              splitFactor = 2
            split = updatedChild.splitOnce(splitFactor)
            if len(split) > 1:
              numFailuresSinceLastSplitOrSuccess = 0
            availableTestStates += split
        # clear invalidation status
        if identifier in invalidatedIds:
          invalidatedIds.remove(identifier)
        del activeTestStatesById[identifier]
        # Check whether we've had enough failures lately to warrant checking for the possibility of dependencies among files
        if numJobsAtFirstSuccessAfterMerge is not None:
          if len(availableTestStates) > 3 * numJobsAtFirstSuccessAfterMerge:
            # It's plausible that every file in one directory depends on every file in another directory
            # If this happens, then after we delete the dependent directory, we can delete the dependency directory too
            # To make sure that we consider deleting the dependency directory, we recombine all of our states and start splitting from there
            print("#############################################################")
            print("#                                                           #")
            print("# Lots of failures since first success!!!!!!!!!!!!!!!!!!!!! #")
            print("# Recombining all states in case we uncovered a dependency! #")
            print("#                                                           #")
            print("#############################################################")
            rejoinedState = FilesState()
            for state in availableTestStates:
              rejoinedState = rejoinedState.expandedWithEmptyEntriesFor(state).withConflictsFrom(state)
            rejoinedState = rejoinedState.withoutDuplicatesFrom(self.resetTo_state)
            availableTestStates = rejoinedState.splitOnce(initialSplitSize)
            numFailuresSinceLastSplitOrSuccess = 0
            numJobsAtFirstSuccessAfterMerge = None
            numCompletionsSinceLastPoolSizeChange = 0

      # if probablyAcceptableStates has become large enough, then retest its contents too
      if len(probablyAcceptableStates) > 0 and (len(probablyAcceptableStates) >= len(activeTestStatesById) + 1 or numConsecutiveFailures >= len(activeTestStatesById) or len(activeTestStatesById) < 1):
        probablyAcceptableState = FilesState()
        for state in probablyAcceptableStates:
          probablyAcceptableState = probablyAcceptableState.expandedWithEmptyEntriesFor(state).withConflictsFrom(state)
        probablyAcceptableState = probablyAcceptableState.withoutDuplicatesFrom(self.resetTo_state)
        if probablyAcceptableState.size() > 0:
          print("Retesting " + str(len(probablyAcceptableStates)) + " previous likely successful states as a single test: " + probablyAcceptableState.summarize())
          availableTestStates = [probablyAcceptableState] + availableTestStates
        probablyAcceptableStates = []
      if len(availableTestStates) < 1 and len(activeTestStatesById) < 1:
        print("Error: no changes remain left to test. It was expected that applying all changes would fail")
        break

      # if we haven't checked everything yet, then try to queue more jobs
      if numFailuresSinceLastSplitOrSuccess < self.resetTo_state.size():
        availableTestStates.sort(reverse=True, key=FilesState.size)

        if self.maxNumJobsAtOnce != "auto":
          targetNumJobs = self.maxNumJobsAtOnce
        else:
          # If N jobs are running then wait for all N to fail before increasing the number of running jobs
            # Recalibrate the number of processes based on the system load
            systemUsageStats = cpuStats.cpu_times_percent()
            systemIdleFraction = systemUsageStats.idle / 100
            if systemIdleFraction >= 0.5:
              if numCompletionsSinceLastPoolSizeChange <= len(activeTestStatesById):
                # Not much time has passed since the previous time we changed the pool size
                targetNumJobs = len(activeTestStatesById) + 1 # just replace existing job
              else:
                # We've been using less than the target capacity for a while, so add another job
                targetNumJobs = len(activeTestStatesById) + 2 # replace existing job and add a new one
                numCompletionsSinceLastPoolSizeChange = 0
            else:
              targetNumJobs = len(activeTestStatesById) # don't replace existing job
              numCompletionsSinceLastPoolSizeChange = 0

              if targetNumJobs < 1:
                targetNumJobs = 1
            print("System idle = " + str(systemIdleFraction) + ", current num jobs = " + str(len(activeTestStatesById) + 1) + ", target num jobs = " + str(targetNumJobs))

        if timedOut:
          print("Timeout reached, not starting new jobs")
        else:
          while len(activeTestStatesById) < targetNumJobs and len(activeTestStatesById) < self.resetTo_state.size() and len(availableTestStates) > 0:
            # find next pending job
            box = availableTestStates[0]
            # find next unused job id
            jobId = 0
            while jobId in activeTestStatesById:
              jobId += 1
            # start job
            workingDir = self.getWorkPath(jobId)
            cacheDir = self.getFilesCachePath(jobId)
            if jobId in workerStatesById:
              workerPreviousState = workerStatesById[jobId]
            else:
              workerPreviousState = FilesState()
            runJobInOtherProcess(self.testScript_path, workingDir, cacheDir, workerPreviousState, self.assumeNoSideEffects, self.full_resetTo_state, box, queue, jobId)
            activeTestStatesById[jobId] = box
            availableTestStates = availableTestStates[1:]

    if timedOut:
      wasSuccessful = False
    else:
      print("double-checking results")
      wasSuccessful = True
      if not self.runnerTest(filesStateFromTree(self.bestState_path))[0]:
        message = "Error: expected best state at " + self.bestState_path + " did not pass the second time. Could the test be non-deterministic?"
        if self.assumeNoSideEffects:
          message += " (it may help to remove the --assume-no-side-effects flag)"
        if self.assumeInputStatesAreCorrect:
          message += " (it may help to remove the --assume-input-states-are-correct flag)"
        print(message)
        wasSuccessful = False

    self.cleanupTempDirs()

    print("")
    if self.targetState.size() < 1000:
      filesDescription = str(self.targetState)
    else:
      filesDescription = str(self.targetState.summarize())
    print("Done trying to transform the contents of passing path:\n " + self.originalPassingPath + "\ninto the contents of failing path:\n " + self.originalFailingPath)
    print("Of " + str(self.originalNumDifferences) + " differences, could not accept: " + filesDescription)
    print("The final accepted state can be seen at " + self.bestState_path)
    if timedOut:
      print("Note that these results might not be optimal due to reaching the timeout of " + str(self.timeoutSeconds) + " seconds")
    return wasSuccessful

def main(args):
  assumeNoSideEffects = False
  assumeInputStatesAreCorrect = False
  workPath = "/tmp/diff-filterer"
  timeoutSeconds = None
  maxNumJobsAtOnce = 1
  while len(args) > 0:
    arg = args[0]
    if arg == "--assume-no-side-effects":
      assumeNoSideEffects = True
      args = args[1:]
      continue
    if arg == "--assume-input-states-are-correct":
      assumeInputStatesAreCorrect = True
      args = args[1:]
      continue
    if arg == "--work-path":
      if len(args) < 2:
        usage()
      workPath = args[1]
      args = args[2:]
      continue
    if arg == "--num-jobs":
      if len(args) < 2:
        usage()
      val = args[1]
      if val == "auto":
        maxNumJobsAtOnce = val
      else:
        maxNumJobsAtOnce = int(val)
      args = args[2:]
      continue
    if arg == "--timeout":
      if len(args) < 2:
        usage()
      val = args[1]
      timeoutSeconds = float(val)
      args = args[2:]
      continue
    if arg == "--debug":
      global debug
      debug = True
      args = args[1:]
      continue
    if len(arg) > 0 and arg[0] == "-":
      print("Unrecognized argument: '" + arg + "'")
      usage()
    break
  if len(args) != 3:
    usage()
  passingPath = args[0]
  failingPath = args[1]
  shellCommand = args[2]
  startTime = datetime.datetime.now()
  if not os.path.exists(passingPath):
    print("Specified passing path " + passingPath + " does not exist")
    sys.exit(1)
  if not os.path.exists(failingPath):
    print("Specified failing path " + failingPath + " does not exist")
    sys.exit(1)
  success = DiffRunner(failingPath, passingPath, shellCommand, workPath, assumeNoSideEffects, assumeInputStatesAreCorrect, maxNumJobsAtOnce, timeoutSeconds).run()
  endTime = datetime.datetime.now()
  duration = endTime - startTime
  if success:
    print("Succeeded in " + str(duration))
  else:
    print("Failed in " + str(duration))
    sys.exit(1)

main(sys.argv[1:])