Fix UB and add Miri to Github CI

[clubby789]

matrix_graph::extend_flat_square_matrix caused Miri to report UB due to taking two mutable pointers into a slice (

petgraph/src/matrix_graph.rs

Lines 858 to 865 in ffb085f

	if pos + old_node_capacity <= new_pos {
	let old = node_adjacencies[pos..pos + old_node_capacity].as_mut_ptr();
	let new = node_adjacencies[new_pos..new_pos + old_node_capacity].as_mut_ptr();
	// SAFE: new starts at least `old_node_capacity` positions after old.
	unsafe {
	std::ptr::swap_nonoverlapping(old, new, old_node_capacity);
	}

).
This PR fixes that by safely splitting the slices to ensure there is no overlap and that the length is valid, as well as adding Miri to the CI.

[clubby789]

I opted to remove the unsafe block completely and use swap_with_slice - when building in release the assertion is removed completely so the generated code is the same.

[ABorgna]

Nice !

The unsafe block was introduced because it was quite faster than the safe code that was there before (#427 (comment)).
Did you check how the benchmarks compare with HEAD ?

[saethlin]

FYI my usual solution to this is

let ptr = node_adjacencies.as_mut_ptr();
let old = ptr.add(pos);
let new = ptr.add(new_pos);

This has zero overhead, and if anything is faster because it omits the bounds checks. Unclear if those are desired, but you could add them back in explicitly if you want.

[clubby789]

I'm not very experienced with benchmarking but the differences seem negligible:
PR:

test add_100_edges_to_self             ... bench:         255 ns/iter (+/- 15)
test add_100_nodes                     ... bench:      13,001 ns/iter (+/- 544)
test add_5_edges_for_each_of_100_nodes ... bench:         857 ns/iter (+/- 54)
test add_adjacent_edges                ... bench:      22,015 ns/iter (+/- 612)
test add_edges_from_root               ... bench:      22,191 ns/iter (+/- 1,604)
test bigger_edges_in                   ... bench:          52 ns/iter (+/- 5)
test bigger_edges_out                  ... bench:          39 ns/iter (+/- 1)
test bigger_kosaraju_sccs              ... bench:       7,955 ns/iter (+/- 401)
test bigger_neighbors_in               ... bench:          49 ns/iter (+/- 2)
test bigger_neighbors_out              ... bench:          50 ns/iter (+/- 2)
test bigger_tarjan_sccs                ... bench:       4,042 ns/iter (+/- 156)
test full_edges_in                     ... bench:          20 ns/iter (+/- 1)
test full_edges_out                    ... bench:          13 ns/iter (+/- 0)
test full_kosaraju_sccs                ... bench:       1,120 ns/iter (+/- 94)
test full_neighbors_in                 ... bench:          16 ns/iter (+/- 0)
test full_neighbors_out                ... bench:          18 ns/iter (+/- 2)
test full_tarjan_sccs                  ... bench:         612 ns/iter (+/- 20)

HEAD:

test add_100_edges_to_self             ... bench:         249 ns/iter (+/- 10)
test add_100_nodes                     ... bench:      13,058 ns/iter (+/- 986)
test add_5_edges_for_each_of_100_nodes ... bench:         857 ns/iter (+/- 24)
test add_adjacent_edges                ... bench:      21,953 ns/iter (+/- 1,604)
test add_edges_from_root               ... bench:      22,075 ns/iter (+/- 697)
test bigger_edges_in                   ... bench:          51 ns/iter (+/- 3)
test bigger_edges_out                  ... bench:          40 ns/iter (+/- 1)
test bigger_kosaraju_sccs              ... bench:       8,085 ns/iter (+/- 443)
test bigger_neighbors_in               ... bench:          50 ns/iter (+/- 2)
test bigger_neighbors_out              ... bench:          50 ns/iter (+/- 1)
test bigger_tarjan_sccs                ... bench:       4,067 ns/iter (+/- 158)
test full_edges_in                     ... bench:          20 ns/iter (+/- 1)
test full_edges_out                    ... bench:          13 ns/iter (+/- 0)
test full_kosaraju_sccs                ... bench:       1,110 ns/iter (+/- 49)
test full_neighbors_in                 ... bench:          16 ns/iter (+/- 0)
test full_neighbors_out                ... bench:          18 ns/iter (+/- 0)
test full_tarjan_sccs                  ... bench:         613 ns/iter (+/- 41)

From a very brief investigation, I think all three methods end up emitting very similar code as the compiler eliminates checks.

[clubby789]

I switched to using the method suggested by @saethlin since the fully-safe method adds a lot of complexity to the code, and it looks like the bounds checks aren't fully eliminated (I get noticable improvements against HEAD with this version). Added in the bounds checks for debug mode only

[ABorgna]

This is great, thanks !