From 34a569d73638dd10162050047d23cd04d286f4bc Mon Sep 17 00:00:00 2001 From: Shin'ya Ueoka Date: Tue, 31 Mar 2020 21:40:03 +0900 Subject: Prefetch completion items and store them to cache --- .../completion/impl/BookmarkRepositoryImpl.ts | 26 ++++- .../completion/impl/HistoryRepositoryImpl.ts | 51 +++++++--- src/background/completion/impl/PrefetchAndCache.ts | 105 +++++++++++++++++++++ src/background/completion/impl/filters.ts | 16 +--- .../completion/impl/PrefetchAndCache.test.ts | 74 +++++++++++++++ test/background/completion/impl/filters.test.ts | 30 +----- 6 files changed, 246 insertions(+), 56 deletions(-) create mode 100644 src/background/completion/impl/PrefetchAndCache.ts create mode 100644 test/background/completion/impl/PrefetchAndCache.test.ts 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 { +export default class CachedBookmarkRepository implements BookmarkRepository { + private bookmarkCache: PrefetchAndCache; + + constructor() { + this.bookmarkCache = new PrefetchAndCache(this.getter, this.filter, 10,); + } + + queryBookmarks(query: string): Promise { + return this.bookmarkCache.get(query); + } + + private async getter(query: string): Promise { 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; + + constructor() { + this.historyCache = new PrefetchAndCache(this.getter, this.filter, 10) + } + async queryHistories(keywords: string): Promise { + const items = await this.historyCache.get(keywords); + + const filterOrKeep = (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 { 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 = (query: string) => Promise; +type Filter = (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 { + private shortKey: string | undefined; + + private shortKeyCache: T[] = []; + + constructor( + private getter: Getter, + private filter: Filter, + private prefetchThrethold: number = 1, + ) { + } + + async get(query: string): Promise { + 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 { diff --git a/test/background/completion/impl/PrefetchAndCache.test.ts b/test/background/completion/impl/PrefetchAndCache.test.ts new file mode 100644 index 0000000..23e3879 --- /dev/null +++ b/test/background/completion/impl/PrefetchAndCache.test.ts @@ -0,0 +1,74 @@ +import PrefetchAndCache, {shortKey} from "../../../../src/background/completion/impl/PrefetchAndCache"; +import { expect } from 'chai'; + +class MockRepository { + public history: string[] = []; + + constructor( + private items: string[], + ) { + } + + get(query: string): Promise { + this.history.push(query); + if (query.length === 0) { + return Promise.resolve(this.items); + } else { + return Promise.resolve(this.items.filter(item => item.includes(query))); + } + } +} +const filter = (items: string[], query: string) => query.length === 0 ? items : items.filter(item => item.includes(query)); + +describe('shortKey', () => { + it('returns query excluding the last word', () => { + const query = "hello\t world good bye"; + const shorten = shortKey(query); + expect(shorten).to.equal("hello world good") + }); + + it('returns half-length of the query', () => { + const query = "the-query-with-super-long-word"; + const shorten = shortKey(query); + expect(shorten).to.equal("the-query-with-") + }); + + it('returns shorten URL', () => { + let query = "https://example.com/path/to/resource?q=hello"; + let shorten = shortKey(query); + expect(shorten).to.equal("https://example.com/path/to/"); + + query = "https://example.com/path/to/resource/#id1"; + shorten = shortKey(query); + expect(shorten).to.equal("https://example.com/path/to/"); + + query = "https://www.google.c"; + shorten = shortKey(query); + expect(shorten).to.equal("https://ww"); + }) +}); + +describe('PrefetchAndCache', () => { + describe('get', () => { + it('returns cached request', async() => { + const repo = new MockRepository(["apple", "apple pie", "apple juice", "banana", "banana pudding", "cherry"]); + const sut = new PrefetchAndCache(repo.get.bind(repo), filter); + + expect(await sut.get("apple pie")).deep.equal(["apple pie"]); + expect(await sut.get("apple ")).deep.equal(["apple", "apple pie", "apple juice"]); + expect(await sut.get("apple")).deep.equal(["apple", "apple pie", "apple juice"]); + expect(await sut.get("appl")).deep.equal(["apple", "apple pie", "apple juice"]); + expect(repo.history).to.deep.equal(["apple", 'ap']); + + expect(await sut.get("banana")).deep.equal(["banana", "banana pudding"]); + expect(repo.history).to.deep.equal(["apple", "ap", "ban"]); + expect(await sut.get("banana p")).deep.equal(["banana pudding"]); + expect(repo.history).to.deep.equal(["apple", "ap", "ban", "banana"]); + expect(await sut.get("ba")).deep.equal(["banana", "banana pudding"]); + expect(repo.history).to.deep.equal(["apple", "ap", "ban", "banana", "b"]); + + expect(await sut.get("")).to.have.lengthOf(6); + expect(repo.history).to.deep.equal(["apple", "ap", "ban", "banana", "b", ""]); + }); + }); +}); \ No newline at end of file diff --git a/test/background/completion/impl/filters.test.ts b/test/background/completion/impl/filters.test.ts index 2b15a9b..a181f60 100644 --- a/test/background/completion/impl/filters.test.ts +++ b/test/background/completion/impl/filters.test.ts @@ -52,19 +52,6 @@ describe('background/usecases/filters', () => { }) describe('filterByPathname', () => { - it('remains items less than minimam length', () => { - const pages = [ - { id: '0', url: 'http://i-beam.org/search?q=apple' }, - { id: '1', url: 'http://i-beam.org/search?q=apple_banana' }, - { id: '2', url: 'http://i-beam.org/search?q=apple_banana_cherry' }, - { id: '3', url: 'http://i-beam.org/request?q=apple' }, - { id: '4', url: 'http://i-beam.org/request?q=apple_banana' }, - { id: '5', url: 'http://i-beam.org/request?q=apple_banana_cherry' }, - ]; - const filtered = filters.filterByPathname(pages, 10); - expect(filtered).to.have.lengthOf(6); - }); - it('filters by length of pathname', () => { const pages = [ { id: '0', url: 'http://i-beam.org/search?q=apple' }, @@ -74,7 +61,7 @@ describe('background/usecases/filters', () => { { id: '4', url: 'http://i-beam.net/search?q=apple_banana' }, { id: '5', url: 'http://i-beam.net/search?q=apple_banana_cherry' }, ]; - const filtered = filters.filterByPathname(pages, 0); + const filtered = filters.filterByPathname(pages); expect(filtered).to.deep.equal([ { id: '0', url: 'http://i-beam.org/search?q=apple' }, { id: '3', url: 'http://i-beam.net/search?q=apple' }, @@ -83,19 +70,6 @@ describe('background/usecases/filters', () => { }); describe('filterByOrigin', () => { - it('remains items less than minimam length', () => { - const pages = [ - { id: '0', url: 'http://i-beam.org/search?q=apple' }, - { id: '1', url: 'http://i-beam.org/search?q=apple_banana' }, - { id: '2', url: 'http://i-beam.org/search?q=apple_banana_cherry' }, - { id: '3', url: 'http://i-beam.org/request?q=apple' }, - { id: '4', url: 'http://i-beam.org/request?q=apple_banana' }, - { id: '5', url: 'http://i-beam.org/request?q=apple_banana_cherry' }, - ]; - const filtered = filters.filterByOrigin(pages, 10); - expect(filtered).to.have.lengthOf(6); - }); - it('filters by length of pathname', () => { const pages = [ { id: '0', url: 'http://i-beam.org/search?q=apple' }, @@ -105,7 +79,7 @@ describe('background/usecases/filters', () => { { id: '4', url: 'http://i-beam.org/request?q=apple_banana' }, { id: '5', url: 'http://i-beam.org/request?q=apple_banana_cherry' }, ]; - const filtered = filters.filterByOrigin(pages, 0); + const filtered = filters.filterByOrigin(pages); expect(filtered).to.deep.equal([ { id: '0', url: 'http://i-beam.org/search?q=apple' }, ]); -- cgit v1.2.3