1/*
2 * Copyright 2023 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17import org.gradle.api.GradleException
18import org.gradle.api.model.ObjectFactory
19import org.gradle.api.initialization.Settings
20
21import javax.annotation.Nullable
22import java.util.regex.Matcher
23import java.util.regex.Pattern
24
25/**
26 * Tracks Gradle projects and their dependencies and provides functionality to get a subset of
27 * projects with their dependencies.
28 *
29 * This class is shared between the main repository and the playground plugin (github).
30 */
31class ProjectDependencyGraph {
32    private Settings settings;
33    private boolean isPlayground;
34    private boolean constraintsEnabled
35    /**
36     * A map of project path to a set of project paths referenced directly by this project.
37     */
38    private Map<String, Set<String>> projectReferences = new HashMap<String, Set<String>>()
39
40    /**
41     * A map of project path to a set of project paths that directly depend on the key project.
42     */
43    private Map<String, Set<String>> projectConsumers = new HashMap<String, Set<String>>()
44
45    private Set<String> publishedLibraryProjects = new HashSet<>()
46
47    /**
48     * A map of all project paths to their project directory.
49     */
50    private Map<String, File> allProjects = new HashMap<String, File>()
51
52    ProjectDependencyGraph(Settings settings, boolean isPlayground, boolean constraintsEnabled) {
53        this.settings = settings
54        this.isPlayground = isPlayground
55        this.constraintsEnabled = constraintsEnabled
56    }
57
58    Set<String> allProjectPaths() {
59        return allProjects.keySet()
60    }
61
62    Map<String, Set<String>> allProjectConsumers() {
63        return projectConsumers
64    }
65
66    /**
67     * Adds the given pair to the list of known projects
68     *
69     * @param projectPath Gradle project path
70     * @param projectDir Gradle project directory
71     */
72    void addToAllProjects(String projectPath, File projectDir) {
73        Set<String> cached = projectReferences.get(projectPath)
74        if (cached != null) {
75            return
76        }
77        allProjects[projectPath] = projectDir
78        Set<String> parsedDependencies = extractReferencesFromBuildFile(projectPath, projectDir)
79        projectReferences[projectPath] = parsedDependencies
80        parsedDependencies.forEach { dependency ->
81            def reverseLookupSet = projectConsumers[dependency] ?: new HashSet<String>()
82            reverseLookupSet.add(projectPath)
83            projectConsumers[dependency] = reverseLookupSet
84        }
85    }
86
87    /**
88     * Returns a set of project path that includes the given `projectPath` as well as any other project
89     * that directly or indirectly depends on `projectPath`
90     */
91    Set<String> findAllProjectsDependingOn(String projectPath) {
92        Set<String> result = new HashSet<String>()
93        ArrayDeque<String> toBeTraversed = new ArrayDeque<String>()
94        toBeTraversed.add(projectPath)
95        while (toBeTraversed.size() > 0) {
96            def path = toBeTraversed.removeFirst()
97            if (result.add(path)) {
98                def dependants = projectConsumers[path]
99                if (dependants != null) {
100                    toBeTraversed.addAll(dependants)
101                }
102            }
103        }
104        return result
105    }
106
107    /**
108     * Returns a list of (projectPath -> projectDir) tuples that include the given filteredProjects
109     * and all of their dependencies (including nested dependencies)
110     *
111     * @param projectPaths The projects which must be included
112     * @return The list of project paths and their directories as a tuple
113     */
114    List<Tuple2<String, File>> getAllProjectsWithDependencies(Set<String> projectPaths) {
115        Set<String> result = new HashSet<String>()
116        projectPaths.forEach {
117            addReferences(it, result)
118        }
119        return result.collect { projectPath ->
120            File projectDir = allProjects[projectPath]
121            if (projectDir == null) {
122                throw new GradleException("cannot find project directory for $projectPath")
123            }
124            new Tuple2(projectPath, projectDir)
125        }
126    }
127
128    private void addReferences(String projectPath, Set<String> target) {
129        if (target.contains(projectPath)) {
130            return // already added
131        }
132        target.add(projectPath)
133        Set<String> allReferences = getOutgoingReferences(projectPath)
134        allReferences.forEach {
135            addReferences(it, target)
136        }
137    }
138
139    private Set<String> getOutgoingReferences(String projectPath) {
140        def references = projectReferences[projectPath]
141        if (references == null) {
142            throw new GradleException("Project $projectPath does not exist.\n" +
143                    "Please check the build.gradle file for your $projectPath project " +
144                    "and update the project dependencies.")
145        }
146        def implicitReferences = findImplicitReferences(projectPath)
147        def constraintReferences = findConstraintReferences(projectPath)
148        return references + implicitReferences + constraintReferences
149    }
150
151    /**
152     * Finds sibling projects that will be needed for constraint publishing. This is necessary
153     * for when androidx.constraints=true is set and automatic atomic group constraints are enabled
154     * meaning that :foo:foo and :foo:foo-bar projects are required even if they don't reference
155     * each other.
156     *
157     * @param projectPath The project path whose sibling projects will be found
158     * @return The set of sibling projects that will be needed for constraint publishing
159     */
160    private Set<String> findConstraintReferences(String projectPath) {
161        Set<String> constraintReferences = new HashSet()
162        if (!constraintsEnabled || !publishedLibraryProjects.contains(projectPath)) return constraintReferences
163        def lastColon = projectPath.lastIndexOf(":")
164        if (lastColon == -1) return constraintReferences
165        allProjectPaths().forEach {
166            if (it.startsWith(projectPath.substring(0, lastColon)) && publishedLibraryProjects.contains(it)) {
167                constraintReferences.add(it)
168            }
169        }
170        return constraintReferences
171    }
172
173
174    /**
175     * Finds implicit dependencies of a project. This is necessary because when ":foo:bar" is
176     * included in Gradle, it automatically also loads ":foo".
177     * @param projectPath The project path whose implicit dependencies will be found
178     *
179     * @return The set of implicit dependencies for projectPath
180     */
181    private Set<String> findImplicitReferences(String projectPath) {
182        Set<String> implicitReferences = new HashSet()
183        for (reference in projectReferences[projectPath]) {
184            String[] segments = reference.substring(1).split(":")
185            String subpath = ""
186            for (int i = 0; i < segments.length; i++) {
187                subpath += ":" + segments[i]
188                if (allProjects.containsKey(subpath)) {
189                    implicitReferences.add(subpath)
190                }
191            }
192        }
193        return implicitReferences
194    }
195
196    /**
197     * Find dependency paths from sourceProjectPaths to targetProjectPath.
198     * @param sourceProjectPaths The project paths whose outgoing references will be traversed
199     * @param targetProjectPath The target project path that will be checked for reachability
200     * @return A list of strings where each item is a representation of a dependency path, in
201     *        the form of: "path1 -> path2 -> path3". This is intended to be human readable.
202     */
203    List<String> findPathsBetween(Set<String> sourceProjectPaths, String targetProjectPath) {
204        return sourceProjectPaths.collect {
205            findPathsBetween(it, targetProjectPath, sourceProjectPaths - it)
206        } - null
207    }
208
209    @Nullable
210    String findPathsBetween(
211            String sourceProjectPath, String targetProjectPath, Set<String> visited
212    ) {
213        if (sourceProjectPath == targetProjectPath) {
214            return targetProjectPath
215        }
216        if (visited.contains(sourceProjectPath)) {
217            return null
218        }
219        Set<String> myReferences = getOutgoingReferences(sourceProjectPath)
220        Set<String> subExclude = visited + sourceProjectPath
221        for (String dependency : myReferences) {
222            String path = findPathsBetween(dependency, targetProjectPath, subExclude)
223            if (path != null) {
224                return "$sourceProjectPath -> $path"
225            }
226        }
227        return null
228    }
229
230    /**
231     * Parses the build file in the given projectDir to find its project dependencies.
232     *
233     * @param projectPath The Gradle projectPath of the project
234     * @param projectDir The project directory on the file system
235     * @return Set of project paths that are dependent by the given project
236     */
237    private Set<String> extractReferencesFromBuildFile(String projectPath, File projectDir) {
238        File buildFile = buildFileNames.findResult { buildFileName ->
239            File candidate = new File(projectDir, buildFileName)
240            return candidate.exists() ? candidate : null
241        }
242        Set<String> links = new HashSet<String>()
243        if (buildFile != null) {
244            def buildGradleProperty = settings.services.get(ObjectFactory).fileProperty()
245                    .fileValue(buildFile)
246            def contents = settings.providers.fileContents(buildGradleProperty)
247                    .getAsText().get()
248            for (line in contents.lines()) {
249                Matcher m = projectReferencePattern.matcher(line)
250                if (m.find()) {
251                    // ignore projectOrArtifact dependencies in playground
252                    def projectOrArtifact = m.group(1) == "projectOrArtifact"
253                    if (!isPlayground || !projectOrArtifact) {
254                        links.add(m.group("name"))
255                    }
256                }
257                if (multilineProjectReference.matcher(line).find()) {
258                    throw new IllegalStateException(
259                            "Multi-line project() references are not supported." +
260                                    "Please fix $file.absolutePath"
261                    )
262                }
263                Matcher targetProject = testProjectTarget.matcher(line)
264                if (targetProject.find()) {
265                    links.add(targetProject.group(1))
266                }
267                Matcher matcherInspection = inspection.matcher(line)
268                if (matcherInspection && !isPlayground) {
269                    // inspection is not supported in playground
270                    links.add(matcherInspection.group(1))
271                }
272                if (composePlugin.matcher(line).find()) {
273                    links.add(":compose:lint:internal-lint-checks")
274                }
275                if (publishedLibrary.matcher(line).find()) {
276                    publishedLibraryProjects.add(projectPath)
277                }
278                Matcher publishProject = publishProjectReference.matcher(line)
279                if (publishProject.find()) {
280                    links.add(publishProject.group(1))
281                }
282            }
283        } else if (!projectDir.exists()) {
284            // Remove file existence checking when https://github.com/gradle/gradle/issues/25531 is
285            // fixed.
286            // This option is supported so that development/simplify_build_failure.sh can try
287            // deleting entire projects at once to identify the cause of a build failure
288            if (System.getenv("ALLOW_MISSING_PROJECTS") == null) {
289                throw new Exception("Path " + buildFile + " does not exist;" +
290                        "cannot include project " + projectPath + " ($projectDir)")
291            }
292        }
293        return links
294    }
295
296    private static Pattern projectReferencePattern = Pattern.compile(
297            "(project|projectOrArtifact)\\((path: )?[\"'](?<name>\\S*)[\"'](, configuration: .*)?\\)"
298    )
299    private static Pattern testProjectTarget = Pattern.compile("targetProjectPath = \"(.*)\"")
300    private static Pattern multilineProjectReference = Pattern.compile("project\\(\$")
301    private static Pattern inspection = Pattern.compile("packageInspector\\(project, \"(.*)\"\\)")
302    private static Pattern composePlugin = Pattern.compile("id\\(\"AndroidXComposePlugin\"\\)")
303    private static Pattern publishedLibrary = Pattern.compile(
304            "(type = SoftwareType\\.(PUBLISHED_LIBRARY|GRADLE_PLUGIN|ANNOTATION_PROCESSOR|ANNOTATION_PROCESSOR_UTILS|OTHER_CODE_PROCESSOR" +
305                    "|STANDALONE_PUBLISHED_LINT|PUBLISHED_LIBRARY_ONLY_USED_BY_KOTLIN_CONSUMERS" +
306                    "|PUBLISHED_TEST_LIBRARY|PUBLISHED_PROTO_LIBRARY|PUBLISHED_KOTLIN_ONLY_TEST_LIBRARY)|" +
307                    "publish = Publish\\.SNAPSHOT_AND_RELEASE)"
308    )
309    private static Pattern publishProjectReference = Pattern.compile("\"(.*):publish\"")
310    private static List<String> buildFileNames = ["build.gradle", "build.gradle.kts"]
311}
312
313ProjectDependencyGraph createProjectDependencyGraph(Settings settings, boolean constraintsEnabled) {
314    return new ProjectDependencyGraph(settings, false /** isPlayground **/, constraintsEnabled)
315}
316// export a function to create ProjectDependencyGraph
317ext.createProjectDependencyGraph = this.&createProjectDependencyGraph
318
319ext.allProjectsConsumers = { ProjectDependencyGraph graph ->
320    graph.allProjectConsumers()
321}
322