It isn't strictly necessary to validate every reference's target
object is reachable in the repository before advertising it to a
client. This is an expensive operation when there are thousands of
references, and its very unlikely that a reference uses a missing
object, because garbage collection proceeds from the references and
walks down through the graph. So trying to hide a dangling reference
from clients is relatively pointless.

Even if we are trying to avoid giving a client a corrupt repository,
this simple check isn't sufficient.  It is possible for a reference to
point to a valid commit, but that commit to have a missing blob in its
root tree.  This can be caused by staging a file into the index,
waiting several weeks, then committing that file while also racing
against a prune.  The prune may delete the blob, since its
modification time is more than 2 weeks ago, but retain the commit,
since its modification time is right now.

Such graph corruption is already caught during PackWriter as it
enumerates the graph from the client's want list and digs back
to the roots or common base.  Leave the reference validation also
for that same phase, where we know we have to parse the object to
support the enumeration.

Change-Id: Iee70ead0d3ed2d2fcc980417d09d7a69b05f5c2f
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

We don't actually need a Repository object here, just an ObjectReader
that can load content for us.  So change the API to depend on that.

However, this breaks the asCommit and asTag legacy translation methods
on RevCommit and RevTag, so we still have to keep the Repository
inside of RevWalk for those two types.  Hopefully we can drop those in
the future, and then drop the Repository off the RevWalk.

Change-Id: Iba983e48b663790061c43ae9ffbb77dfe6f4818e
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

This permits the repository implementation to know what its
alternates concept means, and avoids needing to expose finer details
about the ObjectDatabase to network code like the RefAdvertiser.

Change-Id: Ic6d173f300cb72de34519c7607cf7b0ff3ea6882
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

Don't copy and sort the set of references if they are passed through
in a RefMap or a SortedMap using the key's natural sort ordering.
Either map is already in the order we want to present the items
to the client in, so copying and sorting is a waste of local CPU
and memory.

Change-Id: I49ada7c1220e0fc2a163b9752c2b77525d9c82c1
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

This commit actually does three major changes to the way references
are handled within JGit.  Unfortunately they were easier to do as
a single massive commit than to break them up into smaller units.

Disambiguate symbolic references:
---------------------------------

  Reporting a symbolic reference such as HEAD as though it were
  any other normal reference like refs/heads/master causes subtle
  programming errors.  We have been bitten by this error on several
  occasions, as have some downstream applications written by myself.

  Instead of reporting HEAD as a reference whose name differs from
  its "original name", report it as an actual SymbolicRef object
  that the application can test the type and examine the target of.

  With this change, Ref is now an abstract type with different
  subclasses for the different types.

  In the classical example of "HEAD" being a symbolic reference to
  branch "refs/heads/master", the Repository.getAllRefs() method
  will now return:

      Map<String, Ref> all = repository.getAllRefs();
      SymbolicRef HEAD = (SymbolicRef) all.get("HEAD");
      ObjectIdRef master = (ObjectIdRef) all.get("refs/heads/master");

      assertSame(master,               HEAD.getTarget());
      assertSame(master.getObjectId(), HEAD.getObjectId());

      assertEquals("HEAD",              HEAD.getName());
      assertEquals("refs/heads/master", master.getName());

  A nice side-effect of this change is the storage type of the
  symbolic reference is no longer ambiguous with the storge type
  of the underlying reference it targets.  In the above example,
  if master was only available in the packed-refs file, then the
  following is also true:

      assertSame(Ref.Storage.LOOSE,  HEAD.getStorage());
      assertSame(Ref.Storage.PACKED, master.getStorage());

  (Prior to this change we returned the ambiguous storage of
   LOOSE_PACKED for HEAD, which was confusing since it wasn't
   actually true on disk).

  Another nice side-effect of this change is all intermediate
  symbolic references are preserved, and are therefore visible
  to the application when they walk the target chain.  We can
  now correctly inspect chains of symbolic references.

  As a result of this change the Ref.getOrigName() method has been
  removed from the API.  Applications should identify a symbolic
  reference by testing for isSymbolic() and not by using an arcane
  string comparsion between properties.

Abstract the RefDatabase storage:
---------------------------------

  RefDatabase is now abstract, similar to ObjectDatabase, and a
  new concrete implementation called RefDirectory is used for the
  traditional on-disk storage layout.  In the future we plan to
  support additional implementations, such as a pure in-memory
  RefDatabase for unit testing purposes.

Optimize RefDirectory:
----------------------

  The implementation of the in-memory reference cache, reading, and
  update routines has been completely rewritten.  Much of the code
  was heavily borrowed or cribbed from the prior implementation,
  so copyright notices have been left intact as much as possible.

  The RefDirectory cache no longer confuses symbolic references
  with normal references.  This permits the cache to resolve the
  value of a symbolic reference as late as possible, ensuring it
  is always current, without needing to maintain reverse pointers.

  The cache is now 2 sorted RefLists, rather than 3 HashMaps.
  Using sorted lists allows the implementation to reduce the
  in-memory footprint when storing many refs.  Using specialized
  types for the elements allows the code to avoid additional map
  lookups for auxiliary stat information.

  To improve scan time during getRefs(), the lists are returned via
  a copy-on-write contract.  Most callers of getRefs() do not modify
  the returned collections, so the copy-on-write semantics improves
  access on repositories with a large number of packed references.

  Iterator traversals of the returned Map<String,Ref> are performed
  using a simple merge-join of the two cache lists, ensuring we can
  perform the entire traversal in linear time as a function of the
  number of references: O(PackedRefs + LooseRefs).

  Scans of the loose reference space to update the cache run in
  O(LooseRefs log LooseRefs) time, as the directory contents
  are sorted before being merged against the in-memory cache.
  Since the majority of stable references are kept packed, there
  typically are only a handful of reference names to be sorted,
  so the sorting cost should not be very high.

  Locking is reduced during getRefs() by taking advantage of the
  copy-on-write semantics of the improved cache data structure.
  This permits concurrent readers to pull back references without
  blocking each other.  If there is contention updating the cache
  during a scan, one or more updates are simply skipped and will
  get picked up again in a future scan.

  Writing to the $GIT_DIR/packed-refs during reference delete is
  now fully atomic.  The file is locked, reparsed fresh, and written
  back out if a change is necessary.  This avoids all race conditions
  with concurrent external updates of the packed-refs file.

  The RefLogWriter class has been fully folded into RefDirectory
  and is therefore deleted.  Maintaining the reference's log is
  the responsiblity of the database implementation, and not all
  implementations will use java.io for access.

  Future work still remains to be done to abstract the ReflogReader
  class away from local disk IO.

Change-Id: I26b9287c45a4b2d2be35ba2849daa316f5eec85d
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

Change-Id: Iaa331a476e28cf2880df5607de36bc9f67d041df
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

By making this class and its methods public, and the actual writing
abstract, we can reuse this code for other formats like writing an
info/refs file for HTTP transports.

Change-Id: Id0e349c30a0f5a8c1527e0e7383b80243819d9c5
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

A few locations were doing OBJECT_ID_LENGTH * 2 on their own, as
the old STR_LEN constant wasn't visible.  Replace them with the
new public constant OBJECT_ID_STRING_LENGTH.

Change-Id: Id39bddb52de8c65bb097de042e9d4ed99598201f
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

Per CQ 3448 this is the initial contribution of the JGit project
to eclipse.org.  It is derived from the historical JGit repository
at commit 3a2dd9921c.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>