Add VersionCompatibility helper

3 files changed, 237 insertions, 0 deletions

diff --git a/component/abi-spec.json b/component/abi-spec.json
index 4e89b0e717c..d990a9077b4 100644
--- a/component/abi-spec.json
+++ b/component/abi-spec.json
@@ -158,6 +158,19 @@
       "public static final com.yahoo.component.Version emptyVersion"
     ]
   },
+  "com.yahoo.component.VersionCompatibility": {
+    "superClass": "java.lang.Object",
+    "interfaces": [],
+    "attributes": [
+      "public"
+    ],
+    "methods": [
+      "public static com.yahoo.component.VersionCompatibility fromVersionList(java.util.List)",
+      "public boolean accept(com.yahoo.component.Version, com.yahoo.component.Version)",
+      "public boolean refuse(com.yahoo.component.Version, com.yahoo.component.Version)"
+    ],
+    "fields": []
+  },
   "com.yahoo.component.VersionSpecification": {
     "superClass": "java.lang.Object",
     "interfaces": [
diff --git a/component/src/main/java/com/yahoo/component/VersionCompatibility.java b/component/src/main/java/com/yahoo/component/VersionCompatibility.java
new file mode 100644
index 00000000000..fb9f863f5f0
--- /dev/null
+++ b/component/src/main/java/com/yahoo/component/VersionCompatibility.java
@@ -0,0 +1,109 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.component;
+
+import java.util.List;
+import java.util.NavigableMap;
+import java.util.TreeMap;
+
+/**
+ * Logic for what platform and compile versions are incompatible.
+ *
+ * This class is instantiated with a list of versions which are only compatible with other versions
+ * that are not older than themselves. Each entry in this list is represented by a string, and any
+ * major, minor or micro with the value @{code *} means all versions are such boundaries.
+ * Versions A, B are incompatible iff. there exists an incompatibility boundary X such that
+ * (A ≥ X) ≠ (B ≥ X).
+ *
+ * @author jonmv
+ */
+public class VersionCompatibility {
+
+    private final Node root;
+
+    private VersionCompatibility(Node root) {
+        this.root = root;
+    }
+
+    public static VersionCompatibility fromVersionList(List<String> versions) {
+        Node root = new Node();
+        for (String spec : versions) {
+            String[] parts = spec.split("\\.");
+            if (parts.length < 1 || parts.length > 3)
+                throw new IllegalArgumentException("Each spec must have 1 to 3 parts, but found '" + spec + "'");
+
+            boolean wildcard = false;
+            Node node = root;
+            for (int i = 0; i < 3; i++) {
+                String part = i < parts.length ? parts[i] : wildcard ? null : "0";
+                if (wildcard && part != null && ! part.equals("*"))
+                    throw new IllegalArgumentException("Wildcard parts may only have wildcard children, but found '" + spec + "'");
+
+                if ("*".equals(part)) {
+                    wildcard = true;
+                    if (node.children.isEmpty())
+                        node = node.children.computeIfAbsent(-1, __ -> new Node());
+                    else
+                        throw new IllegalArgumentException("Wildcards may not have siblings, but got: " + versions);
+                }
+                else if (part != null) {
+                    int number = Integer.parseInt(part);
+                    if (number < 0)
+                        throw new IllegalArgumentException("Version parts must be non-negative, but found '" + spec + "'");
+                    if (node.children.containsKey(-1))
+                        throw new IllegalArgumentException("Wildcards may not have siblings, but got: " + versions);
+                    if (i < 2)
+                        node = node.children.computeIfAbsent(number, __ -> new Node());
+                    else if (node.children.put(number, new Node()) != null)
+                        throw new IllegalArgumentException("Duplicate element '" + spec + "'");
+                }
+            }
+        }
+        return new VersionCompatibility(root);
+    }
+
+    public boolean accept(Version first, Version second) {
+        return ! refuse(first, second);
+    }
+
+    public boolean refuse(Version first, Version second) {
+        if (first.compareTo(second) > 0)
+            return refuse(second, first);
+
+        if (first.compareTo(second) == 0)
+            return false;
+
+        return refuse(new int[]{  first.getMajor(),  first.getMinor(),  first.getMicro() },
+                      new int[]{ second.getMajor(), second.getMinor(), second.getMicro() },
+                      0, root, root);
+    }
+
+    private boolean refuse(int[] first, int[] second, int i, Node left, Node right) {
+        if (left == null && right == null) return false;
+        if (i == 3) return right != null;
+        int u = first[i], v = second[i];
+        if (left == right) {
+            Node wildcard = left.children.get(-1);
+            if (wildcard != null)
+                return u != v || refuse(first, second, i + 1, wildcard, wildcard);
+
+            if ( ! left.children.tailMap(u, false).headMap(v, false).isEmpty())
+                return true;
+
+            return refuse(first, second, i + 1, left.children.get(u), left.children.get(v));
+        }
+        if (left != null && (left.children.containsKey(-1) || ! left.children.tailMap(u, false).isEmpty()))
+            return true;
+
+        if (right != null && (right.children.containsKey(-1) || ! right.children.headMap(v, false).isEmpty()))
+            return true;
+
+        return refuse(first, second, i + 1, left == null ? null : left.children.get(u), right == null ? null : right.children.get(v));
+    }
+
+    private static class Node {
+
+        final NavigableMap<Integer, Node> children = new TreeMap<>();
+
+    }
+
+}
diff --git a/component/src/test/java/com/yahoo/component/VersionIncompatibilityTest.java b/component/src/test/java/com/yahoo/component/VersionIncompatibilityTest.java
new file mode 100644
index 00000000000..74be12c618c
--- /dev/null
+++ b/component/src/test/java/com/yahoo/component/VersionIncompatibilityTest.java
@@ -0,0 +1,115 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.component;
+
+import org.junit.Test;
+
+import java.util.List;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+/**
+ * @author jonmv
+ */
+public class VersionIncompatibilityTest {
+
+    @Test
+    public void testNoIncompatibilities() {
+        List<String> versions = List.of();
+        VersionCompatibility compatibility = VersionCompatibility.fromVersionList(versions);
+        assertTrue(compatibility.accept(new Version(0, 0, 0), new Version(0, 0, 0)));
+        assertTrue(compatibility.accept(new Version(0, 0, 0), new Version(0, 0, 1)));
+        assertTrue(compatibility.accept(new Version(0, 0, 0), new Version(0, 1, 0)));
+        assertTrue(compatibility.accept(new Version(0, 0, 0), new Version(1, 0, 0)));
+    }
+
+    @Test
+    public void testValidIncompatibilities() {
+        List<String> versions = List.of("1.2.*", "2", "3.*", "4.0.0", "4.0.1", "4.0.3", "4.1.0", "5");
+        VersionCompatibility compatibility = VersionCompatibility.fromVersionList(versions);
+        assertTrue (compatibility.accept(new Version(0, 0, 0), new Version(0, 0, 0)));
+        assertTrue (compatibility.accept(new Version(0, 0, 0), new Version(1, 1, 1)));
+        assertFalse(compatibility.accept(new Version(0, 0, 0), new Version(1, 2, 3)));
+        assertFalse(compatibility.accept(new Version(1, 1, 0), new Version(1, 2, 0)));
+        assertFalse(compatibility.accept(new Version(1, 2, 1), new Version(1, 2, 0)));
+        assertFalse(compatibility.accept(new Version(1, 1, 0), new Version(1, 3, 0)));
+        assertTrue (compatibility.accept(new Version(1, 2, 3), new Version(1, 2, 3)));
+        assertTrue (compatibility.accept(new Version(1, 3, 0), new Version(1, 9, 9)));
+        assertFalse(compatibility.accept(new Version(1, 3, 0), new Version(2, 0, 0)));
+        assertTrue (compatibility.accept(new Version(2, 0, 0), new Version(2, 2, 2)));
+        assertFalse(compatibility.accept(new Version(2, 0, 0), new Version(3, 0, 0)));
+        assertTrue (compatibility.accept(new Version(3, 0, 0), new Version(3, 0, 0)));
+        assertFalse(compatibility.accept(new Version(3, 0, 0), new Version(3, 1, 0)));
+        assertTrue (compatibility.accept(new Version(3, 0, 0), new Version(3, 0, 1)));
+        assertFalse(compatibility.accept(new Version(3, 0, 0), new Version(4, 0, 0)));
+        assertFalse(compatibility.accept(new Version(4, 0, 0), new Version(4, 0, 1)));
+        assertTrue (compatibility.accept(new Version(4, 0, 1), new Version(4, 0, 2)));
+        assertFalse(compatibility.accept(new Version(4, 0, 2), new Version(4, 0, 3)));
+        assertFalse(compatibility.accept(new Version(4, 0, 3), new Version(4, 1, 0)));
+        assertFalse(compatibility.accept(new Version(4, 1, 0), new Version(5, 0, 0)));
+        assertTrue (compatibility.accept(new Version(5, 0, 0), new Version(6, 0, 0)));
+        assertFalse(compatibility.accept(new Version(0, 0, 0), new Version(2, 0, 0)));
+        assertFalse(compatibility.accept(new Version(0, 0, 0), new Version(6, 0, 0)));
+    }
+
+    @Test
+    public void testIllegalIncompatibilities() {
+        try {
+            VersionCompatibility.fromVersionList(List.of("1", "*"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("*", "*"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("-1"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("0", "0"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("0", "0.0.0"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("0.0.0", "0.0.0"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("*.1"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("*", "*.*"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of(""));
+            fail();
+        }
+        catch (NumberFormatException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("0.0.0.0"));
+            fail();
+        }
+        catch (IllegalArgumentException expected) { }
+        try {
+            VersionCompatibility.fromVersionList(List.of("x"));
+            fail();
+        }
+        catch (NumberFormatException expected) { }
+    }
+
+}