diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php index a1dfd0eb..f2f4fa75 100644 --- a/src/__phutil_library_map__.php +++ b/src/__phutil_library_map__.php @@ -1,184 +1,189 @@ array( + 'AbstractDirectedGraph' => 'utils/abstractgraph', + 'AbstractDirectedGraphTestCase' => 'utils/abstractgraph/__tests__', 'CommandException' => 'future/exec', 'ConduitClient' => 'conduit/client', 'ConduitClientException' => 'conduit/client', 'ConduitFuture' => 'conduit/client', 'ExecFuture' => 'future/exec', 'FileFinder' => 'filesystem/filefinder', 'FileList' => 'filesystem/filelist', 'Filesystem' => 'filesystem', 'FilesystemException' => 'filesystem', 'Future' => 'future', 'FutureIterator' => 'future', 'FutureProxy' => 'future/proxy', 'HTTPFuture' => 'future/http', 'HTTPSFuture' => 'future/https', 'ImmediateFuture' => 'future/immediate', 'LinesOfALargeFile' => 'filesystem/linesofalargefile', 'MFilterTestHelper' => 'utils/__tests__', 'PhutilConsoleFormatter' => 'console', 'PhutilDaemon' => 'daemon/base', 'PhutilDaemonOverseer' => 'daemon/overseer', 'PhutilDefaultSyntaxHighlighter' => 'markup/syntax/highlighter/default', 'PhutilDefaultSyntaxHighlighterEngine' => 'markup/syntax/engine/default', 'PhutilDefaultSyntaxHighlighterEnginePygmentsFuture' => 'markup/syntax/highlighter/pygments/future', 'PhutilDefaultSyntaxHighlighterEngineTestCase' => 'markup/syntax/engine/default/__tests__', 'PhutilDivinerSyntaxHighlighter' => 'markup/syntax/highlighter/diviner', 'PhutilDocblockParser' => 'parser/docblock', 'PhutilDocblockParserTestCase' => 'parser/docblock/__tests__', 'PhutilErrorHandler' => 'error', 'PhutilExcessiveServiceCallsDaemon' => 'daemon/torture/excessiveservicecalls', 'PhutilFatalDaemon' => 'daemon/torture/fatal', 'PhutilHangForeverDaemon' => 'daemon/torture/hangforever', 'PhutilInteractiveEditor' => 'console/editor', 'PhutilJSON' => 'parser/json', 'PhutilMarkupEngine' => 'markup/engine', 'PhutilMissingSymbolException' => 'symbols/exception/missing', 'PhutilNiceDaemon' => 'daemon/torture/nice', 'PhutilProcessGroupDaemon' => 'daemon/torture/processgroup', 'PhutilPygmentsSyntaxHighlighter' => 'markup/syntax/highlighter/pygments', 'PhutilReadableSerializer' => 'readableserializer', 'PhutilRemarkupBlockStorage' => 'markup/engine/remarkup/blockstorage', 'PhutilRemarkupEngine' => 'markup/engine/remarkup', 'PhutilRemarkupEngineBlockRule' => 'markup/engine/remarkup/blockrule/base', 'PhutilRemarkupEngineRemarkupCodeBlockRule' => 'markup/engine/remarkup/blockrule/remarkupcode', 'PhutilRemarkupEngineRemarkupDefaultBlockRule' => 'markup/engine/remarkup/blockrule/remarkupdefault', 'PhutilRemarkupEngineRemarkupHeaderBlockRule' => 'markup/engine/remarkup/blockrule/remarkupheader', 'PhutilRemarkupEngineRemarkupInlineBlockRule' => 'markup/engine/remarkup/blockrule/remarkupinline', 'PhutilRemarkupEngineRemarkupListBlockRule' => 'markup/engine/remarkup/blockrule/remarkuplist', 'PhutilRemarkupEngineRemarkupNoteBlockRule' => 'markup/engine/remarkup/blockrule/remarkupnote', 'PhutilRemarkupEngineRemarkupQuotesBlockRule' => 'markup/engine/remarkup/blockrule/remarkupquotes', 'PhutilRemarkupEngineTestCase' => 'markup/engine/remarkup/__tests__', 'PhutilRemarkupRule' => 'markup/engine/remarkup/markuprule/base', 'PhutilRemarkupRuleBold' => 'markup/engine/remarkup/markuprule/bold', 'PhutilRemarkupRuleEscapeHTML' => 'markup/engine/remarkup/markuprule/escapehtml', 'PhutilRemarkupRuleEscapeRemarkup' => 'markup/engine/remarkup/markuprule/escaperemarkup', 'PhutilRemarkupRuleHyperlink' => 'markup/engine/remarkup/markuprule/hyperlink', 'PhutilRemarkupRuleItalic' => 'markup/engine/remarkup/markuprule/italics', 'PhutilRemarkupRuleLinebreaks' => 'markup/engine/remarkup/markuprule/linebreaks', 'PhutilRemarkupRuleMonospace' => 'markup/engine/remarkup/markuprule/monospace', 'PhutilSaturateStdoutDaemon' => 'daemon/torture/saturatestdout', 'PhutilServiceProfiler' => 'serviceprofiler', 'PhutilSymbolLoader' => 'symbols', 'PhutilSyntaxHighlighter' => 'markup/syntax/highlighter/base', 'PhutilSyntaxHighlighterEngine' => 'markup/syntax/engine/base', 'PhutilTortureTestDaemon' => 'daemon/torture/base', 'PhutilURI' => 'parser/uri', 'PhutilUTF8TestCase' => 'utils/__tests__', 'PhutilUtilsTestCase' => 'utils/__tests__', 'PhutilXHPASTSyntaxHighlighter' => 'markup/syntax/highlighter/xhpast', 'TempFile' => 'filesystem/tempfile', + 'TestAbstractDirectedGraph' => 'utils/abstractgraph/__tests__', 'XHPASTNode' => 'parser/xhpast/api/node', 'XHPASTNodeList' => 'parser/xhpast/api/list', 'XHPASTSyntaxErrorException' => 'parser/xhpast/api/exception', 'XHPASTToken' => 'parser/xhpast/api/token', 'XHPASTTree' => 'parser/xhpast/api/tree', 'XHPASTTreeTestCase' => 'parser/xhpast/api/tree/__tests__', ), 'function' => array( 'Futures' => 'future', 'array_mergev' => 'utils', 'array_select_keys' => 'utils', 'coalesce' => 'utils', 'csprintf' => 'xsprintf/csprintf', 'exec_manual' => 'future/exec', 'execx' => 'future/exec', 'head' => 'utils', 'id' => 'utils', 'idx' => 'utils', 'ifilter' => 'utils', 'igroup' => 'utils', 'ipull' => 'utils', 'isort' => 'utils', 'jsprintf' => 'xsprintf/jsprintf', 'mfilter' => 'utils', 'mgroup' => 'utils', 'mpull' => 'utils', 'msort' => 'utils', 'newv' => 'utils', 'nonempty' => 'utils', 'phlog' => 'error', 'phutil_console_confirm' => 'console', 'phutil_console_format' => 'console', 'phutil_console_prompt' => 'console', 'phutil_console_wrap' => 'console', 'phutil_deprecated' => 'moduleutils', 'phutil_error_listener_example' => 'error', 'phutil_escape_html' => 'markup', 'phutil_escape_uri' => 'markup', 'phutil_get_library_name_for_root' => 'moduleutils', 'phutil_get_library_root' => 'moduleutils', 'phutil_get_library_root_for_path' => 'moduleutils', 'phutil_is_utf8' => 'utils', 'phutil_passthru' => 'future/exec', 'phutil_render_tag' => 'markup', 'phutil_utf8_shorten' => 'utils', 'phutil_utf8_strlen' => 'utils', 'phutil_utf8ize' => 'utils', 'phutil_utf8v' => 'utils', 'vcsprintf' => 'xsprintf/csprintf', 'vjsprintf' => 'xsprintf/jsprintf', 'xhp_parser_node_constants' => 'parser/xhpast/constants', 'xhpast_get_binary_path' => 'parser/xhpast/bin', 'xhpast_get_build_instructions' => 'parser/xhpast/bin', 'xhpast_get_parser_future' => 'parser/xhpast/bin', 'xhpast_is_available' => 'parser/xhpast/bin', 'xhpast_parser_token_constants' => 'parser/xhpast/constants', 'xsprintf' => 'xsprintf', 'xsprintf_callback_example' => 'xsprintf', 'xsprintf_command' => 'xsprintf/csprintf', 'xsprintf_javascript' => 'xsprintf/jsprintf', ), 'requires_class' => array( + 'AbstractDirectedGraphTestCase' => 'ArcanistPhutilTestCase', 'ConduitFuture' => 'FutureProxy', 'ExecFuture' => 'Future', 'FutureProxy' => 'Future', 'HTTPFuture' => 'Future', 'HTTPSFuture' => 'Future', 'ImmediateFuture' => 'Future', 'PhutilDefaultSyntaxHighlighterEngine' => 'PhutilSyntaxHighlighterEngine', 'PhutilDefaultSyntaxHighlighterEnginePygmentsFuture' => 'FutureProxy', 'PhutilDefaultSyntaxHighlighterEngineTestCase' => 'ArcanistPhutilTestCase', 'PhutilDocblockParserTestCase' => 'ArcanistPhutilTestCase', 'PhutilExcessiveServiceCallsDaemon' => 'PhutilTortureTestDaemon', 'PhutilFatalDaemon' => 'PhutilTortureTestDaemon', 'PhutilHangForeverDaemon' => 'PhutilTortureTestDaemon', 'PhutilNiceDaemon' => 'PhutilTortureTestDaemon', 'PhutilProcessGroupDaemon' => 'PhutilTortureTestDaemon', 'PhutilRemarkupEngine' => 'PhutilMarkupEngine', 'PhutilRemarkupEngineRemarkupCodeBlockRule' => 'PhutilRemarkupEngineBlockRule', 'PhutilRemarkupEngineRemarkupDefaultBlockRule' => 'PhutilRemarkupEngineBlockRule', 'PhutilRemarkupEngineRemarkupHeaderBlockRule' => 'PhutilRemarkupEngineBlockRule', 'PhutilRemarkupEngineRemarkupInlineBlockRule' => 'PhutilRemarkupEngineBlockRule', 'PhutilRemarkupEngineRemarkupListBlockRule' => 'PhutilRemarkupEngineBlockRule', 'PhutilRemarkupEngineRemarkupNoteBlockRule' => 'PhutilRemarkupEngineBlockRule', 'PhutilRemarkupEngineRemarkupQuotesBlockRule' => 'PhutilRemarkupEngineBlockRule', 'PhutilRemarkupEngineTestCase' => 'ArcanistPhutilTestCase', 'PhutilRemarkupRuleBold' => 'PhutilRemarkupRule', 'PhutilRemarkupRuleEscapeHTML' => 'PhutilRemarkupRule', 'PhutilRemarkupRuleEscapeRemarkup' => 'PhutilRemarkupRule', 'PhutilRemarkupRuleHyperlink' => 'PhutilRemarkupRule', 'PhutilRemarkupRuleItalic' => 'PhutilRemarkupRule', 'PhutilRemarkupRuleLinebreaks' => 'PhutilRemarkupRule', 'PhutilRemarkupRuleMonospace' => 'PhutilRemarkupRule', 'PhutilSaturateStdoutDaemon' => 'PhutilTortureTestDaemon', 'PhutilTortureTestDaemon' => 'PhutilDaemon', 'PhutilUTF8TestCase' => 'ArcanistPhutilTestCase', 'PhutilUtilsTestCase' => 'ArcanistPhutilTestCase', + 'TestAbstractDirectedGraph' => 'AbstractDirectedGraph', 'XHPASTTreeTestCase' => 'ArcanistPhutilTestCase', ), 'requires_interface' => array( ), )); diff --git a/src/utils/abstractgraph/AbstractDirectedGraph.php b/src/utils/abstractgraph/AbstractDirectedGraph.php new file mode 100644 index 00000000..70308e11 --- /dev/null +++ b/src/utils/abstractgraph/AbstractDirectedGraph.php @@ -0,0 +1,218 @@ +addNodes( + * array( + * $object->getPHID() => $object->getChildPHIDs(), + * )); + * $detector->loadGraph(); + * + * Now you can query the graph, e.g. by detecting cycles: + * + * $cycle = $detector->detectCycles($object->getPHID()); + * + * If ##$cycle## is empty, no graph cycle is reachable from the node. If it + * is nonempty, it contains a list of nodes which form a graph cycle. + * + * NOTE: Nodes must be represented with scalars. + * + * @task build Graph Construction + * @task cycle Cycle Detection + * @task explore Graph Exploration + */ +abstract class AbstractDirectedGraph { + + + private $knownNodes = array(); + private $graphLoaded = false; + + +/* -( Graph Construction )------------------------------------------------- */ + + + /** + * Load the edges for a list of nodes. You must override this method. You + * will be passed a list of nodes, and should return a dictionary mapping + * each node to the list of nodes that can be reached by following its the + * edges which originate at it: for example, the child nodes of an object + * which has a parent-child relationship to other objects. + * + * The intent of this method is to allow you to issue a single query per + * graph level for graphs which are stored as edge tables in the database. + * Generally, you will load all the objects which correspond to the list of + * nodes, and then return a map from each of their IDs to all their children. + * + * NOTE: You must return an entry for every node you are passed, even if it + * is invalid or can not be loaded. Either return an empty array (if this is + * acceptable for your application) or throw an exception if you can't satisfy + * this requirement. + * + * @param list A list of nodes. + * @return dict A map of nodes to the nodes reachable along their edges. + * There must be an entry for each node you were provided. + * @task build + */ + abstract protected function loadEdges(array $nodes); + + + /** + * Seed the graph with known nodes. Often, you will provide the candidate + * edges that a user is trying to create here, or the initial set of edges + * you know about. + * + * @param dict A map of nodes to the nodes reachable along their edges. + * @return this + * @task build + */ + final public function addNodes(array $nodes) { + if ($this->graphLoaded) { + throw new Exception( + "Call addNodes() before calling loadGraph(). You can not add more ". + "nodes once you have loaded the graph."); + } + + $this->knownNodes += $nodes; + return $this; + } + + + /** + * Load the graph, building it out so operations can be performed on it. This + * constructs the graph level-by-level, calling @{method:loadEdges} to + * expand the graph at each stage until it is complete. + * + * @return this + * @task build + */ + final public function loadGraph() { + + $new_nodes = $this->knownNodes; + while (true) { + $load = array(); + foreach ($new_nodes as $node => $edges) { + foreach ($edges as $edge) { + if (!isset($this->knownNodes[$edge])) { + $load[$edge] = true; + } + } + } + + if (empty($load)) { + break; + } + + $load = array_keys($load); + + $new_nodes = $this->loadEdges($load); + foreach ($load as $node) { + if (!isset($new_nodes[$node]) || !is_array($new_nodes[$node])) { + throw new Exception( + "loadEdges() must return an edge list array for each provided ". + "node, or the cycle detection algorithm may not terminate."); + } + } + + $this->addNodes($new_nodes); + } + + $this->graphLoaded = true; + return $this; + } + + +/* -( Cycle Detection )---------------------------------------------------- */ + + + /** + * Detect if there are any cycles reachable from a given node. + * + * If cycles are reachable, it returns a list of nodes which create a cycle. + * Note that this list may include nodes which aren't actually part of the + * cycle, but lie on the graph between the specified node and the cycle. + * For example, it might return something like this (when passed "A"): + * + * A, B, C, D, E, C + * + * This means you can walk from A to B to C to D to E and then back to C, + * which forms a cycle. A and B are included even though they are not part + * of the cycle. When presenting information about graph cycles to users, + * including these nodes is generally useful. This also shouldn't ever happen + * if you've vetted prior edges before writing them, because it means there + * is a preexisting cycle in the graph. + * + * NOTE: This only detects cycles reachable from a node. It does not detect + * cycles in the entire graph. + * + * @param scalar The node to walk from, looking for graph cycles. + * @return list|null Returns null if no cycles are reachable from the node, + * or a list of nodes that form a cycle. + * @task cycle + */ + final public function detectCycles($node) { + if (!$this->graphLoaded) { + throw new Exception( + "Call loadGraph() to build the graph out before calling ". + "detectCycles()."); + } + if (!isset($this->knownNodes[$node])) { + throw new Exception( + "The node '{$node}' is not known. Call addNodes() to seed the graph ". + "with nodes."); + } + + $visited = array(); + return $this->performCycleDetection($node, $visited); + } + + + /** + * Internal cycle detection implementation. Recursively walks the graph, + * keeping track of where it's been, and returns the first cycle it finds. + * + * @param scalar The node to walk from. + * @param list Previously visited nodes. + * @return null|list Null if no cycles are found, or a list of nodes + * which cycle. + * @task cycle + */ + final private function performCycleDetection($node, array $visited) { + $visited[$node] = true; + foreach ($this->knownNodes[$node] as $edge) { + if (isset($visited[$edge])) { + $result = array_keys($visited); + $result[] = $edge; + return $result; + } + $result = $this->performCycleDetection($edge, $visited); + if ($result) { + return $result; + } + } + return null; + } + +} diff --git a/src/utils/abstractgraph/__init__.php b/src/utils/abstractgraph/__init__.php new file mode 100644 index 00000000..1322330d --- /dev/null +++ b/src/utils/abstractgraph/__init__.php @@ -0,0 +1,10 @@ + array(), + ); + + $cycle = $this->findGraphCycle($graph); + $this->assertEqual(null, $cycle, 'Trivial Graph'); + } + + public function testNoncyclicGraph() { + $graph = array( + 'A' => array('B', 'C'), + 'B' => array('D'), + 'C' => array(), + 'D' => array(), + ); + + $cycle = $this->findGraphCycle($graph); + $this->assertEqual(null, $cycle, 'Noncyclic Graph'); + } + + public function testTrivialCyclicGraph() { + $graph = array( + 'A' => array('A'), + ); + + $cycle = $this->findGraphCycle($graph); + $this->assertEqual(array('A', 'A'), $cycle, 'Trivial Cycle'); + } + + public function testCyclicGraph() { + $graph = array( + 'A' => array('B', 'C'), + 'B' => array('D'), + 'C' => array('E', 'F'), + 'D' => array(), + 'E' => array(), + 'F' => array('G', 'C'), + 'G' => array(), + ); + + $cycle = $this->findGraphCycle($graph); + $this->assertEqual(array('A', 'C', 'F', 'C'), $cycle, 'Cyclic Graph'); + } + + public function testNonTreeGraph() { + // This graph is non-cyclic, but C is both a child and a grandchild of A. + // This is permitted. + $graph = array( + 'A' => array('B', 'C'), + 'B' => array('C'), + 'C' => array(), + ); + + $cycle = $this->findGraphCycle($graph); + $this->assertEqual(null, $cycle, 'NonTreeGraph'); + } + + public function testEdgeLoadFailure() { + $graph = array( + 'A' => array('B'), + ); + + $raised = null; + try { + $this->findGraphCycle($graph); + } catch (Exception $ex) { + $raised = $ex; + } + + $this->assertEqual( + true, + (bool)$raised, + 'Exception raised by unloadable edges.'); + } + + private function findGraphCycle(array $graph, $seed = 'A', $search = 'A') { + $detector = new TestAbstractDirectedGraph(); + $detector->setTestData($graph); + $detector->addNodes(array_select_keys($graph, array($seed))); + $detector->loadGraph(); + return $detector->detectCycles($search); + } +} diff --git a/src/utils/abstractgraph/__tests__/TestAbstractDirectedGraph.php b/src/utils/abstractgraph/__tests__/TestAbstractDirectedGraph.php new file mode 100644 index 00000000..17725700 --- /dev/null +++ b/src/utils/abstractgraph/__tests__/TestAbstractDirectedGraph.php @@ -0,0 +1,35 @@ +nodes = $nodes; + return $this; + } + + protected function loadEdges(array $nodes) { + return array_select_keys($this->nodes, $nodes); + } + +} diff --git a/src/utils/abstractgraph/__tests__/__init__.php b/src/utils/abstractgraph/__tests__/__init__.php new file mode 100644 index 00000000..f4b91531 --- /dev/null +++ b/src/utils/abstractgraph/__tests__/__init__.php @@ -0,0 +1,16 @@ +