RefMap.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.util;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.function.BinaryOperator;
import java.util.stream.Collector;
import java.util.stream.Collectors;

import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.lib.RefComparator;

/**
 * Specialized Map to present a {@code RefDatabase} namespace.
 * <p>
 * Although not declared as a {@link java.util.SortedMap}, iterators from this
 * map's projections always return references in
 * {@link org.eclipse.jgit.lib.RefComparator} ordering. The map's internal
 * representation is a sorted array of {@link org.eclipse.jgit.lib.Ref} objects,
 * which means lookup and replacement is O(log N), while insertion and removal
 * can be as expensive as O(N + log N) while the list expands or contracts.
 * Since this is not a general map implementation, all entries must be keyed by
 * the reference name.
 * <p>
 * This class is really intended as a helper for {@code RefDatabase}, which
 * needs to perform a merge-join of three sorted
 * {@link org.eclipse.jgit.util.RefList}s in order to present the unified
 * namespace of the packed-refs file, the loose refs/ directory tree, and the
 * resolved form of any symbolic references.
 */
public class RefMap extends AbstractMap<String, Ref> {
	/**
	 * Prefix denoting the reference subspace this map contains.
	 * <p>
	 * All reference names in this map must start with this prefix. If the
	 * prefix is not the empty string, it must end with a '/'.
	 */
	final String prefix;

	/** Immutable collection of the packed references at construction time. */
	RefList<Ref> packed;

	/**
	 * Immutable collection of the loose references at construction time.
	 * <p>
	 * If an entry appears here and in {@link #packed}, this entry must take
	 * precedence, as its more current. Symbolic references in this collection
	 * are typically unresolved, so they only tell us who their target is, but
	 * not the current value of the target.
	 */
	RefList<Ref> loose;

	/**
	 * Immutable collection of resolved symbolic references.
	 * <p>
	 * This collection contains only the symbolic references we were able to
	 * resolve at map construction time. Other loose references must be read
	 * from {@link #loose}. Every entry in this list must be matched by an entry
	 * in {@code loose}, otherwise it might be omitted by the map.
	 */
	RefList<Ref> resolved;

	int size;

	boolean sizeIsValid;

	private Set<Entry<String, Ref>> entrySet;

	/**
	 * Construct an empty map with a small initial capacity.
	 */
	public RefMap() {
		prefix = ""; //$NON-NLS-1$
		packed = RefList.emptyList();
		loose = RefList.emptyList();
		resolved = RefList.emptyList();
	}

	/**
	 * Construct a map to merge 3 collections together.
	 *
	 * @param prefix
	 *            prefix used to slice the lists down. Only references whose
	 *            names start with this prefix will appear to reside in the map.
	 *            Must not be null, use {@code ""} (the empty string) to select
	 *            all list items.
	 * @param packed
	 *            items from the packed reference list, this is the last list
	 *            searched.
	 * @param loose
	 *            items from the loose reference list, this list overrides
	 *            {@code packed} if a name appears in both.
	 * @param resolved
	 *            resolved symbolic references. This list overrides the prior
	 *            list {@code loose}, if an item appears in both. Items in this
	 *            list <b>must</b> also appear in {@code loose}.
	 */
	@SuppressWarnings("unchecked")
	public RefMap(String prefix, RefList<? extends Ref> packed,
			RefList<? extends Ref> loose, RefList<? extends Ref> resolved) {
		this.prefix = prefix;
		this.packed = (RefList<Ref>) packed;
		this.loose = (RefList<Ref>) loose;
		this.resolved = (RefList<Ref>) resolved;
	}

	/** {@inheritDoc} */
	@Override
	public boolean containsKey(Object name) {
		return get(name) != null;
	}

	/** {@inheritDoc} */
	@Override
	public Ref get(Object key) {
		String name = toRefName((String) key);
		Ref ref = resolved.get(name);
		if (ref == null)
			ref = loose.get(name);
		if (ref == null)
			ref = packed.get(name);
		return ref;
	}

	/** {@inheritDoc} */
	@Override
	public Ref put(String keyName, Ref value) {
		String name = toRefName(keyName);

		if (!name.equals(value.getName()))
			throw new IllegalArgumentException();

		if (!resolved.isEmpty()) {
			// Collapse the resolved list into the loose list so we
			// can discard it and stop joining the two together.
			for (Ref ref : resolved)
				loose = loose.put(ref);
			resolved = RefList.emptyList();
		}

		int idx = loose.find(name);
		if (0 <= idx) {
			Ref prior = loose.get(name);
			loose = loose.set(idx, value);
			return prior;
		}
		Ref prior = get(keyName);
		loose = loose.add(idx, value);
		sizeIsValid = false;
		return prior;
	}

	/** {@inheritDoc} */
	@Override
	public Ref remove(Object key) {
		String name = toRefName((String) key);
		Ref res = null;
		int idx;
		if (0 <= (idx = packed.find(name))) {
			res = packed.get(name);
			packed = packed.remove(idx);
			sizeIsValid = false;
		}
		if (0 <= (idx = loose.find(name))) {
			res = loose.get(name);
			loose = loose.remove(idx);
			sizeIsValid = false;
		}
		if (0 <= (idx = resolved.find(name))) {
			res = resolved.get(name);
			resolved = resolved.remove(idx);
			sizeIsValid = false;
		}
		return res;
	}

	/** {@inheritDoc} */
	@Override
	public boolean isEmpty() {
		return entrySet().isEmpty();
	}

	/** {@inheritDoc} */
	@Override
	public Set<Entry<String, Ref>> entrySet() {
		if (entrySet == null) {
			entrySet = new AbstractSet<>() {

				@Override
				public Iterator<Entry<String, Ref>> iterator() {
					return new SetIterator();
				}

				@Override
				public int size() {
					if (!sizeIsValid) {
						size = 0;
						Iterator<?> i = entrySet().iterator();
						for (; i.hasNext(); i.next())
							size++;
						sizeIsValid = true;
					}
					return size;
				}

				@Override
				public boolean isEmpty() {
					if (sizeIsValid)
						return 0 == size;
					return !iterator().hasNext();
				}

				@Override
				public void clear() {
					packed = RefList.emptyList();
					loose = RefList.emptyList();
					resolved = RefList.emptyList();
					size = 0;
					sizeIsValid = true;
				}
			};
		}
		return entrySet;
	}

	/** {@inheritDoc} */
	@Override
	public String toString() {
		StringBuilder r = new StringBuilder();
		boolean first = true;
		r.append('[');
		for (Ref ref : values()) {
			if (first)
				first = false;
			else
				r.append(", "); //$NON-NLS-1$
			r.append(ref);
		}
		r.append(']');
		return r.toString();
	}

	/**
	 * Create a {@link Collector} for {@link Ref}.
	 *
	 * @param mergeFunction
	 * @return {@link Collector} for {@link Ref}
	 * @since 5.4
	 */
	public static Collector<Ref, ?, RefMap> toRefMap(
			BinaryOperator<Ref> mergeFunction) {
		return Collectors.collectingAndThen(RefList.toRefList(mergeFunction),
				(refs) -> new RefMap("", //$NON-NLS-1$
							refs, RefList.emptyList(),
						RefList.emptyList()));
	}

	private String toRefName(String name) {
		if (0 < prefix.length())
			name = prefix + name;
		return name;
	}

	String toMapKey(Ref ref) {
		String name = ref.getName();
		if (0 < prefix.length())
			name = name.substring(prefix.length());
		return name;
	}

	private class SetIterator implements Iterator<Entry<String, Ref>> {
		private int packedIdx;

		private int looseIdx;

		private int resolvedIdx;

		private Entry<String, Ref> next;

		SetIterator() {
			if (0 < prefix.length()) {
				packedIdx = -(packed.find(prefix) + 1);
				looseIdx = -(loose.find(prefix) + 1);
				resolvedIdx = -(resolved.find(prefix) + 1);
			}
		}

		@Override
		public boolean hasNext() {
			if (next == null)
				next = peek();
			return next != null;
		}

		@Override
		public Entry<String, Ref> next() {
			if (hasNext()) {
				Entry<String, Ref> r = next;
				next = peek();
				return r;
			}
			throw new NoSuchElementException();
		}

		public Entry<String, Ref> peek() {
			if (packedIdx < packed.size() && looseIdx < loose.size()) {
				Ref p = packed.get(packedIdx);
				Ref l = loose.get(looseIdx);
				int cmp = RefComparator.compareTo(p, l);
				if (cmp < 0) {
					packedIdx++;
					return toEntry(p);
				}

				if (cmp == 0)
					packedIdx++;
				looseIdx++;
				return toEntry(resolveLoose(l));
			}

			if (looseIdx < loose.size())
				return toEntry(resolveLoose(loose.get(looseIdx++)));
			if (packedIdx < packed.size())
				return toEntry(packed.get(packedIdx++));
			return null;
		}

		private Ref resolveLoose(Ref l) {
			if (resolvedIdx < resolved.size()) {
				Ref r = resolved.get(resolvedIdx);
				int cmp = RefComparator.compareTo(l, r);
				if (cmp == 0) {
					resolvedIdx++;
					return r;
				} else if (cmp > 0) {
					// WTF, we have a symbolic entry but no match
					// in the loose collection. That's an error.
					throw new IllegalStateException();
				}
			}
			return l;
		}

		private Ent toEntry(Ref p) {
			if (p.getName().startsWith(prefix))
				return new Ent(p);
			packedIdx = packed.size();
			looseIdx = loose.size();
			resolvedIdx = resolved.size();
			return null;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	private class Ent implements Entry<String, Ref> {
		private Ref ref;

		Ent(Ref ref) {
			this.ref = ref;
		}

		@Override
		public String getKey() {
			return toMapKey(ref);
		}

		@Override
		public Ref getValue() {
			return ref;
		}

		@Override
		public Ref setValue(Ref value) {
			Ref prior = put(getKey(), value);
			ref = value;
			return prior;
		}

		@Override
		public int hashCode() {
			return getKey().hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Map.Entry) {
				final Object key = ((Map.Entry) obj).getKey();
				final Object val = ((Map.Entry) obj).getValue();
				if (key instanceof String && val instanceof Ref) {
					final Ref r = (Ref) val;
					if (r.getName().equals(ref.getName())) {
						final ObjectId a = r.getObjectId();
						final ObjectId b = ref.getObjectId();
						if (a != null && b != null
								&& AnyObjectId.isEqual(a, b)) {
							return true;
						}
					}
				}
			}
			return false;
		}

		@Override
		public String toString() {
			return ref.toString();
		}
	}
}