/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/index.py

• browse files at revision 4595.17.2
• compare with another revision
• compare with revision 0.200.196
• download diff
• download tarball
• view history from revision 4595.17.2

Show diffs side-by-side

added

removed

bzrlib/index.py

1

 

# Copyright (C) 2007, 2008 Canonical Ltd

 

1

# Copyright (C) 2007, 2008, 2009 Canonical Ltd

2

2

#

3

3

# This program is free software; you can redistribute it and/or modify

4

4

# it under the terms of the GNU General Public License as published by

40

40

    debug,

41

41

    errors,

42

42

    )

 

43

from bzrlib.static_tuple import StaticTuple

43

44

 

44

45

_HEADER_READV = (0, 200)

45

46

_OPTION_KEY_ELEMENTS = "key_elements="

102

103

 

103

104

    def _check_key(self, key):

104

105

        """Raise BadIndexKey if key is not a valid key for this index."""

105

 

        if type(key) != tuple:

 

106

        if type(key) not in (tuple, StaticTuple):

106

107

            raise errors.BadIndexKey(key)

107

108

        if self._key_length != len(key):

108

109

            raise errors.BadIndexKey(key)

202

203

                if reference not in self._nodes:

203

204

                    self._check_key(reference)

204

205

                    absent_references.append(reference)

 

206

            # TODO: StaticTuple

205

207

            node_refs.append(tuple(reference_list))

 

208

        # TODO: StaticTuple

206

209

        return tuple(node_refs), absent_references

207

210

 

208

211

    def add_node(self, key, value, references=()):

229

232

        if self._nodes_by_key is not None and self._key_length > 1:

230

233

            self._update_nodes_by_key(key, value, node_refs)

231

234

 

 

235

    def clear_cache(self):

 

236

        """See GraphIndex.clear_cache()

 

237

 

 

238

        This is a no-op, but we need the api to conform to a generic 'Index'

 

239

        abstraction.

 

240

        """

 

241

        

232

242

    def finish(self):

233

243

        lines = [_SIGNATURE]

234

244

        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')

333

343

        if combine_backing_indices is not None:

334

344

            self._combine_backing_indices = combine_backing_indices

335

345

 

 

346

    def find_ancestry(self, keys, ref_list_num):

 

347

        """See CombinedGraphIndex.find_ancestry()"""

 

348

        pending = set(keys)

 

349

        parent_map = {}

 

350

        missing_keys = set()

 

351

        while pending:

 

352

            next_pending = set()

 

353

            for _, key, value, ref_lists in self.iter_entries(pending):

 

354

                parent_keys = ref_lists[ref_list_num]

 

355

                parent_map[key] = parent_keys

 

356

                next_pending.update([p for p in parent_keys if p not in

 

357

                                     parent_map])

 

358

                missing_keys.update(pending.difference(parent_map))

 

359

            pending = next_pending

 

360

        return parent_map, missing_keys

 

361

 

336

362

 

337

363

class GraphIndex(object):

338

364

    """An index for data with embedded graphs.

352

378

    suitable for production use. :XXX

353

379

    """

354

380

 

355

 

    def __init__(self, transport, name, size):

 

381

    def __init__(self, transport, name, size, unlimited_cache=False):

356

382

        """Open an index called name on transport.

357

383

 

358

384

        :param transport: A bzrlib.transport.Transport.

442

468

            # there must be one line - the empty trailer line.

443

469

            raise errors.BadIndexData(self)

444

470

 

 

471

    def clear_cache(self):

 

472

        """Clear out any cached/memoized values.

 

473

 

 

474

        This can be called at any time, but generally it is used when we have

 

475

        extracted some information, but don't expect to be requesting any more

 

476

        from this index.

 

477

        """

 

478

 

445

479

    def external_references(self, ref_list_num):

446

480

        """Return references that are not present in this index.

447

481

        """

702

736

                # the last thing looked up was a terminal element

703

737

                yield (self, ) + key_dict

704

738

 

 

739

    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):

 

740

        """See BTreeIndex._find_ancestors."""

 

741

        # The api can be implemented as a trivial overlay on top of

 

742

        # iter_entries, it is not an efficient implementation, but it at least

 

743

        # gets the job done.

 

744

        found_keys = set()

 

745

        search_keys = set()

 

746

        for index, key, value, refs in self.iter_entries(keys):

 

747

            parent_keys = refs[ref_list_num]

 

748

            found_keys.add(key)

 

749

            parent_map[key] = parent_keys

 

750

            search_keys.update(parent_keys)

 

751

        # Figure out what, if anything, was missing

 

752

        missing_keys.update(set(keys).difference(found_keys))

 

753

        search_keys = search_keys.difference(parent_map)

 

754

        return search_keys

 

755

 

705

756

    def key_count(self):

706

757

        """Return an estimate of the number of keys in this index.

707

758

 

1119

1170

            self._parsed_key_map.insert(index + 1, new_key)

1120

1171

 

1121

1172

    def _read_and_parse(self, readv_ranges):

1122

 

        """Read the the ranges and parse the resulting data.

 

1173

        """Read the ranges and parse the resulting data.

1123

1174

 

1124

1175

        :param readv_ranges: A prepared readv range list.

1125

1176

        """

1190

1241

                self.__class__.__name__,

1191

1242

                ', '.join(map(repr, self._indices)))

1192

1243

 

 

1244

    def clear_cache(self):

 

1245

        """See GraphIndex.clear_cache()"""

 

1246

        for index in self._indices:

 

1247

            index.clear_cache()

 

1248

 

1193

1249

    def get_parent_map(self, keys):

1194

1250

        """See graph.StackedParentsProvider.get_parent_map"""

1195

1251

        search_keys = set(keys)

1297

1353

            except errors.NoSuchFile:

1298

1354

                self._reload_or_raise()

1299

1355

 

 

1356

    def find_ancestry(self, keys, ref_list_num):

 

1357

        """Find the complete ancestry for the given set of keys.

 

1358

 

 

1359

        Note that this is a whole-ancestry request, so it should be used

 

1360

        sparingly.

 

1361

 

 

1362

        :param keys: An iterable of keys to look for

 

1363

        :param ref_list_num: The reference list which references the parents

 

1364

            we care about.

 

1365

        :return: (parent_map, missing_keys)

 

1366

        """

 

1367

        missing_keys = set()

 

1368

        parent_map = {}

 

1369

        keys_to_lookup = set(keys)

 

1370

        generation = 0

 

1371

        while keys_to_lookup:

 

1372

            # keys that *all* indexes claim are missing, stop searching them

 

1373

            generation += 1

 

1374

            all_index_missing = None

 

1375

            # print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'

 

1376

            # print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),

 

1377

            #                                   len(parent_map),

 

1378

            #                                   len(missing_keys))

 

1379

            for index_idx, index in enumerate(self._indices):

 

1380

                # TODO: we should probably be doing something with

 

1381

                #       'missing_keys' since we've already determined that

 

1382

                #       those revisions have not been found anywhere

 

1383

                index_missing_keys = set()

 

1384

                # Find all of the ancestry we can from this index

 

1385

                # keep looking until the search_keys set is empty, which means

 

1386

                # things we didn't find should be in index_missing_keys

 

1387

                search_keys = keys_to_lookup

 

1388

                sub_generation = 0

 

1389

                # print '    \t%2d\t\t%4d\t%5d\t%5d' % (

 

1390

                #     index_idx, len(search_keys),

 

1391

                #     len(parent_map), len(index_missing_keys))

 

1392

                while search_keys:

 

1393

                    sub_generation += 1

 

1394

                    # TODO: ref_list_num should really be a parameter, since

 

1395

                    #       CombinedGraphIndex does not know what the ref lists

 

1396

                    #       mean.

 

1397

                    search_keys = index._find_ancestors(search_keys,

 

1398

                        ref_list_num, parent_map, index_missing_keys)

 

1399

                    # print '    \t  \t%2d\t%4d\t%5d\t%5d' % (

 

1400

                    #     sub_generation, len(search_keys),

 

1401

                    #     len(parent_map), len(index_missing_keys))

 

1402

                # Now set whatever was missing to be searched in the next index

 

1403

                keys_to_lookup = index_missing_keys

 

1404

                if all_index_missing is None:

 

1405

                    all_index_missing = set(index_missing_keys)

 

1406

                else:

 

1407

                    all_index_missing.intersection_update(index_missing_keys)

 

1408

                if not keys_to_lookup:

 

1409

                    break

 

1410

            if all_index_missing is None:

 

1411

                # There were no indexes, so all search keys are 'missing'

 

1412

                missing_keys.update(keys_to_lookup)

 

1413

                keys_to_lookup = None

 

1414

            else:

 

1415

                missing_keys.update(all_index_missing)

 

1416

                keys_to_lookup.difference_update(all_index_missing)

 

1417

        return parent_map, missing_keys

 

1418

 

1300

1419

    def key_count(self):

1301

1420

        """Return an estimate of the number of keys in this index.

1302

1421

 

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0