~bzr-pqm/bzr/bzr.dev : revision 183

1

#! /usr/bin/env python

2

# -*- coding: UTF-8 -*-

1

3

2

4

3

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

5

4

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

17

16

18

17

"""Inventories map files to their name in a revision."""

19

18

19

# TODO: Maybe store inventory_id in the file? Not really needed.

20

21

22

21

__author__ = "Martin Pool <mbp@canonical.com>"

23

22

24

import sys, os.path, types

23

24

# This should really be an id randomly assigned when the tree is

25

# created, but it's not for now.

26

ROOT_ID = "TREE_ROOT"

27

28

29

import sys, os.path, types, re

25

30

from sets import Set

26

31

27

32

try:

31

36

32

37

from xml import XMLMixin

33

38

from errors import bailout

34

from osutils import uuid, quotefn, splitpath, joinpath, appendpath

35

from trace import mutter

39

40

import bzrlib

41

from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath

42

from bzrlib.trace import mutter

36

43

37

44

class InventoryEntry(XMLMixin):

38

45

"""Description of a versioned file.

57

64

58

65

>>> i = Inventory()

59

66

>>> i.path2id('')

60

>>> i.add(InventoryEntry('123', 'src', kind='directory'))

61

>>> i.add(InventoryEntry('2323', 'hello.c', parent_id='123'))

67

'TREE_ROOT'

68

>>> i.add(InventoryEntry('123', 'src', 'directory', ROOT_ID))

69

>>> i.add(InventoryEntry('2323', 'hello.c', 'file', parent_id='123'))

62

70

>>> for j in i.iter_entries():

63

71

... print j

64

72

...

65

('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))

73

('src', InventoryEntry('123', 'src', kind='directory', parent_id='TREE_ROOT'))

66

74

('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))

67

>>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))

75

>>> i.add(InventoryEntry('2323', 'bye.c', 'file', '123'))

68

76

Traceback (most recent call last):

69

77

...

70

78

BzrError: ('inventory already contains entry with id {2323}', [])

71

>>> i.add(InventoryEntry('2324', 'bye.c', parent_id='123'))

72

>>> i.add(InventoryEntry('2325', 'wibble', parent_id='123', kind='directory'))

79

>>> i.add(InventoryEntry('2324', 'bye.c', 'file', '123'))

80

>>> i.add(InventoryEntry('2325', 'wibble', 'directory', '123'))

73

81

>>> i.path2id('src/wibble')

74

82

'2325'

75

83

>>> '2325' in i

76

84

True

77

>>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))

85

>>> i.add(InventoryEntry('2326', 'wibble.c', 'file', '2325'))

78

86

>>> i['2326']

79

87

InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')

80

88

>>> for j in i.iter_entries():

93

101

But those depend on its position within a particular inventory, and

94

102

it would be nice not to need to hold the backpointer here.

95

103

"""

96

def __init__(self, file_id, name, kind='file', text_id=None,

97

parent_id=None):

104

105

# TODO: split InventoryEntry into subclasses for files,

106

# directories, etc etc.

107

108

def __init__(self, file_id, name, kind, parent_id, text_id=None):

98

109

"""Create an InventoryEntry

99

110

100

111

The filename must be a single component, relative to the

101

112

parent directory; it cannot be a whole path or relative name.

102

113

103

>>> e = InventoryEntry('123', 'hello.c')

114

>>> e = InventoryEntry('123', 'hello.c', 'file', ROOT_ID)

104

115

>>> e.name

105

116

'hello.c'

106

117

>>> e.file_id

107

118

'123'

108

>>> e = InventoryEntry('123', 'src/hello.c')

119

>>> e = InventoryEntry('123', 'src/hello.c', 'file', ROOT_ID)

109

120

Traceback (most recent call last):

110

121

BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])

111

122

"""

122

133

self.parent_id = parent_id

123

134

self.text_sha1 = None

124

135

self.text_size = None

136

if kind == 'directory':

137

self.children = {}

138

else:

139

assert kind == 'file'

140

141

142

def sorted_children(self):

143

l = self.children.items()

144

l.sort()

145

return l

125

146

126

147

127

148

def copy(self):

128

149

other = InventoryEntry(self.file_id, self.name, self.kind,

129

self.text_id, self.parent_id)

150

self.parent_id, text_id=self.text_id)

130

151

other.text_sha1 = self.text_sha1

131

152

other.text_size = self.text_size

132

153

return other

149

170

e.set('file_id', self.file_id)

150

171

e.set('kind', self.kind)

151

172

152

if self.text_size is not None:

173

if self.text_size != None:

153

174

e.set('text_size', '%d' % self.text_size)

154

175

155

for f in ['text_id', 'text_sha1', 'parent_id']:

176

for f in ['text_id', 'text_sha1']:

156

177

v = getattr(self, f)

157

if v is not None:

178

if v != None:

158

179

e.set(f, v)

159

180

181

# to be conservative, we don't externalize the root pointers

182

# for now, leaving them as null in the xml form. in a future

183

# version it will be implied by nested elements.

184

if self.parent_id != ROOT_ID:

185

assert isinstance(self.parent_id, basestring)

186

e.set('parent_id', self.parent_id)

187

160

188

e.tail = '\n'

161

189

162

190

return e

164

192

165

193

def from_element(cls, elt):

166

194

assert elt.tag == 'entry'

167

self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))

195

196

## original format inventories don't have a parent_id for

197

## nodes in the root directory, but it's cleaner to use one

198

## internally.

199

parent_id = elt.get('parent_id')

200

if parent_id == None:

201

parent_id = ROOT_ID

202

203

self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'), parent_id)

168

204

self.text_id = elt.get('text_id')

169

205

self.text_sha1 = elt.get('text_sha1')

170

self.parent_id = elt.get('parent_id')

171

206

172

207

## mutter("read inventoryentry: %r" % (elt.attrib))

173

208

195

230

196

231

197

232

233

class RootEntry(InventoryEntry):

234

def __init__(self, file_id):

235

self.file_id = file_id

236

self.children = {}

237

self.kind = 'root_directory'

238

self.parent_id = None

239

self.name = ''

240

241

def __cmp__(self, other):

242

if self is other:

243

return 0

244

if not isinstance(other, RootEntry):

245

return NotImplemented

246

return cmp(self.file_id, other.file_id) \

247

or cmp(self.children, other.children)

248

249

250

198

251

class Inventory(XMLMixin):

199

252

"""Inventory of versioned files in a tree.

200

253

213

266

returned quickly.

214

267

215

268

InventoryEntry objects must not be modified after they are

216

inserted.

269

inserted, other than through the Inventory API.

217

270

218

271

>>> inv = Inventory()

219

272

>>> inv.write_xml(sys.stdout)

220

273

221

274

</inventory>

222

>>> inv.add(InventoryEntry('123-123', 'hello.c'))

275

>>> inv.add(InventoryEntry('123-123', 'hello.c', 'file', ROOT_ID))

223

276

>>> inv['123-123'].name

224

277

'hello.c'

225

>>> for file_id in inv: print file_id

226

...

227

123-123

228

278

229

279

May be treated as an iterator or set to look up file ids:

230

280

245

295

246

296

"""

247

297

248

## TODO: Clear up handling of files in subdirectories; we probably

249

## do want to be able to just look them up by name but this

250

## probably means gradually walking down the path, looking up as we go.

251

252

298

## TODO: Make sure only canonical filenames are stored.

253

299

254

300

## TODO: Do something sensible about the possible collisions on

255

301

## case-losing filesystems. Perhaps we should just always forbid

256

302

## such collisions.

257

303

258

## _tree should probably just be stored as

259

## InventoryEntry._children on each directory.

304

## TODO: No special cases for root, rather just give it a file id

305

## like everything else.

306

307

## TODO: Probably change XML serialization to use nesting

260

308

261

309

def __init__(self):

262

310

"""Create or read an inventory.

264

312

If a working directory is specified, the inventory is read

265

313

from there. If the file is specified, read from that. If not,

266

314

the inventory is created empty.

315

316

The inventory is created with a default root directory, with

317

an id of None.

267

318

"""

268

self._byid = dict()

269

270

# _tree is indexed by parent_id; at each level a map from name

271

# to ie. The None entry is the root.

272

self._tree = {None: {}}

319

self.root = RootEntry(ROOT_ID)

320

self._byid = {self.root.file_id: self.root}

273

321

274

322

275

323

def __iter__(self):

281

329

return len(self._byid)

282

330

283

331

284

def iter_entries(self, parent_id=None):

332

def iter_entries(self, from_dir=None):

285

333

"""Return (path, entry) pairs, in order by name."""

286

kids = self._tree[parent_id].items()

334

if from_dir == None:

335

assert self.root

336

from_dir = self.root

337

elif isinstance(from_dir, basestring):

338

from_dir = self._byid[from_dir]

339

340

kids = from_dir.children.items()

287

341

kids.sort()

288

342

for name, ie in kids:

289

343

yield name, ie

290

344

if ie.kind == 'directory':

291

for cn, cie in self.iter_entries(parent_id=ie.file_id):

292

yield joinpath([name, cn]), cie

293

294

295

def directories(self, include_root=True):

345

for cn, cie in self.iter_entries(from_dir=ie.file_id):

346

yield '/'.join((name, cn)), cie

347

348

349

350

def directories(self):

296

351

"""Return (path, entry) pairs for all directories.

297

352

"""

298

if include_root:

299

yield '', None

300

for path, entry in self.iter_entries():

301

if entry.kind == 'directory':

302

yield path, entry

353

def descend(parent_ie):

354

parent_name = parent_ie.name

355

yield parent_name, parent_ie

356

357

# directory children in sorted order

358

dn = []

359

for ie in parent_ie.children.itervalues():

360

if ie.kind == 'directory':

361

dn.append((ie.name, ie))

362

dn.sort()

363

364

for name, child_ie in dn:

365

for sub_name, sub_ie in descend(child_ie):

366

yield appendpath(parent_name, sub_name), sub_ie

367

368

for name, ie in descend(self.root):

369

yield name, ie

303

370

304

371

305

372

306

def children(self, parent_id):

307

"""Return entries that are direct children of parent_id."""

308

return self._tree[parent_id]

309

310

311

312

# TODO: return all paths and entries

313

314

315

373

def __contains__(self, file_id):

316

374

"""True if this entry contains a file with given id.

317

375

318

376

>>> inv = Inventory()

319

>>> inv.add(InventoryEntry('123', 'foo.c'))

377

>>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))

320

378

>>> '123' in inv

321

379

True

322

380

>>> '456' in inv

329

387

"""Return the entry for given file_id.

330

388

331

389

>>> inv = Inventory()

332

>>> inv.add(InventoryEntry('123123', 'hello.c'))

390

>>> inv.add(InventoryEntry('123123', 'hello.c', 'file', ROOT_ID))

333

391

>>> inv['123123'].name

334

392

'hello.c'

335

393

"""

336

return self._byid[file_id]

394

if file_id == None:

395

bailout("can't look up file_id None")

396

397

try:

398

return self._byid[file_id]

399

except KeyError:

400

bailout("file_id {%s} not in inventory" % file_id)

401

402

403

def get_child(self, parent_id, filename):

404

return self[parent_id].children.get(filename)

337

405

338

406

339

407

def add(self, entry):

341

409

342

410

To add a file to a branch ready to be committed, use Branch.add,

343

411

which calls this."""

344

if entry.file_id in self:

412

if entry.file_id in self._byid:

345

413

bailout("inventory already contains entry with id {%s}" % entry.file_id)

346

414

347

if entry.parent_id != None:

348

if entry.parent_id not in self:

349

bailout("parent_id %s of new entry not found in inventory"

350

% entry.parent_id)

351

352

if self._tree[entry.parent_id].has_key(entry.name):

353

bailout("%s is already versioned"

354

% appendpath(self.id2path(entry.parent_id), entry.name))

415

try:

416

parent = self._byid[entry.parent_id]

417

except KeyError:

418

bailout("parent_id {%s} not in inventory" % entry.parent_id)

419

420

if parent.children.has_key(entry.name):

421

bailout("%s is already versioned" %

422

appendpath(self.id2path(parent.file_id), entry.name))

355

423

356

424

self._byid[entry.file_id] = entry

357

self._tree[entry.parent_id][entry.name] = entry

358

359

if entry.kind == 'directory':

360

self._tree[entry.file_id] = {}

425

parent.children[entry.name] = entry

426

427

428

def add_path(self, relpath, kind, file_id=None):

429

"""Add entry from a path.

430

431

The immediate parent must already be versioned"""

432

parts = bzrlib.osutils.splitpath(relpath)

433

if len(parts) == 0:

434

bailout("cannot re-add root of inventory")

435

436

if file_id == None:

437

file_id = bzrlib.branch.gen_file_id(relpath)

438

439

parent_id = self.path2id(parts[:-1])

440

assert parent_id != None

441

ie = InventoryEntry(file_id, parts[-1],

442

kind=kind, parent_id=parent_id)

443

return self.add(ie)

361

444

362

445

363

446

def __delitem__(self, file_id):

364

447

"""Remove entry by id.

365

448

366

449

>>> inv = Inventory()

367

>>> inv.add(InventoryEntry('123', 'foo.c'))

450

>>> inv.add(InventoryEntry('123', 'foo.c', 'file', ROOT_ID))

368

451

>>> '123' in inv

369

452

True

370

453

>>> del inv['123']

373

456

"""

374

457

ie = self[file_id]

375

458

376

assert self._tree[ie.parent_id][ie.name] == ie

459

assert self[ie.parent_id].children[ie.name] == ie

377

460

378

461

# TODO: Test deleting all children; maybe hoist to a separate

379

462

# deltree method?

380

463

if ie.kind == 'directory':

381

for cie in self._tree[file_id].values():

464

for cie in ie.children.values():

382

465

del self[cie.file_id]

383

del self._tree[file_id]

466

del ie.children

384

467

385

468

del self._byid[file_id]

386

del self._tree[ie.parent_id][ie.name]

469

del self[ie.parent_id].children[ie.name]

387

470

388

471

389

472

def id_set(self):

403

486

"""Construct from XML Element

404

487

405

488

>>> inv = Inventory()

406

>>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))

489

>>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c', 'file', ROOT_ID))

407

490

>>> elt = inv.to_element()

408

491

>>> inv2 = Inventory.from_element(elt)

409

492

>>> inv2 == inv

425

508

>>> i2 = Inventory()

426

509

>>> i1 == i2

427

510

True

428

>>> i1.add(InventoryEntry('123', 'foo'))

511

>>> i1.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))

429

512

>>> i1 == i2

430

513

False

431

>>> i2.add(InventoryEntry('123', 'foo'))

514

>>> i2.add(InventoryEntry('123', 'foo', 'file', ROOT_ID))

432

515

>>> i1 == i2

433

516

True

434

517

"""

448

531

return 0

449

532

450

533

451

def id2path(self, file_id):

452

"""Return as a list the path to file_id."""

534

def get_idpath(self, file_id):

535

"""Return a list of file_ids for the path to an entry.

536

537

The list contains one element for each directory followed by

538

the id of the file itself. So the length of the returned list

539

is equal to the depth of the file in the tree, counting the

540

root directory as depth 1.

541

"""

453

542

p = []

454

543

while file_id != None:

455

ie = self[file_id]

456

p = [ie.name] + p

544

try:

545

ie = self._byid[file_id]

546

except KeyError:

547

bailout("file_id {%s} not found in inventory" % file_id)

548

p.insert(0, ie.file_id)

457

549

file_id = ie.parent_id

458

return joinpath(p)

550

return p

551

552

553

def id2path(self, file_id):

554

"""Return as a list the path to file_id."""

555

556

# get all names, skipping root

557

p = [self[fid].name for fid in self.get_idpath(file_id)[1:]]

558

return '/'.join(p)

459

559

460

560

461

561

467

567

468

568

This returns the entry of the last component in the path,

469

569

which may be either a file or a directory.

570

571

Returns None iff the path is not found.

470

572

"""

471

assert isinstance(name, types.StringTypes)

472

473

parent_id = None

474

for f in splitpath(name):

573

if isinstance(name, types.StringTypes):

574

name = splitpath(name)

575

576

mutter("lookup path %r" % name)

577

578

parent = self.root

579

for f in name:

475

580

try:

476

cie = self._tree[parent_id][f]

581

cie = parent.children[f]

477

582

assert cie.name == f

478

parent_id = cie.file_id

583

assert cie.parent_id == parent.file_id

584

parent = cie

479

585

except KeyError:

480

586

# or raise an error?

481

587

return None

482

588

483

return parent_id

484

485

486

def get_child(self, parent_id, child_name):

487

return self._tree[parent_id].get(child_name)

589

return parent.file_id

488

590

489

591

490

592

def has_filename(self, names):

492

594

493

595

494

596

def has_id(self, file_id):

495

assert isinstance(file_id, str)

496

597

return self._byid.has_key(file_id)

497

598

498

599

499

500

if __name__ == '__main__':

501

import doctest, inventory

502

doctest.testmod(inventory)

600

def rename(self, file_id, new_parent_id, new_name):

601

"""Move a file within the inventory.

602

603

This can change either the name, or the parent, or both.

604

605

This does not move the working file."""

606

if not is_valid_name(new_name):

607

bailout("not an acceptable filename: %r" % new_name)

608

609

new_parent = self._byid[new_parent_id]

610

if new_name in new_parent.children:

611

bailout("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))

612

613

new_parent_idpath = self.get_idpath(new_parent_id)

614

if file_id in new_parent_idpath:

615

bailout("cannot move directory %r into a subdirectory of itself, %r"

616

% (self.id2path(file_id), self.id2path(new_parent_id)))

617

618

file_ie = self._byid[file_id]

619

old_parent = self._byid[file_ie.parent_id]

620

621

# TODO: Don't leave things messed up if this fails

622

623

del old_parent.children[file_ie.name]

624

new_parent.children[new_name] = file_ie

625

626

file_ie.name = new_name

627

file_ie.parent_id = new_parent_id

628

629

630

631

632

_NAME_RE = re.compile(r'^[^/\\]+$')

633

634

def is_valid_name(name):

635

return bool(_NAME_RE.match(name))