Implement Ranges in Rib

[afsalthaj]

Steps to follow

Define the syntax, and write parsers for the following

0..10;

This corresponds to Range

which iterates from 0 until 10 , and an optional support for inclusion

0..=10

This corresponds to RangeInclusive.

We can also support for infinite variables with open-ended support

let range = 0..

This corresponds to RangeFrom

We support full range using

..

and corresponds to RangeFull

Optionally, we can support RangeTo and RangeToInclusive

..2;

..=2;

Ranges shouldn't be considered as a mere syntax sugar for list, as ranges can be lazily evaluated saving memory and computation.
Ranges can be used in for comprehensions (except RangeTo), and can be used select_index in list as an example
For this reason, we are not going to convert this to list

Map it to the following Expr

Range can be considered as an expr, making it easier to support anything which Expr is able to do.

let x = foo();

let y = bar(); 

let range = x..=y;

// lazily evaluated
for i in range {
   if i < 5 {
        baz(i + 5);
   }
}

or

 let x: list<u32> = [1, 2, 3, 4,  5, 6]
 
 let y: list<u32> = x[2..5]
 // [3, 4, 5]
 

and therefore, the most natural next step is to add these terms in Expr language

enum Expr {
   ..... 
   Range(Range)
}

enum Idx {
   Number(usize),
   Range(Range)
}

enum Range {
   Range {
       from: Expr
        to: Expr
   }
   RangeInclusive {
     from: Expr
     to: Expr
   }
   
   RangeFrom {
      start: Expr
   }
   
   RangeTo {
     end: Expr
   }
   
   RangeToInclusive {
     end: Expr
   }
   
   RangeFull
}

Handle Range in each phases of type inference

See this code

 pub fn infer_types(
        &mut self,
        function_type_registry: &FunctionTypeRegistry,
    ) -> Result<(), Vec<String>> {
        self.infer_types_initial_phase(function_type_registry)?;
        self.infer_call_arguments_type(function_type_registry)
            .map_err(|x| vec![x])?;
        type_inference::type_inference_fix_point(Self::inference_scan, self)
            .map_err(|x| vec![x])?;

        self.check_types(function_type_registry)
            .map_err(|x| vec![x])?;
        self.unify_types()?;
        Ok(())
    }

We need to handle range in each of these phases, and each of the sub phases within them. Example: initial phase has 5 sub phases in it. The inference fix point is defined for infer_scan and this has the most number of phases such type_push_down and type_pull_up.

Please go through each one of them and see how ranges can be compiled. Return compilation errors in any of these phases only if we cannot continue processing phases, otherwise leave it to type checker. Example : let x = [a, b, c, d]; let range = x..10; is wrong. While it sounds simple, it is almost difficult to infer "early" that this expr is wrong.

Handle Ranges in type checker

Type checker was a late addition and this may not capture all the errors, making it difficult for unification. However, any new additions into Rib should have a corresponding "handling" in type checker phase. As we go we will add more checks in type check phase, which is the primary entry point to better error messages.

Write tests for parser, type inference phases, and compilation phases for Ranges

Write basic tests for ranges and it should have both positive and negative tests.

Write Interpreter for Ranges

Interpreter converts Rib Expr to Rib Byte Code which is a collection of IR.
We have already handled iterative approach for handling list, and to a great extent, we believe this can be reused for ranges for lazily evaluating them, especially these IRs

 CreateSink(AnalysedType),
 AdvanceIterator,
 PushToSink, 
 SinkToList,

Interpretation of range (especially in the context of list comprehension) should mostly be the above IRs. During the real implementation, we will see if anything else would come in.

This type of lazy evaluation is already done for list comprehension.

With tests, ensure that a full range is not computed in usecases where it doesn't need to be computed. Example:

// lazily evaluated
for i in range {
   if i < 5 {
        baz(i + 5);
   }
}