topologicalSortRegistryItems() — ui Function Reference

Architecture documentation for the topologicalSortRegistryItems() function in resolver.ts from the ui codebase.

Function typescript FrameworkTooling SchemaValidation calls 2 called by 1

Entity Profile

FrameworkTooling→ SchemaValidation→ topologicalSortRegistryItems() — ui Function Reference

Dependency Diagram

graph TD
  b52dca21_c127_9ab7_c3a4_02bb7ad550be["topologicalSortRegistryItems()"]
  c819bacb_5122_731b_64d6_d23131b1f806["resolver.ts"]
  b52dca21_c127_9ab7_c3a4_02bb7ad550be -->|defined in| c819bacb_5122_731b_64d6_d23131b1f806
  e645527e_af9e_1457_dc85_48f0a4c79a9a["resolveRegistryTree()"]
  e645527e_af9e_1457_dc85_48f0a4c79a9a -->|calls| b52dca21_c127_9ab7_c3a4_02bb7ad550be
  c370e00a_83e4_54e2_7925_81dcdb37bc1d["computeItemHash()"]
  b52dca21_c127_9ab7_c3a4_02bb7ad550be -->|calls| c370e00a_83e4_54e2_7925_81dcdb37bc1d
  fdbe99c6_359b_8328_7270_49407cee1afa["extractItemIdentifierFromDependency()"]
  b52dca21_c127_9ab7_c3a4_02bb7ad550be -->|calls| fdbe99c6_359b_8328_7270_49407cee1afa
  style b52dca21_c127_9ab7_c3a4_02bb7ad550be fill:#6366f1,stroke:#818cf8,color:#fff

Relationship Graph

Source Code

packages/shadcn/src/registry/resolver.ts lines 622–743

function topologicalSortRegistryItems(
  items: z.infer<typeof registryItemWithSourceSchema>[],
  sourceMap: Map<z.infer<typeof registryItemWithSourceSchema>, string>
) {
  const itemMap = new Map<
    string,
    z.infer<typeof registryItemWithSourceSchema>
  >()
  const hashToItem = new Map<
    string,
    z.infer<typeof registryItemWithSourceSchema>
  >()
  const inDegree = new Map<string, number>()
  const adjacencyList = new Map<string, string[]>()

  items.forEach((item) => {
    const source = sourceMap.get(item) || item.name
    const hash = computeItemHash(item, source)

    itemMap.set(hash, item)
    hashToItem.set(hash, item)
    inDegree.set(hash, 0)
    adjacencyList.set(hash, [])
  })

  // Build a map of dependency to possible items.
  const depToHashes = new Map<string, string[]>()
  items.forEach((item) => {
    const source = sourceMap.get(item) || item.name
    const hash = computeItemHash(item, source)

    if (!depToHashes.has(item.name)) {
      depToHashes.set(item.name, [])
    }
    depToHashes.get(item.name)!.push(hash)

    if (source !== item.name) {
      if (!depToHashes.has(source)) {
        depToHashes.set(source, [])
      }
      depToHashes.get(source)!.push(hash)
    }
  })

  items.forEach((item) => {
    const itemSource = sourceMap.get(item) || item.name
    const itemHash = computeItemHash(item, itemSource)

    if (item.registryDependencies) {
      item.registryDependencies.forEach((dep) => {
        let depHash: string | undefined

        const exactMatches = depToHashes.get(dep) || []
        if (exactMatches.length === 1) {
          depHash = exactMatches[0]
        } else if (exactMatches.length > 1) {
          // Multiple matches - try to disambiguate.
          // For now, just use the first one and warn.
          depHash = exactMatches[0]
        } else {
          const { name } = extractItemIdentifierFromDependency(dep)
          const nameMatches = depToHashes.get(name) || []
          if (nameMatches.length > 0) {
            depHash = nameMatches[0]
          }
        }

        if (depHash && itemMap.has(depHash)) {
          adjacencyList.get(depHash)!.push(itemHash)
          inDegree.set(itemHash, inDegree.get(itemHash)! + 1)
        }
      })
    }
  })

  // Implements Kahn's algorithm.
  const queue: string[] = []
  const sorted: z.infer<typeof registryItemWithSourceSchema>[] = []

  inDegree.forEach((degree, hash) => {
    if (degree === 0) {