1import { fingerprint, stableJson } from "./Json.ts"
2import type { ApiChange, ApiDiff, ApiEntity, ApiSnapshot, ChangeClassification, DeclarationModel } from "./Model.ts"
3
4interface Match {
5 readonly base: ApiEntity
6 readonly head: ApiEntity
7 readonly confidence: number
8 readonly authoritative: boolean
9 readonly note?: string
10}
11
12interface ApiGroup {
13 readonly module: string
14 readonly path: ReadonlyArray<string>
15 readonly entities: ReadonlyArray<ApiEntity>
16}
17
18const pathName = (entity: ApiEntity): string => entity.path.at(-1) ?? ""
19
20const levenshtein = (left: string, right: string): number => {
21 const row = Array.from({ length: right.length + 1 }, (_, index) => index)
22 for (let leftIndex = 1; leftIndex <= left.length; leftIndex++) {
23 let previous = row[0]!
24 row[0] = leftIndex
25 for (let rightIndex = 1; rightIndex <= right.length; rightIndex++) {
26 const above = row[rightIndex]!
27 const diagonal = previous
28 previous = above
29 row[rightIndex] = left[leftIndex - 1] === right[rightIndex - 1]
30 ? diagonal
31 : Math.min(diagonal, above, row[rightIndex - 1]!) + 1
32 }
33 }
34 return row[right.length]!
35}
36
37const nameSimilarity = (left: string, right: string): number => {
38 const length = Math.max(left.length, right.length)
39 return length === 0 ? 1 : 1 - levenshtein(left.toLowerCase(), right.toLowerCase()) / length
40}
41
42const entityFeatureCache = new WeakMap<ApiEntity, ReadonlySet<string>>()
43
44const entityFeatures = (entity: ApiEntity): ReadonlySet<string> => {
45 const cached = entityFeatureCache.get(entity)
46 if (cached !== undefined) {
47 return cached
48 }
49 const features = new Set<string>()
50 for (const declaration of entity.declarations) {
51 features.add(`declaration:${declaration.kind}`)
52 for (const member of declaration.members ?? []) {
53 features.add(`member:${member.kind}:${member.name}`)
54 }
55 }
56 entityFeatureCache.set(entity, features)
57 return features
58}
59
60const setSimilarity = (left: ReadonlySet<string>, right: ReadonlySet<string>): number => {
61 if (left.size === 0 && right.size === 0) {
62 return 1
63 }
64 let shared = 0
65 for (const value of left) {
66 if (right.has(value)) {
67 shared++
68 }
69 }
70 return shared / (left.size + right.size - shared)
71}
72
73const documentationTokenCache = new WeakMap<ApiEntity, ReadonlySet<string>>()
74
75const documentationTokens = (entity: ApiEntity): ReadonlySet<string> => {
76 const cached = documentationTokenCache.get(entity)
77 if (cached !== undefined) {
78 return cached
79 }
80 const tokens = new Set(
81 (entity.documentation.summary ?? "")
82 .toLowerCase()
83 .match(/[a-z][a-z0-9]+/g)
84 ?.filter((token) => token.length >= 4) ?? []
85 )
86 documentationTokenCache.set(entity, tokens)
87 return tokens
88}
89
90const groupEntities = (entities: Iterable<ApiEntity>): ReadonlyArray<ApiGroup> => {
91 const groups = new Map<string, Array<ApiEntity>>()
92 for (const entity of entities) {
93 const key = `${entity.module}#${entity.path.join(".")}`
94 const group = groups.get(key)
95 if (group === undefined) {
96 groups.set(key, [entity])
97 } else {
98 group.push(entity)
99 }
100 }
101 return [...groups.values()].map((group) => ({
102 module: group[0]!.module,
103 path: group[0]!.path,
104 entities: group.sort((left, right) => left.bucket.localeCompare(right.bucket))
105 }))
106}
107
108const groupName = (group: ApiGroup): string => group.path.at(-1) ?? ""
109
110const groupSimilarity = (
111 base: ApiGroup,
112 head: ApiGroup
113): number => {
114 const facets = base.entities.flatMap((baseEntity) => {
115 const headEntity = head.entities.find((candidate) => candidate.bucket === baseEntity.bucket)
116 return headEntity === undefined ? [] : [{ base: baseEntity, head: headEntity }]
117 })
118 if (facets.length === 0) {
119 return 0
120 }
121 const sameKind = facets.filter(({ base, head }) => base.declarationKind === head.declarationKind).length /
122 facets.length
123 const sameFingerprint = facets.filter(({ base, head }) => base.fingerprint === head.fingerprint).length /
124 facets.length
125 const structure = facets.reduce(
126 (total, { base, head }) => total + setSimilarity(entityFeatures(base), entityFeatures(head)),
127 0
128 ) / facets.length
129 const documentation = facets.reduce(
130 (total, { base, head }) => total + setSimilarity(documentationTokens(base), documentationTokens(head)),
131 0
132 ) / facets.length
133 const sameCategory = facets.some(({ base, head }) =>
134 base.documentation.category !== undefined &&
135 base.documentation.category === head.documentation.category
136 )
137 const headModuleName = head.module.split("/").at(-1)?.toLowerCase()
138 const mentionsHeadModule = headModuleName !== undefined &&
139 facets.some(({ base }) => documentationTokens(base).has(headModuleName))
140 const moduleScore = base.module === head.module ? 0.25 : 0
141 const packageScore = base.entities[0]!.packageName === head.entities[0]!.packageName ? 0.05 : 0
142 return Math.min(
143 0.99,
144 0.2 * nameSimilarity(groupName(base), groupName(head)) +
145 (groupName(base) === groupName(head) ? 0.15 : 0) +
146 moduleScore +
147 packageScore +
148 0.4 * sameFingerprint +
149 0.15 * sameKind +
150 0.15 * structure +
151 0.025 * documentation +
152 (sameCategory ? 0.05 : 0) +
153 (mentionsHeadModule ? 0.075 : 0)
154 )
155}
156
157const changeId = (
158 classification: ChangeClassification,
159 base?: ApiEntity,
160 head?: ApiEntity,
161 suffix = ""
162): string => `change-${fingerprint([classification, base?.id ?? null, head?.id ?? null, suffix]).slice(0, 16)}`
163
164const makeChange = (
165 classification: ChangeClassification,
166 match: Partial<Match>,
167 delta?: unknown,
168 suffix = ""
169): ApiChange => ({
170 id: changeId(classification, match.base, match.head, suffix),
171 classification,
172 confidence: match.confidence ?? 1,
173 baseApiId: match.base?.id,
174 headApiId: match.head?.id,
175 before: match.base?.displaySignature,
176 after: match.head?.displaySignature,
177 delta,
178 baseSource: match.base?.source,
179 headSource: match.head?.source,
180 reviewNotes: match.note,
181 authoritative: match.authoritative ?? true
182})
183
184const declarationHash = (value: unknown): string => fingerprint(value)
185
186const memberMap = (declarations: ReadonlyArray<DeclarationModel>): Map<string, DeclarationModel> =>
187 new Map(
188 declarations.flatMap((declaration) => declaration.members ?? [])
189 .map((member) => [`${member.kind}:${member.name}`, member])
190 )
191
192const classifyStructure = (match: Match): ReadonlyArray<ApiChange> => {
193 const base = match.base
194 const head = match.head
195 const changes: Array<ApiChange> = []
196 if (base.bucket !== head.bucket) {
197 changes.push(makeChange("bucket-changed", match, { before: base.bucket, after: head.bucket }))
198 }
199 if (base.declarationKind !== head.declarationKind) {
200 changes.push(makeChange("declaration-kind-changed", match, {
201 before: base.declarationKind,
202 after: head.declarationKind
203 }))
204 }
205
206 const baseDeclarations = base.declarations
207 const headDeclarations = head.declarations
208 const baseSignatures = baseDeclarations.filter((declaration) =>
209 declaration.kind === "function" || declaration.kind === "method"
210 )
211 const headSignatures = headDeclarations.filter((declaration) =>
212 declaration.kind === "function" || declaration.kind === "method"
213 )
214 if (headSignatures.length > baseSignatures.length) {
215 changes.push(makeChange("overload-added", match, {
216 before: baseSignatures.length,
217 after: headSignatures.length
218 }))
219 } else if (headSignatures.length < baseSignatures.length) {
220 changes.push(makeChange("overload-removed", match, {
221 before: baseSignatures.length,
222 after: headSignatures.length
223 }))
224 } else if (
225 baseSignatures.length > 1 &&
226 stableJson(baseSignatures.map(declarationHash).sort()) === stableJson(headSignatures.map(declarationHash).sort()) &&
227 stableJson(baseSignatures.map(declarationHash)) !== stableJson(headSignatures.map(declarationHash))
228 ) {
229 changes.push(makeChange("overload-reordered", match))
230 }
231
232 const comparedSignatures = Math.min(baseSignatures.length, headSignatures.length)
233 for (let index = 0; index < comparedSignatures; index++) {
234 const before = baseSignatures[index]!
235 const after = headSignatures[index]!
236 const beforeParameters = before.parameters ?? []
237 const afterParameters = after.parameters ?? []
238 if (afterParameters.length > beforeParameters.length) {
239 changes.push(makeChange("parameter-added", match, {
240 overload: index,
241 before: beforeParameters,
242 after: afterParameters
243 }, String(index)))
244 } else if (afterParameters.length < beforeParameters.length) {
245 changes.push(makeChange("parameter-removed", match, {
246 overload: index,
247 before: beforeParameters,
248 after: afterParameters
249 }, String(index)))
250 } else if (
251 stableJson(beforeParameters.map((parameter) => parameter.name).sort()) ===
252 stableJson(afterParameters.map((parameter) => parameter.name).sort()) &&
253 stableJson(beforeParameters.map((parameter) => parameter.name)) !==
254 stableJson(afterParameters.map((parameter) => parameter.name))
255 ) {
256 changes.push(makeChange("parameter-reordered", match, {
257 overload: index,
258 before: beforeParameters,
259 after: afterParameters
260 }, String(index)))
261 } else if (stableJson(beforeParameters) !== stableJson(afterParameters)) {
262 changes.push(makeChange("parameter-changed", match, {
263 overload: index,
264 before: beforeParameters,
265 after: afterParameters
266 }, String(index)))
267 }
268 if (stableJson(before.returnType) !== stableJson(after.returnType)) {
269 changes.push(makeChange("return-type-changed", match, {
270 overload: index,
271 before: before.returnType,
272 after: after.returnType
273 }, String(index)))
274 }
275 if (stableJson(before.typeParameters) !== stableJson(after.typeParameters)) {
276 changes.push(makeChange("generic-parameter-changed", match, {
277 overload: index,
278 before: before.typeParameters,
279 after: after.typeParameters
280 }, String(index)))
281 }
282 }
283
284 const baseMembers = memberMap(baseDeclarations)
285 const headMembers = memberMap(headDeclarations)
286 for (const [key, member] of baseMembers) {
287 const next = headMembers.get(key)
288 if (next === undefined) {
289 changes.push(makeChange("member-removed", match, { member }, key))
290 } else if (stableJson(member) !== stableJson(next)) {
291 changes.push(makeChange("member-changed", match, { before: member, after: next }, key))
292 }
293 }
294 for (const [key, member] of headMembers) {
295 if (!baseMembers.has(key)) {
296 changes.push(makeChange("member-added", match, { member }, key))
297 }
298 }
299
300 const baseHeritage = baseDeclarations.flatMap((declaration) => declaration.heritage ?? [])
301 const headHeritage = headDeclarations.flatMap((declaration) => declaration.heritage ?? [])
302 if (stableJson(baseHeritage) !== stableJson(headHeritage)) {
303 changes.push(makeChange("heritage-changed", match, { before: baseHeritage, after: headHeritage }))
304 }
305
306 const baseTypes = baseDeclarations.map((declaration) => declaration.type)
307 const headTypes = headDeclarations.map((declaration) => declaration.type)
308 const baseKinds = new Set(baseTypes.flatMap((type) => type?.kind === undefined ? [] : [type.kind]))
309 const headKinds = new Set(headTypes.flatMap((type) => type?.kind === undefined ? [] : [type.kind]))
310 if ((baseKinds.has("union") || headKinds.has("union")) && stableJson(baseTypes) !== stableJson(headTypes)) {
311 changes.push(makeChange("union-member-changed", match, { before: baseTypes, after: headTypes }))
312 }
313 if (
314 (baseKinds.has("intersection") || headKinds.has("intersection")) &&
315 stableJson(baseTypes) !== stableJson(headTypes)
316 ) {
317 changes.push(makeChange("intersection-member-changed", match, { before: baseTypes, after: headTypes }))
318 }
319 if (stableJson(base.documentation) !== stableJson(head.documentation)) {
320 changes.push(makeChange("documentation-changed", match, {
321 before: base.documentation,
322 after: head.documentation
323 }))
324 }
325 if (base.fingerprint !== head.fingerprint && changes.length === 0) {
326 changes.push(makeChange("structural-change", match, {
327 before: base.declarations,
328 after: head.declarations
329 }))
330 }
331 return changes
332}
333
334const movementChange = (match: Match): ApiChange | undefined => {
335 const beforeName = pathName(match.base)
336 const afterName = pathName(match.head)
337 if (beforeName !== afterName) {
338 return makeChange("api-renamed", match)
339 }
340 if (match.base.module !== match.head.module || match.base.path.join(".") !== match.head.path.join(".")) {
341 return makeChange("api-moved", match)
342 }
343 return undefined
344}
345
346const moduleChanges = (base: ApiSnapshot, head: ApiSnapshot): ReadonlyArray<ApiChange> => {
347 const changes: Array<ApiChange> = []
348 const basePackages = new Set(base.packages)
349 const headPackages = new Set(head.packages)
350 for (const packageName of basePackages) {
351 if (!headPackages.has(packageName)) {
352 changes.push({
353 id: `change-${fingerprint(["package-removed", packageName]).slice(0, 16)}`,
354 classification: "package-removed",
355 confidence: 1,
356 delta: { packageName },
357 authoritative: true
358 })
359 }
360 }
361 for (const packageName of headPackages) {
362 if (!basePackages.has(packageName)) {
363 changes.push({
364 id: `change-${fingerprint(["package-added", packageName]).slice(0, 16)}`,
365 classification: "package-added",
366 confidence: 1,
367 delta: { packageName },
368 authoritative: true
369 })
370 }
371 }
372 const baseModules = new Set(base.entrypoints.map((entrypoint) => entrypoint.module))
373 const headModules = new Set(head.entrypoints.map((entrypoint) => entrypoint.module))
374 for (const module of baseModules) {
375 if (!headModules.has(module)) {
376 changes.push({
377 id: `change-${fingerprint(["module-removed", module]).slice(0, 16)}`,
378 classification: "module-removed",
379 confidence: 1,
380 delta: { from: module, to: [] },
381 authoritative: true
382 })
383 }
384 }
385 for (const module of headModules) {
386 if (!baseModules.has(module)) {
387 changes.push({
388 id: `change-${fingerprint(["module-added", module]).slice(0, 16)}`,
389 classification: "module-added",
390 confidence: 1,
391 delta: { to: [module] },
392 authoritative: true
393 })
394 }
395 }
396 return changes
397}
398
399export const diffSnapshots = (base: ApiSnapshot, head: ApiSnapshot): ApiDiff => {
400 const unmatchedBase = new Map(base.entities.map((entity) => [entity.id, entity]))
401 const unmatchedHead = new Map(head.entities.map((entity) => [entity.id, entity]))
402 const matches: Array<Match> = []
403 const suggestedMatches: Array<Match> = []
404
405 const addMatch = (
406 baseEntity: ApiEntity | undefined,
407 headEntity: ApiEntity | undefined,
408 details: Omit<Match, "base" | "head">
409 ): boolean => {
410 if (
411 baseEntity === undefined || headEntity === undefined ||
412 !unmatchedBase.has(baseEntity.id) || !unmatchedHead.has(headEntity.id)
413 ) {
414 return false
415 }
416 unmatchedBase.delete(baseEntity.id)
417 unmatchedHead.delete(headEntity.id)
418 matches.push({ base: baseEntity, head: headEntity, ...details })
419 return true
420 }
421
422 for (const baseEntity of unmatchedBase.values()) {
423 addMatch(baseEntity, unmatchedHead.get(baseEntity.id), {
424 confidence: 1,
425 authoritative: true
426 })
427 }
428
429 const headGroups = groupEntities(unmatchedHead.values())
430 for (const baseGroup of groupEntities(unmatchedBase.values())) {
431 const ranked = headGroups
432 .filter((group) =>
433 groupName(group) === groupName(baseGroup) ||
434 group.module === baseGroup.module ||
435 baseGroup.entities.some((baseEntity) =>
436 group.entities.some((headEntity) =>
437 baseEntity.bucket === headEntity.bucket &&
438 baseEntity.fingerprint === headEntity.fingerprint
439 )
440 )
441 )
442 .map((group) => ({ group, score: groupSimilarity(baseGroup, group) }))
443 .filter(({ score }) => score > 0)
444 .sort((left, right) =>
445 right.score - left.score ||
446 left.group.module.localeCompare(right.group.module) ||
447 left.group.path.join(".").localeCompare(right.group.path.join("."))
448 )
449 const best = ranked[0]
450 const next = ranked[1]
451 if (best === undefined || best.score < 0.5 || (next !== undefined && best.score - next.score < 0.05)) {
452 continue
453 }
454 for (const baseEntity of baseGroup.entities) {
455 const headEntity = best.group.entities.find((candidate) => candidate.bucket === baseEntity.bucket)
456 if (headEntity !== undefined) {
457 suggestedMatches.push({
458 base: baseEntity,
459 head: headEntity,
460 confidence: Number(best.score.toFixed(3)),
461 authoritative: false,
462 note: "Suggested replacement for removed API; requires review"
463 })
464 }
465 }
466 }
467
468 const changes = [...moduleChanges(base, head)]
469 for (const match of matches) {
470 changes.push(...classifyStructure(match))
471 }
472 for (const match of suggestedMatches) {
473 const movement = movementChange(match)
474 if (movement !== undefined) {
475 changes.push(movement)
476 }
477 }
478 for (const entity of unmatchedBase.values()) {
479 changes.push(makeChange("api-removed", {
480 base: entity,
481 confidence: 1,
482 authoritative: true
483 }))
484 }
485 for (const entity of unmatchedHead.values()) {
486 changes.push(makeChange("api-added", {
487 head: entity,
488 confidence: 1,
489 authoritative: true
490 }))
491 }
492
493 return {
494 version: 1,
495 base: { ref: base.ref, sha: base.sha },
496 head: { ref: head.ref, sha: head.sha },
497 changes: changes.sort((left, right) =>
498 left.classification.localeCompare(right.classification) ||
499 (left.baseApiId ?? "").localeCompare(right.baseApiId ?? "") ||
500 (left.headApiId ?? "").localeCompare(right.headApiId ?? "") ||
501 left.id.localeCompare(right.id)
502 )
503 }
504}