addons/isl/src/dag/dag.tsblame
View source
b69ab311/**
b69ab312 * Copyright (c) Meta Platforms, Inc. and affiliates.
b69ab313 *
b69ab314 * This source code is licensed under the MIT license found in the
b69ab315 * LICENSE file in the root directory of this source tree.
b69ab316 */
b69ab317
b69ab318import type {RecordOf} from 'immutable';
b69ab319import type {Hash} from '../types';
b69ab3110import type {ExtendedGraphRow} from './render';
b69ab3111import type {SetLike} from './set';
b69ab3112
b69ab3113import {Map as ImMap, Set as ImSet, List, Record} from 'immutable';
b69ab3114import {cachedMethod, LRU} from 'shared/LRU';
b69ab3115import {SelfUpdate} from 'shared/immutableExt';
b69ab3116import {group, notEmpty, nullthrows, splitOnce} from 'shared/utils';
b69ab3117import {CommitPreview} from '../previews';
b69ab3118import {BaseDag, type SortProps} from './base_dag';
b69ab3119import {DagCommitInfo} from './dagCommitInfo';
b69ab3120import {MutationDag} from './mutation_dag';
b69ab3121import {Ancestor, AncestorType, Renderer} from './render';
b69ab3122import {TextRenderer} from './renderText';
b69ab3123import {arrayFromHashes, HashSet} from './set';
b69ab3124
b69ab3125/**
b69ab3126 * Main commit graph type used for preview calculation and queries.
b69ab3127 *
b69ab3128 * See `BaseDag` docstring for differences with a traditional source
b69ab3129 * control dag.
b69ab3130 *
b69ab3131 * A commit is associated with the `Info` type. This enables the class
b69ab3132 * to provide features not existed in `BaseDag`, like:
b69ab3133 * - Lookup by name (bookmark, '.', etc) via resolve().
b69ab3134 * - Phase related queries like public() and draft().
b69ab3135 * - Mutation related queries like obsolete().
b69ab3136 * - High-level operations like rebase(), cleanup().
b69ab3137 */
b69ab3138export class Dag extends SelfUpdate<CommitDagRecord> {
b69ab3139 constructor(record?: CommitDagRecord) {
b69ab3140 super(record ?? EMPTY_DAG_RECORD);
b69ab3141 }
b69ab3142
b69ab3143 static fromDag(commitDag?: BaseDag<DagCommitInfo>, mutationDag?: MutationDag): Dag {
b69ab3144 return new Dag(CommitDagRecord({commitDag, mutationDag}));
b69ab3145 }
b69ab3146
b69ab3147 // Delegates
b69ab3148
b69ab3149 get commitDag(): BaseDag<DagCommitInfo> {
b69ab3150 return this.inner.commitDag;
b69ab3151 }
b69ab3152
b69ab3153 get mutationDag(): MutationDag {
b69ab3154 return this.inner.mutationDag;
b69ab3155 }
b69ab3156
b69ab3157 private withCommitDag(f: (dag: BaseDag<DagCommitInfo>) => BaseDag<DagCommitInfo>): Dag {
b69ab3158 const newCommitDag = f(this.commitDag);
b69ab3159 const newRecord = this.inner.set('commitDag', newCommitDag);
b69ab3160 return new Dag(newRecord);
b69ab3161 }
b69ab3162
b69ab3163 // Basic edit
b69ab3164
b69ab3165 add(commits: Iterable<DagCommitInfo>): Dag {
b69ab3166 // When adding commits, also update the mutationDag.
b69ab3167 const seqNumber = this.inner.nextSeqNumber;
b69ab3168 const commitArray = [...commits].map(c =>
b69ab3169 c
b69ab3170 // Assign `seqNumber` (insertion order) to help sorting commits later.
b69ab3171 // The seqNumber is the same for all `commits` so the order does not matter.
b69ab3172 .set('seqNumber', c.seqNumber ?? seqNumber)
b69ab3173 // Extend `parents` for dagwalkerForRendering to properly connect public commits
b69ab3174 .set('parents', [...c.parents, ...c.grandparents])
b69ab3175 // Assign `ancestors` for dagWalkerForRendering to connect public commits properly
b69ab3176 .set('ancestors', c.grandparents.length > 0 ? List(c.grandparents) : c.ancestors),
b69ab3177 );
b69ab3178 const oldNewPairs = new Array<[Hash, Hash]>();
b69ab3179 for (const info of commitArray) {
b69ab3180 info.closestPredecessors?.forEach(p => oldNewPairs.push([p, info.hash]));
b69ab3181 if (info.successorInfo != null) {
b69ab3182 oldNewPairs.push([info.hash, info.successorInfo.hash]);
b69ab3183 }
b69ab3184 }
b69ab3185
b69ab3186 // Update nameMap.
b69ab3187 const toDelete = commitArray.map(c => this.get(c.hash)).filter(notEmpty);
b69ab3188 const nameMap = calculateNewNameMap(this.inner.nameMap, toDelete, commitArray);
b69ab3189
b69ab3190 // Update other fields.
b69ab3191 const commitDag = this.commitDag.add(commitArray);
b69ab3192 const mutationDag = this.mutationDag.addMutations(oldNewPairs);
b69ab3193 const nextSeqNumber = seqNumber + 1;
b69ab3194 const record = this.inner.merge({
b69ab3195 commitDag,
b69ab3196 mutationDag,
b69ab3197 nameMap,
b69ab3198 nextSeqNumber,
b69ab3199 });
b69ab31100 return new Dag(record);
b69ab31101 }
b69ab31102
b69ab31103 /** See MutationDag.addMutations. */
b69ab31104 addMutations(oldNewPairs: Iterable<[Hash, Hash]>): Dag {
b69ab31105 const newMutationDag = this.mutationDag.addMutations(oldNewPairs);
b69ab31106 const newRecord = this.inner.set('mutationDag', newMutationDag);
b69ab31107 return new Dag(newRecord);
b69ab31108 }
b69ab31109
b69ab31110 remove(set: SetLike): Dag {
b69ab31111 // When removing commits, don't remove them from the mutationDag intentionally.
b69ab31112 const hashSet = HashSet.fromHashes(set);
b69ab31113 const toDelete = this.getBatch(hashSet.toArray());
b69ab31114 const nameMap = calculateNewNameMap(this.inner.nameMap, toDelete, []);
b69ab31115 const commitDag = this.commitDag.remove(hashSet);
b69ab31116 const record = this.inner.merge({
b69ab31117 commitDag,
b69ab31118 nameMap,
b69ab31119 });
b69ab31120 return new Dag(record);
b69ab31121 }
b69ab31122
b69ab31123 /** A callback form of remove() and add(). */
b69ab31124 replaceWith(
b69ab31125 set: SetLike,
b69ab31126 replaceFunc: (h: Hash, c?: DagCommitInfo) => DagCommitInfo | undefined,
b69ab31127 ): Dag {
b69ab31128 const hashSet = HashSet.fromHashes(set);
b69ab31129 const hashes = hashSet.toHashes();
b69ab31130 return this.remove(this.present(set)).add(
b69ab31131 hashes
b69ab31132 .map(h => replaceFunc(h, this.get(h)))
b69ab31133 .filter(c => c != undefined) as Iterable<DagCommitInfo>,
b69ab31134 );
b69ab31135 }
b69ab31136
b69ab31137 // Basic query
b69ab31138
b69ab31139 get(hash: Hash | undefined | null): DagCommitInfo | undefined {
b69ab31140 return this.commitDag.get(hash);
b69ab31141 }
b69ab31142
b69ab31143 getBatch(hashes: Array<Hash>): Array<DagCommitInfo> {
b69ab31144 return hashes.map(h => this.get(h)).filter(notEmpty);
b69ab31145 }
b69ab31146
b69ab31147 has(hash: Hash | undefined | null): boolean {
b69ab31148 return this.commitDag.has(hash);
b69ab31149 }
b69ab31150
b69ab31151 [Symbol.iterator](): IterableIterator<Hash> {
b69ab31152 return this.commitDag[Symbol.iterator]();
b69ab31153 }
b69ab31154
b69ab31155 values(): Iterable<Readonly<DagCommitInfo>> {
b69ab31156 return this.commitDag.values();
b69ab31157 }
b69ab31158
b69ab31159 parentHashes(hash: Hash): Readonly<Hash[]> {
b69ab31160 return this.commitDag.parentHashes(hash);
b69ab31161 }
b69ab31162
b69ab31163 childHashes(hash: Hash): List<Hash> {
b69ab31164 return this.commitDag.childHashes(hash);
b69ab31165 }
b69ab31166
b69ab31167 // High-level query
b69ab31168
b69ab31169 /** Return hashes present in this dag. */
b69ab31170 present(set: SetLike): HashSet {
b69ab31171 return this.commitDag.present(set);
b69ab31172 }
b69ab31173
b69ab31174 parents(set: SetLike): HashSet {
b69ab31175 return this.commitDag.parents(set);
b69ab31176 }
b69ab31177
b69ab31178 children(set: SetLike): HashSet {
b69ab31179 return this.commitDag.children(set);
b69ab31180 }
b69ab31181
b69ab31182 ancestors(set: SetLike, props?: {within?: SetLike}): HashSet {
b69ab31183 return this.commitDag.ancestors(set, props);
b69ab31184 }
b69ab31185
b69ab31186 descendants(set: SetLike, props?: {within?: SetLike}): HashSet {
b69ab31187 return this.commitDag.descendants(set, props);
b69ab31188 }
b69ab31189
b69ab31190 range(roots: SetLike, heads: SetLike): HashSet {
b69ab31191 return this.commitDag.range(roots, heads);
b69ab31192 }
b69ab31193
b69ab31194 roots = cachedMethod(this.rootsImpl, {cache: rootsCache});
b69ab31195 private rootsImpl(set: SetLike): HashSet {
b69ab31196 return this.commitDag.roots(set);
b69ab31197 }
b69ab31198
b69ab31199 heads = cachedMethod(this.headsImpl, {cache: headsCache});
b69ab31200 private headsImpl(set: SetLike): HashSet {
b69ab31201 return this.commitDag.heads(set);
b69ab31202 }
b69ab31203
b69ab31204 gca(set1: SetLike, set2: SetLike): HashSet {
b69ab31205 return this.commitDag.gca(set1, set2);
b69ab31206 }
b69ab31207
b69ab31208 isAncestor(ancestor: Hash, descendant: Hash): boolean {
b69ab31209 return this.commitDag.isAncestor(ancestor, descendant);
b69ab31210 }
b69ab31211
b69ab31212 filter(predicate: (commit: Readonly<DagCommitInfo>) => boolean, set?: SetLike): HashSet {
b69ab31213 return this.commitDag.filter(predicate, set);
b69ab31214 }
b69ab31215
b69ab31216 all = cachedMethod(this.allImpl, {cache: allCache});
b69ab31217 private allImpl(): HashSet {
b69ab31218 return HashSet.fromHashes(this);
b69ab31219 }
b69ab31220
b69ab31221 /**
b69ab31222 * Return a subset suitable for rendering. This filters out:
b69ab31223 * - Obsoleted stack. Only roots(obsolete()), heads(obsolete()), and
b69ab31224 * parents(draft()) are kept.
b69ab31225 * - Unnamed public commits that do not have direct draft children.
b69ab31226 */
b69ab31227 subsetForRendering = cachedMethod(this.subsetForRenderingImpl, {cache: subsetForRenderingCache});
b69ab31228 private subsetForRenderingImpl(set?: SetLike, condenseObsoleteStacks: boolean = true): HashSet {
b69ab31229 const all = set === undefined ? this.all() : HashSet.fromHashes(set);
b69ab31230 const draft = this.draft(all);
b69ab31231 const unnamedPublic = this.filter(
b69ab31232 i =>
b69ab31233 i.phase === 'public' &&
b69ab31234 i.remoteBookmarks.length === 0 &&
b69ab31235 i.bookmarks.length === 0 &&
b69ab31236 (i.stableCommitMetadata == null || i.stableCommitMetadata.length === 0) &&
b69ab31237 !i.isDot,
b69ab31238 all,
b69ab31239 );
ab83ad3240 const dot = this.resolve('.');
ab83ad3241 const dotAncestors = dot != null ? this.ancestors(HashSet.fromHashes([dot.hash])) : HashSet.fromHashes([]);
ab83ad3242 const toHidePublic = unnamedPublic.subtract(this.parents(draft)).subtract(dotAncestors);
b69ab31243 let toHide = toHidePublic;
b69ab31244 if (condenseObsoleteStacks) {
b69ab31245 const obsolete = this.obsolete(all);
b69ab31246 const toKeep = this.parents(draft.subtract(obsolete))
b69ab31247 .union(this.roots(obsolete))
b69ab31248 .union(this.heads(obsolete));
b69ab31249 toHide = obsolete.subtract(toKeep).union(toHidePublic);
b69ab31250 }
b69ab31251 return all.subtract(toHide);
b69ab31252 }
b69ab31253
b69ab31254 // Sort
b69ab31255
b69ab31256 /**
b69ab31257 * sortAsc all commits, with the default compare function.
b69ab31258 * Return `[map, array]`. The array is the sorted hashes.
b69ab31259 * The map provides look-up from hash to array index. `map.get(h)` is `array.indexOf(h)`.
b69ab31260 */
b69ab31261 defaultSortAscIndex = cachedMethod(this.defaultSortAscIndexImpl, {
b69ab31262 cache: defaultSortAscIndexCache,
b69ab31263 });
b69ab31264 private defaultSortAscIndexImpl(): [ReadonlyMap<Hash, number>, ReadonlyArray<Hash>] {
b69ab31265 const sorted = this.commitDag.sortAsc(this.all(), {compare: sortAscCompare, gap: false});
b69ab31266 const index = new Map(sorted.map((h, i) => [h, i]));
b69ab31267 return [index, sorted];
b69ab31268 }
b69ab31269
b69ab31270 sortAsc(set: SetLike, props?: SortProps<DagCommitInfo>): Array<Hash> {
b69ab31271 if (props?.compare == null) {
b69ab31272 // If no custom compare function, use the sortAsc index to answer subset
b69ab31273 // sortAsc, which can be slow to calculate otherwise.
b69ab31274 const [index, sorted] = this.defaultSortAscIndex();
b69ab31275 if (set === undefined) {
b69ab31276 return [...sorted];
b69ab31277 }
b69ab31278 const hashes = arrayFromHashes(set === undefined ? this.all() : set);
b69ab31279 return hashes.sort((a, b) => {
b69ab31280 const aIdx = index.get(a);
b69ab31281 const bIdx = index.get(b);
b69ab31282 if (aIdx == null || bIdx == null) {
b69ab31283 throw new Error(`Commit ${a} or ${b} is not in the dag.`);
b69ab31284 }
b69ab31285 return aIdx - bIdx;
b69ab31286 });
b69ab31287 }
b69ab31288 // Otherwise, fallback to sortAsc.
b69ab31289 return this.commitDag.sortAsc(set, {compare: sortAscCompare, ...props});
b69ab31290 }
b69ab31291
b69ab31292 sortDesc(set: SetLike, props?: SortProps<DagCommitInfo>): Array<Hash> {
b69ab31293 return this.commitDag.sortDesc(set, props);
b69ab31294 }
b69ab31295
b69ab31296 // Filters
b69ab31297
b69ab31298 obsolete(set?: SetLike): HashSet {
b69ab31299 return this.filter(c => c.successorInfo != null, set);
b69ab31300 }
b69ab31301
b69ab31302 nonObsolete(set?: SetLike): HashSet {
b69ab31303 return this.filter(c => c.successorInfo == null, set);
b69ab31304 }
b69ab31305
b69ab31306 public_(set?: SetLike): HashSet {
b69ab31307 return this.filter(c => c.phase === 'public', set);
b69ab31308 }
b69ab31309
b69ab31310 draft(set?: SetLike): HashSet {
b69ab31311 return this.filter(c => (c.phase ?? 'draft') === 'draft', set);
b69ab31312 }
b69ab31313
b69ab31314 merge(set?: SetLike): HashSet {
b69ab31315 return this.commitDag.merge(set);
b69ab31316 }
b69ab31317
b69ab31318 // Edit APIs that are less generic, require `C` to be `CommitInfo`.
b69ab31319
b69ab31320 /** Bump the timestamp of descendants(set) to "now". */
b69ab31321 touch(set: SetLike, includeDescendants = true): Dag {
b69ab31322 const affected = includeDescendants ? this.descendants(set) : set;
b69ab31323 const now = new Date();
b69ab31324 return this.replaceWith(affected, (_h, c) => c?.set('date', now));
b69ab31325 }
b69ab31326
b69ab31327 /**
b69ab31328 * Remove obsoleted commits that no longer have non-obsoleted descendants.
b69ab31329 * If `startHeads` is not set, scan all obsoleted draft heads. Otherwise,
b69ab31330 * limit the scan to the given heads.
b69ab31331 */
b69ab31332 cleanup(startHeads?: SetLike): Dag {
b69ab31333 // ancestors(".") are not obsoleted.
b69ab31334 const obsolete = this.obsolete().subtract(this.ancestors(this.resolve('.')?.hash));
b69ab31335 // Don't trust `startHeads` as obsoleted draft heads, so we calculate it anyway.
b69ab31336 let heads = this.heads(this.draft()).intersect(obsolete);
b69ab31337 if (startHeads !== undefined) {
b69ab31338 heads = heads.intersect(HashSet.fromHashes(startHeads));
b69ab31339 }
b69ab31340 const toRemove = this.ancestors(heads, {within: obsolete});
b69ab31341 return this.remove(toRemove);
b69ab31342 }
b69ab31343
b69ab31344 /**
b69ab31345 * Attempt to rebase `srcSet` to `dest` for preview use-case.
b69ab31346 * Handles case that produces "orphaned" or "obsoleted" commits.
b69ab31347 * Does not handle:
b69ab31348 * - copy 'x amended to y' relation when x and y are both being rebased.
b69ab31349 * - skip rebasing 'x' if 'x amended to y' and 'y in ancestors(dest)'.
b69ab31350 */
b69ab31351 rebase(srcSet: SetLike, dest: Hash | undefined): Dag {
b69ab31352 let src = HashSet.fromHashes(srcSet);
b69ab31353 // x is already rebased, if x's parent is dest or 'already rebased'.
b69ab31354 // dest--a--b--c--d--e: when rebasing a+b+d+e to dest, only a+b are already rebased.
b69ab31355 const alreadyRebased = this.descendants(dest, {within: src});
b69ab31356 // Skip already rebased, and skip non-draft commits.
b69ab31357 src = this.draft(src.subtract(alreadyRebased));
b69ab31358 // Nothing to rebase?
b69ab31359 if (dest == null || src.size === 0) {
b69ab31360 return this;
b69ab31361 }
b69ab31362 // Rebase is not simply moving `roots(src)` to `dest`. Consider graph 'a--b--c--d',
b69ab31363 // 'rebase -r a+b+d -d dest' produces 'dest--a--b--d' and 'a(obsoleted)--b(obsoleted)--c':
b69ab31364 // - The new parent of 'd' is 'b', not 'dest'.
b69ab31365 // - 'a' and 'b' got duplicated.
b69ab31366 const srcRoots = this.roots(src); // a, d
b69ab31367 const orphaned = this.range(src, this.draft()).subtract(src); // c
b69ab31368 const duplicated = this.ancestors(orphaned).intersect(src); // a, b
b69ab31369 const maybeSuccHash = (h: Hash) => (duplicated.contains(h) ? `${REBASE_SUCC_PREFIX}${h}` : h);
b69ab31370 const date = new Date();
b69ab31371 const newParents = (h: Hash): Hash[] => {
b69ab31372 const directParents = this.parents(h);
b69ab31373 let parents = directParents.intersect(src);
b69ab31374 if (parents.size === 0) {
b69ab31375 parents = this.heads(this.ancestors(directParents).intersect(src));
b69ab31376 }
b69ab31377 return parents.size === 0 ? [dest] : parents.toHashes().map(maybeSuccHash).toArray();
b69ab31378 };
b69ab31379 const toCleanup = this.parents(srcRoots);
b69ab31380 return this.replaceWith(src.union(duplicated.toHashes().map(maybeSuccHash)), (h, c) => {
b69ab31381 const isSucc = h.startsWith(REBASE_SUCC_PREFIX);
b69ab31382 const pureHash = isSucc ? h.substring(REBASE_SUCC_PREFIX.length) : h;
b69ab31383 const isPred = !isSucc && duplicated.contains(h);
b69ab31384 const isRoot = srcRoots.contains(pureHash);
b69ab31385 const info = nullthrows(isSucc ? this.get(pureHash) : c);
b69ab31386 return info.withMutations(mut => {
b69ab31387 // Reset the seqNumber so the rebase preview tends to show as right-most branches.
b69ab31388 let newInfo = mut.set('seqNumber', undefined);
b69ab31389 if (isPred) {
b69ab31390 // For "predecessors" (ex. a(obsoleted)), keep hash unchanged
b69ab31391 // so orphaned commits (c) don't move. Update successorInfo.
b69ab31392 const succHash = maybeSuccHash(pureHash);
b69ab31393 newInfo = newInfo.set('successorInfo', {hash: succHash, type: 'rebase'});
b69ab31394 } else {
b69ab31395 // Set date, parents, previewType.
b69ab31396 newInfo = newInfo.merge({
b69ab31397 date,
b69ab31398 parents: newParents(pureHash),
b69ab31399 previewType: isRoot
b69ab31400 ? CommitPreview.REBASE_OPTIMISTIC_ROOT
b69ab31401 : CommitPreview.REBASE_OPTIMISTIC_DESCENDANT,
b69ab31402 });
b69ab31403 // Set predecessor info for successors.
b69ab31404 if (isSucc) {
b69ab31405 newInfo = newInfo.merge({
b69ab31406 closestPredecessors: [pureHash],
b69ab31407 hash: h,
b69ab31408 });
b69ab31409 }
b69ab31410 }
b69ab31411 return newInfo;
b69ab31412 });
b69ab31413 }).cleanup(toCleanup);
b69ab31414 }
b69ab31415
b69ab31416 /**
b69ab31417 * Force the disconnected public commits to be connected to each other
b69ab31418 * in chronological order.
b69ab31419 *
b69ab31420 * This is "incorrect" but we don't get the info from `sl log` yet.
b69ab31421 *
b69ab31422 * Useful to reason about ancestry relations. For example, to filter
b69ab31423 * out rebase destinations (ex. remote/stable) that are backwards,
b69ab31424 * we want ancestors(rebase_src) to include public commits like
b69ab31425 * remote/stable.
b69ab31426 */
b69ab31427 private forceConnectPublic(): Dag {
b69ab31428 // Not all public commits need this "fix". Only consider the "roots".
b69ab31429 const toFix = this.roots(this.public_());
b69ab31430 const sorted = toFix
b69ab31431 .toList()
b69ab31432 .sortBy(h => this.get(h)?.date.valueOf() ?? 0)
b69ab31433 .toArray();
b69ab31434 const parentPairs: Array<[Hash, Hash]> = sorted.flatMap((h, i) =>
b69ab31435 i === 0 ? [] : [[h, sorted[i - 1]]],
b69ab31436 );
b69ab31437 const parentMap = new Map<Hash, Hash>(parentPairs);
b69ab31438 return this.replaceWith(toFix, (h, c) => {
b69ab31439 const newParent = parentMap.get(h);
b69ab31440 if (c == null || newParent == null) {
b69ab31441 return c;
b69ab31442 }
b69ab31443 return c.withMutations(m =>
b69ab31444 m.set('parents', [...c.parents, newParent]).set('ancestors', List([newParent])),
b69ab31445 );
b69ab31446 });
b69ab31447 }
b69ab31448
b69ab31449 /**
b69ab31450 * A backward compatible solution to connect public commits
b69ab31451 * using grandparents info from sapling.
b69ab31452 *
b69ab31453 * If an older version of sapling that doesn't support "grandparents"
b69ab31454 * is running, all the grandparents fields will be empty. Fallback
b69ab31455 * to chronological connections (forceConnectPublic) in this case.
b69ab31456 *
b69ab31457 * The function needs to be manually called to connect the nodes,
b69ab31458 * in order to work with forceConnectPublic() to ensure backward compatibility.
b69ab31459 * After the sapling patch gets fully released, we should consider consuming
b69ab31460 * "grandparents" naturally, without having to explicitly update other commit fields.
b69ab31461 */
b69ab31462 maybeForceConnectPublic(): Dag {
b69ab31463 const toConnect = this.roots(this.public_());
b69ab31464 for (const h of toConnect) {
b69ab31465 const c = this.get(h);
b69ab31466 if (c != null && c.grandparents.length > 0) {
b69ab31467 return this;
b69ab31468 }
b69ab31469 }
b69ab31470 return this.forceConnectPublic();
b69ab31471 }
b69ab31472
b69ab31473 // Query APIs that are less generic, require `C` to be `CommitInfo`.
b69ab31474
b69ab31475 /** All visible successors recursively, including `set`. */
b69ab31476 successors(set: SetLike): HashSet {
b69ab31477 return this.mutationDag.range(set, this);
b69ab31478 }
b69ab31479
b69ab31480 /** All visible predecessors of commits in `set`, including `set`. */
b69ab31481 predecessors(set: SetLike): HashSet {
b69ab31482 return this.present(this.mutationDag.ancestors(set));
b69ab31483 }
b69ab31484
b69ab31485 /**
b69ab31486 * Follow successors for the given set.
b69ab31487 *
b69ab31488 * - If a hash does not have successors in this `dag`, then this hash
b69ab31489 * will be included in the result.
b69ab31490 * - If a hash has multiple successors, only the "head" successor that
b69ab31491 * is also in this `dag` will be returned, the hash itself will be
b69ab31492 * excluded from the result.
b69ab31493 * - If `set` contains a hash that gets split into multiple successors
b69ab31494 * that heads(successors) on the mutation graph still contains multiple
b69ab31495 * commits, then heads(ancestors(successors)) on the main graph will
b69ab31496 * be attempted to pick the "stack top".
b69ab31497 *
b69ab31498 * For example, consider the successor relations:
b69ab31499 *
b69ab31500 * A-->A1-->A2-->A3
b69ab31501 *
b69ab31502 * and if the current graph only has 'A1', 'A2' and 'B'.
b69ab31503 * followSuccessors(['A', 'B']) will return ['A2', 'B'].
b69ab31504 * successors(['A', 'B']) will return ['A', 'A1', 'A2', 'B'].
b69ab31505 */
b69ab31506 followSuccessors(set: SetLike): HashSet {
b69ab31507 const hashSet = HashSet.fromHashes(set);
b69ab31508 const mDag = this.mutationDag;
b69ab31509 let successors = mDag.heads(mDag.range(hashSet, this));
b69ab31510 // When following a split to multiple successors, consider using
b69ab31511 // the main dag to pick the stack top.
b69ab31512 if (hashSet.size === 1 && successors.size > 1) {
b69ab31513 successors = this.heads(this.ancestors(successors));
b69ab31514 }
b69ab31515 const obsoleted = mDag.ancestors(mDag.parents(successors));
b69ab31516 return hashSet.subtract(obsoleted).union(successors);
b69ab31517 }
b69ab31518
b69ab31519 /** Attempt to resolve a name by `name`. The `name` can be a hash, a bookmark name, etc. */
b69ab31520 resolve(name: string): Readonly<DagCommitInfo> | undefined {
b69ab31521 // See `hg help revision` and context.py (changectx.__init__),
b69ab31522 // namespaces.py for priorities. Basically (in this order):
b69ab31523 // - hex full hash (40 bytes); '.' (working parent)
b69ab31524 // - nameMap (see infoToNameMapEntries)
b69ab31525 // - partial match (unambiguous partial prefix match)
b69ab31526
b69ab31527 // Full commit hash?
b69ab31528 const info = this.get(name);
b69ab31529 if (info) {
b69ab31530 return info;
b69ab31531 }
b69ab31532
b69ab31533 // Namemap lookup.
b69ab31534 const entries = this.inner.nameMap.get(name);
b69ab31535 if (entries) {
b69ab31536 let best: HashPriRecord | null = null;
b69ab31537 for (const entry of entries) {
b69ab31538 if (best == null || best.priority > entry.priority) {
b69ab31539 best = entry;
b69ab31540 }
b69ab31541 }
b69ab31542 if (best != null) {
b69ab31543 return this.get(best.hash);
b69ab31544 }
b69ab31545 }
b69ab31546
b69ab31547 // Unambiguous prefix match.
b69ab31548 if (shouldPrefixMatch(name)) {
b69ab31549 let matched: undefined | Hash = undefined;
b69ab31550 for (const hash of this) {
b69ab31551 if (hash.startsWith(name)) {
b69ab31552 if (matched === undefined) {
b69ab31553 matched = hash;
b69ab31554 } else {
b69ab31555 // Ambiguous prefix.
b69ab31556 return undefined;
b69ab31557 }
b69ab31558 }
b69ab31559 }
b69ab31560 return matched !== undefined ? this.get(matched) : undefined;
b69ab31561 }
b69ab31562
b69ab31563 // No match.
b69ab31564 return undefined;
b69ab31565 }
b69ab31566
b69ab31567 /** Render `set` into `ExtendedGraphRow`s. */
b69ab31568 renderToRows = cachedMethod(this.renderToRowsImpl, {cache: renderToRowsCache});
b69ab31569 private renderToRowsImpl(set?: SetLike): ReadonlyArray<[DagCommitInfo, ExtendedGraphRow]> {
b69ab31570 const renderer = new Renderer();
b69ab31571 const rows: Array<[DagCommitInfo, ExtendedGraphRow]> = [];
b69ab31572 for (const [type, item] of this.dagWalkerForRendering(set)) {
b69ab31573 if (type === 'row') {
b69ab31574 const [info, typedParents] = item;
b69ab31575 const forceLastColumn = info.isYouAreHere;
b69ab31576 const row = renderer.nextRow(info.hash, typedParents, {forceLastColumn});
b69ab31577 rows.push([info, row]);
b69ab31578 } else if (type === 'reserve') {
b69ab31579 renderer.reserve(item);
b69ab31580 }
b69ab31581 }
b69ab31582 return rows;
b69ab31583 }
b69ab31584
b69ab31585 /**
b69ab31586 * Yield [Info, Ancestor[]] in order, to be used by the rendering logic.
b69ab31587 * This returns a generator. To walk through the entire DAG it can be slow.
b69ab31588 * Use `dagWalkerForRendering` if you want a cached version.
b69ab31589 */
b69ab31590 *dagWalkerForRendering(
b69ab31591 set?: SetLike,
b69ab31592 ): Iterable<['reserve', Hash] | ['row', [DagCommitInfo, Ancestor[]]]> {
b69ab31593 // We want sortDesc, but want to reuse the comprehensive sortAsc compare logic.
b69ab31594 // So we use sortAsc here, then reverse it.
b69ab31595 const sorted =
b69ab31596 set === undefined
b69ab31597 ? this.sortAsc(this, {gap: false}).reverse()
b69ab31598 : this.sortAsc(HashSet.fromHashes(set)).reverse();
b69ab31599 const renderSet = new Set<Hash>(sorted);
b69ab31600 // Reserve a column for the public branch.
b69ab31601 for (const hash of sorted) {
b69ab31602 if (this.get(hash)?.phase === 'public') {
b69ab31603 yield ['reserve', hash];
b69ab31604 break;
b69ab31605 }
b69ab31606 }
b69ab31607 // Render row by row. The main complexity is to figure out the "ancestors",
b69ab31608 // especially when the provided `set` is a subset of the dag.
b69ab31609 for (const hash of sorted) {
b69ab31610 const info = nullthrows(this.get(hash));
b69ab31611 const parents: ReadonlyArray<Hash> = info?.parents ?? [];
b69ab31612 // directParents: solid edges
b69ab31613 // indirectParents: dashed edges
b69ab31614 // anonymousParents: ----"~"
b69ab31615 const {directParents, indirectParents, anonymousParents} = group(parents, p => {
b69ab31616 if (renderSet.has(p)) {
b69ab31617 return 'directParents';
b69ab31618 } else if (this.has(p)) {
b69ab31619 return 'indirectParents';
b69ab31620 } else {
b69ab31621 return 'anonymousParents';
b69ab31622 }
b69ab31623 });
b69ab31624 let typedParents: Ancestor[] = (directParents ?? []).map(p => {
b69ab31625 // We use 'info.ancestors' to fake ancestors as directParents.
b69ab31626 // Convert them to real ancestors so dashed lines are used.
b69ab31627 const type = info?.ancestors?.includes(p) ? AncestorType.Ancestor : AncestorType.Parent;
b69ab31628 return new Ancestor({type, hash: p});
b69ab31629 });
b69ab31630 if (anonymousParents != null && anonymousParents.length > 0 && info.ancestors == null) {
b69ab31631 typedParents.push(new Ancestor({type: AncestorType.Anonymous, hash: undefined}));
b69ab31632 }
b69ab31633 if (indirectParents != null && indirectParents.length > 0) {
b69ab31634 // Indirect parents might connect to "renderSet". Calculate it.
b69ab31635 // This can be expensive.
b69ab31636 // PERF: This is currently a dumb implementation and can probably be optimized.
b69ab31637 const grandParents = this.heads(
b69ab31638 this.ancestors(this.ancestors(indirectParents).intersect(renderSet)),
b69ab31639 );
b69ab31640 // Exclude duplication with faked grand parents, since they are already in typedParents.
b69ab31641 const newGrandParents = grandParents.subtract(directParents);
b69ab31642 typedParents = typedParents.concat(
b69ab31643 newGrandParents.toArray().map(p => new Ancestor({type: AncestorType.Ancestor, hash: p})),
b69ab31644 );
b69ab31645 }
b69ab31646 if (parents.length > 0 && typedParents.length === 0) {
b69ab31647 // The commit has parents but typedParents is empty (ex. (::indirect & renderSet) is empty).
b69ab31648 // Add an anonymous parent to indicate the commit is not a root.
b69ab31649 typedParents.push(new Ancestor({type: AncestorType.Anonymous, hash: undefined}));
b69ab31650 }
b69ab31651 yield ['row', [info, typedParents]];
b69ab31652 }
b69ab31653 }
b69ab31654
b69ab31655 /**
b69ab31656 * Render the dag in ASCII for debugging purpose.
b69ab31657 * If `set` is provided, only render a subset of the graph.
b69ab31658 */
b69ab31659 renderAscii(set?: SetLike): string {
b69ab31660 const renderer = new TextRenderer();
b69ab31661 const renderedRows = ['\n'];
b69ab31662 for (const [kind, data] of this.dagWalkerForRendering(set)) {
b69ab31663 if (kind === 'reserve') {
b69ab31664 renderer.reserve(data);
b69ab31665 } else {
b69ab31666 const [info, typedParents] = data;
b69ab31667 const {hash, title, author, date} = info;
b69ab31668 const message =
b69ab31669 [hash, title, author, date.valueOf() < 1000 ? '' : date.toISOString()]
b69ab31670 .join(' ')
b69ab31671 .trimEnd() + '\n';
b69ab31672 const glyph = info?.isDot ? '@' : info?.successorInfo == null ? 'o' : 'x';
b69ab31673 renderedRows.push(renderer.nextRow(info.hash, typedParents, message, glyph));
b69ab31674 }
b69ab31675 }
b69ab31676 return renderedRows.join('').trimEnd();
b69ab31677 }
b69ab31678
b69ab31679 /** Provided extra fields for debugging use-case. For now, this includes an ASCII graph. */
b69ab31680 getDebugState(): {rendered: Array<string>} {
b69ab31681 const rendered = this.renderAscii().split('\n');
b69ab31682 return {rendered};
b69ab31683 }
b69ab31684}
b69ab31685
b69ab31686const rootsCache = new LRU(1000);
b69ab31687const headsCache = new LRU(1000);
b69ab31688const allCache = new LRU(1000);
b69ab31689const subsetForRenderingCache = new LRU(1000);
b69ab31690const defaultSortAscIndexCache = new LRU(1000);
b69ab31691const renderToRowsCache = new LRU(1000);
b69ab31692
b69ab31693type NameMapEntry = [string, HashPriRecord];
b69ab31694
b69ab31695/** Extract the (name, hash, pri) information for insertion and deletion. */
b69ab31696function infoToNameMapEntries(info: DagCommitInfo): Array<NameMapEntry> {
b69ab31697 // Priority, highest to lowest:
b69ab31698 // - full hash (handled by dag.resolve())
b69ab31699 // - ".", the working parent
b69ab31700 // - namespaces.singlenode lookup
b69ab31701 // - 10: bookmarks
b69ab31702 // - 55: remotebookmarks (ex. "remote/main")
b69ab31703 // - 60: hoistednames (ex. "main" without "remote/")
b69ab31704 // - 70: phrevset (ex. "Dxxx"), but we skip it here due to lack
b69ab31705 // of access to the code review abstraction.
b69ab31706 // - partial hash (handled by dag.resolve())
b69ab31707 const result: Array<NameMapEntry> = [];
b69ab31708 const {hash, isDot, bookmarks, remoteBookmarks} = info;
b69ab31709 if (isDot) {
b69ab31710 result.push(['.', HashPriRecord({hash, priority: 1})]);
b69ab31711 }
b69ab31712 bookmarks.forEach(b => result.push([b, HashPriRecord({hash, priority: 10})]));
b69ab31713 remoteBookmarks.forEach(rb => {
b69ab31714 result.push([rb, HashPriRecord({hash, priority: 55})]);
b69ab31715 const split = splitOnce(rb, '/')?.[1];
b69ab31716 if (split) {
b69ab31717 result.push([split, HashPriRecord({hash, priority: 60})]);
b69ab31718 }
b69ab31719 });
b69ab31720 return result;
b69ab31721}
b69ab31722
b69ab31723/** Return the new NameMap after inserting or deleting `infos`. */
b69ab31724function calculateNewNameMap(
b69ab31725 map: NameMap,
b69ab31726 deleteInfos: Iterable<Readonly<DagCommitInfo>>,
b69ab31727 insertInfos: Iterable<Readonly<DagCommitInfo>>,
b69ab31728): NameMap {
b69ab31729 return map.withMutations(mut => {
b69ab31730 let map = mut;
b69ab31731 for (const info of deleteInfos) {
b69ab31732 const entries = infoToNameMapEntries(info);
b69ab31733 for (const [name, hashPri] of entries) {
b69ab31734 map = map.removeIn([name, hashPri]);
b69ab31735 if (map.get(name)?.isEmpty()) {
b69ab31736 map = map.remove(name);
b69ab31737 }
b69ab31738 }
b69ab31739 }
b69ab31740 for (const info of insertInfos) {
b69ab31741 const entries = infoToNameMapEntries(info);
b69ab31742 for (const [name, hashPri] of entries) {
b69ab31743 const set = map.get(name);
b69ab31744 if (set === undefined) {
b69ab31745 map = map.set(name, ImSet<HashPriRecord>([hashPri]));
b69ab31746 } else {
b69ab31747 map = map.set(name, set.add(hashPri));
b69ab31748 }
b69ab31749 }
b69ab31750 }
b69ab31751 return map;
b69ab31752 });
b69ab31753}
b69ab31754
b69ab31755/** Decide whether `hash` looks like a hash prefix. */
b69ab31756function shouldPrefixMatch(hash: Hash): boolean {
b69ab31757 // No prefix match for full hashes.
b69ab31758 if (hash.length >= 40) {
b69ab31759 return false;
b69ab31760 }
b69ab31761 // No prefix match for non-hex hashes.
b69ab31762 return /^[0-9a-f]+$/.test(hash);
b69ab31763}
b69ab31764
b69ab31765type NameMap = ImMap<string, ImSet<HashPriRecord>>;
b69ab31766
b69ab31767type CommitDagProps = {
b69ab31768 commitDag: BaseDag<DagCommitInfo>;
b69ab31769 mutationDag: MutationDag;
b69ab31770 // derived from Info, for fast "resolve" lookup. name -> hashpri
b69ab31771 nameMap: NameMap;
b69ab31772 nextSeqNumber: number;
b69ab31773};
b69ab31774
b69ab31775const CommitDagRecord = Record<CommitDagProps>({
b69ab31776 commitDag: new BaseDag(),
b69ab31777 mutationDag: new MutationDag(),
b69ab31778 nameMap: ImMap() as NameMap,
b69ab31779 nextSeqNumber: 0,
b69ab31780});
b69ab31781
b69ab31782type CommitDagRecord = RecordOf<CommitDagProps>;
b69ab31783
b69ab31784type HashPriProps = {
b69ab31785 hash: Hash;
b69ab31786 // for 'resolve' use-case; lower number = higher priority
b69ab31787 priority: number;
b69ab31788};
b69ab31789const HashPriRecord = Record<HashPriProps>({hash: '', priority: 0});
b69ab31790type HashPriRecord = RecordOf<HashPriProps>;
b69ab31791
b69ab31792const EMPTY_DAG_RECORD = CommitDagRecord();
b69ab31793
b69ab31794/** 'Hash' prefix for rebase successor in preview. */
b69ab31795export const REBASE_SUCC_PREFIX = 'OPTIMISTIC_REBASE_SUCC:';
b69ab31796
b69ab31797/** Default 'compare' function for sortAsc. */
b69ab31798const sortAscCompare = (a: DagCommitInfo, b: DagCommitInfo) => {
b69ab31799 // Consider phase. Public last. For example, when sorting this dag
b69ab31800 // (used by tests):
b69ab31801 //
b69ab31802 // ```plain
b69ab31803 // o z Commit Z author 2024-01-03T21:10:04.674Z
b69ab31804 // │
b69ab31805 // o y Commit Y author 2024-01-03T21:10:04.674Z
b69ab31806 // │
b69ab31807 // o x Commit X author 2024-01-03T21:10:04.674Z
b69ab31808 // ╭─╯
b69ab31809 // o 2 another public branch author 2024-01-03T21:10:04.674Z
b69ab31810 // ├─╮
b69ab31811 // ╷ │
b69ab31812 // ╷ ~
b69ab31813 // ╷
b69ab31814 // ╷ @ e Commit E author 2024-01-03T21:10:04.674Z
b69ab31815 // ╷ │
b69ab31816 // ╷ o d Commit D author 2024-01-03T21:10:04.674Z
b69ab31817 // ╷ │
b69ab31818 // ╷ o c Commit C author 2024-01-03T21:10:04.674Z
b69ab31819 // ╷ │
b69ab31820 // ╷ o b Commit B author 2024-01-03T21:10:04.674Z
b69ab31821 // ╷ │
b69ab31822 // ╷ o a Commit A author 2024-01-03T21:10:04.674Z
b69ab31823 // ╭─╯
b69ab31824 // o 1 some public base author 2024-01-03T21:10:04.674Z
b69ab31825 // │
b69ab31826 // ~
b69ab31827 // ```
b69ab31828 //
b69ab31829 // The desired order is [1, a, b, c, d, e, 2, x, y, z] that matches
b69ab31830 // the reversed rendering order. 'a' (draft) is before '2' (public).
b69ab31831 if (a.phase !== b.phase) {
b69ab31832 return a.phase === 'public' ? 1 : -1;
b69ab31833 }
b69ab31834 // Consider seqNumber (insertion order during preview calculation).
b69ab31835 if (a.seqNumber != null && b.seqNumber != null) {
b69ab31836 const seqDelta = b.seqNumber - a.seqNumber;
b69ab31837 if (seqDelta !== 0) {
b69ab31838 return seqDelta;
b69ab31839 }
b69ab31840 }
b69ab31841 // Sort by date.
b69ab31842 const timeDelta = a.date.getTime() - b.date.getTime();
b69ab31843 if (timeDelta !== 0) {
b69ab31844 return timeDelta;
b69ab31845 }
b69ab31846 // Always break ties even if timestamp is the same.
b69ab31847 return a.hash < b.hash ? 1 : -1;
b69ab31848};
b69ab31849
b69ab31850export {DagCommitInfo};