sandbox: merge two projects

Farhan is currently working on this. Outstanding tasks:

Merge simple "solid nodes"
Make merge algorithm more easily shared
Crate tests we can re-use in lightning (at the yaml level - merge two yaml files and get a third yaml back)

Maybe for now we should console.warn every time we create a new uuid, just to communicate that ids may not track

Acceptance criteria:

We can basically merge two projects (so long as node names or ids don't change)
We can share the logic of the merge with the Lightning team
We can share a bunch of tests with the Lightning team

@theroinaochieng

@theroinaochieng here is Farhan's current issue - the upcoming pipeline is in the epic

Details are a bit loose a the moment, we'll tighten up as we go

Here is the merge algorithm I've proposed we implement:

Note: in this algorithm a node could be a Step or Trigger

Algorithm to merge one workflow (the source) into another (the target)

Eg, when merging `staging` into `main`, `staging` is the source and `main` is the `target`

The exercise here is basically to map the source nodes to UUIDS in the target workflow

MERGE(sourceWorkflow, targetWorkflow):

Note: in the CLI, merge returns a new workflow and does not mutate source or target.

- Build a pool of all the nodes in the target workflow. Index by name (in CLI, by id)
- Build a flat list of nodes in the source workflow
- Call MATCH_SOLID to map trivial nodes
- Call MATCH_EXPRESSION to map nodes with the same expression
- Call MATCH_PARENT to map nodes with the same structural position in the workflow
- Call MATCH_POSITION to map nodes with the same layout location
- If any nodes are left in the source pool, they are new nodes. Generate a new UUID for them and add them to the target workflow.
- If any nodes are left in the target pool, they must be removed from the target
- Call MAP_EDGES with the latest version of the target workflow


MATCH_SOLID(sourceNodes, targetNodes)
  - For each node in the source pool
  - Look for a single node in the target pool with the same name (in CLI, use `id` instead of `name`)
  - If there's a match, call REPLACE_NODE
  - If there are two source nodes with the same id... error? Or continue?

MATCH_EXPRESSION(sourceNodes, targetNodes)
  - For each Step type node in the source pool
  - Look for a single node in the target pool with the same expression
  - (later) Attempt a fuzzy match, rather than an exact one
  - If there's a single match, call REPLACE_NODE
  - If there are multiple matches, call MATCH_PARENT and MATCH_ADAPTOR to find a match

MATCH_PARENT(sourceNodes, targetNodes)
  - For each Step type node in the source pool
  - Look for a single node in the target pool with the same parent
  - If there are multiple matches, call MATCH_ADAPTOR to find a match

MATCH_ADAPTOR(sourceNodes, targetNodes)
  - For each Step type node in the source pool
  - Look for a single node in the target pool with the same adaptor
  - If there's a single match, call REPLACE_NODE

MAP_EDGES(sourceWorkflow, targetWorkflow):
  - for each edge in the source
  - identify the new from/to UUIDS for the edge
  - In the target, find an edge with the same from/to UUIDS
  - Replace the target edge properties with the source edge propertes (excluding any properties?)


MATCH_EDGES()
  - for each edge in the target
  - Get the UUIDs of the source and target
  - Find the corrsponsing
  - Call REPLACE_NODE

REPLACE_NODE(source, target):

  Replace the values of the target node with the values of the source (or, apply the properties of the source to the target)

  - clone the source node into a new node
  - apply the UUID from the target node into the new node
  - (copy other properties from the target, maybe some options? Maybe the credential?)
  - Remove the source and target node form both pools

Our algorithm will be slightly more performant if we're able to iterate from leaf nodes up to the root.
A post-order traversal.
This is because leaf nodes seem to have less ambiguity compared to the other nodes.

Performance is not a concern here. Workflows are small and merges are infrequent

Algorithm to merge one workflow (the source) into another (the target)

Eg, when merging `staging` into `main`, `staging` is the source and `main` is the `target`

The exercise here is basically to map the source nodes to UUIDS in the target workflow

MERGE(sourceWorkflow, targetWorkflow):

Note: in the CLI, merge returns a new workflow and does not mutate source or target.

- Build an index of of all the nodes in the target workflow, by id (in CLI this means name, not UUID)
- Build a POOL of nodes in the workflow. No sorting required.
- Call MATCH_SOLID to map trivial nodes into an ID Map 
- For each node in the POOL:
  - Call MATCH_EXPRESSION to map nodes with the same expression
  - Call MATCH_PARENT to map nodes with the same structural position in the workflow
  - Call MATCH_POSITION to map nodes with the same layout location
-  At the end of the loop, If a) there are still nodes left, AND b) new ids were added to the ID MAP in the last iteration, run the loop again
- After the pool is exhausted, or all ids have been mapped, any nodes still in the pool need a new UUID
- Call MAP_EDGES with the latest version of the target workflow

MATCH_SOLID(sourceNodes, targetNodes)
  - For each node in the source pool
  - Look for a single node in the target pool with the same name (in CLI, use `id` instead of `name`)
  - If there's a match, call REPLACE_NODE
  - If there are two source nodes with the same id... error? Or continue?

MATCH_EXPRESSION(sourceNodes, targetNodes)
  - For each Step type node in the source pool
  - Look for a single node in the target pool with the same expression
  - (later) Attempt a fuzzy match, rather than an exact one
  - If there's a single match, call REPLACE_NODE
  - If there are multiple matches, call MATCH_PARENT and MATCH_ADAPTOR to find a match

MATCH_PARENT(sourceNodes, targetNodes)
  - For each Step type node in the source pool
  - Look for a single node in the target pool with the same parent
  - If there are multiple matches, call MATCH_ADAPTOR to find a match

MATCH_ADAPTOR(sourceNodes, targetNodes)
  - For each Step type node in the source pool
  - Look for a single node in the target pool with the same adaptor
  - If there's a single match, call REPLACE_NODE

MAP_EDGES(sourceWorkflow, targetWorkflow):
  - for each edge in the source
  - identify the new from/to UUIDS for the edge
  - In the target, find an edge with the same from/to UUIDS
  - Replace the target edge properties with the source edge propertes (excluding any properties?)


MATCH_EDGES()
  - for each edge in the target
  - Get the UUIDs of the source and target
  - Find the corrsponsing
  - Call REPLACE_NODE

REPLACE_NODE(source, target):

  Replace the values of the target node with the values of the source (or, apply the properties of the source to the target)

  - clone the source node into a new node
  - apply the UUID from the target node into the new node
  - (copy other properties from the target, maybe some options? Maybe the credential?)
  - Remove the source and target node form both pools

Workflow merging is about done - subject to review and imperfectly, but good enough to move forward.

Next step is project merge, merging some or all workflows in a project. Map workflows by name, and allow users to pass their own map.

Workflow UUIDs must be perserved. The UUID of the target must not change

How to handle project merging

This explains how to handle id conflicts when choosing which workflows to merge into a project

merge(source, target, {
mappings: {} // allows me to rename workflows
// if not set, this means "all"
removeUnmapped: false // any workflows in the TARGET which are not mapped, should be removed
// if true, this means: remove everything from the target and just apply all workflows in the [mapped] source
})

Examples:

mappings - what from SOURCE do I include in the merge
removedUnmapped - what do I do with unaffected workflows in the TARGET


1.
source - target
[a',b,c] -> [a,b]
mappings: *
removeUnmapped: false
-> [a,b,c]  

2.
[a',b, c] -> [a,b]
mappings: *
removeUnmapped: false
-> [a,b,c]   (b is old!)

3.
[a',b, c] -> [a,b]
mappings: *
removeUnmapped: true
-> [a,c]   (b is removed!)

4.
[a',b, c] -> [a,b]
mappings: { c: a }
removeUnmapped: true
-> [c]   (b and a removed)

5. merge and a rename just one workflow
[a',b, c] -> [a,b]
mappings: { c: a }
removeUnmapped: false
-> [a(c), b]
- a is now c
- b and a are ignored in source
- you'd get an error if mapping c:a AND including a

6. ERROR
[a',b, c] -> [a,b]
mappings: { a: 'a', c: a }
removeUnmapped: false
you can't merge a AND merge C into a!

7. only merge a single workflow
[a',b, c] -> [a,b]
mappings: { a: a }
removeUnmapped: false
-> [a',b]

8. overwrite target (but only include one workflow)
[a',b, c] -> [a,b]
mappings: { a: a }
removeUnmapped: true
-> [a']

Navigation Menu

Repository navigation

sandbox: merge two projects #973

How to handle project merging

Examples:

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

sandbox: merge two projects #973

Description

Activity

josephjclark commented on Sep 1, 2025

josephjclark commented on Sep 2, 2025

doc-han commented on Sep 3, 2025

josephjclark commented on Sep 3, 2025

josephjclark commented on Sep 11, 2025

josephjclark commented on Sep 15, 2025

josephjclark commented on Sep 22, 2025

How to handle project merging

Examples:

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions