Code review request (DAG data structure, topological sort, boolean circuits)

help
1

Could I get a code review?

Playground URL: Rust Playground

Gist URL: https://gist.github.com/a53bc11473522f47fe71a7a46b54908d

This code implements a DAG data structure for Boolean circuits and has a function (compute) to evaluate them, which includes a topological sort algorithm (dfs).

In particular I'm not sure of the following are idiomatic: the data structure itself at line 26, relatives/children/parents functions at lines 34-65, depth first search at line 67, and compute at line 98.

Any help appreciated, thanks!

2

I don't have enough time to check the algorithms and architectures, but I can offer some idiomatic codes. In no particular order:

  • DAG::relatives accepts functions by Box<Fn(...) -> ...>, which is bad because, in addition to an additional allocation and virtual call overhead, it cannot refer to any variable outside of the closure as it is equivalent to Box<Fn(...) -> ... + 'static>! It is normal to use a type parameter for such function arguments unless you have a stronger reason not to do so (e.g. your method should be in the trait object, or you want to avoid binary bloat and there is no more option left).

  • Vec<Bit> parameter is suspicious---in most cases &[Bit] should be sufficient unless it's &mut Vec<Bit>.

  • match x { Some(v) => Some(f(v)), None => None } can be simplified to x.map(f) for many cases. If f has to return from the function, you can also use if let Some(v) = x { Some(f(v)) } else { None }.

  • while !stack.is_empty() { let ix = stack.pop().unwrap(); ... } can be simplified to while let Some(ix) = stack.pop() { ... }. This is a common pattern for queues and stacks.

1 Like
3

Last three - thanks, I made the changes and understand why they're better.

First one - I got it to work correctly, but I don't really understand the difference between a type parameter and inlining the type of the function inside the parens, I thought they were the same thing. Isn't it still the case that the size of edge_fn is not known at compile time?

fn relatives<EFn, NFn>(&self, node_idx: NIdx, edge_fn: EFn, node_fn: NFn) 
        -> Option<Vec<NIdx>>
        where EFn: Fn(NIdx) -> &'a Vec<EIdx>,
              NFn: Fn(EIdx) -> NIdx {
    if self.nodes.contains_key(&node_idx) {
        Some(edge_fn(node_idx).into_iter().map(|x| node_fn(*x)).collect())
    } else {
        None
    }
}

fn children(&self, node_idx: NIdx) -> Option<Vec<NIdx>> {
    self.relatives(
        node_idx,
        |node_idx| &self.nodes[&node_idx].outgoing_edges,
        |edge_idx| self.edges[&edge_idx].sink
    )
}