Patchwork D5413: manifest: convert a recursive function to iterative one using stacks

login
register
mail settings
Submitter phabricator
Date Jan. 9, 2019, 8:10 p.m.
Message ID <0ea248fffe181580901204aa7c9bfe92@localhost.localdomain>
Download mbox | patch
Permalink /patch/37587/
State Not Applicable
Headers show

Comments

phabricator - Jan. 9, 2019, 8:10 p.m.
This revision was automatically updated to reflect the committed changes.
Closed by commit rHG2c3f69855ce8: manifest: convert a recursive function to iterative one using stacks (authored by pulkit, committed by ).

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D5413?vs=12826&id=13106

REVISION DETAIL
  https://phab.mercurial-scm.org/D5413

AFFECTED FILES
  mercurial/manifest.py

CHANGE DETAILS




To: pulkit, #hg-reviewers
Cc: durin42, mercurial-devel

Patch

diff --git a/mercurial/manifest.py b/mercurial/manifest.py
--- a/mercurial/manifest.py
+++ b/mercurial/manifest.py
@@ -1135,20 +1135,23 @@ 
             return m1.diff(m2, clean=clean)
         result = {}
         emptytree = treemanifest()
-        def _diff(t1, t2):
+
+        def _iterativediff(t1, t2, stack):
+            """compares two tree manifests and append new tree-manifests which
+            needs to be compared to stack"""
             if t1._node == t2._node and not t1._dirty and not t2._dirty:
                 return
             t1._load()
             t2._load()
             self._loaddifflazy(t1, t2)
 
             for d, m1 in t1._dirs.iteritems():
                 m2 = t2._dirs.get(d, emptytree)
-                _diff(m1, m2)
+                stack.append((m1, m2))
 
             for d, m2 in t2._dirs.iteritems():
                 if d not in t1._dirs:
-                    _diff(emptytree, m2)
+                    stack.append((emptytree, m2))
 
             for fn, n1 in t1._files.iteritems():
                 fl1 = t1._flags.get(fn, '')
@@ -1164,7 +1167,12 @@ 
                     fl2 = t2._flags.get(fn, '')
                     result[t2._subpath(fn)] = ((None, ''), (n2, fl2))
 
-        _diff(self, m2)
+        stackls = []
+        _iterativediff(self, m2, stackls)
+        while stackls:
+            t1, t2 = stackls.pop()
+            # stackls is populated in the function call
+            _iterativediff(t1, t2, stackls)
         return result
 
     def unmodifiedsince(self, m2):