/b-gtk/fix-viz : revision 0.1.25

1

#!/usr/bin/python

2

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

3

"""Directed graph production.

4

5

This module contains the code to produce an ordered directed graph of a

6

bzr branch, such as we display in the tree view at the top of the bzrk

7

window.

8

"""

9

10

11

__author__ = "Scott James Remnant <scott@ubuntu.com>"

12

13

14

from bzrlib.tsort import merge_sort

15

16

17

class DummyRevision(object):

18

"""Dummy bzr revision.

19

20

Sometimes, especially in older bzr branches, a revision is referenced

21

as the parent of another but not actually present in the branch's store.

22

When this happens we use an instance of this class instead of the real

23

Revision object (which we can't get).

24

"""

25

26

def __init__(self, revid):

27

self.revision_id = revid

28

self.parent_ids = []

29

self.committer = None

30

self.message = self.revision_id

31

32

33

class RevisionProxy(object):

34

"""A revision proxy object.

35

36

This will demand load the revision it represents when the committer or

37

message attributes are accessed in order to populate them. It is

38

constructed with the revision id and parent_ids list and a repository

39

object to request the revision from when needed.

40

"""

41

42

def __init__(self, revid, parent_ids, repository):

43

self.revision_id = revid

44

self.parent_ids = parent_ids

45

self._repository = repository

46

self._revision = None

47

48

def _get_attribute_getter(attr):

49

def get_attribute(self):

50

if self._revision is None:

51

self._load()

52

return getattr(self._revision, attr)

53

return get_attribute

54

committer = property(_get_attribute_getter('committer'))

55

message = property(_get_attribute_getter('message'))

56

properties = property(_get_attribute_getter('properties'))

57

timestamp = property(_get_attribute_getter('timestamp'))

58

timezone = property(_get_attribute_getter('timezone'))

59

60

def _load(self):

61

"""Load the revision object."""

62

self._revision = self._repository.get_revision(self.revision_id)

63

64

65

class DistanceMethod(object):

66

67

def __init__(self, branch, start):

68

self.branch = branch

69

self.start = start

70

self.revisions = {}

71

self.children = {}

72

self.children_of_id = {start: set()}

73

self.parent_ids_of = {}

74

self.colours = { start: 0 }

75

self.last_colour = 0

76

self.direct_parent_of = {}

77

self.graph = {}

78

79

def fill_caches(self):

80

# FIXME: look at using repository.get_revision_graph_with_ghosts - RBC.

81

graph = self.branch.repository.get_revision_graph_with_ghosts([self.start])

82

for revid in graph.ghosts:

83

self.cache_revision(DummyRevision(revid))

84

for revid, parents in graph.get_ancestors().items():

85

self.cache_revision(RevisionProxy(revid, parents, self.branch.repository))

86

87

def cache_revision(self, revision):

88

"Set the caches for a newly retrieved revision."""

89

revid = revision.revision_id

90

# Build a revision cache

91

self.revisions[revid] = revision

92

# Build a children dictionary

93

for parent_id in revision.parent_ids:

94

self.children_of_id.setdefault(parent_id, set()).add(revision)

95

# Build a parents dictionnary, where redundant parents will be removed,

96

# and that will be passed along tothe rest of program.

97

if len(revision.parent_ids) != len(set(revision.parent_ids)):

98

# fix the parent_ids list.

99

parent_ids = []

100

parent_ids_set = set()

101

for parent_id in revision.parent_ids:

102

if parent_id in parent_ids_set:

103

continue

104

parent_ids.append(parent_id)

105

parent_ids_set.add(parent_id)

106

revision.parent_ids = parent_ids

107

self.parent_ids_of[revision] = list(revision.parent_ids)

108

self.graph[revid] = revision.parent_ids

109

110

def make_children_map(self):

111

revisions = self.revisions

112

return dict((revisions[revid], c)

113

for (revid, c) in self.children_of_id.iteritems())

114

115

def sort_revisions(self, sorted_revids, maxnum):

116

revisions = self.revisions

117

parent_ids_of = self.parent_ids_of

118

children_of_id = self.children_of_id

119

# Try to compact sequences of revisions on the same branch.

120

distances = {}

121

skipped_revids = []

122

expected_id = sorted_revids[0]

123

pending_ids = []

124

while True:

125

revid = sorted_revids.pop(0)

126

if revid != expected_id:

127

skipped_revids.append(revid)

128

continue

129

revision = revisions[revid]

130

for child in children_of_id[revid]:

131

# postpone if any child is missing

132

if child.revision_id not in distances:

133

if expected_id not in pending_ids:

134

pending_ids.append(expected_id)

135

expected_id = pending_ids.pop(0)

136

skipped_revids.append(revid)

137

sorted_revids[:0] = skipped_revids

138

del skipped_revids[:]

139

break

140

else:

141

# all children are here, push!

142

distances[revid] = len(distances)

143

if maxnum is not None and len(distances) > maxnum:

144

# bail out early if a limit was specified

145

sorted_revids[:0] = skipped_revids

146

for revid in sorted_revids:

147

distances[revid] = len(distances)

148

break

149

# all parents will need to be pushed as soon as possible

150

for parent in parent_ids_of[revision]:

151

if parent not in pending_ids:

152

pending_ids.insert(0, parent)

153

if not pending_ids:

154

break

155

expected_id = pending_ids.pop(0)

156

# if the next expected revid has already been skipped, requeue

157

# the skipped ids, except those that would go right back to the

158

# skipped list.

159

if expected_id in skipped_revids:

160

pos = skipped_revids.index(expected_id)

161

sorted_revids[:0] = skipped_revids[pos:]

162

del skipped_revids[pos:]

163

self.distances = distances

164

return sorted(distances, key=distances.get)

165

166

def choose_colour(self, revid):

167

revision = self.revisions[revid]

168

children_of_id = self.children_of_id

169

parent_ids_of = self.parent_ids_of

170

colours = self.colours

171

# choose colour

172

the_children = children_of_id[revid]

173

if len(the_children) == 1:

174

[child] = the_children

175

if len(parent_ids_of[child]) == 1:

176

# one-one relationship between parent and child, same

177

# colour

178

colours[revid] = colours[child.revision_id]

179

else:

180

self.choose_colour_one_child(revision, child)

181

else:

182

self.choose_colour_many_children(revision, the_children)

183

184

def choose_colour_one_child(self, revision, child):

185

revid = revision.revision_id

186

direct_parent_of = self.direct_parent_of

187

revisions = self.revisions

188

# one child with multiple parents, the first parent with

189

# the same committer gets the colour

190

direct_parent = direct_parent_of.get(child)

191

if direct_parent is None:

192

# if it has not been found yet, find it now and remember

193

for parent_id in self.parent_ids_of[child]:

194

parent_revision = revisions[parent_id]

195

if parent_revision.committer == child.committer:

196

# found the first parent with the same committer

197

direct_parent = parent_revision

198

direct_parent_of[child] = direct_parent

199

break

200

if direct_parent == revision:

201

self.colours[revid] = self.colours[child.revision_id]

202

else:

203

self.colours[revid] = self.last_colour = self.last_colour + 1

204

205

def choose_colour_many_children(self, revision, the_children):

206

"""Colour revision revision."""

207

revid = revision.revision_id

208

direct_parent_of = self.direct_parent_of

209

# multiple children, get the colour of the last displayed child

210

# with the same committer which does not already have its colour

211

# taken

212

available = {}

213

for child in the_children:

214

if child.committer != revision.committer:

215

continue

216

direct_parent = direct_parent_of.get(child)

217

if direct_parent == revision:

218

self.colours[revid] = self.colours[child.revision_id]

219

break

220

# FIXME: Colouring based on whats been displayed MUST be done with

221

# knowledge of the revisions being output.

222

# until the refactoring to fold graph() into this more compactly is

223

# done, I've disabled this reuse. RBC 20060403

224

# if direct_parent is None:

225

# available[child] = distances[child.revision_id]

226

# .. it will be something like available[child] = \

227

# revs[child.revision_id][0] - which is the sequence number

228

else:

229

if available:

230

sorted_children = sorted(available, key=available.get)

231

child = sorted_children[-1]

232

direct_parent_of[child] = revision

233

self.colours[revid] = self.colours[child.revision_id]

234

else:

235

# no candidate children is available, pick the next

236

# colour

237

self.colours[revid] = self.last_colour = self.last_colour + 1

238

239

240

def distances(branch, start):

241

"""Sort the revisions.

242

243

Traverses the branch revision tree starting at start and produces an

244

ordered list of revisions such that a revision always comes after

245

any revision it is the parent of.

246

247

Returns a tuple of (revids, revisions, colours, children)

248

"""

249

distance = DistanceMethod(branch, start)

250

distance.fill_caches()

251

distance.merge_sorted = merge_sort(distance.graph, distance.start)

252

children = distance.make_children_map()

253

254

for seq, revid, merge_depth, end_of_merge in distance.merge_sorted:

255

distance.choose_colour(revid)

256

257

revisions = distance.revisions

258

colours = distance.colours

259

parent_ids_of = distance.parent_ids_of

260

return (revisions, colours, children, parent_ids_of, distance.merge_sorted)

261

262

263

def graph(revisions, colours, merge_sorted):

264

"""Produce a directed graph of a bzr branch.

265

266

For each revision it then yields a tuple of (revision, node, lines).

267

If the revision is only referenced in the branch and not present in the

268

store, revision will be a DummyRevision object, otherwise it is the bzr

269

Revision object with the meta-data for the revision.

270

271

Node is a tuple of (column, colour) with column being a zero-indexed

272

column number of the graph that this revision represents and colour

273

being a zero-indexed colour (which doesn't specify any actual colour

274

in particular) to draw the node in.

275

276

Lines is a list of tuples which represent lines you should draw away

277

from the revision, if you also need to draw lines into the revision

278

you should use the lines list from the previous iteration. Each

279

typle in the list is in the form (start, end, colour) with start and

280

end being zero-indexed column numbers and colour as in node.

281

282

It's up to you how to actually draw the nodes and lines (straight,

283

curved, kinked, etc.) and to pick the actual colours for each index.

284

"""

285

if not len(merge_sorted):

286

return

287

# split merge_sorted into a map:

288

revs = {}

289

# FIXME: get a hint on this from the merge_sorted data rather than

290

# calculating it ourselves

291

# mapping from rev_id to the sequence number of the next lowest rev

292

next_lower_rev = {}

293

# mapping from rev_id to next-in-branch-revid - may be None for end

294

# of branch

295

next_branch_revid = {}

296

# the stack we are in in the sorted data for determining which

297

# next_lower_rev to set. It is a stack which has one list at each

298

# depth - the ids at that depth that need the same id allocated.

299

current_stack = [[]]

300

for seq, revid, indent, end_merge in merge_sorted:

301

revs[revid] = (seq, indent, end_merge)

302

if indent == len(current_stack):

303

# new merge group starts

304

current_stack.append([revid])

305

elif indent == len(current_stack) - 1:

306

# part of the current merge group

307

current_stack[-1].append(revid)

308

else:

309

# end of a merge group

310

while current_stack[-1]:

311

stack_rev_id = current_stack[-1].pop()

312

# record the next lower rev for this rev:

313

next_lower_rev[stack_rev_id] = seq

314

# if this followed a non-end-merge rev in this group note that

315

if len(current_stack[-1]):

316

if not revs[current_stack[-1][-1]][2]:

317

next_branch_revid[current_stack[-1][-1]] = stack_rev_id

318

current_stack.pop()

319

# append to the now-current merge group

320

current_stack[-1].append(revid)

321

# assign a value to all the depth 0 revisions

322

while current_stack[-1]:

323

stack_rev_id = current_stack[-1].pop()

324

# record the next lower rev for this rev:

325

next_lower_rev[stack_rev_id] = len(merge_sorted)

326

# if this followed a non-end-merge rev in this group note that

327

if len(current_stack[-1]):

328

if not revs[current_stack[-1][-1]][2]:

329

next_branch_revid[current_stack[-1][-1]] = stack_rev_id

330

331

# a list of the current revisions we are drawing lines TO indicating

332

# the sequence of their lines on the screen.

333

# i.e. [A, B, C] means that the line to A, to B, and to C are in

334

# (respectively), 0, 1, 2 on the screen.

335

hanging = [merge_sorted[0][1]]

336

for seq, revid, indent, end_merge in merge_sorted:

337

# a list of the lines to draw: their position in the

338

# previous row, their position in this row, and the colour

339

# (which is the colour they are routing to).

340

lines = []

341

342

new_hanging = []

343

344

for h_idx, hang in enumerate(hanging):

345

# one of these will be the current lines node:

346

# we are drawing a line. h_idx

347

if hang == revid:

348

# we have found the current lines node

349

node = (h_idx, colours[revid])

350

351

# note that we might have done the main parent

352

drawn_parents = set()

353

354

def draw_line(from_idx, to_idx, revision_id):

355

try:

356

n_idx = new_hanging.index(revision_id)

357

except ValueError:

358

# force this to be vertical at the place this rev was

359

# drawn.

360

new_hanging.insert(to_idx, revision_id)

361

n_idx = to_idx

362

lines.append((from_idx, n_idx, colours[revision_id]))

363

364

365

# we want to draw a line to the next commit on 'this' branch

366

if not end_merge:

367

# drop this line first.

368

parent_id = next_branch_revid[revid]

369

draw_line(h_idx, h_idx, parent_id)

370

# we have drawn this parent

371

drawn_parents.add(parent_id)

372

else:

373

# this is the last revision in a 'merge', show where it came from

374

if len(revisions[revid].parent_ids) > 1:

375

# having > 1

376

# parents means this commit was a merge, and being

377

# the end point of a merge group means that all

378

# the parent revisions were merged into branches

379

# to the left of this before this was committed

380

# - so we want to show this as a new branch from

381

# those revisions.

382

# to do this, we show the parent with the lowest

383

# sequence number, which is the one that this

384

# branch 'spawned from', and no others.

385

# If this sounds like a problem, remember that:

386

# if the parent was not already in our mainline

387

# it would show up as a merge into this making

388

# this not the end of a merge-line.

389

lowest = len(merge_sorted)

390

for parent_id in revisions[revid].parent_ids:

391

if revs[parent_id][0] < lowest:

392

lowest = revs[parent_id][0]

393

assert lowest != len(merge_sorted)

394

draw_line(h_idx, len(new_hanging), merge_sorted[lowest][1])

395

drawn_parents.add(merge_sorted[lowest][1])

396

elif len(revisions[revid].parent_ids) == 1:

397

# only one parent, must show this link to be useful.

398

parent_id = revisions[revid].parent_ids[0]

399

draw_line(h_idx, len(new_hanging), parent_id)

400

drawn_parents.add(parent_id)

401

402

# what do we want to draw lines to from here:

403

# each parent IF its relevant.

404

#

405

# Now we need to hang its parents, we put them at the point

406

# the old column was so anything to the right of this has

407

# to move outwards to make room. We also try and collapse

408

# hangs to keep the graph small.

409

# RBC: we do not draw lines to parents that were already merged

410

# unless its the last revision in a merge group.

411

for parent_id in revisions[revid].parent_ids:

412

if parent_id in drawn_parents:

413

continue

414

parent_seq = revs[parent_id][0]

415

parent_depth = revs[parent_id][1]

416

if parent_depth == indent + 1:

417

# The parent was a merge into this branch determine if

418

# it was already merged into the mainline via a

419

# different merge: if all revisions between us and

420

# parent_seq have a indent greater than there are no

421

# revisions with a lower indent than us.

422

# We do not use 'parent_depth < indent' because that

423

# would allow un-uniqueified merges to show up, and

424

# merge_sorted should take care of that for us (but

425

# does not trim the values)

426

if parent_seq < next_lower_rev[revid]:

427

draw_line(h_idx, len(new_hanging), parent_id)

428

elif parent_depth == indent and parent_seq == seq + 1:

429

# part of this branch

430

draw_line(h_idx, len(new_hanging), parent_id)

431

else:

432

# draw a line from the previous position of this line to the

433

# new position.

434

# h_idx is the old position.

435

# new_indent is the new position.

436

draw_line(h_idx, len(new_hanging), hang)

437

# we've calculated the row, assign new_hanging to hanging to setup for

438

# the next row

439

hanging = new_hanging

440

441

yield (revisions[revid], node, lines)

442

443

444

def same_branch(a, b):

445

"""Return whether we think revisions a and b are on the same branch."""

446

if len(a.parent_ids) == 1:

447

# Defacto same branch if only parent

448

return True

449

elif a.committer == b.committer:

450

# Same committer so may as well be

451

return True

452

else:

453

return False