Peter Arrenbrecht avatar Peter Arrenbrecht committed 1a70349

rewrite protocol with bitset and query for server's heads

Comments (0)

Files changed (1)

src/discovery_tonfa.py

 
     def __init__(self, dag, writer, cfg):
         Participant.__init__(self, dag, writer, cfg)
-        self._unknown = self.dag.nodeset()
-        self._common = set()
-        self._missing = set()
 
     def commonheads(self, server):
 
-    def common(self, server):
-        i = 0
-        while self._unknown:
-            if TRACE: self.writer.show("sampling...")
-            sample = clever_sample(self.dag, self._unknown, self._common)
-            if TRACE: self.writer.show("querying...")
-            common, remain = server.discover(sample)
-            self.writer.show("number of unknown left: %i, sample size: %s"
-                             % (len(self._unknown), len(sample)))
-            i += 1
+        dag = self.dag
+        nodes = dag.nodeset()
 
-            if TRACE: self.writer.show("updating missing...")
-            self._missing.update(self.dag.descendants((n for n in sample if n not in common), self._missing))
-            if TRACE: self.writer.show("updating common...")
-            self._common.update(self.dag.ancestors(list(n for n in common if n in self._unknown), self._common))
+        undecided = nodes # own nodes where I don't know if the server knows them
+        common = set() # nodes we both know
+        missing = set() # own nodes the server lacks
 
-            if remain is not None:
-                if TRACE: self.writer.show("updating common...")
-                self._common.update(self.dag.ancestors(list(n for n in remain if n in self._unknown)), self._common)
-                break
+        self.writer.step("sampling")
+        sample = clever_sample(dag, undecided, common)
 
-            if TRACE: self.writer.show("updating unknown...")
-            self._unknown.difference_update(self._missing)
-            self._unknown.difference_update(self._common)
+        # first roundtrip queries server's heads too
+        self.writer.step("querying")
+        i = 1
+        srvheads = set(server.heads())
+        yesno, allremaining = server.discover(sample)
+        self.writer.done()
 
+        if not (srvheads - nodes):
+
+            # all server's heads known
+            self.writer.show("all server heads known")
+            result = srvheads
+
+        else:
+
+            common.update(dag.ancestors(srvheads.intersection(undecided)))
+            undecided.difference_update(common)
+
+            while undecided:
+
+                self.writer.show("still undecided: %i, sample size: %s"
+                                 % (len(undecided), len(sample)))
+
+                self.writer.step("updating common")
+                commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
+                common.update(dag.ancestors(commoninsample, common))
+
+                if allremaining is not None:
+                    self.writer.step("updating common for allremaining")
+                    commonremain = set(allremaining).intersection(undecided)
+                    common.update(dag.ancestors(commonremain, common))
+                    break
+
+                self.writer.step("updating missing")
+                missinginsample = set(n for i, n in enumerate(sample) if not yesno[i])
+                missing.update(dag.descendants(missinginsample, missing))
+
+                self.writer.step("updating undecided")
+                undecided.difference_update(missing)
+                undecided.difference_update(common)
+
+                if not undecided:
+                    break
+
+                self.writer.step("sampling")
+                sample = clever_sample(dag, undecided, common)
+                self.writer.step("querying")
+                i += 1
+                yesno, allremaining = server.discover(sample)
+                self.writer.done()
+
+            result = dag.headsofconnectedset(common)
+
+        self.writer.done()
         self.writer.show("number of iterations: %i" % i)
-        return self._common
+        return result
 
 
 class Server(Participant):
     def __init__(self, dag, writer, cfg):
         Participant.__init__(self, dag, writer, cfg)
 
+    def heads(self):
+        return self.dag.heads()
+
     def discover(self, sample):
-        nodes = self.dag.nodeset()
+        dag = self.dag
+        nodes = dag.nodeset()
 
-        common = set()
-        for n in sample:
+        yesno = [False for i in xrange(len(sample))]
+        known = set()
+        for i, n in enumerate(sample):
             if n in nodes:
-                common.add(n)
+                known.add(n)
+                yesno[i] = True
 
-        allcommon = self.dag.nodeset(list(common))
-        allremain = nodes - allcommon
-        self.writer.show("server remaining: %i" % len(allremain))
-        if len(allremain) < MAX_SAMPLE:
-            return common, allremain
+        allremaining = nodes - dag.ancestors(known)
+        self.writer.show("server remaining: %i" % len(allremaining))
+        if len(allremaining) > MAX_SAMPLE:
+            allremaining = None
 
-        return common, None
+        return yesno, allremaining
 
 
 class Tests(DiscoveryTests):
         self.cfg = Config()
 
     def setupdags(self, a, b, ans, bns):
-        self.expected = ans & bns
+        self.expected = a.headsofconnectedset(ans & bns)
 
     def test(self, cdag, sdag, cns, sns):
         s = Server(sdag, self.writer, self.cfg)
         notraffic = False
 
         self.writer.section("traffic", quiesce=notraffic)
-        actual = c.common(s)
+        actual = c.commonheads(s)
         self.writer.unindent()
-        assertnodes(self.expected, actual)
+        assertnodes(list(self.expected), list(actual))
 
 if __name__ == "__main__":
     random.seed(0)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.