package com.atlassian.bitbucket.pull;

import com.atlassian.bitbucket.scm.pull.PullRequestRescope;
import com.google.common.collect.Sets;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import javax.annotation.concurrent.NotThreadSafe;
import java.util.*;

import static com.atlassian.bitbucket.util.ShaUtils.hashesMatch;

/**
 * Helper class that calculates how a {@link PullRequestRescope rescope} changes its target pull request.
 * The analyzer expects to receive all commits that are reachable from the oldFrom, oldTo, newFrom and newTo commits,
 * but are not reachable from their common ancestor on the {@link #onCommit(String, Collection)} method. It expects to
 * receive these commits in topological order: no commit is received before any of its children.
 * <p>
 * The {@link #onCommit(String, Collection)} method may be called with any other commits; these are ignored.
 *
 * @since 4.5
 * @deprecated in 4.7 for removal in 5.0. Replaced by the more efficient {@link BulkPullRequestRescopeAnalyzer}
 */
@NotThreadSafe
public class PullRequestRescopeAnalyzer {

    private final int maxCommitIds;
    private final PullRequestRescope rescope;
    private final String searchTarget;

    // -- analysis temporary state
    private boolean fromBranchDeleted;
    private boolean fromCommonAncestorFound;
    private boolean toCommonAncestorFound;
    private Set<String> oldFromHeads;
    private Set<String> oldToHeads;
    private Set<String> newFromHeads;
    private Set<String> newToHeads;

    // -- analysis results
    private boolean anyInNewScope;
    private List<String> addedCommits;
    private List<String> removedCommits;
    private String mergeHash;
    private PullRequestRescopeOutcome outcome;
    private int addedCommitsCount;
    private int removedCommitsCount;

    public PullRequestRescopeAnalyzer(PullRequestRescope rescope, int maxCommitIds) {
        this.rescope = rescope;
        this.maxCommitIds = maxCommitIds;

        fromBranchDeleted = rescope.getNewFromHash() == null;
        searchTarget = fromBranchDeleted ? rescope.getOldFromHash() : rescope.getNewFromHash();
        if (fromBranchDeleted && hashesMatch(rescope.getOldToHash(), rescope.getNewToHash())) {
            // source branch has been deleted, but target branch is unchanged
            outcome = PullRequestRescopeOutcome.DECLINE;
        } else {
            outcome = PullRequestRescopeOutcome.UNKNOWN;

            fromCommonAncestorFound = hashesMatch(rescope.getOldFromHash(), rescope.getNewFromHash());
            toCommonAncestorFound = hashesMatch(rescope.getOldToHash(), rescope.getNewToHash());

            oldFromHeads = Sets.newHashSet(rescope.getOldFromHash());
            oldToHeads = Sets.newHashSet(rescope.getOldToHash());
            newFromHeads = fromBranchDeleted ? new HashSet<>() : Sets.newHashSet(rescope.getNewFromHash());
            newToHeads = Sets.newHashSet(rescope.getNewToHash());
        }
    }

    @Nonnull
    public List<String> getAddedCommits() {
        return addedCommits == null ? Collections.emptyList() : addedCommits;
    }

    public int getAddedCommitsCount() {
        return addedCommitsCount;
    }

    @Nullable
    public String getMergeHash() {
        return mergeHash;
    }

    @Nonnull
    public PullRequestRescopeOutcome getOutcome() {
        return outcome;
    }

    @Nonnull
    public List<String> getRemovedCommits() {
        return removedCommits == null ? Collections.emptyList() : removedCommits;
    }

    public boolean isDone() {
        return outcome != PullRequestRescopeOutcome.UNKNOWN;
    }

    public int getRemovedCommitsCount() {
        return removedCommitsCount;
    }

    public boolean onCommit(@Nonnull String commitId, @Nonnull Collection<String> parentIds) {
        if (isDone()) {
            return false;
        }

        boolean ancestorOfNewTo = processCommit(newToHeads, commitId, parentIds);
        if (ancestorOfNewTo && newToHeads.stream().anyMatch(head -> hashesMatch(head, searchTarget))) {
            // the search target is reachable from the to-branch, so the scope is empty

            // TODO: improve merge hash detection. For now this only detects the case where the newToHash is
            // A merge commit was detected that directly merges in searchTarget
            if (hashesMatch(commitId, rescope.getNewToHash()) && parentIds.size() > 1) {
                mergeHash = commitId;
            }
            handleEmptyScope();
            return false;
        }

        boolean ancestorOfOldTo = processCommit(oldToHeads, commitId, parentIds);
        boolean ancestorOfOldFrom = processCommit(oldFromHeads, commitId, parentIds);
        boolean ancestorOfNewFrom = !fromBranchDeleted && processCommit(newFromHeads, commitId, parentIds);
        boolean inOldScope = ancestorOfOldFrom && !ancestorOfOldTo;
        boolean inNewScope = ancestorOfNewFrom && !ancestorOfNewTo;
        anyInNewScope |= inNewScope;

        if (inOldScope && !inNewScope && removedCommitsCount++ < maxCommitIds) {
            if (removedCommits == null) {
                removedCommits = new ArrayList<>(maxCommitIds);
            }
            removedCommits.add(commitId);
        } else if (inNewScope && !inOldScope && addedCommitsCount++ < maxCommitIds) {
            if (addedCommits == null) {
                addedCommits = new ArrayList<>(maxCommitIds);
            }
            addedCommits.add(commitId);
        }

        if (ancestorOfOldFrom || ancestorOfNewFrom || ancestorOfOldTo || ancestorOfNewTo) {
            if (!fromBranchDeleted && !fromCommonAncestorFound) {
                fromCommonAncestorFound = matches(oldFromHeads, newFromHeads);
            }
            if (!toCommonAncestorFound) {
                toCommonAncestorFound = matches(oldToHeads, newToHeads);
            }

            if (toCommonAncestorFound) {
                if (fromBranchDeleted && matches(oldFromHeads, newToHeads)) {
                    // common ancestor found for [oldFromHash, oldToHash, newToHash]. The from-branch was deleted
                    // but not merged into the to-branch
                    setOutcome(PullRequestRescopeOutcome.DECLINE);
                }
                if (!fromBranchDeleted && fromCommonAncestorFound) {
                    // at this point, we know what commits have been added to and removed from the scope. Let's try
                    // to classify the outcome of the rescope: UPDATE / DECLINE / MERGE
                    if (anyInNewScope || removedCommitsCount == 0) {
                        // a commit was found in the new scope, or we have determined for sure that no commits were
                        // _removed_ from the scope ==> there's at least one commit in the new scope -> UPDATE
                        setOutcome(PullRequestRescopeOutcome.UPDATE);
                    } else {
                        // we're not sure yet whether the new scope is empty or not. We'll have to continue walking the
                        // commit graph until we find a commit that is in the new scope (and hence classify as 'UPDATE'),
                        // or until we find the common ancestor of oldFrom, oldTo, newFrom and newTo and classify as
                        // 'DECLINE' or 'MERGE'
                        if (isCommonAncestorFound()) {
                            // common ancestor for [oldFromHash, newFromHash, oldToHash, newToHash] has been found
                            // without finding any commits in scope.
                            handleEmptyScope();
                        }
                    }
                }
            }
        }

        return !isDone();
    }

    public PullRequestRescope getRescope() {
        return rescope;
    }

    private static boolean contains(Set<String> hashes, String value) {
        return hashes.stream().anyMatch(hash -> hashesMatch(hash, value));
    }

    private static boolean matches(Set<String> hashes1, Set<String> hashes2) {
        return hashes1.size() == hashes2.size() && // to shortcut the more expensive content checks
                hashes1.stream().allMatch(hash1 -> contains(hashes2, hash1));
    }

    private static boolean processCommit(Set<String> heads, String commitId, Collection<String> parentIds) {
        Iterator<String> it = heads.iterator();
        while (it.hasNext()) {
            String head = it.next();
            if (hashesMatch(head, commitId)) {
                it.remove();
                heads.addAll(parentIds);
                return true;
            }
        }
        return false;
    }

    private void handleEmptyScope() {
        if (hashesMatch(rescope.getOldToHash(), rescope.getNewToHash())) {
            // The scope is empty, but the to-branch hasn't changed. This can only mean that the from-branch has been
            // rewound to an ancestor of the to-branch, thereby stripping all commits from the PR.
            setOutcome(PullRequestRescopeOutcome.DECLINE);
        } else {
            // to-branch has changed. There are a couple of possibilities here:
            // - from-branch has not been updated:
            //   - the from-branch has been merged into the to-branch  ==> MERGE
            //   - the to-branch has been rebased onto the from-branch ==> MERGE
            // - the from-branch _has_ been updated:
            //   - from-branch updated, then merged into the to-branch ==> MERGE
            //   - from-branch updated, then to-branch was rebased onto the from-branch ==> MERGE
            //   - from-branch was rewound and the to-branch has been updated. This is where it becomes fuzzy:
            //     - from-branch was stripped to empty and an independent update happened to to-branch ==> DECLINE
            //     - from-branch was squash-merged and fast-forward merged into to-branch ==> MERGE
            // Because we cannot easily distinguish between the last two scenarios, we'll pick 'MERGE' in both cases.
            setOutcome(PullRequestRescopeOutcome.MERGE);
        }
    }

    private boolean isCommonAncestorFound() {
        return matches(newFromHeads, newToHeads);
    }

    private PullRequestRescopeOutcome setOutcome(PullRequestRescopeOutcome value) {
        this.outcome = value;

        if (outcome != PullRequestRescopeOutcome.UPDATE) {
            addedCommits = null;
            removedCommits = null;
            addedCommitsCount = 0;
            removedCommitsCount = 0;
        }

        // clear the heads collections to allow the memory to be gc-d
        oldFromHeads = null;
        oldToHeads = null;
        newFromHeads = null;
        newToHeads = null;
        return value;
    }
}
