1 /*
2  * Copyright (C) 2024 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 
17 
18 package com.android.cts.apimap;
19 
20 import com.android.cts.ctsprofiles.MethodProfile;
21 
22 import java.util.ArrayList;
23 import java.util.HashMap;
24 import java.util.List;
25 import java.util.Map;
26 import java.util.Set;
27 import java.util.Stack;
28 
29 /** A class to implement Tarjan's strongly connected components algorithm. */
30 public final class TarJan {
31 
32     private int mTime = 0;
33     private int mNewNodeIndex = 0;
34     private final Map<String, Node> mVertices = new HashMap<>();
35     private final Stack<Node> mStack = new Stack<>();
36     private final Set<String> mResolvedMethods;
37     private final Map<String, Integer> mComponentIDs = new HashMap<>();
38     private final Map<Integer, List<MethodProfile>> mComponentNodes = new HashMap<>();
39 
40     private static final class Node {
41         final int mDfn;
42         final MethodProfile mMethod;
43         int mLow;
44         boolean mInStack;
45 
Node(int index, MethodProfile method)46         Node(int index, MethodProfile method) {
47             mDfn = index;
48             mMethod = method;
49         }
50     }
51 
TarJan(MethodProfile testMethod, Set<String> resolvedMethods)52     public TarJan(MethodProfile testMethod, Set<String> resolvedMethods) {
53         mResolvedMethods = resolvedMethods;
54         tarjan(testMethod);
55     }
56 
57     /** Gets the strongly connected component the given method belongs to. */
getComponentID(String methodSignature)58     public int getComponentID(String methodSignature) {
59         return mComponentIDs.get(methodSignature);
60     }
61 
62     /** Gets a list methods belong to the given strongly connected component. */
getComponent(int id)63     public List<MethodProfile> getComponent(int id) {
64         return mComponentNodes.get(id);
65     }
66 
tarjan(MethodProfile method)67     private Node tarjan(MethodProfile method) {
68         Node v = new Node(mTime++, method);
69         v.mLow = v.mDfn;
70         String methodSignature = method.getMethodSignatureWithClass();
71         mVertices.put(methodSignature, v);
72         mStack.add(v);
73         v.mInStack = true;
74 
75         if (!mResolvedMethods.contains(methodSignature)) {
76             for (MethodProfile callee: method.getCommonMethodCalls().values()) {
77                 String calleeSignature = callee.getMethodSignatureWithClass();
78                 Node w = mVertices.get(calleeSignature);
79                 if (w == null) {
80                     w = tarjan(callee);
81                     v.mLow = Math.min(v.mLow, w.mLow);
82                 } else if (w.mInStack) {
83                     v.mLow = Math.min(v.mLow, w.mDfn);
84                 }
85             }
86         }
87 
88         if (v.mLow == v.mDfn) {
89             Node w;
90             mNewNodeIndex++;
91             mComponentNodes.put(mNewNodeIndex, new ArrayList<>());
92             do {
93                 w = mStack.pop();
94                 mComponentIDs.put(methodSignature, mNewNodeIndex);
95                 mComponentNodes.get(mNewNodeIndex).add(w.mMethod);
96                 w.mInStack = false;
97             } while (!w.equals(v));
98         }
99         return v;
100     }
101 }
102