001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019package org.eclipse.aether.util.graph.transformer; 020 021import java.util.*; 022 023import org.eclipse.aether.RepositoryException; 024import org.eclipse.aether.RepositorySystemSession; 025import org.eclipse.aether.artifact.Artifact; 026import org.eclipse.aether.collection.DependencyGraphTransformationContext; 027import org.eclipse.aether.collection.DependencyGraphTransformer; 028import org.eclipse.aether.graph.DefaultDependencyNode; 029import org.eclipse.aether.graph.Dependency; 030import org.eclipse.aether.graph.DependencyNode; 031import org.eclipse.aether.util.artifact.ArtifactIdUtils; 032 033import static java.util.Objects.requireNonNull; 034 035/** 036 * A dependency graph transformer that resolves version and scope conflicts among dependencies. For a given set of 037 * conflicting nodes, one node will be chosen as the winner and the other nodes are removed from the dependency graph. 038 * The exact rules by which a winning node and its effective scope are determined are controlled by user-supplied 039 * implementations of {@link VersionSelector}, {@link ScopeSelector}, {@link OptionalitySelector} and 040 * {@link ScopeDeriver}. 041 * <p> 042 * By default, this graph transformer will turn the dependency graph into a tree without duplicate artifacts. Using the 043 * configuration property {@link #CONFIG_PROP_VERBOSE}, a verbose mode can be enabled where the graph is still turned 044 * into a tree but all nodes participating in a conflict are retained. The nodes that were rejected during conflict 045 * resolution have no children and link back to the winner node via the {@link #NODE_DATA_WINNER} key in their custom 046 * data. Additionally, the keys {@link #NODE_DATA_ORIGINAL_SCOPE} and {@link #NODE_DATA_ORIGINAL_OPTIONALITY} are used 047 * to store the original scope and optionality of each node. Obviously, the resulting dependency tree is not suitable 048 * for artifact resolution unless a filter is employed to exclude the duplicate dependencies. 049 * <p> 050 * This transformer will query the keys {@link TransformationContextKeys#CONFLICT_IDS}, 051 * {@link TransformationContextKeys#SORTED_CONFLICT_IDS}, {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} for 052 * existing information about conflict ids. In absence of this information, it will automatically invoke the 053 * {@link ConflictIdSorter} to calculate it. 054 */ 055public final class ConflictResolver implements DependencyGraphTransformer { 056 057 /** 058 * The key in the repository session's {@link org.eclipse.aether.RepositorySystemSession#getConfigProperties() 059 * configuration properties} used to store a {@link Boolean} flag controlling the transformer's verbose mode. 060 * Accepted values are {@link Boolean} type, {@link String} type (where "true" would be interpreted as {@code true} 061 * or {@link Verbosity} enum instances. 062 */ 063 public static final String CONFIG_PROP_VERBOSE = "aether.conflictResolver.verbose"; 064 065 /** 066 * The enum representing verbosity levels of conflict resolver. 067 * 068 * @since 1.9.8 069 */ 070 public enum Verbosity { 071 /** 072 * Verbosity level to be used in all "common" resolving use cases (ie. dependencies to build class path). The 073 * {@link ConflictResolver} in this mode will trim down the graph to the barest minimum: will not leave 074 * any conflicting node in place, hence no conflicts will be present in transformed graph either. 075 */ 076 NONE, 077 078 /** 079 * Verbosity level to be used in "analyze" resolving use cases (ie. dependency convergence calculations). The 080 * {@link ConflictResolver} in this mode will remove any redundant collected nodes, in turn it will leave one 081 * with recorded conflicting information. This mode corresponds to "classic verbose" mode when 082 * {@link #CONFIG_PROP_VERBOSE} was set to {@code true}. Obviously, the resulting dependency tree is not 083 * suitable for artifact resolution unless a filter is employed to exclude the duplicate dependencies. 084 */ 085 STANDARD, 086 087 /** 088 * Verbosity level to be used in "analyze" resolving use cases (ie. dependency convergence calculations). The 089 * {@link ConflictResolver} in this mode will not remove any collected node, in turn it will record on all 090 * eliminated nodes the conflicting information. Obviously, the resulting dependency tree is not suitable 091 * for artifact resolution unless a filter is employed to exclude the duplicate dependencies. 092 */ 093 FULL 094 } 095 096 /** 097 * Helper method that uses {@link RepositorySystemSession} and {@link #CONFIG_PROP_VERBOSE} key to figure out 098 * current {@link Verbosity}: if {@link Boolean} or {@code String} found, returns {@link Verbosity#STANDARD} 099 * or {@link Verbosity#NONE}, depending on value (string is parsed with {@link Boolean#parseBoolean(String)} 100 * for {@code true} or {@code false} correspondingly. This is to retain "existing" behavior, where the config 101 * key accepted only these values. 102 * Since 1.9.8 release, this key may contain {@link Verbosity} enum instance as well, in which case that instance 103 * is returned. 104 * This method never returns {@code null}. 105 */ 106 private static Verbosity getVerbosity(RepositorySystemSession session) { 107 final Object verbosityValue = session.getConfigProperties().get(CONFIG_PROP_VERBOSE); 108 if (verbosityValue instanceof Boolean) { 109 return (Boolean) verbosityValue ? Verbosity.STANDARD : Verbosity.NONE; 110 } else if (verbosityValue instanceof String) { 111 return Boolean.parseBoolean(verbosityValue.toString()) ? Verbosity.STANDARD : Verbosity.NONE; 112 } else if (verbosityValue instanceof Verbosity) { 113 return (Verbosity) verbosityValue; 114 } else if (verbosityValue != null) { 115 throw new IllegalArgumentException("Unsupported Verbosity configuration: " + verbosityValue); 116 } 117 return Verbosity.NONE; 118 } 119 120 /** 121 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which a reference to the 122 * {@link DependencyNode} which has won the conflict is stored. 123 */ 124 public static final String NODE_DATA_WINNER = "conflict.winner"; 125 126 /** 127 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which the scope of the 128 * dependency before scope derivation and conflict resolution is stored. 129 */ 130 public static final String NODE_DATA_ORIGINAL_SCOPE = "conflict.originalScope"; 131 132 /** 133 * The key in the dependency node's {@link DependencyNode#getData() custom data} under which the optional flag of 134 * the dependency before derivation and conflict resolution is stored. 135 */ 136 public static final String NODE_DATA_ORIGINAL_OPTIONALITY = "conflict.originalOptionality"; 137 138 private final VersionSelector versionSelector; 139 140 private final ScopeSelector scopeSelector; 141 142 private final ScopeDeriver scopeDeriver; 143 144 private final OptionalitySelector optionalitySelector; 145 146 /** 147 * Creates a new conflict resolver instance with the specified hooks. 148 * 149 * @param versionSelector The version selector to use, must not be {@code null}. 150 * @param scopeSelector The scope selector to use, must not be {@code null}. 151 * @param optionalitySelector The optionality selector ot use, must not be {@code null}. 152 * @param scopeDeriver The scope deriver to use, must not be {@code null}. 153 */ 154 public ConflictResolver( 155 VersionSelector versionSelector, 156 ScopeSelector scopeSelector, 157 OptionalitySelector optionalitySelector, 158 ScopeDeriver scopeDeriver) { 159 this.versionSelector = requireNonNull(versionSelector, "version selector cannot be null"); 160 this.scopeSelector = requireNonNull(scopeSelector, "scope selector cannot be null"); 161 this.optionalitySelector = requireNonNull(optionalitySelector, "optionality selector cannot be null"); 162 this.scopeDeriver = requireNonNull(scopeDeriver, "scope deriver cannot be null"); 163 } 164 165 public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context) 166 throws RepositoryException { 167 requireNonNull(node, "node cannot be null"); 168 requireNonNull(context, "context cannot be null"); 169 List<?> sortedConflictIds = (List<?>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS); 170 if (sortedConflictIds == null) { 171 ConflictIdSorter sorter = new ConflictIdSorter(); 172 sorter.transformGraph(node, context); 173 174 sortedConflictIds = (List<?>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS); 175 } 176 177 @SuppressWarnings("unchecked") 178 Map<String, Object> stats = (Map<String, Object>) context.get(TransformationContextKeys.STATS); 179 long time1 = System.nanoTime(); 180 181 @SuppressWarnings("unchecked") 182 Collection<Collection<?>> conflictIdCycles = 183 (Collection<Collection<?>>) context.get(TransformationContextKeys.CYCLIC_CONFLICT_IDS); 184 if (conflictIdCycles == null) { 185 throw new RepositoryException("conflict id cycles have not been identified"); 186 } 187 188 Map<?, ?> conflictIds = (Map<?, ?>) context.get(TransformationContextKeys.CONFLICT_IDS); 189 if (conflictIds == null) { 190 throw new RepositoryException("conflict groups have not been identified"); 191 } 192 193 Map<Object, Collection<Object>> cyclicPredecessors = new HashMap<>(); 194 for (Collection<?> cycle : conflictIdCycles) { 195 for (Object conflictId : cycle) { 196 Collection<Object> predecessors = cyclicPredecessors.computeIfAbsent(conflictId, k -> new HashSet<>()); 197 predecessors.addAll(cycle); 198 } 199 } 200 201 State state = new State(node, conflictIds, sortedConflictIds.size(), context); 202 for (Iterator<?> it = sortedConflictIds.iterator(); it.hasNext(); ) { 203 Object conflictId = it.next(); 204 205 // reset data structures for next graph walk 206 state.prepare(conflictId, cyclicPredecessors.get(conflictId)); 207 208 // find nodes with the current conflict id and while walking the graph (more deeply), nuke leftover losers 209 gatherConflictItems(node, state); 210 211 // now that we know the min depth of the parents, update depth of conflict items 212 state.finish(); 213 214 // earlier runs might have nuked all parents of the current conflict id, so it might not exist anymore 215 if (!state.items.isEmpty()) { 216 ConflictContext ctx = state.conflictCtx; 217 state.versionSelector.selectVersion(ctx); 218 if (ctx.winner == null) { 219 throw new RepositoryException("conflict resolver did not select winner among " + state.items); 220 } 221 DependencyNode winner = ctx.winner.node; 222 223 state.scopeSelector.selectScope(ctx); 224 if (Verbosity.NONE != state.verbosity) { 225 winner.setData( 226 NODE_DATA_ORIGINAL_SCOPE, winner.getDependency().getScope()); 227 } 228 winner.setScope(ctx.scope); 229 230 state.optionalitySelector.selectOptionality(ctx); 231 if (Verbosity.NONE != state.verbosity) { 232 winner.setData( 233 NODE_DATA_ORIGINAL_OPTIONALITY, 234 winner.getDependency().isOptional()); 235 } 236 winner.setOptional(ctx.optional); 237 238 removeLosers(state); 239 } 240 241 // record the winner so we can detect leftover losers during future graph walks 242 state.winner(); 243 244 // in case of cycles, trigger final graph walk to ensure all leftover losers are gone 245 if (!it.hasNext() && !conflictIdCycles.isEmpty() && state.conflictCtx.winner != null) { 246 DependencyNode winner = state.conflictCtx.winner.node; 247 state.prepare(state, null); 248 gatherConflictItems(winner, state); 249 } 250 } 251 252 if (stats != null) { 253 long time2 = System.nanoTime(); 254 stats.put("ConflictResolver.totalTime", time2 - time1); 255 stats.put("ConflictResolver.conflictItemCount", state.totalConflictItems); 256 } 257 258 return node; 259 } 260 261 private boolean gatherConflictItems(DependencyNode node, State state) throws RepositoryException { 262 Object conflictId = state.conflictIds.get(node); 263 if (state.currentId.equals(conflictId)) { 264 // found it, add conflict item (if not already done earlier by another path) 265 state.add(node); 266 // we don't recurse here so we might miss losers beneath us, those will be nuked during future walks below 267 } else if (state.loser(node, conflictId)) { 268 // found a leftover loser (likely in a cycle) of an already processed conflict id, tell caller to nuke it 269 return false; 270 } else if (state.push(node, conflictId)) { 271 // found potential parent, no cycle and not visisted before with the same derived scope, so recurse 272 for (Iterator<DependencyNode> it = node.getChildren().iterator(); it.hasNext(); ) { 273 DependencyNode child = it.next(); 274 if (!gatherConflictItems(child, state)) { 275 it.remove(); 276 } 277 } 278 state.pop(); 279 } 280 return true; 281 } 282 283 private static void removeLosers(State state) { 284 ConflictItem winner = state.conflictCtx.winner; 285 String winnerArtifactId = ArtifactIdUtils.toId(winner.node.getArtifact()); 286 List<DependencyNode> previousParent = null; 287 ListIterator<DependencyNode> childIt = null; 288 HashSet<String> toRemoveIds = new HashSet<>(); 289 for (ConflictItem item : state.items) { 290 if (item == winner) { 291 continue; 292 } 293 if (item.parent != previousParent) { 294 childIt = item.parent.listIterator(); 295 previousParent = item.parent; 296 } 297 while (childIt.hasNext()) { 298 DependencyNode child = childIt.next(); 299 if (child == item.node) { 300 // NONE: just remove it and done 301 if (Verbosity.NONE == state.verbosity) { 302 childIt.remove(); 303 break; 304 } 305 306 // STANDARD: doing extra bookkeeping to select "which nodes to remove" 307 if (Verbosity.STANDARD == state.verbosity) { 308 String childArtifactId = ArtifactIdUtils.toId(child.getArtifact()); 309 // if two IDs are equal, it means "there is nearest", not conflict per se. 310 // In that case we do NOT allow this child to be removed (but remove others) 311 // and this keeps us safe from iteration (and in general, version) ordering 312 // as we explicitly leave out ID that is "nearest found" state. 313 // 314 // This tackles version ranges mostly, where ranges are turned into list of 315 // several nodes in collector (as many were discovered, ie. from metadata), and 316 // old code would just "mark" the first hit as conflict, and remove the rest, 317 // even if rest could contain "more suitable" version, that is not conflicting/diverging. 318 // This resulted in verbose mode transformed tree, that was misrepresenting things 319 // for dependency convergence calculations: it represented state like parent node 320 // depends on "wrong" version (diverge), while "right" version was present (but removed) 321 // as well, as it was contained in parents version range. 322 if (!Objects.equals(winnerArtifactId, childArtifactId)) { 323 toRemoveIds.add(childArtifactId); 324 } 325 } 326 327 // FULL: just record the facts 328 DependencyNode loser = new DefaultDependencyNode(child); 329 loser.setData(NODE_DATA_WINNER, winner.node); 330 loser.setData( 331 NODE_DATA_ORIGINAL_SCOPE, loser.getDependency().getScope()); 332 loser.setData( 333 NODE_DATA_ORIGINAL_OPTIONALITY, 334 loser.getDependency().isOptional()); 335 loser.setScope(item.getScopes().iterator().next()); 336 loser.setChildren(Collections.emptyList()); 337 childIt.set(loser); 338 item.node = loser; 339 break; 340 } 341 } 342 } 343 344 // 2nd pass to apply "standard" verbosity: leaving only 1 loser, but with care 345 if (Verbosity.STANDARD == state.verbosity && !toRemoveIds.isEmpty()) { 346 previousParent = null; 347 for (ConflictItem item : state.items) { 348 if (item == winner) { 349 continue; 350 } 351 if (item.parent != previousParent) { 352 childIt = item.parent.listIterator(); 353 previousParent = item.parent; 354 } 355 while (childIt.hasNext()) { 356 DependencyNode child = childIt.next(); 357 if (child == item.node) { 358 String childArtifactId = ArtifactIdUtils.toId(child.getArtifact()); 359 if (toRemoveIds.contains(childArtifactId) && item.parent.size() > 1) { 360 childIt.remove(); 361 } 362 break; 363 } 364 } 365 } 366 } 367 368 // there might still be losers beneath the winner (e.g. in case of cycles) 369 // those will be nuked during future graph walks when we include the winner in the recursion 370 } 371 372 static final class NodeInfo { 373 374 /** 375 * The smallest depth at which the node was seen, used for "the" depth of its conflict items. 376 */ 377 int minDepth; 378 379 /** 380 * The set of derived scopes the node was visited with, used to check whether an already seen node needs to be 381 * revisited again in context of another scope. To conserve memory, we start with {@code String} and update to 382 * {@code Set<String>} if needed. 383 */ 384 Object derivedScopes; 385 386 /** 387 * The set of derived optionalities the node was visited with, used to check whether an already seen node needs 388 * to be revisited again in context of another optionality. To conserve memory, encoded as bit field (bit 0 -> 389 * optional=false, bit 1 -> optional=true). 390 */ 391 int derivedOptionalities; 392 393 /** 394 * The conflict items which are immediate children of the node, used to easily update those conflict items after 395 * a new parent scope/optionality was encountered. 396 */ 397 List<ConflictItem> children; 398 399 static final int CHANGE_SCOPE = 0x01; 400 401 static final int CHANGE_OPTIONAL = 0x02; 402 403 private static final int OPT_FALSE = 0x01; 404 405 private static final int OPT_TRUE = 0x02; 406 407 NodeInfo(int depth, String derivedScope, boolean optional) { 408 minDepth = depth; 409 derivedScopes = derivedScope; 410 derivedOptionalities = optional ? OPT_TRUE : OPT_FALSE; 411 } 412 413 @SuppressWarnings("unchecked") 414 int update(int depth, String derivedScope, boolean optional) { 415 if (depth < minDepth) { 416 minDepth = depth; 417 } 418 int changes; 419 if (derivedScopes.equals(derivedScope)) { 420 changes = 0; 421 } else if (derivedScopes instanceof Collection) { 422 changes = ((Collection<String>) derivedScopes).add(derivedScope) ? CHANGE_SCOPE : 0; 423 } else { 424 Collection<String> scopes = new HashSet<>(); 425 scopes.add((String) derivedScopes); 426 scopes.add(derivedScope); 427 derivedScopes = scopes; 428 changes = CHANGE_SCOPE; 429 } 430 int bit = optional ? OPT_TRUE : OPT_FALSE; 431 if ((derivedOptionalities & bit) == 0) { 432 derivedOptionalities |= bit; 433 changes |= CHANGE_OPTIONAL; 434 } 435 return changes; 436 } 437 438 void add(ConflictItem item) { 439 if (children == null) { 440 children = new ArrayList<>(1); 441 } 442 children.add(item); 443 } 444 } 445 446 final class State { 447 448 /** 449 * The conflict id currently processed. 450 */ 451 Object currentId; 452 453 /** 454 * Stats counter. 455 */ 456 int totalConflictItems; 457 458 /** 459 * Flag whether we should keep losers in the graph to enable visualization/troubleshooting of conflicts. 460 */ 461 final Verbosity verbosity; 462 463 /** 464 * A mapping from conflict id to winner node, helps to recognize nodes that have their effective 465 * scope&optionality set or are leftovers from previous removals. 466 */ 467 final Map<Object, DependencyNode> resolvedIds; 468 469 /** 470 * The set of conflict ids which could apply to ancestors of nodes with the current conflict id, used to avoid 471 * recursion early on. This is basically a superset of the key set of resolvedIds, the additional ids account 472 * for cyclic dependencies. 473 */ 474 final Collection<Object> potentialAncestorIds; 475 476 /** 477 * The output from the conflict marker 478 */ 479 final Map<?, ?> conflictIds; 480 481 /** 482 * The conflict items we have gathered so far for the current conflict id. 483 */ 484 final List<ConflictItem> items; 485 486 /** 487 * The (conceptual) mapping from nodes to extra infos, technically keyed by the node's child list which better 488 * captures the identity of a node since we're basically concerned with effects towards children. 489 */ 490 final Map<List<DependencyNode>, NodeInfo> infos; 491 492 /** 493 * The set of nodes on the DFS stack to detect cycles, technically keyed by the node's child list to match the 494 * dirty graph structure produced by the dependency collector for cycles. 495 */ 496 final Map<List<DependencyNode>, Object> stack; 497 498 /** 499 * The stack of parent nodes. 500 */ 501 final List<DependencyNode> parentNodes; 502 503 /** 504 * The stack of derived scopes for parent nodes. 505 */ 506 final List<String> parentScopes; 507 508 /** 509 * The stack of derived optional flags for parent nodes. 510 */ 511 final List<Boolean> parentOptionals; 512 513 /** 514 * The stack of node infos for parent nodes, may contain {@code null} which is used to disable creating new 515 * conflict items when visiting their parent again (conflict items are meant to be unique by parent-node combo). 516 */ 517 final List<NodeInfo> parentInfos; 518 519 /** 520 * The conflict context passed to the version/scope/optionality selectors, updated as we move along rather than 521 * recreated to avoid tmp objects. 522 */ 523 final ConflictContext conflictCtx; 524 525 /** 526 * The scope context passed to the scope deriver, updated as we move along rather than recreated to avoid tmp 527 * objects. 528 */ 529 final ScopeContext scopeCtx; 530 531 /** 532 * The effective version selector, i.e. after initialization. 533 */ 534 final VersionSelector versionSelector; 535 536 /** 537 * The effective scope selector, i.e. after initialization. 538 */ 539 final ScopeSelector scopeSelector; 540 541 /** 542 * The effective scope deriver, i.e. after initialization. 543 */ 544 final ScopeDeriver scopeDeriver; 545 546 /** 547 * The effective optionality selector, i.e. after initialization. 548 */ 549 final OptionalitySelector optionalitySelector; 550 551 State( 552 DependencyNode root, 553 Map<?, ?> conflictIds, 554 int conflictIdCount, 555 DependencyGraphTransformationContext context) 556 throws RepositoryException { 557 this.conflictIds = conflictIds; 558 this.verbosity = getVerbosity(context.getSession()); 559 potentialAncestorIds = new HashSet<>(conflictIdCount * 2); 560 resolvedIds = new HashMap<>(conflictIdCount * 2); 561 items = new ArrayList<>(256); 562 infos = new IdentityHashMap<>(64); 563 stack = new IdentityHashMap<>(64); 564 parentNodes = new ArrayList<>(64); 565 parentScopes = new ArrayList<>(64); 566 parentOptionals = new ArrayList<>(64); 567 parentInfos = new ArrayList<>(64); 568 conflictCtx = new ConflictContext(root, conflictIds, items); 569 scopeCtx = new ScopeContext(null, null); 570 versionSelector = ConflictResolver.this.versionSelector.getInstance(root, context); 571 scopeSelector = ConflictResolver.this.scopeSelector.getInstance(root, context); 572 scopeDeriver = ConflictResolver.this.scopeDeriver.getInstance(root, context); 573 optionalitySelector = ConflictResolver.this.optionalitySelector.getInstance(root, context); 574 } 575 576 void prepare(Object conflictId, Collection<Object> cyclicPredecessors) { 577 currentId = conflictId; 578 conflictCtx.conflictId = conflictId; 579 conflictCtx.winner = null; 580 conflictCtx.scope = null; 581 conflictCtx.optional = null; 582 items.clear(); 583 infos.clear(); 584 if (cyclicPredecessors != null) { 585 potentialAncestorIds.addAll(cyclicPredecessors); 586 } 587 } 588 589 void finish() { 590 List<DependencyNode> previousParent = null; 591 int previousDepth = 0; 592 totalConflictItems += items.size(); 593 for (ListIterator<ConflictItem> iterator = items.listIterator(items.size()); iterator.hasPrevious(); ) { 594 ConflictItem item = iterator.previous(); 595 if (item.parent == previousParent) { 596 item.depth = previousDepth; 597 } else if (item.parent != null) { 598 previousParent = item.parent; 599 NodeInfo info = infos.get(previousParent); 600 previousDepth = info.minDepth + 1; 601 item.depth = previousDepth; 602 } 603 } 604 potentialAncestorIds.add(currentId); 605 } 606 607 void winner() { 608 resolvedIds.put(currentId, (conflictCtx.winner != null) ? conflictCtx.winner.node : null); 609 } 610 611 boolean loser(DependencyNode node, Object conflictId) { 612 DependencyNode winner = resolvedIds.get(conflictId); 613 return winner != null && winner != node; 614 } 615 616 boolean push(DependencyNode node, Object conflictId) throws RepositoryException { 617 if (conflictId == null) { 618 if (node.getDependency() != null) { 619 if (node.getData().get(NODE_DATA_WINNER) != null) { 620 return false; 621 } 622 throw new RepositoryException("missing conflict id for node " + node); 623 } 624 } else if (!potentialAncestorIds.contains(conflictId)) { 625 return false; 626 } 627 628 List<DependencyNode> graphNode = node.getChildren(); 629 if (stack.put(graphNode, Boolean.TRUE) != null) { 630 return false; 631 } 632 633 int depth = depth(); 634 String scope = deriveScope(node, conflictId); 635 boolean optional = deriveOptional(node, conflictId); 636 NodeInfo info = infos.get(graphNode); 637 if (info == null) { 638 info = new NodeInfo(depth, scope, optional); 639 infos.put(graphNode, info); 640 parentInfos.add(info); 641 parentNodes.add(node); 642 parentScopes.add(scope); 643 parentOptionals.add(optional); 644 } else { 645 int changes = info.update(depth, scope, optional); 646 if (changes == 0) { 647 stack.remove(graphNode); 648 return false; 649 } 650 parentInfos.add(null); // disable creating new conflict items, we update the existing ones below 651 parentNodes.add(node); 652 parentScopes.add(scope); 653 parentOptionals.add(optional); 654 if (info.children != null) { 655 if ((changes & NodeInfo.CHANGE_SCOPE) != 0) { 656 ListIterator<ConflictItem> itemIterator = info.children.listIterator(info.children.size()); 657 while (itemIterator.hasPrevious()) { 658 ConflictItem item = itemIterator.previous(); 659 String childScope = deriveScope(item.node, null); 660 item.addScope(childScope); 661 } 662 } 663 if ((changes & NodeInfo.CHANGE_OPTIONAL) != 0) { 664 ListIterator<ConflictItem> itemIterator = info.children.listIterator(info.children.size()); 665 while (itemIterator.hasPrevious()) { 666 ConflictItem item = itemIterator.previous(); 667 boolean childOptional = deriveOptional(item.node, null); 668 item.addOptional(childOptional); 669 } 670 } 671 } 672 } 673 674 return true; 675 } 676 677 void pop() { 678 int last = parentInfos.size() - 1; 679 parentInfos.remove(last); 680 parentScopes.remove(last); 681 parentOptionals.remove(last); 682 DependencyNode node = parentNodes.remove(last); 683 stack.remove(node.getChildren()); 684 } 685 686 void add(DependencyNode node) throws RepositoryException { 687 DependencyNode parent = parent(); 688 if (parent == null) { 689 ConflictItem item = newConflictItem(parent, node); 690 items.add(item); 691 } else { 692 NodeInfo info = parentInfos.get(parentInfos.size() - 1); 693 if (info != null) { 694 ConflictItem item = newConflictItem(parent, node); 695 info.add(item); 696 items.add(item); 697 } 698 } 699 } 700 701 private ConflictItem newConflictItem(DependencyNode parent, DependencyNode node) throws RepositoryException { 702 return new ConflictItem(parent, node, deriveScope(node, null), deriveOptional(node, null)); 703 } 704 705 private int depth() { 706 return parentNodes.size(); 707 } 708 709 private DependencyNode parent() { 710 int size = parentNodes.size(); 711 return (size <= 0) ? null : parentNodes.get(size - 1); 712 } 713 714 private String deriveScope(DependencyNode node, Object conflictId) throws RepositoryException { 715 if ((node.getManagedBits() & DependencyNode.MANAGED_SCOPE) != 0 716 || (conflictId != null && resolvedIds.containsKey(conflictId))) { 717 return scope(node.getDependency()); 718 } 719 720 int depth = parentNodes.size(); 721 scopes(depth, node.getDependency()); 722 if (depth > 0) { 723 scopeDeriver.deriveScope(scopeCtx); 724 } 725 return scopeCtx.derivedScope; 726 } 727 728 private void scopes(int parent, Dependency child) { 729 scopeCtx.parentScope = (parent > 0) ? parentScopes.get(parent - 1) : null; 730 scopeCtx.derivedScope = scope(child); 731 scopeCtx.childScope = scope(child); 732 } 733 734 private String scope(Dependency dependency) { 735 return (dependency != null) ? dependency.getScope() : null; 736 } 737 738 private boolean deriveOptional(DependencyNode node, Object conflictId) { 739 Dependency dep = node.getDependency(); 740 boolean optional = (dep != null) && dep.isOptional(); 741 if (optional 742 || (node.getManagedBits() & DependencyNode.MANAGED_OPTIONAL) != 0 743 || (conflictId != null && resolvedIds.containsKey(conflictId))) { 744 return optional; 745 } 746 int depth = parentNodes.size(); 747 return (depth > 0) ? parentOptionals.get(depth - 1) : false; 748 } 749 } 750 751 /** 752 * A context used to hold information that is relevant for deriving the scope of a child dependency. 753 * 754 * @see ScopeDeriver 755 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may 756 * change without notice and only exists to enable unit testing. 757 */ 758 public static final class ScopeContext { 759 760 String parentScope; 761 762 String childScope; 763 764 String derivedScope; 765 766 /** 767 * Creates a new scope context with the specified properties. 768 * 769 * @param parentScope The scope of the parent dependency, may be {@code null}. 770 * @param childScope The scope of the child dependency, may be {@code null}. 771 * @noreference This class is not intended to be instantiated by clients in production code, the constructor may 772 * change without notice and only exists to enable unit testing. 773 */ 774 public ScopeContext(String parentScope, String childScope) { 775 this.parentScope = (parentScope != null) ? parentScope : ""; 776 derivedScope = (childScope != null) ? childScope : ""; 777 this.childScope = (childScope != null) ? childScope : ""; 778 } 779 780 /** 781 * Gets the scope of the parent dependency. This is usually the scope that was derived by earlier invocations of 782 * the scope deriver. 783 * 784 * @return The scope of the parent dependency, never {@code null}. 785 */ 786 public String getParentScope() { 787 return parentScope; 788 } 789 790 /** 791 * Gets the original scope of the child dependency. This is the scope that was declared in the artifact 792 * descriptor of the parent dependency. 793 * 794 * @return The original scope of the child dependency, never {@code null}. 795 */ 796 public String getChildScope() { 797 return childScope; 798 } 799 800 /** 801 * Gets the derived scope of the child dependency. This is initially equal to {@link #getChildScope()} until the 802 * scope deriver makes changes. 803 * 804 * @return The derived scope of the child dependency, never {@code null}. 805 */ 806 public String getDerivedScope() { 807 return derivedScope; 808 } 809 810 /** 811 * Sets the derived scope of the child dependency. 812 * 813 * @param derivedScope The derived scope of the dependency, may be {@code null}. 814 */ 815 public void setDerivedScope(String derivedScope) { 816 this.derivedScope = (derivedScope != null) ? derivedScope : ""; 817 } 818 } 819 820 /** 821 * A conflicting dependency. 822 * 823 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may 824 * change without notice and only exists to enable unit testing. 825 */ 826 public static final class ConflictItem { 827 828 // nodes can share child lists, we care about the unique owner of a child node which is the child list 829 final List<DependencyNode> parent; 830 831 // only for debugging/toString() to help identify the parent node(s) 832 final Artifact artifact; 833 834 // is mutable as removeLosers will mutate it (if Verbosity==STANDARD) 835 DependencyNode node; 836 837 int depth; 838 839 // we start with String and update to Set<String> if needed 840 Object scopes; 841 842 // bit field of OPTIONAL_FALSE and OPTIONAL_TRUE 843 int optionalities; 844 845 /** 846 * Bit flag indicating whether one or more paths consider the dependency non-optional. 847 */ 848 public static final int OPTIONAL_FALSE = 0x01; 849 850 /** 851 * Bit flag indicating whether one or more paths consider the dependency optional. 852 */ 853 public static final int OPTIONAL_TRUE = 0x02; 854 855 ConflictItem(DependencyNode parent, DependencyNode node, String scope, boolean optional) { 856 if (parent != null) { 857 this.parent = parent.getChildren(); 858 this.artifact = parent.getArtifact(); 859 } else { 860 this.parent = null; 861 this.artifact = null; 862 } 863 this.node = node; 864 this.scopes = scope; 865 this.optionalities = optional ? OPTIONAL_TRUE : OPTIONAL_FALSE; 866 } 867 868 /** 869 * Creates a new conflict item with the specified properties. 870 * 871 * @param parent The parent node of the conflicting dependency, may be {@code null}. 872 * @param node The conflicting dependency, must not be {@code null}. 873 * @param depth The zero-based depth of the conflicting dependency. 874 * @param optionalities The optionalities the dependency was encountered with, encoded as a bit field consisting 875 * of {@link ConflictResolver.ConflictItem#OPTIONAL_TRUE} and 876 * {@link ConflictResolver.ConflictItem#OPTIONAL_FALSE}. 877 * @param scopes The derived scopes of the conflicting dependency, must not be {@code null}. 878 * @noreference This class is not intended to be instantiated by clients in production code, the constructor may 879 * change without notice and only exists to enable unit testing. 880 */ 881 public ConflictItem( 882 DependencyNode parent, DependencyNode node, int depth, int optionalities, String... scopes) { 883 this.parent = (parent != null) ? parent.getChildren() : null; 884 this.artifact = (parent != null) ? parent.getArtifact() : null; 885 this.node = node; 886 this.depth = depth; 887 this.optionalities = optionalities; 888 this.scopes = Arrays.asList(scopes); 889 } 890 891 /** 892 * Determines whether the specified conflict item is a sibling of this item. 893 * 894 * @param item The other conflict item, must not be {@code null}. 895 * @return {@code true} if the given item has the same parent as this item, {@code false} otherwise. 896 */ 897 public boolean isSibling(ConflictItem item) { 898 return parent == item.parent; 899 } 900 901 /** 902 * Gets the dependency node involved in the conflict. 903 * 904 * @return The involved dependency node, never {@code null}. 905 */ 906 public DependencyNode getNode() { 907 return node; 908 } 909 910 /** 911 * Gets the dependency involved in the conflict, short for {@code getNode.getDependency()}. 912 * 913 * @return The involved dependency, never {@code null}. 914 */ 915 public Dependency getDependency() { 916 return node.getDependency(); 917 } 918 919 /** 920 * Gets the zero-based depth at which the conflicting node occurs in the graph. As such, the depth denotes the 921 * number of parent nodes. If actually multiple paths lead to the node, the return value denotes the smallest 922 * possible depth. 923 * 924 * @return The zero-based depth of the node in the graph. 925 */ 926 public int getDepth() { 927 return depth; 928 } 929 930 /** 931 * Gets the derived scopes of the dependency. In general, the same dependency node could be reached via 932 * different paths and each path might result in a different derived scope. 933 * 934 * @see ScopeDeriver 935 * @return The (read-only) set of derived scopes of the dependency, never {@code null}. 936 */ 937 @SuppressWarnings("unchecked") 938 public Collection<String> getScopes() { 939 if (scopes instanceof String) { 940 return Collections.singleton((String) scopes); 941 } 942 return (Collection<String>) scopes; 943 } 944 945 @SuppressWarnings("unchecked") 946 void addScope(String scope) { 947 if (scopes instanceof Collection) { 948 ((Collection<String>) scopes).add(scope); 949 } else if (!scopes.equals(scope)) { 950 Collection<Object> set = new HashSet<>(); 951 set.add(scopes); 952 set.add(scope); 953 scopes = set; 954 } 955 } 956 957 /** 958 * Gets the derived optionalities of the dependency. In general, the same dependency node could be reached via 959 * different paths and each path might result in a different derived optionality. 960 * 961 * @return A bit field consisting of {@link ConflictResolver.ConflictItem#OPTIONAL_FALSE} and/or 962 * {@link ConflictResolver.ConflictItem#OPTIONAL_TRUE} indicating the derived optionalities the 963 * dependency was encountered with. 964 */ 965 public int getOptionalities() { 966 return optionalities; 967 } 968 969 void addOptional(boolean optional) { 970 optionalities |= optional ? OPTIONAL_TRUE : OPTIONAL_FALSE; 971 } 972 973 @Override 974 public String toString() { 975 return node + " @ " + depth + " < " + artifact; 976 } 977 } 978 979 /** 980 * A context used to hold information that is relevant for resolving version and scope conflicts. 981 * 982 * @see VersionSelector 983 * @see ScopeSelector 984 * @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may 985 * change without notice and only exists to enable unit testing. 986 */ 987 public static final class ConflictContext { 988 989 final DependencyNode root; 990 991 final Map<?, ?> conflictIds; 992 993 final Collection<ConflictItem> items; 994 995 Object conflictId; 996 997 ConflictItem winner; 998 999 String scope; 1000 1001 Boolean optional; 1002 1003 ConflictContext(DependencyNode root, Map<?, ?> conflictIds, Collection<ConflictItem> items) { 1004 this.root = root; 1005 this.conflictIds = conflictIds; 1006 this.items = Collections.unmodifiableCollection(items); 1007 } 1008 1009 /** 1010 * Creates a new conflict context. 1011 * 1012 * @param root The root node of the dependency graph, must not be {@code null}. 1013 * @param conflictId The conflict id for the set of conflicting dependencies in this context, must not be 1014 * {@code null}. 1015 * @param conflictIds The mapping from dependency node to conflict id, must not be {@code null}. 1016 * @param items The conflict items in this context, must not be {@code null}. 1017 * @noreference This class is not intended to be instantiated by clients in production code, the constructor may 1018 * change without notice and only exists to enable unit testing. 1019 */ 1020 public ConflictContext( 1021 DependencyNode root, 1022 Object conflictId, 1023 Map<DependencyNode, Object> conflictIds, 1024 Collection<ConflictItem> items) { 1025 this(root, conflictIds, items); 1026 this.conflictId = conflictId; 1027 } 1028 1029 /** 1030 * Gets the root node of the dependency graph being transformed. 1031 * 1032 * @return The root node of the dependeny graph, never {@code null}. 1033 */ 1034 public DependencyNode getRoot() { 1035 return root; 1036 } 1037 1038 /** 1039 * Determines whether the specified dependency node belongs to this conflict context. 1040 * 1041 * @param node The dependency node to check, must not be {@code null}. 1042 * @return {@code true} if the given node belongs to this conflict context, {@code false} otherwise. 1043 */ 1044 public boolean isIncluded(DependencyNode node) { 1045 return conflictId.equals(conflictIds.get(node)); 1046 } 1047 1048 /** 1049 * Gets the collection of conflict items in this context. 1050 * 1051 * @return The (read-only) collection of conflict items in this context, never {@code null}. 1052 */ 1053 public Collection<ConflictItem> getItems() { 1054 return items; 1055 } 1056 1057 /** 1058 * Gets the conflict item which has been selected as the winner among the conflicting dependencies. 1059 * 1060 * @return The winning conflict item or {@code null} if not set yet. 1061 */ 1062 public ConflictItem getWinner() { 1063 return winner; 1064 } 1065 1066 /** 1067 * Sets the conflict item which has been selected as the winner among the conflicting dependencies. 1068 * 1069 * @param winner The winning conflict item, may be {@code null}. 1070 */ 1071 public void setWinner(ConflictItem winner) { 1072 this.winner = winner; 1073 } 1074 1075 /** 1076 * Gets the effective scope of the winning dependency. 1077 * 1078 * @return The effective scope of the winning dependency or {@code null} if none. 1079 */ 1080 public String getScope() { 1081 return scope; 1082 } 1083 1084 /** 1085 * Sets the effective scope of the winning dependency. 1086 * 1087 * @param scope The effective scope, may be {@code null}. 1088 */ 1089 public void setScope(String scope) { 1090 this.scope = scope; 1091 } 1092 1093 /** 1094 * Gets the effective optional flag of the winning dependency. 1095 * 1096 * @return The effective optional flag or {@code null} if none. 1097 */ 1098 public Boolean getOptional() { 1099 return optional; 1100 } 1101 1102 /** 1103 * Sets the effective optional flag of the winning dependency. 1104 * 1105 * @param optional The effective optional flag, may be {@code null}. 1106 */ 1107 public void setOptional(Boolean optional) { 1108 this.optional = optional; 1109 } 1110 1111 @Override 1112 public String toString() { 1113 return winner + " @ " + scope + " < " + items; 1114 } 1115 } 1116 1117 /** 1118 * An extension point of {@link ConflictResolver} that determines the winner among conflicting dependencies. The 1119 * winning node (and its children) will be retained in the dependency graph, the other nodes will get removed. The 1120 * version selector does not need to deal with potential scope conflicts, these will be addressed afterwards by the 1121 * {@link ScopeSelector}. 1122 * <p> 1123 * <strong>Note:</strong> Implementations must be stateless. 1124 */ 1125 public abstract static class VersionSelector { 1126 1127 /** 1128 * Retrieves the version selector for use during the specified graph transformation. The conflict resolver calls 1129 * this method once per 1130 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1131 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1132 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1133 * default implementation simply returns the current instance which is appropriate for implementations which do 1134 * not require auxiliary data. 1135 * 1136 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1137 * @param context The graph transformation context, must not be {@code null}. 1138 * @return The scope deriver to use for the given graph transformation, never {@code null}. 1139 * @throws RepositoryException If the instance could not be retrieved. 1140 */ 1141 public VersionSelector getInstance(DependencyNode root, DependencyGraphTransformationContext context) 1142 throws RepositoryException { 1143 return this; 1144 } 1145 1146 /** 1147 * Determines the winning node among conflicting dependencies. Implementations will usually iterate 1148 * {@link ConflictContext#getItems()}, inspect {@link ConflictItem#getNode()} and eventually call 1149 * {@link ConflictContext#setWinner(ConflictResolver.ConflictItem)} to deliver the winner. Failure to select a 1150 * winner will automatically fail the entire conflict resolution. 1151 * 1152 * @param context The conflict context, must not be {@code null}. 1153 * @throws RepositoryException If the version selection failed. 1154 */ 1155 public abstract void selectVersion(ConflictContext context) throws RepositoryException; 1156 } 1157 1158 /** 1159 * An extension point of {@link ConflictResolver} that determines the effective scope of a dependency from a 1160 * potentially conflicting set of {@link ScopeDeriver derived scopes}. The scope selector gets invoked after the 1161 * {@link VersionSelector} has picked the winning node. 1162 * <p> 1163 * <strong>Note:</strong> Implementations must be stateless. 1164 */ 1165 public abstract static class ScopeSelector { 1166 1167 /** 1168 * Retrieves the scope selector for use during the specified graph transformation. The conflict resolver calls 1169 * this method once per 1170 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1171 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1172 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1173 * default implementation simply returns the current instance which is appropriate for implementations which do 1174 * not require auxiliary data. 1175 * 1176 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1177 * @param context The graph transformation context, must not be {@code null}. 1178 * @return The scope selector to use for the given graph transformation, never {@code null}. 1179 * @throws RepositoryException If the instance could not be retrieved. 1180 */ 1181 public ScopeSelector getInstance(DependencyNode root, DependencyGraphTransformationContext context) 1182 throws RepositoryException { 1183 return this; 1184 } 1185 1186 /** 1187 * Determines the effective scope of the dependency given by {@link ConflictContext#getWinner()}. 1188 * Implementations will usually iterate {@link ConflictContext#getItems()}, inspect 1189 * {@link ConflictItem#getScopes()} and eventually call {@link ConflictContext#setScope(String)} to deliver the 1190 * effective scope. 1191 * 1192 * @param context The conflict context, must not be {@code null}. 1193 * @throws RepositoryException If the scope selection failed. 1194 */ 1195 public abstract void selectScope(ConflictContext context) throws RepositoryException; 1196 } 1197 1198 /** 1199 * An extension point of {@link ConflictResolver} that determines the scope of a dependency in relation to the scope 1200 * of its parent. 1201 * <p> 1202 * <strong>Note:</strong> Implementations must be stateless. 1203 */ 1204 public abstract static class ScopeDeriver { 1205 1206 /** 1207 * Retrieves the scope deriver for use during the specified graph transformation. The conflict resolver calls 1208 * this method once per 1209 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1210 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1211 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1212 * default implementation simply returns the current instance which is appropriate for implementations which do 1213 * not require auxiliary data. 1214 * 1215 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1216 * @param context The graph transformation context, must not be {@code null}. 1217 * @return The scope deriver to use for the given graph transformation, never {@code null}. 1218 * @throws RepositoryException If the instance could not be retrieved. 1219 */ 1220 public ScopeDeriver getInstance(DependencyNode root, DependencyGraphTransformationContext context) 1221 throws RepositoryException { 1222 return this; 1223 } 1224 1225 /** 1226 * Determines the scope of a dependency in relation to the scope of its parent. Implementors need to call 1227 * {@link ScopeContext#setDerivedScope(String)} to deliver the result of their calculation. If said method is 1228 * not invoked, the conflict resolver will assume the scope of the child dependency remains unchanged. 1229 * 1230 * @param context The scope context, must not be {@code null}. 1231 * @throws RepositoryException If the scope deriviation failed. 1232 */ 1233 public abstract void deriveScope(ScopeContext context) throws RepositoryException; 1234 } 1235 1236 /** 1237 * An extension point of {@link ConflictResolver} that determines the effective optional flag of a dependency from a 1238 * potentially conflicting set of derived optionalities. The optionality selector gets invoked after the 1239 * {@link VersionSelector} has picked the winning node. 1240 * <p> 1241 * <strong>Note:</strong> Implementations must be stateless. 1242 */ 1243 public abstract static class OptionalitySelector { 1244 1245 /** 1246 * Retrieves the optionality selector for use during the specified graph transformation. The conflict resolver 1247 * calls this method once per 1248 * {@link ConflictResolver#transformGraph(DependencyNode, DependencyGraphTransformationContext)} invocation to 1249 * allow implementations to prepare any auxiliary data that is needed for their operation. Given that 1250 * implementations must be stateless, a new instance needs to be returned to hold such auxiliary data. The 1251 * default implementation simply returns the current instance which is appropriate for implementations which do 1252 * not require auxiliary data. 1253 * 1254 * @param root The root node of the (possibly cyclic!) graph to transform, must not be {@code null}. 1255 * @param context The graph transformation context, must not be {@code null}. 1256 * @return The optionality selector to use for the given graph transformation, never {@code null}. 1257 * @throws RepositoryException If the instance could not be retrieved. 1258 */ 1259 public OptionalitySelector getInstance(DependencyNode root, DependencyGraphTransformationContext context) 1260 throws RepositoryException { 1261 return this; 1262 } 1263 1264 /** 1265 * Determines the effective optional flag of the dependency given by {@link ConflictContext#getWinner()}. 1266 * Implementations will usually iterate {@link ConflictContext#getItems()}, inspect 1267 * {@link ConflictItem#getOptionalities()} and eventually call {@link ConflictContext#setOptional(Boolean)} to 1268 * deliver the effective optional flag. 1269 * 1270 * @param context The conflict context, must not be {@code null}. 1271 * @throws RepositoryException If the optionality selection failed. 1272 */ 1273 public abstract void selectOptionality(ConflictContext context) throws RepositoryException; 1274 } 1275}