##// END OF EJS Templates
smartset: preserve istopo for baseset operations...
Jun Wu -
r31066:c962bb6a default
parent child Browse files
Show More
@@ -1,1047 +1,1056 b''
1 1 # smartset.py - data structure for revision set
2 2 #
3 3 # Copyright 2010 Matt Mackall <mpm@selenic.com>
4 4 #
5 5 # This software may be used and distributed according to the terms of the
6 6 # GNU General Public License version 2 or any later version.
7 7
8 8 from __future__ import absolute_import
9 9
10 10 from . import (
11 11 util,
12 12 )
13 13
14 14 def _formatsetrepr(r):
15 15 """Format an optional printable representation of a set
16 16
17 17 ======== =================================
18 18 type(r) example
19 19 ======== =================================
20 20 tuple ('<not %r>', other)
21 21 str '<branch closed>'
22 22 callable lambda: '<branch %r>' % sorted(b)
23 23 object other
24 24 ======== =================================
25 25 """
26 26 if r is None:
27 27 return ''
28 28 elif isinstance(r, tuple):
29 29 return r[0] % r[1:]
30 30 elif isinstance(r, str):
31 31 return r
32 32 elif callable(r):
33 33 return r()
34 34 else:
35 35 return repr(r)
36 36
37 37 class abstractsmartset(object):
38 38
39 39 def __nonzero__(self):
40 40 """True if the smartset is not empty"""
41 41 raise NotImplementedError()
42 42
43 43 def __contains__(self, rev):
44 44 """provide fast membership testing"""
45 45 raise NotImplementedError()
46 46
47 47 def __iter__(self):
48 48 """iterate the set in the order it is supposed to be iterated"""
49 49 raise NotImplementedError()
50 50
51 51 # Attributes containing a function to perform a fast iteration in a given
52 52 # direction. A smartset can have none, one, or both defined.
53 53 #
54 54 # Default value is None instead of a function returning None to avoid
55 55 # initializing an iterator just for testing if a fast method exists.
56 56 fastasc = None
57 57 fastdesc = None
58 58
59 59 def isascending(self):
60 60 """True if the set will iterate in ascending order"""
61 61 raise NotImplementedError()
62 62
63 63 def isdescending(self):
64 64 """True if the set will iterate in descending order"""
65 65 raise NotImplementedError()
66 66
67 67 def istopo(self):
68 68 """True if the set will iterate in topographical order"""
69 69 raise NotImplementedError()
70 70
71 71 def min(self):
72 72 """return the minimum element in the set"""
73 73 if self.fastasc is None:
74 74 v = min(self)
75 75 else:
76 76 for v in self.fastasc():
77 77 break
78 78 else:
79 79 raise ValueError('arg is an empty sequence')
80 80 self.min = lambda: v
81 81 return v
82 82
83 83 def max(self):
84 84 """return the maximum element in the set"""
85 85 if self.fastdesc is None:
86 86 return max(self)
87 87 else:
88 88 for v in self.fastdesc():
89 89 break
90 90 else:
91 91 raise ValueError('arg is an empty sequence')
92 92 self.max = lambda: v
93 93 return v
94 94
95 95 def first(self):
96 96 """return the first element in the set (user iteration perspective)
97 97
98 98 Return None if the set is empty"""
99 99 raise NotImplementedError()
100 100
101 101 def last(self):
102 102 """return the last element in the set (user iteration perspective)
103 103
104 104 Return None if the set is empty"""
105 105 raise NotImplementedError()
106 106
107 107 def __len__(self):
108 108 """return the length of the smartsets
109 109
110 110 This can be expensive on smartset that could be lazy otherwise."""
111 111 raise NotImplementedError()
112 112
113 113 def reverse(self):
114 114 """reverse the expected iteration order"""
115 115 raise NotImplementedError()
116 116
117 117 def sort(self, reverse=True):
118 118 """get the set to iterate in an ascending or descending order"""
119 119 raise NotImplementedError()
120 120
121 121 def __and__(self, other):
122 122 """Returns a new object with the intersection of the two collections.
123 123
124 124 This is part of the mandatory API for smartset."""
125 125 if isinstance(other, fullreposet):
126 126 return self
127 127 return self.filter(other.__contains__, condrepr=other, cache=False)
128 128
129 129 def __add__(self, other):
130 130 """Returns a new object with the union of the two collections.
131 131
132 132 This is part of the mandatory API for smartset."""
133 133 return addset(self, other)
134 134
135 135 def __sub__(self, other):
136 136 """Returns a new object with the substraction of the two collections.
137 137
138 138 This is part of the mandatory API for smartset."""
139 139 c = other.__contains__
140 140 return self.filter(lambda r: not c(r), condrepr=('<not %r>', other),
141 141 cache=False)
142 142
143 143 def filter(self, condition, condrepr=None, cache=True):
144 144 """Returns this smartset filtered by condition as a new smartset.
145 145
146 146 `condition` is a callable which takes a revision number and returns a
147 147 boolean. Optional `condrepr` provides a printable representation of
148 148 the given `condition`.
149 149
150 150 This is part of the mandatory API for smartset."""
151 151 # builtin cannot be cached. but do not needs to
152 152 if cache and util.safehasattr(condition, 'func_code'):
153 153 condition = util.cachefunc(condition)
154 154 return filteredset(self, condition, condrepr)
155 155
156 156 class baseset(abstractsmartset):
157 157 """Basic data structure that represents a revset and contains the basic
158 158 operation that it should be able to perform.
159 159
160 160 Every method in this class should be implemented by any smartset class.
161 161
162 162 This class could be constructed by an (unordered) set, or an (ordered)
163 163 list-like object. If a set is provided, it'll be sorted lazily.
164 164
165 165 >>> x = [4, 0, 7, 6]
166 166 >>> y = [5, 6, 7, 3]
167 167
168 168 Construct by a set:
169 169 >>> xs = baseset(set(x))
170 170 >>> ys = baseset(set(y))
171 171 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
172 172 [[0, 4, 6, 7, 3, 5], [6, 7], [0, 4]]
173 173 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
174 174 ['addset', 'baseset', 'baseset']
175 175
176 176 Construct by a list-like:
177 177 >>> xs = baseset(x)
178 178 >>> ys = baseset(i for i in y)
179 179 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
180 180 [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
181 181 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
182 182 ['addset', 'filteredset', 'filteredset']
183 183
184 184 Populate "_set" fields in the lists so set optimization may be used:
185 185 >>> [1 in xs, 3 in ys]
186 186 [False, True]
187 187
188 188 Without sort(), results won't be changed:
189 189 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
190 190 [[4, 0, 7, 6, 5, 3], [7, 6], [4, 0]]
191 191 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
192 192 ['addset', 'filteredset', 'filteredset']
193 193
194 194 With sort(), set optimization could be used:
195 195 >>> xs.sort(reverse=True)
196 196 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
197 197 [[7, 6, 4, 0, 5, 3], [7, 6], [4, 0]]
198 198 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
199 199 ['addset', 'baseset', 'baseset']
200 200
201 201 >>> ys.sort()
202 202 >>> [list(i) for i in [xs + ys, xs & ys, xs - ys]]
203 203 [[7, 6, 4, 0, 3, 5], [7, 6], [4, 0]]
204 204 >>> [type(i).__name__ for i in [xs + ys, xs & ys, xs - ys]]
205 205 ['addset', 'baseset', 'baseset']
206
207 istopo is preserved across set operations
208 >>> xs = baseset(set(x), istopo=True)
209 >>> rs = xs & ys
210 >>> type(rs).__name__
211 'baseset'
212 >>> rs._istopo
213 True
206 214 """
207 215 def __init__(self, data=(), datarepr=None, istopo=False):
208 216 """
209 217 datarepr: a tuple of (format, obj, ...), a function or an object that
210 218 provides a printable representation of the given data.
211 219 """
212 220 self._ascending = None
213 221 self._istopo = istopo
214 222 if not isinstance(data, list):
215 223 if isinstance(data, set):
216 224 self._set = data
217 225 # set has no order we pick one for stability purpose
218 226 self._ascending = True
219 227 # converting set to list has a cost, do it lazily
220 228 data = None
221 229 else:
222 230 data = list(data)
223 231 if data is not None:
224 232 self._list = data
225 233 self._datarepr = datarepr
226 234
227 235 @util.propertycache
228 236 def _set(self):
229 237 return set(self._list)
230 238
231 239 @util.propertycache
232 240 def _asclist(self):
233 241 asclist = self._list[:]
234 242 asclist.sort()
235 243 return asclist
236 244
237 245 @util.propertycache
238 246 def _list(self):
239 247 # _list is only lazily constructed if we have _set
240 248 assert '_set' in self.__dict__
241 249 return list(self._set)
242 250
243 251 def __iter__(self):
244 252 if self._ascending is None:
245 253 return iter(self._list)
246 254 elif self._ascending:
247 255 return iter(self._asclist)
248 256 else:
249 257 return reversed(self._asclist)
250 258
251 259 def fastasc(self):
252 260 return iter(self._asclist)
253 261
254 262 def fastdesc(self):
255 263 return reversed(self._asclist)
256 264
257 265 @util.propertycache
258 266 def __contains__(self):
259 267 return self._set.__contains__
260 268
261 269 def __nonzero__(self):
262 270 return bool(len(self))
263 271
264 272 def sort(self, reverse=False):
265 273 self._ascending = not bool(reverse)
266 274 self._istopo = False
267 275
268 276 def reverse(self):
269 277 if self._ascending is None:
270 278 self._list.reverse()
271 279 else:
272 280 self._ascending = not self._ascending
273 281 self._istopo = False
274 282
275 283 def __len__(self):
276 284 if '_list' in self.__dict__:
277 285 return len(self._list)
278 286 else:
279 287 return len(self._set)
280 288
281 289 def isascending(self):
282 290 """Returns True if the collection is ascending order, False if not.
283 291
284 292 This is part of the mandatory API for smartset."""
285 293 if len(self) <= 1:
286 294 return True
287 295 return self._ascending is not None and self._ascending
288 296
289 297 def isdescending(self):
290 298 """Returns True if the collection is descending order, False if not.
291 299
292 300 This is part of the mandatory API for smartset."""
293 301 if len(self) <= 1:
294 302 return True
295 303 return self._ascending is not None and not self._ascending
296 304
297 305 def istopo(self):
298 306 """Is the collection is in topographical order or not.
299 307
300 308 This is part of the mandatory API for smartset."""
301 309 if len(self) <= 1:
302 310 return True
303 311 return self._istopo
304 312
305 313 def first(self):
306 314 if self:
307 315 if self._ascending is None:
308 316 return self._list[0]
309 317 elif self._ascending:
310 318 return self._asclist[0]
311 319 else:
312 320 return self._asclist[-1]
313 321 return None
314 322
315 323 def last(self):
316 324 if self:
317 325 if self._ascending is None:
318 326 return self._list[-1]
319 327 elif self._ascending:
320 328 return self._asclist[-1]
321 329 else:
322 330 return self._asclist[0]
323 331 return None
324 332
325 333 def _fastsetop(self, other, op):
326 334 # try to use native set operations as fast paths
327 335 if (type(other) is baseset and '_set' in other.__dict__ and '_set' in
328 336 self.__dict__ and self._ascending is not None):
329 s = baseset(data=getattr(self._set, op)(other._set))
337 s = baseset(data=getattr(self._set, op)(other._set),
338 istopo=self._istopo)
330 339 s._ascending = self._ascending
331 340 else:
332 341 s = getattr(super(baseset, self), op)(other)
333 342 return s
334 343
335 344 def __and__(self, other):
336 345 return self._fastsetop(other, '__and__')
337 346
338 347 def __sub__(self, other):
339 348 return self._fastsetop(other, '__sub__')
340 349
341 350 def __repr__(self):
342 351 d = {None: '', False: '-', True: '+'}[self._ascending]
343 352 s = _formatsetrepr(self._datarepr)
344 353 if not s:
345 354 l = self._list
346 355 # if _list has been built from a set, it might have a different
347 356 # order from one python implementation to another.
348 357 # We fallback to the sorted version for a stable output.
349 358 if self._ascending is not None:
350 359 l = self._asclist
351 360 s = repr(l)
352 361 return '<%s%s %s>' % (type(self).__name__, d, s)
353 362
354 363 class filteredset(abstractsmartset):
355 364 """Duck type for baseset class which iterates lazily over the revisions in
356 365 the subset and contains a function which tests for membership in the
357 366 revset
358 367 """
359 368 def __init__(self, subset, condition=lambda x: True, condrepr=None):
360 369 """
361 370 condition: a function that decide whether a revision in the subset
362 371 belongs to the revset or not.
363 372 condrepr: a tuple of (format, obj, ...), a function or an object that
364 373 provides a printable representation of the given condition.
365 374 """
366 375 self._subset = subset
367 376 self._condition = condition
368 377 self._condrepr = condrepr
369 378
370 379 def __contains__(self, x):
371 380 return x in self._subset and self._condition(x)
372 381
373 382 def __iter__(self):
374 383 return self._iterfilter(self._subset)
375 384
376 385 def _iterfilter(self, it):
377 386 cond = self._condition
378 387 for x in it:
379 388 if cond(x):
380 389 yield x
381 390
382 391 @property
383 392 def fastasc(self):
384 393 it = self._subset.fastasc
385 394 if it is None:
386 395 return None
387 396 return lambda: self._iterfilter(it())
388 397
389 398 @property
390 399 def fastdesc(self):
391 400 it = self._subset.fastdesc
392 401 if it is None:
393 402 return None
394 403 return lambda: self._iterfilter(it())
395 404
396 405 def __nonzero__(self):
397 406 fast = None
398 407 candidates = [self.fastasc if self.isascending() else None,
399 408 self.fastdesc if self.isdescending() else None,
400 409 self.fastasc,
401 410 self.fastdesc]
402 411 for candidate in candidates:
403 412 if candidate is not None:
404 413 fast = candidate
405 414 break
406 415
407 416 if fast is not None:
408 417 it = fast()
409 418 else:
410 419 it = self
411 420
412 421 for r in it:
413 422 return True
414 423 return False
415 424
416 425 def __len__(self):
417 426 # Basic implementation to be changed in future patches.
418 427 # until this gets improved, we use generator expression
419 428 # here, since list comprehensions are free to call __len__ again
420 429 # causing infinite recursion
421 430 l = baseset(r for r in self)
422 431 return len(l)
423 432
424 433 def sort(self, reverse=False):
425 434 self._subset.sort(reverse=reverse)
426 435
427 436 def reverse(self):
428 437 self._subset.reverse()
429 438
430 439 def isascending(self):
431 440 return self._subset.isascending()
432 441
433 442 def isdescending(self):
434 443 return self._subset.isdescending()
435 444
436 445 def istopo(self):
437 446 return self._subset.istopo()
438 447
439 448 def first(self):
440 449 for x in self:
441 450 return x
442 451 return None
443 452
444 453 def last(self):
445 454 it = None
446 455 if self.isascending():
447 456 it = self.fastdesc
448 457 elif self.isdescending():
449 458 it = self.fastasc
450 459 if it is not None:
451 460 for x in it():
452 461 return x
453 462 return None #empty case
454 463 else:
455 464 x = None
456 465 for x in self:
457 466 pass
458 467 return x
459 468
460 469 def __repr__(self):
461 470 xs = [repr(self._subset)]
462 471 s = _formatsetrepr(self._condrepr)
463 472 if s:
464 473 xs.append(s)
465 474 return '<%s %s>' % (type(self).__name__, ', '.join(xs))
466 475
467 476 def _iterordered(ascending, iter1, iter2):
468 477 """produce an ordered iteration from two iterators with the same order
469 478
470 479 The ascending is used to indicated the iteration direction.
471 480 """
472 481 choice = max
473 482 if ascending:
474 483 choice = min
475 484
476 485 val1 = None
477 486 val2 = None
478 487 try:
479 488 # Consume both iterators in an ordered way until one is empty
480 489 while True:
481 490 if val1 is None:
482 491 val1 = next(iter1)
483 492 if val2 is None:
484 493 val2 = next(iter2)
485 494 n = choice(val1, val2)
486 495 yield n
487 496 if val1 == n:
488 497 val1 = None
489 498 if val2 == n:
490 499 val2 = None
491 500 except StopIteration:
492 501 # Flush any remaining values and consume the other one
493 502 it = iter2
494 503 if val1 is not None:
495 504 yield val1
496 505 it = iter1
497 506 elif val2 is not None:
498 507 # might have been equality and both are empty
499 508 yield val2
500 509 for val in it:
501 510 yield val
502 511
503 512 class addset(abstractsmartset):
504 513 """Represent the addition of two sets
505 514
506 515 Wrapper structure for lazily adding two structures without losing much
507 516 performance on the __contains__ method
508 517
509 518 If the ascending attribute is set, that means the two structures are
510 519 ordered in either an ascending or descending way. Therefore, we can add
511 520 them maintaining the order by iterating over both at the same time
512 521
513 522 >>> xs = baseset([0, 3, 2])
514 523 >>> ys = baseset([5, 2, 4])
515 524
516 525 >>> rs = addset(xs, ys)
517 526 >>> bool(rs), 0 in rs, 1 in rs, 5 in rs, rs.first(), rs.last()
518 527 (True, True, False, True, 0, 4)
519 528 >>> rs = addset(xs, baseset([]))
520 529 >>> bool(rs), 0 in rs, 1 in rs, rs.first(), rs.last()
521 530 (True, True, False, 0, 2)
522 531 >>> rs = addset(baseset([]), baseset([]))
523 532 >>> bool(rs), 0 in rs, rs.first(), rs.last()
524 533 (False, False, None, None)
525 534
526 535 iterate unsorted:
527 536 >>> rs = addset(xs, ys)
528 537 >>> # (use generator because pypy could call len())
529 538 >>> list(x for x in rs) # without _genlist
530 539 [0, 3, 2, 5, 4]
531 540 >>> assert not rs._genlist
532 541 >>> len(rs)
533 542 5
534 543 >>> [x for x in rs] # with _genlist
535 544 [0, 3, 2, 5, 4]
536 545 >>> assert rs._genlist
537 546
538 547 iterate ascending:
539 548 >>> rs = addset(xs, ys, ascending=True)
540 549 >>> # (use generator because pypy could call len())
541 550 >>> list(x for x in rs), list(x for x in rs.fastasc()) # without _asclist
542 551 ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
543 552 >>> assert not rs._asclist
544 553 >>> len(rs)
545 554 5
546 555 >>> [x for x in rs], [x for x in rs.fastasc()]
547 556 ([0, 2, 3, 4, 5], [0, 2, 3, 4, 5])
548 557 >>> assert rs._asclist
549 558
550 559 iterate descending:
551 560 >>> rs = addset(xs, ys, ascending=False)
552 561 >>> # (use generator because pypy could call len())
553 562 >>> list(x for x in rs), list(x for x in rs.fastdesc()) # without _asclist
554 563 ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
555 564 >>> assert not rs._asclist
556 565 >>> len(rs)
557 566 5
558 567 >>> [x for x in rs], [x for x in rs.fastdesc()]
559 568 ([5, 4, 3, 2, 0], [5, 4, 3, 2, 0])
560 569 >>> assert rs._asclist
561 570
562 571 iterate ascending without fastasc:
563 572 >>> rs = addset(xs, generatorset(ys), ascending=True)
564 573 >>> assert rs.fastasc is None
565 574 >>> [x for x in rs]
566 575 [0, 2, 3, 4, 5]
567 576
568 577 iterate descending without fastdesc:
569 578 >>> rs = addset(generatorset(xs), ys, ascending=False)
570 579 >>> assert rs.fastdesc is None
571 580 >>> [x for x in rs]
572 581 [5, 4, 3, 2, 0]
573 582 """
574 583 def __init__(self, revs1, revs2, ascending=None):
575 584 self._r1 = revs1
576 585 self._r2 = revs2
577 586 self._iter = None
578 587 self._ascending = ascending
579 588 self._genlist = None
580 589 self._asclist = None
581 590
582 591 def __len__(self):
583 592 return len(self._list)
584 593
585 594 def __nonzero__(self):
586 595 return bool(self._r1) or bool(self._r2)
587 596
588 597 @util.propertycache
589 598 def _list(self):
590 599 if not self._genlist:
591 600 self._genlist = baseset(iter(self))
592 601 return self._genlist
593 602
594 603 def __iter__(self):
595 604 """Iterate over both collections without repeating elements
596 605
597 606 If the ascending attribute is not set, iterate over the first one and
598 607 then over the second one checking for membership on the first one so we
599 608 dont yield any duplicates.
600 609
601 610 If the ascending attribute is set, iterate over both collections at the
602 611 same time, yielding only one value at a time in the given order.
603 612 """
604 613 if self._ascending is None:
605 614 if self._genlist:
606 615 return iter(self._genlist)
607 616 def arbitraryordergen():
608 617 for r in self._r1:
609 618 yield r
610 619 inr1 = self._r1.__contains__
611 620 for r in self._r2:
612 621 if not inr1(r):
613 622 yield r
614 623 return arbitraryordergen()
615 624 # try to use our own fast iterator if it exists
616 625 self._trysetasclist()
617 626 if self._ascending:
618 627 attr = 'fastasc'
619 628 else:
620 629 attr = 'fastdesc'
621 630 it = getattr(self, attr)
622 631 if it is not None:
623 632 return it()
624 633 # maybe half of the component supports fast
625 634 # get iterator for _r1
626 635 iter1 = getattr(self._r1, attr)
627 636 if iter1 is None:
628 637 # let's avoid side effect (not sure it matters)
629 638 iter1 = iter(sorted(self._r1, reverse=not self._ascending))
630 639 else:
631 640 iter1 = iter1()
632 641 # get iterator for _r2
633 642 iter2 = getattr(self._r2, attr)
634 643 if iter2 is None:
635 644 # let's avoid side effect (not sure it matters)
636 645 iter2 = iter(sorted(self._r2, reverse=not self._ascending))
637 646 else:
638 647 iter2 = iter2()
639 648 return _iterordered(self._ascending, iter1, iter2)
640 649
641 650 def _trysetasclist(self):
642 651 """populate the _asclist attribute if possible and necessary"""
643 652 if self._genlist is not None and self._asclist is None:
644 653 self._asclist = sorted(self._genlist)
645 654
646 655 @property
647 656 def fastasc(self):
648 657 self._trysetasclist()
649 658 if self._asclist is not None:
650 659 return self._asclist.__iter__
651 660 iter1 = self._r1.fastasc
652 661 iter2 = self._r2.fastasc
653 662 if None in (iter1, iter2):
654 663 return None
655 664 return lambda: _iterordered(True, iter1(), iter2())
656 665
657 666 @property
658 667 def fastdesc(self):
659 668 self._trysetasclist()
660 669 if self._asclist is not None:
661 670 return self._asclist.__reversed__
662 671 iter1 = self._r1.fastdesc
663 672 iter2 = self._r2.fastdesc
664 673 if None in (iter1, iter2):
665 674 return None
666 675 return lambda: _iterordered(False, iter1(), iter2())
667 676
668 677 def __contains__(self, x):
669 678 return x in self._r1 or x in self._r2
670 679
671 680 def sort(self, reverse=False):
672 681 """Sort the added set
673 682
674 683 For this we use the cached list with all the generated values and if we
675 684 know they are ascending or descending we can sort them in a smart way.
676 685 """
677 686 self._ascending = not reverse
678 687
679 688 def isascending(self):
680 689 return self._ascending is not None and self._ascending
681 690
682 691 def isdescending(self):
683 692 return self._ascending is not None and not self._ascending
684 693
685 694 def istopo(self):
686 695 # not worth the trouble asserting if the two sets combined are still
687 696 # in topographical order. Use the sort() predicate to explicitly sort
688 697 # again instead.
689 698 return False
690 699
691 700 def reverse(self):
692 701 if self._ascending is None:
693 702 self._list.reverse()
694 703 else:
695 704 self._ascending = not self._ascending
696 705
697 706 def first(self):
698 707 for x in self:
699 708 return x
700 709 return None
701 710
702 711 def last(self):
703 712 self.reverse()
704 713 val = self.first()
705 714 self.reverse()
706 715 return val
707 716
708 717 def __repr__(self):
709 718 d = {None: '', False: '-', True: '+'}[self._ascending]
710 719 return '<%s%s %r, %r>' % (type(self).__name__, d, self._r1, self._r2)
711 720
712 721 class generatorset(abstractsmartset):
713 722 """Wrap a generator for lazy iteration
714 723
715 724 Wrapper structure for generators that provides lazy membership and can
716 725 be iterated more than once.
717 726 When asked for membership it generates values until either it finds the
718 727 requested one or has gone through all the elements in the generator
719 728 """
720 729 def __init__(self, gen, iterasc=None):
721 730 """
722 731 gen: a generator producing the values for the generatorset.
723 732 """
724 733 self._gen = gen
725 734 self._asclist = None
726 735 self._cache = {}
727 736 self._genlist = []
728 737 self._finished = False
729 738 self._ascending = True
730 739 if iterasc is not None:
731 740 if iterasc:
732 741 self.fastasc = self._iterator
733 742 self.__contains__ = self._asccontains
734 743 else:
735 744 self.fastdesc = self._iterator
736 745 self.__contains__ = self._desccontains
737 746
738 747 def __nonzero__(self):
739 748 # Do not use 'for r in self' because it will enforce the iteration
740 749 # order (default ascending), possibly unrolling a whole descending
741 750 # iterator.
742 751 if self._genlist:
743 752 return True
744 753 for r in self._consumegen():
745 754 return True
746 755 return False
747 756
748 757 def __contains__(self, x):
749 758 if x in self._cache:
750 759 return self._cache[x]
751 760
752 761 # Use new values only, as existing values would be cached.
753 762 for l in self._consumegen():
754 763 if l == x:
755 764 return True
756 765
757 766 self._cache[x] = False
758 767 return False
759 768
760 769 def _asccontains(self, x):
761 770 """version of contains optimised for ascending generator"""
762 771 if x in self._cache:
763 772 return self._cache[x]
764 773
765 774 # Use new values only, as existing values would be cached.
766 775 for l in self._consumegen():
767 776 if l == x:
768 777 return True
769 778 if l > x:
770 779 break
771 780
772 781 self._cache[x] = False
773 782 return False
774 783
775 784 def _desccontains(self, x):
776 785 """version of contains optimised for descending generator"""
777 786 if x in self._cache:
778 787 return self._cache[x]
779 788
780 789 # Use new values only, as existing values would be cached.
781 790 for l in self._consumegen():
782 791 if l == x:
783 792 return True
784 793 if l < x:
785 794 break
786 795
787 796 self._cache[x] = False
788 797 return False
789 798
790 799 def __iter__(self):
791 800 if self._ascending:
792 801 it = self.fastasc
793 802 else:
794 803 it = self.fastdesc
795 804 if it is not None:
796 805 return it()
797 806 # we need to consume the iterator
798 807 for x in self._consumegen():
799 808 pass
800 809 # recall the same code
801 810 return iter(self)
802 811
803 812 def _iterator(self):
804 813 if self._finished:
805 814 return iter(self._genlist)
806 815
807 816 # We have to use this complex iteration strategy to allow multiple
808 817 # iterations at the same time. We need to be able to catch revision
809 818 # removed from _consumegen and added to genlist in another instance.
810 819 #
811 820 # Getting rid of it would provide an about 15% speed up on this
812 821 # iteration.
813 822 genlist = self._genlist
814 823 nextrev = self._consumegen().next
815 824 _len = len # cache global lookup
816 825 def gen():
817 826 i = 0
818 827 while True:
819 828 if i < _len(genlist):
820 829 yield genlist[i]
821 830 else:
822 831 yield nextrev()
823 832 i += 1
824 833 return gen()
825 834
826 835 def _consumegen(self):
827 836 cache = self._cache
828 837 genlist = self._genlist.append
829 838 for item in self._gen:
830 839 cache[item] = True
831 840 genlist(item)
832 841 yield item
833 842 if not self._finished:
834 843 self._finished = True
835 844 asc = self._genlist[:]
836 845 asc.sort()
837 846 self._asclist = asc
838 847 self.fastasc = asc.__iter__
839 848 self.fastdesc = asc.__reversed__
840 849
841 850 def __len__(self):
842 851 for x in self._consumegen():
843 852 pass
844 853 return len(self._genlist)
845 854
846 855 def sort(self, reverse=False):
847 856 self._ascending = not reverse
848 857
849 858 def reverse(self):
850 859 self._ascending = not self._ascending
851 860
852 861 def isascending(self):
853 862 return self._ascending
854 863
855 864 def isdescending(self):
856 865 return not self._ascending
857 866
858 867 def istopo(self):
859 868 # not worth the trouble asserting if the two sets combined are still
860 869 # in topographical order. Use the sort() predicate to explicitly sort
861 870 # again instead.
862 871 return False
863 872
864 873 def first(self):
865 874 if self._ascending:
866 875 it = self.fastasc
867 876 else:
868 877 it = self.fastdesc
869 878 if it is None:
870 879 # we need to consume all and try again
871 880 for x in self._consumegen():
872 881 pass
873 882 return self.first()
874 883 return next(it(), None)
875 884
876 885 def last(self):
877 886 if self._ascending:
878 887 it = self.fastdesc
879 888 else:
880 889 it = self.fastasc
881 890 if it is None:
882 891 # we need to consume all and try again
883 892 for x in self._consumegen():
884 893 pass
885 894 return self.first()
886 895 return next(it(), None)
887 896
888 897 def __repr__(self):
889 898 d = {False: '-', True: '+'}[self._ascending]
890 899 return '<%s%s>' % (type(self).__name__, d)
891 900
892 901 class spanset(abstractsmartset):
893 902 """Duck type for baseset class which represents a range of revisions and
894 903 can work lazily and without having all the range in memory
895 904
896 905 Note that spanset(x, y) behave almost like xrange(x, y) except for two
897 906 notable points:
898 907 - when x < y it will be automatically descending,
899 908 - revision filtered with this repoview will be skipped.
900 909
901 910 """
902 911 def __init__(self, repo, start=0, end=None):
903 912 """
904 913 start: first revision included the set
905 914 (default to 0)
906 915 end: first revision excluded (last+1)
907 916 (default to len(repo)
908 917
909 918 Spanset will be descending if `end` < `start`.
910 919 """
911 920 if end is None:
912 921 end = len(repo)
913 922 self._ascending = start <= end
914 923 if not self._ascending:
915 924 start, end = end + 1, start +1
916 925 self._start = start
917 926 self._end = end
918 927 self._hiddenrevs = repo.changelog.filteredrevs
919 928
920 929 def sort(self, reverse=False):
921 930 self._ascending = not reverse
922 931
923 932 def reverse(self):
924 933 self._ascending = not self._ascending
925 934
926 935 def istopo(self):
927 936 # not worth the trouble asserting if the two sets combined are still
928 937 # in topographical order. Use the sort() predicate to explicitly sort
929 938 # again instead.
930 939 return False
931 940
932 941 def _iterfilter(self, iterrange):
933 942 s = self._hiddenrevs
934 943 for r in iterrange:
935 944 if r not in s:
936 945 yield r
937 946
938 947 def __iter__(self):
939 948 if self._ascending:
940 949 return self.fastasc()
941 950 else:
942 951 return self.fastdesc()
943 952
944 953 def fastasc(self):
945 954 iterrange = xrange(self._start, self._end)
946 955 if self._hiddenrevs:
947 956 return self._iterfilter(iterrange)
948 957 return iter(iterrange)
949 958
950 959 def fastdesc(self):
951 960 iterrange = xrange(self._end - 1, self._start - 1, -1)
952 961 if self._hiddenrevs:
953 962 return self._iterfilter(iterrange)
954 963 return iter(iterrange)
955 964
956 965 def __contains__(self, rev):
957 966 hidden = self._hiddenrevs
958 967 return ((self._start <= rev < self._end)
959 968 and not (hidden and rev in hidden))
960 969
961 970 def __nonzero__(self):
962 971 for r in self:
963 972 return True
964 973 return False
965 974
966 975 def __len__(self):
967 976 if not self._hiddenrevs:
968 977 return abs(self._end - self._start)
969 978 else:
970 979 count = 0
971 980 start = self._start
972 981 end = self._end
973 982 for rev in self._hiddenrevs:
974 983 if (end < rev <= start) or (start <= rev < end):
975 984 count += 1
976 985 return abs(self._end - self._start) - count
977 986
978 987 def isascending(self):
979 988 return self._ascending
980 989
981 990 def isdescending(self):
982 991 return not self._ascending
983 992
984 993 def first(self):
985 994 if self._ascending:
986 995 it = self.fastasc
987 996 else:
988 997 it = self.fastdesc
989 998 for x in it():
990 999 return x
991 1000 return None
992 1001
993 1002 def last(self):
994 1003 if self._ascending:
995 1004 it = self.fastdesc
996 1005 else:
997 1006 it = self.fastasc
998 1007 for x in it():
999 1008 return x
1000 1009 return None
1001 1010
1002 1011 def __repr__(self):
1003 1012 d = {False: '-', True: '+'}[self._ascending]
1004 1013 return '<%s%s %d:%d>' % (type(self).__name__, d,
1005 1014 self._start, self._end - 1)
1006 1015
1007 1016 class fullreposet(spanset):
1008 1017 """a set containing all revisions in the repo
1009 1018
1010 1019 This class exists to host special optimization and magic to handle virtual
1011 1020 revisions such as "null".
1012 1021 """
1013 1022
1014 1023 def __init__(self, repo):
1015 1024 super(fullreposet, self).__init__(repo)
1016 1025
1017 1026 def __and__(self, other):
1018 1027 """As self contains the whole repo, all of the other set should also be
1019 1028 in self. Therefore `self & other = other`.
1020 1029
1021 1030 This boldly assumes the other contains valid revs only.
1022 1031 """
1023 1032 # other not a smartset, make is so
1024 1033 if not util.safehasattr(other, 'isascending'):
1025 1034 # filter out hidden revision
1026 1035 # (this boldly assumes all smartset are pure)
1027 1036 #
1028 1037 # `other` was used with "&", let's assume this is a set like
1029 1038 # object.
1030 1039 other = baseset(other - self._hiddenrevs)
1031 1040
1032 1041 other.sort(reverse=self.isdescending())
1033 1042 return other
1034 1043
1035 1044 def prettyformat(revs):
1036 1045 lines = []
1037 1046 rs = repr(revs)
1038 1047 p = 0
1039 1048 while p < len(rs):
1040 1049 q = rs.find('<', p + 1)
1041 1050 if q < 0:
1042 1051 q = len(rs)
1043 1052 l = rs.count('<', 0, p) - rs.count('>', 0, p)
1044 1053 assert l >= 0
1045 1054 lines.append((l, rs[p:q].rstrip()))
1046 1055 p = q
1047 1056 return '\n'.join(' ' * l + s for l, s in lines)
General Comments 0
You need to be logged in to leave comments. Login now