addons/isl/src/dag/render.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 {Hash} from '../types';
b69ab319
b69ab3110import {assert} from '../utils';
b69ab3111
b69ab3112/* eslint no-bitwise: 0 */
b69ab3113/* Translated from fbcode/eden/scm/lib/renderdag/src/render.rs */
b69ab3114
b69ab3115enum ColumnType {
b69ab3116 Empty = 0,
b69ab3117 Blocked = 1,
b69ab3118 Reserved = 2,
b69ab3119 Ancestor = 3,
b69ab3120 Parent = 4,
b69ab3121}
b69ab3122
b69ab3123type ColumnProps =
b69ab3124 | {
b69ab3125 type: ColumnType.Empty | ColumnType.Blocked;
b69ab3126 hash: undefined;
b69ab3127 }
b69ab3128 | {
b69ab3129 type: ColumnType.Reserved | ColumnType.Ancestor | ColumnType.Parent;
b69ab3130 hash: Hash;
b69ab3131 };
b69ab3132
b69ab3133export class Column {
b69ab3134 constructor(private inner: ColumnProps = {type: ColumnType.Empty, hash: undefined}) {}
b69ab3135
b69ab3136 static empty(): Column {
b69ab3137 return new Column();
b69ab3138 }
b69ab3139
b69ab3140 get type(): ColumnType {
b69ab3141 return this.inner.type;
b69ab3142 }
b69ab3143
b69ab3144 get hash(): undefined | Hash {
b69ab3145 return this.inner.hash;
b69ab3146 }
b69ab3147
b69ab3148 matches(n: Hash): boolean {
b69ab3149 return this.hash === n;
b69ab3150 }
b69ab3151
b69ab3152 isEmpty(): boolean {
b69ab3153 return this.type === ColumnType.Empty;
b69ab3154 }
b69ab3155
b69ab3156 variant(): number {
b69ab3157 return this.type;
b69ab3158 }
b69ab3159
b69ab3160 mergeColumn(other: Column): Column {
b69ab3161 return other.variant() > this.variant() ? other : this;
b69ab3162 }
b69ab3163
b69ab3164 reset(): Column {
b69ab3165 return this.type === ColumnType.Blocked ? Column.empty() : this;
b69ab3166 }
b69ab3167
b69ab3168 toNodeLine(): NodeLine {
b69ab3169 switch (this.type) {
b69ab3170 case ColumnType.Ancestor:
b69ab3171 return NodeLine.Ancestor;
b69ab3172 case ColumnType.Parent:
b69ab3173 return NodeLine.Parent;
b69ab3174 default:
b69ab3175 return NodeLine.Blank;
b69ab3176 }
b69ab3177 }
b69ab3178
b69ab3179 toLinkLine(): LinkLine {
b69ab3180 switch (this.type) {
b69ab3181 case ColumnType.Ancestor:
b69ab3182 return LinkLine.from(LinkLine.VERT_ANCESTOR);
b69ab3183 case ColumnType.Parent:
b69ab3184 return LinkLine.from(LinkLine.VERT_PARENT);
b69ab3185 default:
b69ab3186 return LinkLine.empty();
b69ab3187 }
b69ab3188 }
b69ab3189
b69ab3190 toPadLine(): PadLine {
b69ab3191 switch (this.type) {
b69ab3192 case ColumnType.Ancestor:
b69ab3193 return PadLine.Ancestor;
b69ab3194 case ColumnType.Parent:
b69ab3195 return PadLine.Parent;
b69ab3196 default:
b69ab3197 return PadLine.Blank;
b69ab3198 }
b69ab3199 }
b69ab31100}
b69ab31101
b69ab31102class Columns {
b69ab31103 public inner: Array<Column>;
b69ab31104
b69ab31105 constructor(columns?: Array<Column>) {
b69ab31106 this.inner = columns ?? [];
b69ab31107 }
b69ab31108
b69ab31109 find(node: Hash): number | undefined {
b69ab31110 const index = this.inner.findIndex(column => column.matches(node));
b69ab31111 return index >= 0 ? index : undefined;
b69ab31112 }
b69ab31113
b69ab31114 findEmpty(index?: number): number | undefined {
b69ab31115 if (index != null && this.inner.at(index)?.isEmpty()) {
b69ab31116 return index;
b69ab31117 }
b69ab31118 return this.firstEmpty();
b69ab31119 }
b69ab31120
b69ab31121 firstEmpty(): number | undefined {
b69ab31122 const index = this.inner.findIndex(column => column.isEmpty());
b69ab31123 return index >= 0 ? index : undefined;
b69ab31124 }
b69ab31125
b69ab31126 newEmpty(): number {
b69ab31127 const columns = this.inner;
b69ab31128 columns.push(Column.empty());
b69ab31129 return columns.length - 1;
b69ab31130 }
b69ab31131
b69ab31132 convertAncestorToParent() {
b69ab31133 const columns = this.inner;
b69ab31134 for (let i = 0; i < columns.length; i++) {
b69ab31135 const {type, hash} = columns[i];
b69ab31136 if (type === ColumnType.Ancestor && hash != null) {
b69ab31137 columns[i] = new Column({type: ColumnType.Parent, hash});
b69ab31138 }
b69ab31139 }
b69ab31140 }
b69ab31141
b69ab31142 reset(): void {
b69ab31143 let columns = this.inner;
b69ab31144 columns = columns.map(column => column.reset());
b69ab31145 while (columns.at(-1)?.isEmpty()) {
b69ab31146 columns.pop();
b69ab31147 }
b69ab31148 this.inner = columns;
b69ab31149 }
b69ab31150
b69ab31151 merge(index: number, column: Column) {
b69ab31152 const columns = this.inner;
b69ab31153 columns[index] = columns[index].mergeColumn(column);
b69ab31154 }
b69ab31155
b69ab31156 swap(index1: number, index2: number) {
b69ab31157 if (index1 !== index2) {
b69ab31158 const column1 = this.inner[index1];
b69ab31159 const column2 = this.inner[index2];
b69ab31160 this.inner[index1] = column2;
b69ab31161 this.inner[index2] = column1;
b69ab31162 }
b69ab31163 }
b69ab31164}
b69ab31165
b69ab31166export enum AncestorType {
b69ab31167 Ancestor = 'Ancestor',
b69ab31168 Parent = 'Parent',
b69ab31169 Anonymous = 'Anonymous',
b69ab31170}
b69ab31171
b69ab31172type AncestorProps =
b69ab31173 | {
b69ab31174 type: AncestorType.Ancestor | AncestorType.Parent;
b69ab31175 hash: Hash;
b69ab31176 }
b69ab31177 | {
b69ab31178 type: AncestorType.Anonymous;
b69ab31179 hash: undefined;
b69ab31180 };
b69ab31181
b69ab31182export class Ancestor {
b69ab31183 constructor(private inner: AncestorProps = {type: AncestorType.Anonymous, hash: undefined}) {}
b69ab31184
b69ab31185 toColumn(): Column {
b69ab31186 switch (this.inner.type) {
b69ab31187 case AncestorType.Ancestor:
b69ab31188 return new Column({type: ColumnType.Ancestor, hash: this.inner.hash});
b69ab31189 case AncestorType.Parent:
b69ab31190 return new Column({type: ColumnType.Parent, hash: this.inner.hash});
b69ab31191 case AncestorType.Anonymous:
b69ab31192 return new Column({type: ColumnType.Blocked, hash: undefined});
b69ab31193 }
b69ab31194 }
b69ab31195
b69ab31196 id(): Hash | undefined {
b69ab31197 return this.inner.hash;
b69ab31198 }
b69ab31199
b69ab31200 isDirect(): boolean {
b69ab31201 return this.inner.type !== AncestorType.Ancestor;
b69ab31202 }
b69ab31203
b69ab31204 toLinkLine(direct: LinkLine, indirect: LinkLine): LinkLine {
b69ab31205 return this.isDirect() ? direct : indirect;
b69ab31206 }
b69ab31207}
b69ab31208
b69ab31209type AncestorColumnBoundsProps = {
b69ab31210 target: number;
b69ab31211 minAncestor: number;
b69ab31212 minParent: number;
b69ab31213 maxParent: number;
b69ab31214 maxAncestor: number;
b69ab31215};
b69ab31216
b69ab31217export class AncestorColumnBounds {
b69ab31218 constructor(private inner: AncestorColumnBoundsProps) {}
b69ab31219
b69ab31220 static new(columns: Array<[number, Ancestor]>, target: number): AncestorColumnBounds | undefined {
b69ab31221 if (columns.length === 0) {
b69ab31222 return undefined;
b69ab31223 }
b69ab31224 const ancestorNumbers = [target, ...columns.map(([index]) => index)];
b69ab31225 const parentNumbers = [target, ...columns.filter(([, a]) => a.isDirect()).map(([i]) => i)];
b69ab31226 const minAncestor = Math.min(...ancestorNumbers);
b69ab31227 const maxAncestor = Math.max(...ancestorNumbers);
b69ab31228 const minParent = Math.min(...parentNumbers);
b69ab31229 const maxParent = Math.max(...parentNumbers);
b69ab31230 return new AncestorColumnBounds({
b69ab31231 target,
b69ab31232 minAncestor,
b69ab31233 minParent,
b69ab31234 maxParent,
b69ab31235 maxAncestor,
b69ab31236 });
b69ab31237 }
b69ab31238
b69ab31239 get minAncestor(): number {
b69ab31240 return this.inner.minAncestor;
b69ab31241 }
b69ab31242
b69ab31243 get minParent(): number {
b69ab31244 return this.inner.minParent;
b69ab31245 }
b69ab31246
b69ab31247 get maxParent(): number {
b69ab31248 return this.inner.maxParent;
b69ab31249 }
b69ab31250
b69ab31251 get maxAncestor(): number {
b69ab31252 return this.inner.maxAncestor;
b69ab31253 }
b69ab31254
b69ab31255 get target(): number {
b69ab31256 return this.inner.target;
b69ab31257 }
b69ab31258
b69ab31259 *range(): Iterable<number> {
b69ab31260 for (let i = this.minAncestor + 1; i < this.maxAncestor; ++i) {
b69ab31261 yield i;
b69ab31262 }
b69ab31263 }
b69ab31264
b69ab31265 horizontalLine(index: number): LinkLine {
b69ab31266 if (index === this.target) {
b69ab31267 return LinkLine.empty();
b69ab31268 } else if (index > this.minParent && index < this.maxParent) {
b69ab31269 return LinkLine.from(LinkLine.HORIZ_PARENT);
b69ab31270 } else if (index > this.minAncestor && index < this.maxAncestor) {
b69ab31271 return LinkLine.from(LinkLine.HORIZ_ANCESTOR);
b69ab31272 } else {
b69ab31273 return LinkLine.empty();
b69ab31274 }
b69ab31275 }
b69ab31276}
b69ab31277
b69ab31278export class LinkLine {
b69ab31279 constructor(public value = 0) {}
b69ab31280
b69ab31281 /** This cell contains a horizontal line that connects to a parent. */
b69ab31282 static HORIZ_PARENT = 1 << 0;
b69ab31283 /** This cell contains a horizontal line that connects to an ancestor. */
b69ab31284 static HORIZ_ANCESTOR = 1 << 1;
b69ab31285 /** The descendent of this cell is connected to the parent. */
b69ab31286 static VERT_PARENT = 1 << 2;
b69ab31287 /** The descendent of this cell is connected to an ancestor. */
b69ab31288 static VERT_ANCESTOR = 1 << 3;
b69ab31289 /** The parent of this cell is linked in this link row and the child is to the left. */
b69ab31290 static LEFT_FORK_PARENT = 1 << 4;
b69ab31291 /** The ancestor of this cell is linked in this link row and the child is to the left. */
b69ab31292 static LEFT_FORK_ANCESTOR = 1 << 5;
b69ab31293 /** The parent of this cell is linked in this link row and the child is to the right. */
b69ab31294 static RIGHT_FORK_PARENT = 1 << 6;
b69ab31295 /** The ancestor of this cell is linked in this link row and the child is to the right. */
b69ab31296 static RIGHT_FORK_ANCESTOR = 1 << 7;
b69ab31297 /** The child of this cell is linked to parents on the left. */
b69ab31298 static LEFT_MERGE_PARENT = 1 << 8;
b69ab31299 /** The child of this cell is linked to ancestors on the left. */
b69ab31300 static LEFT_MERGE_ANCESTOR = 1 << 9;
b69ab31301 /** The child of this cell is linked to parents on the right. */
b69ab31302 static RIGHT_MERGE_PARENT = 1 << 10;
b69ab31303 /** The child of this cell is linked to ancestors on the right. */
b69ab31304 static RIGHT_MERGE_ANCESTOR = 1 << 11;
b69ab31305 /**
b69ab31306 * The target node of this link line is the child of this column.
b69ab31307 * This disambiguates between the node that is connected in this link line,
b69ab31308 * and other nodes that are also connected vertically.
b69ab31309 */
b69ab31310 static CHILD = 1 << 12;
b69ab31311
b69ab31312 static HORIZONTAL = LinkLine.HORIZ_PARENT | LinkLine.HORIZ_ANCESTOR;
b69ab31313 static VERTICAL = LinkLine.VERT_PARENT | LinkLine.VERT_ANCESTOR;
b69ab31314 static LEFT_FORK = LinkLine.LEFT_FORK_PARENT | LinkLine.LEFT_FORK_ANCESTOR;
b69ab31315 static RIGHT_FORK = LinkLine.RIGHT_FORK_PARENT | LinkLine.RIGHT_FORK_ANCESTOR;
b69ab31316 static LEFT_MERGE = LinkLine.LEFT_MERGE_PARENT | LinkLine.LEFT_MERGE_ANCESTOR;
b69ab31317 static RIGHT_MERGE = LinkLine.RIGHT_MERGE_PARENT | LinkLine.RIGHT_MERGE_ANCESTOR;
b69ab31318 static ANY_MERGE = LinkLine.LEFT_MERGE | LinkLine.RIGHT_MERGE;
b69ab31319 static ANY_FORK = LinkLine.LEFT_FORK | LinkLine.RIGHT_FORK;
b69ab31320 static ANY_FORK_OR_MERGE = LinkLine.ANY_MERGE | LinkLine.ANY_FORK;
b69ab31321
b69ab31322 static from(value: number): LinkLine {
b69ab31323 return new LinkLine(value);
b69ab31324 }
b69ab31325
b69ab31326 static empty(): LinkLine {
b69ab31327 return new LinkLine(0);
b69ab31328 }
b69ab31329
b69ab31330 valueOf(): number {
b69ab31331 return this.value;
b69ab31332 }
b69ab31333
b69ab31334 contains(value: number): boolean {
b69ab31335 return (this.value & value) === value;
b69ab31336 }
b69ab31337
b69ab31338 intersects(value: number): boolean {
b69ab31339 return (this.value & value) !== 0;
b69ab31340 }
b69ab31341
b69ab31342 or(value: number): LinkLine {
b69ab31343 return LinkLine.from(this.value | value);
b69ab31344 }
b69ab31345}
b69ab31346
b69ab31347export enum NodeLine {
b69ab31348 Blank = 0,
b69ab31349 Ancestor = 1,
b69ab31350 Parent = 2,
b69ab31351 Node = 3,
b69ab31352}
b69ab31353
b69ab31354export enum PadLine {
b69ab31355 Blank = 0,
b69ab31356 Ancestor = 1,
b69ab31357 Parent = 2,
b69ab31358}
b69ab31359
b69ab31360type GraphRow = {
b69ab31361 hash: Hash;
b69ab31362 merge: boolean;
b69ab31363 /** The node ("o") columns for this row. */
b69ab31364 nodeLine: Array<NodeLine>;
b69ab31365 /** The link columns for this row if necessary. Cannot be repeated. */
b69ab31366 linkLine?: Array<LinkLine>;
b69ab31367 /**
b69ab31368 * The location of any terminators, if necessary.
b69ab31369 * Between postNode and ancestryLines.
b69ab31370 */
b69ab31371 termLine?: Array<boolean>;
b69ab31372 /**
b69ab31373 * Lines to represent "ancestry" relationship.
b69ab31374 * "|" for direct parent, ":" for indirect ancestor.
b69ab31375 * Can be repeated. Can be skipped if there are no indirect ancestors.
b69ab31376 * Practically, CLI repeats this line. ISL "repeats" preNode and postNode lines.
b69ab31377 */
b69ab31378 ancestryLine: Array<PadLine>;
b69ab31379
b69ab31380 /** True if the node is a head (no children, uses a new column) */
b69ab31381 isHead: boolean;
b69ab31382 /** True if the node is a root (no parents) */
b69ab31383 isRoot: boolean;
b69ab31384
b69ab31385 /**
b69ab31386 * Column that contains the "node" above the link line.
b69ab31387 * nodeLine[nodeColumn] should be NodeLine.Node.
b69ab31388 */
b69ab31389 nodeColumn: number;
b69ab31390
b69ab31391 /**
b69ab31392 * Parent columns reachable from "node" below the link line.
b69ab31393 */
b69ab31394 parentColumns: number[];
b69ab31395
b69ab31396 /**
b69ab31397 * A subset of LinkLine that comes from "node". For example:
b69ab31398 *
b69ab31399 * │ o // node line
b69ab31400 * ├─╯ // link line
b69ab31401 *
b69ab31402 * The `fromNodeValue` LinkLine looks like:
b69ab31403 *
b69ab31404 * ╭─╯
b69ab31405 *
b69ab31406 * Note "├" is changed to "╭".
b69ab31407 */
b69ab31408 linkLineFromNode?: Array<LinkLine>;
b69ab31409};
b69ab31410
b69ab31411/**
b69ab31412 * Output row for a "commit".
b69ab31413 *
b69ab31414 * Example line types:
b69ab31415 *
b69ab31416 * ```plain
b69ab31417 * │ // preNodeLine (repeatable)
b69ab31418 * │ // preNodeLine
b69ab31419 * o F // nodeLine
b69ab31420 * │ very long message 0 // postNodeLine (repeatable)
b69ab31421 * │ very long message 0 // postNodeLine
b69ab31422 * ├─┬─╮ very long message 1 // linkLine
b69ab31423 * │ │ ~ very long message 2 // termLine
b69ab31424 * : │ very long message 3 // ancestryLine
b69ab31425 * │ │ very long message 4 // postAncestryLine (repeatable)
b69ab31426 * │ │ very long message 5 // postAncestryLine
b69ab31427 * ```
b69ab31428 *
b69ab31429 * This is `GraphRow` with derived fields.
b69ab31430 */
b69ab31431export type ExtendedGraphRow = GraphRow & {
b69ab31432 /** If there are indirect ancestors, aka. the ancestryLine is interesting to render. */
b69ab31433 hasIndirectAncestor: boolean;
b69ab31434 /** The columns before the node columns. Repeatable. */
b69ab31435 preNodeLine: Array<PadLine>;
b69ab31436 /** The columns after node, before the term, link columns. Repeatable. */
b69ab31437 postNodeLine: Array<PadLine>;
b69ab31438 /** The columns after ancestryLine. Repeatable. */
b69ab31439 postAncestryLine: Array<PadLine>;
b69ab31440 /** Str to test equality. */
b69ab31441 valueOf(): string;
b69ab31442};
b69ab31443
b69ab31444function nodeToPadLine(node: NodeLine, useBlank: boolean): PadLine {
b69ab31445 switch (node) {
b69ab31446 case NodeLine.Blank:
b69ab31447 return PadLine.Blank;
b69ab31448 case NodeLine.Ancestor:
b69ab31449 return PadLine.Ancestor;
b69ab31450 case NodeLine.Parent:
b69ab31451 return PadLine.Parent;
b69ab31452 case NodeLine.Node:
b69ab31453 return useBlank ? PadLine.Blank : PadLine.Parent;
b69ab31454 }
b69ab31455}
b69ab31456
b69ab31457function extendGraphRow(row: GraphRow): ExtendedGraphRow {
b69ab31458 // Single string that includes all states of the row.
b69ab31459 // Useful to test equality.
b69ab31460 const rowStr = [
b69ab31461 row.hash,
b69ab31462 row.nodeLine.join(''),
b69ab31463 row.linkLine?.map(l => l.value.toString(16)).join('') ?? '',
b69ab31464 row.termLine?.map(l => (l ? '1' : '0')).join('') ?? '',
b69ab31465 row.ancestryLine?.join('') ?? '',
b69ab31466 row.parentColumns.join(','),
b69ab31467 row.isHead ? 'h' : '',
b69ab31468 row.isRoot ? 'r' : '',
b69ab31469 ].join(';');
b69ab31470
b69ab31471 return {
b69ab31472 ...row,
b69ab31473 get hasIndirectAncestor() {
b69ab31474 return row.ancestryLine.some(line => line === PadLine.Ancestor);
b69ab31475 },
b69ab31476 get preNodeLine() {
b69ab31477 return row.nodeLine.map(l => nodeToPadLine(l, row.isHead));
b69ab31478 },
b69ab31479 get postNodeLine() {
b69ab31480 return row.nodeLine.map(l => nodeToPadLine(l, row.isRoot));
b69ab31481 },
b69ab31482 get postAncestryLine() {
b69ab31483 return row.ancestryLine.map(l => (l === PadLine.Ancestor ? PadLine.Parent : l));
b69ab31484 },
b69ab31485 valueOf(): string {
b69ab31486 return rowStr;
b69ab31487 },
b69ab31488 };
b69ab31489}
b69ab31490
b69ab31491type NextRowOptions = {
b69ab31492 /**
b69ab31493 * Ensure this node uses the last (right-most) column.
b69ab31494 * Only works for heads, i.e. nodes without children.
b69ab31495 */
b69ab31496 forceLastColumn?: boolean;
b69ab31497};
b69ab31498
b69ab31499export class Renderer {
b69ab31500 private columns: Columns = new Columns();
b69ab31501
b69ab31502 /**
b69ab31503 * Reserve a column for the given hash.
b69ab31504 * This is usually used to indent draft commits by reserving
b69ab31505 * columns for public commits.
b69ab31506 */
b69ab31507 reserve(hash: Hash) {
b69ab31508 if (this.columns.find(hash) == null) {
b69ab31509 const index = this.columns.firstEmpty();
b69ab31510 const column = new Column({type: ColumnType.Reserved, hash});
b69ab31511 if (index == null) {
b69ab31512 this.columns.inner.push(column);
b69ab31513 } else {
b69ab31514 this.columns.inner[index] = column;
b69ab31515 }
b69ab31516 }
b69ab31517 }
b69ab31518
b69ab31519 /**
b69ab31520 * Render the next row.
b69ab31521 * Main logic of the renderer.
b69ab31522 */
b69ab31523 nextRow(hash: Hash, parents: Array<Ancestor>, opts?: NextRowOptions): ExtendedGraphRow {
b69ab31524 const {forceLastColumn = false} = opts ?? {};
b69ab31525
b69ab31526 // Find a column for this node.
b69ab31527 const existingColumn = this.columns.find(hash);
b69ab31528 let column: number;
b69ab31529 if (forceLastColumn) {
b69ab31530 assert(
b69ab31531 existingColumn == null,
b69ab31532 'requireLastColumn should only apply to heads (ex. "You are here")',
b69ab31533 );
b69ab31534 column = this.columns.newEmpty();
b69ab31535 } else {
b69ab31536 column = existingColumn ?? this.columns.firstEmpty() ?? this.columns.newEmpty();
b69ab31537 }
b69ab31538 const isHead =
b69ab31539 existingColumn == null || this.columns.inner.at(existingColumn)?.type === ColumnType.Reserved;
b69ab31540 const isRoot = parents.length === 0;
b69ab31541
b69ab31542 this.columns.inner[column] = Column.empty();
b69ab31543
b69ab31544 // This row is for a merge if there are multiple parents.
b69ab31545 const merge = parents.length > 1;
b69ab31546
b69ab31547 // Build the initial node line.
b69ab31548 const nodeLine: NodeLine[] = this.columns.inner.map(c => c.toNodeLine());
b69ab31549 nodeLine[column] = NodeLine.Node;
b69ab31550
b69ab31551 // Build the initial link line.
b69ab31552 const linkLine: LinkLine[] = this.columns.inner.map(c => c.toLinkLine());
b69ab31553 const linkLineFromNode: LinkLine[] = this.columns.inner.map(_c => LinkLine.empty());
b69ab31554 linkLineFromNode[column] = linkLine[column];
b69ab31555 let needLinkLine = false;
b69ab31556
b69ab31557 // Update linkLine[i] and linkLineFromNode[i] to include `bits`.
b69ab31558 const linkBoth = (i: number, bits: number) => {
b69ab31559 if (bits < 0) {
b69ab31560 linkLine[i] = LinkLine.from(bits);
b69ab31561 linkLineFromNode[i] = LinkLine.from(bits);
b69ab31562 } else {
b69ab31563 linkLine[i] = linkLine[i].or(bits);
b69ab31564 linkLineFromNode[i] = linkLineFromNode[i].or(bits);
b69ab31565 }
b69ab31566 };
b69ab31567
b69ab31568 // Build the initial term line.
b69ab31569 const termLine: boolean[] = this.columns.inner.map(_c => false);
b69ab31570 let needTermLine = false;
b69ab31571
b69ab31572 // Build the initial ancestry line.
b69ab31573 const ancestryLine: PadLine[] = this.columns.inner.map(c => c.toPadLine());
b69ab31574
b69ab31575 // Assign each parent to a column.
b69ab31576 const parentColumns = new Map<number, Ancestor>();
b69ab31577 for (const p of parents) {
b69ab31578 // Check if the parent already has a column.
b69ab31579 const parentId = p.id();
b69ab31580 if (parentId != null) {
b69ab31581 const index = this.columns.find(parentId);
b69ab31582 if (index != null) {
b69ab31583 this.columns.merge(index, p.toColumn());
b69ab31584 parentColumns.set(index, p);
b69ab31585 continue;
b69ab31586 }
b69ab31587 }
b69ab31588
b69ab31589 // Assign the parent to an empty column, preferring the column
b69ab31590 // the current node is going in, to maintain linearity.
b69ab31591 const index = this.columns.findEmpty(column);
b69ab31592 if (index != null) {
b69ab31593 this.columns.merge(index, p.toColumn());
b69ab31594 parentColumns.set(index, p);
b69ab31595 continue;
b69ab31596 }
b69ab31597
b69ab31598 // There are no empty columns left. Make a new column.
b69ab31599 parentColumns.set(this.columns.inner.length, p);
b69ab31600 nodeLine.push(NodeLine.Blank);
b69ab31601 ancestryLine.push(PadLine.Blank);
b69ab31602 linkLine.push(LinkLine.empty());
b69ab31603 linkLineFromNode.push(LinkLine.empty());
b69ab31604 termLine.push(false);
b69ab31605 this.columns.inner.push(p.toColumn());
b69ab31606 }
b69ab31607
b69ab31608 // Mark parent columns with anonymous parents as terminating.
b69ab31609 for (const [i, p] of parentColumns.entries()) {
b69ab31610 if (p.id() == null) {
b69ab31611 termLine[i] = true;
b69ab31612 needTermLine = true;
b69ab31613 }
b69ab31614 }
b69ab31615
b69ab31616 // Check if we can move the parent to the current column.
b69ab31617 //
b69ab31618 // Before After
b69ab31619 // ├─╮ ├─╮
b69ab31620 // │ o C │ o C
b69ab31621 // o ╷ B o ╷ B
b69ab31622 // ╰─╮ ├─╯
b69ab31623 // o A o A
b69ab31624 //
b69ab31625 // o J o J
b69ab31626 // ├─┬─╮ ├─┬─╮
b69ab31627 // │ │ o I │ │ o I
b69ab31628 // │ o │ H │ o │ H
b69ab31629 // ╭─┼─┬─┬─╮ ╭─┼─┬─┬─╮
b69ab31630 // │ │ │ │ o G │ │ │ │ o G
b69ab31631 // │ │ │ o │ E │ │ │ o │ E
b69ab31632 // │ │ │ ╰─┤ │ │ │ ├─╯
b69ab31633 // │ │ o │ D │ │ o │ D
b69ab31634 // │ │ ├───╮ │ │ ├─╮
b69ab31635 // │ o │ │ C │ o │ │ C
b69ab31636 // │ ╰─────┤ │ ├───╯
b69ab31637 // o │ │ F o │ │ F
b69ab31638 // ╰───────┤ ├─╯ │
b69ab31639 // │ o B o │ B
b69ab31640 // ├───╯ ├───╯
b69ab31641 // o A o A
b69ab31642 if (parents.length === 1) {
b69ab31643 const [[parentColumn, parentAncestor]] = parentColumns.entries();
b69ab31644 if (parentColumn != null && parentColumn > column) {
b69ab31645 // This node has a single parent which was already
b69ab31646 // assigned to a column to the right of this one.
b69ab31647 // Move the parent to this column.
b69ab31648 this.columns.swap(column, parentColumn);
b69ab31649 parentColumns.delete(parentColumn);
b69ab31650 parentColumns.set(column, parentAncestor);
b69ab31651 // Generate a line from this column to the old
b69ab31652 // parent column. We need to continue with the style
b69ab31653 // that was being used for the parent column.
b69ab31654 //
b69ab31655 // old parent
b69ab31656 // o v
b69ab31657 // ╭────╯
b69ab31658 // ^
b69ab31659 // new parent (moved here, nodeColumn)
b69ab31660 const wasDirect = linkLine.at(parentColumn)?.contains(LinkLine.VERT_PARENT);
b69ab31661 linkLine[column] = linkLine[column].or(
b69ab31662 wasDirect ? LinkLine.RIGHT_FORK_PARENT : LinkLine.RIGHT_FORK_ANCESTOR,
b69ab31663 );
b69ab31664 for (let i = column + 1; i < parentColumn; ++i) {
b69ab31665 linkLine[i] = linkLine[i].or(wasDirect ? LinkLine.HORIZ_PARENT : LinkLine.HORIZ_ANCESTOR);
b69ab31666 }
b69ab31667 linkLine[parentColumn] = LinkLine.from(
b69ab31668 wasDirect ? LinkLine.LEFT_MERGE_PARENT : LinkLine.LEFT_MERGE_ANCESTOR,
b69ab31669 );
b69ab31670 needLinkLine = true;
b69ab31671 // The ancestry line for the old parent column is now blank.
b69ab31672 ancestryLine[parentColumn] = PadLine.Blank;
b69ab31673 }
b69ab31674 }
b69ab31675
b69ab31676 // Connect the node column to all the parent columns.
b69ab31677 const bounds = AncestorColumnBounds.new([...parentColumns.entries()], column);
b69ab31678 if (bounds != null) {
b69ab31679 // If the parents extend beyond the columns adjacent to the node, draw a horizontal
b69ab31680 // ancestor line between the two outermost ancestors.
b69ab31681 for (const i of bounds.range()) {
b69ab31682 linkBoth(i, bounds.horizontalLine(i).value);
b69ab31683 needLinkLine = true;
b69ab31684 }
b69ab31685 // If there is a parent or ancestor to the right of the node
b69ab31686 // column, the node merges from the right.
b69ab31687 if (bounds.maxParent > column) {
b69ab31688 linkBoth(column, LinkLine.RIGHT_MERGE_PARENT);
b69ab31689 needLinkLine = true;
b69ab31690 } else if (bounds.maxAncestor > column) {
b69ab31691 linkBoth(column, LinkLine.RIGHT_MERGE_ANCESTOR);
b69ab31692 needLinkLine = true;
b69ab31693 }
b69ab31694 // If there is a parent or ancestor to the left of the node column, the node merges from the left.
b69ab31695 if (bounds.minParent < column) {
b69ab31696 linkBoth(column, LinkLine.LEFT_MERGE_PARENT);
b69ab31697 needLinkLine = true;
b69ab31698 } else if (bounds.minAncestor < column) {
b69ab31699 linkBoth(column, LinkLine.LEFT_MERGE_ANCESTOR);
b69ab31700 needLinkLine = true;
b69ab31701 }
b69ab31702 // Each parent or ancestor forks towards the node column.
b69ab31703 for (const [i, p] of parentColumns.entries()) {
b69ab31704 ancestryLine[i] = this.columns.inner[i].toPadLine();
b69ab31705 let orValue = 0;
b69ab31706 if (i < column) {
b69ab31707 orValue = p.toLinkLine(
b69ab31708 LinkLine.from(LinkLine.RIGHT_FORK_PARENT),
b69ab31709 LinkLine.from(LinkLine.RIGHT_FORK_ANCESTOR),
b69ab31710 ).value;
b69ab31711 } else if (i === column) {
b69ab31712 orValue =
b69ab31713 LinkLine.CHILD |
b69ab31714 p.toLinkLine(LinkLine.from(LinkLine.VERT_PARENT), LinkLine.from(LinkLine.VERT_ANCESTOR))
b69ab31715 .value;
b69ab31716 } else {
b69ab31717 orValue = p.toLinkLine(
b69ab31718 LinkLine.from(LinkLine.LEFT_FORK_PARENT),
b69ab31719 LinkLine.from(LinkLine.LEFT_FORK_ANCESTOR),
b69ab31720 ).value;
b69ab31721 }
b69ab31722 linkBoth(i, orValue);
b69ab31723 }
b69ab31724 }
b69ab31725
b69ab31726 // Only show ":" once per branch.
b69ab31727 this.columns.convertAncestorToParent();
b69ab31728
b69ab31729 // Now that we have assigned all the columns, reset their state.
b69ab31730 this.columns.reset();
b69ab31731
b69ab31732 // Filter out the link line or term line if they are not needed.
b69ab31733 const optionalLinkLine = needLinkLine ? linkLine : undefined;
b69ab31734 const optionalTermLine = needTermLine ? termLine : undefined;
b69ab31735
b69ab31736 const row: GraphRow = {
b69ab31737 hash,
b69ab31738 merge,
b69ab31739 nodeLine,
b69ab31740 linkLine: optionalLinkLine,
b69ab31741 termLine: optionalTermLine,
b69ab31742 ancestryLine,
b69ab31743 isHead,
b69ab31744 isRoot,
b69ab31745 nodeColumn: column,
b69ab31746 parentColumns: [...parentColumns.keys()].sort((a, b) => a - b),
b69ab31747 linkLineFromNode: needLinkLine ? linkLineFromNode : undefined,
b69ab31748 };
b69ab31749
b69ab31750 return extendGraphRow(row);
b69ab31751 }
b69ab31752}