sailfork / t3code-github / .repos/ effect/ packages/ tools/ api-diff/ src/ Diff.ts

import { fingerprint, stableJson } from "./Json.ts"
import type { ApiChange, ApiDiff, ApiEntity, ApiSnapshot, ChangeClassification, DeclarationModel } from "./Model.ts"

interface Match {
  readonly base: ApiEntity
  readonly head: ApiEntity
  readonly confidence: number
  readonly authoritative: boolean
  readonly note?: string
}

interface ApiGroup {
  readonly module: string
  readonly path: ReadonlyArray<string>
  readonly entities: ReadonlyArray<ApiEntity>
}

const pathName = (entity: ApiEntity): string => entity.path.at(-1) ?? ""

const levenshtein = (left: string, right: string): number => {
  const row = Array.from({ length: right.length + 1 }, (_, index) => index)
  for (let leftIndex = 1; leftIndex <= left.length; leftIndex++) {
    let previous = row[0]!
    row[0] = leftIndex
    for (let rightIndex = 1; rightIndex <= right.length; rightIndex++) {
      const above = row[rightIndex]!
      const diagonal = previous
      previous = above
      row[rightIndex] = left[leftIndex - 1] === right[rightIndex - 1]
        ? diagonal
        : Math.min(diagonal, above, row[rightIndex - 1]!) + 1
    }
  }
  return row[right.length]!
}

const nameSimilarity = (left: string, right: string): number => {
  const length = Math.max(left.length, right.length)
  return length === 0 ? 1 : 1 - levenshtein(left.toLowerCase(), right.toLowerCase()) / length
}

const entityFeatureCache = new WeakMap<ApiEntity, ReadonlySet<string>>()

const entityFeatures = (entity: ApiEntity): ReadonlySet<string> => {
  const cached = entityFeatureCache.get(entity)
  if (cached !== undefined) {
    return cached
  }
  const features = new Set<string>()
  for (const declaration of entity.declarations) {
    features.add(`declaration:${declaration.kind}`)
    for (const member of declaration.members ?? []) {
      features.add(`member:${member.kind}:${member.name}`)
    }
  }
  entityFeatureCache.set(entity, features)
  return features
}

const setSimilarity = (left: ReadonlySet<string>, right: ReadonlySet<string>): number => {
  if (left.size === 0 && right.size === 0) {
    return 1
  }
  let shared = 0
  for (const value of left) {
    if (right.has(value)) {
      shared++
    }
  }
  return shared / (left.size + right.size - shared)
}

const documentationTokenCache = new WeakMap<ApiEntity, ReadonlySet<string>>()

const documentationTokens = (entity: ApiEntity): ReadonlySet<string> => {
  const cached = documentationTokenCache.get(entity)
  if (cached !== undefined) {
    return cached
  }
  const tokens = new Set(
    (entity.documentation.summary ?? "")
      .toLowerCase()
      .match(/[a-z][a-z0-9]+/g)
      ?.filter((token) => token.length >= 4) ?? []
  )
  documentationTokenCache.set(entity, tokens)
  return tokens
}

const groupEntities = (entities: Iterable<ApiEntity>): ReadonlyArray<ApiGroup> => {
  const groups = new Map<string, Array<ApiEntity>>()
  for (const entity of entities) {
    const key = `${entity.module}#${entity.path.join(".")}`
    const group = groups.get(key)
    if (group === undefined) {
      groups.set(key, [entity])
    } else {
      group.push(entity)
    }
  }
  return [...groups.values()].map((group) => ({
    module: group[0]!.module,
    path: group[0]!.path,
    entities: group.sort((left, right) => left.bucket.localeCompare(right.bucket))
  }))
}

const groupName = (group: ApiGroup): string => group.path.at(-1) ?? ""

const groupSimilarity = (
  base: ApiGroup,
  head: ApiGroup
): number => {
  const facets = base.entities.flatMap((baseEntity) => {
    const headEntity = head.entities.find((candidate) => candidate.bucket === baseEntity.bucket)
    return headEntity === undefined ? [] : [{ base: baseEntity, head: headEntity }]
  })
  if (facets.length === 0) {
    return 0
  }
  const sameKind = facets.filter(({ base, head }) => base.declarationKind === head.declarationKind).length /
    facets.length
  const sameFingerprint = facets.filter(({ base, head }) => base.fingerprint === head.fingerprint).length /
    facets.length
  const structure = facets.reduce(
    (total, { base, head }) => total + setSimilarity(entityFeatures(base), entityFeatures(head)),
    0
  ) / facets.length
  const documentation = facets.reduce(
    (total, { base, head }) => total + setSimilarity(documentationTokens(base), documentationTokens(head)),
    0
  ) / facets.length
  const sameCategory = facets.some(({ base, head }) =>
    base.documentation.category !== undefined &&
    base.documentation.category === head.documentation.category
  )
  const headModuleName = head.module.split("/").at(-1)?.toLowerCase()
  const mentionsHeadModule = headModuleName !== undefined &&
    facets.some(({ base }) => documentationTokens(base).has(headModuleName))
  const moduleScore = base.module === head.module ? 0.25 : 0
  const packageScore = base.entities[0]!.packageName === head.entities[0]!.packageName ? 0.05 : 0
  return Math.min(
    0.99,
    0.2 * nameSimilarity(groupName(base), groupName(head)) +
      (groupName(base) === groupName(head) ? 0.15 : 0) +
      moduleScore +
      packageScore +
      0.4 * sameFingerprint +
      0.15 * sameKind +
      0.15 * structure +
      0.025 * documentation +
      (sameCategory ? 0.05 : 0) +
      (mentionsHeadModule ? 0.075 : 0)
  )
}

const changeId = (
  classification: ChangeClassification,
  base?: ApiEntity,
  head?: ApiEntity,
  suffix = ""
): string => `change-${fingerprint([classification, base?.id ?? null, head?.id ?? null, suffix]).slice(0, 16)}`

const makeChange = (
  classification: ChangeClassification,
  match: Partial<Match>,
  delta?: unknown,
  suffix = ""
): ApiChange => ({
  id: changeId(classification, match.base, match.head, suffix),
  classification,
  confidence: match.confidence ?? 1,
  baseApiId: match.base?.id,
  headApiId: match.head?.id,
  before: match.base?.displaySignature,
  after: match.head?.displaySignature,
  delta,
  baseSource: match.base?.source,
  headSource: match.head?.source,
  reviewNotes: match.note,
  authoritative: match.authoritative ?? true
})

const declarationHash = (value: unknown): string => fingerprint(value)

const memberMap = (declarations: ReadonlyArray<DeclarationModel>): Map<string, DeclarationModel> =>
  new Map(
    declarations.flatMap((declaration) => declaration.members ?? [])
      .map((member) => [`${member.kind}:${member.name}`, member])
  )

const classifyStructure = (match: Match): ReadonlyArray<ApiChange> => {
  const base = match.base
  const head = match.head
  const changes: Array<ApiChange> = []
  if (base.bucket !== head.bucket) {
    changes.push(makeChange("bucket-changed", match, { before: base.bucket, after: head.bucket }))
  }
  if (base.declarationKind !== head.declarationKind) {
    changes.push(makeChange("declaration-kind-changed", match, {
      before: base.declarationKind,
      after: head.declarationKind
    }))
  }

  const baseDeclarations = base.declarations
  const headDeclarations = head.declarations
  const baseSignatures = baseDeclarations.filter((declaration) =>
    declaration.kind === "function" || declaration.kind === "method"
  )
  const headSignatures = headDeclarations.filter((declaration) =>
    declaration.kind === "function" || declaration.kind === "method"
  )
  if (headSignatures.length > baseSignatures.length) {
    changes.push(makeChange("overload-added", match, {
      before: baseSignatures.length,
      after: headSignatures.length
    }))
  } else if (headSignatures.length < baseSignatures.length) {
    changes.push(makeChange("overload-removed", match, {
      before: baseSignatures.length,
      after: headSignatures.length
    }))
  } else if (
    baseSignatures.length > 1 &&
    stableJson(baseSignatures.map(declarationHash).sort()) === stableJson(headSignatures.map(declarationHash).sort()) &&
    stableJson(baseSignatures.map(declarationHash)) !== stableJson(headSignatures.map(declarationHash))
  ) {
    changes.push(makeChange("overload-reordered", match))
  }

  const comparedSignatures = Math.min(baseSignatures.length, headSignatures.length)
  for (let index = 0; index < comparedSignatures; index++) {
    const before = baseSignatures[index]!
    const after = headSignatures[index]!
    const beforeParameters = before.parameters ?? []
    const afterParameters = after.parameters ?? []
    if (afterParameters.length > beforeParameters.length) {
      changes.push(makeChange("parameter-added", match, {
        overload: index,
        before: beforeParameters,
        after: afterParameters
      }, String(index)))
    } else if (afterParameters.length < beforeParameters.length) {
      changes.push(makeChange("parameter-removed", match, {
        overload: index,
        before: beforeParameters,
        after: afterParameters
      }, String(index)))
    } else if (
      stableJson(beforeParameters.map((parameter) => parameter.name).sort()) ===
        stableJson(afterParameters.map((parameter) => parameter.name).sort()) &&
      stableJson(beforeParameters.map((parameter) => parameter.name)) !==
        stableJson(afterParameters.map((parameter) => parameter.name))
    ) {
      changes.push(makeChange("parameter-reordered", match, {
        overload: index,
        before: beforeParameters,
        after: afterParameters
      }, String(index)))
    } else if (stableJson(beforeParameters) !== stableJson(afterParameters)) {
      changes.push(makeChange("parameter-changed", match, {
        overload: index,
        before: beforeParameters,
        after: afterParameters
      }, String(index)))
    }
    if (stableJson(before.returnType) !== stableJson(after.returnType)) {
      changes.push(makeChange("return-type-changed", match, {
        overload: index,
        before: before.returnType,
        after: after.returnType
      }, String(index)))
    }
    if (stableJson(before.typeParameters) !== stableJson(after.typeParameters)) {
      changes.push(makeChange("generic-parameter-changed", match, {
        overload: index,
        before: before.typeParameters,
        after: after.typeParameters
      }, String(index)))
    }
  }

  const baseMembers = memberMap(baseDeclarations)
  const headMembers = memberMap(headDeclarations)
  for (const [key, member] of baseMembers) {
    const next = headMembers.get(key)
    if (next === undefined) {
      changes.push(makeChange("member-removed", match, { member }, key))
    } else if (stableJson(member) !== stableJson(next)) {
      changes.push(makeChange("member-changed", match, { before: member, after: next }, key))
    }
  }
  for (const [key, member] of headMembers) {
    if (!baseMembers.has(key)) {
      changes.push(makeChange("member-added", match, { member }, key))
    }
  }

  const baseHeritage = baseDeclarations.flatMap((declaration) => declaration.heritage ?? [])
  const headHeritage = headDeclarations.flatMap((declaration) => declaration.heritage ?? [])
  if (stableJson(baseHeritage) !== stableJson(headHeritage)) {
    changes.push(makeChange("heritage-changed", match, { before: baseHeritage, after: headHeritage }))
  }

  const baseTypes = baseDeclarations.map((declaration) => declaration.type)
  const headTypes = headDeclarations.map((declaration) => declaration.type)
  const baseKinds = new Set(baseTypes.flatMap((type) => type?.kind === undefined ? [] : [type.kind]))
  const headKinds = new Set(headTypes.flatMap((type) => type?.kind === undefined ? [] : [type.kind]))
  if ((baseKinds.has("union") || headKinds.has("union")) && stableJson(baseTypes) !== stableJson(headTypes)) {
    changes.push(makeChange("union-member-changed", match, { before: baseTypes, after: headTypes }))
  }
  if (
    (baseKinds.has("intersection") || headKinds.has("intersection")) &&
    stableJson(baseTypes) !== stableJson(headTypes)
  ) {
    changes.push(makeChange("intersection-member-changed", match, { before: baseTypes, after: headTypes }))
  }
  if (stableJson(base.documentation) !== stableJson(head.documentation)) {
    changes.push(makeChange("documentation-changed", match, {
      before: base.documentation,
      after: head.documentation
    }))
  }
  if (base.fingerprint !== head.fingerprint && changes.length === 0) {
    changes.push(makeChange("structural-change", match, {
      before: base.declarations,
      after: head.declarations
    }))
  }
  return changes
}

const movementChange = (match: Match): ApiChange | undefined => {
  const beforeName = pathName(match.base)
  const afterName = pathName(match.head)
  if (beforeName !== afterName) {
    return makeChange("api-renamed", match)
  }
  if (match.base.module !== match.head.module || match.base.path.join(".") !== match.head.path.join(".")) {
    return makeChange("api-moved", match)
  }
  return undefined
}

const moduleChanges = (base: ApiSnapshot, head: ApiSnapshot): ReadonlyArray<ApiChange> => {
  const changes: Array<ApiChange> = []
  const basePackages = new Set(base.packages)
  const headPackages = new Set(head.packages)
  for (const packageName of basePackages) {
    if (!headPackages.has(packageName)) {
      changes.push({
        id: `change-${fingerprint(["package-removed", packageName]).slice(0, 16)}`,
        classification: "package-removed",
        confidence: 1,
        delta: { packageName },
        authoritative: true
      })
    }
  }
  for (const packageName of headPackages) {
    if (!basePackages.has(packageName)) {
      changes.push({
        id: `change-${fingerprint(["package-added", packageName]).slice(0, 16)}`,
        classification: "package-added",
        confidence: 1,
        delta: { packageName },
        authoritative: true
      })
    }
  }
  const baseModules = new Set(base.entrypoints.map((entrypoint) => entrypoint.module))
  const headModules = new Set(head.entrypoints.map((entrypoint) => entrypoint.module))
  for (const module of baseModules) {
    if (!headModules.has(module)) {
      changes.push({
        id: `change-${fingerprint(["module-removed", module]).slice(0, 16)}`,
        classification: "module-removed",
        confidence: 1,
        delta: { from: module, to: [] },
        authoritative: true
      })
    }
  }
  for (const module of headModules) {
    if (!baseModules.has(module)) {
      changes.push({
        id: `change-${fingerprint(["module-added", module]).slice(0, 16)}`,
        classification: "module-added",
        confidence: 1,
        delta: { to: [module] },
        authoritative: true
      })
    }
  }
  return changes
}

export const diffSnapshots = (base: ApiSnapshot, head: ApiSnapshot): ApiDiff => {
  const unmatchedBase = new Map(base.entities.map((entity) => [entity.id, entity]))
  const unmatchedHead = new Map(head.entities.map((entity) => [entity.id, entity]))
  const matches: Array<Match> = []
  const suggestedMatches: Array<Match> = []

  const addMatch = (
    baseEntity: ApiEntity | undefined,
    headEntity: ApiEntity | undefined,
    details: Omit<Match, "base" | "head">
  ): boolean => {
    if (
      baseEntity === undefined || headEntity === undefined ||
      !unmatchedBase.has(baseEntity.id) || !unmatchedHead.has(headEntity.id)
    ) {
      return false
    }
    unmatchedBase.delete(baseEntity.id)
    unmatchedHead.delete(headEntity.id)
    matches.push({ base: baseEntity, head: headEntity, ...details })
    return true
  }

  for (const baseEntity of unmatchedBase.values()) {
    addMatch(baseEntity, unmatchedHead.get(baseEntity.id), {
      confidence: 1,
      authoritative: true
    })
  }

  const headGroups = groupEntities(unmatchedHead.values())
  for (const baseGroup of groupEntities(unmatchedBase.values())) {
    const ranked = headGroups
      .filter((group) =>
        groupName(group) === groupName(baseGroup) ||
        group.module === baseGroup.module ||
        baseGroup.entities.some((baseEntity) =>
          group.entities.some((headEntity) =>
            baseEntity.bucket === headEntity.bucket &&
            baseEntity.fingerprint === headEntity.fingerprint
          )
        )
      )
      .map((group) => ({ group, score: groupSimilarity(baseGroup, group) }))
      .filter(({ score }) => score > 0)
      .sort((left, right) =>
        right.score - left.score ||
        left.group.module.localeCompare(right.group.module) ||
        left.group.path.join(".").localeCompare(right.group.path.join("."))
      )
    const best = ranked[0]
    const next = ranked[1]
    if (best === undefined || best.score < 0.5 || (next !== undefined && best.score - next.score < 0.05)) {
      continue
    }
    for (const baseEntity of baseGroup.entities) {
      const headEntity = best.group.entities.find((candidate) => candidate.bucket === baseEntity.bucket)
      if (headEntity !== undefined) {
        suggestedMatches.push({
          base: baseEntity,
          head: headEntity,
          confidence: Number(best.score.toFixed(3)),
          authoritative: false,
          note: "Suggested replacement for removed API; requires review"
        })
      }
    }
  }

  const changes = [...moduleChanges(base, head)]
  for (const match of matches) {
    changes.push(...classifyStructure(match))
  }
  for (const match of suggestedMatches) {
    const movement = movementChange(match)
    if (movement !== undefined) {
      changes.push(movement)
    }
  }
  for (const entity of unmatchedBase.values()) {
    changes.push(makeChange("api-removed", {
      base: entity,
      confidence: 1,
      authoritative: true
    }))
  }
  for (const entity of unmatchedHead.values()) {
    changes.push(makeChange("api-added", {
      head: entity,
      confidence: 1,
      authoritative: true
    }))
  }

  return {
    version: 1,
    base: { ref: base.ref, sha: base.sha },
    head: { ref: head.ref, sha: head.sha },
    changes: changes.sort((left, right) =>
      left.classification.localeCompare(right.classification) ||
      (left.baseApiId ?? "").localeCompare(right.baseApiId ?? "") ||
      (left.headApiId ?? "").localeCompare(right.headApiId ?? "") ||
      left.id.localeCompare(right.id)
    )
  }
}