miden-vm icon indicating copy to clipboard operation
miden-vm copied to clipboard

Implement `MastForest` merging

Open PhilippGackstatter opened this issue 4 months ago • 3 comments

Describe your changes

Closes #1529

Implements MastForest merging.

The implementation is explained in comments and it's hopefully sufficient to understand the PR, which is why I'm not adding the details here again. If any explanation is insufficient I'm happy to expand on it!

Couple of notes and ideas:

  • The MastForestDfsIter could be 1) made public and 2) could be made more general to allow for in-order, pre-order as well as post-order iteration of MastForests. Let me know if any of these are desirable. For now it seems best to keep them private.
  • The MastForestMerger is also kept private because the useful functionality can be exposed through the methods added on MastForest directly and there is no benefit in terms of functionality by making it public.
  • Moved EqHash into miden-core.
    • One annoyance is that this type needs to be public in miden-core so that it can be used in miden-assembly by MastForestBuilder where it originally lived. Moving MastForestBuilder into core doesn't seem fitting since it is used only for assembly and specially made for that. Overall it's not bad to have EqHash public in core.
    • Because that type needs to become public, I would propose to rename it to something a more easily understandable, like MastNodeFingerprint and perhaps introduce pub type DecoratorFingerprint = Blake3Digest<32> for decorators. I think the "fingerprint" nicely describes that this type can be used to compare mast nodes although I'm of course open to other suggestions.
    • If this type becomes public we should document its public functions (added TODO).
    • This topic could overall be handled in a quick follow-up PR if desired.
  • I would like to test the implementation with some more complex "real-world" input, but this is difficult in miden-core without an Assembler. I don't want to move those test into miden-assembly though as that separates the implementation and the tests crate-wise. Even with an assembler, it would still be somewhat challenging to come up with the expected merged forest to assert against without basically handwriting it. Although I suppose asserting a couple of properties might be sufficient instead of the entire forest, so it would still be an improvement. One possibility I see to add test in miden-core would be to generate snapshots in miden-assembly, for example, and add them as plaintext serialized MastForests to miden-core. Snapshot testing could be done with something like insta or without, I suppose. This would require adding #[cfg_attr(test, derive(Serialize, Deserialize))] to MastForest and all its descendants which is fine I guess. I'm happy to receive some general input on the testing story for this task though.

Checklist before requesting a review

  • Repo forked and branch created from next according to naming convention.
  • Commit messages and codestyle follow conventions.
  • Relevant issues are linked in the PR description.
  • Tests added for new functionality.
  • Documentation/comments updated according to changes.

PhilippGackstatter avatar Oct 15 '24 15:10 PhilippGackstatter