There has been a long debate as to which type should be used for indexing, sizes and the like. My understanding is that Mojo wants to be a type-safe language, which implies that some bounds checking is done. Bounds checking could be simplified if an unsigned type was used. This, in turn could lead to underflow issues in some cases, though.
I think that a type whose sign is known at compile time could solve some of the issues. Picture an integer type whose sign is known at compile time. When we use it,
- some operations clearly preserve the sign
- some operations clearly flip the sign
- some operations are ambiguous, requiring an extra check if the sign needs to be known.
I would argue that many operations fall into the first two categories in practice, making it efficient to work with such a type. In the other cases, an elaborate check would be needed anyway. If implemented, IntLiterals would materialize to comptime signed ints, and those would stay in the comptime signed realm as long as possible.
Example
Suppose the type in question was named ComptimeSignedInt[positive: Bool], where positive indicates whether it is a positive value. In a collection it could be used as follows:
comptime PosInt = ComptimeSignedInt[True]
comptime NegInt = ComptimeSignedInt[False]
struct SArray[ElementType: Copyable & Movable, size: PosInt](SSizeable):
var storage: InlineArray[ElementType, Int(size)]
fn __init__(out self, *, fill: ElementType):
self.storage = {fill = fill}
fn __getitem__(ref self, var index: Int) raises -> ref[self.storage] ElementType:
print("Warning: inefficient indexing used.")
if index < 0:
index += Int(size)
if index < 0 or index >= Int(size):
raise Error("Index out of bounds")
return self.storage.unsafe_get(index)
fn __getitem__(ref self, var index: PosInt) raises -> ref[self.storage] ElementType:
if index >= size:
raise Error("Index out of bounds")
return self.storage.unsafe_get(Int(index))
fn __getitem__(ref self, var index: NegInt) raises -> ref[self.storage] ElementType:
if index < -size:
raise Error("Index out of bounds")
return self.storage.unsafe_get(size + index)
fn __slen__(self) -> PosInt:
return size
def main():
arr = SArray[Int_, 10](fill=Int_(0))
print(get_type_name[type_of(len(arr)+1)]())
for i in srange(1, len(arr) + 1):
arr[-i] = i * 10
for i in srange(3, len(arr) - 3):
arr[i + 1] = Int_(100)
print("Array contents:")
for i in srange(len(arr)):
print(arr[i])
In the example above, all indexing operations are efficient. Only srange(3, len(arr) - 3), which gives an iterator with signed values, is a potentially raising operation. This is intended if we decide in favour of bounds checking.
Note that I prefix some builtin names with “S” here to avoid conflicts. Also, I had to introduce another Int_ type to make some overloads unambiguous, but I think this would not be needed if this concept were implemented as a first class feature.
Question
I am sure smarter and more experienced people have thought about this, and that there are good reason why this is not the established way to do things. But why?
Otherwise, I would like to discuss this as a potential solution to the indexing problem and make this an “actual” proposal
Reference implementation
Here is a full refernce implementation to play around with.
from compile.reflection import get_type_name
@register_passable("trivial")
struct Int_(Indexer, Writable):
"""A replacement of Int that is not the default of IntLiteral."""
var value: Int
fn __init__(out self, value: Int):
self.value = value
@implicit
fn __init__(out self, value: ComptimeSignedInt):
self.value = Int(value)
fn __init__(out self, value: UInt):
self.value = Int(value)
fn __add__(self, other: Int) -> Self:
return Self(self.value + other)
fn __add__(self, other: Self) -> Self:
return Self(self.value + other.value)
fn __sub__(self, other: Int) -> Self:
return Self(self.value - other)
fn __sub__(self, other: Self) -> Self:
return Self(self.value - other.value)
fn __mul__(self, other: Int) -> Self:
return Self(self.value * other)
fn __mul__(self, other: Self) -> Self:
return Self(self.value * other.value)
fn __lt__(self, other: Int) -> Bool:
return self.value < other
fn __lt__(self, other: Self) -> Bool:
return self.value < other.value
fn __gt__(self, other: Int) -> Bool:
return self.value > other
fn __gt__(self, other: Self) -> Bool:
return self.value > other.value
fn __le__(self, other: Int) -> Bool:
return self.value <= other
fn __le__(self, other: Self) -> Bool:
return self.value <= other.value
fn __ge__(self, other: Int) -> Bool:
return self.value >= other
fn __ge__(self, other: Self) -> Bool:
return self.value >= other.value
fn __neg__(self) -> Self:
return Self(-self.value)
fn __mlir_index__(self) -> __mlir_type.index:
return self.value.__mlir_index__()
fn write_to(self, mut writer: Some[Writer]):
writer.write(self.value.__repr__())
@register_passable("trivial")
struct ComptimeSignedInt[positive: Bool](Intable, Stringable, Representable, Writable):
var value: UInt
@implicit
@always_inline
fn __init__[value: __mlir_type.`!pop.int_literal`](out self: ComptimeSignedInt[True], var v: IntLiteral[value]) where IntLiteral[value]() >= 0:
self.value = v
@implicit
@always_inline
fn __init__[value: __mlir_type.`!pop.int_literal`](out self: ComptimeSignedInt[False], var v: IntLiteral[value]) where IntLiteral[value]() < 0:
self.value = -v
@implicit
@always_inline
fn __init__(out self: ComptimeSignedInt[True], var v: UInt):
self.value = v
@implicit
@always_inline
fn __init__(out self, var v: Int_) raises:
print("Init from int")
@parameter
if positive:
if v < 0:
raise Error("Cannot initialize positive ComptimeSignedInt with negative value")
self.value = UInt(v)
else:
if v >= 0:
raise Error("Cannot initialize negative ComptimeSignedInt with non-negative value")
self.value = UInt(-v)
@always_inline
fn __init__[have_checked: Bool](out self, var v: UInt) where have_checked:
self.value = v
@always_inline
fn __int__(self) -> Int:
@parameter
if positive:
return Int(self.value)
else:
return -Int(self.value)
@always_inline
fn __neg__(self) -> ComptimeSignedInt[not positive]:
return ComptimeSignedInt[not positive].__init__[True](self.value)
@always_inline
fn __add__(self, other: Self, out result: Self):
result = self
result.value += other.value
@always_inline
fn __sub__(self, other: ComptimeSignedInt[not positive], out result: Self):
result = self
result.value += other.value
@always_inline
fn __iadd__(mut self, other: Self):
self.value += other.value
@always_inline
fn __isub__(mut self, other: ComptimeSignedInt[not positive]):
self.value += other.value
@always_inline
fn __add__(self, other: ComptimeSignedInt[not positive]) -> Int_:
@parameter
if positive:
return Int_(self.value) - Int_(other.value)
else:
return Int_(other.value) - Int_(self.value)
@always_inline
fn __sub__(self, other: Self) -> Int_:
@parameter
if positive:
return Int_(self.value) - Int_(other.value)
else:
return Int_(other.value) - Int_(self.value)
@always_inline
fn __add__(self, other: Int_) -> Int_:
@parameter
if positive:
return other + Int_(self.value)
else:
return other - Int_(self.value)
@always_inline
fn __sub__(self, other: Int_) -> Int_:
@parameter
if positive:
return Int_(self.value) - other
else:
return other + Int_(self.value)
@always_inline
fn add_bounded(self, other: ComptimeSignedInt[not positive]) -> Self:
@parameter
if positive:
if other.value >= self.value:
return Self.__init__[True](0)
else:
if other.value >= self.value:
return Self.__init__[True](1)
return Self.__init__[True](self.value - other.value)
@always_inline
fn sub_bounded(self, other: Self) -> Self:
@parameter
if positive:
if other.value >= self.value:
return Self.__init__[True](0)
else:
if other.value >= self.value:
return Self.__init__[True](1)
return Self.__init__[True](self.value - other.value)
@always_inline
fn __mul__(self, other: Self) -> ComptimeSignedInt[True]:
return other.value * self.value
@always_inline
fn __imul__(mut self, other: ComptimeSignedInt[positive]):
self.value *= other.value
@always_inline
fn __mul__(self, other: Int_) -> Int_:
@parameter
if positive:
return other * Int_(self.value)
else:
return -other * Int_(self.value)
@always_inline
fn __mul__(self, other: ComptimeSignedInt[not positive]) -> ComptimeSignedInt[False]:
return ComptimeSignedInt[False].__init__[True](other.value * self.value)
@always_inline
fn __eq__[other_positive: Bool](self, other: ComptimeSignedInt[other_positive]) -> Bool:
@parameter
if positive != other_positive:
return False
return self.value == other.value
@always_inline
fn __lt__[other_positive: Bool](self, other: ComptimeSignedInt[other_positive]) -> Bool:
@parameter
if positive:
@parameter
if other_positive:
return self.value < other.value
else:
return False
else:
@parameter
if other_positive:
return True
else:
return self.value > other.value
@always_inline
fn __le__[other_positive: Bool](self, other: ComptimeSignedInt[other_positive]) -> Bool:
return self < other or self == other
@always_inline
fn __gt__[other_positive: Bool](self, other: ComptimeSignedInt[other_positive]) -> Bool:
return not (self <= other)
@always_inline
fn __ge__[other_positive: Bool](self, other: ComptimeSignedInt[other_positive]) -> Bool:
return not (self < other)
@always_inline
fn __str__(self) -> String:
@parameter
if positive:
return self.value.__str__()
else:
return "-" + self.value.__str__()
@always_inline
fn __repr__(self) -> String:
return "ComptimeSignedInt(" + self.__str__() + ")"
fn write_to(self, mut writer: Some[Writer]):
writer.write(self.__repr__())
comptime PosInt = ComptimeSignedInt[True]
comptime NegInt = ComptimeSignedInt[False]
trait SSizeable:
fn __slen__(self) -> PosInt:
...
fn len[T: SSizeable](value: T) -> PosInt:
return value.__slen__()
@register_passable("trivial")
struct srange[positive: Bool = True](Iterable, Iterator, Movable):
comptime IteratorType[
iterable_mut: Bool, //, iterable_origin: Origin[iterable_mut]
]: Iterator = Self
comptime Element = ComptimeSignedInt[positive]
var curr: Self.Element
var end: Self.Element
alias step = Self.Element.__init__[True](1)
@always_inline
fn __init__(out self: srange[True], end: Self.Element):
self.curr = 0
self.end = rebind[PosInt](end)
@always_inline
fn __init__(out self, start: ComptimeSignedInt[positive], end: ComptimeSignedInt[positive]):
self.curr = start
self.end = end
@always_inline
fn __iter__(ref self) -> Self.IteratorType[origin_of(self)]:
return self
@always_inline
fn __next__(mut self, out curr: Self.Element):
curr = self.curr
self.curr += self.step
@always_inline
fn __has_next__(self) -> Bool:
return self.curr.value < self.end.value
struct SArray[ElementType: Copyable & Movable, size: PosInt](SSizeable):
var storage: InlineArray[ElementType, Int(size)]
fn __init__(out self, *, fill: ElementType):
self.storage = {fill = fill}
fn __getitem__(ref self, var index: Int) raises -> ref[self.storage] ElementType:
print("Warning: inefficient indexing used.")
if index < 0:
index += Int(size)
if index < 0 or index >= Int(size):
raise Error("Index out of bounds")
return self.storage.unsafe_get(index)
fn __getitem__(ref self, var index: PosInt) raises -> ref[self.storage] ElementType:
if index >= size:
raise Error("Index out of bounds")
return self.storage.unsafe_get(Int(index))
fn __getitem__(ref self, var index: NegInt) raises -> ref[self.storage] ElementType:
if index < -size:
raise Error("Index out of bounds")
return self.storage.unsafe_get(size + index)
fn __slen__(self) -> PosInt:
return size
def main():
arr = SArray[Int_, 10](fill=Int_(0))
print(get_type_name[type_of(len(arr)+1)]())
for i in srange(1, len(arr) + 1):
arr[-i] = i * 10
for i in srange(3, len(arr) - 3):
arr[i + 1] = Int_(100)
print("Array contents:")
for i in srange(len(arr)):
print(arr[i])