1 //=- ClangSACheckersEmitter.cpp - Generate Clang SA checkers tables -*- C++ -*-
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This tablegen backend emits Clang Static Analyzer checkers tables.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/DenseSet.h"
15 #include "llvm/TableGen/Error.h"
16 #include "llvm/TableGen/Record.h"
17 #include "llvm/TableGen/TableGenBackend.h"
18 #include <map>
19 #include <string>
20 using namespace llvm;
21 
22 //===----------------------------------------------------------------------===//
23 // Static Analyzer Checkers Tables generation
24 //===----------------------------------------------------------------------===//
25 
26 /// True if it is specified hidden or a parent package is specified
27 /// as hidden, otherwise false.
28 static bool isHidden(const Record &R) {
29   if (R.getValueAsBit("Hidden"))
30     return true;
31   // Not declared as hidden, check the parent package if it is hidden.
32   if (DefInit *DI = dyn_cast<DefInit>(R.getValueInit("ParentPackage")))
33     return isHidden(*DI->getDef());
34 
35   return false;
36 }
37 
38 static bool isCheckerNamed(const Record *R) {
39   return !R->getValueAsString("CheckerName").empty();
40 }
41 
42 static std::string getPackageFullName(const Record *R);
43 
44 static std::string getParentPackageFullName(const Record *R) {
45   std::string name;
46   if (DefInit *DI = dyn_cast<DefInit>(R->getValueInit("ParentPackage")))
47     name = getPackageFullName(DI->getDef());
48   return name;
49 }
50 
51 static std::string getPackageFullName(const Record *R) {
52   std::string name = getParentPackageFullName(R);
53   if (!name.empty()) name += ".";
54   name += R->getValueAsString("PackageName");
55   return name;
56 }
57 
58 static std::string getCheckerFullName(const Record *R) {
59   std::string name = getParentPackageFullName(R);
60   if (isCheckerNamed(R)) {
61     if (!name.empty()) name += ".";
62     name += R->getValueAsString("CheckerName");
63   }
64   return name;
65 }
66 
67 static std::string getStringValue(const Record &R, StringRef field) {
68   if (StringInit *SI = dyn_cast<StringInit>(R.getValueInit(field)))
69     return SI->getValue();
70   return std::string();
71 }
72 
73 namespace {
74 struct GroupInfo {
75   llvm::DenseSet<const Record*> Checkers;
76   llvm::DenseSet<const Record *> SubGroups;
77   bool Hidden;
78   unsigned Index;
79 
80   GroupInfo() : Hidden(false) { }
81 };
82 }
83 
84 static void addPackageToCheckerGroup(const Record *package, const Record *group,
85                   llvm::DenseMap<const Record *, GroupInfo *> &recordGroupMap) {
86   llvm::DenseSet<const Record *> &checkers = recordGroupMap[package]->Checkers;
87   for (llvm::DenseSet<const Record *>::iterator
88          I = checkers.begin(), E = checkers.end(); I != E; ++I)
89     recordGroupMap[group]->Checkers.insert(*I);
90 
91   llvm::DenseSet<const Record *> &subGroups = recordGroupMap[package]->SubGroups;
92   for (llvm::DenseSet<const Record *>::iterator
93          I = subGroups.begin(), E = subGroups.end(); I != E; ++I)
94     addPackageToCheckerGroup(*I, group, recordGroupMap);
95 }
96 
97 namespace clang {
98 void EmitClangSACheckers(RecordKeeper &Records, raw_ostream &OS) {
99   std::vector<Record*> checkers = Records.getAllDerivedDefinitions("Checker");
100   llvm::DenseMap<const Record *, unsigned> checkerRecIndexMap;
101   for (unsigned i = 0, e = checkers.size(); i != e; ++i)
102     checkerRecIndexMap[checkers[i]] = i;
103 
104   // Invert the mapping of checkers to package/group into a one to many
105   // mapping of packages/groups to checkers.
106   std::map<std::string, GroupInfo> groupInfoByName;
107   llvm::DenseMap<const Record *, GroupInfo *> recordGroupMap;
108 
109   std::vector<Record*> packages = Records.getAllDerivedDefinitions("Package");
110   for (unsigned i = 0, e = packages.size(); i != e; ++i) {
111     Record *R = packages[i];
112     std::string fullName = getPackageFullName(R);
113     if (!fullName.empty()) {
114       GroupInfo &info = groupInfoByName[fullName];
115       info.Hidden = isHidden(*R);
116       recordGroupMap[R] = &info;
117     }
118   }
119 
120   std::vector<Record*>
121       checkerGroups = Records.getAllDerivedDefinitions("CheckerGroup");
122   for (unsigned i = 0, e = checkerGroups.size(); i != e; ++i) {
123     Record *R = checkerGroups[i];
124     std::string name = R->getValueAsString("GroupName");
125     if (!name.empty()) {
126       GroupInfo &info = groupInfoByName[name];
127       recordGroupMap[R] = &info;
128     }
129   }
130 
131   for (unsigned i = 0, e = checkers.size(); i != e; ++i) {
132     Record *R = checkers[i];
133     Record *package = nullptr;
134     if (DefInit *
135           DI = dyn_cast<DefInit>(R->getValueInit("ParentPackage")))
136       package = DI->getDef();
137     if (!isCheckerNamed(R) && !package)
138       PrintFatalError(R->getLoc(), "Checker '" + R->getName() +
139                       "' is neither named, nor in a package!");
140 
141     if (isCheckerNamed(R)) {
142       // Create a pseudo-group to hold this checker.
143       std::string fullName = getCheckerFullName(R);
144       GroupInfo &info = groupInfoByName[fullName];
145       info.Hidden = R->getValueAsBit("Hidden");
146       recordGroupMap[R] = &info;
147       info.Checkers.insert(R);
148     } else {
149       recordGroupMap[package]->Checkers.insert(R);
150     }
151 
152     Record *currR = isCheckerNamed(R) ? R : package;
153     // Insert the checker and its parent packages into the subgroups set of
154     // the corresponding parent package.
155     while (DefInit *DI
156              = dyn_cast<DefInit>(currR->getValueInit("ParentPackage"))) {
157       Record *parentPackage = DI->getDef();
158       recordGroupMap[parentPackage]->SubGroups.insert(currR);
159       currR = parentPackage;
160     }
161     // Insert the checker into the set of its group.
162     if (DefInit *DI = dyn_cast<DefInit>(R->getValueInit("Group")))
163       recordGroupMap[DI->getDef()]->Checkers.insert(R);
164   }
165 
166   // If a package is in group, add all its checkers and its sub-packages
167   // checkers into the group.
168   for (unsigned i = 0, e = packages.size(); i != e; ++i)
169     if (DefInit *DI = dyn_cast<DefInit>(packages[i]->getValueInit("Group")))
170       addPackageToCheckerGroup(packages[i], DI->getDef(), recordGroupMap);
171 
172   typedef std::map<std::string, const Record *> SortedRecords;
173   typedef llvm::DenseMap<const Record *, unsigned> RecToSortIndex;
174 
175   SortedRecords sortedGroups;
176   RecToSortIndex groupToSortIndex;
177   OS << "\n#ifdef GET_GROUPS\n";
178   {
179     for (unsigned i = 0, e = checkerGroups.size(); i != e; ++i)
180       sortedGroups[checkerGroups[i]->getValueAsString("GroupName")]
181                    = checkerGroups[i];
182 
183     unsigned sortIndex = 0;
184     for (SortedRecords::iterator
185            I = sortedGroups.begin(), E = sortedGroups.end(); I != E; ++I) {
186       const Record *R = I->second;
187 
188       OS << "GROUP(" << "\"";
189       OS.write_escaped(R->getValueAsString("GroupName")) << "\"";
190       OS << ")\n";
191 
192       groupToSortIndex[R] = sortIndex++;
193     }
194   }
195   OS << "#endif // GET_GROUPS\n\n";
196 
197   OS << "\n#ifdef GET_PACKAGES\n";
198   {
199     SortedRecords sortedPackages;
200     for (unsigned i = 0, e = packages.size(); i != e; ++i)
201       sortedPackages[getPackageFullName(packages[i])] = packages[i];
202 
203     for (SortedRecords::iterator
204            I = sortedPackages.begin(), E = sortedPackages.end(); I != E; ++I) {
205       const Record &R = *I->second;
206 
207       OS << "PACKAGE(" << "\"";
208       OS.write_escaped(getPackageFullName(&R)) << "\", ";
209       // Group index
210       if (DefInit *DI = dyn_cast<DefInit>(R.getValueInit("Group")))
211         OS << groupToSortIndex[DI->getDef()] << ", ";
212       else
213         OS << "-1, ";
214       // Hidden bit
215       if (isHidden(R))
216         OS << "true";
217       else
218         OS << "false";
219       OS << ")\n";
220     }
221   }
222   OS << "#endif // GET_PACKAGES\n\n";
223 
224   OS << "\n#ifdef GET_CHECKERS\n";
225   for (unsigned i = 0, e = checkers.size(); i != e; ++i) {
226     const Record &R = *checkers[i];
227 
228     OS << "CHECKER(" << "\"";
229     std::string name;
230     if (isCheckerNamed(&R))
231       name = getCheckerFullName(&R);
232     OS.write_escaped(name) << "\", ";
233     OS << R.getName() << ", ";
234     OS << getStringValue(R, "DescFile") << ", ";
235     OS << "\"";
236     OS.write_escaped(getStringValue(R, "HelpText")) << "\", ";
237     // Group index
238     if (DefInit *DI = dyn_cast<DefInit>(R.getValueInit("Group")))
239       OS << groupToSortIndex[DI->getDef()] << ", ";
240     else
241       OS << "-1, ";
242     // Hidden bit
243     if (isHidden(R))
244       OS << "true";
245     else
246       OS << "false";
247     OS << ")\n";
248   }
249   OS << "#endif // GET_CHECKERS\n\n";
250 
251   unsigned index = 0;
252   for (std::map<std::string, GroupInfo>::iterator
253          I = groupInfoByName.begin(), E = groupInfoByName.end(); I != E; ++I)
254     I->second.Index = index++;
255 
256   // Walk through the packages/groups/checkers emitting an array for each
257   // set of checkers and an array for each set of subpackages.
258 
259   OS << "\n#ifdef GET_MEMBER_ARRAYS\n";
260   unsigned maxLen = 0;
261   for (std::map<std::string, GroupInfo>::iterator
262          I = groupInfoByName.begin(), E = groupInfoByName.end(); I != E; ++I) {
263     maxLen = std::max(maxLen, (unsigned)I->first.size());
264 
265     llvm::DenseSet<const Record *> &checkers = I->second.Checkers;
266     if (!checkers.empty()) {
267       OS << "static const short CheckerArray" << I->second.Index << "[] = { ";
268       // Make the output order deterministic.
269       std::map<int, const Record *> sorted;
270       for (llvm::DenseSet<const Record *>::iterator
271              I = checkers.begin(), E = checkers.end(); I != E; ++I)
272         sorted[(*I)->getID()] = *I;
273 
274       for (std::map<int, const Record *>::iterator
275              I = sorted.begin(), E = sorted.end(); I != E; ++I)
276         OS << checkerRecIndexMap[I->second] << ", ";
277       OS << "-1 };\n";
278     }
279 
280     llvm::DenseSet<const Record *> &subGroups = I->second.SubGroups;
281     if (!subGroups.empty()) {
282       OS << "static const short SubPackageArray" << I->second.Index << "[] = { ";
283       // Make the output order deterministic.
284       std::map<int, const Record *> sorted;
285       for (llvm::DenseSet<const Record *>::iterator
286              I = subGroups.begin(), E = subGroups.end(); I != E; ++I)
287         sorted[(*I)->getID()] = *I;
288 
289       for (std::map<int, const Record *>::iterator
290              I = sorted.begin(), E = sorted.end(); I != E; ++I) {
291         OS << recordGroupMap[I->second]->Index << ", ";
292       }
293       OS << "-1 };\n";
294     }
295   }
296   OS << "#endif // GET_MEMBER_ARRAYS\n\n";
297 
298   OS << "\n#ifdef GET_CHECKNAME_TABLE\n";
299   for (std::map<std::string, GroupInfo>::iterator
300          I = groupInfoByName.begin(), E = groupInfoByName.end(); I != E; ++I) {
301     // Group option string.
302     OS << "  { \"";
303     OS.write_escaped(I->first) << "\","
304                                << std::string(maxLen-I->first.size()+1, ' ');
305 
306     if (I->second.Checkers.empty())
307       OS << "0, ";
308     else
309       OS << "CheckerArray" << I->second.Index << ", ";
310 
311     // Subgroups.
312     if (I->second.SubGroups.empty())
313       OS << "0, ";
314     else
315       OS << "SubPackageArray" << I->second.Index << ", ";
316 
317     OS << (I->second.Hidden ? "true" : "false");
318 
319     OS << " },\n";
320   }
321   OS << "#endif // GET_CHECKNAME_TABLE\n\n";
322 }
323 } // end namespace clang
324