Repository: graphhopper/graphhopper (java)

Issue:
Max speed can get exceeded due to rounding error
For example `FootFlagEncoder` has a maximum speed of 15km/h. When we store the speed it is converted to an int using `speedFactor`. However, with our current logic it can happen that we set the speed to `15`, but `get(averageSpeedEnc)` returns e.g. `16`. This way the speed of an edge can exceed the maximum even when we did not exceed the maximum speed when we set the value.

This obviously can be problematic when routing with AStar, but also it can result in a 'max speed violated' error in `CustomWeighting`. See the tests here: https://github.com/graphhopper/graphhopper/commit/944d95ae5e0553e9fa74a758ae2ba17cd6d1da8e

The problematic code is in `UnsignedIntDecimalEncodedValue#toInt`:

```java
    private int toInt(double val) {
        return (int) Math.round(val / factor);
    }
```

In the example above the speed factor is 2, so 15/2=7.5 -> round: 8 -> (int) 8, and when later it is multiplied with the factor again we get 16 > 15. Rounding might be the right thing to do for the decimal encoded value, but in the context of the flag encoder's max speed we somehow have to make sure that the maximum speed is definitely never exceeded. 

Btw currently we can even do something like:
```java
edge.set(encoder.getAverageSpeedEnc(), encoder.getMaxSpeed() * 2);
```
without getting an error. But this is maybe for another issue. The main issue here is that we get back a value that exceeds the max speed even when the value we set was within the valid bounds.

Note that the failing tests are *slightly* artificial, because they deliberately use the `FootFlagEncoder`, because it has an uneven maxSpeed (15) *and* set a non-default speed factor (2 instead of 1).


Pull request:
Make sure encoder max speed cannot be exceeded, add DecimalEncodedValue#getNextStorableValue
Trying to fix #2322, but see inline comments.

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValue.java b/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValue.java
index 334a8617c..79ee6f57a 100644
--- a/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValue.java
+++ b/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValue.java
@@ -22,7 +22,15 @@ public interface DecimalEncodedValue extends EncodedValue {
     double getDecimal(boolean reverse, IntsRef ref);
 
     /**
-     * The double value this EncodedValue accepts for setDecimal without throwing an exception.
+     * The maximum double value this EncodedValue accepts for setDecimal without throwing an exception.
      */
     double getMaxDecimal();
+
+    /**
+     * @return the smallest decimal value that is larger or equal to the given value and that can be stored exactly,
+     * i.e. for which {@link #getDecimal} returns the same value that we put in using {@link #setDecimal}.
+     * For example if the internal scaling factor is 3 calling getDecimal after setDecimal(reverse, ref, 5) will return
+     * 6 not 5! The value returned by this method is guaranteed to be storable without such a modification.
+     */
+    double getNextStorableValue(double value);
 }
diff --git a/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValueImpl.java b/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValueImpl.java
index ea22bae24..6584da72e 100644
--- a/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValueImpl.java
+++ b/core/src/main/java/com/graphhopper/routing/ev/DecimalEncodedValueImpl.java
@@ -102,6 +102,16 @@ public final class DecimalEncodedValueImpl extends IntEncodedValueImpl implement
         return value * factor;
     }
 
+    @Override
+    public double getNextStorableValue(double value) {
+        if (!useMaximumAsInfinity && value > getMaxDecimal())
+            throw new IllegalArgumentException(getName() + ": There is no next storable value for " + value + ". max:" + getMaxDecimal());
+        else if (useMaximumAsInfinity && value > getMaxDecimal())
+            return Double.POSITIVE_INFINITY;
+        else
+            return (factor * (int) Math.ceil(value / factor));
+    }
+
     @Override
     public double getMaxDecimal() {
         return maxValue * factor;
diff --git a/core/src/main/java/com/graphhopper/routing/util/AbstractFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/AbstractFlagEncoder.java
index 48bb99f37..e8e52ede1 100644
--- a/core/src/main/java/com/graphhopper/routing/util/AbstractFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/AbstractFlagEncoder.java
@@ -57,7 +57,7 @@ public abstract class AbstractFlagEncoder implements FlagEncoder {
     protected DecimalEncodedValue avgSpeedEnc;
     // This value determines the maximal possible speed of any road regardless of the maxspeed value
     // lower values allow more compact representation of the routing graph
-    protected int maxPossibleSpeed;
+    protected double maxPossibleSpeed;
     private boolean blockFords = true;
     private boolean registered;
     protected EncodedValueLookup encodedValueLookup;
diff --git a/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java
index a441c39e1..3167d6870 100644
--- a/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/BikeCommonFlagEncoder.java
@@ -107,7 +107,7 @@ abstract public class BikeCommonFlagEncoder extends AbstractFlagEncoder {
         unpavedSurfaceTags.add("sand");
         unpavedSurfaceTags.add("wood");
 
-        maxPossibleSpeed = 30;
+        maxPossibleSpeed = avgSpeedEnc.getNextStorableValue(30);
 
         setTrackTypeSpeed("grade1", 18); // paved
         setTrackTypeSpeed("grade2", 12); // now unpaved ...
diff --git a/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java
index 5d610fc8b..0ddc5e6d9 100644
--- a/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/CarFlagEncoder.java
@@ -146,7 +146,7 @@ public class CarFlagEncoder extends AbstractFlagEncoder {
 
         // limit speed on bad surfaces to 30 km/h
         badSurfaceSpeed = 30;
-        maxPossibleSpeed = 140;
+        maxPossibleSpeed = avgSpeedEnc.getNextStorableValue(140);
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/util/FootFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/FootFlagEncoder.java
index 2e4695d87..146a21d92 100644
--- a/core/src/main/java/com/graphhopper/routing/util/FootFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/FootFlagEncoder.java
@@ -133,7 +133,7 @@ public class FootFlagEncoder extends AbstractFlagEncoder {
         allowedSacScale.add("mountain_hiking");
         allowedSacScale.add("demanding_mountain_hiking");
 
-        maxPossibleSpeed = FERRY_SPEED;
+        maxPossibleSpeed = avgSpeedEnc.getNextStorableValue(FERRY_SPEED);
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/util/MotorcycleFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/MotorcycleFlagEncoder.java
index 170b0810a..9bf9d4adb 100644
--- a/core/src/main/java/com/graphhopper/routing/util/MotorcycleFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/MotorcycleFlagEncoder.java
@@ -74,7 +74,7 @@ public class MotorcycleFlagEncoder extends CarFlagEncoder {
         preferSet.add("secondary");
         preferSet.add("tertiary");
 
-        maxPossibleSpeed = 120;
+        maxPossibleSpeed = avgSpeedEnc.getNextStorableValue(120);
 
         // autobahn
         defaultSpeedMap.put("motorway", 100);
diff --git a/core/src/main/java/com/graphhopper/routing/util/WheelchairFlagEncoder.java b/core/src/main/java/com/graphhopper/routing/util/WheelchairFlagEncoder.java
index 0e8e08e7b..177e47c38 100644
--- a/core/src/main/java/com/graphhopper/routing/util/WheelchairFlagEncoder.java
+++ b/core/src/main/java/com/graphhopper/routing/util/WheelchairFlagEncoder.java
@@ -98,7 +98,7 @@ public class WheelchairFlagEncoder extends FootFlagEncoder {
 
         allowedSacScale.clear();
 
-        maxPossibleSpeed = FERRY_SPEED;
+        maxPossibleSpeed = avgSpeedEnc.getNextStorableValue(FERRY_SPEED);
     }
 
     /**


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/ev/DecimalEncodedValueImplTest.java b/core/src/test/java/com/graphhopper/routing/ev/DecimalEncodedValueImplTest.java
index 7aacda1b5..5e7858820 100644
--- a/core/src/test/java/com/graphhopper/routing/ev/DecimalEncodedValueImplTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ev/DecimalEncodedValueImplTest.java
@@ -3,6 +3,8 @@ package com.graphhopper.routing.ev;
 import com.graphhopper.storage.IntsRef;
 import org.junit.jupiter.api.Test;
 
+import java.util.Random;
+
 import static org.junit.jupiter.api.Assertions.*;
 
 public class DecimalEncodedValueImplTest {
@@ -79,4 +81,59 @@ public class DecimalEncodedValueImplTest {
         assertEquals(5.5, testEnc.getDecimal(false, intsRef), .1);
         assertEquals(-5.5, testEnc.getDecimal(true, intsRef), .1);
     }
+
+    @Test
+    public void testNextStorableValue() {
+        DecimalEncodedValueImpl enc = new DecimalEncodedValueImpl("test", 4, 3, false);
+        enc.init(new EncodedValue.InitializerConfig());
+        IntsRef intsRef = new IntsRef(1);
+
+        // some values can be stored...
+        enc.setDecimal(false, intsRef, 3);
+        assertEquals(3, enc.getDecimal(false, intsRef));
+        // ... and some cannot:
+        enc.setDecimal(false, intsRef, 5);
+        assertEquals(6, enc.getDecimal(false, intsRef));
+
+        // getNextStorableValue tells us the next highest value we can store without such modification between set/get
+        assertEquals(0, enc.getNextStorableValue(0));
+        assertEquals(3, enc.getNextStorableValue(0.1));
+        assertEquals(3, enc.getNextStorableValue(1.5));
+        assertEquals(3, enc.getNextStorableValue(2.9));
+        assertEquals(3, enc.getNextStorableValue(3));
+        assertEquals(6, enc.getNextStorableValue(3.1));
+        assertEquals(6, enc.getNextStorableValue(4.5));
+        assertEquals(6, enc.getNextStorableValue(5.9));
+        assertEquals(45, enc.getNextStorableValue(44.3));
+        assertEquals(45, enc.getNextStorableValue(45));
+        // for values higher than 3*15=45 there is no next storable value, and we get an error
+        assertThrows(IllegalArgumentException.class, () -> enc.getNextStorableValue(46));
+
+        // check random values in [0, 45]
+        Random rnd = new Random();
+        for (int i = 0; i < 1000; i++) {
+            double value = rnd.nextDouble() * 45;
+            double nextStorable = enc.getNextStorableValue(value);
+            assertTrue(nextStorable >= value, "next storable value should be larger than the value");
+            enc.setDecimal(false, intsRef, nextStorable);
+            assertEquals(nextStorable, enc.getDecimal(false, intsRef), "next storable value should be returned without modification");
+        }
+    }
+
+    @Test
+    public void testNextStorableValue_maxInfinity() {
+        DecimalEncodedValueImpl enc = new DecimalEncodedValueImpl("test", 4, 0, 3, false, false, false, true);
+        enc.init(new EncodedValue.InitializerConfig());
+        assertEquals(12, enc.getNextStorableValue(11.2));
+        assertEquals(45, enc.getNextStorableValue(44.3));
+        assertEquals(45, enc.getNextStorableValue(45));
+        assertEquals(Double.POSITIVE_INFINITY, enc.getNextStorableValue(45.1));
+        assertEquals(Double.POSITIVE_INFINITY, enc.getNextStorableValue(48));
+        assertEquals(Double.POSITIVE_INFINITY, enc.getNextStorableValue(48.1));
+        IntsRef intsRef = new IntsRef(1);
+        assertThrows(IllegalArgumentException.class, () -> enc.setDecimal(false, intsRef, 48));
+        enc.setDecimal(false, intsRef, Double.POSITIVE_INFINITY);
+        assertEquals(Double.POSITIVE_INFINITY, enc.getDecimal(false, intsRef));
+    }
+
 }
\ No newline at end of file
diff --git a/core/src/test/java/com/graphhopper/routing/util/FootFlagEncoderTest.java b/core/src/test/java/com/graphhopper/routing/util/FootFlagEncoderTest.java
index a2715902d..f59589270 100644
--- a/core/src/test/java/com/graphhopper/routing/util/FootFlagEncoderTest.java
+++ b/core/src/test/java/com/graphhopper/routing/util/FootFlagEncoderTest.java
@@ -23,6 +23,7 @@ import com.graphhopper.routing.ev.BooleanEncodedValue;
 import com.graphhopper.routing.ev.DecimalEncodedValue;
 import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.GraphBuilder;
+import com.graphhopper.storage.GraphHopperStorage;
 import com.graphhopper.storage.IntsRef;
 import com.graphhopper.util.*;
 import org.junit.jupiter.api.Test;
@@ -455,4 +456,20 @@ public class FootFlagEncoderTest {
         node.setTag("barrier", "cattle_grid");
         assertFalse(tmpFootEncoder.isBarrier(node));
     }
+
+    @Test
+    public void maxSpeed() {
+        FootFlagEncoder encoder = new FootFlagEncoder(new PMap().putObject("speed_bits", 4).putObject("speed_factor", 2));
+        // The foot max speed is supposed to be 15km/h, but for speed_bits=4,speed_factor=2 as we use here 15 cannot
+        // be stored. In fact, when we set the speed of an edge to 15 and call the getter afterwards we get a value of 16
+        // because of the internal (scaled) integer representation:
+        EncodingManager em = EncodingManager.create(encoder);
+        GraphHopperStorage graph = new GraphBuilder(em).create();
+        EdgeIteratorState edge = graph.edge(0, 1).setDistance(100).set(encoder.getAverageSpeedEnc(), 15);
+        assertEquals(16, edge.get(encoder.getAverageSpeedEnc()));
+
+        // ... because of this we have to make sure the max speed is set to a value that cannot be exceeded even when
+        // such conversion occurs. in our case it must be 16 not 15!
+        assertEquals(16, encoder.getMaxSpeed());
+    }
 }