/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/versionedfile.py

  • Committer: Frank Aspell
  • Date: 2009-02-22 16:54:02 UTC
  • mto: This revision was merged to the branch mainline in revision 4256.
  • Revision ID: frankaspell@googlemail.com-20090222165402-2myrucnu7er5w4ha
Fixing various typos

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/versionedfile.py
1
 
# Copyright (C) 2006-2010 Canonical Ltd
 
1
# Copyright (C) 2005, 2006, 2007, 2008 Canonical Ltd
2
2
#
3
3
# Authors:
4
4
#   Johan Rydberg <jrydberg@gnu.org>
15
15
#
16
16
# You should have received a copy of the GNU General Public License
17
17
# along with this program; if not, write to the Free Software
18
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
18
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19
19
 
20
20
"""Versioned text file storage api."""
21
21
 
30
30
import urllib
31
31
 
32
32
from bzrlib import (
33
 
    annotate,
34
33
    errors,
35
 
    graph as _mod_graph,
36
 
    groupcompress,
37
34
    index,
38
35
    knit,
39
36
    osutils,
42
39
    revision,
43
40
    ui,
44
41
    )
45
 
from bzrlib.graph import DictParentsProvider, Graph, StackedParentsProvider
 
42
from bzrlib.graph import DictParentsProvider, Graph, _StackedParentsProvider
46
43
from bzrlib.transport.memory import MemoryTransport
47
44
""")
 
45
from bzrlib.inter import InterObject
48
46
from bzrlib.registry import Registry
49
47
from bzrlib.symbol_versioning import *
50
48
from bzrlib.textmerge import TextMerge
51
 
from bzrlib import bencode
 
49
from bzrlib.util import bencode
52
50
 
53
51
 
54
52
adapter_registry = Registry()
70
68
 
71
69
class ContentFactory(object):
72
70
    """Abstract interface for insertion and retrieval from a VersionedFile.
73
 
 
 
71
    
74
72
    :ivar sha1: None, or the sha1 of the content fulltext.
75
73
    :ivar storage_kind: The native storage kind of this factory. One of
76
74
        'mpdiff', 'knit-annotated-ft', 'knit-annotated-delta', 'knit-ft',
160
158
 
161
159
class AbsentContentFactory(ContentFactory):
162
160
    """A placeholder content factory for unavailable texts.
163
 
 
 
161
    
164
162
    :ivar sha1: None.
165
163
    :ivar storage_kind: 'absent'.
166
164
    :ivar key: The key of this content. Each key is a tuple with a single
175
173
        self.key = key
176
174
        self.parents = None
177
175
 
178
 
    def get_bytes_as(self, storage_kind):
179
 
        raise ValueError('A request was made for key: %s, but that'
180
 
                         ' content is not available, and the calling'
181
 
                         ' code does not handle if it is missing.'
182
 
                         % (self.key,))
183
 
 
184
176
 
185
177
class AdapterFactory(ContentFactory):
186
178
    """A content factory to adapt between key prefix's."""
208
200
 
209
201
class VersionedFile(object):
210
202
    """Versioned text file storage.
211
 
 
 
203
    
212
204
    A versioned file manages versions of line-based text files,
213
205
    keeping track of the originating version for each line.
214
206
 
252
244
    def insert_record_stream(self, stream):
253
245
        """Insert a record stream into this versioned file.
254
246
 
255
 
        :param stream: A stream of records to insert.
 
247
        :param stream: A stream of records to insert. 
256
248
        :return: None
257
249
        :seealso VersionedFile.get_record_stream:
258
250
        """
277
269
            the data back accurately. (Checking the lines have been split
278
270
            correctly is expensive and extremely unlikely to catch bugs so it
279
271
            is not done at runtime unless check_content is True.)
280
 
        :param parent_texts: An optional dictionary containing the opaque
 
272
        :param parent_texts: An optional dictionary containing the opaque 
281
273
            representations of some or all of the parents of version_id to
282
274
            allow delta optimisations.  VERY IMPORTANT: the texts must be those
283
275
            returned by add_lines or data corruption can be caused.
311
303
        parent_texts=None, nostore_sha=None, random_id=False,
312
304
        check_content=True, left_matching_blocks=None):
313
305
        """Add lines to the versioned file, allowing ghosts to be present.
314
 
 
 
306
        
315
307
        This takes the same parameters as add_lines and returns the same.
316
308
        """
317
309
        self._check_write_ok()
341
333
 
342
334
    def get_format_signature(self):
343
335
        """Get a text description of the data encoding in this file.
344
 
 
 
336
        
345
337
        :since: 0.90
346
338
        """
347
339
        raise NotImplementedError(self.get_format_signature)
468
460
        if isinstance(version_ids, basestring):
469
461
            version_ids = [version_ids]
470
462
        raise NotImplementedError(self.get_ancestry)
471
 
 
 
463
        
472
464
    def get_ancestry_with_ghosts(self, version_ids):
473
465
        """Return a list of all ancestors of given version(s). This
474
466
        will not include the null revision.
475
467
 
476
468
        Must raise RevisionNotPresent if any of the given versions are
477
469
        not present in file history.
478
 
 
 
470
        
479
471
        Ghosts that are known about will be included in ancestry list,
480
472
        but are not explicitly marked.
481
473
        """
482
474
        raise NotImplementedError(self.get_ancestry_with_ghosts)
483
 
 
 
475
    
484
476
    def get_parent_map(self, version_ids):
485
477
        """Get a map of the parents of version_ids.
486
478
 
549
541
        unchanged   Alive in both a and b (possibly created in both)
550
542
        new-a       Created in a
551
543
        new-b       Created in b
552
 
        ghost-a     Killed in a, unborn in b
 
544
        ghost-a     Killed in a, unborn in b    
553
545
        ghost-b     Killed in b, unborn in a
554
546
        irrelevant  Not in either revision
555
547
        """
556
548
        raise NotImplementedError(VersionedFile.plan_merge)
557
 
 
 
549
        
558
550
    def weave_merge(self, plan, a_marker=TextMerge.A_MARKER,
559
551
                    b_marker=TextMerge.B_MARKER):
560
552
        return PlanWeaveMerge(plan, a_marker, b_marker).merge_lines()[0]
562
554
 
563
555
class RecordingVersionedFilesDecorator(object):
564
556
    """A minimal versioned files that records calls made on it.
565
 
 
 
557
    
566
558
    Only enough methods have been added to support tests using it to date.
567
559
 
568
560
    :ivar calls: A list of the calls made; can be reset at any time by
571
563
 
572
564
    def __init__(self, backing_vf):
573
565
        """Create a RecordingVersionedFilesDecorator decorating backing_vf.
574
 
 
 
566
        
575
567
        :param backing_vf: The versioned file to answer all methods.
576
568
        """
577
569
        self._backing_vf = backing_vf
663
655
 
664
656
    def unmap(self, partition_id):
665
657
        """Map a partitioned storage id back to a key prefix.
666
 
 
 
658
        
667
659
        :param partition_id: The underlying partition id.
668
660
        :return: As much of a key (or prefix) as is derivable from the partition
669
661
            id.
701
693
 
702
694
class PrefixMapper(URLEscapeMapper):
703
695
    """A key mapper that extracts the first component of a key.
704
 
 
 
696
    
705
697
    This mapper is for use with a transport based backend.
706
698
    """
707
699
 
740
732
 
741
733
class HashEscapedPrefixMapper(HashPrefixMapper):
742
734
    """Combines the escaped first component of a key with a hash.
743
 
 
 
735
    
744
736
    This mapper is for use with a transport based backend.
745
737
    """
746
738
 
802
794
        check_content=True):
803
795
        """Add a text to the store.
804
796
 
805
 
        :param key: The key tuple of the text to add. If the last element is
806
 
            None, a CHK string will be generated during the addition.
 
797
        :param key: The key tuple of the text to add.
807
798
        :param parents: The parents key tuples of the text to add.
808
799
        :param lines: A list of lines. Each line must be a bytestring. And all
809
800
            of them except the last must be terminated with \n and contain no
813
804
            the data back accurately. (Checking the lines have been split
814
805
            correctly is expensive and extremely unlikely to catch bugs so it
815
806
            is not done at runtime unless check_content is True.)
816
 
        :param parent_texts: An optional dictionary containing the opaque
 
807
        :param parent_texts: An optional dictionary containing the opaque 
817
808
            representations of some or all of the parents of version_id to
818
809
            allow delta optimisations.  VERY IMPORTANT: the texts must be those
819
810
            returned by add_lines or data corruption can be caused.
836
827
        """
837
828
        raise NotImplementedError(self.add_lines)
838
829
 
839
 
    def _add_text(self, key, parents, text, nostore_sha=None, random_id=False):
840
 
        """Add a text to the store.
841
 
 
842
 
        This is a private function for use by CommitBuilder.
843
 
 
844
 
        :param key: The key tuple of the text to add. If the last element is
845
 
            None, a CHK string will be generated during the addition.
846
 
        :param parents: The parents key tuples of the text to add.
847
 
        :param text: A string containing the text to be committed.
848
 
        :param nostore_sha: Raise ExistingContent and do not add the lines to
849
 
            the versioned file if the digest of the lines matches this.
850
 
        :param random_id: If True a random id has been selected rather than
851
 
            an id determined by some deterministic process such as a converter
852
 
            from a foreign VCS. When True the backend may choose not to check
853
 
            for uniqueness of the resulting key within the versioned file, so
854
 
            this should only be done when the result is expected to be unique
855
 
            anyway.
856
 
        :param check_content: If True, the lines supplied are verified to be
857
 
            bytestrings that are correctly formed lines.
858
 
        :return: The text sha1, the number of bytes in the text, and an opaque
859
 
                 representation of the inserted version which can be provided
860
 
                 back to future _add_text calls in the parent_texts dictionary.
861
 
        """
862
 
        # The default implementation just thunks over to .add_lines(),
863
 
        # inefficient, but it works.
864
 
        return self.add_lines(key, parents, osutils.split_lines(text),
865
 
                              nostore_sha=nostore_sha,
866
 
                              random_id=random_id,
867
 
                              check_content=True)
868
 
 
869
830
    def add_mpdiffs(self, records):
870
831
        """Add mpdiffs to this VersionedFile.
871
832
 
913
874
        raise NotImplementedError(self.annotate)
914
875
 
915
876
    def check(self, progress_bar=None):
916
 
        """Check this object for integrity.
917
 
        
918
 
        :param progress_bar: A progress bar to output as the check progresses.
919
 
        :param keys: Specific keys within the VersionedFiles to check. When
920
 
            this parameter is not None, check() becomes a generator as per
921
 
            get_record_stream. The difference to get_record_stream is that
922
 
            more or deeper checks will be performed.
923
 
        :return: None, or if keys was supplied a generator as per
924
 
            get_record_stream.
925
 
        """
 
877
        """Check this object for integrity."""
926
878
        raise NotImplementedError(self.check)
927
879
 
928
880
    @staticmethod
929
881
    def check_not_reserved_id(version_id):
930
882
        revision.check_not_reserved_id(version_id)
931
883
 
932
 
    def clear_cache(self):
933
 
        """Clear whatever caches this VersionedFile holds.
934
 
 
935
 
        This is generally called after an operation has been performed, when we
936
 
        don't expect to be using this versioned file again soon.
937
 
        """
938
 
 
939
884
    def _check_lines_not_unicode(self, lines):
940
885
        """Check that lines being added to a versioned file are not unicode."""
941
886
        for line in lines:
948
893
            if '\n' in line[:-1]:
949
894
                raise errors.BzrBadParameterContainsNewline("lines")
950
895
 
951
 
    def get_known_graph_ancestry(self, keys):
952
 
        """Get a KnownGraph instance with the ancestry of keys."""
953
 
        # most basic implementation is a loop around get_parent_map
954
 
        pending = set(keys)
955
 
        parent_map = {}
956
 
        while pending:
957
 
            this_parent_map = self.get_parent_map(pending)
958
 
            parent_map.update(this_parent_map)
959
 
            pending = set()
960
 
            map(pending.update, this_parent_map.itervalues())
961
 
            pending = pending.difference(parent_map)
962
 
        kg = _mod_graph.KnownGraph(parent_map)
963
 
        return kg
964
 
 
965
896
    def get_parent_map(self, keys):
966
897
        """Get a map of the parents of keys.
967
898
 
1012
943
    def insert_record_stream(self, stream):
1013
944
        """Insert a record stream into this container.
1014
945
 
1015
 
        :param stream: A stream of records to insert.
 
946
        :param stream: A stream of records to insert. 
1016
947
        :return: None
1017
948
        :seealso VersionedFile.get_record_stream:
1018
949
        """
1159
1090
            result.append((prefix + (origin,), line))
1160
1091
        return result
1161
1092
 
1162
 
    def get_annotator(self):
1163
 
        return annotate.Annotator(self)
1164
 
 
1165
 
    def check(self, progress_bar=None, keys=None):
 
1093
    def check(self, progress_bar=None):
1166
1094
        """See VersionedFiles.check()."""
1167
 
        # XXX: This is over-enthusiastic but as we only thunk for Weaves today
1168
 
        # this is tolerable. Ideally we'd pass keys down to check() and 
1169
 
        # have the older VersiondFile interface updated too.
1170
1095
        for prefix, vf in self._iter_all_components():
1171
1096
            vf.check()
1172
 
        if keys is not None:
1173
 
            return self.get_record_stream(keys, 'unordered', True)
1174
1097
 
1175
1098
    def get_parent_map(self, keys):
1176
1099
        """Get a map of the parents of keys.
1254
1177
    def insert_record_stream(self, stream):
1255
1178
        """Insert a record stream into this container.
1256
1179
 
1257
 
        :param stream: A stream of records to insert.
 
1180
        :param stream: A stream of records to insert. 
1258
1181
        :return: None
1259
1182
        :seealso VersionedFile.get_record_stream:
1260
1183
        """
1408
1331
            result[revision.NULL_REVISION] = ()
1409
1332
        self._providers = self._providers[:1] + self.fallback_versionedfiles
1410
1333
        result.update(
1411
 
            StackedParentsProvider(self._providers).get_parent_map(keys))
 
1334
            _StackedParentsProvider(self._providers).get_parent_map(keys))
1412
1335
        for key, parents in result.iteritems():
1413
1336
            if parents == ():
1414
1337
                result[key] = (revision.NULL_REVISION,)
1417
1340
 
1418
1341
class PlanWeaveMerge(TextMerge):
1419
1342
    """Weave merge that takes a plan as its input.
1420
 
 
 
1343
    
1421
1344
    This exists so that VersionedFile.plan_merge is implementable.
1422
1345
    Most callers will want to use WeaveMerge instead.
1423
1346
    """
1425
1348
    def __init__(self, plan, a_marker=TextMerge.A_MARKER,
1426
1349
                 b_marker=TextMerge.B_MARKER):
1427
1350
        TextMerge.__init__(self, a_marker, b_marker)
1428
 
        self.plan = list(plan)
 
1351
        self.plan = plan
1429
1352
 
1430
1353
    def _merge_struct(self):
1431
1354
        lines_a = []
1444
1367
                yield(lines_a,)
1445
1368
            else:
1446
1369
                yield (lines_a, lines_b)
1447
 
 
 
1370
       
1448
1371
        # We previously considered either 'unchanged' or 'killed-both' lines
1449
1372
        # to be possible places to resynchronize.  However, assuming agreement
1450
1373
        # on killed-both lines may be too aggressive. -- mbp 20060324
1456
1379
                lines_a = []
1457
1380
                lines_b = []
1458
1381
                ch_a = ch_b = False
1459
 
 
 
1382
                
1460
1383
            if state == 'unchanged':
1461
1384
                if line:
1462
1385
                    yield ([line],)
1478
1401
            elif state == 'conflicted-b':
1479
1402
                ch_b = ch_a = True
1480
1403
                lines_b.append(line)
1481
 
            elif state == 'killed-both':
1482
 
                # This counts as a change, even though there is no associated
1483
 
                # line
1484
 
                ch_b = ch_a = True
1485
1404
            else:
1486
1405
                if state not in ('irrelevant', 'ghost-a', 'ghost-b',
1487
 
                        'killed-base'):
 
1406
                        'killed-base', 'killed-both'):
1488
1407
                    raise AssertionError(state)
1489
1408
        for struct in outstanding_struct():
1490
1409
            yield struct
1491
1410
 
1492
 
    def base_from_plan(self):
1493
 
        """Construct a BASE file from the plan text."""
1494
 
        base_lines = []
1495
 
        for state, line in self.plan:
1496
 
            if state in ('killed-a', 'killed-b', 'killed-both', 'unchanged'):
1497
 
                # If unchanged, then this line is straight from base. If a or b
1498
 
                # or both killed the line, then it *used* to be in base.
1499
 
                base_lines.append(line)
1500
 
            else:
1501
 
                if state not in ('killed-base', 'irrelevant',
1502
 
                                 'ghost-a', 'ghost-b',
1503
 
                                 'new-a', 'new-b',
1504
 
                                 'conflicted-a', 'conflicted-b'):
1505
 
                    # killed-base, irrelevant means it doesn't apply
1506
 
                    # ghost-a/ghost-b are harder to say for sure, but they
1507
 
                    # aren't in the 'inc_c' which means they aren't in the
1508
 
                    # shared base of a & b. So we don't include them.  And
1509
 
                    # obviously if the line is newly inserted, it isn't in base
1510
 
 
1511
 
                    # If 'conflicted-a' or b, then it is new vs one base, but
1512
 
                    # old versus another base. However, if we make it present
1513
 
                    # in the base, it will be deleted from the target, and it
1514
 
                    # seems better to get a line doubled in the merge result,
1515
 
                    # rather than have it deleted entirely.
1516
 
                    # Example, each node is the 'text' at that point:
1517
 
                    #           MN
1518
 
                    #          /   \
1519
 
                    #        MaN   MbN
1520
 
                    #         |  X  |
1521
 
                    #        MabN MbaN
1522
 
                    #          \   /
1523
 
                    #           ???
1524
 
                    # There was a criss-cross conflict merge. Both sides
1525
 
                    # include the other, but put themselves first.
1526
 
                    # Weave marks this as a 'clean' merge, picking OTHER over
1527
 
                    # THIS. (Though the details depend on order inserted into
1528
 
                    # weave, etc.)
1529
 
                    # LCA generates a plan:
1530
 
                    # [('unchanged', M),
1531
 
                    #  ('conflicted-b', b),
1532
 
                    #  ('unchanged', a),
1533
 
                    #  ('conflicted-a', b),
1534
 
                    #  ('unchanged', N)]
1535
 
                    # If you mark 'conflicted-*' as part of BASE, then a 3-way
1536
 
                    # merge tool will cleanly generate "MaN" (as BASE vs THIS
1537
 
                    # removes one 'b', and BASE vs OTHER removes the other)
1538
 
                    # If you include neither, 3-way creates a clean "MbabN" as
1539
 
                    # THIS adds one 'b', and OTHER does too.
1540
 
                    # It seems that having the line 2 times is better than
1541
 
                    # having it omitted. (Easier to manually delete than notice
1542
 
                    # it needs to be added.)
1543
 
                    raise AssertionError('Unknown state: %s' % (state,))
1544
 
        return base_lines
1545
 
 
1546
1411
 
1547
1412
class WeaveMerge(PlanWeaveMerge):
1548
1413
    """Weave merge that takes a VersionedFile and two versions as its input."""
1549
1414
 
1550
 
    def __init__(self, versionedfile, ver_a, ver_b,
 
1415
    def __init__(self, versionedfile, ver_a, ver_b, 
1551
1416
        a_marker=PlanWeaveMerge.A_MARKER, b_marker=PlanWeaveMerge.B_MARKER):
1552
1417
        plan = versionedfile.plan_merge(ver_a, ver_b)
1553
1418
        PlanWeaveMerge.__init__(self, plan, a_marker, b_marker)
1554
1419
 
1555
1420
 
1556
1421
class VirtualVersionedFiles(VersionedFiles):
1557
 
    """Dummy implementation for VersionedFiles that uses other functions for
 
1422
    """Dummy implementation for VersionedFiles that uses other functions for 
1558
1423
    obtaining fulltexts and parent maps.
1559
1424
 
1560
 
    This is always on the bottom of the stack and uses string keys
 
1425
    This is always on the bottom of the stack and uses string keys 
1561
1426
    (rather than tuples) internally.
1562
1427
    """
1563
1428
 
1565
1430
        """Create a VirtualVersionedFiles.
1566
1431
 
1567
1432
        :param get_parent_map: Same signature as Repository.get_parent_map.
1568
 
        :param get_lines: Should return lines for specified key or None if
 
1433
        :param get_lines: Should return lines for specified key or None if 
1569
1434
                          not available.
1570
1435
        """
1571
1436
        super(VirtualVersionedFiles, self).__init__()
1572
1437
        self._get_parent_map = get_parent_map
1573
1438
        self._get_lines = get_lines
1574
 
 
 
1439
        
1575
1440
    def check(self, progressbar=None):
1576
1441
        """See VersionedFiles.check.
1577
1442
 
1619
1484
        """See VersionedFile.iter_lines_added_or_present_in_versions()."""
1620
1485
        for i, (key,) in enumerate(keys):
1621
1486
            if pb is not None:
1622
 
                pb.update("Finding changed lines", i, len(keys))
 
1487
                pb.update("iterating texts", i, len(keys))
1623
1488
            for l in self._get_lines(key):
1624
1489
                yield (l, key)
1625
1490
 
1646
1511
            record.get_bytes_as(record.storage_kind) call.
1647
1512
        """
1648
1513
        self._bytes_iterator = bytes_iterator
1649
 
        self._kind_factory = {
1650
 
            'fulltext': fulltext_network_to_record,
1651
 
            'groupcompress-block': groupcompress.network_block_to_records,
1652
 
            'knit-ft-gz': knit.knit_network_to_record,
1653
 
            'knit-delta-gz': knit.knit_network_to_record,
1654
 
            'knit-annotated-ft-gz': knit.knit_network_to_record,
1655
 
            'knit-annotated-delta-gz': knit.knit_network_to_record,
1656
 
            'knit-delta-closure': knit.knit_delta_closure_to_records,
 
1514
        self._kind_factory = {'knit-ft-gz':knit.knit_network_to_record,
 
1515
            'knit-delta-gz':knit.knit_network_to_record,
 
1516
            'knit-annotated-ft-gz':knit.knit_network_to_record,
 
1517
            'knit-annotated-delta-gz':knit.knit_network_to_record,
 
1518
            'knit-delta-closure':knit.knit_delta_closure_to_records,
 
1519
            'fulltext':fulltext_network_to_record,
1657
1520
            }
1658
1521
 
1659
1522
    def read(self):
1671
1534
def fulltext_network_to_record(kind, bytes, line_end):
1672
1535
    """Convert a network fulltext record to record."""
1673
1536
    meta_len, = struct.unpack('!L', bytes[line_end:line_end+4])
1674
 
    record_meta = bytes[line_end+4:line_end+4+meta_len]
 
1537
    record_meta = record_bytes[line_end+4:line_end+4+meta_len]
1675
1538
    key, parents = bencode.bdecode_as_tuple(record_meta)
1676
1539
    if parents == 'nil':
1677
1540
        parents = None
1678
 
    fulltext = bytes[line_end+4+meta_len:]
1679
 
    return [FulltextContentFactory(key, parents, None, fulltext)]
 
1541
    fulltext = record_bytes[line_end+4+meta_len:]
 
1542
    return FulltextContentFactory(key, parents, None, fulltext)
1680
1543
 
1681
1544
 
1682
1545
def _length_prefix(bytes):
1683
1546
    return struct.pack('!L', len(bytes))
1684
1547
 
1685
1548
 
1686
 
def record_to_fulltext_bytes(record):
 
1549
def record_to_fulltext_bytes(self, record):
1687
1550
    if record.parents is None:
1688
1551
        parents = 'nil'
1689
1552
    else:
1692
1555
    record_content = record.get_bytes_as('fulltext')
1693
1556
    return "fulltext\n%s%s%s" % (
1694
1557
        _length_prefix(record_meta), record_meta, record_content)
1695
 
 
1696
 
 
1697
 
def sort_groupcompress(parent_map):
1698
 
    """Sort and group the keys in parent_map into groupcompress order.
1699
 
 
1700
 
    groupcompress is defined (currently) as reverse-topological order, grouped
1701
 
    by the key prefix.
1702
 
 
1703
 
    :return: A sorted-list of keys
1704
 
    """
1705
 
    # gc-optimal ordering is approximately reverse topological,
1706
 
    # properly grouped by file-id.
1707
 
    per_prefix_map = {}
1708
 
    for item in parent_map.iteritems():
1709
 
        key = item[0]
1710
 
        if isinstance(key, str) or len(key) == 1:
1711
 
            prefix = ''
1712
 
        else:
1713
 
            prefix = key[0]
1714
 
        try:
1715
 
            per_prefix_map[prefix].append(item)
1716
 
        except KeyError:
1717
 
            per_prefix_map[prefix] = [item]
1718
 
 
1719
 
    present_keys = []
1720
 
    for prefix in sorted(per_prefix_map):
1721
 
        present_keys.extend(reversed(tsort.topo_sort(per_prefix_map[prefix])))
1722
 
    return present_keys