diff options
| author | Lily <[email protected]> | 2026-07-28 16:12:21 +1000 |
|---|---|---|
| committer | GitHub <[email protected]> | 2026-07-28 16:12:21 +1000 |
| commit | c11e17573334dfb487a8e1cc25fa84fa9e138f5c (patch) | |
| tree | e91dbd19b524f9432da6bcb86b1fc193e0d02e26 /src/commands/tsort.js | |
| parent | 6a2f098e72e71437154ec00506e8e736aa8e1026 (diff) | |
| download | bnu-c11e17573334dfb487a8e1cc25fa84fa9e138f5c.tar.gz bnu-c11e17573334dfb487a8e1cc25fa84fa9e138f5c.zip | |
Refactor coreutils into single-call command modules (#1)
* Refactor to single call
Diffstat (limited to 'src/commands/tsort.js')
| -rw-r--r-- | src/commands/tsort.js | 132 |
1 files changed, 132 insertions, 0 deletions
diff --git a/src/commands/tsort.js b/src/commands/tsort.js new file mode 100644 index 0000000..3c949ba --- /dev/null +++ b/src/commands/tsort.js @@ -0,0 +1,132 @@ +#!/usr/bin/env bun + +import { localeQuotedEscapedDiagnostic, nodeErrorMessage, normalizeHelpVersionOnlyLongOption, normalizeHelpVersionOnlyLongOptions, parseOptions, readAll, systemErrorMessage, textInputDiagnosticName } from "../shared/common.js"; +import { UsageError, stderr, stdout } from "../shared/diagnostics.js"; +import { defineCommand, runAsMain } from "../shared/command.js"; + +export function tsortMetaOption(args) { + for (const arg of args) { + if (arg === "--") return null; + if (arg.startsWith("--")) { + const option = normalizeHelpVersionOnlyLongOption(arg); + if (option.includes("=") || !["--help", "--version"].includes(option)) return null; + return option; + } + if (!arg.startsWith("-") || arg === "-") continue; + for (let j = 1; j < arg.length; j++) if (arg[j] !== "w") return null; + } + return null; +} + +export async function tsort(args) { + const { operands } = parseOptions(normalizeHelpVersionOnlyLongOptions(args), { short: { w: false }, long: { help: false, version: false } }); + if (operands.length > 1) throw new UsageError(`extra operand ${localeQuotedEscapedDiagnostic(operands[1])}`, true); + const file = operands[0] ?? "-"; + let input; + try { + input = await readAll(file); + } catch (error) { + const message = error?.code === "EISDIR" ? `${textInputDiagnosticName(file)}: read error: ${systemErrorMessage(error)}` : file === "-" ? nodeErrorMessage(error) : `${textInputDiagnosticName(file)}: ${systemErrorMessage(error)}`; + stderr(`tsort: ${message}\n`); + return 1; + } + const text = new TextDecoder().decode(input); + const tokens = text.trim().split(/\s+/).filter(Boolean); + if (tokens.length % 2) throw new UsageError(`${file}: input contains an odd number of tokens`); + const nodes = new Map(); + const getNode = (name) => { + if (!nodes.has(name)) nodes.set(name, { name, count: 0, printed: false, qlink: null, succ: [] }); + return nodes.get(name); + }; + for (let i = 0; i < tokens.length; i += 2) { + const from = getNode(tokens[i]); + const to = getNode(tokens[i + 1]); + if (from !== to) { + to.count++; + from.succ.unshift(to); + } + } + const sortedNodes = [...nodes.values()].sort((a, b) => a.name.localeCompare(b.name)); + let remaining = sortedNodes.length; + let ok = true; + while (remaining > 0) { + const queue = tsortScanZeros(sortedNodes); + for (let head = queue.head, tail = queue.tail; head;) { + const node = head; + stdout(`${node.name}\n`); + node.printed = true; + remaining--; + for (const next of node.succ) { + next.count--; + if (next.count === 0) { + tail.qlink = next; + tail = next; + } + } + head = node.qlink; + node.qlink = null; + } + if (remaining > 0) { + stderr(`tsort: ${file}: input contains a loop:\n`); + ok = false; + tsortBreakLoop(sortedNodes); + } + } + return ok ? 0 : 1; +} + +export function tsortScanZeros(nodes) { + let head = null; + let tail = null; + for (const node of nodes) { + if (node.count === 0 && !node.printed) { + if (!head) head = node; + else tail.qlink = node; + tail = node; + node.qlink = null; + } + } + return { head, tail }; +} + +export function tsortBreakLoop(nodes) { + let loop = null; + do { + for (const node of nodes) { + if (node.count <= 0 || node.printed) continue; + if (!loop) { + loop = node; + continue; + } + const idx = node.succ.findIndex((next) => next === loop); + if (idx === -1) continue; + if (!node.qlink) { + node.qlink = loop; + loop = node; + continue; + } + while (loop) { + stderr(`tsort: ${loop.name}\n`); + if (loop === node) { + node.succ[idx].count--; + node.succ.splice(idx, 1); + break; + } + const next = loop.qlink; + loop.qlink = null; + loop = next; + } + while (loop) { + const next = loop.qlink; + loop.qlink = null; + loop = next; + } + return; + } + } while (loop); +} + +const singleCall = defineCommand("tsort", tsort, tsortMetaOption); +export default singleCall; + +if (import.meta.main) await runAsMain(singleCall); |
