feat: Add support for negative search terms

6 files changed, 282 insertions, 69 deletions

diff --git a/apps/web/components/dashboard/search/QueryExplainerTooltip.tsx b/apps/web/components/dashboard/search/QueryExplainerTooltip.tsx
index 191c9ff3..0a325031 100644
--- a/apps/web/components/dashboard/search/QueryExplainerTooltip.tsx
+++ b/apps/web/components/dashboard/search/QueryExplainerTooltip.tsx
@@ -20,28 +20,32 @@ export default function QueryExplainerTooltip({
       case "tagName":
         return (
           <TableRow>
-            <TableCell>Tag Name</TableCell>
+            <TableCell>
+              {matcher.inverse ? "Doesn't have" : "Has"} Tag
+            </TableCell>
             <TableCell>{matcher.tagName}</TableCell>
           </TableRow>
         );
       case "listName":
         return (
           <TableRow>
-            <TableCell>List Name</TableCell>
+            <TableCell>
+              {matcher.inverse ? "Is not in" : "Is in "} List
+            </TableCell>
             <TableCell>{matcher.listName}</TableCell>
           </TableRow>
         );
       case "dateAfter":
         return (
           <TableRow>
-            <TableCell>Created After</TableCell>
+            <TableCell>{matcher.inverse ? "Not" : ""} Created After</TableCell>
             <TableCell>{matcher.dateAfter.toDateString()}</TableCell>
           </TableRow>
         );
       case "dateBefore":
         return (
           <TableRow>
-            <TableCell>Created Before</TableCell>
+            <TableCell>{matcher.inverse ? "Not" : ""} Created Before</TableCell>
             <TableCell>{matcher.dateBefore.toDateString()}</TableCell>
           </TableRow>
         );
diff --git a/packages/shared/searchQueryParser.test.ts b/packages/shared/searchQueryParser.test.ts
index 428d5929..5bbb3f77 100644
--- a/packages/shared/searchQueryParser.test.ts
+++ b/packages/shared/searchQueryParser.test.ts
@@ -12,7 +12,7 @@ describe("Search Query Parser", () => {
         archived: true,
       },
     });
-    expect(parseSearchQuery("is:not_archived")).toEqual({
+    expect(parseSearchQuery("-is:archived")).toEqual({
       result: "full",
       text: "",
       matcher: {
@@ -28,7 +28,7 @@ describe("Search Query Parser", () => {
         favourited: true,
       },
     });
-    expect(parseSearchQuery("is:not_fav")).toEqual({
+    expect(parseSearchQuery("-is:fav")).toEqual({
       result: "full",
       text: "",
       matcher: {
@@ -45,6 +45,16 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "url",
         url: "https://example.com",
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery("-url:https://example.com")).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "url",
+        url: "https://example.com",
+        inverse: true,
       },
     });
     expect(parseSearchQuery('url:"https://example.com"')).toEqual({
@@ -53,6 +63,16 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "url",
         url: "https://example.com",
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery('-url:"https://example.com"')).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "url",
+        url: "https://example.com",
+        inverse: true,
       },
     });
     expect(parseSearchQuery("#my-tag")).toEqual({
@@ -61,6 +81,16 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "tagName",
         tagName: "my-tag",
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery("-#my-tag")).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "tagName",
+        tagName: "my-tag",
+        inverse: true,
       },
     });
     expect(parseSearchQuery('#"my tag"')).toEqual({
@@ -69,6 +99,16 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "tagName",
         tagName: "my tag",
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery('-#"my tag"')).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "tagName",
+        tagName: "my tag",
+        inverse: true,
       },
     });
     expect(parseSearchQuery("list:my-list")).toEqual({
@@ -77,6 +117,16 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "listName",
         listName: "my-list",
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery("-list:my-list")).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "listName",
+        listName: "my-list",
+        inverse: true,
       },
     });
     expect(parseSearchQuery('list:"my list"')).toEqual({
@@ -85,6 +135,16 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "listName",
         listName: "my list",
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery('-list:"my list"')).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "listName",
+        listName: "my list",
+        inverse: true,
       },
     });
   });
@@ -95,6 +155,16 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "dateAfter",
         dateAfter: new Date("2023-10-12"),
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery("-after:2023-10-12")).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "dateAfter",
+        dateAfter: new Date("2023-10-12"),
+        inverse: true,
       },
     });
     expect(parseSearchQuery("before:2023-10-12")).toEqual({
@@ -103,12 +173,22 @@ describe("Search Query Parser", () => {
       matcher: {
         type: "dateBefore",
         dateBefore: new Date("2023-10-12"),
+        inverse: false,
+      },
+    });
+    expect(parseSearchQuery("-before:2023-10-12")).toEqual({
+      result: "full",
+      text: "",
+      matcher: {
+        type: "dateBefore",
+        dateBefore: new Date("2023-10-12"),
+        inverse: true,
       },
     });
   });
 
   test("complex queries", () => {
-    expect(parseSearchQuery("is:fav is:archived")).toEqual({
+    expect(parseSearchQuery("is:fav -is:archived")).toEqual({
       result: "full",
       text: "",
       matcher: {
@@ -120,7 +200,7 @@ describe("Search Query Parser", () => {
           },
           {
             type: "archived",
-            archived: true,
+            archived: false,
           },
         ],
       },
@@ -143,6 +223,7 @@ describe("Search Query Parser", () => {
           {
             type: "tagName",
             tagName: "my-tag",
+            inverse: false,
           },
         ],
       },
@@ -170,6 +251,7 @@ describe("Search Query Parser", () => {
           {
             type: "tagName",
             tagName: "my-tag",
+            inverse: false,
           },
         ],
       },
@@ -197,6 +279,7 @@ describe("Search Query Parser", () => {
           {
             type: "tagName",
             tagName: "my-tag",
+            inverse: false,
           },
         ],
       },
@@ -237,6 +320,7 @@ describe("Search Query Parser", () => {
           {
             type: "tagName",
             tagName: "my-tag",
+            inverse: false,
           },
         ],
       },
diff --git a/packages/shared/searchQueryParser.ts b/packages/shared/searchQueryParser.ts
index faf74d08..02129c14 100644
--- a/packages/shared/searchQueryParser.ts
+++ b/packages/shared/searchQueryParser.ts
@@ -5,6 +5,7 @@ import {
   kmid,
   kright,
   lrec_sc,
+  opt,
   rule,
   seq,
   str,
@@ -28,6 +29,7 @@ enum TokenType {
   RParen = "RPAREN",
   Space = "SPACE",
   Hash = "HASH",
+  Minus = "MINUS",
 }
 
 // Rules are in order of priority
@@ -43,6 +45,7 @@ const lexerRules: [RegExp, TokenType][] = [
   [/^\(/, TokenType.LParen],
   [/^\)/, TokenType.RParen],
   [/^\s+/, TokenType.Space],
+  [/^-/, TokenType.Minus],
 
   // This needs to be last as it matches a lot of stuff
   [/^[^ )(]+/, TokenType.Ident],
@@ -109,38 +112,32 @@ const EXP = rule<TokenType, TextAndMatcher>();
 
 MATCHER.setPattern(
   alt_sc(
-    apply(kright(str("is:"), tok(TokenType.Ident)), (toks) => {
-      switch (toks.text) {
-        case "fav":
-          return {
-            text: "",
-            matcher: { type: "favourited", favourited: true },
-          };
-        case "not_fav":
-          return {
-            text: "",
-            matcher: { type: "favourited", favourited: false },
-          };
-        case "archived":
-          return {
-            text: "",
-            matcher: { type: "archived", archived: true },
-          };
-        case "not_archived":
-          return {
-            text: "",
-            matcher: { type: "archived", archived: false },
-          };
-        default:
-          // If the token is not known, emit it as pure text
-          return {
-            text: `is:${toks.text}`,
-            matcher: undefined,
-          };
-      }
-    }),
+    apply(
+      seq(opt(str("-")), kright(str("is:"), tok(TokenType.Ident))),
+      ([minus, ident]) => {
+        switch (ident.text) {
+          case "fav":
+            return {
+              text: "",
+              matcher: { type: "favourited", favourited: !minus },
+            };
+          case "archived":
+            return {
+              text: "",
+              matcher: { type: "archived", archived: !minus },
+            };
+          default:
+            // If the token is not known, emit it as pure text
+            return {
+              text: `${minus?.text ?? ""}is:${ident.text}`,
+              matcher: undefined,
+            };
+        }
+      },
+    ),
     apply(
       seq(
+        opt(str("-")),
         alt(tok(TokenType.Qualifier), tok(TokenType.Hash)),
         alt(
           apply(tok(TokenType.Ident), (tok) => {
@@ -151,22 +148,22 @@ MATCHER.setPattern(
           }),
         ),
       ),
-      (toks) => {
-        switch (toks[0].text) {
+      ([minus, qualifier, ident]) => {
+        switch (qualifier.text) {
           case "url:":
             return {
               text: "",
-              matcher: { type: "url", url: toks[1] },
+              matcher: { type: "url", url: ident, inverse: !!minus },
             };
           case "#":
             return {
               text: "",
-              matcher: { type: "tagName", tagName: toks[1] },
+              matcher: { type: "tagName", tagName: ident, inverse: !!minus },
             };
           case "list:":
             return {
               text: "",
-              matcher: { type: "listName", listName: toks[1] },
+              matcher: { type: "listName", listName: ident, inverse: !!minus },
             };
           case "after:":
             try {
@@ -174,13 +171,14 @@ MATCHER.setPattern(
                 text: "",
                 matcher: {
                   type: "dateAfter",
-                  dateAfter: z.coerce.date().parse(toks[1]),
+                  dateAfter: z.coerce.date().parse(ident),
+                  inverse: !!minus,
                 },
               };
             } catch (e) {
               return {
                 // If parsing the date fails, emit it as pure text
-                text: toks[0].text + toks[1],
+                text: (minus?.text ?? "") + qualifier.text + ident,
                 matcher: undefined,
               };
             }
@@ -190,20 +188,21 @@ MATCHER.setPattern(
                 text: "",
                 matcher: {
                   type: "dateBefore",
-                  dateBefore: z.coerce.date().parse(toks[1]),
+                  dateBefore: z.coerce.date().parse(ident),
+                  inverse: !!minus,
                 },
               };
             } catch (e) {
               return {
                 // If parsing the date fails, emit it as pure text
-                text: toks[0].text + toks[1],
+                text: (minus?.text ?? "") + qualifier.text + ident,
                 matcher: undefined,
               };
             }
           default:
             // If the token is not known, emit it as pure text
             return {
-              text: toks[0].text + toks[1],
+              text: (minus?.text ?? "") + qualifier.text + ident,
               matcher: undefined,
             };
         }
diff --git a/packages/shared/types/search.ts b/packages/shared/types/search.ts
index d430dad5..4d947a05 100644
--- a/packages/shared/types/search.ts
+++ b/packages/shared/types/search.ts
@@ -3,11 +3,13 @@ import { z } from "zod";
 const zTagNameMatcher = z.object({
   type: z.literal("tagName"),
   tagName: z.string(),
+  inverse: z.boolean(),
 });
 
 const zListNameMatcher = z.object({
   type: z.literal("listName"),
   listName: z.string(),
+  inverse: z.boolean(),
 });
 
 const zArchivedMatcher = z.object({
@@ -18,6 +20,7 @@ const zArchivedMatcher = z.object({
 const urlMatcher = z.object({
   type: z.literal("url"),
   url: z.string(),
+  inverse: z.boolean(),
 });
 
 const zFavouritedMatcher = z.object({
@@ -28,11 +31,13 @@ const zFavouritedMatcher = z.object({
 const zDateAfterMatcher = z.object({
   type: z.literal("dateAfter"),
   dateAfter: z.date(),
+  inverse: z.boolean(),
 });
 
 const zDateBeforeMatcher = z.object({
   type: z.literal("dateBefore"),
   dateBefore: z.date(),
+  inverse: z.boolean(),
 });
 
 const zNonRecursiveMatcher = z.union([
diff --git a/packages/trpc/lib/__tests__/search.test.ts b/packages/trpc/lib/__tests__/search.test.ts
index aa57527b..31f87dfd 100644
--- a/packages/trpc/lib/__tests__/search.test.ts
+++ b/packages/trpc/lib/__tests__/search.test.ts
@@ -160,53 +160,130 @@ beforeEach(async () => {
 
 describe("getBookmarkIdsFromMatcher", () => {
   it("should handle tagName matcher", async () => {
-    const matcher: Matcher = { type: "tagName", tagName: "tag1" };
+    const matcher: Matcher = {
+      type: "tagName",
+      tagName: "tag1",
+      inverse: false,
+    };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
     expect(result).toEqual(["b1"]);
   });
 
+  it("should handle tagName matcher with inverse=true", async () => {
+    const matcher: Matcher = {
+      type: "tagName",
+      tagName: "tag1",
+      inverse: true,
+    };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result.sort()).toEqual(["b2", "b3", "b4", "b5", "b6"]);
+  });
+
   it("should handle listName matcher", async () => {
-    const matcher: Matcher = { type: "listName", listName: "list1" };
+    const matcher: Matcher = {
+      type: "listName",
+      listName: "list1",
+      inverse: false,
+    };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
     expect(result).toEqual(["b1", "b6"]);
   });
 
+  it("should handle listName matcher with inverse=true", async () => {
+    const matcher: Matcher = {
+      type: "listName",
+      listName: "list1",
+      inverse: true,
+    };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result.sort()).toEqual(["b2", "b3", "b4", "b5"]);
+  });
+
   it("should handle archived matcher", async () => {
     const matcher: Matcher = { type: "archived", archived: true };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
     expect(result).toEqual(["b2", "b3", "b6"]);
   });
 
+  it("should handle archived matcher archived=false", async () => {
+    const matcher: Matcher = { type: "archived", archived: false };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result).toEqual(["b1", "b4", "b5"]);
+  });
+
   it("should handle favourited matcher", async () => {
     const matcher: Matcher = { type: "favourited", favourited: true };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
     expect(result).toEqual(["b2", "b4"]);
   });
 
+  it("should handle favourited matcher favourited=false", async () => {
+    const matcher: Matcher = { type: "favourited", favourited: false };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result).toEqual(["b1", "b3", "b5", "b6"]);
+  });
+
   it("should handle url matcher", async () => {
-    const matcher: Matcher = { type: "url", url: "example.com" };
+    const matcher: Matcher = {
+      type: "url",
+      url: "example.com",
+      inverse: false,
+    };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
     expect(result).toEqual(["b1", "b4"]);
   });
 
+  it("should handle url matcher with inverse=true", async () => {
+    const matcher: Matcher = {
+      type: "url",
+      url: "example.com",
+      inverse: true,
+    };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    // Not that only bookmarks of type link are returned
+    expect(result.sort()).toEqual(["b2"]);
+  });
+
   it("should handle dateAfter matcher", async () => {
     const matcher: Matcher = {
       type: "dateAfter",
       dateAfter: new Date("2024-01-02"),
+      inverse: false,
     };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
     expect(result).toEqual(["b2", "b3", "b4", "b5", "b6"]);
   });
 
+  it("should handle dateAfter matcher with inverse=true", async () => {
+    const matcher: Matcher = {
+      type: "dateAfter",
+      dateAfter: new Date("2024-01-02"),
+      inverse: true,
+    };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result).toEqual(["b1"]);
+  });
+
   it("should handle dateBefore matcher", async () => {
     const matcher: Matcher = {
       type: "dateBefore",
       dateBefore: new Date("2024-01-02"),
+      inverse: false,
     };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
     expect(result).toEqual(["b1", "b2"]);
   });
 
+  it("should handle dateBefore matcher with inverse=true", async () => {
+    const matcher: Matcher = {
+      type: "dateBefore",
+      dateBefore: new Date("2024-01-02"),
+      inverse: true,
+    };
+    const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
+    expect(result.sort()).toEqual(["b3", "b4", "b5", "b6"]);
+  });
+
   it("should handle AND matcher", async () => {
     const matcher: Matcher = {
       type: "and",
@@ -235,8 +312,8 @@ describe("getBookmarkIdsFromMatcher", () => {
     const matcher: Matcher = {
       type: "or",
       matchers: [
-        { type: "listName", listName: "favorites" },
-        { type: "tagName", tagName: "work" },
+        { type: "listName", listName: "favorites", inverse: false },
+        { type: "tagName", tagName: "work", inverse: false },
       ],
     };
     const result = await getBookmarkIdsFromMatcher(mockCtx, matcher);
@@ -250,8 +327,8 @@ describe("getBookmarkIdsFromMatcher", () => {
         {
           type: "or",
           matchers: [
-            { type: "listName", listName: "favorites" },
-            { type: "tagName", tagName: "work" },
+            { type: "listName", listName: "favorites", inverse: false },
+            { type: "tagName", tagName: "work", inverse: false },
           ],
         },
         {
diff --git a/packages/trpc/lib/search.ts b/packages/trpc/lib/search.ts
index 0ee9c76e..fcc5abda 100644
--- a/packages/trpc/lib/search.ts
+++ b/packages/trpc/lib/search.ts
@@ -1,4 +1,15 @@
-import { and, eq, gte, like, lte, sql } from "drizzle-orm";
+import {
+  and,
+  eq,
+  exists,
+  gt,
+  gte,
+  like,
+  lt,
+  lte,
+  notExists,
+  notLike,
+} from "drizzle-orm";
 
 import {
   bookmarkLinks,
@@ -76,26 +87,56 @@ async function getIds(
 ): Promise<BookmarkQueryReturnType[]> {
   switch (matcher.type) {
     case "tagName": {
+      const comp = matcher.inverse ? notExists : exists;
       return db
-        .select({ id: sql<string>`${tagsOnBookmarks.bookmarkId}`.as("id") })
-        .from(tagsOnBookmarks)
-        .innerJoin(bookmarkTags, eq(tagsOnBookmarks.tagId, bookmarkTags.id))
+        .selectDistinct({ id: bookmarks.id })
+        .from(bookmarks)
         .where(
           and(
-            eq(bookmarkTags.userId, userId),
-            eq(bookmarkTags.name, matcher.tagName),
+            eq(bookmarks.userId, userId),
+            comp(
+              db
+                .select()
+                .from(tagsOnBookmarks)
+                .innerJoin(
+                  bookmarkTags,
+                  eq(tagsOnBookmarks.tagId, bookmarkTags.id),
+                )
+                .where(
+                  and(
+                    eq(tagsOnBookmarks.bookmarkId, bookmarks.id),
+                    eq(bookmarkTags.userId, userId),
+                    eq(bookmarkTags.name, matcher.tagName),
+                  ),
+                ),
+            ),
           ),
         );
     }
     case "listName": {
+      const comp = matcher.inverse ? notExists : exists;
       return db
-        .select({ id: sql<string>`${bookmarksInLists.bookmarkId}`.as("id") })
-        .from(bookmarksInLists)
-        .innerJoin(bookmarkLists, eq(bookmarksInLists.listId, bookmarkLists.id))
+        .selectDistinct({ id: bookmarks.id })
+        .from(bookmarks)
         .where(
           and(
-            eq(bookmarkLists.userId, userId),
-            eq(bookmarkLists.name, matcher.listName),
+            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),
+                  ),
+                ),
+            ),
           ),
         );
     }
@@ -111,6 +152,7 @@ async function getIds(
         );
     }
     case "url": {
+      const comp = matcher.inverse ? notLike : like;
       return db
         .select({ id: bookmarkLinks.id })
         .from(bookmarkLinks)
@@ -118,7 +160,7 @@ async function getIds(
         .where(
           and(
             eq(bookmarks.userId, userId),
-            like(bookmarkLinks.url, `%${matcher.url}%`),
+            comp(bookmarkLinks.url, `%${matcher.url}%`),
           ),
         );
     }
@@ -134,24 +176,26 @@ async function getIds(
         );
     }
     case "dateAfter": {
+      const comp = matcher.inverse ? lt : gte;
       return db
         .select({ id: bookmarks.id })
         .from(bookmarks)
         .where(
           and(
             eq(bookmarks.userId, userId),
-            gte(bookmarks.createdAt, matcher.dateAfter),
+            comp(bookmarks.createdAt, matcher.dateAfter),
           ),
         );
     }
     case "dateBefore": {
+      const comp = matcher.inverse ? gt : lte;
       return db
         .select({ id: bookmarks.id })
         .from(bookmarks)
         .where(
           and(
             eq(bookmarks.userId, userId),
-            lte(bookmarks.createdAt, matcher.dateBefore),
+            comp(bookmarks.createdAt, matcher.dateBefore),
           ),
         );
     }