Blame · Line-by-line history
issue-similarity.ts
Each line is annotated with the commit that last touched it. Click any SHA to jump to that commit and see the surrounding change.
| b184a75 | 1 | /** |
| 2 | * Block J28 — Issue title similarity / duplicate suggestions. | |
| 3 | * | |
| 4 | * Pure token-based Jaccard similarity for issue titles (+ optional bodies). | |
| 5 | * The idea: when a user is about to open a new issue, we can show the top-N | |
| 6 | * most similar existing issues so they can check if it's a duplicate before | |
| 7 | * posting. Also usable on an existing issue to surface related ones. | |
| 8 | * | |
| 9 | * The algorithm is deliberately simple and IO-free: | |
| 10 | * 1. Lowercase → strip punctuation → whitespace-split. | |
| 11 | * 2. Remove English stopwords. | |
| 12 | * 3. Drop tokens shorter than `MIN_TOKEN_LENGTH`. | |
| 13 | * 4. Score = |A ∩ B| / |A ∪ B| (Jaccard index). | |
| 14 | * | |
| 15 | * Scores are in [0, 1]; `rankCandidates` returns candidates sorted score-desc | |
| 16 | * (tie-break newest-first) and filters by `minScore` + `limit`. | |
| 17 | */ | |
| 18 | ||
| 19 | export const MIN_TOKEN_LENGTH = 2; | |
| 20 | ||
| 21 | // Small, deliberately short English stopword list. Keeping it conservative | |
| 22 | // so titles like "add auth to api" don't collapse to nothing. | |
| 23 | export const STOPWORDS: ReadonlySet<string> = new Set([ | |
| 24 | "a", | |
| 25 | "an", | |
| 26 | "the", | |
| 27 | "and", | |
| 28 | "or", | |
| 29 | "but", | |
| 30 | "if", | |
| 31 | "then", | |
| 32 | "so", | |
| 33 | "to", | |
| 34 | "of", | |
| 35 | "in", | |
| 36 | "on", | |
| 37 | "at", | |
| 38 | "by", | |
| 39 | "for", | |
| 40 | "with", | |
| 41 | "from", | |
| 42 | "as", | |
| 43 | "is", | |
| 44 | "it", | |
| 45 | "its", | |
| 46 | "this", | |
| 47 | "that", | |
| 48 | "these", | |
| 49 | "those", | |
| 50 | "be", | |
| 51 | "been", | |
| 52 | "are", | |
| 53 | "was", | |
| 54 | "were", | |
| 55 | "do", | |
| 56 | "does", | |
| 57 | "did", | |
| 58 | "done", | |
| 59 | "have", | |
| 60 | "has", | |
| 61 | "had", | |
| 62 | "will", | |
| 63 | "would", | |
| 64 | "can", | |
| 65 | "could", | |
| 66 | "should", | |
| 67 | "may", | |
| 68 | "might", | |
| 69 | "i", | |
| 70 | "me", | |
| 71 | "my", | |
| 72 | "we", | |
| 73 | "us", | |
| 74 | "our", | |
| 75 | "you", | |
| 76 | "your", | |
| 77 | "he", | |
| 78 | "she", | |
| 79 | "they", | |
| 80 | "them", | |
| 81 | "their", | |
| 82 | ]); | |
| 83 | ||
| 84 | /** | |
| 85 | * Lowercase, strip non-alphanumeric (Unicode-aware), split on whitespace, | |
| 86 | * drop stopwords + short tokens. Returns a `Set<string>` (dedup implicit). | |
| 87 | */ | |
| 88 | export function tokeniseTitle(input: unknown): Set<string> { | |
| 89 | if (typeof input !== "string") return new Set(); | |
| 90 | const lower = input.toLowerCase(); | |
| 91 | // Replace anything that isn't a Unicode letter, digit, or dash with space. | |
| 92 | // Using \p{L} + \p{N} to stay multilingual. | |
| 93 | const cleaned = lower.replace(/[^\p{L}\p{N}_-]+/gu, " "); | |
| 94 | const out = new Set<string>(); | |
| 95 | for (const tok of cleaned.split(/\s+/)) { | |
| 96 | if (tok.length < MIN_TOKEN_LENGTH) continue; | |
| 97 | if (STOPWORDS.has(tok)) continue; | |
| 98 | out.add(tok); | |
| 99 | } | |
| 100 | return out; | |
| 101 | } | |
| 102 | ||
| 103 | /** Classic Jaccard: |A ∩ B| / |A ∪ B|. Returns 0 when both sets are empty. */ | |
| 104 | export function jaccard<T>(a: ReadonlySet<T>, b: ReadonlySet<T>): number { | |
| 105 | if (a.size === 0 && b.size === 0) return 0; | |
| 106 | let intersection = 0; | |
| 107 | // Iterate the smaller set for efficiency. | |
| 108 | const [small, large] = a.size <= b.size ? [a, b] : [b, a]; | |
| 109 | for (const t of small) if (large.has(t)) intersection++; | |
| 110 | const union = a.size + b.size - intersection; | |
| 111 | return union === 0 ? 0 : intersection / union; | |
| 112 | } | |
| 113 | ||
| 114 | export interface SimilarityCandidate { | |
| 115 | id: string; | |
| 116 | number: number; | |
| 117 | title: string; | |
| 118 | state?: string; | |
| 119 | createdAt?: Date | string | null; | |
| 120 | } | |
| 121 | ||
| 122 | export interface SimilarityResult { | |
| 123 | id: string; | |
| 124 | number: number; | |
| 125 | title: string; | |
| 126 | state?: string; | |
| 127 | score: number; | |
| 128 | } | |
| 129 | ||
| 130 | export interface RankOptions { | |
| 131 | /** Discard candidates with score strictly below this. Default 0.15. */ | |
| 132 | minScore?: number; | |
| 133 | /** Return at most this many results. Default 5. */ | |
| 134 | limit?: number; | |
| 135 | /** Optional id of the source issue — never ranked against itself. */ | |
| 136 | excludeId?: string; | |
| 137 | /** Optional number of the source issue — never ranked against itself. */ | |
| 138 | excludeNumber?: number; | |
| 139 | /** If set, restrict candidates to this state. */ | |
| 140 | state?: string; | |
| 141 | } | |
| 142 | ||
| 143 | export const DEFAULT_MIN_SCORE = 0.15; | |
| 144 | export const DEFAULT_LIMIT = 5; | |
| 145 | ||
| 146 | function toTime(v: Date | string | null | undefined): number { | |
| 147 | if (!v) return 0; | |
| 148 | if (v instanceof Date) { | |
| 149 | const t = v.getTime(); | |
| 150 | return Number.isNaN(t) ? 0 : t; | |
| 151 | } | |
| 152 | if (typeof v === "string") { | |
| 153 | const t = new Date(v).getTime(); | |
| 154 | return Number.isNaN(t) ? 0 : t; | |
| 155 | } | |
| 156 | return 0; | |
| 157 | } | |
| 158 | ||
| 159 | export function rankCandidates( | |
| 160 | targetTitle: string, | |
| 161 | candidates: readonly SimilarityCandidate[], | |
| 162 | opts: RankOptions = {} | |
| 163 | ): SimilarityResult[] { | |
| 164 | const min = opts.minScore ?? DEFAULT_MIN_SCORE; | |
| 165 | const limit = Math.max(0, opts.limit ?? DEFAULT_LIMIT); | |
| 166 | const stateFilter = opts.state; | |
| 167 | const tTokens = tokeniseTitle(targetTitle); | |
| 168 | if (tTokens.size === 0 || limit === 0) return []; | |
| 169 | ||
| 170 | const results: (SimilarityResult & { __t: number })[] = []; | |
| 171 | for (const c of candidates) { | |
| 172 | if (opts.excludeId && c.id === opts.excludeId) continue; | |
| 173 | if ( | |
| 174 | opts.excludeNumber !== undefined && | |
| 175 | c.number === opts.excludeNumber | |
| 176 | ) { | |
| 177 | continue; | |
| 178 | } | |
| 179 | if (stateFilter && c.state !== stateFilter) continue; | |
| 180 | const cTokens = tokeniseTitle(c.title); | |
| 181 | if (cTokens.size === 0) continue; | |
| 182 | const score = jaccard(tTokens, cTokens); | |
| 183 | if (score < min) continue; | |
| 184 | results.push({ | |
| 185 | id: c.id, | |
| 186 | number: c.number, | |
| 187 | title: c.title, | |
| 188 | state: c.state, | |
| 189 | score, | |
| 190 | __t: toTime(c.createdAt), | |
| 191 | }); | |
| 192 | } | |
| 193 | ||
| 194 | results.sort((a, b) => { | |
| 195 | if (a.score !== b.score) return b.score - a.score; | |
| 196 | // Tie-break: newer candidates first (more likely relevant). | |
| 197 | if (a.__t !== b.__t) return b.__t - a.__t; | |
| 198 | // Stable final tie-break on number-desc. | |
| 199 | return b.number - a.number; | |
| 200 | }); | |
| 201 | ||
| 202 | return results.slice(0, limit).map(({ __t, ...rest }) => rest); | |
| 203 | } | |
| 204 | ||
| 205 | /** "47%" style — useful for UI rendering. */ | |
| 206 | export function formatSimilarityPercent(score: number): string { | |
| 207 | if (!Number.isFinite(score)) return "0%"; | |
| 208 | const clamped = Math.max(0, Math.min(1, score)); | |
| 209 | return `${Math.round(clamped * 100)}%`; | |
| 210 | } | |
| 211 | ||
| 212 | /** One-shot convenience: tokenise + rank. */ | |
| 213 | export function findSimilar( | |
| 214 | targetTitle: string, | |
| 215 | candidates: readonly SimilarityCandidate[], | |
| 216 | opts?: RankOptions | |
| 217 | ): SimilarityResult[] { | |
| 218 | return rankCandidates(targetTitle, candidates, opts); | |
| 219 | } | |
| 220 | ||
| 221 | export const __internal = { | |
| 222 | MIN_TOKEN_LENGTH, | |
| 223 | STOPWORDS, | |
| 224 | DEFAULT_MIN_SCORE, | |
| 225 | DEFAULT_LIMIT, | |
| 226 | tokeniseTitle, | |
| 227 | jaccard, | |
| 228 | rankCandidates, | |
| 229 | findSimilar, | |
| 230 | formatSimilarityPercent, | |
| 231 | toTime, | |
| 232 | }; |