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.

2 files changed, 184 insertions, 65 deletions

diff --git a/Library/Homebrew/test/test_versions.rb b/Library/Homebrew/test/test_versions.rb
index e414054ef..cd88bd37c 100644
--- a/Library/Homebrew/test/test_versions.rb
+++ b/Library/Homebrew/test/test_versions.rb
@@ -8,10 +8,20 @@ class VersionComparisonTests < Test::Unit::TestCase
     assert_operator version('0.1'), :==, version('0.1.0')
     assert_operator version('0.1'), :<, version('0.2')
     assert_operator version('1.2.3'), :>, version('1.2.2')
-    assert_operator version('1.2.3-p34'), :>, version('1.2.3-p33')
     assert_operator version('1.2.4'), :<, version('1.2.4.1')
+  end
+
+  def test_patchlevel
+    assert_operator version('1.2.3-p34'), :>, version('1.2.3-p33')
+    assert_operator version('1.2.3-p33'), :<, version('1.2.3-p34')
+  end
+
+  def test_HEAD
     assert_operator version('HEAD'), :>, version('1.2.3')
     assert_operator version('1.2.3'), :<, version('HEAD')
+  end
+
+  def test_alpha_beta_rc
     assert_operator version('3.2.0b4'), :<, version('3.2.0')
     assert_operator version('1.0beta6'), :<, version('1.0b7')
     assert_operator version('1.0b6'), :<, version('1.0beta7')
@@ -19,13 +29,18 @@ class VersionComparisonTests < Test::Unit::TestCase
     assert_operator version('1.1beta2'), :<, version('1.1rc1')
     assert_operator version('1.0.0beta7'), :<, version('1.0.0')
     assert_operator version('3.2.1'), :>, version('3.2beta4')
-    assert_nil version('1.0') <=> 'foo'
   end
 
-  def test_version_queries
-    assert Version.new("1.1alpha1").alpha?
-    assert Version.new("1.0beta2").beta?
-    assert Version.new("1.0rc-1").rc?
+  def test_comparing_unevenly_padded_versions
+    assert_operator version('2.1.0-p194'), :<, version('2.1-p195')
+    assert_operator version('2.1-p195'), :>, version('2.1.0-p194')
+    assert_operator version('2.1-p194'), :<, version('2.1.0-p195')
+    assert_operator version('2.1.0-p195'), :>, version('2.1-p194')
+    assert_operator version('2-p194'), :<, version('2.1-p195')
+  end
+
+  def test_comparison_returns_nil_for_non_version
+    assert_nil version('1.0') <=> 'foo'
   end
 
   def test_compare_patchlevel_to_non_patchlevel
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