FULL PRODUCT VERSION :
java version "1.8.0_40-ea"
Java(TM) SE Runtime Environment (build 1.8.0_40-ea-b23)
Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 6.3.9600]

A DESCRIPTION OF THE PROBLEM :
This is copied from here: http://stackoverflow.com/q/28840047/521799

Some time ago, I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively [1], with a ConcurrentHashMap cache and the new, useful computeIfAbsent() method:

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Test {
    static Map<Integer, Integer> cache = new ConcurrentHashMap<>();

    public static void main(String[] args) {
        System.out.println(
            "f(" + 8 + ") = " + fibonacci(8));
    }

    static int fibonacci(int i) {
        if (i == 0)
            return i;

        if (i == 1)
            return 1;

        return cache.computeIfAbsent(i, (key) -> {
            System.out.println(
                "Slow calculation of " + key);

            return fibonacci(i - 2) + fibonacci(i - 1);
        });
    }
}

I chose ConcurrentHashMap because I was thinking of making this example even more sophisticated by introducing parallelism (which I didn't in the end).

Now, let's increase the number from 8 to 25 and observe what happens:

        System.out.println(
            "f(" + 25 + ") = " + fibonacci(25));

The program never halts. Inside the method, there's a loop that just runs forever:

for (Node<K,V>[] tab = table;;) {
    // ...
}


Matthias, a reader of that blog post also confirmed the issue (he actually found it). [2]

This is weird. I would have expected any of the following two:

- It works
- It throws a ConcurrentModificationException

But just never halting? That seems dangerous. Is it a bug? Or did I misunderstand some contract?

------

This is of course a "feature". The ConcurrentHashMap.computeIfAbsent() Javadoc reads:

> If the specified key is not already associated with a value, 
> attempts to compute its value using the given mapping function 
> and enters it into this map unless null. The entire method
> invocation is performed atomically, so the function is applied at
> most once per key. Some attempted update operations on this
> map by other threads may be blocked while computation is in
> progress, so the computation should be short and simple, and
> must not attempt to update any other mappings of this map.
The "must not" wording is a clear contract, which my algorithm
> violated, although not for the same concurrency reasons.

What's still interesting is that there is no ConcurrentModificationException. Instead, the program just never halts - which still is a rather dangerous bug in my opinion.

The simplest use-site solution for this concrete problem would be to not use a ConcurrentHashMap, but just a HashMap instead:

static Map<Integer, Integer> cache = new HashMap<>();

Now, everything works fine.

Note:

The HashMap.computeIfAbsent() (or Map.computeIfAbsent() Javadoc don't forbid such recursive computation, which is of course crazy as the type of the cache is Map<Integer, Integer>, not ConcurrentHashMap<Integer, Integer>. It is very dangerous for subtypes to drastically re-define super type contracts (Set vs. SortedSet is greeting). It should thus be forbidden also in super types, to perform such recursion.


[1]: http://blog.jooq.org/2014/02/28/java-8-friday-goodies-easy-as-pie-local-caching
[2]: http://blog.jooq.org/2014/02/28/java-8-friday-goodies-easy-as-pie-local-caching/#comment-121821

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
See description

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The program should halt
ACTUAL -
The program doesn't halt

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
See description
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Use a HashMap instead of a ConcurrentHashMap