Interesting about the Taproot internal key appearing last instead of first. Agreed that is weird and it was probably just an accident.

In general I also don't remember why we did this "internal iteration" API with for_each_key etc instead of an "external iteration" API where we provided iterators. I suspect that this pre-dated the Translator API and was intended as a way of mapping keys.

Anyway concept ACK adding iter_pk to Descriptor. But I would like to combine this with adding a map method for simple translate_pk cases. See #817.

If you're feeling motivated, can you think through what the "API for accessing, collecting and mapping keys" should look like? If not I'll give it a shot and open a mega-PR sometime in the coming weeks.

If all you want is iter_pk, ofc, go ahead and add it along with a backport to 12.x.

Thanks.

iter_pk() that iterates in left-to-right order is sufficient for me, the rest of the API seems fine to me (though as you said, translating keys could do with a bit less boilerplate).

Here is a snippet to implement iter_pk() on Tr() in case it is helpful to you:

https://github.com/BitBoxSwiss/bitbox02-firmware/blob/2c07fc74f6b17db3e5d1510de3aec5df545d1338/src/rust/bitbox02-rust/src/hww/api/bitcoin/policies.rs#L233-L242

@apoelstra

If all you want is iter_pk, ofc, go ahead and add it along with a backport to 12.x.

I misread this at first and now see that you asked me to do it 😄 I can give it a shot.

What's the reason for backporting it? Is a 13.x release far out?

@benma yeah, I think 13.x is fairly far out -- we've made some really big, but incomplete, changes to the main Error type and the constructors in Expression, and some other stuff. I'd like to get the library into a more consistent state before we can release. And get it to depend on bitcoin-units 1.0 and hex-conservative 1.0 if possible.

And so far everyone who has requested changes has done so in a way where we can just backport to 12.x, so there's been no pressure..

And I did ask you to do it, but if you don't I'll probably get around to making an issue in the next week or so :)

And I did ask you to do it, but if you don't I'll probably get around to making an issue in the next week or so :)

I am trying to do it with a proper iterator, but am finding it very hard to wrestle with the iterator types. Maybe my approach is totally wrong. Pkh and Wpkh are easy enough as they are just core::iter::Once<Pk>, but Tr is where I am struggling. Here is what I tried:

In tr.rs:

    pub fn iter_pk(&self) -> ???  {
        core::iter::once(self.internal_key.clone())
            .chain(self.leaves().flat_map(|leaf| leaf.miniscript().iter_pk()))
    }

In descriptor/mod.rs:

impl<Pk: MiniscriptKey> Descriptor<Pk> {
    pub fn iter_pk(&self) -> PkIter<Pk> { PkIter::new(self) }
}

pub enum PkIter<Pk: MiniscriptKey> {
    Once(core::iter::Once<Pk>),
    Tr(???),
}

impl<Pk: MiniscriptKey> PkIter<Pk> {
    fn new(descriptor: &Descriptor<Pk>) -> Self {
        match descriptor {
            Descriptor::Bare(bare) => todo!(),
            Descriptor::Pkh(pkh) => PkIter::Once(pkh.iter_pk()),
            Descriptor::Wpkh(wpkh) => PkIter::Once(wpkh.iter_pk()),
            Descriptor::Sh(sh) => todo!(),
            Descriptor::Wsh(wsh) => todo!(),
            Descriptor::Tr(tr) => PkIter::Tr(tr.iter_pk()),
        }
    }
}

impl<Pk: MiniscriptKey> Iterator for PkIter<Pk> {
    type Item = Pk;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            PkIter::Once(iter) => iter.next(),
            PkIter::Tr(iter) => iter.next(),
        }
    }
}

But I can't figure out the type of ???, and it does not seem practical to try to spell it out. Of course using Box<dyn Iterator<Item = Pk>> would do it, but we don't want Box I assume.

Long story short, I'd be happy if you could do it instead, let me know if that is okay for you.

For sure, I'll give it a shot. Though I can tell you that you won't be able to use map or flat_map in an iterator that you're storing like this. Annoyingly you are going to need to write your own "custom iterator" whose next impl emulates flat_map and chain.

In this library I'm not that opposed to 'Boxbecause we struggle with compile times anyway and we use a lot of dynamic memory...but I'd prefer to avoid aBoxbecause it will prevent us from implementing/usingExactSizedIterator, DoubleEndedIterator`, etc., which we ought to have for most/all of our pk iterators.

What does ExactSizedIterator etc. have to do with it? Iterators can still be exact sized even if wrapped in a box.

What prevents the use of ExactSizedIterator is using adapters like Chain, as they don't implement it, but I assume that iterator could be wrapped in a struct with the length and implement ``ExactSizedIterator` anyway, something like this:

struct ExactSize<T> {
    iterator: Box<dyn Iterator<Item = T>>,
    remaining: usize,
}

impl<T> ExactSize<T> {
    fn new(iterator: Box<dyn Iterator<Item = T>>, len: usize) -> Self {
        ExactSize {
            iterator,
            remaining: len,
        }
    }
}

impl<T> Iterator for ExactSize<T> {
    type Item = T;
    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        match self.iterator.next() {
            item @ Some(_) => {
                self.remaining -= 1;
                item
            }
            None => None,
        }
    }
}

If the use of Box is okay, this would work for iter_pk():

// in tr.rs

    pub fn iter_pk(&self) -> impl Iterator<Item = Pk> + '_ {
        core::iter::once(self.internal_key.clone())
            .chain(self.leaves().flat_map(|leaf| leaf.miniscript().iter_pk()))
    }

// in descriptor/mod.rs:

pub fn iter_pk(&self) -> Box<dyn Iterator<Item = Pk> + '_> {
        match self {
            Descriptor::Pkh(pk) => Box::new(pk.iter_pk()),
            Descriptor::Wpkh(pk) => Box::new(pk.iter_pk()),
            Descriptor::Tr(tr) => Box::new(tr.iter_pk()),
            _ => todo!(), // etc.
        }
    }

@apoelstra how about something like this?

https://github.com/benma/rust-miniscript/commit/iter_pk/

Feel free to pick this commit up and adapt it as you see fit, or to throw it away and go with manually writing the custom iterators.

Iterators can still be exact sized even if wrapped in a box.

No, a Box<dyn Iterator> does not implement ExactSizedIterator (how could it?), and Box<dyn Iterator + ExactSizedIterator> is invalid Rust syntax and also you can't construct one from an iterator that isn't ExactSizedIterator.

I'm not sure what you're getting at with the ExactSize struct. Are you suggesting that users of iter_pk should then wrap the result in that struct? How would they get len?

Chain doesn't implement ExactSizedIterator because std is stupid, but that's an independent issue that can be resolved by manually implementing Chain.

Note that the commit I linked above does not deal with ExactSizedIterator etc, so I didn't suggest that Box<dyn Iterator> could implement ExactSizedIterator. For that, it would need to return something else, like a PkIter wrapper struct where ExactSizedIterator would be implemented on, similar to the ExactSize struct example I gave above.

My point was that the use of Box (to be able to use chain/flat_map etc. without manually emulating them) in my commit (with some changes to return a wrapper struct instead) does not prevent implementing ExactSizedIterator, it just wouldn't be as elegant. Anyway, doing without Box is cleaner anyway, so I'm of course happy if you go with that approach.

I really don't understand what you're saying. What is "use of Box (to be able to use chain/flat_map etc. without manually emulating them)" if not the use of Box<dyn Iterator>? All of your examples have used Box<dyn Iterator> and/or impl Iterator, as did your original comment "Of course using Box<dyn Iterator<Item = Pk>> would do it, but we don't want Box I assume.", and all of these things get in the way of ExactSizedIterator and other traits.

Yeah it's confusing, apologies. We don't need to spend much more time here, just to wrap it up:

When you said

but I'd prefer to avoid a Box because it will prevent us from implementing/using ExactSizedIterator

I just thought that was not generally correct. For clarity, here is a commit thatt uses Box and implements ExactSizeIterator:

https://github.com/benma/rust-miniscript/commit/iter_pk_exact/#diff-9ca7709271ba89bc7f96b4a9017ee77d4feddf6855b4727ad39fbc0734887199

Box here:

https://github.com/benma/rust-miniscript/commit/iter_pk_exact/#diff-9ca7709271ba89bc7f96b4a9017ee77d4feddf6855b4727ad39fbc0734887199R417

The Box<dyn ...> there is what allows using chain and flat_map in the Taproot iterator and other kinds of iterators for the other arms (without it, there would be a type mismatch between the arms).

The descriptor PkIter also implements ExactSizeIterator. pk_iter() just needs to precompute the number of keys, where I inserted a todo!():

https://github.com/benma/rust-miniscript/commit/iter_pk_exact/#diff-9ca7709271ba89bc7f96b4a9017ee77d4feddf6855b4727ad39fbc0734887199R425

But I can see that this is not very composable or nice, and it's also possible I am completely missing your point 😅

So let's shelve this discussion about Boxes and I'll be looking forward to your implementation.

impl<Pk: MiniscriptKey> ExactSizeIterator for PkIter<'_, Pk> {}

Ok, I understand what you mean now. However, I would definitely not accept code like this. If you are implementing an iterator trait for a struct wrapping an iterator, you should always pass through to the inner iterator. e.g. impl ExactSizeIterator for MyIter { fn len() { self.inner.len() } }.

What you've written here is equivalent { fn len() { self.size_hint().0 } } which will silently become wrong if the inner iterator changes (which won't even be visible in the type system because of the Box<dyn>) ... and worse, the silently wrong code is implicit because it's hidden away in a default impl of a trait method in std. This feels like obfuscated Rust to me.

So let's shelve this discussion about Boxes and I'll be looking forward to your implementation.

Sounds good!

I think the reason this hasn't existed before is that the Ctx parameter on Miniscript pollutes miniscript::PkIter, and has different values for all the different descriptor variants ... so the PkIter struct will need to wind up having an enum of every kind of PkIter in it.

For 12.x I am tempted to just box it and not support any traits except Iterator..