/b-gtk/fix-viz : revision 298.2.2

1

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

2

"""Directed graph production.

3

4

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

5

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

6

window.

7

"""

8

9

10

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

11

12

13

from bzrlib.revision import Revision

14

from bzrlib.tsort import merge_sort

15

16

17

class DummyRevision(Revision):

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

def __init__(self, revid):

26

super(DummyRevision, self).__init__(revid)

27

self.committer = None

28

self.timestamp = None

29

self.timezone = None

30

self.message = revid

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

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

81

for revid in graph.ghosts:

82

self.cache_revision(DummyRevision(revid))

83

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

84

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

85

86

def cache_revision(self, revision):

87

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

88

revid = revision.revision_id

89

# Build a revision cache

90

self.revisions[revid] = revision

91

# Build a children dictionary

92

for parent_id in revision.parent_ids:

93

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

94

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

95

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

96

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

97

# fix the parent_ids list.

98

parent_ids = []

99

parent_ids_set = set()

100

for parent_id in revision.parent_ids:

101

if parent_id in parent_ids_set:

102

continue

103

parent_ids.append(parent_id)

104

parent_ids_set.add(parent_id)

105

revision.parent_ids = parent_ids

106

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

107

self.graph[revid] = revision.parent_ids

108

109

def make_children_map(self):

110

revisions = self.revisions

111

return dict((revisions[revid], c)

112

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

113

114

def sort_revisions(self, sorted_revids, maxnum):

115

revisions = self.revisions

116

parent_ids_of = self.parent_ids_of

117

children_of_id = self.children_of_id

118

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

119

distances = {}

120

skipped_revids = []

121

expected_id = sorted_revids[0]

122

pending_ids = []

123

while True:

124

revid = sorted_revids.pop(0)

125

if revid != expected_id:

126

skipped_revids.append(revid)

127

continue

128

revision = revisions[revid]

129

for child in children_of_id[revid]:

130

# postpone if any child is missing

131

if child.revision_id not in distances:

132

if expected_id not in pending_ids:

133

pending_ids.append(expected_id)

134

expected_id = pending_ids.pop(0)

135

skipped_revids.append(revid)

136

sorted_revids[:0] = skipped_revids

137

del skipped_revids[:]

138

break

139

else:

140

# all children are here, push!

141

distances[revid] = len(distances)

142

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

143

# bail out early if a limit was specified

144

sorted_revids[:0] = skipped_revids

145

for revid in sorted_revids:

146

distances[revid] = len(distances)

147

break

148

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

149

for parent in parent_ids_of[revision]:

150

if parent not in pending_ids:

151

pending_ids.insert(0, parent)

152

if not pending_ids:

153

break

154

expected_id = pending_ids.pop(0)

155

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

156

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

157

# skipped list.

158

if expected_id in skipped_revids:

159

pos = skipped_revids.index(expected_id)

160

sorted_revids[:0] = skipped_revids[pos:]

161

del skipped_revids[pos:]

162

self.distances = distances

163

return sorted(distances, key=distances.get)

164

165

def choose_colour(self, revid):

166

revision = self.revisions[revid]

167

children_of_id = self.children_of_id

168

parent_ids_of = self.parent_ids_of

169

colours = self.colours

170

# choose colour

171

the_children = children_of_id[revid]

172

if len(the_children) == 1:

173

[child] = the_children

174

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

175

# one-one relationship between parent and child, same

176

# colour

177

colours[revid] = colours[child.revision_id]

178

else:

179

self.choose_colour_one_child(revision, child)

180

else:

181

self.choose_colour_many_children(revision, the_children)

182

183

def choose_colour_one_child(self, revision, child):

184

revid = revision.revision_id

185

direct_parent_of = self.direct_parent_of

186

revisions = self.revisions

187

# one child with multiple parents, the first parent with

188

# the same committer gets the colour

189

direct_parent = direct_parent_of.get(child)

190

if direct_parent is None:

191

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

192

for parent_id in self.parent_ids_of[child]:

193

parent_revision = revisions[parent_id]

194

if parent_revision.committer == child.committer:

195

# found the first parent with the same committer

196

direct_parent = parent_revision

197

direct_parent_of[child] = direct_parent

198

break

199

if direct_parent == revision:

200

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

201

else:

202

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

203

204

def choose_colour_many_children(self, revision, the_children):

205

"""Colour revision revision."""

206

revid = revision.revision_id

207

direct_parent_of = self.direct_parent_of

208

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

209

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

210

# taken

211

available = {}

212

for child in the_children:

213

if child.committer != revision.committer:

214

continue

215

direct_parent = direct_parent_of.get(child)

216

if direct_parent == revision:

217

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

218

break

219

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

220

# knowledge of the revisions being output.

221

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

222

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

223

# if direct_parent is None:

224

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

225

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

226

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

227

else:

228

if available:

229

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

230

child = sorted_children[-1]

231

direct_parent_of[child] = revision

232

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

233

else:

234

# no candidate children is available, pick the next

235

# colour

236

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

237

238

239

def distances(branch, start):

240

"""Sort the revisions.

241

242

Traverses the branch revision tree starting at start and produces an

243

ordered list of revisions such that a revision always comes after

244

any revision it is the parent of.

245

246

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

247

"""

248

distance = DistanceMethod(branch, start)

249

distance.fill_caches()

250

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

251

children = distance.make_children_map()

252

253

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

254

distance.choose_colour(revid)

255

256

revisions = distance.revisions

257

colours = distance.colours

258

parent_ids_of = distance.parent_ids_of

259

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

260

261

262

def graph(revisions, colours, merge_sorted):

263

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

264

265

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

266

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

267

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

268

Revision object with the meta-data for the revision.

269

270

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

271

column number of the graph that this revision represents and colour

272

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

273

in particular) to draw the node in.

274

275

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

276

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

277

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

278

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

279

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

280

281

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

282

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

283

"""

284

if not len(merge_sorted):

285

return

286

# split merge_sorted into a map:

287

revs = {}

288

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

289

# calculating it ourselves

290

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

291

next_lower_rev = {}

292

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

293

# of branch

294

next_branch_revid = {}

295

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

296

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

297

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

298

current_stack = [[]]

299

for seq, revid, indent, end_merge in merge_sorted:

300

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

301

if indent == len(current_stack):

302

# new merge group starts

303

current_stack.append([revid])

304

elif indent == len(current_stack) - 1:

305

# part of the current merge group

306

current_stack[-1].append(revid)

307

else:

308

# end of a merge group

309

while current_stack[-1]:

310

stack_rev_id = current_stack[-1].pop()

311

# record the next lower rev for this rev:

312

next_lower_rev[stack_rev_id] = seq

313

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

314

if len(current_stack[-1]):

315

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

316

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

317

current_stack.pop()

318

# append to the now-current merge group

319

current_stack[-1].append(revid)

320

# assign a value to all the depth 0 revisions

321

while current_stack[-1]:

322

stack_rev_id = current_stack[-1].pop()

323

# record the next lower rev for this rev:

324

next_lower_rev[stack_rev_id] = len(merge_sorted)

325

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

326

if len(current_stack[-1]):

327

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

328

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

329

330

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

331

# the sequence of their lines on the screen.

332

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

333

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

334

hanging = [merge_sorted[0][1]]

335

for seq, revid, indent, end_merge in merge_sorted:

336

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

337

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

338

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

339

lines = []

340

341

new_hanging = []

342

343

for h_idx, hang in enumerate(hanging):

344

# one of these will be the current lines node:

345

# we are drawing a line. h_idx

346

if hang == revid:

347

# we have found the current lines node

348

node = (h_idx, colours[revid])

349

350

# note that we might have done the main parent

351

drawn_parents = set()

352

353

def draw_line(from_idx, to_idx, revision_id):

354

try:

355

n_idx = new_hanging.index(revision_id)

356

except ValueError:

357

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

358

# drawn.

359

new_hanging.insert(to_idx, revision_id)

360

n_idx = to_idx

361

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

362

363

364

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

365

if not end_merge:

366

# drop this line first.

367

parent_id = next_branch_revid[revid]

368

draw_line(h_idx, h_idx, parent_id)

369

# we have drawn this parent

370

drawn_parents.add(parent_id)

371

else:

372

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

373

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

374

# having > 1

375

# parents means this commit was a merge, and being

376

# the end point of a merge group means that all

377

# the parent revisions were merged into branches

378

# to the left of this before this was committed

379

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

380

# those revisions.

381

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

382

# sequence number, which is the one that this

383

# branch 'spawned from', and no others.

384

# If this sounds like a problem, remember that:

385

# if the parent was not already in our mainline

386

# it would show up as a merge into this making

387

# this not the end of a merge-line.

388

lowest = len(merge_sorted)

389

for parent_id in revisions[revid].parent_ids:

390

if revs[parent_id][0] < lowest:

391

lowest = revs[parent_id][0]

392

assert lowest != len(merge_sorted)

393

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

394

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

395

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

396

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

397

parent_id = revisions[revid].parent_ids[0]

398

draw_line(h_idx, len(new_hanging), parent_id)

399

drawn_parents.add(parent_id)

400

401

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

402

# each parent IF its relevant.

403

#

404

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

405

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

406

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

407

# hangs to keep the graph small.

408

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

409

# unless its the last revision in a merge group.

410

for parent_id in revisions[revid].parent_ids:

411

if parent_id in drawn_parents:

412

continue

413

parent_seq = revs[parent_id][0]

414

parent_depth = revs[parent_id][1]

415

if parent_depth == indent + 1:

416

# The parent was a merge into this branch determine if

417

# it was already merged into the mainline via a

418

# different merge: if all revisions between us and

419

# parent_seq have a indent greater than there are no

420

# revisions with a lower indent than us.

421

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

422

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

423

# merge_sorted should take care of that for us (but

424

# does not trim the values)

425

if parent_seq < next_lower_rev[revid]:

426

draw_line(h_idx, len(new_hanging), parent_id)

427

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

428

# part of this branch

429

draw_line(h_idx, len(new_hanging), parent_id)

430

else:

431

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

432

# new position.

433

# h_idx is the old position.

434

# new_indent is the new position.

435

draw_line(h_idx, len(new_hanging), hang)

436

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

437

# the next row

438

hanging = new_hanging

439

440

yield (revisions[revid], node, lines)

441

442

443

def same_branch(a, b):

444

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

445

if len(a.parent_ids) == 1:

446

# Defacto same branch if only parent

447

return True

448

elif a.committer == b.committer:

449

# Same committer so may as well be

450

return True

451

else:

452

return False

1

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

2

"""Directed graph production.

3

4

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

5

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

6

window.

7

"""

8

9

10

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

11

12

from bzrlib.tsort import merge_sort

13

14

def linegraph(branch, start, maxnum):

15

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

16

17

Returns a tuple of (line_graph, revid_index, columns_len) where

18

* line_graph is a list of tuples of (revid,

19

node,

20

lines,

21

parents,

22

children,

23

revno_sequence),

24

* revid_index is a dict of each revision with the key being the revid, and

25

the value the row index, and

26

* columns_len is the number of columns need to draw the line graph.

27

28

29

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

30

column number of the graph that this revision represents and colour

31

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

32

in particular) to draw the node in.

33

34

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

35

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

36

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

37

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

38

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

39

40

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

41

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

42

"""

43

44

# FIXME: This should be configurable

45

BROKEN_LINE_LENGTH = 32

46

47

# We get the mainline so we can pass it to merge_sort to make merge_sort

48

# run faster.

49

mainline = [None]

50

mainline.extend(branch.revision_history())

51

graph_parents = branch.repository.get_revision_graph(start)

52

graph_children = {}

53

for revid in graph_parents.iterkeys():

54

graph_children[revid] = []

55

56

merge_sorted_revisions = merge_sort(

57

graph_parents,

58

start,

59

mainline,

60

generate_revno=True)

61

62

revid_index = {}

63

revno_index = {}

64

65

# This will hold an item for each "branch". For a revisions, the revsion

66

# number less the least significant digit is the branch_id, and used as the

67

# key for the dict. Hence revision with the same revsion number less the

68

# least significant digit are considered to be in the same branch line.

69

# e.g.: for revisions 290.12.1 and 290.12.2, the branch_id would be 290.12,

70

# and these two revisions will be in the same branch line. Each value is

71

# a list of rev_indexes in the branch.

72

branch_lines = {}

73

74

linegraph = []

75

76

for (rev_index, (sequence_number,

77

revid,

78

merge_depth,

79

revno_sequence,

80

end_of_merge)) in enumerate(merge_sorted_revisions):

81

if maxnum and rev_index >= maxnum:

82

break

83

revid_index[revid] = rev_index

84

revno_index[revno_sequence] = rev_index

85

86

branch_id = revno_sequence[0:-1]

87

88

branch_line = None

89

if branch_id not in branch_lines:

90

branch_line = []

91

branch_lines[branch_id] = branch_line

92

else:

93

branch_line = branch_lines[branch_id]

94

95

branch_line.append(rev_index)

96

97

parents = graph_parents[revid]

98

for parent_revid in parents:

99

graph_children[parent_revid].append(revid)

100

101

linegraph.append([revid,

102

None,

103

[],

104

parents,

105

None,

106

revno_sequence])

107

108

branch_ids = branch_lines.keys()

109

110

def branch_id_cmp(x, y):

111

"""Compaire branch_id's first by the number of digits, then reversed

112

by their value"""

113

len_x = len(x)

114

len_y = len(y)

115

if len_x == len_y:

116

return -cmp(x, y)

117

return cmp(len_x, len_y)

118

119

branch_ids.sort(branch_id_cmp)

120

# This will hold a tuple of (child_index, parent_index, col_index) for each

121

# line that needs to be drawn. If col_index is not none, then the line is

122

# drawn along that column, else the the line can be drawn directly between

123

# the child and parent because either the child and parent are in the same

124

# branch line, or the child and parent are 1 row apart.

125

lines = []

126

empty_column = [False for i in range(len(graph_parents))]

127

# This will hold a bit map for each cell. If the cell is true, then the

128

# cell allready contains a node or line. This use when deciding what column

129

# to place a branch line or line in, without it overlaping something else.

130

columns = [list(empty_column)]

131

132

133

for branch_id in branch_ids:

134

branch_line = branch_lines[branch_id]

135

136

# Find the col_index for the direct parent branch. This will be the

137

# starting point when looking for a free column.

138

parent_col_index = 0

139

parent_index = None

140

if len(branch_id) > 1:

141

parent_revno = branch_id[0:-1]

142

if parent_revno in revno_index:

143

parent_index = revno_index[parent_revno]

144

parent_node = linegraph[parent_index][1]

145

if parent_node:

146

parent_col_index = parent_node[0]

147

148

149

col_search_order = _branch_line_col_search_order(columns,

150

parent_col_index)

151

color = reduce(lambda x, y: x+y, branch_id, 0)

152

cur_cont_line = []

153

154

line_range = []

155

last_rev_index = None

156

for rev_index in branch_line:

157

if last_rev_index:

158

if BROKEN_LINE_LENGTH and \

159

rev_index - last_rev_index > BROKEN_LINE_LENGTH:

160

line_range.append(last_rev_index+1)

161

line_range.append(rev_index-1)

162

else:

163

line_range.extend(range(last_rev_index+1, rev_index))

164

165

line_range.append(rev_index)

166

last_rev_index = rev_index

167

168

if parent_index:

169

if BROKEN_LINE_LENGTH and \

170

parent_index - last_rev_index > BROKEN_LINE_LENGTH:

171

line_range.append(last_rev_index+1)

172

else:

173

line_range.extend(range(last_rev_index+1, parent_index))

174

175

col_index = _find_free_column(columns,

176

empty_column,

177

col_search_order,

178

line_range)

179

node = (col_index, color)

180

for rev_index in branch_line:

181

linegraph[rev_index][1] = node

182

columns[col_index][rev_index] = True

183

184

for rev_index in branch_line:

185

(sequence_number,

186

revid,

187

merge_depth,

188

revno_sequence,

189

end_of_merge) = merge_sorted_revisions[rev_index]

190

191

linegraph[rev_index][4] = graph_children[revid]

192

col_index = linegraph[rev_index][1][0]

193

194

for parent_revid in graph_parents[revid]:

195

if parent_revid in revid_index:

196

197

parent_index = revid_index[parent_revid]

198

parent_node = linegraph[parent_index][1]

199

if parent_node:

200

parent_col_index = parent_node[0]

201

else:

202

parent_col_index = None

203

col_search_order = \

204

_line_col_search_order(columns,

205

parent_col_index,

206

col_index)

207

208

# If this line is really long, break it.

209

if len(branch_id) > 0 and \

210

BROKEN_LINE_LENGTH and \

211

parent_index - rev_index > BROKEN_LINE_LENGTH:

212

child_line_col_index = \

213

_find_free_column(columns,

214

empty_column,

215

col_search_order,

216

(rev_index + 1,))

217

_mark_column_as_used(columns,

218

child_line_col_index,

219

(rev_index + 1,))

220

221

# Recall _line_col_search_order to reset it back to

222

# the beging.

223

col_search_order = \

224

_line_col_search_order(columns,

225

parent_col_index,

226

col_index)

227

parent_col_line_index = \

228

_find_free_column(columns,

229

empty_column,

230

col_search_order,

231

(parent_index - 1,))

232

_mark_column_as_used(columns,

233

parent_col_line_index,

234

(parent_index - 1,))

235

lines.append((rev_index,

236

parent_index,

237

(child_line_col_index,

238

parent_col_line_index)))

239

else :

240

line_col_index = col_index

241

if parent_index - rev_index >1:

242

line_range = range(rev_index + 1, parent_index)

243

line_col_index = \

244

_find_free_column(columns,

245

empty_column,

246

col_search_order,

247

line_range)

248

_mark_column_as_used(columns,

249

line_col_index,

250

line_range)

251

lines.append((rev_index,

252

parent_index,

253

(line_col_index,)))

254

255

for (child_index, parent_index, line_col_indexes) in lines:

256

(child_col_index, child_color) = linegraph[child_index][1]

257

(parent_col_index, parent_color) = linegraph[parent_index][1]

258

259

if len(line_col_indexes) == 1:

260

if parent_index - child_index == 1:

261

linegraph[child_index][2].append(

262

(child_col_index,

263

parent_col_index,

264

parent_color))

265

else:

266

# line from the child's column to the lines column

267

linegraph[child_index][2].append(

268

(child_col_index,

269

line_col_indexes[0],

270

parent_color))

271

# lines down the line's column

272

for line_part_index in range(child_index+1, parent_index-1):

273

linegraph[line_part_index][2].append(

274

(line_col_indexes[0],

275

line_col_indexes[0],

276

parent_color))

277

# line from the line's column to the parent's column

278

linegraph[parent_index-1][2].append(

279

(line_col_indexes[0],

280

parent_col_index,

281

parent_color))

282

else:

283

# Broken line

284

# line from the child's column to the lines column

285

linegraph[child_index][2].append(

286

(child_col_index,

287

line_col_indexes[0],

288

parent_color))

289

# Broken line end

290

linegraph[child_index+1][2].append(

291

(line_col_indexes[0],

292

None,

293

parent_color))

294

295

# Broken line end

296

linegraph[parent_index-2][2].append(

297

(None,

298

line_col_indexes[1],

299

parent_color))

300

# line from the line's column to the parent's column

301

linegraph[parent_index-1][2].append(

302

(line_col_indexes[1],

303

parent_col_index,

304

parent_color))

305

306

307

return (linegraph, revid_index, len(columns))

308

309

def _branch_line_col_search_order(columns, parent_col_index):

310

for col_index in range(parent_col_index, len(columns)):

311

yield col_index

312

for col_index in range(parent_col_index-1, -1, -1):

313

yield col_index

314

315

def _line_col_search_order(columns, parent_col_index, child_col_index):

316

if parent_col_index is not None:

317

max_index = max(parent_col_index, child_col_index)

318

min_index = min(parent_col_index, child_col_index)

319

for col_index in range(max_index, min_index -1, -1):

320

yield col_index

321

else:

322

max_index = child_col_index

323

min_index = child_col_index

324

yield child_col_index

325

i = 1

326

while max_index + i < len(columns) or \

327

min_index - i > -1:

328

if max_index + i < len(columns):

329

yield max_index + i

330

if min_index - i > -1:

331

yield min_index - i

332

i += 1

333

334

def _find_free_column(columns, empty_column, col_search_order, line_range):

335

for col_index in col_search_order:

336

column = columns[col_index]

337

has_overlaping_line = False

338

for row_index in line_range:

339

if column[row_index]:

340

has_overlaping_line = True

341

break

342

if not has_overlaping_line:

343

break

344

else:

345

col_index = len(columns)

346

column = list(empty_column)

347

columns.append(column)

348

return col_index

349

350

def _mark_column_as_used(columns, col_index, line_range):

351

column = columns[col_index]

352

for row_index in line_range:

353

column[row_index] = True

354

355

def same_branch(a, b):

356

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

357

if len(a.parent_ids) == 1:

358

# Defacto same branch if only parent

359

return True

360

elif a.committer == b.committer:

361

# Same committer so may as well be

362

return True

363

else:

364

return False