Repository: jlfwong/speedscope (ts)

Issue:
Search for occurences of whole word.
Hi! 

Thank you very much for this outstanding and powerful tool, which makes my life much easier and more productive! :) I'm using speedscope from some time and currently I have a feeling that its built-in search functionality is not searching for whole words, which is quite unusual for me. Seems to me that it's enough that the respective letters constituting the word I'm searching for are present to be counted as an occurrence. 

![image](https://user-images.githubusercontent.com/36447190/121038455-9bfaab80-c7b0-11eb-8f9a-f56476d5ed44.png)

How can I make the search engine to search for whole words? If that's not possible could you kindly add such feature please?


Pull request description:
Replace fuzzy matching with exact substring matching for finding matching frames
In #297, I re-used the fuzzy matching logic I implemented in #282 for profile selection. Based on feedback from several people in #352, this is surprising behavior.

Upon reflection, this should have been obvious -- I hijacked the Ctrl/Cmd+F browser behaviour, so I should try to replicate the expected behaviour there as closely as possible. Given more patience, I also would've done some user research :)

This PR updates this logic to try to more closely match browser behaviour. This means case-insensitive, exact-substring matching.

I've left the fuzzy matching alone for profile selection since that doesn't attempt to mimic browser behaviour.

The non-fuzzy matching feels slightly odd to me given the filtering behaviour on the sandwich view, but I think consistency across this find UI is important.

Here are the before & after results when searching for the string "ca" in the example profile.

|Before|After|
|-|-|
|<img width="1791" alt="image" src="https://user-images.githubusercontent.com/150329/197232741-6d1d7a8a-8b8c-4a4f-98e3-2c043fd7efd5.png">|<img width="1789" alt="image" src="https://user-images.githubusercontent.com/150329/197232694-82697b68-ca15-49e7-887b-2606646ee5e9.png">|


Fixes #352 
Supersedes #403 

Patch:
diff --git a/src/lib/profile-search.ts b/src/lib/profile-search.ts
index 5286129..81a9a02 100644
--- a/src/lib/profile-search.ts
+++ b/src/lib/profile-search.ts
@@ -1,5 +1,4 @@
 import {Profile, Frame, CallTreeNode} from './profile'
-import {FuzzyMatch, fuzzyMatchStrings} from './fuzzy-find'
 import {Flamechart, FlamechartFrame} from './flamechart'
 import {Rect, Vec2} from './math'
 
@@ -8,19 +7,47 @@ export enum FlamechartType {
   LEFT_HEAVY_FLAME_GRAPH,
 }
 
+// In previous versions of speedscope, searching for strings within the profile
+// was done using fuzzy finding. As it turns out, this was surprising behavior
+// to most people, so we've switched to a more traditional substring search that
+// more closely mimics browser behavior.
+//
+// This is case insensitive for both the needle & the haystack. This means
+// searching for "hello" will match "Hello" and "HELLO", and searching for
+// "HELLO" will match both "hello" and "Hello". This matches Chrome's behavior
+// as far as I can tell.
+//
+// See https://github.com/jlfwong/speedscope/issues/352
+//
+// Return ranges for all matches in order to highlight them.
+export function exactMatchStrings(text: string, pattern: string): [number, number][] {
+  const lowerText = text.toLocaleLowerCase()
+  const lowerPattern = pattern.toLocaleLowerCase()
+
+  let lastIndex = 0
+  const matchedRanges: Array<[number, number]> = []
+  while (true) {
+    let index = lowerText.indexOf(lowerPattern, lastIndex)
+    if (index === -1) {
+      return matchedRanges
+    }
+    matchedRanges.push([index, index + pattern.length])
+    lastIndex = index + pattern.length
+  }
+}
+
 // A utility class for storing cached search results to avoid recomputation when
 // the search results & profile did not change.
 export class ProfileSearchResults {
   constructor(readonly profile: Profile, readonly searchQuery: string) {}
 
-  private matches: Map<Frame, FuzzyMatch> | null = null
-  getMatchForFrame(frame: Frame): FuzzyMatch | null {
+  private matches: Map<Frame, [number, number][] | null> | null = null
+  getMatchForFrame(frame: Frame): [number, number][] | null {
     if (!this.matches) {
       this.matches = new Map()
       this.profile.forEachFrame(frame => {
-        const match = fuzzyMatchStrings(frame.name, this.searchQuery)
-        if (match == null) return
-        this.matches!.set(frame, match)
+        const match = exactMatchStrings(frame.name, this.searchQuery)
+        this.matches!.set(frame, match.length === 0 ? null : match)
       })
     }
     return this.matches.get(frame) || null
diff --git a/src/views/flamechart-pan-zoom-view.tsx b/src/views/flamechart-pan-zoom-view.tsx
index 26d51fb..2cf5c08 100644
--- a/src/views/flamechart-pan-zoom-view.tsx
+++ b/src/views/flamechart-pan-zoom-view.tsx
@@ -241,7 +241,7 @@ export class FlamechartPanZoomView extends Component<FlamechartPanZoomViewProps,
           if (match) {
             const rangesToHighlightInTrimmedText = remapRangesToTrimmedText(
               trimmedText,
-              match.matchedRanges,
+              match
             )
 
             // Once we have the character ranges to highlight, we need to
diff --git a/src/views/profile-table-view.tsx b/src/views/profile-table-view.tsx
index dcde036..d46638d 100644
--- a/src/views/profile-table-view.tsx
+++ b/src/views/profile-table-view.tsx
@@ -217,7 +217,7 @@ export const ProfileTableView = memo(
           rows.push(
             ProfileTableRowView({
               frame,
-              matchedRanges: match == null ? null : match.matchedRanges,
+              matchedRanges: match == null ? null : match,
               index: i,
               profile: profile,
               selectedFrame: selectedFrame,
diff --git a/src/views/sandwich-view.tsx b/src/views/sandwich-view.tsx
index 77adbb7..08ab148 100644
--- a/src/views/sandwich-view.tsx
+++ b/src/views/sandwich-view.tsx
@@ -11,7 +11,6 @@ import {SandwichSearchView} from './sandwich-search-view'
 import {ActiveProfileState} from '../app-state/active-profile-state'
 import {sortBy} from '../lib/utils'
 import {ProfileSearchContext} from './search-view'
-import {FuzzyMatch} from '../lib/fuzzy-find'
 import {Theme, useTheme, withTheme} from './themes/theme'
 import {SortField, SortDirection, profileGroupAtom, tableSortMethodAtom} from '../app-state'
 import {useAtom} from '../lib/atom'
@@ -141,7 +140,7 @@ interface SandwichViewContextData {
   selectedFrame: Frame | null
   setSelectedFrame: (frame: Frame | null) => void
   getIndexForFrame: (frame: Frame) => number | null
-  getSearchMatchForFrame: (frame: Frame) => FuzzyMatch | null
+  getSearchMatchForFrame: (frame: Frame) => [number, number][] | null
 }
 
 export const SandwichViewContext = createContext<SandwichViewContextData | null>(null)
@@ -204,7 +203,7 @@ export const SandwichViewContainer = memo((ownProps: SandwichViewContainerProps)
     }
   }, [rowList])
 
-  const getSearchMatchForFrame: (frame: Frame) => FuzzyMatch | null = useMemo(() => {
+  const getSearchMatchForFrame: (frame: Frame) => [number, number][] | null = useMemo(() => {
     return (frame: Frame) => {
       if (profileSearchResults == null) return null
       return profileSearchResults.getMatchForFrame(frame)


Test patch:
diff --git a/src/lib/profile-search.test.ts b/src/lib/profile-search.test.ts
new file mode 100644
index 0000000..5195cda
--- /dev/null
+++ b/src/lib/profile-search.test.ts
@@ -0,0 +1,50 @@
+import {exactMatchStrings} from './profile-search'
+
+function assertMatch(text: string, pattern: string, expected: string) {
+  const match = exactMatchStrings(text, pattern)
+
+  let highlighted = ''
+  let last = 0
+  for (let range of match) {
+    highlighted += `${text.slice(last, range[0])}[${text.slice(range[0], range[1])}]`
+    last = range[1]
+  }
+  highlighted += text.slice(last)
+
+  expect(highlighted).toEqual(expected)
+}
+
+function assertNoMatch(text: string, pattern: string) {
+  assertMatch(text, pattern, text)
+}
+
+describe('exactMatchStrings', () => {
+  test('no match', () => {
+    assertNoMatch('a', 'b')
+    assertNoMatch('aa', 'ab')
+    assertNoMatch('a', 'aa')
+    assertNoMatch('ca', 'ac')
+  })
+
+  test('full text match', () => {
+    assertMatch('hello', 'hello', '[hello]')
+    assertMatch('multiple words', 'multiple words', '[multiple words]')
+  })
+
+  test('case sensitivity', () => {
+    assertMatch('HELLO', 'hello', '[HELLO]')
+    assertMatch('Hello', 'hello', '[Hello]')
+    assertMatch('hello', 'Hello', '[hello]')
+    assertMatch('hello', 'HELLO', '[hello]')
+  })
+
+  test('multiple occurrences', () => {
+    assertMatch('hello hello', 'hello', '[hello] [hello]')
+    assertMatch('hellohello', 'hello', '[hello][hello]')
+  })
+
+  test('overlapping occurrences', () => {
+    assertMatch('aaaaa', 'aa', '[aa][aa]a')
+    assertMatch('abababa', 'aba', '[aba]b[aba]')
+  })
+})