Merge pull request #736 from ueokande/completion-performance

Improve completion performance on the console

4 files changed, 170 insertions, 28 deletions

diff --git a/src/background/completion/impl/BookmarkRepositoryImpl.ts b/src/background/completion/impl/BookmarkRepositoryImpl.ts
index 58df129..f34c7d1 100644
--- a/src/background/completion/impl/BookmarkRepositoryImpl.ts
+++ b/src/background/completion/impl/BookmarkRepositoryImpl.ts
@@ -1,11 +1,21 @@
-import { injectable } from "tsyringe";
 import BookmarkRepository, {BookmarkItem} from "../BookmarkRepository";
+import {HistoryItem} from "../HistoryRepository";
+import PrefetchAndCache from "./PrefetchAndCache";
 
 const COMPLETION_ITEM_LIMIT = 10;
 
-@injectable()
-export default class BookmarkRepositoryImpl implements BookmarkRepository {
-  async queryBookmarks(query: string): Promise<BookmarkItem[]> {
+export default class CachedBookmarkRepository implements BookmarkRepository {
+  private bookmarkCache: PrefetchAndCache<BookmarkItem>;
+
+  constructor() {
+    this.bookmarkCache = new PrefetchAndCache(this.getter, this.filter, 10,);
+  }
+
+  queryBookmarks(query: string): Promise<BookmarkItem[]> {
+    return this.bookmarkCache.get(query);
+  }
+
+  private async getter(query: string): Promise<BookmarkItem[]> {
     const items = await browser.bookmarks.search({query});
     return items
       .filter(item => item.title && item.title.length > 0)
@@ -25,4 +35,12 @@ export default class BookmarkRepositoryImpl implements BookmarkRepository {
         url: item.url!!,
       }));
   }
+
+  private filter(items: HistoryItem[], query: string) {
+    return items.filter(item => {
+      return query.split(' ').some(keyword => {
+        return item.title.toLowerCase().includes(keyword.toLowerCase()) || item.url.includes(keyword)
+      });
+    })
+  };
 }
diff --git a/src/background/completion/impl/HistoryRepositoryImpl.ts b/src/background/completion/impl/HistoryRepositoryImpl.ts
index 42691aa..cd55cd0 100644
--- a/src/background/completion/impl/HistoryRepositoryImpl.ts
+++ b/src/background/completion/impl/HistoryRepositoryImpl.ts
@@ -1,12 +1,39 @@
-import { injectable } from "tsyringe";
 import * as filters from "./filters";
 import HistoryRepository, {HistoryItem} from "../HistoryRepository";
+import PrefetchAndCache from "./PrefetchAndCache";
 
 const COMPLETION_ITEM_LIMIT = 10;
 
-@injectable()
-export default class HistoryRepositoryImpl implements HistoryRepository {
+export default class CachedHistoryRepository implements HistoryRepository {
+  private historyCache: PrefetchAndCache<browser.history.HistoryItem>;
+
+  constructor() {
+    this.historyCache = new PrefetchAndCache(this.getter, this.filter, 10)
+  }
+
   async queryHistories(keywords: string): Promise<HistoryItem[]> {
+    const items = await this.historyCache.get(keywords);
+
+    const filterOrKeep = <T>(source: T[], filter: (items: T[]) => T[], min: number): T[] => {
+      const filtered = filter(source);
+      if (filtered.length < min) {
+        return source;
+      }
+      return filtered;
+    };
+
+    return [items]
+        .map(items => filterOrKeep(items, filters.filterByPathname, COMPLETION_ITEM_LIMIT))
+        .map(items => filterOrKeep(items, filters.filterByOrigin,  COMPLETION_ITEM_LIMIT))[0]
+        .sort((x, y) => Number(y.visitCount) - Number(x.visitCount))
+        .slice(0, COMPLETION_ITEM_LIMIT)
+        .map(item => ({
+          title: item.title!!,
+          url: item.url!!,
+        }));
+  }
+
+  private async getter (keywords: string): Promise<browser.history.HistoryItem[]> {
     const items = await browser.history.search({
       text: keywords,
       startTime: 0,
@@ -15,14 +42,14 @@ export default class HistoryRepositoryImpl implements HistoryRepository {
     return [items]
       .map(filters.filterBlankTitle)
       .map(filters.filterHttp)
-      .map(filters.filterByTailingSlash)
-      .map(pages => filters.filterByPathname(pages, COMPLETION_ITEM_LIMIT))
-      .map(pages => filters.filterByOrigin(pages, COMPLETION_ITEM_LIMIT))[0]
-      .sort((x, y) => Number(y.visitCount) - Number(x.visitCount))
-      .slice(0, COMPLETION_ITEM_LIMIT)
-      .map(item => ({
-        title: item.title!!,
-        url: item.url!!,
-      }))
+      .map(filters.filterByTailingSlash)[0]
   }
+
+  private filter(items: browser.history.HistoryItem[], query: string) {
+    return items.filter(item => {
+      return query.split(' ').every(keyword => {
+        return item.title!!.toLowerCase().includes(keyword.toLowerCase()) || item.url!!.includes(keyword)
+      });
+    })
+  };
 }
diff --git a/src/background/completion/impl/PrefetchAndCache.ts b/src/background/completion/impl/PrefetchAndCache.ts
new file mode 100644
index 0000000..3c074c2
--- /dev/null
+++ b/src/background/completion/impl/PrefetchAndCache.ts
@@ -0,0 +1,105 @@
+type Getter<T> = (query: string) => Promise<T[]>;
+type Filter<T> = (src: T[], query: string) => T[];
+
+const WHITESPACE = /\s/;
+
+// `shortKey` returns a shorten key to pre-fetch completions and store in the
+// cache.  The shorten key is generated by the following rules:
+// 
+// 1. If the query contains a space in the middle: i.e. the query consists of
+//    multiple words, the method removes the last word from the query, and
+//    returns joined remaining words with space.
+// 
+// 2. If the query is a single word and it's an URL, the method returns a new
+//    URL excluding search query with the upper path of the original URL.
+// 
+// 3. If the query is a single word and it's not an URL, the method returns a
+//    word with the half-length of the original query.
+//
+//  Examples:
+//
+//    shortKey("hello world good bye")
+//    => "hello world good"
+//
+//    shortKey("https://example.com/path/to/resource?q=hello")
+//    => "https://example.com/path/to/"
+//
+//    shortKey("the-query-with-super-long-word")
+//    => "the-query-with-"
+//
+export const shortKey = (query: string): string => {
+  if (WHITESPACE.test(query)) {
+      return query.split(WHITESPACE).filter(word => word.length > 0).slice(0, -1).join(' ');
+  }
+  let url;
+  try {
+    url = new URL(query)
+  } catch (e) {
+    return query.slice(0, query.length / 2);
+  }
+
+  if (url.origin === query) {
+    // may be on typing or removing URLs such as "such as https://goog"
+    return query.slice(0, query.length / 2);
+  }
+  if (url.pathname.endsWith('/')) {
+    // remove parameters and move to upper path
+    return new URL('..', url).href;
+  }
+  // remove parameters
+  return new URL('.', url).href;
+};
+
+export default class PrefetchAndCache<T> {
+  private shortKey: string | undefined;
+
+  private shortKeyCache: T[] = [];
+
+  constructor(
+    private getter: Getter<T>,
+    private filter: Filter<T>,
+    private prefetchThrethold: number = 1,
+  ) {
+  }
+
+  async get(query: string): Promise<T[]> {
+    query = query.trim();
+    if (query.length < this.prefetchThrethold) {
+      this.shortKey = undefined;
+      return this.getter(query);
+    }
+
+    if (this.needToRefresh(query)) {
+      this.shortKey = shortKey(query);
+      this.shortKeyCache = await this.getter(this.shortKey);
+    }
+    return this.filter(this.shortKeyCache, query);
+  }
+
+  private needToRefresh(query: string): boolean {
+    if (!this.shortKey) {
+      // no cache
+      return true
+    }
+
+    if (query.length < this.shortKey.length) {
+      // query: "hello"
+      // cache: "hello_world"
+      return true;
+    }
+
+    if (!query.startsWith(this.shortKey)) {
+        // queyr:   "hello_w"
+        // shorten: "hello_morning"
+        return true
+    }
+
+    if (query.slice(this.shortKey.length).includes(' ')) {
+      // queyr:   "hello x"
+      // shorten: "hello"
+      return true;
+    }
+
+    return false
+  }
+}
diff --git a/src/background/completion/impl/filters.ts b/src/background/completion/impl/filters.ts
index 98957a7..3aa56e4 100644
--- a/src/background/completion/impl/filters.ts
+++ b/src/background/completion/impl/filters.ts
@@ -33,7 +33,7 @@ const filterByTailingSlash = (items: Item[]): Item[] => {
   });
 };
 
-const filterByPathname = (items: Item[], min: number): Item[] => {
+const filterByPathname = (items: Item[]): Item[] => {
   const hash: {[key: string]: Item} = {};
   for (const item of items) {
     const url = new URL(item.url as string);
@@ -45,14 +45,10 @@ const filterByPathname = (items: Item[], min: number): Item[] => {
       hash[pathname] = item;
     }
   }
-  const filtered = Object.values(hash);
-  if (filtered.length < min) {
-    return items;
-  }
-  return filtered;
+  return Object.values(hash);
 };
 
-const filterByOrigin = (items: Item[], min: number): Item[] => {
+const filterByOrigin = (items: Item[]): Item[] => {
   const hash: {[key: string]: Item} = {};
   for (const item of items) {
     const origin = new URL(item.url as string).origin;
@@ -63,11 +59,7 @@ const filterByOrigin = (items: Item[], min: number): Item[] => {
       hash[origin] = item;
     }
   }
-  const filtered = Object.values(hash);
-  if (filtered.length < min) {
-    return items;
-  }
-  return filtered;
+  return Object.values(hash);
 };
 
 export {