[MNG-7716] ConcurrencyDependencyGraph deadlock if no root can be selected

Co-authored-by: Michael Osipov <michaelo@apache.org>

This closes #250
diff --git a/core-it-suite/src/test/java/org/apache/maven/it/MavenITmng7716BuildDeadlock.java b/core-it-suite/src/test/java/org/apache/maven/it/MavenITmng7716BuildDeadlock.java
new file mode 100644
index 0000000..f1a4ebc
--- /dev/null
+++ b/core-it-suite/src/test/java/org/apache/maven/it/MavenITmng7716BuildDeadlock.java
@@ -0,0 +1,73 @@
+package org.apache.maven.it;
+
+/*
+ * 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.
+ */
+
+import java.io.File;
+import java.util.concurrent.TimeUnit;
+
+import org.apache.maven.shared.verifier.Verifier;
+import org.apache.maven.shared.verifier.util.ResourceExtractor;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.api.Timeout;
+
+/**
+ * This is a test set for
+ * <a href="https://issues.apache.org/jira/browse/MNG-7716">MNG-7716</a>.
+ * Executing the project should not deadlock
+ *
+ */
+class MavenITmng7716BuildDeadlock
+    extends AbstractMavenIntegrationTestCase
+{
+
+    public MavenITmng7716BuildDeadlock()
+    {
+        super( "[3.8.8,3.9.0),[3.9.1,4.0.0-alpha-1),[4.0.0-alpha-5,)" );
+    }
+
+    /**
+     * Verify that maven invocation works (no NPE/error happens).
+     *
+     * @throws Exception in case of failure
+     */
+    @Test
+    @Timeout( value = 120, unit = TimeUnit.SECONDS )
+    void testNoDeadlockAtVersionUpdate()
+        throws Exception
+    {
+        File testDir = ResourceExtractor.simpleExtractResources( getClass(), "/mng-7716" );
+
+        Verifier verifier = newVerifier( testDir.getAbsolutePath() );
+        verifier.addCliArgument( "-f" );
+        verifier.addCliArgument( "settings" );
+        verifier.addCliArgument( "install" );
+        verifier.setLogFileName( "log-settings.txt" );
+        verifier.execute();
+        verifier.verifyErrorFreeLog();
+
+        verifier = newVerifier( testDir.getAbsolutePath() );
+        verifier.addCliArgument( "-T1C" );
+        verifier.addCliArgument( "org.codehaus.mojo:versions-maven-plugin:2.15.0:set" );
+        verifier.addCliArgument( "-DnewVersion=1.2.3" );
+        verifier.execute();
+        verifier.verifyErrorFreeLog();
+    }
+
+}
diff --git a/core-it-suite/src/test/java/org/apache/maven/it/TestSuiteOrdering.java b/core-it-suite/src/test/java/org/apache/maven/it/TestSuiteOrdering.java
index c44203d..c18616c 100644
--- a/core-it-suite/src/test/java/org/apache/maven/it/TestSuiteOrdering.java
+++ b/core-it-suite/src/test/java/org/apache/maven/it/TestSuiteOrdering.java
@@ -105,6 +105,7 @@
          * the tests are to finishing. Newer tests are also more likely to fail, so this is
          * a fail fast technique as well.
          */
+        suite.addTestSuite( MavenITmng7716BuildDeadlock.class );
         suite.addTestSuite( MavenITmng7679SingleMojoNoPomTest.class );
         suite.addTestSuite( MavenITmng7629SubtreeBuildTest.class );
         suite.addTestSuite( MavenITmng7606DependencyImportScopeTest.class );
diff --git a/core-it-suite/src/test/resources-filtered/bootstrap.txt b/core-it-suite/src/test/resources-filtered/bootstrap.txt
index 148c05a..2ff5710 100644
--- a/core-it-suite/src/test/resources-filtered/bootstrap.txt
+++ b/core-it-suite/src/test/resources-filtered/bootstrap.txt
@@ -134,6 +134,7 @@
 org.codehaus.gmavenplus:gmavenplus-plugin:1.11.0
 org.codehaus.mojo:build-helper-maven-plugin:3.2.0
 org.codehaus.mojo:flatten-maven-plugin:1.0.0
+org.codehaus.mojo:versions-maven-plugin:2.15.0
 org.codehaus.plexus:plexus-classworlds:2.5.1
 org.codehaus.plexus:plexus-component-annotations:1.5.5
 org.codehaus.plexus:plexus-component-metadata:1.5.5
diff --git a/core-it-suite/src/test/resources/mng-7716/pom.xml b/core-it-suite/src/test/resources/mng-7716/pom.xml
new file mode 100644
index 0000000..7f0cd80
--- /dev/null
+++ b/core-it-suite/src/test/resources/mng-7716/pom.xml
@@ -0,0 +1,19 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>mng</groupId>
+  <artifactId>base</artifactId>
+  <version>1.2.3</version>
+  <packaging>pom</packaging>
+  <build>
+    <extensions>
+      <extension>
+        <groupId>mng</groupId>
+        <artifactId>settings</artifactId>
+        <version>0.0.1-SNAPSHOT</version>
+      </extension>
+    </extensions>
+  </build>
+  <modules>
+    <module>settings</module>
+  </modules>
+</project>
diff --git a/core-it-suite/src/test/resources/mng-7716/settings/pom.xml b/core-it-suite/src/test/resources/mng-7716/settings/pom.xml
new file mode 100644
index 0000000..e1a0685
--- /dev/null
+++ b/core-it-suite/src/test/resources/mng-7716/settings/pom.xml
@@ -0,0 +1,6 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
+  <modelVersion>4.0.0</modelVersion>
+  <groupId>mng</groupId>
+  <version>0.0.1-SNAPSHOT</version>
+  <artifactId>settings</artifactId>
+</project>
\ No newline at end of file