2 * Copyright (C) 2008, Robin Rosenberg <robin.rosenberg@dewire.com>
3 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
7 * Redistribution and use in source and binary forms, with or
8 * without modification, are permitted provided that the following
11 * - Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
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.
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
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.
39 package org
.spearce
.jgit
.transport
;
42 import java
.io
.FileNotFoundException
;
43 import java
.io
.FileOutputStream
;
44 import java
.io
.IOException
;
45 import java
.util
.ArrayList
;
46 import java
.util
.Collection
;
47 import java
.util
.HashMap
;
48 import java
.util
.HashSet
;
49 import java
.util
.Iterator
;
50 import java
.util
.LinkedList
;
51 import java
.util
.List
;
54 import org
.spearce
.jgit
.errors
.CompoundException
;
55 import org
.spearce
.jgit
.errors
.CorruptObjectException
;
56 import org
.spearce
.jgit
.errors
.MissingObjectException
;
57 import org
.spearce
.jgit
.errors
.ObjectWritingException
;
58 import org
.spearce
.jgit
.errors
.TransportException
;
59 import org
.spearce
.jgit
.lib
.AnyObjectId
;
60 import org
.spearce
.jgit
.lib
.Constants
;
61 import org
.spearce
.jgit
.lib
.FileMode
;
62 import org
.spearce
.jgit
.lib
.ObjectId
;
63 import org
.spearce
.jgit
.lib
.PackIndex
;
64 import org
.spearce
.jgit
.lib
.ProgressMonitor
;
65 import org
.spearce
.jgit
.lib
.Ref
;
66 import org
.spearce
.jgit
.lib
.Repository
;
67 import org
.spearce
.jgit
.lib
.UnpackedObjectLoader
;
68 import org
.spearce
.jgit
.revwalk
.DateRevQueue
;
69 import org
.spearce
.jgit
.revwalk
.RevCommit
;
70 import org
.spearce
.jgit
.revwalk
.RevFlag
;
71 import org
.spearce
.jgit
.revwalk
.RevObject
;
72 import org
.spearce
.jgit
.revwalk
.RevTag
;
73 import org
.spearce
.jgit
.revwalk
.RevTree
;
74 import org
.spearce
.jgit
.revwalk
.RevWalk
;
75 import org
.spearce
.jgit
.treewalk
.TreeWalk
;
78 * Generic fetch support for dumb transport protocols.
80 * Since there are no Git-specific smarts on the remote side of the connection
81 * the client side must determine which objects it needs to copy in order to
82 * completely fetch the requested refs and their history. The generic walk
83 * support in this class parses each individual object (once it has been copied
84 * to the local repository) and examines the list of objects that must also be
85 * copied to create a complete history. Objects which are already available
86 * locally are retained (and not copied), saving bandwidth for incremental
87 * fetches. Pack files are copied from the remote repository only as a last
88 * resort, as the entire pack must be copied locally in order to access any
91 * This fetch connection does not actually perform the object data transfer.
92 * Instead it delegates the transfer to a {@link WalkRemoteObjectDatabase},
93 * which knows how to read individual files from the remote repository and
94 * supply the data as a standard Java InputStream.
96 * @see WalkRemoteObjectDatabase
98 class WalkFetchConnection
extends BaseFetchConnection
{
99 /** The repository this transport fetches into, or pushes out of. */
100 private final Repository local
;
103 * List of all remote repositories we may need to get objects out of.
105 * The first repository in the list is the one we were asked to fetch from;
106 * the remaining repositories point to the alternate locations we can fetch
109 private final List
<WalkRemoteObjectDatabase
> remotes
;
111 /** Most recently used item in {@link #remotes}. */
112 private int lastRemoteIdx
;
114 private final RevWalk revWalk
;
116 private final TreeWalk treeWalk
;
118 /** Objects whose direct dependents we know we have (or will have). */
119 private final RevFlag COMPLETE
;
121 /** Objects that have already entered {@link #workQueue}. */
122 private final RevFlag IN_WORK_QUEUE
;
124 /** Commits that have already entered {@link #localCommitQueue}. */
125 private final RevFlag LOCALLY_SEEN
;
127 /** Commits already reachable from all local refs. */
128 private final DateRevQueue localCommitQueue
;
130 /** Objects we need to copy from the remote repository. */
131 private LinkedList
<ObjectId
> workQueue
;
133 /** Databases we have not yet obtained the list of packs from. */
134 private final LinkedList
<WalkRemoteObjectDatabase
> noPacksYet
;
136 /** Databases we have not yet obtained the alternates from. */
137 private final LinkedList
<WalkRemoteObjectDatabase
> noAlternatesYet
;
139 /** Packs we have discovered, but have not yet fetched locally. */
140 private final LinkedList
<RemotePack
> unfetchedPacks
;
143 * Packs whose indexes we have looked at in {@link #unfetchedPacks}.
145 * We try to avoid getting duplicate copies of the same pack through
146 * multiple alternates by only looking at packs whose names are not yet in
149 private final Set
<String
> packsConsidered
;
152 * Errors received while trying to obtain an object.
154 * If the fetch winds up failing because we cannot locate a specific object
155 * then we need to report all errors related to that object back to the
156 * caller as there may be cascading failures.
158 private final HashMap
<ObjectId
, List
<Throwable
>> fetchErrors
;
160 WalkFetchConnection(final WalkTransport walkTransport
,
161 final WalkRemoteObjectDatabase w
) {
162 local
= walkTransport
.local
;
164 remotes
= new ArrayList
<WalkRemoteObjectDatabase
>();
167 unfetchedPacks
= new LinkedList
<RemotePack
>();
168 packsConsidered
= new HashSet
<String
>();
170 noPacksYet
= new LinkedList
<WalkRemoteObjectDatabase
>();
173 noAlternatesYet
= new LinkedList
<WalkRemoteObjectDatabase
>();
174 noAlternatesYet
.add(w
);
176 fetchErrors
= new HashMap
<ObjectId
, List
<Throwable
>>();
178 revWalk
= new RevWalk(local
);
179 treeWalk
= new TreeWalk(local
);
180 COMPLETE
= revWalk
.newFlag("COMPLETE");
181 IN_WORK_QUEUE
= revWalk
.newFlag("IN_WORK_QUEUE");
182 LOCALLY_SEEN
= revWalk
.newFlag("LOCALLY_SEEN");
184 localCommitQueue
= new DateRevQueue();
185 workQueue
= new LinkedList
<ObjectId
>();
189 protected void doFetch(final ProgressMonitor monitor
,
190 final Collection
<Ref
> want
) throws TransportException
{
191 markLocalRefsComplete();
194 while (!monitor
.isCancelled() && !workQueue
.isEmpty()) {
195 final ObjectId id
= workQueue
.removeFirst();
196 if (!(id
instanceof RevObject
) || !((RevObject
) id
).has(COMPLETE
))
197 downloadObject(monitor
, id
);
203 public void close() {
204 for (final WalkRemoteObjectDatabase r
: remotes
)
208 private void queueWants(final Collection
<Ref
> want
)
209 throws TransportException
{
210 final HashSet
<ObjectId
> inWorkQueue
= new HashSet
<ObjectId
>();
211 for (final Ref r
: want
) {
212 final ObjectId id
= r
.getObjectId();
214 final RevObject obj
= revWalk
.parseAny(id
);
215 if (obj
.has(COMPLETE
))
217 if (inWorkQueue
.add(id
)) {
218 obj
.add(IN_WORK_QUEUE
);
221 } catch (MissingObjectException e
) {
222 if (inWorkQueue
.add(id
))
224 } catch (IOException e
) {
225 throw new TransportException("Object read error " + id
+ ".", e
);
230 private void process(final ObjectId id
) throws TransportException
{
233 if (id
instanceof RevObject
) {
234 obj
= (RevObject
) id
;
235 if (obj
.has(COMPLETE
))
239 obj
= revWalk
.parseAny(id
);
240 if (obj
.has(COMPLETE
))
243 } catch (IOException e
) {
244 throw new TransportException("Object read error " + id
+ ".", e
);
247 // We only care about traversal; disposing an object throws its
248 // message buffer (if any) away but retains the links so we can
249 // continue to navigate, but use less memory long-term.
253 switch (obj
.getType()) {
254 case Constants
.OBJ_BLOB
:
257 case Constants
.OBJ_TREE
:
260 case Constants
.OBJ_COMMIT
:
263 case Constants
.OBJ_TAG
:
267 throw new TransportException("Unknown object type " + obj
.getId());
270 // If we had any prior errors fetching this object they are
271 // now resolved, as the object was parsed successfully.
273 fetchErrors
.remove(id
.copy());
276 private void processBlob(final RevObject obj
) throws TransportException
{
277 if (!local
.hasObject(obj
))
278 throw new TransportException("Cannot read blob " + obj
,
279 new MissingObjectException(obj
, Constants
.TYPE_BLOB
));
283 private void processTree(final RevObject obj
) throws TransportException
{
285 treeWalk
.reset(new ObjectId
[] { obj
});
286 while (treeWalk
.next()) {
287 final FileMode mode
= treeWalk
.getFileMode(0);
288 final int sType
= mode
.getObjectType();
291 case Constants
.OBJ_BLOB
:
292 case Constants
.OBJ_TREE
: {
293 final ObjectId sId
= treeWalk
.getObjectId(0);
294 needs(revWalk
.lookupAny(sId
, sType
));
298 if (FileMode
.GITLINK
.equals(mode
))
300 throw new CorruptObjectException("Invalid mode " + mode
301 + " for " + treeWalk
.getObjectId(0) + " "
302 + treeWalk
.getPathString() + " in " + obj
.getId()
306 } catch (IOException ioe
) {
307 throw new TransportException("Cannot read tree " + obj
, ioe
);
312 private void processCommit(final RevObject obj
) throws TransportException
{
313 final RevCommit commit
= (RevCommit
) obj
;
314 markLocalCommitsComplete(commit
.getCommitTime());
315 needs(commit
.getTree());
316 for (final RevCommit p
: commit
.getParents())
321 private void processTag(final RevObject obj
) {
322 final RevTag tag
= (RevTag
) obj
;
323 needs(tag
.getObject());
327 private void needs(final RevObject obj
) {
328 if (obj
.has(COMPLETE
))
330 if (!obj
.has(IN_WORK_QUEUE
)) {
331 obj
.add(IN_WORK_QUEUE
);
336 private void downloadObject(final ProgressMonitor pm
, final AnyObjectId id
)
337 throws TransportException
{
338 if (local
.hasObject(id
))
342 // Try a pack file we know about, but don't have yet. Odds are
343 // that if it has this object, it has others related to it so
344 // getting the pack is a good bet.
346 if (downloadPackedObject(pm
, id
))
349 // Search for a loose object over all alternates, starting
350 // from the one we last successfully located an object through.
352 final String idStr
= id
.toString();
353 final String subdir
= idStr
.substring(0, 2);
354 final String file
= idStr
.substring(2);
355 final String looseName
= subdir
+ "/" + file
;
357 for (int i
= lastRemoteIdx
; i
< remotes
.size(); i
++) {
358 if (downloadLooseObject(id
, looseName
, remotes
.get(i
))) {
363 for (int i
= 0; i
< lastRemoteIdx
; i
++) {
364 if (downloadLooseObject(id
, looseName
, remotes
.get(i
))) {
370 // Try to obtain more pack information and search those.
372 while (!noPacksYet
.isEmpty()) {
373 final WalkRemoteObjectDatabase wrr
= noPacksYet
.removeFirst();
374 final Collection
<String
> packNameList
;
376 pm
.beginTask("Listing packs", ProgressMonitor
.UNKNOWN
);
377 packNameList
= wrr
.getPackNames();
378 } catch (IOException e
) {
379 // Try another repository.
387 if (packNameList
== null || packNameList
.isEmpty())
389 for (final String packName
: packNameList
) {
390 if (packsConsidered
.add(packName
))
391 unfetchedPacks
.add(new RemotePack(wrr
, packName
));
393 if (downloadPackedObject(pm
, id
))
397 // Try to expand the first alternate we haven't expanded yet.
399 Collection
<WalkRemoteObjectDatabase
> al
= expandOneAlternate(id
, pm
);
400 if (al
!= null && !al
.isEmpty()) {
401 for (final WalkRemoteObjectDatabase alt
: al
) {
404 noAlternatesYet
.add(alt
);
409 // We could not obtain the object. There may be reasons why.
411 List
<Throwable
> failures
= fetchErrors
.get(id
.copy());
412 final TransportException te
;
414 te
= new TransportException("Cannot get " + id
+ ".");
415 if (failures
!= null && !failures
.isEmpty()) {
416 if (failures
.size() == 1)
417 te
.initCause(failures
.get(0));
419 te
.initCause(new CompoundException(failures
));
425 private boolean downloadPackedObject(final ProgressMonitor monitor
,
426 final AnyObjectId id
) throws TransportException
{
427 // Search for the object in a remote pack whose index we have,
428 // but whose pack we do not yet have.
430 final Iterator
<RemotePack
> packItr
= unfetchedPacks
.iterator();
431 while (packItr
.hasNext() && !monitor
.isCancelled()) {
432 final RemotePack pack
= packItr
.next();
434 pack
.openIndex(monitor
);
435 } catch (IOException err
) {
436 // If the index won't open its either not found or
437 // its a format we don't recognize. In either case
438 // we may still be able to obtain the object from
439 // another source, so don't consider it a failure.
441 recordError(id
, err
);
446 if (monitor
.isCancelled()) {
447 // If we were cancelled while the index was opening
448 // the open may have aborted. We can't search an
454 if (!pack
.index
.hasObject(id
)) {
455 // Not in this pack? Try another.
460 // It should be in the associated pack. Download that
461 // and attach it to the local repository so we can use
462 // all of the contained objects.
465 pack
.downloadPack(monitor
);
466 } catch (IOException err
) {
467 // If the pack failed to download, index correctly,
468 // or open in the local repository we may still be
469 // able to obtain this object from another pack or
472 recordError(id
, err
);
475 // If the pack was good its in the local repository
476 // and Repository.hasObject(id) will succeed in the
477 // future, so we do not need this data anymore. If
478 // it failed the index and pack are unusable and we
479 // shouldn't consult them again.
481 pack
.tmpIdx
.delete();
485 if (!local
.hasObject(id
)) {
486 // What the hell? This pack claimed to have
487 // the object, but after indexing we didn't
488 // actually find it in the pack.
490 recordError(id
, new FileNotFoundException("Object " + id
491 + " not found in " + pack
.packName
+ "."));
495 // Complete any other objects that we can.
497 final Iterator
<ObjectId
> pending
= swapFetchQueue();
498 while (pending
.hasNext()) {
499 final ObjectId p
= pending
.next();
500 if (pack
.index
.hasObject(p
)) {
513 private Iterator
<ObjectId
> swapFetchQueue() {
514 final Iterator
<ObjectId
> r
= workQueue
.iterator();
515 workQueue
= new LinkedList
<ObjectId
>();
519 private boolean downloadLooseObject(final AnyObjectId id
,
520 final String looseName
, final WalkRemoteObjectDatabase remote
)
521 throws TransportException
{
523 final byte[] compressed
= remote
.open(looseName
).toArray();
524 verifyLooseObject(id
, compressed
);
525 saveLooseObject(id
, compressed
);
527 } catch (FileNotFoundException e
) {
528 // Not available in a loose format from this alternate?
529 // Try another strategy to get the object.
533 } catch (IOException e
) {
534 throw new TransportException("Cannot download " + id
+ ".", e
);
538 private void verifyLooseObject(final AnyObjectId id
, final byte[] compressed
)
540 final UnpackedObjectLoader uol
;
542 uol
= new UnpackedObjectLoader(compressed
);
543 } catch (CorruptObjectException parsingError
) {
544 // Some HTTP servers send back a "200 OK" status with an HTML
545 // page that explains the requested file could not be found.
546 // These servers are most certainly misconfigured, but many
547 // of them exist in the world, and many of those are hosting
550 // Since an HTML page is unlikely to hash to one of our loose
551 // objects we treat this condition as a FileNotFoundException
552 // and attempt to recover by getting the object from another
555 final FileNotFoundException e
;
556 e
= new FileNotFoundException(id
.toString());
557 e
.initCause(parsingError
);
561 if (!AnyObjectId
.equals(id
, uol
.getId()))
562 throw new TransportException("Incorrect hash for " + id
563 + "; computed " + uol
.getId() + " as a " + uol
.getType()
564 + " from " + compressed
.length
+ " bytes.");
567 private void saveLooseObject(final AnyObjectId id
, final byte[] compressed
)
568 throws IOException
, ObjectWritingException
{
571 tmp
= File
.createTempFile("noz", null, local
.getObjectsDirectory());
573 final FileOutputStream out
= new FileOutputStream(tmp
);
575 out
.write(compressed
);
580 } catch (IOException e
) {
585 final File o
= local
.toFile(id
);
589 // Maybe the directory doesn't exist yet as the object
590 // directories are always lazily created. Note that we
591 // try the rename first as the directory likely does exist.
593 o
.getParentFile().mkdir();
598 if (local
.hasObject(id
))
600 throw new ObjectWritingException("Unable to store " + id
+ ".");
603 private Collection
<WalkRemoteObjectDatabase
> expandOneAlternate(
604 final AnyObjectId id
, final ProgressMonitor pm
) {
605 while (!noAlternatesYet
.isEmpty()) {
606 final WalkRemoteObjectDatabase wrr
= noAlternatesYet
.removeFirst();
608 pm
.beginTask("Listing alternates", ProgressMonitor
.UNKNOWN
);
609 Collection
<WalkRemoteObjectDatabase
> altList
= wrr
611 if (altList
!= null && !altList
.isEmpty())
613 } catch (IOException e
) {
614 // Try another repository.
624 private void markLocalRefsComplete() throws TransportException
{
625 for (final Ref r
: local
.getAllRefs().values()) {
627 markLocalObjComplete(revWalk
.parseAny(r
.getObjectId()));
628 } catch (IOException readError
) {
629 throw new TransportException("Local ref " + r
.getName()
630 + " is missing object(s).", readError
);
635 private void markLocalObjComplete(RevObject obj
) throws IOException
{
636 while (obj
.getType() == Constants
.OBJ_TAG
) {
639 obj
= ((RevTag
) obj
).getObject();
643 switch (obj
.getType()) {
644 case Constants
.OBJ_BLOB
:
647 case Constants
.OBJ_COMMIT
:
648 pushLocalCommit((RevCommit
) obj
);
650 case Constants
.OBJ_TREE
:
651 markTreeComplete((RevTree
) obj
);
656 private void markLocalCommitsComplete(final int until
)
657 throws TransportException
{
660 final RevCommit c
= localCommitQueue
.peek();
661 if (c
== null || c
.getCommitTime() < until
)
663 localCommitQueue
.next();
665 markTreeComplete(c
.getTree());
666 for (final RevCommit p
: c
.getParents())
669 } catch (IOException err
) {
670 throw new TransportException("Local objects incomplete.", err
);
674 private void pushLocalCommit(final RevCommit p
)
675 throws MissingObjectException
, IOException
{
676 if (p
.has(LOCALLY_SEEN
))
683 localCommitQueue
.add(p
);
686 private void markTreeComplete(final RevTree tree
) throws IOException
{
687 if (tree
.has(COMPLETE
))
690 treeWalk
.reset(new ObjectId
[] { tree
});
691 while (treeWalk
.next()) {
692 final FileMode mode
= treeWalk
.getFileMode(0);
693 final int sType
= mode
.getObjectType();
696 case Constants
.OBJ_BLOB
: {
697 final ObjectId sid
= treeWalk
.getObjectId(0);
698 revWalk
.lookupAny(sid
, sType
).add(COMPLETE
);
701 case Constants
.OBJ_TREE
: {
702 final ObjectId sid
= treeWalk
.getObjectId(0);
703 final RevObject o
= revWalk
.lookupAny(sid
, sType
);
704 if (!o
.has(COMPLETE
)) {
706 treeWalk
.enterSubtree();
711 if (FileMode
.GITLINK
.equals(mode
))
713 throw new CorruptObjectException("Invalid mode " + mode
714 + " for " + treeWalk
.getObjectId(0) + " "
715 + treeWalk
.getPathString() + " in " + tree
+ ".");
720 private void recordError(final AnyObjectId id
, final Throwable what
) {
721 final ObjectId objId
= id
.copy();
722 List
<Throwable
> errors
= fetchErrors
.get(objId
);
723 if (errors
== null) {
724 errors
= new ArrayList
<Throwable
>(2);
725 fetchErrors
.put(objId
, errors
);
730 private class RemotePack
{
731 final WalkRemoteObjectDatabase connection
;
733 final String packName
;
735 final String idxName
;
741 RemotePack(final WalkRemoteObjectDatabase c
, final String pn
) {
742 final File objdir
= local
.getObjectsDirectory();
745 idxName
= packName
.substring(0, packName
.length() - 5) + ".idx";
748 if (tn
.startsWith("pack-"))
749 tn
= tn
.substring(5);
750 if (tn
.endsWith(".idx"))
751 tn
= tn
.substring(0, tn
.length() - 4);
752 tmpIdx
= new File(objdir
, "walk-" + tn
+ ".walkidx");
755 void openIndex(final ProgressMonitor pm
) throws IOException
{
758 if (tmpIdx
.isFile()) {
760 index
= PackIndex
.open(tmpIdx
);
762 } catch (FileNotFoundException err
) {
763 // Fall through and get the file.
767 final WalkRemoteObjectDatabase
.FileStream s
;
768 s
= connection
.open("pack/" + idxName
);
769 pm
.beginTask("Get " + idxName
.substring(0, 12) + "..idx",
770 s
.length
< 0 ? ProgressMonitor
.UNKNOWN
771 : (int) (s
.length
/ 1024));
773 final FileOutputStream fos
= new FileOutputStream(tmpIdx
);
775 final byte[] buf
= new byte[2048];
777 while (!pm
.isCancelled() && (cnt
= s
.in
.read(buf
)) >= 0) {
778 fos
.write(buf
, 0, cnt
);
779 pm
.update(cnt
/ 1024);
784 } catch (IOException err
) {
792 if (pm
.isCancelled()) {
798 index
= PackIndex
.open(tmpIdx
);
799 } catch (IOException e
) {
805 void downloadPack(final ProgressMonitor monitor
) throws IOException
{
806 final WalkRemoteObjectDatabase
.FileStream s
;
809 s
= connection
.open("pack/" + packName
);
810 ip
= IndexPack
.create(local
, s
.in
);
811 ip
.setFixThin(false);
813 ip
.renameAndOpenPack();