chrome/browser/resources/tab_search/search.ts

// Copyright 2020 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

import {quoteString} from 'chrome://resources/js/util.js';

import type {ItemData, TabData, TabGroupData} from './tab_data.js';

export interface OptionKeyObject {
  name: string;
  getter: (data: TabData|TabGroupData) => string | undefined;
  weight: number;
}

export interface SearchOptions {
  includeScore?: boolean;
  includeMatches?: boolean;
  ignoreLocation?: boolean;
  threshold?: number;
  distance?: number;
  keys: OptionKeyObject[];
}

/**
 * @return A new array of entries satisfying the input. If no search input is
 *     present, returns a shallow copy of the records.
 */
export function search<T extends ItemData>(
    input: string, records: T[], options: SearchOptions): T[] {
  if (input.length === 0) {
    return [...records];
  }
  const searchStartTime = Date.now();
  const result = exactSearch(input, records, options);
  chrome.metricsPrivate.recordTime(
      'Tabs.TabSearch.WebUI.SearchAlgorithmDuration',
      Math.round(Date.now() - searchStartTime));
  return result;
}

function cloneTabDataObj<T extends ItemData>(tabData: T): T {
  const clone = Object.assign({}, tabData);
  clone.highlightRanges = {};
  Object.setPrototypeOf(clone, Object.getPrototypeOf(tabData));

  return clone;
}

////////////////////////////////////////////////////////////////////////////////
// Exact Match Implementation :

/**
 * The exact match algorithm returns records ranked according to priorities
 * and scores. Records are ordered by priority (higher priority comes
 * first) and sorted by score within the same priority. See `scoringFunction`
 * for how to calculate score and `prioritizeMatchResult` for how to calculate
 * priority.
 */
function exactSearch<T extends ItemData>(
    searchText: string, records: T[], options: SearchOptions): T[] {
  if (searchText.length === 0) {
    return records;
  }

  // Default distance to calculate score for search fields based on match
  // position.
  const defaultDistance = 200;
  const distance = options.distance || defaultDistance;

  // Controls how heavily weighted the search field weights are relative to each
  // other in the scoring function.
  const searchFieldWeights = (options.keys).reduce((acc, {name, weight}) => {
    acc[name] = weight;
    return acc;
  }, {} as {[key: string]: number});

  // Perform an exact match search with range discovery.
  const exactMatches = [];
  for (const tabDataRecord of records) {
    let matchFound = false;
    const matchedRecord = cloneTabDataObj(tabDataRecord);
    // Searches for fields or nested fields in the record.
    for (const key of options.keys) {
      const text = key.getter(tabDataRecord as TabData | TabGroupData);
      if (text) {
        const ranges = getRanges(text, searchText);
        if (ranges.length !== 0) {
          matchedRecord.highlightRanges[key.name] = ranges;
          matchFound = true;
        }
      }
    }

    if (matchFound) {
      exactMatches.push({
        tab: matchedRecord,
        score: scoringFunction(matchedRecord, distance, searchFieldWeights),
      });
    }
  }

  // Sort by score.
  exactMatches.sort((a, b) => (b.score - a.score));

  // Reorder match result by priorities.
  return prioritizeMatchResult(
      searchText, options.keys, exactMatches.map(item => item.tab));
}

/**
 * Determines whether the given tab has a search field with identified matches
 * at the beginning of the string.
 */
function hasMatchStringStart(
    tab: ItemData, searchText: string, keys: OptionKeyObject[]): boolean {
  return keys.some(key => {
    const value = key.getter(tab as TabData | TabGroupData);
    return value !== undefined && value.startsWith(searchText);
  });
}

/**
 * Determines whether the given tab has a match for the given regexp in its
 * search fields.
 */
function hasRegexMatch(
    tab: ItemData, regexp: RegExp, keys: OptionKeyObject[]): boolean {
  return keys.some((key) => {
    const value = key.getter(tab as TabData | TabGroupData);
    return value !== undefined && value.search(regexp) !== -1;
  });
}

// https://crbug.com/433531973: Replace single and double left and right
// quotation characters with the regular ones.
function replaceSpecialQuotationCharacters(text: string) {
  return text.replace(/[‘’]/g, '\'').replace(/[“”]/g, '"');
}

/**
 * Returns an array of matches that indicate where in the target string the
 * searchText appears. If there are no identified matches an empty array is
 * returned.
 */
function getRanges(target: string, searchText: string):
    Array<{start: number, length: number}> {
  target = replaceSpecialQuotationCharacters(target);
  searchText = replaceSpecialQuotationCharacters(searchText);
  const escapedText = quoteString(searchText);
  const ranges = [];
  let match = null;
  for (const re = new RegExp(escapedText, 'gi'); match = re.exec(target);) {
    ranges.push({
      start: match.index,
      length: searchText.length,
    });
  }
  return ranges;
}

/**
 * A scoring function based on match indices of specified search fields.
 * Matches near the beginning of the string will have a higher score than
 * matches near the end of the string. Multiple matches will have a higher score
 * than single matches.
 */
function scoringFunction(
    tabData: ItemData, distance: number,
    searchFieldWeights: {[key: string]: number}) {
  let score = 0;
  // For every match, map the match index in [0, distance] to a scalar value in
  // [1, 0].
  for (const key in searchFieldWeights) {
    if (tabData.highlightRanges[key]) {
      for (const {start} of tabData.highlightRanges[key]) {
        score += Math.max((distance - start) / distance, 0) *
            searchFieldWeights[key]!;
      }
    }
  }

  return score;
}

/**
 * Reorder match result based on priorities (highest to lowest priority):
 * 1. All items with a search key matching the searchText at the beginning of
 *    the string.
 * 2. All items with a search key matching the searchText at the beginning of a
 *    word in the string.
 * 3. All remaining items with a search key matching the searchText elsewhere in
 *    the string.
 */
function prioritizeMatchResult<T extends ItemData>(
    searchText: string, keys: OptionKeyObject[], result: T[]): T[] {
  const itemsMatchingStringStart = [];
  const itemsMatchingWordStart = [];
  const others = [];
  const wordStartRegexp = new RegExp(`\\b${quoteString(searchText)}`, 'i');
  for (const tab of result) {
    // Find matches that occur at the beginning of the string.
    if (hasMatchStringStart(tab, searchText, keys)) {
      itemsMatchingStringStart.push(tab);
    } else if (hasRegexMatch(tab, wordStartRegexp, keys)) {
      itemsMatchingWordStart.push(tab);
    } else {
      others.push(tab);
    }
  }
  return itemsMatchingStringStart.concat(itemsMatchingWordStart, others);
}