Would a "Miniscript context object" be acceptable?

[apoelstra]

In rust-simplicity we have a context parameter that you must pass to every leaf node. We use this context object to hold a slab allocator for nodes to improve cache locality and so that we can programattically cache common constructions.

Simplicity is structurally very similar to Miniscript except that it can express arbitrary functions rather than just monotone ones, and its leaf nodes are computational primitives (the identity and unit function) rather than key/hash/time checks. In rust-simplicity we were forced to have a context object because our programs are represented as DAGs rather than trees so you can "naturally" construct cycles within the type inference logic, so we couldn't use Arc without our fuzzer complaining about
leaked memory. But once we had the context object for type inference, we realized that we could also use it to slab-allocate entire nodes, eliminating the recursive representation of nodes entirely.

Miniscript does not have type inference (or rather, it has a very boring form of type inference where every expression has a unique specific type no matter where it appears), so Arc works fine. But by using a recursive structure containing Arc<Self> we have a number of problems:

• Everything is inherently recursive, including the compiler-generated Drop impl, necessitating the MAX_RECURSION_DEPTH constant and the recent string of bugfixes related to that.
• Cache locality is poor and destructing is slow because it involves a ton of individual calls to Arc::drop.
• Translating involves completely reconstructing trees, redoing type inference, etc., which is slow and also involves a ton of code (see Translator traits take up a lot of space #717)
• Because our main Miniscript type is an enum, Rust gives us a ton of constructors that can be used to construct invalid values...
• ...but we don't even get the benefit of the enum (nice matching) because you can't match through Arcs.

I propose that we copy the structure from rust-simplicity for Miniscript, where:

• We have a Node type which is an opaque struct (it can still be called Miniscript).
• This type contains an Inner enum which is the public enum which users can get read-only access to, and can use to match. (Users can create their own invalid Inners if they want but they can't convert to a Miniscript without going through the typechecker.)
• The way that users construct nodes, assuming they don't want to just parse strings/scripts, is by inherent functions: Miniscript::key(pk) which is infallible; Miniscript::and_v(&Self, &Self) which can error if the child types are incompatible; etc etc.
• We have a Context object which contains a slab allocator for nodes and contains a non-generic Box<dyn ScriptContext> that it uses to do correctness checks during construction. So the Ctx generic goes away across the board. To manually construct Miniscript objects users must create this object (and they can/should create distinct ones for distinct Miniscripts, though I think in Miniscript this doesn't matter). But the Miniscripts will hold Arcs to their context so users don't need to keep them alive, and when parsing from strings/scripts users never see them.
• We retain the iterator API but make it first-class by adding iterator adaptors so that users can write e.g. miniscript.post_order_iter().keys_only() rather than needing the specialized ForEachKey trait.
• We replace the TranslatePk trait with an inherent Miniscript::translate method which takes a generic Translator, and which rather than returning a top-level crate::Error only returns an error if the translation results in duplicate keys (I think this the only error that can actually happen) (and I think this would fix Translator traits take up a lot of space #717). The equivalent method in Simplicity is Node::convert but I'm hesitant to link to that since the Simplicity version is way more complicated. But for your curiosity our equivalent to Translator, is this trait, which has the documentation for how to use it.

TL;DR I am proposing to

• get rid of the Miniscript enum in favor of an opaque type with explicit constructors
• make users add an extra let ctx = Context::new() line if they use these constructors (but if they are parsing from strings/scripts no change)
• eliminate the Ctx generic on Miniscript
• futz with the iterator API a bit

Edit After a moment's thought, I think the iterator stuff should be dropped from this discussion since it's a minor thing, not really fleshed out, and not necessary to the main proposal.

[apoelstra]

cc @sanket1729 @notmandatory and also I will bring this issue up today or tomorrow during the rust-bitcoin summit in Nashville.

[sanket1729]

@apoelstra, I did some preliminary analysis on the binary generated by parse example.
Current cargo bloat results on master.

New results after removing Ctx parameter.

Miniscript is still 110Kb text data compared to rust-bitcoin which is < 50 Kb (hashes + bech32 + bitcoin.)

WIP Branch remove Ctx from Miniscript struct and converting that into an enum here. This is not ready for merge and tests are still not working and it is based on Jan version of miniscript.

If this is not sufficient, I think having a dynamic dispatch for Pk will be useful in further reducing the size of binaries. All of the APIs are effectively compiled once for each Pk. We lose performance doing this, but maybe we have to do this :(

In my small experiments, the compiler is smart enough to not include interpreter related code binary in binary if we don't use it. We don't have to worry about feature gating interperter related stuff in cfg flag, but we can do that as required.

[sanket1729]

Related to context object, it is great idea. As long as basic APIs for descriptors don't change, I don't mind making things harder for advanced users of Miniscript.