AbbreviatedObjectId.java

  1. /*
  2.  * Copyright (C) 2008-2009, 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.  */

  10. package org.eclipse.jgit.lib;

  11. import java.io.Serializable;
  12. import java.text.MessageFormat;

  13. import org.eclipse.jgit.errors.InvalidObjectIdException;
  14. import org.eclipse.jgit.internal.JGitText;
  15. import org.eclipse.jgit.util.NB;
  16. import org.eclipse.jgit.util.RawParseUtils;

  17. /**
  18.  * A prefix abbreviation of an {@link org.eclipse.jgit.lib.ObjectId}.
  19.  * <p>
  20.  * Sometimes Git produces abbreviated SHA-1 strings, using sufficient leading
  21.  * digits from the ObjectId name to still be unique within the repository the
  22.  * string was generated from. These ids are likely to be unique for a useful
  23.  * period of time, especially if they contain at least 6-10 hex digits.
  24.  * <p>
  25.  * This class converts the hex string into a binary form, to make it more
  26.  * efficient for matching against an object.
  27.  */
  28. public final class AbbreviatedObjectId implements Serializable {
  29.     private static final long serialVersionUID = 1L;

  30.     /**
  31.      * Test a string of characters to verify it is a hex format.
  32.      * <p>
  33.      * If true the string can be parsed with {@link #fromString(String)}.
  34.      *
  35.      * @param id
  36.      *            the string to test.
  37.      * @return true if the string can converted into an AbbreviatedObjectId.
  38.      */
  39.     public static final boolean isId(String id) {
  40.         if (id.length() < 2 || Constants.OBJECT_ID_STRING_LENGTH < id.length())
  41.             return false;
  42.         try {
  43.             for (int i = 0; i < id.length(); i++)
  44.                 RawParseUtils.parseHexInt4((byte) id.charAt(i));
  45.             return true;
  46.         } catch (ArrayIndexOutOfBoundsException e) {
  47.             return false;
  48.         }
  49.     }

  50.     /**
  51.      * Convert an AbbreviatedObjectId from hex characters (US-ASCII).
  52.      *
  53.      * @param buf
  54.      *            the US-ASCII buffer to read from.
  55.      * @param offset
  56.      *            position to read the first character from.
  57.      * @param end
  58.      *            one past the last position to read (<code>end-offset</code> is
  59.      *            the length of the string).
  60.      * @return the converted object id.
  61.      */
  62.     public static final AbbreviatedObjectId fromString(final byte[] buf,
  63.             final int offset, final int end) {
  64.         if (end - offset > Constants.OBJECT_ID_STRING_LENGTH)
  65.             throw new IllegalArgumentException(MessageFormat.format(
  66.                     JGitText.get().invalidIdLength,
  67.                     Integer.valueOf(end - offset),
  68.                     Integer.valueOf(Constants.OBJECT_ID_STRING_LENGTH)));
  69.         return fromHexString(buf, offset, end);
  70.     }

  71.     /**
  72.      * Convert an AbbreviatedObjectId from an
  73.      * {@link org.eclipse.jgit.lib.AnyObjectId}.
  74.      * <p>
  75.      * This method copies over all bits of the Id, and is therefore complete
  76.      * (see {@link #isComplete()}).
  77.      *
  78.      * @param id
  79.      *            the {@link org.eclipse.jgit.lib.ObjectId} to convert from.
  80.      * @return the converted object id.
  81.      */
  82.     public static final AbbreviatedObjectId fromObjectId(AnyObjectId id) {
  83.         return new AbbreviatedObjectId(Constants.OBJECT_ID_STRING_LENGTH,
  84.                 id.w1, id.w2, id.w3, id.w4, id.w5);
  85.     }

  86.     /**
  87.      * Convert an AbbreviatedObjectId from hex characters.
  88.      *
  89.      * @param str
  90.      *            the string to read from. Must be &lt;= 40 characters.
  91.      * @return the converted object id.
  92.      */
  93.     public static final AbbreviatedObjectId fromString(String str) {
  94.         if (str.length() > Constants.OBJECT_ID_STRING_LENGTH)
  95.             throw new IllegalArgumentException(MessageFormat.format(JGitText.get().invalidId, str));
  96.         final byte[] b = Constants.encodeASCII(str);
  97.         return fromHexString(b, 0, b.length);
  98.     }

  99.     private static final AbbreviatedObjectId fromHexString(final byte[] bs,
  100.             int ptr, final int end) {
  101.         try {
  102.             final int a = hexUInt32(bs, ptr, end);
  103.             final int b = hexUInt32(bs, ptr + 8, end);
  104.             final int c = hexUInt32(bs, ptr + 16, end);
  105.             final int d = hexUInt32(bs, ptr + 24, end);
  106.             final int e = hexUInt32(bs, ptr + 32, end);
  107.             return new AbbreviatedObjectId(end - ptr, a, b, c, d, e);
  108.         } catch (ArrayIndexOutOfBoundsException e) {
  109.             InvalidObjectIdException e1 = new InvalidObjectIdException(bs, ptr,
  110.                     end - ptr);
  111.             e1.initCause(e);
  112.             throw e1;
  113.         }
  114.     }

  115.     private static final int hexUInt32(final byte[] bs, int p, final int end) {
  116.         if (8 <= end - p)
  117.             return RawParseUtils.parseHexInt32(bs, p);

  118.         int r = 0, n = 0;
  119.         while (n < 8 && p < end) {
  120.             r <<= 4;
  121.             r |= RawParseUtils.parseHexInt4(bs[p++]);
  122.             n++;
  123.         }
  124.         return r << ((8 - n) * 4);
  125.     }

  126.     static int mask(int nibbles, int word, int v) {
  127.         final int b = (word - 1) * 8;
  128.         if (b + 8 <= nibbles) {
  129.             // We have all of the bits required for this word.
  130.             //
  131.             return v;
  132.         }

  133.         if (nibbles <= b) {
  134.             // We have none of the bits required for this word.
  135.             //
  136.             return 0;
  137.         }

  138.         final int s = 32 - (nibbles - b) * 4;
  139.         return (v >>> s) << s;
  140.     }

  141.     /** Number of half-bytes used by this id. */
  142.     final int nibbles;

  143.     final int w1;

  144.     final int w2;

  145.     final int w3;

  146.     final int w4;

  147.     final int w5;

  148.     AbbreviatedObjectId(final int n, final int new_1, final int new_2,
  149.             final int new_3, final int new_4, final int new_5) {
  150.         nibbles = n;
  151.         w1 = new_1;
  152.         w2 = new_2;
  153.         w3 = new_3;
  154.         w4 = new_4;
  155.         w5 = new_5;
  156.     }

  157.     /**
  158.      * Get number of hex digits appearing in this id.
  159.      *
  160.      * @return number of hex digits appearing in this id.
  161.      */
  162.     public int length() {
  163.         return nibbles;
  164.     }

  165.     /**
  166.      * Whether this ObjectId is actually a complete id.
  167.      *
  168.      * @return true if this ObjectId is actually a complete id.
  169.      */
  170.     public boolean isComplete() {
  171.         return length() == Constants.OBJECT_ID_STRING_LENGTH;
  172.     }

  173.     /**
  174.      * A complete ObjectId; null if {@link #isComplete()} is false
  175.      *
  176.      * @return a complete ObjectId; null if {@link #isComplete()} is false
  177.      */
  178.     public ObjectId toObjectId() {
  179.         return isComplete() ? new ObjectId(w1, w2, w3, w4, w5) : null;
  180.     }

  181.     /**
  182.      * Compares this abbreviation to a full object id.
  183.      *
  184.      * @param other
  185.      *            the other object id.
  186.      * @return &lt;0 if this abbreviation names an object that is less than
  187.      *         <code>other</code>; 0 if this abbreviation exactly matches the
  188.      *         first {@link #length()} digits of <code>other.name()</code>;
  189.      *         &gt;0 if this abbreviation names an object that is after
  190.      *         <code>other</code>.
  191.      */
  192.     public final int prefixCompare(AnyObjectId other) {
  193.         int cmp;

  194.         cmp = NB.compareUInt32(w1, mask(1, other.w1));
  195.         if (cmp != 0)
  196.             return cmp;

  197.         cmp = NB.compareUInt32(w2, mask(2, other.w2));
  198.         if (cmp != 0)
  199.             return cmp;

  200.         cmp = NB.compareUInt32(w3, mask(3, other.w3));
  201.         if (cmp != 0)
  202.             return cmp;

  203.         cmp = NB.compareUInt32(w4, mask(4, other.w4));
  204.         if (cmp != 0)
  205.             return cmp;

  206.         return NB.compareUInt32(w5, mask(5, other.w5));
  207.     }

  208.     /**
  209.      * Compare this abbreviation to a network-byte-order ObjectId.
  210.      *
  211.      * @param bs
  212.      *            array containing the other ObjectId in network byte order.
  213.      * @param p
  214.      *            position within {@code bs} to start the compare at. At least
  215.      *            20 bytes, starting at this position are required.
  216.      * @return &lt;0 if this abbreviation names an object that is less than
  217.      *         <code>other</code>; 0 if this abbreviation exactly matches the
  218.      *         first {@link #length()} digits of <code>other.name()</code>;
  219.      *         &gt;0 if this abbreviation names an object that is after
  220.      *         <code>other</code>.
  221.      */
  222.     public final int prefixCompare(byte[] bs, int p) {
  223.         int cmp;

  224.         cmp = NB.compareUInt32(w1, mask(1, NB.decodeInt32(bs, p)));
  225.         if (cmp != 0)
  226.             return cmp;

  227.         cmp = NB.compareUInt32(w2, mask(2, NB.decodeInt32(bs, p + 4)));
  228.         if (cmp != 0)
  229.             return cmp;

  230.         cmp = NB.compareUInt32(w3, mask(3, NB.decodeInt32(bs, p + 8)));
  231.         if (cmp != 0)
  232.             return cmp;

  233.         cmp = NB.compareUInt32(w4, mask(4, NB.decodeInt32(bs, p + 12)));
  234.         if (cmp != 0)
  235.             return cmp;

  236.         return NB.compareUInt32(w5, mask(5, NB.decodeInt32(bs, p + 16)));
  237.     }

  238.     /**
  239.      * Compare this abbreviation to a network-byte-order ObjectId.
  240.      *
  241.      * @param bs
  242.      *            array containing the other ObjectId in network byte order.
  243.      * @param p
  244.      *            position within {@code bs} to start the compare at. At least 5
  245.      *            ints, starting at this position are required.
  246.      * @return &lt;0 if this abbreviation names an object that is less than
  247.      *         <code>other</code>; 0 if this abbreviation exactly matches the
  248.      *         first {@link #length()} digits of <code>other.name()</code>;
  249.      *         &gt;0 if this abbreviation names an object that is after
  250.      *         <code>other</code>.
  251.      */
  252.     public final int prefixCompare(int[] bs, int p) {
  253.         int cmp;

  254.         cmp = NB.compareUInt32(w1, mask(1, bs[p]));
  255.         if (cmp != 0)
  256.             return cmp;

  257.         cmp = NB.compareUInt32(w2, mask(2, bs[p + 1]));
  258.         if (cmp != 0)
  259.             return cmp;

  260.         cmp = NB.compareUInt32(w3, mask(3, bs[p + 2]));
  261.         if (cmp != 0)
  262.             return cmp;

  263.         cmp = NB.compareUInt32(w4, mask(4, bs[p + 3]));
  264.         if (cmp != 0)
  265.             return cmp;

  266.         return NB.compareUInt32(w5, mask(5, bs[p + 4]));
  267.     }

  268.     /**
  269.      * Get value for a fan-out style map, only valid of length &gt;= 2.
  270.      *
  271.      * @return value for a fan-out style map, only valid of length &gt;= 2.
  272.      */
  273.     public final int getFirstByte() {
  274.         return w1 >>> 24;
  275.     }

  276.     private int mask(int word, int v) {
  277.         return mask(nibbles, word, v);
  278.     }

  279.     /** {@inheritDoc} */
  280.     @Override
  281.     public int hashCode() {
  282.         return w1;
  283.     }

  284.     /** {@inheritDoc} */
  285.     @Override
  286.     public boolean equals(Object o) {
  287.         if (o instanceof AbbreviatedObjectId) {
  288.             final AbbreviatedObjectId b = (AbbreviatedObjectId) o;
  289.             return nibbles == b.nibbles && w1 == b.w1 && w2 == b.w2
  290.                     && w3 == b.w3 && w4 == b.w4 && w5 == b.w5;
  291.         }
  292.         return false;
  293.     }

  294.     /**
  295.      * Get string form of the abbreviation, in lower case hexadecimal.
  296.      *
  297.      * @return string form of the abbreviation, in lower case hexadecimal.
  298.      */
  299.     public final String name() {
  300.         final char[] b = new char[Constants.OBJECT_ID_STRING_LENGTH];

  301.         AnyObjectId.formatHexChar(b, 0, w1);
  302.         if (nibbles <= 8)
  303.             return new String(b, 0, nibbles);

  304.         AnyObjectId.formatHexChar(b, 8, w2);
  305.         if (nibbles <= 16)
  306.             return new String(b, 0, nibbles);

  307.         AnyObjectId.formatHexChar(b, 16, w3);
  308.         if (nibbles <= 24)
  309.             return new String(b, 0, nibbles);

  310.         AnyObjectId.formatHexChar(b, 24, w4);
  311.         if (nibbles <= 32)
  312.             return new String(b, 0, nibbles);

  313.         AnyObjectId.formatHexChar(b, 32, w5);
  314.         return new String(b, 0, nibbles);
  315.     }

  316.     /** {@inheritDoc} */
  317.     @SuppressWarnings("nls")
  318.     @Override
  319.     public String toString() {
  320.         return "AbbreviatedObjectId[" + name() + "]"; //$NON-NLS-1$
  321.     }
  322. }