Skip to content

Commit c794057

Browse files
ash211Joel Costigliola
ash211
authored and
Joel Costigliola
committed
Fix a performance regression in the recursive comparison related to FieldLocation
FieldLocation maintains set of paths to use in rules ordered from leaf to parent. The set provides O(1) hierarchyMatches operation. Co-authored-by: Andrea Ash <[email protected]> Co-authored-by: David Schlosnagle <[email protected]> Fix #3350
1 parent 9ecb7f4 commit c794057

File tree

4 files changed

+257
-55
lines changed

4 files changed

+257
-55
lines changed

‎assertj-core/src/main/java/org/assertj/core/api/recursive/comparison/FieldLocation.java

+67-55
Original file line numberDiff line numberDiff line change
@@ -14,14 +14,16 @@
1414

1515
import static java.util.Collections.emptyList;
1616
import static java.util.Collections.unmodifiableList;
17+
import static java.util.Collections.unmodifiableSet;
1718
import static java.util.Objects.requireNonNull;
1819
import static java.util.stream.Collectors.joining;
19-
import static java.util.stream.Collectors.toList;
2020
import static org.assertj.core.util.Lists.list;
21+
import static org.assertj.core.util.Sets.newLinkedHashSet;
2122

2223
import java.util.ArrayList;
2324
import java.util.List;
2425
import java.util.Objects;
26+
import java.util.Set;
2527
import java.util.regex.Pattern;
2628

2729
/**
@@ -33,7 +35,7 @@ public final class FieldLocation implements Comparable<FieldLocation> {
3335

3436
private final String pathToUseInRules;
3537
private final List<String> decomposedPath;
36-
private final List<String> pathsHierarchyToUseInRules;
38+
private final Set<String> pathsHierarchyToUseInRules;
3739

3840
public FieldLocation(List<String> path) {
3941
decomposedPath = unmodifiableList(requireNonNull(path, "path cannot be null"));
@@ -45,6 +47,46 @@ public FieldLocation(String s) {
4547
this(list(s.split("\\.")));
4648
}
4749

50+
@Override
51+
public int compareTo(final FieldLocation other) {
52+
return pathToUseInRules.compareTo(other.pathToUseInRules);
53+
}
54+
55+
@Override
56+
public boolean equals(Object obj) {
57+
if (this == obj) return true;
58+
if (!(obj instanceof FieldLocation)) return false;
59+
FieldLocation that = (FieldLocation) obj;
60+
return Objects.equals(pathToUseInRules, that.pathToUseInRules)
61+
&& Objects.equals(decomposedPath, that.decomposedPath)
62+
&& Objects.equals(pathsHierarchyToUseInRules, that.pathsHierarchyToUseInRules);
63+
}
64+
65+
@Override
66+
public int hashCode() {
67+
int result = Objects.hashCode(pathToUseInRules);
68+
result = 31 * result + Objects.hashCode(decomposedPath);
69+
result = 31 * result + Objects.hashCode(pathsHierarchyToUseInRules);
70+
return result;
71+
}
72+
73+
@Override
74+
public String toString() {
75+
return String.format("<%s>", pathToUseInRules);
76+
}
77+
78+
public String shortDescription() {
79+
return pathToUseInRules;
80+
}
81+
82+
private static String pathToUseInRules(List<String> path) {
83+
// remove the array sub-path, so person.children.[2].name -> person.children.name
84+
// rules for ignoring fields don't apply at the element level (ex: children.[2]) but at the group level (ex: children).
85+
return path.stream()
86+
.filter(subpath -> !subpath.startsWith("["))
87+
.collect(joining("."));
88+
}
89+
4890
public boolean exactlyMatches(FieldLocation field) {
4991
return exactlyMatches(field.pathToUseInRules);
5092
}
@@ -126,7 +168,7 @@ public boolean hierarchyMatches(String fieldPath) {
126168
* </code></pre>
127169
*
128170
* @param regex the regex to test
129-
* @return true this fieldLocation or any of its parent matches the given regex., false otherwise.
171+
* @return true, this fieldLocation or any of its parent matches the given regex., false otherwise.
130172
*/
131173
public boolean hierarchyMatchesRegex(Pattern regex) {
132174
return pathsHierarchyToUseInRules.stream().anyMatch(path -> regex.matcher(path).matches());
@@ -146,43 +188,6 @@ public FieldLocation field(String field) {
146188
return new FieldLocation(decomposedPathWithField);
147189
}
148190

149-
@Override
150-
public int compareTo(final FieldLocation other) {
151-
return pathToUseInRules.compareTo(other.pathToUseInRules);
152-
}
153-
154-
@Override
155-
public boolean equals(Object obj) {
156-
if (this == obj) return true;
157-
if (!(obj instanceof FieldLocation)) return false;
158-
FieldLocation that = (FieldLocation) obj;
159-
return Objects.equals(pathToUseInRules, that.pathToUseInRules)
160-
&& Objects.equals(decomposedPath, that.decomposedPath)
161-
&& Objects.equals(pathsHierarchyToUseInRules, that.pathsHierarchyToUseInRules);
162-
}
163-
164-
@Override
165-
public int hashCode() {
166-
return Objects.hash(pathToUseInRules, decomposedPath, pathsHierarchyToUseInRules);
167-
}
168-
169-
@Override
170-
public String toString() {
171-
return String.format("<%s>", pathToUseInRules);
172-
}
173-
174-
public String shortDescription() {
175-
return pathToUseInRules;
176-
}
177-
178-
private static String pathToUseInRules(List<String> path) {
179-
// remove the array sub-path, so person.children.[2].name -> person.children.name
180-
// rules for ignoring fields don't apply at the element level (ex: children.[2]) but at the group level (ex: children).
181-
return path.stream()
182-
.filter(subpath -> !subpath.startsWith("["))
183-
.collect(joining("."));
184-
}
185-
186191
public String getPathToUseInErrorReport() {
187192
return String.join(".", decomposedPath);
188193
}
@@ -193,8 +198,13 @@ public String getFieldName() {
193198
}
194199

195200
public boolean isRoot() {
196-
// root is the top level object compared or in case of the top level is a iterable/array the elements are considered as roots.
197-
// we don't do it for optional it has a 'value' field so for the moment
201+
// Root is the top level object compared or in case of the top level is an iterable/array the elements are
202+
// considered as roots.
203+
// We don't do it for optional since it has a 'value' field (at least for now)
204+
return isRootPath(pathToUseInRules);
205+
}
206+
207+
private boolean isRootPath(String pathToUseInRules) {
198208
return pathToUseInRules.isEmpty();
199209
}
200210

@@ -256,21 +266,23 @@ public boolean hasChild(FieldLocation child) {
256266
return child.hasParent(this);
257267
}
258268

259-
private List<String> pathsHierarchyToUseInRules() {
260-
List<FieldLocation> fieldAndParentFields = list();
261-
FieldLocation currentLocation = this;
262-
while (!currentLocation.isRoot()) {
263-
fieldAndParentFields.add(currentLocation);
264-
currentLocation = currentLocation.parent();
269+
private Set<String> pathsHierarchyToUseInRules() {
270+
// using LinkedHashSet to maintain leaf to root iteration order
271+
// so that hierarchyMatchesRegex can try matching from the longest to the shortest path
272+
Set<String> fieldAndParentFields = newLinkedHashSet();
273+
String currentPath = this.pathToUseInRules;
274+
while (!isRootPath(currentPath)) {
275+
fieldAndParentFields.add(currentPath);
276+
currentPath = parent(currentPath);
265277
}
266-
return fieldAndParentFields.stream()
267-
.map(fieldLocation -> fieldLocation.pathToUseInRules)
268-
.collect(toList());
278+
return unmodifiableSet(fieldAndParentFields);
269279
}
270280

271-
private FieldLocation parent() {
272-
List<String> parentPath = new ArrayList<>(decomposedPath);
273-
parentPath.remove(decomposedPath.size() - 1);
274-
return new FieldLocation(parentPath);
281+
private String parent(String currentPath) {
282+
int lastDot = currentPath.lastIndexOf('.');
283+
if (lastDot < 0) {
284+
return "";
285+
}
286+
return currentPath.substring(0, lastDot);
275287
}
276288
}

‎assertj-core/src/test/java/org/assertj/core/api/recursive/FieldLocation_Test.java

+12
Original file line numberDiff line numberDiff line change
@@ -15,12 +15,15 @@
1515
import static org.assertj.core.api.BDDAssertions.then;
1616
import static org.assertj.core.util.Lists.list;
1717

18+
import java.time.Duration;
1819
import java.util.Collections;
1920
import java.util.List;
2021

2122
import org.assertj.core.api.recursive.comparison.FieldLocation;
2223
import org.junit.jupiter.api.Test;
2324

25+
import com.google.common.base.Stopwatch;
26+
2427
import nl.jqno.equalsverifier.EqualsVerifier;
2528

2629
class FieldLocation_Test {
@@ -73,4 +76,13 @@ void should_build_from_string_nested_path() {
7376
then(underTest.getDecomposedPath()).isEqualTo(list("name", "first", "second"));
7477
}
7578

79+
@Test
80+
void should_build_from_long_nested_path_in_reasonable_time() {
81+
// WHEN
82+
Stopwatch stopwatch = Stopwatch.createStarted();
83+
FieldLocation underTest = new FieldLocation("1.2.3.4.5.6.7.8.9.10");
84+
// THEN
85+
then(stopwatch.elapsed()).isLessThan(Duration.ofSeconds(10));
86+
then(underTest.getDecomposedPath()).isEqualTo(list("1", "2", "3", "4", "5", "6", "7", "8", "9", "10"));
87+
}
7688
}

‎assertj-core/src/test/java/org/assertj/core/api/recursive/comparison/RecursiveComparisonAssert_isEqualTo_Test.java

+120
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@
3232
import java.nio.file.Path;
3333
import java.nio.file.Paths;
3434
import java.sql.Timestamp;
35+
import java.time.Duration;
3536
import java.util.Date;
3637
import java.util.List;
3738
import java.util.Map;
@@ -40,6 +41,7 @@
4041

4142
import javax.xml.datatype.DatatypeFactory;
4243

44+
import com.google.common.base.Stopwatch;
4345
import org.assertj.core.api.RecursiveComparisonAssert_isEqualTo_BaseTest;
4446
import org.assertj.core.internal.objects.data.AlwaysEqualPerson;
4547
import org.assertj.core.internal.objects.data.FriendlyPerson;
@@ -538,6 +540,124 @@ void performance_for_comparing_lots_of_similar_types() {
538540
// config.setIntrospectionStrategy(ComparingFields.COMPARING_FIELDS);
539541

540542
new RecursiveComparisonDifferenceCalculator().determineDifferences(actual, expected, config);
543+
}
541544

545+
@Test
546+
void can_compare_deeply_nested_objects_in_reasonable_time() {
547+
Person p1a = new Person("Alice");
548+
Person p1b = new Person("Alice");
549+
Person p2a = new Person("Brian");
550+
Person p2b = new Person("Brian");
551+
Person p3a = new Person("Christina");
552+
Person p3b = new Person("Christina");
553+
Person p4a = new Person("David");
554+
Person p4b = new Person("David");
555+
Person p5a = new Person("Emily");
556+
Person p5b = new Person("Emily");
557+
Person p6a = new Person("Francisco");
558+
Person p6b = new Person("Francisco");
559+
Person p7a = new Person("Gabriella");
560+
Person p7b = new Person("Gabriella");
561+
Person p8a = new Person("Henry");
562+
Person p8b = new Person("Henry");
563+
Person p9a = new Person("Isabelle");
564+
Person p9b = new Person("Isabelle");
565+
Person p10a = new Person("Jackson");
566+
Person p10b = new Person("Jackson");
567+
Person p11a = new Person("Kimberly");
568+
Person p11b = new Person("Kimberly");
569+
Person p12a = new Person("Lucas");
570+
Person p12b = new Person("Lucas");
571+
Person p13a = new Person("Melissa");
572+
Person p13b = new Person("Melissa");
573+
Person p14a = new Person("Nathan");
574+
Person p14b = new Person("Nathan");
575+
Person p15a = new Person("Olivia");
576+
Person p15b = new Person("Olivia");
577+
Person p16a = new Person("Penelope");
578+
Person p16b = new Person("Penelope");
579+
Person p17a = new Person("Quentin");
580+
Person p17b = new Person("Quentin");
581+
Person p18a = new Person("Rebecca");
582+
Person p18b = new Person("Rebecca");
583+
Person p19a = new Person("Samuel");
584+
Person p19b = new Person("Samuel");
585+
Person p20a = new Person("Tanya");
586+
Person p20b = new Person("Tanya");
587+
Person p21a = new Person("Ursula");
588+
Person p21b = new Person("Ursula");
589+
Person p22a = new Person("Victor");
590+
Person p22b = new Person("Victor");
591+
Person p23a = new Person("Whitney");
592+
Person p23b = new Person("Whitney");
593+
Person p24a = new Person("Xavier");
594+
Person p24b = new Person("Xavier");
595+
Person p25a = new Person("Yasmine");
596+
Person p25b = new Person("Yasmine");
597+
Person p26a = new Person("Zachary");
598+
Person p26b = new Person("Zachary");
599+
p1a.neighbour = p2a;
600+
p1b.neighbour = p2b;
601+
p2a.neighbour = p3a;
602+
p2b.neighbour = p3b;
603+
p3a.neighbour = p4a;
604+
p3b.neighbour = p4b;
605+
p4a.neighbour = p5a;
606+
p4b.neighbour = p5b;
607+
p5a.neighbour = p6a;
608+
p5b.neighbour = p6b;
609+
p6a.neighbour = p7a;
610+
p6b.neighbour = p7b;
611+
p7a.neighbour = p8a;
612+
p7b.neighbour = p8b;
613+
p8a.neighbour = p9a;
614+
p8b.neighbour = p9b;
615+
p9a.neighbour = p10a;
616+
p9b.neighbour = p10b;
617+
p10a.neighbour = p11a;
618+
p10b.neighbour = p11b;
619+
p11a.neighbour = p12a;
620+
p11b.neighbour = p12b;
621+
p12a.neighbour = p13a;
622+
p12b.neighbour = p13b;
623+
p13a.neighbour = p14a;
624+
p13b.neighbour = p14b;
625+
p14a.neighbour = p15a;
626+
p14b.neighbour = p15b;
627+
p15a.neighbour = p16a;
628+
p15b.neighbour = p16b;
629+
p16a.neighbour = p17a;
630+
p16b.neighbour = p17b;
631+
p17a.neighbour = p18a;
632+
p17b.neighbour = p18b;
633+
p18a.neighbour = p19a;
634+
p18b.neighbour = p19b;
635+
p19a.neighbour = p20a;
636+
p19b.neighbour = p20b;
637+
638+
// This fails at 15sec > 10sec on my 2021 Apple M1 Pro. Uncomment more references below to increase the time. Every
639+
// additional link roughly doubles the execution time.
640+
641+
p20a.neighbour = p21a;
642+
p20b.neighbour = p21b;
643+
644+
p21a.neighbour = p22a;
645+
p21b.neighbour = p22b;
646+
647+
p22a.neighbour = p23a;
648+
p22b.neighbour = p23b;
649+
650+
p23a.neighbour = p24a;
651+
p23b.neighbour = p24b;
652+
653+
p24a.neighbour = p25a;
654+
p24b.neighbour = p25b;
655+
656+
p25a.neighbour = p26a;
657+
p25b.neighbour = p26b;
658+
659+
Stopwatch stopwatch = Stopwatch.createStarted();
660+
assertThat(p1a).usingRecursiveComparison().isEqualTo(p1b);
661+
assertThat(stopwatch.elapsed()).isLessThan(Duration.ofSeconds(10));
542662
}
543663
}

0 commit comments

Comments
 (0)