fix: Support nested smart lists with cycle detection (#2470)

* fix: Support nested smart lists and prevent infinite loops
---------

Co-authored-by: Claude <noreply@anthropic.com>

4 files changed, 512 insertions, 27 deletions

diff --git a/packages/trpc/lib/__tests__/search.test.ts b/packages/trpc/lib/__tests__/search.test.ts
index ee8bfb60..d39e27a6 100644
--- a/packages/trpc/lib/__tests__/search.test.ts
+++ b/packages/trpc/lib/__tests__/search.test.ts
@@ -240,6 +240,61 @@ describe("getBookmarkIdsFromMatcher", () => {
     expect(result.sort()).toEqual(["b2", "b3", "b4", "b5"]);
   });
 
+  it("should handle listName matcher when multiple lists share the same name", async () => {
+    await mockCtx.db.insert(bookmarkLists).values({
+      id: "l5",
+      userId: testUserId,
+      name: "list1",
+      icon: "🚀",
+      type: "manual",
+    });
+    await mockCtx.db.insert(bookmarksInLists).values({
+      bookmarkId: "b2",
+      listId: "l5",
+    });
+
+    const matcher: Matcher = {
+      type: "listName",
+      listName: "list1",
+      inverse: false,
+    };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result.sort()).toEqual(["b1", "b2", "b6"]);
+  });
+
+  it("should handle inverse listName matcher when multiple lists share the same name", async () => {
+    await mockCtx.db.insert(bookmarkLists).values({
+      id: "l5",
+      userId: testUserId,
+      name: "list1",
+      icon: "🚀",
+      type: "manual",
+    });
+    await mockCtx.db.insert(bookmarksInLists).values({
+      bookmarkId: "b2",
+      listId: "l5",
+    });
+
+    const matcher: Matcher = {
+      type: "listName",
+      listName: "list1",
+      inverse: true,
+    };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result.sort()).toEqual(["b3", "b4", "b5"]);
+  });
+
+  it("should return empty when inverse listName references a missing list", async () => {
+    const matcher: Matcher = {
+      type: "listName",
+      listName: "does-not-exist",
+      inverse: true,
+    };
+
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result).toEqual([]);
+  });
+
   it("should handle archived matcher", async () => {
     const matcher: Matcher = { type: "archived", archived: true };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
diff --git a/packages/trpc/lib/search.ts b/packages/trpc/lib/search.ts
index 51e51d1c..d0f529f5 100644
--- a/packages/trpc/lib/search.ts
+++ b/packages/trpc/lib/search.ts
@@ -4,6 +4,7 @@ import {
   exists,
   gt,
   gte,
+  inArray,
   isNotNull,
   isNull,
   like,
@@ -11,6 +12,7 @@ import {
   lte,
   ne,
   notExists,
+  notInArray,
   notLike,
   or,
 } from "drizzle-orm";
@@ -89,10 +91,13 @@ function union(vals: BookmarkQueryReturnType[][]): BookmarkQueryReturnType[] {
 }
 
 async function getIds(
-  db: AuthedContext["db"],
-  userId: string,
+  ctx: AuthedContext,
   matcher: Matcher,
+  visitedListIds = new Set<string>(),
 ): Promise<BookmarkQueryReturnType[]> {
+  const { db } = ctx;
+  const userId = ctx.user.id;
+
   switch (matcher.type) {
     case "tagName": {
       const comp = matcher.inverse ? notExists : exists;
@@ -139,29 +144,54 @@ async function getIds(
         );
     }
     case "listName": {
-      const comp = matcher.inverse ? notExists : exists;
+      // First, look up the list by name
+      const lists = await db.query.bookmarkLists.findMany({
+        where: and(
+          eq(bookmarkLists.userId, userId),
+          eq(bookmarkLists.name, matcher.listName),
+        ),
+      });
+
+      if (lists.length === 0) {
+        // No matching lists
+        return [];
+      }
+
+      // Use List model to resolve list membership (manual and smart)
+      // Import dynamically to avoid circular dependency
+      const { List } = await import("../models/lists");
+      const listBookmarkIds = [
+        ...new Set(
+          (
+            await Promise.all(
+              lists.map(async (list) => {
+                const listModel = await List.fromId(ctx, list.id);
+                return await listModel.getBookmarkIds(visitedListIds);
+              }),
+            )
+          ).flat(),
+        ),
+      ];
+
+      if (listBookmarkIds.length === 0) {
+        if (matcher.inverse) {
+          return db
+            .selectDistinct({ id: bookmarks.id })
+            .from(bookmarks)
+            .where(eq(bookmarks.userId, userId));
+        }
+        return [];
+      }
+
       return db
         .selectDistinct({ id: bookmarks.id })
         .from(bookmarks)
         .where(
           and(
             eq(bookmarks.userId, userId),
-            comp(
-              db
-                .select()
-                .from(bookmarksInLists)
-                .innerJoin(
-                  bookmarkLists,
-                  eq(bookmarksInLists.listId, bookmarkLists.id),
-                )
-                .where(
-                  and(
-                    eq(bookmarksInLists.bookmarkId, bookmarks.id),
-                    eq(bookmarkLists.userId, userId),
-                    eq(bookmarkLists.name, matcher.listName),
-                  ),
-                ),
-            ),
+            matcher.inverse
+              ? notInArray(bookmarks.id, listBookmarkIds)
+              : inArray(bookmarks.id, listBookmarkIds),
           ),
         );
     }
@@ -391,13 +421,13 @@ async function getIds(
     }
     case "and": {
       const vals = await Promise.all(
-        matcher.matchers.map((m) => getIds(db, userId, m)),
+        matcher.matchers.map((m) => getIds(ctx, m, visitedListIds)),
       );
       return intersect(vals);
     }
     case "or": {
       const vals = await Promise.all(
-        matcher.matchers.map((m) => getIds(db, userId, m)),
+        matcher.matchers.map((m) => getIds(ctx, m, visitedListIds)),
       );
       return union(vals);
     }
@@ -411,7 +441,8 @@ async function getIds(
 export async function getBookmarkIdsFromMatcher(
   ctx: AuthedContext,
   matcher: Matcher,
+  visitedListIds = new Set<string>(),
 ): Promise<string[]> {
-  const results = await getIds(ctx.db, ctx.user.id, matcher);
+  const results = await getIds(ctx, matcher, visitedListIds);
   return results.map((r) => r.id);
 }
diff --git a/packages/trpc/models/lists.ts b/packages/trpc/models/lists.ts
index 29945b92..10d7d9bf 100644
--- a/packages/trpc/models/lists.ts
+++ b/packages/trpc/models/lists.ts
@@ -809,8 +809,8 @@ export abstract class List {
   }
 
   abstract get type(): "manual" | "smart";
-  abstract getBookmarkIds(ctx: AuthedContext): Promise<string[]>;
-  abstract getSize(ctx: AuthedContext): Promise<number>;
+  abstract getBookmarkIds(visitedListIds?: Set<string>): Promise<string[]>;
+  abstract getSize(): Promise<number>;
   abstract addBookmark(bookmarkId: string): Promise<void>;
   abstract removeBookmark(bookmarkId: string): Promise<void>;
   abstract mergeInto(
@@ -820,6 +820,8 @@ export abstract class List {
 }
 
 export class SmartList extends List {
+  private static readonly MAX_VISITED_LISTS = 30;
+
   parsedQuery: ReturnType<typeof parseSearchQuery> | null = null;
 
   constructor(ctx: AuthedContext, list: ZBookmarkList & { userId: string }) {
@@ -847,12 +849,27 @@ export class SmartList extends List {
     return this.parsedQuery;
   }
 
-  async getBookmarkIds(): Promise<string[]> {
+  async getBookmarkIds(visitedListIds = new Set<string>()): Promise<string[]> {
+    if (visitedListIds.size >= SmartList.MAX_VISITED_LISTS) {
+      return [];
+    }
+
+    if (visitedListIds.has(this.list.id)) {
+      return [];
+    }
+
+    const newVisitedListIds = new Set(visitedListIds);
+    newVisitedListIds.add(this.list.id);
+
     const parsedQuery = this.getParsedQuery();
     if (!parsedQuery.matcher) {
       return [];
     }
-    return await getBookmarkIdsFromMatcher(this.ctx, parsedQuery.matcher);
+    return await getBookmarkIdsFromMatcher(
+      this.ctx,
+      parsedQuery.matcher,
+      newVisitedListIds,
+    );
   }
 
   async getSize(): Promise<number> {
@@ -898,7 +915,7 @@ export class ManualList extends List {
     return this.list.type;
   }
 
-  async getBookmarkIds(): Promise<string[]> {
+  async getBookmarkIds(_visitedListIds?: Set<string>): Promise<string[]> {
     const results = await this.ctx.db
       .select({ id: bookmarksInLists.bookmarkId })
       .from(bookmarksInLists)
diff --git a/packages/trpc/routers/lists.test.ts b/packages/trpc/routers/lists.test.ts
index 8797b35e..214df32a 100644
--- a/packages/trpc/routers/lists.test.ts
+++ b/packages/trpc/routers/lists.test.ts
@@ -594,3 +594,385 @@ describe("recursive delete", () => {
     expect(lists.lists.find((l) => l.id === child.id)).toBeUndefined();
   });
 });
+
+describe("Nested smart lists", () => {
+  test<CustomTestContext>("smart list can reference another smart list", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create a bookmark that is favourited
+    const bookmark1 = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Favourited bookmark",
+    });
+    await api.bookmarks.updateBookmark({
+      bookmarkId: bookmark1.id,
+      favourited: true,
+    });
+
+    // Create a bookmark that is not favourited
+    const bookmark2 = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Non-favourited bookmark",
+    });
+
+    // Create a smart list that matches favourited bookmarks
+    await api.lists.create({
+      name: "Favourites",
+      type: "smart",
+      query: "is:fav",
+      icon: "⭐",
+    });
+
+    // Create a smart list that references the first smart list
+    const smartListB = await api.lists.create({
+      name: "From Favourites",
+      type: "smart",
+      query: "list:Favourites",
+      icon: "📋",
+    });
+
+    // Get bookmarks from the nested smart list
+    const bookmarksInSmartListB = await api.bookmarks.getBookmarks({
+      listId: smartListB.id,
+    });
+
+    // Should contain the favourited bookmark
+    expect(bookmarksInSmartListB.bookmarks.length).toBe(1);
+    expect(bookmarksInSmartListB.bookmarks[0].id).toBe(bookmark1.id);
+
+    // Verify bookmark2 is not in the nested smart list
+    expect(
+      bookmarksInSmartListB.bookmarks.find((b) => b.id === bookmark2.id),
+    ).toBeUndefined();
+  });
+
+  test<CustomTestContext>("nested smart lists with multiple levels", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create a bookmark that is archived
+    const bookmark = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Archived bookmark",
+    });
+    await api.bookmarks.updateBookmark({
+      bookmarkId: bookmark.id,
+      archived: true,
+    });
+
+    // Create smart list A: matches archived bookmarks
+    await api.lists.create({
+      name: "Archived",
+      type: "smart",
+      query: "is:archived",
+      icon: "📦",
+    });
+
+    // Create smart list B: references list A
+    await api.lists.create({
+      name: "Level1",
+      type: "smart",
+      query: "list:Archived",
+      icon: "1️⃣",
+    });
+
+    // Create smart list C: references list B (3 levels deep)
+    const smartListC = await api.lists.create({
+      name: "Level2",
+      type: "smart",
+      query: "list:Level1",
+      icon: "2️⃣",
+    });
+
+    // Get bookmarks from the deepest nested smart list
+    const bookmarksInSmartListC = await api.bookmarks.getBookmarks({
+      listId: smartListC.id,
+    });
+
+    // Should contain the archived bookmark
+    expect(bookmarksInSmartListC.bookmarks.length).toBe(1);
+    expect(bookmarksInSmartListC.bookmarks[0].id).toBe(bookmark.id);
+  });
+
+  test<CustomTestContext>("smart list with inverse reference to another smart list", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create two bookmarks
+    const favouritedBookmark = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Favourited bookmark",
+    });
+    await api.bookmarks.updateBookmark({
+      bookmarkId: favouritedBookmark.id,
+      favourited: true,
+    });
+
+    const normalBookmark = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Normal bookmark",
+    });
+
+    // Create a smart list that matches favourited bookmarks
+    await api.lists.create({
+      name: "Favourites",
+      type: "smart",
+      query: "is:fav",
+      icon: "⭐",
+    });
+
+    // Create a smart list with negative reference to Favourites
+    const notInFavourites = await api.lists.create({
+      name: "Not In Favourites",
+      type: "smart",
+      query: "-list:Favourites",
+      icon: "❌",
+    });
+
+    // Get bookmarks from the smart list
+    const bookmarksNotInFav = await api.bookmarks.getBookmarks({
+      listId: notInFavourites.id,
+    });
+
+    // Should contain only the non-favourited bookmark
+    expect(bookmarksNotInFav.bookmarks.length).toBe(1);
+    expect(bookmarksNotInFav.bookmarks[0].id).toBe(normalBookmark.id);
+  });
+
+  test<CustomTestContext>("circular reference between smart lists returns empty", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create a bookmark
+    const bookmark = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Test bookmark",
+    });
+    await api.bookmarks.updateBookmark({
+      bookmarkId: bookmark.id,
+      favourited: true,
+    });
+
+    // Create smart list A that references smart list B
+    const smartListA = await api.lists.create({
+      name: "ListA",
+      type: "smart",
+      query: "list:ListB",
+      icon: "🅰️",
+    });
+
+    // Create smart list B that references smart list A (circular!)
+    await api.lists.create({
+      name: "ListB",
+      type: "smart",
+      query: "list:ListA",
+      icon: "🅱️",
+    });
+
+    // Querying ListA should return empty because of the circular reference
+    const bookmarksInListA = await api.bookmarks.getBookmarks({
+      listId: smartListA.id,
+    });
+
+    // Should be empty due to circular reference detection
+    expect(bookmarksInListA.bookmarks.length).toBe(0);
+  });
+
+  test<CustomTestContext>("self-referencing smart list returns empty", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create a bookmark
+    await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Test bookmark",
+    });
+
+    // Create a smart list that references itself
+    const selfRefList = await api.lists.create({
+      name: "SelfRef",
+      type: "smart",
+      query: "list:SelfRef",
+      icon: "🔄",
+    });
+
+    // Querying should return empty because of self-reference
+    const bookmarks = await api.bookmarks.getBookmarks({
+      listId: selfRefList.id,
+    });
+
+    expect(bookmarks.bookmarks.length).toBe(0);
+  });
+
+  test<CustomTestContext>("three-way circular reference returns empty", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create a bookmark
+    await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Test bookmark",
+    });
+
+    // Create three smart lists with circular references: A -> B -> C -> A
+    const listA = await api.lists.create({
+      name: "CircularA",
+      type: "smart",
+      query: "list:CircularB",
+      icon: "🅰️",
+    });
+
+    await api.lists.create({
+      name: "CircularB",
+      type: "smart",
+      query: "list:CircularC",
+      icon: "🅱️",
+    });
+
+    await api.lists.create({
+      name: "CircularC",
+      type: "smart",
+      query: "list:CircularA",
+      icon: "©️",
+    });
+
+    // Querying any of them should return empty due to circular reference
+    const bookmarksInListA = await api.bookmarks.getBookmarks({
+      listId: listA.id,
+    });
+
+    expect(bookmarksInListA.bookmarks.length).toBe(0);
+  });
+
+  test<CustomTestContext>("smart list traversal above max visited lists returns empty", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    const bookmark = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Depth test bookmark",
+    });
+
+    const manualList = await api.lists.create({
+      name: "DepthBaseManual",
+      type: "manual",
+      icon: "📋",
+    });
+    await api.lists.addToList({
+      listId: manualList.id,
+      bookmarkId: bookmark.id,
+    });
+
+    const maxVisitedLists = 30;
+    const overLimitChainLength = maxVisitedLists + 1;
+
+    for (let i = overLimitChainLength; i >= 2; i--) {
+      await api.lists.create({
+        name: `DepthL${i}`,
+        type: "smart",
+        query:
+          i === overLimitChainLength
+            ? "list:DepthBaseManual"
+            : `list:DepthL${i + 1}`,
+        icon: "D",
+      });
+    }
+
+    const depthRoot = await api.lists.create({
+      name: "DepthL1",
+      type: "smart",
+      query: "list:DepthL2",
+      icon: "D",
+    });
+
+    const bookmarksInRoot = await api.bookmarks.getBookmarks({
+      listId: depthRoot.id,
+    });
+
+    expect(bookmarksInRoot.bookmarks.length).toBe(0);
+  });
+
+  test<CustomTestContext>("smart list references non-existent list returns empty", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create a bookmark
+    await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Test bookmark",
+    });
+
+    // Create a smart list that references a non-existent list
+    const smartList = await api.lists.create({
+      name: "RefNonExistent",
+      type: "smart",
+      query: "list:NonExistentList",
+      icon: "❓",
+    });
+
+    // Should return empty since the referenced list doesn't exist
+    const bookmarks = await api.bookmarks.getBookmarks({
+      listId: smartList.id,
+    });
+
+    expect(bookmarks.bookmarks.length).toBe(0);
+  });
+
+  test<CustomTestContext>("smart list can reference manual list", async ({
+    apiCallers,
+  }) => {
+    const api = apiCallers[0];
+
+    // Create bookmarks
+    const bookmark1 = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Bookmark in manual list",
+    });
+    const bookmark2 = await api.bookmarks.createBookmark({
+      type: BookmarkTypes.TEXT,
+      text: "Bookmark not in list",
+    });
+
+    // Create a manual list and add bookmark1
+    const manualList = await api.lists.create({
+      name: "ManualList",
+      type: "manual",
+      icon: "📋",
+    });
+    await api.lists.addToList({
+      listId: manualList.id,
+      bookmarkId: bookmark1.id,
+    });
+
+    // Create a smart list that references the manual list
+    const smartList = await api.lists.create({
+      name: "SmartRefManual",
+      type: "smart",
+      query: "list:ManualList",
+      icon: "🔗",
+    });
+
+    // Get bookmarks from the smart list
+    const bookmarksInSmartList = await api.bookmarks.getBookmarks({
+      listId: smartList.id,
+    });
+
+    // Should contain only bookmark1
+    expect(bookmarksInSmartList.bookmarks.length).toBe(1);
+    expect(bookmarksInSmartList.bookmarks[0].id).toBe(bookmark1.id);
+
+    // Verify bookmark2 is not in the smart list
+    expect(
+      bookmarksInSmartList.bookmarks.find((b) => b.id === bookmark2.id),
+    ).toBeUndefined();
+  });
+});