/b-gtk/fix-viz : revision 278.1.7

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, repository, start_revid):

68

self.repository = repository

69

self.start_revid = start_revid

70

self.revisions = {}

71

self.children_of_id = {start_revid: set()}

72

self.parent_ids_of = {}

73

self.colours = { start_revid: 0 }

74

self.last_colour = 0

75

self.direct_parent_of = {}

76

self.graph = {}

77

78

def fill_caches(self):

79

graph = self.repository.get_revision_graph_with_ghosts([self.start_revid])

80

for revid in graph.ghosts:

81

self.cache_revision(DummyRevision(revid))

82

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

83

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

84

85

def cache_revision(self, revision):

86

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

87

revid = revision.revision_id

88

# Build a revision cache

89

self.revisions[revid] = revision

90

# Build a children dictionary

91

for parent_id in revision.parent_ids:

92

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

93

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

94

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

95

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

96

# fix the parent_ids list.

97

parent_ids = []

98

parent_ids_set = set()

99

for parent_id in revision.parent_ids:

100

if parent_id in parent_ids_set:

101

continue

102

parent_ids.append(parent_id)

103

parent_ids_set.add(parent_id)

104

revision.parent_ids = parent_ids

105

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

106

self.graph[revid] = revision.parent_ids

107

108

def make_children_map(self):

109

revisions = self.revisions

110

return dict((revisions[revid], c)

111

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

112

113

def sort_revisions(self, sorted_revids, maxnum):

114

revisions = self.revisions

115

parent_ids_of = self.parent_ids_of

116

children_of_id = self.children_of_id

117

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

118

distances = {}

119

skipped_revids = []

120

expected_id = sorted_revids[0]

121

pending_ids = []

122

while True:

123

revid = sorted_revids.pop(0)

124

if revid != expected_id:

125

skipped_revids.append(revid)

126

continue

127

revision = revisions[revid]

128

for child in children_of_id[revid]:

129

# postpone if any child is missing

130

if child.revision_id not in distances:

131

if expected_id not in pending_ids:

132

pending_ids.append(expected_id)

133

expected_id = pending_ids.pop(0)

134

skipped_revids.append(revid)

135

sorted_revids[:0] = skipped_revids

136

del skipped_revids[:]

137

break

138

else:

139

# all children are here, push!

140

distances[revid] = len(distances)

141

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

142

# bail out early if a limit was specified

143

sorted_revids[:0] = skipped_revids

144

for revid in sorted_revids:

145

distances[revid] = len(distances)

146

break

147

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

148

for parent in parent_ids_of[revision]:

149

if parent not in pending_ids:

150

pending_ids.insert(0, parent)

151

if not pending_ids:

152

break

153

expected_id = pending_ids.pop(0)

154

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

155

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

156

# skipped list.

157

if expected_id in skipped_revids:

158

pos = skipped_revids.index(expected_id)

159

sorted_revids[:0] = skipped_revids[pos:]

160

del skipped_revids[pos:]

161

self.distances = distances

162

return sorted(distances, key=distances.get)

163

164

def choose_null_colour(self, revid):

165

"""We know we don't need this color, so just set it to NULL"""

166

self.colours[revid] = 0

167

168

def choose_colour(self, revid):

169

revision = self.revisions[revid]

170

children_of_id = self.children_of_id

171

parent_ids_of = self.parent_ids_of

172

colours = self.colours

173

# choose colour

174

the_children = children_of_id[revid]

175

if len(the_children) == 1:

176

[child] = the_children

177

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

178

# one-one relationship between parent and child, same

179

# colour

180

colours[revid] = colours[child.revision_id]

181

else:

182

self.choose_colour_one_child(revision, child)

183

else:

184

self.choose_colour_many_children(revision, the_children)

185

186

def choose_colour_one_child(self, revision, child):

187

revid = revision.revision_id

188

direct_parent_of = self.direct_parent_of

189

revisions = self.revisions

190

# one child with multiple parents, the first parent with

191

# the same committer gets the colour

192

direct_parent = direct_parent_of.get(child)

193

if direct_parent is None:

194

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

195

for parent_id in self.parent_ids_of[child]:

196

parent_revision = revisions[parent_id]

197

if parent_revision.committer == child.committer:

198

# found the first parent with the same committer

199

direct_parent = parent_revision

200

direct_parent_of[child] = direct_parent

201

break

202

if direct_parent == revision:

203

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

204

else:

205

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

206

207

def choose_colour_many_children(self, revision, the_children):

208

"""Colour revision revision."""

209

revid = revision.revision_id

210

direct_parent_of = self.direct_parent_of

211

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

212

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

213

# taken

214

available = {}

215

for child in the_children:

216

if child.committer != revision.committer:

217

continue

218

direct_parent = direct_parent_of.get(child)

219

if direct_parent == revision:

220

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

221

break

222

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

223

# knowledge of the revisions being output.

224

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

225

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

226

# if direct_parent is None:

227

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

228

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

229

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

230

else:

231

if available:

232

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

233

child = sorted_children[-1]

234

direct_parent_of[child] = revision

235

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

236

else:

237

# no candidate children is available, pick the next

238

# colour

239

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

240

241

242

def distances(repository, start_revid, maxnum=None):

243

"""Sort the revisions.

244

245

Traverses the branch revision tree starting at start and produces an

246

ordered list of revisions such that a revision always comes after

247

any revision it is the parent of.

248

249

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

250

"""

251

distance = DistanceMethod(repository, start_revid)

252

distance.fill_caches()

253

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

254

children = distance.make_children_map()

255

256

count = 0

257

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

258

count += 1

259

if maxnum is not None and count > maxnum:

260

distance.choose_null_colour(revid)

261

else:

262

distance.choose_colour(revid)

263

264

revisions = distance.revisions

265

colours = distance.colours

266

parent_ids_of = distance.parent_ids_of

267

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

268

269

270

def graph(revisions, colours, merge_sorted):

271

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

272

273

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

274

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

275

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

276

Revision object with the meta-data for the revision.

277

278

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

279

column number of the graph that this revision represents and colour

280

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

281

in particular) to draw the node in.

282

283

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

284

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

285

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

286

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

287

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

288

289

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

290

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

291

"""

292

if not len(merge_sorted):

293

return

294

# split merge_sorted into a map:

295

revs = {}

296

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

297

# calculating it ourselves

298

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

299

next_lower_rev = {}

300

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

301

# of branch

302

next_branch_revid = {}

303

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

304

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

305

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

306

current_stack = [[]]

307

for seq, revid, indent, end_merge in merge_sorted:

308

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

309

if indent == len(current_stack):

310

# new merge group starts

311

current_stack.append([revid])

312

elif indent == len(current_stack) - 1:

313

# part of the current merge group

314

current_stack[-1].append(revid)

315

else:

316

# end of a merge group

317

while current_stack[-1]:

318

stack_rev_id = current_stack[-1].pop()

319

# record the next lower rev for this rev:

320

next_lower_rev[stack_rev_id] = seq

321

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

322

if len(current_stack[-1]):

323

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

324

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

325

current_stack.pop()

326

# append to the now-current merge group

327

current_stack[-1].append(revid)

328

# assign a value to all the depth 0 revisions

329

while current_stack[-1]:

330

stack_rev_id = current_stack[-1].pop()

331

# record the next lower rev for this rev:

332

next_lower_rev[stack_rev_id] = len(merge_sorted)

333

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

334

if len(current_stack[-1]):

335

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

336

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

337

338

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

339

# the sequence of their lines on the screen.

340

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

341

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

342

hanging = [merge_sorted[0][1]]

343

for seq, revid, indent, end_merge in merge_sorted:

344

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

345

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

346

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

347

lines = []

348

349

new_hanging = []

350

351

for h_idx, hang in enumerate(hanging):

352

# one of these will be the current lines node:

353

# we are drawing a line. h_idx

354

if hang == revid:

355

# we have found the current lines node

356

node = (h_idx, colours[revid])

357

358

# note that we might have done the main parent

359

drawn_parents = set()

360

361

def draw_line(from_idx, to_idx, revision_id):

362

try:

363

n_idx = new_hanging.index(revision_id)

364

except ValueError:

365

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

366

# drawn.

367

new_hanging.insert(to_idx, revision_id)

368

n_idx = to_idx

369

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

370

371

372

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

373

if not end_merge:

374

# drop this line first.

375

parent_id = next_branch_revid[revid]

376

draw_line(h_idx, h_idx, parent_id)

377

# we have drawn this parent

378

drawn_parents.add(parent_id)

379

else:

380

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

381

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

382

# having > 1

383

# parents means this commit was a merge, and being

384

# the end point of a merge group means that all

385

# the parent revisions were merged into branches

386

# to the left of this before this was committed

387

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

388

# those revisions.

389

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

390

# sequence number, which is the one that this

391

# branch 'spawned from', and no others.

392

# If this sounds like a problem, remember that:

393

# if the parent was not already in our mainline

394

# it would show up as a merge into this making

395

# this not the end of a merge-line.

396

lowest = len(merge_sorted)

397

for parent_id in revisions[revid].parent_ids:

398

if revs[parent_id][0] < lowest:

399

lowest = revs[parent_id][0]

400

assert lowest != len(merge_sorted)

401

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

402

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

403

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

404

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

405

parent_id = revisions[revid].parent_ids[0]

406

draw_line(h_idx, len(new_hanging), parent_id)

407

drawn_parents.add(parent_id)

408

409

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

410

# each parent IF its relevant.

411

#

412

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

413

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

414

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

415

# hangs to keep the graph small.

416

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

417

# unless its the last revision in a merge group.

418

for parent_id in revisions[revid].parent_ids:

419

if parent_id in drawn_parents:

420

continue

421

parent_seq = revs[parent_id][0]

422

parent_depth = revs[parent_id][1]

423

if parent_depth == indent + 1:

424

# The parent was a merge into this branch determine if

425

# it was already merged into the mainline via a

426

# different merge: if all revisions between us and

427

# parent_seq have a indent greater than there are no

428

# revisions with a lower indent than us.

429

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

430

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

431

# merge_sorted should take care of that for us (but

432

# does not trim the values)

433

if parent_seq < next_lower_rev[revid]:

434

draw_line(h_idx, len(new_hanging), parent_id)

435

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

436

# part of this branch

437

draw_line(h_idx, len(new_hanging), parent_id)

438

else:

439

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

440

# new position.

441

# h_idx is the old position.

442

# new_indent is the new position.

443

draw_line(h_idx, len(new_hanging), hang)

444

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

445

# the next row

446

hanging = new_hanging

447

448

yield (revisions[revid], node, lines)

449

450

451

def same_branch(a, b):

452

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

453

if len(a.parent_ids) == 1:

454

# Defacto same branch if only parent

455

return True

456

elif a.committer == b.committer:

457

# Same committer so may as well be

458

return True

459

else:

460

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 = branch.revision_history()

50

graph_parents = branch.repository.get_revision_graph(start)

51

graph_children = {}

52

for revid in graph_parents.iterkeys():

53

graph_children[revid] = []

54

55

merge_sorted_revisions = merge_sort(

56

graph_parents,

57

start,

58

mainline,

59

generate_revno=True)

60

61

revid_index = {}

62

revno_index = {}

63

64

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

65

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

66

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

67

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

68

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

69

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

70

# a list of rev_indexes in the branch.

71

branch_lines = {}

72

73

linegraph = []

74

75

for (rev_index, (sequence_number,

76

revid,

77

merge_depth,

78

revno_sequence,

79

end_of_merge)) in enumerate(merge_sorted_revisions):

80

if maxnum and rev_index >= maxnum:

81

break

82

revid_index[revid] = rev_index

83

revno_index[revno_sequence] = rev_index

84

85

branch_id = revno_sequence[0:-1]

86

87

branch_line = None

88

if branch_id not in branch_lines:

89

branch_line = []

90

branch_lines[branch_id] = branch_line

91

else:

92

branch_line = branch_lines[branch_id]

93

94

branch_line.append(rev_index)

95

96

parents = graph_parents[revid]

97

for parent_revid in parents:

98

graph_children[parent_revid].append(revid)

99

100

linegraph.append([revid,

101

None,

102

[],

103

parents,

104

None,

105

revno_sequence])

106

107

branch_ids = branch_lines.keys()

108

109

def branch_id_cmp(x, y):

110

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

111

by their value"""

112

len_x = len(x)

113

len_y = len(y)

114

if len_x == len_y:

115

return -cmp(x, y)

116

return cmp(len_x, len_y)

117

118

branch_ids.sort(branch_id_cmp)

119

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

120

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

121

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

122

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

123

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

124

lines = []

125

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

126

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

127

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

128

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

129

columns = [list(empty_column)]

130

131

132

for branch_id in branch_ids:

133

branch_line = branch_lines[branch_id]

134

135

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

136

# starting point when looking for a free column.

137

parent_col_index = 0

138

parent_index = None

139

if len(branch_id) > 1:

140

parent_revno = branch_id[0:-1]

141

if parent_revno in revno_index:

142

parent_index = revno_index[parent_revno]

143

parent_node = linegraph[parent_index][1]

144

if parent_node:

145

parent_col_index = parent_node[0]

146

147

148

col_search_order = _branch_line_col_search_order(columns,

149

parent_col_index)

150

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

151

cur_cont_line = []

152

153

line_range = []

154

last_rev_index = None

155

for rev_index in branch_line:

156

if last_rev_index:

157

if BROKEN_LINE_LENGTH and \

158

rev_index - last_rev_index > BROKEN_LINE_LENGTH:

159

line_range.append(last_rev_index+1)

160

line_range.append(rev_index-1)

161

else:

162

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

163

164

line_range.append(rev_index)

165

last_rev_index = rev_index

166

167

if parent_index:

168

if BROKEN_LINE_LENGTH and \

169

parent_index - last_rev_index > BROKEN_LINE_LENGTH:

170

line_range.append(last_rev_index+1)

171

else:

172

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

173

174

col_index = _find_free_column(columns,

175

empty_column,

176

col_search_order,

177

line_range)

178

node = (col_index, color)

179

for rev_index in branch_line:

180

linegraph[rev_index][1] = node

181

columns[col_index][rev_index] = True

182

183

for rev_index in branch_line:

184

(sequence_number,

185

revid,

186

merge_depth,

187

revno_sequence,

188

end_of_merge) = merge_sorted_revisions[rev_index]

189

190

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

191

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

192

193

for parent_revid in graph_parents[revid]:

194

if parent_revid in revid_index:

195

196

parent_index = revid_index[parent_revid]

197

parent_node = linegraph[parent_index][1]

198

if parent_node:

199

parent_col_index = parent_node[0]

200

else:

201

parent_col_index = None

202

col_search_order = \

203

_line_col_search_order(columns,

204

parent_col_index,

205

col_index)

206

207

# If this line is really long, break it.

208

if len(branch_id) > 0 and \

209

BROKEN_LINE_LENGTH and \

210

parent_index - rev_index > BROKEN_LINE_LENGTH:

211

child_line_col_index = \

212

_find_free_column(columns,

213

empty_column,

214

col_search_order,

215

(rev_index + 1,))

216

_mark_column_as_used(columns,

217

child_line_col_index,

218

(rev_index + 1,))

219

220

# Recall _line_col_search_order to reset it back to

221

# the beging.

222

col_search_order = \

223

_line_col_search_order(columns,

224

parent_col_index,

225

col_index)

226

parent_col_line_index = \

227

_find_free_column(columns,

228

empty_column,

229

col_search_order,

230

(parent_index - 1,))

231

_mark_column_as_used(columns,

232

parent_col_line_index,

233

(parent_index - 1,))

234

lines.append((rev_index,

235

parent_index,

236

(child_line_col_index,

237

parent_col_line_index)))

238

else :

239

line_col_index = col_index

240

if parent_index - rev_index >1:

241

line_range = range(rev_index + 1, parent_index)

242

line_col_index = \

243

_find_free_column(columns,

244

empty_column,

245

col_search_order,

246

line_range)

247

_mark_column_as_used(columns,

248

line_col_index,

249

line_range)

250

lines.append((rev_index,

251

parent_index,

252

(line_col_index,)))

253

254

for (child_index, parent_index, line_col_indexes) in lines:

255

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

256

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

257

258

if len(line_col_indexes) == 1:

259

if parent_index - child_index == 1:

260

linegraph[child_index][2].append(

261

(child_col_index,

262

parent_col_index,

263

parent_color))

264

else:

265

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

266

linegraph[child_index][2].append(

267

(child_col_index,

268

line_col_indexes[0],

269

parent_color))

270

# lines down the line's column

271

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

272

linegraph[line_part_index][2].append(

273

(line_col_indexes[0],

274

line_col_indexes[0],

275

parent_color))

276

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

277

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

278

(line_col_indexes[0],

279

parent_col_index,

280

parent_color))

281

else:

282

# Broken line

283

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

284

linegraph[child_index][2].append(

285

(child_col_index,

286

line_col_indexes[0],

287

parent_color))

288

# Broken line end

289

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

290

(line_col_indexes[0],

291

None,

292

parent_color))

293

294

# Broken line end

295

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

296

(None,

297

line_col_indexes[1],

298

parent_color))

299

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

300

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

301

(line_col_indexes[1],

302

parent_col_index,

303

parent_color))

304

305

306

return (linegraph, revid_index, len(columns))

307

308

def _branch_line_col_search_order(columns, parent_col_index):

309

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

310

yield col_index

311

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

312

yield col_index

313

314

def _line_col_search_order(columns, parent_col_index, child_col_index):

315

if parent_col_index is not None:

316

max_index = max(parent_col_index, child_col_index)

317

min_index = min(parent_col_index, child_col_index)

318

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

319

yield col_index

320

else:

321

max_index = child_col_index

322

min_index = child_col_index

323

yield child_col_index

324

i = 1

325

while max_index + i < len(columns) or \

326

min_index - i > -1:

327

if max_index + i < len(columns):

328

yield max_index + i

329

if min_index - i > -1:

330

yield min_index - i

331

i += 1

332

333

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

334

for col_index in col_search_order:

335

column = columns[col_index]

336

has_overlaping_line = False

337

for row_index in line_range:

338

if column[row_index]:

339

has_overlaping_line = True

340

break

341

if not has_overlaping_line:

342

break

343

else:

344

col_index = len(columns)

345

column = list(empty_column)

346

columns.append(column)

347

return col_index

348

349

def _mark_column_as_used(columns, col_index, line_range):

350

column = columns[col_index]

351

for row_index in line_range:

352

column[row_index] = True

353

354

def same_branch(a, b):

355

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

356

if len(a.parent_ids) == 1:

357

# Defacto same branch if only parent

358

return True

359

elif a.committer == b.committer:

360

# Same committer so may as well be

361

return True

362

else:

363

return False