Potential Soundness Issues

[sisy2020]

Hi, I noticed a couple of potential soundness issues in i_triangle 0.26.0. Both seem to rely on crate-internal invariants being upheld.

1. Delaunay::build
   In src/delaunay/delaunay.rs:

pub(crate) fn build(&mut self) {
    let count = self.triangles.len();
    let mut visit_marks = vec![false; count];
    // ...
    let mut triangle = *unsafe { self.triangles.get_unchecked(i) };
    // ...
    for k in 0..3 {
        let neighbor_index = triangle.neighbor_by_order(k);
        if neighbor_index.is_nil() {
            continue;
        }
        let neighbor = *unsafe { self.triangles.get_unchecked(neighbor_index) };
        // ...
    }
}

This assumes that every non-NIL value in DTriangle.neighbors is a valid index into self.triangles. If an internal construction path ever produces a triangle with a neighbor index greater than or equal to self.triangles.len(), the call to get_unchecked(neighbor_index) would be out of bounds.

2. MSliceBuffer::new
   In src/monotone/mslice_buffer.rs:

pub(crate) fn new(vertex_count: usize, slices: &[MSlice]) -> Self {
    let mut vertex_marks = vec![false; vertex_count];
    let mut edges = vec![Edge::EMPTY; slices.len()];

    for (i, slice) in slices.iter().enumerate() {
        unsafe {
            *vertex_marks.get_unchecked_mut(slice.a) = true;
            *vertex_marks.get_unchecked_mut(slice.b) = true;

            let id = Self::id(vertex_count, slice.a, slice.b);
            *edges.get_unchecked_mut(i) = Edge {
                id,
                edge: NIL_INDEX,
                triangle: NIL_INDEX,
            };
        }
    }
    // ...
}

This assumes that both slice.a and slice.b are smaller than vertex_count. Since MSlice::new(a, b) accepts arbitrary endpoint values, an internal caller could potentially pass an endpoint outside the bounds of vertex_marks, making either unchecked write out of bounds.

Thanks for taking a look!

[NailxSharipov]

Hi!

1. The internal logic guarantees that every non NIL neighbor index is less than self.triangles.len(). A NIL neighbor index indicates a boundary edge with no neighboring triangle.

   That said, it would be better to add a debug_assert! here and document this invariant explicitly.

2. slice.a and slice.b are vertex indices and are guaranteed by construction to be less than vertex_count.

   And yes, it would also be better to add debug_assert! checks here, together with a short explanation of the invariant.

Thanks for pointing this out!