This is an automated email from the ASF dual-hosted git repository.
ppkarwasz pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-codec.git
The following commit(s) were added to refs/heads/master by this push:
new f49b9638 GitIdentifiers: order tree entries by UTF-8 bytes as Git does
(#443)
f49b9638 is described below
commit f49b96388c2d97d093d8669cf74f57a5a92e7dff
Author: Jeff Lenamon <[email protected]>
AuthorDate: Mon Sep 14 13:55:50 2026 -0400
GitIdentifiers: order tree entries by UTF-8 bytes as Git does (#443)
* GitIdentifiers: order tree entries by UTF-8 bytes as Git does
DirectoryEntry.compareTo used String.compareTo, which orders UTF-16
code units; Git orders the raw UTF-8 bytes, and the two disagree for
names outside the Basic Multilingual Plane, so treeId returned an id
git write-tree does not. The sort key is now the name's UTF-8 bytes,
compared unsigned. A test pins the id git write-tree produces for a
two-entry tree and fails on the old comparator.
* Keep tree entries whose names share UTF-8 bytes
String.getBytes replaces a lone surrogate with '?', so a name holding one
had the same sort key as a name holding '?', and the TreeSet in
TreeIdBuilder.get kept only one of them. compareTo now falls back to the
String order when the bytes tie, which keeps both, as the String
comparator did. The class and test descriptions of the ordering are
reworded.
* Document the UTF-8 encoding of names and link targets
Git and SWHID treat file names and symbolic link targets as bytes with
no defined encoding, and this class encodes both as UTF-8, so its
identifiers match theirs only when the originals were UTF-8. The
paragraph is the one proposed in the review, with link targets added.
---
src/changes/changes.xml | 1 +
.../commons/codec/digest/GitIdentifiers.java | 28 +++++++++----
.../commons/codec/digest/GitIdentifiersTest.java | 46 ++++++++++++++++++++++
3 files changed, 68 insertions(+), 7 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index c881d90e..ae10848b 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -45,6 +45,7 @@ The <action> type attribute can be add,update,fix,remove.
<body>
<release version="1.23.0" date="YYYY-MM-DD" description="This is a feature
and maintenance release. Java 8 or later is required.">
<!-- FIX -->
+ <action type="fix" dev="ggregory" due-to="Jeff Lenamon">GitIdentifiers
orders tree entries by unsigned UTF-8 bytes, as Git does, instead of UTF-16
code units.</action>
<action type="fix" dev="ggregory" due-to="Yu Bao, Gary Gregory">Optimize
PhoneticEngine.encode(String, LanguageSet) for speed.</action>
<action type="fix" dev="ggregory" due-to="Yu Bao, Gary
Gregory">RFC1522Codec.decodeText(String) now throws a DecoderException instead
of a StringIndexOutOfBoundsException when a separator is missing.</action>
<action type="fix" dev="ggregory" due-to="Yu Bao, Gary Gregory">Optimize
Base58.convertFromBase58(byte[], Context) for speed and temporary object
allocation.</action>
diff --git a/src/main/java/org/apache/commons/codec/digest/GitIdentifiers.java
b/src/main/java/org/apache/commons/codec/digest/GitIdentifiers.java
index 0f7a3015..f9e42311 100644
--- a/src/main/java/org/apache/commons/codec/digest/GitIdentifiers.java
+++ b/src/main/java/org/apache/commons/codec/digest/GitIdentifiers.java
@@ -39,6 +39,10 @@ import java.util.function.Supplier;
* <p>When the hash algorithm is SHA-1, the identifiers produced by this class
are identical to those used by Git.
* Other hash algorithms produce generalized identifiers as described by the
SWHID specification.</p>
*
+ * <p>Git and SWHID treat file names and symbolic link targets as opaque byte
sequences with no defined encoding. The
+ * identifiers produced here coincide with Git's or SWHID's own identifiers
only if the original names and targets were
+ * UTF-8 encoded.</p>
+ *
* <p>This class is immutable and thread-safe. However, the {@link
MessageDigest} instances passed to it generally won't be.</p>
*
* @see <a href="https://git-scm.com/book/en/v2/Git-Internals-Git-Objects";>Git
Internals – Git Objects</a>
@@ -57,8 +61,9 @@ public class GitIdentifiers {
* <li>the raw object id of the referenced blob or sub-tree.</li>
* </ul>
*
- * <p>Entries are ordered by {@link #compareTo} using Git's tree-sort
rule: directory names are compared as if they ended with {@code '/'}, so that
{@code foo/}
- * sorts after {@code foobar}.</p>
+ * <p>Entries are ordered by {@link #compareTo} using Git's tree-sort
rule: names are compared as unsigned UTF-8 bytes, and directory names are
compared as if
+ * they ended with {@code '/'}, so that {@code foo/} sorts after {@code
foobar}. Comparing the UTF-8 bytes rather than the Java {@link String} matches
Git's
+ * order for names outside the Basic Multilingual Plane, whose UTF-16 code
units do not sort in code point order.</p>
*
* @see <a
href="https://git-scm.com/book/en/v2/Git-Internals-Git-Objects";>Git Internals –
Git Objects</a>
* @see <a
href="https://www.swhid.org/swhid-specification/v1.2/5.Core_identifiers/#53-directories";>SWHID
Directory Identifier</a>
@@ -76,11 +81,11 @@ public class GitIdentifiers {
private final byte[] rawObjectId;
/**
- * The key used for ordering entries within a tree object.
+ * The key used for ordering entries within a tree object, as the
UTF-8 bytes Git itself compares.
*
- * <p>>Git appends {@code '/'} to directory names before comparing.</p>
+ * <p>Git appends {@code '/'} to directory names before comparing.</p>
*/
- private final String sortKey;
+ private final byte[] sortKey;
/**
* The Git object type, which determines the Unix file-mode prefix.
@@ -100,13 +105,22 @@ public class GitIdentifiers {
}
this.name = name;
this.type = Objects.requireNonNull(type, "type");
- this.sortKey = type == FileMode.DIRECTORY ? name + "/" : name;
+ this.sortKey = (type == FileMode.DIRECTORY ? name + "/" :
name).getBytes(StandardCharsets.UTF_8);
this.rawObjectId = Objects.requireNonNull(rawObjectId,
"rawObjectId");
}
@Override
public int compareTo(final DirectoryEntry o) {
- return sortKey.compareTo(o.sortKey);
+ final byte[] a = sortKey;
+ final byte[] b = o.sortKey;
+ final int shared = Math.min(a.length, b.length);
+ for (int i = 0; i < shared; i++) {
+ final int diff = (a[i] & 0xff) - (b[i] & 0xff);
+ if (diff != 0) {
+ return diff;
+ }
+ }
+ return a.length != b.length ? a.length - b.length :
name.compareTo(o.name);
}
@Override
diff --git
a/src/test/java/org/apache/commons/codec/digest/GitIdentifiersTest.java
b/src/test/java/org/apache/commons/codec/digest/GitIdentifiersTest.java
index e455173d..bae2a761 100644
--- a/src/test/java/org/apache/commons/codec/digest/GitIdentifiersTest.java
+++ b/src/test/java/org/apache/commons/codec/digest/GitIdentifiersTest.java
@@ -24,6 +24,7 @@ import static
org.junit.jupiter.api.Assertions.assertNotEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;
import java.io.ByteArrayInputStream;
+import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
@@ -221,6 +222,51 @@ class GitIdentifiersTest {
assertFalse(regular.equals("foo"));
}
+ /**
+ * Tree entry names are ordered by their UTF-8 bytes, which is not the
order {@link String#compareTo(String)} gives when a supplementary character
meets a
+ * Basic Multilingual Plane character from U+E000 up: U+FF21 encodes to
{@code EF BC A1} and U+1F600 to {@code F0 9F 98 80}, so Git sorts U+FF21 first,
while
+ * the UTF-16 code units place the surrogate pair of U+1F600 first.
+ *
+ * <p>The expected identifier is the one {@code git write-tree} produces
for a tree holding the same two entries.</p>
+ */
+ @Test
+ void testTreeIdSortsSupplementaryPlaneNamesLikeGit(@TempDir final Path
tempDir) throws Exception {
+ final String fullWidthA = "\uFF21";
+ final String grinningFace = "\uD83D\uDE00";
+ final byte[] content = "x".getBytes(StandardCharsets.UTF_8);
+ final String expected = "9f9c1fc3580195f51d3e71b384ef1d57740e2151";
+ final MessageDigest md = DigestUtils.getSha1Digest();
+
+ // Entries are added in the wrong order on purpose, so only the sort
decides the result.
+ final GitIdentifiers.TreeIdBuilder builder =
GitIdentifiers.treeIdBuilder(md);
+ builder.addFile(GitIdentifiers.FileMode.REGULAR, grinningFace,
content);
+ builder.addFile(GitIdentifiers.FileMode.REGULAR, fullWidthA, content);
+ assertEquals(expected, Hex.encodeHexString(builder.get()));
+
+ try {
+ Files.write(tempDir.resolve(fullWidthA), content);
+ Files.write(tempDir.resolve(grinningFace), content);
+ } catch (final IOException e) {
+ Assumptions.abort("Filesystem cannot hold the test entry names: "
+ e);
+ }
+ assertEquals(expected, Hex.encodeHexString(GitIdentifiers.treeId(md,
tempDir)));
+ }
+
+ /**
+ * A lone surrogate encodes to {@code ?} in UTF-8, the same byte as a
question mark, so the two names share a sort key; both entries must stay in the
tree.
+ */
+ @Test
+ void testTreeIdKeepsNamesWithTheSameUtf8Bytes() throws Exception {
+ final byte[] content = "x".getBytes(StandardCharsets.UTF_8);
+ final MessageDigest md = DigestUtils.getSha1Digest();
+ final GitIdentifiers.TreeIdBuilder one =
GitIdentifiers.treeIdBuilder(md);
+ one.addFile(GitIdentifiers.FileMode.REGULAR, "?", content);
+ final GitIdentifiers.TreeIdBuilder both =
GitIdentifiers.treeIdBuilder(md);
+ both.addFile(GitIdentifiers.FileMode.REGULAR, "?", content);
+ both.addFile(GitIdentifiers.FileMode.REGULAR, "\uD800", content);
+ assertNotEquals(Hex.encodeHexString(one.get()),
Hex.encodeHexString(both.get()));
+ }
+
/**
* Entries should be sorted by Git sort rule.
*
