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 }