MergeBaseGenerator.java

/*
 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> and others
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Distribution License v. 1.0 which is available at
 * https://www.eclipse.org/org/documents/edl-v10.php.
 *
 * SPDX-License-Identifier: BSD-3-Clause
 */

package org.eclipse.jgit.revwalk;

import java.io.IOException;
import java.text.MessageFormat;
import java.util.LinkedList;

import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.internal.JGitText;

/**
 * Computes the merge base(s) of the starting commits.
 * <p>
 * This generator is selected if the RevFilter is only
 * {@link org.eclipse.jgit.revwalk.filter.RevFilter#MERGE_BASE}.
 * <p>
 * To compute the merge base we assign a temporary flag to each of the starting
 * commits. The maximum number of starting commits is bounded by the number of
 * free flags available in the RevWalk when the generator is initialized. These
 * flags will be automatically released on the next reset of the RevWalk, but
 * not until then, as they are assigned to commits throughout the history.
 * <p>
 * Several internal flags are reused here for a different purpose, but this
 * should not have any impact as this generator should be run alone, and without
 * any other generators wrapped around it.
 */
class MergeBaseGenerator extends Generator {
    private static final int PARSED = RevWalk.PARSED;
    private static final int IN_PENDING = RevWalk.SEEN;
    private static final int POPPED = RevWalk.TEMP_MARK;
    private static final int MERGE_BASE = RevWalk.REWRITE;

    private final RevWalk walker;
    private final DateRevQueue pending;

    private int branchMask;
    private int recarryTest;
    private int recarryMask;
    private int mergeBaseAncestor = -1;
    private LinkedList<RevCommit> ret = new LinkedList<>();

    private CarryStack stack;

    MergeBaseGenerator(RevWalk w) {
        super(w.isFirstParent());
        walker = w;
        pending = new DateRevQueue(firstParent);
    }

    void init(AbstractRevQueue p) throws IOException {
        try {
            for (;;) {
                final RevCommit c = p.next();
                if (c == null)
                    break;
                add(c);
            }
            // Setup the condition used by carryOntoOne to detect a late
            // merge base and produce it on the next round.
            //
            recarryTest = branchMask | POPPED;
            recarryMask = branchMask | POPPED | MERGE_BASE;
            mergeBaseAncestor = walker.allocFlag();

            for (;;) {
                RevCommit c = _next();
                if (c == null) {
                    break;
                }
                ret.add(c);
            }
        } finally {
            // Always free the flags immediately. This ensures the flags
            // will be available for reuse when the walk resets.
            //
            walker.freeFlag(branchMask | mergeBaseAncestor);
        }
    }

    private void add(RevCommit c) {
        final int flag = walker.allocFlag();
        branchMask |= flag;
        if ((c.flags & branchMask) != 0) {
            // This should never happen. RevWalk ensures we get a
            // commit admitted to the initial queue only once. If
            // we see this marks aren't correctly erased.
            //
            throw new IllegalStateException(MessageFormat.format(JGitText.get().staleRevFlagsOn, c.name()));
        }
        c.flags |= flag;
        pending.add(c);
    }

    @Override
    int outputType() {
        return 0;
    }

    private RevCommit _next() throws MissingObjectException,
            IncorrectObjectTypeException, IOException {
        for (;;) {
            final RevCommit c = pending.next();
            if (c == null) {
                return null;
            }

            for (RevCommit p : c.getParents()) {
                if ((p.flags & IN_PENDING) != 0)
                    continue;
                if ((p.flags & PARSED) == 0)
                    p.parseHeaders(walker);
                p.flags |= IN_PENDING;
                pending.add(p);
            }

            int carry = c.flags & branchMask;
            boolean mb = carry == branchMask;
            if (mb) {
                // If we are a merge base make sure our ancestors are
                // also flagged as being popped, so that they do not
                // generate to the caller.
                //
                carry |= MERGE_BASE | mergeBaseAncestor;
            }
            carryOntoHistory(c, carry);

            if ((c.flags & MERGE_BASE) != 0) {
                // This commit is an ancestor of a merge base we already
                // popped back to the caller. If everyone in pending is
                // that way we are done traversing; if not we just need
                // to move to the next available commit and try again.
                //
                if (pending.everbodyHasFlag(MERGE_BASE))
                    return null;
                continue;
            }
            c.flags |= POPPED;

            if (mb) {
                c.flags |= MERGE_BASE;
                return c;
            }
        }
    }

    @Override
    RevCommit next() throws MissingObjectException,
            IncorrectObjectTypeException, IOException {
        while (!ret.isEmpty()) {
            RevCommit commit = ret.remove();
            if ((commit.flags & mergeBaseAncestor) == 0) {
                return commit;
            }
        }
        return null;
    }

    private void carryOntoHistory(RevCommit c, int carry) {
        stack = null;
        for (;;) {
            carryOntoHistoryInnerLoop(c, carry);
            if (stack == null) {
                break;
            }
            c = stack.c;
            carry = stack.carry;
            stack = stack.prev;
        }
    }

    private void carryOntoHistoryInnerLoop(RevCommit c, int carry) {
        for (;;) {
            RevCommit[] parents = c.getParents();
            if (parents == null || parents.length == 0) {
                break;
            }

            int e = parents.length - 1;
            for (int i = 0; i < e; i++) {
                RevCommit p = parents[i];
                if (carryOntoOne(p, carry) == CONTINUE) {
                    // Walking p will be required, buffer p on stack.
                    stack = new CarryStack(stack, p, carry);
                }
                // For other results from carryOntoOne:
                // HAVE_ALL: p has all bits, do nothing to skip that path.
                // CONTINUE_ON_STACK: callee pushed StackElement for p.
            }

            c = parents[e];
            if (carryOntoOne(c, carry) != CONTINUE) {
                break;
            }
        }
    }

    private static final int CONTINUE = 0;
    private static final int HAVE_ALL = 1;
    private static final int CONTINUE_ON_STACK = 2;

    private int carryOntoOne(RevCommit p, int carry) {
        // If we already had all carried flags, our parents do too.
        // Return HAVE_ALL to stop caller from running down this leg
        // of the revision graph any further.
        //
        // Otherwise return CONTINUE to ask the caller to walk history.
        int rc = (p.flags & carry) == carry ? HAVE_ALL : CONTINUE;
        p.flags |= carry;

        if ((p.flags & recarryMask) == recarryTest) {
            // We were popped without being a merge base, but we just got
            // voted to be one. Inject ourselves back at the front of the
            // pending queue and tell all of our ancestors they are within
            // the merge base now.
            p.flags &= ~POPPED;
            pending.add(p);
            stack = new CarryStack(stack, p, branchMask | MERGE_BASE);
            return CONTINUE_ON_STACK;
        }
        return rc;
    }

    private static class CarryStack {
        final CarryStack prev;
        final RevCommit c;
        final int carry;

        CarryStack(CarryStack prev, RevCommit c, int carry) {
            this.prev = prev;
            this.c = c;
            this.carry = carry;
        }
    }
}