51 

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

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

    54 

    55     Callers most commonly need to iterate backwards over the history

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

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

    58 

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

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

    61     order (usually backwards) to display it.

    62 

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

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

    65 

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

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

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

    69 

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

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

    72     possible display

    73 

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

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

    76 

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

    78         if start < end:

    79             while start < end:

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

    81                 start += windowsize

    82                 if windowsize < sizelimit:

    83                     windowsize *= 2

    84         else:

    85             while start > end:

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

    87                 start -= windowsize

    88                 if windowsize < sizelimit:

    89                     windowsize *= 2

    90 

    91     files, matchfn, anypats = cmdutil.matchpats(repo, pats, opts)

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

    93 

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

    95         return [], matchfn

    96 

    97     if follow:

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

    99     else:

   100         defrange = 'tip:0'

   101     revs = cmdutil.revrange(ui, repo, opts['rev'] or [defrange])

   102     wanted = {}

   103     slowpath = anypats

   104     fncache = {}

   105 

   106     if not slowpath and not files:

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

   108         wanted = dict.fromkeys(revs)

   109     copies = []

   110     if not slowpath:

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

   112         def filerevgen(filelog, node):

   113             cl_count = repo.changelog.count()

   114             if node is None:

   115                 last = filelog.count() - 1

   116             else:

   117                 last = filelog.rev(node)

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

   119                 revs = []

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

   121                     n = filelog.node(j)

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

   123                                  follow and filelog.renamed(n)))

   124                 revs.reverse()

   125                 for rev in revs:

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

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

   128                     if rev[0] < cl_count:

   129                         yield rev

   130         def iterfiles():

   131             for filename in files:

   132                 yield filename, None

   133             for filename_node in copies:

   134                 yield filename_node

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

   136         for file_, node in iterfiles():

   137             filelog = repo.file(file_)

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

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

   140             if filelog.count() == 0:

   141                 slowpath = True

   142                 break

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

   144                 if rev <= maxrev:

   145                     if rev < minrev:

   146                         break

   147                     fncache.setdefault(rev, [])

   148                     fncache[rev].append(file_)

   149                     wanted[rev] = 1

   150                     if follow and copied:

   151                         copies.append(copied)

   152     if slowpath:

   153         if follow:

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

   155                                'file names'))

   156 

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

   158         def changerevgen():

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

   160                                                 nullrev):

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

   162                     yield j, change(j)[3]

   163 

   164         for rev, changefiles in changerevgen():

   165             matches = filter(matchfn, changefiles)

   166             if matches:

   167                 fncache[rev] = matches

   168                 wanted[rev] = 1

   169 

   170     class followfilter:

   171         def __init__(self, onlyfirst=False):

   172             self.startrev = nullrev

   173             self.roots = []

   174             self.onlyfirst = onlyfirst

   175 

   176         def match(self, rev):

   177             def realparents(rev):

   178                 if self.onlyfirst:

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

   180                 else:

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

   182                                   repo.changelog.parentrevs(rev))

   183 

   184             if self.startrev == nullrev:

   185                 self.startrev = rev

   186                 return True

   187 

   188             if rev > self.startrev:

   189                 # forward: all descendants

   190                 if not self.roots:

   191                     self.roots.append(self.startrev)

   192                 for parent in realparents(rev):

   193                     if parent in self.roots:

   194                         self.roots.append(rev)

   195                         return True

   196             else:

   197                 # backwards: all parents

   198                 if not self.roots:

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

   200                 if rev in self.roots:

   201                     self.roots.remove(rev)

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

   203                     return True

   204 

   205             return False

   206 

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

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

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

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

   211         ff = followfilter()

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

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

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

   215                 del wanted[x]

   216 

   217     def iterate():

   218         if follow and not files:

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

   220             def want(rev):

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

   222                     return True

   223                 return False

   224         else:

   225             def want(rev):

   226                 return rev in wanted

   227 

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

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

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

   231             srevs = list(nrevs)

   232             srevs.sort()

   233             for rev in srevs:

   234                 fns = fncache.get(rev)

   235                 if not fns:

   236                     def fns_generator():

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

   238                             if matchfn(f):

   239                                 yield f

   240                     fns = fns_generator()

   241                 yield 'add', rev, fns

   242             for rev in nrevs:

   243                 yield 'iter', rev, None

   244     return iterate(), matchfn