1 module jcli.commandgraph.graph;
2
3 // TODO:
4 // Ways to specify children instead of the parent.
5 // Needs some changes in the graph code. Not hard.
6 //
7 // TODO:
8 // Ways to parent all commands within a module.
9 // I bet this one can be really useful.
10 // Should also be pretty easy to implement.
11 //
12 // TODO:
13 // Discover commands through a parent command, by looking at its children.
14 // Should be very useful when you decide to go top-down
15 // and have more control over the command layout.
16 // I imagine it shouldn't be that hard?
17
18 import jcli.core.udas : ParentCommand, Subcommands;
19
20 import std.traits;
21 import std.meta;
22
23 template escapedName(T)
24 {
25 import std.conv : to;
26 import std.path : baseName;
27 import std.algorithm;
28 import std.range;
29
30 // The idea here is to minimize collisions between type symbols.
31 enum location = __traits(getLocation, T);
32 enum escapedName = baseName(location[0])
33 .chain(fullyQualifiedName!T)
34 .map!(ch => canFind([cast(dchar) '.', ' ', '!', '(', ')'], ch) ? '_' : ch)
35 .chain(location[1].to!string)
36 .to!string;
37 }
38
39 struct TypeGraphNode
40 {
41 int typeIndex;
42
43 /// Shows which field of the given command type points to the parent context.
44 /// Is -1 if the related command does not have a member pointing to the parent context.
45 int fieldIndex;
46 }
47
48 /// Represents a command type graph with only one type.
49 template DegenerateCommandTypeGraph(CommandType)
50 {
51 alias Types = AliasSeq!CommandType;
52 immutable TypeGraphNode[][1] adjacencies = [[]];
53 immutable int[] rootTypeIndices = [0];
54
55 template getTypeIndexOf(T)
56 {
57 static assert(is(T == CommandType));
58 enum int getTypeIndexOf = 0;
59 }
60 }
61
62 /// Represents a command type graph where the information about the parent-child
63 /// relationships of commands are drawn from the children, via the @ParentCommand UDA.
64 template BottomUpCommandTypeGraph(_Types...)
65 {
66 alias Node = TypeGraphNode;
67 alias Types = _Types;
68
69 // Mappings, rootTypeIndices, adjacencies
70 mixin(getGraphMixinText());
71 // pragma(msg, getGraphMixinText());
72
73 template getTypeIndexOf(T)
74 {
75 mixin("alias getTypeIndexOf = Mappings!()." ~ escapedName!T ~ ";");
76 }
77
78 // Note:
79 // I'm realying on the idea that name lookup in scopes is linear in time to
80 // essentially have a fake compile time AA.
81 // Normal AA's are not allowed to be used at compile time rn.
82 // (E.g. `immutable int[int] example = [1: 2]` does not compile).
83 // TODO: refactor to return an info struct, like the top-down graph below.
84 private string getGraphMixinText()
85 {
86 size_t[string] typeToIndex;
87 static foreach (index, Type; Types)
88 typeToIndex[escapedName!Type] = index;
89 Node[][Types.length] childrenGraph;
90
91 foreach (outerIndex, Type; Types)
92 {
93 static foreach (fieldIndex, field; Type.tupleof)
94 {
95 static if (is(typeof(field) : T*, T))
96 {
97 static if (hasUDA!(field, ParentCommand))
98 {{
99 const name = escapedName!T;
100 if (auto index = name in typeToIndex)
101 {
102 // A command being a child of itself is not detected anywhere else, it's an edge case.
103 assert(*index != outerIndex, "`" ~ T.stringof ~ "` cannot be a parent of itself.");
104
105 childrenGraph[*index] ~= Node(cast(int) outerIndex, cast(int) fieldIndex);
106 }
107 else
108 {
109 assert(false, "`" ~ T.stringof ~ "` not found among types.");
110 }
111 }}
112 }
113 }
114 }
115
116 // TODO: is bit array worth it?
117 bool [Types.length] isNotRootCache;
118 foreach (parentIndex, children; childrenGraph)
119 {
120 foreach (childNode; children)
121 isNotRootCache[childNode.typeIndex] = true;
122 }
123
124 size_t[] rootTypeIndices;
125 foreach (index, isNotRoot; isNotRootCache)
126 {
127 if (!isNotRoot)
128 rootTypeIndices ~= index;
129 }
130
131 checkNodeAcessibility(childrenGraph[], rootTypeIndices);
132
133 {
134 // Check for cicles in the graph.
135 // Cicles will stifle the compiler (but I'm not sure).
136 // TODO: use bit array?
137 bool[Types.length] visited = false;
138
139 bool isCyclic(size_t index)
140 {
141 if (visited[index])
142 return true;
143
144 visited[index] = true;
145 foreach (childNode; childrenGraph[index])
146 {
147 if (isCyclic(childNode.typeIndex))
148 return true;
149 }
150 return false;
151 }
152
153 foreach (parentIndex, isNotRoot; isNotRootCache)
154 {
155 if (isNotRoot)
156 continue;
157 visited[] = false;
158 if (isCyclic(parentIndex))
159 {
160 // TODO: report more info here.
161 assert(false, "The command graph contains a cycle");
162 }
163 }
164 }
165
166 import std.array : appender;
167 import std.format : formattedWrite;
168 import std.algorithm : map;
169
170 auto ret = appender!string;
171
172 {
173 ret ~= "template Mappings() {";
174 foreach (key, index; typeToIndex)
175 formattedWrite(ret, "enum int %s = %d;", key, index);
176 ret ~= "}";
177 }
178
179 // TODO: return normally
180 {
181 formattedWrite(ret, "immutable int[] rootTypeIndices = %s;\n", rootTypeIndices);
182 }
183 {
184 formattedWrite(ret, "immutable Node[][] adjacencies = %s;\n", childrenGraph);
185 }
186
187 // Extra info, not actually used
188 static if (0)
189 {
190 formattedWrite(ret, "immutable bool[] isNodeRoot = %s;\n", isNotRootCache[].map!"!a");
191
192 auto types = appender!string;
193 auto fields = appender!string;
194
195 foreach (parentIndex, ParentType; Types)
196 {
197 types ~= "alias " ~ escapedName!ParentType ~ " = AliasSeq!(";
198 fields ~= "alias " ~ escapedName!ParentType ~ " = AliasSeq!(";
199
200 foreach (typeIndexIndex, childNode; childrenGraph[parentIndex])
201 {
202 if (typeIndexIndex > 0)
203 {
204 types ~= ", ";
205 fields ~= ", ";
206 }
207
208 formattedWrite(fields, "Types[%d].tupleof[%d]",
209 childNode.typeIndex, childNode.fieldIndex);
210
211 formattedWrite(types, "Types[%d]",
212 childNode.typeIndex);
213 }
214
215 types ~= ");\n";
216 fields ~= ");\n";
217 }
218
219 ret ~= "\ntemplate Commands() {\n";
220 ret ~= types[];
221 ret ~= "\n}\n";
222
223 ret ~= "\ntemplate Fields() {\n";
224 ret ~= fields[];
225 ret ~= "\n}\n";
226 }
227
228 return ret[];
229 }
230 }
231
232 unittest
233 {
234 {
235 static struct A {}
236 static struct B { @ParentCommand A* a; }
237 alias Graph = BottomUpCommandTypeGraph!(A, B);
238 static assert(is(Graph.Types == AliasSeq!(A, B)));
239
240 enum AIndex = Graph.getTypeIndexOf!A;
241 static assert(AIndex == 0);
242
243 enum BIndex = Graph.getTypeIndexOf!B;
244 static assert(BIndex == 1);
245
246 static assert(Graph.adjacencies[AIndex] == [TypeGraphNode(BIndex, 0)]);
247 static assert(Graph.adjacencies[BIndex].length == 0);
248
249 static assert(Graph.rootTypeIndices == [AIndex]);
250 }
251
252 // Cycle detection
253 {
254 static struct A { @ParentCommand A* a; }
255 static assert(!__traits(compiles, BottomUpCommandTypeGraph!A));
256 }
257
258 template Cycle()
259 {
260 struct A0 { @ParentCommand B0* b; }
261 struct B0 { @ParentCommand A0* a; }
262 static assert(!__traits(compiles, BottomUpCommandTypeGraph!(A0, B0)));
263 }
264
265 alias a = Cycle!();
266 }
267
268
269
270 // Haven't tested this one, haven't used it either.
271 template AllCommandsOf(Modules...)
272 {
273 template getCommands(alias Module)
274 {
275 template isCommand(string memberName)
276 {
277 import jcli.core;
278 enum isCommand = hasUDA!(__traits(getMember, Module, memberName), Command)
279 || hasUDA!(__traits(getMember, Module, memberName), CommandDefault);
280 }
281 alias commandNames = Filter!(isCommand, __traits(allMembers, Module));
282
283 alias getMember(string memberName) = __traits(getMember, Module, memberName);
284 alias getCommands = staticMap!(getMember, commandNames);
285 }
286
287 alias AllCommandsOf = staticMap!(getCommands, Modules);
288 }
289
290
291 /// Represents a command type graph where the information about the parent-child
292 /// relationships of commands are drawn from the parents, via the @Subcommands UDA.
293 template TopDownCommandTypeGraph(RootTypes...)
294 {
295 alias Node = TypeGraphNode;
296 private alias AllTypes = AllSubcommandsOf!RootTypes;
297
298 private immutable graphData = getGraphData();
299
300 // Types, Mappings
301 mixin(graphData.mixinText);
302 immutable Node[][] adjacencies = graphData.childrenGraph;
303 immutable size_t[] rootTypeIndices = graphData.rootTypeIndices;
304
305 template getTypeIndexOf(T)
306 {
307 mixin("alias getTypeIndexOf = Mappings!()." ~ escapedName!T ~ ";");
308 }
309
310 private auto getGraphData()
311 {
312 static struct Result
313 {
314 string mixinText;
315 Node[][] childrenGraph;
316 size_t[] rootTypeIndices;
317 }
318
319 // This thing could contain duplicates!
320 // Which is why I'm doing all of the remapping below.
321 // It's still a bad idea to map to a command from two places, because then this array
322 // will contain ALL of the subcommands of that type both times!
323
324 size_t[string] typeToIndex;
325 size_t[] actualTypeIndexToAllTypeIndex;
326
327 static foreach (index, Type; AllTypes)
328 {{
329 if (escapedName!Type !in typeToIndex)
330 {
331 typeToIndex[escapedName!Type] = actualTypeIndexToAllTypeIndex.length;
332 actualTypeIndexToAllTypeIndex ~= index;
333 }
334 }}
335
336 size_t numTypes = actualTypeIndexToAllTypeIndex.length;
337 auto childrenGraph = new Node[][](numTypes);
338
339 static foreach (index, ParentType; AllTypes)
340 {{
341 size_t actualTypeIndex = typeToIndex[escapedName!ParentType];
342
343 if (actualTypeIndexToAllTypeIndex[actualTypeIndex] == index)
344 {
345 static foreach (Subcommand; SubcommandsOf!ParentType)
346 {{
347 int fieldIndex = getIndexOfFieldWithParentPointerType!(ParentType, Subcommand);
348 size_t subcommandActualTypeIndex = typeToIndex[escapedName!Subcommand];
349 childrenGraph[actualTypeIndex] ~= Node(cast(int) subcommandActualTypeIndex, cast(int) fieldIndex);
350 }}
351 }
352 }}
353
354 size_t[] rootTypeIndices; // @suppress(dscanner.suspicious.label_var_same_name)
355 foreach (RootType; RootTypes)
356 rootTypeIndices ~= typeToIndex[escapedName!RootType];
357
358 checkNodeAcessibility(childrenGraph[], rootTypeIndices);
359
360 import std.array : appender;
361 import std.format : formattedWrite;
362 import std.algorithm : map;
363
364 auto ret = appender!string;
365
366 {
367 ret ~= "template Mappings() {";
368 foreach (key, index; typeToIndex)
369 formattedWrite!"enum int %s = %d;"(ret, key, index);
370 ret ~= "}";
371 }
372
373 {
374 ret ~= "\n";
375 ret ~= "alias Types = AliasSeq!(";
376 size_t appendedCount = 0;
377 static foreach (index, Type; AllTypes)
378 {{
379 size_t actualIndex = typeToIndex[escapedName!Type];
380 if (actualTypeIndexToAllTypeIndex[actualIndex] == index)
381 {
382 if (appendedCount > 0)
383 ret ~= ",";
384
385 assert(appendedCount == actualIndex);
386 appendedCount++;
387
388 formattedWrite!"AllTypes[%d]"(ret, actualTypeIndexToAllTypeIndex[actualIndex]);
389 }
390 }}
391 ret ~= ");";
392 ret ~= "\n";
393 }
394
395 return Result(ret[], childrenGraph, rootTypeIndices);
396 }
397 }
398
399 unittest
400 {
401 template Basic()
402 {
403 @(Subcommands!B)
404 static struct A {}
405
406 static struct B { A* a; }
407
408 alias Graph = TopDownCommandTypeGraph!(A);
409 static assert(is(Graph.Types == AliasSeq!(A, B)));
410
411 enum AIndex = 0;
412 static assert(AIndex == Graph.getTypeIndexOf!A);
413
414 enum BIndex = 1;
415 static assert(BIndex == Graph.getTypeIndexOf!B);
416
417 enum node = TypeGraphNode(BIndex, 0);
418 static assert(Graph.adjacencies[AIndex].length == 1);
419 static assert(Graph.adjacencies[AIndex][0] == node);
420 static assert(Graph.adjacencies[BIndex].length == 0);
421
422 static assert(Graph.rootTypeIndices == [AIndex]);
423 }
424
425 // Cycle detection
426 template ParentOfSelf()
427 {
428 @(Subcommands!A)
429 static struct A { A* a; }
430 static assert(!__traits(compiles, TopDownCommandTypeGraph!A));
431 }
432
433 template Cycle()
434 {
435 @(Subcommands!B)
436 static struct A { B* b; }
437 @(Subcommands!A)
438 static struct B { A* a; }
439 static assert(!__traits(compiles, TopDownCommandTypeGraph!(A, B)));
440 static assert(!__traits(compiles, TopDownCommandTypeGraph!(A)));
441 static assert(!__traits(compiles, TopDownCommandTypeGraph!(B)));
442 }
443
444 template NoField()
445 {
446 @(Subcommands!B)
447 static struct A {}
448 static struct B {}
449
450 alias Graph = TopDownCommandTypeGraph!(A);
451 enum AIndex = Graph.getTypeIndexOf!A;
452 enum BIndex = Graph.getTypeIndexOf!B;
453
454 enum node = TypeGraphNode(BIndex, -1);
455 static assert(Graph.adjacencies[AIndex].length == 1);
456 static assert(Graph.adjacencies[AIndex][0] == node);
457 }
458
459 template DuplicateParents()
460 {
461 @(Subcommands!C)
462 static struct A {}
463 @(Subcommands!C)
464 static struct B {}
465 static struct C {A* a; B* b;}
466
467 alias Graph = TopDownCommandTypeGraph!(A, B);
468 enum AIndex = Graph.getTypeIndexOf!A;
469 enum BIndex = Graph.getTypeIndexOf!B;
470 enum CIndex = Graph.getTypeIndexOf!C;
471 static assert(Graph.Types.length == 3);
472
473 enum nodeParentA = TypeGraphNode(CIndex, 0);
474 enum nodeParentB = TypeGraphNode(CIndex, 1);
475
476 static assert(Graph.adjacencies[AIndex].length == 1);
477 static assert(Graph.adjacencies[AIndex][0] == nodeParentA);
478
479 static assert(Graph.adjacencies[BIndex].length == 1);
480 static assert(Graph.adjacencies[BIndex][0] == nodeParentB);
481
482 static assert(Graph.adjacencies[CIndex].length == 0);
483 }
484
485 {
486 alias _ = Basic!();
487 }
488 {
489 alias _ = ParentOfSelf!();
490 }
491 {
492 alias _ = Cycle!();
493 }
494 {
495 alias _ = NoField!();
496 }
497 {
498 alias _ = DuplicateParents!();
499 }
500 }
501
502
503 template SubcommandsOf(CommandType)
504 {
505 alias _Subcommands = getUDAs!(CommandType, Subcommands);
506 alias getTypes(Attr : Subcommands!(Types), Types...) = Types;
507 alias SubcommandsOf = staticMap!(getTypes, _Subcommands);
508 }
509 unittest
510 {
511 {
512 static struct A {}
513 static assert(is(SubcommandsOf!A == AliasSeq!()));
514 }
515 {
516 static struct A {}
517 @(Subcommands!A)
518 static struct B {}
519 static assert(is(SubcommandsOf!B == AliasSeq!A));
520 }
521 {
522 static struct A1 {}
523 static struct A2 {}
524 static struct A3 {}
525
526 @(Subcommands!(A1, A2))
527 @(Subcommands!(A3))
528 static struct B {}
529
530 static assert(is(SubcommandsOf!(B) == AliasSeq!(A1, A2, A3)));
531 }
532 }
533
534 template AllSubcommandsOf(CommandTypes...)
535 {
536 static if (CommandTypes.length == 1)
537 {
538 alias AllSubcommandsOf = AliasSeq!(
539 CommandTypes[0], staticMap!(.AllSubcommandsOf, SubcommandsOf!(CommandTypes[0])));
540 }
541 else static if (CommandTypes.length == 0)
542 {
543 alias AllSubcommandsOf = AliasSeq!();
544 }
545 else
546 {
547 alias AllSubcommandsOf = staticMap!(.AllSubcommandsOf, CommandTypes);
548 }
549 }
550 unittest
551 {
552 template Cycle()
553 {
554 @(Subcommands!B)
555 static struct A {}
556 @(Subcommands!A)
557 static struct B {}
558 static assert(!__traits(compiles, AllSubcommandsOf!A));
559 static assert(!__traits(compiles, AllSubcommandsOf!B));
560 static assert(!__traits(compiles, AllSubcommandsOf!(A, B)));
561 }
562
563 {
564 static struct A {}
565 static assert(is(AllSubcommandsOf!A == AliasSeq!(A)));
566 }
567
568 template SelfIncluded()
569 {
570 static struct A {}
571 @(Subcommands!A)
572 static struct B {}
573 static assert(is(AllSubcommandsOf!B == AliasSeq!(B, A)));
574 }
575
576 {
577 alias _ = Cycle!();
578 }
579 {
580 alias _ = SelfIncluded!();
581 }
582
583 }
584
585
586 private int getIndexOfFieldWithParentPointerType(ParentType, ChildType)()
587 {
588 int result = -1;
589 static foreach (SubcommandType; SubcommandsOf!ParentType)
590 {
591 static foreach (fieldIndex, field; SubcommandType.tupleof)
592 {{
593 static if (is(typeof(field) : T*, T))
594 {
595 // TODO: ParentCommand uda checks
596 static if (is(T == ParentType))
597 {
598 result = cast(int) fieldIndex;
599 }
600 }
601 }}
602 }
603 return result;
604 }
605
606 unittest
607 {
608 {
609 static struct A {}
610 static assert(is(AllSubcommandsOf!A == AliasSeq!(A)));
611 }
612 {
613 static struct A {}
614 static struct B {}
615 static assert(is(AllSubcommandsOf!(A, B) == AliasSeq!(A, B)));
616 }
617 {
618 static struct B {}
619 static struct C {}
620
621 @(Subcommands!(B, C))
622 static struct A {}
623
624 static assert(is(AllSubcommandsOf!(A) == AliasSeq!(A, B, C)));
625 }
626 }
627
628
629 private void checkNodeAcessibility(const TypeGraphNode[][] adjacencies, const size_t[] rootTypeIndices)
630 {
631 bool[] isAccessibleCache = new bool[adjacencies.length];
632
633 void markChildrenAccessible(size_t index)
634 {
635 foreach (childNode; adjacencies[index])
636 {
637 if (isAccessibleCache[childNode.typeIndex])
638 continue;
639 isAccessibleCache[childNode.typeIndex] = true;
640 markChildrenAccessible(childNode.typeIndex);
641 }
642 }
643
644 foreach (parentIndex; rootTypeIndices)
645 {
646 isAccessibleCache[parentIndex] = true;
647 markChildrenAccessible(parentIndex);
648 }
649
650 import std.algorithm : all;
651 // TODO: better error here.
652 assert(all(isAccessibleCache[]), "Some types were inaccessible.");
653 }