/*! * Copyright (c) Microsoft Corporation and contributors. All rights reserved. * Licensed under the MIT License. */ import { strict as assert } from "node:assert"; import { type IGCResult, runGarbageCollection } from "../../gc/index.js"; interface IGCNode { id: string; outboundRoutes: string[]; } describe("Garbage Collector", () => { function runGCAndValidateResults( gcNodes: IGCNode[], startingIds: string[], deletedNodes: IGCNode[], ) { const referenceGraph: { [id: string]: string[] } = {}; for (const node of gcNodes) { referenceGraph[node.id] = node.outboundRoutes; } // Referenced nodes are all nodes in the gcNodes that are not in deletedNodes. const referencedNodes = gcNodes.filter((node) => !deletedNodes.includes(node)); const referencedNodeIds = Array.from(referencedNodes, (node: IGCNode) => node.id); const deletedNodeIds = Array.from(deletedNodes, (node: IGCNode) => node.id); const gcResult: IGCResult = runGarbageCollection(referenceGraph, startingIds); assert.deepStrictEqual( gcResult.referencedNodeIds.sort(), referencedNodeIds.sort(), "Referenced nodes generated by GC are incorrect", ); assert.deepStrictEqual( gcResult.deletedNodeIds.sort(), deletedNodeIds.sort(), "Deleted nodes generated by GC are incorrect", ); } it("should not collect nodes when all nodes are referenced", () => { const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] }; const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] }; const gcNode3: IGCNode = { id: "/ds2", outboundRoutes: [] }; const gcNode4: IGCNode = { id: "/ds1/dds1", outboundRoutes: ["/ds2"] }; const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4]; const deletedNodes = []; runGCAndValidateResults(gcNodes, ["/"], deletedNodes); }); it("should collect nodes that are not referenced", () => { const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] }; const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] }; const gcNode3: IGCNode = { id: "/ds1/dds1", outboundRoutes: [] }; // The following nodes are not referenced by any of the nodes above. const gcNode4: IGCNode = { id: "/ds2", outboundRoutes: ["/ds2/dds1"] }; const gcNode5: IGCNode = { id: "/ds2/dds1", outboundRoutes: [] }; const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4, gcNode5]; const deletedNodes = [gcNode4, gcNode5]; runGCAndValidateResults(gcNodes, ["/"], deletedNodes); }); it("should collect nodes with cycles in the graph", () => { const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] }; const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] }; const gcNode3: IGCNode = { id: "/ds2", outboundRoutes: ["/ds2/dds1"] }; const gcNode4: IGCNode = { id: "/ds1/dds1", outboundRoutes: ["/ds2", "/ds1"] }; const gcNode5: IGCNode = { id: "/ds2/dds1", outboundRoutes: ["/ds1", "/ds2"] }; // The following node is not referenced by any of the nodes above. const gcNode6: IGCNode = { id: "/ds3", outboundRoutes: [] }; const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4, gcNode5, gcNode6]; const deletedNodes = [gcNode6]; runGCAndValidateResults(gcNodes, ["/"], deletedNodes); }); it("should collect nodes with multiple starting ids", () => { const gcNode1: IGCNode = { id: "/", outboundRoutes: ["/ds1"] }; const gcNode2: IGCNode = { id: "/ds1", outboundRoutes: ["/ds1/dds1"] }; const gcNode3: IGCNode = { id: "/ds1/dds1", outboundRoutes: [] }; // The following node is not referenced by any of the nodes above. But its id will be given as starting id to // GC, so it will be referenced. const gcNode4: IGCNode = { id: "/ds2", outboundRoutes: ["/ds2/dds1"] }; const gcNode5: IGCNode = { id: "/ds2/dds1", outboundRoutes: [] }; // The following node is not referenced by any of the nodes above. const gcNode6: IGCNode = { id: "/ds3", outboundRoutes: [] }; const gcNodes = [gcNode1, gcNode2, gcNode3, gcNode4, gcNode5, gcNode6]; const deletedNodes = [gcNode6]; runGCAndValidateResults(gcNodes, ["/", "/ds2"], deletedNodes); }); });