package com.atlassian.stash.internal.scm.git.merge;

import com.atlassian.bitbucket.i18n.I18nService;
import com.atlassian.bitbucket.i18n.KeyedMessage;
import com.atlassian.bitbucket.io.SingleLineOutputHandler;
import com.atlassian.bitbucket.pull.PullRequest;
import com.atlassian.bitbucket.pull.PullRequestMergeCanceledException;
import com.atlassian.bitbucket.scm.MergeCanceledException;
import com.atlassian.bitbucket.scm.git.GitAgent;
import com.atlassian.bitbucket.scm.git.GitScmConfig;
import com.atlassian.bitbucket.scm.git.command.GitCommand;
import com.atlassian.bitbucket.scm.git.command.GitCommandBuilderFactory;
import com.atlassian.bitbucket.scm.git.command.GitScmCommandBuilder;
import com.atlassian.bitbucket.scm.git.command.merge.GitMergeException;
import com.atlassian.bitbucket.scm.git.command.updateref.GitUpdateRefSetBuilder;
import com.atlassian.bitbucket.scm.git.event.GitMergeRequestedEvent;
import com.atlassian.bitbucket.scm.git.event.GitPullRequestMergeRequestedEvent;
import com.atlassian.bitbucket.util.*;
import com.atlassian.event.api.EventPublisher;
import com.atlassian.stash.internal.scm.git.command.FileInputHandler;
import com.atlassian.stash.internal.scm.git.command.FileOutputHandler;
import com.atlassian.stash.internal.scm.git.command.merge.UpdateRefCommandExitHandler;
import com.atlassian.stash.internal.scm.git.pull.PullRequestRefBuilder;
import com.atlassian.stash.internal.scm.git.pull.PullRequestRefType;
import org.apache.commons.lang3.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import javax.annotation.Nonnull;
import java.io.File;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.*;
import java.nio.file.attribute.BasicFileAttributes;
import java.util.EnumSet;
import java.util.List;
import java.util.regex.Pattern;

import static com.atlassian.stash.internal.scm.git.InternalGitConstants.PATH_GIT;
import static com.atlassian.stash.internal.scm.git.InternalGitConstants.PATH_OBJECTS;
import static com.google.common.io.Files.readFirstLine;

/**
 * A {@link FetchStrategy} which fetches merges by copying across objects and then updates the target ref using
 * {@code git update-ref}. This two-step process can be useful for fetching to targets outside of {@code refs/}.
 * Where {@code git fetch} cannot update such refs, {@code git update-ref} can. An example of where this ability
 * is useful is performing automatic merges (to show the diff) for pull requests.
 * <p>
 * For single-repository merges, this strategy uses Java I/O to copy the loose objects from the work tree directly
 * into the destination repository without forking any {@code git} processes. Since most pull requests are single
 * repository, this no-fork approach provides the best performance.
 * <p>
 * For cross-repository merges, this strategy drops below {@code git fetch} uses some plumbing commands directly
 * to produce a more efficient copy:
 * <ul>
 *     <li>{@code git rev-list --objects} is used to determine which objects need to be copied to the destination
 *     repository</li>
 *     <li>{@code git pack-objects} is fed the object list from {@code git rev-list --objects} and used to stream
 *     a pack containing the necessary objects</li>
 *     <li>{@code git unpack-objects} is fed the streamed pack and used to write the necessary objects as loose
 *     files in the destination repository</li>
 * </ul>
 * This closely mirrors what {@code git fetch} does, but it avoids some of the extra processing {@code git fetch}
 * does. Specifically, when {@code git fetch} runs {@code git rev-list --objects}, it uses {@code --not --all} to
 * exclude all of the objects that are currently in the repository. That couples {@code git fetch}'s performance
 * to the number of refs in the repository and makes it progressively heavier as more refs are added. The direct
 * {@code git rev-list --objects} run here uses a fixed set of refs to decouple its performance from the number
 * of refs the repository has.
 *
 * @since 3.9
 */
public class ObjectFetchStrategy implements FetchStrategy {

    private static final Logger log = LoggerFactory.getLogger(ObjectFetchStrategy.class);

    private final GitCommandBuilderFactory builderFactory;
    private final GitScmConfig config;
    private final EventPublisher eventPublisher;
    private final I18nService i18nService;
    private final PullRequest pullRequest;
    private final boolean tryMove;

    public ObjectFetchStrategy(GitCommandBuilderFactory builderFactory, GitScmConfig config,
                               EventPublisher eventPublisher, I18nService i18nService) {
        this(builderFactory, config, eventPublisher, i18nService, null);
    }

    public ObjectFetchStrategy(GitCommandBuilderFactory builderFactory, GitScmConfig config,
                               EventPublisher eventPublisher, I18nService i18nService,
                               PullRequest pullRequest) {
        this.builderFactory = builderFactory;
        this.config = config;
        this.eventPublisher = eventPublisher;
        this.i18nService = i18nService;
        this.pullRequest = pullRequest;

        //Try to eagerly detect whether atomic moves will be possible. This is an optimization for fetch-via-copy
        //so that it doesn't try atomic moves when they won't be supported
        tryMove = isSameFileStore(config);
    }

    @Override
    public void fetch(@Nonnull File workTree, @Nonnull MergeRequest request) {
        //Resolve the merge commit's hash, so that it can be provided on the cancelable event later. This is done first
        //because, if it fails, there's no point in forking any git processes
        String mergeHash = resolveMerge(workTree, request);

        //Step 1: Fetch the merge back into the real repository, retrieving the objects but not updating the target ref
        if (request.isCrossRepository()) {
            fetchViaPack(workTree, request);
        } else {
            fetchViaCopy(workTree, request);
        }

        //Step 2: If a cancelable merge was requested, raise an event to allow listeners to review it
        if (request.isCancelable()) {
            fireMergeRequested(request, mergeHash);
        }

        //Step 3: If the merge wasn't canceled, update the target ref. This may fail if the target ref was updated
        //        simultaneously by other processing, but that's no different than if we had fetched to it directly
        updateRef(request, mergeHash);
    }

    /**
     * Retrieves a flag indicating whether the {@link GitScmConfig#getRepositoriesDir repositories directory} and
     * the {@link GitScmConfig#getTempDir tmp directory} are on the same {@code FileStore}. If they're not, atomic
     * moves between them will not be possible.
     *
     * @param config the SCM configuration
     * @return {@code true} if the repositories and tmp directories are on the same {@code FileStore}, meaning
     *         atomic moves should be possible; otherwise, {@code false} if they're on separate stores
     */
    private static boolean isSameFileStore(GitScmConfig config) {
        Path repositoriesDir = config.getRepositoriesDir().toPath();
        Path tempDir = config.getTempDir().toPath();

        try {
            return Files.getFileStore(repositoriesDir).equals(Files.getFileStore(tempDir));
        } catch (IOException e) {
            log.warn("Could not check FileStores for {} and {}", repositoriesDir, tempDir, e);

            return false;
        }
    }

    private GitMergeRequestedEvent newGitMergeRequestedEvent(MergeRequest request, String mergeHash,
                                                             CancelState cancelState) {
        if (pullRequest == null) {
            return new GitMergeRequestedEvent(this, cancelState, request.getToRepository(), request.getFrom(),
                    request.getTo(), mergeHash);
        }

        return new GitPullRequestMergeRequestedEvent(this, cancelState, pullRequest, mergeHash);
    }

    private MergeCanceledException newMergeCanceledException(MergeRequest request, List<KeyedMessage> messages) {
        if (pullRequest == null) {
            return new MergeCanceledException(
                    i18nService.createKeyedMessage("bitbucket.scm.git.merge.canceled", request.getTo().getDisplayId()),
                    messages, request.getToRepository(), request.getFrom(), request.getTo());
        }

        return new PullRequestMergeCanceledException(
                i18nService.createKeyedMessage("bitbucket.scm.git.pull.mergecanceled", request.getTo().getDisplayId()),
                messages, pullRequest);
    }

    /**
     * Fetches the merge by directly copying loose objects from the work tree to the destination repository.
     * <p>
     * Because the work tree has an alternate back to the origin repository, and has no objects of its own when
     * {@code git clone --shared} completes, any objects in the work tree must belong to the merge. Copying those
     * loose objects to the destination repository is conceptually identical to the {@code git pack-objects} to
     * {@code git unpack-objects} chaining {@code git fetch} has, but avoids the overhead of spawning processes.
     * <p>
     * Note that this means, as objects are copied, the destination repository likely has incomplete objects, like
     * commits referring to trees that don't exist or trees referring to blobs that don't exist. It appears to be
     * natural for Git to handle this case, though, because a normal {@code git fetch} unpacks its new objects into
     * the repository without writing the pack first. That results in the same transient missing objects as copying.
     *
     * @param workTree the work tree containing the merge to fetch
     * @param request  describes the merge being fetched
     */
    private void fetchViaCopy(File workTree, MergeRequest request) {
        try (Timer ignored = TimerUtils.start("copy loose objects")) {
            Path repositoryDir = config.getRepositoryDir(request.getToRepository()).toPath();

            log.debug("{}: Fetching single-repository merge by copying new objects", request);
            Files.walkFileTree(FileUtils.construct(workTree, PATH_GIT, PATH_OBJECTS).toPath(),
                    EnumSet.noneOf(FileVisitOption.class), 2, new CopyLooseObjectsVisitor(repositoryDir, tryMove));
        } catch (IOException e) {
            throw new GitMergeException(i18nService.createKeyedMessage("bitbucket.scm.git.pull.copypackfailed"), e);
        }
    }

    /**
     * Fetches the merge by piping {@code git rev-list --objects} into {@code git pack-objects} into {@code git
     * unpack-objects}.
     * <p>
     * This process amounts to dropping to the plumbing commands that underpin the {@code git fetch} porcelain.
     * The goal of this approach is to avoid the ref advertisement and object negotiation work {@code git fetch}
     * does. That processing becomes progressively more expensive as the number of refs in the repository grows,
     * making fetching merges slower in larger repositories.
     * <p>
     * By building our own {@code git rev-list --objects} command, we're able to consume a fixed number of refs,
     * regardless of how many the destination repository has. This should achieve much more stable performance
     * than {@code git fetch} offers.
     *
     * @param workTree the work tree containing the merge to fetch
     * @param request  describes the merge being fetched
     */
    private void fetchViaPack(File workTree, MergeRequest request) {
        File mergeObjects = listObjects(workTree, request);
        if (mergeObjects == null) {
            log.debug("{}: Merge produced no new objects", request);
        } else {
            File mergePack = packObjects(workTree, mergeObjects, request);
            if (mergePack == null) {
                log.debug("{}: Merge produced an empty pack", request);
            } else {
                unpackObjects(mergePack, request);
            }
        }
    }

    private void fireMergeRequested(MergeRequest request, String mergeHash) {
        SimpleCancelState cancelState = new SimpleCancelState();

        eventPublisher.publish(newGitMergeRequestedEvent(request, mergeHash, cancelState));

        if (cancelState.isCanceled()) {
            //If any of the integrators cancel the merge, provide their cancel messages back to the caller to explain
            //why the merge could not be applied
            throw newMergeCanceledException(request, cancelState.getCancelMessages());
        }
    }

    /**
     * Uses {@code git rev-list --objects} to list the new objects created by the merge. If the merge only reused
     * existing objects, {@code null} is returned to indicate there are no new objects.
     *
     * @param workTree the work tree containing the merge to fetch
     * @param request  describes the merge being fetched
     * @return a file listing the new objects, or {@code null} if no new objects were produced
     */
    private File listObjects(File workTree, MergeRequest request) {
        File objects = FileUtils.construct(workTree, PATH_GIT, "bb-merge-objects.txt");

        GitScmCommandBuilder revListBuilder = builderFactory.builder().command("rev-list")
                .argument("--objects")
                .workingDirectory(workTree);
        if (pullRequest != null) {
            //If we're merging a pull request, whether for the auto-merge or for real, we can exclude any objects
            //reachable from the previous auto-merge, if one is present. This exclusion should make handling pull
            //request merges after the first auto-merge extremely efficient
            maybeExcludePreviousMerge(revListBuilder);
        }
        //Whether the merge is cross-repository or not we can always exclude the tip of the to ref, because
        //it and all of its objects are guaranteed to be in the target repository
        GitCommand<Boolean> revList = revListBuilder.argument("^" + request.getTo().getLatestCommit())
                .argument(GitAgent.HEAD)
                .build(new FileOutputHandler(objects));
        log.debug("{}: Streaming {} to {}", request, revList, objects.getAbsolutePath());

        return request.configureAndCall(revList) ? objects : null; //Return the file only if we wrote some bytes
    }

    /**
     * Reads in the {@link PullRequestRefBuilder#darkRef() dark ref} for the current {@link #pullRequest pull
     * request's} auto merge, if it exists, and excludes it on the provided {@code git rev-list} builder.
     *
     * @param revListBuilder the builder to exclude the merge on, if the merge is present
     */
    private void maybeExcludePreviousMerge(GitScmCommandBuilder revListBuilder) {
        try {
            String previousMerge = readFirstLine(
                    PullRequestRefBuilder.darkRef()
                            .id(pullRequest)
                            .type(PullRequestRefType.MERGE)
                            .toFile(config.getRepositoryDir(pullRequest.getToRef().getRepository())),
                    StandardCharsets.UTF_8);
            if (StringUtils.isNotBlank(previousMerge)) {
                revListBuilder.argument("^" + previousMerge);
            }
        } catch (IOException ignored) {
            //If we can't read in the previous merge, just don't exclude it. The resulting pack might be a
            //little larger with a few duplicate objects, but the next garbage collection should fix that
        }
    }

    /**
     * Streams the {@code mergeObjects} into {@code git pack-objects} to produce a pack. This new pack may
     * contain new objects created by the merge <i>as well as</i> other objects from the source repository
     * that the destination repository doesn't already have.
     *
     * @param workTree     the work tree containing the merge to fetch
     * @param mergeObjects a list of the objects to pack
     * @param request      describes the merge being fetched
     * @return a pack containing the specified objects, or {@code null} if the resulting pack was empty
     */
    private File packObjects(File workTree, File mergeObjects, MergeRequest request) {
        File mergePack = FileUtils.construct(workTree, PATH_GIT, "bb-merge.pack");

        GitCommand<Boolean> packObjects = builderFactory.builder().command("pack-objects")
                .argument("--delta-base-offset")
                .argument("-q")
                .argument("--stdout")
                .inputHandler(new FileInputHandler(mergeObjects))
                .workingDirectory(workTree)
                .build(new FileOutputHandler(mergePack));
        log.debug("{}: Streaming {} to {}", request, packObjects, mergePack.getAbsolutePath());

        return request.configureAndCall(packObjects) ? mergePack : null;
    }

    /**
     * Reads in the current commit hash for the target ref in the work tree. This is the SHA-1 of the new merge.
     *
     * @param workTree the work tree containing the merge to fetch
     * @param request  describes the merge being fetched
     * @return the SHA-1 of the new merge
     */
    private String resolveMerge(File workTree, MergeRequest request) {
        try {
            return readFirstLine(
                    FileUtils.construct(workTree, PATH_GIT, request.getTo().getId()),
                    StandardCharsets.UTF_8);
        } catch (IOException e) {
            throw new GitMergeException(i18nService.createKeyedMessage("bitbucket.scm.git.pull.mergeunresolved"), e);
        }
    }

    /**
     * Streams the {@code mergePack} into {@code git unpack-objects} to unpack the merge's objects into the
     * destination repository. {@code git unpack-objects} ignores any objects in the pack which are already
     * in the destination repository, so only <i>new</i> objects will actually be written.
     *
     * @param mergePack a pack containing the merge objects to unpack
     * @param request  describes the merge being fetched
     */
    private void unpackObjects(File mergePack, MergeRequest request) {
        GitCommand<String> unpackObjects = builderFactory.builder(request.getToRepository())
                .command("unpack-objects")
                .argument("-q")
                .inputHandler(new FileInputHandler(mergePack))
                .build(new SingleLineOutputHandler()); //Should produce no output
        log.debug("{}: Using {} to unpack objects from {}", request, unpackObjects, mergePack.getAbsolutePath());
        request.configureAndCall(unpackObjects);
    }

    private void updateRef(MergeRequest request, String mergeHash) {
        GitUpdateRefSetBuilder builder = builderFactory.builder(request.getToRepository()).updateRef()
                .set(request.getTargetRef(), mergeHash) //targetRef, not to.id
                .author(request.getAuthor()) //Just in case reflogs are enabled
                .exitHandler(new UpdateRefCommandExitHandler(i18nService, request.getToRepository()));
        if (!request.isForced()) {
            //If the fetch is not a forced update, supply an old value to ensure the update fails if the ref
            //does not point to the expected commit
            builder.oldValue(request.getTo().getLatestCommit());
        }
        request.configureAndCall(builder.build());
    }

    /**
     * A {@code FileVisitor} implementation which copies loose object files from the work tree to the
     * {@code objects} directory of the destination repository.
     */
    private static class CopyLooseObjectsVisitor extends SimpleFileVisitor<Path> {

        private static final Pattern PATTERN_OBJECT_DIR = Pattern.compile("[a-f0-9]{2}");
        private static final Pattern PATTERN_OBJECT_FILE = Pattern.compile("[a-f0-9]{38}");

        private final Path objectsDir;

        private boolean tryMove;

        CopyLooseObjectsVisitor(Path repositoryDir, boolean tryMove) {
            this.tryMove = tryMove;

            objectsDir = repositoryDir.resolve(PATH_OBJECTS);
        }

        /**
         * Limits the traversal to the work tree's {@code objects} directory and its immediate object directory
         * descendants. Object directories are identified by having names containing exactly two hex characters.
         *
         * @param dir   the directory to filter on
         * @param attrs ignored
         * @return {@code CONTINUE} for object directories, otherwise {@code SKIP_SUBTREE}
         */
        @Override
        public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) {
            String dirName = dir.getFileName().toString();

            return PATH_OBJECTS.equals(dirName) || PATTERN_OBJECT_DIR.matcher(dirName).matches() ?
                    FileVisitResult.CONTINUE :
                    FileVisitResult.SKIP_SUBTREE; //Most likely "info" or "pack" directories
        }

        /**
         * Copies the file to the destination repository's {@code objects} directory if it is an object file.
         * Object files are identified by having names containing exactly 38 hex characters.
         *
         * @param file  the file to potentially copy
         * @param attrs ignored
         * @return {@code CONTINUE}
         * @throws IOException if copying an object file fails
         */
        @Override
        public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException {
            Path fileName = file.getFileName();
            if (PATTERN_OBJECT_FILE.matcher(fileName.toString()).matches()) {
                Path objectDir = objectsDir.resolve(file.getParent().getFileName());
                Path objectFile = objectDir.resolve(fileName);

                //Checking for existence here is racy, but the move and copy strategies both include handling
                //for the case where the loose object appears after this check but before the move/copy. This
                //check is just intended to avoid the exception overhead in the simple case.
                //
                //It appears that newer versions of Git (2.3.7, for example), at least on Windows, can create
                //loose objects in the work tree that already exist as loose in the destination repository (a
                //behavior not seen in 1.9.5, for example). That results in a higher incidence of the objects
                //already existing than one might expect.
                if (!Files.exists(objectFile)) {
                    Files.createDirectories(objectDir);

                    if (!(tryMove && moveObject(file, objectFile))) {
                        copyObject(file, objectFile);
                    }
                }
            }

            return FileVisitResult.CONTINUE;
        }

        /**
         * If {@link #moveObject moving} the loose object fails, try to copy it. To ensure concurrent {@code git}
         * processes don't ever see partially-written loose objects, the object is written to a temporary file in
         * the destination repository and then atomically renamed into place. This mirrors how Git itself creates
         * new loose objects.
         *
         * @param srcObject the loose object in the temporary work tree
         * @param dstObject the loose object in the repository
         * @throws IOException if copy to a temporary file, or renaming that temporary file, fails
         */
        private void copyObject(Path srcObject, Path dstObject) throws IOException {
            //The implementation for Files.createTempFile will never return the same temporary file for concurrent
            //requests, so there's no need to worry about another concurrent fetch getting the same one (even when
            //the concurrent fetch is happening on another cluster node)
            Path tmpObject = Files.createTempFile(dstObject.getParent(), "atl-", null);
            try {
                Files.copy(srcObject, tmpObject, StandardCopyOption.COPY_ATTRIBUTES, StandardCopyOption.REPLACE_EXISTING);

                try {
                    Files.move(tmpObject, dstObject, StandardCopyOption.ATOMIC_MOVE);
                } catch (AccessDeniedException e) {
                    //This will either fall through, if the destination object exists, or rethrow the exception
                    //if the loose object couldn't be created
                    onAccessDenied(dstObject, e);
                } catch (FileAlreadyExistsException e) {
                    //If the loose object has appeared in the repository since we started copying, that's fine
                }
            } finally {
                Files.deleteIfExists(tmpObject);
            }
        }

        /**
         * As an optimization for standalone instances, which represent the majority of installs, try to atomically
         * move the object from the temporary clone to the target repository. This pairs the best performance with
         * concurrency safety (meaning other {@code git} processes will never see partially-written objects).
         *
         * @param srcObject the loose object in the temporary work tree
         * @param dstObject the loose object in the repository
         * @return {@code true} if the object was moved successfully; otherwise, {@code false} if it must be copied
         */
        private boolean moveObject(Path srcObject, Path dstObject) throws AccessDeniedException {
            try {
                Files.move(srcObject, dstObject, StandardCopyOption.ATOMIC_MOVE);
            } catch (AccessDeniedException e) {
                //This will either fall through and return true, if the destination object exists, or rethrow
                //the exception if the loose object couldn't be created
                onAccessDenied(dstObject, e);
            } catch (FileAlreadyExistsException e) {
                //If the object is already loose in the destination repository, indicate the move was
                //successful to preempt trying to copy it
            } catch (IOException e) {
                //If atomic moves are not supported between the temporary work tree and the target repository,
                //don't try any more moves. One move failing this way means they likely all will
                tryMove = !(e instanceof AtomicMoveNotSupportedException);

                //If an atomic move can't be performed, or the move fails for any other reason, rather than
                //immediately giving up, we should still try to copy the file.
                return false;
            }

            //If we make it here we either caught a FileAlreadyExistsException or the move succeeded
            return true;
        }

        /**
         * Handles {@code AccessDeniedException}s raised while attempting to write loose objects.
         * <p>
         * Git writes loose objects with {@code r--r--r--} (444) permissions. Especially on Windows this appears to
         * trigger an {@code AccessDeniedException} when the destination loose object already exists, rather than
         * the more desirable {@code FileAlreadyExistsException}. Unfortunately, that {@code AccessDeniedException}
         * can <i>also</i> be triggered if the system lacks the necessary permissions to <i>create</i> the new loose
         * object.
         * <p>
         * Based on that, if the destination object exists the exception is <i>ignored</i>; otherwise the exception
         * is assumed to indicate the object could not be created and is rethrown.
         *
         * @param dstObject the destination object
         * @param e         the {@code AccessDeniedException} to handle
         * @throws AccessDeniedException if the destination object does not exist, indicating the system lacks the
         *                               necessary filesystem permissions to create it
         */
        private void onAccessDenied(Path dstObject, AccessDeniedException e) throws AccessDeniedException {
            if (!Files.exists(dstObject)) {
                throw e;
            }
        }
    }
}
