:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.
Python ab-testingai-analyticsanalyticscdpdata-warehouseexperimentsfeature-flagsjavascriptproduct-analyticspythonreactsession-replaysurveystypescriptweb-analytics
const WORD = /[\p{L}\p{N}_]+/gu
export type RankKey = number[]
export const MAX_LOCAL_QUERY_LENGTH = 200
export const searchWords = (text: string): string[] => text.toLowerCase().match(WORD) ?? []
const FILTER_KEY = '(?:path|name|user|author|type|ref)'
export const FILTER_TOKEN = new RegExp(`(^|\\s)([-!](?:${FILTER_KEY}:"[^"]*"|\\S+)|${FILTER_KEY}:("[^"]*"|\\S*))`, 'gi')
export const freeWords = (query: string): string[] => searchWords(query.replace(FILTER_TOKEN, ' '))
// Stops once every path is longer than limit, because a row's smallest value never shrinks.
function osaDistance(a: string, b: string, limit = Infinity): number {
if (Math.abs(a.length - b.length) > limit) {
return limit + 1
}
if (!a.length) {
return b.length
}
if (!b.length) {
return a.length
}
let previousPrevious: number[] = []
let previous = Array.from({ length: b.length + 1 }, (_, j) => j)
for (let i = 1; i <= a.length; i++) {
const current = [i]
for (let j = 1; j <= b.length; j++) {
let value = Math.min(previous[j] + 1, current[j - 1] + 1, previous[j - 1] + (a[i - 1] === b[j - 1] ? 0 : 1))
if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
value = Math.min(value, previousPrevious[j - 2] + 1)
}
current.push(value)
}
if (Math.min(...current) > limit) {
return limit + 1
}
previousPrevious = previous
previous = current
}
return previous[b.length]
}
const singular = (word: string): string =>
word.length > 3 && word.endsWith('s') && !word.endsWith('ss') ? word.slice(0, -1) : word
const allowedTypos = (token: string): number => (token.length < 5 ? 0 : token.length < 9 ? 1 : 2)
export function tokenTypos(token: string, word: string): number | null {
if (word.startsWith(token) || word === singular(token)) {
return 0
}
const budget = allowedTypos(token)
if (!budget) {
return null
}
const distance = Math.min(
osaDistance(token, word.slice(0, token.length), budget),
osaDistance(token, word, budget),
osaDistance(token, singular(word), budget)
)
return distance <= budget ? distance : null
}
export const compareRanks = (a: RankKey, b: RankKey): number => {
for (let i = 0; i < Math.min(a.length, b.length); i++) {
if (a[i] !== b[i]) {
return a[i] - b[i]
}
}
return a.length - b.length
}
interface HighlightSegment {
text: string
match: boolean
}
export function highlightSegments(name: string, words: string[]): HighlightSegment[] {
if (!words.length) {
return [{ text: name, match: false }]
}
const segments: HighlightSegment[] = []
let cursor = 0
for (const found of name.matchAll(WORD)) {
const word = found[0].toLowerCase()
const start = found.index ?? 0
const prefix = words.find((token) => word.startsWith(token))
const length = prefix
? prefix.length
: words.some((token) => tokenTypos(token, word) !== null)
? word.length
: 0
if (!length) {
continue
}
if (start > cursor) {
segments.push({ text: name.slice(cursor, start), match: false })
}
segments.push({ text: name.slice(start, start + length), match: true })
cursor = start + length
}
if (cursor < name.length) {
segments.push({ text: name.slice(cursor), match: false })
}
return segments
}
const UNIFIED_WORD = /[\p{L}\p{N}]+/gu
const unifiedWords = (text: string): string[] => text.toLowerCase().match(UNIFIED_WORD) ?? []
const unifiedSingularText = (text: string): string => unifiedWords(text).map(singular).join(' ')
export const SERVER_FRECENCY_INDEX = 7
export const SERVER_CREATED_INDEX = 8
export interface RankCandidate {
name: string
aliases?: string[]
identity?: string[]
context?: string[]
frecency?: number
createdAt?: number
typePrior?: number
indirect?: boolean
matchesQuery?: boolean
tierBoost?: number
}
const MatchTier = {
Exact: 0,
ExactSingular: 1,
ExactAlias: 2,
Prefix: 3,
PrefixSingular: 4,
NameWords: 5,
AliasWords: 6,
Identity: 7,
Partial: 8,
Weak: 9,
} as const
type MatchTier = (typeof MatchTier)[keyof typeof MatchTier]
type Field = 'name' | 'alias' | 'identity' | 'context'
interface TokenHit {
typos: number
position: number
field: Field
wordStart: boolean
}
const MAX_POSITION_PENALTY = 3
const MIN_PARTIAL_TOKEN_LENGTH = 3
export const isIdentityQuery = (query: string): boolean => /^\S*[.@]\S+$/.test(query.trim())
function hitInWords(token: string, words: string[]): Omit<TokenHit, 'field'> | null {
let best: Omit<TokenHit, 'field'> | null = null
for (let position = 0; position < words.length; position++) {
const typos = tokenTypos(token, words[position])
if (typos === 0) {
return { typos, position, wordStart: true }
}
if (typos !== null && (!best || typos < best.typos)) {
best = { typos, position, wordStart: true }
}
}
// A literal match inside a word needs no typo, so it beats a fuzzy word match.
const inside = token.length < MIN_PARTIAL_TOKEN_LENGTH ? -1 : words.findIndex((word) => word.includes(token))
return inside >= 0 ? { typos: 0, position: inside, wordStart: false } : best
}
const isClean = (hit: Omit<TokenHit, 'field'> | null): boolean => !!hit && hit.typos === 0 && hit.wordStart
const wordStartPosition = (token: string, words: string[]): number =>
words.findIndex((word) => word.startsWith(token) || word === singular(token))
function cleanHit(token: string, candidate: RankCandidate, nameWords: string[]): TokenHit | null {
const name = wordStartPosition(token, nameWords)
if (name >= 0) {
return { typos: 0, position: name, field: 'name', wordStart: true }
}
if ((candidate.aliases ?? []).some((alias) => wordStartPosition(token, unifiedWords(alias)) >= 0)) {
return { typos: 0, position: MAX_POSITION_PENALTY, field: 'alias', wordStart: true }
}
const inIdentity = (candidate.identity ?? []).some((value) => value.toLowerCase().includes(token))
return inIdentity ? { typos: 0, position: MAX_POSITION_PENALTY, field: 'identity', wordStart: true } : null
}
function tokenHit(token: string, candidate: RankCandidate, nameWords: string[], strict: boolean): TokenHit | null {
const clean = cleanHit(token, candidate, nameWords)
if (clean || strict) {
return clean
}
const name = hitInWords(token, nameWords)
const context = hitInWords(token, (candidate.context ?? []).flatMap(unifiedWords))
const hits: TokenHit[] = [
...(name ? [{ ...name, field: 'name' as const }] : []),
...(candidate.aliases ?? []).flatMap((alias) => {
const hit = hitInWords(token, unifiedWords(alias))
return hit ? [{ ...hit, position: MAX_POSITION_PENALTY, field: 'alias' as const }] : []
}),
...(context ? [{ ...context, position: MAX_POSITION_PENALTY, field: 'context' as const }] : []),
// The source already matched the whole search on fields the browser cannot see.
...(candidate.matchesQuery
? [{ typos: 0, position: MAX_POSITION_PENALTY, field: 'identity' as const, wordStart: true }]
: []),
]
return hits.length ? hits.reduce((best, hit) => (hit.typos < best.typos ? hit : best)) : null
}
function wholeQueryTier(query: string, candidate: RankCandidate): MatchTier | null {
const exactQuery = unifiedWords(query).join(' ')
const exactName = unifiedWords(candidate.name).join(' ')
const singularQuery = unifiedSingularText(query)
const singularName = unifiedSingularText(candidate.name)
const rawQuery = query.trim().toLowerCase()
const identity = isIdentityQuery(query) ? (candidate.identity ?? []).map((value) => value.toLowerCase()) : []
const tiers: [MatchTier, () => boolean][] = [
[MatchTier.Exact, () => exactName === exactQuery || identity.includes(rawQuery)],
[MatchTier.ExactSingular, () => singularName === singularQuery],
[
MatchTier.ExactAlias,
() => (candidate.aliases ?? []).some((alias) => unifiedSingularText(alias) === singularQuery),
],
[
MatchTier.Prefix,
() => exactName.startsWith(exactQuery) || identity.some((value) => value.startsWith(rawQuery)),
],
[MatchTier.PrefixSingular, () => singularName.startsWith(singularQuery)],
]
return tiers.find(([, matches]) => matches())?.[0] ?? null
}
const WORD_TIERS: [MatchTier, (hits: TokenHit[]) => boolean][] = [
[MatchTier.NameWords, (hits) => hits.every((hit) => hit.field === 'name' && isClean(hit))],
[
MatchTier.AliasWords,
(hits) => hits.every((hit) => (hit.field === 'name' || hit.field === 'alias') && isClean(hit)),
],
[
MatchTier.Identity,
(hits) => hits.some((hit) => hit.field === 'identity') && hits.every((hit) => hit.field !== 'context'),
],
[MatchTier.Partial, (hits) => hits.every((hit) => hit.field === 'name')],
]
function matchTier(query: string, hits: (TokenHit | null)[], candidate: RankCandidate): MatchTier {
const whole = wholeQueryTier(query, candidate)
if (whole !== null) {
return whole
}
if (hits.some((hit) => hit === null)) {
return MatchTier.Weak
}
return WORD_TIERS.find(([, matches]) => matches(hits as TokenHit[]))?.[0] ?? MatchTier.Weak
}
function proximityOf(positions: number[]): number {
let proximity = 0
for (let i = 1; i < positions.length; i++) {
proximity +=
Math.max(Math.abs(positions[i] - positions[i - 1]) - 1, 0) + (positions[i] < positions[i - 1] ? 1 : 0)
}
return Math.min(proximity, MAX_POSITION_PENALTY)
}
const usageTier = (frecency: number): number => (frecency >= 1 ? 0 : frecency > 0 ? 1 : 2)
export function rankCandidate(query: string, candidate: RankCandidate, strict = false): RankKey | null {
const normalizedQuery = query.trim().toLowerCase().replace(/\s+/g, ' ').slice(0, MAX_LOCAL_QUERY_LENGTH)
const tokens = [...new Set(unifiedWords(normalizedQuery))]
if (!tokens.length) {
return null
}
const nameWords = unifiedWords(candidate.name)
const hits = tokens.map((token) => tokenHit(token, candidate, nameWords, strict))
const found = hits.filter((hit): hit is TokenHit => hit !== null)
if (!found.length || (strict && found.length < hits.length)) {
return null
}
const positions = found.filter((hit) => hit.field === 'name').map((hit) => hit.position)
const frecency = candidate.frecency ?? 0
return [
-found.length,
found.reduce((sum, hit) => sum + hit.typos, 0),
Math.max(matchTier(normalizedQuery, hits, candidate) - (candidate.tierBoost ?? 0), 0),
usageTier(frecency),
proximityOf(positions),
Math.min(...positions, MAX_POSITION_PENALTY),
candidate.typePrior ?? 1,
Number(!!candidate.indirect),
-Math.round(frecency * 1000),
-(candidate.createdAt ?? 0),
]
}
// The server matched words the browser cannot find, so the result ranks as a folder or type match.
export function serverOnlyRank(serverRank: RankKey, candidate: RankCandidate): RankKey {
const frecency = candidate.frecency ?? 0
return [
serverRank[0],
serverRank[1],
MatchTier.Weak,
usageTier(frecency),
Math.min(serverRank[2], MAX_POSITION_PENALTY),
MAX_POSITION_PENALTY,
candidate.typePrior ?? 1,
1,
-Math.round(frecency * 1000),
-(candidate.createdAt ?? 0),
]
}
export function strictLocalMatches<T extends { name: string; displayName?: string; searchKeywords?: string[] }>(
items: T[],
query: string
): T[] {
return items
.map((item) => ({
item,
rank: rankCandidate(
query,
{ name: String(item.displayName || item.name), aliases: item.searchKeywords },
true
),
}))
.filter((entry): entry is { item: T; rank: RankKey } => !!entry.rank)
.sort((a, b) => compareRanks(a.rank, b.rank))
.map(({ item }) => item)
}