/b-gtk/fix-viz : revision 423.2.1

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.tsort import merge_sort

14

15

16

class DummyRevision(object):

17

"""Dummy bzr revision.

18

19

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

20

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

21

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

22

Revision object (which we can't get).

23

"""

24

25

def __init__(self, revid):

26

self.revision_id = revid

27

self.parent_ids = []

28

self.committer = None

29

self.message = self.revision_id

30

31

32

class RevisionProxy(object):

33

"""A revision proxy object.

34

35

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

36

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

37

constructed with the revision id and parent_ids list and a repository

38

object to request the revision from when needed.

39

"""

40

41

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

42

self.revision_id = revid

43

self.parent_ids = parent_ids

44

self._repository = repository

45

self._revision = None

46

47

def _get_attribute_getter(attr):

48

def get_attribute(self):

49

if self._revision is None:

50

self._load()

51

return getattr(self._revision, attr)

52

return get_attribute

53

committer = property(_get_attribute_getter('committer'))

54

message = property(_get_attribute_getter('message'))

55

properties = property(_get_attribute_getter('properties'))

56

timestamp = property(_get_attribute_getter('timestamp'))

57

timezone = property(_get_attribute_getter('timezone'))

58

59

def _load(self):

60

"""Load the revision object."""

61

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

62

63

64

class DistanceMethod(object):

65

66

def __init__(self, branch, start):

67

self.branch = branch

68

self.start = start

69

self.revisions = {}

70

self.children = {}

71

self.children_of_id = {start: set()}

72

self.parent_ids_of = {}

73

self.colours = { start: 0 }

74

self.last_colour = 0

75

self.direct_parent_of = {}

76

self.graph = {}

77

78

def fill_caches(self):

79

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

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.branch.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_colour(self, revid):

165

revision = self.revisions[revid]

166

children_of_id = self.children_of_id

167

parent_ids_of = self.parent_ids_of

168

colours = self.colours

169

# choose colour

170

the_children = children_of_id[revid]

171

if len(the_children) == 1:

172

[child] = the_children

173

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

174

# one-one relationship between parent and child, same

175

# colour

176

colours[revid] = colours[child.revision_id]

177

else:

178

self.choose_colour_one_child(revision, child)

179

else:

180

self.choose_colour_many_children(revision, the_children)

181

182

def choose_colour_one_child(self, revision, child):

183

revid = revision.revision_id

184

direct_parent_of = self.direct_parent_of

185

revisions = self.revisions

186

# one child with multiple parents, the first parent with

187

# the same committer gets the colour

188

direct_parent = direct_parent_of.get(child)

189

if direct_parent is None:

190

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

191

for parent_id in self.parent_ids_of[child]:

192

parent_revision = revisions[parent_id]

193

if parent_revision.committer == child.committer:

194

# found the first parent with the same committer

195

direct_parent = parent_revision

196

direct_parent_of[child] = direct_parent

197

break

198

if direct_parent == revision:

199

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

200

else:

201

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

202

203

def choose_colour_many_children(self, revision, the_children):

204

"""Colour revision revision."""

205

revid = revision.revision_id

206

direct_parent_of = self.direct_parent_of

207

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

208

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

209

# taken

210

available = {}

211

for child in the_children:

212

if child.committer != revision.committer:

213

continue

214

direct_parent = direct_parent_of.get(child)

215

if direct_parent == revision:

216

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

217

break

218

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

219

# knowledge of the revisions being output.

220

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

221

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

222

# if direct_parent is None:

223

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

224

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

225

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

226

else:

227

if available:

228

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

229

child = sorted_children[-1]

230

direct_parent_of[child] = revision

231

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

232

else:

233

# no candidate children is available, pick the next

234

# colour

235

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

236

237

238

def distances(branch, start):

239

"""Sort the revisions.

240

241

Traverses the branch revision tree starting at start and produces an

242

ordered list of revisions such that a revision always comes after

243

any revision it is the parent of.

244

245

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

246

"""

247

distance = DistanceMethod(branch, start)

248

distance.fill_caches()

249

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

250

children = distance.make_children_map()

251

252

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

253

distance.choose_colour(revid)

254

255

revisions = distance.revisions

256

colours = distance.colours

257

parent_ids_of = distance.parent_ids_of

258

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

259

260

261

def graph(revisions, colours, merge_sorted):

262

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

263

264

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

265

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

266

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

267

Revision object with the meta-data for the revision.

268

269

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

270

column number of the graph that this revision represents and colour

271

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

272

in particular) to draw the node in.

273

274

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

275

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

276

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

277

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

278

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

279

280

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

281

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

282

"""

283

if not len(merge_sorted):

284

return

285

# split merge_sorted into a map:

286

revs = {}

287

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

288

# calculating it ourselves

289

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

290

next_lower_rev = {}

291

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

292

# of branch

293

next_branch_revid = {}

294

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

295

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

296

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

297

current_stack = [[]]

298

for seq, revid, indent, end_merge in merge_sorted:

299

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

300

if indent == len(current_stack):

301

# new merge group starts

302

current_stack.append([revid])

303

elif indent == len(current_stack) - 1:

304

# part of the current merge group

305

current_stack[-1].append(revid)

306

else:

307

# end of a merge group

308

while current_stack[-1]:

309

stack_rev_id = current_stack[-1].pop()

310

# record the next lower rev for this rev:

311

next_lower_rev[stack_rev_id] = seq

312

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

313

if len(current_stack[-1]):

314

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

315

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

316

current_stack.pop()

317

# append to the now-current merge group

318

current_stack[-1].append(revid)

319

# assign a value to all the depth 0 revisions

320

while current_stack[-1]:

321

stack_rev_id = current_stack[-1].pop()

322

# record the next lower rev for this rev:

323

next_lower_rev[stack_rev_id] = len(merge_sorted)

324

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

325

if len(current_stack[-1]):

326

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

327

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

328

329

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

330

# the sequence of their lines on the screen.

331

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

332

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

333

hanging = [merge_sorted[0][1]]

334

for seq, revid, indent, end_merge in merge_sorted:

335

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

336

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

337

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

338

lines = []

339

340

new_hanging = []

341

342

for h_idx, hang in enumerate(hanging):

343

# one of these will be the current lines node:

344

# we are drawing a line. h_idx

345

if hang == revid:

346

# we have found the current lines node

347

node = (h_idx, colours[revid])

348

349

# note that we might have done the main parent

350

drawn_parents = set()

351

352

def draw_line(from_idx, to_idx, revision_id):

353

try:

354

n_idx = new_hanging.index(revision_id)

355

except ValueError:

356

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

357

# drawn.

358

new_hanging.insert(to_idx, revision_id)

359

n_idx = to_idx

360

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

361

362

363

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

364

if not end_merge:

365

# drop this line first.

366

parent_id = next_branch_revid[revid]

367

draw_line(h_idx, h_idx, parent_id)

368

# we have drawn this parent

369

drawn_parents.add(parent_id)

370

else:

371

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

372

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

373

# having > 1

374

# parents means this commit was a merge, and being

375

# the end point of a merge group means that all

376

# the parent revisions were merged into branches

377

# to the left of this before this was committed

378

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

379

# those revisions.

380

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

381

# sequence number, which is the one that this

382

# branch 'spawned from', and no others.

383

# If this sounds like a problem, remember that:

384

# if the parent was not already in our mainline

385

# it would show up as a merge into this making

386

# this not the end of a merge-line.

387

lowest = len(merge_sorted)

388

for parent_id in revisions[revid].parent_ids:

389

if revs[parent_id][0] < lowest:

390

lowest = revs[parent_id][0]

391

assert lowest != len(merge_sorted)

392

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

393

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

394

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

395

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

396

parent_id = revisions[revid].parent_ids[0]

397

draw_line(h_idx, len(new_hanging), parent_id)

398

drawn_parents.add(parent_id)

399

400

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

401

# each parent IF its relevant.

402

#

403

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

404

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

405

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

406

# hangs to keep the graph small.

407

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

408

# unless its the last revision in a merge group.

409

for parent_id in revisions[revid].parent_ids:

410

if parent_id in drawn_parents:

411

continue

412

parent_seq = revs[parent_id][0]

413

parent_depth = revs[parent_id][1]

414

if parent_depth == indent + 1:

415

# The parent was a merge into this branch determine if

416

# it was already merged into the mainline via a

417

# different merge: if all revisions between us and

418

# parent_seq have a indent greater than there are no

419

# revisions with a lower indent than us.

420

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

421

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

422

# merge_sorted should take care of that for us (but

423

# does not trim the values)

424

if parent_seq < next_lower_rev[revid]:

425

draw_line(h_idx, len(new_hanging), parent_id)

426

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

427

# part of this branch

428

draw_line(h_idx, len(new_hanging), parent_id)

429

else:

430

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

431

# new position.

432

# h_idx is the old position.

433

# new_indent is the new position.

434

draw_line(h_idx, len(new_hanging), hang)

435

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

436

# the next row

437

hanging = new_hanging

438

439

yield (revisions[revid], node, lines)

440

441

442

def same_branch(a, b):

443

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

444

if len(a.parent_ids) == 1:

445

# Defacto same branch if only parent

446

return True

447

elif a.committer == b.committer:

448

# Same committer so may as well be

449

return True

450

else:

451

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(repository, start, maxnum, broken_line_length=None):

15

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

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

graph_parents = repository.get_revision_graph(start)

45

graph_children = {}

46

for revid in graph_parents.iterkeys():

47

graph_children[revid] = []

48

49

if len(graph_parents)>0:

50

merge_sorted_revisions = merge_sort(

51

graph_parents,

52

start,

53

generate_revno=True)

54

else:

55

merge_sorted_revisions = ()

56

57

revid_index = {}

58

revno_index = {}

59

60

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

61

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

62

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

63

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

64

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

65

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

66

# a list of rev_indexes in the branch.

67

branch_lines = {}

68

69

linegraph = []

70

71

for (rev_index, (sequence_number,

72

revid,

73

merge_depth,

74

revno_sequence,

75

end_of_merge)) in enumerate(merge_sorted_revisions):

76

if maxnum and rev_index >= maxnum:

77

break

78

revid_index[revid] = rev_index

79

revno_index[revno_sequence] = rev_index

80

81

branch_id = revno_sequence[0:-1]

82

83

branch_line = None

84

if branch_id not in branch_lines:

85

branch_line = []

86

branch_lines[branch_id] = branch_line

87

else:

88

branch_line = branch_lines[branch_id]

89

90

branch_line.append(rev_index)

91

92

parents = graph_parents[revid]

93

for parent_revid in parents:

94

graph_children[parent_revid].append(revid)

95

96

linegraph.append([revid,

97

None,

98

[],

99

parents,

100

None,

101

revno_sequence])

102

103

branch_ids = branch_lines.keys()

104

105

def branch_id_cmp(x, y):

106

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

107

by their value"""

108

len_x = len(x)

109

len_y = len(y)

110

if len_x == len_y:

111

return -cmp(x, y)

112

return cmp(len_x, len_y)

113

114

branch_ids.sort(branch_id_cmp)

115

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

116

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

117

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

118

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

119

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

120

lines = []

121

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

122

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

123

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

124

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

125

columns = [list(empty_column)]

126

127

128

for branch_id in branch_ids:

129

branch_line = branch_lines[branch_id]

130

131

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

132

# starting point when looking for a free column.

133

parent_col_index = 0

134

parent_index = None

135

if len(branch_id) > 1:

136

parent_revno = branch_id[0:-1]

137

if parent_revno in revno_index:

138

parent_index = revno_index[parent_revno]

139

parent_node = linegraph[parent_index][1]

140

if parent_node:

141

parent_col_index = parent_node[0]

142

143

144

col_search_order = _branch_line_col_search_order(columns,

145

parent_col_index)

146

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

147

cur_cont_line = []

148

149

line_range = []

150

last_rev_index = None

151

for rev_index in branch_line:

152

if last_rev_index:

153

if broken_line_length and \

154

rev_index - last_rev_index > broken_line_length:

155

line_range.append(last_rev_index+1)

156

line_range.append(rev_index-1)

157

else:

158

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

159

160

line_range.append(rev_index)

161

last_rev_index = rev_index

162

163

if parent_index:

164

if broken_line_length and \

165

parent_index - last_rev_index > broken_line_length:

166

line_range.append(last_rev_index+1)

167

else:

168

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

169

170

col_index = _find_free_column(columns,

171

empty_column,

172

col_search_order,

173

line_range)

174

node = (col_index, color)

175

for rev_index in branch_line:

176

linegraph[rev_index][1] = node

177

columns[col_index][rev_index] = True

178

179

for rev_index in branch_line:

180

(sequence_number,

181

revid,

182

merge_depth,

183

revno_sequence,

184

end_of_merge) = merge_sorted_revisions[rev_index]

185

186

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

187

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

188

189

for parent_revid in graph_parents[revid]:

190

if parent_revid in revid_index:

191

192

parent_index = revid_index[parent_revid]

193

parent_node = linegraph[parent_index][1]

194

if parent_node:

195

parent_col_index = parent_node[0]

196

else:

197

parent_col_index = None

198

col_search_order = \

199

_line_col_search_order(columns,

200

parent_col_index,

201

col_index)

202

203

# If this line is really long, break it.

204

if len(branch_id) > 0 and \

205

broken_line_length and \

206

parent_index - rev_index > broken_line_length:

207

child_line_col_index = \

208

_find_free_column(columns,

209

empty_column,

210

col_search_order,

211

(rev_index + 1,))

212

_mark_column_as_used(columns,

213

child_line_col_index,

214

(rev_index + 1,))

215

216

# Recall _line_col_search_order to reset it back to

217

# the beging.

218

col_search_order = \

219

_line_col_search_order(columns,

220

parent_col_index,

221

col_index)

222

parent_col_line_index = \

223

_find_free_column(columns,

224

empty_column,

225

col_search_order,

226

(parent_index - 1,))

227

_mark_column_as_used(columns,

228

parent_col_line_index,

229

(parent_index - 1,))

230

lines.append((rev_index,

231

parent_index,

232

(child_line_col_index,

233

parent_col_line_index)))

234

else :

235

line_col_index = col_index

236

if parent_index - rev_index >1:

237

line_range = range(rev_index + 1, parent_index)

238

line_col_index = \

239

_find_free_column(columns,

240

empty_column,

241

col_search_order,

242

line_range)

243

_mark_column_as_used(columns,

244

line_col_index,

245

line_range)

246

lines.append((rev_index,

247

parent_index,

248

(line_col_index,)))

249

250

for (child_index, parent_index, line_col_indexes) in lines:

251

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

252

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

253

254

if len(line_col_indexes) == 1:

255

if parent_index - child_index == 1:

256

linegraph[child_index][2].append(

257

(child_col_index,

258

parent_col_index,

259

parent_color))

260

else:

261

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

262

linegraph[child_index][2].append(

263

(child_col_index,

264

line_col_indexes[0],

265

parent_color))

266

# lines down the line's column

267

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

268

linegraph[line_part_index][2].append(

269

(line_col_indexes[0],

270

line_col_indexes[0],

271

parent_color))

272

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

273

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

274

(line_col_indexes[0],

275

parent_col_index,

276

parent_color))

277

else:

278

# Broken line

279

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

280

linegraph[child_index][2].append(

281

(child_col_index,

282

line_col_indexes[0],

283

parent_color))

284

# Broken line end

285

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

286

(line_col_indexes[0],

287

None,

288

parent_color))

289

290

# Broken line end

291

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

292

(None,

293

line_col_indexes[1],

294

parent_color))

295

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

296

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

297

(line_col_indexes[1],

298

parent_col_index,

299

parent_color))

300

301

302

return (linegraph, revid_index, len(columns))

303

304

def _branch_line_col_search_order(columns, parent_col_index):

305

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

306

yield col_index

307

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

308

yield col_index

309

310

def _line_col_search_order(columns, parent_col_index, child_col_index):

311

if parent_col_index is not None:

312

max_index = max(parent_col_index, child_col_index)

313

min_index = min(parent_col_index, child_col_index)

314

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

315

yield col_index

316

else:

317

max_index = child_col_index

318

min_index = child_col_index

319

yield child_col_index

320

i = 1

321

while max_index + i < len(columns) or \

322

min_index - i > -1:

323

if max_index + i < len(columns):

324

yield max_index + i

325

if min_index - i > -1:

326

yield min_index - i

327

i += 1

328

329

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

330

for col_index in col_search_order:

331

column = columns[col_index]

332

has_overlaping_line = False

333

for row_index in line_range:

334

if column[row_index]:

335

has_overlaping_line = True

336

break

337

if not has_overlaping_line:

338

break

339

else:

340

col_index = len(columns)

341

column = list(empty_column)

342

columns.append(column)

343

return col_index

344

345

def _mark_column_as_used(columns, col_index, line_range):

346

column = columns[col_index]

347

for row_index in line_range:

348

column[row_index] = True

349

350

def same_branch(a, b):

351

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

352

if len(a.parent_ids) == 1:

353

# Defacto same branch if only parent

354

return True

355

elif a.committer == b.committer:

356

# Same committer so may as well be

357

return True

358

else:

359

return False