1 /** 2 Contains definitions of the syntax tree elements. 3 4 Copyright: © 2012-2015 RejectedSoftware e.K. 5 License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file. 6 Authors: Sönke Ludwig 7 */ 8 module ddox.entities; 9 10 import ddox.ddoc; 11 import std.algorithm : countUntil, joiner, map; 12 import std.range; 13 import std.string; 14 import std.typecons; 15 16 17 class Entity { 18 Entity parent; 19 CachedString name; 20 DocGroup docGroup; 21 22 this(Entity parent, string name) 23 { 24 this.parent = parent; 25 this.name = name; 26 } 27 28 @property auto qualifiedName() const { return qualifiedPath().map!(e => e.name[]).joiner("."); } 29 30 auto qualifiedPath() 31 const { 32 static struct R { 33 private { 34 Rebindable!(const(Entity)) m_current; 35 Rebindable!(const(Entity)) m_back; 36 size_t m_length; 37 } 38 39 @property const(Entity) front() { return m_current; } 40 @property bool empty() const { return m_current is null; } 41 @property size_t length() const { return m_length; } 42 void popFront() 43 { 44 if (m_back is m_current) { 45 m_current = null; 46 } else { 47 Rebindable!(const(Entity)) e = m_back; 48 while (e.parent !is m_current) 49 e = e.parent; 50 m_current = e; 51 m_length--; 52 } 53 } 54 } 55 56 R ret; 57 ret.m_current = this; 58 ret.m_length = 1; 59 while (ret.m_current.parent && ret.m_current.parent.parent) { 60 ret.m_current = ret.m_current.parent; 61 ret.m_length++; 62 } 63 ret.m_back = this; 64 return ret; 65 } 66 67 @property string moduleName() 68 const { 69 import std.conv : text; 70 auto m = this.module_(); 71 return m ? text(m.qualifiedName) : null; 72 } 73 74 @property const(Module) module_() 75 const { 76 Rebindable!(const(Entity)) e = this; 77 while (e && !cast(const(Module))e) e = e.parent; 78 return cast(const(Module))e; 79 } 80 @property Module module_() 81 { 82 Entity e = this; 83 while (e && !cast(Module)e) e = e.parent; 84 return cast(Module)e; 85 } 86 87 @property string nestedName() 88 const { 89 string s = name; 90 Rebindable!(const(Entity)) e = parent; 91 while( e && e.parent ){ 92 if (cast(const(Module))e) break; 93 s = e.name ~ "." ~ s; 94 e = e.parent; 95 } 96 return s; 97 } 98 99 @property string kindCaption() const { return "Entity"; } 100 101 bool isAncestorOf(in Entity node) 102 const { 103 auto n = rebindable(node); 104 while( n ){ 105 if( n.parent is this ) return true; 106 n = n.parent; 107 } 108 return false; 109 } 110 111 abstract void iterateChildren(scope bool delegate(Entity) del); 112 113 final inout(T) findChild(T = Entity)(string name) 114 inout { 115 T ret; 116 (cast(Entity)this).iterateChildren((ch) { 117 if (ch.name == name) { 118 ret = cast(T)ch; 119 return ret is null; 120 } 121 return true; 122 }); 123 return cast(inout)ret; 124 } 125 126 final inout(T)[] findChildren(T = Entity)(string name) 127 inout { 128 inout(T)[] ret; 129 (cast(Entity)this).iterateChildren((ch) { 130 if (ch.name == name) { 131 auto t = cast(T)ch; 132 if (t) ret ~= cast(inout)t; 133 } 134 return true; 135 }); 136 return ret; 137 } 138 139 final inout(T) lookup(T = Entity)(string qualified_name, bool recurse = true) 140 inout { 141 assert(qualified_name.length > 0, "Looking up empty name."); 142 auto parts = split(qualified_name, "."); 143 Entity e = cast(Entity)this; 144 foreach (i, p; parts) { 145 if (i+1 < parts.length) { 146 e = e.findChild(p); 147 if (!e) break; 148 } else { 149 auto r = e.findChild!T(p); 150 if (r) return cast(inout)r; 151 } 152 } 153 static if (is(T == Declaration)) { 154 if (auto decl = cast(inout(Declaration))this) { 155 auto idx = decl.templateArgs.countUntil!(p => p.name.stripEllipsis() == qualified_name); 156 if (idx >= 0) return cast(inout)decl.templateArgs[idx]; 157 } 158 } 159 if (recurse && parent) return cast(inout)parent.lookup!T(qualified_name); 160 return null; 161 } 162 163 final inout(T)[] lookupAll(T = Entity)(string qualified_name) 164 inout { 165 assert(qualified_name.length > 0, "Looking up empty name."); 166 auto parts = split(qualified_name, "."); 167 Entity e = cast(Entity)this; 168 foreach (i, p; parts) { 169 if( i+1 < parts.length ) e = e.findChild(p); 170 else return cast(inout)e.findChildren!T(p); 171 if( !e ) return null; 172 } 173 return null; 174 } 175 176 final inout(Entity) lookdown(string qualified_name, bool stop_at_module_level = false) 177 inout { 178 auto parts = split(qualified_name, "."); 179 Entity e = cast(Entity)this; 180 foreach (p; parts) { 181 e = e.findChild(p); 182 if (!e) { 183 if( stop_at_module_level && cast(Module)this ) return null; 184 Entity ret; 185 (cast(Entity)this).iterateChildren((ch){ 186 if (auto res = (cast()ch).lookdown(qualified_name)) { 187 ret = res; 188 return false; 189 } 190 return true; 191 }); 192 return cast(inout)ret; 193 } 194 } 195 return cast(inout)e; 196 } 197 198 void visit(T)(scope void delegate(T) del) 199 { 200 if (auto t = cast(T)this) del(t); 201 iterateChildren((ch) { 202 ch.visit!T(del); 203 return true; 204 }); 205 } 206 207 void visit(T)(scope void delegate(T) del) 208 const { 209 Entity uthis = cast(Entity)this; 210 if (auto t = cast(Unqual!T)uthis) del(t); 211 uthis.iterateChildren((ch) { 212 (cast(const)ch).visit!T(del); 213 return true; 214 }); 215 } 216 } 217 218 final class DocGroup { 219 Entity[] members; 220 CachedString text; 221 DdocComment comment; 222 223 this(Entity entity, string text) 224 { 225 this.members = [entity]; 226 this.text = text; 227 this.comment = new DdocComment(text); 228 } 229 230 this(Entity entity, string text, DdocComment comment) 231 { 232 this.members = [entity]; 233 this.text = text; 234 this.comment = comment; 235 } 236 } 237 238 final class Package : Entity { 239 Package[] packages; 240 Module[] modules; 241 242 this(Entity parent, string name){ super(parent, name); } 243 244 override @property string kindCaption() const { return "Package"; } 245 246 Module createModule(string name) 247 { 248 assert(findChild!Module(name) is null, "Module already present"); 249 auto mod = new Module(this, name); 250 modules ~= mod; 251 return mod; 252 } 253 254 Package getOrAddPackage(string name) 255 { 256 foreach( p; packages ) 257 if( p.name == name ) 258 return p; 259 auto pack = new Package(this, name); 260 pack.docGroup = new DocGroup(pack, null); 261 packages ~= pack; 262 return pack; 263 } 264 265 override void iterateChildren(scope bool delegate(Entity) del) 266 { 267 foreach( p; packages ) if( !del(p) ) return; 268 foreach( m; modules ) if( !del(m) ) return; 269 } 270 } 271 272 final class Module : Entity{ 273 Declaration[] members; 274 CachedString file; 275 276 this(Entity parent, string name){ super(parent, name); } 277 278 override @property string kindCaption() const { return "Module"; } 279 280 /// Determines if this module is a "package.d" module. 281 @property bool isPackageModule() { return parent && parent.findChild!Package(this.name); } 282 283 override void iterateChildren(scope bool delegate(Entity) del) 284 { 285 foreach( m; members ) if( !del(m) ) return; 286 } 287 } 288 289 enum DeclarationKind { 290 Variable, 291 Function, 292 Struct, 293 Union, 294 Class, 295 Interface, 296 Enum, 297 EnumMember, 298 Alias, 299 Template, 300 TemplateParameter 301 } 302 303 enum Protection { 304 Private, 305 Package, 306 Protected, 307 Public 308 } 309 310 class Declaration : Entity { 311 Declaration inheritingDecl; 312 Protection protection = Protection.Public; 313 immutable(CachedString)[] attributes; 314 int line; 315 bool isTemplate; 316 TemplateParameterDeclaration[] templateArgs; 317 CachedString templateConstraint; 318 319 override @property string kindCaption() const { return "Declaration"; } 320 abstract @property Declaration dup(); 321 abstract @property DeclarationKind kind() const; 322 @property inout(Declaration) parentDeclaration() inout { return cast(inout(Declaration))parent; } 323 override @property Module module_() { 324 Entity e = parent; 325 while(e){ 326 if( auto m = cast(Module)e ) return m; 327 e = e.parent; 328 } 329 assert(false, "Declaration without module?"); 330 } 331 override @property const(Module) module_() const { 332 Rebindable!(const(Entity)) e = parent; 333 while(e){ 334 if( auto m = cast(const(Module))e ) return m; 335 e = e.parent; 336 } 337 assert(false, "Declaration without module?"); 338 } 339 340 this(Entity parent, string name){ super(parent, name); } 341 342 abstract override void iterateChildren(scope bool delegate(Entity) del); 343 344 protected void copyFrom(Declaration src) 345 { 346 this.docGroup = src.docGroup; 347 this.inheritingDecl = src.inheritingDecl; 348 this.protection = src.protection; 349 this.attributes = src.attributes; 350 this.line = src.line; 351 this.templateArgs = src.templateArgs; 352 this.templateConstraint = src.templateConstraint; 353 } 354 } 355 356 class TypedDeclaration : Declaration { 357 CachedType type; 358 359 this(Entity parent, string name){ super(parent, name); } 360 361 override @property string kindCaption() const { return "Typed declaration"; } 362 363 abstract override @property DeclarationKind kind() const; 364 365 abstract override void iterateChildren(scope bool delegate(Entity) del); 366 367 protected override void copyFrom(Declaration src) 368 { 369 super.copyFrom(src); 370 if (auto tsrc = cast(TypedDeclaration)src) 371 this.type = tsrc.type; 372 } 373 } 374 375 final class VariableDeclaration : TypedDeclaration { 376 Value initializer; 377 378 override @property string kindCaption() const { return "Variable"; } 379 override @property VariableDeclaration dup() { auto ret = new VariableDeclaration(parent, name); ret.copyFrom(this); ret.initializer = initializer; return ret; } 380 override @property DeclarationKind kind() const { return DeclarationKind.Variable; } 381 382 this(Entity parent, string name){ super(parent, name); } 383 384 override void iterateChildren(scope bool delegate(Entity) del) {} 385 } 386 387 final class FunctionDeclaration : TypedDeclaration { 388 CachedType returnType; 389 VariableDeclaration[] parameters; 390 391 override @property string kindCaption() const { return "Function"; } 392 override @property FunctionDeclaration dup() { auto ret = new FunctionDeclaration(parent, name); ret.copyFrom(this); ret.returnType = returnType; ret.parameters = parameters.dup; ret.attributes = attributes; return ret; } 393 override @property DeclarationKind kind() const { return DeclarationKind.Function; } 394 395 this(Entity parent, string name){ super(parent, name); } 396 397 bool hasAttribute(string att) const { foreach( a; attributes ) if( a == att ) return true; return false; } 398 399 override void iterateChildren(scope bool delegate(Entity) del) 400 { 401 foreach( p; parameters ) del(p); 402 } 403 } 404 405 class CompositeTypeDeclaration : Declaration { 406 Declaration[] members; 407 408 override @property string kindCaption() const { return "Composite type"; } 409 override abstract @property DeclarationKind kind() const; 410 411 this(Entity parent, string name){ super(parent, name); } 412 413 override void iterateChildren(scope bool delegate(Entity) del) 414 { 415 foreach( m; members ) if( !del(m) ) return; 416 } 417 } 418 419 final class StructDeclaration : CompositeTypeDeclaration { 420 override @property string kindCaption() const { return "Struct"; } 421 override @property StructDeclaration dup() { auto ret = new StructDeclaration(parent, name); ret.copyFrom(this); ret.members = members; return ret; } 422 override @property DeclarationKind kind() const { return DeclarationKind.Struct; } 423 424 this(Entity parent, string name){ super(parent, name); } 425 } 426 427 final class UnionDeclaration : CompositeTypeDeclaration { 428 override @property string kindCaption() const { return "Union"; } 429 override @property UnionDeclaration dup() { auto ret = new UnionDeclaration(parent, name); ret.copyFrom(this); ret.members = members; return ret; } 430 override @property DeclarationKind kind() const { return DeclarationKind.Union; } 431 432 this(Entity parent, string name){ super(parent, name); } 433 } 434 435 final class InterfaceDeclaration : CompositeTypeDeclaration { 436 CachedType[] derivedInterfaces; 437 438 override @property string kindCaption() const { return "Interface"; } 439 override @property InterfaceDeclaration dup() { auto ret = new InterfaceDeclaration(parent, name); ret.copyFrom(this); ret.members = members; ret.derivedInterfaces = derivedInterfaces.dup; return ret; } 440 override @property DeclarationKind kind() const { return DeclarationKind.Interface; } 441 442 this(Entity parent, string name){ super(parent, name); } 443 } 444 445 final class ClassDeclaration : CompositeTypeDeclaration { 446 CachedType baseClass; 447 CachedType[] derivedInterfaces; 448 449 override @property string kindCaption() const { return "Class"; } 450 override @property ClassDeclaration dup() { auto ret = new ClassDeclaration(parent, name); ret.copyFrom(this); ret.members = members; ret.baseClass = baseClass; ret.derivedInterfaces = derivedInterfaces.dup; return ret; } 451 override @property DeclarationKind kind() const { return DeclarationKind.Class; } 452 453 this(Entity parent, string name){ super(parent, name); } 454 } 455 456 final class EnumDeclaration : CompositeTypeDeclaration { 457 CachedType baseType; 458 459 override @property string kindCaption() const { return "Enum"; } 460 override @property EnumDeclaration dup() { auto ret = new EnumDeclaration(parent, name); ret.copyFrom(this); ret.members = members; ret.baseType = baseType; return ret; } 461 override @property DeclarationKind kind() const { return DeclarationKind.Enum; } 462 463 this(Entity parent, string name){ super(parent, name); } 464 } 465 466 final class EnumMemberDeclaration : Declaration { 467 Value value; 468 469 override @property string kindCaption() const { return "Enum member"; } 470 override @property EnumMemberDeclaration dup() { auto ret = new EnumMemberDeclaration(parent, name); ret.copyFrom(this); ret.value = value; return ret; } 471 override @property DeclarationKind kind() const { return DeclarationKind.EnumMember; } 472 @property CachedType type() { if (!value) return CachedType.init; return value.type; } 473 474 this(Entity parent, string name){ super(parent, name); } 475 476 override void iterateChildren(scope bool delegate(Entity) del) {} 477 } 478 479 final class AliasDeclaration : Declaration { 480 Declaration targetDecl; 481 CachedType targetType; 482 CachedString targetString; 483 484 override @property string kindCaption() const { return "Alias"; } 485 override @property AliasDeclaration dup() { auto ret = new AliasDeclaration(parent, name); ret.copyFrom(this); ret.targetDecl = targetDecl; ret.targetType = targetType; return ret; } 486 override @property DeclarationKind kind() const { return DeclarationKind.Alias; } 487 @property CachedType type() { return targetType; } 488 489 this(Entity parent, string name){ super(parent, name); } 490 491 override void iterateChildren(scope bool delegate(Entity) del) {} 492 } 493 494 final class TemplateDeclaration : Declaration { 495 Declaration[] members; 496 497 override @property string kindCaption() const { return "Template"; } 498 override @property TemplateDeclaration dup() { auto ret = new TemplateDeclaration(parent, name); ret.copyFrom(this); ret.members = members.dup; return ret; } 499 override @property DeclarationKind kind() const { return DeclarationKind.Template; } 500 501 this(Entity parent, string name){ super(parent, name); isTemplate = true; } 502 503 override void iterateChildren(scope bool delegate(Entity) del) 504 { 505 foreach( m; members ) del(m); 506 } 507 } 508 509 final class TemplateParameterDeclaration : TypedDeclaration { 510 string defaultValue; 511 512 override @property string kindCaption() const { return "Template parameter"; } 513 override @property TemplateParameterDeclaration dup() { auto ret = new TemplateParameterDeclaration(parent, name); ret.copyFrom(this); ret.type = type; return ret; } 514 override @property DeclarationKind kind() const { return DeclarationKind.TemplateParameter; } 515 516 this(Entity parent, string name){ super(parent, name); } 517 518 override void iterateChildren(scope bool delegate(Entity) del) {} 519 } 520 521 final class Value { 522 CachedType type; 523 CachedString valueString; 524 525 this() {} 526 this(CachedType type, string value_string) { this.type = type; this.valueString = value_string; } 527 } 528 529 enum TypeKind { 530 Primitive, 531 Pointer, 532 Array, 533 StaticArray, 534 AssociativeArray, 535 Function, 536 Delegate 537 } 538 539 struct CachedType { 540 private { 541 uint m_id = uint.max; 542 543 static uint[const(Type)] s_typeIDs; 544 static const(Type)[] s_types; 545 static const(Type) s_emptyType; 546 } 547 548 static CachedType fromTypeDecl(Declaration decl) 549 { 550 import std.conv : to; 551 Type tp; 552 tp.kind = TypeKind.Primitive; 553 tp.typeName = decl.qualifiedName.to!string; 554 tp.typeDecl = decl; 555 tp.text = decl.name; 556 auto ct = CachedType(tp); 557 auto existing = ct.typeDecl; 558 //assert(!existing || existing is decl, "Replacing type decl "~existing.qualifiedName.to!string~" with "~decl.qualifiedName.to!string); 559 return ct; 560 } 561 562 this(in ref Type tp) 563 { 564 this.type = tp; 565 } 566 567 this(Type tp) 568 { 569 this.type = tp; 570 } 571 572 bool opCast() const { return m_id != uint.max; } 573 574 @property ref const(Type) type() const { return m_id == uint.max ? s_emptyType : s_types[m_id]; } 575 @property ref const(Type) type(const(Type) tp) 576 { 577 if (auto pi = tp in s_typeIDs) { 578 m_id = *pi; 579 } else { 580 if (!s_types.length) s_types.reserve(16384); 581 582 m_id = cast(uint)s_types.length; 583 s_types ~= tp; 584 s_typeIDs[tp] = m_id; 585 } 586 return this.type; 587 } 588 589 alias type this; 590 } 591 592 struct Type { 593 import std.typecons : Rebindable; 594 595 TypeKind kind; 596 597 immutable(CachedString)[] attributes; 598 immutable(CachedString)[] modifiers; 599 CachedString templateArgs; 600 CachedString text; // original text as in DMDs JSON output 601 // Primitive 602 CachedString typeName; 603 Rebindable!(const(Declaration)) typeDecl; 604 // P, A, SA, AA 605 CachedType elementType; 606 // SA 607 CachedString arrayLength; 608 // AA 609 CachedType keyType; 610 // Function/Delegate 611 CachedType returnType; 612 immutable(CachedType)[] parameterTypes; 613 immutable(CachedString)[] _parameterNames; 614 immutable(Value)[] _parameterDefaultValues; 615 public import std.traits : Variadic; 616 Variadic variadic; 617 618 static Type makePointer(CachedType base_type) { Type ret; ret.kind = TypeKind.Pointer; ret.elementType = base_type; return ret; } 619 static Type makeArray(CachedType base_type) { Type ret; ret.kind = TypeKind.Array; ret.elementType = base_type; return ret; } 620 static Type makeStaticArray(CachedType base_type, string length) { Type ret; ret.kind = TypeKind.StaticArray; ret.elementType = base_type; ret.arrayLength = length; return ret; } 621 static Type makeAssociativeArray(CachedType value_type, CachedType key_type) { Type ret; ret.kind = TypeKind.AssociativeArray; ret.keyType = key_type; ret.elementType = value_type; return ret; } 622 static Type makeFunction(CachedType return_type, immutable(CachedType)[] parameter_types) { Type ret; ret.kind = TypeKind.Function; ret.returnType = return_type; ret.parameterTypes = parameter_types; return ret; } 623 static Type makeDelegate(CachedType return_type, immutable(CachedType)[] parameter_types) { Type ret; ret.kind = TypeKind.Delegate; ret.returnType = return_type; ret.parameterTypes = parameter_types; return ret; } 624 625 equals_t opEquals(in Type other) 626 const { 627 if( kind != other.kind ) return false; 628 if( attributes != other.attributes ) return false; // TODO use set comparison instead 629 if( modifiers != other.modifiers ) return false; // TODO: use set comparison instead 630 631 final switch( kind ){ 632 case TypeKind.Primitive: return typeName == other.typeName; 633 case TypeKind.Pointer: 634 case TypeKind.Array: return elementType == other.elementType; 635 case TypeKind.StaticArray: return elementType == other.elementType && arrayLength == other.arrayLength; 636 case TypeKind.AssociativeArray: return elementType == other.elementType && keyType == other.keyType; 637 case TypeKind.Function: 638 case TypeKind.Delegate: 639 if( returnType != other.returnType ) return false; 640 if( parameterTypes.length != other.parameterTypes.length ) return false; 641 foreach( i, p; parameterTypes ) 642 if( p != other.parameterTypes[i] ) 643 return false; 644 } 645 return true; 646 } 647 } 648 649 struct CachedString { 650 private { 651 uint m_id = uint.max; 652 static uint[string] s_stringIDs; 653 static string[] s_strings; 654 } 655 656 this(string str) { this.str = str; } 657 658 string toString() const { return this.str; } 659 660 @property size_t length() const { return this.str.length; } 661 662 string opSlice(size_t lo, size_t hi) const { return this.str[lo .. hi]; } 663 string opSlice() const { return this.str; } 664 size_t opDollar() const { return this.length; } 665 666 string opOpAssign(string op : "~")(string val) { return this.str = this.str ~ val; } 667 668 @property string str() const { return m_id == uint.max ? "" : s_strings[m_id]; } 669 @property string str(string value) { 670 if (auto pi = value in s_stringIDs) { 671 m_id = *pi; 672 } else { 673 if (!s_strings.length) { 674 s_strings.length = 16384; 675 s_strings.length = 0; 676 s_strings.assumeSafeAppend(); 677 } 678 679 // TODO: use a big pool of memory instead of individual allocations 680 auto su = value.idup; 681 auto id = cast(uint)s_strings.length; 682 s_strings ~= su; 683 s_stringIDs[su] = id; 684 m_id = id; 685 } 686 return this.str; 687 } 688 689 alias str this; 690 } 691 692 private string stripEllipsis(string arg) 693 { 694 return arg.endsWith("...") ? arg[0 .. $-3] : arg; 695 }