catalog-model/src/main/java/org/openecomp/sdc/be/model/tosca/version/ComparableVersion.java

   1 /*-
   2  * ============LICENSE_START=======================================================
   3  * SDC
   4  * ================================================================================
   5  * Copyright (C) 2017 AT&T Intellectual Property. All rights reserved.
   6  * ================================================================================
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  * ============LICENSE_END=========================================================
  19  */
  20
  21 package org.openecomp.sdc.be.model.tosca.version;
  22
  23 /*
  24  * Licensed to the Apache Software Foundation (ASF) under one
  25  * or more contributor license agreements.  See the NOTICE file
  26  * distributed with this work for additional information
  27  * regarding copyright ownership.  The ASF licenses this file
  28  * to you under the Apache License, Version 2.0 (the
  29  * "License"); you may not use this file except in compliance
  30  * with the License.  You may obtain a copy of the License at
  31  *
  32  *  http://www.apache.org/licenses/LICENSE-2.0
  33  *
  34  * Unless required by applicable law or agreed to in writing,
  35  * software distributed under the License is distributed on an
  36  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  37  * KIND, either express or implied.  See the License for the
  38  * specific language governing permissions and limitations
  39  * under the License.
  40  */
  41
  42 import java.math.BigInteger;
  43 import java.util.*;
  44
  45 /**
  46  * Generic implementation of version comparison.
  47  *
  48  * <p>
  49  * Features:
  50  * <ul>
  51  * <li>mixing of '<code>-</code>' (dash) and '<code>.</code>' (dot)
  52  * separators,</li>
  53  * <li>transition between characters and digits also constitutes a separator:
  54  * <code>1.0alpha1 =&gt; [1, 0, alpha, 1]</code></li>
  55  * <li>unlimited number of version components,</li>
  56  * <li>version components in the text can be digits or strings,</li>
  57  * <li>strings are checked for well-known qualifiers and the qualifier ordering
  58  * is used for version ordering. Well-known qualifiers (case insensitive) are:
  59  * <ul>
  60  * <li><code>alpha</code> or <code>a</code></li>
  61  * <li><code>beta</code> or <code>b</code></li>
  62  * <li><code>milestone</code> or <code>m</code></li>
  63  * <li><code>rc</code> or <code>cr</code></li>
  64  * <li><code>snapshot</code></li>
  65  * <li><code>(the empty string)</code> or <code>ga</code> or
  66  * <code>final</code></li>
  67  * <li><code>sp</code></li>
  68  * </ul>
  69  * Unknown qualifiers are considered after known qualifiers, with lexical order
  70  * (always case insensitive),</li>
  71  * <li>a dash usually precedes a qualifier, and is always less important than
  72  * something preceded with a dot.</li>
  73  * </ul>
  74  * </p>
  75  *
  76  * @see <a href=
  77  *      "https://cwiki.apache.org/confluence/display/MAVENOLD/Versioning">"Versioning"
  78  *      on Maven Wiki</a>
  79  * @author <a href="mailto:kenney@apache.org">Kenney Westerhof</a>
  80  * @author <a href="mailto:hboutemy@apache.org">Hervé Boutemy</a>
  81  */
  82 public class ComparableVersion implements Comparable<ComparableVersion> {
  83     private String value;
  84
  85     private String canonical;
  86
  87     private ListItem items;
  88
  89     private interface Item {
  90         int INTEGER_ITEM = 0;
  91         int STRING_ITEM = 1;
  92         int LIST_ITEM = 2;
  93
  94         int compareTo(Item item);
  95
  96         int getType();
  97
  98         boolean isNull();
  99     }
 100
 101     /**
 102      * Represents a numeric item in the version item list.
 103      */
 104     private static class IntegerItem implements Item {
 105         private static final String INVALID_ITEM = "invalid item: ";
 106                 private static final BigInteger BIG_INTEGER_ZERO = new BigInteger("0");
 107         private final BigInteger value;
 108         public static final IntegerItem ZERO = new IntegerItem();
 109
 110         private IntegerItem() {
 111             this.value = BIG_INTEGER_ZERO;
 112         }
 113
 114         public IntegerItem(String str) {
 115             this.value = new BigInteger(str);
 116         }
 117
 118         @Override
 119         public int getType() {
 120             return INTEGER_ITEM;
 121         }
 122
 123         @Override
 124         public boolean isNull() {
 125             return BIG_INTEGER_ZERO.equals(value);
 126         }
 127
 128         @Override
 129         public int compareTo(Item item) {
 130             if (item == null) {
 131                 return BIG_INTEGER_ZERO.equals(value) ? 0 : 1; // 1.0 == 1, 1.1
 132                                                                 // > 1
 133             }
 134
 135             switch (item.getType()) {
 136             case INTEGER_ITEM:
 137                 return value.compareTo(((IntegerItem) item).value);
 138
 139             case STRING_ITEM:
 140                 return 1; // 1.1 > 1-sp
 141
 142             case LIST_ITEM:
 143                 return 1; // 1.1 > 1-1
 144
 145             default:
 146                 throw new RuntimeException(INVALID_ITEM + item.getClass());
 147             }
 148         }
 149
 150         @Override
 151         public String toString() {
 152             return value.toString();
 153         }
 154     }
 155
 156     /**
 157      * Represents a string in the version item list, usually a qualifier.
 158      */
 159     private static class StringItem implements Item {
 160         private static final String[] QUALIFIERS = { "alpha", "beta", "milestone", "rc", "snapshot", "", "sp" };
 161
 162         private static final List<String> _QUALIFIERS = Arrays.asList(QUALIFIERS);
 163
 164         private static final Properties ALIASES = new Properties();
 165         static {
 166             ALIASES.put("ga", "");
 167             ALIASES.put("final", "");
 168             ALIASES.put("cr", "rc");
 169         }
 170
 171         /**
 172          * A comparable value for the empty-string qualifier. This one is used
 173          * to determine if a given qualifier makes the version older than one
 174          * without a qualifier, or more recent.
 175          */
 176         private static final String RELEASE_VERSION_INDEX = String.valueOf(_QUALIFIERS.indexOf(""));
 177
 178         private String value;
 179
 180         public StringItem(String value, boolean followedByDigit) {
 181             if (followedByDigit && value.length() == 1) {
 182                 // a1 = alpha-1, b1 = beta-1, m1 = milestone-1
 183                 switch (value.charAt(0)) {
 184                 case 'a':
 185                     value = "alpha";
 186                     break;
 187                 case 'b':
 188                     value = "beta";
 189                     break;
 190                 case 'm':
 191                     value = "milestone";
 192                     break;
 193                 default:
 194                     throw new RuntimeException("Invalid item");
 195                 }
 196             }
 197             this.value = ALIASES.getProperty(value, value);
 198         }
 199
 200         @Override
 201         public int getType() {
 202             return STRING_ITEM;
 203         }
 204
 205         @Override
 206         public boolean isNull() {
 207             return (comparableQualifier(value).compareTo(RELEASE_VERSION_INDEX) == 0);
 208         }
 209
 210         /**
 211          * Returns a comparable value for a qualifier.
 212          *
 213          * This method takes into account the ordering of known qualifiers then
 214          * unknown qualifiers with lexical ordering.
 215          *
 216          * just returning an Integer with the index here is faster, but requires
 217          * a lot of if/then/else to check for -1 or QUALIFIERS.size and then
 218          * resort to lexical ordering. Most comparisons are decided by the first
 219          * character, so this is still fast. If more characters are needed then
 220          * it requires a lexical sort anyway.
 221          *
 222          * @param qualifier
 223          * @return an equivalent value that can be used with lexical comparison
 224          */
 225         public static String comparableQualifier(String qualifier) {
 226             int i = _QUALIFIERS.indexOf(qualifier);
 227
 228             return i == -1 ? (_QUALIFIERS.size() + "-" + qualifier) : String.valueOf(i);
 229         }
 230
 231         // @Override
 232         public int compareTo(Item item) {
 233             if (item == null) {
 234                 // 1-rc < 1, 1-ga > 1
 235                 return comparableQualifier(value).compareTo(RELEASE_VERSION_INDEX);
 236             }
 237             switch (item.getType()) {
 238             case INTEGER_ITEM:
 239                 return -1; // 1.any < 1.1 ?
 240
 241             case STRING_ITEM:
 242                 return comparableQualifier(value).compareTo(comparableQualifier(((StringItem) item).value));
 243
 244             case LIST_ITEM:
 245                 return -1; // 1.any < 1-1
 246
 247             default:
 248                 throw new RuntimeException("invalid item: " + item.getClass());
 249             }
 250         }
 251
 252         @Override
 253         public String toString() {
 254             return value;
 255         }
 256     }
 257
 258     /**
 259      * Represents a version list item. This class is used both for the global
 260      * item list and for sub-lists (which start with '-(number)' in the version
 261      * specification).
 262      */
 263     private static class ListItem extends ArrayList<Item> implements Item {
 264
 265         @Override
 266         public int getType() {
 267             return LIST_ITEM;
 268         }
 269
 270         @Override
 271         public boolean isNull() {
 272             return (size() == 0);
 273         }
 274
 275         void normalize() {
 276             for (ListIterator<Item> iterator = listIterator(size()); iterator.hasPrevious();) {
 277                 Item item = iterator.previous();
 278                 if (item.isNull()) {
 279                     iterator.remove(); // remove null trailing items: 0, "",
 280                                         // empty list
 281                 } else {
 282                     break;
 283                 }
 284             }
 285         }
 286
 287         @Override
 288         public int compareTo(Item item) {
 289             if (item == null) {
 290                 if (size() == 0) {
 291                     return 0; // 1-0 = 1- (normalize) = 1
 292                 }
 293                 Item first = get(0);
 294                 return first.compareTo(null);
 295             }
 296             switch (item.getType()) {
 297             case INTEGER_ITEM:
 298                 return -1; // 1-1 < 1.0.x
 299
 300             case STRING_ITEM:
 301                 return 1; // 1-1 > 1-sp
 302
 303             case LIST_ITEM:
 304                 Iterator<Item> left = iterator();
 305                 Iterator<Item> right = ((ListItem) item).iterator();
 306
 307                 while (left.hasNext() || right.hasNext()) {
 308                     Item l = left.hasNext() ? left.next() : null;
 309                     Item r = right.hasNext() ? right.next() : null;
 310
 311                     int result = 0;
 312                     if (r != null && l != null) {
 313                         result = l.compareTo(r);
 314                     } else if (r == null && l == null) {
 315                         result = 0;
 316                     } else if (l == null) {
 317                         result = -1;
 318                     } else {
 319                         result = 1;
 320                     }
 321
 322                     // if this is shorter, then invert the compare and mul with
 323                     // -1
 324                     // int result = (l == null ? (r == null ? 0 : -1 *
 325                     // r.compareTo(l)) : l.compareTo(r));
 326
 327                     if (result != 0) {
 328                         return result;
 329                     }
 330                 }
 331
 332                 return 0;
 333
 334             default:
 335                 throw new RuntimeException("invalid item: " + item.getClass());
 336             }
 337         }
 338
 339         @Override
 340         public String toString() {
 341             StringBuilder buffer = new StringBuilder("(");
 342             for (Iterator<Item> iter = iterator(); iter.hasNext();) {
 343                 buffer.append(iter.next());
 344                 if (iter.hasNext()) {
 345                     buffer.append(',');
 346                 }
 347             }
 348             buffer.append(')');
 349             return buffer.toString();
 350         }
 351     }
 352
 353     public ComparableVersion(String version) {
 354         parseVersion(version);
 355     }
 356
 357     public final void parseVersion(String version) {
 358         this.value = version;
 359
 360         items = new ListItem();
 361
 362         version = version.toLowerCase(Locale.ENGLISH);
 363
 364         ListItem list = items;
 365
 366         Stack<Item> stack = new Stack<>();
 367         stack.push(list);
 368
 369         boolean isDigit = false;
 370
 371         int startIndex = 0;
 372
 373         for (int i = 0; i < version.length(); i++) {
 374             char c = version.charAt(i);
 375
 376             if (c == '.') {
 377                 if (i == startIndex) {
 378                     list.add(IntegerItem.ZERO);
 379                 } else {
 380                     list.add(parseItem(isDigit, version.substring(startIndex, i)));
 381                 }
 382                 startIndex = i + 1;
 383             } else if (c == '-') {
 384                 if (i == startIndex) {
 385                     list.add(IntegerItem.ZERO);
 386                 } else {
 387                     list.add(parseItem(isDigit, version.substring(startIndex, i)));
 388                 }
 389                 startIndex = i + 1;
 390
 391                 if (isDigit) {
 392                     list.normalize(); // 1.0-* = 1-*
 393
 394                     if ((i + 1 < version.length()) && Character.isDigit(version.charAt(i + 1))) {
 395                         // new ListItem only if previous were digits and new
 396                         // char is a digit,
 397                         // ie need to differentiate only 1.1 from 1-1
 398                         list.add(list = new ListItem());
 399
 400                         stack.push(list);
 401                     }
 402                 }
 403             } else if (Character.isDigit(c)) {
 404                 if (!isDigit && i > startIndex) {
 405                     list.add(new StringItem(version.substring(startIndex, i), true));
 406                     startIndex = i;
 407                 }
 408
 409                 isDigit = true;
 410             } else {
 411                 if (isDigit && i > startIndex) {
 412                     list.add(parseItem(true, version.substring(startIndex, i)));
 413                     startIndex = i;
 414                 }
 415
 416                 isDigit = false;
 417             }
 418         }
 419
 420         if (version.length() > startIndex) {
 421             list.add(parseItem(isDigit, version.substring(startIndex)));
 422         }
 423
 424         while (!stack.isEmpty()) {
 425             list = (ListItem) stack.pop();
 426             list.normalize();
 427         }
 428
 429         canonical = items.toString();
 430     }
 431
 432     private static Item parseItem(boolean isDigit, String buf) {
 433         return isDigit ? new IntegerItem(buf) : new StringItem(buf, false);
 434     }
 435
 436     @Override
 437     public int compareTo(ComparableVersion o) {
 438         return items.compareTo(o.items);
 439     }
 440
 441     @Override
 442     public String toString() {
 443         return value;
 444     }
 445
 446     @Override
 447     public boolean equals(Object o) {
 448         return (o instanceof ComparableVersion) && canonical.equals(((ComparableVersion) o).canonical);
 449     }
 450
 451     @Override
 452     public int hashCode() {
 453         return canonical.hashCode();
 454     }
 455 }