diff options
| author | Mazdak Farrokhzad <twingoow@gmail.com> | 2019-09-24 23:45:22 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2019-09-24 23:45:22 +0200 |
| commit | e00bd27953a096929c0a5d6f41b8aca6243eabb2 (patch) | |
| tree | 4b3747aa9c616334516977fd64e9b3c1ecf8bd04 /src/rustllvm/RustWrapper.cpp | |
| parent | 4a58b14db5ed21654e952f051af2a6c51dfb15fd (diff) | |
| parent | c9e4816fe319b2fde83779ff375037c8079d36a2 (diff) | |
| download | rust-e00bd27953a096929c0a5d6f41b8aca6243eabb2.tar.gz rust-e00bd27953a096929c0a5d6f41b8aca6243eabb2.zip | |
Rollup merge of #64622 - ecstatic-morse:cycle-detector, r=oli-obk
Add a cycle detector for generic `Graph`s and `mir::Body`s Cycle detection is one way to differentiate the upcoming `const_loop` feature flag (#52000) from the `const_if_match` one (#49146). It would be possible to use the existing implementation of strongly-connected components for this but less efficient. The ["tri-color" terminology](http://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/lec24-12sp.html) is common in introductory data structures and algorithms courses: black nodes are settled, grey nodes are visited, and white nodes have no state. This particular implementation is iterative and uses a well-known technique where "node settled" events are kept on the stack alongside nodes to visit. When a settled event is popped, we know that all successors of that node have been visited and themselves settled. If we encounter a successor node that has been visited (is on the stack) but not yet settled, we have found a cycle. r? @eddyb
Diffstat (limited to 'src/rustllvm/RustWrapper.cpp')
0 files changed, 0 insertions, 0 deletions