# All files / packages/shared/src utils.ts

40% Statements 38/95
31.25% Branches 15/48
56.25% Functions 9/16
41.25% Lines 33/80

Press n or j to go to the next uncovered block, b, p or k for the previous block.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198

    1x

    10x

    23x
    9x
    9x

    9x
    23x
    23x

    9x
    10x
    9x
    10x

    9x
    23x
    10x

    9x

    9x

    21x
    21x
    21x

    21x
    7x
    7x
    7x
    6x

    9x
    1x
    1x
    3x
    1x
    1x

    9x

    40x

     /**
     * Shared utility functions that can be used across frontend and backend.
     */

    export interface SortableItem {
      priority: 'low' | 'medium' | 'high';
      createdAt: Date | string;
    }

    /**
     * Priority order mapping for sorting (higher number = higher priority)
     */
    const PRIORITY_ORDER = {
      high: 3,
      medium: 2,
      low: 1,
    } as const;

    /**
     * Sorts items by priority (high to low) then by queue time (oldest first).
     * This ensures high-priority items come first, but within the same priority,
     * items are processed in FIFO order.
     */
    export function sortByPriorityAndQueueTime<T extends SortableItem>(items: T[]): T[] {
      return [...items].sort((a, b) => {
        // First sort by priority (high to low)
        const priorityDiff = PRIORITY_ORDER[b.priority] - PRIORITY_ORDER[a.priority];
        if (priorityDiff !== 0) {
          return priorityDiff;
        }

        // Within same priority, sort by creation time (oldest first - FIFO)
        const aTime = typeof a.createdAt === 'string' ? new Date(a.createdAt) : a.createdAt;
        const bTime = typeof b.createdAt === 'string' ? new Date(b.createdAt) : b.createdAt;
        return aTime.getTime() - bTime.getTime();
      });
    }

    // ---------------------------------------------------------------------------
    // Topological Phase Sorting
    // ---------------------------------------------------------------------------

    export interface PhaseForSort {
      id: string;
      createdAt: Date | string;
    }

    export interface DependencyEdge {
      phaseId: string;
      dependsOnPhaseId: string;
    }

    /**
     * Topologically sort phases by their dependency edges (Kahn's algorithm).
     * Phases with no dependencies come first. Deterministic tiebreaker: createdAt ascending.
     * Phases involved in cycles are appended at the end, sorted by createdAt.
     */
    export function topologicalSortPhases<T extends PhaseForSort>(
      phases: T[],
      edges: DependencyEdge[],
    ): T[] {
      if (phases.length === 0) return [];

      const phaseMap = new Map(phases.map((p) => [p.id, p]));
      const inDegree = new Map<string, number>();
      const adjacency = new Map<string, string[]>(); // dependsOnPhaseId -> phaseIds that depend on it

      for (const p of phases) {
        inDegree.set(p.id, 0);
        adjacency.set(p.id, []);
      }

      for (const edge of edges) {
        if (!phaseMap.has(edge.phaseId) || !phaseMap.has(edge.dependsOnPhaseId)) continue;
        inDegree.set(edge.phaseId, (inDegree.get(edge.phaseId) ?? 0) + 1);
        adjacency.get(edge.dependsOnPhaseId)!.push(edge.phaseId);
      }

      // Seed queue with zero in-degree phases, sorted by createdAt
      const queue = phases
        .filter((p) => (inDegree.get(p.id) ?? 0) === 0)
        .sort((a, b) => toTime(a.createdAt) - toTime(b.createdAt));

      const result: T[] = [];

      while (queue.length > 0) {
        // Pick the earliest-created from the queue
        queue.sort((a, b) => toTime(a.createdAt) - toTime(b.createdAt));
        const current = queue.shift()!;
        result.push(current);

        for (const neighborId of adjacency.get(current.id) ?? []) {
          const newDeg = (inDegree.get(neighborId) ?? 1) - 1;
          inDegree.set(neighborId, newDeg);
          if (newDeg === 0) {
            queue.push(phaseMap.get(neighborId)!);
          }
        }
      }

      // Append any phases caught in cycles, sorted by createdAt
      if (result.length < phases.length) {
        const inResult = new Set(result.map((p) => p.id));
        const remaining = phases
          .filter((p) => !inResult.has(p.id))
          .sort((a, b) => toTime(a.createdAt) - toTime(b.createdAt));
        result.push(...remaining);
      }

      return result;
    }

    function toTime(d: Date | string): number {
      return typeof d === 'string' ? new Date(d).getTime() : d.getTime();
    }

    // ---------------------------------------------------------------------------
    // Pipeline Column Grouping
    // ---------------------------------------------------------------------------

    export interface PipelineColumn<T> {
      depth: number;
      phases: T[];
    }

    /**
     * Groups phases into pipeline columns by dependency depth.
     * Depth 0 = no dependencies, depth N = longest path from a root is N.
     * Phases within a column are sorted by createdAt ascending.
     * Phases in cycles are placed in the last column + 1.
     */
    export function groupPhasesByDependencyLevel<T extends PhaseForSort>(
      phases: T[],
      edges: DependencyEdge[],
    ): PipelineColumn<T>[] {
      if (phases.length === 0) return [];

      const phaseIds = new Set(phases.map((p) => p.id));

      // Build adjacency: for each phase, what does it depend on?
      const dependsOn = new Map<string, string[]>();
      for (const p of phases) dependsOn.set(p.id, []);
      for (const edge of edges) {
        if (!phaseIds.has(edge.phaseId) || !phaseIds.has(edge.dependsOnPhaseId)) continue;
        dependsOn.get(edge.phaseId)!.push(edge.dependsOnPhaseId);
      }

      // Compute depth via recursive longest path with cycle detection
      const depthCache = new Map<string, number>();
      const visiting = new Set<string>();

      function computeDepth(id: string): number {
        if (depthCache.has(id)) return depthCache.get(id)!;
        if (visiting.has(id)) return -1; // cycle detected

        visiting.add(id);
        const deps = dependsOn.get(id) ?? [];
        let maxDepth = 0;
        for (const depId of deps) {
          const d = computeDepth(depId);
          if (d === -1) {
            visiting.delete(id);
            return -1;
          }
          maxDepth = Math.max(maxDepth, d + 1);
        }
        visiting.delete(id);
        depthCache.set(id, maxDepth);
        return maxDepth;
      }

      // Compute depths
      let maxValidDepth = 0;
      for (const p of phases) {
        const d = computeDepth(p.id);
        if (d >= 0) maxValidDepth = Math.max(maxValidDepth, d);
      }

      // Group by depth
      const columnMap = new Map<number, T[]>();
      for (const p of phases) {
        const d = depthCache.get(p.id);
        const depth = d != null && d >= 0 ? d : maxValidDepth + 1; // cycles go last
        if (!columnMap.has(depth)) columnMap.set(depth, []);
        columnMap.get(depth)!.push(p);
      }

      // Sort phases within each column by createdAt
      const columns: PipelineColumn<T>[] = [];
      const sortedDepths = [...columnMap.keys()].sort((a, b) => a - b);
      for (const depth of sortedDepths) {
        const phasesInCol = columnMap.get(depth)!;
        phasesInCol.sort((a, b) => toTime(a.createdAt) - toTime(b.createdAt));
        columns.push({ depth, phases: phasesInCol });
      }

      return columns;
    }