2 * Copyright (C) 2008 Shawn Pearce <spearce@spearce.org>
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License, version 2, as published by the Free Software Foundation.
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this library; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
17 package org
.spearce
.jgit
.transport
;
20 import java
.io
.FileNotFoundException
;
21 import java
.io
.FileOutputStream
;
22 import java
.io
.IOException
;
23 import java
.util
.ArrayList
;
24 import java
.util
.Collection
;
25 import java
.util
.HashMap
;
26 import java
.util
.HashSet
;
27 import java
.util
.Iterator
;
28 import java
.util
.LinkedList
;
29 import java
.util
.List
;
32 import org
.spearce
.jgit
.errors
.CompoundException
;
33 import org
.spearce
.jgit
.errors
.CorruptObjectException
;
34 import org
.spearce
.jgit
.errors
.MissingObjectException
;
35 import org
.spearce
.jgit
.errors
.ObjectWritingException
;
36 import org
.spearce
.jgit
.errors
.TransportException
;
37 import org
.spearce
.jgit
.lib
.AnyObjectId
;
38 import org
.spearce
.jgit
.lib
.Constants
;
39 import org
.spearce
.jgit
.lib
.FileMode
;
40 import org
.spearce
.jgit
.lib
.ObjectId
;
41 import org
.spearce
.jgit
.lib
.PackIndex
;
42 import org
.spearce
.jgit
.lib
.ProgressMonitor
;
43 import org
.spearce
.jgit
.lib
.Ref
;
44 import org
.spearce
.jgit
.lib
.Repository
;
45 import org
.spearce
.jgit
.lib
.UnpackedObjectLoader
;
46 import org
.spearce
.jgit
.revwalk
.DateRevQueue
;
47 import org
.spearce
.jgit
.revwalk
.RevBlob
;
48 import org
.spearce
.jgit
.revwalk
.RevCommit
;
49 import org
.spearce
.jgit
.revwalk
.RevFlag
;
50 import org
.spearce
.jgit
.revwalk
.RevObject
;
51 import org
.spearce
.jgit
.revwalk
.RevTag
;
52 import org
.spearce
.jgit
.revwalk
.RevTree
;
53 import org
.spearce
.jgit
.revwalk
.RevWalk
;
54 import org
.spearce
.jgit
.treewalk
.TreeWalk
;
57 * Generic fetch support for dumb transport protocols.
59 * Since there are no Git-specific smarts on the remote side of the connection
60 * the client side must determine which objects it needs to copy in order to
61 * completely fetch the requested refs and their history. The generic walk
62 * support in this class parses each individual object (once it has been copied
63 * to the local repository) and examines the list of objects that must also be
64 * copied to create a complete history. Objects which are already available
65 * locally are retained (and not copied), saving bandwidth for incremental
66 * fetches. Pack files are copied from the remote repository only as a last
67 * resort, as the entire pack must be copied locally in order to access any
70 * This fetch connection does not actually perform the object data transfer.
71 * Instead it delegates the transfer to a {@link WalkRemoteObjectDatabase},
72 * which knows how to read individual files from the remote repository and
73 * supply the data as a standard Java InputStream.
75 * @see WalkRemoteObjectDatabase
77 class WalkFetchConnection
extends FetchConnection
{
78 /** The repository this transport fetches into, or pushes out of. */
79 private final Repository local
;
82 * List of all remote repositories we may need to get objects out of.
84 * The first repository in the list is the one we were asked to fetch from;
85 * the remaining repositories point to the alternate locations we can fetch
88 private final List
<WalkRemoteObjectDatabase
> remotes
;
90 /** Most recently used item in {@link #remotes}. */
91 private int lastRemoteIdx
;
93 private final RevWalk revWalk
;
95 private final TreeWalk treeWalk
;
97 /** Objects whose direct dependents we know we have (or will have). */
98 private final RevFlag COMPLETE
;
100 /** Objects that have already entered {@link #workQueue}. */
101 private final RevFlag IN_WORK_QUEUE
;
103 /** Commits that have already entered {@link #localCommitQueue}. */
104 private final RevFlag LOCALLY_SEEN
;
106 /** Commits already reachable from all local refs. */
107 private final DateRevQueue localCommitQueue
;
109 /** Objects we need to copy from the remote repository. */
110 private LinkedList
<ObjectId
> workQueue
;
112 /** Databases we have not yet obtained the list of packs from. */
113 private final LinkedList
<WalkRemoteObjectDatabase
> noPacksYet
;
115 /** Databases we have not yet obtained the alternates from. */
116 private final LinkedList
<WalkRemoteObjectDatabase
> noAlternatesYet
;
118 /** Packs we have discovered, but have not yet fetched locally. */
119 private final LinkedList
<RemotePack
> unfetchedPacks
;
122 * Packs whose indexes we have looked at in {@link #unfetchedPacks}.
124 * We try to avoid getting duplicate copies of the same pack through
125 * multiple alternates by only looking at packs whose names are not yet in
128 private final Set
<String
> packsConsidered
;
131 * Errors received while trying to obtain an object.
133 * If the fetch winds up failing because we cannot locate a specific object
134 * then we need to report all errors related to that object back to the
135 * caller as there may be cascading failures.
137 private final HashMap
<ObjectId
, List
<Throwable
>> fetchErrors
;
139 WalkFetchConnection(final WalkTransport walkTransport
,
140 final WalkRemoteObjectDatabase w
) {
141 local
= walkTransport
.local
;
143 remotes
= new ArrayList
<WalkRemoteObjectDatabase
>();
146 unfetchedPacks
= new LinkedList
<RemotePack
>();
147 packsConsidered
= new HashSet
<String
>();
149 noPacksYet
= new LinkedList
<WalkRemoteObjectDatabase
>();
152 noAlternatesYet
= new LinkedList
<WalkRemoteObjectDatabase
>();
153 noAlternatesYet
.add(w
);
155 fetchErrors
= new HashMap
<ObjectId
, List
<Throwable
>>();
157 revWalk
= new RevWalk(local
);
158 treeWalk
= new TreeWalk(local
);
159 COMPLETE
= revWalk
.newFlag("COMPLETE");
160 IN_WORK_QUEUE
= revWalk
.newFlag("IN_WORK_QUEUE");
161 LOCALLY_SEEN
= revWalk
.newFlag("LOCALLY_SEEN");
163 localCommitQueue
= new DateRevQueue();
164 workQueue
= new LinkedList
<ObjectId
>();
168 protected void doFetch(final ProgressMonitor monitor
,
169 final Collection
<Ref
> want
) throws TransportException
{
170 markLocalRefsComplete();
173 while (!monitor
.isCancelled() && !workQueue
.isEmpty()) {
174 final ObjectId id
= workQueue
.removeFirst();
175 if (!(id
instanceof RevObject
) || !((RevObject
) id
).has(COMPLETE
))
176 downloadObject(monitor
, id
);
182 public void close() {
183 for (final WalkRemoteObjectDatabase r
: remotes
)
187 private void queueWants(final Collection
<Ref
> want
)
188 throws TransportException
{
189 final HashSet
<ObjectId
> inWorkQueue
= new HashSet
<ObjectId
>();
190 for (final Ref r
: want
) {
191 final ObjectId id
= r
.getObjectId();
193 final RevObject obj
= revWalk
.parseAny(id
);
194 if (obj
.has(COMPLETE
))
196 if (inWorkQueue
.add(id
)) {
197 obj
.add(IN_WORK_QUEUE
);
200 } catch (MissingObjectException e
) {
201 if (inWorkQueue
.add(id
))
203 } catch (IOException e
) {
204 throw new TransportException("Object read error " + id
+ ".", e
);
209 private void process(final ObjectId id
) throws TransportException
{
212 if (id
instanceof RevObject
) {
213 obj
= (RevObject
) id
;
214 if (obj
.has(COMPLETE
))
218 obj
= revWalk
.parseAny(id
);
219 if (obj
.has(COMPLETE
))
222 } catch (IOException e
) {
223 throw new TransportException("Object read error " + id
+ ".", e
);
226 // We only care about traversal; disposing an object throws its
227 // message buffer (if any) away but retains the links so we can
228 // continue to navigate, but use less memory long-term.
232 if (obj
instanceof RevBlob
)
235 else if (obj
instanceof RevTree
)
238 else if (obj
instanceof RevCommit
)
241 else if (obj
instanceof RevTag
)
245 throw new TransportException("Unknown object type " + obj
.getId());
247 // If we had any prior errors fetching this object they are
248 // now resolved, as the object was parsed successfully.
250 fetchErrors
.remove(id
.copy());
253 private void processBlob(final RevObject obj
) throws TransportException
{
254 if (!local
.hasObject(obj
))
255 throw new TransportException("Cannot read blob " + obj
,
256 new MissingObjectException(obj
, Constants
.TYPE_BLOB
));
260 private void processTree(final RevObject obj
) throws TransportException
{
262 treeWalk
.reset(new ObjectId
[] { obj
});
263 while (treeWalk
.next()) {
264 final FileMode mode
= treeWalk
.getFileMode(0);
265 final int sType
= mode
.getObjectType();
268 case Constants
.OBJ_BLOB
:
269 case Constants
.OBJ_TREE
: {
270 final ObjectId sId
= treeWalk
.getObjectId(0);
271 needs(revWalk
.lookupAny(sId
, sType
));
275 if (FileMode
.GITLINK
.equals(mode
))
277 throw new CorruptObjectException("Invalid mode " + mode
278 + " for " + treeWalk
.getObjectId(0) + " "
279 + treeWalk
.getPathString() + " in " + obj
.getId()
283 } catch (IOException ioe
) {
284 throw new TransportException("Cannot read tree " + obj
, ioe
);
289 private void processCommit(final RevObject obj
) throws TransportException
{
290 final RevCommit commit
= (RevCommit
) obj
;
291 markLocalCommitsComplete(commit
.getCommitTime());
292 needs(commit
.getTree());
293 for (final RevCommit p
: commit
.getParents())
298 private void processTag(final RevObject obj
) {
299 final RevTag tag
= (RevTag
) obj
;
300 needs(tag
.getObject());
304 private void needs(final RevObject obj
) {
305 if (obj
.has(COMPLETE
))
307 if (!obj
.has(IN_WORK_QUEUE
)) {
308 obj
.add(IN_WORK_QUEUE
);
313 private void downloadObject(final ProgressMonitor pm
, final AnyObjectId id
)
314 throws TransportException
{
315 if (local
.hasObject(id
))
319 // Try a pack file we know about, but don't have yet. Odds are
320 // that if it has this object, it has others related to it so
321 // getting the pack is a good bet.
323 if (downloadPackedObject(pm
, id
))
326 // Search for a loose object over all alternates, starting
327 // from the one we last successfully located an object through.
329 final String idStr
= id
.toString();
330 final String subdir
= idStr
.substring(0, 2);
331 final String file
= idStr
.substring(2);
332 final String looseName
= subdir
+ "/" + file
;
334 for (int i
= lastRemoteIdx
; i
< remotes
.size(); i
++) {
335 if (downloadLooseObject(id
, looseName
, remotes
.get(i
))) {
340 for (int i
= 0; i
< lastRemoteIdx
; i
++) {
341 if (downloadLooseObject(id
, looseName
, remotes
.get(i
))) {
347 // Try to obtain more pack information and search those.
349 while (!noPacksYet
.isEmpty()) {
350 final WalkRemoteObjectDatabase wrr
= noPacksYet
.removeFirst();
351 final Collection
<String
> packNameList
;
353 pm
.beginTask("Listing packs", ProgressMonitor
.UNKNOWN
);
354 packNameList
= wrr
.getPackNames();
355 } catch (IOException e
) {
356 // Try another repository.
364 if (packNameList
== null || packNameList
.isEmpty())
366 for (final String packName
: packNameList
) {
367 if (packsConsidered
.add(packName
))
368 unfetchedPacks
.add(new RemotePack(wrr
, packName
));
370 if (downloadPackedObject(pm
, id
))
374 // Try to expand the first alternate we haven't expanded yet.
376 Collection
<WalkRemoteObjectDatabase
> al
= expandOneAlternate(id
, pm
);
377 if (al
!= null && !al
.isEmpty()) {
378 for (final WalkRemoteObjectDatabase alt
: al
) {
381 noAlternatesYet
.add(alt
);
386 // We could not obtain the object. There may be reasons why.
388 List
<Throwable
> failures
= fetchErrors
.get(id
.copy());
389 final TransportException te
;
391 te
= new TransportException("Cannot get " + id
+ ".");
392 if (failures
!= null && !failures
.isEmpty()) {
393 if (failures
.size() == 1)
394 te
.initCause(failures
.get(0));
396 te
.initCause(new CompoundException(failures
));
402 private boolean downloadPackedObject(final ProgressMonitor monitor
,
403 final AnyObjectId id
) throws TransportException
{
404 // Search for the object in a remote pack whose index we have,
405 // but whose pack we do not yet have.
407 final Iterator
<RemotePack
> packItr
= unfetchedPacks
.iterator();
408 while (packItr
.hasNext() && !monitor
.isCancelled()) {
409 final RemotePack pack
= packItr
.next();
411 pack
.openIndex(monitor
);
412 } catch (IOException err
) {
413 // If the index won't open its either not found or
414 // its a format we don't recognize. In either case
415 // we may still be able to obtain the object from
416 // another source, so don't consider it a failure.
418 recordError(id
, err
);
423 if (monitor
.isCancelled()) {
424 // If we were cancelled while the index was opening
425 // the open may have aborted. We can't search an
431 if (!pack
.index
.hasObject(id
)) {
432 // Not in this pack? Try another.
437 // It should be in the associated pack. Download that
438 // and attach it to the local repository so we can use
439 // all of the contained objects.
442 pack
.downloadPack(monitor
);
443 } catch (IOException err
) {
444 // If the pack failed to download, index correctly,
445 // or open in the local repository we may still be
446 // able to obtain this object from another pack or
449 recordError(id
, err
);
452 // If the pack was good its in the local repository
453 // and Repository.hasObject(id) will succeed in the
454 // future, so we do not need this data anymore. If
455 // it failed the index and pack are unusable and we
456 // shouldn't consult them again.
458 pack
.tmpIdx
.delete();
462 if (!local
.hasObject(id
)) {
463 // What the hell? This pack claimed to have
464 // the object, but after indexing we didn't
465 // actually find it in the pack.
467 recordError(id
, new FileNotFoundException("Object " + id
468 + " not found in " + pack
.packName
+ "."));
472 // Complete any other objects that we can.
474 final Iterator
<ObjectId
> pending
= swapFetchQueue();
475 while (pending
.hasNext()) {
476 final ObjectId p
= pending
.next();
477 if (pack
.index
.hasObject(p
)) {
490 private Iterator
<ObjectId
> swapFetchQueue() {
491 final Iterator
<ObjectId
> r
= workQueue
.iterator();
492 workQueue
= new LinkedList
<ObjectId
>();
496 private boolean downloadLooseObject(final AnyObjectId id
,
497 final String looseName
, final WalkRemoteObjectDatabase remote
)
498 throws TransportException
{
500 final byte[] compressed
= remote
.open(looseName
).toArray();
501 verifyLooseObject(id
, compressed
);
502 saveLooseObject(id
, compressed
);
504 } catch (FileNotFoundException e
) {
505 // Not available in a loose format from this alternate?
506 // Try another strategy to get the object.
510 } catch (IOException e
) {
511 throw new TransportException("Cannot download " + id
+ ".", e
);
515 private void verifyLooseObject(final AnyObjectId id
, final byte[] compressed
)
517 final UnpackedObjectLoader uol
;
519 uol
= new UnpackedObjectLoader(compressed
);
520 } catch (CorruptObjectException parsingError
) {
521 // Some HTTP servers send back a "200 OK" status with an HTML
522 // page that explains the requested file could not be found.
523 // These servers are most certainly misconfigured, but many
524 // of them exist in the world, and many of those are hosting
527 // Since an HTML page is unlikely to hash to one of our loose
528 // objects we treat this condition as a FileNotFoundException
529 // and attempt to recover by getting the object from another
532 final FileNotFoundException e
;
533 e
= new FileNotFoundException(id
.toString());
534 e
.initCause(parsingError
);
538 if (!AnyObjectId
.equals(id
, uol
.getId()))
539 throw new TransportException("Incorrect hash for " + id
540 + "; computed " + uol
.getId() + " as a " + uol
.getType()
541 + " from " + compressed
.length
+ " bytes.");
544 private void saveLooseObject(final AnyObjectId id
, final byte[] compressed
)
545 throws IOException
, ObjectWritingException
{
548 tmp
= File
.createTempFile("noz", null, local
.getObjectsDirectory());
550 final FileOutputStream out
= new FileOutputStream(tmp
);
552 out
.write(compressed
);
557 } catch (IOException e
) {
562 final File o
= local
.toFile(id
);
566 // Maybe the directory doesn't exist yet as the object
567 // directories are always lazily created. Note that we
568 // try the rename first as the directory likely does exist.
570 o
.getParentFile().mkdir();
575 if (local
.hasObject(id
))
577 throw new ObjectWritingException("Unable to store " + id
+ ".");
580 private Collection
<WalkRemoteObjectDatabase
> expandOneAlternate(
581 final AnyObjectId id
, final ProgressMonitor pm
) {
582 while (!noAlternatesYet
.isEmpty()) {
583 final WalkRemoteObjectDatabase wrr
= noAlternatesYet
.removeFirst();
585 pm
.beginTask("Listing alternates", ProgressMonitor
.UNKNOWN
);
586 Collection
<WalkRemoteObjectDatabase
> altList
= wrr
588 if (altList
!= null && !altList
.isEmpty())
590 } catch (IOException e
) {
591 // Try another repository.
601 private void markLocalRefsComplete() throws TransportException
{
602 for (final String name
: local
.getAllRefs()) {
604 markLocalObjComplete(revWalk
.parseAny(local
.resolve(name
)));
605 } catch (IOException readError
) {
606 throw new TransportException("Local ref " + name
607 + " is missing object(s).", readError
);
612 private void markLocalObjComplete(RevObject obj
) throws IOException
{
613 while (obj
instanceof RevTag
) {
616 obj
= ((RevTag
) obj
).getObject();
620 if (obj
instanceof RevBlob
)
622 else if (obj
instanceof RevCommit
)
623 pushLocalCommit((RevCommit
) obj
);
624 else if (obj
instanceof RevTree
)
625 markTreeComplete((RevTree
) obj
);
628 private void markLocalCommitsComplete(final int until
)
629 throws TransportException
{
632 final RevCommit c
= localCommitQueue
.peek();
633 if (c
== null || c
.getCommitTime() < until
)
635 localCommitQueue
.next();
637 markTreeComplete(c
.getTree());
638 for (final RevCommit p
: c
.getParents())
641 } catch (IOException err
) {
642 throw new TransportException("Local objects incomplete.", err
);
646 private void pushLocalCommit(final RevCommit p
)
647 throws MissingObjectException
, IOException
{
648 if (p
.has(LOCALLY_SEEN
))
655 localCommitQueue
.add(p
);
658 private void markTreeComplete(final RevTree tree
) throws IOException
{
659 if (tree
.has(COMPLETE
))
662 treeWalk
.reset(new ObjectId
[] { tree
});
663 while (treeWalk
.next()) {
664 final FileMode mode
= treeWalk
.getFileMode(0);
665 final int sType
= mode
.getObjectType();
668 case Constants
.OBJ_BLOB
: {
669 final ObjectId sid
= treeWalk
.getObjectId(0);
670 revWalk
.lookupAny(sid
, sType
).add(COMPLETE
);
673 case Constants
.OBJ_TREE
: {
674 final ObjectId sid
= treeWalk
.getObjectId(0);
675 final RevObject o
= revWalk
.lookupAny(sid
, sType
);
676 if (!o
.has(COMPLETE
)) {
678 treeWalk
.enterSubtree();
683 if (FileMode
.GITLINK
.equals(mode
))
685 throw new CorruptObjectException("Invalid mode " + mode
686 + " for " + treeWalk
.getObjectId(0) + " "
687 + treeWalk
.getPathString() + " in " + tree
+ ".");
692 private void recordError(final AnyObjectId id
, final Throwable what
) {
693 final ObjectId objId
= id
.copy();
694 List
<Throwable
> errors
= fetchErrors
.get(objId
);
695 if (errors
== null) {
696 errors
= new ArrayList
<Throwable
>(2);
697 fetchErrors
.put(objId
, errors
);
702 private class RemotePack
{
703 final WalkRemoteObjectDatabase connection
;
705 final String packName
;
707 final String idxName
;
713 RemotePack(final WalkRemoteObjectDatabase c
, final String pn
) {
714 final File objdir
= local
.getObjectsDirectory();
717 idxName
= packName
.substring(0, packName
.length() - 5) + ".idx";
720 if (tn
.startsWith("pack-"))
721 tn
= tn
.substring(5);
722 if (tn
.endsWith(".idx"))
723 tn
= tn
.substring(0, tn
.length() - 4);
724 tmpIdx
= new File(objdir
, "walk-" + tn
+ ".walkidx");
727 void openIndex(final ProgressMonitor pm
) throws IOException
{
730 if (tmpIdx
.isFile()) {
732 index
= PackIndex
.open(tmpIdx
);
734 } catch (FileNotFoundException err
) {
735 // Fall through and get the file.
739 final WalkRemoteObjectDatabase
.FileStream s
;
740 s
= connection
.open("pack/" + idxName
);
741 pm
.beginTask("Get " + idxName
.substring(0, 12) + "..idx",
742 s
.length
< 0 ? ProgressMonitor
.UNKNOWN
743 : (int) (s
.length
/ 1024));
745 final FileOutputStream fos
= new FileOutputStream(tmpIdx
);
747 final byte[] buf
= new byte[2048];
749 while (!pm
.isCancelled() && (cnt
= s
.in
.read(buf
)) >= 0) {
750 fos
.write(buf
, 0, cnt
);
751 pm
.update(cnt
/ 1024);
756 } catch (IOException err
) {
764 if (pm
.isCancelled()) {
770 index
= PackIndex
.open(tmpIdx
);
771 } catch (IOException e
) {
777 void downloadPack(final ProgressMonitor monitor
) throws IOException
{
778 final WalkRemoteObjectDatabase
.FileStream s
;
781 s
= connection
.open("pack/" + packName
);
782 ip
= IndexPack
.create(local
, s
.in
);
783 ip
.setFixThin(false);
785 ip
.renameAndOpenPack();