Change matcher to accept a TemplateResult as well to avoid using unsafeHtml

src/common/string/casing.ts

@@ -0,0 +1,5 @@
+export const toTitleCase = (str: string) => {
+  return str.replace(/\w\S*/g, (txt) => {
+    return txt.charAt(0).toUpperCase() + txt.substr(1).toLowerCase();
+  });
+};

src/common/string/filter/filter.ts

@@ -510,13 +510,10 @@ export interface FuzzyScorer {
   ): FuzzyScore | undefined;
 }
 
-export function createMatches(score: undefined | FuzzyScore): Match[] {
+function _createMatches(score: FuzzyScore, wordPos: number) {
-  if (typeof score === "undefined") {
-    return [];
-  }
   const res: Match[] = [];
-  const wordPos = score[1];
+
-  for (let i = score.length - 1; i > 1; i--) {
+  for (let i = score.length - 1; i >= 0; i--) {
     const pos = score[i] + wordPos;
     const last = res[res.length - 1];
     if (last && last.end === pos) {
@@ -525,9 +522,66 @@ export function createMatches(score: undefined | FuzzyScore): Match[] {
       res.push({ start: pos, end: pos + 1 });
     }
   }
+
   return res;
 }
 
+export function createMatches(score: undefined | FuzzyScore): Match[] {
+  if (typeof score === "undefined") {
+    return [];
+  }
+
+  const wordPos = score[1];
+  const _score = score.splice(2);
+
+  return _createMatches(_score, wordPos);
+}
+
+const findFirstOutOfRangeElement = (number, score: FuzzyScore) =>
+  score.findIndex((num) => num < number);
+
+export function createMatchesFragmented(
+  score: undefined | FuzzyScore,
+  strings: string[]
+): Match[][] {
+  if (typeof score === "undefined") {
+    return [];
+  }
+
+  const matches: Match[][] = [];
+  const wordPos = score[1];
+  let lengthCounter = 0;
+
+  // The first and second elements in score represent total score, and the offset at which
+  // matching started. For this method, we only care about the rest of the score array
+  // which represents matched position indexes.
+  const _score = score.splice(2);
+
+  const fragmentedScores: FuzzyScore[] = [];
+
+  for (const string of strings) {
+    const prevLengthCounter = lengthCounter;
+    lengthCounter += string.length;
+    const lastIndex = findFirstOutOfRangeElement(lengthCounter, _score);
+
+    if (lastIndex < 0) {
+      fragmentedScores.push([]);
+      continue;
+    }
+
+    fragmentedScores.push(
+      _score.splice(lastIndex).map((pos) => pos - prevLengthCounter)
+    );
+  }
+
+  for (const fragmentedScore of fragmentedScores) {
+    const res = _createMatches(fragmentedScore, wordPos);
+    matches.push(res);
+  }
+
+  return matches;
+}
+
 /**
  * A fast function (therefore imprecise) to check if code points are emojis.
  * Generated using https://github.com/alexdima/unicode-utils/blob/master/generate-emoji-test.js

src/common/string/filter/sequence-matching.ts

@@ -1,4 +1,10 @@
-import { fuzzyScore } from "./filter";
+import { TemplateResult } from "lit-html";
+import {
+  createMatches,
+  createMatchesFragmented,
+  FuzzyScore,
+  fuzzyScore,
+} from "./filter";
 
 /**
  * Determine whether a sequence of letters exists in another string,
@@ -10,13 +16,24 @@ import { fuzzyScore } from "./filter";
  * @return {number} Score representing how well the word matches the filter. Return of 0 means no match.
  */
 
-export const fuzzySequentialMatch = (
+type FuzzySequentialMatcher = (
   filter: string,
-  item: ScorableTextItem
+  item: ScorableTextItem,
+  decorate?: MatchDecorator
+) => ScorableTextItem | undefined;
+
+export const fuzzySequentialMatch: FuzzySequentialMatcher = (
+  filter,
+  item,
+  decorate = createMatchDecorator((letter) => `[${letter}]`)
 ) => {
   let topScore = Number.NEGATIVE_INFINITY;
+  const decoratedStrings: Decoration[][][] = [];
+  const strings = item.treatArrayAsSingleString
+    ? [item.strings.join("")]
+    : item.strings;
 
-  for (const word of item.strings) {
+  for (const word of strings) {
     const scores = fuzzyScore(
       filter,
       filter.toLowerCase(),
@@ -27,6 +44,10 @@ export const fuzzySequentialMatch = (
       true
     );
 
+    if (decorate) {
+      decoratedStrings.push(decorate(word, item, scores));
+    }
+
     if (!scores) {
       continue;
     }
@@ -45,7 +66,11 @@ export const fuzzySequentialMatch = (
     return undefined;
   }
 
-  return topScore;
+  return {
+    score: topScore,
+    strings: item.strings,
+    decoratedStrings,
+  };
 };
 
 /**
@@ -64,17 +89,28 @@ export const fuzzySequentialMatch = (
 export interface ScorableTextItem {
   score?: number;
   strings: string[];
+  decoratedStrings?: Decoration[][][];
+  treatArrayAsSingleString?: boolean;
 }
 
 type FuzzyFilterSort = <T extends ScorableTextItem>(
   filter: string,
-  items: T[]
+  items: T[],
+  decorate?: MatchDecorator
 ) => T[];
 
-export const fuzzyFilterSort: FuzzyFilterSort = (filter, items) => {
+export const fuzzyFilterSort: FuzzyFilterSort = (
+  filter,
+  items,
+  decorate = createMatchDecorator((letter) => `[${letter}]`)
+) => {
   return items
     .map((item) => {
-      item.score = fuzzySequentialMatch(filter, item);
+      const match = fuzzySequentialMatch(filter, item, decorate);
+
+      item.score = match?.score;
+      item.decoratedStrings = match?.decoratedStrings;
+
       return item;
     })
     .filter((item) => item.score !== undefined)
@@ -82,3 +118,58 @@ export const fuzzyFilterSort: FuzzyFilterSort = (filter, items) => {
       scoreA > scoreB ? -1 : scoreA < scoreB ? 1 : 0
     );
 };
+
+type Decoration = string | TemplateResult;
+
+export type Surrounder = (matchedChunk: Decoration) => Decoration;
+
+type MatchDecorator = (
+  word: string,
+  item: ScorableTextItem,
+  scores?: FuzzyScore
+) => Decoration[][];
+
+export const createMatchDecorator: (
+  surrounder: Surrounder
+) => MatchDecorator = (surrounder) => (word, item, scores) =>
+  _decorateMatch(word, surrounder, item, scores);
+
+const _decorateMatch: (
+  word: string,
+  surrounder: Surrounder,
+  item: ScorableTextItem,
+  scores?: FuzzyScore
+) => Decoration[][] = (word, surrounder, item, scores) => {
+  if (!scores) {
+    return [[word]];
+  }
+
+  const decoratedText: Decoration[][] = [];
+  const matches = item.treatArrayAsSingleString
+    ? createMatchesFragmented(scores, item.strings)
+    : [createMatches(scores)];
+
+  for (let i = 0; i < matches.length; i++) {
+    const match = matches[i];
+    const _word = item.treatArrayAsSingleString ? item.strings[i] : word;
+    let pos = 0;
+    const actualWord: Decoration[] = [];
+
+    for (const fragmentedMatch of match) {
+      const unmatchedChunk = _word.substring(pos, fragmentedMatch.start);
+      const matchedChunk = _word.substring(
+        fragmentedMatch.start,
+        fragmentedMatch.end
+      );
+
+      actualWord.push(unmatchedChunk);
+      actualWord.push(surrounder(matchedChunk));
+
+      pos = fragmentedMatch.end;
+    }
+
+    actualWord.push(_word.substring(pos));
+    decoratedText.push(actualWord);
+  }
+  return decoratedText;
+};

src/dialogs/quick-bar/ha-quick-bar.ts

@@ -34,6 +34,7 @@ import { navigate } from "../../common/navigate";
 import "../../common/search/search-input";
 import { compare } from "../../common/string/compare";
 import {
+  createMatchDecorator,
   fuzzyFilterSort,
   ScorableTextItem,
 } from "../../common/string/filter/sequence-matching";
@@ -53,6 +54,7 @@ import {
 } from "../generic/show-dialog-box";
 import { QuickBarParams } from "./show-dialog-quick-bar";
 import "../../components/ha-chip";
+import { toTitleCase } from "../../common/string/casing";
 
 interface QuickBarItem extends ScorableTextItem {
   primaryText: string;
@@ -118,6 +120,7 @@ export class QuickBar extends LitElement {
     this._focusSet = false;
     this._filter = "";
     this._search = "";
+    this._resetDecorations();
     fireEvent(this, "dialog-closed", { dialog: this.localName });
   }
 
@@ -253,11 +256,19 @@ export class QuickBar extends LitElement {
               class="entity"
               slot="graphic"
             ></ha-icon>`}
-        <span>${item.primaryText}</span>
+        <span class="item-text primary"
+          >${item.decoratedStrings
+            ? item.decoratedStrings[0]
+            : item.primaryText}</span
+        >
         ${item.altText
           ? html`
-              <span slot="secondary" class="item-text secondary"
+              <span slot="secondary" class="item-text secondary">
-                >${item.altText}</span
+                <span
+                  >${item.decoratedStrings
+                    ? item.decoratedStrings[1]
+                    : item.altText}</span
+                ></span
               >
             `
           : null}
@@ -266,6 +277,8 @@ export class QuickBar extends LitElement {
   }
 
   private _renderCommandItem(item: CommandItem, index?: number) {
+    const decoratedItem = item.decoratedStrings && item.decoratedStrings[0];
+
     return html`
       <mwc-list-item
         .item=${item}
@@ -285,11 +298,13 @@ export class QuickBar extends LitElement {
                   slot="icon"
                 ></ha-svg-icon>`
               : ""}
-            ${item.categoryText}</ha-chip
+            ${decoratedItem ? decoratedItem[0] : item.categoryText}</ha-chip
           >
         </span>
 
-        <span class="command-text">${item.primaryText}</span>
+        <span class="command-text"
+          >${decoratedItem ? decoratedItem[1] : item.primaryText}</span
+        >
       </mwc-list-item>
     `;
   }
@@ -343,6 +358,10 @@ export class QuickBar extends LitElement {
     } else {
       this._commandMode = false;
       this._search = newFilter;
+      this._filter = this._search;
+      if (this._filter === "") {
+        this._clearSearch();
+      }
     }
 
     if (oldCommandMode !== this._commandMode) {
@@ -357,6 +376,18 @@ export class QuickBar extends LitElement {
   private _clearSearch() {
     this._search = "";
     this._filter = "";
+    this._resetDecorations();
+  }
+
+  private _resetDecorations() {
+    this._entityItems = this._entityItems?.map((item) => ({
+      ...item,
+      decoratedStrings: undefined,
+    }));
+    this._commandItems = this._commandItems?.map((item) => ({
+      ...item,
+      decoratedStrings: undefined,
+    }));
   }
 
   private _debouncedSetFilter = debounce((filter: string) => {
@@ -421,26 +452,28 @@ export class QuickBar extends LitElement {
 
     return reloadableDomains.map((domain) => {
       const commandItem = {
-        primaryText:
+        primaryText: toTitleCase(
           this.hass.localize(
             `ui.dialogs.quick-bar.commands.reload.${domain}`
           ) ||
-          this.hass.localize(
+            this.hass.localize(
-            "ui.dialogs.quick-bar.commands.reload.reload",
+              "ui.dialogs.quick-bar.commands.reload.reload",
-            "domain",
+              "domain",
-            domainToName(this.hass.localize, domain)
+              domainToName(this.hass.localize, domain)
-          ),
+            )
+        ),
         action: () => this.hass.callService(domain, "reload"),
         iconPath: mdiReload,
-        categoryText: this.hass.localize(
+        categoryText: toTitleCase(
-          `ui.dialogs.quick-bar.commands.types.reload`
+          this.hass.localize(`ui.dialogs.quick-bar.commands.types.reload`)
         ),
       };
 
       return {
         ...commandItem,
         categoryKey: "reload",
-        strings: [`${commandItem.categoryText} ${commandItem.primaryText}`],
+        strings: [`${commandItem.categoryText} `, commandItem.primaryText],
+        treatArrayAsSingleString: true,
       };
     });
   }
@@ -452,16 +485,20 @@ export class QuickBar extends LitElement {
       const categoryKey: CommandItem["categoryKey"] = "server_control";
 
       const item = {
-        primaryText: this.hass.localize(
+        primaryText: toTitleCase(
-          "ui.dialogs.quick-bar.commands.server_control.perform_action",
-          "action",
           this.hass.localize(
-            `ui.dialogs.quick-bar.commands.server_control.${action}`
+            "ui.dialogs.quick-bar.commands.server_control.perform_action",
+            "action",
+            this.hass.localize(
+              `ui.dialogs.quick-bar.commands.server_control.${action}`
+            )
           )
         ),
         iconPath: mdiServerNetwork,
-        categoryText: this.hass.localize(
+        categoryText: toTitleCase(
-          `ui.dialogs.quick-bar.commands.types.${categoryKey}`
+          this.hass.localize(
+            `ui.dialogs.quick-bar.commands.types.${categoryKey}`
+          )
         ),
         categoryKey,
         action: () => this.hass.callService("homeassistant", action),
@@ -470,7 +507,8 @@ export class QuickBar extends LitElement {
       return this._generateConfirmationCommand(
         {
           ...item,
-          strings: [`${item.categoryText} ${item.primaryText}`],
+          strings: [`${item.categoryText} `, item.primaryText],
+          treatArrayAsSingleString: true,
         },
         this.hass.localize("ui.dialogs.generic.ok")
       );
@@ -559,16 +597,20 @@ export class QuickBar extends LitElement {
 
       const navItem = {
         ...item,
+        primaryText: toTitleCase(item.primaryText),
         iconPath: mdiEarth,
-        categoryText: this.hass.localize(
+        categoryText: toTitleCase(
-          `ui.dialogs.quick-bar.commands.types.${categoryKey}`
+          this.hass.localize(
+            `ui.dialogs.quick-bar.commands.types.${categoryKey}`
+          )
         ),
         action: () => navigate(this, item.path),
       };
 
       return {
         ...navItem,
-        strings: [`${navItem.categoryText} ${navItem.primaryText}`],
+        strings: [`${navItem.categoryText} `, navItem.primaryText],
+        treatArrayAsSingleString: true,
         categoryKey,
       };
     });
@@ -580,7 +622,14 @@ export class QuickBar extends LitElement {
 
   private _filterItems = memoizeOne(
     (items: QuickBarItem[], filter: string): QuickBarItem[] => {
-      return fuzzyFilterSort<QuickBarItem>(filter.trimLeft(), items);
+      return fuzzyFilterSort<QuickBarItem>(
+        filter.trimLeft(),
+        items,
+        createMatchDecorator(
+          (matchedChunk) =>
+            html`<span class="highlight-letter">${matchedChunk}</span>`
+        )
+      );
     }
   );
 
@@ -643,6 +692,18 @@ export class QuickBar extends LitElement {
           margin-left: 8px;
         }
 
+        ha-chip.command-category span.highlight-letter {
+          font-weight: bold;
+          color: #0051ff;
+        }
+
+        span.command-text span.highlight-letter,
+        span.item-text.secondary span.highlight-letter,
+        span.item-text.primary span.highlight-letter {
+          font-weight: bold;
+          color: #0098ff;
+        }
+
         .uni-virtualizer-host {
           display: block;
           position: relative;
@@ -658,10 +719,6 @@ export class QuickBar extends LitElement {
         mwc-list-item {
           width: 100%;
         }
-
-        mwc-list-item.command-item {
-          text-transform: capitalize;
-        }
       `,
     ];
   }

test-mocha/common/string/sequence_matching.test.ts

@@ -6,42 +6,54 @@ import {
   ScorableTextItem,
 } from "../../../src/common/string/filter/sequence-matching";
 
+type CreateExpectation = (
+  pattern: string,
+  expScore: number,
+  expDecorated: string
+) => {
+  pattern: string;
+  expected: {
+    score: number;
+    decoratedString: string;
+  };
+};
+const createExpectation: CreateExpectation = (
+  pattern,
+  expScore,
+  expDecorated
+) => ({
+  pattern,
+  expected: {
+    score: expScore,
+    decoratedString: expDecorated,
+  },
+});
+
 describe("fuzzySequentialMatch", () => {
   const item: ScorableTextItem = {
     strings: ["automation.ticker", "Stocks"],
   };
 
-  const createExpectation: (
-    pattern,
-    expected
-  ) => {
-    pattern: string;
-    expected: string | number | undefined;
-  } = (pattern, expected) => ({
-    pattern,
-    expected,
-  });
-
   const shouldMatchEntity = [
-    createExpectation("automation.ticker", 131),
+    createExpectation("automation.ticker", 131, "[automation.ticker]"),
-    createExpectation("automation.ticke", 121),
+    createExpectation("automation.ticke", 121, "[automation.ticke]r"),
-    createExpectation("automation.", 82),
+    createExpectation("automation.", 82, "[automation.]ticker"),
-    createExpectation("au", 10),
+    createExpectation("au", 10, "[au]tomation.ticker"),
-    createExpectation("automationticker", 85),
+    createExpectation("automationticker", 85, "[automation].[ticker]"),
-    createExpectation("tion.tick", 8),
+    createExpectation("tion.tick", 8, "automa[tion.tick]er"),
-    createExpectation("ticker", -4),
+    createExpectation("ticker", -4, "automation.[ticker]"),
-    createExpectation("automation.r", 73),
+    createExpectation("automation.r", 73, "[automation.]ticke[r]"),
-    createExpectation("tick", -8),
+    createExpectation("tick", -8, "automation.[tick]er"),
-    createExpectation("aumatick", 9),
+    createExpectation("aumatick", 9, "[au]to[ma]tion.[tick]er"),
-    createExpectation("aion.tck", 4),
+    createExpectation("aion.tck", 4, "[a]utomat[ion.t]i[ck]er"),
-    createExpectation("ioticker", -4),
+    createExpectation("ioticker", -4, "automat[io]n.[ticker]"),
-    createExpectation("atmto.ikr", -34),
+    createExpectation("atmto.ikr", -34, "[a]u[t]o[m]a[t]i[o]n[.]t[i]c[k]e[r]"),
-    createExpectation("uoaintce", -39),
+    createExpectation("uoaintce", -39, "a[u]t[o]m[a]t[i]o[n].[t]i[c]k[e]r"),
-    createExpectation("au.tce", -3),
+    createExpectation("au.tce", -3, "[au]tomation[.t]i[c]k[e]r"),
-    createExpectation("tomaontkr", -19),
+    createExpectation("tomaontkr", -19, "au[toma]ti[on].[t]ic[k]e[r]"),
-    createExpectation("s", 1),
+    createExpectation("s", 1, "[S]tocks"),
-    createExpectation("stocks", 42),
+    createExpectation("stocks", 42, "[Stocks]"),
-    createExpectation("sks", -5),
+    createExpectation("sks", -5, "[S]toc[ks]"),
   ];
 
   const shouldNotMatchEntity = [
@@ -58,9 +70,21 @@ describe("fuzzySequentialMatch", () => {
 
   describe(`Entity '${item.strings[0]}'`, () => {
     for (const expectation of shouldMatchEntity) {
-      it(`matches '${expectation.pattern}' with return of '${expectation.expected}'`, () => {
+      it(`matches '${expectation.pattern}' with score of '${expectation.expected?.score}'`, () => {
         const res = fuzzySequentialMatch(expectation.pattern, item);
-        assert.equal(res, expectation.expected);
+        assert.equal(res?.score, expectation.expected?.score);
+      });
+
+      it(`decorates '${expectation.pattern}' as '${expectation.expected?.decoratedString}'`, () => {
+        const res = fuzzySequentialMatch(expectation.pattern, item);
+        const allDecoratedStrings = [
+          res!.decoratedStrings![0][0].join(""),
+          res!.decoratedStrings![1][0].join(""),
+        ];
+
+        assert.includeDeepMembers(allDecoratedStrings, [
+          expectation.expected!.decoratedString!,
+        ]);
       });
     }
 
@@ -95,7 +119,7 @@ describe("fuzzyFilterSort", () => {
     strings: ["light.chandelier", "Chandelier"],
     score: 0,
   };
-  const itemsBeforeFilter = [
+  const itemsBeforeFilter: ScorableTextItem[] = [
     automationTicker,
     sensorTicker,
     timerCheckRouter,
@@ -105,13 +129,38 @@ describe("fuzzyFilterSort", () => {
 
   it(`filters and sorts correctly`, () => {
     const expectedItemsAfterFilter = [
-      { ...ticker, score: 44 },
+      {
-      { ...sensorTicker, score: 1 },
+        ...ticker,
-      { ...automationTicker, score: -4 },
+        score: 44,
-      { ...timerCheckRouter, score: -8 },
+        decoratedStrings: [["[ticker]"], ["Just [ticker]"]],
+      },
+      {
+        ...sensorTicker,
+        score: 1,
+        decoratedStrings: [["sensor.[ticker]"], ["Stocks up"]],
+      },
+      {
+        ...automationTicker,
+        score: -4,
+        decoratedStrings: [["automation.[ticker]"], ["Stocks"]],
+      },
+      {
+        ...timerCheckRouter,
+        score: -8,
+        decoratedStrings: [
+          ["automa[ti]on.[c]hec[k]_rout[er]"],
+          ["[Ti]mer [C]hec[k] Rout[er]"],
+        ],
+      },
     ];
 
-    const res = fuzzyFilterSort(filter, itemsBeforeFilter);
+    const res = fuzzyFilterSort(filter, itemsBeforeFilter).map((item) => ({
+      ...item,
+      decoratedStrings: [
+        [item.decoratedStrings![0][0].join("")],
+        [item.decoratedStrings![1][0].join("")],
+      ],
+    }));
 
     assert.deepEqual(res, expectedItemsAfterFilter);
   });