source: src/SymTab/Demangle.cc@ 03f944f

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 03f944f was 8abca06, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

rewrite isPrefix using memcmp to increase performance, same change in Demangle but untested
  • Property mode set to 100644
File size: 20.1 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// Demangler.cc --
8//
9// Author : Rob Schluntz
10// Created On : Thu Jul 19 12:52:41 2018
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Tue Feb 11 15:09:18 2020
13// Update Count : 10
14//
15
16#include <algorithm>
17#include <sstream>
18
19#include "CodeGen/GenType.h"
20#include "Common/PassVisitor.h"
21#include "Common/utility.h" // isPrefix
22#include "Mangler.h"
23#include "SynTree/Type.h"
24#include "SynTree/Declaration.h"
25
26#define DEBUG
27#ifdef DEBUG
28#define PRINT(x) x
29#else
30#define PRINT(x) {}
31#endif
32
33namespace {
34 struct GenType : public WithVisitorRef<GenType>, public WithShortCircuiting {
35 std::string typeString;
36 GenType( const std::string &typeString );
37
38 void previsit( BaseSyntaxNode * );
39 void postvisit( BaseSyntaxNode * );
40
41 void postvisit( FunctionType * funcType );
42 void postvisit( VoidType * voidType );
43 void postvisit( BasicType * basicType );
44 void postvisit( PointerType * pointerType );
45 void postvisit( ArrayType * arrayType );
46 void postvisit( ReferenceType * refType );
47 void postvisit( StructInstType * structInst );
48 void postvisit( UnionInstType * unionInst );
49 void postvisit( EnumInstType * enumInst );
50 void postvisit( TypeInstType * typeInst );
51 void postvisit( TupleType * tupleType );
52 void postvisit( VarArgsType * varArgsType );
53 void postvisit( ZeroType * zeroType );
54 void postvisit( OneType * oneType );
55 void postvisit( GlobalScopeType * globalType );
56 void postvisit( QualifiedType * qualType );
57
58 private:
59 void handleQualifiers( Type *type );
60 std::string handleGeneric( ReferenceToType * refType );
61 void genArray( const Type::Qualifiers &qualifiers, Type *base, Expression *dimension, bool isVarLen, bool isStatic );
62 };
63
64 std::string genDemangleType( Type * type, const std::string & baseString ) {
65 PassVisitor<GenType> gt( baseString );
66 assert( type );
67 type->accept( gt );
68 return gt.pass.typeString;
69 }
70
71 GenType::GenType( const std::string &typeString ) : typeString( typeString ) {}
72
73 // *** BaseSyntaxNode
74 void GenType::previsit( BaseSyntaxNode * ) {
75 // turn off automatic recursion for all nodes, to allow each visitor to
76 // precisely control the order in which its children are visited.
77 visit_children = false;
78 }
79
80 void GenType::postvisit( BaseSyntaxNode * node ) {
81 std::stringstream ss;
82 node->print( ss );
83 assertf( false, "Unhandled node reached in GenType: %s", ss.str().c_str() );
84 }
85
86 void GenType::postvisit( VoidType * voidType ) {
87 typeString = "void " + typeString;
88 handleQualifiers( voidType );
89 }
90
91 void GenType::postvisit( BasicType * basicType ) {
92 BasicType::Kind kind = basicType->kind;
93 assert( 0 <= kind && kind < BasicType::NUMBER_OF_BASIC_TYPES );
94 typeString = std::string( BasicType::typeNames[kind] ) + " " + typeString;
95 handleQualifiers( basicType );
96 }
97
98 void GenType::genArray( const Type::Qualifiers & qualifiers, Type * base, Expression *dimension, bool isVarLen, bool ) {
99 std::ostringstream os;
100 if ( typeString != "" ) {
101 if ( typeString[ 0 ] == '*' ) {
102 os << "(" << typeString << ")";
103 } else {
104 os << typeString;
105 } // if
106 } // if
107 os << "[";
108
109 if ( qualifiers.is_const ) {
110 os << "const ";
111 } // if
112 if ( qualifiers.is_volatile ) {
113 os << "volatile ";
114 } // if
115 if ( qualifiers.is_restrict ) {
116 os << "__restrict ";
117 } // if
118 if ( qualifiers.is_atomic ) {
119 os << "_Atomic ";
120 } // if
121 if ( dimension != 0 ) {
122 // TODO: ???
123 // PassVisitor<CodeGenerator> cg( os, pretty, genC, lineMarks );
124 // dimension->accept( cg );
125 } else if ( isVarLen ) {
126 // no dimension expression on a VLA means it came in with the * token
127 os << "*";
128 } // if
129 os << "]";
130
131 typeString = os.str();
132
133 base->accept( *visitor );
134 }
135
136 void GenType::postvisit( PointerType * pointerType ) {
137 assert( pointerType->base != 0);
138 if ( pointerType->get_isStatic() || pointerType->get_isVarLen() || pointerType->dimension ) {
139 assert(false);
140 genArray( pointerType->get_qualifiers(), pointerType->base, pointerType->dimension, pointerType->get_isVarLen(), pointerType->get_isStatic() );
141 } else {
142 handleQualifiers( pointerType );
143 if ( typeString[ 0 ] == '?' ) {
144 typeString = "* " + typeString;
145 } else {
146 typeString = "*" + typeString;
147 } // if
148 pointerType->base->accept( *visitor );
149 } // if
150 }
151
152 void GenType::postvisit( ArrayType * arrayType ) {
153 genArray( arrayType->get_qualifiers(), arrayType->base, arrayType->dimension, arrayType->get_isVarLen(), arrayType->get_isStatic() );
154 }
155
156 void GenType::postvisit( ReferenceType * refType ) {
157 assert( false );
158 assert( refType->base != 0);
159 handleQualifiers( refType );
160 typeString = "&" + typeString;
161 refType->base->accept( *visitor );
162 }
163
164 void GenType::postvisit( FunctionType * funcType ) {
165 std::ostringstream os;
166
167 if ( typeString != "" ) {
168 if ( typeString[0] == '*' ) {
169 os << "(" << typeString << ")";
170 } else {
171 os << typeString;
172 } // if
173 } // if
174
175 /************* parameters ***************/
176 const std::list<DeclarationWithType *> &pars = funcType->parameters;
177
178 if ( pars.empty() ) {
179 if ( funcType->get_isVarArgs() ) {
180 os << "()";
181 } else {
182 os << "(void)";
183 } // if
184 } else {
185 os << "(" ;
186
187 unsigned int i = 0;
188 for (DeclarationWithType * p : pars) {
189 os << genDemangleType( p->get_type(), "" );
190 if (++i != pars.size()) os << ", ";
191 }
192
193 if ( funcType->get_isVarArgs() ) {
194 os << ", ...";
195 } // if
196 os << ")";
197 } // if
198
199 typeString = os.str();
200
201 if ( funcType->returnVals.size() == 0 ) {
202 typeString += ": void";
203 } else {
204 typeString += ": " + genDemangleType(funcType->returnVals.front()->get_type(), "");
205 } // if
206
207 // add forall
208 if( ! funcType->forall.empty() ) {
209 std::ostringstream os;
210 os << "forall(";
211 unsigned int i = 0;
212 for ( auto td : funcType->forall ) {
213 os << td->typeString() << " " << td->name;
214 if (! td->assertions.empty()) {
215 os << " | { ";
216 unsigned int j = 0;
217 for (DeclarationWithType * assert : td->assertions) {
218 os << genDemangleType(assert->get_type(), assert->name);
219 if (++j != td->assertions.size()) os << ", ";
220 }
221 os << "}";
222 }
223 if (++i != funcType->forall.size()) os << ", ";
224 }
225 os << ")";
226 typeString = typeString + " -> " + os.str();
227 }
228 }
229
230 std::string GenType::handleGeneric( ReferenceToType * refType ) {
231 if ( ! refType->parameters.empty() ) {
232 std::ostringstream os;
233 // TODO: ???
234 // PassVisitor<CodeGenerator> cg( os, pretty, genC, lineMarks );
235 os << "(";
236 // cg.pass.genCommaList( refType->parameters.begin(), refType->parameters.end() );
237 os << ") ";
238 return os.str();
239 }
240 return "";
241 }
242
243 void GenType::postvisit( StructInstType * structInst ) {
244 typeString = "struct " + structInst->name + handleGeneric( structInst ) + " " + typeString;
245 handleQualifiers( structInst );
246 }
247
248 void GenType::postvisit( UnionInstType * unionInst ) {
249 typeString = "union " + unionInst->name + handleGeneric( unionInst ) + " " + typeString;
250 handleQualifiers( unionInst );
251 }
252
253 void GenType::postvisit( EnumInstType * enumInst ) {
254 typeString = "enum " + enumInst->name + " " + typeString;
255 handleQualifiers( enumInst );
256 }
257
258 void GenType::postvisit( TypeInstType * typeInst ) {
259 typeString = typeInst->name + " " + typeString;
260 handleQualifiers( typeInst );
261 }
262
263 void GenType::postvisit( TupleType * tupleType ) {
264 unsigned int i = 0;
265 std::ostringstream os;
266 os << "[";
267 for ( Type * t : *tupleType ) {
268 i++;
269 os << genDemangleType( t, "" ) << (i == tupleType->size() ? "" : ", ");
270 }
271 os << "] ";
272 typeString = os.str() + typeString;
273 }
274
275 void GenType::postvisit( VarArgsType * varArgsType ) {
276 typeString = "__builtin_va_list " + typeString;
277 handleQualifiers( varArgsType );
278 }
279
280 void GenType::postvisit( ZeroType * zeroType ) {
281 // ideally these wouldn't hit codegen at all, but should be safe to make them ints
282 typeString = "zero_t " + typeString;
283 handleQualifiers( zeroType );
284 }
285
286 void GenType::postvisit( OneType * oneType ) {
287 // ideally these wouldn't hit codegen at all, but should be safe to make them ints
288 typeString = "one_t " + typeString;
289 handleQualifiers( oneType );
290 }
291
292 void GenType::postvisit( GlobalScopeType * globalType ) {
293 handleQualifiers( globalType );
294 }
295
296 void GenType::postvisit( QualifiedType * qualType ) {
297 std::ostringstream os;
298 os << genDemangleType( qualType->parent, "" ) << "." << genDemangleType( qualType->child, "" ) << typeString;
299 typeString = os.str();
300 handleQualifiers( qualType );
301 }
302
303 void GenType::handleQualifiers( Type * type ) {
304 if ( type->get_const() ) {
305 typeString = "const " + typeString;
306 } // if
307 if ( type->get_volatile() ) {
308 typeString = "volatile " + typeString;
309 } // if
310 if ( type->get_restrict() ) {
311 typeString = "__restrict " + typeString;
312 } // if
313 if ( type->get_atomic() ) {
314 typeString = "_Atomic " + typeString;
315 } // if
316 }
317}
318
319
320namespace SymTab {
321 namespace Mangler {
322 namespace {
323 struct StringView {
324 private:
325 std::string str;
326 size_t idx = 0;
327 // typedef Type * (StringView::*parser)(Type::Qualifiers);
328 typedef std::function<Type * (Type::Qualifiers)> parser;
329 std::vector<std::pair<std::string, parser>> parsers;
330 public:
331 StringView(const std::string & str);
332
333 bool done() const { return idx >= str.size(); }
334 char cur() const { assert(! done()); return str[idx]; }
335
336 bool expect(char ch) { return str[idx++] == ch; }
337 void next(size_t inc = 1) { idx += inc; }
338
339 /// determines if `pref` is a prefix of `str`
340 bool isPrefix(const std::string & pref);
341 bool extractNumber(size_t & out);
342 bool extractName(std::string & out);
343 bool stripMangleName(std::string & name);
344
345 Type * parseFunction(Type::Qualifiers tq);
346 Type * parseTuple(Type::Qualifiers tq);
347 Type * parseVoid(Type::Qualifiers tq);
348 Type * parsePointer(Type::Qualifiers tq);
349 Type * parseArray(Type::Qualifiers tq);
350 Type * parseStruct(Type::Qualifiers tq);
351 Type * parseUnion(Type::Qualifiers tq);
352 Type * parseEnum(Type::Qualifiers tq);
353 Type * parseType(Type::Qualifiers tq);
354
355 Type * parseType();
356 bool parse(std::string & name, Type *& type);
357 };
358
359 StringView::StringView(const std::string & str) : str(str) {
360 // basic types
361 for (size_t k = 0; k < BasicType::NUMBER_OF_BASIC_TYPES; ++k) {
362 parsers.emplace_back(Encoding::basicTypes[k], [k](Type::Qualifiers tq) {
363 PRINT( std::cerr << "basic type: " << k << std::endl; )
364 return new BasicType(tq, (BasicType::Kind)k);
365 });
366 }
367 // type variable types
368 for (size_t k = 0; k < TypeDecl::NUMBER_OF_KINDS; ++k) {
369 static const std::string typeVariableNames[] = { "DT", "OT", "FT", "TT", };
370 static_assert(
371 sizeof(typeVariableNames)/sizeof(typeVariableNames[0]) == TypeDecl::NUMBER_OF_KINDS,
372 "Each type variable kind should have a demangle name prefix"
373 );
374 parsers.emplace_back(Encoding::typeVariables[k], [k, this](Type::Qualifiers tq) -> TypeInstType * {
375 PRINT( std::cerr << "type variable type: " << k << std::endl; )
376 size_t N;
377 if (! extractNumber(N)) return nullptr;
378 return new TypeInstType(tq, toString(typeVariableNames[k], N), (TypeDecl::Kind)k != TypeDecl::Ftype);
379 });
380 }
381 // everything else
382 parsers.emplace_back(Encoding::void_t, [this](Type::Qualifiers tq) { return parseVoid(tq); });
383 parsers.emplace_back(Encoding::function, [this](Type::Qualifiers tq) { return parseFunction(tq); });
384 parsers.emplace_back(Encoding::pointer, [this](Type::Qualifiers tq) { return parsePointer(tq); });
385 parsers.emplace_back(Encoding::array, [this](Type::Qualifiers tq) { return parseArray(tq); });
386 parsers.emplace_back(Encoding::tuple, [this](Type::Qualifiers tq) { return parseTuple(tq); });
387 parsers.emplace_back(Encoding::struct_t, [this](Type::Qualifiers tq) { return parseStruct(tq); });
388 parsers.emplace_back(Encoding::union_t, [this](Type::Qualifiers tq) { return parseUnion(tq); });
389 parsers.emplace_back(Encoding::enum_t, [this](Type::Qualifiers tq) { return parseEnum(tq); });
390 parsers.emplace_back(Encoding::type, [this](Type::Qualifiers tq) { return parseType(tq); });
391 parsers.emplace_back(Encoding::zero, [](Type::Qualifiers tq) { return new ZeroType(tq); });
392 parsers.emplace_back(Encoding::one, [](Type::Qualifiers tq) { return new OneType(tq); });
393 }
394
395 bool StringView::extractNumber(size_t & out) {
396 std::stringstream numss;
397 if (idx >= str.size()) return false;
398 while (isdigit(str[idx])) {
399 numss << str[idx];
400 ++idx;
401 if (idx == str.size()) break;
402 }
403 if (! (numss >> out)) return false;
404 PRINT( std::cerr << "extractNumber success: " << out << std::endl; )
405 return true;
406 }
407
408 bool StringView::extractName(std::string & out) {
409 size_t len;
410 if (! extractNumber(len)) return false;
411 if (idx+len > str.size()) return false;
412 out = str.substr(idx, len);
413 idx += len;
414 PRINT( std::cerr << "extractName success: " << out << std::endl; )
415 return true;
416 }
417
418 bool StringView::isPrefix(const std::string & pref) {
419 // if ( pref.size() > str.size()-idx ) return false;
420 // auto its = std::mismatch( pref.begin(), pref.end(), std::next(str.begin(), idx) );
421 // if (its.first == pref.end()) {
422 // idx += pref.size();
423 // return true;
424 // }
425
426 // This update is untested because there are no tests for this code.
427 if ( ::isPrefix( str, pref, idx ) ) {
428 idx += pref.size();
429 return true;
430 }
431 return false;
432 }
433
434 // strips __NAME__cfa__TYPE_N, where N is [0-9]+: returns str is a match is found, returns empty string otherwise
435 bool StringView::stripMangleName(std::string & name) {
436 PRINT( std::cerr << "====== " << str.size() << " " << str << std::endl; )
437 if (str.size() < 2+Encoding::manglePrefix.size()) return false; // +2 for at least _1 suffix
438 if ( ! isPrefix(Encoding::manglePrefix) || ! isdigit(str.back() ) ) return false;
439
440 // get name
441 if (! extractName(name)) return false;
442
443 // find bounds for type
444 PRINT( std::cerr << idx << " " << str.size() << std::endl; )
445 PRINT( std::cerr << "[");
446 while (isdigit(str.back())) {
447 PRINT(std::cerr << ".");
448 str.pop_back();
449 if (str.size() <= idx) return false;
450 }
451 PRINT( std::cerr << "]" << std::endl );
452 if (str.back() != '_') return false;
453 str.pop_back();
454 PRINT( std::cerr << str.size() << " " << name << " " << str.substr(idx) << std::endl; )
455 return str.size() > idx;
456 }
457
458 Type * StringView::parseFunction(Type::Qualifiers tq) {
459 PRINT( std::cerr << "function..." << std::endl; )
460 if (done()) return nullptr;
461 FunctionType * ftype = new FunctionType( tq, false );
462 std::unique_ptr<Type> manager(ftype);
463 Type * retVal = parseType();
464 if (! retVal) return nullptr;
465 PRINT( std::cerr << "with return type: " << retVal << std::endl; )
466 ftype->returnVals.push_back(ObjectDecl::newObject("", retVal, nullptr));
467 if (done() || ! expect('_')) return nullptr;
468 while (! done()) {
469 PRINT( std::cerr << "got ch: " << cur() << std::endl; )
470 if (cur() == '_') return manager.release();
471 Type * param = parseType();
472 if (! param) return nullptr;
473 PRINT( std::cerr << "with parameter : " << param << std::endl; )
474 ftype->parameters.push_back(ObjectDecl::newObject("", param, nullptr));
475 }
476 return nullptr;
477 }
478
479 Type * StringView::parseTuple(Type::Qualifiers tq) {
480 PRINT( std::cerr << "tuple..." << std::endl; )
481 std::list< Type * > types;
482 size_t ncomponents;
483 if (! extractNumber(ncomponents)) return nullptr;
484 for (size_t i = 0; i < ncomponents; ++i) {
485 // TODO: delete all on return
486 if (done()) return nullptr;
487 PRINT( std::cerr << "got ch: " << cur() << std::endl; )
488 Type * t = parseType();
489 if (! t) return nullptr;
490 PRINT( std::cerr << "with type : " << t << std::endl; )
491 types.push_back(t);
492 }
493 return new TupleType( tq, types );
494 }
495
496 Type * StringView::parseVoid(Type::Qualifiers tq) {
497 return new VoidType( tq );
498 }
499
500 Type * StringView::parsePointer(Type::Qualifiers tq) {
501 PRINT( std::cerr << "pointer..." << std::endl; )
502 Type * t = parseType();
503 if (! t) return nullptr;
504 return new PointerType( tq, t );
505 }
506
507 Type * StringView::parseArray(Type::Qualifiers tq) {
508 PRINT( std::cerr << "array..." << std::endl; )
509 size_t length;
510 if (! extractNumber(length)) return nullptr;
511 Type * t = parseType();
512 if (! t) return nullptr;
513 return new ArrayType( tq, t, new ConstantExpr( Constant::from_ulong(length) ), false, false );
514 }
515
516 Type * StringView::parseStruct(Type::Qualifiers tq) {
517 PRINT( std::cerr << "struct..." << std::endl; )
518 std::string name;
519 if (! extractName(name)) return nullptr;
520 return new StructInstType(tq, name);
521 }
522
523 Type * StringView::parseUnion(Type::Qualifiers tq) {
524 PRINT( std::cerr << "union..." << std::endl; )
525 std::string name;
526 if (! extractName(name)) return nullptr;
527 return new UnionInstType(tq, name);
528 }
529
530 Type * StringView::parseEnum(Type::Qualifiers tq) {
531 PRINT( std::cerr << "enum..." << std::endl; )
532 std::string name;
533 if (! extractName(name)) return nullptr;
534 return new EnumInstType(tq, name);
535 }
536
537 Type * StringView::parseType(Type::Qualifiers tq) {
538 PRINT( std::cerr << "type..." << std::endl; )
539 std::string name;
540 if (! extractName(name)) return nullptr;
541 PRINT( std::cerr << "typename..." << name << std::endl; )
542 return new TypeInstType(tq, name, false);
543 }
544
545 Type * StringView::parseType() {
546 if (done()) return nullptr;
547
548 std::list<TypeDecl *> forall;
549 if (isPrefix(Encoding::forall)) {
550 PRINT( std::cerr << "polymorphic with..." << std::endl; )
551 size_t dcount, fcount, vcount, acount;
552 if (! extractNumber(dcount)) return nullptr;
553 PRINT( std::cerr << dcount << " dtypes" << std::endl; )
554 if (! expect('_')) return nullptr;
555 if (! extractNumber(fcount)) return nullptr;
556 PRINT( std::cerr << fcount << " ftypes" << std::endl; )
557 if (! expect('_')) return nullptr;
558 if (! extractNumber(vcount)) return nullptr;
559 PRINT( std::cerr << vcount << " ttypes" << std::endl; )
560 if (! expect('_')) return nullptr;
561 if (! extractNumber(acount)) return nullptr;
562 PRINT( std::cerr << acount << " assertions" << std::endl; )
563 if (! expect('_')) return nullptr;
564 for (size_t i = 0; i < acount; ++i) {
565 // TODO: need to recursively parse assertions, but for now just return nullptr so that
566 // demangler does not crash if there are assertions
567 return nullptr;
568 }
569 if (! expect('_')) return nullptr;
570 }
571
572 // qualifiers
573 Type::Qualifiers tq;
574 while (true) {
575 auto qual = std::find_if(Encoding::qualifiers.begin(), Encoding::qualifiers.end(), [this](decltype(Encoding::qualifiers)::value_type val) {
576 return isPrefix(val.second);
577 });
578 if (qual == Encoding::qualifiers.end()) break;
579 tq |= qual->first;
580 }
581
582 // find the correct type parser and use it
583 auto iter = std::find_if(parsers.begin(), parsers.end(), [this](std::pair<std::string, parser> & p) {
584 return isPrefix(p.first);
585 });
586 assertf(iter != parsers.end(), "Unhandled type letter: %c at index: %zd", cur(), idx);
587 Type * ret = iter->second(tq);
588 if (! ret) return nullptr;
589 ret->forall = std::move(forall);
590 return ret;
591 }
592
593 bool StringView::parse(std::string & name, Type *& type) {
594 if (! stripMangleName(name)) return false;
595 PRINT( std::cerr << "stripped name: " << name << std::endl; )
596 Type * t = parseType();
597 if (! t) return false;
598 type = t;
599 return true;
600 }
601
602 std::string demangle(const std::string & mangleName) {
603 SymTab::Mangler::StringView view(mangleName);
604 std::string name;
605 Type * type = nullptr;
606 if (! view.parse(name, type)) return mangleName;
607 std::unique_ptr<Type> manager(type);
608 return genDemangleType(type, name);
609 }
610 } // namespace
611 } // namespace Mangler
612} // namespace SymTab
613
614extern "C" {
615 char * cforall_demangle(const char * mangleName, int option __attribute__((unused))) {
616 const std::string & demangleName = SymTab::Mangler::demangle(mangleName);
617 return strdup(demangleName.c_str());
618 }
619}
620
621// Local Variables: //
622// tab-width: 4 //
623// mode: c++ //
624// compile-command: "make install" //
625// End: //
Note: See TracBrowser for help on using the repository browser.