MergedReftable.java

  1. /*
  2.  * Copyright (C) 2017, Google Inc. and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  11. package org.eclipse.jgit.internal.storage.reftable;

  13. import java.io.IOException;
  14. import java.util.ArrayList;
  15. import java.util.List;
  16. import java.util.PriorityQueue;

  18. import org.eclipse.jgit.lib.AnyObjectId;
  19. import org.eclipse.jgit.lib.Ref;
  20. import org.eclipse.jgit.lib.ReflogEntry;

  22. /**
  23.  * Merges multiple reference tables together.
  24.  * <p>
  25.  * A {@link org.eclipse.jgit.internal.storage.reftable.MergedReftable}
  26.  * merge-joins multiple
  27.  * {@link org.eclipse.jgit.internal.storage.reftable.ReftableReader} on the fly.
  28.  * Tables higher/later in the stack shadow lower/earlier tables, hiding
  29.  * references that been updated/replaced.
  30.  * <p>
  31.  * By default deleted references are skipped and not returned to the caller.
  32.  * {@link #setIncludeDeletes(boolean)} can be used to modify this behavior if
  33.  * the caller needs to preserve deletions during partial compaction.
  34.  * <p>
  35.  * A {@code MergedReftable} is not thread-safe.
  36.  */
  37. public class MergedReftable extends Reftable {
  38.     private final ReftableReader[] tables;

  40.     /**
  41.      * Initialize a merged table reader.
  42.      * <p>
  43.      *
  44.      * @param tableStack
  45.      *            stack of tables to read from. The base of the stack is at
  46.      *            index 0, the most recent should be at the top of the stack at
  47.      *            {@code tableStack.size() - 1}. The top of the stack (higher
  48.      *            index) shadows the base of the stack (lower index).
  49.      */
  50.     public MergedReftable(List<ReftableReader> tableStack) {
  51.         tables = tableStack.toArray(new ReftableReader[0]);

  53.         // Tables must expose deletes to this instance to correctly
  54.         // shadow references from lower tables.
  55.         for (ReftableReader t : tables) {
  56.             t.setIncludeDeletes(true);
  57.         }
  58.     }

  60.     /**
  61.      * {@inheritDoc}
  62.      */
  63.     @Override
  64.     public long maxUpdateIndex() throws IOException {
  65.         if (tables.length == 0) {
  66.             return 0;
  67.         }
  68.         long maxUpdateIndex = tables[tables.length - 1].maxUpdateIndex();
  69.         for (int i = tables.length - 2; i >= 0; i--) {
  70.             if (maxUpdateIndex < tables[i].maxUpdateIndex()) {
  71.                 maxUpdateIndex = tables[i].maxUpdateIndex();
  72.             }
  73.         }
  74.         return maxUpdateIndex;
  75.     }

  77.     /**
  78.      * {@inheritDoc}
  79.      */
  80.     @Override
  81.     public long minUpdateIndex() throws IOException {
  82.         if (tables.length == 0) {
  83.             return 0;
  84.         }
  85.         long minUpdateIndex = tables[0].minUpdateIndex();
  86.         for (int i = 1; i < tables.length; i++) {
  87.             if (tables[i].minUpdateIndex() < minUpdateIndex) {
  88.                 minUpdateIndex = tables[i].minUpdateIndex();
  89.             }
  90.         }
  91.         return minUpdateIndex;
  92.     }

  94.     /** {@inheritDoc} */
  95.     @Override
  96.     public boolean hasObjectMap() throws IOException {
  97.         boolean has = true;
  98.         for (int i = 0; has && i < tables.length; i++) {
  99.             has = has && tables[i].hasObjectMap();
  100.         }
  101.         return has;
  102.     }

  104.     /** {@inheritDoc} */
  105.     @Override
  106.     public RefCursor allRefs() throws IOException {
  107.         MergedRefCursor m = new MergedRefCursor();
  108.         for (int i = 0; i < tables.length; i++) {
  109.             m.add(new RefQueueEntry(tables[i].allRefs(), i));
  110.         }
  111.         return m;
  112.     }

  114.     /** {@inheritDoc} */
  115.     @Override
  116.     public RefCursor seekRef(String name) throws IOException {
  117.         MergedRefCursor m = new MergedRefCursor();
  118.         for (int i = 0; i < tables.length; i++) {
  119.             m.add(new RefQueueEntry(tables[i].seekRef(name), i));
  120.         }
  121.         return m;
  122.     }

  124.     /** {@inheritDoc} */
  125.     @Override
  126.     public RefCursor seekRefsWithPrefix(String prefix) throws IOException {
  127.         MergedRefCursor m = new MergedRefCursor();
  128.         for (int i = 0; i < tables.length; i++) {
  129.             m.add(new RefQueueEntry(tables[i].seekRefsWithPrefix(prefix), i));
  130.         }
  131.         return m;
  132.     }

  134.     /** {@inheritDoc} */
  135.     @Override
  136.     public RefCursor byObjectId(AnyObjectId name) throws IOException {
  137.         MergedRefCursor m = new FilteringMergedRefCursor(name);
  138.         for (int i = 0; i < tables.length; i++) {
  139.             m.add(new RefQueueEntry(tables[i].byObjectId(name), i));
  140.         }
  141.         return m;
  142.     }

  144.     /** {@inheritDoc} */
  145.     @Override
  146.     public LogCursor allLogs() throws IOException {
  147.         MergedLogCursor m = new MergedLogCursor();
  148.         for (int i = 0; i < tables.length; i++) {
  149.             m.add(new LogQueueEntry(tables[i].allLogs(), i));
  150.         }
  151.         return m;
  152.     }

  154.     /** {@inheritDoc} */
  155.     @Override
  156.     public LogCursor seekLog(String refName, long updateIdx)
  157.             throws IOException {
  158.         MergedLogCursor m = new MergedLogCursor();
  159.         for (int i = 0; i < tables.length; i++) {
  160.             m.add(new LogQueueEntry(tables[i].seekLog(refName, updateIdx), i));
  161.         }
  162.         return m;
  163.     }

  165.     int queueSize() {
  166.         return Math.max(1, tables.length);
  167.     }

  169.     private class MergedRefCursor extends RefCursor {
  170.         private final PriorityQueue<RefQueueEntry> queue;
  171.         private RefQueueEntry head;
  172.         private Ref ref;

  174.         MergedRefCursor() {
  175.             queue = new PriorityQueue<>(queueSize(), RefQueueEntry::compare);
  176.         }

  178.         void add(RefQueueEntry t) throws IOException {
  179.             // Common case is many iterations over the same RefQueueEntry
  180.             // for the bottom of the stack (scanning all refs). Its almost
  181.             // always less than the top of the queue. Avoid the queue's
  182.             // O(log N) insertion and removal costs for this common case.
  183.             if (!t.rc.next()) {
  184.                 t.rc.close();
  185.             } else if (head == null) {
  186.                 RefQueueEntry p = queue.peek();
  187.                 if (p == null || RefQueueEntry.compare(t, p) < 0) {
  188.                     head = t;
  189.                 } else {
  190.                     head = queue.poll();
  191.                     queue.add(t);
  192.                 }
  193.             } else if (RefQueueEntry.compare(t, head) > 0) {
  194.                 queue.add(t);
  195.             } else {
  196.                 queue.add(head);
  197.                 head = t;
  198.             }
  199.         }

  201.         @Override
  202.         public boolean next() throws IOException {
  203.             for (;;) {
  204.                 RefQueueEntry t = poll();
  205.                 if (t == null) {
  206.                     return false;
  207.                 }

  209.                 ref = t.rc.getRef();
  210.                 boolean include = includeDeletes || !t.rc.wasDeleted();
  211.                 add(t);
  212.                 skipShadowedRefs(ref.getName());
  213.                 if (include) {
  214.                     return true;
  215.                 }
  216.             }
  217.         }

  219.         @Override
  220.         public void seekPastPrefix(String prefixName) throws IOException {
  221.             List<RefQueueEntry> entriesToAdd = new ArrayList<>();
  222.             entriesToAdd.addAll(queue);
  223.             if (head != null) {
  224.                 entriesToAdd.add(head);
  225.             }

  227.             head = null;
  228.             queue.clear();

  230.             for(RefQueueEntry entry : entriesToAdd){
  231.                 entry.rc.seekPastPrefix(prefixName);
  232.                 add(entry);
  233.             }
  234.         }

  236.         private RefQueueEntry poll() {
  237.             RefQueueEntry e = head;
  238.             if (e != null) {
  239.                 head = null;
  240.                 return e;
  241.             }
  242.             return queue.poll();
  243.         }

  245.         private void skipShadowedRefs(String name) throws IOException {
  246.             for (;;) {
  247.                 RefQueueEntry t = head != null ? head : queue.peek();
  248.                 if (t != null && name.equals(t.name())) {
  249.                     add(poll());
  250.                 } else {
  251.                     break;
  252.                 }
  253.             }
  254.         }

  256.         @Override
  257.         public Ref getRef() {
  258.             return ref;
  259.         }

  261.         @Override
  262.         public void close() {
  263.             if (head != null) {
  264.                 head.rc.close();
  265.                 head = null;
  266.             }
  267.             while (!queue.isEmpty()) {
  268.                 queue.remove().rc.close();
  269.             }
  270.         }
  271.     }

  273.     private class FilteringMergedRefCursor extends MergedRefCursor {
  274.         final AnyObjectId filterId;
  275.         Ref filteredRef;

  277.         FilteringMergedRefCursor(AnyObjectId id) {
  278.             filterId = id;
  279.             filteredRef = null;
  280.         }

  282.         @Override
  283.         public Ref getRef() {
  284.             return filteredRef;
  285.         }

  287.         @Override
  288.         public boolean next() throws IOException {
  289.             for (;;) {
  290.                 boolean ok = super.next();
  291.                 if (!ok) {
  292.                     return false;
  293.                 }

  295.                 String name = super.getRef().getName();

  297.                 try (RefCursor c = seekRef(name)) {
  298.                     if (c.next()) {
  299.                         if (filterId.equals(c.getRef().getObjectId())) {
  300.                             filteredRef = c.getRef();
  301.                             return true;
  302.                         }
  303.                     }
  304.                 }
  305.             }
  306.         }
  307.     }

  309.     private static class RefQueueEntry {
  310.         static int compare(RefQueueEntry a, RefQueueEntry b) {
  311.             int cmp = a.name().compareTo(b.name());
  312.             if (cmp == 0) {
  313.                 // higher updateIndex shadows lower updateIndex.
  314.                 cmp = Long.signum(b.updateIndex() - a.updateIndex());
  315.             }
  316.             if (cmp == 0) {
  317.                 // higher index shadows lower index, so higher index first.
  318.                 cmp = b.stackIdx - a.stackIdx;
  319.             }
  320.             return cmp;
  321.         }

  323.         final RefCursor rc;
  324.         final int stackIdx;

  326.         RefQueueEntry(RefCursor rc, int stackIdx) {
  327.             this.rc = rc;
  328.             this.stackIdx = stackIdx;
  329.         }

  331.         String name() {
  332.             return rc.getRef().getName();
  333.         }

  335.         long updateIndex() {
  336.             return rc.getRef().getUpdateIndex();
  337.         }
  338.     }

  340.     private class MergedLogCursor extends LogCursor {
  341.         private final PriorityQueue<LogQueueEntry> queue;
  342.         private String refName;
  343.         private long updateIndex;
  344.         private ReflogEntry entry;

  346.         MergedLogCursor() {
  347.             queue = new PriorityQueue<>(queueSize(), LogQueueEntry::compare);
  348.         }

  350.         void add(LogQueueEntry t) throws IOException {
  351.             if (t.lc.next()) {
  352.                 queue.add(t);
  353.             } else {
  354.                 t.lc.close();
  355.             }
  356.         }

  358.         @Override
  359.         public boolean next() throws IOException {
  360.             for (;;) {
  361.                 LogQueueEntry t = queue.poll();
  362.                 if (t == null) {
  363.                     return false;
  364.                 }

  366.                 refName = t.lc.getRefName();
  367.                 updateIndex = t.lc.getUpdateIndex();
  368.                 entry = t.lc.getReflogEntry();
  369.                 boolean include = includeDeletes || entry != null;
  370.                 skipShadowed(refName, updateIndex);
  371.                 add(t);
  372.                 if (include) {
  373.                     return true;
  374.                 }
  375.             }
  376.         }

  378.         private void skipShadowed(String name, long index) throws IOException {
  379.             for (;;) {
  380.                 LogQueueEntry t = queue.peek();
  381.                 if (t != null && name.equals(t.name()) && index == t.index()) {
  382.                     add(queue.remove());
  383.                 } else {
  384.                     break;
  385.                 }
  386.             }
  387.         }

  389.         @Override
  390.         public String getRefName() {
  391.             return refName;
  392.         }

  394.         @Override
  395.         public long getUpdateIndex() {
  396.             return updateIndex;
  397.         }

  399.         @Override
  400.         public ReflogEntry getReflogEntry() {
  401.             return entry;
  402.         }

  404.         @Override
  405.         public void close() {
  406.             while (!queue.isEmpty()) {
  407.                 queue.remove().lc.close();
  408.             }
  409.         }
  410.     }

  412.     private static class LogQueueEntry {
  413.         static int compare(LogQueueEntry a, LogQueueEntry b) {
  414.             int cmp = a.name().compareTo(b.name());
  415.             if (cmp == 0) {
  416.                 // higher update index sorts first.
  417.                 cmp = Long.signum(b.index() - a.index());
  418.             }
  419.             if (cmp == 0) {
  420.                 // higher index comes first.
  421.                 cmp = b.stackIdx - a.stackIdx;
  422.             }
  423.             return cmp;
  424.         }

  426.         final LogCursor lc;
  427.         final int stackIdx;

  429.         LogQueueEntry(LogCursor lc, int stackIdx) {
  430.             this.lc = lc;
  431.             this.stackIdx = stackIdx;
  432.         }

  434.         String name() {
  435.             return lc.getRefName();
  436.         }

  438.         long index() {
  439.             return lc.getUpdateIndex();
  440.         }
  441.     }
  442. }
Created with JaCoCo 0.8.6.202009150832