xref: /aosp_15_r20/external/perfetto/ui/src/core/search_manager.ts (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc) 
1// Copyright (C) 2024 The Android Open Source Project
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15import {AsyncLimiter} from '../base/async_limiter';
16import {searchSegment} from '../base/binary_search';
17import {assertExists, assertTrue} from '../base/logging';
18import {sqliteString} from '../base/string_utils';
19import {Time, TimeSpan} from '../base/time';
20import {exists} from '../base/utils';
21import {ResultStepEventHandler} from '../public/search';
22import {
23  ANDROID_LOGS_TRACK_KIND,
24  CPU_SLICE_TRACK_KIND,
25} from '../public/track_kinds';
26import {Workspace} from '../public/workspace';
27import {Engine} from '../trace_processor/engine';
28import {LONG, NUM, STR} from '../trace_processor/query_result';
29import {escapeSearchQuery} from '../trace_processor/query_utils';
30import {raf} from './raf_scheduler';
31import {SearchSource} from './search_data';
32import {TimelineImpl} from './timeline';
33import {TrackManagerImpl} from './track_manager';
34
35export interface SearchResults {
36  eventIds: Float64Array;
37  tses: BigInt64Array;
38  utids: Float64Array;
39  trackUris: string[];
40  sources: SearchSource[];
41  totalResults: number;
42}
43
44export class SearchManagerImpl {
45  private _searchGeneration = 0;
46  private _searchText = '';
47  private _searchWindow?: TimeSpan;
48  private _results?: SearchResults;
49  private _resultIndex = -1;
50  private _searchInProgress = false;
51
52  // TODO(primiano): once we get rid of globals, these below can be made always
53  // defined. the ?: is to deal with globals-before-trace-load.
54  private _timeline?: TimelineImpl;
55  private _trackManager?: TrackManagerImpl;
56  private _workspace?: Workspace;
57  private _engine?: Engine;
58  private _limiter = new AsyncLimiter();
59  private _onResultStep?: ResultStepEventHandler;
60
61  constructor(args?: {
62    timeline: TimelineImpl;
63    trackManager: TrackManagerImpl;
64    workspace: Workspace;
65    engine: Engine;
66    onResultStep: ResultStepEventHandler;
67  }) {
68    this._timeline = args?.timeline;
69    this._trackManager = args?.trackManager;
70    this._engine = args?.engine;
71    this._workspace = args?.workspace;
72    this._onResultStep = args?.onResultStep;
73  }
74
75  search(text: string) {
76    if (text === this._searchText) {
77      return;
78    }
79    this._searchText = text;
80    this._searchGeneration++;
81    this._results = undefined;
82    this._resultIndex = -1;
83    this._searchInProgress = false;
84    if (text !== '') {
85      this._searchInProgress = true;
86      this._searchWindow = this._timeline?.visibleWindow.toTimeSpan();
87      this._limiter.schedule(async () => {
88        await this.executeSearch();
89        this._searchInProgress = false;
90        raf.scheduleFullRedraw();
91      });
92    }
93    raf.scheduleFullRedraw();
94  }
95
96  reset() {
97    this.search('');
98  }
99
100  stepForward() {
101    this.stepInternal(false);
102  }
103
104  stepBackwards() {
105    this.stepInternal(true);
106  }
107
108  private stepInternal(reverse = false) {
109    if (this._searchWindow === undefined) return;
110    if (this._results === undefined) return;
111
112    const index = this._resultIndex;
113    const {start: startNs, end: endNs} = this._searchWindow;
114    const currentTs = this._results.tses[index];
115
116    // If the value of |this._results.totalResults| is 0,
117    // it means that the query is in progress or no results are found.
118    if (this._results.totalResults === 0) {
119      return;
120    }
121
122    // If this is a new search or the currentTs is not in the viewport,
123    // select the first/last item in the viewport.
124    if (
125      index === -1 ||
126      (currentTs !== -1n && (currentTs < startNs || currentTs > endNs))
127    ) {
128      if (reverse) {
129        const [smaller] = searchSegment(this._results.tses, endNs);
130        // If there is no item in the viewport just go to the previous.
131        if (smaller === -1) {
132          this.setResultIndexWithSaturation(index - 1);
133        } else {
134          this._resultIndex = smaller;
135        }
136      } else {
137        const [, larger] = searchSegment(this._results.tses, startNs);
138        // If there is no item in the viewport just go to the next.
139        if (larger === -1) {
140          this.setResultIndexWithSaturation(index + 1);
141        } else {
142          this._resultIndex = larger;
143        }
144      }
145    } else {
146      // If the currentTs is in the viewport, increment the index.
147      if (reverse) {
148        this.setResultIndexWithSaturation(index - 1);
149      } else {
150        this.setResultIndexWithSaturation(index + 1);
151      }
152    }
153    if (this._onResultStep) {
154      this._onResultStep({
155        eventId: this._results.eventIds[this._resultIndex],
156        ts: Time.fromRaw(this._results.tses[this._resultIndex]),
157        trackUri: this._results.trackUris[this._resultIndex],
158        source: this._results.sources[this._resultIndex],
159      });
160    }
161    raf.scheduleFullRedraw();
162  }
163
164  private setResultIndexWithSaturation(nextIndex: number) {
165    const tot = assertExists(this._results).totalResults;
166    assertTrue(tot !== 0); // The early out in step() guarantees this.
167    // This is a modulo operation that works also for negative numbers.
168    this._resultIndex = ((nextIndex % tot) + tot) % tot;
169  }
170
171  get hasResults() {
172    return this._results !== undefined;
173  }
174
175  get searchResults() {
176    return this._results;
177  }
178
179  get resultIndex() {
180    return this._resultIndex;
181  }
182
183  get searchText() {
184    return this._searchText;
185  }
186
187  get searchGeneration() {
188    return this._searchGeneration;
189  }
190
191  get searchInProgress(): boolean {
192    return this._searchInProgress;
193  }
194
195  private async executeSearch() {
196    const search = this._searchText;
197    const window = this._searchWindow;
198    const searchLiteral = escapeSearchQuery(this._searchText);
199    const generation = this._searchGeneration;
200
201    const engine = this._engine;
202    const trackManager = this._trackManager;
203    const workspace = this._workspace;
204    if (!engine || !trackManager || !workspace || !window) {
205      return;
206    }
207
208    // TODO(stevegolton): Avoid recomputing these indexes each time.
209    const trackUrisByCpu = new Map<number, string>();
210    const allTracks = trackManager.getAllTracks();
211    allTracks.forEach((td) => {
212      const tags = td?.tags;
213      const cpu = tags?.cpu;
214      const kind = tags?.kind;
215      exists(cpu) &&
216        kind === CPU_SLICE_TRACK_KIND &&
217        trackUrisByCpu.set(cpu, td.uri);
218    });
219
220    const trackUrisByTrackId = new Map<number, string>();
221    allTracks.forEach((td) => {
222      const trackIds = td?.tags?.trackIds ?? [];
223      trackIds.forEach((trackId) => trackUrisByTrackId.set(trackId, td.uri));
224    });
225
226    const utidRes = await engine.query(`select utid from thread join process
227    using(upid) where
228      thread.name glob ${searchLiteral} or
229      process.name glob ${searchLiteral}`);
230    const utids = [];
231    for (const it = utidRes.iter({utid: NUM}); it.valid(); it.next()) {
232      utids.push(it.utid);
233    }
234
235    const res = await engine.query(`
236      select
237        id as sliceId,
238        ts,
239        'cpu' as source,
240        cpu as sourceId,
241        utid
242      from sched where utid in (${utids.join(',')})
243      union all
244      select *
245      from (
246        select
247          slice_id as sliceId,
248          ts,
249          'slice' as source,
250          track_id as sourceId,
251          0 as utid
252          from slice
253          where slice.name glob ${searchLiteral}
254            or (
255              0 != CAST(${sqliteString(search)} AS INT) and
256              sliceId = CAST(${sqliteString(search)} AS INT)
257            )
258        union
259        select
260          slice_id as sliceId,
261          ts,
262          'slice' as source,
263          track_id as sourceId,
264          0 as utid
265        from slice
266        join args using(arg_set_id)
267        where string_value glob ${searchLiteral} or key glob ${searchLiteral}
268      )
269      union all
270      select
271        id as sliceId,
272        ts,
273        'log' as source,
274        0 as sourceId,
275        utid
276      from android_logs where msg glob ${searchLiteral}
277      order by ts
278    `);
279
280    const searchResults: SearchResults = {
281      eventIds: new Float64Array(0),
282      tses: new BigInt64Array(0),
283      utids: new Float64Array(0),
284      sources: [],
285      trackUris: [],
286      totalResults: 0,
287    };
288
289    const lowerSearch = search.toLowerCase();
290    for (const track of workspace.flatTracksOrdered) {
291      // We don't support searching for tracks that don't have a URI.
292      if (!track.uri) continue;
293      if (track.title.toLowerCase().indexOf(lowerSearch) === -1) {
294        continue;
295      }
296      searchResults.totalResults++;
297      searchResults.sources.push('track');
298      searchResults.trackUris.push(track.uri);
299    }
300
301    const rows = res.numRows();
302    searchResults.eventIds = new Float64Array(
303      searchResults.totalResults + rows,
304    );
305    searchResults.tses = new BigInt64Array(searchResults.totalResults + rows);
306    searchResults.utids = new Float64Array(searchResults.totalResults + rows);
307    for (let i = 0; i < searchResults.totalResults; ++i) {
308      searchResults.eventIds[i] = -1;
309      searchResults.tses[i] = -1n;
310      searchResults.utids[i] = -1;
311    }
312
313    const it = res.iter({
314      sliceId: NUM,
315      ts: LONG,
316      source: STR,
317      sourceId: NUM,
318      utid: NUM,
319    });
320    for (; it.valid(); it.next()) {
321      let track: string | undefined = undefined;
322
323      if (it.source === 'cpu') {
324        track = trackUrisByCpu.get(it.sourceId);
325      } else if (it.source === 'slice') {
326        track = trackUrisByTrackId.get(it.sourceId);
327      } else if (it.source === 'log') {
328        track = trackManager
329          .getAllTracks()
330          .find((td) => td.tags?.kind === ANDROID_LOGS_TRACK_KIND)?.uri;
331      }
332      // The .get() calls above could return undefined, this isn't just an else.
333      if (track === undefined) {
334        continue;
335      }
336
337      const i = searchResults.totalResults++;
338      searchResults.trackUris.push(track);
339      searchResults.sources.push(it.source as SearchSource);
340      searchResults.eventIds[i] = it.sliceId;
341      searchResults.tses[i] = it.ts;
342      searchResults.utids[i] = it.utid;
343    }
344
345    if (generation !== this._searchGeneration) {
346      // We arrived too late. By the time we computed results the user issued
347      // another search.
348      return;
349    }
350    this._results = searchResults;
351    this._resultIndex = -1;
352  }
353}
354