https://github.com/rust-lang/rust http://git.dreamy.place/mirrors/rust/atom?h=1.53.0 2021-02-10T08:20:41+00:00 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. 2020-11-08T17:07:45+00:00 Andreas Molzer andreas.molzer@gmx.de 2020-10-30T22:12:24+00:00 urn:sha1:eb597f5c4e258563cac1a957ae348f7c24cb0734 This allows constructing the sccc for large that visit many nodes before finding a single cycle of sccc, for example lists. When used to find dependencies in borrow checking the list case is what occurs in very long functions. 2020-11-05T18:24:49+00:00 Andreas Molzer andreas.molzer@gmx.de 2020-10-30T23:43:00+00:00 urn:sha1:355904dca086675b1c3dac25e8c0410f27f80a6d 2020-11-05T18:24:49+00:00 Andreas Molzer andreas.molzer@gmx.de 2019-05-22T23:00:43+00:00 urn:sha1:a41e2fd963915c940a46a67825ec053afb004f87 The basic conversion is a straightforward conversion of the linear recursion to a loop forwards and backwards propagation of the result. But this uses an optimization to avoid the need for extra space that would otherwise be necessary to store the stack of unfinished states as the function is not tail recursive. Observe that only non-root-nodes in cycles have a recursive call and that every such call overwrites their own node state. Thus we reuse the node state itself as temporary storage for the stack of unfinished states by inverting the links to a chain back to the previous state update. When we hit the root or end of the full explored chain we propagate the node state update backwards by following the chain until a node with a link to itself. 2020-10-31T17:52:00+00:00 Andreas Molzer andreas.molzer@gmx.de 2020-10-31T16:56:13+00:00 urn:sha1:af72a70ee27faa85522f7656e042c85ab1ee275e The previous recursive approach might overflow the stack when walking a particularly deep, list-like, graph. In particular, dominator calculation for borrow checking does such a traversal and very long functions might lead to a region dependency graph with in this problematic structure. 2020-10-31T00:05:15+00:00 Andreas Molzer andreas.molzer@gmx.de 2019-05-22T23:00:07+00:00 urn:sha1:4fdf8a5630a621c44a0928a1e30d881b0e00022b While a bit primitive, it should get us at least a better number than nothing.