Wie sicher sind schnelle Sammlungen bei Verwendung ungültiger Iteratoren/Indizes?

Question

Ich sehe nicht viele Informationen in der swift stdlib-Referenz. Zum Beispiel sagt Dictionary, dass bestimmte Methoden (wie Entfernen) Indizes ungültig machen, aber das ist es.

Für eine Sprache selbst „sicher“ zu nennen, muss es eine Lösung für die klassischen C++ footguns:

1. in einem Vektor Zeiger auf Element erhält, dann weitere Elemente hinzuzufügen (Zeiger nun für ungültig erklärt wird), verwenden jetzt Zeiger, crash

2. Start durch eine Sammlung iterieren. Entfernen Sie während der Iteration einige Elemente (entweder vor oder nach der aktuellen Iteratorposition). weiter iterieren, abstürzen.

(edit: in C++, sind Sie Glück zum Absturz zu bringen - schlimmer Fall ist eine Speicherbeschädigung)

I 1 glaube, durch rasche, denn wenn eine Sammlung speichert Klassen gelöst wird, eine Referenz genommen wird (zB starker Zeiger) auf ein Element erhöht den Refcount. Allerdings weiß ich nicht die Antwort für 2.

Es wäre super nützlich, wenn es einen Vergleich von footguns in C++ war, die/sind nicht durch rasche gelöst.

EDIT, Antwort aufgrund Robs:

Es scheint, dass auf mit Wörterbuch und/oder für Schleifen gehen einige undokumentierte Snapshot-ähnliches Verhalten gibt. Die Iteration erstellt eine Snapshot/versteckte Kopie davon beim Start.

Was mir gibt sowohl ein großes „WAT“ und „cool, das ist irgendwie sicher, ich denke,“ und „wie teuer diese Kopie ist?“.

Ich sehe dies entweder in Generator oder in for-Schleife nicht dokumentiert.

Der Code unten druckt zwei logische Schnappschüsse des Wörterbuchs. Der erste -Snapshot ist userInfo, wie er am Anfang der Iterationsschleife war, und zeigt keine Änderungen, die während der Schleife vorgenommen wurden, .

var userInfo: [String: String] = [ 
    "first_name" : "Andrei", 
    "last_name" : "Puni", 
    "job_title" : "Mad scientist" 
] 

userInfo["added_one"] = "1" // can modify because it's var 

print("first snapshot:") 
var hijacked = false 
for (key, value) in userInfo { 
    if !hijacked { 
     userInfo["added_two"] = "2" // doesn't error  
     userInfo.removeValueForKey("first_name") // doesn't error 
     hijacked = true 
    } 
    print("- \(key): \(value)") 
} 

userInfo["added_three"] = "3" // modify again 

print("final snapshot:") 
for (key, value) in userInfo { 
    print("- \(key): \(value)") 
} 

Answer 1

Wie Sie sagen, # 1 ist kein Problem. Sie haben keinen Zeiger auf das Objekt in Swift. Sie haben entweder ihren Wert oder einen Verweis darauf. Wenn Sie ihren Wert haben, dann ist es eine Kopie. Wenn Sie eine Referenz haben, ist sie geschützt. Also gibt es hier kein Problem.

Aber lassen Sie sich die zweite und Experiment betrachtet, überrascht sein, und dann überrascht stoppen zu sein.

var xs = [1,2,3,4] 

for x in xs { // (1) 
    if x == 2 { 
     xs.removeAll() // (2) 
    } 
    print(x) // Prints "1\n2\n3\n\4\n" 
} 

xs // [] (3) 

Warte, wie werden alle Werte gedruckt, wenn wir die Werte bei (2) wegblasen. Wir sind jetzt sehr überrascht.

Aber wir sollten nicht sein. Schnelle Arrays sind Werte. Die xs bei (1) ist ein Wert. Nichts kann es jemals ändern. Es ist kein "Zeiger auf Speicher, der eine Array-Struktur enthält, die 4 Elemente enthält". Es ist der Wert[1,2,3,4]. Bei (2) "entfernen wir nicht alle Elemente aus dem Objekt xs, auf das gezeigt wird."Wir nehmen die Sache xs ist, erstellen Sie ein Array, das, wenn Sie führt alle Elemente entfernen (das [] in allen Fällen wäre), und weisen Sie dann das neue Array xs. Nichts Schlimmes passiert.

Was bedeutet die Dokumentation von „verlieren alle Indizes?“ Es bedeutet genau, dass, wenn wir Indizes erzeugt, sie mehr nicht gut sind wir sehen:..

var xs = [1,2,3,4] 

for i in xs.indices { 
    if i == 2 { 
     xs.removeAll() 
    } 
    print(xs[i]) // Prints "1\n2\n" and then CRASH!!! 
} 

Sobald xs.removeAll() genannt wird, gibt es kein Versprechen, dass das alte Ergebnis of xs.indices bedeutet nichts mehr Sie dürfen diese Indizes nicht sicher gegen die Sammlung verwenden, aus der sie stammen

"Invalidates Indizes" in Swift ist nicht das gleiche wie C++ "Iteratoren ungültig". Ich würde das ziemlich sicher nennen, abgesehen davon, dass die Verwendung von Auflistungsindizes immer ein bisschen gefährlich ist kann es helfen; iteriere sie stattdessen. Auch wenn Sie die Indizes aus irgendeinem Grund benötigen, verwenden Sie enumerate, um sie zu erhalten, ohne die Gefahr einer Indizierung zu erzeugen.

(Randbemerkung, dict["key"] indiziert nicht in dict. Wörterbücher etwas verwirrend ist, weil ihre Schlüssel nicht ihr Index. Zugriff auf Wörterbücher von ihrem DictionaryIndex Index ist genauso gefährlich wie Arrays von ihrem Int Index zugreifen.)

Beachten Sie auch, dass das obige nicht für NSArray gilt. Wenn Sie während der Iteration NSArray ändern, erhalten Sie einen Fehler "mutierte Sammlung während der Iteration". Ich diskutiere nur Swift Datentypen.

---

EDIT: for-in ist very explicit in, wie es funktioniert:

Der erzeugen() Methode auf dem Sammelausdruck bezeichnet wird, einen Wert eines Generators typ die zu erhalten, die eine Art ist, dass Konform zum GeneratorType-Protokoll. Das Programm beginnt mit dem Ausführen einer Schleife, indem es die next() -Methode für den Stream aufruft. Wenn der zurückgegebene Wert nicht None ist, wird er dem Objektmuster zugewiesen, das Programm führt die Anweisungen aus und setzt dann die Ausführung am Anfang der Schleife fort. Andernfalls führt das Programm keine Zuweisung aus oder führt die Anweisungen nicht aus, und die For-In-Anweisung wird beendet.

Der zurück Generator a struct ist und enthält eine Sammlung Wert. Sie würden keine Änderungen an einem anderen Wert erwarten, um sein Verhalten zu ändern. Denken Sie daran: [1,2,3] ist nicht anders als 4. Sie sind beide Werte. Wenn Sie sie zuweisen, erstellen sie Kopien. Wenn Sie also einen Generator über einem Collection-Wert erstellen, werden Sie diesen Wert aufnehmen, genau so, als ob ich einen Generator über der Zahl 4 erstellt hätte. (Dies wirft ein interessantes Problem auf, da Generatoren nicht wirklich Werte sind und so wirklich sollten nicht structs sein, sondern sollten Klassen sein, Swift stdlib hat das behoben, siehe zum Beispiel die neue AnyGenerator, aber sie enthalten immer noch einen Array-Wert, und Sie würden niemals erwarten, dass Änderungen an einem anderen Array-Wert sie beeinflussen.)

Siehe auch "Structures and Enumerations Are Value Types", die auf die Bedeutung von Werttypen in Swift näher eingeht. Arrays sind nur Strukturen.

Ja, das bedeutet, dass logisch kopiert wird. Swift verfügt über viele Optimierungen, um das tatsächliche Kopieren zu minimieren, wenn es nicht benötigt wird. In Ihrem Fall, wenn Sie das Wörterbuch während der Iteration mutieren, wird dies eine Kopie erzwingen.Mutation ist billig, wenn Sie der einzige Verbraucher eines bestimmten Werts Backing-Storage sind. Aber es ist O (n) wenn du es nicht bist. (Dies wird durch die eingebaute Swift isUniquelyReferenced() bestimmt.) Lange Geschichte kurz: Swift Collections sind Copy-on-Write, und die einfache Übergabe eines Arrays führt nicht dazu, dass echter Speicher zugewiesen oder kopiert wird.

Sie erhalten keine COW kostenlos. Ihre eigenen Strukturen sind nicht COW. Es ist etwas, das Swift in stdlib macht. (Siehe Mike Ashs great discussion, wie Sie es neu erstellen würden.) Übergeben Sie Ihre eigenen benutzerdefinierten Strukturen verursacht echte Kopien passieren. Das heißt, der Großteil des Speichers in den meisten Strukturen ist in Sammlungen gespeichert, und diese Sammlungen sind COW, so dass die Kosten für das Kopieren von Strukturen in der Regel ziemlich gering sind.

Das Buch verbringt nicht viel Zeit damit, Werttypen in Swift zu bohren (es erklärt alles; es sagt einfach nicht "hey, und das ist was das bedeutet"). Auf der anderen Seite war es das konstante Thema auf der WWDC. Sie könnten besonders interessiert sein an Building Better Apps with Value Types in Swift, die alles zu diesem Thema ist. Ich glaube, Swift in Practice diskutierte es auch.

---

EDIT2:

@KarlP wirft einen interessanten Punkt in den Kommentaren unten, und es ist Adressierung wert. Keine der Wert-Sicherheitsversprechen, die wir diskutieren, beziehen sich auf for-in. Sie basieren auf Array. for-in macht überhaupt keine Versprechungen darüber, was passiert, wenn Sie eine Sammlung mutieren, während sie iteriert wird. Das wäre nicht einmal sinnvoll. for-in "iteriert nicht über Sammlungen", ruft es next() auf Generators. Also, wenn Ihre Generator undefiniert wird, wenn die Sammlung geändert wird, dann wird for-in explodieren, weil die Generator explodiert.

Das bedeutet, dass die folgenden unsicher sein können, je nachdem, wie streng lesen Sie die Spezifikation:

func nukeFromOrbit<C: RangeReplaceableCollectionType>(var xs: C) { 
    var hijack = true 
    for x in xs { 
     if hijack { 
      xs.removeAll() 
      hijack = false 
     } 
     print(x) 
    } 
} 

Und der Compiler wird Ihnen hier nicht helfen. Es wird für alle Swift-Sammlungen funktionieren. Aber wenn next() nach der Mutation für Ihre Sammlung ist undefiniertes Verhalten, dann ist dies ein undefiniertes Verhalten.

Meine Meinung ist, dass es schlecht Swift wäre, eine Sammlung zu machen, die ihre Generator zu werden undefined in diesem Fall erlaubt. Sie könnten sogar argumentieren, dass Sie die Generator Spezifikation gebrochen haben, wenn Sie dies tun (es bietet keine UB "out", es sei denn, der Generator wurde kopiert oder hat Null zurückgegeben). Man könnte also argumentieren, dass der obige Code absolut innerhalb der Spezifikation liegt und der Generator kaputt ist. Diese Argumente neigen dazu, ein bisschen unordentlich mit einer "Spezifikation" wie Swift's zu sein, die nicht in alle Eckfälle eintaucht.

Bedeutet das, dass Sie in Swift unsicheren Code schreiben können, ohne eine klare Warnung zu erhalten? Absolut. Aber in den vielen Fällen, die häufig Fehler in der realen Welt verursachen, macht Swifts eingebautes Verhalten das Richtige. Und das ist sicherer als einige andere Optionen.