Fix ToC bug & add tests (#726)

3 files changed, 163 insertions, 38 deletions

diff --git a/.changeset/fuzzy-bottles-join.md b/.changeset/fuzzy-bottles-join.md
new file mode 100644
index 00000000..4ed39492
--- /dev/null
+++ b/.changeset/fuzzy-bottles-join.md
@@ -0,0 +1,5 @@
+---
+'@astrojs/starlight': patch
+---
+
+Fix a rare bug in table of contents when handling headings that increase by more than one level on a page.
diff --git a/packages/starlight/__tests__/basics/toc.test.ts b/packages/starlight/__tests__/basics/toc.test.ts
new file mode 100644
index 00000000..f4070b30
--- /dev/null
+++ b/packages/starlight/__tests__/basics/toc.test.ts
@@ -0,0 +1,143 @@
+import { expect, test } from 'vitest';
+import { generateToC } from '../../components/TableOfContents/generateToC';
+
+const defaultOpts = { minHeadingLevel: 2, maxHeadingLevel: 3, title: 'Overview' };
+
+test('generates an overview entry with no headings available', () => {
+	const toc = generateToC([], defaultOpts);
+	expect(toc).toHaveLength(1);
+	expect(toc[0]).toEqual({ children: [], depth: 2, slug: '_top', text: 'Overview' });
+});
+
+test('generates entries from heading array', () => {
+	const toc = generateToC([{ text: 'One', slug: 'one', depth: 2 }], defaultOpts);
+	expect(toc).toHaveLength(2);
+	expect(toc[0]).toEqual({ children: [], depth: 2, slug: '_top', text: 'Overview' });
+	expect(toc[1]).toEqual({ children: [], depth: 2, slug: 'one', text: 'One' });
+});
+
+test('nests lower-level headings in children array h2 => h3', () => {
+	const toc = generateToC(
+		[
+			{ text: 'One', slug: 'one', depth: 2 },
+			{ text: 'Two', slug: 'two', depth: 3 },
+		],
+		defaultOpts
+	);
+	expect(toc).toHaveLength(2);
+	expect(toc[0]).toEqual({ children: [], depth: 2, slug: '_top', text: 'Overview' });
+	expect(toc[1]).toEqual({
+		children: [{ children: [], depth: 3, slug: 'two', text: 'Two' }],
+		depth: 2,
+		slug: 'one',
+		text: 'One',
+	});
+});
+
+test('nests lower-level headings in children array h2 => h4', () => {
+	const toc = generateToC(
+		[
+			{ text: 'One', slug: 'one', depth: 2 },
+			{ text: 'Two', slug: 'two', depth: 4 },
+		],
+		{ ...defaultOpts, maxHeadingLevel: 6 }
+	);
+	expect(toc).toHaveLength(2);
+	expect(toc[0]).toEqual({ children: [], depth: 2, slug: '_top', text: 'Overview' });
+	expect(toc[1]).toEqual({
+		children: [{ children: [], depth: 4, slug: 'two', text: 'Two' }],
+		depth: 2,
+		slug: 'one',
+		text: 'One',
+	});
+});
+
+test('nests lower-level headings deeply h2 => h4 => h6', () => {
+	const toc = generateToC(
+		[
+			{ text: 'One', slug: 'one', depth: 2 },
+			{ text: 'Two', slug: 'two', depth: 4 },
+			{ text: 'Three', slug: 'three', depth: 6 },
+		],
+		{ ...defaultOpts, maxHeadingLevel: 6 }
+	);
+	expect(toc).toHaveLength(2);
+	expect(toc[0]).toEqual({ children: [], depth: 2, slug: '_top', text: 'Overview' });
+	expect(toc[1]).toMatchInlineSnapshot(`
+		{
+		  "children": [
+		    {
+		      "children": [
+		        {
+		          "children": [],
+		          "depth": 6,
+		          "slug": "three",
+		          "text": "Three",
+		        },
+		      ],
+		      "depth": 4,
+		      "slug": "two",
+		      "text": "Two",
+		    },
+		  ],
+		  "depth": 2,
+		  "slug": "one",
+		  "text": "One",
+		}
+	`);
+});
+
+test('adds higher-level headings sequentially h6 => h4 => h2', () => {
+	const toc = generateToC(
+		[
+			{ text: 'One', slug: 'one', depth: 6 },
+			{ text: 'Two', slug: 'two', depth: 4 },
+			{ text: 'Three', slug: 'three', depth: 2 },
+		],
+		{ ...defaultOpts, maxHeadingLevel: 6 }
+	);
+	console.log(toc);
+
+	expect(toc).toHaveLength(2);
+	expect(toc).toMatchInlineSnapshot(`
+		[
+		  {
+		    "children": [
+		      {
+		        "children": [],
+		        "depth": 6,
+		        "slug": "one",
+		        "text": "One",
+		      },
+		      {
+		        "children": [],
+		        "depth": 4,
+		        "slug": "two",
+		        "text": "Two",
+		      },
+		    ],
+		    "depth": 2,
+		    "slug": "_top",
+		    "text": "Overview",
+		  },
+		  {
+		    "children": [],
+		    "depth": 2,
+		    "slug": "three",
+		    "text": "Three",
+		  },
+		]
+	`);
+});
+
+test('filters out higher-level headings than minHeadingLevel', () => {
+	const toc = generateToC([{ text: 'One', slug: 'one', depth: 1 }], defaultOpts);
+	expect(toc).toHaveLength(1);
+	expect(toc[0]).toEqual({ children: [], depth: 2, slug: '_top', text: 'Overview' });
+});
+
+test('filters out lower-level headings than maxHeadingLevel', () => {
+	const toc = generateToC([{ text: 'One', slug: 'one', depth: 4 }], defaultOpts);
+	expect(toc).toHaveLength(1);
+	expect(toc[0]).toEqual({ children: [], depth: 2, slug: '_top', text: 'Overview' });
+});
diff --git a/packages/starlight/components/TableOfContents/generateToC.ts b/packages/starlight/components/TableOfContents/generateToC.ts
index 30d1005f..73c08e3d 100644
--- a/packages/starlight/components/TableOfContents/generateToC.ts
+++ b/packages/starlight/components/TableOfContents/generateToC.ts
@@ -4,52 +4,29 @@ export interface TocItem extends MarkdownHeading {
 	children: TocItem[];
 }
 
-function diveChildren(item: TocItem, depth: number): TocItem[] {
-	if (depth === 1) {
-		return item.children;
-	} else if (item.children.length > 0) {
-		return diveChildren(item.children.at(-1)!, depth - 1);
-	} else {
-		return [];
-	}
-}
-
 interface TocOpts {
 	minHeadingLevel: number;
 	maxHeadingLevel: number;
-	title?: string;
+	title: string;
 }
 
+/** Convert the flat headings array generated by Astro into a nested tree structure. */
 export function generateToC(
 	headings: MarkdownHeading[],
-	{ minHeadingLevel, maxHeadingLevel, title = 'Overview' }: TocOpts
+	{ minHeadingLevel, maxHeadingLevel, title }: TocOpts
 ) {
-	const overview = { depth: 2, slug: '_top', text: title };
-	headings = [
-		overview,
-		...headings.filter(({ depth }) => depth >= minHeadingLevel && depth <= maxHeadingLevel),
-	];
-	const toc: Array<TocItem> = [];
+	headings = headings.filter(({ depth }) => depth >= minHeadingLevel && depth <= maxHeadingLevel);
+	const toc: Array<TocItem> = [{ depth: 2, slug: '_top', text: title, children: [] }];
+	for (const heading of headings) injectChild(toc, { ...heading, children: [] });
+	return toc;
+}
 
-	for (const heading of headings) {
-		if (toc.length === 0) {
-			toc.push({ ...heading, children: [] });
-		} else {
-			const lastItemInToc = toc.at(-1)!;
-			if (heading.depth < lastItemInToc.depth) {
-				throw new Error(`Orphan heading found: ${heading.text}.`);
-			}
-			if (heading.depth === lastItemInToc.depth) {
-				// same depth
-				toc.push({ ...heading, children: [] });
-			} else {
-				// higher depth
-				// push into children, or children's children alike
-				const gap = heading.depth - lastItemInToc.depth;
-				const target = diveChildren(lastItemInToc, gap);
-				target.push({ ...heading, children: [] });
-			}
-		}
+/** Inject a ToC entry as deep in the tree as its `depth` property requires. */
+function injectChild(items: TocItem[], item: TocItem): void {
+	const lastItem = items.at(-1);
+	if (!lastItem || lastItem.depth >= item.depth) {
+		items.push(item);
+	} else {
+		return injectChild(lastItem.children, item);
 	}
-	return toc;
 }