1 module reggae.range; 2 3 import reggae.build; 4 import std.range; 5 import std.algorithm; 6 7 @safe: 8 9 struct DepthFirst { 10 const(Target)[] targets; 11 12 this(in Target target) pure nothrow { 13 this.targets = depthFirstTargets(target); 14 } 15 16 const(Target)[] depthFirstTargets(in Target target) pure nothrow { 17 //if leaf, return 18 if(target.isLeaf) return target.command is null ? [] : [target]; 19 20 //if not, add ourselves to the end to get depth-first 21 return reduce!((a, b) => a ~ depthFirstTargets(b))(typeof(return).init, target.dependencies) ~ 22 reduce!((a, b) => a ~ depthFirstTargets(b))(typeof(return).init, target.implicits) ~ 23 target; 24 } 25 26 auto front() pure nothrow { 27 return targets.front; 28 } 29 30 void popFront() pure nothrow { 31 targets.popFront; 32 } 33 34 bool empty() pure nothrow { 35 return targets.empty; 36 } 37 38 static assert(isInputRange!DepthFirst); 39 } 40 41 42 struct ByDepthLevel { 43 const(Target)[][] targets; 44 45 this(in Target target) pure nothrow { 46 this.targets = sortTargets(target); 47 } 48 49 auto front() pure nothrow { 50 return targets.front; 51 } 52 53 void popFront() pure nothrow { 54 targets.popFront; 55 } 56 57 bool empty() pure nothrow { 58 return targets.empty; 59 } 60 61 private const(Target)[][] sortTargets(in Target target) pure nothrow { 62 if(target.isLeaf) return []; 63 64 const(Target)[][] targets = [[target]]; 65 rec(0, [target], targets); 66 return targets.retro.array; 67 } 68 69 private void rec(int level, in Target[] targets, ref const(Target)[][] soFar) @trusted pure nothrow { 70 const notLeaves = targets. 71 map!(a => chain(a.dependencies, a.implicits)). //get all dependencies 72 flatten. //flatten into a regular range 73 filter!(a => !a.isLeaf). //don't care about leaves 74 array; 75 if(notLeaves.empty) return; 76 77 soFar ~= notLeaves; 78 rec(level + 1, notLeaves, soFar); 79 } 80 81 static assert(isInputRange!ByDepthLevel); 82 } 83 84 85 //TODO: a non-allocating version with no arrays 86 auto flatten(R)(R range) pure nothrow { 87 alias rangeType = ElementType!R; 88 alias T = ElementType!rangeType; 89 T[] res; 90 foreach(x; range) res ~= x.array; 91 return res; 92 }