org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexWriter.java

   1 /*
   2  * Copyright (C) 2008, Robin Rosenberg <robin.rosenberg@dewire.com>
   3  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   4  *
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or
   8  * without modification, are permitted provided that the following
   9  * conditions are met:
  10  *
  11  * - Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  *
  14  * - Redistributions in binary form must reproduce the above
  15  *   copyright notice, this list of conditions and the following
  16  *   disclaimer in the documentation and/or other materials provided
  17  *   with the distribution.
  18  *
  19  * - Neither the name of the Git Development Community nor the
  20  *   names of its contributors may be used to endorse or promote
  21  *   products derived from this software without specific prior
  22  *   written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  25  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  26  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  27  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  29  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  34  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  36  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37  */
  38
  39 package org.spearce.jgit.lib;
  40
  41 import java.io.BufferedOutputStream;
  42 import java.io.IOException;
  43 import java.io.OutputStream;
  44 import java.security.DigestOutputStream;
  45 import java.util.List;
  46
  47 import org.spearce.jgit.transport.PackedObjectInfo;
  48 import org.spearce.jgit.util.NB;
  49
  50 /**
  51  * Creates a table of contents to support random access by {@link PackFile}.
  52  * <p>
  53  * Pack index files (the <code>.idx</code> suffix in a pack file pair)
  54  * provides random access to any object in the pack by associating an ObjectId
  55  * to the byte offset within the pack where the object's data can be read.
  56  */
  57 public abstract class PackIndexWriter {
  58         /** Magic constant indicating post-version 1 format. */
  59         protected static final byte[] TOC = { -1, 't', 'O', 'c' };
  60
  61         /**
  62          * Create a new writer for the oldest (most widely understood) format.
  63          * <p>
  64          * This method selects an index format that can accurate describe the
  65          * supplied objects and that will be the most compatible format with older
  66          * Git implementations.
  67          * <p>
  68          * Index version 1 is widely recognized by all Git implementations, but
  69          * index version 2 (and later) is not as well recognized as it was
  70          * introduced more than a year later. Index version 1 can only be used if
  71          * the resulting pack file is under 4 gigabytes in size; packs larger than
  72          * that limit must use index version 2.
  73          *
  74          * @param dst
  75          *            the stream the index data will be written to. If not already
  76          *            buffered it will be automatically wrapped in a buffered
  77          *            stream. Callers are always responsible for closing the stream.
  78          * @param objs
  79          *            the objects the caller needs to store in the index. Entries
  80          *            will be examined until a format can be conclusively selected.
  81          * @return a new writer to output an index file of the requested format to
  82          *         the supplied stream.
  83          * @throws IllegalArgumentException
  84          *             no recognized pack index version can support the supplied
  85          *             objects. This is likely a bug in the implementation.
  86          */
  87         @SuppressWarnings("fallthrough")
  88         public static PackIndexWriter createOldestPossible(final OutputStream dst,
  89                         final List<PackedObjectInfo> objs) {
  90                 int version = 1;
  91                 LOOP: for (final PackedObjectInfo oe : objs) {
  92                         switch (version) {
  93                         case 1:
  94                                 if (PackIndexWriterV1.canStore(oe))
  95                                         continue;
  96                                 version = 2;
  97                         case 2:
  98                                 break LOOP;
  99                         }
 100                 }
 101                 return createVersion(dst, version);
 102         }
 103
 104         /**
 105          * Create a new writer instance for a specific index format version.
 106          *
 107          * @param dst
 108          *            the stream the index data will be written to. If not already
 109          *            buffered it will be automatically wrapped in a buffered
 110          *            stream. Callers are always responsible for closing the stream.
 111          * @param version
 112          *            index format version number required by the caller. Exactly
 113          *            this formatted version will be written.
 114          * @return a new writer to output an index file of the requested format to
 115          *         the supplied stream.
 116          * @throws IllegalArgumentException
 117          *             the version requested is not supported by this
 118          *             implementation.
 119          */
 120         public static PackIndexWriter createVersion(final OutputStream dst,
 121                         final int version) {
 122                 switch (version) {
 123                 case 1:
 124                         return new PackIndexWriterV1(dst);
 125                 default:
 126                         throw new IllegalArgumentException(
 127                                         "Unsupported pack index version " + version);
 128                 }
 129         }
 130
 131         /** The index data stream we are responsible for creating. */
 132         protected final DigestOutputStream out;
 133
 134         /** A temporary buffer for use during IO to {link #out}. */
 135         protected final byte[] tmp;
 136
 137         /** The entries this writer must pack. */
 138         protected List<PackedObjectInfo> entries;
 139
 140         /** SHA-1 checksum for the entire pack data. */
 141         protected byte[] packChecksum;
 142
 143         /**
 144          * Create a new writer instance.
 145          *
 146          * @param dst
 147          *            the stream this instance outputs to. If not already buffered
 148          *            it will be automatically wrapped in a buffered stream.
 149          */
 150         protected PackIndexWriter(final OutputStream dst) {
 151                 out = new DigestOutputStream(dst instanceof BufferedOutputStream ? dst
 152                                 : new BufferedOutputStream(dst), Constants.newMessageDigest());
 153                 tmp = new byte[4 + Constants.OBJECT_ID_LENGTH];
 154         }
 155
 156         /**
 157          * Write all object entries to the index stream.
 158          * <p>
 159          * After writing the stream passed to the factory is flushed but remains
 160          * open. Callers are always responsible for closing the output stream.
 161          *
 162          * @param toStore
 163          *            sorted list of objects to store in the index. The caller must
 164          *            have previously sorted the list using {@link PackedObjectInfo}'s
 165          *            native {@link Comparable} implementation.
 166          * @param packDataChecksum
 167          *            checksum signature of the entire pack data content. This is
 168          *            traditionally the last 20 bytes of the pack file's own stream.
 169          * @throws IOException
 170          *             an error occurred while writing to the output stream, or this
 171          *             index format cannot store the object data supplied.
 172          */
 173         public void write(final List<PackedObjectInfo> toStore,
 174                         final byte[] packDataChecksum) throws IOException {
 175                 entries = toStore;
 176                 packChecksum = packDataChecksum;
 177                 writeImpl();
 178                 out.flush();
 179         }
 180
 181         /**
 182          * Writes the index file to {@link #out}.
 183          * <p>
 184          * Implementations should go something like:
 185          *
 186          * <pre>
 187          * writeFanOutTable();
 188          * for (final PackedObjectInfo po : entries)
 189          *      writeOneEntry(po);
 190          * writeChecksumFooter();
 191          * </pre>
 192          *
 193          * <p>
 194          * Where the logic for <code>writeOneEntry</code> is specific to the index
 195          * format in use. Additional headers/footers may be used if necessary and
 196          * the {@link #entries} collection may be iterated over more than once if
 197          * necessary. Implementors therefore have complete control over the data.
 198          *
 199          * @throws IOException
 200          *             an error occurred while writing to the output stream, or this
 201          *             index format cannot store the object data supplied.
 202          */
 203         protected abstract void writeImpl() throws IOException;
 204
 205         /**
 206          * Output the standard 256 entry first-level fan-out table.
 207          * <p>
 208          * The fan-out table is 4 KB in size, holding 256 32-bit unsigned integer
 209          * counts. Each count represents the number of objects within this index
 210          * whose {@link ObjectId#getFirstByte()} matches the count's position in the
 211          * fan-out table.
 212          *
 213          * @throws IOException
 214          *             an error occurred while writing to the output stream.
 215          */
 216         protected void writeFanOutTable() throws IOException {
 217                 final int[] fanout = new int[256];
 218                 for (final PackedObjectInfo po : entries)
 219                         fanout[po.getFirstByte() & 0xff]++;
 220                 for (int i = 1; i < 256; i++)
 221                         fanout[i] += fanout[i - 1];
 222                 for (final int n : fanout) {
 223                         NB.encodeInt32(tmp, 0, n);
 224                         out.write(tmp, 0, 4);
 225                 }
 226         }
 227
 228         /**
 229          * Output the standard two-checksum index footer.
 230          * <p>
 231          * The standard footer contains two checksums (20 byte SHA-1 values):
 232          * <ol>
 233          * <li>Pack data checksum - taken from the last 20 bytes of the pack file.</li>
 234          * <li>Index data checksum - checksum of all index bytes written, including
 235          * the pack data checksum above.</li>
 236          * </ol>
 237          *
 238          * @throws IOException
 239          *             an error occurred while writing to the output stream.
 240          */
 241         protected void writeChecksumFooter() throws IOException {
 242                 out.write(packChecksum);
 243                 out.on(false);
 244                 out.write(out.getMessageDigest().digest());
 245         }
 246 }