~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/revision.py

• browse files at revision 1553.5.82
• compare with another revision
• compare with revision 1553.5.82
• download diff
• download tarball
• view history from revision 1553.5.82

Show diffs side-by-side

added

removed

bzrlib/revision.py

17

17

# TODO: Some kind of command-line display of revision properties: 

18

18

# perhaps show them in log -v and allow them as options to the commit command.

19

19

 

 

20

 

20

21

import bzrlib.errors

 

22

import bzrlib.errors as errors

21

23

from bzrlib.graph import node_distances, select_farthest, all_descendants

22

24

from bzrlib.osutils import contains_whitespace

23

25

from bzrlib.progress import DummyProgress

160

162

 

161

163

def revision_graph(revision, revision_source):

162

164

    """Produce a graph of the ancestry of the specified revision.

163

 

    Return root, ancestors map, descendants map

164

 

 

165

 

    TODO: Produce graphs with the NULL revision as root, so that we can find

166

 

    a common even when trees are not branches don't represent a single line

167

 

    of descent.

168

 

    RBC: 20051024: note that when we have two partial histories, this may not

169

 

         be possible. But if we are willing to pretend :)... sure.

 

165

    

 

166

    :return: root, ancestors map, descendants map

170

167

    """

171

168

    revision_source.lock_read()

172

169

    try:

174

171

    finally:

175

172

        revision_source.unlock()

176

173

 

 

174

 

177

175

def _revision_graph(revision, revision_source):

178

176

    """See revision_graph."""

 

177

    from bzrlib.tsort import topo_sort

 

178

    graph = revision_source.get_revision_graph(revision)

 

179

    # mark all no-parent revisions as being NULL_REVISION parentage.

 

180

    for node, parents in graph.items():

 

181

        if len(parents) == 0:

 

182

            graph[node] = [NULL_REVISION]

 

183

    # add NULL_REVISION to the graph

 

184

    graph[NULL_REVISION] = []

 

185

 

 

186

    # pick a root. If there are multiple roots

 

187

    # this could pick a random one.

 

188

    topo_order = topo_sort(graph.items())

 

189

    root = topo_order[0]

 

190

 

179

191

    ancestors = {}

180

192

    descendants = {}

181

 

    lines = [revision]

182

 

    root = None

183

 

    descendants[revision] = {}

184

 

    while len(lines) > 0:

185

 

        new_lines = set()

186

 

        for line in lines:

187

 

            if line == NULL_REVISION:

188

 

                parents = []

189

 

                root = NULL_REVISION

190

 

            else:

191

 

                try:

192

 

                    rev = revision_source.get_revision(line)

193

 

                    parents = list(rev.parent_ids)

194

 

                    if len(parents) == 0:

195

 

                        parents = [NULL_REVISION]

196

 

                except bzrlib.errors.NoSuchRevision:

197

 

                    if line == revision:

198

 

                        raise

199

 

                    parents = None

200

 

            if parents is not None:

201

 

                for parent in parents:

202

 

                    if parent not in ancestors:

203

 

                        new_lines.add(parent)

204

 

                    if parent not in descendants:

205

 

                        descendants[parent] = {}

206

 

                    descendants[parent][line] = 1

207

 

            if parents is not None:

208

 

                ancestors[line] = set(parents)

209

 

        lines = new_lines

210

 

    if root is None:

211

 

        # The history for revision becomes inaccessible without

212

 

        # actually hitting a no-parents revision. This then

213

 

        # makes these asserts below trigger. So, if root is None

214

 

        # determine the actual root by walking the accessible tree

215

 

        # and then stash NULL_REVISION at the end.

216

 

        root = NULL_REVISION

217

 

        descendants[root] = {}

218

 

        # for every revision, check we can access at least

219

 

        # one parent, if we cant, add NULL_REVISION and

220

 

        # a link

221

 

        for rev in ancestors:

222

 

            if len(ancestors[rev]) == 0:

223

 

                raise RuntimeError('unreachable code ?!')

224

 

            ok = False

225

 

            for parent in ancestors[rev]:

226

 

                if parent in ancestors:

227

 

                    ok = True

228

 

            if ok:

229

 

                continue

230

 

            descendants[root][rev] = 1

231

 

            ancestors[rev].add(root)

232

 

        ancestors[root] = set()

 

193

 

 

194

    # map the descendants of the graph.

 

195

    # and setup our set based return graph.

 

196

    for node in graph.keys():

 

197

        descendants[node] = {}

 

198

    for node, parents in graph.items():

 

199

        for parent in parents:

 

200

            descendants[parent][node] = 1

 

201

        ancestors[node] = set(parents)

 

202

 

233

203

    assert root not in descendants[root]

234

204

    assert root not in ancestors[root]

235

205

    return root, ancestors, descendants

238

208

def combined_graph(revision_a, revision_b, revision_source):

239

209

    """Produce a combined ancestry graph.

240

210

    Return graph root, ancestors map, descendants map, set of common nodes"""

241

 

    root, ancestors, descendants = revision_graph(revision_a, revision_source)

242

 

    root_b, ancestors_b, descendants_b = revision_graph(revision_b, 

243

 

                                                        revision_source)

 

211

    root, ancestors, descendants = revision_graph(

 

212

        revision_a, revision_source)

 

213

    root_b, ancestors_b, descendants_b = revision_graph(

 

214

        revision_b, revision_source)

244

215

    if root != root_b:

245

216

        raise bzrlib.errors.NoCommonRoot(revision_a, revision_b)

246

217

    common = set()

265

236

        try:

266

237

            pb.update('Picking ancestor', 1, 3)

267

238

            root, ancestors, descendants, common = \

268

 

                combined_graph(revision_a, revision_b, revision_source)

 

239

                combined_graph(revision_a,

 

240

                               revision_b,

 

241

                               revision_source)

269

242

        except bzrlib.errors.NoCommonRoot:

270

243

            raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)

271

244

            

287

260

        assert len(args) != 0

288

261

        self._revision_sources = args

289

262

 

 

263

    def revision_parents(self, revision_id):

 

264

        for source in self._revision_sources:

 

265

            try:

 

266

                return source.revision_parents(revision_id)

 

267

            except (errors.WeaveRevisionNotPresent, errors.NoSuchRevision), e:

 

268

                pass

 

269

        raise e

 

270

 

290

271

    def get_revision(self, revision_id):

291

272

        for source in self._revision_sources:

292

273

            try:

295

276

                pass

296

277

        raise e

297

278

 

 

279

    def get_revision_graph(self, revision_id):

 

280

        # we could probe incrementally until the pending

 

281

        # ghosts list stop growing, but its cheaper for now

 

282

        # to just ask for the complete graph for each repository.

 

283

        graphs = []

 

284

        for source in self._revision_sources:

 

285

            ghost_graph = source.get_revision_graph_with_ghosts()

 

286

            graphs.append(ghost_graph)

 

287

        absent = 0

 

288

        for graph in graphs:

 

289

            if not revision_id in graph.get_ancestors():

 

290

                absent += 1

 

291

        if absent == len(graphs):

 

292

            raise errors.NoSuchRevision(self._revision_sources[0], revision_id)

 

293

 

 

294

        # combine the graphs

 

295

        result = {}

 

296

        pending = set([revision_id])

 

297

        def find_parents(node_id):

 

298

            """find the parents for node_id."""

 

299

            for graph in graphs:

 

300

                ancestors = graph.get_ancestors()

 

301

                try:

 

302

                    return ancestors[node_id]

 

303

                except KeyError:

 

304

                    pass

 

305

            raise errors.NoSuchRevision(self._revision_sources[0], node_id)

 

306

        while len(pending):

 

307

            # all the graphs should have identical parent lists

 

308

            node_id = pending.pop()

 

309

            try:

 

310

                result[node_id] = find_parents(node_id)

 

311

                for parent_node in result[node_id]:

 

312

                    if not parent_node in result:

 

313

                        pending.add(parent_node)

 

314

            except errors.NoSuchRevision:

 

315

                # ghost, ignore it.

 

316

                pass

 

317

        return result

 

318

 

298

319

    def lock_read(self):

299

320

        for source in self._revision_sources:

300

321

            source.lock_read()

303

324

        for source in self._revision_sources:

304

325

            source.unlock()

305

326

 

 

327

 

306

328

def get_intervening_revisions(ancestor_id, rev_id, rev_source, 

307

329

                              revision_history=None):

308

330

    """Find the longest line of descent from maybe_ancestor to revision.

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1