Pick any line to see why it is the way it is: the commit, the pull request and issue it came from, and what the agent was thinking.
| Docs: a workspace knowledge base people and agents write together | 1 | /** |
| 2 | * The page tree: order within a parent, moving, and the paths a space's | |
| 3 | * export uses. Pure. | |
| 4 | * | |
| 5 | * Order is a number per page (`position`), compared within one parent. A | |
| 6 | * page moved between two others takes the midpoint, so a move writes one | |
| 7 | * row; when two neighbours get too close, the parent's children are | |
| 8 | * renumbered. | |
| 9 | */ | |
| 10 | ||
| 11 | export type TreeRow = { id: string; parent_id: string | null; position: number }; | |
| 12 | ||
| 13 | /** The gap between consecutive positions after renumbering. */ | |
| 14 | export const STEP = 1024; | |
| 15 | /** Below this gap, midpoints lose precision: renumber instead. */ | |
| 16 | const MIN_GAP = 1e-6; | |
| 17 | ||
| 18 | /** The children of `parent`, in order. */ | |
| 19 | export function childrenOf<T extends TreeRow>(rows: T[], parent: string | null): T[] { | |
| 20 | return rows.filter((r) => r.parent_id === parent).sort((a, b) => a.position - b.position || a.id.localeCompare(b.id)); | |
| 21 | } | |
| 22 | ||
| 23 | /** A position at the end of `parent`'s children. */ | |
| 24 | export function lastPosition(rows: TreeRow[], parent: string | null): number { | |
| 25 | const kids = childrenOf(rows, parent); | |
| 26 | return kids.length ? kids[kids.length - 1]!.position + STEP : STEP; | |
| 27 | } | |
| 28 | ||
| 29 | /** | |
| 30 | * Where `id` goes to sit under `parent` before `beforeId` (null: at the | |
| 31 | * end): its new position, and any siblings that had to be renumbered to | |
| 32 | * make room (`renumber`), as id → position. | |
| 33 | */ | |
| 34 | export function placeBefore( | |
| 35 | rows: TreeRow[], | |
| 36 | id: string, | |
| 37 | parent: string | null, | |
| 38 | beforeId: string | null, | |
| 39 | ): { position: number; renumber: Map<string, number> } { | |
| 40 | const siblings = childrenOf(rows, parent).filter((r) => r.id !== id); | |
| 41 | const at = beforeId ? siblings.findIndex((r) => r.id === beforeId) : -1; | |
| 42 | if (at < 0) { | |
| 43 | const last = siblings[siblings.length - 1]; | |
| 44 | return { position: last ? last.position + STEP : STEP, renumber: new Map() }; | |
| 45 | } | |
| 46 | const next = siblings[at]!.position; | |
| 47 | const prev = at > 0 ? siblings[at - 1]!.position : next - 2 * STEP; | |
| 48 | if (next - prev > MIN_GAP * 2) return { position: (prev + next) / 2, renumber: new Map() }; | |
| 49 | // Too close: renumber every sibling, leaving a slot before `beforeId`. | |
| 50 | const renumber = new Map<string, number>(); | |
| 51 | let position = 0; | |
| 52 | let mine = 0; | |
| 53 | for (let i = 0; i < siblings.length; i++) { | |
| 54 | if (i === at) { | |
| 55 | position += STEP; | |
| 56 | mine = position; | |
| 57 | } | |
| 58 | position += STEP; | |
| 59 | renumber.set(siblings[i]!.id, position); | |
| 60 | } | |
| 61 | return { position: mine, renumber }; | |
| 62 | } | |
| 63 | ||
| 64 | /** Whether making `parent` the parent of `id` would put a page under itself. */ | |
| 65 | export function wouldCycle(rows: TreeRow[], id: string, parent: string | null): boolean { | |
| 66 | const byId = new Map(rows.map((r) => [r.id, r])); | |
| 67 | let at = parent; | |
| 68 | const seen = new Set<string>(); | |
| 69 | while (at) { | |
| 70 | if (at === id) return true; | |
| 71 | if (seen.has(at)) return true; | |
| 72 | seen.add(at); | |
| 73 | at = byId.get(at)?.parent_id ?? null; | |
| 74 | } | |
| 75 | return false; | |
| 76 | } | |
| 77 | ||
| 78 | /** `id` and every page under it. */ | |
| 79 | export function descendants(rows: TreeRow[], id: string): string[] { | |
| 80 | const out = [id]; | |
| 81 | for (let i = 0; i < out.length; i++) { | |
| 82 | for (const r of rows) if (r.parent_id === out[i]) out.push(r.id); | |
| 83 | } | |
| 84 | return out; | |
| 85 | } | |
| 86 | ||
| 87 | /** A page's ancestors, root first (not the page itself). */ | |
| 88 | export function ancestors<T extends TreeRow>(rows: T[], id: string): T[] { | |
| 89 | const byId = new Map(rows.map((r) => [r.id, r])); | |
| 90 | const out: T[] = []; | |
| 91 | const seen = new Set<string>([id]); | |
| 92 | let at = byId.get(id)?.parent_id ?? null; | |
| 93 | while (at && !seen.has(at)) { | |
| 94 | seen.add(at); | |
| 95 | const row = byId.get(at); | |
| 96 | if (!row) break; | |
| 97 | out.unshift(row); | |
| 98 | at = row.parent_id; | |
| 99 | } | |
| 100 | return out; | |
| 101 | } | |
| 102 | ||
| 103 | /** | |
| 104 | * Paths for a space's export: each page at `<title>.md`, and a page with | |
| 105 | * children also as a folder of the same name holding them. Names are made | |
| 106 | * safe for file systems and unique among siblings. | |
| 107 | */ | |
| 108 | export function exportPaths<T extends TreeRow & { title: string }>(rows: T[]): Map<string, string> { | |
| 109 | const out = new Map<string, string>(); | |
| 110 | const walk = (parent: string | null, dir: string) => { | |
| 111 | const used = new Set<string>(); | |
| 112 | for (const row of childrenOf(rows, parent)) { | |
| 113 | const base = fileName(row.title); | |
| 114 | let name = base; | |
| 115 | for (let n = 2; used.has(name.toLowerCase()); n++) name = `${base} (${n})`; | |
| 116 | used.add(name.toLowerCase()); | |
| 117 | out.set(row.id, `${dir}${name}.md`); | |
| 118 | walk(row.id, `${dir}${name}/`); | |
| 119 | } | |
| 120 | }; | |
| 121 | walk(null, ""); | |
| 122 | return out; | |
| 123 | } | |
| 124 | ||
| 125 | /** A title as a file name: no path separators or characters file systems refuse. */ | |
| 126 | export function fileName(title: string): string { | |
| 127 | const name = title | |
| 128 | .replace(/[\\/:*?"<>|\u0000-\u001f]+/g, " ") | |
| 129 | .replace(/\s+/g, " ") | |
| 130 | .trim() | |
| 131 | .replace(/^\.+/, "") | |
| 132 | .slice(0, 100) | |
| 133 | .trim(); | |
| 134 | return name || "Untitled"; | |
| 135 | } |
