RefDirectory.java

/*
 * Copyright (C) 2007, Dave Watson <dwatson@mimvista.com>
 * Copyright (C) 2009-2010, Google Inc.
 * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
 * Copyright (C) 2006, 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.internal.storage.file;

import static java.nio.charset.StandardCharsets.UTF_8;
import static org.eclipse.jgit.lib.Constants.HEAD;
import static org.eclipse.jgit.lib.Constants.LOGS;
import static org.eclipse.jgit.lib.Constants.OBJECT_ID_STRING_LENGTH;
import static org.eclipse.jgit.lib.Constants.PACKED_REFS;
import static org.eclipse.jgit.lib.Constants.R_HEADS;
import static org.eclipse.jgit.lib.Constants.R_REFS;
import static org.eclipse.jgit.lib.Constants.R_TAGS;
import static org.eclipse.jgit.lib.Ref.Storage.LOOSE;
import static org.eclipse.jgit.lib.Ref.Storage.NEW;
import static org.eclipse.jgit.lib.Ref.Storage.PACKED;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.InterruptedIOException;
import java.nio.file.DirectoryNotEmptyException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.security.DigestInputStream;
import java.security.MessageDigest;
import java.text.MessageFormat;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Stream;

import org.eclipse.jgit.annotations.NonNull;
import org.eclipse.jgit.annotations.Nullable;
import org.eclipse.jgit.errors.InvalidObjectIdException;
import org.eclipse.jgit.errors.LockFailedException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.errors.ObjectWritingException;
import org.eclipse.jgit.events.RefsChangedEvent;
import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.ConfigConstants;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectIdRef;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.lib.RefComparator;
import org.eclipse.jgit.lib.RefDatabase;
import org.eclipse.jgit.lib.RefUpdate;
import org.eclipse.jgit.lib.RefWriter;
import org.eclipse.jgit.lib.Repository;
import org.eclipse.jgit.lib.SymbolicRef;
import org.eclipse.jgit.revwalk.RevObject;
import org.eclipse.jgit.revwalk.RevTag;
import org.eclipse.jgit.revwalk.RevWalk;
import org.eclipse.jgit.util.FS;
import org.eclipse.jgit.util.FileUtils;
import org.eclipse.jgit.util.IO;
import org.eclipse.jgit.util.RawParseUtils;
import org.eclipse.jgit.util.RefList;
import org.eclipse.jgit.util.RefMap;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Traditional file system based {@link org.eclipse.jgit.lib.RefDatabase}.
 * <p>
 * This is the classical reference database representation for a Git repository.
 * References are stored in two formats: loose, and packed.
 * <p>
 * Loose references are stored as individual files within the {@code refs/}
 * directory. The file name matches the reference name and the file contents is
 * the current {@link org.eclipse.jgit.lib.ObjectId} in string form.
 * <p>
 * Packed references are stored in a single text file named {@code packed-refs}.
 * In the packed format, each reference is stored on its own line. This file
 * reduces the number of files needed for large reference spaces, reducing the
 * overall size of a Git repository on disk.
 */
public class RefDirectory extends RefDatabase {
    private static final Logger LOG = LoggerFactory
            .getLogger(RefDirectory.class);

    /** Magic string denoting the start of a symbolic reference file. */
    public static final String SYMREF = "ref: "; //$NON-NLS-1$

    /** Magic string denoting the header of a packed-refs file. */
    public static final String PACKED_REFS_HEADER = "# pack-refs with:"; //$NON-NLS-1$

    /** If in the header, denotes the file has peeled data. */
    public static final String PACKED_REFS_PEELED = " peeled"; //$NON-NLS-1$

    /** The names of the additional refs supported by this class */
    private static final String[] additionalRefsNames = new String[] {
            Constants.MERGE_HEAD, Constants.FETCH_HEAD, Constants.ORIG_HEAD,
            Constants.CHERRY_PICK_HEAD };

    @SuppressWarnings("boxing")
    private static final List<Integer> RETRY_SLEEP_MS =
            Collections.unmodifiableList(Arrays.asList(0, 100, 200, 400, 800, 1600));

    private final FileRepository parent;

    private final File gitDir;

    final File refsDir;

    final File packedRefsFile;

    final File logsDir;

    final File logsRefsDir;

    /**
     * Immutable sorted list of loose references.
     * <p>
     * Symbolic references in this collection are stored unresolved, that is
     * their target appears to be a new reference with no ObjectId. These are
     * converted into resolved references during a get operation, ensuring the
     * live value is always returned.
     */
    private final AtomicReference<RefList<LooseRef>> looseRefs = new AtomicReference<>();

    /** Immutable sorted list of packed references. */
    final AtomicReference<PackedRefList> packedRefs = new AtomicReference<>();

    /**
     * Lock for coordinating operations within a single process that may contend
     * on the {@code packed-refs} file.
     * <p>
     * All operations that write {@code packed-refs} must still acquire a
     * {@link LockFile} on {@link #packedRefsFile}, even after they have acquired
     * this lock, since there may be multiple {@link RefDirectory} instances or
     * other processes operating on the same repo on disk.
     * <p>
     * This lock exists so multiple threads in the same process can wait in a fair
     * queue without trying, failing, and retrying to acquire the on-disk lock. If
     * {@code RepositoryCache} is used, this lock instance will be used by all
     * threads.
     */
    final ReentrantLock inProcessPackedRefsLock = new ReentrantLock(true);

    /**
     * Number of modifications made to this database.
     * <p>
     * This counter is incremented when a change is made, or detected from the
     * filesystem during a read operation.
     */
    private final AtomicInteger modCnt = new AtomicInteger();

    /**
     * Last {@link #modCnt} that we sent to listeners.
     * <p>
     * This value is compared to {@link #modCnt}, and a notification is sent to
     * the listeners only when it differs.
     */
    private final AtomicInteger lastNotifiedModCnt = new AtomicInteger();

    private List<Integer> retrySleepMs = RETRY_SLEEP_MS;

    RefDirectory(FileRepository db) {
        final FS fs = db.getFS();
        parent = db;
        gitDir = db.getDirectory();
        refsDir = fs.resolve(gitDir, R_REFS);
        logsDir = fs.resolve(gitDir, LOGS);
        logsRefsDir = fs.resolve(gitDir, LOGS + '/' + R_REFS);
        packedRefsFile = fs.resolve(gitDir, PACKED_REFS);

        looseRefs.set(RefList.<LooseRef> emptyList());
        packedRefs.set(NO_PACKED_REFS);
    }

    Repository getRepository() {
        return parent;
    }

    ReflogWriter newLogWriter(boolean force) {
        return new ReflogWriter(this, force);
    }

    /**
     * Locate the log file on disk for a single reference name.
     *
     * @param name
     *            name of the ref, relative to the Git repository top level
     *            directory (so typically starts with refs/).
     * @return the log file location.
     */
    public File logFor(String name) {
        if (name.startsWith(R_REFS)) {
            name = name.substring(R_REFS.length());
            return new File(logsRefsDir, name);
        }
        return new File(logsDir, name);
    }

    /** {@inheritDoc} */
    @Override
    public void create() throws IOException {
        FileUtils.mkdir(refsDir);
        FileUtils.mkdir(new File(refsDir, R_HEADS.substring(R_REFS.length())));
        FileUtils.mkdir(new File(refsDir, R_TAGS.substring(R_REFS.length())));
        newLogWriter(false).create();
    }

    /** {@inheritDoc} */
    @Override
    public void close() {
        clearReferences();
    }

    private void clearReferences() {
        looseRefs.set(RefList.<LooseRef> emptyList());
        packedRefs.set(NO_PACKED_REFS);
    }

    /** {@inheritDoc} */
    @Override
    public void refresh() {
        super.refresh();
        clearReferences();
    }

    /** {@inheritDoc} */
    @Override
    public boolean isNameConflicting(String name) throws IOException {
        RefList<Ref> packed = getPackedRefs();
        RefList<LooseRef> loose = getLooseRefs();

        // Cannot be nested within an existing reference.
        int lastSlash = name.lastIndexOf('/');
        while (0 < lastSlash) {
            String needle = name.substring(0, lastSlash);
            if (loose.contains(needle) || packed.contains(needle))
                return true;
            lastSlash = name.lastIndexOf('/', lastSlash - 1);
        }

        // Cannot be the container of an existing reference.
        String prefix = name + '/';
        int idx;

        idx = -(packed.find(prefix) + 1);
        if (idx < packed.size() && packed.get(idx).getName().startsWith(prefix))
            return true;

        idx = -(loose.find(prefix) + 1);
        if (idx < loose.size() && loose.get(idx).getName().startsWith(prefix))
            return true;

        return false;
    }

    private RefList<LooseRef> getLooseRefs() {
        final RefList<LooseRef> oldLoose = looseRefs.get();

        LooseScanner scan = new LooseScanner(oldLoose);
        scan.scan(ALL);

        RefList<LooseRef> loose;
        if (scan.newLoose != null) {
            loose = scan.newLoose.toRefList();
            if (looseRefs.compareAndSet(oldLoose, loose))
                modCnt.incrementAndGet();
        } else
            loose = oldLoose;
        return loose;
    }

    @Nullable
    private Ref readAndResolve(String name, RefList<Ref> packed) throws IOException {
        try {
            Ref ref = readRef(name, packed);
            if (ref != null) {
                ref = resolve(ref, 0, null, null, packed);
            }
            return ref;
        } catch (IOException e) {
            if (name.contains("/") //$NON-NLS-1$
                    || !(e.getCause() instanceof InvalidObjectIdException)) {
                throw e;
            }

            // While looking for a ref outside of refs/ (e.g., 'config'), we
            // found a non-ref file (e.g., a config file) instead.  Treat this
            // as a ref-not-found condition.
            return null;
        }
    }

    /** {@inheritDoc} */
    @Override
    public Ref exactRef(String name) throws IOException {
        try {
            return readAndResolve(name, getPackedRefs());
        } finally {
            fireRefsChanged();
        }
    }

    /** {@inheritDoc} */
    @Override
    @NonNull
    public Map<String, Ref> exactRef(String... refs) throws IOException {
        try {
            RefList<Ref> packed = getPackedRefs();
            Map<String, Ref> result = new HashMap<>(refs.length);
            for (String name : refs) {
                Ref ref = readAndResolve(name, packed);
                if (ref != null) {
                    result.put(name, ref);
                }
            }
            return result;
        } finally {
            fireRefsChanged();
        }
    }

    /** {@inheritDoc} */
    @Override
    @Nullable
    public Ref firstExactRef(String... refs) throws IOException {
        try {
            RefList<Ref> packed = getPackedRefs();
            for (String name : refs) {
                Ref ref = readAndResolve(name, packed);
                if (ref != null) {
                    return ref;
                }
            }
            return null;
        } finally {
            fireRefsChanged();
        }
    }

    /** {@inheritDoc} */
    @Override
    public Map<String, Ref> getRefs(String prefix) throws IOException {
        final RefList<LooseRef> oldLoose = looseRefs.get();
        LooseScanner scan = new LooseScanner(oldLoose);
        scan.scan(prefix);
        final RefList<Ref> packed = getPackedRefs();

        RefList<LooseRef> loose;
        if (scan.newLoose != null) {
            scan.newLoose.sort();
            loose = scan.newLoose.toRefList();
            if (looseRefs.compareAndSet(oldLoose, loose))
                modCnt.incrementAndGet();
        } else
            loose = oldLoose;
        fireRefsChanged();

        RefList.Builder<Ref> symbolic = scan.symbolic;
        for (int idx = 0; idx < symbolic.size();) {
            final Ref symbolicRef = symbolic.get(idx);
            final Ref resolvedRef = resolve(symbolicRef, 0, prefix, loose, packed);
            if (resolvedRef != null && resolvedRef.getObjectId() != null) {
                symbolic.set(idx, resolvedRef);
                idx++;
            } else {
                // A broken symbolic reference, we have to drop it from the
                // collections the client is about to receive. Should be a
                // rare occurrence so pay a copy penalty.
                symbolic.remove(idx);
                final int toRemove = loose.find(symbolicRef.getName());
                if (0 <= toRemove)
                    loose = loose.remove(toRemove);
            }
        }
        symbolic.sort();

        return new RefMap(prefix, packed, upcast(loose), symbolic.toRefList());
    }

    /** {@inheritDoc} */
    @Override
    public List<Ref> getAdditionalRefs() throws IOException {
        List<Ref> ret = new LinkedList<>();
        for (String name : additionalRefsNames) {
            Ref r = exactRef(name);
            if (r != null)
                ret.add(r);
        }
        return ret;
    }

    @SuppressWarnings("unchecked")
    private RefList<Ref> upcast(RefList<? extends Ref> loose) {
        return (RefList<Ref>) loose;
    }

    private class LooseScanner {
        private final RefList<LooseRef> curLoose;

        private int curIdx;

        final RefList.Builder<Ref> symbolic = new RefList.Builder<>(4);

        RefList.Builder<LooseRef> newLoose;

        LooseScanner(RefList<LooseRef> curLoose) {
            this.curLoose = curLoose;
        }

        void scan(String prefix) {
            if (ALL.equals(prefix)) {
                scanOne(HEAD);
                scanTree(R_REFS, refsDir);

                // If any entries remain, they are deleted, drop them.
                if (newLoose == null && curIdx < curLoose.size())
                    newLoose = curLoose.copy(curIdx);

            } else if (prefix.startsWith(R_REFS) && prefix.endsWith("/")) { //$NON-NLS-1$
                curIdx = -(curLoose.find(prefix) + 1);
                File dir = new File(refsDir, prefix.substring(R_REFS.length()));
                scanTree(prefix, dir);

                // Skip over entries still within the prefix; these have
                // been removed from the directory.
                while (curIdx < curLoose.size()) {
                    if (!curLoose.get(curIdx).getName().startsWith(prefix))
                        break;
                    if (newLoose == null)
                        newLoose = curLoose.copy(curIdx);
                    curIdx++;
                }

                // Keep any entries outside of the prefix space, we
                // do not know anything about their status.
                if (newLoose != null) {
                    while (curIdx < curLoose.size())
                        newLoose.add(curLoose.get(curIdx++));
                }
            }
        }

        private boolean scanTree(String prefix, File dir) {
            final String[] entries = dir.list(LockFile.FILTER);
            if (entries == null) // not a directory or an I/O error
                return false;
            if (0 < entries.length) {
                for (int i = 0; i < entries.length; ++i) {
                    String e = entries[i];
                    File f = new File(dir, e);
                    if (f.isDirectory())
                        entries[i] += '/';
                }
                Arrays.sort(entries);
                for (String name : entries) {
                    if (name.charAt(name.length() - 1) == '/')
                        scanTree(prefix + name, new File(dir, name));
                    else
                        scanOne(prefix + name);
                }
            }
            return true;
        }

        private void scanOne(String name) {
            LooseRef cur;

            if (curIdx < curLoose.size()) {
                do {
                    cur = curLoose.get(curIdx);
                    int cmp = RefComparator.compareTo(cur, name);
                    if (cmp < 0) {
                        // Reference is not loose anymore, its been deleted.
                        // Skip the name in the new result list.
                        if (newLoose == null)
                            newLoose = curLoose.copy(curIdx);
                        curIdx++;
                        cur = null;
                        continue;
                    }

                    if (cmp > 0) // Newly discovered loose reference.
                        cur = null;
                    break;
                } while (curIdx < curLoose.size());
            } else
                cur = null; // Newly discovered loose reference.

            LooseRef n;
            try {
                n = scanRef(cur, name);
            } catch (IOException notValid) {
                n = null;
            }

            if (n != null) {
                if (cur != n && newLoose == null)
                    newLoose = curLoose.copy(curIdx);
                if (newLoose != null)
                    newLoose.add(n);
                if (n.isSymbolic())
                    symbolic.add(n);
            } else if (cur != null) {
                // Tragically, this file is no longer a loose reference.
                // Kill our cached entry of it.
                if (newLoose == null)
                    newLoose = curLoose.copy(curIdx);
            }

            if (cur != null)
                curIdx++;
        }
    }

    /** {@inheritDoc} */
    @Override
    public Ref peel(Ref ref) throws IOException {
        final Ref leaf = ref.getLeaf();
        if (leaf.isPeeled() || leaf.getObjectId() == null)
            return ref;

        ObjectIdRef newLeaf = doPeel(leaf);

        // Try to remember this peeling in the cache, so we don't have to do
        // it again in the future, but only if the reference is unchanged.
        if (leaf.getStorage().isLoose()) {
            RefList<LooseRef> curList = looseRefs.get();
            int idx = curList.find(leaf.getName());
            if (0 <= idx && curList.get(idx) == leaf) {
                LooseRef asPeeled = ((LooseRef) leaf).peel(newLeaf);
                RefList<LooseRef> newList = curList.set(idx, asPeeled);
                looseRefs.compareAndSet(curList, newList);
            }
        }

        return recreate(ref, newLeaf);
    }

    private ObjectIdRef doPeel(Ref leaf) throws MissingObjectException,
            IOException {
        try (RevWalk rw = new RevWalk(getRepository())) {
            RevObject obj = rw.parseAny(leaf.getObjectId());
            if (obj instanceof RevTag) {
                return new ObjectIdRef.PeeledTag(leaf.getStorage(), leaf
                        .getName(), leaf.getObjectId(), rw.peel(obj).copy());
            }
            return new ObjectIdRef.PeeledNonTag(leaf.getStorage(),
                    leaf.getName(), leaf.getObjectId());
        }
    }

    private static Ref recreate(Ref old, ObjectIdRef leaf) {
        if (old.isSymbolic()) {
            Ref dst = recreate(old.getTarget(), leaf);
            return new SymbolicRef(old.getName(), dst);
        }
        return leaf;
    }

    void storedSymbolicRef(RefDirectoryUpdate u, FileSnapshot snapshot,
            String target) {
        putLooseRef(newSymbolicRef(snapshot, u.getRef().getName(), target));
        fireRefsChanged();
    }

    /** {@inheritDoc} */
    @Override
    public RefDirectoryUpdate newUpdate(String name, boolean detach)
            throws IOException {
        boolean detachingSymbolicRef = false;
        final RefList<Ref> packed = getPackedRefs();
        Ref ref = readRef(name, packed);
        if (ref != null)
            ref = resolve(ref, 0, null, null, packed);
        if (ref == null)
            ref = new ObjectIdRef.Unpeeled(NEW, name, null);
        else {
            detachingSymbolicRef = detach && ref.isSymbolic();
        }
        RefDirectoryUpdate refDirUpdate = new RefDirectoryUpdate(this, ref);
        if (detachingSymbolicRef)
            refDirUpdate.setDetachingSymbolicRef();
        return refDirUpdate;
    }

    /** {@inheritDoc} */
    @Override
    public RefDirectoryRename newRename(String fromName, String toName)
            throws IOException {
        RefDirectoryUpdate from = newUpdate(fromName, false);
        RefDirectoryUpdate to = newUpdate(toName, false);
        return new RefDirectoryRename(from, to);
    }

    /** {@inheritDoc} */
    @Override
    public PackedBatchRefUpdate newBatchUpdate() {
        return new PackedBatchRefUpdate(this);
    }

    /** {@inheritDoc} */
    @Override
    public boolean performsAtomicTransactions() {
        return true;
    }

    void stored(RefDirectoryUpdate update, FileSnapshot snapshot) {
        final ObjectId target = update.getNewObjectId().copy();
        final Ref leaf = update.getRef().getLeaf();
        putLooseRef(new LooseUnpeeled(snapshot, leaf.getName(), target));
    }

    private void putLooseRef(LooseRef ref) {
        RefList<LooseRef> cList, nList;
        do {
            cList = looseRefs.get();
            nList = cList.put(ref);
        } while (!looseRefs.compareAndSet(cList, nList));
        modCnt.incrementAndGet();
        fireRefsChanged();
    }

    void delete(RefDirectoryUpdate update) throws IOException {
        Ref dst = update.getRef();
        if (!update.isDetachingSymbolicRef()) {
            dst = dst.getLeaf();
        }
        String name = dst.getName();

        // Write the packed-refs file using an atomic update. We might
        // wind up reading it twice, before and after the lock, to ensure
        // we don't miss an edit made externally.
        final PackedRefList packed = getPackedRefs();
        if (packed.contains(name)) {
            inProcessPackedRefsLock.lock();
            try {
                LockFile lck = lockPackedRefsOrThrow();
                try {
                    PackedRefList cur = readPackedRefs();
                    int idx = cur.find(name);
                    if (0 <= idx) {
                        commitPackedRefs(lck, cur.remove(idx), packed, true);
                    }
                } finally {
                    lck.unlock();
                }
            } finally {
                inProcessPackedRefsLock.unlock();
            }
        }

        RefList<LooseRef> curLoose, newLoose;
        do {
            curLoose = looseRefs.get();
            int idx = curLoose.find(name);
            if (idx < 0)
                break;
            newLoose = curLoose.remove(idx);
        } while (!looseRefs.compareAndSet(curLoose, newLoose));

        int levels = levelsIn(name) - 2;
        delete(logFor(name), levels);
        if (dst.getStorage().isLoose()) {
            update.unlock();
            delete(fileFor(name), levels);
        }

        modCnt.incrementAndGet();
        fireRefsChanged();
    }

    /**
     * Adds a set of refs to the set of packed-refs. Only non-symbolic refs are
     * added. If a ref with the given name already existed in packed-refs it is
     * updated with the new value. Each loose ref which was added to the
     * packed-ref file is deleted. If a given ref can't be locked it will not be
     * added to the pack file.
     *
     * @param refs
     *            the refs to be added. Must be fully qualified.
     * @throws java.io.IOException
     */
    public void pack(List<String> refs) throws IOException {
        pack(refs, Collections.emptyMap());
    }

    PackedRefList pack(Map<String, LockFile> heldLocks) throws IOException {
        return pack(heldLocks.keySet(), heldLocks);
    }

    private PackedRefList pack(Collection<String> refs,
            Map<String, LockFile> heldLocks) throws IOException {
        for (LockFile ol : heldLocks.values()) {
            ol.requireLock();
        }
        if (refs.isEmpty()) {
            return null;
        }
        FS fs = parent.getFS();

        // Lock the packed refs file and read the content
        inProcessPackedRefsLock.lock();
        try {
            LockFile lck = lockPackedRefsOrThrow();
            try {
                final PackedRefList packed = getPackedRefs();
                RefList<Ref> cur = readPackedRefs();

                // Iterate over all refs to be packed
                boolean dirty = false;
                for (String refName : refs) {
                    Ref oldRef = readRef(refName, cur);
                    if (oldRef == null) {
                        continue; // A non-existent ref is already correctly packed.
                    }
                    if (oldRef.isSymbolic()) {
                        continue; // can't pack symbolic refs
                    }
                    // Add/Update it to packed-refs
                    Ref newRef = peeledPackedRef(oldRef);
                    if (newRef == oldRef) {
                        // No-op; peeledPackedRef returns the input ref only if it's already
                        // packed, and readRef returns a packed ref only if there is no
                        // loose ref.
                        continue;
                    }

                    dirty = true;
                    int idx = cur.find(refName);
                    if (idx >= 0) {
                        cur = cur.set(idx, newRef);
                    } else {
                        cur = cur.add(idx, newRef);
                    }
                }
                if (!dirty) {
                    // All requested refs were already packed accurately
                    return packed;
                }

                // The new content for packed-refs is collected. Persist it.
                PackedRefList result = commitPackedRefs(lck, cur, packed,
                        false);

                // Now delete the loose refs which are now packed
                for (String refName : refs) {
                    // Lock the loose ref
                    File refFile = fileFor(refName);
                    if (!fs.exists(refFile)) {
                        continue;
                    }

                    LockFile rLck = heldLocks.get(refName);
                    boolean shouldUnlock;
                    if (rLck == null) {
                        rLck = new LockFile(refFile);
                        if (!rLck.lock()) {
                            continue;
                        }
                        shouldUnlock = true;
                    } else {
                        shouldUnlock = false;
                    }

                    try {
                        LooseRef currentLooseRef = scanRef(null, refName);
                        if (currentLooseRef == null || currentLooseRef.isSymbolic()) {
                            continue;
                        }
                        Ref packedRef = cur.get(refName);
                        ObjectId clr_oid = currentLooseRef.getObjectId();
                        if (clr_oid != null
                                && clr_oid.equals(packedRef.getObjectId())) {
                            RefList<LooseRef> curLoose, newLoose;
                            do {
                                curLoose = looseRefs.get();
                                int idx = curLoose.find(refName);
                                if (idx < 0) {
                                    break;
                                }
                                newLoose = curLoose.remove(idx);
                            } while (!looseRefs.compareAndSet(curLoose, newLoose));
                            int levels = levelsIn(refName) - 2;
                            delete(refFile, levels, rLck);
                        }
                    } finally {
                        if (shouldUnlock) {
                            rLck.unlock();
                        }
                    }
                }
                // Don't fire refsChanged. The refs have not change, only their
                // storage.
                return result;
            } finally {
                lck.unlock();
            }
        } finally {
            inProcessPackedRefsLock.unlock();
        }
    }

    @Nullable
    LockFile lockPackedRefs() throws IOException {
        LockFile lck = new LockFile(packedRefsFile);
        for (int ms : getRetrySleepMs()) {
            sleep(ms);
            if (lck.lock()) {
                return lck;
            }
        }
        return null;
    }

    private LockFile lockPackedRefsOrThrow() throws IOException {
        LockFile lck = lockPackedRefs();
        if (lck == null) {
            throw new LockFailedException(packedRefsFile);
        }
        return lck;
    }

    /**
     * Make sure a ref is peeled and has the Storage PACKED. If the given ref
     * has this attributes simply return it. Otherwise create a new peeled
     * {@link ObjectIdRef} where Storage is set to PACKED.
     *
     * @param f
     * @return a ref for Storage PACKED having the same name, id, peeledId as f
     * @throws MissingObjectException
     * @throws IOException
     */
    private Ref peeledPackedRef(Ref f)
            throws MissingObjectException, IOException {
        if (f.getStorage().isPacked() && f.isPeeled()) {
            return f;
        }
        if (!f.isPeeled()) {
            f = peel(f);
        }
        ObjectId peeledObjectId = f.getPeeledObjectId();
        if (peeledObjectId != null) {
            return new ObjectIdRef.PeeledTag(PACKED, f.getName(),
                    f.getObjectId(), peeledObjectId);
        }
        return new ObjectIdRef.PeeledNonTag(PACKED, f.getName(),
                f.getObjectId());
    }

    void log(boolean force, RefUpdate update, String msg, boolean deref)
            throws IOException {
        newLogWriter(force).log(update, msg, deref);
    }

    private Ref resolve(final Ref ref, int depth, String prefix,
            RefList<LooseRef> loose, RefList<Ref> packed) throws IOException {
        if (ref.isSymbolic()) {
            Ref dst = ref.getTarget();

            if (MAX_SYMBOLIC_REF_DEPTH <= depth)
                return null; // claim it doesn't exist

            // If the cached value can be assumed to be current due to a
            // recent scan of the loose directory, use it.
            if (loose != null && dst.getName().startsWith(prefix)) {
                int idx;
                if (0 <= (idx = loose.find(dst.getName())))
                    dst = loose.get(idx);
                else if (0 <= (idx = packed.find(dst.getName())))
                    dst = packed.get(idx);
                else
                    return ref;
            } else {
                dst = readRef(dst.getName(), packed);
                if (dst == null)
                    return ref;
            }

            dst = resolve(dst, depth + 1, prefix, loose, packed);
            if (dst == null)
                return null;
            return new SymbolicRef(ref.getName(), dst);
        }
        return ref;
    }

    PackedRefList getPackedRefs() throws IOException {
        boolean trustFolderStat = getRepository().getConfig().getBoolean(
                ConfigConstants.CONFIG_CORE_SECTION,
                ConfigConstants.CONFIG_KEY_TRUSTFOLDERSTAT, true);

        final PackedRefList curList = packedRefs.get();
        if (trustFolderStat && !curList.snapshot.isModified(packedRefsFile)) {
            return curList;
        }

        final PackedRefList newList = readPackedRefs();
        if (packedRefs.compareAndSet(curList, newList)
                && !curList.id.equals(newList.id)) {
            modCnt.incrementAndGet();
        }
        return newList;
    }

    private PackedRefList readPackedRefs() throws IOException {
        int maxStaleRetries = 5;
        int retries = 0;
        while (true) {
            final FileSnapshot snapshot = FileSnapshot.save(packedRefsFile);
            final MessageDigest digest = Constants.newMessageDigest();
            try (BufferedReader br = new BufferedReader(new InputStreamReader(
                    new DigestInputStream(new FileInputStream(packedRefsFile),
                            digest),
                    UTF_8))) {
                try {
                    return new PackedRefList(parsePackedRefs(br), snapshot,
                            ObjectId.fromRaw(digest.digest()));
                } catch (IOException e) {
                    if (FileUtils.isStaleFileHandleInCausalChain(e)
                            && retries < maxStaleRetries) {
                        if (LOG.isDebugEnabled()) {
                            LOG.debug(MessageFormat.format(
                                    JGitText.get().packedRefsHandleIsStale,
                                    Integer.valueOf(retries)), e);
                        }
                        retries++;
                        continue;
                    }
                    throw e;
                }
            } catch (FileNotFoundException noPackedRefs) {
                if (packedRefsFile.exists()) {
                    throw noPackedRefs;
                }
                // Ignore it and leave the new list empty.
                return NO_PACKED_REFS;
            }
        }
    }

    private RefList<Ref> parsePackedRefs(BufferedReader br)
            throws IOException {
        RefList.Builder<Ref> all = new RefList.Builder<>();
        Ref last = null;
        boolean peeled = false;
        boolean needSort = false;

        String p;
        while ((p = br.readLine()) != null) {
            if (p.charAt(0) == '#') {
                if (p.startsWith(PACKED_REFS_HEADER)) {
                    p = p.substring(PACKED_REFS_HEADER.length());
                    peeled = p.contains(PACKED_REFS_PEELED);
                }
                continue;
            }

            if (p.charAt(0) == '^') {
                if (last == null)
                    throw new IOException(JGitText.get().peeledLineBeforeRef);

                ObjectId id = ObjectId.fromString(p.substring(1));
                last = new ObjectIdRef.PeeledTag(PACKED, last.getName(), last
                        .getObjectId(), id);
                all.set(all.size() - 1, last);
                continue;
            }

            int sp = p.indexOf(' ');
            if (sp < 0) {
                throw new IOException(MessageFormat.format(
                        JGitText.get().packedRefsCorruptionDetected,
                        packedRefsFile.getAbsolutePath()));
            }
            ObjectId id = ObjectId.fromString(p.substring(0, sp));
            String name = copy(p, sp + 1, p.length());
            ObjectIdRef cur;
            if (peeled)
                cur = new ObjectIdRef.PeeledNonTag(PACKED, name, id);
            else
                cur = new ObjectIdRef.Unpeeled(PACKED, name, id);
            if (last != null && RefComparator.compareTo(last, cur) > 0)
                needSort = true;
            all.add(cur);
            last = cur;
        }

        if (needSort)
            all.sort();
        return all.toRefList();
    }

    private static String copy(String src, int off, int end) {
        // Don't use substring since it could leave a reference to the much
        // larger existing string. Force construction of a full new object.
        return new StringBuilder(end - off).append(src, off, end).toString();
    }

    PackedRefList commitPackedRefs(final LockFile lck, final RefList<Ref> refs,
            final PackedRefList oldPackedList, boolean changed)
            throws IOException {
        // Can't just return packedRefs.get() from this method; it might have been
        // updated again after writePackedRefs() returns.
        AtomicReference<PackedRefList> result = new AtomicReference<>();
        new RefWriter(refs) {
            @Override
            protected void writeFile(String name, byte[] content)
                    throws IOException {
                lck.setFSync(true);
                lck.setNeedSnapshot(true);
                try {
                    lck.write(content);
                } catch (IOException ioe) {
                    throw new ObjectWritingException(MessageFormat.format(JGitText.get().unableToWrite, name), ioe);
                }
                try {
                    lck.waitForStatChange();
                } catch (InterruptedException e) {
                    lck.unlock();
                    throw new ObjectWritingException(
                            MessageFormat.format(
                                    JGitText.get().interruptedWriting, name),
                            e);
                }
                if (!lck.commit())
                    throw new ObjectWritingException(MessageFormat.format(JGitText.get().unableToWrite, name));

                byte[] digest = Constants.newMessageDigest().digest(content);
                PackedRefList newPackedList = new PackedRefList(
                        refs, lck.getCommitSnapshot(), ObjectId.fromRaw(digest));

                // This thread holds the file lock, so no other thread or process should
                // be able to modify the packed-refs file on disk. If the list changed,
                // it means something is very wrong, so throw an exception.
                //
                // However, we can't use a naive compareAndSet to check whether the
                // update was successful, because another thread might _read_ the
                // packed refs file that was written out by this thread while holding
                // the lock, and update the packedRefs reference to point to that. So
                // compare the actual contents instead.
                PackedRefList afterUpdate = packedRefs.updateAndGet(
                        p -> p.id.equals(oldPackedList.id) ? newPackedList : p);
                if (!afterUpdate.id.equals(newPackedList.id)) {
                    throw new ObjectWritingException(
                            MessageFormat.format(JGitText.get().unableToWrite, name));
                }
                if (changed) {
                    modCnt.incrementAndGet();
                }
                result.set(newPackedList);
            }
        }.writePackedRefs();
        return result.get();
    }

    private Ref readRef(String name, RefList<Ref> packed) throws IOException {
        final RefList<LooseRef> curList = looseRefs.get();
        final int idx = curList.find(name);
        if (0 <= idx) {
            final LooseRef o = curList.get(idx);
            final LooseRef n = scanRef(o, name);
            if (n == null) {
                if (looseRefs.compareAndSet(curList, curList.remove(idx)))
                    modCnt.incrementAndGet();
                return packed.get(name);
            }

            if (o == n)
                return n;
            if (looseRefs.compareAndSet(curList, curList.set(idx, n)))
                modCnt.incrementAndGet();
            return n;
        }

        final LooseRef n = scanRef(null, name);
        if (n == null)
            return packed.get(name);

        // check whether the found new ref is the an additional ref. These refs
        // should not go into looseRefs
        for (String additionalRefsName : additionalRefsNames) {
            if (name.equals(additionalRefsName)) {
                return n;
            }
        }

        if (looseRefs.compareAndSet(curList, curList.add(idx, n)))
            modCnt.incrementAndGet();
        return n;
    }

    LooseRef scanRef(LooseRef ref, String name) throws IOException {
        final File path = fileFor(name);
        FileSnapshot currentSnapshot = null;

        if (ref != null) {
            currentSnapshot = ref.getSnapShot();
            if (!currentSnapshot.isModified(path))
                return ref;
            name = ref.getName();
        }

        final int limit = 4096;
        final byte[] buf;
        FileSnapshot otherSnapshot = FileSnapshot.save(path);
        try {
            buf = IO.readSome(path, limit);
        } catch (FileNotFoundException noFile) {
            if (path.exists() && path.isFile()) {
                throw noFile;
            }
            return null; // doesn't exist or no file; not a reference.
        }

        int n = buf.length;
        if (n == 0)
            return null; // empty file; not a reference.

        if (isSymRef(buf, n)) {
            if (n == limit)
                return null; // possibly truncated ref

            // trim trailing whitespace
            while (0 < n && Character.isWhitespace(buf[n - 1]))
                n--;
            if (n < 6) {
                String content = RawParseUtils.decode(buf, 0, n);
                throw new IOException(MessageFormat.format(JGitText.get().notARef, name, content));
            }
            final String target = RawParseUtils.decode(buf, 5, n);
            if (ref != null && ref.isSymbolic()
                    && ref.getTarget().getName().equals(target)) {
                assert(currentSnapshot != null);
                currentSnapshot.setClean(otherSnapshot);
                return ref;
            }
            return newSymbolicRef(otherSnapshot, name, target);
        }

        if (n < OBJECT_ID_STRING_LENGTH)
            return null; // impossibly short object identifier; not a reference.

        final ObjectId id;
        try {
            id = ObjectId.fromString(buf, 0);
            if (ref != null && !ref.isSymbolic()
                    && id.equals(ref.getTarget().getObjectId())) {
                assert(currentSnapshot != null);
                currentSnapshot.setClean(otherSnapshot);
                return ref;
            }

        } catch (IllegalArgumentException notRef) {
            while (0 < n && Character.isWhitespace(buf[n - 1]))
                n--;
            String content = RawParseUtils.decode(buf, 0, n);

            throw new IOException(MessageFormat.format(JGitText.get().notARef,
                    name, content), notRef);
        }
        return new LooseUnpeeled(otherSnapshot, name, id);
    }

    private static boolean isSymRef(byte[] buf, int n) {
        if (n < 6)
            return false;
        return /**/buf[0] == 'r' //
                && buf[1] == 'e' //
                && buf[2] == 'f' //
                && buf[3] == ':' //
                && buf[4] == ' ';
    }

    /**
     * Detect if we are in a clone command execution
     *
     * @return {@code true} if we are currently cloning a repository
     * @throws IOException
     */
    boolean isInClone() throws IOException {
        return hasDanglingHead() && !packedRefsFile.exists() && !hasLooseRef();
    }

    private boolean hasDanglingHead() throws IOException {
        Ref head = exactRef(Constants.HEAD);
        if (head != null) {
            ObjectId id = head.getObjectId();
            return id == null || id.equals(ObjectId.zeroId());
        }
        return false;
    }

    private boolean hasLooseRef() throws IOException {
        try (Stream<Path> stream = Files.walk(refsDir.toPath())) {
            return stream.anyMatch(Files::isRegularFile);
        }
    }

    /** If the parent should fire listeners, fires them. */
    void fireRefsChanged() {
        final int last = lastNotifiedModCnt.get();
        final int curr = modCnt.get();
        if (last != curr && lastNotifiedModCnt.compareAndSet(last, curr) && last != 0)
            parent.fireEvent(new RefsChangedEvent());
    }

    /**
     * Create a reference update to write a temporary reference.
     *
     * @return an update for a new temporary reference.
     * @throws IOException
     *             a temporary name cannot be allocated.
     */
    RefDirectoryUpdate newTemporaryUpdate() throws IOException {
        File tmp = File.createTempFile("renamed_", "_ref", refsDir); //$NON-NLS-1$ //$NON-NLS-2$
        String name = Constants.R_REFS + tmp.getName();
        Ref ref = new ObjectIdRef.Unpeeled(NEW, name, null);
        return new RefDirectoryUpdate(this, ref);
    }

    /**
     * Locate the file on disk for a single reference name.
     *
     * @param name
     *            name of the ref, relative to the Git repository top level
     *            directory (so typically starts with refs/).
     * @return the loose file location.
     */
    File fileFor(String name) {
        if (name.startsWith(R_REFS)) {
            name = name.substring(R_REFS.length());
            return new File(refsDir, name);
        }
        return new File(gitDir, name);
    }

    static int levelsIn(String name) {
        int count = 0;
        for (int p = name.indexOf('/'); p >= 0; p = name.indexOf('/', p + 1))
            count++;
        return count;
    }

    static void delete(File file, int depth) throws IOException {
        delete(file, depth, null);
    }

    private static void delete(File file, int depth, LockFile rLck)
            throws IOException {
        if (!file.delete() && file.isFile()) {
            throw new IOException(MessageFormat.format(
                    JGitText.get().fileCannotBeDeleted, file));
        }

        if (rLck != null) {
            rLck.unlock(); // otherwise cannot delete dir below
        }
        File dir = file.getParentFile();
        for (int i = 0; i < depth; ++i) {
            try {
                Files.deleteIfExists(dir.toPath());
            } catch (DirectoryNotEmptyException e) {
                // Don't log; normal case when there are other refs with the
                // same prefix
                break;
            } catch (IOException e) {
                LOG.warn(MessageFormat.format(JGitText.get().unableToRemovePath,
                        dir), e);
                break;
            }
            dir = dir.getParentFile();
        }
    }

    /**
     * Get times to sleep while retrying a possibly contentious operation.
     * <p>
     * For retrying an operation that might have high contention, such as locking
     * the {@code packed-refs} file, the caller may implement a retry loop using
     * the returned values:
     *
     * <pre>
     * for (int toSleepMs : getRetrySleepMs()) {
     *   sleep(toSleepMs);
     *   if (isSuccessful(doSomething())) {
     *     return success;
     *   }
     * }
     * return failure;
     * </pre>
     *
     * The first value in the returned iterable is 0, and the caller should treat
     * a fully-consumed iterator as a timeout.
     *
     * @return iterable of times, in milliseconds, that the caller should sleep
     *         before attempting an operation.
     */
    Iterable<Integer> getRetrySleepMs() {
        return retrySleepMs;
    }

    void setRetrySleepMs(List<Integer> retrySleepMs) {
        if (retrySleepMs == null || retrySleepMs.isEmpty()
                || retrySleepMs.get(0).intValue() != 0) {
            throw new IllegalArgumentException();
        }
        this.retrySleepMs = retrySleepMs;
    }

    /**
     * Sleep with {@link Thread#sleep(long)}, converting {@link
     * InterruptedException} to {@link InterruptedIOException}.
     *
     * @param ms
     *            time to sleep, in milliseconds; zero or negative is a no-op.
     * @throws InterruptedIOException
     *             if sleeping was interrupted.
     */
    static void sleep(long ms) throws InterruptedIOException {
        if (ms <= 0) {
            return;
        }
        try {
            Thread.sleep(ms);
        } catch (InterruptedException e) {
            InterruptedIOException ie = new InterruptedIOException();
            ie.initCause(e);
            throw ie;
        }
    }

    static class PackedRefList extends RefList<Ref> {

        private final FileSnapshot snapshot;

        private final ObjectId id;

        private PackedRefList(RefList<Ref> src, FileSnapshot s, ObjectId i) {
            super(src);
            snapshot = s;
            id = i;
        }
    }

    private static final PackedRefList NO_PACKED_REFS = new PackedRefList(
            RefList.emptyList(), FileSnapshot.MISSING_FILE,
            ObjectId.zeroId());

    private static LooseSymbolicRef newSymbolicRef(FileSnapshot snapshot,
            String name, String target) {
        Ref dst = new ObjectIdRef.Unpeeled(NEW, target, null);
        return new LooseSymbolicRef(snapshot, name, dst);
    }

    private static interface LooseRef extends Ref {
        FileSnapshot getSnapShot();

        LooseRef peel(ObjectIdRef newLeaf);
    }

    private static final class LoosePeeledTag extends ObjectIdRef.PeeledTag
            implements LooseRef {
        private final FileSnapshot snapShot;

        LoosePeeledTag(FileSnapshot snapshot, @NonNull String refName,
                @NonNull ObjectId id, @NonNull ObjectId p) {
            super(LOOSE, refName, id, p);
            this.snapShot = snapshot;
        }

        @Override
        public FileSnapshot getSnapShot() {
            return snapShot;
        }

        @Override
        public LooseRef peel(ObjectIdRef newLeaf) {
            return this;
        }
    }

    private static final class LooseNonTag extends ObjectIdRef.PeeledNonTag
            implements LooseRef {
        private final FileSnapshot snapShot;

        LooseNonTag(FileSnapshot snapshot, @NonNull String refName,
                @NonNull ObjectId id) {
            super(LOOSE, refName, id);
            this.snapShot = snapshot;
        }

        @Override
        public FileSnapshot getSnapShot() {
            return snapShot;
        }

        @Override
        public LooseRef peel(ObjectIdRef newLeaf) {
            return this;
        }
    }

    private static final class LooseUnpeeled extends ObjectIdRef.Unpeeled
            implements LooseRef {
        private FileSnapshot snapShot;

        LooseUnpeeled(FileSnapshot snapShot, @NonNull String refName,
                @NonNull ObjectId id) {
            super(LOOSE, refName, id);
            this.snapShot = snapShot;
        }

        @Override
        public FileSnapshot getSnapShot() {
            return snapShot;
        }

        @NonNull
        @Override
        public ObjectId getObjectId() {
            ObjectId id = super.getObjectId();
            assert id != null; // checked in constructor
            return id;
        }

        @Override
        public LooseRef peel(ObjectIdRef newLeaf) {
            ObjectId peeledObjectId = newLeaf.getPeeledObjectId();
            ObjectId objectId = getObjectId();
            if (peeledObjectId != null) {
                return new LoosePeeledTag(snapShot, getName(),
                        objectId, peeledObjectId);
            }
            return new LooseNonTag(snapShot, getName(), objectId);
        }
    }

    private static final class LooseSymbolicRef extends SymbolicRef implements
            LooseRef {
        private final FileSnapshot snapShot;

        LooseSymbolicRef(FileSnapshot snapshot, @NonNull String refName,
                @NonNull Ref target) {
            super(refName, target);
            this.snapShot = snapshot;
        }

        @Override
        public FileSnapshot getSnapShot() {
            return snapShot;
        }

        @Override
        public LooseRef peel(ObjectIdRef newLeaf) {
            // We should never try to peel the symbolic references.
            throw new UnsupportedOperationException();
        }
    }
}