source: src/SymTab/Demangle.cc@ 04c77791

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr no_list persistent-indexer pthread-emulation qualifiedEnum stuck-waitfor-destruct
Last change on this file since 04c77791 was 04c77791, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

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