-
Notifications
You must be signed in to change notification settings - Fork 119
/
ConflictResolver.java
1275 lines (1122 loc) · 55.6 KB
/
ConflictResolver.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
*/
package org.eclipse.aether.util.graph.transformer;
import java.util.*;
import org.eclipse.aether.RepositoryException;
import org.eclipse.aether.RepositorySystemSession;
import org.eclipse.aether.artifact.Artifact;
import org.eclipse.aether.collection.DependencyGraphTransformationContext;
import org.eclipse.aether.collection.DependencyGraphTransformer;
import org.eclipse.aether.graph.DefaultDependencyNode;
import org.eclipse.aether.graph.Dependency;
import org.eclipse.aether.graph.DependencyNode;
import org.eclipse.aether.util.artifact.ArtifactIdUtils;
import static java.util.Objects.requireNonNull;
/**
* A dependency graph transformer that resolves version and scope conflicts among dependencies. For a given set of
* conflicting nodes, one node will be chosen as the winner and the other nodes are removed from the dependency graph.
* The exact rules by which a winning node and its effective scope are determined are controlled by user-supplied
* implementations of {@link VersionSelector}, {@link ScopeSelector}, {@link OptionalitySelector} and
* {@link ScopeDeriver}.
* <p>
* By default, this graph transformer will turn the dependency graph into a tree without duplicate artifacts. Using the
* configuration property {@link #CONFIG_PROP_VERBOSE}, a verbose mode can be enabled where the graph is still turned
* into a tree but all nodes participating in a conflict are retained. The nodes that were rejected during conflict
* resolution have no children and link back to the winner node via the {@link #NODE_DATA_WINNER} key in their custom
* data. Additionally, the keys {@link #NODE_DATA_ORIGINAL_SCOPE} and {@link #NODE_DATA_ORIGINAL_OPTIONALITY} are used
* to store the original scope and optionality of each node. Obviously, the resulting dependency tree is not suitable
* for artifact resolution unless a filter is employed to exclude the duplicate dependencies.
* <p>
* This transformer will query the keys {@link TransformationContextKeys#CONFLICT_IDS},
* {@link TransformationContextKeys#SORTED_CONFLICT_IDS}, {@link TransformationContextKeys#CYCLIC_CONFLICT_IDS} for
* existing information about conflict ids. In absence of this information, it will automatically invoke the
* {@link ConflictIdSorter} to calculate it.
*/
public final class ConflictResolver implements DependencyGraphTransformer {
/**
* The key in the repository session's {@link org.eclipse.aether.RepositorySystemSession#getConfigProperties()
* configuration properties} used to store a {@link Boolean} flag controlling the transformer's verbose mode.
* Accepted values are {@link Boolean} type, {@link String} type (where "true" would be interpreted as {@code true}
* or {@link Verbosity} enum instances.
*/
public static final String CONFIG_PROP_VERBOSE = "aether.conflictResolver.verbose";
/**
* The enum representing verbosity levels of conflict resolver.
*
* @since 1.9.8
*/
public enum Verbosity {
/**
* Verbosity level to be used in all "common" resolving use cases (ie. dependencies to build class path). The
* {@link ConflictResolver} in this mode will trim down the graph to the barest minimum: will not leave
* any conflicting node in place, hence no conflicts will be present in transformed graph either.
*/
NONE,
/**
* Verbosity level to be used in "analyze" resolving use cases (ie. dependency convergence calculations). The
* {@link ConflictResolver} in this mode will remove any redundant collected nodes, in turn it will leave one
* with recorded conflicting information. This mode corresponds to "classic verbose" mode when
* {@link #CONFIG_PROP_VERBOSE} was set to {@code true}. Obviously, the resulting dependency tree is not
* suitable for artifact resolution unless a filter is employed to exclude the duplicate dependencies.
*/
STANDARD,
/**
* Verbosity level to be used in "analyze" resolving use cases (ie. dependency convergence calculations). The
* {@link ConflictResolver} in this mode will not remove any collected node, in turn it will record on all
* eliminated nodes the conflicting information. Obviously, the resulting dependency tree is not suitable
* for artifact resolution unless a filter is employed to exclude the duplicate dependencies.
*/
FULL
}
/**
* Helper method that uses {@link RepositorySystemSession} and {@link #CONFIG_PROP_VERBOSE} key to figure out
* current {@link Verbosity}: if {@link Boolean} or {@code String} found, returns {@link Verbosity#STANDARD}
* or {@link Verbosity#NONE}, depending on value (string is parsed with {@link Boolean#parseBoolean(String)}
* for {@code true} or {@code false} correspondingly. This is to retain "existing" behavior, where the config
* key accepted only these values.
* Since 1.9.8 release, this key may contain {@link Verbosity} enum instance as well, in which case that instance
* is returned.
* This method never returns {@code null}.
*/
private static Verbosity getVerbosity(RepositorySystemSession session) {
final Object verbosityValue = session.getConfigProperties().get(CONFIG_PROP_VERBOSE);
if (verbosityValue instanceof Boolean) {
return (Boolean) verbosityValue ? Verbosity.STANDARD : Verbosity.NONE;
} else if (verbosityValue instanceof String) {
return Boolean.parseBoolean(verbosityValue.toString()) ? Verbosity.STANDARD : Verbosity.NONE;
} else if (verbosityValue instanceof Verbosity) {
return (Verbosity) verbosityValue;
} else if (verbosityValue != null) {
throw new IllegalArgumentException("Unsupported Verbosity configuration: " + verbosityValue);
}
return Verbosity.NONE;
}
/**
* The key in the dependency node's {@link DependencyNode#getData() custom data} under which a reference to the
* {@link DependencyNode} which has won the conflict is stored.
*/
public static final String NODE_DATA_WINNER = "conflict.winner";
/**
* The key in the dependency node's {@link DependencyNode#getData() custom data} under which the scope of the
* dependency before scope derivation and conflict resolution is stored.
*/
public static final String NODE_DATA_ORIGINAL_SCOPE = "conflict.originalScope";
/**
* The key in the dependency node's {@link DependencyNode#getData() custom data} under which the optional flag of
* the dependency before derivation and conflict resolution is stored.
*/
public static final String NODE_DATA_ORIGINAL_OPTIONALITY = "conflict.originalOptionality";
private final VersionSelector versionSelector;
private final ScopeSelector scopeSelector;
private final ScopeDeriver scopeDeriver;
private final OptionalitySelector optionalitySelector;
/**
* Creates a new conflict resolver instance with the specified hooks.
*
* @param versionSelector The version selector to use, must not be {@code null}.
* @param scopeSelector The scope selector to use, must not be {@code null}.
* @param optionalitySelector The optionality selector ot use, must not be {@code null}.
* @param scopeDeriver The scope deriver to use, must not be {@code null}.
*/
public ConflictResolver(
VersionSelector versionSelector,
ScopeSelector scopeSelector,
OptionalitySelector optionalitySelector,
ScopeDeriver scopeDeriver) {
this.versionSelector = requireNonNull(versionSelector, "version selector cannot be null");
this.scopeSelector = requireNonNull(scopeSelector, "scope selector cannot be null");
this.optionalitySelector = requireNonNull(optionalitySelector, "optionality selector cannot be null");
this.scopeDeriver = requireNonNull(scopeDeriver, "scope deriver cannot be null");
}
public DependencyNode transformGraph(DependencyNode node, DependencyGraphTransformationContext context)
throws RepositoryException {
requireNonNull(node, "node cannot be null");
requireNonNull(context, "context cannot be null");
List<?> sortedConflictIds = (List<?>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS);
if (sortedConflictIds == null) {
ConflictIdSorter sorter = new ConflictIdSorter();
sorter.transformGraph(node, context);
sortedConflictIds = (List<?>) context.get(TransformationContextKeys.SORTED_CONFLICT_IDS);
}
@SuppressWarnings("unchecked")
Map<String, Object> stats = (Map<String, Object>) context.get(TransformationContextKeys.STATS);
long time1 = System.nanoTime();
@SuppressWarnings("unchecked")
Collection<Collection<?>> conflictIdCycles =
(Collection<Collection<?>>) context.get(TransformationContextKeys.CYCLIC_CONFLICT_IDS);
if (conflictIdCycles == null) {
throw new RepositoryException("conflict id cycles have not been identified");
}
Map<?, ?> conflictIds = (Map<?, ?>) context.get(TransformationContextKeys.CONFLICT_IDS);
if (conflictIds == null) {
throw new RepositoryException("conflict groups have not been identified");
}
Map<Object, Collection<Object>> cyclicPredecessors = new HashMap<>();
for (Collection<?> cycle : conflictIdCycles) {
for (Object conflictId : cycle) {
Collection<Object> predecessors = cyclicPredecessors.computeIfAbsent(conflictId, k -> new HashSet<>());
predecessors.addAll(cycle);
}
}
State state = new State(node, conflictIds, sortedConflictIds.size(), context);
for (Iterator<?> it = sortedConflictIds.iterator(); it.hasNext(); ) {
Object conflictId = it.next();
// reset data structures for next graph walk
state.prepare(conflictId, cyclicPredecessors.get(conflictId));
// find nodes with the current conflict id and while walking the graph (more deeply), nuke leftover losers
gatherConflictItems(node, state);
// now that we know the min depth of the parents, update depth of conflict items
state.finish();
// earlier runs might have nuked all parents of the current conflict id, so it might not exist anymore
if (!state.items.isEmpty()) {
ConflictContext ctx = state.conflictCtx;
state.versionSelector.selectVersion(ctx);
if (ctx.winner == null) {
throw new RepositoryException("conflict resolver did not select winner among " + state.items);
}
DependencyNode winner = ctx.winner.node;
state.scopeSelector.selectScope(ctx);
if (Verbosity.NONE != state.verbosity) {
winner.setData(
NODE_DATA_ORIGINAL_SCOPE, winner.getDependency().getScope());
}
winner.setScope(ctx.scope);
state.optionalitySelector.selectOptionality(ctx);
if (Verbosity.NONE != state.verbosity) {
winner.setData(
NODE_DATA_ORIGINAL_OPTIONALITY,
winner.getDependency().isOptional());
}
winner.setOptional(ctx.optional);
removeLosers(state);
}
// record the winner so we can detect leftover losers during future graph walks
state.winner();
// in case of cycles, trigger final graph walk to ensure all leftover losers are gone
if (!it.hasNext() && !conflictIdCycles.isEmpty() && state.conflictCtx.winner != null) {
DependencyNode winner = state.conflictCtx.winner.node;
state.prepare(state, null);
gatherConflictItems(winner, state);
}
}
if (stats != null) {
long time2 = System.nanoTime();
stats.put("ConflictResolver.totalTime", time2 - time1);
stats.put("ConflictResolver.conflictItemCount", state.totalConflictItems);
}
return node;
}
private boolean gatherConflictItems(DependencyNode node, State state) throws RepositoryException {
Object conflictId = state.conflictIds.get(node);
if (state.currentId.equals(conflictId)) {
// found it, add conflict item (if not already done earlier by another path)
state.add(node);
// we don't recurse here so we might miss losers beneath us, those will be nuked during future walks below
} else if (state.loser(node, conflictId)) {
// found a leftover loser (likely in a cycle) of an already processed conflict id, tell caller to nuke it
return false;
} else if (state.push(node, conflictId)) {
// found potential parent, no cycle and not visisted before with the same derived scope, so recurse
for (Iterator<DependencyNode> it = node.getChildren().iterator(); it.hasNext(); ) {
DependencyNode child = it.next();
if (!gatherConflictItems(child, state)) {
it.remove();
}
}
state.pop();
}
return true;
}
private static void removeLosers(State state) {
ConflictItem winner = state.conflictCtx.winner;
String winnerArtifactId = ArtifactIdUtils.toId(winner.node.getArtifact());
List<DependencyNode> previousParent = null;
ListIterator<DependencyNode> childIt = null;
HashSet<String> toRemoveIds = new HashSet<>();
for (ConflictItem item : state.items) {
if (item == winner) {
continue;
}
if (item.parent != previousParent) {
childIt = item.parent.listIterator();
previousParent = item.parent;
}
while (childIt.hasNext()) {
DependencyNode child = childIt.next();
if (child == item.node) {
// NONE: just remove it and done
if (Verbosity.NONE == state.verbosity) {
childIt.remove();
break;
}
// STANDARD: doing extra bookkeeping to select "which nodes to remove"
if (Verbosity.STANDARD == state.verbosity) {
String childArtifactId = ArtifactIdUtils.toId(child.getArtifact());
// if two IDs are equal, it means "there is nearest", not conflict per se.
// In that case we do NOT allow this child to be removed (but remove others)
// and this keeps us safe from iteration (and in general, version) ordering
// as we explicitly leave out ID that is "nearest found" state.
//
// This tackles version ranges mostly, where ranges are turned into list of
// several nodes in collector (as many were discovered, ie. from metadata), and
// old code would just "mark" the first hit as conflict, and remove the rest,
// even if rest could contain "more suitable" version, that is not conflicting/diverging.
// This resulted in verbose mode transformed tree, that was misrepresenting things
// for dependency convergence calculations: it represented state like parent node
// depends on "wrong" version (diverge), while "right" version was present (but removed)
// as well, as it was contained in parents version range.
if (!Objects.equals(winnerArtifactId, childArtifactId)) {
toRemoveIds.add(childArtifactId);
}
}
// FULL: just record the facts
DependencyNode loser = new DefaultDependencyNode(child);
loser.setData(NODE_DATA_WINNER, winner.node);
loser.setData(
NODE_DATA_ORIGINAL_SCOPE, loser.getDependency().getScope());
loser.setData(
NODE_DATA_ORIGINAL_OPTIONALITY,
loser.getDependency().isOptional());
loser.setScope(item.getScopes().iterator().next());
loser.setChildren(Collections.emptyList());
childIt.set(loser);
item.node = loser;
break;
}
}
}
// 2nd pass to apply "standard" verbosity: leaving only 1 loser, but with care
if (Verbosity.STANDARD == state.verbosity && !toRemoveIds.isEmpty()) {
previousParent = null;
for (ConflictItem item : state.items) {
if (item == winner) {
continue;
}
if (item.parent != previousParent) {
childIt = item.parent.listIterator();
previousParent = item.parent;
}
while (childIt.hasNext()) {
DependencyNode child = childIt.next();
if (child == item.node) {
String childArtifactId = ArtifactIdUtils.toId(child.getArtifact());
if (toRemoveIds.contains(childArtifactId) && item.parent.size() > 1) {
childIt.remove();
}
break;
}
}
}
}
// there might still be losers beneath the winner (e.g. in case of cycles)
// those will be nuked during future graph walks when we include the winner in the recursion
}
static final class NodeInfo {
/**
* The smallest depth at which the node was seen, used for "the" depth of its conflict items.
*/
int minDepth;
/**
* The set of derived scopes the node was visited with, used to check whether an already seen node needs to be
* revisited again in context of another scope. To conserve memory, we start with {@code String} and update to
* {@code Set<String>} if needed.
*/
Object derivedScopes;
/**
* The set of derived optionalities the node was visited with, used to check whether an already seen node needs
* to be revisited again in context of another optionality. To conserve memory, encoded as bit field (bit 0 ->
* optional=false, bit 1 -> optional=true).
*/
int derivedOptionalities;
/**
* The conflict items which are immediate children of the node, used to easily update those conflict items after
* a new parent scope/optionality was encountered.
*/
List<ConflictItem> children;
static final int CHANGE_SCOPE = 0x01;
static final int CHANGE_OPTIONAL = 0x02;
private static final int OPT_FALSE = 0x01;
private static final int OPT_TRUE = 0x02;
NodeInfo(int depth, String derivedScope, boolean optional) {
minDepth = depth;
derivedScopes = derivedScope;
derivedOptionalities = optional ? OPT_TRUE : OPT_FALSE;
}
@SuppressWarnings("unchecked")
int update(int depth, String derivedScope, boolean optional) {
if (depth < minDepth) {
minDepth = depth;
}
int changes;
if (derivedScopes.equals(derivedScope)) {
changes = 0;
} else if (derivedScopes instanceof Collection) {
changes = ((Collection<String>) derivedScopes).add(derivedScope) ? CHANGE_SCOPE : 0;
} else {
Collection<String> scopes = new HashSet<>();
scopes.add((String) derivedScopes);
scopes.add(derivedScope);
derivedScopes = scopes;
changes = CHANGE_SCOPE;
}
int bit = optional ? OPT_TRUE : OPT_FALSE;
if ((derivedOptionalities & bit) == 0) {
derivedOptionalities |= bit;
changes |= CHANGE_OPTIONAL;
}
return changes;
}
void add(ConflictItem item) {
if (children == null) {
children = new ArrayList<>(1);
}
children.add(item);
}
}
final class State {
/**
* The conflict id currently processed.
*/
Object currentId;
/**
* Stats counter.
*/
int totalConflictItems;
/**
* Flag whether we should keep losers in the graph to enable visualization/troubleshooting of conflicts.
*/
final Verbosity verbosity;
/**
* A mapping from conflict id to winner node, helps to recognize nodes that have their effective
* scope&optionality set or are leftovers from previous removals.
*/
final Map<Object, DependencyNode> resolvedIds;
/**
* The set of conflict ids which could apply to ancestors of nodes with the current conflict id, used to avoid
* recursion early on. This is basically a superset of the key set of resolvedIds, the additional ids account
* for cyclic dependencies.
*/
final Collection<Object> potentialAncestorIds;
/**
* The output from the conflict marker
*/
final Map<?, ?> conflictIds;
/**
* The conflict items we have gathered so far for the current conflict id.
*/
final List<ConflictItem> items;
/**
* The (conceptual) mapping from nodes to extra infos, technically keyed by the node's child list which better
* captures the identity of a node since we're basically concerned with effects towards children.
*/
final Map<List<DependencyNode>, NodeInfo> infos;
/**
* The set of nodes on the DFS stack to detect cycles, technically keyed by the node's child list to match the
* dirty graph structure produced by the dependency collector for cycles.
*/
final Map<List<DependencyNode>, Object> stack;
/**
* The stack of parent nodes.
*/
final List<DependencyNode> parentNodes;
/**
* The stack of derived scopes for parent nodes.
*/
final List<String> parentScopes;
/**
* The stack of derived optional flags for parent nodes.
*/
final List<Boolean> parentOptionals;
/**
* The stack of node infos for parent nodes, may contain {@code null} which is used to disable creating new
* conflict items when visiting their parent again (conflict items are meant to be unique by parent-node combo).
*/
final List<NodeInfo> parentInfos;
/**
* The conflict context passed to the version/scope/optionality selectors, updated as we move along rather than
* recreated to avoid tmp objects.
*/
final ConflictContext conflictCtx;
/**
* The scope context passed to the scope deriver, updated as we move along rather than recreated to avoid tmp
* objects.
*/
final ScopeContext scopeCtx;
/**
* The effective version selector, i.e. after initialization.
*/
final VersionSelector versionSelector;
/**
* The effective scope selector, i.e. after initialization.
*/
final ScopeSelector scopeSelector;
/**
* The effective scope deriver, i.e. after initialization.
*/
final ScopeDeriver scopeDeriver;
/**
* The effective optionality selector, i.e. after initialization.
*/
final OptionalitySelector optionalitySelector;
State(
DependencyNode root,
Map<?, ?> conflictIds,
int conflictIdCount,
DependencyGraphTransformationContext context)
throws RepositoryException {
this.conflictIds = conflictIds;
this.verbosity = getVerbosity(context.getSession());
potentialAncestorIds = new HashSet<>(conflictIdCount * 2);
resolvedIds = new HashMap<>(conflictIdCount * 2);
items = new ArrayList<>(256);
infos = new IdentityHashMap<>(64);
stack = new IdentityHashMap<>(64);
parentNodes = new ArrayList<>(64);
parentScopes = new ArrayList<>(64);
parentOptionals = new ArrayList<>(64);
parentInfos = new ArrayList<>(64);
conflictCtx = new ConflictContext(root, conflictIds, items);
scopeCtx = new ScopeContext(null, null);
versionSelector = ConflictResolver.this.versionSelector.getInstance(root, context);
scopeSelector = ConflictResolver.this.scopeSelector.getInstance(root, context);
scopeDeriver = ConflictResolver.this.scopeDeriver.getInstance(root, context);
optionalitySelector = ConflictResolver.this.optionalitySelector.getInstance(root, context);
}
void prepare(Object conflictId, Collection<Object> cyclicPredecessors) {
currentId = conflictId;
conflictCtx.conflictId = conflictId;
conflictCtx.winner = null;
conflictCtx.scope = null;
conflictCtx.optional = null;
items.clear();
infos.clear();
if (cyclicPredecessors != null) {
potentialAncestorIds.addAll(cyclicPredecessors);
}
}
void finish() {
List<DependencyNode> previousParent = null;
int previousDepth = 0;
totalConflictItems += items.size();
for (ListIterator<ConflictItem> iterator = items.listIterator(items.size()); iterator.hasPrevious(); ) {
ConflictItem item = iterator.previous();
if (item.parent == previousParent) {
item.depth = previousDepth;
} else if (item.parent != null) {
previousParent = item.parent;
NodeInfo info = infos.get(previousParent);
previousDepth = info.minDepth + 1;
item.depth = previousDepth;
}
}
potentialAncestorIds.add(currentId);
}
void winner() {
resolvedIds.put(currentId, (conflictCtx.winner != null) ? conflictCtx.winner.node : null);
}
boolean loser(DependencyNode node, Object conflictId) {
DependencyNode winner = resolvedIds.get(conflictId);
return winner != null && winner != node;
}
boolean push(DependencyNode node, Object conflictId) throws RepositoryException {
if (conflictId == null) {
if (node.getDependency() != null) {
if (node.getData().get(NODE_DATA_WINNER) != null) {
return false;
}
throw new RepositoryException("missing conflict id for node " + node);
}
} else if (!potentialAncestorIds.contains(conflictId)) {
return false;
}
List<DependencyNode> graphNode = node.getChildren();
if (stack.put(graphNode, Boolean.TRUE) != null) {
return false;
}
int depth = depth();
String scope = deriveScope(node, conflictId);
boolean optional = deriveOptional(node, conflictId);
NodeInfo info = infos.get(graphNode);
if (info == null) {
info = new NodeInfo(depth, scope, optional);
infos.put(graphNode, info);
parentInfos.add(info);
parentNodes.add(node);
parentScopes.add(scope);
parentOptionals.add(optional);
} else {
int changes = info.update(depth, scope, optional);
if (changes == 0) {
stack.remove(graphNode);
return false;
}
parentInfos.add(null); // disable creating new conflict items, we update the existing ones below
parentNodes.add(node);
parentScopes.add(scope);
parentOptionals.add(optional);
if (info.children != null) {
if ((changes & NodeInfo.CHANGE_SCOPE) != 0) {
ListIterator<ConflictItem> itemIterator = info.children.listIterator(info.children.size());
while (itemIterator.hasPrevious()) {
ConflictItem item = itemIterator.previous();
String childScope = deriveScope(item.node, null);
item.addScope(childScope);
}
}
if ((changes & NodeInfo.CHANGE_OPTIONAL) != 0) {
ListIterator<ConflictItem> itemIterator = info.children.listIterator(info.children.size());
while (itemIterator.hasPrevious()) {
ConflictItem item = itemIterator.previous();
boolean childOptional = deriveOptional(item.node, null);
item.addOptional(childOptional);
}
}
}
}
return true;
}
void pop() {
int last = parentInfos.size() - 1;
parentInfos.remove(last);
parentScopes.remove(last);
parentOptionals.remove(last);
DependencyNode node = parentNodes.remove(last);
stack.remove(node.getChildren());
}
void add(DependencyNode node) throws RepositoryException {
DependencyNode parent = parent();
if (parent == null) {
ConflictItem item = newConflictItem(parent, node);
items.add(item);
} else {
NodeInfo info = parentInfos.get(parentInfos.size() - 1);
if (info != null) {
ConflictItem item = newConflictItem(parent, node);
info.add(item);
items.add(item);
}
}
}
private ConflictItem newConflictItem(DependencyNode parent, DependencyNode node) throws RepositoryException {
return new ConflictItem(parent, node, deriveScope(node, null), deriveOptional(node, null));
}
private int depth() {
return parentNodes.size();
}
private DependencyNode parent() {
int size = parentNodes.size();
return (size <= 0) ? null : parentNodes.get(size - 1);
}
private String deriveScope(DependencyNode node, Object conflictId) throws RepositoryException {
if ((node.getManagedBits() & DependencyNode.MANAGED_SCOPE) != 0
|| (conflictId != null && resolvedIds.containsKey(conflictId))) {
return scope(node.getDependency());
}
int depth = parentNodes.size();
scopes(depth, node.getDependency());
if (depth > 0) {
scopeDeriver.deriveScope(scopeCtx);
}
return scopeCtx.derivedScope;
}
private void scopes(int parent, Dependency child) {
scopeCtx.parentScope = (parent > 0) ? parentScopes.get(parent - 1) : null;
scopeCtx.derivedScope = scope(child);
scopeCtx.childScope = scope(child);
}
private String scope(Dependency dependency) {
return (dependency != null) ? dependency.getScope() : null;
}
private boolean deriveOptional(DependencyNode node, Object conflictId) {
Dependency dep = node.getDependency();
boolean optional = (dep != null) && dep.isOptional();
if (optional
|| (node.getManagedBits() & DependencyNode.MANAGED_OPTIONAL) != 0
|| (conflictId != null && resolvedIds.containsKey(conflictId))) {
return optional;
}
int depth = parentNodes.size();
return (depth > 0) ? parentOptionals.get(depth - 1) : false;
}
}
/**
* A context used to hold information that is relevant for deriving the scope of a child dependency.
*
* @see ScopeDeriver
* @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
* change without notice and only exists to enable unit testing.
*/
public static final class ScopeContext {
String parentScope;
String childScope;
String derivedScope;
/**
* Creates a new scope context with the specified properties.
*
* @param parentScope The scope of the parent dependency, may be {@code null}.
* @param childScope The scope of the child dependency, may be {@code null}.
* @noreference This class is not intended to be instantiated by clients in production code, the constructor may
* change without notice and only exists to enable unit testing.
*/
public ScopeContext(String parentScope, String childScope) {
this.parentScope = (parentScope != null) ? parentScope : "";
derivedScope = (childScope != null) ? childScope : "";
this.childScope = (childScope != null) ? childScope : "";
}
/**
* Gets the scope of the parent dependency. This is usually the scope that was derived by earlier invocations of
* the scope deriver.
*
* @return The scope of the parent dependency, never {@code null}.
*/
public String getParentScope() {
return parentScope;
}
/**
* Gets the original scope of the child dependency. This is the scope that was declared in the artifact
* descriptor of the parent dependency.
*
* @return The original scope of the child dependency, never {@code null}.
*/
public String getChildScope() {
return childScope;
}
/**
* Gets the derived scope of the child dependency. This is initially equal to {@link #getChildScope()} until the
* scope deriver makes changes.
*
* @return The derived scope of the child dependency, never {@code null}.
*/
public String getDerivedScope() {
return derivedScope;
}
/**
* Sets the derived scope of the child dependency.
*
* @param derivedScope The derived scope of the dependency, may be {@code null}.
*/
public void setDerivedScope(String derivedScope) {
this.derivedScope = (derivedScope != null) ? derivedScope : "";
}
}
/**
* A conflicting dependency.
*
* @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
* change without notice and only exists to enable unit testing.
*/
public static final class ConflictItem {
// nodes can share child lists, we care about the unique owner of a child node which is the child list
final List<DependencyNode> parent;
// only for debugging/toString() to help identify the parent node(s)
final Artifact artifact;
// is mutable as removeLosers will mutate it (if Verbosity==STANDARD)
DependencyNode node;
int depth;
// we start with String and update to Set<String> if needed
Object scopes;
// bit field of OPTIONAL_FALSE and OPTIONAL_TRUE
int optionalities;
/**
* Bit flag indicating whether one or more paths consider the dependency non-optional.
*/
public static final int OPTIONAL_FALSE = 0x01;
/**
* Bit flag indicating whether one or more paths consider the dependency optional.
*/
public static final int OPTIONAL_TRUE = 0x02;
ConflictItem(DependencyNode parent, DependencyNode node, String scope, boolean optional) {
if (parent != null) {
this.parent = parent.getChildren();
this.artifact = parent.getArtifact();
} else {
this.parent = null;
this.artifact = null;
}
this.node = node;
this.scopes = scope;
this.optionalities = optional ? OPTIONAL_TRUE : OPTIONAL_FALSE;
}
/**
* Creates a new conflict item with the specified properties.
*
* @param parent The parent node of the conflicting dependency, may be {@code null}.
* @param node The conflicting dependency, must not be {@code null}.
* @param depth The zero-based depth of the conflicting dependency.
* @param optionalities The optionalities the dependency was encountered with, encoded as a bit field consisting
* of {@link ConflictResolver.ConflictItem#OPTIONAL_TRUE} and
* {@link ConflictResolver.ConflictItem#OPTIONAL_FALSE}.
* @param scopes The derived scopes of the conflicting dependency, must not be {@code null}.
* @noreference This class is not intended to be instantiated by clients in production code, the constructor may
* change without notice and only exists to enable unit testing.
*/
public ConflictItem(
DependencyNode parent, DependencyNode node, int depth, int optionalities, String... scopes) {
this.parent = (parent != null) ? parent.getChildren() : null;
this.artifact = (parent != null) ? parent.getArtifact() : null;
this.node = node;
this.depth = depth;
this.optionalities = optionalities;
this.scopes = Arrays.asList(scopes);
}
/**
* Determines whether the specified conflict item is a sibling of this item.
*
* @param item The other conflict item, must not be {@code null}.
* @return {@code true} if the given item has the same parent as this item, {@code false} otherwise.
*/
public boolean isSibling(ConflictItem item) {
return parent == item.parent;
}
/**
* Gets the dependency node involved in the conflict.
*
* @return The involved dependency node, never {@code null}.
*/
public DependencyNode getNode() {
return node;
}
/**
* Gets the dependency involved in the conflict, short for {@code getNode.getDependency()}.
*
* @return The involved dependency, never {@code null}.
*/
public Dependency getDependency() {
return node.getDependency();
}
/**
* Gets the zero-based depth at which the conflicting node occurs in the graph. As such, the depth denotes the
* number of parent nodes. If actually multiple paths lead to the node, the return value denotes the smallest
* possible depth.
*
* @return The zero-based depth of the node in the graph.
*/
public int getDepth() {
return depth;
}
/**
* Gets the derived scopes of the dependency. In general, the same dependency node could be reached via
* different paths and each path might result in a different derived scope.
*
* @see ScopeDeriver
* @return The (read-only) set of derived scopes of the dependency, never {@code null}.
*/
@SuppressWarnings("unchecked")
public Collection<String> getScopes() {
if (scopes instanceof String) {
return Collections.singleton((String) scopes);
}
return (Collection<String>) scopes;
}
@SuppressWarnings("unchecked")
void addScope(String scope) {
if (scopes instanceof Collection) {
((Collection<String>) scopes).add(scope);
} else if (!scopes.equals(scope)) {
Collection<Object> set = new HashSet<>();
set.add(scopes);
set.add(scope);
scopes = set;
}
}
/**
* Gets the derived optionalities of the dependency. In general, the same dependency node could be reached via
* different paths and each path might result in a different derived optionality.
*
* @return A bit field consisting of {@link ConflictResolver.ConflictItem#OPTIONAL_FALSE} and/or
* {@link ConflictResolver.ConflictItem#OPTIONAL_TRUE} indicating the derived optionalities the
* dependency was encountered with.
*/
public int getOptionalities() {
return optionalities;
}
void addOptional(boolean optional) {
optionalities |= optional ? OPTIONAL_TRUE : OPTIONAL_FALSE;
}
@Override
public String toString() {
return node + " @ " + depth + " < " + artifact;
}
}
/**
* A context used to hold information that is relevant for resolving version and scope conflicts.
*
* @see VersionSelector
* @see ScopeSelector
* @noinstantiate This class is not intended to be instantiated by clients in production code, the constructor may
* change without notice and only exists to enable unit testing.
*/
public static final class ConflictContext {
final DependencyNode root;
final Map<?, ?> conflictIds;
final Collection<ConflictItem> items;
Object conflictId;
ConflictItem winner;
String scope;