Implement FileMode.fromBits utility in TreeWalk
[egit.git] / org.spearce.jgit / src / org / spearce / jgit / transport / WalkFetchConnection.java
blobf36699d8dc04b2ed71bd882c13c1fbbe4644bc2b
1 /*
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;
19 import java.io.File;
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;
30 import java.util.Set;
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;
56 /**
57 * Generic fetch support for dumb transport protocols.
58 * <p>
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
68 * single object.
69 * <p>
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;
81 /**
82 * List of all remote repositories we may need to get objects out of.
83 * <p>
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
86 * objects through.
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}.
123 * <p>
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
126 * this collection.
128 private final Set<String> packsConsidered;
131 * Errors received while trying to obtain an object.
132 * <p>
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>();
144 remotes.add(w);
146 unfetchedPacks = new LinkedList<RemotePack>();
147 packsConsidered = new HashSet<String>();
149 noPacksYet = new LinkedList<WalkRemoteObjectDatabase>();
150 noPacksYet.add(w);
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>();
167 @Override
168 protected void doFetch(final ProgressMonitor monitor,
169 final Collection<Ref> want) throws TransportException {
170 markLocalRefsComplete();
171 queueWants(want);
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);
177 process(id);
181 @Override
182 public void close() {
183 for (final WalkRemoteObjectDatabase r : remotes)
184 r.close();
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();
192 try {
193 final RevObject obj = revWalk.parseAny(id);
194 if (obj.has(COMPLETE))
195 continue;
196 if (inWorkQueue.add(id)) {
197 obj.add(IN_WORK_QUEUE);
198 workQueue.add(obj);
200 } catch (MissingObjectException e) {
201 if (inWorkQueue.add(id))
202 workQueue.add(id);
203 } catch (IOException e) {
204 throw new TransportException("Object read error " + id + ".", e);
209 private void process(final ObjectId id) throws TransportException {
210 final RevObject obj;
211 try {
212 if (id instanceof RevObject) {
213 obj = (RevObject) id;
214 if (obj.has(COMPLETE))
215 return;
216 revWalk.parse(obj);
217 } else {
218 obj = revWalk.parseAny(id);
219 if (obj.has(COMPLETE))
220 return;
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.
230 obj.dispose();
232 if (obj instanceof RevBlob)
233 processBlob(obj);
235 else if (obj instanceof RevTree)
236 processTree(obj);
238 else if (obj instanceof RevCommit)
239 processCommit(obj);
241 else if (obj instanceof RevTag)
242 processTag(obj);
244 else
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));
257 obj.add(COMPLETE);
260 private void processTree(final RevObject obj) throws TransportException {
261 try {
262 treeWalk.reset(new ObjectId[] { obj });
263 while (treeWalk.next()) {
264 final FileMode mode = treeWalk.getFileMode(0);
265 final int sType = mode.getObjectType();
267 switch (sType) {
268 case Constants.OBJ_BLOB:
269 case Constants.OBJ_TREE: {
270 final ObjectId sId = treeWalk.getObjectId(0);
271 needs(revWalk.lookupAny(sId, sType));
272 continue;
274 default:
275 if (FileMode.GITLINK.equals(mode))
276 continue;
277 throw new CorruptObjectException("Invalid mode " + mode
278 + " for " + treeWalk.getObjectId(0) + " "
279 + treeWalk.getPathString() + " in " + obj.getId()
280 + ".");
283 } catch (IOException ioe) {
284 throw new TransportException("Cannot read tree " + obj, ioe);
286 obj.add(COMPLETE);
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())
294 needs(p);
295 obj.add(COMPLETE);
298 private void processTag(final RevObject obj) {
299 final RevTag tag = (RevTag) obj;
300 needs(tag.getObject());
301 obj.add(COMPLETE);
304 private void needs(final RevObject obj) {
305 if (obj.has(COMPLETE))
306 return;
307 if (!obj.has(IN_WORK_QUEUE)) {
308 obj.add(IN_WORK_QUEUE);
309 workQueue.add(obj);
313 private void downloadObject(final ProgressMonitor pm, final AnyObjectId id)
314 throws TransportException {
315 if (local.hasObject(id))
316 return;
318 for (;;) {
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))
324 return;
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))) {
336 lastRemoteIdx = i;
337 return;
340 for (int i = 0; i < lastRemoteIdx; i++) {
341 if (downloadLooseObject(id, looseName, remotes.get(i))) {
342 lastRemoteIdx = i;
343 return;
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;
352 try {
353 pm.beginTask("Listing packs", ProgressMonitor.UNKNOWN);
354 packNameList = wrr.getPackNames();
355 } catch (IOException e) {
356 // Try another repository.
358 recordError(id, e);
359 continue;
360 } finally {
361 pm.endTask();
364 if (packNameList == null || packNameList.isEmpty())
365 continue;
366 for (final String packName : packNameList) {
367 if (packsConsidered.add(packName))
368 unfetchedPacks.add(new RemotePack(wrr, packName));
370 if (downloadPackedObject(pm, id))
371 return;
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) {
379 remotes.add(alt);
380 noPacksYet.add(alt);
381 noAlternatesYet.add(alt);
383 continue;
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));
395 else
396 te.initCause(new CompoundException(failures));
398 throw te;
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();
410 try {
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);
419 packItr.remove();
420 continue;
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
426 // unopen index.
428 return false;
431 if (!pack.index.hasObject(id)) {
432 // Not in this pack? Try another.
434 continue;
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.
441 try {
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
447 // an alternate.
449 recordError(id, err);
450 continue;
451 } finally {
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();
459 packItr.remove();
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 + "."));
469 continue;
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)) {
478 pending.remove();
479 process(p);
480 } else {
481 workQueue.add(p);
484 return true;
487 return false;
490 private Iterator<ObjectId> swapFetchQueue() {
491 final Iterator<ObjectId> r = workQueue.iterator();
492 workQueue = new LinkedList<ObjectId>();
493 return r;
496 private boolean downloadLooseObject(final AnyObjectId id,
497 final String looseName, final WalkRemoteObjectDatabase remote)
498 throws TransportException {
499 try {
500 final byte[] compressed = remote.open(looseName).toArray();
501 verifyLooseObject(id, compressed);
502 saveLooseObject(id, compressed);
503 return true;
504 } catch (FileNotFoundException e) {
505 // Not available in a loose format from this alternate?
506 // Try another strategy to get the object.
508 recordError(id, e);
509 return false;
510 } catch (IOException e) {
511 throw new TransportException("Cannot download " + id + ".", e);
515 private void verifyLooseObject(final AnyObjectId id, final byte[] compressed)
516 throws IOException {
517 final UnpackedObjectLoader uol;
518 try {
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
525 // Git repositories.
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
530 // source.
532 final FileNotFoundException e;
533 e = new FileNotFoundException(id.toString());
534 e.initCause(parsingError);
535 throw e;
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 {
546 final File tmp;
548 tmp = File.createTempFile("noz", null, local.getObjectsDirectory());
549 try {
550 final FileOutputStream out = new FileOutputStream(tmp);
551 try {
552 out.write(compressed);
553 } finally {
554 out.close();
556 tmp.setReadOnly();
557 } catch (IOException e) {
558 tmp.delete();
559 throw e;
562 final File o = local.toFile(id);
563 if (tmp.renameTo(o))
564 return;
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();
571 if (tmp.renameTo(o))
572 return;
574 tmp.delete();
575 if (local.hasObject(id))
576 return;
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();
584 try {
585 pm.beginTask("Listing alternates", ProgressMonitor.UNKNOWN);
586 Collection<WalkRemoteObjectDatabase> altList = wrr
587 .getAlternates();
588 if (altList != null && !altList.isEmpty())
589 return altList;
590 } catch (IOException e) {
591 // Try another repository.
593 recordError(id, e);
594 } finally {
595 pm.endTask();
598 return null;
601 private void markLocalRefsComplete() throws TransportException {
602 for (final String name : local.getAllRefs()) {
603 try {
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) {
614 obj.add(COMPLETE);
615 obj.dispose();
616 obj = ((RevTag) obj).getObject();
617 revWalk.parse(obj);
620 if (obj instanceof RevBlob)
621 obj.add(COMPLETE);
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 {
630 try {
631 for (;;) {
632 final RevCommit c = localCommitQueue.peek();
633 if (c == null || c.getCommitTime() < until)
634 return;
635 localCommitQueue.next();
637 markTreeComplete(c.getTree());
638 for (final RevCommit p : c.getParents())
639 pushLocalCommit(p);
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))
649 return;
650 revWalk.parse(p);
651 p.add(LOCALLY_SEEN);
652 p.add(COMPLETE);
653 p.carry(COMPLETE);
654 p.dispose();
655 localCommitQueue.add(p);
658 private void markTreeComplete(final RevTree tree) throws IOException {
659 if (tree.has(COMPLETE))
660 return;
661 tree.add(COMPLETE);
662 treeWalk.reset(new ObjectId[] { tree });
663 while (treeWalk.next()) {
664 final FileMode mode = treeWalk.getFileMode(0);
665 final int sType = mode.getObjectType();
667 switch (sType) {
668 case Constants.OBJ_BLOB: {
669 final ObjectId sid = treeWalk.getObjectId(0);
670 revWalk.lookupAny(sid, sType).add(COMPLETE);
671 continue;
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)) {
677 o.add(COMPLETE);
678 treeWalk.enterSubtree();
680 continue;
682 default:
683 if (FileMode.GITLINK.equals(mode))
684 continue;
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);
699 errors.add(what);
702 private class RemotePack {
703 final WalkRemoteObjectDatabase connection;
705 final String packName;
707 final String idxName;
709 final File tmpIdx;
711 PackIndex index;
713 RemotePack(final WalkRemoteObjectDatabase c, final String pn) {
714 final File objdir = local.getObjectsDirectory();
715 connection = c;
716 packName = pn;
717 idxName = packName.substring(0, packName.length() - 5) + ".idx";
719 String tn = idxName;
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 {
728 if (index != null)
729 return;
730 if (tmpIdx.isFile()) {
731 try {
732 index = PackIndex.open(tmpIdx);
733 return;
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));
744 try {
745 final FileOutputStream fos = new FileOutputStream(tmpIdx);
746 try {
747 final byte[] buf = new byte[2048];
748 int cnt;
749 while (!pm.isCancelled() && (cnt = s.in.read(buf)) >= 0) {
750 fos.write(buf, 0, cnt);
751 pm.update(cnt / 1024);
753 } finally {
754 fos.close();
756 } catch (IOException err) {
757 tmpIdx.delete();
758 throw err;
759 } finally {
760 s.in.close();
762 pm.endTask();
764 if (pm.isCancelled()) {
765 tmpIdx.delete();
766 return;
769 try {
770 index = PackIndex.open(tmpIdx);
771 } catch (IOException e) {
772 tmpIdx.delete();
773 throw e;
777 void downloadPack(final ProgressMonitor monitor) throws IOException {
778 final WalkRemoteObjectDatabase.FileStream s;
779 final IndexPack ip;
781 s = connection.open("pack/" + packName);
782 ip = IndexPack.create(local, s.in);
783 ip.setFixThin(false);
784 ip.index(monitor);
785 ip.renameAndOpenPack();