Adding a way to see the parents of expressions - Help Needed!

[Kieranoski702]

So I am currently trying to implement the clean/dirty optimisation which is explained briefly in this issue under "The rewrite function". I have implemented almost everything I need to get this working except I need some way to traverse back up the expressions to mark them as dirty. For context, the apply_all_rules function is the function that should mark nodes as dirty if there are rules to apply. I have made a mock mark_dirty function which would work if Expression had some sort of parent attribute but this does not exist.

There are quite a few ways this could be achieved but I am unsure what the best course of action is. If we were to add to the Expression itself then we would need to set each node's parent when creating the model. I don't know much about how the model is made, would this be simple? Alternatively, we could put this parent attribute within the Metadata but this would also require us to set it somewhere and I am not sure exactly where I would be able to do this in the code.

@ozgurakgun @ChrisJefferson @niklasdewally @lixitrixi @gskorokhod
If anybody has suggestions on the best course of action for this then please let me know as this is the last hurdle before the PR for this optimisation can be made. Thanks in advance!

fn apply_all_rules<'a>(
    expression: &'a Expression,
    model: &'a Model,
    rules: &'a Vec<&'a Rule<'a>>,
) -> Vec<RuleResult<'a>> {
    let mut results = Vec::new();
    for rule in rules {
        match rule.apply(expression, model) {
            Ok(red) => {
                results.push(RuleResult {
                    rule,
                    reduction: red,
                });
                mark_dirty(expression); // Mark this expression (and it's parents) as dirty
                log::trace!(target: "file", "Rule applied: {:?}", rule);
            }
            Err(_) => {
                log::trace!(target: "file", "Rule attempted but not applied: {:?}", rule);
                continue;
            }
        }
    }
    results
}

fn mark_dirty(expression: &Expression) {
    let mut current = expression;
    while let Some(parent) = current.parent() {
        parent.set_clean(false); // Mark parent as dirty
        current = parent;
    }
}

[niklasdewally]

@Kieranoski702

If we were to add to the Expression itself then we would need to set each node's parent when creating the model. I don't know much about how the model is made, would this be simple? Alternatively, we could put this parent attribute within the Metadata but this would also require us to set it somewhere and I am not sure exactly where I would be able to do this in the code.

I think the underlying problems are that our trees are immutable data structures and how Rusts ownership model gets in the way of trees in general.

Doing this bidirectional "parent contains child which contains a pointer to the parent" seems to be annoying in Rust from as it basically turns things into a DAG and creates ownership problems. (https://github.com/SimonSapin/rust-forest, https://timidger.github.io/posts/designing-a-bi-mutable-directional-tree-safely-in-rust/). Then something like cursors, visitor pattern, etc to traverse the tree.

To do this, Rc Refcells would be needed. However, we decided early on that we would do a functional / immutable tree instead and I think that has advantages in this case (eg handling backtracking).

Our general solution to this was Uniplate - if it is a "all in one" recursive algorithm something like descend() or transform() would work, or for "one at a time" things there are Zippers, which would allow directly going up to the parent.

[niklasdewally]

Is this a tree traversal?

[niklasdewally]

If this is still a tree traversal, the parent could check the children and make itself dirty if any of the children are dirty?

[Kieranoski702]

If this is still a tree traversal, the parent could check the children and make itself dirty if any of the children are dirty?

This is still a tree traversal but the issue with that would be if rules have a depth higher than one down. I don't know if any rules do have a further depth than that so you might be able to advise me. If that is the case then yeah looking at children would work but if grandchildren can affect grandparents then those would need to be checked etc.

[niklasdewally]

If this is still a tree traversal, the parent could check the children and make itself dirty if any of the children are dirty?

This is still a tree traversal but the issue with that would be if rules have a depth higher than one down. I don't know if any rules do have a further depth than that so you might be able to advise me. If that is the case then yeah looking at children would work but if grandchildren can affect grandparents then those would need to be checked etc.

One thing i am not sure about is whether a clean to dirty change propagates all the way up the tree, or just changes the immediate parent? My understanding is that it should make all ancestors dirty, as those expressions have all changed in some way? That makes the recursion simpler as dirty just bubbles up all layers instead of just one (this would require some sort of "if we are directly above a node that has just had a rule applied to it" logic)

Also, if the children of the current node are moved around by a rule, are they clean or dirty?

For the rule stuff, CC @gskorokhod @ozgurakgun @lixitrixi

[ChrisJefferson]

I think dirty should go all the way up the tree. Also, I'd mark children dirty if they move -- in general it's safer to mark things as "dirty", as it just means rules and simplifications are applied to them (and, if things move around, they might now be candidates for that).

I think Rust's immutablility helps with dealing with dirty. If you mark something as dirty, it means you have a mutable reference to it. That means whoever asked you to look at it is either going to put it in a new parent, or has a mutable reference to the parent (else how did they give you a mutable reference to the child?)

Therefore you could introduce a rule (not sure it's possible to enforce this with code reasonably) that if you call "apply_all_rules" (or other methods which can make things dirty), then it's your job to check if it made it dirty, and if so pass the flag up to the parent.

Can add a debug check which sweeps the whole tree every so often, and check if there is ever a dirty child with a clean parent, which means someone messed up!