Recursion depth in git_fs.py traverse - "trac-admin repository sync" fails

[anonymous]

trac-admin repository sync myrepo fails for me:

  File "/usr/lib/python2.7/dist-packages/tracopt/versioncontrol/git/git_fs.py", line 122, in traverse
    revs[idx:idx] = traverse(parent, seen)
  File "/usr/lib/python2.7/dist-packages/tracopt/versioncontrol/git/git_fs.py", line 122, in traverse
    revs[idx:idx] = traverse(parent, seen)
  File "/usr/lib/python2.7/dist-packages/tracopt/versioncontrol/git/git_fs.py", line 122, in traverse
    revs[idx:idx] = traverse(parent, seen)
  File "/usr/lib/python2.7/dist-packages/tracopt/versioncontrol/git/git_fs.py", line 110, in traverse
    if is_synced(rev):
  File "/usr/lib/python2.7/dist-packages/tracopt/versioncontrol/git/git_fs.py", line 99, in is_synced
    """, (self.id, rev)):
  File "/usr/lib/python2.7/dist-packages/trac/db/api.py", line 122, in execute
    with self as db:
  File "/usr/lib/python2.7/dist-packages/trac/db/api.py", line 175, in __enter__
    db = self.dbmgr.get_connection(readonly=True)
  File "/usr/lib/python2.7/dist-packages/trac/db/api.py", line 288, in get_connection
    db = self._cnx_pool.get_cnx(self.timeout or None)
  File "/usr/lib/python2.7/dist-packages/trac/db/pool.py", line 213, in get_cnx
    return _backend.get_cnx(self._connector, self._kwargs, timeout)
  File "/usr/lib/python2.7/dist-packages/trac/db/pool.py", line 91, in get_cnx
    self._active[(tid, key)] = (cnx, num)
  File "/usr/lib/python2.7/threading.py", line 289, in __exit__
    return self.__lock.__exit__(*args)
  File "/usr/lib/python2.7/threading.py", line 216, in __exit__
    self.release()
  File "/usr/lib/python2.7/threading.py", line 210, in release
    self._note("%s.release(): final release", self)
RuntimeError: maximum recursion depth exceeded

If you have a very complicated repository (with lots of merges, e.g. because of migration from other version control systems - probably something like 1000 merges is the limit of trac right now?), the "traverse" method in git_fs.py can fail with a recursion depth exception. The last line of traverse gets invoked when a revision has more than one parent.

May I suggest to use a list based approach that always uses a loop, not falls back to recursion when there is more than one parent?

Some logic (e.g. inserting at revs[idx:idx]) does not appear to be necessary, not even for topology ordering. It only changes the order of the parents backwards, something that can be easily achieved otherwise.

Two modifications in below code (still recursive, though!):

1. filter seen parents out early
2. collect into a single array of revisions, assuming that the order of parent_revs does not matter anyway.

With below patch, synchronisation seems to work for me - it does not fan out badly, but there are a lot of merges in my codebase. By filtering the seen revisions, the non-recursive codepath seems to be used more often.

tracopt/versioncontrol/git/git_fs.py

@@ -103 +103 @@
         def traverse(rev, seen, revs=None):
             if revs is None:
                 revs = []
             while True:
                 if rev in seen:
                     return revs
                 seen.add(rev)
                 if is_synced(rev):
                     return revs
                 revs.append(rev)
-                parent_revs = repos.parent_revs(rev)
+                parent_revs = filter(lambda x: not x in seen, repos.parent_revs(rev))
                 if not parent_revs:
                     return revs
                 if len(parent_revs) == 1:
                     rev = parent_revs[0]
                     continue
-                idx = len(revs)
                 traverse(parent_revs.pop(), seen, revs)
                 for parent in parent_revs:
-                    revs[idx:idx] = traverse(parent, seen)
+                    traverse(parent, seen, revs)

[Jun Omae]

Thanks for the reporting! I'll reproduce it and confirm suggested fix.

[Jun Omae]

I confirmed suggested fix for git repository with 2000 merge commits. The issue still exists. I just created patch in [55f4f3dd/jomae.git] (jomae.git@t11905).

Could you please try the patch on your environment?

[Jun Omae]

Added unit tests for this issue in [61b3244ff/jomae.git]. I'll push proposed changes tonight.

[Ryan J Ollos]

I'm running late in creating the release but plan to do that tomorrow, so pushing proposed changes tonight would be good timing.

[Jun Omae]

Yeah. I just pushed in [13633] and merged to trunk in [13634].