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

1

2

#

3

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

4

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

5

# the Free Software Foundation; either version 2 of the License, or

6

# (at your option) any later version.

7

#

8

# This program is distributed in the hope that it will be useful,

9

# but WITHOUT ANY WARRANTY; without even the implied warranty of

10

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

11

# GNU General Public License for more details.

12

#

13

# You should have received a copy of the GNU General Public License

14

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

15

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

16

17

"""Tests for indices."""

18

19

from bzrlib import errors

20

from bzrlib.index import *

21

from bzrlib.tests import TestCaseWithMemoryTransport

22

23

24

class TestGraphIndexBuilder(TestCaseWithMemoryTransport):

25

26

def test_build_index_empty(self):

27

builder = GraphIndexBuilder()

28

stream = builder.finish()

29

contents = stream.read()

30

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n\n", contents)

31

32

def test_build_index_one_reference_list_empty(self):

33

builder = GraphIndexBuilder(reference_lists=1)

34

stream = builder.finish()

35

contents = stream.read()

36

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n\n", contents)

37

38

def test_build_index_two_reference_list_empty(self):

39

builder = GraphIndexBuilder(reference_lists=2)

40

stream = builder.finish()

41

contents = stream.read()

42

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n\n", contents)

43

44

def test_build_index_one_node_no_refs(self):

45

builder = GraphIndexBuilder()

46

builder.add_node('akey', 'data')

47

stream = builder.finish()

48

contents = stream.read()

49

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"

50

"akey\x00\x00\x00data\n\n", contents)

51

52

def test_build_index_one_node_no_refs_accepts_empty_reflist(self):

53

builder = GraphIndexBuilder()

54

builder.add_node('akey', 'data', ())

55

stream = builder.finish()

56

contents = stream.read()

57

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"

58

"akey\x00\x00\x00data\n\n", contents)

59

60

def test_add_node_empty_value(self):

61

builder = GraphIndexBuilder()

62

builder.add_node('akey', '')

63

stream = builder.finish()

64

contents = stream.read()

65

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"

66

"akey\x00\x00\x00\n\n", contents)

67

68

def test_build_index_two_nodes_sorted(self):

69

# the highest sorted node comes first.

70

builder = GraphIndexBuilder()

71

# use three to have a good chance of glitching dictionary hash

72

# lookups etc. Insert in randomish order that is not correct

73

# and not the reverse of the correct order.

74

builder.add_node('2002', 'data')

75

builder.add_node('2000', 'data')

76

builder.add_node('2001', 'data')

77

stream = builder.finish()

78

contents = stream.read()

79

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=0\n"

80

"2000\x00\x00\x00data\n"

81

"2001\x00\x00\x00data\n"

82

"2002\x00\x00\x00data\n"

83

"\n", contents)

84

85

def test_build_index_reference_lists_are_included_one(self):

86

builder = GraphIndexBuilder(reference_lists=1)

87

builder.add_node('key', 'data', ([], ))

88

stream = builder.finish()

89

contents = stream.read()

90

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"

91

"key\x00\x00\x00data\n"

92

"\n", contents)

93

94

def test_build_index_reference_lists_are_included_two(self):

95

builder = GraphIndexBuilder(reference_lists=2)

96

builder.add_node('key', 'data', ([], []))

97

stream = builder.finish()

98

contents = stream.read()

99

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n"

100

"key\x00\x00\t\x00data\n"

101

"\n", contents)

102

103

def test_node_references_are_byte_offsets(self):

104

builder = GraphIndexBuilder(reference_lists=1)

105

builder.add_node('reference', 'data', ([], ))

106

builder.add_node('key', 'data', (['reference'], ))

107

stream = builder.finish()

108

contents = stream.read()

109

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"

110

"key\x00\x0051\x00data\n"

111

"reference\x00\x00\x00data\n"

112

"\n", contents)

113

114

def test_node_references_are_cr_delimited(self):

115

builder = GraphIndexBuilder(reference_lists=1)

116

builder.add_node('reference', 'data', ([], ))

117

builder.add_node('reference2', 'data', ([], ))

118

builder.add_node('key', 'data', (['reference', 'reference2'], ))

119

stream = builder.finish()

120

contents = stream.read()

121

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"

122

"key\x00\x0054\r71\x00data\n"

123

"reference\x00\x00\x00data\n"

124

"reference2\x00\x00\x00data\n"

125

"\n", contents)

126

127

def test_multiple_reference_lists_are_tab_delimited(self):

128

builder = GraphIndexBuilder(reference_lists=2)

129

builder.add_node('keference', 'data', ([], []))

130

builder.add_node('rey', 'data', (['keference'], ['keference']))

131

stream = builder.finish()

132

contents = stream.read()

133

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n"

134

"keference\x00\x00\t\x00data\n"

135

"rey\x00\x0038\t38\x00data\n"

136

"\n", contents)

137

138

def test_add_node_referencing_missing_key_makes_absent(self):

139

builder = GraphIndexBuilder(reference_lists=1)

140

builder.add_node('rey', 'data', (['beference', 'aeference2'], ))

141

stream = builder.finish()

142

contents = stream.read()

143

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"

144

"aeference2\x00a\x00\x00\n"

145

"beference\x00a\x00\x00\n"

146

"rey\x00\x0053\r38\x00data\n"

147

"\n", contents)

148

149

def test_node_references_three_digits(self):

150

# test the node digit expands as needed.

151

builder = GraphIndexBuilder(reference_lists=1)

152

references = map(str, reversed(range(9)))

153

builder.add_node('2-key', '', (references, ))

154

stream = builder.finish()

155

contents = stream.read()

156

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=1\n"

157

"0\x00a\x00\x00\n"

158

"1\x00a\x00\x00\n"

159

"2\x00a\x00\x00\n"

160

"2-key\x00\x00130\r124\r118\r112\r106\r100\r050\r044\r038\x00\n"

161

"3\x00a\x00\x00\n"

162

"4\x00a\x00\x00\n"

163

"5\x00a\x00\x00\n"

164

"6\x00a\x00\x00\n"

165

"7\x00a\x00\x00\n"

166

"8\x00a\x00\x00\n"

167

"\n", contents)

168

169

def test_absent_has_no_reference_overhead(self):

170

# the offsets after an absent record should be correct when there are

171

# >1 reference lists.

172

builder = GraphIndexBuilder(reference_lists=2)

173

builder.add_node('parent', '', (['aail', 'zther'], []))

174

stream = builder.finish()

175

contents = stream.read()

176

self.assertEqual("Bazaar Graph Index 1\nnode_ref_lists=2\n"

177

"aail\x00a\x00\x00\n"

178

"parent\x00\x0038\r63\t\x00\n"

179

"zther\x00a\x00\x00\n"

180

"\n", contents)

181

182

def test_add_node_bad_key(self):

183

builder = GraphIndexBuilder()

184

for bad_char in '\t\n\x0b\x0c\r\x00 ':

185

self.assertRaises(errors.BadIndexKey, builder.add_node,

186

'a%skey' % bad_char, 'data')

187

self.assertRaises(errors.BadIndexKey, builder.add_node,

188

'', 'data')

189

190

def test_add_node_bad_data(self):

191

builder = GraphIndexBuilder()

192

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

193

'data\naa')

194

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

195

'data\x00aa')

196

197

def test_add_node_bad_mismatched_ref_lists_length(self):

198

builder = GraphIndexBuilder()

199

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

200

'data aa', ([], ))

201

builder = GraphIndexBuilder(reference_lists=1)

202

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

203

'data aa')

204

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

205

'data aa', (), )

206

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

207

'data aa', ([], []))

208

builder = GraphIndexBuilder(reference_lists=2)

209

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

210

'data aa')

211

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

212

'data aa', ([], ))

213

self.assertRaises(errors.BadIndexValue, builder.add_node, 'akey',

214

'data aa', ([], [], []))

215

216

def test_add_node_bad_key_in_reference_lists(self):

217

# first list, first key - trivial

218

builder = GraphIndexBuilder(reference_lists=1)

219

self.assertRaises(errors.BadIndexKey, builder.add_node, 'akey',

220

'data aa', (['a key'], ))

221

# need to check more than the first key in the list

222

self.assertRaises(errors.BadIndexKey, builder.add_node, 'akey',

223

'data aa', (['agoodkey', 'this is a bad key'], ))

224

# and if there is more than one list it should be getting checked

225

# too

226

builder = GraphIndexBuilder(reference_lists=2)

227

self.assertRaises(errors.BadIndexKey, builder.add_node, 'akey',

228

'data aa', ([], ['a bad key']))

229

230

def test_add_duplicate_key(self):

231

builder = GraphIndexBuilder()

232

builder.add_node('key', 'data')

233

self.assertRaises(errors.BadIndexDuplicateKey, builder.add_node, 'key',

234

'data')

235

236

def test_add_key_after_referencing_key(self):

237

builder = GraphIndexBuilder(reference_lists=1)

238

builder.add_node('key', 'data', (['reference'], ))

239

builder.add_node('reference', 'data', ([],))

240

241

242

class TestGraphIndex(TestCaseWithMemoryTransport):

243

244

def make_index(self, ref_lists=0, nodes=[]):

245

builder = GraphIndexBuilder(ref_lists)

246

for node, value, references in nodes:

247

builder.add_node(node, value, references)

248

stream = builder.finish()

249

trans = self.get_transport()

250

trans.put_file('index', stream)

251

return GraphIndex(trans, 'index')

252

253

def test_open_bad_index_no_error(self):

254

trans = self.get_transport()

255

trans.put_bytes('name', "not an index\n")

256

index = GraphIndex(trans, 'name')

257

258

def test_iter_all_entries_empty(self):

259

index = self.make_index()

260

self.assertEqual([], list(index.iter_all_entries()))

261

262

def test_iter_all_entries_simple(self):

263

index = self.make_index(nodes=[('name', 'data', ())])

264

self.assertEqual([('name', 'data')],

265

list(index.iter_all_entries()))

266

267

def test_iter_all_entries_references_resolved(self):

268

index = self.make_index(1, nodes=[

269

('name', 'data', (['ref'], )),

270

('ref', 'refdata', ([], ))])

271

self.assertEqual(set([('name', 'data', (('ref',),)),

272

('ref', 'refdata', ((), ))]),

273

set(index.iter_all_entries()))

274

275

def test_iteration_absent_skipped(self):

276

index = self.make_index(1, nodes=[

277

('name', 'data', (['ref'], ))])

278

self.assertEqual(set([('name', 'data', (('ref',),))]),

279

set(index.iter_all_entries()))

280

self.assertEqual(set([('name', 'data', (('ref',),))]),

281

set(index.iter_entries(['name'])))

282

self.assertEqual([], list(index.iter_entries(['ref'])))

283

284

def test_iter_all_keys(self):

285

index = self.make_index(1, nodes=[

286

('name', 'data', (['ref'], )),

287

('ref', 'refdata', ([], ))])

288

self.assertEqual(set([('name', 'data', (('ref',),)),

289

('ref', 'refdata', ((), ))]),

290

set(index.iter_entries(['name', 'ref'])))

291

292

def test_iter_nothing_empty(self):

293

index = self.make_index()

294

self.assertEqual([], list(index.iter_entries([])))

295

296

def test_iter_missing_entry_empty(self):

297

index = self.make_index()

298

self.assertEqual([], list(index.iter_entries(['a'])))

299

300

def test_validate_bad_index_errors(self):

301

trans = self.get_transport()

302

trans.put_bytes('name', "not an index\n")

303

index = GraphIndex(trans, 'name')

304

self.assertRaises(errors.BadIndexFormatSignature, index.validate)

305

306

def test_validate_bad_node_refs(self):

307

index = self.make_index(2)

308

trans = self.get_transport()

309

content = trans.get_bytes('index')

310

# change the options line to end with a rather than a parseable number

311

new_content = content[:-2] + 'a\n\n'

312

trans.put_bytes('index', new_content)

313

self.assertRaises(errors.BadIndexOptions, index.validate)

314

315

def test_validate_missing_end_line_empty(self):

316

index = self.make_index(2)

317

trans = self.get_transport()

318

content = trans.get_bytes('index')

319

# truncate the last byte

320

trans.put_bytes('index', content[:-1])

321

self.assertRaises(errors.BadIndexData, index.validate)

322

323

def test_validate_missing_end_line_nonempty(self):

324

index = self.make_index(2, [('key', '', ([], []))])

325

trans = self.get_transport()

326

content = trans.get_bytes('index')

327

# truncate the last byte

328

trans.put_bytes('index', content[:-1])

329

self.assertRaises(errors.BadIndexData, index.validate)

330

331

def test_validate_empty(self):

332

index = self.make_index()

333

index.validate()

334

335

def test_validate_no_refs_content(self):

336

index = self.make_index(nodes=[('key', 'value', ())])

337

index.validate()

338

339

340

class TestCombinedGraphIndex(TestCaseWithMemoryTransport):

341

342

def make_index(self, name, ref_lists=0, nodes=[]):

343

builder = GraphIndexBuilder(ref_lists)

344

for node, value, references in nodes:

345

builder.add_node(node, value, references)

346

stream = builder.finish()

347

trans = self.get_transport()

348

trans.put_file(name, stream)

349

return GraphIndex(trans, name)

350

351

def test_open_missing_index_no_error(self):

352

trans = self.get_transport()

353

index1 = GraphIndex(trans, 'missing')

354

index = CombinedGraphIndex([index1])

355

356

def test_add_index(self):

357

index = CombinedGraphIndex([])

358

index1 = self.make_index('name', 0, nodes=[('key', '', ())])

359

index.insert_index(0, index1)

360

self.assertEqual([('key', '')], list(index.iter_all_entries()))

361

362

def test_iter_all_entries_empty(self):

363

index = CombinedGraphIndex([])

364

self.assertEqual([], list(index.iter_all_entries()))

365

366

def test_iter_all_entries_children_empty(self):

367

index1 = self.make_index('name')

368

index = CombinedGraphIndex([index1])

369

self.assertEqual([], list(index.iter_all_entries()))

370

371

def test_iter_all_entries_simple(self):

372

index1 = self.make_index('name', nodes=[('name', 'data', ())])

373

index = CombinedGraphIndex([index1])

374

self.assertEqual([('name', 'data')],

375

list(index.iter_all_entries()))

376

377

def test_iter_all_entries_two_indices(self):

378

index1 = self.make_index('name1', nodes=[('name', 'data', ())])

379

index2 = self.make_index('name2', nodes=[('2', '', ())])

380

index = CombinedGraphIndex([index1, index2])

381

self.assertEqual([('name', 'data'),

382

('2', '')],

383

list(index.iter_all_entries()))

384

385

def test_iter_entries_two_indices_dup_key(self):

386

index1 = self.make_index('name1', nodes=[('name', 'data', ())])

387

index2 = self.make_index('name2', nodes=[('name', 'data', ())])

388

index = CombinedGraphIndex([index1, index2])

389

self.assertEqual([('name', 'data')],

390

list(index.iter_entries(['name'])))

391

392

def test_iter_all_entries_two_indices_dup_key(self):

393

index1 = self.make_index('name1', nodes=[('name', 'data', ())])

394

index2 = self.make_index('name2', nodes=[('name', 'data', ())])

395

index = CombinedGraphIndex([index1, index2])

396

self.assertEqual([('name', 'data')],

397

list(index.iter_all_entries()))

398

399

def test_iter_nothing_empty(self):

400

index = CombinedGraphIndex([])

401

self.assertEqual([], list(index.iter_entries([])))

402

403

def test_iter_nothing_children_empty(self):

404

index1 = self.make_index('name')

405

index = CombinedGraphIndex([index1])

406

self.assertEqual([], list(index.iter_entries([])))

407

408

def test_iter_all_keys(self):

409

index1 = self.make_index('1', 1, nodes=[

410

('name', 'data', (['ref'], ))])

411

index2 = self.make_index('2', 1, nodes=[

412

('ref', 'refdata', ((), ))])

413

index = CombinedGraphIndex([index1, index2])

414

self.assertEqual(set([('name', 'data', (('ref', ), )),

415

('ref', 'refdata', ((), ))]),

416

set(index.iter_entries(['name', 'ref'])))

417

418

def test_iter_all_keys_dup_entry(self):

419

index1 = self.make_index('1', 1, nodes=[

420

('name', 'data', (['ref'], )),

421

('ref', 'refdata', ([], ))])

422

index2 = self.make_index('2', 1, nodes=[

423

('ref', 'refdata', ([], ))])

424

index = CombinedGraphIndex([index1, index2])

425

self.assertEqual(set([('name', 'data', (('ref',),)),

426

('ref', 'refdata', ((), ))]),

427

set(index.iter_entries(['name', 'ref'])))

428

429

def test_iter_missing_entry_empty(self):

430

index = CombinedGraphIndex([])

431

self.assertEqual([], list(index.iter_entries(['a'])))

432

433

def test_iter_missing_entry_one_index(self):

434

index1 = self.make_index('1')

435

index = CombinedGraphIndex([index1])

436

self.assertEqual([], list(index.iter_entries(['a'])))

437

438

def test_iter_missing_entry_two_index(self):

439

index1 = self.make_index('1')

440

index2 = self.make_index('2')

441

index = CombinedGraphIndex([index1, index2])

442

self.assertEqual([], list(index.iter_entries(['a'])))

443

444

def test_iter_entry_present_one_index_only(self):

445

index1 = self.make_index('1', nodes=[('key', '', ())])

446

index2 = self.make_index('2', nodes=[])

447

index = CombinedGraphIndex([index1, index2])

448

self.assertEqual([('key', '')],

449

list(index.iter_entries(['key'])))

450

# and in the other direction

451

index = CombinedGraphIndex([index2, index1])

452

self.assertEqual([('key', '')],

453

list(index.iter_entries(['key'])))

454

455

def test_validate_bad_child_index_errors(self):

456

trans = self.get_transport()

457

trans.put_bytes('name', "not an index\n")

458

index1 = GraphIndex(trans, 'name')

459

index = CombinedGraphIndex([index1])

460

self.assertRaises(errors.BadIndexFormatSignature, index.validate)

461

462

def test_validate_empty(self):

463

index = CombinedGraphIndex([])

464

index.validate()

465

466

467

class TestInMemoryGraphIndex(TestCaseWithMemoryTransport):

468

469

def make_index(self, ref_lists=0, nodes=[]):

470

result = InMemoryGraphIndex(ref_lists)

471

result.add_nodes(nodes)

472

return result

473

474

def test_add_nodes(self):

475

index = self.make_index(1)

476

index.add_nodes([('name', 'data', ([],))])

477

index.add_nodes([('name2', '', ([],)), ('name3', '', (['r'],))])

478

self.assertEqual(set([

479

('name', 'data', ((),)),

480

('name2', '', ((),)),

481

('name3', '', (('r',),)),

482

]), set(index.iter_all_entries()))

483

484

def test_iter_all_entries_empty(self):

485

index = self.make_index()

486

self.assertEqual([], list(index.iter_all_entries()))

487

488

def test_iter_all_entries_simple(self):

489

index = self.make_index(nodes=[('name', 'data', ())])

490

self.assertEqual([('name', 'data')],

491

list(index.iter_all_entries()))

492

493

def test_iter_all_entries_references(self):

494

index = self.make_index(1, nodes=[

495

('name', 'data', (['ref'], )),

496

('ref', 'refdata', ([], ))])

497

self.assertEqual(set([('name', 'data', (('ref',),)),

498

('ref', 'refdata', ((), ))]),

499

set(index.iter_all_entries()))

500

501

def test_iteration_absent_skipped(self):

502

index = self.make_index(1, nodes=[

503

('name', 'data', (['ref'], ))])

504

self.assertEqual(set([('name', 'data', (('ref',),))]),

505

set(index.iter_all_entries()))

506

self.assertEqual(set([('name', 'data', (('ref',),))]),

507

set(index.iter_entries(['name'])))

508

self.assertEqual([], list(index.iter_entries(['ref'])))

509

510

def test_iter_all_keys(self):

511

index = self.make_index(1, nodes=[

512

('name', 'data', (['ref'], )),

513

('ref', 'refdata', ([], ))])

514

self.assertEqual(set([('name', 'data', (('ref',),)),

515

('ref', 'refdata', ((), ))]),

516

set(index.iter_entries(['name', 'ref'])))

517

518

def test_iter_nothing_empty(self):

519

index = self.make_index()

520

self.assertEqual([], list(index.iter_entries([])))

521

522

def test_iter_missing_entry_empty(self):

523

index = self.make_index()

524

self.assertEqual([], list(index.iter_entries(['a'])))

525

526

def test_validate_empty(self):

527

index = self.make_index()

528

index.validate()

529

530

def test_validate_no_refs_content(self):

531

index = self.make_index(nodes=[('key', 'value', ())])

532

index.validate()

533

534