miden-vm
miden-vm copied to clipboard
Implement `MastForest` merging
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 ofMastForest
s. 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 onMastForest
directly and there is no benefit in terms of functionality by making it public. - Moved
EqHash
intomiden-core
.- One annoyance is that this type needs to be public in
miden-core
so that it can be used inmiden-assembly
byMastForestBuilder
where it originally lived. MovingMastForestBuilder
into core doesn't seem fitting since it is used only for assembly and specially made for that. Overall it's not bad to haveEqHash
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 introducepub 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.
- One annoyance is that this type needs to be public in
- I would like to test the implementation with some more complex "real-world" input, but this is difficult in
miden-core
without anAssembler
. I don't want to move those test intomiden-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 inmiden-assembly
, for example, and add them as plaintext serializedMastForest
s to miden-core. Snapshot testing could be done with something likeinsta
or without, I suppose. This would require adding#[cfg_attr(test, derive(Serialize, Deserialize))]
toMastForest
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.