flatted: Unbounded recursion DoS in parse() revive phase

@@ -22,8 +22,7 @@ const Primitives = (_, value) => (
   typeof value === primitive ? new Primitive(value) : value
 );
 
-const revive = (input, parsed, output, $) => {
-  const lazy = [];
+const resolver = (input, lazy, parsed, $) => output => {
   for (let ke = keys(output), {length} = ke, y = 0; y < length; y++) {
     const k = ke[y];
     const value = output[k];
@@ -32,18 +31,14 @@ const revive = (input, parsed, output, $) => {
       if (typeof tmp === object && !parsed.has(tmp)) {
         parsed.add(tmp);
         output[k] = ignore;
-        lazy.push({k, a: [input, parsed, tmp, $]});
+        lazy.push({ o: output, k, r: tmp });
       }
       else
         output[k] = $.call(output, k, tmp);
     }
     else if (output[k] !== ignore)
       output[k] = $.call(output, k, value);
   }
-  for (let {length} = lazy, i = 0; i < length; i++) {
-    const {k, a} = lazy[i];
-    output[k] = $.call(output, k, revive.apply(null, a));
-  }
   return output;
 };
 
@@ -61,12 +56,24 @@ const set = (known, input, value) => {
  */
 const parse = (text, reviver) => {
   const input = $parse(text, Primitives).map(primitives);
-  const value = input[0];
   const $ = reviver || noop;
-  const tmp = typeof value === object && value ?
-              revive(input, new Set, value, $) :
-              value;
-  return $.call({'': tmp}, '', tmp);
+
+  let value = input[0];
+
+  if (typeof value === object && value) {
+    const lazy = [];
+    const revive = resolver(input, lazy, new Set, $);
+    value = revive(value);
+
+    let i = 0;
+    while (i < lazy.length) {
+      // it could be a lazy.shift() but that's costly
+      const {o, k, r} = lazy[i++];
+      o[k] = $.call(o, k, revive(r));
+    }
+  }
+
+  return $.call({'': value}, '', value);
 };
 exports.parse = parse;
 

@@ -1 +1 @@
-self.Flatted=function(t){"use strict";const{parse:e,stringify:n}=JSON,{keys:r}=Object,s=String,o="string",c={},l="object",a=(t,e)=>e,f=t=>t instanceof s?s(t):t,i=(t,e)=>typeof e===o?new s(e):e,u=(t,e,n,o)=>{const a=[];for(let f=r(n),{length:i}=f,u=0;u<i;u++){const r=f[u],i=n[r];if(i instanceof s){const s=t[i];typeof s!==l||e.has(s)?n[r]=o.call(n,r,s):(e.add(s),n[r]=c,a.push({k:r,a:[t,e,s,o]}))}else n[r]!==c&&(n[r]=o.call(n,r,i))}for(let{length:t}=a,e=0;e<t;e++){const{k:t,a:r}=a[e];n[t]=o.call(n,t,u.apply(null,r))}return n},p=(t,e,n)=>{const r=s(e.push(n)-1);return t.set(n,r),r},y=(t,n)=>{const r=e(t,i).map(f),s=r[0],o=n||a,c=typeof s===l&&s?u(r,new Set,s,o):s;return o.call({"":c},"",c)},g=(t,e,r)=>{const s=e&&typeof e===l?(t,n)=>""===t||-1<e.indexOf(t)?n:void 0:e||a,c=new Map,f=[],i=[];let u=+p(c,f,s.call({"":t},"",t)),y=!u;for(;u<f.length;)y=!0,i[u]=n(f[u++],g,r);return"["+i.join(",")+"]";function g(t,e){if(y)return y=!y,e;const n=s.call(this,t,e);switch(typeof n){case l:if(null===n)return n;case o:return c.get(n)||p(c,f,n)}return n}};return t.fromJSON=t=>y(n(t)),t.parse=y,t.stringify=g,t.toJSON=t=>e(g(t)),t}({});
+self.Flatted=function(t){"use strict";const{parse:e,stringify:n}=JSON,{keys:r}=Object,o=String,s="string",c={},l="object",f=(t,e)=>e,i=t=>t instanceof o?o(t):t,a=(t,e)=>typeof e===s?new o(e):e,u=(t,e,n)=>{const r=o(e.push(n)-1);return t.set(n,r),r},p=(t,n)=>{const s=e(t,a).map(i),u=n||f;let p=s[0];if(typeof p===l&&p){const t=[],e=((t,e,n,s)=>f=>{for(let i=r(f),{length:a}=i,u=0;u<a;u++){const r=i[u],a=f[r];if(a instanceof o){const o=t[a];typeof o!==l||n.has(o)?f[r]=s.call(f,r,o):(n.add(o),f[r]=c,e.push({o:f,k:r,r:o}))}else f[r]!==c&&(f[r]=s.call(f,r,a))}return f})(s,t,new Set,u);p=e(p);let n=0;for(;n<t.length;){const{o:r,k:o,r:s}=t[n++];r[o]=u.call(r,o,e(s))}}return u.call({"":p},"",p)},g=(t,e,r)=>{const o=e&&typeof e===l?(t,n)=>""===t||-1<e.indexOf(t)?n:void 0:e||f,c=new Map,i=[],a=[];let p=+u(c,i,o.call({"":t},"",t)),g=!p;for(;p<i.length;)g=!0,a[p]=n(i[p++],h,r);return"["+a.join(",")+"]";function h(t,e){if(g)return g=!g,e;const n=o.call(this,t,e);switch(typeof n){case l:if(null===n)return n;case s:return c.get(n)||u(c,i,n)}return n}};return t.fromJSON=t=>p(n(t)),t.parse=p,t.stringify=g,t.toJSON=t=>e(g(t)),t}({});

@@ -21,8 +21,7 @@ const Primitives = (_, value) => (
   typeof value === primitive ? new Primitive(value) : value
 );
 
-const revive = (input, parsed, output, $) => {
-  const lazy = [];
+const resolver = (input, lazy, parsed, $) => output => {
   for (let ke = keys(output), {length} = ke, y = 0; y < length; y++) {
     const k = ke[y];
     const value = output[k];
@@ -31,18 +30,14 @@ const revive = (input, parsed, output, $) => {
       if (typeof tmp === object && !parsed.has(tmp)) {
         parsed.add(tmp);
         output[k] = ignore;
-        lazy.push({k, a: [input, parsed, tmp, $]});
+        lazy.push({ o: output, k, r: tmp });
       }
       else
         output[k] = $.call(output, k, tmp);
     }
     else if (output[k] !== ignore)
       output[k] = $.call(output, k, value);
   }
-  for (let {length} = lazy, i = 0; i < length; i++) {
-    const {k, a} = lazy[i];
-    output[k] = $.call(output, k, revive.apply(null, a));
-  }
   return output;
 };
 
@@ -60,12 +55,24 @@ const set = (known, input, value) => {
  */
 export const parse = (text, reviver) => {
   const input = $parse(text, Primitives).map(primitives);
-  const value = input[0];
   const $ = reviver || noop;
-  const tmp = typeof value === object && value ?
-              revive(input, new Set, value, $) :
-              value;
-  return $.call({'': tmp}, '', tmp);
+
+  let value = input[0];
+
+  if (typeof value === object && value) {
+    const lazy = [];
+    const revive = resolver(input, lazy, new Set, $);
+    value = revive(value);
+
+    let i = 0;
+    while (i < lazy.length) {
+      // it could be a lazy.shift() but that's costly
+      const {o, k, r} = lazy[i++];
+      o[k] = $.call(o, k, revive(r));
+    }
+  }
+
+  return $.call({'': value}, '', value);
 };
 
 /**

@@ -1 +1 @@
-const{parse:t,stringify:e}=JSON,{keys:n}=Object,l=String,o="string",r={},s="object",c=(t,e)=>e,a=t=>t instanceof l?l(t):t,f=(t,e)=>typeof e===o?new l(e):e,i=(t,e,o,c)=>{const a=[];for(let f=n(o),{length:i}=f,p=0;p<i;p++){const n=f[p],i=o[n];if(i instanceof l){const l=t[i];typeof l!==s||e.has(l)?o[n]=c.call(o,n,l):(e.add(l),o[n]=r,a.push({k:n,a:[t,e,l,c]}))}else o[n]!==r&&(o[n]=c.call(o,n,i))}for(let{length:t}=a,e=0;e<t;e++){const{k:t,a:n}=a[e];o[t]=c.call(o,t,i.apply(null,n))}return o},p=(t,e,n)=>{const o=l(e.push(n)-1);return t.set(n,o),o},u=(e,n)=>{const l=t(e,f).map(a),o=l[0],r=n||c,p=typeof o===s&&o?i(l,new Set,o,r):o;return r.call({"":p},"",p)},h=(t,n,l)=>{const r=n&&typeof n===s?(t,e)=>""===t||-1<n.indexOf(t)?e:void 0:n||c,a=new Map,f=[],i=[];let u=+p(a,f,r.call({"":t},"",t)),h=!u;for(;u<f.length;)h=!0,i[u]=e(f[u++],y,l);return"["+i.join(",")+"]";function y(t,e){if(h)return h=!h,e;const n=r.call(this,t,e);switch(typeof n){case s:if(null===n)return n;case o:return a.get(n)||p(a,f,n)}return n}},y=e=>t(h(e)),g=t=>u(e(t));export{g as fromJSON,u as parse,h as stringify,y as toJSON};
+const{parse:t,stringify:e}=JSON,{keys:n}=Object,o=String,r="string",s={},c="object",l=(t,e)=>e,f=t=>t instanceof o?o(t):t,i=(t,e)=>typeof e===r?new o(e):e,a=(t,e,n)=>{const r=o(e.push(n)-1);return t.set(n,r),r},u=(e,r)=>{const a=t(e,i).map(f),u=r||l;let p=a[0];if(typeof p===c&&p){const t=[],e=((t,e,r,l)=>f=>{for(let i=n(f),{length:a}=i,u=0;u<a;u++){const n=i[u],a=f[n];if(a instanceof o){const o=t[a];typeof o!==c||r.has(o)?f[n]=l.call(f,n,o):(r.add(o),f[n]=s,e.push({o:f,k:n,r:o}))}else f[n]!==s&&(f[n]=l.call(f,n,a))}return f})(a,t,new Set,u);p=e(p);let r=0;for(;r<t.length;){const{o:n,k:o,r:s}=t[r++];n[o]=u.call(n,o,e(s))}}return u.call({"":p},"",p)},p=(t,n,o)=>{const s=n&&typeof n===c?(t,e)=>""===t||-1<n.indexOf(t)?e:void 0:n||l,f=new Map,i=[],u=[];let p=+a(f,i,s.call({"":t},"",t)),h=!p;for(;p<i.length;)h=!0,u[p]=e(i[p++],g,o);return"["+u.join(",")+"]";function g(t,e){if(h)return h=!h,e;const n=s.call(this,t,e);switch(typeof n){case c:if(null===n)return n;case r:return f.get(n)||a(f,i,n)}return n}},h=e=>t(p(e)),g=t=>u(e(t));export{g as fromJSON,u as parse,p as stringify,h as toJSON};

@@ -32,30 +32,26 @@ self.Flatted = (function (exports) {
   var Primitives = function Primitives(_, value) {
     return _typeof(value) === primitive ? new Primitive(value) : value;
   };
-  var _revive = function revive(input, parsed, output, $) {
-    var lazy = [];
-    for (var ke = keys(output), length = ke.length, y = 0; y < length; y++) {
-      var k = ke[y];
-      var value = output[k];
-      if (value instanceof Primitive) {
-        var tmp = input[value];
-        if (_typeof(tmp) === object && !parsed.has(tmp)) {
-          parsed.add(tmp);
-          output[k] = ignore;
-          lazy.push({
-            k: k,
-            a: [input, parsed, tmp, $]
-          });
-        } else output[k] = $.call(output, k, tmp);
-      } else if (output[k] !== ignore) output[k] = $.call(output, k, value);
-    }
-    for (var _length = lazy.length, i = 0; i < _length; i++) {
-      var _lazy$i = lazy[i],
-        _k = _lazy$i.k,
-        a = _lazy$i.a;
-      output[_k] = $.call(output, _k, _revive.apply(null, a));
-    }
-    return output;
+  var resolver = function resolver(input, lazy, parsed, $) {
+    return function (output) {
+      for (var ke = keys(output), length = ke.length, y = 0; y < length; y++) {
+        var k = ke[y];
+        var value = output[k];
+        if (value instanceof Primitive) {
+          var tmp = input[value];
+          if (_typeof(tmp) === object && !parsed.has(tmp)) {
+            parsed.add(tmp);
+            output[k] = ignore;
+            lazy.push({
+              o: output,
+              k: k,
+              r: tmp
+            });
+          } else output[k] = $.call(output, k, tmp);
+        } else if (output[k] !== ignore) output[k] = $.call(output, k, value);
+      }
+      return output;
+    };
   };
   var set = function set(known, input, value) {
     var index = Primitive(input.push(value) - 1);
@@ -71,12 +67,25 @@ self.Flatted = (function (exports) {
    */
   var parse = function parse(text, reviver) {
     var input = $parse(text, Primitives).map(primitives);
-    var value = input[0];
     var $ = reviver || noop;
-    var tmp = _typeof(value) === object && value ? _revive(input, new Set(), value, $) : value;
+    var value = input[0];
+    if (_typeof(value) === object && value) {
+      var lazy = [];
+      var revive = resolver(input, lazy, new Set(), $);
+      value = revive(value);
+      var i = 0;
+      while (i < lazy.length) {
+        // it could be a lazy.shift() but that's costly
+        var _lazy$i = lazy[i++],
+          o = _lazy$i.o,
+          k = _lazy$i.k,
+          r = _lazy$i.r;
+        o[k] = $.call(o, k, revive(r));
+      }
+    }
     return $.call({
-      '': tmp
-    }, '', tmp);
+      '': value
+    }, '', value);
   };
 
   /**

@@ -1 +1 @@
-self.Flatted=function(n){"use strict";function t(n){return t="function"==typeof Symbol&&"symbol"==typeof Symbol.iterator?function(n){return typeof n}:function(n){return n&&"function"==typeof Symbol&&n.constructor===Symbol&&n!==Symbol.prototype?"symbol":typeof n},t(n)}var r=JSON.parse,e=JSON.stringify,o=Object.keys,u=String,f="string",i={},c="object",a=function(n,t){return t},l=function(n){return n instanceof u?u(n):n},s=function(n,r){return t(r)===f?new u(r):r},y=function(n,r,e,f){for(var a=[],l=o(e),s=l.length,p=0;p<s;p++){var v=l[p],S=e[v];if(S instanceof u){var b=n[S];t(b)!==c||r.has(b)?e[v]=f.call(e,v,b):(r.add(b),e[v]=i,a.push({k:v,a:[n,r,b,f]}))}else e[v]!==i&&(e[v]=f.call(e,v,S))}for(var m=a.length,g=0;g<m;g++){var h=a[g],O=h.k,d=h.a;e[O]=f.call(e,O,y.apply(null,d))}return e},p=function(n,t,r){var e=u(t.push(r)-1);return n.set(r,e),e},v=function(n,e){var o=r(n,s).map(l),u=o[0],f=e||a,i=t(u)===c&&u?y(o,new Set,u,f):u;return f.call({"":i},"",i)},S=function(n,r,o){for(var u=r&&t(r)===c?function(n,t){return""===n||-1<r.indexOf(n)?t:void 0}:r||a,i=new Map,l=[],s=[],y=+p(i,l,u.call({"":n},"",n)),v=!y;y<l.length;)v=!0,s[y]=e(l[y++],S,o);return"["+s.join(",")+"]";function S(n,r){if(v)return v=!v,r;var e=u.call(this,n,r);switch(t(e)){case c:if(null===e)return e;case f:return i.get(e)||p(i,l,e)}return e}};return n.fromJSON=function(n){return v(e(n))},n.parse=v,n.stringify=S,n.toJSON=function(n){return r(S(n))},n}({});
\ No newline at end of file
+self.Flatted=function(n){"use strict";function t(n){return t="function"==typeof Symbol&&"symbol"==typeof Symbol.iterator?function(n){return typeof n}:function(n){return n&&"function"==typeof Symbol&&n.constructor===Symbol&&n!==Symbol.prototype?"symbol":typeof n},t(n)}var r=JSON.parse,e=JSON.stringify,o=Object.keys,u=String,f="string",i={},c="object",a=function(n,t){return t},l=function(n){return n instanceof u?u(n):n},s=function(n,r){return t(r)===f?new u(r):r},y=function(n,t,r){var e=u(t.push(r)-1);return n.set(r,e),e},p=function(n,e){var f=r(n,s).map(l),y=e||a,p=f[0];if(t(p)===c&&p){var v=[],S=function(n,r,e,f){return function(a){for(var l=o(a),s=l.length,y=0;y<s;y++){var p=l[y],v=a[p];if(v instanceof u){var S=n[v];t(S)!==c||e.has(S)?a[p]=f.call(a,p,S):(e.add(S),a[p]=i,r.push({o:a,k:p,r:S}))}else a[p]!==i&&(a[p]=f.call(a,p,v))}return a}}(f,v,new Set,y);p=S(p);for(var b=0;b<v.length;){var m=v[b++],g=m.o,h=m.k,O=m.r;g[h]=y.call(g,h,S(O))}}return y.call({"":p},"",p)},v=function(n,r,o){for(var u=r&&t(r)===c?function(n,t){return""===n||-1<r.indexOf(n)?t:void 0}:r||a,i=new Map,l=[],s=[],p=+y(i,l,u.call({"":n},"",n)),v=!p;p<l.length;)v=!0,s[p]=e(l[p++],S,o);return"["+s.join(",")+"]";function S(n,r){if(v)return v=!v,r;var e=u.call(this,n,r);switch(t(e)){case c:if(null===e)return e;case f:return i.get(e)||y(i,l,e)}return e}};return n.fromJSON=function(n){return p(e(n))},n.parse=p,n.stringify=v,n.toJSON=function(n){return r(v(n))},n}({});
\ No newline at end of file

@@ -50,19 +50,19 @@
   },
   "homepage": "https://github.com/WebReflection/flatted#readme",
   "devDependencies": {
-    "@babel/core": "^7.27.1",
-    "@babel/preset-env": "^7.27.2",
-    "@rollup/plugin-babel": "^6.0.4",
-    "@rollup/plugin-terser": "^0.4.4",
+    "@babel/core": "^7.29.0",
+    "@babel/preset-env": "^7.29.0",
+    "@rollup/plugin-babel": "^7.0.0",
+    "@rollup/plugin-terser": "^1.0.0",
     "@ungap/structured-clone": "^1.3.0",
     "ascjs": "^6.0.3",
-    "c8": "^10.1.3",
+    "c8": "^11.0.0",
     "circular-json": "^0.5.9",
     "circular-json-es6": "^2.0.2",
     "jsan": "^3.1.14",
-    "rollup": "^4.41.1",
-    "terser": "^5.39.2",
-    "typescript": "^5.8.3"
+    "rollup": "^4.59.0",
+    "terser": "^5.46.0",
+    "typescript": "^5.9.3"
   },
   "module": "./esm/index.js",
   "type": "module",

@@ -16,15 +16,9 @@ Available also for **[Go](./golang/README.md)**.
 
 - - -
 
-## Announcement 📣
+## ℹ️ JSON only values
 
-There is a standard approach to recursion and more data-types than what JSON allows, and it's part of the [Structured Clone polyfill](https://github.com/ungap/structured-clone/#readme).
-
-Beside acting as a polyfill, its `@ungap/structured-clone/json` export provides both `stringify` and `parse`, and it's been tested for being faster than *flatted*, but its produced output is also smaller than *flatted* in general.
-
-The *@ungap/structured-clone* module is, in short, a drop in replacement for *flatted*, but it's not compatible with *flatted* specialized syntax.
-
-However, if recursion, as well as more data-types, are what you are after, or interesting for your projects/use cases, consider switching to this new module whenever you can 👍
+If you need anything more complex than values JSON understands, there is a standard approach to recursion and more data-types than what JSON allows, and it's part of the [Structured Clone polyfill](https://github.com/ungap/structured-clone/#readme).
 
 - - -
 

@@ -0,0 +1,22 @@
+const { parse, stringify } = require('../cjs');
+
+const AMOUNT = 5500;
+
+// Build a chain of 5500 linked objects
+let chain = ["leaf"];
+for (let i = 0; i < AMOUNT; i++) {
+  chain = [chain];
+}
+
+const str = stringify(chain);
+console.log('stringify', '✅');
+// console.log(str);
+
+const parsed = parse(str);
+
+let current = parsed;
+for (let i = 0; i < AMOUNT; i++) {
+  current = current[0];
+}
+console.log(current);
+console.log('parse', '✅');