Hugging Face's logo

Spaces:
Leon4gr45
/
twenty
Build error

App Files Community
1
twenty
File size: 2,730 Bytes
d9494a5
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
import { isDefined } from '@/utils';
import { TRIGGER_STEP_ID } from '@/workflow/constants/TriggerStepId';
import { type ValidatableWorkflow } from '@/workflow/validation/types/workflow-validation.type';
import { getStepOutgoingStepIds } from '@/workflow/validation/utils/get-step-outgoing-step-ids.util';

export type WorkflowGraph = {
  childrenByStepId: Map<string, string[]>;
  reachableFromTrigger: Set<string>;
  ancestorsByStepId: Map<string, Set<string>>;
};

export const buildWorkflowGraph = ({
  trigger,
  steps,
}: ValidatableWorkflow): WorkflowGraph => {
  const childrenByStepId = new Map<string, string[]>();

  const triggerNextStepIds = isDefined(trigger?.nextStepIds)
    ? trigger.nextStepIds.filter(isDefined)
    : [];

  childrenByStepId.set(TRIGGER_STEP_ID, triggerNextStepIds);

  for (const step of steps ?? []) {
    childrenByStepId.set(step.id, getStepOutgoingStepIds(step));
  }

  const reachableFromTrigger = new Set<string>();
  const queue: string[] = [TRIGGER_STEP_ID];

  while (queue.length > 0) {
    const currentStepId = queue.shift();

    if (!isDefined(currentStepId) || reachableFromTrigger.has(currentStepId)) {
      continue;
    }

    reachableFromTrigger.add(currentStepId);

    for (const nextStepId of childrenByStepId.get(currentStepId) ?? []) {
      if (!reachableFromTrigger.has(nextStepId)) {
        queue.push(nextStepId);
      }
    }
  }

  const ancestorsByStepId = computeAncestors(childrenByStepId);

  return { childrenByStepId, reachableFromTrigger, ancestorsByStepId };
};

const computeAncestors = (
  childrenByStepId: Map<string, string[]>,
): Map<string, Set<string>> => {
  const parentsByStepId = new Map<string, Set<string>>();

  for (const [stepId, nextStepIds] of childrenByStepId.entries()) {
    for (const nextStepId of nextStepIds) {
      const parents = parentsByStepId.get(nextStepId) ?? new Set<string>();

      parents.add(stepId);
      parentsByStepId.set(nextStepId, parents);
    }
  }

  const ancestorsByStepId = new Map<string, Set<string>>();

  for (const stepId of childrenByStepId.keys()) {
    if (ancestorsByStepId.has(stepId)) {
      continue;
    }

    const ancestors = new Set<string>();
    const queue = [...(parentsByStepId.get(stepId) ?? [])];

    while (queue.length > 0) {
      const ancestorStepId = queue.shift()!;

      if (ancestors.has(ancestorStepId)) {
        continue;
      }

      ancestors.add(ancestorStepId);

      for (const grandParentStepId of parentsByStepId.get(ancestorStepId) ??
        []) {
        if (!ancestors.has(grandParentStepId)) {
          queue.push(grandParentStepId);
        }
      }
    }

    ancestorsByStepId.set(stepId, ancestors);
  }

  return ancestorsByStepId;
};