Rust Borrow-Checker und Vektor-Manipulation

Compilerfehler: Vektor-Manipulation

Programm 1:

/// Entfernt alle Nullen direkt aus einem Vektor von Ganzzahlen.
fn remove_zeros(v: &mut Vec<i32>) {
    for (i, t) in v.iter().enumerate().rev() {
        if *t == 0 {
            v.remove(i);
            v.shrink_to_fit();
        }
    }
}

Wenn Sie versuchen würden, diese Funktion zu kompilieren, welche der folgenden Beschreibungen trifft am besten auf den Compilerfehler zu, den Sie erhalten würden?

1. v.remove(i) kann v nicht als mutabel borgen

2. t kann nicht dereferenziert werden, während i lebt

3. v.iter() kann nicht auf einer mutablen Referenz aufgerufen werden

4. v lebt nicht lange genug, um v.remove(i) aufzurufen

Prüfen

Die Funktion v.iter() borgt einen Vektor v für die Dauer der For-Schleife unveränderlich. v.remove(i) benötigt jedoch eine mutable Referenz auf v. Daher kann v.remove(i) v nicht als mutabel borgen, da dies mit dem Iterator in Konflikt stünde.

---

Undefined Behavior bei Vektor-Manipulation

Programm 1:

/// Entfernt alle Nullen direkt aus einem Vektor von Ganzzahlen.
fn remove_zeros(v: &mut Vec<i32>) {
    for (i, t) in v.iter().enumerate().rev() {
        if *t == 0 {
            v.remove(i);
            v.shrink_to_fit();
        }
    }
}

Normalerweise gibt der Compiler beim Versuch, diese Funktion zu kompilieren, den folgenden Fehler zurück:

error[E0502]: cannot borrow `*v` as mutable because it is also borrowed as immutable
 --> test.rs:5:13
  |
3 |     for (i, t) in v.iter().enumerate().rev() {
  |                   --------------------------
  |                   |
  |                   immutable borrow occurs here
  |                   immutable borrow later used here
4 |         if *t == 0 {
5 |             v.remove(i);
  |             ^^^^^^^^^^^ mutable borrow occurs here

Angenommen, der Compiler hätte diese Funktion NICHT abgelehnt. Welche (falls zutreffend) der folgenden Programme würden (1) den Compiler passieren und (2) möglicherweise undefiniertes Verhalten verursachen, wenn sie ausgeführt werden? Markieren Sie jedes Programm, das beide Kriterien erfüllt, ODER markieren Sie „Keines dieser Programme“, wenn keines davon zutrifft.

1. Keines dieser Programme

2. let mut v = vec![5, 5, 0];
   remove_zeros(&mut v);
   println!("{:?}", v);

3. let mut v = vec![1, 2, 0, 3];
   remove_zeros(&mut v);

4. let mut v = vec![1; 100];
   remove_zeros(&mut v);

Prüfen

Um die Speichersicherheit zu verletzen, muss remove_zeros mit einem Vektor aufgerufen werden, der eine Null nach dem ersten Element enthält. Der Aufruf von v.shrink_to_fit() wird Speicher freigeben, der dem Vektor gehört (aufgrund der Größenänderung), was den Iterator v.iter() invalidiert, der einen Zeiger auf die alten Daten enthält. Beachten Sie, dass das Lesen des Vektors v nach dem Aufruf von remove_zeros für die Sicherheitsverletzung nicht wesentlich ist, da das Problem intern in remove_zeros liegt.

---

Vektor-Manipulation: Korrekte Fixes

Programm 1:

/// Entfernt alle Nullen direkt aus einem Vektor von Ganzzahlen.
fn remove_zeros(v: &mut Vec<i32>) {
    for (i, t) in v.iter().enumerate().rev() {
        if *t == 0 {
            v.remove(i);
            v.shrink_to_fit();
        }
    }
}

Welche der folgenden Korrekturen (gelb hervorgehoben) erfüllt diese drei Kriterien am besten:

1. Die korrigierte Funktion besteht den Rust-Compiler,
2. Die korrigierte Funktion bewahrt die Absicht des ursprünglichen Codes, und
3. Die korrigierte Funktion führt keine unnötigen Ineffizienzen ein

1. fn remove_zeros(v: `[Vec<i32>]`) {
   for (i, t) in v.iter().enumerate().rev() {
   if *t == 0 {
       v.remove(i);
       v.shrink_to_fit();
   }
   }
   }

2. fn remove_zeros(v: `[&]`Vec<i32>) `[-> Vec<i32>]` {
   `[let mut new_vec = Vec::new();]`
   for (i, t) in v.iter().enumerate().rev() {
   if *t `[!=]` 0 {
       `[new_vec.push(*t)]`
   }
   }
   `[new_vec]`
   }

3. fn remove_zeros(v: &mut Vec<i32>) {
   for (i, t) in v`[.clone()]`.iter().enumerate().rev() {
   if *t == 0 {
       v.remove(i);
       v.shrink_to_fit();
   }
   }
   }

4. fn remove_zeros(v: &mut Vec<i32>) {
   for `[i in (0 .. v.len()).rev()]` {
   if `[v[i]]` == 0 {
       v.remove(i);
       v.shrink_to_fit();
   }
   }
   }

Prüfen

Jede Strategie, die die Allokation eines neuen Vektors erfordert, entweder über Vec::clone oder Vec::new, erfordert unnötige zusätzliche Allokation. Daher ist die einfachste funktionierende Strategie, nur über die Indizes 0 .. v.len() zu iterieren, was v nicht borgt. Wir tun dies in umgekehrter Reihenfolge, um das Entfernen fehlender Indizes zu vermeiden.

Wie bei Problem 1 ist die idiomatischste Strategie tatsächlich die Verwendung einer eingebauten Funktion, die wir noch nicht besprochen haben, Vec::retain. Diese Funktion behält nur Elemente in einem Vektor, die ein Prädikat erfüllen, tut dies aber mit höherer Speichereffizienz.

---

Compilerfehler: Doppeltes mutables Borgen

Programm 2:

/// Kehrt die Elemente eines Vektors direkt um
fn reverse(v: &mut Vec<String>) {
    let n = v.len();
    for i in 0 .. n / 2 {
        std::mem::swap(&mut v[i], &mut v[n - i - 1]);
    }
}

Wenn Sie versuchen würden, dieses Programm zu kompilieren, welche der folgenden Beschreibungen trifft am besten auf den Compilerfehler zu, den Sie erhalten würden?

1. kann v nicht zweimal mutabel borgen für v[i] und v[n - i - 1]

2. kann v nicht als unveränderlich für v.len() borgen, wenn v ein mutables Borgen ist

3. kann ein Element v[i] eines mutablen Vektors nicht mutabel borgen

Prüfen

Der Compiler berücksichtigt nicht den spezifischen Wert der Indizes, die für den Zugriff auf ein Array verwendet werden, daher wird angenommen, dass &mut v[i] und &mut v[n - i - 1] möglicherweise auf dasselbe Element verweisen. Daher erhalten wir einen Fehler, bei dem v nicht zweimal mutabel geborgt werden kann.

---

Kein Undefined Behavior bei Vektor-Umkehrung

Programm 2:

/// Kehrt die Elemente eines Vektors direkt um
fn reverse(v: &mut Vec<String>) {
    let n = v.len();
    for i in 0 .. n / 2 {
        std::mem::swap(&mut v[i], &mut v[n - i - 1]);
    }
}

Normalerweise gibt der Compiler beim Versuch, diese Funktion zu kompilieren, den folgenden Fehler zurück:

error[E0499]: cannot borrow `*v` as mutable more than once at a time
 --> test.rs:5:40
  |
5 |         std::mem::swap(&mut v[i], &mut v[n - i - 1]);
  |         --------------      -          ^ second mutable borrow occurs here
  |         |                   |
  |         |                   first mutable borrow occurs here
  |         first borrow later used by call

Angenommen, der Compiler hätte diese Funktion NICHT abgelehnt. Welche (falls zutreffend) der folgenden Programme würden (1) den Compiler passieren und (2) möglicherweise undefiniertes Verhalten verursachen, wenn sie ausgeführt werden? Markieren Sie jedes Programm, das beide Kriterien erfüllt, ODER markieren Sie „Keines dieser Programme“, wenn keines davon zutrifft.

1. let mut v = vec![String::from("a"), String::from("b")];
   reverse(&mut v);

2. let mut v = vec![String::from("a"), String::from("b")];
   let x = &v[0];
   reverse(&mut v);
   println!("{x}");

3. Keines dieser Programme

4. let mut v = vec![String::from("a"), String::from("b")];
   reverse(&mut v);
   println!("{:?}", v);

Prüfen

Diese Funktion kann keine Speichersicherheitsverletzung verursachen, da i != n - i - 1 für alle i gilt, sodass die beiden mutablen Referenzen immer auf verschiedene Elemente verweisen. Beachten Sie, dass das Programm let x = &v[0] nicht kompilieren würde, da Rusts Borrow-Checker den Aufruf von reverse nicht zulassen würde, solange x lebt.

---

Vektor-Umkehrung: Effiziente Korrektur

Programm 2:

/// Kehrt die Elemente eines Vektors direkt um
fn reverse(v: &mut Vec<String>) {
    let n = v.len();
    for i in 0 .. n / 2 {
        std::mem::swap(&mut v[i], &mut v[n - i - 1]);
    }
}

Welche der folgenden Korrekturen (gelb hervorgehoben) erfüllt diese drei Kriterien am besten:

1. Die korrigierte Funktion besteht den Rust-Compiler,
2. Die korrigierte Funktion bewahrt die Absicht des ursprünglichen Codes, und
3. Die korrigierte Funktion führt keine unnötigen Ineffizienzen ein

1. fn reverse(v: &mut Vec<String>) {
   let n = v.len();
   for i in 0 .. n / 2 {
   `[let p1 = &mut v[i] as *mut String;]`
   `[let p2 = &mut v[n - i - 1] as *mut String;]`
   `[unsafe { std::ptr::swap_nonoverlapping(p1, p2, 1); }]`
   }
   }

2. fn reverse(v: &mut Vec<String>) {
   let n = v.len();
   `[let mut v2 = v.clone();]`
   for i in 0 .. n / 2 {
   std::mem::swap(&mut v[i], &mut `[v2]`[n - i - 1]);
   }
   }

3. fn reverse(v: &mut Vec<String>) {
   let n = v.len();
   for i in 0 .. n / 2 {
   `[let s1 = v[i].clone();]`
   `[let s2 = v[n - i - 1].clone();]`
   `[v[i] = s2;]`
   `[v[n - i - 1] = s1;]`
   }
   }

4. fn reverse(v: `[&Vec<String>]`) -> `[Vec<String>]` {
   let n = v.len();
   `[let mut v2 = Vec::new();]`
   for _ in 0 .. `[n]` {
   `[v2.push(v.pop().unwrap());]`
   }
   `[v2]`
   }

Prüfen

In einer Situation, in der der Borrow-Checker eine Operation ablehnt, die tatsächlich sicher ist und keine Umgehungsmöglichkeit bietet, ist unsicherer Code manchmal akzeptabel, wenn es entscheidend ist, Allokationen zu vermeiden. In diesem speziellen Fall sollten Sie tatsächlich Vec::swap verwenden, das intern mit intensiv getestetem unsafe-Code implementiert ist, ähnlich dem obigen Code. Aber im Allgemeinen, wenn die Standardbibliothek Ihren Anwendungsfall nicht unterstützt, kann unsafe bei korrekter Verwendung akzeptabel sein.

---