jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2022, Eli Youngs <eli.m.youngs@gmail.com>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/CharacterTypes.h>
8#include <AK/HashMap.h>
9#include <LibCore/ArgsParser.h>
10#include <LibCore/File.h>
11#include <LibCore/System.h>
12#include <LibMain/Main.h>
13
14enum NodeStatus {
15 NotSeen,
16 Seen,
17 Prioritized,
18};
19
20struct Node {
21 StringView name;
22 OrderedHashTable<StringView> ancestors;
23 NodeStatus status;
24};
25
26using NodeMap = OrderedHashMap<StringView, Node>;
27using NodeStack = Vector<Node&>;
28
29static void handle_cycle(NodeStack& stack, Node& duplicated_node, bool quiet)
30{
31 // Report on a cycle by moving down the stack of dependencies, logging every node
32 // between the implicit top of the stack (represented by duplicate_node) and that
33 // node's first appearance.
34
35 if (!quiet)
36 warnln("tsort: The following nodes form a cycle");
37
38 for (auto it = stack.rbegin(); it != stack.rend(); ++it) {
39 auto node = *it;
40 node.status = NodeStatus::NotSeen;
41 if (!quiet)
42 warnln("tsort: {}", node.name);
43 if (node.name == duplicated_node.name)
44 return;
45 }
46}
47
48static void prioritize_nodes(Node& start, NodeMap& node_map, NodeStack& stack, bool quiet)
49{
50 // Prioritize (topologically sort) a subset of a directed graph using a depth first
51 // search. The "deepest" nodes are the earliest ancestors of all other nodes and
52 // have no dependencies. To avoid a stack overflow when processing deep dependency
53 // chains, this function does not call itself recursively. Instead, the recursive
54 // algorithm is implemented on a provided stack.
55
56 assert(stack.is_empty());
57 stack.append(start);
58
59 while (!stack.is_empty()) {
60 auto& node = stack.last();
61
62 // If a node has already been prioritized, it can be ignored.
63 if (node.status == NodeStatus::Prioritized) {
64 stack.take_last();
65 continue;
66 }
67
68 // Keep track of which nodes have been seen to detect cycles.
69 node.status = NodeStatus::Seen;
70
71 if (node.ancestors.is_empty()) {
72 // If a node has no remaining ancestors (dependencies), it either never had
73 // ancestors, or its ancestors have already been prioritized. In either case,
74 // this is now the deepest un-prioritized node, which makes it the next
75 // highest priority.
76 node.status = NodeStatus::Prioritized;
77 outln("{}", stack.take_last().name);
78 } else {
79 auto next_ancestor_name = node.ancestors.take_last();
80 auto& next_ancestor = node_map.get(next_ancestor_name).release_value();
81 if (next_ancestor.status == NodeStatus::Seen)
82 // If the same node is seen multiple times, this represents a cycle in
83 // the graph. To avoid an infinite loop, the duplicate node is not added
84 // to the stack a second time. Instead, the edge is deliberately ignored,
85 // and the topological sort proceeds as though the cycle did not exist.
86 handle_cycle(stack, next_ancestor, quiet);
87 else
88 // Recursively prioritize all ancestors.
89 stack.append(next_ancestor);
90 }
91 }
92}
93
94ErrorOr<int> serenity_main(Main::Arguments arguments)
95{
96 TRY(Core::System::pledge("stdio rpath"));
97
98 StringView path;
99 bool quiet;
100
101 Core::ArgsParser args_parser;
102 args_parser.add_positional_argument(path, "Path to file", "path", Core::ArgsParser::Required::No);
103 args_parser.add_option(quiet, "Suppress warnings about cycles", "quiet", 'q');
104 args_parser.parse(arguments);
105
106 auto file = TRY(Core::File::open_file_or_standard_stream(path, Core::File::OpenMode::Read));
107 auto input_bytes = TRY(file->read_until_eof());
108 auto inputs = StringView(input_bytes).split_view_if(is_ascii_space);
109
110 if (inputs.is_empty())
111 return 0;
112
113 if (inputs.size() % 2 != 0) {
114 warnln("tsort: the number of inputs must be even");
115 return 1;
116 }
117
118 NodeMap node_map;
119
120 // Each pair of inputs (e.g. "a b") represents an edge of a directed acyclic graph.
121 // If the same input is repeated (e.g. "a a"), this defines a single node with no
122 // connection to any other nodes. Otherwise, the first input is interpreted as an
123 // ancestor of the second.
124 for (size_t i = 0; i < inputs.size(); i += 2) {
125 auto ancestor_name = inputs[i];
126 auto descendent_name = inputs[i + 1];
127
128 TRY(node_map.try_ensure(descendent_name, [&]() { return Node { descendent_name, OrderedHashTable<StringView> {}, NodeStatus::NotSeen }; }));
129 if (descendent_name != ancestor_name) {
130 TRY(node_map.try_ensure(ancestor_name, [&]() { return Node { ancestor_name, OrderedHashTable<StringView> {}, NodeStatus::NotSeen }; }));
131 // Creating the ancestor_node might cause the node_map to expand, re-hash
132 // its contents, and invalidate existing references to its values. To handle
133 // this, we always get a new reference to the descendent_node.
134 auto& descendent_node = node_map.get(descendent_name).release_value();
135 TRY(descendent_node.ancestors.try_set(ancestor_name));
136 }
137 }
138
139 // Each node must be checked individually, since any node could be disconnected from
140 // the rest of the graph.
141 NodeStack stack;
142 for (auto& entry : node_map) {
143 auto& node_to_prioritize = entry.value;
144 if (node_to_prioritize.status == NodeStatus::NotSeen)
145 prioritize_nodes(node_to_prioritize, node_map, stack, quiet);
146 }
147
148 return 0;
149}