Blame · mutation_dag.ts

b69ab31	1	/**
b69ab31	2	* Copyright (c) Meta Platforms, Inc. and affiliates.
b69ab31	3	*
b69ab31	4	* This source code is licensed under the MIT license found in the
b69ab31	5	* LICENSE file in the root directory of this source tree.
b69ab31	6	*/
b69ab31	7
b69ab31	8	import type {Hash} from '../types';
b69ab31	9	import type {HashWithParents} from './base_dag';
b69ab31	10
b69ab31	11	import {BaseDag} from './base_dag';
b69ab31	12	import {Ancestor, AncestorType} from './render';
b69ab31	13	import {TextRenderer} from './renderText';
b69ab31	14
b69ab31	15	/**
b69ab31	16	* Dag that tracks predecessor -> successor relationships.
b69ab31	17	*
b69ab31	18	* Predecessors are "ancestors". Successors are "descendants".
b69ab31	19	*
b69ab31	20	* This graph can contain hashes that were deleted in the main graph.
b69ab31	21	* For example, amend A1 to A2 to A3 to A4. This graph will keep all
b69ab31	22	* 4 hashes so it can answer questions like "I had A1, what is it now?"
b69ab31	23	* (A4) when the main graph only contains A4.
b69ab31	24	*
b69ab31	25	* In the above example, the user can also hide A4 and review A3
b69ab31	26	* (ex. undo, or hide when A3 has visible descendants). In this case,
b69ab31	27	* "what A1 becomes?" should be A3. So the followSuccessor()
b69ab31	28	* implementation should consider the mainDag, like:
b69ab31	29	*
b69ab31	30	* // Consider what is present in the mainDag.
b69ab31	31	* mutationDag.heads(mutationDag.range(start, mainDag))
b69ab31	32	*
b69ab31	33	* not:
b69ab31	34	*
b69ab31	35	* // BAD: Only consider mutationDag, might return hashes
b69ab31	36	* // missing in the mainDag.
b69ab31	37	* mutationDag.heads(mutationDag.descendants(start))
b69ab31	38	*
b69ab31	39	* Note: "dag" is a lossy view for actual mutation data. For example,
b69ab31	40	* it does not distinguish between:
b69ab31	41	* - amending A to A1, amending A to A2 (considered "divergence")
b69ab31	42	* - splitting A into A1 and A2 (not considered as a "divergence")
b69ab31	43	* Be careful when it is necessary to distinguish between them.
b69ab31	44	*/
b69ab31	45	export class MutationDag extends BaseDag<HashWithParents> {
b69ab31	46	constructor(baseDag?: BaseDag<HashWithParents>) {
b69ab31	47	const record = baseDag?.inner;
b69ab31	48	super(record);
b69ab31	49	}
b69ab31	50
b69ab31	51	/**
b69ab31	52	* Insert old->new mappings to the mutation dag.
b69ab31	53	*
b69ab31	54	* Note about `oldNewPairs`:
b69ab31	55	* - a same 'new' can have multiple 'old's (ex. fold)
b69ab31	56	* - a same 'old' can have multiple 'new's (ex. split)
b69ab31	57	* So the `oldNewPairs` should not be `Map`s with unique keys.
b69ab31	58	*/
b69ab31	59	addMutations(oldNewPairs: Iterable<[Hash, Hash]>): MutationDag {
b69ab31	60	const infoMap: Map<Hash, HashWithParents> = new Map();
b69ab31	61	const insert = (hash: Hash, parents: Hash[]) => {
b69ab31	62	// Insert `hash` to the infoMap on demand.
b69ab31	63	let info = infoMap.get(hash);
b69ab31	64	if (info == null) {
b69ab31	65	info = {
b69ab31	66	hash,
b69ab31	67	parents: this.get(hash)?.parents ?? [],
b69ab31	68	grandparents: this.get(hash)?.grandparents ?? [],
b69ab31	69	};
b69ab31	70	infoMap.set(hash, info);
b69ab31	71	}
b69ab31	72	// Append parents.
b69ab31	73	if (parents.length > 0) {
b69ab31	74	info.parents = Array.from(new Set(info.parents.concat(parents)));
b69ab31	75	}
b69ab31	76	};
b69ab31	77	for (const [oldHash, newHash] of oldNewPairs) {
b69ab31	78	insert(newHash, [oldHash]);
b69ab31	79	insert(oldHash, []);
b69ab31	80	}
b69ab31	81	const baseDag = this.add(infoMap.values());
b69ab31	82	return new MutationDag(baseDag);
b69ab31	83	}
b69ab31	84
b69ab31	85	/** Provided extra fields for debugging use-case. For now, this includes an ASCII graph. */
b69ab31	86	getDebugState(): {rendered: Array<string>} {
b69ab31	87	const renderer = new TextRenderer();
b69ab31	88	const rendered = [];
b69ab31	89
b69ab31	90	// Render row by row. The main complexity is to figure out the "ancestors",
b69ab31	91	// especially when the provided `set` is a subset of the dag.
b69ab31	92	for (const hash of this.sortDesc(this, {gap: false})) {
b69ab31	93	const parents = this.parentHashes(hash);
b69ab31	94	const typedParents: Ancestor[] = parents.map(
b69ab31	95	hash => new Ancestor({type: AncestorType.Parent, hash}),
b69ab31	96	);
b69ab31	97	const renderedRow = renderer.nextRow(hash, typedParents, hash);
b69ab31	98	for (const line of renderedRow.trimEnd().split('\n')) {
b69ab31	99	rendered.push(line);
b69ab31	100	}
b69ab31	101	}
b69ab31	102	return {rendered};
b69ab31	103	}
b69ab31	104	}