https://github.com/rust-lang/rust http://git.dreamy.place/mirrors/rust/atom?h=1.57.0 2021-10-10T13:38:19+00:00 2021-10-10T13:38:19+00:00 Clemens Wasser clemens.wasser@gmail.com 2021-10-09T18:44:22+00:00 urn:sha1:71dd0b928b8b175b69e56fc58e5878b73f090718 2021-09-28T12:28:22+00:00 Oli Scherer github35764891676564198441@oli-obk.de 2021-08-20T13:36:04+00:00 urn:sha1:9b5aa063d8e9808eacd27a0bf75a85495ff01bd4 2021-09-24T10:44:28+00:00 r00ster91 r00ster91@protonmail.com 2021-09-24T10:44:28+00:00 urn:sha1:956f87fb04f589ac2fbe262a043c9f3cad6b2ac0 2021-09-08T16:23:37+00:00 Niko Matsakis niko@alum.mit.edu 2020-11-23T14:26:10+00:00 urn:sha1:c9d46eb2244d49215e0a1ccf8bd4b7e700b252e7 This expands the API to be more flexible, allowing for more visitation patterns on graphs. This will be useful to avoid extra datasets (and allocations) in cases where the expanded DFS API is sufficient. This also fixes a bug with the previous DFS constructor, which left the start node not marked as visited (even though it was immediately returned). 2021-08-09T13:52:04+00:00 pierwill pierwill@users.noreply.github.com 2021-08-09T13:52:04+00:00 urn:sha1:3e123e415014d700b83f3b373423507683105910 2021-02-10T08:20:41+00:00 Dániel Buga bugadani@gmail.com 2021-01-17T19:20:16+00:00 urn:sha1:3c1d792f498ae40eb759d4554540a94612a3df55 2021-01-24T12:32:18+00:00 Dániel Buga bugadani@gmail.com 2021-01-24T12:32:18+00:00 urn:sha1:f8416faaaf3a1fb6ca57ff8f0b3bdf972eed266f 2020-12-29T21:26:58+00:00 Matthias Krüger matthias.krueger@famsik.de 2020-12-29T21:02:47+00:00 urn:sha1:0c3af22e08124a371b182bfec94437d447e15810 2020-12-18T20:22:51+00:00 Joshua Nelson jyn514@gmail.com 2020-12-01T22:41:09+00:00 urn:sha1:35f16c60e7d3fd1b42c90a0fc084689c817345cb rustc_lint and rustc_lint_defs weren't switched because they're included in the compiler book and so can't use intra-doc links. 2020-11-21T01:30:26+00:00 bors bors@rust-lang.org 2020-11-21T01:30:26+00:00 urn:sha1:8cfa7b4ec9d314a412f79c1748bd2dfa7575b2e3 Reworks Sccc computation to iteration instead of recursion Linear graphs, producing as many scc's as nodes, would recurse once for every node when entered from the start of the list. This adds a test that exhausted the stack at least on my machine with error: ``` thread 'graph::scc::tests::test_deep_linear' has overflowed its stack fatal runtime error: stack overflow ``` This may or may not be connected to #78567. I was only reminded that I started this rework some time ago. It might be plausible as borrow checking a long function with many borrow regions around each other—((((((…))))))— may produce the linear list setup to trigger this stack overflow ? I don't know enough about borrow check to say for sure. This is best read in two separate commits. The first addresses only `find_state` internally. This is classical union phase from union-find. There's also a common solution of using the parent pointers in the (virtual) linked list to track the backreferences while traversing upwards and then following them backwards in a second path compression phase. The second is more involved as it rewrites the mutually recursive `walk_node` and `walk_unvisited_node`. Firstly, the caller is required to handle the unvisited case of `walk_node` so a new `start_walk_from` method is added to handle that by walking the unvisited node if necessary. Then `walk_unvisited_node`, where we would previously recurse into in the missing case, is rewritten to construct a manual stack of its frames. The state fields consist of the previous stack slots.