← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

remove all trailing whitespace from bzr source

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])
1798
1798
                if present:
1799
1799
                    entry = self._dirblocks[block_index][1][entry_index]
1800
1800
                    if entry[1][tree_index][0] in 'fdlt':
1801
 
                        # this is the result we are looking for: the  
 
1801
                        # this is the result we are looking for: the
1802
1802
                        # real home of this file_id in this tree.
1803
1803
                        return entry
1804
1804
                    if entry[1][tree_index][0] == 'a':
1885
1885
    def _iter_child_entries(self, tree_index, path_utf8):
1886
1886
        """Iterate over all the entries that are children of path_utf.
1887
1887
 
1888
 
        This only returns entries that are present (not in 'a', 'r') in 
 
1888
        This only returns entries that are present (not in 'a', 'r') in
1889
1889
        tree_index. tree_index data is not refreshed, so if tree 0 is used,
1890
1890
        results may differ from that obtained if paths were statted to
1891
1891
        determine what ones were directories.
1922
1922
                        else:
1923
1923
                            path = entry[0][1]
1924
1924
                        next_pending_dirs.append(path)
1925
 
    
 
1925
 
1926
1926
    def _iter_entries(self):
1927
1927
        """Iterate over all the entries in the dirstate.
1928
1928
 
1979
1979
 
1980
1980
    def _read_dirblocks_if_needed(self):
1981
1981
        """Read in all the dirblocks from the file if they are not in memory.
1982
 
        
 
1982
 
1983
1983
        This populates self._dirblocks, and sets self._dirblock_state to
1984
1984
        IN_MEMORY_UNMODIFIED. It is not currently ready for incremental block
1985
1985
        loading.
2110
2110
 
2111
2111
        :param parent_ids: A list of parent tree revision ids.
2112
2112
        :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 
 
2113
            tree. Each tuple contains the directory path and a list of entries
2114
2114
            found in that directory.
2115
2115
        """
2116
2116
        # our memory copy is now authoritative.
2150
2150
        """Set the parent trees for the dirstate.
2151
2151
 
2152
2152
        :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 
 
2153
            even if the revision_id refers to a ghost: supply an empty tree in
2154
2154
            this case.
2155
2155
        :param ghosts: A list of the revision_ids that are ghosts at the time
2156
2156
            of setting.
2157
 
        """ 
2158
 
        # TODO: generate a list of parent indexes to preserve to save 
 
2157
        """
 
2158
        # TODO: generate a list of parent indexes to preserve to save
2159
2159
        # processing specific parent trees. In the common case one tree will
2160
2160
        # be preserved - the left most parent.
2161
2161
        # TODO: if the parent tree is a dirstate, we might want to walk them
2166
2166
        # map and then walk the new parent trees only, mapping them into the
2167
2167
        # dirstate. Walk the dirstate at the same time to remove unreferenced
2168
2168
        # entries.
2169
 
        # for now: 
2170
 
        # sketch: loop over all entries in the dirstate, cherry picking 
 
2169
        # for now:
 
2170
        # sketch: loop over all entries in the dirstate, cherry picking
2171
2171
        # entries from the parent trees, if they are not ghost trees.
2172
2172
        # after we finish walking the dirstate, all entries not in the dirstate
2173
2173
        # are deletes, so we want to append them to the end as per the design
2178
2178
        #   links. We dont't trivially use the inventory from other trees
2179
2179
        #   because this leads to either double touching, or to accessing
2180
2180
        #   missing keys,
2181
 
        # - find other keys containing a path 
2182
 
        # We accumulate each entry via this dictionary, including the root 
 
2181
        # - find other keys containing a path
 
2182
        # We accumulate each entry via this dictionary, including the root
2183
2183
        by_path = {}
2184
2184
        id_index = {}
2185
2185
        # we could do parallel iterators, but because file id data may be
2189
2189
        # parent, but for now the common cases are adding a new parent (merge),
2190
2190
        # and replacing completely (commit), and commit is more common: so
2191
2191
        # optimise merge later.
2192
 
        
 
2192
 
2193
2193
        # ---- start generation of full tree mapping data
2194
2194
        # what trees should we use?
2195
2195
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2196
 
        # how many trees do we end up with 
 
2196
        # how many trees do we end up with
2197
2197
        parent_count = len(parent_trees)
2198
2198
 
2199
2199
        # one: the current tree
2204
2204
            by_path[entry[0]] = [entry[1][0]] + \
2205
2205
                [DirState.NULL_PARENT_DETAILS] * parent_count
2206
2206
            id_index[entry[0][2]] = set([entry[0]])
2207
 
        
 
2207
 
2208
2208
        # now the parent trees:
2209
2209
        for tree_index, tree in enumerate(parent_trees):
2210
2210
            # the index is off by one, adjust it.
2224
2224
                # avoid checking all known paths for the id when generating a
2225
2225
                # new entry at this path: by adding the id->path mapping last,
2226
2226
                # all the mappings are valid and have correct relocation
2227
 
                # records where needed. 
 
2227
                # records where needed.
2228
2228
                file_id = entry.file_id
2229
2229
                path_utf8 = path.encode('utf8')
2230
2230
                dirname, basename = osutils.split(path_utf8)
2241
2241
                        # This is the vertical axis in the matrix, all pointing
2242
2242
                        # to the real path.
2243
2243
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
2244
 
                # by path consistency: Insert into an existing path record (trivial), or 
 
2244
                # by path consistency: Insert into an existing path record (trivial), or
2245
2245
                # add a new one with relocation pointers for the other tree indexes.
2246
2246
                if new_entry_key in id_index[file_id]:
2247
2247
                    # there is already an entry where this data belongs, just insert it.
2260
2260
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2261
2261
                        else:
2262
2262
                            # grab any one entry, use it to find the right path.
2263
 
                            # TODO: optimise this to reduce memory use in highly 
 
2263
                            # TODO: optimise this to reduce memory use in highly
2264
2264
                            # fragmented situations by reusing the relocation
2265
2265
                            # records.
2266
2266
                            a_key = iter(id_index[file_id]).next()
2299
2299
        return sorted(entry_list, key=_key)
2300
2300
 
2301
2301
    def set_state_from_inventory(self, new_inv):
2302
 
        """Set new_inv as the current state. 
 
2302
        """Set new_inv as the current state.
2303
2303
 
2304
2304
        This API is called by tree transform, and will usually occur with
2305
2305
        existing parent trees.
2311
2311
                "set_state_from_inventory called; please mutate the tree instead")
2312
2312
        self._read_dirblocks_if_needed()
2313
2313
        # sketch:
2314
 
        # Two iterators: current data and new data, both in dirblock order. 
 
2314
        # Two iterators: current data and new data, both in dirblock order.
2315
2315
        # We zip them together, which tells about entries that are new in the
2316
2316
        # inventory, or removed in the inventory, or present in both and
2317
 
        # possibly changed.  
 
2317
        # possibly changed.
2318
2318
        #
2319
2319
        # You might think we could just synthesize a new dirstate directly
2320
2320
        # since we're processing it in the right order.  However, we need to
2469
2469
        :param minikind: The type for the entry ('f' == 'file', 'd' ==
2470
2470
                'directory'), etc.
2471
2471
        :param executable: Should the executable bit be set?
2472
 
        :param fingerprint: Simple fingerprint for new entry: sha1 for files, 
 
2472
        :param fingerprint: Simple fingerprint for new entry: sha1 for files,
2473
2473
            referenced revision id for subtrees, etc.
2474
2474
        :param packed_stat: Packed stat value for new entry.
2475
2475
        :param size: Size information for new entry
2520
2520
                num_present_parents = self._num_present_parents()
2521
2521
                for lookup_index in xrange(1, num_present_parents + 1):
2522
2522
                    # grab any one entry, use it to find the right path.
2523
 
                    # TODO: optimise this to reduce memory use in highly 
 
2523
                    # TODO: optimise this to reduce memory use in highly
2524
2524
                    # fragmented situations by reusing the relocation
2525
2525
                    # records.
2526
2526
                    update_block_index, present = \
2543
2543
            block.insert(entry_index, new_entry)
2544
2544
            existing_keys.add(key)
2545
2545
        else:
2546
 
            # Does the new state matter? 
 
2546
            # Does the new state matter?
2547
2547
            block[entry_index][1][0] = new_details
2548
2548
            # parents cannot be affected by what we do.
2549
 
            # other occurences of this id can be found 
 
2549
            # other occurences of this id can be found
2550
2550
            # from the id index.
2551
2551
            # ---
2552
2552
            # tree index consistency: All other paths for this id in this tree
2585
2585
    def _validate(self):
2586
2586
        """Check that invariants on the dirblock are correct.
2587
2587
 
2588
 
        This can be useful in debugging; it shouldn't be necessary in 
 
2588
        This can be useful in debugging; it shouldn't be necessary in
2589
2589
        normal code.
2590
2590
 
2591
2591
        This must be called with a lock held.
2660
2660
        # For each file id, for each tree: either
2661
2661
        # the file id is not present at all; all rows with that id in the
2662
2662
        # key have it marked as 'absent'
2663
 
        # OR the file id is present under exactly one name; any other entries 
 
2663
        # OR the file id is present under exactly one name; any other entries
2664
2664
        # that mention that id point to the correct name.
2665
2665
        #
2666
2666
        # We check this with a dict per tree pointing either to the present
2713
2713
                        # absent; should not occur anywhere else
2714
2714
                        this_tree_map[file_id] = None, this_path
2715
2715
                    elif minikind == 'r':
2716
 
                        # relocation, must occur at expected location 
 
2716
                        # relocation, must occur at expected location
2717
2717
                        this_tree_map[file_id] = tree_state[1], this_path
2718
2718
                    else:
2719
2719
                        this_tree_map[file_id] = this_path, this_path
3181
3181
        search_specific_files = self.search_specific_files
3182
3182
        searched_specific_files = self.searched_specific_files
3183
3183
        splitpath = osutils.splitpath
3184
 
        # sketch: 
 
3184
        # sketch:
3185
3185
        # compare source_index and target_index at or under each element of search_specific_files.
3186
3186
        # 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 
 
3187
        # the target is fdl because thats when the walkdirs logic will have exposed the pathinfo
3188
3188
        # for the target.
3189
3189
        # cases:
3190
 
        # 
 
3190
        #
3191
3191
        # Source | Target | disk | action
3192
3192
        #   r    | fdlt   |      | add source to search, add id path move and perform
3193
3193
        #        |        |      | diff check on source-target
3194
 
        #   r    | fdlt   |  a   | dangling file that was present in the basis. 
 
3194
        #   r    | fdlt   |  a   | dangling file that was present in the basis.
3195
3195
        #        |        |      | ???
3196
3196
        #   r    |  a     |      | add source to search
3197
 
        #   r    |  a     |  a   | 
 
3197
        #   r    |  a     |  a   |
3198
3198
        #   r    |  r     |      | this path is present in a non-examined tree, skip.
3199
3199
        #   r    |  r     |  a   | this path is present in a non-examined tree, skip.
3200
3200
        #   a    | fdlt   |      | add new id
3308
3308
                            raise AssertionError()
3309
3309
                        del current_dir_info[1][bzr_index]
3310
3310
            # walk until both the directory listing and the versioned metadata
3311
 
            # are exhausted. 
 
3311
            # are exhausted.
3312
3312
            if (block_index < len(self.state._dirblocks) and
3313
3313
                osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
3314
3314
                current_block = self.state._dirblocks[block_index]
3475
3475
                            if current_path_info[2] in ('directory'):
3476
3476
                                del current_dir_info[1][path_index]
3477
3477
                                path_index -= 1
3478
 
                        # dont descend the disk iterator into any tree 
 
3478
                        # dont descend the disk iterator into any tree
3479
3479
                        # paths.
3480
3480
                        if current_path_info[2] == 'tree-reference':
3481
3481
                            del current_dir_info[1][path_index]