2024-02-08 20:07:36 +00:00
|
|
|
# ranged_int
|
|
|
|
|
|
|
|
[![Package Version](https://img.shields.io/hexpm/v/ranged_int)](https://hex.pm/packages/ranged_int)
|
|
|
|
[![Hex Docs](https://img.shields.io/badge/hex-docs-ffaff3)](https://hexdocs.pm/ranged_int/)
|
|
|
|
|
2024-02-12 19:50:37 +00:00
|
|
|
Type safe ranged integer operations for Gleam.
|
|
|
|
|
|
|
|
Some features:
|
|
|
|
|
|
|
|
- Builtin types for the most used ranges
|
|
|
|
- Create custom types for your own ranges in a type safe way
|
|
|
|
- Big integer arithmetic to avoid loss of precision
|
2024-02-13 18:58:05 +00:00
|
|
|
- Opt-in support for overflow and underflow for all ranges (with both a minimum and
|
|
|
|
maximum limit)
|
2024-02-12 19:50:37 +00:00
|
|
|
- Partially limited ranges (only a minimum or maximum limit)
|
|
|
|
- Generic ranged integers for cases where ranges are not known at compile time
|
|
|
|
|
2024-02-13 18:58:05 +00:00
|
|
|
## Big integers
|
|
|
|
|
2024-02-12 19:50:37 +00:00
|
|
|
This library uses the [bigi](https://hex.pm/packages/bigi) library for handling big
|
|
|
|
integers. The API operates on big integers and only a few builtin types have helpers for
|
|
|
|
working with regular Gleam `Int`s. This is to ensure correctness on both targets by
|
|
|
|
avoiding the JavaScript
|
|
|
|
[number type limitations](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number#integer_range_for_number).
|
|
|
|
|
|
|
|
When dealing with math operations, it is useful to check the
|
|
|
|
[bigi documentation](https://hexdocs.pm/bigi), as the math operations merely delegate to
|
|
|
|
the bigi math functions.
|
|
|
|
|
|
|
|
## Overflow
|
|
|
|
|
|
|
|
Whenever a ranged integer is created from an unranged big integer, or a math operation
|
|
|
|
is performed on a ranged integer, the result is either a new ranged integer, or
|
|
|
|
overflow. In this context overflow includes both overflow and underflow, i.e. the
|
|
|
|
ranged integer's maximum or minimum limit being broken, respectively.
|
|
|
|
|
|
|
|
If wanted, the resulting `utils.Overflow` type can then be passed on to the
|
|
|
|
`interface.overflow` or `interface.eject` functions to decide how to handle the
|
|
|
|
situation: the former will calculate a new value with the overflow algorithm, and the
|
|
|
|
latter will return an unranged big integer. An example with `ranged_int/builtin/uint8`,
|
|
|
|
where these functions are wrapped:
|
|
|
|
|
|
|
|
```gleam
|
2024-02-18 18:13:50 +00:00
|
|
|
let assert Ok(a) = uint8.from_int(120)
|
2024-02-12 19:50:37 +00:00
|
|
|
let b = bigi.from_int(160)
|
|
|
|
uint8.overflow(uint8.add(a, b)) // Uint8(24)
|
|
|
|
uint8.eject(uint8.add(a, b)) // BigInt(280)
|
|
|
|
```
|
|
|
|
|
|
|
|
### Overflow algorithm
|
|
|
|
|
|
|
|
The overflow algorithm is based on how unsigned integer overflow is done in the C
|
|
|
|
language. In C it is not defined for signed integers, but this library defines it for all
|
2024-02-18 18:13:50 +00:00
|
|
|
ranged integers, using 2's complement for the builtin signed integers. The formula for
|
|
|
|
calculating the overflowed result is
|
2024-02-12 19:50:37 +00:00
|
|
|
|
2024-02-18 18:13:50 +00:00
|
|
|
```
|
|
|
|
(value - min) % amount_of_values + min
|
|
|
|
```
|
|
|
|
|
|
|
|
where `min` is the minimum allowed value in the range, `amount_of_values` is the total
|
|
|
|
amount of allowed values, and `%` is the modulo (not remainder) operation.
|
|
|
|
|
|
|
|
In effect, for types that represent unsigned integers or 2's complement signed integers,
|
|
|
|
this is equivalent to truncating the value to the amount of bits that defines the range.
|
|
|
|
|
|
|
|
It's left up to the user to decide when overflowing makes sense, and to call `overflow`
|
|
|
|
when appropriate.
|
2024-02-12 19:50:37 +00:00
|
|
|
|
|
|
|
## The builtin types
|
|
|
|
|
|
|
|
In the `ranged_int/builtin` namespace there are builtin types for the most popular
|
|
|
|
ranges: unsigned and signed integers from 8 to 128 bits, and an unsigned integer of
|
|
|
|
unlimited size. When implementing your own integer range, you may wish to consult the
|
|
|
|
sources of these implementations as a template.
|
|
|
|
|
|
|
|
## Implementing your own type
|
|
|
|
|
|
|
|
If none of the builtin types match your use case, you can create your own type with
|
|
|
|
custom limits. Creating your own type allows for type safety, for example preventing
|
|
|
|
accidentally passing a regular `Int` in place of your ranged integer, or mixing different
|
|
|
|
kinds of ranged integers in the same `List`.
|
|
|
|
|
|
|
|
Creating your own type requires that the possible limits are known at compile time. If
|
|
|
|
you don't know the limits until runtime, you should take a look at the builtin generic
|
|
|
|
ranged integer.
|
|
|
|
|
|
|
|
### Minimum viable product
|
|
|
|
|
|
|
|
Let's say you want an integer that tracks the years the band
|
|
|
|
[Katzenjammer](<https://en.wikipedia.org/wiki/Katzenjammer_(band)>) was active. It's
|
|
|
|
understandable, those were some good years. Let's make a minimal ranged integer that
|
|
|
|
goes from 2007 to 2015:
|
|
|
|
|
|
|
|
```gleam
|
|
|
|
import bigi.{type BigInt}
|
|
|
|
import ranged_int/interface.{type Interface, Interface}
|
|
|
|
|
|
|
|
const max_limit = 2015
|
|
|
|
|
|
|
|
const min_limit = 2007
|
|
|
|
|
|
|
|
pub opaque type Katzen {
|
|
|
|
Katzen(data: BigInt)
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
This is just a start, and you can't do anything with this yet. But we define the limits
|
|
|
|
and an opaque type to represent our data. The type is opaque to prevent anyone from
|
|
|
|
outside the module touching it, because that would ruin our correctness guarantees.
|
|
|
|
|
|
|
|
Next, let's define the minimal set of functions to operate with the type:
|
|
|
|
|
|
|
|
```gleam
|
|
|
|
pub fn to_bigint(value: Katzen) {
|
|
|
|
value.data
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn limits() {
|
|
|
|
interface.overflowable_limits(
|
|
|
|
bigi.from_int(min_limit),
|
|
|
|
bigi.from_int(max_limit),
|
|
|
|
)
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn from_bigint_unsafe(value: BigInt) {
|
|
|
|
Katzen(data: value)
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
- `to_bigint` converts the ranged integer to an unlimited big integer.
|
|
|
|
- `limits` sets the limits of the integer. There are helper functions in `interface` for
|
|
|
|
constructing these limits.
|
|
|
|
- `from_bigint_unsafe` constructs the value _unsafely_ from an unlimited big integer.
|
|
|
|
This function is for the library's internal use and not for other use, as it breaks the
|
|
|
|
guarantees of the library.
|
|
|
|
|
|
|
|
Finally, we need an _interface_ structure that tells the library how to use your type:
|
|
|
|
|
|
|
|
```gleam
|
|
|
|
pub const iface: Interface(Katzen, interface.Overflowable) = Interface(
|
|
|
|
from_bigint_unsafe: from_bigint_unsafe,
|
|
|
|
to_bigint: to_bigint,
|
|
|
|
limits: limits,
|
|
|
|
)
|
|
|
|
```
|
|
|
|
|
|
|
|
The interface contains references to the aforementioned functions, that the library
|
|
|
|
needs to operate on your integers. The second type parameter defines if your integer can
|
|
|
|
use the [overflow](#overflow) operation: if `interface.NonOverflowable` was passed, the
|
|
|
|
type system would prevent that. Note that overflowing is still opt-in, and must be
|
|
|
|
explicitly called.
|
|
|
|
|
|
|
|
Note that [due to a Gleam bug](https://github.com/gleam-lang/gleam/issues/2178), the
|
|
|
|
functions used in a public constant have to be public, even though `limits` and
|
|
|
|
`from_bigint_unsafe` would be better suited as private. If you define the constant as
|
|
|
|
private and define wrapper functions for all the `interface` API functions (described
|
|
|
|
later), then these functions may also be private.
|
|
|
|
|
|
|
|
Now this module is ready to be used:
|
|
|
|
|
|
|
|
```gleam
|
|
|
|
import gleam/order
|
|
|
|
import bigi
|
|
|
|
import gleeunit/should
|
|
|
|
import ranged_int/interface
|
|
|
|
import ranged_int/utils
|
|
|
|
import mvp
|
|
|
|
|
|
|
|
pub fn mvp_test() {
|
|
|
|
let assert Ok(a) = interface.from_bigint(bigi.from_int(2007), mvp.iface)
|
|
|
|
let assert Ok(b) = interface.from_bigint(bigi.from_int(2009), mvp.iface)
|
|
|
|
let c = interface.compare(a, b, mvp.iface)
|
2024-04-11 15:35:52 +00:00
|
|
|
should.equal(c, order.Lt)
|
2024-02-12 19:50:37 +00:00
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
We can also do math on the integers:
|
|
|
|
|
|
|
|
```gleam
|
|
|
|
pub fn mvp_add_test() {
|
|
|
|
let assert Ok(a) = interface.from_bigint(bigi.from_int(2007), mvp.iface)
|
|
|
|
let b = bigi.from_int(9)
|
|
|
|
let c = interface.math_op(a, b, mvp.iface, bigi.add)
|
2024-02-18 18:13:50 +00:00
|
|
|
should.equal(c, Error(utils.WouldOverflow(bigi.from_int(1))))
|
2024-02-12 19:50:37 +00:00
|
|
|
}
|
2024-02-08 20:07:36 +00:00
|
|
|
```
|
2024-02-12 19:50:37 +00:00
|
|
|
|
|
|
|
Here we see that the addition failed because it would have overflowed the allowed range.
|
|
|
|
|
|
|
|
### Prettifying the API
|
|
|
|
|
|
|
|
Now, `interface.math_op(a, b, mvp.iface, bigi.add)` is really a mouthful. It calls the
|
|
|
|
`interface` module's generic math operation function, passing the operands, the ranged
|
|
|
|
integer's interface, and the math operation itself (from `bigi`). It works, but it's not
|
|
|
|
nice to use, and is prone to mistakes (you could replace `bigi.add` with `bigi.subtract`
|
|
|
|
and the type system wouldn't be able to help you).
|
|
|
|
|
|
|
|
To make the type easier to use, we can wrap the functions of the `interface` module:
|
|
|
|
|
2024-02-08 20:07:36 +00:00
|
|
|
```gleam
|
2024-02-12 19:50:37 +00:00
|
|
|
pub fn from_bigint(value: BigInt) {
|
|
|
|
interface.from_bigint(value, iface)
|
|
|
|
}
|
2024-02-08 20:07:36 +00:00
|
|
|
|
2024-02-12 19:50:37 +00:00
|
|
|
pub fn add(a: Katzen, b: BigInt) {
|
|
|
|
interface.math_op(a, b, iface, bigi.add)
|
|
|
|
}
|
|
|
|
|
|
|
|
pub fn compare(a: Katzen, b: Katzen) {
|
|
|
|
interface.compare(a, b, iface)
|
2024-02-08 20:07:36 +00:00
|
|
|
}
|
|
|
|
```
|
|
|
|
|
2024-02-12 19:50:37 +00:00
|
|
|
This way, the user can call e.g. `mvp.add(a, b)` directly, without having to mess with
|
|
|
|
the interface and the underlying math functions. The API is now nicer and safer to use!
|
|
|
|
Additionally, the interface constant and the `limits` and `from_bigint_unsafe` can be
|
|
|
|
made private, meaning the only way to use the integer is via the functions you choose to
|
|
|
|
implement.
|
|
|
|
|
|
|
|
We can now see that the integer's usage is simpler:
|
|
|
|
|
|
|
|
```gleam
|
|
|
|
import gleam/order
|
|
|
|
import bigi
|
|
|
|
import gleeunit/should
|
|
|
|
import ranged_int/utils
|
|
|
|
import readme/mvp2
|
2024-02-08 20:07:36 +00:00
|
|
|
|
2024-02-12 19:50:37 +00:00
|
|
|
pub fn mvp2_test() {
|
|
|
|
let assert Ok(a) = mvp2.from_bigint(bigi.from_int(2007))
|
|
|
|
let assert Ok(b) = mvp2.from_bigint(bigi.from_int(2009))
|
|
|
|
let c = mvp2.compare(a, b)
|
2024-04-11 15:35:52 +00:00
|
|
|
should.equal(c, order.Lt)
|
2024-02-12 19:50:37 +00:00
|
|
|
}
|
2024-02-08 20:07:36 +00:00
|
|
|
|
2024-02-12 19:50:37 +00:00
|
|
|
pub fn mvp2_add_test() {
|
|
|
|
let assert Ok(a) = mvp2.from_bigint(bigi.from_int(2007))
|
|
|
|
let b = bigi.from_int(9)
|
|
|
|
let c = mvp2.add(a, b)
|
2024-02-18 18:13:50 +00:00
|
|
|
should.equal(c, Error(utils.WouldOverflow(bigi.from_int(1))))
|
|
|
|
should.equal(
|
|
|
|
mvp2.overflow(c)
|
|
|
|
|> mvp2.to_bigint(),
|
|
|
|
bigi.from_int(2007),
|
|
|
|
)
|
2024-02-12 19:50:37 +00:00
|
|
|
}
|
2024-02-08 20:07:36 +00:00
|
|
|
```
|
2024-02-12 19:50:37 +00:00
|
|
|
|
|
|
|
You may wish to check out the sources of the builtin implementations for seeing how they
|
|
|
|
can be done, and for easier copying of the boilerplate.
|