fix(folder): use memoized trie instead of handrolled path solution (closes ...

Jacky Zhao

2025-03-14 fbb452385325d4418ce53e61178fe2494255caf5

fix(folder): use memoized trie instead of handrolled path solution (closes #1767)

 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()

 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) => {
      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

      if (!prefixed) {
        return
      }

      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 (file.frontmatter) {
          trie.add({
            ...file,
            slug: file.slug!,
            title: file.frontmatter.title,
            filePath: file.filePath!,
          })
      }
    })
    }

    allPagesInSubfolders.forEach((files, subfolderSlug) => {
      const hasIndex = allPagesInFolder.some(
        (file) => subfolderSlug === stripSlashes(simplifySlug(file.slug!)),
    const folder = trie.findNode(fileData.slug!.split("/"))
    if (!folder) {
      return null
    }

    const allPagesInFolder: QuartzPluginData[] =
      folder.children
        .map((node) => {
          // regular file, proceed
          if (node.data) {
            return node.data
          }

          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
                    }

                    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(),
                }
      )
      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"] },
        })
            }

            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 = {

 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 = {

 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
   */

 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") ||