/*
    * 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>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: directory names are compared as if they ended with {@code '/'}, so that {@code foo/}
       * sorts after {@code foobar}.</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> {
  
          /**
           * 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.
           *
           * <p>>Git appends {@code '/'} to directory names before comparing.</p>
           */
          private final String sortKey;
  
          /**
           * The Git object type, which determines the Unix file-mode prefix.
           */
          private final FileMode type;
  
          /**
           * Constructs a new entry.
           *
           * @param name The name of the entry, not containing {@code '/'}.
           * @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) {
              if (Objects.requireNonNull(name).indexOf('/') >= 0) {
                  throw new IllegalArgumentException("Entry name must not contain '/': " + name);
             }
             this.name = name;
             this.type = Objects.requireNonNull(type);
             this.sortKey = type == FileMode.DIRECTORY ? name + "/" : name;
             this.rawObjectId = Objects.requireNonNull(rawObjectId);
         }
 
         @Override
         public int compareTo(final DirectoryEntry o) {
             return sortKey.compareTo(o.sortKey);
         }
 
         @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 static String requireNoParentTraversal(final String name) {
             if ("..".equals(name)) {
                 throw new IllegalArgumentException("Path component not allowed: " + name);
             }
             return name;
         }
 
         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);
         }
 
         /**
          * 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 If any path component is {@code ".."}.
          */
         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(requireNoParentTraversal(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) {
                 fileEntries.put(name, new DirectoryEntry(requireNoParentTraversal(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 If an I/O error occurs.
          * @throws IllegalArgumentException If any path component is {@code ".."}.
          */
         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 If the stream cannot be read.
          * @throws IllegalArgumentException If any path component is {@code ".."}.
          */
         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 If an I/O error occurs.
          * @throws IllegalArgumentException If any path component is {@code ".."}.
          */
         public void addSymbolicLink(final String name, final String target) throws IOException {
             addFile(FileMode.SYMBOLIC_LINK, name, target.getBytes(StandardCharsets.UTF_8));
         }
 
         /**
          * Computes the Git tree identifier for this directory and all its descendants.
          *
          * @return The raw tree identifier bytes.
          */
         @Override
         public byte[] get() {
             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>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 On error reading the stream.
      */
     public static byte[] blobId(final MessageDigest messageDigest, final long dataSize, final InputStream data) throws IOException {
         messageDigest.reset();
         DigestUtils.updateDigest(messageDigest, getGitBlobPrefix(dataSize));
         return DigestUtils.updateDigest(messageDigest, data).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 On error accessing the file.
      */
     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);
         }
         messageDigest.reset();
         DigestUtils.updateDigest(messageDigest, getGitBlobPrefix(Files.size(data)));
         return DigestUtils.updateDigest(messageDigest, data).digest();
     }
 
     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 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
     }
 }