1 
2 #include <magic/support/EDIType.h>
3 
4 using namespace llvm;
5 
6 namespace llvm {
7 
8 #define DEBUG_EDI_EQUALS        0
9 int debugEDIEquals = 0;
10 
11 //===----------------------------------------------------------------------===//
12 // Constructors, destructor, and operators
13 //===----------------------------------------------------------------------===//
14 
15 EDIType::EDIType(const MDNode *N, bool norm, bool checkOpaqueTypes) : aDIType(N) {
16     init(norm, checkOpaqueTypes);
17 }
18 
19 EDIType::EDIType(bool norm, bool checkOpaqueTypes) : aDIType() {
20     init(norm, checkOpaqueTypes);
21 }
22 
23 EDIType::EDIType(const DIType aDIType, bool norm, bool checkOpaqueTypes) : aDIType(aDIType) {
24     init(norm, checkOpaqueTypes);
25 }
26 
27 bool EDIType::operator == (const EDIType& aEDIType) const {
28     const DIType oDIType = *(aEDIType.getDIType());
29     return (aDIType == oDIType);
30 }
31 
32 //===----------------------------------------------------------------------===//
33 // Getters
34 //===----------------------------------------------------------------------===//
35 
36 const std::string EDIType::getDescription(int skipUnions, int skipStructs, int allowMultiNames) const {
37     std::string string;
38     raw_string_ostream ostream(string);
39     printDescription(ostream, skipUnions, skipStructs, allowMultiNames);
40     ostream.flush();
41     return string;
42 }
43 
44 const EDIType& EDIType::getContainedType(unsigned i, bool norm) const {
45     static EDIType subType;
46     EDIType_assert(!isBasicType() && !isVoidTy() && !isEnumTy());
47     bool isArrayOrVectorTy = isArrayTy() || isVectorTy();
48     if(isDerivedType() || isArrayOrVectorTy) {
49         EDIType_assert(i == 0);
50         if(isArrayOrVectorTy && getCurrentDimension() < getNumDimensions()-1) {
51             subType = *this;
52             subType.setCurrentDimension(getCurrentDimension() + 1);
53         }
54         else {
55             subType = getTypeDerivedFrom();
56         }
57         return subType;
58     }
59     DIArray aDIArray = getTypeArray();
60     unsigned numContainedTypes = aDIArray.getNumElements();
61     assert(i < numContainedTypes);
62     EDIType tmpType((const DIType) aDIArray.getElement(i), norm);
63     subType = tmpType;
64     return subType;
65 }
66 
67 unsigned EDIType::getNumContainedTypes() const {
68     if(isBasicType() || isVoidTy() || isEnumTy()) {
69         return 0;
70     }
71     bool isArrayOrVectorTy = isArrayTy() || isVectorTy();
72     if(isDerivedType() || isArrayOrVectorTy) {
73         return 1;
74     }
75     DIArray aDIArray = getTypeArray();
76     unsigned numContainedTypes = aDIArray.getNumElements();
77     return numContainedTypes;
78 }
79 
80 const DIDerivedType& EDIType::getMember(unsigned i) const {
81     static DIDerivedType aDIDerivedType;
82     EDIType_assert(isUnionOrStructTy());
83     DIArray aDIArray = getTypeArray();
84     DIDescriptor aDIDescriptor = aDIArray.getElement(i);
85     assert(aDIDescriptor.getTag() == dwarf::DW_TAG_member);
86     aDIDerivedType = (DIDerivedType) aDIDescriptor;
87     return aDIDerivedType;
88 }
89 
90 bool EDIType::isUnionOrStructTy(bool isStruct, bool isUnion) const {
91     if(isOpaqueTy()) {
92         return false;
93     }
94     if((isStruct && getTag() == dwarf::DW_TAG_structure_type) ||
95         (isUnion && getTag() == dwarf::DW_TAG_union_type)) {
96         EDIType_assert(isCompositeType());
97         return true;
98     }
99     return false;
100 }
101 
102 bool EDIType::hasInnerPointers() const {
103     if(isOpaqueTy() || isFunctionTy()) {
104         return false;
105     }
106     if(isPointerTy()) {
107         return true;
108     }
109 
110     unsigned numContainedTypes = getNumContainedTypes();
111     if(numContainedTypes == 0) {
112         return false;
113     }
114     else if(isArrayTy() || isVectorTy()) {
115         const EDIType subType = getContainedType(0);
116         return subType.hasInnerPointers();
117     }
118     else {
119         assert(isUnionOrStructTy());
120         for(unsigned i=0;i<numContainedTypes;i++) {
121             const EDIType subType = getContainedType(i);
122             if(subType.hasInnerPointers()) {
123                 return true;
124             }
125         }
126    }
127 
128    return false;
129 }
130 
131 DIArray EDIType::getTypeArray() const {
132     static std::set<std::string> nonOpaqueEmptyTypes;
133     static std::set<std::string>::iterator nonOpaqueEmptyTypesIt;
134     EDIType_assert(isCompositeType());
135     DIArray aDIArray = ((const DICompositeType)aDIType).getTypeArray();
136     if(aDIArray.getNumElements() == 0 && checkOpaqueTypes && myNames.size() > 0) {
137         const EDIType *aType = NULL;
138         std::string name;
139         for(int i=myNames.size()-1;i>=0;i--) {
140             name = myNames[i];
141             aType = getStructEDITypeByName(name);
142             if(aType) {
143                 break;
144             }
145         }
146         if(aType) {
147             aDIArray = ((const DICompositeType *)aType->getDIType())->getTypeArray();
148             nonOpaqueEmptyTypesIt = nonOpaqueEmptyTypes.find(name);
149             if(nonOpaqueEmptyTypesIt == nonOpaqueEmptyTypes.end()) {
150                 EDITypeLog("Found a non-opaque composite type with 0 members! Name is: " << name);
151                 nonOpaqueEmptyTypes.insert(name);
152             }
153         }
154     }
155     return aDIArray;
156 }
157 
158 const EDIType* EDIType::getTopStructType(unsigned index) const {
159     static unsigned level = 0;
160     static unsigned structsLeft;
161     static EDIType targetType;
162 
163     if(level == 0) {
164         structsLeft = index;
165     }
166 
167     if(isUnionOrStructTy() || isOpaqueTy()) {
168         if(structsLeft == 0) {
169             targetType = *this;
170             return &targetType;
171         }
172         else {
173             structsLeft--;
174             return NULL;
175         }
176     }
177     unsigned numContainedTypes = getNumContainedTypes();
178     for(unsigned i=0;i<numContainedTypes;i++) {
179         const EDIType containedType(getContainedType(i));
180         level++;
181         const EDIType *topStructType = containedType.getTopStructType(index);
182         level--;
183         if(topStructType != NULL) {
184             return topStructType;
185         }
186     }
187     return NULL;
188 }
189 
190 //===----------------------------------------------------------------------===//
191 // Other public methods
192 //===----------------------------------------------------------------------===//
193 
194 void EDIType::print(raw_ostream &OS) const {
195      OS << getDescription();
196 }
197 
198 void EDIType::printDescription(raw_ostream &OS, int skipUnions, int skipStructs, int allowMultiNames) const {
199     static std::vector<const EDIType*> nestedTypes;
200     int printMultiNames = allowMultiNames && myNames.size() > 1;
201     if(allowMultiNames && !printMultiNames && isPointerTy() && myName.compare("")) {
202         printMultiNames = 1;
203     }
204 
205     if(isOpaqueTy()) {
206         OS << "opaque";
207         return;
208     }
209 
210     unsigned numContainedTypes = getNumContainedTypes();
211     if(numContainedTypes == 0) {
212         OS << (printMultiNames ? getNamesString() : getName());
213         return;
214     }
215 
216     if(isPointerTy() && getContainedType(0).isUnionOrStructTy()) {
217         bool isNestedType = false;
218         unsigned j;
219         for(j=0;j<nestedTypes.size();j++) {
220             if(nestedTypes[j]->equals(this)) {
221                 isNestedType = true;
222                 break;
223             }
224         }
225         if(isNestedType) {
226             OS << "\\" << nestedTypes.size() - j;
227             return;
228         }
229     }
230 
231     nestedTypes.push_back(this);
232     if(isPointerTy()) {
233         const EDIType subType = getContainedType(0);
234         subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
235         OS << "*";
236         if(printMultiNames) {
237             OS << "|" << getNamesString();
238         }
239     }
240     else if(isArrayTy() || isVectorTy()) {
241         const EDIType subType = getContainedType(0);
242         unsigned numElements = getNumElements();
243         char startSep = isArrayTy() ? '[' : '<';
244         char endSep = isArrayTy() ? ']' : '>';
245         OS << startSep;
246         if(numElements) {
247             OS << numElements << " x ";
248         }
249         subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
250         OS << endSep;
251     }
252     else if(isUnionOrStructTy()) {
253         if(skipUnions && isUnionTy()) {
254             OS << "(U) $" << (printMultiNames ? getNamesString() : (myName.compare("") ? myName : "ANONYMOUS"));
255             nestedTypes.pop_back();
256             return;
257         }
258         if(skipStructs && isStructTy()) {
259             OS << "$" << (printMultiNames ? getNamesString() : (myName.compare("") ? myName : "ANONYMOUS"));
260             nestedTypes.pop_back();
261             return;
262         }
263         unsigned numContainedTypes = getNumContainedTypes();
264         OS << "{ ";
265         if(isUnionTy()) {
266             OS << "(U) ";
267         }
268         OS << "$" << (printMultiNames ? getNamesString() : (myName.compare("") ? myName : "ANONYMOUS")) << " ";
269         for(unsigned i=0;i<numContainedTypes;i++) {
270             if(i > 0) {
271                 OS << ", ";
272             }
273             EDIType subType = getContainedType(i);
274             subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
275         }
276         OS << " }";
277    }
278    else if(isFunctionTy()) {
279        unsigned numContainedTypes = getNumContainedTypes();
280        assert(numContainedTypes > 0);
281        EDIType subType = getContainedType(0);
282        subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
283        numContainedTypes--;
284        OS << " (";
285        for(unsigned i=0;i<numContainedTypes;i++) {
286            if(i > 0) {
287                OS << ", ";
288            }
289            subType = getContainedType(i+1);
290            subType.printDescription(OS, skipUnions, skipStructs, allowMultiNames);
291        }
292        OS << ")";
293    }
294    else {
295        OS << "???";
296    }
297    nestedTypes.pop_back();
298 }
299 
300 bool EDIType::equals(const EDIType *other) const {
301     static std::set<std::pair<MDNode*, MDNode*> > compatibleMDNodes;
302     static std::set<std::pair<MDNode*, MDNode*> >::iterator compatibleMDNodesIt;
303     static int max_recursive_steps = -1;
304 #if DEBUG_EDI_EQUALS
305     if(debugEDIEquals>1) EDITypeErr("COMPARING :" << getTag() << ":" << getName() << " VS " << other->getTag() << ":" << other->getName());
306 #endif
307     if(isOpaqueTy() || other->isOpaqueTy()) {
308 #if DEBUG_EDI_EQUALS
309         if(debugEDIEquals) EDITypeErr("----> ???1");
310 #endif
311         return isOpaqueTy() && other->isOpaqueTy();
312     }
313     if(getTag() != other->getTag()) {
314 #if DEBUG_EDI_EQUALS
315         if(debugEDIEquals) EDITypeErr("----> false1");
316 #endif
317         return false;
318     }
319     unsigned numContainedTypes = getNumContainedTypes();
320     unsigned numOtherContainedTypes = other->getNumContainedTypes();
321     if(numContainedTypes != numOtherContainedTypes) {
322 #if DEBUG_EDI_EQUALS
323         if(debugEDIEquals) EDITypeErr("----> false2");
324 #endif
325         return false;
326     }
327     if(getNumElements() != other->getNumElements()) {
328 #if DEBUG_EDI_EQUALS
329         if(debugEDIEquals) EDITypeErr("----> false3");
330 #endif
331         return false;
332     }
333     if(myName.compare(other->getName())) {
334 #if DEBUG_EDI_EQUALS
335         if(debugEDIEquals) EDITypeErr("----> false4");
336 #endif
337         return false;
338     }
339     if((myNames.size() > 0 || other->getNames().size() > 0) && getNamesString().compare(other->getNamesString())) {
340 #if DEBUG_EDI_EQUALS
341         if(debugEDIEquals) EDITypeErr("----> false5");
342 #endif
343         return false;
344     }
345     if(numContainedTypes == 0) {
346 #if DEBUG_EDI_EQUALS
347         if(debugEDIEquals) EDITypeErr("----> true1");
348 #endif
349         return true;
350     }
351     MDNode *aNode = *(&aDIType);
352     MDNode *otherNode = *(other->getDIType());
353     if(aNode == otherNode) {
354 #if DEBUG_EDI_EQUALS
355         if(debugEDIEquals) EDITypeErr("----> true2");
356 #endif
357         return true;
358     }
359     int isUnionOrStruct = isUnionOrStructTy();
360     int isNonAnonUnionOrStruct = isUnionOrStruct && myName.size() > 0;
361     int saved_max_recursive_steps = max_recursive_steps;
362     if(max_recursive_steps == -1 && isNonAnonUnionOrStruct) {
363         //A simple way to break recursion for recursive non-anonymous structs/unions.
364         max_recursive_steps = 10;
365     }
366     else if(max_recursive_steps == 0) {
367 #if DEBUG_EDI_EQUALS
368         if(debugEDIEquals) EDITypeErr("----> true4");
369 #endif
370         return true;
371     }
372     else {
373         max_recursive_steps--;
374     }
375     for(unsigned i=0;i<numContainedTypes;i++) {
376         const EDIType &subEDIType = getContainedType(i);
377         const EDIType &subOtherEDIType = other->getContainedType(i);
378         if(!subEDIType.equals(&subOtherEDIType)) {
379             max_recursive_steps = saved_max_recursive_steps;
380             return false;
381         }
382     }
383     max_recursive_steps = saved_max_recursive_steps;
384     return true;
385 }
386 
387 //===----------------------------------------------------------------------===//
388 // Public static methods
389 //===----------------------------------------------------------------------===//
390 
391 std::string EDIType::lookupTypedefName(std::string &typedefName) {
392     static std::string noName;
393     for (DebugInfoFinder::iterator I = DIFinder.type_begin(),
394         E = DIFinder.type_end(); I != E; ++I) {
395         DIType aDIType(*I);
396         if(aDIType.getTag() == dwarf::DW_TAG_typedef && aDIType.getName().compare(typedefName)) {
397             while(aDIType.getTag() == dwarf::DW_TAG_typedef) {
398                 aDIType = PassUtil::getDITypeDerivedFrom((const DIDerivedType)aDIType);
399             }
400             if(aDIType.getName().compare("")) {
401                 return aDIType.getName();
402             }
403         }
404     }
405     return noName;
406 }
407 
408 std::string EDIType::lookupUnionMemberName(TYPECONST Type* type) {
409     std::string string;
410     std::string error;
411     if(!type->isStructTy() || type->getNumContainedTypes() != 1) {
412         return "";
413     }
414     raw_string_ostream ostream(string);
415     writeTypeSymbolic(ostream, type->getContainedType(0), EDIType::module);
416     ostream.flush();
417     Regex unionRegex("%(union|struct)\\.([^ ]+)", 0);
418     assert(unionRegex.isValid(error));
419     SmallVector<StringRef, 8> unionMatches;
420     if(unionRegex.match(string, &unionMatches)) {
421         return unionMatches[2];
422     }
423     return "";
424 }
425 
426 const EDIType* EDIType::getStructEDITypeByName(std::string &typeName) {
427     static EDIType aEDIType;
428     assert(module);
429     for (DebugInfoFinder::iterator I = DIFinder.type_begin(),
430         E = DIFinder.type_end(); I != E; ++I) {
431         const DIType aDIType(*I);
432         //skip zero-element stuct types, necessary to avoid infinite recursion during opaque type lookup
433         //xxx opaque type lookup should not be necessary but is there a bug in the frontend that leaves certain concrete types unnecessarily opaque?
434         const EDIType tmpEDIType(aDIType, NORMALIZE, DO_NOT_CHECK_OPAQUE_TYPES);
435         aEDIType = tmpEDIType;
436         if(typeName.compare(aEDIType.getName())) {
437             continue;
438         }
439         if(aEDIType.isUnionOrStructTy()) {
440             return &aEDIType;
441         }
442     }
443     return NULL;
444 }
445 
446 void EDIType::setModule(Module *M) {
447     assert(module == NULL);
448     module = M;
449     DIFinder.processModule(*module);
450 }
451 
452 //===----------------------------------------------------------------------===//
453 // Private methods
454 //===----------------------------------------------------------------------===//
455 void EDIType::init(bool norm, bool checkOpaqueTypes) {
456     EDIType_assert(isType());
457     currentDimension = 0;
458     this->checkOpaqueTypes = checkOpaqueTypes;
459     myName = "";
460     if(norm) {
461         normalize();
462     }
463     if(myNames.size() == 0) {
464         //nobody assigned names yet, do it here
465         myName = isVoidTy() ? voidName : aDIType.getName();
466         if(myName.compare("")) {
467             myNames.push_back(myName);
468         }
469     }
470 }
471 
472 void EDIType::normalize() {
473     if(getTag() == dwarf::DW_TAG_typedef) {
474         normalizeTypedef();
475     }
476     if(isBasicType() || isVoidTy() || isEnumTy() || isOpaqueTy()) {
477         return;
478     }
479     if(isDerivedType()) {
480         if(isPointerTy() || isUnionOrStructTy()) {
481            return;
482         }
483         aDIType = PassUtil::getDITypeDerivedFrom((const DIDerivedType)aDIType);
484         normalize();
485         return;
486     }
487     EDIType_assert(isCompositeType());
488     if(isAggregateType() || isVectorTy() || isFunctionTy()) {
489        return;
490     }
491     EDIType_assert(getNumContainedTypes() == 1);
492     aDIType = *(getContainedType(0, DO_NOT_NORMALIZE).getDIType());
493     normalize();
494 }
495 
496 void EDIType::normalizeTypedef() {
497     myNames.clear();
498     while(aDIType.getTag() == dwarf::DW_TAG_typedef) {
499         if(aDIType.getName().compare("")) {
500             myNames.push_back(aDIType.getName());
501         }
502         aDIType = PassUtil::getDITypeDerivedFrom((const DIDerivedType)aDIType);
503     }
504     myName = isVoidTy() ? voidName : aDIType.getName();
505     if(!myName.compare("")) {
506         //anonymous typedefed type, use the deepest typedef name
507         assert(!isBasicType());
508         assert(myNames.size() > 0);
509         myName = myNames[myNames.size()-1];
510     }
511     else {
512         myNames.push_back(myName);
513     }
514 }
515 
516 StringRef EDIType::voidName("void");
517 Module *EDIType::module = NULL;
518 DebugInfoFinder EDIType::DIFinder;
519 
520 }
521