addons/isl/src/getCommitTree.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 {CommitPreview, Dag, WithPreviewType} from './previews';
b69ab319import type {CommitInfo, Hash} from './types';
b69ab3110
b69ab3111export type CommitTree = {
b69ab3112 info: CommitInfo;
b69ab3113 children: Array<CommitTree>;
b69ab3114};
b69ab3115
b69ab3116export type CommitTreeWithPreviews = {
b69ab3117 info: CommitInfo;
b69ab3118 children: Array<CommitTreeWithPreviews>;
b69ab3119 previewType?: CommitPreview;
b69ab3120};
b69ab3121
b69ab3122const byTimeDecreasing = (a: CommitInfo & WithPreviewType, b: CommitInfo & WithPreviewType) => {
b69ab3123 // Consider seqNumber (insertion order during preview calculation).
b69ab3124 if (a.seqNumber != null && b.seqNumber != null) {
b69ab3125 const seqDelta = a.seqNumber - b.seqNumber;
b69ab3126 if (seqDelta !== 0) {
b69ab3127 return seqDelta;
b69ab3128 }
b69ab3129 }
b69ab3130 // Sort by date.
b69ab3131 const timeDelta = b.date.getTime() - a.date.getTime();
b69ab3132 if (timeDelta !== 0) {
b69ab3133 return timeDelta;
b69ab3134 }
b69ab3135 // Always break ties even if timestamp is the same.
b69ab3136 return a.hash < b.hash ? 1 : -1;
b69ab3137};
b69ab3138
b69ab3139/**
b69ab3140 * Given a list of commits from disk, produce a tree capturing the
b69ab3141 * parent/child structure of the commits.
b69ab3142 * - Public commits are always top level (on the main line)
b69ab3143 * - Public commits are sorted by date
b69ab3144 * - Draft commits are always offshoots of public commits (never on main line)
b69ab3145 * - Caveat: if there are no public commits found, use the parent of everything
b69ab3146 * as if it were a public commit
b69ab3147 * - If a public commit has no draft children, it is hidden
b69ab3148 * - ...unless it has a bookmark
b69ab3149 * - If a commit has multiple children, they are sorted by date
b69ab3150 */
b69ab3151export function getCommitTree(
b69ab3152 commits: Array<CommitInfo & WithPreviewType>,
b69ab3153): Array<CommitTreeWithPreviews> {
b69ab3154 const childNodesByParent = new Map<string, Set<CommitInfo>>();
b69ab3155 commits.forEach(commit => {
b69ab3156 const [parent] = commit.parents;
b69ab3157 if (!parent) {
b69ab3158 return;
b69ab3159 }
b69ab3160 let set = childNodesByParent.get(parent);
b69ab3161 if (!set) {
b69ab3162 set = new Set();
b69ab3163 childNodesByParent.set(parent, set);
b69ab3164 }
b69ab3165 set.add(commit);
b69ab3166 });
b69ab3167
b69ab3168 const makeTree = (revision: CommitInfo & WithPreviewType): CommitTreeWithPreviews => {
b69ab3169 const {hash, previewType} = revision;
b69ab3170 const childrenSet = childNodesByParent.get(hash) ?? [];
b69ab3171
b69ab3172 const childrenInfos = [...childrenSet].sort(byTimeDecreasing);
b69ab3173
b69ab3174 const children: Array<CommitTree> =
b69ab3175 childrenInfos == null
b69ab3176 ? []
b69ab3177 : // only make branches off the main line for non-public revisions
b69ab3178 childrenInfos.filter(child => child.phase !== 'public').map(makeTree);
b69ab3179
b69ab3180 return {
b69ab3181 info: revision,
b69ab3182 children,
b69ab3183 previewType,
b69ab3184 };
b69ab3185 };
b69ab3186
b69ab3187 const initialCommits = commits.filter(
b69ab3188 commit => commit.phase === 'public' || commit.parents.length === 0,
b69ab3189 );
b69ab3190
b69ab3191 // build tree starting from public revisions
b69ab3192 return initialCommits.sort(byTimeDecreasing).map(makeTree);
b69ab3193}
b69ab3194
b69ab3195export function* walkTreePostorder(
b69ab3196 commitTree: Array<CommitTreeWithPreviews>,
b69ab3197): IterableIterator<CommitTreeWithPreviews> {
b69ab3198 for (const node of commitTree) {
b69ab3199 if (node.children.length > 0) {
b69ab31100 yield* walkTreePostorder(node.children);
b69ab31101 }
b69ab31102 yield node;
b69ab31103 }
b69ab31104}
b69ab31105
b69ab31106export function isDescendant(hash: string, commitTree: CommitTree): boolean {
b69ab31107 for (const commit of walkTreePostorder([commitTree])) {
b69ab31108 if (commit.info.hash === hash) {
b69ab31109 return true;
b69ab31110 }
b69ab31111 }
b69ab31112 return false;
b69ab31113}
b69ab31114
b69ab31115/** Test if a tree is linear - no merge or folds. */
b69ab31116export function isTreeLinear(tree: CommitTreeWithPreviews): boolean {
b69ab31117 if (tree.children.length > 1 || tree.info.parents.length > 1) {
b69ab31118 return false;
b69ab31119 }
b69ab31120 return tree.children.every(t => isTreeLinear(t));
b69ab31121}
b69ab31122
b69ab31123/** Finds the public ancestor by walking up parents, either from a starting hash or from `.` if none provided. */
b69ab31124export function findPublicBaseAncestor(dag?: Dag, from?: Hash): CommitInfo | undefined {
b69ab31125 let commit = dag?.resolve(from ?? '.');
b69ab31126 while (commit) {
b69ab31127 if (commit.phase === 'public') {
b69ab31128 return commit;
b69ab31129 }
b69ab31130 commit = dag?.get(commit.parents.at(0));
b69ab31131 }
b69ab31132 return undefined;
b69ab31133}