Array indexes strong typing

Hello, this ilog function computes the integer logarithm in base 10, I have adapted it from Hacker's Delight:

#![feature(core_intrinsics)]
#![feature(nonzero_leading_trailing_zeros)]

use std::num::NonZeroU32;
use std::intrinsics::assume;
use std::convert::TryFrom;

#[cfg(not(debug_assertions))]
macro_rules! to { ($e:expr, $t:ident) => (($e) as $t) }

#[cfg(debug_assertions)]
macro_rules! to { ($e:expr, $t:ident) => ($t::try_from($e).unwrap()) }

fn ilog(x: u32) -> Option<u32> {
    const TABLE2: [u32; 11] = [1, 10, 100, 1_000, 10_000, 100_000, 1_000_000,
                               10_000_000, 100_000_000, 1_000_000_000, 0];
    const TABLE1: [u32; 33] = [10, 9, 9, 8, 8, 8,
        7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3,
        2, 2, 2, 1, 1, 1, 0, 0, 0, 0];

    let x = NonZeroU32::new(x)?;
    let y = TABLE1[to!{x.leading_zeros(), usize}];
    let yu = to!{y, usize};
    unsafe { assume(yu < TABLE2.len()); }
    Some(y - (x.get().wrapping_sub(TABLE2[yu]) >> 31))
}

(Those to macros are used pervasively in my code as a workaround of a design mistake of as casts).

I have added that assume because LLVM isn't able to avoid a bound test when performing TABLE2[yu] despite all values inside TABLE1 are within the bounds of TABLE2 (it could be related to https://github.com/rust-lang/rust/issues/74014 ).

Later I've seen that in a situation like that I could use a quite different solution, inspired by a feature of the Ada language, that is indexes typed on the size of arrays, that can't generate out of bound errors (here I've added few more features not strictly necessary for ilog, you can ignore them if you want):

#![feature(
    const_evaluatable_checked,
    const_generics,
    const_option,
    const_panic,
    const_trait_impl,
    step_trait,
    step_trait_ext,
    nonzero_leading_trailing_zeros,
)]
#![allow(incomplete_features)]

use std::convert::TryFrom;
use std::num::NonZeroU32;
use std::ops::{Index, RangeInclusive};
use std::iter::Zip;
use std::slice::Iter;

#[cfg(not(debug_assertions))]
macro_rules! to { ($e:expr, $t:ident) => (($e) as $t) }

#[cfg(debug_assertions)]
macro_rules! to { ($e:expr, $t:ident) => ($t::try_from($e).unwrap()) }

const fn is_nonzero(n: usize) -> usize {
    assert!(n != 0);
    n
}


mod idx {
    use std::iter::Step;
    use super::is_nonzero;

    #[derive(Debug, Copy, Clone, PartialOrd, PartialEq)]
    #[repr(transparent)]
    pub struct Idx<const N: usize>(usize);

    impl<const N: usize> Idx<N> where [(); is_nonzero(N)]: {
        pub const fn new(i: usize) -> Option<Idx<N>> {
            if i < N {
                Some(Idx(i))
            } else {
                None
            }
        }

        pub const unsafe fn new_unchecked(i: usize) -> Idx<N> {
            Idx(i)
        }

        pub const fn get(&self) -> usize {
            self.0
        }
    }

    unsafe impl<const N: usize> Step for Idx<N> where [(); is_nonzero(N)]: {
        fn steps_between(start: &Self, end: &Self) -> Option<usize> {
            Some(end.0 - start.0)
        }

        fn forward_checked(start: Self, count: usize) -> Option<Self> {
            Self::new(start.0 + count)
        }

        fn backward_checked(start: Self, count: usize) -> Option<Self> {
            Some(Self(start.0.checked_sub(count)?))
        }
    }
}

use idx::Idx;

const fn is_contained(n: usize, m: usize) -> usize {
    assert!(n <= m);
    n
}

impl<T, const N: usize, const M: usize> Index<Idx<N>> for [T; M]
where [(); is_nonzero(N)]: ,
      [(); is_contained(N, M)]: {
    type Output = T;

    fn index(&self, i: Idx<N>) -> &Self::Output {
        unsafe { self.get_unchecked(i.get()) }
    }
}

trait ArraySpan<const N: usize> {
    fn span(&self) -> RangeInclusive<Idx<N>>;
}

impl<T, const N: usize> const ArraySpan<N> for [T; N]
where [(); is_nonzero(N)]: {
    fn span(&self) -> RangeInclusive<Idx<N>> {
        unsafe {
            Idx::new_unchecked(0) ..= Idx::new_unchecked(N - 1)
        }
    }
}


trait ArrayEnumerate<T, const N: usize> {
    fn enumerate(&self) -> Zip<RangeInclusive<Idx<N>>, Iter<'_, T>>;
}

impl<T, const N: usize> ArrayEnumerate<T, N> for [T; N]
where [(); is_nonzero(N)]: {
    fn enumerate(&self) -> Zip<RangeInclusive<Idx<N>>, Iter<'_, T>> {
        self.span().zip(self.iter())
    }
}

// Add usize::rem_idx e Idx::Div?


fn ilog_new(x: u32) -> Option<u32> {
    const TABLE2: [u32; 11] = [1, 10, 100, 1_000, 10_000, 100_000, 1_000_000,
                               10_000_000, 100_000_000, 1_000_000_000, 0];
    const fn i(x: usize) -> Idx<11> { Idx::new(x).unwrap() }
    const TABLE1: [Idx<11>; 33] = [i(10), i(9), i(9), i(8), i(8), i(8), i(7), i(7), i(7), i(6), i(6),
                                   i(6), i(6), i(5), i(5), i(5), i(4), i(4), i(4), i(3), i(3), i(3),
                                   i(3), i(2), i(2), i(2), i(1), i(1), i(1), i(0), i(0), i(0), i(0)];

    let x = NonZeroU32::new(x)?;
    let y = TABLE1[to!{x.leading_zeros(), usize}];
    Some(to!{y.get(), u32} - (x.get().wrapping_sub(TABLE2[y]) >> 31))
}

(TABLE1 of ilog_new contains 64 bit values while TABLE1 of ilog contains 32 bit values. Idx could also be parametrixed by type to allow smaller types, as Idx<u32, N>.)

I'd like Rust to gain strong typing for array indexing, but in the meantime some of the uses cases could be covered by Idx. Is a type like Idx useful in sufficiently common cases? :slight_smile:

2 Likes

Would a combination of procedural macros and something like int-enum work? Then you could do something very similar to the example for the Index trait in that your array could only be indexed by the generated enum, which guarantees that you cannot use something that is out of bounds. I don't know how efficient the generated code would be, but that is something that would need to be experimented with.

So far I've seen this Idx idea as a toy, but for fun I've tried to use it in more realistic code, short and self-contained. This is a sufficiently efficient solution to an Euler Project problem (https://projecteuler.net/problem=96 with a link to the test data), this solution is efficient also because avoids most heap-allocated data and works with arrays as much as possible (also thanks to the array_chunks feature):

#![feature(default_free_fn, array_chunks)]

use std::default::default;
use std::fs::read;

fn e96() -> u32 {
    const L: usize = 3;
    const SIDE: usize = L * L;
    const SIDE_SQ: usize = SIDE * SIDE;
    const SIDE_8: u8 = SIDE as _;
    const SIDE_32: u32 = SIDE as _;

    type Grid = [[u8; SIDE]; SIDE];
    type V = [u32; SIDE];
    type Squares = [[u32; L]; L];
    type Zeroes = [(usize, usize); SIDE_SQ];

    fn remove_title_lines(bytes: &mut [u8]) -> &[u8] {
        let mut current = 0;
        let mut i = 0;

        while i < bytes.len() {
            match bytes[i] {
                b'G' => {
                    // Skip the title line.
                    i += 1;
                    while i < bytes.len() && bytes[i] != b'\n' {
                        i += 1;
                    }
                },
                b'0' ..= b'9' => {
                    bytes[current] = bytes[i];
                    current += 1;
                },
                _ => {},
            }
            i += 1;
        }

        &bytes[.. current]
    }

    struct Sudoku {
        grid: Grid,
        rows: V,
        cols: V,
        squares: Squares,
        zeroes: Zeroes,
        n_zeroes: usize,
    }

    impl Sudoku {
        fn new(data: &[u8; SIDE_SQ]) -> Option<Self> {
            let mut grid: Grid = default();
            for i in 0 .. SIDE {
                for j in 0 .. SIDE {
                    if let d @ b'0' ..= b'9' = data[i * SIDE + j] {
                        grid[i][j] = d - b'0';
                    } else {
                        return None;
                    }
                }
            }

            let mut rows: V = default();
            let mut cols: V = default();
            let mut squares: Squares = default();
            let mut zeroes: Zeroes = [default(); SIDE_SQ];

            let mut n_zeroes = 0;
            for i in 0 .. SIDE {
                for j in 0 .. SIDE {
                    if grid[i][j] > 0 {
                        rows[i] |= 1 << (grid[i][j] - 1);
                        cols[j] |= 1 << (grid[i][j] - 1);
                        squares[i / L][j / L] |= 1 << (grid[i][j] - 1);
                    } else {
                        zeroes[n_zeroes] = (i, j);
                        n_zeroes += 1;
                    }
                }
            }

            Some(Self { grid, rows, cols, squares, zeroes, n_zeroes })
        }

        fn solve(&mut self) -> Option<u32> {
            let mut best_mask = 0;
            let mut best_index = 0;
            let mut best_num_bits = None;

            for (index, &(i, j)) in self.zeroes[.. self.n_zeroes].iter().enumerate() {
                let mask = self.rows[i] | self.cols[j] | self.squares[i / L][j / L];
                let num_bits = Some(mask.count_ones());
                if num_bits > best_num_bits {
                    best_index = index;
                    best_mask = mask;
                    best_num_bits = num_bits;
                }
            }

            if best_num_bits.is_none() {
                return Some(u32::from(self.grid[0][0]) * 100 +
                            u32::from(self.grid[0][1]) * 10 +
                            u32::from(self.grid[0][2]));
            } else if let Some(SIDE_32) = best_num_bits {
                return None;
            }

            let (i, j) = self.zeroes[best_index];
            self.zeroes[best_index] = self.zeroes[self.n_zeroes - 1];
            self.n_zeroes -= 1;

            for candidate_minus_1 in 0 .. SIDE_8 {
                if (best_mask & (1 << candidate_minus_1)) == 0 {
                    let old_rows = self.rows[i];
                    let old_cols = self.cols[j];
                    let old_squares = self.squares[i / L][j / L];
                    self.rows[i] |= 1 << candidate_minus_1;
                    self.cols[j] |= 1 << candidate_minus_1;
                    self.squares[i / L][j / L] |= 1 << candidate_minus_1;
                    self.grid[i][j] = candidate_minus_1 + 1;
                    if let result @ Some(_) = self.solve() {
                        return result;
                    }
                    self.rows[i] = old_rows;
                    self.cols[j] = old_cols;
                    self.squares[i / L][j / L] = old_squares;
                    self.grid[i][j] = 0;
                }
            }
            self.zeroes[self.n_zeroes] = (i, j);
            self.n_zeroes += 1;
            None
        }
    }

    remove_title_lines(&mut read("p096_sudoku.txt").unwrap())
    .array_chunks()
    .map(|ch| Sudoku::new(ch).unwrap().solve().unwrap())
    .sum()
}

fn main() {
    assert_eq!(e96(), 24_702);
}

Even compiling with aggressive compilation options this code contains a lot (about 15) array bound tests. And many of those lines seem a very good fit for Idx:

let (i, j) = self.zeroes[best_index];
...
let old_rows = self.rows[i];
let old_cols = self.cols[j];
let old_squares = self.squares[i / L][j / L];

So I've applied the Idx (that's a poor's man implementation of a built-in feature of Ada language, that allows to define the type of variables as indexes of specific arrays):

#![feature(
    array_chunks,
    const_assume,
    const_evaluatable_checked,
    const_generics,
    const_option,
    const_panic,
    const_trait_impl,
    core_intrinsics,
    default_free_fn,
    nonzero_leading_trailing_zeros,
    step_trait,
    step_trait_ext,
)]
#![allow(incomplete_features)]

use std::default::default;
use std::fs::read;
use std::ops::{Index, IndexMut, RangeInclusive};
use std::iter::Zip;
use std::slice::Iter;
use std::intrinsics::assume;

const fn is_nonzero(n: usize) -> usize {
    assert!(n != 0);
    n
}

mod idx {
    use std::iter::Step;
    use super::is_nonzero;
    use super::assume;

    #[derive(Debug, Copy, Clone, PartialOrd, PartialEq, Default)]
    #[repr(transparent)]
    pub struct Idx<const N: usize>(usize);

    impl<const N: usize> Idx<N> where [(); is_nonzero(N)]: {
        #[inline(always)]
        pub const fn new(i: usize) -> Option<Idx<N>> {
            if i < N {
                Some(Idx(i))
            } else {
                None
            }
        }

        #[inline(always)]
        pub const unsafe fn new_unchecked(i: usize) -> Idx<N> {
            Idx(i)
        }

        #[inline(always)]
        pub const fn get(&self) -> usize {
            unsafe { assume(self.0 < N); }
            self.0
        }
    }

    unsafe impl<const N: usize> Step for Idx<N> where [(); is_nonzero(N)]: {
        fn steps_between(start: &Self, end: &Self) -> Option<usize> {
            Some(end.0 - start.0)
        }

        fn forward_checked(start: Self, count: usize) -> Option<Self> {
            Self::new(start.0 + count)
        }

        fn backward_checked(start: Self, count: usize) -> Option<Self> {
            Some(Self(start.0.checked_sub(count)?))
        }
    }
}

use idx::Idx;

const fn is_contained(n: usize, m: usize) -> usize {
    assert!(n <= m);
    n
}

impl<T, const N: usize, const M: usize> Index<Idx<N>> for [T; M]
where [(); is_nonzero(N)]: ,
      [(); is_contained(N, M)]: {
    type Output = T;

    #[inline(always)]
    fn index(&self, i: Idx<N>) -> &Self::Output {
        unsafe { self.get_unchecked(i.get()) }
    }
}

impl<T, const N: usize, const M: usize> IndexMut<Idx<N>> for [T; M]
where [(); is_nonzero(N)]: ,
      [(); is_contained(N, M)]: {
    #[inline(always)]
    fn index_mut(&mut self, i: Idx<N>) -> &mut Self::Output {
        unsafe { self.get_unchecked_mut(i.get()) }
    }
}

trait ArraySpan<const N: usize> {
    fn span(&self) -> RangeInclusive<Idx<N>>;
}

impl<T, const N: usize> const ArraySpan<N> for [T; N]
where [(); is_nonzero(N)]: {
    #[inline(always)]
    fn span(&self) -> RangeInclusive<Idx<N>> {
        unsafe {
            Idx::new_unchecked(0) ..= Idx::new_unchecked(N - 1)
        }
    }
}

trait ArrayEnumerate<T, const N: usize> {
    fn enumerate(&self) -> Zip<RangeInclusive<Idx<N>>, Iter<'_, T>>;
}

impl<T, const N: usize> ArrayEnumerate<T, N> for [T; N]
where [(); is_nonzero(N)]: {
    fn enumerate(&self) -> Zip<RangeInclusive<Idx<N>>, Iter<'_, T>> {
        self.span().zip(self.iter())
    }
}

fn e96() -> u32 {
    const L: usize = 3;
    const SIDE: usize = L * L;
    const SIDE_SQ: usize = SIDE * SIDE;
    const SIDE_8: u8 = SIDE as _;
    const SIDE_32: u32 = SIDE as _;

    type Grid = [[u8; SIDE]; SIDE];
    type V = [u32; SIDE];
    type Squares = [[u32; L]; L];
    type IdxS = Idx<SIDE>;
    type Zeroes = [(IdxS, IdxS); SIDE_SQ];

    fn remove_title_lines(bytes: &mut [u8]) -> &[u8] {
        let mut current = 0;
        let mut i = 0;

        while i < bytes.len() {
            match bytes[i] {
                b'G' => {
                    // Skip the title line.
                    i += 1;
                    while i < bytes.len() && bytes[i] != b'\n' {
                        i += 1;
                    }
                },
                b'0' ..= b'9' => {
                    bytes[current] = bytes[i];// 1/5 ##########
                    current += 1;
                },
                _ => {},
            }
            i += 1;
        }

        &bytes[.. current]// 2/5 ##########
    }

    struct Sudoku {
        grid: Grid,
        rows: V,
        cols: V,
        squares: Squares,
        zeroes: Zeroes,
        n_zeroes: usize,
    }

    impl Sudoku {
        fn new(data: &[u8; SIDE_SQ]) -> Option<Self> {
            let mut grid: Grid = default();
            for i in 0 .. SIDE {
                for j in 0 .. SIDE {
                    if let d @ b'0' ..= b'9' = data[i * SIDE + j] {
                        grid[i][j] = d - b'0';
                    } else {
                        return None;
                    }
                }
            }

            let mut rows: V = default();
            let mut cols: V = default();
            let mut squares: Squares = default();
            let mut zeroes: Zeroes = [default(); SIDE_SQ];

            let mut n_zeroes = 0;
            for i in rows.span() {
                for j in cols.span() {
                    if grid[i][j] > 0 {
                        rows[i] |= 1 << (grid[i][j] - 1);
                        cols[j] |= 1 << (grid[i][j] - 1);
                        squares[i.get() / L][j.get() / L] |= 1 << (grid[i][j] - 1);
                    } else {
                        zeroes[n_zeroes] = (i, j);// 3/5 ##########
                        n_zeroes += 1;
                    }
                }
            }

            Some(Self { grid, rows, cols, squares, zeroes, n_zeroes })
        }

        fn solve(&mut self) -> Option<u32> {
            let mut best_mask = 0;
            let mut best_index = Idx::<SIDE_SQ>::default();
            let mut best_num_bits = None;

            for (index, &(i, j)) in self.zeroes.enumerate().take(self.n_zeroes) {//SLOW
                let mask = self.rows[i] | self.cols[j] | self.squares[i.get() / L][j.get() / L];
                let num_bits = Some(mask.count_ones());
                if num_bits > best_num_bits {
                    best_index = index;
                    best_mask = mask;
                    best_num_bits = num_bits;
                }
            }

            if best_num_bits.is_none() {
                return Some(u32::from(self.grid[0][0]) * 100 +
                            u32::from(self.grid[0][1]) * 10 +
                            u32::from(self.grid[0][2]));
            } else if let Some(SIDE_32) = best_num_bits {
                return None;
            }

            let (i, j) = self.zeroes[best_index];
            self.zeroes[best_index] = self.zeroes[self.n_zeroes - 1];// 4/5 ##########
            self.n_zeroes -= 1;

            for candidate_minus_1 in 0 .. SIDE_8 {
                if (best_mask & (1 << candidate_minus_1)) == 0 {
                    let old_rows = self.rows[i];
                    let old_cols = self.cols[j];
                    let old_squares = self.squares[i.get() / L][j.get() / L];
                    self.rows[i] |= 1 << candidate_minus_1;
                    self.cols[j] |= 1 << candidate_minus_1;
                    self.squares[i.get() / L][j.get() / L] |= 1 << candidate_minus_1;
                    self.grid[i][j] = candidate_minus_1 + 1;
                    if let result @ Some(_) = self.solve() {
                        return result;
                    }
                    self.rows[i] = old_rows;
                    self.cols[j] = old_cols;
                    self.squares[i.get() / L][j.get() / L] = old_squares;
                    self.grid[i][j] = 0;
                }
            }
            self.zeroes[self.n_zeroes] = (i, j);// 5/5 ##########
            self.n_zeroes += 1;
            None
        }
    }

    remove_title_lines(&mut read("p096_sudoku.txt").unwrap())
    .array_chunks()
    .map(|ch| Sudoku::new(ch).unwrap().solve().unwrap())
    .sum()
}

fn main() {
    assert_eq!(e96(), 24_702);
}

This was a success, the code is still simple and readable as before, but now I think there are about only 5 array bound tests left. Unfortunately this line slows down the code:

for (index, &(i, j)) in self.zeroes.enumerate().take(self.n_zeroes) {//SLOW

So I have had to restore index as a normal usize, so the code has now about 7 array bound tests. And it's about 5% faster than the original version. A better built-in implementation of this idea should allow to leave only 5 array bound tests. Such tests slow down code and introduce possible panics. And no-panic code is a worthy goal to desire, even if those tests are invisible it's good to have code that has being mechanically verified as safer.

The remaining 5 array bound tests can be removed with preconditions/invariants/postconditions that someday I'd like to see as built-in features of Rust core language. In particular it should be sufficiently easy to write down invariants for the remove_title_lines to verify that the current index is always <= i, and i is always in-bound.

Currently LLVM is able to remove the first array bound test inside remove_title_lines if you replace the loop test with:

while i < bytes.len() and j < bytes.len() {

But currently this is not an improvement because it slows down code. In future LLVM will probably be able to remove that test even with this loop test (see https://github.com/rust-lang/rust/issues/80075 https://bugs.llvm.org/show_bug.cgi?id=48544 ):

while i < bytes.len() and j <= i {

Also this line is probably easy to demonstrate panic-less because n_zeroes gets incremented at most every time the Cartesian product of the two loops:

zeroes[n_zeroes] = (i, j);// 3/5 ##########

In this code there's also an example of code with an index that can't go past the array length, so it can't be memory-unsafe, but it could be still logically wrong, because zeroes is an array that has meaning only for its first n_zeroes items (this was done to avoid heap-allocated memory). So here verifying both lack of out of bound indexing and logical out of bounds is a bit different. If you use a Vec and you grow it only as much as necessary, the logically used part of the sequence is as long as the Vec.

Later there are instructions to increment and decrement self.n_zeroes in the recursive calls, this makes the in-bound demonstration a bit more elaborate. In the end you can decide how much you want to work to remove array bound tests in your code.

There is little to no need for nightly features, not even for const generics, as long as you know the bounds beforehand, they are static, and unique. I've already implemented this: https://docs.rs/index-ext/0.0.2/index_ext/tag/index.html and tested it to elide the bounds checks. Some const-fn features would help because currently a lot of methods are not const qualified due to having bounds but that's about it. The same system can tolerate some dynamic bounds (see: Generative) but keep in mind each introduces a new type-level parameter. Since the generative approach of dynamic bounds relies on the inability to name a precise type, you can't store indices of dynamic bounds in structures—for static bounds it's not a problem of course.

In this part of the code:

let mut zeroes: Zeroes = [default(); SIDE_SQ];
let mut n_zeroes = 0;
for i in rows.span() {
    for j in cols.span() {
        if grid[i][j] > 0 {
            rows[i] |= 1 << (grid[i][j] - 1);
            cols[j] |= 1 << (grid[i][j] - 1);
            squares[i.get() / L][j.get() / L] |= 1 << (grid[i][j] - 1);
        } else {
            zeroes[n_zeroes] = (i, j); // Bound test.
            n_zeroes += 1;
        }
    }
}

I think we can avoid another array bound test with a special Cartesian product and an enumerate that includes a test:

let mut zeroes: Zeroes = [default(); SIDE_SQ];
let mut n_zeroes = 0;
for (idx, (i, j), test) in cartesian_product_idx(rows.span(), cols.span())
                           .enumerate_if(|&(i, j)| grid[i][j] == 0) {
    if test {
        zeroes[idx] = (i, j);
        n_zeroes = idx.get() + 1;
    } else {
        rows[i] |= 1 << (grid[i][j] - 1);
        cols[j] |= 1 << (grid[i][j] - 1);
        squares[i.get() / L][j.get() / L] |= 1 << (grid[i][j] - 1);
    }
}

I haven't implemented it, but I suspect the code gets slower. enumerate_if is another example of code pattern that could be fit inside the framework of fixed size indexes.

I've tried in another example code, an old Advent Of Code solution, here it gives about 10% speedup (and the code is still memory safe):

use std::io::{ BufRead, BufReader };
use std::fs::File;

fn main() {
    const MAX: usize = 1_000;
    let mut lights = [[false; MAX]; MAX];
    type IDX = Idx::<MAX>;

    let parse_two = |part: &str| {
        let mut two = part.split(',');
        (IDX::new(two.next().unwrap().parse::<usize>().unwrap()).unwrap(),
         IDX::new(two.next().unwrap().parse::<usize>().unwrap()).unwrap())
    };

    for row in BufReader::new(File::open("input128.txt").unwrap())
               .lines()
               .map(Result::unwrap) {
        let mut parts = row.split_ascii_whitespace().rev().take(3);
        let (x2, y2) = parse_two(parts.next().unwrap());
        parts.next().unwrap();
        let (x1, y1) = parse_two(parts.next().unwrap());

        if row.starts_with("toggle") {
            for x in x1 ..= x2 {
                for y in y1 ..= y2 {
                    lights[x][y] = !lights[x][y];
                }
            }
        } else if row.starts_with("turn off") {
            for x in x1 ..= x2 {
                for y in y1 ..= y2 {
                    lights[x][y] = false;
                }
            }
        } else if row.starts_with("turn on") {
            for x in x1 ..= x2 {
                for y in y1 ..= y2 {
                    lights[x][y] = true;
                }
            }
        } else {
            println!("{}", row);
        }
    }

    let result = lights
                 .iter()
                 .map(|row| row.iter()
                 .copied()
                 .map(u32::from).sum::<u32>())
                .sum::<u32>();
    println!("{}", result);
}