/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      https://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package org.apache.commons.codec.digest;
  
  import java.io.ByteArrayOutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.nio.charset.StandardCharsets;
  import java.nio.file.DirectoryStream;
  import java.nio.file.Files;
  import java.nio.file.Path;
  import java.security.MessageDigest;
  import java.util.HashMap;
  import java.util.Map;
  import java.util.Objects;
  import java.util.Set;
  import java.util.TreeSet;
  import java.util.function.Supplier;
  
  /**
   * Computes <a href="https://git-scm.com/">Git</a> object identifiers and their generalizations described by the
   * <a href="https://www.swhid.org/swhid-specification/">SWHID specification</a>.
   *
   * <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>
   * @see <a href="https://www.swhid.org/swhid-specification/">SWHID Specification</a>
   * @since 1.22.0
   */
  public class GitIdentifiers {
  
      /**
       * Represents a single entry in a Git tree object.
       *
       * <p>
       * A Git tree object encodes a directory snapshot. Each entry holds:
       * </p>
       * <ul>
       *   <li>a {@link FileMode} that determines the Unix file mode (e.g. {@code 100644} for a regular file),</li>
       *   <li>the entry name (file or directory name, without a path separator),</li>
       *   <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: 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>
       */
      static class DirectoryEntry implements Comparable<DirectoryEntry> {
  
          private static String requireValidName(final String name) {
              Objects.requireNonNull(name, "name");
              if (name.isEmpty() || ".".equals(name) || "..".equals(name)) {
                  throw new IllegalArgumentException("Entry name must not be empty, '.' or '..'");
              }
              if (name.indexOf('/') >= 0 || name.indexOf('\0') >= 0) {
                  throw new IllegalArgumentException("Entry name must not contain '/' or NUL");
              }
              if (!StandardCharsets.UTF_8.newEncoder().canEncode(name)) {
                  throw new IllegalArgumentException("Entry name must not contain unpaired surrogates");
              }
              return name;
          }
  
          /**
           * The entry name (file or directory name, no path separator).
           */
         private final String name;
 
         /**
          * The raw object id of the referenced blob or sub-tree.
          */
         private final byte[] rawObjectId;
 
         /**
          * 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>
          */
         private final byte[] sortKey;
 
         /**
          * The Git object type, which determines the Unix file-mode prefix.
          */
         private final FileMode type;
 
         /**
          * Constructs a new entry.
          *
          * @param name The nonempty entry name, not {@code .} or {@code ..}, without {@code '/'}, NUL or unpaired surrogates.
          * @param type The type of the entry, not null.
          * @param rawObjectId The id of the entry, not null.
          */
         DirectoryEntry(final String name, final FileMode type, final byte[] rawObjectId) {
             this.name = requireValidName(name);
             this.type = Objects.requireNonNull(type, "type");
             this.sortKey = (type == FileMode.DIRECTORY ? name + "/" : name).getBytes(StandardCharsets.UTF_8);
             this.rawObjectId = Objects.requireNonNull(rawObjectId, "rawObjectId");
         }
 
         @Override
         public int compareTo(final DirectoryEntry o) {
             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
         public boolean equals(final Object obj) {
             if (obj == this) {
                 return true;
             }
             if (!(obj instanceof DirectoryEntry)) {
                 return false;
             }
             final DirectoryEntry other = (DirectoryEntry) obj;
             return name.equals(other.name);
         }
 
         @Override
         public int hashCode() {
             return name.hashCode();
         }
 
     }
 
     /**
      * The type of a Git tree entry, which maps to a Unix file-mode string.
      *
      * <p>
      * Git encodes the file type and permission bits as an ASCII octal string that precedes the entry name in the binary tree format. The values defined here
      * cover the four entry types that Git itself produces.
      * </p>
      *
      * @see <a href="https://git-scm.com/book/en/v2/Git-Internals-Git-Objects">Git Internals – Git Objects</a>
      */
     public enum FileMode {
 
         /**
          * A subdirectory. Subdirectories can only be specified by SHA or through a tree mark set with {@code --import-marks}.
          *
          * @see <a href="https://git-scm.com/docs/git-fast-import">git-fast-import - Backend for fast Git data importers</a>
          */
         DIRECTORY(new byte[] { '4', '0', '0', '0', '0' }),
 
         /**
          * A regular, but executable, file.
          */
         EXECUTABLE(new byte[] { '1', '0', '0', '7', '5', '5' }),
 
         /**
          * A gitlink, SHA-1 of the object refers to a commit in another repository. Git links can only be specified either by SHA or through a commit mark. They
          * are used to implement submodules.
          *
          * @see <a href="https://git-scm.com/docs/gitdatamodel">gitdatamodel - Git&#39;s core data model</a>
          * @see <a href="https://git-scm.com/docs/git-fast-import">git-fast-import - Backend for fast Git data importers</a>
          */
         GIT_LINK(new byte[] { '1', '6', '0', '0', '0', '0' }),
 
         /**
          * A regular (non-executable) file.
          * <p>
          * The majority of files in most projects use this mode. If in doubt, this is what you want.
          * </p>
          */
         REGULAR(new byte[] { '1', '0', '0', '6', '4', '4' }),
 
         /**
          * A symbolic link. The content of the file will be the link target.
          */
         SYMBOLIC_LINK(new byte[] { '1', '2', '0', '0', '0', '0' });
 
         private static FileMode get(final Path path) {
             // Symbolic links first
             if (Files.isSymbolicLink(path)) {
                 return SYMBOLIC_LINK;
             }
             if (Files.isDirectory(path)) {
                 return DIRECTORY;
             }
             if (Files.isExecutable(path)) {
                 return EXECUTABLE;
             }
             return REGULAR;
         }
 
         /**
          * Serialized {@code mode}: since this is mutable, it must remain private.
          */
         private final byte[] modeBytes;
 
         FileMode(final byte[] modeBytes) {
             // No need for a defensive copy since the array is private and never exposed,
             this.modeBytes = modeBytes;
         }
     }
 
     /**
      * Builds a Git tree identifier for a virtual directory structure, such as the contents of
      * an archive.
      */
     public static final class TreeIdBuilder implements Supplier<byte[]> {
 
         /**
          * Supplies a blob identifier that may throw {@link IOException}.
          */
         @FunctionalInterface
         private interface BlobIdSupplier {
             byte[] get() throws IOException;
         }
 
         private final Map<String, TreeIdBuilder> dirEntries = new HashMap<>();
         private final Map<String, DirectoryEntry> fileEntries = new HashMap<>();
         private final MessageDigest messageDigest;
 
         private TreeIdBuilder(final MessageDigest messageDigest) {
             this.messageDigest = Objects.requireNonNull(messageDigest, "messageDigest");
         }
 
         /**
          * Adds and returns the {@link TreeIdBuilder} for the named subdirectory, creating it if absent.
          *
          * @param name The relative path of the subdirectory in normalized form (may contain {@code '/'}).
          * @return The {@link TreeIdBuilder} for the subdirectory.
          * @throws IllegalArgumentException Thrown if any path component is {@code ".."}, contains NUL or contains unpaired surrogates.
          */
         public TreeIdBuilder addDirectory(final String name) {
             TreeIdBuilder current = this;
             for (final String component : name.split("/", -1)) {
                 // Noop segments
                 if (component.isEmpty() || ".".equals(component)) {
                     continue;
                 }
                 current = current.dirEntries.computeIfAbsent(DirectoryEntry.requireValidName(component), k -> new TreeIdBuilder(messageDigest));
             }
             return current;
         }
 
         private void addFile(final FileMode mode, final String name, final BlobIdSupplier blobId) throws IOException {
             final int slash = name.lastIndexOf('/');
             if (slash < 0) {
                 DirectoryEntry.requireValidName(name);
                 fileEntries.put(name, new DirectoryEntry(name, mode, blobId.get()));
             } else {
                 addDirectory(name.substring(0, slash)).addFile(mode, name.substring(slash + 1), blobId);
             }
         }
 
         /**
          * Adds a file entry at the given path within this tree.
          *
          * <p>
          * If {@code name} contains {@code '/'}, intermediate subdirectories are created automatically.
          * </p>
          *
          * @param mode The file mode (e.g. {@link FileMode#REGULAR}).
          * @param name The relative path of the entry in normalized form(may contain {@code '/'}).
          * @param data The file content.
          * @throws IOException Thrown if an I/O error occurs.
          * @throws IllegalArgumentException Thrown if the entry name is empty or {@code "."}, or any path component is {@code ".."}, contains NUL or contains unpaired
          *                                  surrogates.
          */
         public void addFile(final FileMode mode, final String name, final byte[] data) throws IOException {
             addFile(mode, name, () -> blobId(messageDigest, data));
         }
 
         /**
          * Adds a file entry at the given path within this tree, streaming content without buffering.
          *
          * <p>
          * If {@code name} contains {@code '/'}, intermediate subdirectories are created automatically.
          * </p>
          *
          * <p>
          * The stream is eagerly drained.
          * </p>
          *
          * @param mode     The file mode (e.g. {@link FileMode#REGULAR}).
          * @param name The relative path of the entry in normalized form(may contain {@code '/'}).
          * @param dataSize The exact number of bytes in {@code data}.
          * @param data     The file content.
          * @throws IOException Thrown if the stream cannot be read, or does not contain exactly {@code dataSize} bytes.
          * @throws IllegalArgumentException Thrown if the entry name is empty or {@code "."}, or any path component is {@code ".."}, contains NUL or contains unpaired
          *                                  surrogates.
          */
         public void addFile(final FileMode mode, final String name, final long dataSize, final InputStream data) throws IOException {
             addFile(mode, name, () -> blobId(messageDigest, dataSize, data));
         }
 
         /**
          * Adds a symbolic link entry at the given path within this tree.
          *
          * <p>
          * If {@code name} contains {@code '/'}, intermediate subdirectories are created automatically.
          * </p>
          *
          * @param name The relative path of the entry in normalized form(may contain {@code '/'}).
          * @param target The target of the symbolic link.
          * @throws IOException Thrown if an I/O error occurs.
          * @throws IllegalArgumentException Thrown if the entry name is empty or {@code "."}, or any path component is {@code ".."}, contains NUL or contains unpaired
          *                                  surrogates.
          */
         public void addSymbolicLink(final String name, final String target) throws IOException {
             addFile(FileMode.SYMBOLIC_LINK, name, target.getBytes(StandardCharsets.UTF_8));
         }
 
         /**
          * Gets the Git tree identifier for this directory and all its descendants.
          *
          * @return The raw tree identifier bytes.
          * @throws IllegalStateException Thrown if a file and a directory have the same name in this directory or any descendant.
          */
         @Override
         public byte[] get() {
             for (final String name : dirEntries.keySet()) {
                 if (fileEntries.containsKey(name)) {
                     throw new IllegalStateException("File and directory have the same name: " + name);
                 }
             }
             final Set<DirectoryEntry> entries = new TreeSet<>(fileEntries.values());
             dirEntries.forEach((k, v) -> entries.add(new DirectoryEntry(k, FileMode.DIRECTORY, v.get())));
             final ByteArrayOutputStream baos = new ByteArrayOutputStream();
             for (final DirectoryEntry entry : entries) {
                 baos.write(entry.type.modeBytes, 0, entry.type.modeBytes.length);
                 baos.write(' ');
                 final byte[] bytes = entry.name.getBytes(StandardCharsets.UTF_8);
                 baos.write(bytes, 0, bytes.length);
                 baos.write('\0');
                 baos.write(entry.rawObjectId, 0, entry.rawObjectId.length);
             }
             messageDigest.reset();
             DigestUtils.updateDigest(messageDigest, getGitTreePrefix(baos.size()));
             return DigestUtils.updateDigest(messageDigest, baos.toByteArray()).digest();
         }
 
         private TreeIdBuilder populate(final Path directory) throws IOException {
             try (DirectoryStream<Path> files = Files.newDirectoryStream(directory)) {
                 for (final Path path : files) {
                     final String name = Objects.toString(path.getFileName());
                     final FileMode mode = FileMode.get(path);
                     if (mode == FileMode.DIRECTORY) {
                         addDirectory(name).populate(path);
                     } else {
                         addFile(mode, name, () -> blobId(messageDigest, path));
                     }
                 }
             }
             return this;
         }
     }
 
     /**
      * Reads through a byte array and returns a generalized Git blob identifier.
      *
      * <p>
      * The identifier is computed in the way described by the
      * <a href="https://www.swhid.org/swhid-specification/v1.2/5.Core_identifiers/#52-contents">SWHID contents identifier</a>, but it can use any hash
      * algorithm.
      * </p>
      *
      * <p>
      * When the hash algorithm is SHA-1, the identifier is identical to Git blob identifier and SWHID contents identifier.
      * </p>
      *
      * @param messageDigest The MessageDigest to use (for example SHA-1).
      * @param data          Data to digest.
      * @return A generalized Git blob identifier.
      */
     public static byte[] blobId(final MessageDigest messageDigest, final byte[] data) {
         messageDigest.reset();
         DigestUtils.updateDigest(messageDigest, getGitBlobPrefix(data.length));
         return DigestUtils.digest(messageDigest, data);
     }
 
     /**
      * Reads through a stream of known size and returns a generalized Git blob identifier, without buffering.
      *
      * <p>
      * When the size of the content is known in advance, this overload streams {@code data} directly through
      * the digest without buffering the full content in memory.
      * </p>
      *
      * <p>
      * The stream is drained to its end. If the number of bytes read differs from {@code dataSize}, an {@link IOException} is thrown.
      * </p>
      *
      * <p>
      * When the hash algorithm is SHA-1, the identifier is identical to Git blob identifier and SWHID contents identifier.
      * </p>
      *
      * @param messageDigest The MessageDigest to use (for example SHA-1).
      * @param dataSize      The exact number of bytes in {@code data}.
      * @param data          Stream to digest.
      * @return A generalized Git blob identifier.
      * @throws IOException Thrown on error reading the stream, or if the stream does not contain exactly {@code dataSize} bytes.
      */
     public static byte[] blobId(final MessageDigest messageDigest, final long dataSize, final InputStream data) throws IOException {
         messageDigest.reset();
         DigestUtils.updateDigest(messageDigest, getGitBlobPrefix(dataSize));
         final byte[] buffer = new byte[8192];
         long actualSize = 0;
         int read;
         while ((read = data.read(buffer)) != -1) {
             messageDigest.update(buffer, 0, read);
             actualSize += read;
         }
         if (actualSize != dataSize) {
             throw new IOException("Stream contained " + actualSize + " bytes, but dataSize declared " + dataSize + " bytes");
         }
         return messageDigest.digest();
     }
 
     /**
      * Reads through a file and returns a generalized Git blob identifier.
      *
      * <p>
      * The identifier is computed in the way described by the
      * <a href="https://www.swhid.org/swhid-specification/v1.2/5.Core_identifiers/#52-contents">SWHID contents identifier</a>, but it can use any hash
      * algorithm.
      * </p>
      *
      * <p>
      * When the hash algorithm is SHA-1, the identifier is identical to Git blob identifier and SWHID contents identifier.
      * </p>
      *
      * @param messageDigest The MessageDigest to use (for example SHA-1).
      * @param data          Path to the file to digest.
      * @return A generalized Git blob identifier.
      * @throws IOException Thrown on error accessing the file, or if the number of bytes read differs from its measured size.
      */
     public static byte[] blobId(final MessageDigest messageDigest, final Path data) throws IOException {
         if (Files.isSymbolicLink(data)) {
             final byte[] linkTarget = Files.readSymbolicLink(data).toString().getBytes(StandardCharsets.UTF_8);
             return blobId(messageDigest, linkTarget);
         }
         final long dataSize = Files.size(data);
         try (InputStream input = Files.newInputStream(data)) {
             return blobId(messageDigest, dataSize, input);
         }
     }
 
     private static byte[] getGitBlobPrefix(final long dataSize) {
         return getGitPrefix("blob", dataSize);
     }
 
     private static byte[] getGitPrefix(final String type, final long dataSize) {
         return (type + " " + dataSize + "\0").getBytes(StandardCharsets.UTF_8);
     }
 
     private static byte[] getGitTreePrefix(final long dataSize) {
         return getGitPrefix("tree", dataSize);
     }
 
     /**
      * Reads through a directory and returns a generalized Git tree identifier.
      *
      * <p>
      * The identifier is computed in the way described by the
      * <a href="https://www.swhid.org/swhid-specification/v1.2/5.Core_identifiers/#53-directories">SWHID directory identifier</a>, but it can use any hash
      * algorithm.
      * </p>
      *
      * <p>
      * When the hash algorithm is SHA-1, the identifier is identical to Git tree identifier and SWHID directory identifier.
      * </p>
      *
      * @param messageDigest The MessageDigest to use (for example SHA-1).
      * @param data          Path to the directory to digest.
      * @return A generalized Git tree identifier.
      * @throws IOException Thrown on error accessing the directory or its contents.
      */
     public static byte[] treeId(final MessageDigest messageDigest, final Path data) throws IOException {
         return treeIdBuilder(messageDigest).populate(data).get();
     }
 
     /**
      * Returns a new {@link TreeIdBuilder} for constructing a generalized Git tree identifier from a virtual directory
      * structure, such as the contents of an archive.
      *
      * <p>
      * The identifier is computed in the way described by the
      * <a href="https://www.swhid.org/swhid-specification/v1.2/5.Core_identifiers/#53-directories">SWHID directory identifier</a>, but it can use any hash
      * algorithm.
      * </p>
      *
      * <p>
      * When the hash algorithm is SHA-1, the identifier is identical to Git tree identifier and SWHID directory identifier.
      * </p>
      *
      * @param messageDigest The MessageDigest to use (for example SHA-1).
      * @return A new {@link TreeIdBuilder}.
      */
     public static TreeIdBuilder treeIdBuilder(final MessageDigest messageDigest) {
         return new TreeIdBuilder(messageDigest);
     }
 
     private GitIdentifiers() {
         // utility class
     }
 }