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

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

15

14

# along with this program; if not, write to the Free Software

16

15

# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

17

16

18

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

19

20

21

22

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

23

24

import sys, os.path, types

17

18

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

19

20

21

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

22

# created, but it's not for now.

23

ROOT_ID = "TREE_ROOT"

24

25

26

import sys, os.path, types, re

25

27

from sets import Set

26

28

27

29

try:

30

32

from elementtree.ElementTree import Element, ElementTree, SubElement

31

33

32

34

from xml import XMLMixin

33

from errors import bailout

35

from errors import bailout, BzrError

34

36

35

37

import bzrlib

36

38

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

59

61

60

62

>>> i = Inventory()

61

63

>>> i.path2id('')

62

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

63

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

64

'TREE_ROOT'

65

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

66

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

64

67

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

65

68

... print j

66

69

...

67

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

70

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

68

71

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

69

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

72

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

70

73

Traceback (most recent call last):

71

74

...

72

75

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

73

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

74

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

76

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

77

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

75

78

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

76

79

'2325'

77

80

>>> '2325' in i

78

81

True

79

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

82

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

80

83

>>> i['2326']

81

84

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

82

85

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

91

94

>>> i.id2path('2326')

92

95

'src/wibble/wibble.c'

93

96

94

:todo: Maybe also keep the full path of the entry, and the children?

97

TODO: Maybe also keep the full path of the entry, and the children?

95

98

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

96

99

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

97

100

"""

98

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

99

parent_id=None):

101

102

# TODO: split InventoryEntry into subclasses for files,

103

# directories, etc etc.

104

105

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

100

106

"""Create an InventoryEntry

101

107

102

108

The filename must be a single component, relative to the

103

109

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

104

110

105

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

111

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

106

112

>>> e.name

107

113

'hello.c'

108

114

>>> e.file_id

109

115

'123'

110

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

116

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

111

117

Traceback (most recent call last):

112

118

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

113

119

"""

118

124

119

125

self.file_id = file_id

120

126

self.name = name

121

assert kind in ['file', 'directory']

122

127

self.kind = kind

123

128

self.text_id = text_id

124

129

self.parent_id = parent_id

125

130

self.text_sha1 = None

126

131

self.text_size = None

132

if kind == 'directory':

133

self.children = {}

134

elif kind == 'file':

135

pass

136

else:

137

raise BzrError("unhandled entry kind %r" % kind)

138

139

140

141

def sorted_children(self):

142

l = self.children.items()

143

l.sort()

144

return l

127

145

128

146

129

147

def copy(self):

130

148

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

131

self.text_id, self.parent_id)

149

self.parent_id, text_id=self.text_id)

132

150

other.text_sha1 = self.text_sha1

133

151

other.text_size = self.text_size

134

152

return other

151

169

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

152

170

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

153

171

154

if self.text_size is not None:

172

if self.text_size != None:

155

173

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

156

174

157

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

175

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

158

176

v = getattr(self, f)

159

if v is not None:

177

if v != None:

160

178

e.set(f, v)

161

179

180

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

181

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

182

# version it will be implied by nested elements.

183

if self.parent_id != ROOT_ID:

184

assert isinstance(self.parent_id, basestring)

185

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

186

162

187

e.tail = '\n'

163

188

164

189

return e

166

191

167

192

def from_element(cls, elt):

168

193

assert elt.tag == 'entry'

169

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

194

195

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

196

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

197

## internally.

198

parent_id = elt.get('parent_id')

199

if parent_id == None:

200

parent_id = ROOT_ID

201

202

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

170

203

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

171

204

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

172

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

173

205

174

206

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

175

207

197

229

198

230

199

231

232

class RootEntry(InventoryEntry):

233

def __init__(self, file_id):

234

self.file_id = file_id

235

self.children = {}

236

self.kind = 'root_directory'

237

self.parent_id = None

238

self.name = ''

239

240

def __cmp__(self, other):

241

if self is other:

242

return 0

243

if not isinstance(other, RootEntry):

244

return NotImplemented

245

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

246

or cmp(self.children, other.children)

247

248

249

200

250

class Inventory(XMLMixin):

201

251

"""Inventory of versioned files in a tree.

202

252

203

An Inventory acts like a set of InventoryEntry items. You can

204

also look files up by their file_id or name.

205

206

May be read from and written to a metadata file in a tree. To

207

manipulate the inventory (for example to add a file), it is read

208

in, modified, and then written back out.

253

This describes which file_id is present at each point in the tree,

254

and possibly the SHA-1 or other information about the file.

255

Entries can be looked up either by path or by file_id.

209

256

210

257

The inventory represents a typical unix file tree, with

211

258

directories containing files and subdirectories. We never store

215

262

returned quickly.

216

263

217

264

InventoryEntry objects must not be modified after they are

218

inserted.

265

inserted, other than through the Inventory API.

219

266

220

267

>>> inv = Inventory()

221

268

>>> inv.write_xml(sys.stdout)

222

269

223

270

</inventory>

224

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

271

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

225

272

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

226

273

'hello.c'

227

>>> for file_id in inv: print file_id

228

...

229

123-123

230

274

231

275

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

232

276

247

291

248

292

"""

249

293

250

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

251

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

252

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

253

254

294

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

255

295

256

296

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

257

297

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

258

298

## such collisions.

259

299

260

## _tree should probably just be stored as

261

## InventoryEntry._children on each directory.

300

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

301

## like everything else.

302

303

## TODO: Probably change XML serialization to use nesting rather

304

## than parent_id pointers.

305

306

## TODO: Perhaps hold the ElementTree in memory and work directly

307

## on that rather than converting into Python objects every time?

262

308

263

309

def __init__(self):

264

310

"""Create or read an inventory.

266

312

If a working directory is specified, the inventory is read

267

313

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

268

314

the inventory is created empty.

315

316

The inventory is created with a default root directory, with

317

an id of None.

269

318

"""

270

self._byid = dict()

271

272

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

273

# to ie. The None entry is the root.

274

self._tree = {None: {}}

319

self.root = RootEntry(ROOT_ID)

320

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

275

321

276

322

277

323

def __iter__(self):

283

329

return len(self._byid)

284

330

285

331

286

def iter_entries(self, parent_id=None):

332

def iter_entries(self, from_dir=None):

287

333

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

288

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()

289

341

kids.sort()

290

342

for name, ie in kids:

291

343

yield name, ie

292

344

if ie.kind == 'directory':

293

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

294

yield joinpath([name, cn]), cie

295

296

297

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):

298

351

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

299

352

"""

300

if include_root:

301

yield '', None

302

for path, entry in self.iter_entries():

303

if entry.kind == 'directory':

304

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

305

370

306

371

307

372

308

def children(self, parent_id):

309

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

310

return self._tree[parent_id]

311

312

313

314

# TODO: return all paths and entries

315

316

317

373

def __contains__(self, file_id):

318

374

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

319

375

320

376

>>> inv = Inventory()

321

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

377

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

322

378

>>> '123' in inv

323

379

True

324

380

>>> '456' in inv

331

387

"""Return the entry for given file_id.

332

388

333

389

>>> inv = Inventory()

334

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

390

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

335

391

>>> inv['123123'].name

336

392

'hello.c'

337

393

"""

338

return self._byid[file_id]

394

if file_id == None:

395

raise BzrError("can't look up file_id None")

396

397

try:

398

return self._byid[file_id]

399

except KeyError:

400

raise BzrError("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)

339

405

340

406

341

407

def add(self, entry):

343

409

344

410

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

345

411

which calls this."""

346

if entry.file_id in self:

412

if entry.file_id in self._byid:

347

413

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

348

414

349

if entry.parent_id != None:

350

if entry.parent_id not in self:

351

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

352

% entry.parent_id)

353

354

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

355

bailout("%s is already versioned"

356

% 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))

357

423

358

424

self._byid[entry.file_id] = entry

359

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

360

361

if entry.kind == 'directory':

362

self._tree[entry.file_id] = {}

425

parent.children[entry.name] = entry

363

426

364

427

365

428

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

370

433

if len(parts) == 0:

371

434

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

372

435

373

if file_id is None:

436

if file_id == None:

374

437

file_id = bzrlib.branch.gen_file_id(relpath)

375

438

376

439

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

440

assert parent_id != None

377

441

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

378

442

kind=kind, parent_id=parent_id)

379

443

return self.add(ie)

383

447

"""Remove entry by id.

384

448

385

449

>>> inv = Inventory()

386

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

450

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

387

451

>>> '123' in inv

388

452

True

389

453

>>> del inv['123']

392

456

"""

393

457

ie = self[file_id]

394

458

395

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

459

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

396

460

397

461

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

398

462

# deltree method?

399

463

if ie.kind == 'directory':

400

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

464

for cie in ie.children.values():

401

465

del self[cie.file_id]

402

del self._tree[file_id]

466

del ie.children

403

467

404

468

del self._byid[file_id]

405

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

469

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

406

470

407

471

408

472

def id_set(self):

422

486

"""Construct from XML Element

423

487

424

488

>>> inv = Inventory()

425

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

489

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

426

490

>>> elt = inv.to_element()

427

491

>>> inv2 = Inventory.from_element(elt)

428

492

>>> inv2 == inv

444

508

>>> i2 = Inventory()

445

509

>>> i1 == i2

446

510

True

447

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

511

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

448

512

>>> i1 == i2

449

513

False

450

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

514

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

451

515

>>> i1 == i2

452

516

True

453

517

"""

467

531

return 0

468

532

469

533

470

def id2path(self, file_id):

471

"""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

"""

472

542

p = []

473

543

while file_id != None:

474

ie = self[file_id]

475

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)

476

549

file_id = ie.parent_id

477

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)

478

559

479

560

480

561

486

567

487

568

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

488

569

which may be either a file or a directory.

570

571

Returns None iff the path is not found.

489

572

"""

490

573

if isinstance(name, types.StringTypes):

491

574

name = splitpath(name)

492

575

493

parent_id = None

576

mutter("lookup path %r" % name)

577

578

parent = self.root

494

579

for f in name:

495

580

try:

496

cie = self._tree[parent_id][f]

581

cie = parent.children[f]

497

582

assert cie.name == f

498

parent_id = cie.file_id

583

assert cie.parent_id == parent.file_id

584

parent = cie

499

585

except KeyError:

500

586

# or raise an error?

501

587

return None

502

588

503

return parent_id

504

505

506

def get_child(self, parent_id, child_name):

507

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

589

return parent.file_id

508

590

509

591

510

592

def has_filename(self, names):

512

594

513

595

514

596

def has_id(self, file_id):

515

assert isinstance(file_id, str)

516

597

return self._byid.has_key(file_id)

517

598

518

599

519

520

521

522

if __name__ == '__main__':

523

import doctest, inventory

524

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))