You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@flink.apache.org by ch...@apache.org on 2022/11/14 11:23:03 UTC
[flink] branch master updated: [FLINK-28245][ci] Parse actual Tree structure
This is an automated email from the ASF dual-hosted git repository.
chesnay pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/flink.git
The following commit(s) were added to refs/heads/master by this push:
new 1d28a978b6b [FLINK-28245][ci] Parse actual Tree structure
1d28a978b6b is described below
commit 1d28a978b6ba52850bdb320b661a61b584627f6a
Author: Chesnay Schepler <ch...@apache.org>
AuthorDate: Thu Jun 23 10:40:52 2022 +0200
[FLINK-28245][ci] Parse actual Tree structure
---
.../tools/ci/suffixcheck/ScalaSuffixChecker.java | 6 +-
.../ci/utils/dependency/DependencyParser.java | 82 +++++++++++---
.../tools/ci/utils/shared/DependencyTree.java | 120 +++++++++++++++++++++
.../utils/dependency/DependencyParserTreeTest.java | 13 +--
.../tools/ci/utils/shared/DependencyTreeTest.java | 115 ++++++++++++++++++++
tools/maven/suppressions.xml | 1 +
6 files changed, 313 insertions(+), 24 deletions(-)
diff --git a/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/suffixcheck/ScalaSuffixChecker.java b/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/suffixcheck/ScalaSuffixChecker.java
index 9e125496ff1..b40f7b7ee6d 100644
--- a/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/suffixcheck/ScalaSuffixChecker.java
+++ b/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/suffixcheck/ScalaSuffixChecker.java
@@ -19,6 +19,7 @@ package org.apache.flink.tools.ci.suffixcheck;
import org.apache.flink.tools.ci.utils.dependency.DependencyParser;
import org.apache.flink.tools.ci.utils.shared.Dependency;
+import org.apache.flink.tools.ci.utils.shared.DependencyTree;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -98,7 +99,7 @@ public class ScalaSuffixChecker {
final Set<String> cleanModules = new HashSet<>();
final Set<String> infectedModules = new HashSet<>();
- final Map<String, Set<Dependency>> dependenciesByModule =
+ final Map<String, DependencyTree> dependenciesByModule =
DependencyParser.parseDependencyTreeOutput(path);
for (String module : dependenciesByModule.keySet()) {
@@ -108,7 +109,8 @@ public class ScalaSuffixChecker {
}
LOG.trace("Processing module '{}'.", moduleName);
- final Collection<Dependency> dependencies = dependenciesByModule.get(module);
+ final List<Dependency> dependencies =
+ dependenciesByModule.get(module).flatten().collect(Collectors.toList());
boolean infected = false;
for (Dependency dependency : dependencies) {
diff --git a/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/utils/dependency/DependencyParser.java b/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/utils/dependency/DependencyParser.java
index 53da0007382..ee02c959cbd 100644
--- a/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/utils/dependency/DependencyParser.java
+++ b/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/utils/dependency/DependencyParser.java
@@ -19,6 +19,7 @@ package org.apache.flink.tools.ci.utils.dependency;
import org.apache.flink.annotation.VisibleForTesting;
import org.apache.flink.tools.ci.utils.shared.Dependency;
+import org.apache.flink.tools.ci.utils.shared.DependencyTree;
import java.io.IOException;
import java.nio.file.Files;
@@ -29,6 +30,7 @@ import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
+import java.util.Stack;
import java.util.function.Function;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
@@ -81,7 +83,7 @@ public class DependencyParser {
* Parses the output of a Maven build where {@code dependency:tree} was used, and returns a set
* of dependencies for each module.
*/
- public static Map<String, Set<Dependency>> parseDependencyTreeOutput(Path buildOutput)
+ public static Map<String, DependencyTree> parseDependencyTreeOutput(Path buildOutput)
throws IOException {
return processLines(buildOutput, DependencyParser::parseDependencyTreeOutput);
}
@@ -102,18 +104,18 @@ public class DependencyParser {
}
@VisibleForTesting
- static Map<String, Set<Dependency>> parseDependencyTreeOutput(Stream<String> lines) {
+ static Map<String, DependencyTree> parseDependencyTreeOutput(Stream<String> lines) {
return parseDependencyOutput(
lines,
DEPENDENCY_TREE_NEXT_MODULE_PATTERN,
DependencyParser::parseTreeDependencyBlock);
}
- private static Map<String, Set<Dependency>> parseDependencyOutput(
+ private static <D> Map<String, D> parseDependencyOutput(
Stream<String> lines,
Pattern executionLinePattern,
- Function<Iterator<String>, Set<Dependency>> blockParser) {
- final Map<String, Set<Dependency>> result = new LinkedHashMap<>();
+ Function<Iterator<String>, D> blockParser) {
+ final Map<String, D> result = new LinkedHashMap<>();
final Iterator<String> iterator = lines.iterator();
@@ -138,10 +140,23 @@ public class DependencyParser {
}
private static Set<Dependency> parseCopyDependencyBlock(Iterator<String> block) {
- return parseDependencyBlock(block, DependencyParser::parseCopyDependency);
+ final Set<Dependency> dependencies = new LinkedHashSet<>();
+
+ Optional<Dependency> parsedDependency = parseCopyDependency(block.next());
+ while (parsedDependency.isPresent()) {
+ dependencies.add(parsedDependency.get());
+
+ if (block.hasNext()) {
+ parsedDependency = parseCopyDependency(block.next());
+ } else {
+ parsedDependency = Optional.empty();
+ }
+ }
+
+ return dependencies;
}
- private static Set<Dependency> parseTreeDependencyBlock(Iterator<String> block) {
+ private static DependencyTree parseTreeDependencyBlock(Iterator<String> block) {
// discard one line, which only contains the current module name
block.next();
@@ -149,19 +164,36 @@ public class DependencyParser {
throw new IllegalStateException("Expected more output from the dependency-plugin.");
}
- return parseDependencyBlock(block, DependencyParser::parseTreeDependency);
- }
-
- private static Set<Dependency> parseDependencyBlock(
- Iterator<String> block, Function<String, Optional<Dependency>> lineItemParser) {
- final Set<Dependency> dependencies = new LinkedHashSet<>();
+ final DependencyTree dependencies = new DependencyTree();
- Optional<Dependency> parsedDependency = lineItemParser.apply(block.next());
+ final Stack<Dependency> parentStack = new Stack<>();
+ final Stack<Integer> treeDepthStack = new Stack<>();
+ String line = block.next();
+ Optional<Dependency> parsedDependency = parseTreeDependency(line);
while (parsedDependency.isPresent()) {
- dependencies.add(parsedDependency.get());
+ int treeDepth = getDepth(line);
+
+ while (!treeDepthStack.isEmpty() && treeDepth <= treeDepthStack.peek()) {
+ parentStack.pop();
+ treeDepthStack.pop();
+ }
+
+ final Dependency dependency = parsedDependency.get();
+
+ if (parentStack.isEmpty()) {
+ dependencies.addDirectDependency(dependency);
+ } else {
+ dependencies.addTransitiveDependencyTo(dependency, parentStack.peek());
+ }
+
+ if (treeDepthStack.isEmpty() || treeDepth > treeDepthStack.peek()) {
+ treeDepthStack.push(treeDepth);
+ parentStack.push(dependency);
+ }
if (block.hasNext()) {
- parsedDependency = lineItemParser.apply(block.next());
+ line = block.next();
+ parsedDependency = parseTreeDependency(line);
} else {
parsedDependency = Optional.empty();
}
@@ -201,4 +233,22 @@ public class DependencyParser {
dependencyMatcher.group("scope"),
dependencyMatcher.group("optional") != null));
}
+
+ /**
+ * The depths returned by this method do NOT return a continuous sequence.
+ *
+ * <pre>
+ * +- org.apache.flink:...
+ * | +- org.apache.flink:...
+ * | | \- org.apache.flink:...
+ * ...
+ * </pre>
+ */
+ private static int getDepth(String line) {
+ final int level = line.indexOf('+');
+ if (level != -1) {
+ return level;
+ }
+ return line.indexOf('\\');
+ }
}
diff --git a/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/utils/shared/DependencyTree.java b/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/utils/shared/DependencyTree.java
new file mode 100644
index 00000000000..0d7dd91a85d
--- /dev/null
+++ b/tools/ci/flink-ci-tools/src/main/java/org/apache/flink/tools/ci/utils/shared/DependencyTree.java
@@ -0,0 +1,120 @@
+/*
+ * 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.apache.flink.tools.ci.utils.shared;
+
+import com.google.common.graph.Traverser;
+
+import javax.annotation.Nullable;
+
+import java.util.ArrayList;
+import java.util.LinkedHashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+/**
+ * Represents a dependency tree.
+ *
+ * <p>Every dependency can only occur exactly once.
+ */
+public class DependencyTree {
+
+ private final Map<String, Node> lookup = new LinkedHashMap<>();
+ private final List<Node> directDependencies = new ArrayList<>();
+
+ public void addDirectDependency(Dependency dependency) {
+ final String key = getKey(dependency);
+ if (lookup.containsKey(key)) {
+ return;
+ }
+ final Node node = new Node(dependency, null);
+
+ lookup.put(key, node);
+ directDependencies.add(node);
+ }
+
+ public void addTransitiveDependencyTo(Dependency transitiveDependency, Dependency parent) {
+ final String key = getKey(transitiveDependency);
+ if (lookup.containsKey(key)) {
+ return;
+ }
+ final Node node = lookup.get(getKey(parent)).addTransitiveDependency(transitiveDependency);
+
+ lookup.put(key, node);
+ }
+
+ private static final class Node {
+ private final Dependency dependency;
+ @Nullable private final Node parent;
+ private final List<Node> children = new ArrayList<>();
+
+ private Node(Dependency dependency, @Nullable Node parent) {
+ this.dependency = dependency;
+ this.parent = parent;
+ }
+
+ public Node addTransitiveDependency(Dependency dependency) {
+ final Node node = new Node(dependency, this);
+ this.children.add(node);
+ return node;
+ }
+
+ private boolean isRoot() {
+ return parent == null;
+ }
+ }
+
+ public List<Dependency> getPathTo(Dependency dependency) {
+ final LinkedList<Dependency> path = new LinkedList<>();
+
+ Node node = lookup.get(getKey(dependency));
+ path.addFirst(node.dependency);
+ while (!node.isRoot()) {
+ node = node.parent;
+ path.addFirst(node.dependency);
+ }
+
+ return path;
+ }
+
+ public Stream<Dependency> flatten() {
+ return StreamSupport.stream(
+ Traverser.<Node>forTree(node -> node.children)
+ .depthFirstPreOrder(directDependencies)
+ .spliterator(),
+ false)
+ .map(node -> node.dependency);
+ }
+
+ /**
+ * We don't use the {@link Dependency} as a key because we don't want lookups to be dependent on
+ * scope or the optional flag.
+ *
+ * @param dependency
+ * @return
+ */
+ private static String getKey(Dependency dependency) {
+ return dependency.getGroupId()
+ + ":"
+ + dependency.getArtifactId()
+ + ":"
+ + dependency.getVersion();
+ }
+}
diff --git a/tools/ci/flink-ci-tools/src/test/java/org/apache/flink/tools/ci/utils/dependency/DependencyParserTreeTest.java b/tools/ci/flink-ci-tools/src/test/java/org/apache/flink/tools/ci/utils/dependency/DependencyParserTreeTest.java
index 9e1bbd42d85..260c4c60ace 100644
--- a/tools/ci/flink-ci-tools/src/test/java/org/apache/flink/tools/ci/utils/dependency/DependencyParserTreeTest.java
+++ b/tools/ci/flink-ci-tools/src/test/java/org/apache/flink/tools/ci/utils/dependency/DependencyParserTreeTest.java
@@ -18,11 +18,11 @@
package org.apache.flink.tools.ci.utils.dependency;
import org.apache.flink.tools.ci.utils.shared.Dependency;
+import org.apache.flink.tools.ci.utils.shared.DependencyTree;
import org.junit.jupiter.api.Test;
import java.util.Map;
-import java.util.Set;
import java.util.stream.Stream;
import static org.assertj.core.api.Assertions.assertThat;
@@ -36,7 +36,7 @@ class DependencyParserTreeTest {
"[INFO] internal:m1:jar:1.1",
"[INFO] +- external:dependency1:jar:2.1:compile",
"[INFO] | +- external:dependency2:jar:2.2:compile (optional)",
- "[INFO] | | \\- external:dependency3:jar:2.3:provided (optional)",
+ "[INFO] | | \\- external:dependency3:jar:2.3:provided",
"[INFO] | +- external:dependency4:classifier:jar:2.4:compile",
"[INFO]",
"[INFO] --- maven-dependency-plugin:3.2.0:tree (default-cli) @ m2 ---",
@@ -47,18 +47,19 @@ class DependencyParserTreeTest {
@Test
void testTreeParsing() {
- final Map<String, Set<Dependency>> dependenciesByModule =
+ final Map<String, DependencyTree> dependenciesByModule =
DependencyParser.parseDependencyTreeOutput(getTestDependencyTree());
assertThat(dependenciesByModule).containsOnlyKeys("m1", "m2");
- assertThat(dependenciesByModule.get("m1"))
+ assertThat(dependenciesByModule.get("m1").flatten())
.containsExactlyInAnyOrder(
Dependency.create("external", "dependency1", "2.1", null, "compile", false),
Dependency.create("external", "dependency2", "2.2", null, "compile", true),
- Dependency.create("external", "dependency3", "2.3", null, "provided", true),
+ Dependency.create(
+ "external", "dependency3", "2.3", null, "provided", false),
Dependency.create(
"external", "dependency4", "2.4", "classifier", "compile", false));
- assertThat(dependenciesByModule.get("m2"))
+ assertThat(dependenciesByModule.get("m2").flatten())
.containsExactlyInAnyOrder(
Dependency.create("internal", "m1", "1.1", null, "compile", false),
Dependency.create(
diff --git a/tools/ci/java-ci-tools/src/test/java/org/apache/flink/tools/ci/utils/shared/DependencyTreeTest.java b/tools/ci/java-ci-tools/src/test/java/org/apache/flink/tools/ci/utils/shared/DependencyTreeTest.java
new file mode 100644
index 00000000000..1b8819650f9
--- /dev/null
+++ b/tools/ci/java-ci-tools/src/test/java/org/apache/flink/tools/ci/utils/shared/DependencyTreeTest.java
@@ -0,0 +1,115 @@
+/*
+ * 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.apache.flink.tools.ci.utils.shared;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.function.Supplier;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+class DependencyTreeTest {
+
+ @Test
+ void testGetPathToDirectDependency() {
+ final DependencyTree dependencyTree = new DependencyTree();
+
+ final Dependency dependency = Dependency.create("internal", "m1", "1.0");
+
+ dependencyTree.addDirectDependency(dependency);
+
+ assertThat(dependencyTree.getPathTo(dependency)).containsExactly(dependency);
+ }
+
+ @Test
+ void testGetPathToTransitiveDependency() {
+ final DependencyTree dependencyTree = new DependencyTree();
+
+ final Dependency dependency1 = Dependency.create("internal", "m1", "1.0");
+ final Dependency dependency2 = Dependency.create("internal", "m2", "1.0");
+
+ dependencyTree.addDirectDependency(dependency1);
+ dependencyTree.addTransitiveDependencyTo(dependency2, dependency1);
+
+ assertThat(dependencyTree.getPathTo(dependency2)).containsExactly(dependency1, dependency2);
+ }
+
+ @Test
+ void testFlatten() {
+ final DependencyTree dependencyTree = new DependencyTree();
+
+ final Dependency dependency1 = Dependency.create("internal", "m1", "1.0");
+ final Dependency dependency2 = Dependency.create("internal", "m2", "1.0");
+ final Dependency dependency3 = Dependency.create("internal", "m3", "1.0");
+
+ dependencyTree.addDirectDependency(dependency1);
+ dependencyTree.addTransitiveDependencyTo(dependency2, dependency1);
+ dependencyTree.addDirectDependency(dependency3);
+
+ assertThat(dependencyTree.flatten()).containsExactly(dependency1, dependency2, dependency3);
+ }
+
+ @Test
+ void testUniquenessDirectDependency() {
+ final DependencyTree dependencyTree = new DependencyTree();
+
+ final Dependency dependency = Dependency.create("internal", "m1", "1.0");
+ final Dependency dependencyCopy = Dependency.create("internal", "m1", "1.0");
+
+ dependencyTree.addDirectDependency(dependency);
+ dependencyTree.addDirectDependency(dependencyCopy);
+
+ assertThat(dependencyTree.flatten()).hasSize(1);
+ }
+
+ @Test
+ void testUniquenessTransitiveDependency() {
+ final DependencyTree dependencyTree = new DependencyTree();
+
+ final Dependency directDependency1 = Dependency.create("internal", "m1", "1.0");
+ final Dependency directDependency2 = Dependency.create("internal", "m2", "1.0");
+ final Supplier<Dependency> copySupplier = () -> Dependency.create("internal", "m3", "1.0");
+
+ dependencyTree.addDirectDependency(directDependency1);
+ dependencyTree.addDirectDependency(directDependency2);
+ dependencyTree.addTransitiveDependencyTo(copySupplier.get(), directDependency1);
+ dependencyTree.addTransitiveDependencyTo(copySupplier.get(), directDependency2);
+
+ assertThat(dependencyTree.flatten()).hasSize(3);
+ assertThat(dependencyTree.getPathTo(copySupplier.get()))
+ .containsExactly(directDependency1, copySupplier.get());
+ }
+
+ @Test
+ void testLookupIgnoresOptionalFlagAndScope() {
+ final DependencyTree dependencyTree = new DependencyTree();
+
+ final Dependency slimDependency = Dependency.create("internal", "m1", "1.0");
+ final Dependency extendedDependency =
+ Dependency.create(
+ slimDependency.getGroupId(),
+ slimDependency.getArtifactId(),
+ slimDependency.getVersion(),
+ "compile",
+ false);
+
+ dependencyTree.addDirectDependency(extendedDependency);
+
+ assertThat(dependencyTree.getPathTo(slimDependency)).containsExactly(extendedDependency);
+ }
+}
diff --git a/tools/maven/suppressions.xml b/tools/maven/suppressions.xml
index a6d9158534b..747279a23aa 100644
--- a/tools/maven/suppressions.xml
+++ b/tools/maven/suppressions.xml
@@ -32,6 +32,7 @@ under the License.
<suppress files="NoticeFileChecker.java" checks="Regexp"/>
<suppress files="NoticeFileChecker.java" checks="IllegalImport"/>
<suppress files="NoticeFileCheckerTest.java" checks="IllegalImport"/>
+ <suppress files="DependencyTree.java" checks="IllegalImport"/>
<suppress files="JoinOperator.java" checks="FileLength"/>
<suppress files="WindowOperatorTest.java" checks="FileLength"/>