← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to multiparent.py

  • Committer: Aaron Bentley
  • Date: 2007-04-14 05:52:01 UTC
  • mto: (2520.4.1 bzr.mpbundle)
  • mto: This revision was merged to the branch mainline in revision 2631.
  • Revision ID: abentley@panoramicfeedback.com-20070414055201-hmz83pf1w4whsi79
Add build ranking

Show diffs side-by-side

added added

removed removed

Lines of Context:
multiparent.py
285
285
        self.add_diff(diff, version_id, parent_ids)
286
286
        self._lines[version_id] = lines
287
287
 
 
288
    def get_parents(self, version_id):
 
289
        return self._parents[version_id]
 
290
 
288
291
    def make_snapshot(self, version_id):
289
292
        snapdiff = MultiParent([NewText(self.cache_version(version_id))])
290
293
        self._snapshots.add(version_id)
353
356
        return snapshots
354
357
 
355
358
    def select_by_size(self, num):
 
359
        """Select snapshots for minimum output size"""
 
360
        num -= len(self._snapshots)
 
361
        return get_size_ranking()[:num]
 
362
 
 
363
    def get_size_ranking(self):
356
364
        versions = []
357
365
        new_snapshots = set()
358
 
        num -= len(self._snapshots)
359
366
        for version_id in self.versions():
360
367
            if version_id in self._snapshots:
361
368
                continue
366
373
        versions.sort()
367
374
        return [v for n, v in versions[:num]]
368
375
 
 
376
    def get_build_ranking(self):
 
377
        could_avoid = {}
 
378
        referenced_by = {}
 
379
        for version_id in topo_iter(self):
 
380
            could_avoid[version_id] = set()
 
381
            if version_id not in self._snapshots:
 
382
                for parent_id in self._parents[version_id]:
 
383
                    could_avoid[version_id].update(could_avoid[parent_id])
 
384
                could_avoid[version_id].update(self._parents)
 
385
                could_avoid[version_id].discard(version_id)
 
386
            for avoid_id in could_avoid[version_id]:
 
387
                referenced_by.setdefault(avoid_id, set()).add(version_id)
 
388
        available_versions = list(self.versions())
 
389
        ranking = []
 
390
        while len(available_versions) > 0:
 
391
            available_versions.sort(key=lambda x:
 
392
                len(could_avoid[x]) *
 
393
                len(referenced_by.get(x, [])))
 
394
            selected = available_versions.pop()
 
395
            ranking.append(selected)
 
396
            for version_id in referenced_by[selected]:
 
397
                could_avoid[version_id].difference_update(
 
398
                    could_avoid[selected])
 
399
            for version_id in could_avoid[selected]:
 
400
                referenced_by[version_id].difference_update(
 
401
                    referenced_by[selected]
 
402
                )
 
403
        return ranking
 
404
 
369
405
    def clear_cache(self):
370
406
        self._lines.clear()
371
407