rust-bitcoin / rust-miniscript

Support for Miniscript and Output Descriptors for rust-bitcoin
Creative Commons Zero v1.0 Universal
342 stars 135 forks source link

Make `from_slice_delim` (expression parser) non-recursive #696

Open brunoerg opened 2 months ago

brunoerg commented 2 months ago

Sorry if it's a dumb question, as far as I understand there is a recursion depth limit on from_slice_delim to avoid running out of stack space (based on https://github.com/sipa/miniscript/pull/5) when parsing an expression with round brackets. However, the parse function from sipa/miniscript is not recursive anymore (https://github.com/sipa/miniscript/pull/68). Worths make it non-recursive here as well? I noticed that some miniscripts that can be parsed on Core fails here because of this limit.

// https://github.com/sipa/miniscript/pull/5 for discussion on this number
const MAX_RECURSION_DEPTH: u32 = 402;
impl<'a> Tree<'a> {
    /// Parse an expression with round brackets
    pub fn from_slice(sl: &'a str) -> Result<(Tree<'a>, &'a str), Error> {
        // Parsing TapTree or just miniscript
        Self::from_slice_delim(sl, 0u32, '(')
    }

    pub(crate) fn from_slice_delim(
        mut sl: &'a str,
        depth: u32,
        delim: char,
    ) -> Result<(Tree<'a>, &'a str), Error> {
        if depth >= MAX_RECURSION_DEPTH {
            return Err(Error::MaxRecursiveDepthExceeded);
        }
apoelstra commented 2 months ago

@brunoerg yes, we would like to eliminate all the recursion from the library. This has been an ongoing project. See pulls #567 #601 #606 #614 and also the issue #484.

I have a branch which tries to eliminate recursion from from_string_delim but I haven't touched it in a little while. The issue is that our parsing logic currently has a ton of stringly-typed errors, so I got sidetracked trying to fix that, and then further sidetracked trying to remove the generics from the error types to help with #585, and then I got completely gummed up because we have these associated error types like <MiniscriptKey::Hash160 as core::FromStr>::Err which are gated on std::error::Error but only when std is enabled, and good luck defining a boxed type that can handle that while keeping the std feature additive.

In principle somebody could fix from_slice_delim to be non-recursive while preserving the existing hideous stringly-typed error situation. But that person would need to have a stronger stomach than me :).