CapabilityComparator.compare violates contract

[mnlipp]

When running the resolver (bnd 6.4.0), I sometimes get

Exception during resolution.
java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
	at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
	at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
	at java.base/java.util.TimSort.sort(TimSort.java:254)
	at java.base/java.util.Arrays.sort(Arrays.java:1308)
	at java.base/java.util.stream.SortedOps$SizedRefSortingSink.end(SortedOps.java:353)
	at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:510)
	at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
	at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
	at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
	at java.base/java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:682)
	at biz.aQute.resolve.AbstractResolveContext.findProvidersFromRepositories(AbstractResolveContext.java:286)
	at biz.aQute.resolve.AbstractResolveContext.lambda$0(AbstractResolveContext.java:244)
	at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1228)
	at biz.aQute.resolve.AbstractResolveContext.findProviders0(AbstractResolveContext.java:213)
	at biz.aQute.resolve.AbstractResolveContext.findProviders(AbstractResolveContext.java:153)
	at biz.aQute.resolve.ResolveProcess$1.findProviders(ResolveProcess.java:151)
	at org.apache.felix.resolver.Candidates.populate(Candidates.java:208)
	at org.apache.felix.resolver.ResolverImpl.getInitialCandidates(ResolverImpl.java:543)
	at org.apache.felix.resolver.ResolverImpl.doResolve(ResolverImpl.java:432)
	at org.apache.felix.resolver.ResolverImpl.resolve(ResolverImpl.java:421)
	at org.apache.felix.resolver.ResolverImpl.resolve(ResolverImpl.java:375)
	at biz.aQute.resolve.BndResolver.resolve(BndResolver.java:32)
	at biz.aQute.resolve.ResolveProcess.resolveRequired(ResolveProcess.java:187)
	at biz.aQute.resolve.RunResolution.resolve(RunResolution.java:101)
	at org.bndtools.core.resolve.ResolveOperation.lambda$run$0(ResolveOperation.java:57)
	at org.bndtools.core.resolve.ResolveOperation.coordinate(ResolveOperation.java:96)
	at org.bndtools.core.resolve.ResolveOperation.run(ResolveOperation.java:51)
	at org.bndtools.core.resolve.ResolveJob.run(ResolveJob.java:89)
	at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63)

I've added this simple code to find out which capabilities cause the problem:

		this.capabilityComparator = new CapabilityComparator(log) {

			@Override
			public int compare(Capability o1, Capability o2) {
				if (super.compare(o1, o2) + super.compare(o2, o1) != 0) {
					System.out.println("Compare violates contract for " + o1 + " and " + o2);
				}
				return super.compare(o1, o2);
			}

		};

As it turns out, the capabilities causing the problem are osgi.ee;osgi.ee='JavaSE/compact1';version:Version='1.8.0' and osgi.ee;osgi.ee=JavaSE;version:Version='1.7.0'. The comparator returns inconsistent results when the arguments are swapped.

Knowing the resources, the problem is quite obvious:

			// 1. Framework bundle
			if (isSystemResource(res1))
				return -1;
			if (isSystemResource(res2))
				return +1;

If both arguments are framework bundles, the first is always considered smaller

[mnlipp]

It' more complicated. The CapabilityComparator does not ensure the transitivity of the relation ("The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.").

I've used this simple check (added to the code before the sorting in AbstractResolverContext.java:270). It inserts each element into a sorted list, checking that not only the element at the insertion point but also all subsequent elements are "greater" than the element to be inserted.

		LinkedList<Capability> caps = new LinkedList<>();
		for (Capability cap : set) {
			if (caps.isEmpty()) {
				caps.add(cap);
				continue;
			}
			int insPos = 0;
			boolean searching = true;
			for (Capability ref : caps) {
				int cmpRes = capabilityComparator.compare(ref, cap);
				if (searching) {
					if (cmpRes > 0) {
						searching = false;
					} else {
						insPos += 1;
					}
				} else {
					if (!(cmpRes > 0)) {
						String msg = "Inconsistent comparator: " + cap + " is smaller than " + caps.get(insPos)
							+ "but greater " + ref;
						log.log(LogService.LOG_ERROR, msg);
						System.out.println(msg);
					}
				}
			}
			if (searching) {
				caps.add(cap);
			} else {
				caps.add(insPos, cap);
			}
		}

Here's an example of a failure:

caps already has 24 (successfully inserted) elements. Now I insert

osgi.wiring.package;uses:='org.osgi.framework';bnd.hashes:List<Long>='2054177710,459075576,-1361742930,1955537649';bundle-symbolic-name='org.apache.felix.ipojo';bundle-version:Version='1.12.1';osgi.wiring.package='org.osgi.service.log';version:Version='1.3.0'

The comparator considers the element shown next (already in the list at index 11) to be "greater" (because the bundle version is lower):

osgi.wiring.package;uses:='org.osgi.framework';bnd.hashes:List<Long>='2054177710,459075576,-1361742930,1955537649';bundle-symbolic-name='org.apache.felix.ipojo';bundle-version:Version='1.6.4';osgi.wiring.package='org.osgi.service.log';version:Version='1.3.0'

However, the element shown next (which appears later in the list) is "smaller" than the element to be inserted, thus violating the assumption that everything beyond the bigger element at the insertion point must be bigger than the element to be inserted (note the difference in the bundle-symbolic-name):

osgi.wiring.package;uses:='org.osgi.framework';bnd.hashes:List<Long>='2054177710,459075576,-1361742930,1955537649';bundle-symbolic-name='org.apache.felix.org.apache.felix.ipojo';bundle-version:Version='0.8.0';osgi.wiring.package='org.osgi.service.log';version:Version='1.3.0'

While these differences won't break simple sorting algorithms (just for the record: I do know that there are better ones than creating a sorted list), this inconsistency makes Timsort fail.

[pkriens]

The comparator is as far as I can see having at least 4 or 5 serious bugs. I will fix this.

[pkriens]

Fixed in #5807