Fix false positives in hashing used by PathFilterGroup

The ByteArraySet failed to check the length of the entry correctly leading
to matches where no match should be.

Bug: 401249
Change-Id: I925bc48d9cafcdf13e1a797bb09fc2555eb270c5
Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
Accept Change-Id even if footer contains not well-formed entries

Instead of only looking for a Change-Id in the last section if it 
consists only of well-formed "key: value" lines replace the last
occurrence of a valid Change-Id line in the last section. Some tools
require footer lines e.g. without a colon.

Gerrit doesn't accept Change-Id lines in the footer if the Change-Id
line doesn't start at the beginning of the line.

Bug: 400818
Change-Id: Icce54872adc8c566994beea848448a2f7ca87085
Signed-off-by: Stefan Lay <stefan.lay@sap.com>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Merge "Accept Change-Id even if footer contains not well-formed entries" into stable-2.3
JGit v2.3.1.201302201838-r

Change-Id: I0d79873137ad4042ecc2a0210fe1f6305608b851
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Prepare 2.3.2-SNAPSHOT builds

Change-Id: I51a8a53194928416b1aef1f3fce0ce66aadceca4
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Merge branch 'stable-2.3'

* stable-2.3:
  Prepare 2.3.2-SNAPSHOT builds
  JGit v2.3.1.201302201838-r
  Accept Change-Id even if footer contains not well-formed entries
  Fix false positives in hashing used by PathFilterGroup

Change-Id: I5882aa3b482d6bcd40a45bed51e5ab03f018a5bc
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Fix off by one error in PackReverseIndex.

The last 32bit offset is at Integer.MAX_VALUE.

Change-Id: Idee8be3c7887e1d0c8339ff94aceff36dbf000db
Improve the documentation of the ByteArraySet used by PathFilterGroup

Change-Id: I2ba7a67e8e1596aa6c33a9caddee03a6be48f008
Implement recursive merge strategy

Extend ResolveMerger with RecursiveMerger to merge two tips
that have up to 200 bases.

Bug: 380314
CQ: 6854
Change-Id: I6292bb7bda55c0242a448a94956f2d6a94fddbaa
Also-by: Christian Halstrick <christian.halstrick@sap.com>
Signed-off-by: Chris Aniszczyk <zx@twitter.com>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Deploy Maven artifacts to Eclipse Nexus repository

Bug: 401469
Bug: 401470
Change-Id: I4901dc208fe8f9e4055d27ab7e0ced979fd234f5
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Update last release version to 2.3.1.201302201838-r

Change-Id: I9c6d774526028e56707e15e80370460d964de76e
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Performance fixes in DateRevQueue

When a lot of commits are added to DateRevQueue, the
sort-on-insertion approach is very heavy on CPU cycles.

One approach to fix this was made by Dave Borowitz:
https://git.eclipse.org/r/#/c/5491/

But using Java's PriorityQueue seems to have brought some
extra overhead, and the desired performance could not be
reached.

This fix takes another approach to the insertion problem,
without changing the expected behaviour or bringing extra
memory overhead:

If we detect over 1000 commits in the DateRevQueue, a
"seek-index" is rebuilt every 1000th added commit.

The index keeps track of every 100th commit in the
DateRevQueue. During insertions, it will be used for a
preliminary scanning (binary search) of the queue, with
the intention of helping add() find a good starting point
to start walking from. After finding this starting point,
add() will step commit-by-commit until the correct
insertion place in the queue is found (today, the queue
is expected to be sorted at all times).

When applied to repositories with many refs, this approach
has proven to bring huge performance gains and scales quite
well.

For instance, in a repository with close to 80000 refs,
we could cut down the time a typical Gerrit replication
of 1 commit would take (just a push from JGit's point of
view) from 32sec down to 3.5sec.

Below you see some typical times to add a specific amount
of commits (with random commit times) to the DateRevQueue
and the difference the preliminary seek-index makes:

Commits | Index | No Index
   1024     8ms        8ms
   2048    13ms        9ms
   4096     5ms       59ms
   8192    11ms      595ms
  16384    22ms     3058ms
  32768    64ms    13811ms
  65536   201ms    62677ms
 131072   783ms   331585ms

Only one extra reference is needed for every 100 inserted
commits (and only when we see more than 1000 commits in
the queue), so the memory overhead should be negligible.

Various index-stepping values were tested, and 100 seemed to
scale very well and be effective from start.

In the future, it should probably be dynamic and based on
the number of refs in the queue, but this should serve well
as a starting point.

Note: While other fundamentally different data structures may
be more suitable, the DateRevQueue is extremely central to
many of the Git core operations. This approach was chosen,
since the effect of the patch is easy to predict in conjuction
with the current implementation. A totally new data structure
will make it harder to predict behaviour in many common and
uncommon cases (in terms of breaking ties, memory usage, cost
when using few elements, object creation/disposing overhead,
etc).

Change-Id: Ie7b99f40eacf6324bfb4716d82073adeda64d10f
Merge "Performance fixes in DateRevQueue"
Fix while boundries in DateRevQueue.add()

In add(), "low" will never equals "first". This fact
should be reflected in the code.

Change-Id: I5cab51374e67bd2d3301e5d9dac47c4259b5e562
Include supported extensions in PackFile constructor.

Previously a PackFile class was assumed to only support a .pack and .idx
file. Update the constructor to enumerate the supported extensions for
the pack file. This will allow the bitmap code to only be executed if
the bitmap extension file is known to exist.

Change-Id: Ie59041dffec5f60d7ea2771026ffd945106bd4bf
Merge "Improve the documentation of the ByteArraySet used by PathFilterGroup"
Fix RefUpdate performance for existing Refs

No longer invoke the expensive RefDatabase.isNameConflicting() check on
updating existing refs, reducing batch ref update time by ~97%.

The RefDirectory implementation of isNameConflicting() is quite
slow (it has to do an expensive loose-ref scan) but it's only necessary
to perform this check on ref update if the ref is being *created* - if
the ref already exists, we can already guarantee that it does not
conflict with any other refs.

C-Git seems to use a similar condition before making the
is_refname_available() check:

https://github.com/git/git/blob/v1.8.1.4/refs.c#L1660-L1670

As an example of the effects on performance, here's a simple timing
experiment using The BFG to remove one file from the JGit repo:

---
$ wget http://repo1.maven.org/maven2/com/madgag/bfg-repo-cleaner/1.0.1/bfg-1.0.1.jar
$ git clone --mirror https://git.eclipse.org/r/p/jgit/jgit.git
$ java -jar bfg-1.0.1.jar -D make_jgit.sh jgit.git
....
Updating references:    100% (5760/5760)
...Ref update completed in 148,949 ms.

BFG run is complete!
---

The execution time for the run is completely dominated by the batch ref
update at the end. Repeating the experiment with BFG v1.0.2 (using JGit
patched with this change), the refs update is dramatically reduced:

---
Updating references:    100% (5760/5760)
...Ref update completed in 4,327 ms.
---

Change-Id: I9057bc4ee22f9cc269b1cc00c493841c71527cd6
Fix corrupted CloneCommand bare-repo fetch-refspec (#402031)

CloneCommand has been creating fetch refspecs like this on bare clones:

[remote "origin"]
        url = ssh://example.com/my-repo.git
        fetch = +refs/heads/*:refs/heads//*

As you can see, the destination ref pattern has a superfluous slash.

It looks like this behaviour has always been the case for CloneCommand,
at least since cc2197ed when code catering to bare-clone fetch refspecs
was added. That was released with JGit v1.0 almost 2 years ago, so
there will probably be some bare repos in the wild which will have been
cloned with JGit and have these corrupted refspecs.

The effect of the corrupted fetch refspec is quite interesting. Up to
and including JGit 2.0, the corrupt refspec was tolerated and fetches
would work as intended with no indication to the user that anything was
amiss. With JGit 2.1, a change was introduced which made JGit less
tolerant, and fetches now attempt to update the non-existing ref
"refs/heads//master". No exception is raised, but the real ref -
"refs/heads/master" - is not updated.

This behaviour was noticed by a user of Agit (which does bare clones by
default and recently updated from JGit v2.0 to v2.2), reported here:

https://github.com/rtyley/agit/issues/92


If you run C-Git fetch on a bare-repo cloned by JGit, it flat-out
rejects the refspec (checked against v1.7.10.4):

fatal: Invalid refspec '+refs/heads/*:refs/heads//*'

Incidentally, C-Git does not create an explicit fetch refspec at all
when performing a bare clone - the full remote config generated by C-Git
looks like this:

[remote "origin"]
        url = ssh://example.com/my-repo.git

Using JGit on such a repository works fine, so omitting the fetch
refspec entirely is also an option.

Change-Id: I14b0d359dc69b8908f68e02cea7a756ac34bf881
Remove the unused method PackFile.hasExt().

It will be used in a future change, so just include it with that change.

Change-Id: I7db28d86f8e8b282a403acd9a4c4defaae828f94
Merge "Remove the unused method PackFile.hasExt()."