juil.
2010
Java Quiz #40
To please your Project Manager, a former developer (yeaaars ago), you sometimes let him help you develop some "very important" parts of your application.
Today, he's in charge of displaying "Hello World" by iterating on a list containing those words. Alas, distracted by his going on vacation this very afternoon, he forgets to add "World" to the list before starting the iteration. Trying to correct his mistake, he adds it a few lines later, but now his code unexpectedly breaks down at runtime ("this must be a JVM bug !").
A few minutes before leaving, he asks you to find a solution in his absence, with the following instructions :
- Do not modify his existing code, it's Perfect (of course).
- The
FIXME
tag shows where you're allowed to insert your corrective code - He must be able to understand your solution when he comes back (so
using Reflection is not an option).
Are you worth the trust of your beloved Manager ?
final List<String> list = new ArrayList<String>() {{ add("Hello"); }}; final Iterator<String> iterator = list.iterator(); System.out.println(iterator.next()); list.add("World"); // FIXME : work here while I'm sunbathing System.out.println(iterator.next());
Hints - Keep in mind that :
- the iterator is declared final
- this is only a code fragment, so you cannot use System.exit(0) or return; you wouldn't like your application to terminate prematurely, would you ?
- since you cannot modify the existing code, you cannot delete or ignore the last line, which must print "World"
Note : I must thank Romain Revol for helping me to write this quiz. Romain successfully attended the "Heinz Kabutz's Java Specialist Master Course" training session I presented in France in June at Zenika's office.
Answer :
Well, this is unusual. Since Steen gave the most detailed (and correct) answer I've ever seen on this blog (see comment 45 below), I will simply paste it here as the official answer.
Congratulations, Steen :)
When running:
java -cp . ManagersHello
We get :
Hello Exception in thread "main" java.util.ConcurrentModificationException at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372) at java.util.AbstractList$Itr.next(AbstractList.java:343) at ManagersHello.main(ManagersHello.java:146)
The javadoc for ConcurrentModificationException says:
If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will throw this exception.
The AbstractList
class provides the Iterator that is used in the ArrayList
, and this class has an internal class Itr
that uses two field to detect whether there has been made 'structural modifications' to the subject of the iteration.
The field "int expectedModCount
" is initiated to be equal to the field "protected transient int modCount = 0;
", and modCount
keeps track of the structural modifications. If modCount
at some points in the iteration does not equal expectedModCount
, a ConcurrentModificationException
is thrown.
Such a check is made on most calls on the Iterator, which is implemented using the Itr
inner class.
In the code below, the assertation holds until the second call to iterator.next()
is made, because at that time, the expectedModCount
is 0, while the modCount
of the list is 1.
The call "list.add("World");
" will increment the modCount
after the list has been structurally changed. This means that the first call to the check method after this statement will throw a ConcurrentModificationException
.
This window can be used to try to modify the modCount
of the list instance so that it will again be equal to expectedModCount
before the iterator.next()
method is called. Since modCount
is an int
, an overflow will wrap the value from Integet.MAX_VALUE
to Integer.MIN_VALUE
and therefore it will be possible to reach the value of expectedModCount
through an integer overflow.
In the ArrayList
implementation, which is the instantiated type of the field list
in the code, 4 methods change the variable modCount
upon invocation :
public void trimToSize()
public void ensureCapacity(int minCapacity)
public E remove(int index)
public void clear()
trimToSize
will increase the modification count by one and then check to see if the number of elements in an internal array buffer is smaller the number of elements specified in the construction of the ArrayList
. If this is the case, an invokation of Arrays.copyOf(T original, int newLength)
is made.
ensureCapacity
will likewise increase the modification count and the perform a check on whether the specified minimum capacity is larger than the number of elements currently in the ArrayList
.
remove
will do a range check, increase the modification count and remove the element E at the specified index.
clear
will increase the modification count and then remove (nullify) all elements in the ArrayList
Starting from the bottom, neither the clear()
nor the remove()
methods will work in this scenario, since their structural modification will be to remove the very element we wish to print. Using clear()
will make the second call to iterator.next()
fail with a NoSuchElementException
. Using remove(int)
will make the second call to ((ArrayList)list).remove(0)
fail with an IndexOutOfBoundsException
, since there is no more elements to remove and hence none at index 0.
Of course, calling remove(0)
for uneven numbers (except Integer.MIN_VALUE
) and subsequently add("World")
(for even numbers) will work, as the list will end up on the correct modification count and the correct number of elements ("World") at the end of the for loop.
This leaves us with ensureCapacity(int)
and trimToSize()
, both of which will work, because they preserve the elements in the list.
public class Quiz40 { public static void main(String[] args) { final List<String> list = new ArrayList<String>() {{ add("Hello"); }}; final Iterator<String> iterator = list.iterator(); System.out.println(iterator.next()); list.add("World"); // FIXME : work here while I'm sunbathing for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) { //solution_one ((ArrayList) list).ensureCapacity(1); //solution_two ((ArrayList) list).trimToSize(); //solution_three if (!(i == Integer.MIN_VALUE) && !(i % 2 == 0)) { ((ArrayList) list).remove(0); } if (i % 2 == 0) { list.add("World"); } } System.out.println(iterator.next()); } }
Commentaires
Le but est de faire un overflow sur modCount. La méthode trimToSize est a priori la plus rapide car ne fait presque aucune opération quand la liste ne change pas, sauf augmenter modCount
ArrayList al = (ArrayList) list;
for (int n = Integer.MIN_VALUE; n < Integer.MAX_VALUE; n++) al.trimToSize();
Et si vous voulez formaté tel que demandé, lancer le code suivant avec "java -Dline.separator= Main"
System.out.print(" ");
ArrayList al = (ArrayList) list;
for (int n = Integer.MIN_VALUE; n < Integer.MAX_VALUE; n++) al.trimToSize();
Ok I thing I got it
@@
//First of all lets put stuff in a new Iterator so we can work with
Iterator newIter = list.iterator();
//Take the Hello String and remove it
newIter.next();
newIter.remove();
//Print the world String
System.out.println(newIter.next().toString());
//Stop the iterator from continuing
while(iterator.hasNext())
@@
@Alexius : Interesting solution, though not the one I expected.
Now try again, but using only the existing iterator.
Bon, je suis sûr que ce n'est pas ce que tu as en tête, je n'utilise ni la liste ni l'iterator, mais même le chef de projet qui a codé pour la dernière fois en VB 1.0 devrait comprendre :
System.out.println("World"); if(false)
En plus, les perfs sont bonnes :)
@Jerome LoL I love it!!!!!
@Olivier
How about this?
list.remove("Hello");
System.out.println(list.get(0));
while(iterator.hasNext())
Bon, vu que notre CP n'est surement pas adapte de l'optimisation, ce code lui permet de faire le travail et de prendre un bon café :
final Iterator<String> iterator = list.iterator();
System.out.println(iterator.next());
list.add("World");
/* FIX */
((ArrayList)list).trimToSize();
for( int j = 0 ;j< Integer.MAX_VALUE ; j++){
((ArrayList)list).trimToSize();
((ArrayList)list).trimToSize();
}
/* END FIX */
System.out.println(iterator.next());
Another solution, highly dependent on the internals of ArrayList. An integer overflow is used to "reset" the internal modification counter.
for(int i=0;i!=-1;i++) ((ArrayList)list).ensureCapacity(0);
It takes around 30 seconds on my computer to run, I hope this code is not called too often.
Je fais faire un ptit tour au modCount interne de l'array list histoire qu'il revienne à sa valeur attendue :)
L'exception survient lorsque le modCount de la liste (nombre de modifications de la liste) est différent de l'expectedModCount de l'itérateur (nombre de modifications de la liste à la création de l'itérateur).
Dans notre cas : expectedModCount = 1 et le modCount = 2 (apres l'ajout de "World").
Chaque modification de la liste incrémente le modCount, je l'incrémente donc jusqu'à ce qu'il revienne sur sa valeur initiale (=1) en appelant la méthode trimToSize(), qui ne consomme presque rien en CPU, autant de fois que nécessaire :
// FIXME : insert some magic code here
ArrayList<String> list2 = (ArrayList<String>) list;
for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
}
// modCount back to 1!
Wahou, 3 fois la même solution en 3 minutes...
Bon les gars, ça va pas du tout, vous êtes trop forts, les quizz tiennent de moins en moins longtemps !
(Mention spéciale pour Mathieu qui a répondu à 3h du mat' :)
Ça, en postant tes quiz à 1 heure du matin aussi, ça favorise pas les masses laborieuses qui se lèvent tôt pour aller travailler en France ;)
Non ca favorise ceux qui sont à Montréal (Canada) ;-)
Hi mate,
I think you blog has a bug regarding the timestamp!
I was the fisrt to answer (and as a metter of fact twice) but suddenly I have the seccond entry! :P
Maybe next time you should think of making a Blog in JAVA and not in php! :)
Would you like your Greek affiliates to host it for you?
ps When you will be visiting Greece to stop by from Zenika Hellas offices?
cheers!
@Alexius : this is not a bug :)
Mathieu answered just a couple hours after I published the quiz, so I hid it to keep you guys searching by yourselves. When I saw everyone got it right, I just displayed Mathieu's comment again.
long tt = 2147483647L + 2147483647L + 1;
for(long i=0; i<tt; i++) {
}
This would make the modCount variable in AbstractList equal to 1. calling iterator.next() would not satisfy the condition for checkForComodification() function and "World" would be printed.
I could not test it as I don't have enough memory to allocate to JVM.
The trouble with all the solutions involving the modCount field is that they violate the third requirement, to wit, that the bugger is supposed to understand it. How on earth would he be able to, if doesn't know the contract of java.util.Iterator and thinks a ConcurrentModificationException is a JVM bug?
Jérôme's first solution (#4) is the only correct one posted so far, per requirements.
@Alexius, I think your version can still throw a ConcurrentModificationException from iterator.hasNext() (it might be implementation-dependent)
// FIXME : work here while I'm sunbathing
iterator = list.iterator();
iterator.next();
System.err.println(iterator.next());
Pareil que dd, j'aurais simplement dit :
(iterator = list.iterator()).next();
Hi,
very nice riddle - but which answer does the author meant?
@dd & @lapsus63 : the iterator variable is declared "final", so your code wouldn't compile.
@Yogesh Sinha : you could alternatively add and remove items in the list, instead of keeping adding only ; this would eliminate the memory consumption issue, and still increment the modcount.
final List<String> list = new ArrayList()
;final Iterator<String> iterator = list.iterator();
System.out.println(iterator.next());
list.add("World");
System.out.println(list.get(1));
if(lis.size(0 ==0)
System.out.println(iterator.next());
Can someone explain why this works. Is the modCount value changing? Also I was playing with the loop and noticed:
for (int n = Integer.MIN_VALUE; n < Integer.MAX_VALUE-1; n++) al.trimToSize();
doesn't work but
for (int n = Integer.MIN_VALUE; n < Integer.MAX_VALUE; n++) al.trimToSize();
does. What is the trick to looping through the complete range of Integer?
// Run with -Dline.separator=" " to avoid the line break, but you get an extra space at the end.
// FIXME BEGIN
for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
((ArrayList<String>) list).trimToSize();
}
// FIXME END
// FIXME : work here while I'm sunbathing
Thread.setDefaultUncaughtExceptionHandler(new UncaughtExceptionHandler(){
@Override
public void uncaughtException(Thread t, Throwable e) {
}
});
System.out.println("World");
System.out.println("World");
System.exit(0);
@finnw
No it will not mate because it does not actually move the pointer but just checks if it can be moved :)
@Brad
Yes I would like to know why too! :)
The trick is to overflow the modCount variable, so that ConcurrentModificationException is not thrown.
modCount is incremented in each modifying method of ArrayList (add, addAll, clear, etc.), and checked in the methods of the Iterator implementations ( next(), etc.). So by overflowing and in a sense restarting the modCount, we can make sure that modCount is the same as before even after we call add() on the list.
@Brad
In adition to the above explanation, let me give another example. If we need to add two strings to the list (instead of one), we would loop one less, in order to satisfy the equality in that case. I guess this clarifies the case.
Interesting problem. I had a go, and came up with this - it's very hacky, but takes less time to complete!
// FIXME : work here while I'm sunbathing
try {
System.out.println(iterator.next());
} catch (ConcurrentModificationException cme) {
System.out.println(list.get(1));
}
Interesting problem. I had a go, and came up with this - it's very hacky, but takes less time to complete!
try {
System.out.println(iterator.next());
} catch (ConcurrentModificationException cme) {
System.out.println(list.get(1));
}
// FIXME : work here while I'm sunbathing
System.out.println(list.listIterator(1).next());
I know the following is not the correct answer. However just for fun.
// FIXME : insert some magic code here
Thread.currentThread().setUncaughtExceptionHandler(new Thread.UncaughtExceptionHandler() {
public void uncaughtException(Thread t, Throwable e) {
if(e instanceof ConcurrentModificationException) {
System.out.println(list.get(1));
}
}
});
System.out.println(list.get(1));
if (1 == 0)
Try these lines:
@@
@@
Interesting ideas! Maybe the easiest way is simply:
iterator = list.listIterator(1);
keep in mind, that the iterator reference was declared final.
// FIXME : work here while I'm sunbathing
list.remove(0);
System.out.println(list.iterator().next());
Many interesting ideas here, but also many wrong answers.
Keep in mind that :
- the iterator is declared final, so you cannot do
iterator = list.iterator();
- this is only a code fragment, so you cannot use
System.exit(0)
or return; you wouldn't like your application to terminate prematurely.- since you cannot modify the existing code, you cannot delete or ignore the last line, which performs
iterator.next()
and therefore triggers aConcurrentModificationException
Have fun :)
public static void main(String args) {
final List<String> list = new ArrayList<String>() ;
final Iterator<String> iterator = list.iterator();
System.out.println(iterator.next());
list.add("World");
System.out.println(list.get(list.size()-1));}} class TheLinesFollowsThisCalssIsNotUsed{{Iterator iterator = null;
System.out.println(iterator.next());
}
final List<String> list = new ArrayList<String>() ;
final Iterator<String> iterator = list.iterator();
System.out.println(iterator.next());
list.add("World");
System.out.println(list.get(list.size()-1));}} class TheLinesFollowsThisCalssIsNotUsed{{Iterator iterator = null;
System.out.println(iterator.next());
...
// FIXME : work here while I'm sunbathing
new Runnable(){
public void run(){
try {
Field f = iterator.getClass().getDeclaredField("expectedModCount");
f.setAccessible(true);
f.setInt(iterator, 2);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}.run();
// FIXME : work here while I'm sunbathing
System.out.println(iterator.next());
ArrayList<String> list2 = (ArrayList<String>) list;
for (long i = 0; i < Integer.MAX_VALUE * 2l + 1; i ++) {
}
ehm... sorry... i haven't read the third condition line :-(
Easy and simple:
final List<String> list = new ArrayList()
;final Iterator<String> iterator = list.iterator();
System.out.println(iterator.next());
list.add("World");
System.out.println("World");
if (0)
System.out.println(iterator.next());
Sorry for the verbosity. Please delete this post if it is deemed unsuitably long:
<code>
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
/*
public class ManagersHello
{
}
</code>
This must be the most complete solution to one of my quizzes I've ever seen O_O
And it works !
Nice job !
@@
// FIXME : work here while I'm sunbathing
try {
Field f = iterator.getClass().getDeclaredField("expectedModCount");
f.setAccessible(true);
f.setInt(iterator, 2);
} catch (Exception e) {}
// FIXME : work here while I'm sunbathing
@@
@@
// FIXME : work here while I'm sunbathing
try {
Field f = iterator.getClass().getDeclaredField("expectedModCount");
f.setAccessible(true);
f.setInt(iterator, list.size());
} catch (Exception e) {}
// FIXME : work here while I'm sunbathing
@@
Please elaborate more on this statment :
"Since modCount is an int, an overflow will wrap the value from Integet.MAX_VALUE to Integer.MIN_VALUE and therefore it will be possible to reach the value of expectedModCount through an integer overflow. "
How it is working ?