View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.maven.artifact.versioning;
20  
21  import java.math.BigInteger;
22  import java.util.ArrayDeque;
23  import java.util.ArrayList;
24  import java.util.Arrays;
25  import java.util.Deque;
26  import java.util.Iterator;
27  import java.util.List;
28  import java.util.Locale;
29  import java.util.Properties;
30  
31  /**
32   * <p>
33   * Generic implementation of version comparison.
34   * </p>
35   *
36   * Features:
37   * <ul>
38   * <li>mixing of '<code>-</code>' (hyphen) and '<code>.</code>' (dot) separators,</li>
39   * <li>transition between characters and digits also constitutes a separator:
40   *     <code>1.0alpha1 =&gt; [1, 0, alpha, 1]</code></li>
41   * <li>unlimited number of version components,</li>
42   * <li>version components in the text can be digits or strings,</li>
43   * <li>strings are checked for well-known qualifiers and the qualifier ordering is used for version ordering.
44   *     Well-known qualifiers (case insensitive) are:<ul>
45   *     <li><code>alpha</code> or <code>a</code></li>
46   *     <li><code>beta</code> or <code>b</code></li>
47   *     <li><code>milestone</code> or <code>m</code></li>
48   *     <li><code>rc</code> or <code>cr</code></li>
49   *     <li><code>snapshot</code></li>
50   *     <li><code>(the empty string)</code> or <code>ga</code> or <code>final</code></li>
51   *     <li><code>sp</code></li>
52   *     </ul>
53   *     Unknown qualifiers are considered after known qualifiers, with lexical order (always case insensitive),
54   *   </li>
55   * <li>a hyphen usually precedes a qualifier, and is always less important than digits/number, for example
56   *   {@code 1.0.RC2 < 1.0-RC3 < 1.0.1}; but prefer {@code 1.0.0-RC1} over {@code 1.0.0.RC1}, and more
57   *   generally: {@code 1.0.X2 < 1.0-X3 < 1.0.1} for any string {@code X}; but prefer {@code 1.0.0-X1}
58   *   over {@code 1.0.0.X1}.</li>
59   * </ul>
60   *
61   * @see <a href="https://cwiki.apache.org/confluence/display/MAVENOLD/Versioning">"Versioning" on Maven Wiki</a>
62   * @author <a href="mailto:kenney@apache.org">Kenney Westerhof</a>
63   * @author <a href="mailto:hboutemy@apache.org">Hervé Boutemy</a>
64   */
65  public class ComparableVersion implements Comparable<ComparableVersion> {
66      private static final int MAX_INTITEM_LENGTH = 9;
67  
68      private static final int MAX_LONGITEM_LENGTH = 18;
69  
70      private String value;
71  
72      private String canonical;
73  
74      private ListItem items;
75  
76      private interface Item {
77          int INT_ITEM = 3;
78          int LONG_ITEM = 4;
79          int BIGINTEGER_ITEM = 0;
80          int STRING_ITEM = 1;
81          int LIST_ITEM = 2;
82  
83          int compareTo(Item item);
84  
85          int getType();
86  
87          boolean isNull();
88      }
89  
90      /**
91       * Represents a numeric item in the version item list that can be represented with an int.
92       */
93      private static class IntItem implements Item {
94          private final int value;
95  
96          public static final IntItem ZERO = new IntItem();
97  
98          private IntItem() {
99              this.value = 0;
100         }
101 
102         IntItem(String str) {
103             this.value = Integer.parseInt(str);
104         }
105 
106         @Override
107         public int getType() {
108             return INT_ITEM;
109         }
110 
111         @Override
112         public boolean isNull() {
113             return value == 0;
114         }
115 
116         @Override
117         public int compareTo(Item item) {
118             if (item == null) {
119                 return (value == 0) ? 0 : 1; // 1.0 == 1, 1.1 > 1
120             }
121 
122             switch (item.getType()) {
123                 case INT_ITEM:
124                     int itemValue = ((IntItem) item).value;
125                     return Integer.compare(value, itemValue);
126                 case LONG_ITEM:
127                 case BIGINTEGER_ITEM:
128                     return -1;
129 
130                 case STRING_ITEM:
131                     return 1; // 1.1 > 1-sp
132 
133                 case LIST_ITEM:
134                     return 1; // 1.1 > 1-1
135 
136                 default:
137                     throw new IllegalStateException("invalid item: " + item.getClass());
138             }
139         }
140 
141         @Override
142         public boolean equals(Object o) {
143             if (this == o) {
144                 return true;
145             }
146             if (o == null || getClass() != o.getClass()) {
147                 return false;
148             }
149 
150             IntItem intItem = (IntItem) o;
151 
152             return value == intItem.value;
153         }
154 
155         @Override
156         public int hashCode() {
157             return value;
158         }
159 
160         @Override
161         public String toString() {
162             return Integer.toString(value);
163         }
164     }
165 
166     /**
167      * Represents a numeric item in the version item list that can be represented with a long.
168      */
169     private static class LongItem implements Item {
170         private final long value;
171 
172         LongItem(String str) {
173             this.value = Long.parseLong(str);
174         }
175 
176         @Override
177         public int getType() {
178             return LONG_ITEM;
179         }
180 
181         @Override
182         public boolean isNull() {
183             return value == 0;
184         }
185 
186         @Override
187         public int compareTo(Item item) {
188             if (item == null) {
189                 return (value == 0) ? 0 : 1; // 1.0 == 1, 1.1 > 1
190             }
191 
192             switch (item.getType()) {
193                 case INT_ITEM:
194                     return 1;
195                 case LONG_ITEM:
196                     long itemValue = ((LongItem) item).value;
197                     return Long.compare(value, itemValue);
198                 case BIGINTEGER_ITEM:
199                     return -1;
200 
201                 case STRING_ITEM:
202                     return 1; // 1.1 > 1-sp
203 
204                 case LIST_ITEM:
205                     return 1; // 1.1 > 1-1
206 
207                 default:
208                     throw new IllegalStateException("invalid item: " + item.getClass());
209             }
210         }
211 
212         @Override
213         public boolean equals(Object o) {
214             if (this == o) {
215                 return true;
216             }
217             if (o == null || getClass() != o.getClass()) {
218                 return false;
219             }
220 
221             LongItem longItem = (LongItem) o;
222 
223             return value == longItem.value;
224         }
225 
226         @Override
227         public int hashCode() {
228             return (int) (value ^ (value >>> 32));
229         }
230 
231         @Override
232         public String toString() {
233             return Long.toString(value);
234         }
235     }
236 
237     /**
238      * Represents a numeric item in the version item list.
239      */
240     private static class BigIntegerItem implements Item {
241         private final BigInteger value;
242 
243         BigIntegerItem(String str) {
244             this.value = new BigInteger(str);
245         }
246 
247         @Override
248         public int getType() {
249             return BIGINTEGER_ITEM;
250         }
251 
252         @Override
253         public boolean isNull() {
254             return BigInteger.ZERO.equals(value);
255         }
256 
257         @Override
258         public int compareTo(Item item) {
259             if (item == null) {
260                 return BigInteger.ZERO.equals(value) ? 0 : 1; // 1.0 == 1, 1.1 > 1
261             }
262 
263             switch (item.getType()) {
264                 case INT_ITEM:
265                 case LONG_ITEM:
266                     return 1;
267 
268                 case BIGINTEGER_ITEM:
269                     return value.compareTo(((BigIntegerItem) item).value);
270 
271                 case STRING_ITEM:
272                     return 1; // 1.1 > 1-sp
273 
274                 case LIST_ITEM:
275                     return 1; // 1.1 > 1-1
276 
277                 default:
278                     throw new IllegalStateException("invalid item: " + item.getClass());
279             }
280         }
281 
282         @Override
283         public boolean equals(Object o) {
284             if (this == o) {
285                 return true;
286             }
287             if (o == null || getClass() != o.getClass()) {
288                 return false;
289             }
290 
291             BigIntegerItem that = (BigIntegerItem) o;
292 
293             return value.equals(that.value);
294         }
295 
296         @Override
297         public int hashCode() {
298             return value.hashCode();
299         }
300 
301         public String toString() {
302             return value.toString();
303         }
304     }
305 
306     /**
307      * Represents a string in the version item list, usually a qualifier.
308      */
309     private static class StringItem implements Item {
310         private static final List<String> QUALIFIERS =
311                 Arrays.asList("alpha", "beta", "milestone", "rc", "snapshot", "", "sp");
312 
313         private static final Properties ALIASES = new Properties();
314 
315         static {
316             ALIASES.put("ga", "");
317             ALIASES.put("final", "");
318             ALIASES.put("release", "");
319             ALIASES.put("cr", "rc");
320         }
321 
322         /**
323          * A comparable value for the empty-string qualifier. This one is used to determine if a given qualifier makes
324          * the version older than one without a qualifier, or more recent.
325          */
326         private static final String RELEASE_VERSION_INDEX = String.valueOf(QUALIFIERS.indexOf(""));
327 
328         private final String value;
329 
330         StringItem(String value, boolean followedByDigit) {
331             if (followedByDigit && value.length() == 1) {
332                 // a1 = alpha-1, b1 = beta-1, m1 = milestone-1
333                 switch (value.charAt(0)) {
334                     case 'a':
335                         value = "alpha";
336                         break;
337                     case 'b':
338                         value = "beta";
339                         break;
340                     case 'm':
341                         value = "milestone";
342                         break;
343                     default:
344                 }
345             }
346             this.value = ALIASES.getProperty(value, value);
347         }
348 
349         @Override
350         public int getType() {
351             return STRING_ITEM;
352         }
353 
354         @Override
355         public boolean isNull() {
356             return (comparableQualifier(value).compareTo(RELEASE_VERSION_INDEX) == 0);
357         }
358 
359         /**
360          * Returns a comparable value for a qualifier.
361          *
362          * This method takes into account the ordering of known qualifiers then unknown qualifiers with lexical
363          * ordering.
364          *
365          * just returning an Integer with the index here is faster, but requires a lot of if/then/else to check for -1
366          * or QUALIFIERS.size and then resort to lexical ordering. Most comparisons are decided by the first character,
367          * so this is still fast. If more characters are needed then it requires a lexical sort anyway.
368          *
369          * @param qualifier
370          * @return an equivalent value that can be used with lexical comparison
371          */
372         public static String comparableQualifier(String qualifier) {
373             int i = QUALIFIERS.indexOf(qualifier);
374 
375             return i == -1 ? (QUALIFIERS.size() + "-" + qualifier) : String.valueOf(i);
376         }
377 
378         @Override
379         public int compareTo(Item item) {
380             if (item == null) {
381                 // 1-rc < 1, 1-ga > 1
382                 return comparableQualifier(value).compareTo(RELEASE_VERSION_INDEX);
383             }
384             switch (item.getType()) {
385                 case INT_ITEM:
386                 case LONG_ITEM:
387                 case BIGINTEGER_ITEM:
388                     return -1; // 1.any < 1.1 ?
389 
390                 case STRING_ITEM:
391                     return comparableQualifier(value).compareTo(comparableQualifier(((StringItem) item).value));
392 
393                 case LIST_ITEM:
394                     return -1; // 1.any < 1-1
395 
396                 default:
397                     throw new IllegalStateException("invalid item: " + item.getClass());
398             }
399         }
400 
401         @Override
402         public boolean equals(Object o) {
403             if (this == o) {
404                 return true;
405             }
406             if (o == null || getClass() != o.getClass()) {
407                 return false;
408             }
409 
410             StringItem that = (StringItem) o;
411 
412             return value.equals(that.value);
413         }
414 
415         @Override
416         public int hashCode() {
417             return value.hashCode();
418         }
419 
420         public String toString() {
421             return value;
422         }
423     }
424 
425     /**
426      * Represents a version list item. This class is used both for the global item list and for sub-lists (which start
427      * with '-(number)' in the version specification).
428      */
429     private static class ListItem extends ArrayList<Item> implements Item {
430         @Override
431         public int getType() {
432             return LIST_ITEM;
433         }
434 
435         @Override
436         public boolean isNull() {
437             return (size() == 0);
438         }
439 
440         void normalize() {
441             for (int i = size() - 1; i >= 0; i--) {
442                 Item lastItem = get(i);
443 
444                 if (lastItem.isNull()) {
445                     // remove null trailing items: 0, "", empty list
446                     remove(i);
447                 } else if (!(lastItem instanceof ListItem)) {
448                     break;
449                 }
450             }
451         }
452 
453         @Override
454         public int compareTo(Item item) {
455             if (item == null) {
456                 if (size() == 0) {
457                     return 0; // 1-0 = 1- (normalize) = 1
458                 }
459                 // Compare the entire list of items with null - not just the first one, MNG-6964
460                 for (Item i : this) {
461                     int result = i.compareTo(null);
462                     if (result != 0) {
463                         return result;
464                     }
465                 }
466                 return 0;
467             }
468             switch (item.getType()) {
469                 case INT_ITEM:
470                 case LONG_ITEM:
471                 case BIGINTEGER_ITEM:
472                     return -1; // 1-1 < 1.0.x
473 
474                 case STRING_ITEM:
475                     return 1; // 1-1 > 1-sp
476 
477                 case LIST_ITEM:
478                     Iterator<Item> left = iterator();
479                     Iterator<Item> right = ((ListItem) item).iterator();
480 
481                     while (left.hasNext() || right.hasNext()) {
482                         Item l = left.hasNext() ? left.next() : null;
483                         Item r = right.hasNext() ? right.next() : null;
484 
485                         // if this is shorter, then invert the compare and mul with -1
486                         int result = l == null ? (r == null ? 0 : -1 * r.compareTo(l)) : l.compareTo(r);
487 
488                         if (result != 0) {
489                             return result;
490                         }
491                     }
492 
493                     return 0;
494 
495                 default:
496                     throw new IllegalStateException("invalid item: " + item.getClass());
497             }
498         }
499 
500         @Override
501         public String toString() {
502             StringBuilder buffer = new StringBuilder();
503             for (Item item : this) {
504                 if (buffer.length() > 0) {
505                     buffer.append((item instanceof ListItem) ? '-' : '.');
506                 }
507                 buffer.append(item);
508             }
509             return buffer.toString();
510         }
511 
512         /**
513          * Return the contents in the same format that is used when you call toString() on a List.
514          */
515         private String toListString() {
516             StringBuilder buffer = new StringBuilder();
517             buffer.append("[");
518             for (Item item : this) {
519                 if (buffer.length() > 1) {
520                     buffer.append(", ");
521                 }
522                 if (item instanceof ListItem) {
523                     buffer.append(((ListItem) item).toListString());
524                 } else {
525                     buffer.append(item);
526                 }
527             }
528             buffer.append("]");
529             return buffer.toString();
530         }
531     }
532 
533     public ComparableVersion(String version) {
534         parseVersion(version);
535     }
536 
537     @SuppressWarnings("checkstyle:innerassignment")
538     public final void parseVersion(String version) {
539         this.value = version;
540 
541         items = new ListItem();
542 
543         version = version.toLowerCase(Locale.ENGLISH);
544 
545         ListItem list = items;
546 
547         Deque<Item> stack = new ArrayDeque<>();
548         stack.push(list);
549 
550         boolean isDigit = false;
551 
552         int startIndex = 0;
553 
554         for (int i = 0; i < version.length(); i++) {
555             char c = version.charAt(i);
556 
557             if (c == '.') {
558                 if (i == startIndex) {
559                     list.add(IntItem.ZERO);
560                 } else {
561                     list.add(parseItem(isDigit, version.substring(startIndex, i)));
562                 }
563                 startIndex = i + 1;
564             } else if (c == '-') {
565                 if (i == startIndex) {
566                     list.add(IntItem.ZERO);
567                 } else {
568                     list.add(parseItem(isDigit, version.substring(startIndex, i)));
569                 }
570                 startIndex = i + 1;
571 
572                 list.add(list = new ListItem());
573                 stack.push(list);
574             } else if (Character.isDigit(c)) {
575                 if (!isDigit && i > startIndex) {
576                     // 1.0.0.X1 < 1.0.0-X2
577                     // treat .X as -X for any string qualifier X
578                     if (!list.isEmpty()) {
579                         list.add(list = new ListItem());
580                         stack.push(list);
581                     }
582 
583                     list.add(new StringItem(version.substring(startIndex, i), true));
584                     startIndex = i;
585 
586                     list.add(list = new ListItem());
587                     stack.push(list);
588                 }
589 
590                 isDigit = true;
591             } else {
592                 if (isDigit && i > startIndex) {
593                     list.add(parseItem(true, version.substring(startIndex, i)));
594                     startIndex = i;
595 
596                     list.add(list = new ListItem());
597                     stack.push(list);
598                 }
599 
600                 isDigit = false;
601             }
602         }
603 
604         if (version.length() > startIndex) {
605             // 1.0.0.X1 < 1.0.0-X2
606             // treat .X as -X for any string qualifier X
607             if (!isDigit && !list.isEmpty()) {
608                 list.add(list = new ListItem());
609                 stack.push(list);
610             }
611 
612             list.add(parseItem(isDigit, version.substring(startIndex)));
613         }
614 
615         while (!stack.isEmpty()) {
616             list = (ListItem) stack.pop();
617             list.normalize();
618         }
619     }
620 
621     private static Item parseItem(boolean isDigit, String buf) {
622         if (isDigit) {
623             buf = stripLeadingZeroes(buf);
624             if (buf.length() <= MAX_INTITEM_LENGTH) {
625                 // lower than 2^31
626                 return new IntItem(buf);
627             } else if (buf.length() <= MAX_LONGITEM_LENGTH) {
628                 // lower than 2^63
629                 return new LongItem(buf);
630             }
631             return new BigIntegerItem(buf);
632         }
633         return new StringItem(buf, false);
634     }
635 
636     private static String stripLeadingZeroes(String buf) {
637         if (buf == null || buf.isEmpty()) {
638             return "0";
639         }
640         for (int i = 0; i < buf.length(); ++i) {
641             char c = buf.charAt(i);
642             if (c != '0') {
643                 return buf.substring(i);
644             }
645         }
646         return buf;
647     }
648 
649     @Override
650     public int compareTo(ComparableVersion o) {
651         return items.compareTo(o.items);
652     }
653 
654     @Override
655     public String toString() {
656         return value;
657     }
658 
659     public String getCanonical() {
660         if (canonical == null) {
661             canonical = items.toString();
662         }
663         return canonical;
664     }
665 
666     @Override
667     public boolean equals(Object o) {
668         return (o instanceof ComparableVersion) && items.equals(((ComparableVersion) o).items);
669     }
670 
671     @Override
672     public int hashCode() {
673         return items.hashCode();
674     }
675 
676     // CHECKSTYLE_OFF: LineLength
677     /**
678      * Main to test version parsing and comparison.
679      * <p>
680      * To check how "1.2.7" compares to "1.2-SNAPSHOT", for example, you can issue
681      * <pre>java -jar ${maven.repo.local}/org/apache/maven/maven-artifact/${maven.version}/maven-artifact-${maven.version}.jar "1.2.7" "1.2-SNAPSHOT"</pre>
682      * command to command line. Result of given command will be something like this:
683      * <pre>
684      * Display parameters as parsed by Maven (in canonical form) and comparison result:
685      * 1. 1.2.7 == 1.2.7
686      *    1.2.7 &gt; 1.2-SNAPSHOT
687      * 2. 1.2-SNAPSHOT == 1.2-snapshot
688      * </pre>
689      *
690      * @param args the version strings to parse and compare. You can pass arbitrary number of version strings and always
691      * two adjacent will be compared
692      */
693     // CHECKSTYLE_ON: LineLength
694     public static void main(String... args) {
695         System.out.println("Display parameters as parsed by Maven (in canonical form and as a list of tokens) and"
696                 + " comparison result:");
697         if (args.length == 0) {
698             return;
699         }
700 
701         ComparableVersion prev = null;
702         int i = 1;
703         for (String version : args) {
704             ComparableVersion c = new ComparableVersion(version);
705 
706             if (prev != null) {
707                 int compare = prev.compareTo(c);
708                 System.out.println("   " + prev.toString() + ' ' + ((compare == 0) ? "==" : ((compare < 0) ? "<" : ">"))
709                         + ' ' + version);
710             }
711 
712             System.out.println(
713                     (i++) + ". " + version + " -> " + c.getCanonical() + "; tokens: " + c.items.toListString());
714 
715             prev = c;
716         }
717     }
718 }