Add a Range<T: Integer> type and allow in for-loop

[turbolent]

• Add a new built-in type Range:

  struct Range<T: Integer> {
     let start: T
     let endInclusive: T
  }
  

• Add support for iterating over Range in for-in statements

Tasks

Beta Give feedback

1. Disallow covariant subtyping in checker #2885
   Technical Debt +1
   
2. Make checkParameterizedTypeIsInstantiated recursive #2884
   Feedback Technical Debt +2
   
3. Fix incorrect type inference for InclusiveRange #2886
   Bug +1
   
4. Support storing InclusiveRange in Account storage #2870
   Feedback Technical Debt +2
   
5. Improve the smallIntegerValueCache added during InclusiveRange implementation #2871
   Feedback Technical Debt +2
   

[turbolent]

Before starting an implementation, we should discuss the design and publish a proper design document, potentially a FLIP.

[bluesign]

Maybe it is good time to expose built in interfaces (comparable, enumerable etc) to Cadence. Also ‘step’ here can be useful too. ( reverse ranges especially)

[darkdrag00nv2]

publish a proper design document, potentially a FLIP.

Ack, will write up a FLIP. I'm sharing my proposal below but happy to write a FLIP if we want to exclusively discuss on the FLIP itself.

Here is what Kotlin does:

Forward range - rangeTo on each type and the .. shorthand operator

for ( num in 1.rangeTo(10)) {
     println(num)
}

for ( num in 1..10) {
     println(num)
}

for ( num in 1.rangeTo(10) step 2) {
     println(num)
}

for ( num in 1..10 step 2) {
     println(num)
}

Reverse range - downTo operator

for ( num in 10 downTo 1) {
     println(num)
}

for ( num in 10 downTo 1 step 2) {
     println(num)
}

Here is what I would like to propose for Cadence:

1. Forward range can use upTo and .. operator.
2. Reverse range can use downTo

I believe using upTo would be more consistent that using rangeTo in the way Kotlin does.

struct Range<T: Integer> {
   let start: T
   let endInclusive: T
   let step: T  // Only positive values allowed. Default = 1.
}

Examples:

A) With default step and forward direction

for x in 1..6 {
  // do something
}

for x in 1 upTo 6 {
  // do something
}

Will iterate for x = 1, 2, 3, 4, 5, 6.

B) With custom step and forward direction

for x in 1..6 step 2 {
  // do something
}

for x in 1 upTo 6 step 2 {
  // do something
}

Will iterate for x = 1, 3, 5.

C) With default step and reverse direction

for x in 6 downTo 1 {
  // do something
}

Will iterate for x = 6, 5, 4, 3, 2, 1.

D) With custom step and reverse direction

for x in 6 downTo 1 step 2 {
  // do something
}

Will iterate for x = 6, 4, 2.

[turbolent]

It might be a good idea to include the concept of a step, but for the concept of a range, that seems a bit odd.

For example, in Kotlin, Swift, and Rust, ranges do not have a step.

Instead, some languages have a separate concept for progression, e.g. Kotlin has Progression, and Swift has StrideThrough. It looks like Rust has the concept of a "wrapper iterator" that allows stepping, StepBy.

Maybe we can start with a simple Range, and then follow up with a progression type.

[bluesign]

Are we planning ranges to be Values? If so we also need to discuss about the API they will have.

[turbolent]

@bluesign Yes, see the description

[darkdrag00nv2]

Kotlin ranges only have two member functions:

1. contains<T>(value: T): Check if T belongs in the Range
2. isEmpty(): Checks if the Range is empty

They inherit a lot of functions from Iterable such as any, all, distinct, drop, filter, ... but I think if we wish to support these, they should first be added in Array. So may be we should only add the above two functions in Range for now.

[bluesign]

I think we need to expose somehow; next() or similar functions as this is iterator. I am thinking maybe more python way, but range , stride etc feels more like generators to me. contains is pretty cool. isEmpty probably can be replaced with length.

[darkdrag00nv2]

For example, in Kotlin, Swift, and Rust, ranges do not have a step.

@turbolent Actually Range in Kotlin does have a step. They are just always set to 1 but they are publicly accessible. For example IntRange is also an IntProgression with step set to 1.

val r = 1..10 // this creates a IntRange
val s = 1..10 step 10 // this creates a IntProgression

println(r.step) // prints 1

May be we can also do the same i.e Range can be a Progression with step equal to 1.

[SupunS]

This issue can now be closed as completed, since the feature was added in the following PRs:

• Introduce InclusiveRange<T: Integer> type #2523
• Allow InclusiveRange<T> in a for-in loop #2892

The remaining improvements #2886 and #2870, depend on some general improvements to the Cadence checker and interpreter, hence would need to be addressed separately, and don't need to be part of this issue.