Improve tokenization of version strings

Tokens like "b4", "beta1", "p195", &c. are now treated as atoms rather
than being broken down even further. Additionally, we enable support for
padding in the middle of versions strings, so we can successfully
compare something like "2.1-p195" with "2.1.0-p194" by inferring that
"2.1" is really "2.1.0".

This fixes the comparison "9.9.3-P1" > "9.9.3" which previously has not
been handled correctly.

1 files changed, 163 insertions, 59 deletions

diff --git a/Library/Homebrew/version.rb b/Library/Homebrew/version.rb
index 4a165d72b..e2b752496 100644
--- a/Library/Homebrew/version.rb
+++ b/Library/Homebrew/version.rb
@@ -1,92 +1,168 @@
-class VersionElement
+class Version
   include Comparable
 
-  def initialize elem
-    elem = elem.to_s.downcase
-    @elem = case elem
-      when /\d+/ then elem.to_i
-      when 'a', 'alpha' then 'alpha'
-      when 'b', 'beta' then 'beta'
-      else elem
-      end
+  class Token
+    include Comparable
+
+    attr_reader :value
+
+    def initialize(value)
+      @value = value
+    end
+
+    def inspect
+      "#<#{self.class} #{value.inspect}>"
+    end
   end
 
-  ZERO = VersionElement.new(0)
+  class NullToken < Token
+    def initialize(value=nil)
+      super
+    end
 
-  def <=>(other)
-    return unless other.is_a? VersionElement
-    return -1 if string? and other.numeric?
-    return 1 if numeric? and other.string?
-    return elem <=> other.elem
+    def <=>(other)
+      case other
+      when NumericToken
+        other.value == 0 ? 0 : -1
+      when AlphaToken, BetaToken, RCToken
+        1
+      else
+        -1
+      end
+    end
+
+    def inspect
+      "#<#{self.class}>"
+    end
   end
 
-  def to_s
-    @elem.to_s
+  NULL_TOKEN = NullToken.new
+
+  class StringToken < Token
+    PATTERN = /[a-z]+[0-9]+/i
+
+    def initialize(value)
+      @value = value.to_s
+    end
+
+    def <=>(other)
+      case other
+      when StringToken
+        value <=> other.value
+      when NumericToken, NullToken
+        -Integer(other <=> self)
+      end
+    end
   end
 
-  protected
+  class NumericToken < Token
+    PATTERN = /[0-9]+/i
 
-  attr_reader :elem
+    def initialize(value)
+      @value = value.to_i
+    end
 
-  def string?
-    elem.is_a? String
+    def <=>(other)
+      case other
+      when NumericToken
+        value <=> other.value
+      when StringToken
+        1
+      when NullToken
+        -Integer(other <=> self)
+      end
+    end
   end
 
-  def numeric?
-    elem.is_a? Numeric
+  class CompositeToken < StringToken
+    def rev
+      value[/([0-9]+)/, 1]
+    end
   end
-end
 
-class Version
-  include Comparable
+  class AlphaToken < CompositeToken
+    PATTERN = /a(?:lpha)?[0-9]+/i
 
-  def initialize val, detected=false
-    @version = val.to_s
-    @detected_from_url = detected
+    def <=>(other)
+      case other
+      when AlphaToken
+        rev <=> other.rev
+      else
+        super
+      end
+    end
   end
 
-  def detected_from_url?
-    @detected_from_url
+  class BetaToken < CompositeToken
+    PATTERN = /b(?:eta)?[0-9]+/i
+
+    def <=>(other)
+      case other
+      when BetaToken
+        rev <=> other.rev
+      when AlphaToken
+        1
+      when RCToken, PatchToken
+        -1
+      else
+        super
+      end
+    end
   end
 
-  def head?
-    @version == 'HEAD'
+  class RCToken < CompositeToken
+    PATTERN = /rc[0-9]+/i
+
+    def <=>(other)
+      case other
+      when RCToken
+        rev <=> other.rev
+      when AlphaToken, BetaToken
+        1
+      when PatchToken
+        -1
+      else
+        super
+      end
+    end
   end
 
-  def devel?
-    alpha? or beta? or rc?
+  class PatchToken < CompositeToken
+    PATTERN = /p[0-9]+/i
+
+    def <=>(other)
+      case other
+      when PatchToken
+        rev <=> other.rev
+      when AlphaToken, BetaToken, RCToken
+        1
+      else
+        super
+      end
+    end
   end
 
-  def alpha?
-    to_a.any? { |e| e.to_s == 'alpha' }
+  def initialize(val, detected=false)
+    @version = val.to_s
+    @detected_from_url = detected
   end
 
-  def beta?
-    to_a.any? { |e| e.to_s == 'beta' }
+  def detected_from_url?
+    @detected_from_url
   end
 
-  def rc?
-    to_a.any? { |e| e.to_s == 'rc' }
+  def head?
+    @version == 'HEAD'
   end
 
   def <=>(other)
-    # Return nil if objects aren't comparable
-    return unless other.is_a? Version
-    # Versions are equal if both are HEAD
-    return  0 if head? and other.head?
-    # HEAD is greater than any numerical version
-    return  1 if head? and not other.head?
-    return -1 if not head? and other.head?
-
-    stuple, otuple = to_a, other.to_a
-    slen, olen = stuple.length, otuple.length
+    return unless Version === other
+    return 0 if head? && other.head?
+    return 1 if head? && !other.head?
+    return -1 if !head? && other.head?
 
-    max = [slen, olen].max
-
-    stuple.fill(VersionElement::ZERO, slen, max - slen)
-    otuple.fill(VersionElement::ZERO, olen, max - olen)
-
-    stuple <=> otuple
+    max = [tokens.length, other.tokens.length].max
+    pad_to(max) <=> other.pad_to(max)
   end
 
   def to_s
@@ -96,8 +172,36 @@ class Version
 
   protected
 
-  def to_a
-    @array ||= @version.scan(/\d+|[a-zA-Z]+/).map! { |e| VersionElement.new(e) }
+  def pad_to(length)
+    nums, rest = tokens.partition { |t| NumericToken === t }
+    nums.concat([NULL_TOKEN]*(length - tokens.length)).concat(rest)
+  end
+
+  def tokens
+    @tokens ||= tokenize
+  end
+  alias_method :to_a, :tokens
+
+  def tokenize
+    @version.scan(
+      Regexp.union(
+        AlphaToken::PATTERN,
+        BetaToken::PATTERN,
+        RCToken::PATTERN,
+        PatchToken::PATTERN,
+        NumericToken::PATTERN,
+        StringToken::PATTERN
+      )
+    ).map! do |token|
+      case token
+      when /\A#{AlphaToken::PATTERN}\z/o   then AlphaToken
+      when /\A#{BetaToken::PATTERN}\z/o    then BetaToken
+      when /\A#{RCToken::PATTERN}\z/o      then RCToken
+      when /\A#{PatchToken::PATTERN}\z/o   then PatchToken
+      when /\A#{NumericToken::PATTERN}\z/o then NumericToken
+      when /\A#{StringToken::PATTERN}\z/o  then StringToken
+      end.new(token)
+    end
   end
 
   def self.parse spec