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

21

22

"""Weave - storage of related text file versions"""

23

24

# before intset (r923) 2000 versions in 41.5s

25

# with intset (r926) 2000 versions in 93s !!!

26

# better to just use plain sets.

27

28

# making _extract build and return a list, rather than being a generator

29

# takes 37.94s

30

31

# with python -O, r923 does 2000 versions in 36.87s

32

33

# with optimizations to avoid mutating lists - 35.75! I guess copying

34

# all the elements every time costs more than the small manipulations.

35

# a surprisingly small change.

36

37

# r931, which avoids using a generator for extract, does 36.98s

38

39

# with memoized inclusions, takes 41.49s; not very good

40

41

# with slots, takes 37.35s; without takes 39.16, a bit surprising

42

43

# with the delta calculation mixed in with the add method, rather than

44

# separated, takes 36.78s

45

46

# with delta folded in and mutation of the list, 36.13s

47

48

# with all this and simplification of add code, 33s

49

50

51

24

# TODO: Perhaps have copy method for Weave instances?

52

25

53

26

# XXX: If we do weaves this way, will a merge still behave the same

71

44

# properly nested, that there is no text outside of an insertion, that

72

45

# insertions or deletions are not repeated, etc.

73

46

47

# TODO: Make the info command just show info, not extract everything:

48

# it can be much faster.

49

50

# TODO: Perhaps use long integers as sets instead of set objects; may

51

# be faster.

52

74

53

# TODO: Parallel-extract that passes back each line along with a

75

54

# description of which revisions include it. Nice for checking all

76

55

# shas in parallel.

78

57

79

58

80

59

60

try:

61

set

62

frozenset

63

except NameError:

64

from sets import Set, ImmutableSet

65

set = Set

66

frozenset = ImmutableSet

67

del Set, ImmutableSet

68

69

81

70

class WeaveError(Exception):

82

71

"""Exception in processing weave"""

83

72

107

96

the version-id is used to reference it in the larger world.

108

97

109

98

The weave is represented as a list mixing edit instructions and

110

literal text. Each entry in _weave can be either a string (or

99

literal text. Each entry in _l can be either a string (or

111

100

unicode), or a tuple. If a string, it means that the given line

112

101

should be output in the currently active revisions.

113

102

151

140

should be no way to get an earlier version deleting a later

152

141

version.

153

142

154

_weave

155

Text of the weave; list of control instruction tuples and strings.

143

_l

144

Text of the weave.

156

145

157

_parents

146

_v

158

147

List of parents, indexed by version number.

159

148

It is only necessary to store the minimal set of parents for

160

149

each version; the parent's parents are implied.

162

151

_sha1s

163

152

List of hex SHA-1 of each version, or None if not recorded.

164

153

"""

165

166

__slots__ = ['_weave', '_parents', '_sha1s']

167

168

154

def __init__(self):

169

self._weave = []

170

self._parents = []

155

self._l = []

156

self._v = []

171

157

self._sha1s = []

172

158

173

159

174

160

def __eq__(self, other):

175

161

if not isinstance(other, Weave):

176

162

return False

177

return self._parents == other._parents \

178

and self._weave == other._weave

163

return self._v == other._v \

164

and self._l == other._l

179

165

180

166

181

167

def __ne__(self, other):

192

178

193

179

text

194

180

Sequence of lines to be added in the new version."""

195

196

self._check_versions(parents)

181

## self._check_versions(parents)

197

182

## self._check_lines(text)

198

new_version = len(self._parents)

183

idx = len(self._v)

199

184

200

185

import sha

201

186

s = sha.new()

202

map(s.update, text)

187

for l in text:

188

s.update(l)

203

189

sha1 = s.hexdigest()

204

190

del s

205

191

206

# if we abort after here the weave will be corrupt

207

self._parents.append(frozenset(parents))

192

# TODO: It'd probably be faster to append things on to a new

193

# list rather than modifying the existing one, which is likely

194

# to cause a lot of copying.

195

196

if parents:

197

ancestors = self.inclusions(parents)

198

delta = self._delta(ancestors, text)

199

200

# offset gives the number of lines that have been inserted

201

# into the weave up to the current point; if the original edit instruction

202

# says to change line A then we actually change (A+offset)

203

offset = 0

204

205

for i1, i2, newlines in delta:

206

assert 0 <= i1

207

assert i1 <= i2

208

assert i2 <= len(self._l)

209

210

# the deletion and insertion are handled separately.

211

# first delete the region.

212

if i1 != i2:

213

self._l.insert(i1+offset, ('[', idx))

214

self._l.insert(i2+offset+1, (']', idx))

215

offset += 2

216

# is this OK???

217

218

if newlines:

219

# there may have been a deletion spanning up to

220

# i2; we want to insert after this region to make sure

221

# we don't destroy ourselves

222

i = i2 + offset

223

self._l[i:i] = [('{', idx)] \

224

+ newlines \

225

+ [('}', idx)]

226

offset += 2 + len(newlines)

227

228

self._addversion(parents)

229

else:

230

# special case; adding with no parents revision; can do this

231

# more quickly by just appending unconditionally

232

self._l.append(('{', idx))

233

self._l += text

234

self._l.append(('}', idx))

235

236

self._addversion(None)

237

208

238

self._sha1s.append(sha1)

209

210

211

if not parents:

212

# special case; adding with no parents revision; can do

213

# this more quickly by just appending unconditionally.

214

# even more specially, if we're adding an empty text we

215

# need do nothing at all.

216

if text:

217

self._weave.append(('{', new_version))

218

self._weave.extend(text)

219

self._weave.append(('}', new_version))

220

221

return new_version

222

223

if len(parents) == 1:

224

pv = list(parents)[0]

225

if sha1 == self._sha1s[pv]:

226

# special case: same as the single parent

227

return new_version

228

229

230

ancestors = self.inclusions(parents)

231

232

l = self._weave

233

234

# basis a list of (origin, lineno, line)

235

basis_lineno = []

236

basis_lines = []

237

for origin, lineno, line in self._extract(ancestors):

238

basis_lineno.append(lineno)

239

basis_lines.append(line)

240

241

# another small special case: a merge, producing the same text as auto-merge

242

if text == basis_lines:

243

return new_version

244

245

# add a sentinal, because we can also match against the final line

246

basis_lineno.append(len(self._weave))

247

248

# XXX: which line of the weave should we really consider

249

# matches the end of the file? the current code says it's the

250

# last line of the weave?

251

252

#print 'basis_lines:', basis_lines

253

#print 'new_lines: ', lines

254

255

from difflib import SequenceMatcher

256

s = SequenceMatcher(None, basis_lines, text)

257

258

# offset gives the number of lines that have been inserted

259

# into the weave up to the current point; if the original edit instruction

260

# says to change line A then we actually change (A+offset)

261

offset = 0

262

263

for tag, i1, i2, j1, j2 in s.get_opcodes():

264

# i1,i2 are given in offsets within basis_lines; we need to map them

265

# back to offsets within the entire weave

266

#print 'raw match', tag, i1, i2, j1, j2

267

if tag == 'equal':

268

continue

269

270

i1 = basis_lineno[i1]

271

i2 = basis_lineno[i2]

272

273

assert 0 <= j1 <= j2 <= len(text)

274

275

#print tag, i1, i2, j1, j2

276

277

# the deletion and insertion are handled separately.

278

# first delete the region.

279

if i1 != i2:

280

self._weave.insert(i1+offset, ('[', new_version))

281

self._weave.insert(i2+offset+1, (']', new_version))

282

offset += 2

283

284

if j1 != j2:

285

# there may have been a deletion spanning up to

286

# i2; we want to insert after this region to make sure

287

# we don't destroy ourselves

288

i = i2 + offset

289

self._weave[i:i] = ([('{', new_version)]

290

+ text[j1:j2]

291

+ [('}', new_version)])

292

offset += 2 + (j2 - j1)

293

294

return new_version

239

240

return idx

241

242

243

def inclusions_bitset(self, versions):

244

i = 0

245

for v in versions:

246

i |= (1L << v)

247

v = max(versions)

248

while v >= 0:

249

if i & (1L << v):

250

# if v is included, include all its parents

251

for pv in self._v[v]:

252

i |= (1L << pv)

253

v -= 1

254

return i

295

255

296

256

297

257

def inclusions(self, versions):

302

262

while v >= 0:

303

263

if v in i:

304

264

# include all its parents

305

i.update(self._parents[v])

265

i.update(self._v[v])

306

266

v -= 1

307

267

return i

308

268

except IndexError:

311

271

312

272

def minimal_parents(self, version):

313

273

"""Find the minimal set of parents for the version."""

314

included = self._parents[version]

274

included = self._v[version]

315

275

if not included:

316

276

return []

317

277

331

291

return mininc

332

292

333

293

294

def _addversion(self, parents):

295

if parents:

296

self._v.append(parents)

297

else:

298

self._v.append(frozenset())

299

334

300

335

301

def _check_lines(self, text):

336

302

if not isinstance(text, list):

347

313

"""Check everything in the sequence of indexes is valid"""

348

314

for i in indexes:

349

315

try:

350

self._parents[i]

316

self._v[i]

351

317

except IndexError:

352

318

raise IndexError("invalid version number %r" % i)

353

319

373

339

"""

374

340

375

341

istack = []

376

dset = set()

342

dset = 0L

377

343

378

344

lineno = 0 # line of weave, 0-based

379

345

380

for l in self._weave:

346

for l in self._l:

381

347

if isinstance(l, tuple):

382

348

c, v = l

383

349

isactive = None

386

352

elif c == '}':

387

353

oldv = istack.pop()

388

354

elif c == '[':

389

assert v not in dset

390

dset.add(v)

355

vs = (1L << v)

356

assert not (dset & vs)

357

dset |= vs

391

358

elif c == ']':

392

dset.remove(v)

359

vs = (1L << v)

360

assert dset & vs

361

dset ^= vs

393

362

else:

394

363

raise WeaveFormatError('unexpected instruction %r'

395

364

% v)

419

388

420

389

isactive = None

421

390

422

result = []

423

424

391

WFE = WeaveFormatError

425

392

426

for l in self._weave:

393

for l in self._l:

427

394

if isinstance(l, tuple):

428

395

c, v = l

429

396

isactive = None

447

414

if isactive is None:

448

415

isactive = (not dset) and istack and (istack[-1] in included)

449

416

if isactive:

450

result.append((istack[-1], lineno, l))

417

yield istack[-1], lineno, l

451

418

lineno += 1

452

419

453

420

if istack:

457

424

raise WFE("unclosed deletion blocks at end of weave",

458

425

dset)

459

426

460

return result

461

462

463

427

464

428

def get_iter(self, version):

465

429

"""Yield lines for the specified version."""

473

437

474

438

def mash_iter(self, included):

475

439

"""Return composed version of multiple included versions."""

440

included = frozenset(included)

476

441

for origin, lineno, text in self._extract(included):

477

442

yield text

478

443

479

444

480

445

def dump(self, to_file):

481

446

from pprint import pprint

482

print >>to_file, "Weave._weave = ",

483

pprint(self._weave, to_file)

484

print >>to_file, "Weave._parents = ",

485

pprint(self._parents, to_file)

447

print >>to_file, "Weave._l = ",

448

pprint(self._l, to_file)

449

print >>to_file, "Weave._v = ",

450

pprint(self._v, to_file)

486

451

487

452

488

453

489

454

def numversions(self):

490

l = len(self._parents)

455

l = len(self._v)

491

456

assert l == len(self._sha1s)

492

457

return l

493

458

494

459

495

def __len__(self):

496

return self.numversions()

497

498

499

460

def check(self, progress_bar=None):

500

461

# check no circular inclusions

501

462

for version in range(self.numversions()):

502

inclusions = list(self._parents[version])

463

inclusions = list(self._v[version])

503

464

if inclusions:

504

465

inclusions.sort()

505

466

if inclusions[-1] >= version:

565

526

If line1=line2, this is a pure insert; if newlines=[] this is a

566

527

pure delete. (Similar to difflib.)

567

528

"""

529

# basis a list of (origin, lineno, line)

530

basis_lineno = []

531

basis_lines = []

532

for origin, lineno, line in self._extract(included):

533

basis_lineno.append(lineno)

534

basis_lines.append(line)

535

536

# add a sentinal, because we can also match against the final line

537

basis_lineno.append(len(self._l))

538

539

# XXX: which line of the weave should we really consider

540

# matches the end of the file? the current code says it's the

541

# last line of the weave?

542

543

from difflib import SequenceMatcher

544

s = SequenceMatcher(None, basis_lines, lines)

545

546

# TODO: Perhaps return line numbers from composed weave as well?

547

548

for tag, i1, i2, j1, j2 in s.get_opcodes():

549

##print tag, i1, i2, j1, j2

550

551

if tag == 'equal':

552

continue

553

554

# i1,i2 are given in offsets within basis_lines; we need to map them

555

# back to offsets within the entire weave

556

real_i1 = basis_lineno[i1]

557

real_i2 = basis_lineno[i2]

558

559

assert 0 <= j1

560

assert j1 <= j2

561

assert j2 <= len(lines)

562

563

yield real_i1, real_i2, lines[j1:j2]

568

564

569

565

570

566

576

572

577

573

Weave lines present in none of them are skipped entirely.

578

574

"""

579

inc_a = self.inclusions([ver_a])

580

inc_b = self.inclusions([ver_b])

575

inc_a = self.inclusions_bitset([ver_a])

576

inc_b = self.inclusions_bitset([ver_b])

581

577

inc_c = inc_a & inc_b

582

578

583

579

for lineno, insert, deleteset, line in self._walk():

580

insertset = (1L << insert)

584

581

if deleteset & inc_c:

585

582

# killed in parent; can't be in either a or b

586

583

# not relevant to our work

587

584

yield 'killed-base', line

588

elif insert in inc_c:

585

elif insertset & inc_c:

589

586

# was inserted in base

590

587

killed_a = bool(deleteset & inc_a)

591

588

killed_b = bool(deleteset & inc_b)

597

594

yield 'killed-b', line

598

595

else:

599

596

yield 'unchanged', line

600

elif insert in inc_a:

597

elif insertset & inc_a:

601

598

if deleteset & inc_a:

602

599

yield 'ghost-a', line

603

600

else:

604

601

# new in A; not in B

605

602

yield 'new-a', line

606

elif insert in inc_b:

603

elif insertset & inc_b:

607

604

if deleteset & inc_b:

608

605

yield 'ghost-b', line

609

606

else:

670

667

671

668

672

669

673

def weave_info(w):

670

def weave_info(filename, out):

674

671

"""Show some text information about the weave."""

675

print '%6s %40s %20s' % ('ver', 'sha1', 'parents')

676

for i in (6, 40, 20):

677

print '-' * i,

678

print

679

for i in range(w.numversions()):

680

sha1 = w._sha1s[i]

681

print '%6d %40s %s' % (i, sha1, ' '.join(map(str, w._parents[i])))

682

683

684

685

def weave_stats(weave_file):

686

from bzrlib.progress import ProgressBar

687

from bzrlib.weavefile import read_weave

688

689

pb = ProgressBar()

690

691

wf = file(weave_file, 'rb')

672

from weavefile import read_weave

673

wf = file(filename, 'rb')

692

674

w = read_weave(wf)

693

675

# FIXME: doesn't work on pipes

694

676

weave_size = wf.tell()

677

print >>out, "weave file size %d bytes" % weave_size

678

print >>out, "weave contains %d versions" % len(w._v)

695

679

696

680

total = 0

697

vers = len(w)

698

for i in range(vers):

699

pb.update('checking sizes', i, vers)

700

for line in w.get_iter(i):

701

total += len(line)

702

703

pb.clear()

704

705

print 'versions %9d' % vers

706

print 'weave file %9d bytes' % weave_size

707

print 'total contents %9d bytes' % total

708

print 'compression ratio %9.2fx' % (float(total) / float(weave_size))

709

681

print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')

682

for i in (6, 6, 8, 40, 20):

683

print '-' * i,

684

print

685

for i in range(len(w._v)):

686

text = w.get(i)

687

lines = len(text)

688

bytes = sum((len(a) for a in text))

689

sha1 = w._sha1s[i]

690

print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),

691

for pv in w._v[i]:

692

print pv,

693

print

694

total += bytes

695

696

print >>out, "versions total %d bytes" % total

697

print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))

710

698

711

699

712

700

def usage():

810

798

lasto = origin

811

799

812

800

elif cmd == 'info':

813

weave_info(readit())

814

815

elif cmd == 'stats':

816

weave_stats(argv[2])

801

weave_info(argv[2], sys.stdout)

817

802

818

803

elif cmd == 'check':

819

804

w = readit()

820

805

pb = ProgressBar()

821

806

w.check(pb)

822

807

pb.clear()

823

print '%d versions ok' % w.numversions()

824

808

825

809

elif cmd == 'inclusions':

826

810

w = readit()

828

812

829

813

elif cmd == 'parents':

830

814

w = readit()

831

print ' '.join(map(str, w._parents[int(argv[3])]))

815

print ' '.join(map(str, w._v[int(argv[3])]))

832

816

833

817

elif cmd == 'plan-merge':

834

818

w = readit()