/b-gtk/fix-viz : revision 423.1.21

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.message = revid

29

30

31

class RevisionProxy(object):

32

"""A revision proxy object.

33

34

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

35

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

36

constructed with the revision id and parent_ids list and a repository

37

object to request the revision from when needed.

38

"""

39

40

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

41

self.revision_id = revid

42

self.parent_ids = parent_ids

43

self._repository = repository

44

self._revision = None

45

46

def _get_attribute_getter(attr):

47

def get_attribute(self):

48

if self._revision is None:

49

self._load()

50

return getattr(self._revision, attr)

51

return get_attribute

52

committer = property(_get_attribute_getter('committer'))

53

message = property(_get_attribute_getter('message'))

54

properties = property(_get_attribute_getter('properties'))

55

timestamp = property(_get_attribute_getter('timestamp'))

56

timezone = property(_get_attribute_getter('timezone'))

57

58

def _load(self):

59

"""Load the revision object."""

60

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

61

62

63

class DistanceMethod(object):

64

65

def __init__(self, branch, start):

66

self.branch = branch

67

self.start = start

68

self.revisions = {}

69

self.children = {}

70

self.children_of_id = {start: set()}

71

self.parent_ids_of = {}

72

self.colours = { start: 0 }

73

self.last_colour = 0

74

self.direct_parent_of = {}

75

self.graph = {}

76

77

def fill_caches(self):

78

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

79

for revid in graph.ghosts:

80

self.cache_revision(DummyRevision(revid))

81

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

82

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

83

84

def cache_revision(self, revision):

85

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

86

revid = revision.revision_id

87

# Build a revision cache

88

self.revisions[revid] = revision

89

# Build a children dictionary

90

for parent_id in revision.parent_ids:

91

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

92

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

93

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

94

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

95

# fix the parent_ids list.

96

parent_ids = []

97

parent_ids_set = set()

98

for parent_id in revision.parent_ids:

99

if parent_id in parent_ids_set:

100

continue

101

parent_ids.append(parent_id)

102

parent_ids_set.add(parent_id)

103

revision.parent_ids = parent_ids

104

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

105

self.graph[revid] = revision.parent_ids

106

107

def make_children_map(self):

108

revisions = self.revisions

109

return dict((revisions[revid], c)

110

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

111

112

def sort_revisions(self, sorted_revids, maxnum):

113

revisions = self.revisions

114

parent_ids_of = self.parent_ids_of

115

children_of_id = self.children_of_id

116

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

117

distances = {}

118

skipped_revids = []

119

expected_id = sorted_revids[0]

120

pending_ids = []

121

while True:

122

revid = sorted_revids.pop(0)

123

if revid != expected_id:

124

skipped_revids.append(revid)

125

continue

126

revision = revisions[revid]

127

for child in children_of_id[revid]:

128

# postpone if any child is missing

129

if child.revision_id not in distances:

130

if expected_id not in pending_ids:

131

pending_ids.append(expected_id)

132

expected_id = pending_ids.pop(0)

133

skipped_revids.append(revid)

134

sorted_revids[:0] = skipped_revids

135

del skipped_revids[:]

136

break

137

else:

138

# all children are here, push!

139

distances[revid] = len(distances)

140

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

141

# bail out early if a limit was specified

142

sorted_revids[:0] = skipped_revids

143

for revid in sorted_revids:

144

distances[revid] = len(distances)

145

break

146

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

147

for parent in parent_ids_of[revision]:

148

if parent not in pending_ids:

149

pending_ids.insert(0, parent)

150

if not pending_ids:

151

break

152

expected_id = pending_ids.pop(0)

153

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

154

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

155

# skipped list.

156

if expected_id in skipped_revids:

157

pos = skipped_revids.index(expected_id)

158

sorted_revids[:0] = skipped_revids[pos:]

159

del skipped_revids[pos:]

160

self.distances = distances

161

return sorted(distances, key=distances.get)

162

163

def choose_colour(self, revid):

164

revision = self.revisions[revid]

165

children_of_id = self.children_of_id

166

parent_ids_of = self.parent_ids_of

167

colours = self.colours

168

# choose colour

169

the_children = children_of_id[revid]

170

if len(the_children) == 1:

171

[child] = the_children

172

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

173

# one-one relationship between parent and child, same

174

# colour

175

colours[revid] = colours[child.revision_id]

176

else:

177

self.choose_colour_one_child(revision, child)

178

else:

179

self.choose_colour_many_children(revision, the_children)

180

181

def choose_colour_one_child(self, revision, child):

182

revid = revision.revision_id

183

direct_parent_of = self.direct_parent_of

184

revisions = self.revisions

185

# one child with multiple parents, the first parent with

186

# the same committer gets the colour

187

direct_parent = direct_parent_of.get(child)

188

if direct_parent is None:

189

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

190

for parent_id in self.parent_ids_of[child]:

191

parent_revision = revisions[parent_id]

192

if parent_revision.committer == child.committer:

193

# found the first parent with the same committer

194

direct_parent = parent_revision

195

direct_parent_of[child] = direct_parent

196

break

197

if direct_parent == revision:

198

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

199

else:

200

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

201

202

def choose_colour_many_children(self, revision, the_children):

203

"""Colour revision revision."""

204

revid = revision.revision_id

205

direct_parent_of = self.direct_parent_of

206

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

207

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

208

# taken

209

available = {}

210

for child in the_children:

211

if child.committer != revision.committer:

212

continue

213

direct_parent = direct_parent_of.get(child)

214

if direct_parent == revision:

215

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

216

break

217

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

218

# knowledge of the revisions being output.

219

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

220

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

221

# if direct_parent is None:

222

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

223

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

224

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

225

else:

226

if available:

227

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

228

child = sorted_children[-1]

229

direct_parent_of[child] = revision

230

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

231

else:

232

# no candidate children is available, pick the next

233

# colour

234

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

235

236

237

def distances(branch, start):

238

"""Sort the revisions.

239

240

Traverses the branch revision tree starting at start and produces an

241

ordered list of revisions such that a revision always comes after

242

any revision it is the parent of.

243

244

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

245

"""

246

distance = DistanceMethod(branch, start)

247

distance.fill_caches()

248

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

249

children = distance.make_children_map()

250

251

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

252

distance.choose_colour(revid)

253

254

revisions = distance.revisions

255

colours = distance.colours

256

parent_ids_of = distance.parent_ids_of

257

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

258

259

260

def graph(revisions, colours, merge_sorted):

261

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

262

263

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

264

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

265

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

266

Revision object with the meta-data for the revision.

267

268

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

269

column number of the graph that this revision represents and colour

270

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

271

in particular) to draw the node in.

272

273

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

274

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

275

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

276

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

277

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

278

279

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

280

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

281

"""

282

if not len(merge_sorted):

283

return

284

# split merge_sorted into a map:

285

revs = {}

286

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

287

# calculating it ourselves

288

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

289

next_lower_rev = {}

290

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

291

# of branch

292

next_branch_revid = {}

293

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

294

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

295

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

296

current_stack = [[]]

297

for seq, revid, indent, end_merge in merge_sorted:

298

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

299

if indent == len(current_stack):

300

# new merge group starts

301

current_stack.append([revid])

302

elif indent == len(current_stack) - 1:

303

# part of the current merge group

304

current_stack[-1].append(revid)

305

else:

306

# end of a merge group

307

while current_stack[-1]:

308

stack_rev_id = current_stack[-1].pop()

309

# record the next lower rev for this rev:

310

next_lower_rev[stack_rev_id] = seq

311

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

312

if len(current_stack[-1]):

313

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

314

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

315

current_stack.pop()

316

# append to the now-current merge group

317

current_stack[-1].append(revid)

318

# assign a value to all the depth 0 revisions

319

while current_stack[-1]:

320

stack_rev_id = current_stack[-1].pop()

321

# record the next lower rev for this rev:

322

next_lower_rev[stack_rev_id] = len(merge_sorted)

323

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

324

if len(current_stack[-1]):

325

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

326

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

327

328

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

329

# the sequence of their lines on the screen.

330

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

331

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

332

hanging = [merge_sorted[0][1]]

333

for seq, revid, indent, end_merge in merge_sorted:

334

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

335

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

336

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

337

lines = []

338

339

new_hanging = []

340

341

for h_idx, hang in enumerate(hanging):

342

# one of these will be the current lines node:

343

# we are drawing a line. h_idx

344

if hang == revid:

345

# we have found the current lines node

346

node = (h_idx, colours[revid])

347

348

# note that we might have done the main parent

349

drawn_parents = set()

350

351

def draw_line(from_idx, to_idx, revision_id):

352

try:

353

n_idx = new_hanging.index(revision_id)

354

except ValueError:

355

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

356

# drawn.

357

new_hanging.insert(to_idx, revision_id)

358

n_idx = to_idx

359

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

360

361

362

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

363

if not end_merge:

364

# drop this line first.

365

parent_id = next_branch_revid[revid]

366

draw_line(h_idx, h_idx, parent_id)

367

# we have drawn this parent

368

drawn_parents.add(parent_id)

369

else:

370

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

371

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

372

# having > 1

373

# parents means this commit was a merge, and being

374

# the end point of a merge group means that all

375

# the parent revisions were merged into branches

376

# to the left of this before this was committed

377

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

378

# those revisions.

379

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

380

# sequence number, which is the one that this

381

# branch 'spawned from', and no others.

382

# If this sounds like a problem, remember that:

383

# if the parent was not already in our mainline

384

# it would show up as a merge into this making

385

# this not the end of a merge-line.

386

lowest = len(merge_sorted)

387

for parent_id in revisions[revid].parent_ids:

388

if revs[parent_id][0] < lowest:

389

lowest = revs[parent_id][0]

390

assert lowest != len(merge_sorted)

391

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

392

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

393

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

394

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

395

parent_id = revisions[revid].parent_ids[0]

396

draw_line(h_idx, len(new_hanging), parent_id)

397

drawn_parents.add(parent_id)

398

399

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

400

# each parent IF its relevant.

401

#

402

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

403

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

404

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

405

# hangs to keep the graph small.

406

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

407

# unless its the last revision in a merge group.

408

for parent_id in revisions[revid].parent_ids:

409

if parent_id in drawn_parents:

410

continue

411

parent_seq = revs[parent_id][0]

412

parent_depth = revs[parent_id][1]

413

if parent_depth == indent + 1:

414

# The parent was a merge into this branch determine if

415

# it was already merged into the mainline via a

416

# different merge: if all revisions between us and

417

# parent_seq have a indent greater than there are no

418

# revisions with a lower indent than us.

419

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

420

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

421

# merge_sorted should take care of that for us (but

422

# does not trim the values)

423

if parent_seq < next_lower_rev[revid]:

424

draw_line(h_idx, len(new_hanging), parent_id)

425

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

426

# part of this branch

427

draw_line(h_idx, len(new_hanging), parent_id)

428

else:

429

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

430

# new position.

431

# h_idx is the old position.

432

# new_indent is the new position.

433

draw_line(h_idx, len(new_hanging), hang)

434

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

435

# the next row

436

hanging = new_hanging

437

438

yield (revisions[revid], node, lines)

439

440

441

def same_branch(a, b):

442

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

443

if len(a.parent_ids) == 1:

444

# Defacto same branch if only parent

445

return True

446

elif a.committer == b.committer:

447

# Same committer so may as well be

448

return True

449

else:

450

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

graph_data = True, mainline_only = False):

16

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

17

18

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

19

* line_graph is a list of tuples of (revid,

20

node,

21

lines,

22

parents,

23

children,

24

revno_sequence),

25

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

26

the value the row index, and

27

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

28

29

30

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

31

column number of the graph that this revision represents and colour

32

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

33

in particular) to draw the node in.

34

35

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

36

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

37

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

38

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

39

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

40

41

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

42

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

43

"""

44

45

graph_parents = repository.get_revision_graph(start)

46

graph_children = {}

47

for revid in graph_parents.iterkeys():

48

graph_children[revid] = []

49

50

if len(graph_parents)>0:

51

merge_sorted_revisions = merge_sort(

52

graph_parents,

53

start,

54

generate_revno=True)

55

else:

56

merge_sorted_revisions = ()

57

58

if mainline_only:

59

merge_sorted_revisions = [elem for elem in merge_sorted_revisions \

60

if len(elem[3])==1 ]

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

85

parents = graph_parents[revid]

86

for parent_revid in parents:

87

graph_children[parent_revid].append(revid)

88

89

linegraph.append([revid,

90

None,

91

[],

92

parents,

93

None,

94

revno_sequence])

95

96

if graph_data:

97

revno_index[revno_sequence] = rev_index

98

99

branch_id = revno_sequence[0:-1]

100

101

branch_line = None

102

if branch_id not in branch_lines:

103

branch_line = []

104

branch_lines[branch_id] = branch_line

105

else:

106

branch_line = branch_lines[branch_id]

107

108

branch_line.append(rev_index)

109

110

if graph_data:

111

branch_ids = branch_lines.keys()

112

113

def branch_id_cmp(x, y):

114

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

115

by their value"""

116

len_x = len(x)

117

len_y = len(y)

118

if len_x == len_y:

119

return -cmp(x, y)

120

return cmp(len_x, len_y)

121

122

branch_ids.sort(branch_id_cmp)

123

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

124

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

125

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

126

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

127

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

128

lines = []

129

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

130

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

131

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

132

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

133

columns = [list(empty_column)]

134

135

136

for branch_id in branch_ids:

137

branch_line = branch_lines[branch_id]

138

139

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

140

# starting point when looking for a free column.

141

parent_col_index = 0

142

parent_index = None

143

if len(branch_id) > 1:

144

parent_revno = branch_id[0:-1]

145

if parent_revno in revno_index:

146

parent_index = revno_index[parent_revno]

147

parent_node = linegraph[parent_index][1]

148

if parent_node:

149

parent_col_index = parent_node[0]

150

151

152

col_search_order = _branch_line_col_search_order(columns,

153

parent_col_index)

154

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

155

cur_cont_line = []

156

157

line_range = []

158

last_rev_index = None

159

for rev_index in branch_line:

160

if last_rev_index:

161

if broken_line_length and \

162

rev_index - last_rev_index > broken_line_length:

163

line_range.append(last_rev_index+1)

164

line_range.append(rev_index-1)

165

else:

166

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

167

168

line_range.append(rev_index)

169

last_rev_index = rev_index

170

171

if parent_index:

172

if broken_line_length and \

173

parent_index - last_rev_index > broken_line_length:

174

line_range.append(last_rev_index+1)

175

else:

176

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

177

178

col_index = _find_free_column(columns,

179

empty_column,

180

col_search_order,

181

line_range)

182

node = (col_index, color)

183

for rev_index in branch_line:

184

linegraph[rev_index][1] = node

185

columns[col_index][rev_index] = True

186

187

for rev_index in branch_line:

188

(sequence_number,

189

revid,

190

merge_depth,

191

revno_sequence,

192

end_of_merge) = merge_sorted_revisions[rev_index]

193

194

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

195

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

196

197

for parent_revid in graph_parents[revid]:

198

if parent_revid in revid_index:

199

200

parent_index = revid_index[parent_revid]

201

parent_node = linegraph[parent_index][1]

202

if parent_node:

203

parent_col_index = parent_node[0]

204

else:

205

parent_col_index = None

206

col_search_order = \

207

_line_col_search_order(columns,

208

parent_col_index,

209

col_index)

210

211

# If this line is really long, break it.

212

if len(branch_id) > 0 and \

213

broken_line_length and \

214

parent_index - rev_index > broken_line_length:

215

child_line_col_index = \

216

_find_free_column(columns,

217

empty_column,

218

col_search_order,

219

(rev_index + 1,))

220

_mark_column_as_used(columns,

221

child_line_col_index,

222

(rev_index + 1,))

223

224

# Recall _line_col_search_order to reset it back to

225

# the beging.

226

col_search_order = \

227

_line_col_search_order(columns,

228

parent_col_index,

229

col_index)

230

parent_col_line_index = \

231

_find_free_column(columns,

232

empty_column,

233

col_search_order,

234

(parent_index - 1,))

235

_mark_column_as_used(columns,

236

parent_col_line_index,

237

(parent_index - 1,))

238

lines.append((rev_index,

239

parent_index,

240

(child_line_col_index,

241

parent_col_line_index)))

242

else :

243

line_col_index = col_index

244

if parent_index - rev_index >1:

245

line_range = range(rev_index + 1, parent_index)

246

line_col_index = \

247

_find_free_column(columns,

248

empty_column,

249

col_search_order,

250

line_range)

251

_mark_column_as_used(columns,

252

line_col_index,

253

line_range)

254

lines.append((rev_index,

255

parent_index,

256

(line_col_index,)))

257

258

for (child_index, parent_index, line_col_indexes) in lines:

259

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

260

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

261

262

if len(line_col_indexes) == 1:

263

if parent_index - child_index == 1:

264

linegraph[child_index][2].append(

265

(child_col_index,

266

parent_col_index,

267

parent_color))

268

else:

269

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

270

linegraph[child_index][2].append(

271

(child_col_index,

272

line_col_indexes[0],

273

parent_color))

274

# lines down the line's column

275

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

276

linegraph[line_part_index][2].append(

277

(line_col_indexes[0],

278

line_col_indexes[0],

279

parent_color))

280

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

281

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

282

(line_col_indexes[0],

283

parent_col_index,

284

parent_color))

285

else:

286

# Broken line

287

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

288

linegraph[child_index][2].append(

289

(child_col_index,

290

line_col_indexes[0],

291

parent_color))

292

# Broken line end

293

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

294

(line_col_indexes[0],

295

None,

296

parent_color))

297

298

# Broken line end

299

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

300

(None,

301

line_col_indexes[1],

302

parent_color))

303

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

304

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

305

(line_col_indexes[1],

306

parent_col_index,

307

parent_color))

308

return (linegraph, revid_index, len(columns))

309

else:

310

return (linegraph, revid_index, 0)

311

312

313

def _branch_line_col_search_order(columns, parent_col_index):

314

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

315

yield col_index

316

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

317

yield col_index

318

319

def _line_col_search_order(columns, parent_col_index, child_col_index):

320

if parent_col_index is not None:

321

max_index = max(parent_col_index, child_col_index)

322

min_index = min(parent_col_index, child_col_index)

323

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

324

yield col_index

325

else:

326

max_index = child_col_index

327

min_index = child_col_index

328

yield child_col_index

329

i = 1

330

while max_index + i < len(columns) or \

331

min_index - i > -1:

332

if max_index + i < len(columns):

333

yield max_index + i

334

if min_index - i > -1:

335

yield min_index - i

336

i += 1

337

338

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

339

for col_index in col_search_order:

340

column = columns[col_index]

341

has_overlaping_line = False

342

for row_index in line_range:

343

if column[row_index]:

344

has_overlaping_line = True

345

break

346

if not has_overlaping_line:

347

break

348

else:

349

col_index = len(columns)

350

column = list(empty_column)

351

columns.append(column)

352

return col_index

353

354

def _mark_column_as_used(columns, col_index, line_range):

355

column = columns[col_index]

356

for row_index in line_range:

357

column[row_index] = True

358

359

def same_branch(a, b):

360

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

361

if len(a.parent_ids) == 1:

362

# Defacto same branch if only parent

363

return True

364

elif a.committer == b.committer:

365

# Same committer so may as well be

366

return True

367

else:

368

return False