CanonicalTreeParser.java

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

  12. package org.eclipse.jgit.treewalk;

  14. import static org.eclipse.jgit.lib.Constants.DOT_GIT_ATTRIBUTES;
  15. import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
  16. import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
  17. import static org.eclipse.jgit.lib.Constants.OBJ_TREE;
  18. import static org.eclipse.jgit.lib.Constants.TYPE_TREE;
  19. import static org.eclipse.jgit.lib.Constants.encode;

  21. import java.io.IOException;
  22. import java.io.InputStream;
  23. import java.util.Arrays;
  24. import java.util.Collections;

  26. import org.eclipse.jgit.attributes.AttributesNode;
  27. import org.eclipse.jgit.attributes.AttributesRule;
  28. import org.eclipse.jgit.errors.IncorrectObjectTypeException;
  29. import org.eclipse.jgit.errors.MissingObjectException;
  30. import org.eclipse.jgit.lib.AnyObjectId;
  31. import org.eclipse.jgit.lib.FileMode;
  32. import org.eclipse.jgit.lib.MutableObjectId;
  33. import org.eclipse.jgit.lib.ObjectId;
  34. import org.eclipse.jgit.lib.ObjectReader;

  36. /**
  37.  * Parses raw Git trees from the canonical semi-text/semi-binary format.
  38.  */
  39. public class CanonicalTreeParser extends AbstractTreeIterator {
  40.     private static final byte[] EMPTY = {};
  41.     private static final byte[] ATTRS = encode(DOT_GIT_ATTRIBUTES);

  43.     private byte[] raw;

  45.     /** First offset within {@link #raw} of the prior entry. */
  46.     private int prevPtr;

  48.     /** First offset within {@link #raw} of the current entry's data. */
  49.     private int currPtr;

  51.     /** Offset one past the current entry (first byte of next entry). */
  52.     private int nextPtr;

  54.     /**
  55.      * Create a new parser.
  56.      */
  57.     public CanonicalTreeParser() {
  58.         reset(EMPTY);
  59.     }

  61.     /**
  62.      * Create a new parser for a tree appearing in a subset of a repository.
  63.      *
  64.      * @param prefix
  65.      *            position of this iterator in the repository tree. The value
  66.      *            may be null or the empty array to indicate the prefix is the
  67.      *            root of the repository. A trailing slash ('/') is
  68.      *            automatically appended if the prefix does not end in '/'.
  69.      * @param reader
  70.      *            reader to load the tree data from.
  71.      * @param treeId
  72.      *            identity of the tree being parsed; used only in exception
  73.      *            messages if data corruption is found.
  74.      * @throws MissingObjectException
  75.      *             the object supplied is not available from the repository.
  76.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  77.      *             the object supplied as an argument is not actually a tree and
  78.      *             cannot be parsed as though it were a tree.
  79.      * @throws java.io.IOException
  80.      *             a loose object or pack file could not be read.
  81.      */
  82.     public CanonicalTreeParser(final byte[] prefix, final ObjectReader reader,
  83.             final AnyObjectId treeId) throws IncorrectObjectTypeException,
  84.             IOException {
  85.         super(prefix);
  86.         reset(reader, treeId);
  87.     }

  89.     private CanonicalTreeParser(CanonicalTreeParser p) {
  90.         super(p);
  91.     }

  93.     /**
  94.      * Get the parent of this tree parser.
  95.      *
  96.      * @return the parent of this tree parser.
  97.      * @deprecated internal use only
  98.      */
  99.     @Deprecated
  100.     public CanonicalTreeParser getParent() {
  101.         return (CanonicalTreeParser) parent;
  102.     }

  104.     /**
  105.      * Reset this parser to walk through the given tree data.
  106.      *
  107.      * @param treeData
  108.      *            the raw tree content.
  109.      */
  110.     public void reset(byte[] treeData) {
  111.         attributesNode = null;
  112.         raw = treeData;
  113.         prevPtr = -1;
  114.         currPtr = 0;
  115.         if (eof())
  116.             nextPtr = 0;
  117.         else
  118.             parseEntry();
  119.     }

  121.     /**
  122.      * Reset this parser to walk through the given tree.
  123.      *
  124.      * @param reader
  125.      *            reader to use during repository access.
  126.      * @param id
  127.      *            identity of the tree being parsed; used only in exception
  128.      *            messages if data corruption is found.
  129.      * @return the root level parser.
  130.      * @throws MissingObjectException
  131.      *             the object supplied is not available from the repository.
  132.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  133.      *             the object supplied as an argument is not actually a tree and
  134.      *             cannot be parsed as though it were a tree.
  135.      * @throws java.io.IOException
  136.      *             a loose object or pack file could not be read.
  137.      */
  138.     public CanonicalTreeParser resetRoot(final ObjectReader reader,
  139.             final AnyObjectId id) throws IncorrectObjectTypeException,
  140.             IOException {
  141.         CanonicalTreeParser p = this;
  142.         while (p.parent != null)
  143.             p = (CanonicalTreeParser) p.parent;
  144.         p.reset(reader, id);
  145.         return p;
  146.     }

  148.     /**
  149.      * Get this iterator, or its parent, if the tree is at eof.
  150.      *
  151.      * @return this iterator, or its parent, if the tree is at eof.
  152.      */
  153.     public CanonicalTreeParser next() {
  154.         CanonicalTreeParser p = this;
  155.         for (;;) {
  156.             if (p.nextPtr == p.raw.length) {
  157.                 // This parser has reached EOF, return to the parent.
  158.                 if (p.parent == null) {
  159.                     p.currPtr = p.nextPtr;
  160.                     return p;
  161.                 }
  162.                 p = (CanonicalTreeParser) p.parent;
  163.                 continue;
  164.             }

  166.             p.prevPtr = p.currPtr;
  167.             p.currPtr = p.nextPtr;
  168.             p.parseEntry();
  169.             return p;
  170.         }
  171.     }

  173.     /**
  174.      * Reset this parser to walk through the given tree.
  175.      *
  176.      * @param reader
  177.      *            reader to use during repository access.
  178.      * @param id
  179.      *            identity of the tree being parsed; used only in exception
  180.      *            messages if data corruption is found.
  181.      * @throws MissingObjectException
  182.      *             the object supplied is not available from the repository.
  183.      * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
  184.      *             the object supplied as an argument is not actually a tree and
  185.      *             cannot be parsed as though it were a tree.
  186.      * @throws java.io.IOException
  187.      *             a loose object or pack file could not be read.
  188.      */
  189.     public void reset(ObjectReader reader, AnyObjectId id)
  190.             throws IncorrectObjectTypeException, IOException {
  191.         reset(reader.open(id, OBJ_TREE).getCachedBytes());
  192.     }

  194.     /** {@inheritDoc} */
  195.     @Override
  196.     public CanonicalTreeParser createSubtreeIterator(final ObjectReader reader,
  197.             final MutableObjectId idBuffer)
  198.             throws IncorrectObjectTypeException, IOException {
  199.         idBuffer.fromRaw(idBuffer(), idOffset());
  200.         if (!FileMode.TREE.equals(mode)) {
  201.             final ObjectId me = idBuffer.toObjectId();
  202.             throw new IncorrectObjectTypeException(me, TYPE_TREE);
  203.         }
  204.         return createSubtreeIterator0(reader, idBuffer);
  205.     }

  207.     /**
  208.      * Back door to quickly create a subtree iterator for any subtree.
  209.      * <p>
  210.      * Don't use this unless you are ObjectWalk. The method is meant to be
  211.      * called only once the current entry has been identified as a tree and its
  212.      * identity has been converted into an ObjectId.
  213.      *
  214.      * @param reader
  215.      *            reader to load the tree data from.
  216.      * @param id
  217.      *            ObjectId of the tree to open.
  218.      * @return a new parser that walks over the current subtree.
  219.      * @throws java.io.IOException
  220.      *             a loose object or pack file could not be read.
  221.      */
  222.     public final CanonicalTreeParser createSubtreeIterator0(
  223.             final ObjectReader reader, final AnyObjectId id)
  224.             throws IOException {
  225.         final CanonicalTreeParser p = new CanonicalTreeParser(this);
  226.         p.reset(reader, id);
  227.         return p;
  228.     }

  230.     /** {@inheritDoc} */
  231.     @Override
  232.     public CanonicalTreeParser createSubtreeIterator(ObjectReader reader)
  233.             throws IncorrectObjectTypeException, IOException {
  234.         return createSubtreeIterator(reader, new MutableObjectId());
  235.     }

  237.     /** {@inheritDoc} */
  238.     @Override
  239.     public boolean hasId() {
  240.         return true;
  241.     }

  243.     /** {@inheritDoc} */
  244.     @Override
  245.     public byte[] idBuffer() {
  246.         return raw;
  247.     }

  249.     /** {@inheritDoc} */
  250.     @Override
  251.     public int idOffset() {
  252.         return nextPtr - OBJECT_ID_LENGTH;
  253.     }

  255.     /** {@inheritDoc} */
  256.     @Override
  257.     public void reset() {
  258.         if (!first())
  259.             reset(raw);
  260.     }

  262.     /** {@inheritDoc} */
  263.     @Override
  264.     public boolean first() {
  265.         return currPtr == 0;
  266.     }

  268.     /** {@inheritDoc} */
  269.     @Override
  270.     public boolean eof() {
  271.         return currPtr == raw.length;
  272.     }

  274.     /** {@inheritDoc} */
  275.     @Override
  276.     public void next(int delta) {
  277.         if (delta == 1) {
  278.             // Moving forward one is the most common case.
  279.             //
  280.             prevPtr = currPtr;
  281.             currPtr = nextPtr;
  282.             if (!eof())
  283.                 parseEntry();
  284.             return;
  285.         }

  287.         // Fast skip over records, then parse the last one.
  288.         //
  289.         final int end = raw.length;
  290.         int ptr = nextPtr;
  291.         while (--delta > 0 && ptr != end) {
  292.             prevPtr = ptr;
  293.             while (raw[ptr] != 0)
  294.                 ptr++;
  295.             ptr += OBJECT_ID_LENGTH + 1;
  296.         }
  297.         if (delta != 0)
  298.             throw new ArrayIndexOutOfBoundsException(delta);
  299.         currPtr = ptr;
  300.         if (!eof())
  301.             parseEntry();
  302.     }

  304.     /** {@inheritDoc} */
  305.     @Override
  306.     public void back(int delta) {
  307.         if (delta == 1 && 0 <= prevPtr) {
  308.             // Moving back one is common in NameTreeWalk, as the average tree
  309.             // won't have D/F type conflicts to study.
  310.             //
  311.             currPtr = prevPtr;
  312.             prevPtr = -1;
  313.             if (!eof())
  314.                 parseEntry();
  315.             return;
  316.         } else if (delta <= 0)
  317.             throw new ArrayIndexOutOfBoundsException(delta);

  319.         // Fast skip through the records, from the beginning of the tree.
  320.         // There is no reliable way to read the tree backwards, so we must
  321.         // parse all over again from the beginning. We hold the last "delta"
  322.         // positions in a buffer, so we can find the correct position later.
  323.         //
  324.         final int[] trace = new int[delta + 1];
  325.         Arrays.fill(trace, -1);
  326.         int ptr = 0;
  327.         while (ptr != currPtr) {
  328.             System.arraycopy(trace, 1, trace, 0, delta);
  329.             trace[delta] = ptr;
  330.             while (raw[ptr] != 0)
  331.                 ptr++;
  332.             ptr += OBJECT_ID_LENGTH + 1;
  333.         }
  334.         if (trace[1] == -1)
  335.             throw new ArrayIndexOutOfBoundsException(delta);
  336.         prevPtr = trace[0];
  337.         currPtr = trace[1];
  338.         parseEntry();
  339.     }

  341.     private void parseEntry() {
  342.         int ptr = currPtr;
  343.         byte c = raw[ptr++];
  344.         int tmp = c - '0';
  345.         for (;;) {
  346.             c = raw[ptr++];
  347.             if (' ' == c)
  348.                 break;
  349.             tmp <<= 3;
  350.             tmp += c - '0';
  351.         }
  352.         mode = tmp;

  354.         tmp = pathOffset;
  355.         for (;; tmp++) {
  356.             c = raw[ptr++];
  357.             if (c == 0) {
  358.                 break;
  359.             }
  360.             if (tmp >= path.length) {
  361.                 growPath(tmp);
  362.             }
  363.             path[tmp] = c;
  364.         }
  365.         pathLen = tmp;
  366.         nextPtr = ptr + OBJECT_ID_LENGTH;
  367.     }

  369.     /**
  370.      * Retrieve the {@link org.eclipse.jgit.attributes.AttributesNode} for the
  371.      * current entry.
  372.      *
  373.      * @param reader
  374.      *            {@link org.eclipse.jgit.lib.ObjectReader} used to parse the
  375.      *            .gitattributes entry.
  376.      * @return {@link org.eclipse.jgit.attributes.AttributesNode} for the
  377.      *         current entry.
  378.      * @throws java.io.IOException
  379.      * @since 4.2
  380.      */
  381.     public AttributesNode getEntryAttributesNode(ObjectReader reader)
  382.             throws IOException {
  383.         if (attributesNode == null) {
  384.             attributesNode = findAttributes(reader);
  385.         }
  386.         return attributesNode.getRules().isEmpty() ? null : attributesNode;
  387.     }

  389.     private AttributesNode findAttributes(ObjectReader reader)
  390.             throws IOException {
  391.         CanonicalTreeParser itr = new CanonicalTreeParser();
  392.         itr.reset(raw);
  393.         if (itr.findFile(ATTRS)) {
  394.             return loadAttributes(reader, itr.getEntryObjectId());
  395.         }
  396.         return noAttributes();
  397.     }

  399.     private static AttributesNode loadAttributes(ObjectReader reader,
  400.             AnyObjectId id) throws IOException {
  401.         AttributesNode r = new AttributesNode();
  402.         try (InputStream in = reader.open(id, OBJ_BLOB).openStream()) {
  403.             r.parse(in);
  404.         }
  405.         return r.getRules().isEmpty() ? noAttributes() : r;
  406.     }

  408.     private static AttributesNode noAttributes() {
  409.         return new AttributesNode(Collections.<AttributesRule> emptyList());
  410.     }
  411. }
Created with JaCoCo 0.8.7.202105040129