lib/choir/src/core/cfg.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 pub fn contains(source: anytype, target: anytype) bool {
  2     return containsExcluding(source, target, null);
  3 }
  4 
  5 pub fn containsOther(source: anytype, target: anytype, excluded: anytype) bool {
  6     return containsExcluding(source, target, @ptrCast(excluded));
  7 }
  8 
  9 pub fn containsBounded(
 10     source: anytype,
 11     target: anytype,
 12     operation_limit: usize,
 13 ) error{OperationListCorrupted}!bool {
 14     var operations = source.getOperations();
 15     var count: usize = 0;
 16     while (operations.next()) |operation| {
 17         count += 1;
 18         if (count > operation_limit) return error.OperationListCorrupted;
 19         for (operation.successors.items) |successor| {
 20             if (successor == target) return true;
 21         }
 22     }
 23     return false;
 24 }
 25 
 26 fn containsExcluding(
 27     source: anytype,
 28     target: anytype,
 29     excluded: ?*const anyopaque,
 30 ) bool {
 31     var operations = source.getOperations();
 32     while (operations.next()) |operation| {
 33         const operation_ptr: *const anyopaque = @ptrCast(operation);
 34         if (excluded != null and excluded.? == operation_ptr) continue;
 35         for (operation.successors.items) |successor| {
 36             if (successor == target) return true;
 37         }
 38     }
 39     return false;
 40 }
 41 
 42 pub fn prepare(source: anytype, successors: anytype) !void {
 43     for (successors, 0..) |successor, index| {
 44         if (appearedBefore(successors, index, successor)) continue;
 45         if (successor.hasPredecessor(source)) continue;
 46         try successor.predecessors.ensureUnusedCapacity(successor.allocator, 1);
 47     }
 48 }
 49 
 50 pub fn attachAssumeCapacity(source: anytype, successors: anytype) void {
 51     for (successors) |successor| {
 52         if (successor.hasPredecessor(source)) continue;
 53         successor.predecessors.appendAssumeCapacity(source);
 54     }
 55 }
 56 
 57 pub fn attach(source: anytype, operation: anytype) !void {
 58     try prepare(source, operation.successors.items);
 59     attachAssumeCapacity(source, operation.successors.items);
 60 }
 61 
 62 pub fn detach(source: anytype, operation: anytype) void {
 63     for (operation.successors.items) |successor| {
 64         if (containsOther(source, successor, operation)) continue;
 65         removePredecessor(successor, source);
 66     }
 67 }
 68 
 69 pub fn detachReplaced(source: anytype, operation: anytype, successors: anytype) void {
 70     for (operation.successors.items) |successor| {
 71         if (containsTarget(successors, successor)) continue;
 72         if (containsOther(source, successor, operation)) continue;
 73         removePredecessor(successor, source);
 74     }
 75 }
 76 
 77 fn appearedBefore(successors: anytype, index: usize, expected: anytype) bool {
 78     for (successors[0..index]) |successor| {
 79         if (successor == expected) return true;
 80     }
 81     return false;
 82 }
 83 
 84 fn containsTarget(successors: anytype, expected: anytype) bool {
 85     for (successors) |successor| {
 86         if (successor == expected) return true;
 87     }
 88     return false;
 89 }
 90 
 91 fn removePredecessor(target: anytype, source: anytype) void {
 92     var index: usize = 0;
 93     while (index < target.predecessors.items.len) {
 94         if (target.predecessors.items[index] != source) {
 95             index += 1;
 96             continue;
 97         }
 98         _ = target.predecessors.swapRemove(index);
 99     }
100 }