From fbb452385325d4418ce53e61178fe2494255caf5 Mon Sep 17 00:00:00 2001
From: Jacky Zhao <j.zhao2k19@gmail.com>
Date: Fri, 14 Mar 2025 22:08:23 +0000
Subject: [PATCH] fix(folder): use memoized trie instead of handrolled path solution (closes #1767)
---
quartz/util/fileTrie.test.ts | 52 +++++++++++++
quartz/components/PageList.tsx | 9 ++
quartz/util/path.ts | 2
quartz/components/pages/FolderContent.tsx | 115 ++++++++++++++++++----------
quartz/util/fileTrie.ts | 8 ++
5 files changed, 144 insertions(+), 42 deletions(-)
diff --git a/quartz/components/PageList.tsx b/quartz/components/PageList.tsx
index c0538f5..2a5f0e0 100644
--- a/quartz/components/PageList.tsx
+++ b/quartz/components/PageList.tsx
@@ -1,4 +1,4 @@
-import { FullSlug, resolveRelative } from "../util/path"
+import { FullSlug, isFolderPath, resolveRelative } from "../util/path"
import { QuartzPluginData } from "../plugins/vfile"
import { Date, getDate } from "./Date"
import { QuartzComponent, QuartzComponentProps } from "./types"
@@ -8,6 +8,13 @@
export function byDateAndAlphabetical(cfg: GlobalConfiguration): SortFn {
return (f1, f2) => {
+ // Sort folders first
+ const f1IsFolder = isFolderPath(f1.slug ?? "")
+ const f2IsFolder = isFolderPath(f2.slug ?? "")
+ if (f1IsFolder && !f2IsFolder) return -1
+ if (!f1IsFolder && f2IsFolder) return 1
+
+ // If both are folders or both are files, sort by date/alphabetical
if (f1.dates && f2.dates) {
// sort descending
return getDate(cfg, f2)!.getTime() - getDate(cfg, f1)!.getTime()
diff --git a/quartz/components/pages/FolderContent.tsx b/quartz/components/pages/FolderContent.tsx
index 2a727c0..e775653 100644
--- a/quartz/components/pages/FolderContent.tsx
+++ b/quartz/components/pages/FolderContent.tsx
@@ -1,16 +1,14 @@
import { QuartzComponent, QuartzComponentConstructor, QuartzComponentProps } from "../types"
-import path from "path"
import style from "../styles/listPage.scss"
-import { byDateAndAlphabetical, PageList, SortFn } from "../PageList"
-import { stripSlashes, simplifySlug, joinSegments, FullSlug } from "../../util/path"
+import { PageList, SortFn } from "../PageList"
import { Root } from "hast"
import { htmlToJsx } from "../../util/jsx"
import { i18n } from "../../i18n"
import { QuartzPluginData } from "../../plugins/vfile"
import { ComponentChildren } from "preact"
import { concatenateResources } from "../../util/resources"
-
+import { FileTrieNode } from "../../util/fileTrie"
interface FolderContentOptions {
/**
* Whether to display number of folders
@@ -27,51 +25,88 @@
export default ((opts?: Partial<FolderContentOptions>) => {
const options: FolderContentOptions = { ...defaultOptions, ...opts }
+ let trie: FileTrieNode<
+ QuartzPluginData & {
+ slug: string
+ title: string
+ filePath: string
+ }
+ >
const FolderContent: QuartzComponent = (props: QuartzComponentProps) => {
const { tree, fileData, allFiles, cfg } = props
- const folderSlug = stripSlashes(simplifySlug(fileData.slug!))
- const folderParts = folderSlug.split(path.posix.sep)
- const allPagesInFolder: QuartzPluginData[] = []
- const allPagesInSubfolders: Map<FullSlug, QuartzPluginData[]> = new Map()
+ if (!trie) {
+ trie = new FileTrieNode([])
+ allFiles.forEach((file) => {
+ if (file.frontmatter) {
+ trie.add({
+ ...file,
+ slug: file.slug!,
+ title: file.frontmatter.title,
+ filePath: file.filePath!,
+ })
+ }
+ })
+ }
- allFiles.forEach((file) => {
- const fileSlug = stripSlashes(simplifySlug(file.slug!))
- const prefixed = fileSlug.startsWith(folderSlug) && fileSlug !== folderSlug
- const fileParts = fileSlug.split(path.posix.sep)
- const isDirectChild = fileParts.length === folderParts.length + 1
+ const folder = trie.findNode(fileData.slug!.split("/"))
+ if (!folder) {
+ return null
+ }
- if (!prefixed) {
- return
- }
+ const allPagesInFolder: QuartzPluginData[] =
+ folder.children
+ .map((node) => {
+ // regular file, proceed
+ if (node.data) {
+ return node.data
+ }
- if (isDirectChild) {
- allPagesInFolder.push(file)
- } else if (options.showSubfolders) {
- const subfolderSlug = joinSegments(
- ...fileParts.slice(0, folderParts.length + 1),
- ) as FullSlug
- const pagesInFolder = allPagesInSubfolders.get(subfolderSlug) || []
- allPagesInSubfolders.set(subfolderSlug, [...pagesInFolder, file])
- }
- })
+ if (node.isFolder && options.showSubfolders) {
+ // folders that dont have data need synthetic files
+ const getMostRecentDates = (): QuartzPluginData["dates"] => {
+ let maybeDates: QuartzPluginData["dates"] | undefined = undefined
+ for (const child of node.children) {
+ if (child.data?.dates) {
+ // compare all dates and assign to maybeDates if its more recent or its not set
+ if (!maybeDates) {
+ maybeDates = child.data.dates
+ } else {
+ if (child.data.dates.created > maybeDates.created) {
+ maybeDates.created = child.data.dates.created
+ }
- allPagesInSubfolders.forEach((files, subfolderSlug) => {
- const hasIndex = allPagesInFolder.some(
- (file) => subfolderSlug === stripSlashes(simplifySlug(file.slug!)),
- )
- if (!hasIndex) {
- const subfolderDates = files.sort(byDateAndAlphabetical(cfg))[0].dates
- const subfolderTitle = subfolderSlug.split(path.posix.sep).at(-1)!
- allPagesInFolder.push({
- slug: subfolderSlug,
- dates: subfolderDates,
- frontmatter: { title: subfolderTitle, tags: ["folder"] },
+ if (child.data.dates.modified > maybeDates.modified) {
+ maybeDates.modified = child.data.dates.modified
+ }
+
+ if (child.data.dates.published > maybeDates.published) {
+ maybeDates.published = child.data.dates.published
+ }
+ }
+ }
+ }
+ return (
+ maybeDates ?? {
+ created: new Date(),
+ modified: new Date(),
+ published: new Date(),
+ }
+ )
+ }
+
+ return {
+ slug: node.slug,
+ dates: getMostRecentDates(),
+ frontmatter: {
+ title: node.displayName,
+ tags: [],
+ },
+ }
+ }
})
- }
- })
-
+ .filter((page) => page !== undefined) ?? []
const cssClasses: string[] = fileData.frontmatter?.cssclasses ?? []
const classes = cssClasses.join(" ")
const listProps = {
diff --git a/quartz/util/fileTrie.test.ts b/quartz/util/fileTrie.test.ts
index a333397..d66e142 100644
--- a/quartz/util/fileTrie.test.ts
+++ b/quartz/util/fileTrie.test.ts
@@ -229,6 +229,58 @@
})
})
+ describe("findNode", () => {
+ test("should find root node with empty path", () => {
+ const data = { title: "Root", slug: "index", filePath: "index.md" }
+ trie.add(data)
+ const found = trie.findNode([])
+ assert.strictEqual(found, trie)
+ })
+
+ test("should find node at first level", () => {
+ const data = { title: "Test", slug: "test", filePath: "test.md" }
+ trie.add(data)
+ const found = trie.findNode(["test"])
+ assert.strictEqual(found?.data, data)
+ })
+
+ test("should find nested node", () => {
+ const data = {
+ title: "Nested",
+ slug: "folder/subfolder/test",
+ filePath: "folder/subfolder/test.md",
+ }
+ trie.add(data)
+ const found = trie.findNode(["folder", "subfolder", "test"])
+ assert.strictEqual(found?.data, data)
+
+ // should find the folder and subfolder indexes too
+ assert.strictEqual(
+ trie.findNode(["folder", "subfolder", "index"]),
+ trie.children[0].children[0],
+ )
+ assert.strictEqual(trie.findNode(["folder", "index"]), trie.children[0])
+ })
+
+ test("should return undefined for non-existent path", () => {
+ const data = { title: "Test", slug: "test", filePath: "test.md" }
+ trie.add(data)
+ const found = trie.findNode(["nonexistent"])
+ assert.strictEqual(found, undefined)
+ })
+
+ test("should return undefined for partial path", () => {
+ const data = {
+ title: "Nested",
+ slug: "folder/subfolder/test",
+ filePath: "folder/subfolder/test.md",
+ }
+ trie.add(data)
+ const found = trie.findNode(["folder"])
+ assert.strictEqual(found?.data, null)
+ })
+ })
+
describe("getFolderPaths", () => {
test("should return all folder paths", () => {
const data1 = {
diff --git a/quartz/util/fileTrie.ts b/quartz/util/fileTrie.ts
index b39833c..e3dc2e7 100644
--- a/quartz/util/fileTrie.ts
+++ b/quartz/util/fileTrie.ts
@@ -89,6 +89,14 @@
this.insert(file.slug.split("/"), file)
}
+ findNode(path: string[]): FileTrieNode<T> | undefined {
+ if (path.length === 0 || (path.length === 1 && path[0] === "index")) {
+ return this
+ }
+
+ return this.children.find((c) => c.slugSegment === path[0])?.findNode(path.slice(1))
+ }
+
/**
* Filter trie nodes. Behaves similar to `Array.prototype.filter()`, but modifies tree in place
*/
diff --git a/quartz/util/path.ts b/quartz/util/path.ts
index 6d99c36..32d846b 100644
--- a/quartz/util/path.ts
+++ b/quartz/util/path.ts
@@ -247,7 +247,7 @@
}
// path helpers
-function isFolderPath(fplike: string): boolean {
+export function isFolderPath(fplike: string): boolean {
return (
fplike.endsWith("/") ||
endsWith(fplike, "index") ||
--
Gitblit v1.10.0