HistogramDiffIndex.java

/*
 * Copyright (C) 2010, Google Inc. 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.diff;

import org.eclipse.jgit.internal.JGitText;

/**
 * Support {@link HistogramDiff} by computing occurrence counts of elements.
 * <p>
 * Each element in the range being considered is put into a hash table, tracking
 * the number of times that distinct element appears in the sequence. Once all
 * elements have been inserted from sequence A, each element of sequence B is
 * probed in the hash table and the longest common subsequence with the lowest
 * occurrence count in A is used as the result.
 *
 * @param <S>
 *            type of the base sequence.
 */
final class HistogramDiffIndex<S extends Sequence> {
    private static final int REC_NEXT_SHIFT = 28 + 8;

    private static final int REC_PTR_SHIFT = 8;

    private static final int REC_PTR_MASK = (1 << 28) - 1;

    private static final int REC_CNT_MASK = (1 << 8) - 1;

    private static final int MAX_PTR = REC_PTR_MASK;

    private static final int MAX_CNT = (1 << 8) - 1;

    private final int maxChainLength;

    private final HashedSequenceComparator<S> cmp;

    private final HashedSequence<S> a;

    private final HashedSequence<S> b;

    private final Edit region;

    /** Keyed by {@link #hash(HashedSequence, int)} for {@link #recs} index. */
    private final int[] table;

    /** Number of low bits to discard from a key to index {@link #table}. */
    private final int keyShift;

    /**
     * Describes a unique element in sequence A.
     *
     * The records in this table are actually 3-tuples of:
     * <ul>
     * <li>index of next record in this table that has same hash code</li>
     * <li>index of first element in this occurrence chain</li>
     * <li>occurrence count for this element (length of locs list)</li>
     * </ul>
     *
     * The occurrence count is capped at {@link #MAX_CNT}, as the field is only
     * a few bits wide. Elements that occur more frequently will have their
     * count capped.
     */
    private long[] recs;

    /** Number of elements in {@link #recs}; also is the unique element count. */
    private int recCnt;

    /**
     * For {@code ptr}, {@code next[ptr - ptrShift]} has subsequent index.
     *
     * For the sequence element {@code ptr}, the value stored at location
     * {@code next[ptr - ptrShift]} is the next occurrence of the exact same
     * element in the sequence.
     *
     * Chains always run from the lowest index to the largest index. Therefore
     * the array will store {@code next[1] = 2}, but never {@code next[2] = 1}.
     * This allows a chain to terminate with {@code 0}, as {@code 0} would never
     * be a valid next element.
     *
     * The array is sized to be {@code region.getLengthA()} and element indexes
     * are converted to array indexes by subtracting {@link #ptrShift}, which is
     * just a cached version of {@code region.beginA}.
     */
    private int[] next;

    /**
     * For element {@code ptr} in A, index of the record in {@link #recs} array.
     *
     * The record at {@code recs[recIdx[ptr - ptrShift]]} is the record
     * describing all occurrences of the element appearing in sequence A at
     * position {@code ptr}. The record is needed to get the occurrence count of
     * the element, or to locate all other occurrences of that element within
     * sequence A. This index provides constant-time access to the record, and
     * avoids needing to scan the hash chain.
     */
    private int[] recIdx;

    /** Value to subtract from element indexes to key {@link #next} array. */
    private int ptrShift;

    private Edit lcs;

    private int cnt;

    private boolean hasCommon;

    HistogramDiffIndex(int maxChainLength, HashedSequenceComparator<S> cmp,
            HashedSequence<S> a, HashedSequence<S> b, Edit r) {
        this.maxChainLength = maxChainLength;
        this.cmp = cmp;
        this.a = a;
        this.b = b;
        this.region = r;

        if (region.endA >= MAX_PTR)
            throw new IllegalArgumentException(
                    JGitText.get().sequenceTooLargeForDiffAlgorithm);

        final int sz = r.getLengthA();
        final int tableBits = tableBits(sz);
        table = new int[1 << tableBits];
        keyShift = 32 - tableBits;
        ptrShift = r.beginA;

        recs = new long[Math.max(4, sz >>> 3)];
        next = new int[sz];
        recIdx = new int[sz];
    }

    Edit findLongestCommonSequence() {
        if (!scanA())
            return null;

        lcs = new Edit(0, 0);
        cnt = maxChainLength + 1;

        for (int bPtr = region.beginB; bPtr < region.endB;)
            bPtr = tryLongestCommonSequence(bPtr);

        return hasCommon && maxChainLength < cnt ? null : lcs;
    }

    private boolean scanA() {
        // Scan the elements backwards, inserting them into the hash table
        // as we go. Going in reverse places the earliest occurrence of any
        // element at the start of the chain, so we consider earlier matches
        // before later matches.
        //
        SCAN: for (int ptr = region.endA - 1; region.beginA <= ptr; ptr--) {
            final int tIdx = hash(a, ptr);

            int chainLen = 0;
            for (int rIdx = table[tIdx]; rIdx != 0;) {
                final long rec = recs[rIdx];
                if (cmp.equals(a, recPtr(rec), a, ptr)) {
                    // ptr is identical to another element. Insert it onto
                    // the front of the existing element chain.
                    //
                    int newCnt = recCnt(rec) + 1;
                    if (MAX_CNT < newCnt)
                        newCnt = MAX_CNT;
                    recs[rIdx] = recCreate(recNext(rec), ptr, newCnt);
                    next[ptr - ptrShift] = recPtr(rec);
                    recIdx[ptr - ptrShift] = rIdx;
                    continue SCAN;
                }

                rIdx = recNext(rec);
                chainLen++;
            }

            if (chainLen == maxChainLength)
                return false;

            // This is the first time we have ever seen this particular
            // element in the sequence. Construct a new chain for it.
            //
            final int rIdx = ++recCnt;
            if (rIdx == recs.length) {
                int sz = Math.min(recs.length << 1, 1 + region.getLengthA());
                long[] n = new long[sz];
                System.arraycopy(recs, 0, n, 0, recs.length);
                recs = n;
            }

            recs[rIdx] = recCreate(table[tIdx], ptr, 1);
            recIdx[ptr - ptrShift] = rIdx;
            table[tIdx] = rIdx;
        }
        return true;
    }

    private int tryLongestCommonSequence(int bPtr) {
        int bNext = bPtr + 1;
        int rIdx = table[hash(b, bPtr)];
        for (long rec; rIdx != 0; rIdx = recNext(rec)) {
            rec = recs[rIdx];

            // If there are more occurrences in A, don't use this chain.
            if (recCnt(rec) > cnt) {
                if (!hasCommon)
                    hasCommon = cmp.equals(a, recPtr(rec), b, bPtr);
                continue;
            }

            int as = recPtr(rec);
            if (!cmp.equals(a, as, b, bPtr))
                continue;

            hasCommon = true;
            TRY_LOCATIONS: for (;;) {
                int np = next[as - ptrShift];
                int bs = bPtr;
                int ae = as + 1;
                int be = bs + 1;
                int rc = recCnt(rec);

                while (region.beginA < as && region.beginB < bs
                        && cmp.equals(a, as - 1, b, bs - 1)) {
                    as--;
                    bs--;
                    if (1 < rc)
                        rc = Math.min(rc, recCnt(recs[recIdx[as - ptrShift]]));
                }
                while (ae < region.endA && be < region.endB
                        && cmp.equals(a, ae, b, be)) {
                    if (1 < rc)
                        rc = Math.min(rc, recCnt(recs[recIdx[ae - ptrShift]]));
                    ae++;
                    be++;
                }

                if (bNext < be)
                    bNext = be;
                if (lcs.getLengthA() < ae - as || rc < cnt) {
                    // If this region is the longest, or there are less
                    // occurrences of it in A, its now our LCS.
                    //
                    lcs.beginA = as;
                    lcs.beginB = bs;
                    lcs.endA = ae;
                    lcs.endB = be;
                    cnt = rc;
                }

                // Because we added elements in reverse order index 0
                // cannot possibly be the next position. Its the first
                // element of the sequence and thus would have been the
                // value of as at the start of the TRY_LOCATIONS loop.
                //
                if (np == 0)
                    break TRY_LOCATIONS;

                while (np < ae) {
                    // The next location to consider was actually within
                    // the LCS we examined above. Don't reconsider it.
                    //
                    np = next[np - ptrShift];
                    if (np == 0)
                        break TRY_LOCATIONS;
                }

                as = np;
            }
        }
        return bNext;
    }

    private int hash(HashedSequence<S> s, int idx) {
        return (cmp.hash(s, idx) * 0x9e370001 /* mix bits */) >>> keyShift;
    }

    private static long recCreate(int next, int ptr, int cnt) {
        return ((long) next << REC_NEXT_SHIFT) //
                | ((long) ptr << REC_PTR_SHIFT) //
                | cnt;
    }

    private static int recNext(long rec) {
        return (int) (rec >>> REC_NEXT_SHIFT);
    }

    private static int recPtr(long rec) {
        return ((int) (rec >>> REC_PTR_SHIFT)) & REC_PTR_MASK;
    }

    private static int recCnt(long rec) {
        return ((int) rec) & REC_CNT_MASK;
    }

    private static int tableBits(int sz) {
        int bits = 31 - Integer.numberOfLeadingZeros(sz);
        if (bits == 0)
            bits = 1;
        if (1 << bits < sz)
            bits++;
        return bits;
    }
}