Crystal: Downto with unsigned integers

[gmarcais]

The #downto method behaves like an infinite loop for an unsigned integer and a target value of 0. For example:

UInt16(3).downto(1) { |i| p i } # Good, prints 3, 2, 1
UInt16(3).downto(1).each { |i| p i } # Same with iterator
UInt16(3).downto(0) { |i| p i } # Bad, infinite loop.
UInt16(3).downto(0).each { |i| p i } # Same with iterator.

The first two lines print 3,2,1 as expected. The last two lines do not print 3,2,1,0 as expected, but rather loop back to UInt16::MAX and are infinite loops.

The current code for #downto in the class Int is:

def downto(to, &block : self ->) : Nil
    x = self
    while x >= to
      yield x
      x -= 1
    end
  end

This does not work for an unsigned integer: x -= 1 loops back to the max positive value and is always >= 0. It could be changed to:

def downto(to, &block : self ->) : Nil
  return unless self >= to
  x = self
  yield x
  while x > to
    x -= 1
    yield x
  end
end

Similarly, the DowntotoIterator private to the class Int could be implemented as:

private class DowntoIterator(T, N)
  include Iterator(T)

  @from : T
  @to : N
  @current : T
  @done : Bool

  def initialize(@from : T, @to : N)
    @current = @from
    @done = false
  end

  def next
    return stop if @done
    value = @current
    @done = @current == @to
    @current -= 1 unless @done
    value
  end

  def rewind
    @current = @from
    @done = false
    self
  end
end

[straight-shoota]

This error is actually not specific to unsigned integers but to all types when counting down to the min value. And similarly when counting up to max value.

Implementation wise it is probably easier to just return when x == to inside the loop:

  def downto(to, &block : self ->) : Nil
    return unless self >= to
    x = self
    while true
      yield x
      return if x == to
      x -= 1
   end
  end

[gmarcais]

One more issue: the current implementation of #downto and the proposed new implementation differ from the Ruby version when to > self. That is: 3.downto(5) { |i| p i } prints 3 in Ruby, and nothing in Crystal. Should they agree? Same difference with #upto.

Ruby compatible implementation:

def downto(to, &block : self ->) : NIL
  yield self
  return unless self > to
    x = self
    while true
      x -= 1
      yield x
      return if x == to
    end
  end
end

[straight-shoota]

IMHO Crystal's implementation makes more sense. When you're supposed to count (upwards) from 5 to 3, you wouldn't even start counting the first number because you're already above the target.

[asterite]

Guys, Ruby doesn't behave like that.

[asterite]

https://carc.in/#/r/4wdr

@gmarcais Don't confuse IRB's result with output ;-)

[ysbaddaden]

Yup, in ruby the block is never invoked, but it does return the initial value (3 or 5) when in crystal we return nil.

>> 3.downto(5) { |i| p i }
=> 3
>> 5.upto(3) { |i| p i }
=> 5

[gmarcais]

Oops, my bad. You are correct. Ruby does not invoke the block.

[gmarcais]

Created PR #6678.

[asterite]

There's also a problem with Number#step with signed integers (and I think it can happen with unsigned too): if you give it a by too big, it can overflow and start from negative values:

1.step(to: Int32::MAX - 10, by: 100_000) do |x|
  puts x
end

All of these methods are way more complex than what I originally thought. I think we need to do these kind of things with overflowing checks: if we add/subtract by and it overflows, we stop the iteration. For that I think + and &+ are not enough: we need a property way to add with overflow check and know whether it overflowed without having to raise and catch an exception. I suggest add_with_overflow, subtract_with_overflow, etc.

[asterite]

I'm also thinking 1234567812345678.to_i32 should probably raise on overflow, and/or we should have a way to know whether that overflowed. I don't know how we would implement step if self is an Int32 and by is a large Int64... I'm wondering because the LLVM overflow operations (well, all operations) only work on integers of the same size.

[asterite]

It would be really cool if someone would change the language so that there's a single number type that can hold integers of any size, and in case of overflow automatically convert things to big_int, or where a number could also hold a float type, essentially almost like in Ruby. Maybe it won't be that slow if it's compiled... no idea :-P

But having all of these different integer types and not having type restrictions on any of these operations is a huge mess.

[refi64]

AFAIK automatically sized integers are slow because of all the checks, not because of compiled vs interpreted code.

[straight-shoota]

@asterite I think this just comes down to the same problem as with other math operations and could be solved if the types are restricted to being equal or the argument having a lesser type.

[Sija]

@straight-shoota more about transparent extending types in case of overflows.

[asterite]

Fixed by #6678