package com.atlassian.stash.internal.pull.rescope;

import com.atlassian.bitbucket.pull.PullRequestRef;
import com.atlassian.bitbucket.repository.RefChange;
import com.atlassian.bitbucket.repository.RefChangeType;
import com.atlassian.bitbucket.repository.Repository;
import com.atlassian.bitbucket.repository.StandardRefType;
import com.atlassian.bitbucket.user.ApplicationUser;
import com.atlassian.stash.internal.pull.InternalPullRequest;
import com.atlassian.stash.internal.pull.InternalRescopeRequest;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.ImmutableList;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.util.*;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;

import static com.atlassian.bitbucket.util.ShaUtils.hashesMatch;
import static com.google.common.base.MoreObjects.firstNonNull;
import static java.util.Objects.requireNonNull;
import static java.util.Optional.empty;
import static java.util.Optional.of;

/**
 * Represents a sequence of rescope operations that describe how the refs for a pull request were changed to a
 * target from-hash and a target to-hash. The chain is constructed by processing
 * {@link InternalRescopeRequest rescope requests} in order of their timestamps. For every rescope request,
 * a {@link SimplePullRequestRescope} is created.
 * <p>
 * Subsequent rescope requests do not have to align (e.g. the new from-ref from the last rescope request does not match
 * the old from-ref of the next rescope request). When this happens, a <em>gap</em> is detected and an extra rescope
 * operation is introduced to bridge the gap.
 * <p>
 * Gaps can have a number of causes:
 * <ul>
 *     <li>The event queue was full and the rescope triggering event was dropped -> no rescope request created</li>
 *     <li>A database error occurred when persisting the rescope request</li>
 *     <li>Rescope requests were manually deleted from the database - e.g. as instructed by support</li>
 *     <li>The branches have been updated on disk, but the rescope request hasn't been persisted yet because of
 *         delays in event processing (full event queue)</li>
 *     <li>In a cluster, the clocks are slightly out sync and rescope request timestamps lead to reordering of
 *         requests</li>
 * </ul>
 * The chain building does what it can to eliminate unnecessary gaps by allowing rescope requests to be reordered.
 * <p>
 * Any remaining gaps in the chain are filled by either attributing them to rescope requests for which no ref changes
 * were provided, or by constructing a placeholder {@code SimplePullRequestRescope} that is attributed to the most
 * likely user. If no user can be guessed from the rescope requests (because no requests apply to the chain), the
 * pull request author is selected.
 * <p>
 * The chain-building logic happens in the Builder to ensure that the resulting chain uses the minimum memory required.
 */
public class PullRequestRescopeChain {

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

    // Maximum time between rescope requests where requests can be reordered
    private static final long MAX_TIME_DRIFT_MS = TimeUnit.MINUTES.toMillis(3);
    // Used as a placeholder to for an absent hash value - only used during construction of the chain
    private static final String DELETED_REF = "deleted-ref";

    private final SimpleMinimalPullRequest pullRequest;
    private final List<SimplePullRequestRescope> rescopes;

    private PullRequestRescopeChain(Builder builder) {
        this.pullRequest = builder.pullRequest;
        this.rescopes = builder.buildRescopes();
    }

    @Nonnull
    public SimpleMinimalPullRequest getPullRequest() {
        return pullRequest;
    }

    @Nonnull
    public List<SimplePullRequestRescope> getRescopes() {
        return rescopes;
    }

    public static class Builder {

        private final List<InternalRescopeRequest> candidates;
        private final SimpleMinimalPullRequest pullRequest;
        private final Date startDate;
        private final LinkedList<Segment> segments;

        private String curFromRefHash;
        private String curToRefHash;
        private int gapCount;
        private Date targetDate;
        private String targetFromRefHash;
        private String targetToRefHash;

        public Builder(@Nonnull SimpleMinimalPullRequest pullRequest) {
            this.pullRequest = pullRequest;
            this.startDate = pullRequest.getRescopeDate();

            candidates = new ArrayList<>(2);
            segments = new LinkedList<>();

            curFromRefHash = pullRequest.getFromRef().getLatestCommit();
            curToRefHash = pullRequest.getToRef().getLatestCommit();
            targetDate = new Date();
        }

        @VisibleForTesting // constructor to facilitate testing
        Builder(InternalPullRequest pullRequest) {
            this(new SimpleMinimalPullRequest(pullRequest));
        }

        @Nonnull
        public PullRequestRescopeChain build() {
            return new PullRequestRescopeChain(this);
        }

        @Nonnull
        public SimpleMinimalPullRequest getPullRequest() {
            return pullRequest;
        }

        /**
         * Adds a {@link SimplePullRequestRescope rescope} for the request, <em>if</em> the request applies to the
         * pull request.
         *
         * @param request the rescope request
         * @return the builder
         */
        @Nonnull
        public Builder request(InternalRescopeRequest request) {
            if (!targetsPullRequest(request) || !isInDateScope(request, MAX_TIME_DRIFT_MS)) {
                return this;
            }
            if (!isInDateScope(request, 0)) {
                // Request _does_ target the pull request, but is out of scope based on the request's timestamp.
                // Don't add a segment to the chain for the request, but consider it a candidate for filling gaps
                // in the chain. This allows requests from cluster nodes that are out of sync to be processed
                // correctly.
                candidates.add(request);
                return this;
            }

            if (request.getChanges().isEmpty()) {
                // full repo request - we have no ref details. Hang on to it to use it to disambiguate / resolve any gaps
                // in the rescope segments when it's time to build the chain
                candidates.add(request);
                return this;
            }

            maybeCreateSegment(request).ifPresent(this::insertSegment);

            return this;
        }

        /**
         * Configures the final state of the pull request that the chain should produce.
         *
         * @param targetDate the date the provided hashes were determined. If a gap is discovered at the end of the chain,
         *                   an extra {@link SimplePullRequestRescope rescope} is introduced to bridge the gap. The date
         *                   on that rescope will be guaranteed to not be greater than the provided {code targetDate}.
         * @param targetFromHash the target commit ID (hash) for the {@link InternalPullRequest#getFromRef() from-ref}
         *                       of the pull request. If {@code null} is provided, the
         *                       {@link SimplePullRequestRescope#getNewFromHash() will be considered to have been
         *                       deleted.
         * @param targetToHash the target commit ID (hash) for the {@link InternalPullRequest#getToRef() to-ref}
         *                       of the pull request. If {@code null} is provided, the
         *                       {@link SimplePullRequestRescope#getNewToHash() will be considered to have been
         *                       deleted.
         * @return the builder
         */
        @Nonnull
        public Builder targetState(@Nonnull Date targetDate, @Nullable String targetFromHash, @Nullable String targetToHash) {
            this.targetDate = targetDate;
            this.targetFromRefHash = targetFromHash == null ? DELETED_REF : targetFromHash;
            this.targetToRefHash = targetToHash == null ? DELETED_REF : targetToHash;

            return this;
        }

        private static boolean canFillGap(Segment filler, Segment gap, boolean nextFromDefined, boolean nextToDefined) {
            if ((filler.fromRefChange != null && gap.fromRefChange == null && nextFromDefined) ||
                    (filler.toRefChange != null && gap.toRefChange == null && nextToDefined)) {
                // filler updates a ref that cannot be updated; there is no gap and a change is defined _after_ the gap
                return false;
            }
            // can only fill the gap if filler updates a branch for which a gap exists
            return (gap.fromRefChange != null && filler.fromRefChange != null) ||
                    (gap.toRefChange != null && filler.toRefChange != null);
        }

        private static String resolveSegmentHash(String segmentHash, @Nonnull String previousHash) {
            // transform a DELETED_REF into null.
            if (DELETED_REF.equals(segmentHash)) {
                return null;
            }
            // If segmentHash is null, this means that that ref was not updated in the segment and the hash from
            // the previous segment should be returned
            return firstNonNull(segmentHash, previousHash);
        }

        /**
         * Tries to fill an existing gap in {@code segments} with the provided {@code filler} segment that is the
         * result incorrectly of ordered rescope requests. This can happen because the timestamps are out of order
         * (different nodes in cluster having slightly different clocks), or because different requests end up having
         * the same timestamp (MySQL storing timestamps with 1s resolution)
         *
         * @param oldFrom the hash the from-branch is at at the start of the gap
         * @param oldTo the hash the to-branch is at at the start of the gap
         * @param newFrom the hash the from-branch should be at at the end of the gap. Is {@code null} if no rescopes
         *                after the gap modify the from-branch
         * @param newTo the hash the to-branch should be at at the end of the gap. Is {@code null} if no rescopes after
         *              the gap modify the to-branch
         * @param filler the (attributed) segment to be used to fill the gap
         * @return empty list if the gap cannot be filled with {@code filler}. A list of replacement segments if the gap
         *         can be filled with the {@code filler} segment.
         */
        private static List<Segment> tryFillGap(@Nonnull String oldFrom, @Nonnull String oldTo,
                                                @Nullable String newFrom, @Nullable String newTo,
                                                @Nonnull Segment filler) {
            GapMatch from = new GapMatch(oldFrom, newFrom, filler.fromRefChange);
            GapMatch to = new GapMatch(oldTo, newTo, filler.toRefChange);

            boolean startGapRemains = from.gapBeforeFiller || to.gapBeforeFiller;
            boolean endGapRemains = from.gapAfterFiller || to.gapAfterFiller;
            if (from.failed || to.failed || (startGapRemains && endGapRemains)) {
                // filling the gap with segment would leave two new gaps, which is worse..
                return Collections.emptyList();
            }
            List<Segment> result = new ArrayList<>(2);
            if (startGapRemains) {
                result.add(new Segment(from.remainingGap, to.remainingGap));
            }
            result.add(filler);
            if (endGapRemains) {
                result.add(new Segment(from.remainingGap, to.remainingGap));
            }

            return result;
        }

        /**
         * Iterates over the segments list, resolves any unresolved segments and then generates SimplePullRequestRescope
         * instances for each resolved segment.
         *
         * @return a list of {@code SimplePullRequestRescope} instances
         */
        @Nonnull
        private List<SimplePullRequestRescope> buildRescopes() {
            // check whether there's a gap between the current hashes and the target hashes
            maybeCreateGap(curFromRefHash, curToRefHash, targetFromRefHash, targetToRefHash).ifPresent(endGap -> {
                segments.add(endGap);
                ++gapCount;
                curFromRefHash = firstNonNull(endGap.getNewFromHash(), curFromRefHash);
                curToRefHash = firstNonNull(endGap.getNewToHash(), curToRefHash);
            });

            Iterator<InternalRescopeRequest> it = candidates.iterator();
            while (gapCount > 0 && it.hasNext()) {
                // try to fill gaps with candidates that are considered out of scope based on the timestamp (either
                // before the start-date or after the target-date). We'll allow filling gaps with these requests
                if (maybeCreateSegment(it.next()).map(this::maybeFillGap).orElse(false)) {
                    // used the candidate to fill a gap, no longer a candidate to explain other gaps
                    it.remove();
                }
            }

            Date lowerBound = startDate;
            String fromHash = pullRequest.getFromRef().getLatestCommit();
            String toHash = pullRequest.getToRef().getLatestCommit();

            ImmutableList.Builder<SimplePullRequestRescope> result = ImmutableList.builder();
            List<InternalRescopeRequest> resolveCandidates = new ArrayList<>(candidates);
            int index = 0;
            for (Segment segment : segments) {
                Segment resolved = segment.isAttributed()
                        ? segment
                        : resolve(segment, lowerBound, getFirstDateAfter(index), resolveCandidates);
                // if resolved does not change one side of the pull request, the change on that side will be null. For
                // example, if the fromRef does not change, the segment's fromChange will be null. However, when the
                // rescope is built, the oldFromHash and newFromHash cannot be null and must both be set to the current
                // fromHash. This is why the fromHash and toHash are passed in to the createPullRequestRescope method.
                SimplePullRequestRescope rescope = createPullRequestRescope(resolved, fromHash, toHash);

                fromHash = rescope.getNewFromHash();
                toHash = rescope.getNewToHash();
                lowerBound = rescope.getDate();
                result.add(rescope);
                if (toHash == null || fromHash == null) {
                    // the source or target branch has been deleted. This is sure to end the chain
                    return result.build();
                }
                ++index;
            }
            return result.build();
        }

        private String findPreviousHash(int startIndex, Function<Segment, MinimalRefChange> branchPicker, String defaultHash) {
            ListIterator<Segment> it = segments.listIterator(startIndex + 1);
            while (it.hasPrevious()) {
                Segment prev = it.previous();
                MinimalRefChange change = branchPicker.apply(prev);
                if (change != null) {
                    return change.newHash;
                }
            }
            return defaultHash;
        }

        private void insertSegment(Segment segment) {
            String newFrom = segment.getNewFromHash();
            String newTo = segment.getNewToHash();
            if (segments.isEmpty() &&
                    (newFrom == null || hashesMatch(newFrom, curFromRefHash)) &&
                    (newTo == null || hashesMatch(newTo, curToRefHash))) {
                // inserting the segment would introduce a gap and then completely revert the gap again. The pull
                // request is already in the target state. The rescope described by the rescope request has already
                // happened. This can happen when a gap has been detected in a previous rescope run.
                log.debug("{}, Skipping rescope {} because the pull request is already in the target state",
                        pullRequest, segment);
                return;
            }

            if (!maybeFillGap(segment)) {
                // if the new segment does not line up with its predecessor, create a GapSegment to bridge the gap
                maybeInsertGapPrecedingSegment(segment);

                segments.add(segment);
                curFromRefHash = firstNonNull(segment.getNewFromHash(), curFromRefHash);
                curToRefHash = firstNonNull(segment.getNewToHash(), curToRefHash);
            }
        }

        /**
         * Determines whether the provided rescope request applies to the chain that is being built. A rescope request
         * is only considered in scope if it is for the 'from' or 'to' repository of the pull request <em>and</em> the
         * {@link InternalRescopeRequest#getCreatedDate() date} of the request is within the date range that is being
         * considered for the chain.
         *
         * @param request the request
         * @return {@code true} if the request applies to the chain, otherwise {@code false}
         */
        private boolean isInDateScope(InternalRescopeRequest request, long marginMs) {
            long timestamp = request.getCreatedDate().getTime();

            return timestamp >= startDate.getTime() - marginMs && timestamp <= targetDate.getTime() + marginMs;
        }

        private Optional<Segment> maybeCreateGap(String oldFrom, String oldTo, String newFrom, String newTo) {
            MinimalRefChange fromRefGap = null;
            MinimalRefChange toRefGap = null;
            if (newFrom != null && !hashesMatch(oldFrom, newFrom)) {
                fromRefGap = new MinimalRefChange(oldFrom, newFrom);
            }
            if (newTo != null && !hashesMatch(oldTo, newTo)) {
                toRefGap = new MinimalRefChange(oldTo, newTo);
            }
            if (fromRefGap != null || toRefGap != null) {
                return of(new Segment(fromRefGap, toRefGap));
            }
            return empty();
        }

        private Optional<Segment> maybeCreateSegment(InternalRescopeRequest request) {
            MinimalRefChange fromChange = null;
            MinimalRefChange toChange = null;
            boolean matchFrom = request.getRepository().equals(pullRequest.getFromRef().getRepository());
            boolean matchTo = request.getRepository().equals(pullRequest.getToRef().getRepository());
            for (RefChange change : request.getChanges()) {
                if (change.getType() == RefChangeType.ADD || StandardRefType.TAG.equals(change.getRef().getType())) {
                    // adds and any change to a tag can never trigger rescopes
                    continue;
                }
                if (matchFrom && fromChange == null && change.getRef().getId().equals(pullRequest.getFromRef().getId())) {
                    fromChange = MinimalRefChange.valueOf(change);
                } else if (matchTo && toChange == null && change.getRef().getId().equals(pullRequest.getToRef().getId())) {
                    // only try to match the to-ref if we didn't match the from-ref (a RefChange can apply to
                    // either the to-ref or the from-ref, but never both)
                    toChange = MinimalRefChange.valueOf(change);
                }
            }

            if (fromChange == null && toChange == null) {
                return empty();
            }
            return of(new Segment(request.getCreatedDate(), request.getUser(), fromChange, toChange));
        }

        private boolean maybeFillGap(Segment filler) {
            if (gapCount == 0) {
                // there are no gaps - nothing to do
                return false;
            }

            // try to find a preceding gap that can be filled with segment
            ListIterator<Segment> it = segments.listIterator(segments.size());
            Date cutoffDate = new Date(filler.date.getTime() - MAX_TIME_DRIFT_MS);
            String nextFromHash = null; // from-hash at the end of the gap
            String nextToHash = null; // to-hash at the of the gap
            while (it.hasPrevious()) {
                Segment gap = it.previous();
                if (!gap.isAttributed() && canFillGap(filler, gap, nextFromHash != null, nextToHash != null)) {
                    // found a gap - check whether the segment fits in the gap
                    String oldFrom, newFrom, oldTo, newTo;
                    if (gap.fromRefChange != null) {
                        oldFrom = gap.getOldFromHash();
                        newFrom = gap.getNewFromHash();
                    } else {
                        oldFrom = findPreviousHash(it.previousIndex(), seg -> seg.fromRefChange, pullRequest.getFromRef().getLatestCommit());
                        newFrom = nextFromHash;
                    }
                    if (gap.toRefChange != null) {
                        oldTo = gap.getOldToHash();
                        newTo = gap.getNewToHash();
                    } else {
                        oldTo = findPreviousHash(it.previousIndex(), seg -> seg.toRefChange, pullRequest.getToRef().getLatestCommit());
                        newTo = nextToHash;
                    }
                    List<Segment> filling = tryFillGap(oldFrom, oldTo, newFrom, newTo, filler);
                    if (!filling.isEmpty()) {
                        it.remove();
                        // -2 because a gap was removed and one element in filled is not a gap
                        gapCount += filling.size() - 2;
                        filling.stream().forEach(it::add);
                        if (newTo == null && filler.toRefChange != null) {
                            curToRefHash = filler.getNewToHash();
                        }
                        if (newFrom == null && filler.fromRefChange != null) {
                            curFromRefHash = filler.getNewFromHash();
                        }
                        return true;
                    }
                } else if (gap.date != null && gap.date.before(cutoffDate)) {
                    break;
                }
                if (gap.getOldFromHash() != null) {
                    nextFromHash = gap.getOldFromHash();
                }
                if (gap.getOldToHash() != null) {
                    nextToHash = gap.getOldToHash();
                }
            }
            return false;
        }

        private void maybeInsertGapPrecedingSegment(Segment seg) {
            maybeCreateGap(curFromRefHash, curToRefHash, seg.getOldFromHash(), seg.getOldToHash()).ifPresent(gap -> {
                // we've got a gap, but we may be able to merge it with an existing gap in the segments. This can happen
                // when one rescope request uncovers a gap on the from-ref and another rescope request uncovers a gap
                // on the to-ref.
                // Walk backwards until we either:
                // - find a gap that we can merge with
                // - find an attributed Segment that modifies a ref for which we've detected a gap. In this case, we
                //   have to add a new gap to the segments list
                // - we run out of segments, in which case we have to add a new gap to the segments list
                ListIterator<Segment> it = segments.listIterator(segments.size());
                while (it.hasPrevious()) {
                    Segment s = it.previous();
                    Optional<Segment> merged = s.maybeMerge(gap);
                    if (merged.isPresent()) {
                        // found a gap that we can merge with - do it
                        it.set(merged.get());
                        return;
                    }
                    if ((gap.fromRefChange != null && s.fromRefChange != null) ||
                            (gap.toRefChange != null && s.toRefChange != null)) {
                        // found a segment that modifies a ref for which a gap needs to be added -
                        // cannot merge with an existing gap
                        break;
                    }
                }

                segments.add(gap);
                ++gapCount;
            });
        }

        private SimplePullRequestRescope createPullRequestRescope(Segment segment,
                                                                  @Nonnull String prevFromHash,
                                                                  @Nonnull String prevToHash) {
            // oldFromHash and oldToHash can never be null because the chain aborts when either the from-ref or
            // the to-ref is deleted
            String oldFromHash = requireNonNull(resolveSegmentHash(segment.getOldFromHash(), prevFromHash), "oldFromHash");
            String newFromHash = resolveSegmentHash(segment.getNewFromHash(), prevFromHash);
            String oldToHash = requireNonNull(resolveSegmentHash(segment.getOldToHash(), prevToHash), "oldToHash");
            String newToHash = resolveSegmentHash(segment.getNewToHash(), prevToHash);

            return new SimplePullRequestRescope(pullRequest, segment.date, segment.user, oldFromHash, oldToHash,
                    newFromHash, newToHash);
        }

        /**
         * Calculates the 'best' user to attribute an unresolved change to. The best user is calculated by looking at
         * all attributed segments and scoring the users on those segments. The scoring goes as follows:
         * <ul>
         *     <li>if both the attributed segment and the gap update the from-ref: +5</li>
         *     <li>if the attributed segment updates the from-ref, but the gap does not: +1</li>
         *     <li>if both the attributed segment and the gap update the to-ref: +3</li>
         *     <li>if the attributed segment updates the to-ref, but the gap does not: +1</li>
         * </ul>
         * Next, the users from all incomplete rescope requests are given 1 point. The user with the most points is
         * returned.
         * <p>
         * If there isn't any candidate user (can happen if there are no other segments and no candidate rescope
         * requests), the pull request author is picked as the most likely user.
         */
        private ApplicationUser getBestUser(Segment gap) {
            int fromWeight = gap.fromRefChange != null ? 5 : 1;
            int toWeight = gap.toRefChange != null ? 3 : 1;

            Map<ApplicationUser, Integer> userScores = new HashMap<>();
            segments.stream()
                    .filter(s -> s.user != null)
                    .forEach(segment -> {
                        int score = fromWeight * (segment.fromRefChange == null ? 0 : 1) +
                                toWeight * (segment.toRefChange == null ? 0 : 1);
                        userScores.compute(segment.user, (user, value) -> value == null ? score : value + score);
                    });
            candidates.stream()
                    .filter(req -> isInDateScope(req, 0)) // only consider rescope requests that are in scope
                    .forEach(req -> userScores.compute(req.getUser(), (user, value) -> value == null ? 1 : value + 1));

            return userScores.entrySet().stream()
                    .reduce((entry, best) -> (best == null || best.getValue() < entry.getValue()) ? entry : best)
                    .map(Map.Entry::getKey)
                    .orElse(pullRequest.getCreatedBy());
        }

        /**
         * Returns the first non-null date on a segment starting from index {@code segmentIndex}
         */
        private Date getFirstDateAfter(int segmentIndex) {
            if (segmentIndex < segments.size()) {
                ListIterator<Segment> it = segments.listIterator(segmentIndex + 1);
                while (it.hasNext()) {
                    Segment segment = it.next();
                    if (segment.date != null) {
                        return segment.date;
                    }
                }
            }
            return targetDate;
        }

        private Segment resolve(Segment segment, Date lowerBound, Date upperBound, List<InternalRescopeRequest> candidates) {
            Iterator<InternalRescopeRequest> it = candidates.iterator();
            while (it.hasNext()) {
                InternalRescopeRequest request = it.next();
                Date date = request.getCreatedDate();
                if (!date.before(lowerBound) && !date.after(upperBound) && request.getChanges().isEmpty()) {
                    it.remove(); // the candidate whole-repo request has been used - remove it from the list
                    return new Segment(date, request.getUser(), segment.fromRefChange, segment.toRefChange);
                }
            }

            // no rescope request found that can explain the gap - pick a date and choose the best user
            Date date = new Date(upperBound.getTime() / 2 + lowerBound.getTime() / 2);
            ApplicationUser bestUser = getBestUser(segment);
            log.info("{}: A gap was detected in the pull request history: {}. Attributing the scope change to user {} " +
                    "and setting the rescope date to {} based on known changes",
                    pullRequest, segment, bestUser != null ? bestUser.getName() : "unknown", date);
            return new Segment(date, bestUser, segment.fromRefChange, segment.toRefChange);
        }

        /**
         * Determines whether the provided rescope targets the pull request that this chain represents. Only requests
         * that update the from or to branch and whole-repository requests (without changes) are considered matches.
         *
         * @param request the request
         * @return {@code true} if the request targets the pull request, otherwise {@code false}
         */
        private boolean targetsPullRequest(InternalRescopeRequest request) {
            Repository repository = request.getRepository();
            PullRequestRef fromRef = pullRequest.getFromRef();
            PullRequestRef toRef = pullRequest.getToRef();
            Set<RefChange> changes = request.getChanges();
            boolean matchesFrom = repository.equals(fromRef.getRepository()) && (changes.isEmpty() ||
                    changes.stream().anyMatch(change -> change.getRef().getId().equals(fromRef.getId())));
            boolean matchesTo = repository.equals(toRef.getRepository()) && (
                    changes.isEmpty() ||
                            changes.stream().anyMatch(change -> change.getRef().getId().equals(toRef.getId())));
            return matchesFrom || matchesTo;
        }
    }

    /**
     * Describes how a ref changed. For compactness, only the old and new hashes are represented. NULL_SHA is used
     * to represent an absent ref (in the case of an add / delete operation).
     */
    private static class MinimalRefChange {
        private final String oldHash;
        private final String newHash;

        MinimalRefChange(@Nonnull String oldHash, @Nonnull String newHash) {
            this.oldHash = requireNonNull(oldHash, "oldHash");
            this.newHash = requireNonNull(newHash, "newHash");
        }

        public String toString() {
            return "{old-hash: " + oldHash + ", new-hash: " + newHash + "}";
        }

        private static MinimalRefChange merge(MinimalRefChange first, MinimalRefChange second) {
            if (first == null) {
                return second;
            }
            if (second == null) {
                return first;
            }
            return new MinimalRefChange(first.oldHash, second.newHash);
        }

        private static MinimalRefChange valueOf(RefChange change) {
            if (change == null) {
                return null;
            }
            switch (change.getType()) {
                case ADD:
                    throw new IllegalArgumentException("Adds should be ignored");
                case DELETE:
                    return new MinimalRefChange(change.getFromHash(), DELETED_REF);
                default:
                    return new MinimalRefChange(change.getFromHash(), change.getToHash());
            }
        }
    }

    /**
     * Describes a change to one or both pull request refs. If a ref is updated in the segment, the corresponding
     * {@code MinimalRefChange} is non-null. A {@code null} {@code MinimalRefChange} means that the ref was not changed
     * in the segment.
     */
    private static class Segment {
        private final Date date;
        private final MinimalRefChange fromRefChange;
        private final MinimalRefChange toRefChange;
        private final ApplicationUser user;

        private Segment(MinimalRefChange fromRefChange, MinimalRefChange toRefChange) {
            this(null, null, fromRefChange, toRefChange);
        }

        private Segment(Date date, ApplicationUser user, MinimalRefChange fromRefChange, MinimalRefChange toRefChange) {
            this.date = date;
            this.fromRefChange = fromRefChange;
            this.toRefChange = toRefChange;
            this.user = user;
        }

        private String getNewFromHash() {
            return fromRefChange == null ? null : fromRefChange.newHash;
        }

        private String getNewToHash() {
            return toRefChange == null ? null : toRefChange.newHash;
        }

        private String getOldFromHash() {
            return fromRefChange == null ? null : fromRefChange.oldHash;
        }

        private String getOldToHash() {
            return toRefChange == null ? null : toRefChange.oldHash;
        }

        private boolean isAttributed() {
            return user != null;
        }

        private Optional<Segment> maybeMerge(Segment other) {
            if (user == null && other.user == null) {
                return of(new Segment(MinimalRefChange.merge(fromRefChange, other.fromRefChange),
                        MinimalRefChange.merge(toRefChange, other.toRefChange)));
            }
            return empty();
        }
    }

    private static class GapMatch {

        private final boolean gapAfterFiller;
        private final boolean gapBeforeFiller;
        private final boolean failed;
        private final MinimalRefChange remainingGap;

        private GapMatch(String gapOldHash, String gapNewHash, MinimalRefChange filler) {
            boolean startAligns = false, endAligns = false;
            if (filler != null) {
                startAligns = hashesMatch(gapOldHash, filler.oldHash);
                endAligns = hashesMatch(gapNewHash, filler.newHash);
            }

            failed = filler != null && !startAligns && !endAligns;
            if (failed) {
                // not a good match - the gap won't be used, but we have to initialize it anyway
                remainingGap = null;
            } else if (startAligns && (endAligns || gapNewHash == null)) {
                // completely fills the gap, no gap remains
                remainingGap = null;
            } else if (startAligns) {
                // filler aligns at start, but not at end
                remainingGap = new MinimalRefChange(filler.newHash, gapNewHash);
            } else if (endAligns) {
                // filler aligns at end, but not at start
                remainingGap = new MinimalRefChange(gapOldHash, filler.oldHash);
            } else if (gapNewHash != null && !hashesMatch(gapOldHash, gapNewHash)) {
                // gap remains unchanged
                remainingGap = new MinimalRefChange(gapOldHash, gapNewHash);
            } else {
                // there was no gap to begin with
                remainingGap = null;
            }
            gapBeforeFiller = remainingGap != null && endAligns;
            gapAfterFiller = remainingGap != null && remainingGap.newHash.equals(gapNewHash);
        }
    }
}
