FlexVerBenchmarkHarness.csproj

FlexVerBenchmarkHarness.csproj

<Project Sdk="Microsoft.NET.Sdk">

    <PropertyGroup>
        <OutputType>Exe</OutputType>
        <TargetFramework>net7.0</TargetFramework>
        <ImplicitUsings>enable</ImplicitUsings>
        <Nullable>enable</Nullable>
    </PropertyGroup>

    <ItemGroup>
      <PackageReference Include="BenchmarkDotNet" Version="0.13.5" />
    </ItemGroup>

    <ItemGroup>
      <ProjectReference Include="..\FlexVer\FlexVer.csproj" />
    </ItemGroup>

</Project>

FlexVerComparer.cs

/*
 * To the extent possible under law, the author has dedicated all copyright
 * and related and neighboring rights to this software to the public domain
 * worldwide. This software is distributed without any warranty.
 *
 * See <http://creativecommons.org/publicdomain/zero/1.0/>
 */

using System.Globalization;
using System.Runtime.CompilerServices;

[assembly:InternalsVisibleTo("FlexVerTests")]

namespace FlexVer;

/**
 * Implements FlexVer, a SemVer-compatible intuitive comparator for free-form versioning strings as
 * seen in the wild. It's designed to sort versions like people do, rather than attempting to force
 * conformance to a rigid and limited standard. As such, it imposes no restrictions. Comparing two
 * versions with differing formats will likely produce nonsensical results (garbage in, garbage out),
 * but best effort is made to correct for basic structural changes, and versions of differing length
 * will be parsed in a logical fashion.
 */
public static class FlexVerComparer
{
	public static IComparer<string> Default { get; } = new FlexVerComparerImpl();

	private sealed class FlexVerComparerImpl : IComparer<string>
	{
		// ReSharper disable once MemberHidesStaticFromOuterClass
		public int Compare(string? x, string? y)
		{
			if (x is null) return y is null ? 0 : -1;
			if (y is null) return 1;
			return FlexVerComparer.Compare(x, y);
		}
	}

	/// <summary>
	/// Parse the given strings as freeform version strings, and compare them according to FlexVer.
	/// </summary>
	/// <param name="a">the first version string</param>
	/// <param name="b">the second version string</param>
	/// <returns><c>0</c> if the two versions are equal, a negative number if <c>a &lt; b</c>, or a positive number if <c>a &gt; b</c></returns>
	public static int Compare(string a, string b)
	{
		if (a is null) throw new ArgumentNullException(nameof(a));
		if (b is null) throw new ArgumentNullException(nameof(b));
		List<VersionComponent> ad = Decompose(a);
		List<VersionComponent> bd = Decompose(b);
		int highestCount = Math.Max(ad.Count, bd.Count);
		for (int i = 0; i < highestCount; i++) {
			int c = Get(ad, i).CompareTo(Get(bd, i));
			if (c != 0) return c;
		}
		return 0;
	}

	private static readonly VersionComponent Null = NullVersionComponent.Instance;

	internal class NullVersionComponent : VersionComponent
	{
		public static NullVersionComponent Instance { get; } = new();

		public override int CompareTo(VersionComponent other)
		=> ReferenceEquals(other, Null) ? 0 : -other.CompareTo(this);

		private NullVersionComponent() : base(Array.Empty<int>())
		{ }
	}

	internal class VersionComponent
	{
		public int[] Codepoints { get; }

		public VersionComponent(int[] codepoints)
		{
			Codepoints = codepoints;
		}

		public virtual int CompareTo(VersionComponent that)
		{
			if (ReferenceEquals(that, Null)) return 1;

			int[] a = this.Codepoints;
			int[] b = that.Codepoints;

			for (int i = 0; i < Math.Min(a.Length, b.Length); i++) {
				int c1 = a[i];
				int c2 = b[i];
				if (c1 != c2) return c1 - c2;
			}

			return a.Length - b.Length;
		}

		public override string ToString() => new string(Codepoints.Select(el => (char)el).ToArray());
	}

	internal sealed class SemVerPrereleaseVersionComponent : VersionComponent
	{
		public SemVerPrereleaseVersionComponent(int[] codepoints) : base (codepoints) { }

		public override int CompareTo(VersionComponent that)
		{
			if (ReferenceEquals(that, Null)) return -1; // opposite order
			return base.CompareTo(that);
		}
	}

	internal sealed class NumericVersionComponent : VersionComponent
	{
		public NumericVersionComponent(int[] codepoints) : base(codepoints) { }

		public override int CompareTo(VersionComponent that)
		{
			if (ReferenceEquals(that, Null)) return 1;
			if (that is NumericVersionComponent) {
				ReadOnlySpan<int> a = RemoveLeadingZeroes(this.Codepoints);
				ReadOnlySpan<int> b = RemoveLeadingZeroes(that.Codepoints);
				if (a.Length != b.Length) return a.Length-b.Length;
				for (int i = 0; i < a.Length; i++) {
					int ad = a[i];
					int bd = b[i];
					if (ad != bd) return ad-bd;
				}
				return 0;
			}
			return base.CompareTo(that);
		}

		private static ReadOnlySpan<int> RemoveLeadingZeroes(ReadOnlySpan<int> a)
		{
			if (a.Length == 1) return a;
			int i = 0;
			while (i < a.Length && a[i] == '0') {
				i++;
			}
			return a[i..];
		}

	}

	/*
	 * Break apart a string into intuitive version components, by splitting it where a run of
	 * characters changes from numeric to non-numeric.
	 */
	internal static List<VersionComponent> Decompose(string str)
	{
		if (string.Empty == str) return new List<VersionComponent>();
		bool lastWasNumber = char.IsAsciiDigit(str[0]);
		var stringInfo = new StringInfo(str);
		int totalCodepoints = stringInfo.LengthInTextElements;
		int[] accum = new int[totalCodepoints];
		List<VersionComponent> outComponents = new();
		int j = 0;

		for (int i = 0; i < str.Length; i++) {
			char cp = str[i];
			if (char.IsHighSurrogate(cp)) i++;
			if (cp == '+') break; // remove appendices
			bool isNumber = char.IsAsciiDigit(cp);
			if (isNumber != lastWasNumber || (cp == '-' && j > 0 && accum[0] != '-')) {
				outComponents.Add(CreateComponent(lastWasNumber, accum, j));
				j = 0;
				lastWasNumber = isNumber;
			}
			accum[j] = cp;
			j++;
		}
		outComponents.Add(CreateComponent(lastWasNumber, accum, j));
		return outComponents;
	}

	private static VersionComponent CreateComponent(bool number, int[] s, int j)
	{
		s = s[..j];

		if (number) {
			return new NumericVersionComponent(s);
		}

		if (s.Length > 1 && s[0] == '-') {
			return new SemVerPrereleaseVersionComponent(s);
		}

		return new VersionComponent(s);
	}

	private static VersionComponent Get(List<VersionComponent> li, int i)
	=> i >= li.Count ? Null : li[i];
}

FlexVerComparerV2.cs

/*
 * To the extent possible under law, the author has dedicated all copyright
 * and related and neighboring rights to this software to the public domain
 * worldwide. This software is distributed without any warranty.
 *
 * See <http://creativecommons.org/publicdomain/zero/1.0/>
 */

using System.Diagnostics;
using System.Runtime.CompilerServices;

[assembly:InternalsVisibleTo("FlexVerTests")]

namespace FlexVer;

/**
 * Implements FlexVer, a SemVer-compatible intuitive comparator for free-form versioning strings as
 * seen in the wild. It's designed to sort versions like people do, rather than attempting to force
 * conformance to a rigid and limited standard. As such, it imposes no restrictions. Comparing two
 * versions with differing formats will likely produce nonsensical results (garbage in, garbage out),
 * but best effort is made to correct for basic structural changes, and versions of differing length
 * will be parsed in a logical fashion.
 */
public static class FlexVerComparerV2
{
	public static IComparer<string> Default { get; } = new FlexVerComparerImpl();

	private sealed class FlexVerComparerImpl : IComparer<string>
	{
		// ReSharper disable once MemberHidesStaticFromOuterClass
		public int Compare(string? x, string? y)
		{
			if (x is null) return y is null ? 0 : -1;
			if (y is null) return 1;
			return FlexVerComparer.Compare(x, y);
		}
	}

	/// <summary>
	/// Parse the given strings as freeform version strings, and compare them according to FlexVer.
	/// </summary>
	/// <param name="a">the first version string</param>
	/// <param name="b">the second version string</param>
	/// <returns><c>0</c> if the two versions are equal, a negative number if <c>a &lt; b</c>, or a positive number if <c>a &gt; b</c></returns>
	public static int Compare(string a, string b)
	{
		if (a is null) throw new ArgumentNullException(nameof(a));
		if (b is null) throw new ArgumentNullException(nameof(b));

		var offsetA = 0;
		var offSetB = 0;
		Span<int> codepointsA = stackalloc int[32]; // 32 arbitrarily chosen
		Span<int> codepointsB = stackalloc int[32];
		while (true) {
			var ac = GetNextVersionComponent(a, ref offsetA, codepointsA);
			var bc = GetNextVersionComponent(b, ref offSetB, codepointsB);

			if (ac.ComponentType is VersionComponentType.Null && bc.ComponentType is VersionComponentType.Null) {
				return 0;
			}

			int c = VersionComponent.CompareTo(ac, bc);
			if (c != 0) return c;
			codepointsA.Clear();
			codepointsB.Clear();
		}
	}

	internal enum VersionComponentType
	{
		Default,
		SemVerPrerelease,
		Numeric,
		Null,
	}

	[DebuggerDisplay("{ComponentType} | '{Codepoints}'")]
	internal ref struct VersionComponent
	{
		public ReadOnlySpan<int> Codepoints { get; }
		public VersionComponentType ComponentType { get; }

		public VersionComponent(ReadOnlySpan<int> codepoints, VersionComponentType componentType)
		{
			Codepoints = codepoints;
			ComponentType = componentType;
		}

		public static int CompareTo(VersionComponent cur, VersionComponent other)
		{
#pragma warning disable CS8524
			return cur.ComponentType switch
#pragma warning restore CS8524
			{
				VersionComponentType.Default => CompareToBase(cur, other),
				VersionComponentType.Null when other.ComponentType == VersionComponentType.Null => 0,
				VersionComponentType.Null => -CompareToBase(other, cur),
				VersionComponentType.Numeric => CompareToNumeric(cur, other),
				VersionComponentType.SemVerPrerelease => CompareToSemVerPrerelease(cur, other)
			};
		}

		public static int CompareToBase(VersionComponent cur, VersionComponent other)
		{
			if (other.ComponentType == VersionComponentType.Null) return 1;

			ReadOnlySpan<int> a = cur.Codepoints;
			ReadOnlySpan<int> b = other.Codepoints;

			for (int i = 0; i < Math.Min(a.Length, b.Length); i++) {
				int c1 = a[i];
				int c2 = b[i];
				if (c1 != c2) return c1 - c2;
			}

			return a.Length - b.Length;
		}

		public static int CompareToNumeric(VersionComponent cur, VersionComponent that)
		{
			if (that.ComponentType == VersionComponentType.Null) return 1;
			if (that.ComponentType == VersionComponentType.Numeric) {
				ReadOnlySpan<int> a = RemoveLeadingZeroes(cur.Codepoints);
				ReadOnlySpan<int> b = RemoveLeadingZeroes(that.Codepoints);
				if (a.Length != b.Length) return a.Length-b.Length;
				for (int i = 0; i < a.Length; i++) {
					int ad = a[i];
					int bd = b[i];
					if (ad != bd) return ad-bd;
				}
				return 0;
			}
			return CompareToBase(cur, that);
		}

		public static int CompareToSemVerPrerelease(VersionComponent left, VersionComponent right)
		{
			if (right.ComponentType == VersionComponentType.Null) return -1; // opposite order
			return CompareToBase(left, right);
		}

		private static ReadOnlySpan<int> RemoveLeadingZeroes(ReadOnlySpan<int> a)
		{
			if (a.Length == 1) return a;
			int i = 0;
			while (i < a.Length && a[i] == '0') {
				i++;
			}
			return a[i..];
		}

		public override string ToString() => new string(Codepoints.ToArray().Select(el => (char)el).ToArray());
	}

	internal static VersionComponent GetNextVersionComponent(ReadOnlySpan<char> span, ref int i, Span<int> writableComponentCodepoints)
	{
		if (span.Length == i) {
			return new VersionComponent(ReadOnlySpan<int>.Empty, VersionComponentType.Null);
		}

		bool lastWasNumber = char.IsAsciiDigit(span[i]);

		ValueListBuilder<int> builder = new ValueListBuilder<int>(writableComponentCodepoints); // 16 arbitrarily chosen

		int j = 0;
		while (i < span.Length) {
			char cp = span[i];
			if (char.IsHighSurrogate(cp)) i++;
			if (cp == '+') break; // remove appendices
			bool isNumber = char.IsAsciiDigit(cp);
			if (isNumber != lastWasNumber || (cp == '-' && j > 0 && builder[0] != '-')) {
				i++;
				return CreateComponent(lastWasNumber, builder.AsSpan(), j);
			}
			j++;
			builder.Append(cp);
			i++;
		}
		return CreateComponent(lastWasNumber, builder.AsSpan(), j);
	}

	private static VersionComponent CreateComponent(bool number, ReadOnlySpan<int> s, int j)
	{
		s = s[..j];

		if (number) {
			return new VersionComponent(s, VersionComponentType.Numeric);
		}

		if (s.Length > 1 && s[0] == '-') {
			return new VersionComponent(s, VersionComponentType.SemVerPrerelease);
		}

		return new VersionComponent(s, VersionComponentType.Default);
	}

}

Program.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using FlexVer;

var instance = new Benchmarker();
instance.Setup();

// instance.CompareAll_AV2();

BenchmarkRunner.Run<Benchmarker>();

[MemoryDiagnoser]
public class Benchmarker
{
	private List<(string, string)> _versionsToCompare = null!;
	// private List<string> _versionsToSort = null!;

	[Benchmark]
	public void CompareAll_AV2_StackAlloc_ToArray()
	{
		foreach (var (a, b) in _versionsToCompare) {
			FlexVerComparerV2.Compare(a, b);
		}
	}

	[Benchmark]
	public void CompareAll_Existing()
	{
		foreach (var (a, b) in _versionsToCompare) {
			FlexVerComparer.Compare(a, b);
		}
	}

#region TestData
	[GlobalSetup]
	public void Setup()
	{
		_versionsToCompare = VersionsToTest.Split('\n')
			.Where(line => !line.StartsWith('#'))
			.Where(line => !string.IsNullOrWhiteSpace(line))
			.Select(line =>
			{
				var split = line.Split(' ');
				if (split.Length != 3) throw new ArgumentException($"Line formatted incorrectly, expected 2 spaces: '{line}'");
				return (split[0], split[2]);
			})
			.ToList();
	}

	private const string VersionsToTest = """
		# This test file is formatted as "<lefthand> <operator> <righthand>", seperated by the space character
		# Implementations should ignore lines starting with "#" and lines that have a length of 0

		# Basic numeric ordering (lexical string sort fails these)
		10 > 2
		100 > 10

		# Trivial common numerics
		1.0 < 1.1
		1.0 < 1.0.1
		1.1 > 1.0.1

		# SemVer compatibility
		1.5 > 1.5-pre1
		1.5 = 1.5+foobar

		# SemVer incompatibility
		1.5 < 1.5-2
		1.5-pre10 > 1.5-pre2

		# Check boundary between textual and prerelease
		a-a < a

		# Check boundary between textual and appendix
		a+a = a

		# Dash is included in prerelease comparison (if stripped it will be a smaller component)
		# Note that a-a < a=a regardless since the prerelease splits the component creating a smaller first component; 0 is added to force splitting regardless
		a0-a < a0=a

		# Pre-releases must contain only non-digit
		1.16.5-10 > 1.16.5

		# Pre-releases can have multiple dashes (should not be split)
		# Reasoning for test data: "p-a!" > "p-a-" (correct); "p-a!" < "p-a t-" (what happens if every dash creates a new component)
		-a- > -a!

		# Misc
		b1.7.3 > a1.2.6
		b1.2.6 > a1.7.3
		a1.1.2 < a1.1.2_01
		1.16.5-0.00.5 > 1.14.2-1.3.7
		1.0.0 < 1.0.0_01
		1.0.1 > 1.0.0_01
		1.0.0_01 < 1.0.1
		0.17.1-beta.1 < 0.17.1
		0.17.1-beta.1 < 0.17.1-beta.2
		1.4.5_01 = 1.4.5_01+fabric-1.17
		1.4.5_01 = 1.4.5_01+fabric-1.17+ohgod
		14w16a < 18w40b
		18w40a < 18w40b
		1.4.5_01+fabric-1.17 < 18w40b
		13w02a < c0.3.0_01
		0.6.0-1.18.x < 0.9.beta-1.18.x
		""";
#endregion TestData
}

ValueListBuilder.cs

using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace FlexVer;

internal ref struct ValueListBuilder<T>
{
	private Span<T> _span;
	private int _pos;

	public static ValueListBuilder<T> Empty()
		=> new ValueListBuilder<T>(Span<T>.Empty);

	public ValueListBuilder(Span<T> initialSpan)
	{
		_span = initialSpan;
		_pos = 0;
	}

	public int Length
	{
		get => _pos;
		set
		{
			Debug.Assert(value >= 0);
			Debug.Assert(value <= _span.Length);
			_pos = value;
		}
	}

	public int Capacity
	{
		get => _span.Length;
	}

	public ref T this[int index]
	{
		get
		{
			Debug.Assert(index < _pos);
			return ref _span[index];
		}
	}

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public void Append(T item)
	{
		int pos = _pos;
		if (pos >= _span.Length)
			Grow();

		_span[pos] = item;
		_pos = pos + 1;
	}

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public void AppendRange(T[] items)
	{
		int pos = _pos;
		while (pos + items.Length >= _span.Length) {
			Grow();
		}


		foreach (T item in items)
		{
			_span[pos] = item;
			_pos = pos + 1;
			pos++;
		}
	}

	public ReadOnlySpan<T> AsSpan()
	{
		return _span[.._pos];
	}

	public void Grow()
	{
		T[] array = new T[_span.Length * 2];

		bool success = _span.TryCopyTo(array);
		Debug.Assert(success);

		_span = array;
	}
}