12 files changed, 486 insertions, 0 deletions
diff --git a/src/background/completion/BookmarkRepository.ts b/src/background/completion/BookmarkRepository.ts
new file mode 100644
index 0000000..14105c8
--- /dev/null
+++ b/src/background/completion/BookmarkRepository.ts
@@ -0,0 +1,8 @@
+export type BookmarkItem = {
+  title: string
+  url: string
+}
+
+export default interface BookmarkRepository {
+  queryBookmarks(query: string): Promise<BookmarkItem[]>;
+}
diff --git a/src/background/completion/HistoryRepository.ts b/src/background/completion/HistoryRepository.ts
new file mode 100644
index 0000000..5eb3a2b
--- /dev/null
+++ b/src/background/completion/HistoryRepository.ts
@@ -0,0 +1,8 @@
+export type HistoryItem = {
+  title: string
+  url: string
+}
+
+export default interface HistoryRepository {
+  queryHistories(keywords: string): Promise<HistoryItem[]>;
+}
diff --git a/src/background/completion/OpenCompletionUseCase.ts b/src/background/completion/OpenCompletionUseCase.ts
new file mode 100644
index 0000000..1b63e7c
--- /dev/null
+++ b/src/background/completion/OpenCompletionUseCase.ts
@@ -0,0 +1,59 @@
+import { inject, injectable } from "tsyringe";
+import CachedSettingRepository from "../repositories/CachedSettingRepository";
+import CompletionType from "../../shared/CompletionType";
+import BookmarkRepository from "./BookmarkRepository";
+import HistoryRepository from "./HistoryRepository";
+
+export type BookmarkItem = {
+  title: string
+  url: string
+}
+
+export type HistoryItem = {
+  title: string
+  url: string
+}
+
+@injectable()
+export default class OpenCompletionUseCase {
+  constructor(
+    @inject('BookmarkRepository') private bookmarkRepository: BookmarkRepository,
+    @inject('HistoryRepository') private historyRepository: HistoryRepository,
+    @inject("CachedSettingRepository") private cachedSettingRepository: CachedSettingRepository,
+  ) {
+  }
+
+  async getCompletionTypes(): Promise<CompletionType[]> {
+    const settings = await this.cachedSettingRepository.get();
+    const types: CompletionType[] = [];
+    for (const c of settings.properties.complete) {
+      switch (c) {
+      case 's':
+        types.push(CompletionType.SearchEngines);
+        break;
+      case 'h':
+        types.push(CompletionType.History);
+        break;
+      case 'b':
+        types.push(CompletionType.Bookmarks);
+        break;
+      }
+      // ignore invalid characters in the complete property
+    }
+    return types;
+  }
+
+  async requestSearchEngines(query: string): Promise<string[]> {
+    const settings = await this.cachedSettingRepository.get();
+    return Object.keys(settings.search.engines)
+      .filter(key => key.startsWith(query))
+  }
+
+  requestBookmarks(query: string): Promise<BookmarkItem[]> {
+    return this.bookmarkRepository.queryBookmarks(query);
+  }
+
+  requestHistory(query: string): Promise<HistoryItem[]> {
+    return this.historyRepository.queryHistories(query);
+  }
+}
+\ No newline at end of file
diff --git a/src/background/completion/PropertyCompletionUseCase.ts b/src/background/completion/PropertyCompletionUseCase.ts
new file mode 100644
index 0000000..049cfb8
--- /dev/null
+++ b/src/background/completion/PropertyCompletionUseCase.ts
@@ -0,0 +1,16 @@
+import { injectable } from "tsyringe";
+import Properties from "../../shared/settings/Properties";
+
+type Property = {
+  name: string;
+  type: 'string' | 'boolean' | 'number';
+}
+@injectable()
+export default class PropertyCompletionUseCase {
+  async getProperties(): Promise<Property[]> {
+    return Properties.defs().map(def => ({
+      name: def.name,
+      type: def.type,
+    }));
+  }
+}
+\ No newline at end of file
diff --git a/src/background/completion/TabCompletionUseCase.ts b/src/background/completion/TabCompletionUseCase.ts
new file mode 100644
index 0000000..dec86e9
--- /dev/null
+++ b/src/background/completion/TabCompletionUseCase.ts
@@ -0,0 +1,55 @@
+import { inject, injectable } from "tsyringe";
+import TabItem from "./TabItem";
+import TabRepository, { Tab } from "./TabRepository";
+import TabPresenter from "../presenters/TabPresenter";
+import TabFlag from "../../shared/TabFlag";
+
+@injectable()
+export default class TabCompletionUseCase {
+  constructor(
+      @inject('TabRepository') private tabRepository: TabRepository,
+      @inject('TabPresenter') private tabPresenter: TabPresenter,
+  ) {
+  }
+
+  async queryTabs(query: string, excludePinned: boolean): Promise<TabItem[]> {
+    const lastTabId = await this.tabPresenter.getLastSelectedId();
+    const allTabs = await this.tabRepository.getAllTabs(excludePinned);
+    const num = parseInt(query, 10);
+    let tabs: Tab[] = [];
+    if (!isNaN(num)) {
+      const tab = allTabs.find(t => t.index === num - 1);
+      if (tab) {
+        tabs = [tab];
+      }
+    } else if (query == '%') {
+      const tab = allTabs.find(t => t.active);
+      if (tab) {
+        tabs = [tab];
+      }
+    } else if (query == '#') {
+      const tab = allTabs.find(t => t.id === lastTabId);
+      if (tab) {
+        tabs = [tab];
+      }
+    } else {
+      tabs = await this.tabRepository.queryTabs(query, excludePinned);
+    }
+
+    return tabs.map(tab => {
+      let flag = TabFlag.None;
+      if (tab.active) {
+        flag = TabFlag.CurrentTab
+      } else if (tab.id == lastTabId) {
+        flag = TabFlag.LastTab
+      }
+      return {
+        index: tab.index + 1,
+        flag: flag,
+        title: tab.title,
+        url: tab.url,
+        faviconUrl : tab.faviconUrl
+      }
+    });
+  }
+}
diff --git a/src/background/completion/TabItem.ts b/src/background/completion/TabItem.ts
new file mode 100644
index 0000000..630855a
--- /dev/null
+++ b/src/background/completion/TabItem.ts
@@ -0,0 +1,11 @@
+import TabFlag from "../../shared/TabFlag";
+
+type TabItem = {
+    index: number
+    flag: TabFlag
+    title: string
+    url: string
+    faviconUrl?: string
+}
+
+export default TabItem;
+\ No newline at end of file
diff --git a/src/background/completion/TabRepository.ts b/src/background/completion/TabRepository.ts
new file mode 100644
index 0000000..fe1b601
--- /dev/null
+++ b/src/background/completion/TabRepository.ts
@@ -0,0 +1,14 @@
+export type Tab = {
+  id: number
+  index: number
+  active: boolean
+  title: string
+  url: string
+  faviconUrl?: string
+}
+
+export default interface TabRepository {
+  queryTabs(query: string, excludePinned: boolean): Promise<Tab[]>;
+
+  getAllTabs(excludePinned: boolean): Promise<Tab[]>
+}
diff --git a/src/background/completion/impl/BookmarkRepositoryImpl.ts b/src/background/completion/impl/BookmarkRepositoryImpl.ts
new file mode 100644
index 0000000..3b80b93
--- /dev/null
+++ b/src/background/completion/impl/BookmarkRepositoryImpl.ts
@@ -0,0 +1,46 @@
+import BookmarkRepository, {BookmarkItem} from "../BookmarkRepository";
+import {HistoryItem} from "../HistoryRepository";
+import PrefetchAndCache from "./PrefetchAndCache";
+
+const COMPLETION_ITEM_LIMIT = 10;
+
+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)
+      .filter(item => item.type === 'bookmark' && item.url)
+      .filter((item) => {
+        let url = undefined;
+        try {
+          url = new URL(item.url!!);
+        } catch (e) {
+          return false;
+        }
+        return url.protocol !== 'place:';
+      })
+      .slice(0, COMPLETION_ITEM_LIMIT)
+      .map(item => ({
+        title: item.title!!,
+        url: item.url!!,
+      }));
+  }
+
+  private filter(items: 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/HistoryRepositoryImpl.ts b/src/background/completion/impl/HistoryRepositoryImpl.ts
new file mode 100644
index 0000000..cd55cd0
--- /dev/null
+++ b/src/background/completion/impl/HistoryRepositoryImpl.ts
@@ -0,0 +1,55 @@
+import * as filters from "./filters";
+import HistoryRepository, {HistoryItem} from "../HistoryRepository";
+import PrefetchAndCache from "./PrefetchAndCache";
+
+const COMPLETION_ITEM_LIMIT = 10;
+
+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,
+    });
+
+    return [items]
+      .map(filters.filterBlankTitle)
+      .map(filters.filterHttp)
+      .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/TabRepositoryImpl.ts b/src/background/completion/impl/TabRepositoryImpl.ts
new file mode 100644
index 0000000..adcaba7
--- /dev/null
+++ b/src/background/completion/impl/TabRepositoryImpl.ts
@@ -0,0 +1,41 @@
+import TabRepository, { Tab } from "../TabRepository";
+
+const COMPLETION_ITEM_LIMIT = 10;
+
+export default class TabRepositoryImpl implements TabRepository {
+  async queryTabs(query: string, excludePinned: boolean): Promise<Tab[]> {
+    const tabs = await browser.tabs.query({ currentWindow: true });
+    return tabs
+      .filter((t) => {
+        return t.url && t.url.toLowerCase().includes(query.toLowerCase()) ||
+          t.title && t.title.toLowerCase().includes(query.toLowerCase());
+      })
+      .filter((t) => {
+        return !(excludePinned && t.pinned);
+      })
+      .filter(item => item.id && item.title && item.url)
+      .slice(0, COMPLETION_ITEM_LIMIT)
+      .map(TabRepositoryImpl.toEntity);
+  }
+
+  async getAllTabs(excludePinned: boolean): Promise<Tab[]> {
+      if (excludePinned) {
+          return (await browser.tabs.query({ currentWindow: true, pinned: true }))
+              .map(TabRepositoryImpl.toEntity)
+
+      }
+      return (await browser.tabs.query({ currentWindow: true }))
+          .map(TabRepositoryImpl.toEntity)
+  }
+
+  private static toEntity(tab: browser.tabs.Tab,): Tab {
+    return {
+      id: tab.id!!,
+      url: tab.url!!,
+      active: tab.active,
+      title: tab.title!!,
+      faviconUrl: tab.favIconUrl,
+      index: tab.index,
+    }
+  }
+}
diff --git a/src/background/completion/impl/filters.ts b/src/background/completion/impl/filters.ts
new file mode 100644
index 0000000..3aa56e4
--- /dev/null
+++ b/src/background/completion/impl/filters.ts
@@ -0,0 +1,68 @@
+type Item = browser.history.HistoryItem;
+
+const filterHttp = (items: Item[]): Item[] => {
+  const httpsHosts = items.map(x => new URL(x.url as string))
+    .filter(x => x.protocol === 'https:')
+    .map(x => x.host);
+  const hostsSet = new Set(httpsHosts);
+
+  return items.filter((item: Item) => {
+    const url = new URL(item.url as string);
+    return url.protocol === 'https:' || !hostsSet.has(url.host);
+  });
+};
+
+const filterBlankTitle = (items: Item[]): Item[] => {
+  return items.filter(item => item.title && item.title !== '');
+};
+
+const filterByTailingSlash = (items: Item[]): Item[] => {
+  const urls = items.map(item => new URL(item.url as string));
+  const simplePaths = urls
+    .filter(url => url.hash === '' && url.search === '')
+    .map(url => url.origin + url.pathname);
+  const pathsSet = new Set(simplePaths);
+
+  return items.filter((item) => {
+    const url = new URL(item.url as string);
+    if (url.hash !== '' || url.search !== '' ||
+      url.pathname.slice(-1) !== '/') {
+      return true;
+    }
+    return !pathsSet.has(url.origin + url.pathname.slice(0, -1));
+  });
+};
+
+const filterByPathname = (items: Item[]): Item[] => {
+  const hash: {[key: string]: Item} = {};
+  for (const item of items) {
+    const url = new URL(item.url as string);
+    const pathname = url.origin + url.pathname;
+    if (!hash[pathname]) {
+      hash[pathname] = item;
+    } else if ((hash[pathname].url as string).length >
+      (item.url as string).length) {
+      hash[pathname] = item;
+    }
+  }
+  return Object.values(hash);
+};
+
+const filterByOrigin = (items: Item[]): Item[] => {
+  const hash: {[key: string]: Item} = {};
+  for (const item of items) {
+    const origin = new URL(item.url as string).origin;
+    if (!hash[origin]) {
+      hash[origin] = item;
+    } else if ((hash[origin].url as string).length >
+      (item.url as string).length) {
+      hash[origin] = item;
+    }
+  }
+  return Object.values(hash);
+};
+
+export {
+  filterHttp, filterBlankTitle, filterByTailingSlash,
+  filterByPathname, filterByOrigin
+};