Skip to content
rachel/bland
File

Blob: src/client/lib/page-tree-model.ts

typescript349 lines
1import { DEFAULT_PAGE_TITLE, MAX_TREE_DEPTH } from "@/shared/constants";
2import type { Page } from "@/shared/types";
3 
4export type MoveKind = "reorder" | "indent" | "outdent" | "to_root" | "into_parent";
5export type MoveRelation = "before" | "inside" | "after" | "root-top" | "root-bottom";
6export type MoveValidationReason = "self" | "cycle" | "depth" | "noop" | "boundary";
7 
8export interface MoveProposal {
9  kind: MoveKind;
10  parentId: string | null;
11  insertionIndex: number;
12  siblings: Page[];
13  position: number;
14  previewLabel: string;
15}
16 
17export interface MoveResolution {
18  ok: true;
19  proposal: MoveProposal;
20}
21 
22export interface MoveRejection {
23  ok: false;
24  reason: MoveValidationReason;
25  message: string;
26}
27 
28export type MoveResult = MoveResolution | MoveRejection;
29 
30export interface PageTreeIndex {
31  byId: Map<string, Page>;
32  // Children sorted by position, archived pages excluded. Use null key for roots.
33  childrenByParent: Map<string | null, Page[]>;
34  activePages: Page[];
35}
36 
37function getPageLabel(page: Page): string {
38  return page.title || DEFAULT_PAGE_TITLE;
39}
40 
41export function buildPageMap(allPages: Page[]): Map<string, Page> {
42  return new Map(allPages.map((page) => [page.id, page]));
43}
44 
45export function buildPageTreeIndex(allPages: Page[]): PageTreeIndex {
46  const byId = new Map<string, Page>();
47  const childrenByParent = new Map<string | null, Page[]>();
48  const activePages: Page[] = [];
49  for (const page of allPages) {
50    byId.set(page.id, page);
51    if (page.archived_at) continue;
52    activePages.push(page);
53    const arr = childrenByParent.get(page.parent_id);
54    if (arr) arr.push(page);
55    else childrenByParent.set(page.parent_id, [page]);
56  }
57  for (const arr of childrenByParent.values()) arr.sort((a, b) => a.position - b.position);
58  return { byId, childrenByParent, activePages };
59}
60 
61export function getPageDepth(byId: Map<string, Page>, pageId: string): number {
62  let cur = byId.get(pageId);
63  let depth = 0;
64  while (cur?.parent_id) {
65    cur = byId.get(cur.parent_id);
66    depth += 1;
67  }
68  return depth;
69}
70 
71function getSubtreeDepth(index: PageTreeIndex, pageId: string): number {
72  const children = index.childrenByParent.get(pageId);
73  if (!children || children.length === 0) return 0;
74  let max = 0;
75  for (const child of children) {
76    const d = getSubtreeDepth(index, child.id);
77    if (d > max) max = d;
78  }
79  return 1 + max;
80}
81 
82function isDescendant(byId: Map<string, Page>, draggedId: string, targetId: string): boolean {
83  let cur = byId.get(targetId);
84  while (cur) {
85    if (cur.parent_id === draggedId) return true;
86    cur = cur.parent_id ? byId.get(cur.parent_id) : undefined;
87  }
88  return false;
89}
90 
91function siblingsFromIndex(index: PageTreeIndex, parentId: string | null, excludeId?: string): Page[] {
92  const arr = index.childrenByParent.get(parentId);
93  if (!arr) return [];
94  return excludeId ? arr.filter((p) => p.id !== excludeId) : arr.slice();
95}
96 
97export function getSortedSiblings(allPages: Page[], parentId: string | null, excludeId?: string): Page[] {
98  return allPages
99    .filter((page) => page.parent_id === parentId && page.id !== excludeId && !page.archived_at)
100    .sort((a, b) => a.position - b.position);
101}
102 
103export function computePosition(siblings: Page[], index: number): number {
104  if (siblings.length === 0) return 1;
105  if (index <= 0) return siblings[0].position - 1;
106  if (index >= siblings.length) return siblings[siblings.length - 1].position + 1;
107  return (siblings[index - 1].position + siblings[index].position) / 2;
108}
109 
110export function getPagePathLabel(byId: Map<string, Page>, pageId: string): string {
111  const parts: string[] = [];
112  let cur = byId.get(pageId);
113  while (cur) {
114    parts.unshift(cur.title);
115    cur = cur.parent_id ? byId.get(cur.parent_id) : undefined;
116  }
117  return parts.join(" / ");
118}
119 
120export function getAncestorIds(byId: Map<string, Page>, pageId: string | null): Set<string> {
121  const result = new Set<string>();
122  let cur = pageId ? byId.get(pageId) : undefined;
123  while (cur?.parent_id) {
124    result.add(cur.parent_id);
125    cur = byId.get(cur.parent_id);
126  }
127  return result;
128}
129 
130function arraysEqual(a: string[], b: string[]): boolean {
131  return a.length === b.length && a.every((value, index) => value === b[index]);
132}
133 
134function validateMoveParent(index: PageTreeIndex, page: Page, targetParentId: string | null): MoveRejection | null {
135  if (targetParentId === page.id) {
136    return { ok: false, reason: "self", message: "A page cannot move inside itself" };
137  }
138 
139  if (targetParentId !== null && isDescendant(index.byId, page.id, targetParentId)) {
140    return { ok: false, reason: "cycle", message: "That move would place the page inside its own subtree" };
141  }
142 
143  const newDepth = targetParentId ? getPageDepth(index.byId, targetParentId) + 1 : 0;
144  const subtreeDepth = getSubtreeDepth(index, page.id);
145  if (newDepth + subtreeDepth >= MAX_TREE_DEPTH) {
146    return {
147      ok: false,
148      reason: "depth",
149      message: `That move would exceed the maximum nesting depth of ${MAX_TREE_DEPTH}`,
150    };
151  }
152 
153  return null;
154}
155 
156function finalizeMoveProposal(args: {
157  index: PageTreeIndex;
158  page: Page;
159  parentId: string | null;
160  insertionIndex: number;
161  siblings: Page[];
162  kind: MoveKind;
163  previewLabel: string;
164}): MoveResult {
165  const { index, page, parentId, insertionIndex, siblings, kind, previewLabel } = args;
166 
167  const validation = validateMoveParent(index, page, parentId);
168  if (validation) return validation;
169 
170  if (page.parent_id === parentId) {
171    const currentOrder = siblingsFromIndex(index, parentId).map((candidate) => candidate.id);
172    const nextOrder = [...siblings.slice(0, insertionIndex), page, ...siblings.slice(insertionIndex)].map(
173      (candidate) => candidate.id,
174    );
175    if (arraysEqual(currentOrder, nextOrder)) {
176      return { ok: false, reason: "noop", message: "That move would not change anything" };
177    }
178  }
179 
180  return {
181    ok: true,
182    proposal: {
183      kind,
184      parentId,
185      insertionIndex,
186      siblings,
187      position: computePosition(siblings, insertionIndex),
188      previewLabel,
189    },
190  };
191}
192 
193function resolveIndex(allPages: Page[], index?: PageTreeIndex): PageTreeIndex {
194  return index ?? buildPageTreeIndex(allPages);
195}
196 
197export function resolveMoveUp(allPages: Page[], page: Page, providedIndex?: PageTreeIndex): MoveResult {
198  const index = resolveIndex(allPages, providedIndex);
199  const currentSiblings = siblingsFromIndex(index, page.parent_id);
200  const currentIndex = currentSiblings.findIndex((candidate) => candidate.id === page.id);
201  if (currentIndex <= 0) {
202    return { ok: false, reason: "boundary", message: "Already first in this level" };
203  }
204 
205  const siblings = siblingsFromIndex(index, page.parent_id, page.id);
206  const target = currentSiblings[currentIndex - 1];
207  return finalizeMoveProposal({
208    index,
209    page,
210    parentId: page.parent_id,
211    insertionIndex: currentIndex - 1,
212    siblings,
213    kind: "reorder",
214    previewLabel: `Move before ${getPageLabel(target)}`,
215  });
216}
217 
218export function resolveMoveDown(allPages: Page[], page: Page, providedIndex?: PageTreeIndex): MoveResult {
219  const index = resolveIndex(allPages, providedIndex);
220  const currentSiblings = siblingsFromIndex(index, page.parent_id);
221  const currentIndex = currentSiblings.findIndex((candidate) => candidate.id === page.id);
222  if (currentIndex === -1 || currentIndex >= currentSiblings.length - 1) {
223    return { ok: false, reason: "boundary", message: "Already last in this level" };
224  }
225 
226  const siblings = siblingsFromIndex(index, page.parent_id, page.id);
227  const target = currentSiblings[currentIndex + 1];
228  return finalizeMoveProposal({
229    index,
230    page,
231    parentId: page.parent_id,
232    insertionIndex: currentIndex + 1,
233    siblings,
234    kind: "reorder",
235    previewLabel: `Move after ${getPageLabel(target)}`,
236  });
237}
238 
239export function resolveIndent(allPages: Page[], page: Page, providedIndex?: PageTreeIndex): MoveResult {
240  const index = resolveIndex(allPages, providedIndex);
241  const currentSiblings = siblingsFromIndex(index, page.parent_id);
242  const currentIndex = currentSiblings.findIndex((candidate) => candidate.id === page.id);
243  if (currentIndex <= 0) {
244    return { ok: false, reason: "boundary", message: "No previous sibling to indent into" };
245  }
246 
247  const previousSibling = currentSiblings[currentIndex - 1];
248  const siblings = siblingsFromIndex(index, previousSibling.id, page.id);
249  return finalizeMoveProposal({
250    index,
251    page,
252    parentId: previousSibling.id,
253    insertionIndex: siblings.length,
254    siblings,
255    kind: "indent",
256    previewLabel: `Move inside ${getPageLabel(previousSibling)}`,
257  });
258}
259 
260export function resolveOutdent(allPages: Page[], page: Page, providedIndex?: PageTreeIndex): MoveResult {
261  const index = resolveIndex(allPages, providedIndex);
262  if (!page.parent_id) {
263    return { ok: false, reason: "boundary", message: "Already at the top level" };
264  }
265 
266  const parent = index.byId.get(page.parent_id);
267  if (!parent) {
268    return { ok: false, reason: "boundary", message: "Parent page not found" };
269  }
270 
271  const siblings = siblingsFromIndex(index, parent.parent_id, page.id);
272  const parentIndex = siblings.findIndex((candidate) => candidate.id === parent.id);
273  if (parentIndex === -1) {
274    return { ok: false, reason: "boundary", message: "Parent page not found in the destination level" };
275  }
276 
277  return finalizeMoveProposal({
278    index,
279    page,
280    parentId: parent.parent_id,
281    insertionIndex: parentIndex + 1,
282    siblings,
283    kind: parent.parent_id === null ? "to_root" : "outdent",
284    previewLabel: `Move after ${getPageLabel(parent)}`,
285  });
286}
287 
288export function resolveMoveRelative(args: {
289  allPages: Page[];
290  page: Page;
291  targetPage: Page;
292  relation: "before" | "inside" | "after";
293  index?: PageTreeIndex;
294}): MoveResult {
295  const { allPages, page, targetPage, relation } = args;
296  const index = resolveIndex(allPages, args.index);
297 
298  if (relation === "inside") {
299    const siblings = siblingsFromIndex(index, targetPage.id, page.id);
300    return finalizeMoveProposal({
301      index,
302      page,
303      parentId: targetPage.id,
304      insertionIndex: siblings.length,
305      siblings,
306      kind: "into_parent",
307      previewLabel: `Move inside ${getPageLabel(targetPage)}`,
308    });
309  }
310 
311  const siblings = siblingsFromIndex(index, targetPage.parent_id, page.id);
312  const targetIndex = siblings.findIndex((candidate) => candidate.id === targetPage.id);
313  if (targetIndex === -1) {
314    return { ok: false, reason: "boundary", message: "Target page is not in the expected level" };
315  }
316 
317  const insertionIndex = relation === "before" ? targetIndex : targetIndex + 1;
318  return finalizeMoveProposal({
319    index,
320    page,
321    parentId: targetPage.parent_id,
322    insertionIndex,
323    siblings,
324    kind:
325      targetPage.parent_id === page.parent_id ? "reorder" : targetPage.parent_id === null ? "to_root" : "into_parent",
326    previewLabel:
327      relation === "before" ? `Move before ${getPageLabel(targetPage)}` : `Move after ${getPageLabel(targetPage)}`,
328  });
329}
330 
331export function resolveMoveToRoot(
332  allPages: Page[],
333  page: Page,
334  placement: "top" | "bottom",
335  providedIndex?: PageTreeIndex,
336): MoveResult {
337  const index = resolveIndex(allPages, providedIndex);
338  const siblings = siblingsFromIndex(index, null, page.id);
339  return finalizeMoveProposal({
340    index,
341    page,
342    parentId: null,
343    insertionIndex: placement === "top" ? 0 : siblings.length,
344    siblings,
345    kind: "to_root",
346    previewLabel: placement === "top" ? "Move to the top level" : "Move to the bottom of the top level",
347  });
348}