595 def walkchangerevs(ui, repo, pats, change, opts):

   596     '''Iterate over files and the revs they changed in.

   597 

   598     Callers most commonly need to iterate backwards over the history

   599     it is interested in.  Doing so has awful (quadratic-looking)

   600     performance, so we use iterators in a "windowed" way.

   601 

   602     We walk a window of revisions in the desired order.  Within the

   603     window, we first walk forwards to gather data, then in the desired

   604     order (usually backwards) to display it.

   605 

   606     This function returns an (iterator, matchfn) tuple. The iterator

   607     yields 3-tuples. They will be of one of the following forms:

   608 

   609     "window", incrementing, lastrev: stepping through a window,

   610     positive if walking forwards through revs, last rev in the

   611     sequence iterated over - use to reset state for the current window

   612 

   613     "add", rev, fns: out-of-order traversal of the given file names

   614     fns, which changed during revision rev - use to gather data for

   615     possible display

   616 

   617     "iter", rev, None: in-order traversal of the revs earlier iterated

   618     over with "add" - use to display data'''

   619 

   620     def increasing_windows(start, end, windowsize=8, sizelimit=512):

   621         if start < end:

   622             while start < end:

   623                 yield start, min(windowsize, end-start)

   624                 start += windowsize

   625                 if windowsize < sizelimit:

   626                     windowsize *= 2

   627         else:

   628             while start > end:

   629                 yield start, min(windowsize, start-end-1)

   630                 start -= windowsize

   631                 if windowsize < sizelimit:

   632                     windowsize *= 2

   633 

   634     files, matchfn, anypats = matchpats(repo, pats, opts)

   635     follow = opts.get('follow') or opts.get('follow_first')

   636 

   637     if repo.changelog.count() == 0:

   638         return [], matchfn

   639 

   640     if follow:

   641         defrange = '%s:0' % repo.changectx().rev()

   642     else:

   643         defrange = 'tip:0'

   644     revs = revrange(ui, repo, opts['rev'] or [defrange])

   645     wanted = {}

   646     slowpath = anypats

   647     fncache = {}

   648 

   649     if not slowpath and not files:

   650         # No files, no patterns.  Display all revs.

   651         wanted = dict.fromkeys(revs)

   652     copies = []

   653     if not slowpath:

   654         # Only files, no patterns.  Check the history of each file.

   655         def filerevgen(filelog, node):

   656             cl_count = repo.changelog.count()

   657             if node is None:

   658                 last = filelog.count() - 1

   659             else:

   660                 last = filelog.rev(node)

   661             for i, window in increasing_windows(last, nullrev):

   662                 revs = []

   663                 for j in xrange(i - window, i + 1):

   664                     n = filelog.node(j)

   665                     revs.append((filelog.linkrev(n),

   666                                  follow and filelog.renamed(n)))

   667                 revs.reverse()

   668                 for rev in revs:

   669                     # only yield rev for which we have the changelog, it can

   670                     # happen while doing "hg log" during a pull or commit

   671                     if rev[0] < cl_count:

   672                         yield rev

   673         def iterfiles():

   674             for filename in files:

   675                 yield filename, None

   676             for filename_node in copies:

   677                 yield filename_node

   678         minrev, maxrev = min(revs), max(revs)

   679         for file_, node in iterfiles():

   680             filelog = repo.file(file_)

   681             # A zero count may be a directory or deleted file, so

   682             # try to find matching entries on the slow path.

   683             if filelog.count() == 0:

   684                 slowpath = True

   685                 break

   686             for rev, copied in filerevgen(filelog, node):

   687                 if rev <= maxrev:

   688                     if rev < minrev:

   689                         break

   690                     fncache.setdefault(rev, [])

   691                     fncache[rev].append(file_)

   692                     wanted[rev] = 1

   693                     if follow and copied:

   694                         copies.append(copied)

   695     if slowpath:

   696         if follow:

   697             raise util.Abort(_('can only follow copies/renames for explicit '

   698                                'file names'))

   699 

   700         # The slow path checks files modified in every changeset.

   701         def changerevgen():

   702             for i, window in increasing_windows(repo.changelog.count()-1,

   703                                                 nullrev):

   704                 for j in xrange(i - window, i + 1):

   705                     yield j, change(j)[3]

   706 

   707         for rev, changefiles in changerevgen():

   708             matches = filter(matchfn, changefiles)

   709             if matches:

   710                 fncache[rev] = matches

   711                 wanted[rev] = 1

   712 

   713     class followfilter:

   714         def __init__(self, onlyfirst=False):

   715             self.startrev = nullrev

   716             self.roots = []

   717             self.onlyfirst = onlyfirst

   718 

   719         def match(self, rev):

   720             def realparents(rev):

   721                 if self.onlyfirst:

   722                     return repo.changelog.parentrevs(rev)[0:1]

   723                 else:

   724                     return filter(lambda x: x != nullrev,

   725                                   repo.changelog.parentrevs(rev))

   726 

   727             if self.startrev == nullrev:

   728                 self.startrev = rev

   729                 return True

   730 

   731             if rev > self.startrev:

   732                 # forward: all descendants

   733                 if not self.roots:

   734                     self.roots.append(self.startrev)

   735                 for parent in realparents(rev):

   736                     if parent in self.roots:

   737                         self.roots.append(rev)

   738                         return True

   739             else:

   740                 # backwards: all parents

   741                 if not self.roots:

   742                     self.roots.extend(realparents(self.startrev))

   743                 if rev in self.roots:

   744                     self.roots.remove(rev)

   745                     self.roots.extend(realparents(rev))

   746                     return True

   747 

   748             return False

   749 

   750     # it might be worthwhile to do this in the iterator if the rev range

   751     # is descending and the prune args are all within that range

   752     for rev in opts.get('prune', ()):

   753         rev = repo.changelog.rev(repo.lookup(rev))

   754         ff = followfilter()

   755         stop = min(revs[0], revs[-1])

   756         for x in xrange(rev, stop-1, -1):

   757             if ff.match(x) and x in wanted:

   758                 del wanted[x]

   759 

   760     def iterate():

   761         if follow and not files:

   762             ff = followfilter(onlyfirst=opts.get('follow_first'))

   763             def want(rev):

   764                 if ff.match(rev) and rev in wanted:

   765                     return True

   766                 return False

   767         else:

   768             def want(rev):

   769                 return rev in wanted

   770 

   771         for i, window in increasing_windows(0, len(revs)):

   772             yield 'window', revs[0] < revs[-1], revs[-1]

   773             nrevs = [rev for rev in revs[i:i+window] if want(rev)]

   774             srevs = list(nrevs)

   775             srevs.sort()

   776             for rev in srevs:

   777                 fns = fncache.get(rev)

   778                 if not fns:

   779                     def fns_generator():

   780                         for f in change(rev)[3]:

   781                             if matchfn(f):

   782                                 yield f

   783                     fns = fns_generator()

   784                 yield 'add', rev, fns

   785             for rev in nrevs:

   786                 yield 'iter', rev, None

   787     return iterate(), matchfn