/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/dirstate.py

  • Committer: Martin Pool
  • Date: 2009-03-13 07:54:48 UTC
  • mfrom: (4144 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4189.
  • Revision ID: mbp@sourcefrog.net-20090313075448-jlz1t7baz7gzipqn
merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/dirstate.py
99
99
 
100
100
--- Format 1 had the following different definition: ---
101
101
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
102
 
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target, 
 
102
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
103
103
    {PARENT ROW}
104
104
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
105
105
    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
130
130
operations for the less common but still occurs a lot status/diff/commit
131
131
on specific files). Operations on specific files involve a scan for all
132
132
the children of a path, *in every involved tree*, which the current
133
 
format did not accommodate. 
 
133
format did not accommodate.
134
134
----
135
135
 
136
136
Design priorities:
148
148
 
149
149
Memory representation:
150
150
 vector of all directories, and vector of the childen ?
151
 
   i.e. 
152
 
     root_entrie = (direntry for root, [parent_direntries_for_root]), 
 
151
   i.e.
 
152
     root_entrie = (direntry for root, [parent_direntries_for_root]),
153
153
     dirblocks = [
154
154
     ('', ['data for achild', 'data for bchild', 'data for cchild'])
155
155
     ('dir', ['achild', 'cchild', 'echild'])
158
158
    - in-order for serialisation - this is 'dirblock' grouping.
159
159
    - insertion of a file '/a' affects only the '/' child-vector, that is, to
160
160
      insert 10K elements from scratch does not generates O(N^2) memoves of a
161
 
      single vector, rather each individual, which tends to be limited to a 
162
 
      manageable number. Will scale badly on trees with 10K entries in a 
 
161
      single vector, rather each individual, which tends to be limited to a
 
162
      manageable number. Will scale badly on trees with 10K entries in a
163
163
      single directory. compare with Inventory.InventoryDirectory which has
164
164
      a dictionary for the children. No bisect capability, can only probe for
165
165
      exact matches, or grab all elements and sort.
166
166
    - What's the risk of error here? Once we have the base format being processed
167
 
      we should have a net win regardless of optimality. So we are going to 
 
167
      we should have a net win regardless of optimality. So we are going to
168
168
      go with what seems reasonable.
169
169
open questions:
170
170
 
331
331
        # IN_MEMORY_UNMODIFIED indicates that what we have in memory
332
332
        #   is the same as is on disk
333
333
        # IN_MEMORY_MODIFIED indicates that we have a modified version
334
 
        #   of what is on disk. 
 
334
        #   of what is on disk.
335
335
        # In future we will add more granularity, for instance _dirblock_state
336
336
        # will probably support partially-in-memory as a separate variable,
337
337
        # allowing for partially-in-memory unmodified and partially-in-memory
338
338
        # modified states.
339
339
        self._header_state = DirState.NOT_IN_MEMORY
340
340
        self._dirblock_state = DirState.NOT_IN_MEMORY
341
 
        # If true, an error has been detected while updating the dirstate, and 
 
341
        # If true, an error has been detected while updating the dirstate, and
342
342
        # for safety we're not going to commit to disk.
343
343
        self._changes_aborted = False
344
344
        self._dirblocks = []
374
374
        """Add a path to be tracked.
375
375
 
376
376
        :param path: The path within the dirstate - '' is the root, 'foo' is the
377
 
            path foo within the root, 'foo/bar' is the path bar within foo 
 
377
            path foo within the root, 'foo/bar' is the path bar within foo
378
378
            within the root.
379
379
        :param file_id: The file id of the path being added.
380
 
        :param kind: The kind of the path, as a string like 'file', 
 
380
        :param kind: The kind of the path, as a string like 'file',
381
381
            'directory', etc.
382
382
        :param stat: The output of os.lstat for the path.
383
383
        :param fingerprint: The sha value of the file,
386
386
            or '' for directories.
387
387
        """
388
388
        # adding a file:
389
 
        # find the block its in. 
 
389
        # find the block its in.
390
390
        # find the location in the block.
391
391
        # check its not there
392
392
        # add it.
405
405
        # in the parent, or according to the special treatment for the root
406
406
        if basename == '.' or basename == '..':
407
407
            raise errors.InvalidEntryName(path)
408
 
        # now that we've normalised, we need the correct utf8 path and 
 
408
        # now that we've normalised, we need the correct utf8 path and
409
409
        # dirname and basename elements. This single encode and split should be
410
410
        # faster than three separate encodes.
411
411
        utf8path = (dirname + '/' + basename).strip('/').encode('utf8')
439
439
            # check the path is not in the tree
440
440
            block = self._dirblocks[block_index][1]
441
441
            entry_index, _ = self._find_entry_index(first_key, block)
442
 
            while (entry_index < len(block) and 
 
442
            while (entry_index < len(block) and
443
443
                block[entry_index][0][0:2] == first_key[0:2]):
444
444
                if block[entry_index][1][0][0] not in 'ar':
445
445
                    # this path is in the dirstate in the current tree.
935
935
 
936
936
    def _discard_merge_parents(self):
937
937
        """Discard any parents trees beyond the first.
938
 
        
 
938
 
939
939
        Note that if this fails the dirstate is corrupted.
940
940
 
941
941
        After this function returns the dirstate contains 2 trees, neither of
1011
1011
                raise AssertionError("bad dirname %r" % dirname)
1012
1012
        block_index, present = self._find_block_index_from_key((dirname, '', ''))
1013
1013
        if not present:
1014
 
            ## In future, when doing partial parsing, this should load and 
 
1014
            ## In future, when doing partial parsing, this should load and
1015
1015
            # populate the entire block.
1016
1016
            self._dirblocks.insert(block_index, (dirname, []))
1017
1017
        return block_index
1029
1029
        if new_entries[0][0][0:2] != ('', ''):
1030
1030
            raise AssertionError(
1031
1031
                "Missing root row %r" % (new_entries[0][0],))
1032
 
        # The two blocks here are deliberate: the root block and the 
 
1032
        # The two blocks here are deliberate: the root block and the
1033
1033
        # contents-of-root block.
1034
1034
        self._dirblocks = [('', []), ('', [])]
1035
1035
        current_block = self._dirblocks[0][1]
1159
1159
        # one to use it. we use _right here because there are two
1160
1160
        # '' blocks - the root, and the contents of root
1161
1161
        # we always have a minimum of 2 in self._dirblocks: root and
1162
 
        # root-contents, and for '', we get 2 back, so this is 
 
1162
        # root-contents, and for '', we get 2 back, so this is
1163
1163
        # simple and correct:
1164
1164
        present = (block_index < len(self._dirblocks) and
1165
1165
            self._dirblocks[block_index][0] == key[0])
1588
1588
        #       already in memory. However, this really needs to be done at a
1589
1589
        #       higher level, because there either won't be anything on disk,
1590
1590
        #       or the thing on disk will be a file.
1591
 
        return os.readlink(abspath)
 
1591
        fs_encoding = osutils._fs_enc
 
1592
        if isinstance(abspath, unicode):
 
1593
            # abspath is defined as the path to pass to lstat. readlink is
 
1594
            # buggy in python < 2.6 (it doesn't encode unicode path into FS
 
1595
            # encoding), so we need to encode ourselves knowing that unicode
 
1596
            # paths are produced by UnicodeDirReader on purpose.
 
1597
            abspath = abspath.encode(fs_encoding)
 
1598
        target = os.readlink(abspath)
 
1599
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
 
1600
            # Change encoding if needed
 
1601
            target = target.decode(fs_encoding).encode('UTF-8')
 
1602
        return target
1592
1603
 
1593
1604
    def get_ghosts(self):
1594
1605
        """Return a list of the parent tree revision ids that are ghosts."""
1798
1809
                if present:
1799
1810
                    entry = self._dirblocks[block_index][1][entry_index]
1800
1811
                    if entry[1][tree_index][0] in 'fdlt':
1801
 
                        # this is the result we are looking for: the  
 
1812
                        # this is the result we are looking for: the
1802
1813
                        # real home of this file_id in this tree.
1803
1814
                        return entry
1804
1815
                    if entry[1][tree_index][0] == 'a':
1866
1877
            size = 0
1867
1878
            executable = False
1868
1879
        elif kind == 'symlink':
1869
 
            # We don't support non-ascii targets for symlinks yet.
1870
 
            fingerprint = str(inv_entry.symlink_target or '')
 
1880
            if inv_entry.symlink_target is None:
 
1881
                fingerprint = ''
 
1882
            else:
 
1883
                fingerprint = inv_entry.symlink_target.encode('utf8')
1871
1884
            size = 0
1872
1885
            executable = False
1873
1886
        elif kind == 'file':
1885
1898
    def _iter_child_entries(self, tree_index, path_utf8):
1886
1899
        """Iterate over all the entries that are children of path_utf.
1887
1900
 
1888
 
        This only returns entries that are present (not in 'a', 'r') in 
 
1901
        This only returns entries that are present (not in 'a', 'r') in
1889
1902
        tree_index. tree_index data is not refreshed, so if tree 0 is used,
1890
1903
        results may differ from that obtained if paths were statted to
1891
1904
        determine what ones were directories.
1922
1935
                        else:
1923
1936
                            path = entry[0][1]
1924
1937
                        next_pending_dirs.append(path)
1925
 
    
 
1938
 
1926
1939
    def _iter_entries(self):
1927
1940
        """Iterate over all the entries in the dirstate.
1928
1941
 
1979
1992
 
1980
1993
    def _read_dirblocks_if_needed(self):
1981
1994
        """Read in all the dirblocks from the file if they are not in memory.
1982
 
        
 
1995
 
1983
1996
        This populates self._dirblocks, and sets self._dirblock_state to
1984
1997
        IN_MEMORY_UNMODIFIED. It is not currently ready for incremental block
1985
1998
        loading.
2110
2123
 
2111
2124
        :param parent_ids: A list of parent tree revision ids.
2112
2125
        :param dirblocks: A list containing one tuple for each directory in the
2113
 
            tree. Each tuple contains the directory path and a list of entries 
 
2126
            tree. Each tuple contains the directory path and a list of entries
2114
2127
            found in that directory.
2115
2128
        """
2116
2129
        # our memory copy is now authoritative.
2150
2163
        """Set the parent trees for the dirstate.
2151
2164
 
2152
2165
        :param trees: A list of revision_id, tree tuples. tree must be provided
2153
 
            even if the revision_id refers to a ghost: supply an empty tree in 
 
2166
            even if the revision_id refers to a ghost: supply an empty tree in
2154
2167
            this case.
2155
2168
        :param ghosts: A list of the revision_ids that are ghosts at the time
2156
2169
            of setting.
2157
 
        """ 
2158
 
        # TODO: generate a list of parent indexes to preserve to save 
 
2170
        """
 
2171
        # TODO: generate a list of parent indexes to preserve to save
2159
2172
        # processing specific parent trees. In the common case one tree will
2160
2173
        # be preserved - the left most parent.
2161
2174
        # TODO: if the parent tree is a dirstate, we might want to walk them
2166
2179
        # map and then walk the new parent trees only, mapping them into the
2167
2180
        # dirstate. Walk the dirstate at the same time to remove unreferenced
2168
2181
        # entries.
2169
 
        # for now: 
2170
 
        # sketch: loop over all entries in the dirstate, cherry picking 
 
2182
        # for now:
 
2183
        # sketch: loop over all entries in the dirstate, cherry picking
2171
2184
        # entries from the parent trees, if they are not ghost trees.
2172
2185
        # after we finish walking the dirstate, all entries not in the dirstate
2173
2186
        # are deletes, so we want to append them to the end as per the design
2178
2191
        #   links. We dont't trivially use the inventory from other trees
2179
2192
        #   because this leads to either double touching, or to accessing
2180
2193
        #   missing keys,
2181
 
        # - find other keys containing a path 
2182
 
        # We accumulate each entry via this dictionary, including the root 
 
2194
        # - find other keys containing a path
 
2195
        # We accumulate each entry via this dictionary, including the root
2183
2196
        by_path = {}
2184
2197
        id_index = {}
2185
2198
        # we could do parallel iterators, but because file id data may be
2189
2202
        # parent, but for now the common cases are adding a new parent (merge),
2190
2203
        # and replacing completely (commit), and commit is more common: so
2191
2204
        # optimise merge later.
2192
 
        
 
2205
 
2193
2206
        # ---- start generation of full tree mapping data
2194
2207
        # what trees should we use?
2195
2208
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2196
 
        # how many trees do we end up with 
 
2209
        # how many trees do we end up with
2197
2210
        parent_count = len(parent_trees)
2198
2211
 
2199
2212
        # one: the current tree
2204
2217
            by_path[entry[0]] = [entry[1][0]] + \
2205
2218
                [DirState.NULL_PARENT_DETAILS] * parent_count
2206
2219
            id_index[entry[0][2]] = set([entry[0]])
2207
 
        
 
2220
 
2208
2221
        # now the parent trees:
2209
2222
        for tree_index, tree in enumerate(parent_trees):
2210
2223
            # the index is off by one, adjust it.
2224
2237
                # avoid checking all known paths for the id when generating a
2225
2238
                # new entry at this path: by adding the id->path mapping last,
2226
2239
                # all the mappings are valid and have correct relocation
2227
 
                # records where needed. 
 
2240
                # records where needed.
2228
2241
                file_id = entry.file_id
2229
2242
                path_utf8 = path.encode('utf8')
2230
2243
                dirname, basename = osutils.split(path_utf8)
2241
2254
                        # This is the vertical axis in the matrix, all pointing
2242
2255
                        # to the real path.
2243
2256
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
2244
 
                # by path consistency: Insert into an existing path record (trivial), or 
 
2257
                # by path consistency: Insert into an existing path record (trivial), or
2245
2258
                # add a new one with relocation pointers for the other tree indexes.
2246
2259
                if new_entry_key in id_index[file_id]:
2247
2260
                    # there is already an entry where this data belongs, just insert it.
2260
2273
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2261
2274
                        else:
2262
2275
                            # grab any one entry, use it to find the right path.
2263
 
                            # TODO: optimise this to reduce memory use in highly 
 
2276
                            # TODO: optimise this to reduce memory use in highly
2264
2277
                            # fragmented situations by reusing the relocation
2265
2278
                            # records.
2266
2279
                            a_key = iter(id_index[file_id]).next()
2299
2312
        return sorted(entry_list, key=_key)
2300
2313
 
2301
2314
    def set_state_from_inventory(self, new_inv):
2302
 
        """Set new_inv as the current state. 
 
2315
        """Set new_inv as the current state.
2303
2316
 
2304
2317
        This API is called by tree transform, and will usually occur with
2305
2318
        existing parent trees.
2311
2324
                "set_state_from_inventory called; please mutate the tree instead")
2312
2325
        self._read_dirblocks_if_needed()
2313
2326
        # sketch:
2314
 
        # Two iterators: current data and new data, both in dirblock order. 
 
2327
        # Two iterators: current data and new data, both in dirblock order.
2315
2328
        # We zip them together, which tells about entries that are new in the
2316
2329
        # inventory, or removed in the inventory, or present in both and
2317
 
        # possibly changed.  
 
2330
        # possibly changed.
2318
2331
        #
2319
2332
        # You might think we could just synthesize a new dirstate directly
2320
2333
        # since we're processing it in the right order.  However, we need to
2469
2482
        :param minikind: The type for the entry ('f' == 'file', 'd' ==
2470
2483
                'directory'), etc.
2471
2484
        :param executable: Should the executable bit be set?
2472
 
        :param fingerprint: Simple fingerprint for new entry: sha1 for files, 
 
2485
        :param fingerprint: Simple fingerprint for new entry: sha1 for files,
2473
2486
            referenced revision id for subtrees, etc.
2474
2487
        :param packed_stat: Packed stat value for new entry.
2475
2488
        :param size: Size information for new entry
2520
2533
                num_present_parents = self._num_present_parents()
2521
2534
                for lookup_index in xrange(1, num_present_parents + 1):
2522
2535
                    # grab any one entry, use it to find the right path.
2523
 
                    # TODO: optimise this to reduce memory use in highly 
 
2536
                    # TODO: optimise this to reduce memory use in highly
2524
2537
                    # fragmented situations by reusing the relocation
2525
2538
                    # records.
2526
2539
                    update_block_index, present = \
2543
2556
            block.insert(entry_index, new_entry)
2544
2557
            existing_keys.add(key)
2545
2558
        else:
2546
 
            # Does the new state matter? 
 
2559
            # Does the new state matter?
2547
2560
            block[entry_index][1][0] = new_details
2548
2561
            # parents cannot be affected by what we do.
2549
 
            # other occurences of this id can be found 
 
2562
            # other occurences of this id can be found
2550
2563
            # from the id index.
2551
2564
            # ---
2552
2565
            # tree index consistency: All other paths for this id in this tree
2585
2598
    def _validate(self):
2586
2599
        """Check that invariants on the dirblock are correct.
2587
2600
 
2588
 
        This can be useful in debugging; it shouldn't be necessary in 
 
2601
        This can be useful in debugging; it shouldn't be necessary in
2589
2602
        normal code.
2590
2603
 
2591
2604
        This must be called with a lock held.
2660
2673
        # For each file id, for each tree: either
2661
2674
        # the file id is not present at all; all rows with that id in the
2662
2675
        # key have it marked as 'absent'
2663
 
        # OR the file id is present under exactly one name; any other entries 
 
2676
        # OR the file id is present under exactly one name; any other entries
2664
2677
        # that mention that id point to the correct name.
2665
2678
        #
2666
2679
        # We check this with a dict per tree pointing either to the present
2713
2726
                        # absent; should not occur anywhere else
2714
2727
                        this_tree_map[file_id] = None, this_path
2715
2728
                    elif minikind == 'r':
2716
 
                        # relocation, must occur at expected location 
 
2729
                        # relocation, must occur at expected location
2717
2730
                        this_tree_map[file_id] = tree_state[1], this_path
2718
2731
                    else:
2719
2732
                        this_tree_map[file_id] = this_path, this_path
2807
2820
    (saved_minikind, saved_link_or_sha1, saved_file_size,
2808
2821
     saved_executable, saved_packed_stat) = entry[1][0]
2809
2822
 
 
2823
    if minikind == 'd' and saved_minikind == 't':
 
2824
        minikind = 't'
2810
2825
    if (minikind == saved_minikind
2811
2826
        and packed_stat == saved_packed_stat):
2812
2827
        # The stat hasn't changed since we saved, so we can re-use the
3181
3196
        search_specific_files = self.search_specific_files
3182
3197
        searched_specific_files = self.searched_specific_files
3183
3198
        splitpath = osutils.splitpath
3184
 
        # sketch: 
 
3199
        # sketch:
3185
3200
        # compare source_index and target_index at or under each element of search_specific_files.
3186
3201
        # follow the following comparison table. Note that we only want to do diff operations when
3187
 
        # the target is fdl because thats when the walkdirs logic will have exposed the pathinfo 
 
3202
        # the target is fdl because thats when the walkdirs logic will have exposed the pathinfo
3188
3203
        # for the target.
3189
3204
        # cases:
3190
 
        # 
 
3205
        #
3191
3206
        # Source | Target | disk | action
3192
3207
        #   r    | fdlt   |      | add source to search, add id path move and perform
3193
3208
        #        |        |      | diff check on source-target
3194
 
        #   r    | fdlt   |  a   | dangling file that was present in the basis. 
 
3209
        #   r    | fdlt   |  a   | dangling file that was present in the basis.
3195
3210
        #        |        |      | ???
3196
3211
        #   r    |  a     |      | add source to search
3197
 
        #   r    |  a     |  a   | 
 
3212
        #   r    |  a     |  a   |
3198
3213
        #   r    |  r     |      | this path is present in a non-examined tree, skip.
3199
3214
        #   r    |  r     |  a   | this path is present in a non-examined tree, skip.
3200
3215
        #   a    | fdlt   |      | add new id
3308
3323
                            raise AssertionError()
3309
3324
                        del current_dir_info[1][bzr_index]
3310
3325
            # walk until both the directory listing and the versioned metadata
3311
 
            # are exhausted. 
 
3326
            # are exhausted.
3312
3327
            if (block_index < len(self.state._dirblocks) and
3313
3328
                osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
3314
3329
                current_block = self.state._dirblocks[block_index]
3405
3420
                while (current_entry is not None or
3406
3421
                    current_path_info is not None):
3407
3422
                    if current_entry is None:
3408
 
                        # the check for path_handled when the path is adnvaced
 
3423
                        # the check for path_handled when the path is advanced
3409
3424
                        # will yield this path if needed.
3410
3425
                        pass
3411
3426
                    elif current_path_info is None:
3475
3490
                            if current_path_info[2] in ('directory'):
3476
3491
                                del current_dir_info[1][path_index]
3477
3492
                                path_index -= 1
3478
 
                        # dont descend the disk iterator into any tree 
 
3493
                        # dont descend the disk iterator into any tree
3479
3494
                        # paths.
3480
3495
                        if current_path_info[2] == 'tree-reference':
3481
3496
                            del current_dir_info[1][path_index]