tb3: tinderbox coordinator

tb3 is an robust asyncronous tinderbox coodinator allowing multiple builders to
coordinate work in a distributed fashion.

Change-Id: I5364dbb25cebd160a967995e2c96fad8fddd7e0b
Reviewed-on: https://gerrit.libreoffice.org/4166
Reviewed-by: Thorsten Behrens <tbehrens@suse.com>
Tested-by: Thorsten Behrens <tbehrens@suse.com>

14 files changed, 843 insertions, 0 deletions

diff --git a/tb3/Makefile b/tb3/Makefile
new file mode 100644
index 0000000..b03b70a
--- /dev/null
+++ b/tb3/Makefile
@@ -0,0 +1,17 @@
+define runtest
+./tests/tb3/$(1).py
+endef
+
+test: test-repostate test-scheduler test-cli
+	@true
+.PHONY: test
+
+test-%:
+	$(call runtest,$*)
+
+test-cli:
+	./tests/tb3-cli.py
+
+.PHONY: test-%
+
+# vim: set noet sw=4 ts=4:
diff --git a/tb3/dist-packages/tb3/__init__.py b/tb3/dist-packages/tb3/__init__.py
new file mode 100644
index 0000000..c7a73e3
--- /dev/null
+++ b/tb3/dist-packages/tb3/__init__.py
@@ -0,0 +1,10 @@
+#!/usr/bin/env python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+# vim: set et sw=4 ts=4:
diff --git a/tb3/dist-packages/tb3/repostate.py b/tb3/dist-packages/tb3/repostate.py
new file mode 100644
index 0000000..dd4e877
--- /dev/null
+++ b/tb3/dist-packages/tb3/repostate.py
@@ -0,0 +1,212 @@
+#! /usr/bin/env python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+import sh
+import json
+import datetime
+
+class StateEncoder(json.JSONEncoder):
+    def default(self, obj):
+        if isinstance(obj, datetime.datetime):
+            return [ '__datetime__', (obj - datetime.datetime(1970,1,1)).total_seconds() ]
+        elif isinstance(obj, datetime.timedelta):
+            return [ '__timedelta__', obj.total_seconds() ]
+        return json.JSONEncoder.default(self, obj)
+
+class StateDecoder(json.JSONDecoder):
+    def decode(self, s):
+        obj = super(StateDecoder, self).decode(s)
+        for (key, value) in obj.iteritems():
+            if isinstance(value, list):
+                if value[0] == '__datetime__':
+                    obj[key] = datetime.datetime.utcfromtimestamp(value[1])
+                elif value[0] == '__timedelta__':
+                    obj[key] = datetime.timedelta(float(value[1]))
+        return obj
+
+class RepoState:
+    def __init__(self, platform, branch, repo):
+        self.platform = platform
+        self.branch = branch
+        self.repo = repo
+        self.git = sh.git.bake(_cwd=repo)
+    def __str__(self):
+        (last_good, first_bad, last_bad) = (self.get_last_good(), self.get_first_bad(), self.get_last_bad())
+        result = 'State of repository %s on branch %s for platform %s' % (self.repo, self.branch, self.platform)
+        result += '\nhead            : %s' % (self.get_head())
+        if last_good:
+            result += '\nlast good commit: %s (%s-%d)' % (last_good, self.branch, self.__distance_to_branch_head(last_good))
+        if first_bad:
+            result += '\nfirst bad commit: %s (%s-%d)' % (first_bad, self.branch, self.__distance_to_branch_head(first_bad))
+        if last_bad:
+            result += '\nlast  bad commit: %s (%s-%d)' % (last_bad, self.branch, self.__distance_to_branch_head(last_bad))
+        return result
+    def __resolve_ref(self, refname):
+        try:
+            return self.git('show-ref', refname).split(' ')[0]
+        except sh.ErrorReturnCode_1:
+            return None
+    def __distance_to_branch_head(self, commit):
+        return int(self.git('rev-list', '--count', '%s..%s' % (commit, self.branch)))
+    def __get_fullref(self, name):
+        return 'refs/tb3/state/%s/%s/%s' % (self.platform, self.branch, name)
+    def __set_ref(self, refname, target):
+        return self.git('update-ref', refname, target)
+    def __clear_ref(self, refname):
+        return self.git('update-ref', '-d', self.__get_fullref(refname))
+    def sync(self):
+        self.git('fetch', all=True)
+    def get_last_good(self):
+        return self.__resolve_ref(self.__get_fullref('last_good'))
+    def set_last_good(self, target):
+        self.__set_ref(self.__get_fullref('last_good'),target)
+    def clear_last_good(self):
+        self.__clear_ref('last_good')
+    def get_first_bad(self):
+        return self.__resolve_ref(self.__get_fullref('first_bad'))
+    def set_first_bad(self, target):
+        self.__set_ref(self.__get_fullref('first_bad'), target)
+    def clear_first_bad(self):
+        self.__clear_ref('first_bad')
+    def get_last_bad(self):
+        return self.__resolve_ref(self.__get_fullref('last_bad'))
+    def set_last_bad(self, target):
+        self.__set_ref(self.__get_fullref('last_bad'), target)
+    def clear_last_bad(self):
+        self.__clear_ref('last_bad')
+    def get_head(self):
+        return self.__resolve_ref('refs/heads/%s' % self.branch)
+    def get_last_build(self):
+        (last_bad, last_good) = (self.get_last_bad(), self.get_last_good())
+        if not last_bad:
+            return last_good
+        if not last_good:
+            return last_bad
+        if self.git('merge-base', '--is-ancestor', last_good, last_bad, _ok_code=[0,1]).exit_code == 0:
+            return last_bad
+        return last_good
+
+class CommitState:
+    STATES=['BAD', 'GOOD', 'ASSUMED_GOOD', 'ASSUMED_BAD', 'POSSIBLY_BREAKING', 'POSSIBLY_FIXING', 'UNKNOWN', 'RUNNING', 'BREAKING']
+    def __init__(self, state='UNKNOWN', started=None, builder=None, estimated_duration=None, finished=None, artifactreference=None):
+        if not state in CommitState.STATES:
+            raise AttributeError
+        self.state = state
+        self.builder = builder
+        self.started = started
+        self.finished = finished
+        self.estimated_duration = estimated_duration
+        self.artifactreference = artifactreference
+    def __eq__(self, other):
+        if not hasattr(other, '__dict__'):
+            return False
+        return self.__dict__ == other.__dict__
+    def __str__(self):
+        result = 'started on %s with builder %s and finished on %s -- artifacts at %s, state: %s' % (self.started, self.builder, self.finished, self.artifactreference, self.state)
+        if self.started and self.finished:
+            result += ' (took %s)' % (self.finished-self.started)
+        if self.estimated_duration:
+            result += ' (estimated %s)' % (self.estimated_duration)
+        return result
+
+class RepoHistory:
+    def __init__(self, platform, repo):
+        self.platform = platform
+        self.git = sh.git.bake(_cwd=repo)
+        self.gitnotes = sh.git.bake('--no-pager', 'notes', '--ref', 'core.notesRef=refs/notes/tb3/history/%s' % self.platform, _cwd=repo)
+    def get_commit_state(self, commit):
+        commitstate_json = str(self.gitnotes.show(commit, _ok_code=[0,1]))
+        commitstate = CommitState()
+        if len(commitstate_json):
+            commitstate.__dict__ = json.loads(commitstate_json, cls=StateDecoder)
+        return commitstate
+    def get_recent_commit_states(self, branch, count):
+        commits = self.git('rev-list', '%s~%d..%s' % (branch, count, branch)).split('\n')[:-1]
+        return [(c, self.get_commit_state(c)) for c in commits]
+    def set_commit_state(self, commit, commitstate):
+        self.gitnotes.add(commit, force=True, m=json.dumps(commitstate.__dict__, cls=StateEncoder)) 
+    def update_inner_range_state(self, begin, end, commitstate, skipstates):
+        for commit in self.git('rev-list', '%s..%s' % (begin, end)).split('\n')[1:-1]:
+            oldstate = self.get_commit_state(commit)
+            if not oldstate.state in skipstates:
+                self.set_commit_state(commit, commitstate)
+
+class RepoStateUpdater:
+    def __init__(self, platform, branch, repo):
+        (self.platform, self.branch) = (platform, branch)
+        self.git = sh.git.bake(_cwd=repo)
+        self.repostate = RepoState(platform, branch, repo)
+        self.repohistory = RepoHistory(platform, repo)
+    def __update(self, commit, last_good_state, last_bad_state, forward, bisect_state):
+        last_build = self.repostate.get_last_build()
+        last_good = self.repostate.get_last_good()
+        if last_build and last_good:
+            if self.git('merge-base', '--is-ancestor', last_build, commit, _ok_code=[0,1]).exit_code == 0:
+                rangestate = last_bad_state
+                if last_build == last_good:
+                    rangestate = last_good_state
+                self.repohistory.update_inner_range_state(last_build, commit, CommitState(rangestate), ['GOOD', 'BAD'])
+            else:
+                first_bad = self.repostate.get_first_bad()
+                assert(self.git('merge-base', '--is-ancestor', last_good, commit, _ok_code=[0,1]).exit_code == 0)
+                assert(self.git('merge-base', '--is-ancestor', commit, first_bad, _ok_code=[0,1]).exit_code == 0)
+                assume_range = (last_good, commit)
+                if forward:
+                    assume_range = (commit, first_bad)
+                self.repohistory.update_inner_range_state(assume_range[0], assume_range[1], CommitState(bisect_state), ['GOOD', 'BAD'])
+    def __finalize_bisect(self):
+        (first_bad, last_bad) = (self.repostate.get_first_bad(), self.repostate.get_last_bad())
+        if not first_bad:
+            #assert(self.repostate.get_last_bad() is None)
+            return
+        last_good = self.repostate.get_last_good()
+        if not last_good:
+            #assert(self.repostate.get_last_bad() is None)
+            return
+        if last_good in self.git('rev-list', first_bad, max_count=2).split()[1:]:
+            commitstate = self.repohistory.get_commit_state(first_bad)
+            commitstate.state = 'BREAKING'
+            self.repohistory.set_commit_state(first_bad, commitstate)
+        if self.git('merge-base', '--is-ancestor', last_bad, last_good, _ok_code=[0,1]).exit_code == 0:
+            self.repostate.clear_first_bad()
+            self.repostate.clear_last_bad()
+    def set_scheduled(self, commit, builder, estimated_duration):
+        # FIXME: dont hardcode limit
+        estimated_duration = max(estimated_duration, datetime.timedelta(hours=4))
+        commitstate = CommitState('RUNNING', datetime.datetime.now(), builder, estimated_duration)
+        self.repohistory.set_commit_state(commit, commitstate)
+    def set_finished(self, commit, builder, state, artifactreference):
+        if not state in ['GOOD', 'BAD']:
+            raise AttributeError
+        commitstate = self.repohistory.get_commit_state(commit)
+        #assert(commitstate.state == 'RUNNING')
+        #assert(commitstate.builder == builder)
+        # we want to keep a failure around, even if we have a success somehow
+        if not commitstate.state in ['BAD'] or state in ['BAD']:
+            commitstate.state = state
+            commitstate.finished = datetime.datetime.now()
+            commitstate.builder = builder
+            commitstate.estimated_duration = None
+            commitstate.artifactreference = artifactreference
+            self.repohistory.set_commit_state(commit, commitstate)
+            if state == 'GOOD':
+                last_good = self.repostate.get_last_good()
+                if last_good:
+                    self.__update(commit, 'ASSUMED_GOOD', 'POSSIBLY_FIXING', False, 'ASSUMED_GOOD')
+                if not last_good or self.git('merge-base', '--is-ancestor', last_good, commit, _ok_code=[0,1]).exit_code == 0:
+                    self.repostate.set_last_good(commit)
+            else:
+                self.__update(commit, 'POSSIBLY_BREAKING', 'ASSUMED_BAD', True, 'ASSUMED_BAD')
+                (first_bad, last_bad) = (self.repostate.get_first_bad(), self.repostate.get_last_bad())
+                if not first_bad or self.git('merge-base', '--is-ancestor', commit, first_bad, _ok_code=[0,1]).exit_code == 0:
+                    self.repostate.set_first_bad(commit)
+                if not last_bad:
+                    self.repostate.set_last_bad(commit)
+            self.__finalize_bisect()
+# vim: set et sw=4 ts=4:
diff --git a/tb3/dist-packages/tb3/scheduler.py b/tb3/dist-packages/tb3/scheduler.py
new file mode 100644
index 0000000..e3accab
--- /dev/null
+++ b/tb3/dist-packages/tb3/scheduler.py
@@ -0,0 +1,105 @@
+#!/usr/bin/env python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+import sh
+import math
+import tb3.repostate
+import functools
+import datetime
+
+class Proposal:
+    def __init__(self, score, commit, scheduler):
+        (self.score, self.commit, self.scheduler) = (score, commit, scheduler)
+    def __repr__(self):
+        return 'Proposal(%f, %s, %s)' % (self.score, self.commit, self.scheduler)
+    def __cmp__(self, other):
+        return other.score - self.score
+
+class Scheduler:
+    def __init__(self, platform, branch, repo):
+        self.branch = branch
+        self.repo = repo
+        self.platform = platform
+        self.repostate = tb3.repostate.RepoState(self.platform, self.branch, self.repo)
+        self.repohistory = tb3.repostate.RepoHistory(self.platform, self.repo)
+        self.git = sh.git.bake(_cwd=repo)
+    def count_commits(self, start, to):
+        return int(self.git('rev-list', '%s..%s' % (start, to), count=True))
+    def get_commits(self, begin, end):
+        commits = []
+        for commit in self.git('rev-list', '%s..%s' % (begin, end)).strip('\n').split('\n'):
+            if len(commit) == 40:
+                commits.append( (len(commits), commit, self.repohistory.get_commit_state(commit)) )
+        return commits
+    def norm_results(self, proposals):
+        maxscore = 0
+        #maxscore = functools.reduce( lambda x,y: max(x.score, y.score), proposals)
+        for proposal in proposals:
+            maxscore = max(maxscore, proposal.score)
+        if maxscore > 0:
+            for proposal in proposals:
+                proposal.score = proposal.score / maxscore * len(proposals)
+    def dampen_running_commits(self, commits, proposals, time):
+        for commit in commits:
+            if commit[2].state == 'RUNNING':
+                running_time = max(datetime.timedelta(), time - commit[2].started)
+                timedistance = running_time.total_seconds() / commit[2].estimated_duration.total_seconds()
+                for idx in range(len(proposals)):
+                    proposals[idx].score *= 1-1/((commit[0]-idx+timedistance)**2+1)
+    def get_proposals(self, time):
+        return [(0, None, self.__class__.__name__)]
+
+class HeadScheduler(Scheduler):
+    def get_proposals(self, time):
+        head = self.repostate.get_head()
+        last_build = self.repostate.get_last_build()
+        proposals = []
+        if not last_build is None:
+            commits = self.get_commits(last_build, head)
+            for commit in commits:
+                proposals.append(Proposal(1-1/((len(commits)-float(commit[0]))**2+1), commit[1], self.__class__.__name__))
+            self.dampen_running_commits(commits, proposals, time)
+        else:
+            proposals.append(Proposal(float(1), head, self.__class__.__name__))
+        self.norm_results(proposals)
+        return proposals
+
+class BisectScheduler(Scheduler):
+    def __init__(self, platform, branch, repo):
+        Scheduler.__init__(self, platform, branch, repo)
+    def get_proposals(self, time):
+        last_good = self.repostate.get_last_good()
+        first_bad = self.repostate.get_first_bad()
+        if last_good is None or first_bad is None:
+            return []
+        commits = self.get_commits(last_good, '%s^' % first_bad)
+        proposals = []
+        for commit in commits:
+            proposals.append(Proposal(1.0, commit[1], self.__class__.__name__))
+        for idx in range(len(proposals)):
+            proposals[idx].score *= (1-1/(float(idx)**2+1)) * (1-1/((float(idx-len(proposals)))**2+1))
+        self.dampen_running_commits(commits, proposals, time)
+        self.norm_results(proposals)
+        return proposals
+
+class MergeScheduler(Scheduler):
+    def __init__(self, platform, branch, repo):
+        Scheduler.__init__(self, platform, branch, repo)
+        self.schedulers = []
+    def add_scheduler(self, scheduler, weight=1):
+        self.schedulers.append((weight, scheduler))
+    def get_proposals(self, time):
+        proposals = []
+        for scheduler in self.schedulers:
+            new_proposals = scheduler[1].get_proposals(time)
+            for proposal in new_proposals:
+                proposal.score *= scheduler[0]
+                proposals.append(proposal)
+        return sorted(proposals)
+# vim: set et sw=4 ts=4:
diff --git a/tb3/tb3 b/tb3/tb3
new file mode 100755
index 0000000..8a7c4ba
--- /dev/null
+++ b/tb3/tb3
@@ -0,0 +1,137 @@
+#!/usr/bin/python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+import argparse
+import datetime
+import json
+import os.path
+import sys
+
+sys.path.append('./dist-packages')
+import tb3.repostate
+import tb3.scheduler
+
+updater = None
+def get_updater(parms):
+    global updater
+    if not updater:
+        updater = tb3.repostate.RepoStateUpdater(parms['platform'], parms['branch'], parms['repo'])
+    return updater
+
+repostate = None
+def get_repostate(parms):
+    global repostate
+    if not repostate:
+        repostate = tb3.repostate.RepoState(parms['platform'], parms['branch'], parms['repo'])
+    return repostate
+
+def sync(parms):
+    get_repostate(parms).sync()
+    
+def set_commit_finished(parms):
+    get_updater(parms).set_finished(parms['set_commit_finished'], parms['builder'], parms['result'].upper(), parms['result_reference'])
+
+def set_commit_running(parms):
+    get_updater(parms).set_scheduled(parms['set_commit_running'], parms['builder'], parms['estimated_duration'])
+
+def show_state(parms):
+    if parms['format'] == 'json':
+        raise NotImplementedError
+    print(get_repostate(parms))
+    
+def show_history(parms):
+    if parms['format'] == 'json':
+        raise NotImplementedError
+    history = tb3.repostate.RepoHistory(parms['platform'], parms['repo'])
+    for (commit, state) in history.get_recent_commit_states(parms['branch'], parms['history_count']):
+        print("%s %s" % (commit, state))
+
+def show_proposals(parms):
+    merge_scheduler = tb3.scheduler.MergeScheduler(parms['platform'], parms['branch'], parms['repo'])
+    merge_scheduler.add_scheduler(tb3.scheduler.HeadScheduler(parms['platform'], parms['branch'], parms['repo']), parms['head_weight'])
+    merge_scheduler.add_scheduler(tb3.scheduler.BisectScheduler(parms['platform'], parms['branch'], parms['repo']), parms['bisect_weight'])
+    proposals = merge_scheduler.get_proposals(datetime.datetime.now())
+    if parms['format'] == 'text':
+        print('')
+        print('Proposals:')
+        for proposal in proposals:
+            print(proposals)
+    else:
+        print(json.dumps([p.__dict__ for p in proposals]))
+
+def execute(parms):
+    if type(parms['estimated_duration']) is float:
+        parms['estimated_duration'] = datetime.timedelta(minutes=parms['estimated_duration'])
+    if parms['sync']:
+        sync(parms)
+    if parms['set_commit_finished']:
+        set_commit_finished(parms)
+    if parms['set_commit_running']:
+        set_commit_running(parms)
+    if parms['show_state']:
+        show_state(parms)
+    if parms['show_history']:
+        show_history(parms)
+    if parms['show_proposals']:
+        show_proposals(parms)
+
+if __name__ == '__main__':
+    commandname = os.path.basename(sys.argv[0])
+    fullcommand = False
+    parser = argparse.ArgumentParser(description='tinderbox coordinator')
+    set_commit_finished_only = ' (only for --set-commit-finished)'
+    set_commit_running_only = ' (only for --set-commit-running)'
+    show_proposals_only = '(only for --show-proposals)'
+    show_history_only = '(only for --show-history)'
+    if commandname == 'tb3-sync':
+        pass
+    elif commandname == 'tb3-set-commit-finished':
+        set_commit_finished_only = ''
+        parser.add_argument('set-commit-finished', nargs=1, help='the commit to set the state for')
+    elif commandname == 'tb3-set-commit-running':
+        set_commit_running_only = ''
+        parser.add_argument('set-commit-running', nargs=1, help='commit to set to state running')
+    elif commandname == 'tb3-show-state':
+        pass
+    elif commandname == 'tb3-show-history':
+        show_history_only = ''
+    elif commandname == 'tb3-show-proposals':
+        show_proposals_only = ''
+    else:
+        fullcommand = True
+    parser.add_argument('--repo', help='location of the LibreOffice core git repository', required=True)
+    parser.add_argument('--platform', help='platform for which coordination is requested', required=True)
+    parser.add_argument('--branch', help='branch for which coordination is requested', required=True)
+    parser.add_argument('--builder', help='name of the build machine interacting with the coordinator', required=True)
+    if fullcommand:
+        parser.add_argument('--sync', help='syncs the repository from its origin', action='store_true')
+        parser.add_argument('--set-commit-finished', help='set the result for this commit')
+        parser.add_argument('--set-commit-running', help='set this commit to state running')
+        parser.add_argument('--show-state', help='shows the current repository state (text only for now)', action='store_true')
+        parser.add_argument('--show-history', help='shows the current build proposals', action='store_true')
+        parser.add_argument('--show-proposals', help='shows the current build proposals', action='store_true')
+    if fullcommand or commandname == 'tb3-set-commit-running':
+        parser.add_argument('--estimated-duration', help='the estimated time to complete in minutes (default: 120)%s' % set_commit_running_only, type=float, default=120.0)
+    if fullcommand or commandname == 'tb3-set-commit-finished':
+        parser.add_argument('--result', help='the result to store%s' % set_commit_finished_only, choices=['good','bad'], default='bad', required=not fullcommand)
+        parser.add_argument('--result-reference', help='the result reference (a string) to store%s' % set_commit_finished_only, default='')
+    if fullcommand or commandname == 'tb3-show-history':
+        parser.add_argument('--history-count', help='number of commits to show (default: 50)%s' % show_history_only, type=int, default=50)
+    if fullcommand or commandname == 'tb3-show-proposals':
+        parser.add_argument('--head-weight', help='set scoring weight for head (default: 1.0)%s' % show_proposals_only, type=float, default=1.0)
+        parser.add_argument('--bisect-weight', help='set scoring weight for bisection (default: 1.0)%s' % show_proposals_only, type=float, default=1.0)
+    if fullcommand or commandname == 'tb3-show-proposals' or commandname == 'tb3-show-history':
+        parser.add_argument('--format', help='set format for proposals and history (default: text)', choices=['text', 'json'], default='text')
+    args = vars(parser.parse_args())
+    if not fullcommand:
+        args['sync'] = commandname == 'tb3-sync'
+        args['show_proposals'] = commandname == 'tb3-show-proposals'
+        args['show_state'] = commandname == 'tb3-show-state'
+    execute(args)
+    
+# vim: set et sw=4 ts=4:
diff --git a/tb3/tb3-set-commit-finished b/tb3/tb3-set-commit-finished
new file mode 120000
index 0000000..f130a9b
--- /dev/null
+++ b/tb3/tb3-set-commit-finished
@@ -0,0 +1 @@
+tb3
\ No newline at end of file
diff --git a/tb3/tb3-set-commit-running b/tb3/tb3-set-commit-running
new file mode 120000
index 0000000..f130a9b
--- /dev/null
+++ b/tb3/tb3-set-commit-running
@@ -0,0 +1 @@
+tb3
\ No newline at end of file
diff --git a/tb3/tb3-show-history b/tb3/tb3-show-history
new file mode 120000
index 0000000..f130a9b
--- /dev/null
+++ b/tb3/tb3-show-history
@@ -0,0 +1 @@
+tb3
\ No newline at end of file
diff --git a/tb3/tb3-show-proposals b/tb3/tb3-show-proposals
new file mode 120000
index 0000000..f130a9b
--- /dev/null
+++ b/tb3/tb3-show-proposals
@@ -0,0 +1 @@
+tb3
\ No newline at end of file
diff --git a/tb3/tb3-show-state b/tb3/tb3-show-state
new file mode 120000
index 0000000..f130a9b
--- /dev/null
+++ b/tb3/tb3-show-state
@@ -0,0 +1 @@
+tb3
\ No newline at end of file
diff --git a/tb3/tests/helpers.py b/tb3/tests/helpers.py
new file mode 100755
index 0000000..821882f
--- /dev/null
+++ b/tb3/tests/helpers.py
@@ -0,0 +1,44 @@
+#! /usr/bin/env python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+# vim: set et sw=4 ts=4:
+import os.path
+import sh
+import tempfile
+
+def createTestRepo():
+    testdir = tempfile.mkdtemp()
+    git = sh.git.bake('--no-pager',_cwd=testdir)
+    git.init()
+    touch = sh.touch.bake(_cwd=testdir)
+    for commit in range(0,10):
+        touch('commit%d' % commit)
+        git.add('commit%d' % commit)
+        git.commit('.', '-m', 'commit %d' % commit)
+        if commit == 0:
+            git.tag('pre-branchoff-1')
+        elif commit == 3:
+            git.tag('pre-branchoff-2')
+        elif commit == 5:
+            git.tag('branchpoint')
+        elif commit == 7:
+            git.tag('post-branchoff-1')
+        elif commit == 9:
+            git.tag('post-branchoff-2')
+    git.checkout('-b', 'branch', 'branchpoint')
+    for commit in range(5,10):
+        touch('branch%d' % commit)
+        git.add('branch%d' % commit)
+        git.commit('.', '-m', 'branch %d' % commit)
+        if commit == 7:
+            git.tag('post-branchoff-on-branch-1')
+        elif commit == 9:
+            git.tag('post-branchoff-on-branch-2')
+    return (testdir, git)
+# vim: set et sw=4 ts=4:
diff --git a/tb3/tests/tb3-cli.py b/tb3/tests/tb3-cli.py
new file mode 100755
index 0000000..0dbc906
--- /dev/null
+++ b/tb3/tests/tb3-cli.py
@@ -0,0 +1,56 @@
+#!/usr/bin/python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+import sh
+import sys
+import os
+import unittest
+
+sys.path.append('./tests')
+import helpers
+
+#only for setup
+sys.path.append('./dist-packages')
+import tb3.repostate
+
+
+class TestTb3Cli(unittest.TestCase):
+    def __resolve_ref(self, refname):
+        return self.git('show-ref', refname).split(' ')[0]
+    def setUp(self):
+        (self.branch, self.platform) = ('master', 'linux')
+        os.environ['PATH'] += ':.'
+        (self.testdir, self.git) = helpers.createTestRepo()
+        self.tb3 = sh.tb3.bake(repo=self.testdir, branch=self.branch, platform=self.platform, builder='testbuilder')
+        self.state = tb3.repostate.RepoState(self.platform, self.branch, self.testdir)
+        self.head = self.state.get_head()
+    def tearDown(self):
+        sh.rm('-r', self.testdir)
+    def test_sync(self):
+        self.tb3(sync=True)
+    def test_set_commit_finished_good(self):
+        self.tb3(set_commit_finished=self.head, result='good')
+        self.tb3(set_commit_finished=self.head, result='good', result_reference='foo')
+    def test_set_commit_finished_bad(self):
+        self.tb3(set_commit_finished=self.head, result='bad')
+        self.tb3(set_commit_finished=self.head, result='bad', result_reference='bar')
+    def test_set_commit_running(self):
+        self.tb3(set_commit_running=self.head)
+        self.tb3(set_commit_running=self.head, estimated_duration=240)
+    def test_show_state(self):
+        self.tb3(show_state=True)
+    def test_show_history(self):
+        self.tb3(show_history=True, history_count=5)
+    def test_show_proposals(self):
+        self.tb3(show_proposals=True)
+        self.tb3(show_proposals=True, format='json')
+
+if __name__ == '__main__':
+    unittest.main()
+# vim: set et sw=4 ts=4:
diff --git a/tb3/tests/tb3/repostate.py b/tb3/tests/tb3/repostate.py
new file mode 100755
index 0000000..f69c372
--- /dev/null
+++ b/tb3/tests/tb3/repostate.py
@@ -0,0 +1,147 @@
+#! /usr/bin/env python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+import datetime
+import sh
+import sys
+import unittest
+
+sys.path.append('./dist-packages')
+sys.path.append('./tests')
+import helpers
+import tb3.repostate
+
+
+class TestRepoState(unittest.TestCase):
+    def __resolve_ref(self, refname):
+        return self.git('show-ref', refname).split(' ')[0]
+    def setUp(self):
+        (self.testdir, self.git) = helpers.createTestRepo()
+        self.state = tb3.repostate.RepoState('linux', 'master', self.testdir)
+        self.head = self.state.get_head()
+        self.preb1 = self.__resolve_ref('refs/tags/pre-branchoff-1')
+        self.preb2 = self.__resolve_ref('refs/tags/pre-branchoff-2')
+        self.bp = self.__resolve_ref('refs/tags/branchpoint')
+        self.postb1 = self.__resolve_ref('refs/tags/post-branchoff-1')
+        self.postb2 = self.__resolve_ref('refs/tags/post-branchoff-2')
+    def tearDown(self):
+        sh.rm('-r', self.testdir)
+    def test_sync(self):
+        self.state.sync()
+    def test_last_good(self):
+        self.state.set_last_good(self.head)
+        self.assertEqual(self.state.get_last_good(), self.head)
+    def test_first_bad(self):
+        self.state.set_first_bad(self.head)
+        self.assertEqual(self.state.get_first_bad(), self.head)
+    def test_last_bad(self):
+        self.state.set_last_bad(self.head)
+        self.assertEqual(self.state.get_last_bad(), self.head)
+    def test_last_build(self):
+        self.state.set_last_good(self.preb1)
+        self.assertEqual(self.state.get_last_build(), self.preb1)
+        self.state.set_last_bad(self.preb2)
+        self.assertEqual(self.state.get_last_build(), self.preb2)
+
+class TestRepoHistory(unittest.TestCase):
+    def setUp(self):
+        (self.testdir, self.git) = helpers.createTestRepo()
+        self.state = tb3.repostate.RepoState('linux', 'master', self.testdir)
+        self.head = self.state.get_head()
+        self.history = tb3.repostate.RepoHistory('linux', self.testdir)
+    def tearDown(self):
+        sh.rm('-r', self.testdir)
+    def test_commitState(self):
+        self.assertEqual(self.history.get_commit_state(self.head), tb3.repostate.CommitState())
+        for state in tb3.repostate.CommitState.STATES:
+            commitstate = tb3.repostate.CommitState(state)
+            self.history.set_commit_state(self.head, commitstate)
+            self.assertEqual(self.history.get_commit_state(self.head), commitstate)
+        with self.assertRaises(AttributeError):
+            self.history.set_commit_state(self.head, tb3.repostate.CommitState('foo!'))
+ 
+class TestRepoUpdater(unittest.TestCase):
+    def __resolve_ref(self, refname):
+        return self.git('show-ref', refname).split(' ')[0]
+    def setUp(self):
+        (self.testdir, self.git) = helpers.createTestRepo()
+        self.state = tb3.repostate.RepoState('linux', 'master', self.testdir)
+        self.preb1 = self.__resolve_ref('refs/tags/pre-branchoff-1')
+        self.bp = self.__resolve_ref('refs/tags/branchpoint')
+        self.postb1 = self.__resolve_ref('refs/tags/post-branchoff-1')
+        self.head = self.state.get_head()
+        self.history = tb3.repostate.RepoHistory('linux', self.testdir)
+        self.updater = tb3.repostate.RepoStateUpdater('linux', 'master', self.testdir)
+    def tearDown(self):
+        sh.rm('-r', self.testdir)
+    def test_set_scheduled(self):
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=2400))
+    def test_good_head(self):
+        self.updater.set_finished(self.head, 'testbuilder', 'GOOD', 'foo')
+    def test_bad_head(self):
+        self.updater.set_finished(self.head, 'testbuilder', 'BAD', 'foo')
+    def test_bisect(self):
+        self.updater.set_scheduled(self.preb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.bp, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.postb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_finished(self.preb1, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished(self.bp, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished(self.postb1, 'testbuilder', 'BAD', 'foo')
+        self.updater.set_finished(self.head, 'testbuilder', 'GOOD', 'foo')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.head).state, 'POSSIBLY_FIXING')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.postb1).state, 'POSSIBLY_BREAKING')
+        #for (commit, state) in self.history.get_recent_commit_states('master',9):
+        #    print('bisect: %s %s' % (commit, state))
+        #print(self.state)
+    def test_breaking(self):
+        self.updater.set_scheduled(self.preb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled('%s^^' % self.postb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled('%s^' % self.postb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_finished(self.preb1, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished('%s^^' % self.postb1, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished('%s^' % self.postb1, 'testbuilder', 'BAD', 'foo')
+        self.updater.set_finished(self.head, 'testbuilder', 'GOOD', 'foo')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.head).state, 'POSSIBLY_FIXING')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.postb1).state, 'BREAKING')
+        self.assertEqual(self.history.get_commit_state('%s^^' % self.postb1).state, 'GOOD')
+    def test_possibly_breaking(self):
+        self.updater.set_scheduled(self.preb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_finished(self.preb1, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished(self.head, 'testbuilder', 'BAD', 'foo')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.head).state, 'POSSIBLY_BREAKING')
+    def test_possibly_fixing(self):
+        self.updater.set_scheduled(self.preb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.bp, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_finished(self.preb1, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished(self.bp, 'testbuilder', 'BAD', 'foo')
+        self.updater.set_finished(self.head, 'testbuilder', 'GOOD', 'foo')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.head).state, 'POSSIBLY_FIXING')
+    def test_assume_good(self):
+        self.updater.set_scheduled(self.preb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_finished(self.preb1, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished(self.head, 'testbuilder', 'GOOD', 'foo')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.head).state, 'ASSUMED_GOOD')
+    def test_assume_bad(self):
+        self.updater.set_scheduled(self.preb1, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.bp, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_scheduled(self.head, 'testbuilder', datetime.timedelta(minutes=240))
+        self.updater.set_finished(self.preb1, 'testbuilder', 'GOOD', 'foo')
+        self.updater.set_finished(self.bp, 'testbuilder', 'BAD', 'foo')
+        self.updater.set_finished(self.head, 'testbuilder', 'BAD', 'foo')
+        self.assertEqual(self.history.get_commit_state('%s^' % self.head).state, 'ASSUMED_BAD')
+
+if __name__ == '__main__':
+    unittest.main()
+# vim: set et sw=4 ts=4:
diff --git a/tb3/tests/tb3/scheduler.py b/tb3/tests/tb3/scheduler.py
new file mode 100755
index 0000000..17870c6
--- /dev/null
+++ b/tb3/tests/tb3/scheduler.py
@@ -0,0 +1,110 @@
+#! /usr/bin/env python
+#
+# This file is part of the LibreOffice project.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+#
+
+import datetime
+import sh
+import unittest
+import sys
+
+sys.path.append('./dist-packages')
+sys.path.append('./tests')
+import helpers
+import tb3.scheduler
+import tb3.repostate
+
+class TestScheduler(unittest.TestCase):
+    def __resolve_ref(self, refname):
+        return self.git('show-ref', refname).split(' ')[0]
+    def setUp(self):
+        (self.testdir, self.git) = helpers.createTestRepo()
+        self.state = tb3.repostate.RepoState('linux', 'master', self.testdir)
+        self.repohistory = tb3.repostate.RepoHistory('linux', self.testdir)
+        self.updater = tb3.repostate.RepoStateUpdater('linux', 'master', self.testdir)
+        self.head = self.state.get_head()
+        self.preb1 = self.__resolve_ref('refs/tags/pre-branchoff-1')
+        self.preb2 = self.__resolve_ref('refs/tags/pre-branchoff-2')
+        self.bp = self.__resolve_ref('refs/tags/branchpoint')
+        self.postb1 = self.__resolve_ref('refs/tags/post-branchoff-1')
+        self.postb2 = self.__resolve_ref('refs/tags/post-branchoff-2')
+    def tearDown(self):
+        sh.rm('-r', self.testdir)
+
+class TestHeadScheduler(TestScheduler):
+    def test_get_proposals(self):
+        self.scheduler = tb3.scheduler.HeadScheduler('linux', 'master', self.testdir)
+        self.state.set_last_good(self.preb1)
+        proposals = self.scheduler.get_proposals(datetime.datetime.now())
+        self.assertEqual(len(proposals), 9)
+        best_proposal = proposals[0]
+        for proposal in proposals:
+            if proposal.score > best_proposal.score:
+                best_proposal = proposal
+        self.assertEqual(proposal.scheduler, 'HeadScheduler')
+        self.assertEqual(best_proposal.commit, self.head)
+        self.assertEqual(best_proposal.score, 9)
+        self.updater.set_scheduled(self.head, 'box', datetime.timedelta(hours=2))
+        proposals = self.scheduler.get_proposals(datetime.datetime.now())
+        self.assertEqual(len(proposals), 9)
+        proposal = proposals[0]
+        best_proposal = proposals[0]
+        for proposal in proposals:
+            if proposal.score > best_proposal.score:
+                best_proposal = proposal
+        self.assertEqual(proposal.scheduler, 'HeadScheduler')
+        precommits = self.scheduler.count_commits(self.preb1, best_proposal.commit)
+        postcommits = self.scheduler.count_commits(best_proposal.commit, self.head)
+        self.assertLessEqual(abs(precommits-postcommits),1)
+ 
+class TestBisectScheduler(TestScheduler):
+    def test_get_proposals(self):
+        self.state.set_last_good(self.preb1)
+        self.state.set_first_bad(self.postb2)
+        self.state.set_last_bad(self.postb2)
+        self.scheduler = tb3.scheduler.BisectScheduler('linux', 'master', self.testdir)
+        proposals = self.scheduler.get_proposals(datetime.datetime.now())
+        self.assertEqual(len(proposals), 8)
+        best_proposal = proposals[0]
+        for proposal in proposals:
+            if proposal.score > best_proposal.score:
+                best_proposal = proposal
+        self.assertEqual(best_proposal.scheduler, 'BisectScheduler')
+        self.git('merge-base', '--is-ancestor', self.preb1, best_proposal.commit)
+        self.git('merge-base', '--is-ancestor', best_proposal.commit, self.postb2)
+        precommits = self.scheduler.count_commits(self.preb1, best_proposal.commit)
+        postcommits = self.scheduler.count_commits(best_proposal.commit, self.postb2)
+        self.assertLessEqual(abs(precommits-postcommits),1)
+
+class TestMergeScheduler(TestScheduler):
+    def test_get_proposal(self):
+        self.state.set_last_good(self.preb1)
+        self.bisect_scheduler = tb3.scheduler.BisectScheduler('linux', 'master', self.testdir)
+        self.head_scheduler = tb3.scheduler.HeadScheduler('linux', 'master', self.testdir)
+        self.merge_scheduler = tb3.scheduler.MergeScheduler('linux', 'master', self.testdir)
+        self.merge_scheduler.add_scheduler(self.bisect_scheduler)
+        self.merge_scheduler.add_scheduler(self.head_scheduler)
+        proposals = self.merge_scheduler.get_proposals(datetime.datetime.now())
+        self.assertEqual(len(proposals), 9)
+        self.assertEqual(set((p.scheduler for p in proposals)), set(['HeadScheduler']))
+        proposal = proposals[0]
+        self.assertEqual(proposal.commit, self.head)
+        self.assertEqual(proposal.scheduler, 'HeadScheduler')
+        self.state.set_first_bad(self.preb2)
+        self.state.set_last_bad(self.postb1)
+        proposals = self.merge_scheduler.get_proposals(datetime.datetime.now())
+        self.assertEqual(len(proposals), 4)
+        self.assertEqual(set((p.scheduler for p in proposals)), set(['HeadScheduler', 'BisectScheduler']))
+        proposal = proposals[0]
+        self.git('merge-base', '--is-ancestor', proposal.commit, self.preb2)
+        self.git('merge-base', '--is-ancestor', self.preb1, proposal.commit)
+        self.assertEqual(proposal.scheduler, 'BisectScheduler')
+
+
+if __name__ == '__main__':
+    unittest.main()
+# vim: set et sw=4 ts=4: