| /* |
| * 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<Entry<String, Ref>>() { |
| @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(); |
| } |
| } |
| } |