JAVA-1404: Fix min token handling in TokenRange.contains (apache#813)

olim7t · web-flow · commit 697d90310ce1 · 2017-02-23T10:30:04.000-08:00
diff --git a/changelog/README.md b/changelog/README.md
@@ -1,5 +1,10 @@
 ## Changelog
 
+### 3.0.8 (in progress)
+
+- [bug] JAVA-1404: Fix min token handling in TokenRange.contains.
+
+
 ### 3.0.7
 
 - [bug] JAVA-1371: Reintroduce connection pool timeout.
diff --git a/driver-core/src/main/java/com/datastax/driver/core/TokenRange.java b/driver-core/src/main/java/com/datastax/driver/core/TokenRange.java
@@ -215,7 +215,7 @@ public List<TokenRange> intersectWith(TokenRange that) {
      * Checks whether this range contains a given token.
      *
      * @param token the token to check for.
-     * @return whether this range contains the token, i.e. {@code range.start &lt; token &lt;= range.end}.
+     * @return whether this range contains the token, i.e. {@code range.start < token <= range.end}.
      */
     public boolean contains(Token token) {
         return contains(token, false);
@@ -224,13 +224,27 @@ public boolean contains(Token token) {
     // isStart handles the case where the token is the start of another range, for example:
     // * ]1,2] contains 2, but it does not contain the start of ]2,3]
     // * ]1,2] does not contain 1, but it contains the start of ]1,3]
-    private boolean contains(Token token, boolean isStart) {
-        boolean isAfterStart = isStart ? token.compareTo(start) >= 0 : token.compareTo(start) > 0;
-        boolean isBeforeEnd = end.equals(factory.minToken()) ||
-                (isStart ? token.compareTo(end) < 0 : token.compareTo(end) <= 0);
-        return isWrappedAround()
-                ? isAfterStart || isBeforeEnd
-                : isAfterStart && isBeforeEnd;
+    @VisibleForTesting
+    boolean contains(Token token, boolean isStart) {
+        if (isEmpty()) {
+            return false;
+        }
+        Token minToken = factory.minToken();
+        if (end.equals(minToken)) {
+            if (start.equals(minToken)) { // ]min, min] = full ring, contains everything
+                return true;
+            } else if (token.equals(minToken)) {
+                return !isStart;
+            } else {
+                return isStart ? token.compareTo(start) >= 0 : token.compareTo(start) > 0;
+            }
+        } else {
+            boolean isAfterStart = isStart ? token.compareTo(start) >= 0 : token.compareTo(start) > 0;
+            boolean isBeforeEnd = isStart ? token.compareTo(end) < 0 : token.compareTo(end) <= 0;
+            return isWrappedAround()
+                    ? isAfterStart || isBeforeEnd //  ####]----]####
+                    : isAfterStart && isBeforeEnd; // ----]####]----
+        }
     }
 
     /**
diff --git a/driver-core/src/test/java/com/datastax/driver/core/TokenRangeAssert.java b/driver-core/src/test/java/com/datastax/driver/core/TokenRangeAssert.java
@@ -99,4 +99,14 @@ public TokenRangeAssert doesNotIntersect(TokenRange... that) {
         }
         return this;
     }
+
+    public TokenRangeAssert contains(Token token, boolean isStart) {
+        assertThat(actual.contains(token, isStart)).isTrue();
+        return this;
+    }
+
+    public TokenRangeAssert doesNotContain(Token token, boolean isStart) {
+        assertThat(actual.contains(token, isStart)).isFalse();
+        return this;
+    }
 }
diff --git a/driver-core/src/test/java/com/datastax/driver/core/TokenRangeTest.java b/driver-core/src/test/java/com/datastax/driver/core/TokenRangeTest.java
@@ -235,6 +235,45 @@ public void should_create_empty_token_ranges_if_too_many_splits() {
         }
     }
 
+    @Test(groups = "unit")
+    public void should_check_if_range_contains_token() {
+        // ]1,2] contains 2, but it does not contain the start of ]2,3]
+        assertThat(tokenRange(1, 2))
+                .contains(newM3PToken(2), false)
+                .doesNotContain(newM3PToken(2), true);
+        // ]1,2] does not contain 1, but it contains the start of ]1,3]
+        assertThat(tokenRange(1, 2))
+                .doesNotContain(newM3PToken(1), false)
+                .contains(newM3PToken(1), true);
+
+        // ]2,1] contains the start of ]min,5]
+        assertThat(tokenRange(2, 1))
+                .contains(minToken, true);
+
+        // ]min, 1] does not contain min, but it contains the start of ]min, 2]
+        assertThat(tokenRange(minToken, 1))
+                .doesNotContain(minToken, false)
+                .contains(minToken, true);
+        // ]1, min] contains min, but not the start of ]min, 2]
+        assertThat(tokenRange(1, minToken))
+                .contains(minToken, false)
+                .doesNotContain(minToken, true);
+
+        // An empty range contains nothing
+        assertThat(tokenRange(1, 1))
+                .doesNotContain(newM3PToken(1), true)
+                .doesNotContain(newM3PToken(1), false)
+                .doesNotContain(minToken, true)
+                .doesNotContain(minToken, false);
+
+        // The whole ring contains everything
+        assertThat(tokenRange(minToken, minToken))
+                .contains(minToken, true)
+                .contains(minToken, false)
+                .contains(newM3PToken(1), true)
+                .contains(newM3PToken(1), false);
+    }
+
     private TokenRange tokenRange(long start, long end) {
         return new TokenRange(newM3PToken(start), newM3PToken(end), factory);
     }

Original file line number	Diff line number	Diff line change
`@@ -99,4 +99,14 @@ public TokenRangeAssert doesNotIntersect(TokenRange... that) {`
`99`	`99`	`}`
`100`	`100`	`return this;`
`101`	`101`	`}`
	`102`	`+`
	`103`	`+ public TokenRangeAssert contains(Token token, boolean isStart) {`
	`104`	`+ assertThat(actual.contains(token, isStart)).isTrue();`
	`105`	`+ return this;`
	`106`	`+ }`
	`107`	`+`
	`108`	`+ public TokenRangeAssert doesNotContain(Token token, boolean isStart) {`
	`109`	`+ assertThat(actual.contains(token, isStart)).isFalse();`
	`110`	`+ return this;`
	`111`	`+ }`
`102`	`112`	`}`