Soyez prudent lorsque vous modifiez des données lors de l'utilisation d'un itérateur Java

Alors que ce semestre commence à se terminer, j'ai pensé que je partagerais une petite histoire sur la façon dont je me suis très, très familiarisé avec les itérateurs Java.

Contexte du monde réel

Pour le contexte, j'enseigne un cours de composants logiciels de deuxième année qui sert de dernier obstacle pour les étudiants qui tentent d'entrer dans la majeure. Naturellement, ce cours est très stressant pour les étudiants et je dois souvent travailler très dur pour leur donner toutes les chances de réussir.

Malheureusement, ce semestre, nous avons été emportés par la pandémie et avons dû nous convertir à l'enseignement en ligne. En conséquence, nous avons dû prendre des décisions rapides sur l'enseignement qui ont changé la façon dont les élèves allaient apprendre. En particulier, nous avons converti tous nos examens papier en quiz en ligne.

Pour certains élèves, ce fut une bénédiction majeure. Après tout, ces quiz n'étaient pas plus difficiles que les examens, et nous les avons faits à livre ouvert. En d'autres termes, nous avons rendu la classe un peu plus facile à réussir.

Bien sûr, les étudiants étaient partout dans le monde et ils n'ont pas pu obtenir l'aide dont ils avaient besoin. De plus, les étudiants ne prenaient pas leurs études aussi au sérieux qu'ils le feraient pour un examen. Cette combinaison a créé des scores de quiz assez abyssaux.

Au moment où nous avons atteint le quatrième quiz, les étudiants étaient assez contrariés. En fait, j'ai entendu plusieurs instructeurs dire que leurs étudiants en avaient assez des « questions pièges ». En tant qu'instructeur, c'était un peu frustrant à entendre car il s'agissait de questions d'examen assez typiques. Nous n'augmentions pas exactement la difficulté juste pour eux, mais c'était la première fois que j'entendais ces plaintes.

Exemple de problème

Puis, quelque chose de bizarre s'est produit. Nous leur avons posé une question à laquelle je ne connaissais pas vraiment la réponse, et cela ressemblait un peu à ceci :

Quelle est la valeur de la variable Set nums après le fragment de code suivant ?

Set<NaturalNumber> nums = new SomeSetImplementation<>();
nums.add(new NaturalNumber2(1));
nums.add(new NaturalNumber2(5));
nums.add(new NaturalNumber2(6));
for (NaturalNumber n : nums) {
    n.increment();
}

Naturellement, les options des étudiants sont les suivantes :

• chiffres ={1, 5, 6, 2, 6, 7}
• nums ={2, 6, 7}
• chiffres ={1, 5, 6}
• Impossible de dire à partir des informations fournies.

Maintenant, pour le contexte, il y a quelques composants internes dans cet exemple.

Premièrement, un NaturalNumber est une classe mutable qui représente un entier non négatif non borné. En d'autres termes, un NaturalNumber peut aller de zéro à l'infini. De plus, un NaturalNumber peut être modifié à l'aide d'une série d'opérations mathématiques de base comme les suivantes :

• increment() :ajoute 1 à this
• add(NaturalNumber n) :ajoute n à this

De plus, cette question utilise un Set qui s'apparente à un ensemble mathématique. L'idée ici est qu'un Set a deux propriétés principales :

1. Un Set manque de doublons (c'est-à-dire que {1, 2, 1} n'est pas un ensemble légal).
2. Un Set n'est pas ordonné (c'est-à-dire que {1, 2, 3} et {3, 2, 1} sont équivalents).

Pour référence, ces deux composants sont soigneusement documentés sur le site Web du cours, si vous souhaitez lire plus de détails. Tous les composants sont écrits à l'aide de Design by Contract, de sorte que chaque méthode inclura un contrat approprié où la condition préalable est indiquée par @requires et la postcondition est indiquée par @assures.

De plus, nous étiquetons chaque paramètre à l'aide de modes de paramètres tels que @restores, @updates, @clears et @replaces. Bien sûr, cela sort un peu du cadre de cette pièce.

Résoudre le problème

Maintenant, je répète que je ne savais pas exactement quelle réponse était correcte au début. De toute évidence, la première réponse (c'est-à-dire {1, 5, 6, 2, 6, 7}) est incorrecte car l'incrémentation de la valeur sous-jacente n'ajoute pas de nouvelles valeurs au Set - ou alors je pensais. En utilisant cette même logique, j'ai également supposé que le troisième ensemble (c'est-à-dire {1, 5, 6}) était évidemment incorrect car nous modifions clairement les valeurs sous-jacentes.

À ce stade, j'étais assez confiant que la deuxième réponse (c'est-à-dire {2, 6, 7}) était correcte, tout comme 87 % de mes élèves. Bien sûr, j'avais le corrigé, j'ai donc dû me mettre au défi de comprendre pourquoi la bonne réponse était en fait la réponse finale (c'est-à-dire "Impossible de dire à partir des informations fournies").

Maintenant, d'après le titre de cet article, vous pourriez déjà être bien en avance sur moi. C'est très bien! Cependant, je n'ai pas sauté à cette conclusion tout de suite. Au lieu de cela, j'ai pris du recul et j'ai décidé de tirer le Set .

Bien sûr, il y a quelques problèmes majeurs lorsque vous essayez de le faire. Tout d'abord, comme je l'ai mentionné précédemment, un Set n'a pas d'ordre. Par conséquent, comment raisonner sur quel élément passe en premier lors de l'itération ? Essaie-t-on toutes les configurations possibles ?

Ce sont des questions auxquelles je n'étais pas prêt à répondre. Heureusement, il s'avère que l'itération par ordre d'apparition nous fait gagner beaucoup de temps. Jetez un œil :

{1, 5, 6} // Initial state
{2, 5, 6}  // After incrementing the first element
{2, 6, 6}  // After incrementing the second element

Oh oh ! Nous avons enfreint notre première règle :un Set ne doit pas contenir de doublons. Par conséquent, nous ne pouvons pas dire ce que le résultat Set ressemblera. Ma réponse finale est D :"Impossible de dire à partir des informations fournies."

Malheureusement, cette explication ne me satisfaisait pas vraiment. Genre, j'obtiens qu'un Set ne peut pas contenir de doublons, mais quelles sont les conséquences pratiques d'une violation de cette règle ? En d'autres termes, si c'est si mauvais, pourquoi donnons-nous même à l'utilisateur l'accès aux données sous-jacentes ?

À mon avis, les utilisateurs ne devraient pouvoir accéder aux données que lorsqu'ils les suppriment. En général, je pense que la bibliothèque fait un excellent travail à cet égard. Si Set n'a pas implémenté Iterable , nous serions en clair.

Présentation des itérateurs Java

Ce qui m'amène à un problème encore plus étrange :les itérateurs Java. Pour que ce code fonctionne, Set doit implémenter Iterable, ce qui signifie définir un Iterator pour l'architecture sous-jacente.

Maintenant, si vous avez déjà écrit votre propre itérateur, vous savez que vous devez faire quelque chose comme ceci :

new Iterator<T>() {
  @Override
  public boolean hasNext() { ... }
  @Override
  public T next() { ... }
  @Override
  public void remove() { ... }
}

Ici, l'idée de base est que nous définissons une sorte de structure qui peut servir de structure de données paresseuse. Si vous êtes familier avec les expressions de générateur d'autres langages comme Python, c'est la même idée :nous créons un objet qui peut renvoyer un élément à la fois à partir d'une séquence d'éléments.

En pratique, un Iterator fonctionne en continuant à fournir des éléments via le next() méthode jusqu'à ce qu'il n'y ait plus rien à retourner (ce qui peut ne jamais arriver). Dans les séquences bornées, nous savons quand nous arrêter car le hasNext() la méthode renverra false . Ensemble, ces méthodes peuvent servir de base à un mécanisme de bouclage :

while (iter.hasNext()) {
  T item = next();
}

En faisant en sorte qu'une classe implémente Iterable , nous pouvons alors exploiter un peu de sucre syntaxique Java appelé la boucle for-each :

for (T item: collection) { ... }

Mises en garde sur l'itérateur Java

Dans le problème défini ci-dessus, nous avons pu boucler sur le Set car il implémente Iterable .

Bien sûr, ce n'est pas parce que nous sommes capables de boucler sur la structure de données que nous ne rencontrerons pas de problèmes. Après tout, le Iterator classe a quelques règles qui lui sont propres. Peut-être que la règle la plus importante se trouve dans la description du remove() méthode :

Supprime de la collection sous-jacente le dernier élément renvoyé par cet itérateur (opération facultative). Cette méthode ne peut être appelée qu'une seule fois par appel à next() . Le comportement d'un itérateur n'est pas spécifié si la collection sous-jacente est modifiée pendant que l'itération est en cours autrement qu'en appelant cette méthode.

Docs Java 8 (capturés le 23/04/2020)

Rappelez-vous comment j'ai dit que modifier un NaturalNumber est mauvais car cela pourrait entraîner des doublons. Eh bien, sur la base de cette définition, modifier un Set pourrait entraîner un comportement imprévisible malgré tout.

Bien sûr, cela soulève une question pour moi :que signifie modifier la collection sous-jacente. Pour les collections Java, les boucles for-each interdisent l'ajout ou la suppression d'un élément d'une collection. Dans ces cas, nous pouvons nous attendre à voir un ConcurrentModificationException (documents).

Maintenant, cette erreur n'est pas universelle. Après tout, comment un Iterator pourrait-il peut-être savoir si une collection a été modifiée ? Il s'avère que ce comportement est personnalisé dans le next() méthode pour chaque collection. Avec le List collection, par exemple, le ConcurrentModificationException est lancé lorsque la taille de la liste change. En d'autres termes, l'intégrité de la structure de données est vérifiée à chaque invocation de next() .

Étant donné que les collections utilisent des types génériques, il est impossible de tenir compte de tous les différents types de situations qui pourraient survenir. Par conséquent, il n'y a aucun moyen pour next() pour détecter si des données ont été mutées sans état de suivi. Par exemple, vérifier si des valeurs ont changé dans une liste peut nécessiter de stocker une copie de l'état précédent et de vérifier régulièrement cet état précédent. Ce n'est pas bon marché !

Pour aggraver les choses, nous n'avons pas vraiment parlé des effets que la modification des données sous-jacentes pourrait avoir sur le processus d'itération réel. Par exemple, si next() dépend en quelque sorte des données sous-jacentes, les modifier changerait clairement ce qui vient ensuite.

Imaginez une seconde que nous ayons un Iterator pour une liste dont les éléments doivent implémenter Comparable . Ensuite, nous avons fait ce Iterator de telle sorte qu'il renvoie toujours la valeur suivante dans l'ordre trié. Si nous devions ensuite modifier les valeurs sous-jacentes, nous pourrions créer une boucle qui ne parcourt jamais toute la liste :

[1, 2, 3]  // next() returns 1 which we scale by 5
[5, 2, 3]  // hasNext() claims there are no other values

Maintenant, ce n'est pas idéal. En règle générale, vous vous attendez à ce qu'une boucle for-each traverse réellement une structure de données entière, et ce n'est tout simplement pas le cas.

Revisiter le problème d'ensemble

À ce stade, nous avons eu l'occasion de parler du Set problème sous deux angles différents :

1. Que se passe-t-il si nous invalidons un Set ? en générant des doublons ?
2. Que se passe-t-il si nous invalidons une boucle for-each en modifiant la structure de données sous-jacente ?

Maintenant, je veux profiter de l'occasion pour parler de ce qui peut réellement arriver lors de l'exécution de l'extrait de problème :

Set<NaturalNumber> nums = new SomeSetImplementation<>();
nums.add(new NaturalNumber2(1));
nums.add(new NaturalNumber2(5));
nums.add(new NaturalNumber2(6));
for (NaturalNumber n : nums) {
    n.increment();
}

En supposant que le Iterator pour Set n'a pas de détection de modification sophistiquée, un résultat possible est le même Set la plupart des gens s'attendraient à :{2, 6, 7}.

Un autre résultat possible est que nous obtenons un Set où seules certaines valeurs sont incrémentées. Peut-être, comme je l'ai déjà dit, le next() dépend des données sous-jacentes pour prendre sa décision sur ce qui vient ensuite.

Dans ce scénario, nous pourrions nous retrouver avec n'importe quelle combinaison de sorties incrémentées :

• {2, 5, 6}
• {1, 6, 6}
• {1, 5, 7}
• {2, 6, 6}
• {2, 5, 7}
• {1, 6, 7}

Dans les deux cas, nous ne sommes pas exactement en sécurité. Bien sûr, le Set ça se ressemble, mais est-ce vraiment pareil ?

Imaginons une seconde que le Set est implémenté à l'aide d'une table de hachage. Cela offre l'avantage de pouvoir vérifier rapidement les doublons, mais cela nécessite un peu plus de maintenance. Par exemple, si nous voulons changer une valeur dans le Set , nous devons recalculer le hachage et vérifier les collisions.

Lorsque nous modifions le NaturalNumber directement, nous sautons cette phase de maintenance. Par conséquent, notre table de hachage contiendra toujours les trois hachages d'origine. Quand quelqu'un vérifie si le Set contient deux, par exemple, la méthode retournera incorrectement false .

Bien entendu, il s'agit d'un détail d'implémentation. Il est très possible qu'aucun problème ne soit détecté. Le programme continue de se dérouler sans heurts et personne ne sourcille. Comme pour tous les détails de mise en œuvre, cependant, nous ne pouvons pas dépendre de leur comportement supposé. En d'autres termes, le programme est toujours imprévisible.

En passant, l'implémentation Java de Set appelle en fait ce problème précis :

Remarque :Une grande prudence doit être exercée si des objets modifiables sont utilisés comme éléments d'ensemble. Le comportement d'un ensemble n'est pas spécifié si la valeur d'un objet est modifiée d'une manière qui affecte les comparaisons d'égalité alors que l'objet est un élément de l'ensemble. Un cas particulier de cette interdiction est qu'il n'est pas permis à un ensemble de se contenir en tant qu'élément.

Documentation Java Set (consultée le 24/04/2020)

On dirait qu'il est assez difficile d'assembler un Set implémentation qui n'a pas de problèmes avec les types mutables. Je me demande ce que cela dit sur les types mutables…

Quel est le plat à emporter ?

Au final, je pense que le Iterator la documentation est écrite d'une manière qui laisse à l'utilisateur le soin de jouer correctement. En d'autres termes, quand il dit :

Le comportement d'un itérateur n'est pas spécifié si la collection sous-jacente est modifiée pendant que l'itération est en cours autrement qu'en appelant cette méthode.

Cela signifie vraiment "de quelque manière que ce soit .” Bien sûr, je n'ai jamais été en mesure de confirmer ces soupçons, donc je serais intéressé de voir ce que les autres ont à dire.

En attendant, si vous avez aimé cet article, j'aimerais que vous en profitiez pour apprendre comment vous pouvez aider à développer un peu le site. Dans cet article, vous découvrirez ma liste de diffusion ainsi que mon Patreon.

Sinon, voici quelques articles connexes rien que pour vous :

• L'opérateur de reste fonctionne sur les doublons en Java
• Soyez prudent lorsque vous copiez des types de données mutables

De même, voici quelques ressources utiles sur Amazon (publicité) :

• Problèmes de codage Java :améliorez vos compétences en programmation Java en résolvant des problèmes de codage réels
• Apprendre la programmation Java 12 :un guide étape par étape pour apprendre les concepts essentiels de Java SE 10, 11 et 12

Sinon, merci d'être resté. J'espère que mes divagations nocturnes à l'école des diplômés vous ont été utiles !