( references: SchemaRepresentation.References )
| 91 | |
| 92 | /** @internal */ |
| 93 | export function topologicalSort( |
| 94 | references: SchemaRepresentation.References |
| 95 | ): TopologicalSort { |
| 96 | const identifiers = Object.keys(references) |
| 97 | const identifierSet = new Set(identifiers) |
| 98 | |
| 99 | function collectRefs(root: SchemaRepresentation.Representation): ReadonlySet<string> { |
| 100 | const refs = new Set<string>() |
| 101 | const visited = new WeakSet<object>() |
| 102 | const stack: Array<SchemaRepresentation.Representation> = [root] |
| 103 | |
| 104 | function pushRepresentationSchemas(representation: CheckRepresentationAnnotation | undefined): void { |
| 105 | if (representation?.schemas !== undefined) stack.push(...representation.schemas) |
| 106 | } |
| 107 | |
| 108 | function pushChecks( |
| 109 | checks: ReadonlyArray<SchemaRepresentation.Check> |
| 110 | ): void { |
| 111 | for (const check of checks) { |
| 112 | pushRepresentationSchemas(check.representation) |
| 113 | if (check._tag === "FilterGroup") pushChecks(check.checks) |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | while (stack.length > 0) { |
| 118 | const representation = stack.pop()! |
| 119 | if (visited.has(representation)) continue |
| 120 | visited.add(representation) |
| 121 | if (representation._tag === "Reference") { |
| 122 | if (identifierSet.has(representation.$ref)) refs.add(representation.$ref) |
| 123 | continue |
| 124 | } |
| 125 | |
| 126 | pushChecks(representation.checks) |
| 127 | switch (representation._tag) { |
| 128 | case "Declaration": |
| 129 | pushRepresentationSchemas(representation.representation) |
| 130 | stack.push(...representation.typeParameters) |
| 131 | break |
| 132 | case "Suspend": |
| 133 | stack.push(representation.thunk) |
| 134 | break |
| 135 | case "TemplateLiteral": |
| 136 | stack.push(...representation.parts) |
| 137 | break |
| 138 | case "Arrays": |
| 139 | for (const element of representation.elements) stack.push(element.type) |
| 140 | stack.push(...representation.rest) |
| 141 | break |
| 142 | case "Objects": |
| 143 | for (const property of representation.propertySignatures) stack.push(property.type) |
| 144 | for (const signature of representation.indexSignatures) { |
| 145 | stack.push(signature.parameter, signature.type) |
| 146 | } |
| 147 | break |
| 148 | case "Union": |
| 149 | stack.push(...representation.types) |
| 150 | break |
no test coverage detected