Skip to content

Exponential complexity in mergeDeep when merging recursive objects #1587

@abhishekg999

Description

@abhishekg999

What version of Elysia is running?

1.4.17

What platform is your computer?

Darwin 24.3.0 arm64 arm

What environment are you using

1.3.2

Are you using dynamic mode?

no

What steps can reproduce the bug?

for debug i just have this patch in src/utils.ts

diff --git a/src/utils.ts b/src/utils.ts
index 4a8ec09a..959db157 100644
--- a/src/utils.ts
+++ b/src/utils.ts
@@ -1,4 +1,3 @@
-import { isStringTextContainingNode } from 'typescript'
 import type { Sucrose } from './sucrose'
 import type { TraceHandler } from './trace'
 
@@ -49,6 +48,9 @@ export const isClass = (v: Object) =>
 const isObject = (item: any): item is Object =>
 	item && typeof item === 'object' && !Array.isArray(item)
 
+let mergeDeepCounter = 0
+export const DEBUG_getMergeDeepCount = () => mergeDeepCounter
+
 export const mergeDeep = <
 	A extends Record<string, any>,
 	B extends Record<string, any>
@@ -61,6 +63,7 @@ export const mergeDeep = <
 		mergeArray?: boolean
 	}
 ): A & B => {
+	mergeDeepCounter++
 	const skipKeys = options?.skipKeys
 	const override = options?.override ?? true
 	const mergeArray = options?.mergeArray ?? false

Minimal reproduction

import Elysia from './src'
import { DEBUG_getMergeDeepCount } from './src/utils'

const a: Record<string, unknown> = { x: 1 }
const b: Record<string, unknown> = { y: 2 }
const c: Record<string, unknown> = { z: 3 }

void a
void b
void c

// 23k mergeDeep calls
a.toB = b
b.toA = a

// server wont start i havent ran this long enough to see when but
// more than 30 mil mergeDeep calls
// a.toC = c
// c.toA = a

const complex = { a }

const Plugin = new Elysia({ name: 'Complex.Plugin', seed: 'seed' })
	.decorate('dep', complex)
	.as('scoped')

const ModuleA = new Elysia({ name: 'ModuleA' }).use(Plugin).get('/a', () => 'a')
const ModuleB = new Elysia({ name: 'ModuleB' }).use(Plugin).get('/b', () => 'b')

let app = new Elysia()

console.log(DEBUG_getMergeDeepCount())
app.use(ModuleA)
console.log('MergeDeep calls after ModuleA:', DEBUG_getMergeDeepCount())
app.use(ModuleB)
console.log('MergeDeep calls after ModuleB:', DEBUG_getMergeDeepCount())
app.listen(3333, ({ hostname, port }) => {
	console.log(`Server started on ${hostname}:${port}`)
})

The mergeDeep utility has exponential complexity when trying to merge decorated objects that may have recursive references.
The below showcases a simple example of where this complexity jump can be seen. With just having two objects that point to each other,
this makes:

MergeDeep calls after ModuleA: 3
MergeDeep calls after ModuleB: 21260
Server started on localhost:3333

21k recursive calls.

if you uncomment the:

// a.toC = c
// c.toA = a

lines, the server wont start and it has run beyond 30mil times.

Initially noticed this when using https://github.com/aws/aws-sdk-js-v3/blob/main/clients/client-ses/src/SESClient.ts for reference which will infinitely load.

While there probably is some things that can be updated in mergeDeep regarding the recursion and tracking seen objects similar to deepClone, my understanding was that plugins should be deduplicated and that meant that if I use(Plugin) multiple times, the later use() are effectively ignored? and shouldnt cause any merge to happen?

What is the expected behavior?

It should not have exponential complexity.

What do you see instead?

Server does not start for highly recursive objects. For the simple example provided above it makes 20k calls.

MergeDeep calls after ModuleA: 3
MergeDeep calls after ModuleB: 21260
Server started on localhost:3333

Additional information

No response

Have you try removing the node_modules and bun.lockb and try again yet?

yes

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions