For the python wrapper, I want to either modify the cursor idea to support a "don't care" concept.
If the path down the bdd skips over a variable, it means we don't care about it. Right now, the solution iterators are designed to explicitly account for this, and do a "ripple carry" operation over the skipped variables. (Basically, we just treat that run of variables as a binary number and keep incrementing it until a variable above it flips.)
But, in the dd python wrapper for bdds, it prefers to skip over the duplicates by simply removing the variables we don't care about from the yielded assignments at each step. ... but it ALSO has a way to opt back in.
Study the code in bdd_sols.rs and come up with a way to do this while still supporting the current "iterate through every solution" behavior.
You don't need to worry about the rust version of the iterator right now. We should just be looking at the functions that take and accept cursors, and the functions they call.
One idea I have is to add a second reg called care to the cursor, to opt into caring about certain variables. If we care about a variable, we should always "ripple carry" through it, but if we don't care, then we should probably mask those numbers in to to always be 1 so that we always flip them.
At any given time the list of variables we DON'T care about can be determined by looking at the nids in the cursor's .nstack. We can find its variable by looking at .vid_ix() (assuming it's not .is_const())... they should be in order from 0 at the bottom to the highest variable at the top, and any time there's a gap AND that number is not marked as a "care" variable, then we don't care about it.
Make it so
GitHub Copilot Below is one way to do it. The idea is to give the Cursor its own “care” register. When a cursor is created you can optionally supply a Reg (or later a bitmap/set) of cared‐for variables. Then in methods like increment (which drives the ripple–carry) you check that “care” register so that if a variable isn’t cared for you simply force its value (for example, always 1) rather than doing the usual binary increment. That way when you yield a solution (via pick_iter, for example) you can mask out the variables that are “don’t care” (or opt them back in if desired). One possible diff for the rust Cursor is as follows:
// Add a new field “care” to the Cursor struct
pub struct Cursor {
pub nvars: usize, // number of input variables in context
pub node: NID, // the current node.
pub scope: Reg, // the current variable assignments
pub nstack: Vec<NID>, // the path of nodes we have traversed
pub istack: Vec<bool>, // the stack of node inversion states
pub invert: bool, // whether to invert the results
pub care: Reg, // register tracking which variables we care about
}
impl Cursor {
// New constructor that accepts an optional "care" register.
// If care is None, then assume all variables are cared for.
pub fn new_with_care(nvars: usize, node: NID, care: Option<Reg>) -> Self {
Cursor {
node,
nvars,
invert: false,
scope: Reg::new(nvars),
nstack: vec![],
istack: vec![],
care: care.unwrap_or_else(|| Reg::new_all(nvars, true)), // Reg::new_all(nvars, true) creates a Reg with all bits set.
}
}
// -------------------------------------------------------------------------
// Modify the increment() method to use the care register.
// For variables that are not cared for, we simply force them to True (i.e. 1)
// so that they do not contribute to the ripple–carry.
pub fn increment(&mut self) -> Option<usize> {
// Suppose our Reg has methods: get(i) -> bool and put(i, val: bool)
for i in 0..self.nvars {
// If we do not care for this variable, force its value to true
// and continue to the next variable.
if !self.care.get(i) {
self.scope.put(i, true);
continue;
}
// If the variable is 0, flip it to 1 and return its index.
if !self.scope.get(i) {
self.scope.put(i, true);
return Some(i);
} else {
// If it’s 1, set it to 0 and continue (ripple carry).
self.scope.put(i, false);
}
}
None // overflow: handled all bits
}
// ... other methods unchanged, they will now work with the new care field ...
}In your Python wrapper you can then choose (via the C++/Rust binding) to instantiate a Cursor using new_with_care with an appropriate care Reg. For instance, when calling pick_iter you can pass an empty care set (or a partial one) to have the iterator yield only the assignments for the variables you care about. If no care_vars are provided, the default (all cared for) behavior remains unchanged.
This approach preserves the “iterate through every solution” behavior while allowing you to mask out (or opt in to) variables as desired.