Proposal: Git ordering for commit-based module versions

[MeteorsLiu]

Proposal: Git ordering for commit-based module versions

1. Problem

LLAR allows a module version to be either a release tag or a Git commit. The module resolver must still determine which of two versions of the same module is greater, both when selecting a formula by fromVer and when resolving dependency requirements.

Existing string comparators cannot provide that ordering:

• A commit ID is not a semantic version, so semantic-version comparison cannot distinguish two commit IDs reliably.
• GNU or lexical comparison orders the spelling of commit IDs, not their position in repository history.
• Treating commit IDs as equal prevents dependency resolution from distinguishing two different revisions.

Repository history provides the missing ordering information. A commit may be based on a release tag, may be a descendant of that tag, and has a commit timestamp. These facts must be combined with the Formula's existing tag-ordering policy.

2. Solution

Provide a Git-based version comparator that can be used by the Formula's existing compareVer function.

The Formula remains responsible for deciding how release tags are ordered. The Git comparator supplies the history-based ordering only for the parts that a tag comparator cannot determine: the relationship between a commit and its base tag, and the ordering of commits after the same base tag.

The comparison keeps commit IDs as the visible version values. It does not convert them to pseudo-versions or require changes to the module version representation or MVS contract.

The result is deterministic for both ordinary release tags and commit-based versions, including dependencies that select a commit revision.

3. Algorithm

For each input version, derive a comparable revision:

1. Resolve the input to its commit.
2. If the input is a tag, use that tag as its base tag.
3. If the input is a commit, collect the module's tags that point to the commit or one of its ancestors. Select the greatest reachable tag using the Formula's tag comparator. Do not use tag spelling, tag creation time, or graph distance to choose the base tag.
4. Record whether the selected base tag points directly to the resolved commit. A commit at its selected tag is equivalent to that tag; a later commit is after the base tag.
5. Record the commit's UTC committer timestamp and its full resolved commit ID.

Compare two derived revisions in this order:

1. A revision with no reachable base tag is lower than a revision with a base tag.
2. If both have base tags, compare the base tags with the Formula's tag comparator. A different base tag takes precedence over commit time.
3. If the base tags are equal, the base tag itself is lower than a commit after that tag.
4. If both inputs are commits after the same base tag, compare their UTC committer timestamps.
5. If timestamps are equal, compare the full commit IDs lexically to obtain a stable result.
6. Return equality only when the derived revisions are equivalent, including a commit that points directly at its selected tag.

The following examples use complete commit IDs as the version strings. Commit times are UTC.

1. Tag versus tag

   left  = madler/zlib@v1.3.1
   right = madler/zlib@v1.3.2
   
   baseTag(left)  = v1.3.1
   baseTag(right) = v1.3.2
   Formula tag order: v1.3.1 < v1.3.2
   
   result: left < right
   

2. A commit that is exactly a tag

   left  = madler/zlib@51b7f2abdade71cd9bb0e7a373ef2610ec6f9daf
   right = madler/zlib@v1.3.1
   
   51b7f2ab... is the commit pointed to by v1.3.1.
   Both normalize to baseTag v1.3.1 at the base commit.
   
   result: left = right
   

3. Two commits after the same base tag

   left  = madler/zlib@9f0f2d4f9f1f28be7e16d8bf3b4e9d4ada70aa9f
   right = madler/zlib@4de0b054a58bfee6974afabd831538dcedc23e22
   
   baseTag(left)  = v1.3.1, commit time = 2024-01-22T21:07:41Z
   baseTag(right) = v1.3.1, commit time = 2024-01-23T14:27:49Z
   
   The base tags are equal, so compare commit times.
   result: left < right
   

4. Different base tags are compared before commit time

   left  = madler/zlib@9f0f2d4f9f1f28be7e16d8bf3b4e9d4ada70aa9f
   right = madler/zlib@da607da739fa6047df13e66a2af6b8bec7c2a498
   
   baseTag(left)  = v1.3.1
   baseTag(right) = v1.3.2, and right is the v1.3.2 tag itself
   Formula tag order: v1.3.1 < v1.3.2
   
   The comparator returns left < right from the base tags and does not use commit time.
   

5. The highest reachable tag is the base tag

   version = madler/zlib@9f0f2d4f9f1f28be7e16d8bf3b4e9d4ada70aa9f
   reachable tags include: v1.2.9, v1.3, v1.3.1
   Formula tag order:      v1.2.9 < v1.3 < v1.3.1
   
   baseTag(version) = v1.3.1
   

   The closest tag, tag creation time, and lexical tag order do not affect base-tag selection.

6. No reachable tag

   repository = benhoyt/inih
   left  = benhoyt/inih@6aae10568f45ddea2ec2b29db76e4beab955f0f0
   right = benhoyt/inih@r30
   
   baseTag(left)  = empty
   baseTag(right) = r30
   
   A revision with no reachable tag sorts below one with a reachable tag.
   result: left < right
   

7. Equal commit timestamps

   left  = madler/zlib@bb0c497580e4ae2a20655af7d8557573bdaef776
   right = madler/zlib@e3dc0a85b7032e98380dec011bc8f2c2ee0d8fca
   
   baseTag(left)  = baseTag(right) = v1.3.2
   commit time(left) = commit time(right) = 2026-06-01T09:11:27Z
   full ID order: bb0c4975... < e3dc0a85...
   
   result: left < right
   

8. A commit used as a dependency version

   requirements:
   madler/zlib@v1.3.1
   madler/zlib@9f0f2d4f9f1f28be7e16d8bf3b4e9d4ada70aa9f
   
   The tag normalizes to baseTag v1.3.1 at the base commit.
   The commit normalizes to baseTag v1.3.1 after the base commit.
   The commit therefore compares greater and is the selected dependency version.