| #!/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-input-states-are-correct] [--allow-goal-passing] [--work-path <workpath>] [--num-jobs <count>] [--timeout <seconds>] [--debug] <passingPath> <goalPath> <shellCommand> |
| |
| diff-filterer.py attempts to transform (a copy of) the contents of <passingPath> into the contents of <goalPath> subject to the constraint that when <shellCommand> is run in that directory, it returns 0 |
| |
| OPTIONS |
| --assume-input-states-are-correct |
| Assume that <shellCommand> passes in <passingPath> and fails in <goalPath> rather than re-verifying this |
| --allow-goal-passing |
| If <goalPath> passes the test, report it as the best result rather than reporting an error. |
| Usually it's a mistake to pass a passing state as the goal path, because then the passing state is the best result. This usually means the inputs might be reversed or mistaken. It also means that the binary search is very short. |
| In some cases this can make sense if the caller hasn't already checked whether the goal state passes. |
| --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 move(self, fromPath, toPath): |
| os.rename(fromPath, toPath) |
| |
| 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 |
| |
| # returns the time at which <path> was last modified, without following symlinks |
| def getModificationTime(self, path): |
| if os.path.exists(path): |
| if os.path.islink(path): |
| # for a symlink, the last time the link itself was modified is the ctime (mtime for a broken link is undefined) |
| return os.path.getctime(path) |
| else: |
| # for a file, the last time its content was modified is the mtime |
| return os.path.getmtime(path) |
| return None |
| |
| 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() |
| |
| # 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): |
| 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): |
| fileIo.copyFile(self.referencePath, filePath) |
| |
| 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): |
| 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): |
| 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): |
| for relPath, state in self.fileStates.items(): |
| state.apply(fileIo.join(filePath, relPath)) |
| |
| 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, listEmptyDirs=False): |
| 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() |
| if listEmptyDirs: |
| newImpliedDirs = other.listImpliedDirs() |
| oldImpliedDirs = result.listImpliedDirs() |
| for impliedDir in newImpliedDirs: |
| if impliedDir not in oldImpliedDirs and impliedDir not in result.fileStates: |
| result.add(impliedDir, 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 Test in this process |
| def runJobInSameProcess(shellCommand, workPath, previousTestState, clean, fullTestState, description, twoWayPipe): |
| job = Test(shellCommand, workPath, previousTestState, clean, fullTestState, description, twoWayPipe) |
| job.runAndReport() |
| |
| # starts a Test in a new process |
| def runJobInOtherProcess(shellCommand, workPath, previousTestState, clean, fullTestState, description, queue, identifier): |
| parentWriter, childReader = multiprocessing.Pipe() |
| childInfo = TwoWayPipe(childReader, queue, identifier) |
| process = multiprocessing.Process(target=runJobInSameProcess, args=(shellCommand, workPath, previousTestState, clean, fullTestState, description, 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 Test(object): |
| def __init__(self, shellCommand, workPath, previousTestState, clean, fullTestState, description, twoWayPipe): |
| # the test to run |
| self.shellCommand = shellCommand |
| # directory to run the test in |
| self.workPath = workPath |
| # The previous state that we were asked to test. If the test command didn't modify any files, then our working directly would exactly match this state |
| self.previousTestState = previousTestState |
| # whether to reset the worker's state to match the target state exactly |
| self.clean = clean |
| # the state to test |
| self.fullTestState = fullTestState |
| # description of changes |
| self.description = description |
| self.pipe = twoWayPipe |
| |
| def runAndReport(self): |
| succeeded = False |
| postState = None |
| try: |
| succeeded = self.run() |
| finally: |
| print("^" * 100) |
| self.pipe.writerQueue.put((self.pipe.identifier, succeeded, self.clean)) |
| |
| def run(self): |
| print("#" * 100) |
| print("Checking " + self.description + " at " + str(datetime.datetime.now())) |
| |
| if self.clean: |
| # update all files to match the target state |
| currentState = filesStateFromTree(self.workPath) |
| self.fullTestState.expandedWithEmptyEntriesFor(currentState, True).withoutDuplicatesFrom(currentState).apply(self.workPath) |
| else: |
| # just apply the difference from previousTestState to full_resetTo_state |
| self.fullTestState.expandedWithEmptyEntriesFor(self.previousTestState).withoutDuplicatesFrom(self.previousTestState).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() |
| |
| # report results |
| if returnCode == 0: |
| print("Passed: " + self.description + " at " + str(datetime.datetime.now()) + " in " + str(duration) + "s") |
| return True |
| else: |
| print("Failed: " + self.description + " at " + str(datetime.datetime.now()) + " in " + str(duration) + "s") |
| return False |
| |
| # keeps track of a plan for running a Test |
| class Job(object): |
| def __init__(self, testState, ancestorSucceeded): |
| self.testState = testState |
| self.ancestorSucceeded = ancestorSucceeded |
| |
| def size(self): |
| return self.testState.size() |
| |
| # 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, assumeInputStatesAreCorrect, allowGoalPassing, 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.assumeInputStatesAreCorrect = assumeInputStatesAreCorrect |
| self.allowGoalPassing = allowGoalPassing |
| 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) |
| |
| def runnerTest(self, testState, timeout = None): |
| self.cleanupTempDirs() |
| workPath = self.getWorkPath(0) |
| 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: |
| 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) |
| self.full_resetTo_state = self.full_resetTo_state.expandedWithEmptyEntriesFor(delta).withConflictsFrom(delta) |
| # Update results path for the user to look at |
| if os.path.exists(self.bestState_path): |
| # The previous results are still there, so we just apply the difference between the previous and new best results |
| delta.apply(self.bestState_path) |
| else: |
| # The previous results are missing (most likely moved/deleted by the user) so we save them again |
| self.full_resetTo_state.apply(self.bestState_path) |
| 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 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]: |
| if self.allowGoalPassing: |
| print("\nGiven goal state at " + self.originalFailingPath + " passes, so it is the best result") |
| self.cleanupTempDirs() |
| fileIo.removePath(self.bestState_path) |
| self.originalFailingState.apply(self.bestState_path) |
| return True |
| print("\nGiven goal state at " + self.originalFailingPath + " does not fail! Pass --allow-goal-passing if this is intentional") |
| 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() |
| activeJobsById = {} |
| workerStatesById = {} |
| consecutiveIncrementalBuildsById = {} |
| initialSplitSize = 2 |
| if self.maxNumJobsAtOnce != "auto" and self.maxNumJobsAtOnce > 2: |
| initialSplitSize = self.maxNumJobsAtOnce |
| availableJobs = [Job(testState, False) for testState in 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 |
| summaryLogPath = os.path.join(self.workPath, "diff-filterer.log") |
| summaryLog = open(summaryLogPath, "w") |
| summaryLog.write("diff-filterer.py starting at " + str(datetime.datetime.now())) |
| summaryLog.flush() |
| # continue until all files fail and no jobs are running |
| while (numFailuresSinceLastSplitOrSuccess < self.resetTo_state.size() and not timedOut) or len(activeJobsById) > 0: |
| # display status message |
| now = datetime.datetime.now() |
| elapsedDuration = now - start |
| minNumTestsRemaining = sum([math.log(job.testState.size(), 2) + 1 for job in availableJobs + list(activeJobsById.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(activeJobsById)) + " active subprocesses (" + str(len(availableJobs) + len(activeJobsById)) + " 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(activeJobsById) + 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(activeJobsById) > 0: |
| # wait for a response from a worker |
| identifier, didAcceptState, clean = queue.get() |
| job = activeJobsById[identifier] |
| numCompletedTests += 1 |
| numCompletionsSinceLastPoolSizeChange += 1 |
| if didAcceptState: |
| numConsecutiveFailures = 0 |
| numFailuresSinceLastSplitOrSuccess = 0 |
| acceptedState = job.testState |
| maxRunningSize = max([job.testState.size() for job in activeJobsById.values()]) |
| maxRelevantSize = maxRunningSize / len(activeJobsById) |
| 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: |
| print("Queuing a retest of response from job " + str(identifier) + " due to previous invalidation. Successful state: " + str(acceptedState.summarize())) |
| probablyAcceptableStates.append(acceptedState) |
| else: |
| if not clean: |
| print("Queuing a clean retest of incremental success from job " + str(identifier)) |
| probablyAcceptableStates.append(acceptedState) |
| else: |
| print("Accepting clean success from job " + str(identifier)) |
| summaryLog.write("Succeeded : " + acceptedState.summarize() + " (job " + str(identifier) + ") at " + str(datetime.datetime.now()) + "\n") |
| summaryLog.flush() |
| # 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 activeJobsById.keys(): |
| if i != identifier: |
| invalidatedIds.add(i) |
| # record our first success |
| if numJobsAtFirstSuccessAfterMerge is None: |
| numJobsAtFirstSuccessAfterMerge = len(availableJobs) + len(activeJobsById) |
| else: |
| testState = job.testState |
| 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)) |
| # write to a temporary directory so if a user looks at this path while we're writing, they don't see incomplete results |
| tempPath = self.sampleFailure_path + ".temp" |
| fileIo.removePath(tempPath) |
| fileIo.ensureDirExists(tempPath) |
| self.full_resetTo_state.expandedWithEmptyEntriesFor(testState).withConflictsFrom(testState, True).apply(tempPath) |
| # rename temporary directory |
| if os.path.exists(tempPath): |
| fileIo.move(tempPath, self.sampleFailure_path) |
| # count failures |
| numConsecutiveFailures += 1 |
| numFailuresSinceLastSplitOrSuccess += 1 |
| # find any children that failed and queue a re-test of those children |
| updatedChild = testState.withoutDuplicatesFrom(testState.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 |
| for testState in split: |
| availableJobs.append(Job(testState, job.ancestorSucceeded)) |
| # clear invalidation status |
| if identifier in invalidatedIds: |
| invalidatedIds.remove(identifier) |
| del activeJobsById[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(availableJobs) > 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 (" + str(len(availableJobs)) + " available jobs) since first success (" + str(numJobsAtFirstSuccessAfterMerge) + ")!") |
| print("# Recombining all states in case we uncovered a dependency! #") |
| print("# #") |
| print("#############################################################") |
| rejoinedState = FilesState() |
| for job in availableJobs: |
| state = job.testState |
| rejoinedState = rejoinedState.expandedWithEmptyEntriesFor(state).withConflictsFrom(state) |
| rejoinedState = rejoinedState.withoutDuplicatesFrom(self.resetTo_state) |
| availableJobs = [Job(testState, False) for testState in 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(activeJobsById) + 1 or numConsecutiveFailures >= len(activeJobsById) or len(activeJobsById) < 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()) |
| availableJobs = [Job(probablyAcceptableState, True)] + availableJobs |
| probablyAcceptableStates = [] |
| if len(availableJobs) < 1 and len(activeJobsById) < 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(): |
| availableJobs.sort(reverse=True, key=Job.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(activeJobsById): |
| # Not much time has passed since the previous time we changed the pool size |
| targetNumJobs = len(activeJobsById) + 1 # just replace existing job |
| else: |
| # We've been using less than the target capacity for a while, so add another job |
| targetNumJobs = len(activeJobsById) + 2 # replace existing job and add a new one |
| numCompletionsSinceLastPoolSizeChange = 0 |
| else: |
| targetNumJobs = len(activeJobsById) # don't replace existing job |
| numCompletionsSinceLastPoolSizeChange = 0 |
| |
| if targetNumJobs < 1: |
| targetNumJobs = 1 |
| print("System idle = " + str(systemIdleFraction) + ", current num jobs = " + str(len(activeJobsById) + 1) + ", target num jobs = " + str(targetNumJobs)) |
| |
| if timedOut: |
| print("Timeout reached, not starting new jobs") |
| else: |
| while len(activeJobsById) < targetNumJobs and len(activeJobsById) < self.resetTo_state.size() and len(availableJobs) > 0: |
| # find next pending job |
| job = availableJobs[0] |
| # find next unused job id |
| workerId = 0 |
| while workerId in activeJobsById: |
| workerId += 1 |
| # start job |
| workingDir = self.getWorkPath(workerId) |
| if workerId in workerStatesById: |
| workerPreviousState = workerStatesById[workerId] |
| else: |
| workerPreviousState = FilesState() |
| testState = job.testState |
| |
| # If job.ancestorSucceeded, then this job came from another job that succeeded (it's either the union of several jobs that succeeded, or a piece of a job that succeeded). |
| # However, if we get here, then this job failed. |
| # So, joining or splitting this job's successful ancestor(s) created a failed job (this one). |
| # So, in the future it's also likely that we'll find jobs that succeed on their own but if joined will fail. |
| # So, in the future we don't want to join all successful jobs (because that could be likely to introduce a failure). |
| # Any successful jobs in the future that we don't accept, we join together. |
| # So, we want to accept a successful job soon. |
| # We can only accept the results of clean builds (because for incremental builds we're not sure that the results are reliable) |
| # So, if job.ancestorSucceeded, we make the descendants of this job be clean |
| # |
| # Also, we want each worker to occasionally use a new state in case so that incremental errors can't remain forever |
| clean = job.ancestorSucceeded |
| if workerId in consecutiveIncrementalBuildsById: |
| consecutiveIncrementalBuilds = consecutiveIncrementalBuildsById[workerId] |
| if consecutiveIncrementalBuilds >= 10: |
| clean = True |
| consecutiveIncrementalBuilds = 0 |
| else: |
| consecutiveIncrementalBuilds = 0 |
| # Also, if this worker hasn't run any jobs yet, then we don't expect it to have any leftover files, so an incremental test is essentially equivalent to a clean test anyway |
| # We ask the worker to run a clean test so that if it succeeds, we can detect that the success started from a clean state |
| clean = True |
| consecutiveIncrementalBuildsById[workerId] = 0 |
| fullTestState = self.full_resetTo_state.expandedWithEmptyEntriesFor(testState).withConflictsFrom(testState) |
| description = testState.summarize() + " (job " + str(workerId) + ", " |
| if clean: |
| description += "clean" |
| else: |
| description += "incremental" |
| description += ")" |
| runJobInOtherProcess(self.testScript_path, workingDir, workerPreviousState, clean, fullTestState, description, queue, workerId) |
| activeJobsById[workerId] = job |
| workerStatesById[workerId] = fullTestState |
| availableJobs = availableJobs[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.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) |
| print("Ran " + str(numCompletedTests) + " tests") |
| 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): |
| assumeInputStatesAreCorrect = False |
| allowGoalPassing = False |
| workPath = "/tmp/diff-filterer" |
| timeoutSeconds = None |
| maxNumJobsAtOnce = 1 |
| while len(args) > 0: |
| arg = args[0] |
| if arg == "--assume-input-states-are-correct": |
| assumeInputStatesAreCorrect = True |
| args = args[1:] |
| continue |
| if arg == "--allow-goal-passing": |
| allowGoalPassing = 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, assumeInputStatesAreCorrect, allowGoalPassing, 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:]) |
