[stdlib] Add `reversed`

[helehex]

Adds an initial implementation of reversed(), for getting a reversed iterator of a range or list.

This isn't meant to be final, since iterators are not fully worked out yet, but it works for now.

Changes:

• Added submodule /builtin/reversed.mojo
• Added function reversed()
• Added trait ReversibleRange
• Implemented ReversibleRange for ranges
• Added method __reversed__() in List
• Changed _ListIter to allow for backwards iteration
• Added tests for ranges and reversed list iterator
• Fixed original ranges with negative size not passing the new tests

[helehex]

oups i had a premature submit

[helehex]

The fix for ranges having negative length is mostly unnecessary since it never really matters in practice, so that could be changed back to avoid the extra operations. Just have to remove the edge case section of test_range_len() in test_range.mojo aswell.

[helehex]

_StridedRangeIterator now has a __iter__() method which returns itself. So reversed(range(...)) behaves as expected with for loops.

Somehow i missed that when testing, because i started off by having reversed() return a non iterator strided range.

[helehex]

that looping test was a little excessive, it makes more sense to check the sums of both ranges.

[helehex]

It occurred to me that i never checked this with the @unroll decorator, so i checked and everything seems to work good

[jayzhan211]

As a follow-up, we can go implement reverse iterator support for Set and Dict, right? I'm happy to create some GitHub issues for that if anyone is interested in working on that.

I'm interested to help on Set and Dict.

[helehex]

ok i added the suggestions, and moved all the reversed range tests into one function (it was kind of split before)

[JoeLoser]

ok i added the suggestions, and moved all the reversed range tests into one function (it was kind of split before)

Merged! Thanks so much for this great contribution — we really appreciate it! 🎉

[lattner]

This is great, thank you!