topo.rs - source

Files

addr2line

function.rs lazy.rs lib.rs

adler

aho_corasick

packed

teddy

compile.rs mod.rs runtime.rs

api.rs mod.rs pattern.rs rabinkarp.rs vector.rs

ahocorasick.rs automaton.rs buffer.rs byte_frequencies.rs classes.rs dfa.rs error.rs lib.rs nfa.rs prefilter.rs state_id.rs

arrayvec

array.rs array_string.rs char.rs errors.rs lib.rs maybe_uninit.rs

atty

backtrace

backtrace

libunwind.rs mod.rs

symbolize

gimli

elf.rs libs_dl_iterate_phdr.rs mmap_unix.rs stash.rs

gimli.rs mod.rs

capture.rs lib.rs print.rs types.rs

bitflags

camino

lib.rs serde_impls.rs

cargo_metadata

dependency.rs diagnostic.rs errors.rs lib.rs messages.rs

cargo_nextest

cargo_cli.rs dispatch.rs errors.rs lib.rs output.rs

cargo_platform

cfg.rs error.rs lib.rs

cfg_expr

expr

lexer.rs parser.rs

targets

error.rs expr.rs lib.rs targets.rs

cfg_if

chrono

format

mod.rs parse.rs parsed.rs scan.rs strftime.rs

naive

date.rs datetime.rs internals.rs isoweek.rs time.rs

offset

fixed.rs local.rs mod.rs utc.rs

sys

date.rs datetime.rs div.rs lib.rs round.rs sys.rs

clap

clap_derive

derives

arg_enum.rs args.rs into_app.rs mod.rs parser.rs subcommand.rs

utils

doc_comments.rs mod.rs spanned.rs ty.rs

attrs.rs dummies.rs lib.rs parse.rs

color_eyre

section

config.rs fmt.rs handler.rs lib.rs private.rs writers.rs

config

file

format

source

file.rs mod.rs string.rs

path

mod.rs parser.rs

config.rs de.rs env.rs error.rs lib.rs ser.rs source.rs value.rs

crossbeam_channel

flavors

array.rs at.rs list.rs mod.rs never.rs tick.rs zero.rs

channel.rs context.rs counter.rs err.rs lib.rs select.rs select_macro.rs utils.rs waker.rs

crossbeam_deque

deque.rs lib.rs

crossbeam_epoch

sync

list.rs mod.rs queue.rs

atomic.rs collector.rs default.rs deferred.rs epoch.rs guard.rs internal.rs lib.rs

crossbeam_utils

atomic

atomic_cell.rs consume.rs mod.rs seq_lock.rs

sync

mod.rs parker.rs sharded_lock.rs wait_group.rs

backoff.rs cache_padded.rs lib.rs thread.rs

ctrlc

platform

unix

error.rs lib.rs signal.rs

datatest_stable

lib.rs macros.rs runner.rs utils.rs

debug_ignore

duct

either

enable_ansi_support

env_logger

filter

mod.rs string.rs

fmt

humantime

mod.rs shim_impl.rs

writer

termcolor

mod.rs shim_impl.rs

eyre

backtrace.rs chain.rs context.rs error.rs fmt.rs kind.rs lib.rs macros.rs wrapper.rs

fixedbitset

lib.rs range.rs

gimli

guppy

guppy_workspace_hack

hashbrown

external_trait_impls

raw

alloc.rs bitmask.rs mod.rs sse2.rs

lib.rs macros.rs map.rs scopeguard.rs set.rs

humantime

date.rs duration.rs lib.rs wrapper.rs

humantime_serde

indent_write

fmt.rs indentable.rs io.rs lib.rs

indenter

indexmap

map

core

equivalent.rs lib.rs macros.rs map.rs mutable_keys.rs set.rs util.rs

is_ci

itertools

itoa

lib.rs udiv128.rs

lazy_static

inline_lazy.rs lib.rs

lexical_core

libc

unix

linux_like

linux

arch

generic

gnu

b64

x86_64

align.rs mod.rs not_x32.rs

align.rs mod.rs

align.rs mod.rs non_exhaustive.rs

align.rs mod.rs

fixed_width_ints.rs lib.rs macros.rs

log

lib.rs macros.rs

memchr

memchr

x86

avx.rs mod.rs sse2.rs

fallback.rs iter.rs mod.rs naive.rs

memmem

prefilter

x86

avx.rs mod.rs sse.rs

fallback.rs genericsimd.rs mod.rs

x86

avx.rs mod.rs sse.rs

byte_frequencies.rs genericsimd.rs mod.rs rabinkarp.rs rarebytes.rs twoway.rs util.rs vector.rs

memoffset

lib.rs offset_of.rs raw_field.rs span_of.rs

miniz_oxide

deflate

buffer.rs core.rs mod.rs stream.rs

inflate

core.rs mod.rs output_buffer.rs stream.rs

lib.rs shared.rs

nested

nextest_metadata

errors.rs exit_codes.rs lib.rs test_list.rs

nextest_runner

reporter

test_list

output_format.rs

config.rs errors.rs helpers.rs lib.rs partition.rs reporter.rs runner.rs signal.rs stopwatch.rs test_filter.rs test_list.rs

nix

nom

bits

complete.rs macros.rs mod.rs streaming.rs

branch

macros.rs mod.rs

bytes

complete.rs macros.rs mod.rs streaming.rs

character

complete.rs macros.rs mod.rs streaming.rs

combinator

macros.rs mod.rs

multi

macros.rs mod.rs

number

complete.rs macros.rs mod.rs streaming.rs

sequence

macros.rs mod.rs

error.rs internal.rs lib.rs methods.rs str.rs traits.rs util.rs whitespace.rs

num_cpus

lib.rs linux.rs

num_integer

average.rs lib.rs roots.rs

num_traits

ops

checked.rs inv.rs mod.rs mul_add.rs overflowing.rs saturating.rs wrapping.rs

bounds.rs cast.rs float.rs identities.rs int.rs lib.rs macros.rs pow.rs sign.rs

object

once_cell

imp_std.rs lib.rs race.rs

os_pipe

os_str_bytes

common

iter.rs lib.rs pattern.rs raw_str.rs util.rs

owo_colors

colors

css.rs custom.rs dynamic.rs xterm.rs

colors.rs combo.rs dyn_colors.rs dyn_styles.rs lib.rs overrides.rs styles.rs supports_colors.rs

pathdiff

petgraph

proc_macro2

detection.rs fallback.rs lib.rs marker.rs parse.rs wrapper.rs

proc_macro_error

imp

diagnostic.rs dummy.rs lib.rs macros.rs sealed.rs

proc_macro_error_attr

lib.rs parse.rs settings.rs

quick_junit

lib.rs report.rs serialize.rs

quick_xml

events

attributes.rs mod.rs

errors.rs escapei.rs lib.rs reader.rs utils.rs writer.rs

quote

ext.rs format.rs ident_fragment.rs lib.rs runtime.rs spanned.rs to_tokens.rs

rayon

array.rs delegate.rs lib.rs math.rs option.rs par_either.rs prelude.rs private.rs range.rs range_inclusive.rs result.rs split_producer.rs str.rs string.rs vec.rs

rayon_core

compile_fail

mod.rs quicksort_race1.rs quicksort_race2.rs quicksort_race3.rs rc_return.rs rc_upvar.rs scope_join_bad.rs

join

scope

sleep

counters.rs mod.rs

spawn

thread_pool

job.rs latch.rs lib.rs log.rs private.rs registry.rs unwind.rs

regex

literal

backtrack.rs compile.rs dfa.rs error.rs exec.rs expand.rs find_byte.rs input.rs lib.rs pikevm.rs pool.rs prog.rs re_builder.rs re_bytes.rs re_set.rs re_trait.rs re_unicode.rs sparse.rs utf8.rs

regex_syntax

rustc_demangle

legacy.rs lib.rs v0.rs

ryu

buffer

pretty

exponent.rs mantissa.rs mod.rs

common.rs d2s.rs d2s_full_table.rs d2s_intrinsics.rs digit_table.rs f2s.rs f2s_intrinsics.rs lib.rs

same_file

scopeguard

semver

backport.rs display.rs error.rs eval.rs identifier.rs impls.rs lib.rs parse.rs serde.rs

serde

de

format.rs ignored_any.rs impls.rs mod.rs seed.rs utf8.rs value.rs

private

de.rs doc.rs mod.rs ser.rs size_hint.rs

ser

fmt.rs impls.rs impossible.rs mod.rs

integer128.rs lib.rs macros.rs

serde_derive

internals

ast.rs attr.rs case.rs check.rs ctxt.rs mod.rs receiver.rs respan.rs symbol.rs

bound.rs de.rs dummy.rs fragment.rs lib.rs pretend.rs ser.rs try.rs

serde_json

features_check

io

value

de.rs from.rs index.rs mod.rs partial_eq.rs ser.rs

de.rs error.rs iter.rs lib.rs macros.rs map.rs number.rs read.rs ser.rs

shared_child

sys

shellwords

smallvec

static_assertions

assert_cfg.rs assert_eq_align.rs assert_eq_size.rs assert_fields.rs assert_impl.rs assert_obj_safe.rs assert_trait.rs assert_type.rs const_assert.rs lib.rs

strip_ansi_escapes

strsim

structopt

structopt_derive

attrs.rs doc_comments.rs lib.rs parse.rs spanned.rs ty.rs

supports_color

syn

target_lexicon

data_model.rs host.rs lib.rs parse_error.rs targets.rs triple.rs

target_spec

errors.rs lib.rs platform.rs simple_eval.rs spec.rs triple.rs

termcolor

textwrap

core.rs indentation.rs lib.rs word_separators.rs word_splitters.rs wrap_algorithms.rs

time

display.rs duration.rs lib.rs parse.rs sys.rs

toml

datetime.rs de.rs lib.rs macros.rs map.rs ser.rs spanned.rs tokens.rs value.rs

twox_hash

lib.rs sixty_four.rs thirty_two.rs xxh3.rs

unicode_xid

lib.rs tables.rs

utf8parse

lib.rs types.rs

vte

definitions.rs lib.rs params.rs table.rs

vte_generate_state_changes

walkdir

dent.rs error.rs lib.rs util.rs

// Copyright (c) The cargo-guppy Contributors
// SPDX-License-Identifier: MIT OR Apache-2.0

use petgraph::{
    graph::IndexType,
    prelude::*,
    visit::{
        GraphRef, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCompactIndexable, VisitMap,
        Visitable, Walker,
    },
};
use std::marker::PhantomData;

/// A cycle-aware topological sort of a graph.
#[derive(Clone, Debug)]
pub struct TopoWithCycles<Ix> {
    // This is a map of each node index to its corresponding topo index.
    reverse_index: Box<[usize]>,
    // Prevent mixing up index types.
    _phantom: PhantomData<Ix>,
}

impl<Ix: IndexType> TopoWithCycles<Ix> {
    pub fn new<G>(graph: G) -> Self
    where
        G: GraphRef
            + Visitable<NodeId = NodeIndex<Ix>>
            + IntoNodeIdentifiers
            + IntoNeighborsDirected<NodeId = NodeIndex<Ix>>
            + NodeCompactIndexable,
        G::Map: VisitMap<NodeIndex<Ix>>,
    {
        // petgraph's default topo algorithms don't handle cycles. Use DfsPostOrder which does.
        let mut dfs = DfsPostOrder::empty(graph);
        dfs.stack.extend(
            graph
                .node_identifiers()
                .filter(move |&a| graph.neighbors_directed(a, Incoming).next().is_none()),
        );
        let mut topo: Vec<NodeIndex<Ix>> = dfs.iter(graph).collect();
        // dfs returns its data in postorder (reverse topo order), so reverse that for forward topo
        // order.
        topo.reverse();

        // Because the graph is NodeCompactIndexable, the indexes are in the range (0..topo.len()).
        // Use this property to build a reverse map.
        let mut reverse_index = vec![0; topo.len()];
        topo.iter().enumerate().for_each(|(topo_ix, node_ix)| {
            reverse_index[node_ix.index()] = topo_ix;
        });

        Self {
            reverse_index: reverse_index.into_boxed_slice(),
            _phantom: PhantomData,
        }
    }

    /// Sort nodes based on the topo order in self.
    #[inline]
    pub fn sort_nodes(&self, nodes: &mut Vec<NodeIndex<Ix>>) {
        nodes.sort_unstable_by_key(|node_ix| self.topo_ix(*node_ix))
    }

    #[inline]
    pub fn topo_ix(&self, node_ix: NodeIndex<Ix>) -> usize {
        self.reverse_index[node_ix.index()]
    }
}