//
// Copyright 2023 DXOS.org
//

import * as Effect from 'effect/Effect';
import * as Fiber from 'effect/Fiber';
import * as Option from 'effect/Option';
import * as Atom from 'effect/reactivity/Atom';
import * as Registry from 'effect/reactivity/AtomRegistry';
import { assert, describe, expect, onTestFinished, test } from 'vitest';

import * as EffectEx from '@dxos/effect/EffectEx';
import * as GraphNode from '@dxos/graph/GraphNode';

import * as Graph from './AppGraph.ts';
import * as GraphBuilder from './AppGraphBuilder.ts';
import * as Node from './AppGraphNode.ts';

const exampleId = (id: number) => `dx:test:${id}`;
const EXAMPLE_ID = exampleId(1);
const EXAMPLE_TYPE = 'org.dxos.type.example';
const CHILD_RELATION_KEY = Graph.relationKey('child');
const CHILD_INBOUND_RELATION_KEY = Graph.relationKey(Graph.inverseRelation(Node.child));
const ACTIONS_RELATION_KEY = Graph.relationKey('action');
const ACTIONS_INBOUND_RELATION_KEY = Graph.relationKey(Graph.inverseRelation(Node.action));

describe('Graph', () => {
  test('getGraph', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    const root = registry.get(graph.node(GraphNode.RootId));
    assert.ok(Option.isSome(root));
    expect(root.value.id).toEqual(GraphNode.RootId);
    expect(root.value.type).toEqual(Node.RootType);
    expect(Graph.getGraph(root.value)).toEqual(graph);
  });

  test('add node', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
    const node = registry.get(graph.node(EXAMPLE_ID));
    assert.ok(Option.isSome(node));
    expect(node.value.id).toEqual(EXAMPLE_ID);
    expect(node.value.type).toEqual(EXAMPLE_TYPE);
    expect(node.value.data).toEqual(null);
    expect(node.value.properties).toEqual({});
  });

  test('add node curried', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    const result = Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
    expect(result).toEqual(graph);
    const node = registry.get(graph.node(EXAMPLE_ID));
    assert.ok(Option.isSome(node));
    expect(node.value.id).toEqual(EXAMPLE_ID);
    expect(node.value.type).toEqual(EXAMPLE_TYPE);
  });

  test('add nodes updates existing nodes', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    const nodeKey = graph.node(EXAMPLE_ID);

    let count = 0;
    const cancel = registry.subscribe(nodeKey, (_) => {
      count++;
    });
    onTestFinished(() => cancel());

    expect(registry.get(nodeKey)).toEqual(Option.none());
    expect(count).toEqual(1);

    expect(registry.get(nodeKey)).toEqual(Option.none());
    expect(count).toEqual(1);

    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
    const node = registry.get(nodeKey);
    assert.ok(Option.isSome(node));
    expect(node.value.id).toEqual(EXAMPLE_ID);
    expect(node.value.type).toEqual(EXAMPLE_TYPE);
    expect(node.value.data).toEqual(null);
    expect(node.value.properties).toEqual({});
    expect(count).toEqual(2);

    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
    expect(count).toEqual(2);
  });

  test('getNodeOrThrow throws NotFoundError for a missing node', () => {
    const graph = Graph.make({ registry: Registry.make() });
    expect(() => Graph.getNodeOrThrow(graph, EXAMPLE_ID)).toThrow(GraphNode.NotFoundError);
  });

  test('remove node', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });

    {
      const node = registry.get(graph.node(EXAMPLE_ID));
      expect(Option.isNone(node)).toEqual(true);
    }

    {
      Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
      const node = registry.get(graph.node(EXAMPLE_ID));
      expect(Option.isSome(node)).toEqual(true);
    }

    {
      Graph.removeNode(graph, EXAMPLE_ID);
      const node = registry.get(graph.node(EXAMPLE_ID));
      expect(Option.isNone(node)).toEqual(true);
    }
  });

  test('remove node with edges=true removes default inbound counterparts', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });

    Graph.removeNode(graph, exampleId(2), true);

    const sourceEdges = registry.get(graph.edges(exampleId(1)));
    expect(sourceEdges[CHILD_RELATION_KEY]).toEqual([]);
    expect(sourceEdges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
  });

  test('remove node with edges=true removes typed inbound and outbound counterparts', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(3), type: EXAMPLE_TYPE });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'action' });
    Graph.addEdge(graph, { source: exampleId(2), target: exampleId(3), relation: 'action' });

    Graph.removeNode(graph, exampleId(2), true);

    const sourceEdges = registry.get(graph.edges(exampleId(1)));
    const targetEdges = registry.get(graph.edges(exampleId(3)));
    expect(sourceEdges[ACTIONS_RELATION_KEY]).toEqual([]);
    expect(sourceEdges[ACTIONS_INBOUND_RELATION_KEY]).toBeUndefined();
    expect(targetEdges[ACTIONS_RELATION_KEY]).toBeUndefined();
    expect(targetEdges[ACTIONS_INBOUND_RELATION_KEY]).toEqual([]);
  });

  test('remove node curried', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
    const result = Graph.removeNode(graph, EXAMPLE_ID);
    expect(result).toEqual(graph);
    const node = registry.get(graph.node(EXAMPLE_ID));
    assert.ok(Option.isNone(node));
  });

  test('waitFor resolves immediately when the node is already present', async () => {
    const graph = Graph.make();
    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });

    const node = await EffectEx.runPromise(Graph.waitFor(graph, EXAMPLE_ID));
    expect(node.id).toEqual(EXAMPLE_ID);
  });

  test('waitFor resolves when the node arrives later', async () => {
    const graph = Graph.make();
    const pending = EffectEx.runPromise(Graph.waitFor(graph, EXAMPLE_ID));

    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });

    const node = await pending;
    expect(node.id).toEqual(EXAMPLE_ID);
  });

  test('waitFor ignores other nodes', async () => {
    const graph = Graph.make();
    const pending = EffectEx.runPromise(Graph.waitFor(graph, EXAMPLE_ID));

    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });

    expect((await pending).id).toEqual(EXAMPLE_ID);
  });

  test('waitFor stays pending while the node is absent', async () => {
    const graph = Graph.make();
    const settled = await EffectEx.runPromise(
      Graph.waitFor(graph, EXAMPLE_ID).pipe(
        Effect.map(() => 'settled' as const),
        Effect.timeoutOrElse({ duration: '50 millis', orElse: () => Effect.succeed('pending' as const) }),
      ),
    );
    expect(settled).toEqual('pending');
  });

  test('waitFor is interruptible and releases its subscription', async () => {
    const graph = Graph.make();
    const interrupted = await EffectEx.runPromise(
      Graph.waitFor(graph, EXAMPLE_ID).pipe(Effect.timeout('20 millis'), Effect.option),
    );
    expect(Option.isNone(interrupted)).toBe(true);

    // A later arrival must not reach the released listener (it would throw on a settled resume).
    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
    expect(Option.isSome(Graph.getNode(graph, EXAMPLE_ID))).toBe(true);
  });

  test('onNodeChanged', () => {
    const graph = Graph.make();

    let node: Option.Option<Node.Node> = Option.none();
    graph.onNodeChanged.on(({ node: newNode }) => {
      node = newNode;
    });

    Graph.addNode(graph, { id: EXAMPLE_ID, type: EXAMPLE_TYPE });
    assert.ok(Option.isSome(node));
    expect(node.value.id).toEqual(EXAMPLE_ID);
    expect(node.value.type).toEqual(EXAMPLE_TYPE);

    Graph.removeNode(graph, EXAMPLE_ID);
    expect(node.pipe(Option.getOrNull)).toEqual(null);
  });

  test('add edge', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });

    {
      const edges = registry.get(graph.edges(exampleId(1)));
      expect(edges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
      expect(edges[CHILD_RELATION_KEY]).toEqual([exampleId(2)]);
    }

    {
      const edges = registry.get(graph.edges(exampleId(2)));
      expect(edges[CHILD_INBOUND_RELATION_KEY]).toEqual([exampleId(1)]);
      expect(edges[CHILD_RELATION_KEY]).toBeUndefined();
    }
  });

  test('add edges is idempotent', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
    const edges = registry.get(graph.edges(exampleId(1)));
    expect(edges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
    expect(edges[CHILD_RELATION_KEY]).toEqual([exampleId(2)]);
  });

  test('sort edges', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });

    {
      Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
      Graph.addEdge(graph, { source: exampleId(1), target: exampleId(3), relation: 'child' });
      Graph.addEdge(graph, { source: exampleId(1), target: exampleId(4), relation: 'child' });
      const edges = registry.get(graph.edges(exampleId(1)));
      expect(edges[CHILD_RELATION_KEY]).toEqual([exampleId(2), exampleId(3), exampleId(4)]);
    }

    {
      Graph.sortEdges(graph, exampleId(1), 'child', [exampleId(3), exampleId(2)]);
      const edges = registry.get(graph.edges(exampleId(1)));
      expect(edges[CHILD_RELATION_KEY]).toEqual([exampleId(3), exampleId(2), exampleId(4)]);
    }
  });

  test('remove edge', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });

    {
      Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
      const edges = registry.get(graph.edges(exampleId(1)));
      expect(edges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
      expect(edges[CHILD_RELATION_KEY]).toEqual([exampleId(2)]);
    }

    {
      Graph.removeEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
      const edges = registry.get(graph.edges(exampleId(1)));
      expect(edges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
      expect(edges[CHILD_RELATION_KEY]).toEqual([]);
    }
  });

  test('remove edge curried', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
    const result = Graph.removeEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
    expect(result).toEqual(graph);
    const edges = registry.get(graph.edges(exampleId(1)));
    expect(edges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
    expect(edges[CHILD_RELATION_KEY]).toEqual([]);
  });

  test('add edge with custom relation creates typed inbound inverse', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'action' });
    const sourceEdges = registry.get(graph.edges(exampleId(1)));
    expect(sourceEdges[ACTIONS_RELATION_KEY]).toEqual([exampleId(2)]);
    expect(sourceEdges[CHILD_RELATION_KEY]).toBeUndefined();
    const targetEdges = registry.get(graph.edges(exampleId(2)));
    expect(targetEdges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
    expect(targetEdges[ACTIONS_INBOUND_RELATION_KEY]).toEqual([exampleId(1)]);
    const reverseConnections = registry.get(graph.connections(exampleId(2), Graph.inverseRelation(Node.action)));
    expect(reverseConnections.map(({ id }) => id)).toEqual([exampleId(1)]);
  });

  test('remove edge with custom relation removes typed inbound inverse', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'action' });
    Graph.removeEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'action' });
    const sourceEdges = registry.get(graph.edges(exampleId(1)));
    expect(sourceEdges[ACTIONS_RELATION_KEY]).toEqual([]);
    const targetEdges = registry.get(graph.edges(exampleId(2)));
    expect(targetEdges[CHILD_INBOUND_RELATION_KEY]).toBeUndefined();
    expect(targetEdges[CHILD_RELATION_KEY]).toBeUndefined();
    expect(targetEdges[ACTIONS_RELATION_KEY]).toBeUndefined();
    expect(targetEdges[ACTIONS_INBOUND_RELATION_KEY]).toEqual([]);
  });

  test('get connections', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
    const nodes = registry.get(graph.connections(exampleId(1), 'child'));
    expect(nodes).has.length(1);
    expect(nodes[0].id).toEqual(exampleId(2));
  });

  test('can subscribe to a node before it exists', async () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    const nodeKey = graph.node(exampleId(1));

    let node: Option.Option<Node.Node> = Option.none();
    const cancel = registry.subscribe(
      nodeKey,
      (n) => {
        node = n;
      },
      { immediate: true },
    );
    onTestFinished(() => cancel());

    expect(node).toEqual(Option.none());
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    assert.ok(Option.isSome(node));
    expect(node.value.id).toEqual(exampleId(1));
  });

  test('connections updates', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    assert.strictEqual(graph.connections(exampleId(1), 'child'), graph.connections(exampleId(1), 'child'));
    const childrenKey = graph.connections(exampleId(1), 'child');

    let count = 0;
    const cancel = registry.subscribe(childrenKey, (_) => {
      count++;
    });
    onTestFinished(() => cancel());

    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });

    expect(count).toEqual(0);
    const children = registry.get(childrenKey);
    expect(children).has.length(1);
    expect(children[0].id).toEqual(exampleId(2));
    expect(count).toEqual(1);

    // Updating an existing node fires an update.
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE, data: 'updated' });
    expect(count).toEqual(2);

    // Adding a node with no changes does not fire an update.
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE, data: 'updated' });
    expect(count).toEqual(2);

    // Adding an unconnected node does not fire an update.
    Graph.addNode(graph, { id: exampleId(3), type: EXAMPLE_TYPE });
    expect(count).toEqual(2);

    // Connecting a node fires an update.
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(3), relation: 'child' });
    expect(count).toEqual(3);

    // Adding an edge to a node that does not exist yet resolves to nothing, so connections are unchanged.
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(4), relation: 'child' });
    expect(count).toEqual(3);

    // Adding the node behind that edge fires an update.
    Graph.addNode(graph, { id: exampleId(4), type: EXAMPLE_TYPE });
    expect(count).toEqual(4);

    // Batching the edge and node updates fires a single update.
    Atom.batch(() => {
      Graph.addEdge(graph, { source: exampleId(1), target: exampleId(6), relation: 'child' });
      Graph.addNode(graph, { id: exampleId(6), type: EXAMPLE_TYPE });
    });
    expect(count).toEqual(5);
  });

  test('toJSON', () => {
    const graph = Graph.make();

    Graph.addNode(graph, {
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [
        { id: 'test1', type: 'test' },
        { id: 'test2', type: 'test' },
      ],
    });
    Graph.addEdge(graph, { source: 'test1', target: 'test2', relation: 'child' });

    const json = Graph.toJSON(graph);
    expect(json).to.deep.equal({
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [
        { id: 'test1', type: 'test', nodes: [{ id: 'test2', type: 'test' }] },
        { id: 'test2', type: 'test' },
      ],
    });
  });

  test('subscribe to json', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });

    Graph.addNode(graph, {
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [
        { id: 'test1', type: 'test' },
        { id: 'test2', type: 'test' },
      ],
    });
    Graph.addEdge(graph, { source: 'test1', target: 'test2', relation: 'child' });

    let json: any;
    const cancel = registry.subscribe(graph.json(), (_) => {
      json = _;
    });
    onTestFinished(() => cancel());

    registry.get(graph.json());
    expect(json).to.deep.equal({
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [
        { id: 'test1', type: 'test', nodes: [{ id: 'test2', type: 'test' }] },
        { id: 'test2', type: 'test' },
      ],
    });

    Graph.addNode(graph, { id: 'test3', type: 'test' });
    Graph.addEdge(graph, { source: 'root', target: 'test3', relation: 'child' });
    expect(json).to.deep.equal({
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [
        { id: 'test1', type: 'test', nodes: [{ id: 'test2', type: 'test' }] },
        { id: 'test2', type: 'test' },
        { id: 'test3', type: 'test' },
      ],
    });
  });

  test('json skips a node removed without its edges', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: GraphNode.RootId, type: Node.RootType, nodes: [{ id: 'test1', type: 'test' }] });
    const cancel = registry.subscribe(graph.json(), () => {});
    onTestFinished(() => cancel());

    Graph.removeNode(graph, 'test1');
    expect(registry.get(graph.json())).to.deep.equal({ id: GraphNode.RootId, type: Node.RootType });
  });

  test('get path', () => {
    const graph = Graph.make();
    Graph.addNode(graph, {
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [
        { id: exampleId(1), type: EXAMPLE_TYPE },
        { id: exampleId(2), type: EXAMPLE_TYPE },
      ],
    });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });

    expect(Graph.getPath(graph, { target: exampleId(2) }).pipe(Option.getOrNull)).to.deep.equal([
      'root',
      exampleId(1),
      exampleId(2),
    ]);
    expect(Graph.getPath(graph, { source: exampleId(1), target: exampleId(2) }).pipe(Option.getOrNull)).to.deep.equal([
      exampleId(1),
      exampleId(2),
    ]);
    expect(Graph.getPath(graph, { source: exampleId(2), target: exampleId(1) }).pipe(Option.getOrNull)).to.be.null;
  });

  test('get path curried', () => {
    const graph = Graph.make();
    Graph.addNode(graph, {
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [
        { id: exampleId(1), type: EXAMPLE_TYPE },
        { id: exampleId(2), type: EXAMPLE_TYPE },
      ],
    });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
    const path = Graph.getPath(graph, { target: exampleId(2) });
    expect(path.pipe(Option.getOrNull)).to.deep.equal(['root', exampleId(1), exampleId(2)]);
  });

  describe('traverse', () => {
    test('can be traversed', () => {
      const graph = Graph.make();
      Graph.addNode(graph, {
        id: GraphNode.RootId,
        type: Node.RootType,
        nodes: [
          { id: 'test1', type: 'test' },
          { id: 'test2', type: 'test' },
        ],
      });

      const nodes: string[] = [];
      Graph.traverse(graph, {
        relation: 'child',
        visitor: (node) => {
          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['root', 'test1', 'test2']);
    });

    test('traversal breaks cycles', () => {
      const graph = Graph.make();
      Graph.addNode(graph, {
        id: GraphNode.RootId,
        type: Node.RootType,
        nodes: [
          { id: 'test1', type: 'test' },
          { id: 'test2', type: 'test' },
        ],
      });
      Graph.addEdge(graph, { source: 'test1', target: 'root', relation: 'child' });

      const nodes: string[] = [];
      Graph.traverse(graph, {
        relation: 'child',
        visitor: (node) => {
          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['root', 'test1', 'test2']);
    });

    test('traversal can be started from any node', () => {
      const graph = Graph.make();
      Graph.addNode(graph, {
        id: GraphNode.RootId,
        type: Node.RootType,
        nodes: [
          {
            id: 'test1',
            type: 'test',
            nodes: [{ id: 'test2', type: 'test', nodes: [{ id: 'test3', type: 'test' }] }],
          },
        ],
      });

      const nodes: string[] = [];
      Graph.traverse(graph, {
        source: 'test2',
        relation: 'child',
        visitor: (node) => {
          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['test2', 'test3']);
    });

    test('traversal can follow inbound edges', () => {
      const graph = Graph.make();
      Graph.addNode(graph, {
        id: GraphNode.RootId,
        type: Node.RootType,
        nodes: [
          {
            id: 'test1',
            type: 'test',
            nodes: [{ id: 'test2', type: 'test', nodes: [{ id: 'test3', type: 'test' }] }],
          },
        ],
      });

      const nodes: string[] = [];
      Graph.traverse(graph, {
        source: 'test2',
        relation: Graph.inverseRelation(Node.child),
        visitor: (node) => {
          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['test2', 'test1', 'root']);
    });

    test('traversal can follow typed inbound edges', () => {
      const graph = Graph.make();
      Graph.addNode(graph, { id: 'host', type: 'test' });
      Graph.addNode(graph, { id: 'action', type: 'test' });
      Graph.addEdge(graph, { source: 'host', target: 'action', relation: 'action' });

      const nodes: string[] = [];
      Graph.traverse(graph, {
        source: 'action',
        relation: Graph.inverseRelation(Node.action),
        visitor: (node) => {
          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['action', 'host']);
    });

    test('traversal can be terminated early', () => {
      const graph = Graph.make();
      Graph.addNode(graph, {
        id: GraphNode.RootId,
        type: Node.RootType,
        nodes: [
          { id: 'test1', type: 'test' },
          { id: 'test2', type: 'test' },
        ],
      });

      const nodes: string[] = [];
      Graph.traverse(graph, {
        relation: 'child',
        visitor: (node) => {
          if (nodes.length === 2) {
            return false;
          }

          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['root', 'test1']);
    });

    test('traversal with multiple relations follows all edge types', () => {
      const graph = Graph.make();
      Graph.addNode(graph, {
        id: GraphNode.RootId,
        type: Node.RootType,
        nodes: [{ id: 'child1', type: 'test' }],
      });
      Graph.addNode(graph, { id: 'action1', type: Node.ActionType });
      Graph.addEdge(graph, { source: GraphNode.RootId, target: 'action1', relation: 'action' });

      const nodes: string[] = [];
      Graph.traverse(graph, {
        relation: ['child', 'action'],
        visitor: (node) => {
          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['root', 'child1', 'action1']);
    });

    test('traverse curried', () => {
      const graph = Graph.make();
      Graph.addNode(graph, {
        id: GraphNode.RootId,
        type: Node.RootType,
        nodes: [{ id: 'test1', type: 'test' }],
      });
      Graph.addNode(graph, { id: 'test2', type: 'test' });
      Graph.addEdge(graph, { source: 'test1', target: 'test2', relation: 'child' });
      const nodes: string[] = [];
      Graph.traverse(graph, {
        source: GraphNode.RootId,
        relation: 'child',
        visitor: (node, _path) => {
          nodes.push(node.id);
        },
      });
      expect(nodes).to.deep.equal(['root', 'test1', 'test2']);
    });
  });

  test('add nodes curried', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    const result = Graph.addNodes(graph, [
      { id: exampleId(1), type: EXAMPLE_TYPE },
      { id: exampleId(2), type: EXAMPLE_TYPE },
    ]);
    expect(result).toEqual(graph);
    const node1 = registry.get(graph.node(exampleId(1)));
    const node2 = registry.get(graph.node(exampleId(2)));
    assert.ok(Option.isSome(node1));
    assert.ok(Option.isSome(node2));
    expect(node1.value.id).toEqual(exampleId(1));
    expect(node2.value.id).toEqual(exampleId(2));
  });

  test('add edges curried', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(3), type: EXAMPLE_TYPE });
    const result = Graph.addEdges(graph, [
      { source: exampleId(1), target: exampleId(2), relation: 'child' },
      { source: exampleId(1), target: exampleId(3), relation: 'child' },
    ]);
    expect(result).toEqual(graph);
    const edges = registry.get(graph.edges(exampleId(1)));
    expect(edges[CHILD_RELATION_KEY]).to.have.length(2);
    expect(edges[CHILD_RELATION_KEY]).to.include(exampleId(2));
    expect(edges[CHILD_RELATION_KEY]).to.include(exampleId(3));
  });

  test('remove nodes curried', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    const result = Graph.removeNodes(graph, [exampleId(1), exampleId(2)]);
    expect(result).toEqual(graph);
    const node1 = registry.get(graph.node(exampleId(1)));
    const node2 = registry.get(graph.node(exampleId(2)));
    assert.ok(Option.isNone(node1));
    assert.ok(Option.isNone(node2));
  });

  test('remove edges curried', () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE });
    Graph.addNode(graph, { id: exampleId(3), type: EXAMPLE_TYPE });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(2), relation: 'child' });
    Graph.addEdge(graph, { source: exampleId(1), target: exampleId(3), relation: 'child' });
    const result = Graph.removeEdges(graph, [
      { source: exampleId(1), target: exampleId(2), relation: 'child' },
      { source: exampleId(1), target: exampleId(3), relation: 'child' },
    ]);
    expect(result).toEqual(graph);
    const edges = registry.get(graph.edges(exampleId(1)));
    expect(edges[CHILD_RELATION_KEY]).to.have.length(0);
  });

  test('expand curried', async () => {
    const registry = Registry.make();
    const builder = GraphBuilder.make({ registry });
    const graph = builder.graph;
    let expandCalled = false;
    GraphBuilder.addExtension(
      builder,
      GraphBuilder.createExtensionRaw({
        id: 'test',
        connector: () => {
          expandCalled = true;
          return Atom.make([]);
        },
      }),
    );
    await Graph.expandSync(graph, GraphNode.RootId, 'child');
    expect(expandCalled).to.be.true;
  });

  test('expand runs the expansion off the caller frame', async () => {
    const registry = Registry.make();
    const builder = GraphBuilder.make({ registry });
    const graph = builder.graph;
    let expandCalled = false;
    GraphBuilder.addExtension(
      builder,
      GraphBuilder.createExtensionRaw({
        id: 'test',
        connector: () => {
          expandCalled = true;
          return Atom.make([]);
        },
      }),
    );

    const effect = Graph.expand(graph, GraphNode.RootId, 'child');
    // Nothing runs while the effect is only described.
    expect(expandCalled).to.be.false;

    await EffectEx.runPromise(effect);
    expect(expandCalled).to.be.true;
  });

  test('interrupting a delayed expand cancels it', async () => {
    const registry = Registry.make();
    const builder = GraphBuilder.make({ registry });
    const graph = builder.graph;
    let expandCalled = false;
    GraphBuilder.addExtension(
      builder,
      GraphBuilder.createExtensionRaw({
        id: 'test',
        connector: () => {
          expandCalled = true;
          return Atom.make([]);
        },
      }),
    );

    // Mirrors the nav-tree's hover prefetch: a settle delay in front of the expansion, superseded by
    // interrupting the fiber.
    const fiber = Effect.runFork(
      Effect.sleep('1 second').pipe(Effect.andThen(Graph.expand(graph, GraphNode.RootId, 'child'))),
    );
    await EffectEx.runPromise(Fiber.interrupt(fiber));
    expect(expandCalled).to.be.false;

    // The graph is untouched, so a later expansion still runs.
    await EffectEx.runPromise(Graph.expand(graph, GraphNode.RootId, 'child'));
    expect(expandCalled).to.be.true;
  });

  test('expand defers for non-existent node and applies when node is added', () => {
    const registry = Registry.make();
    const expandCalls: [string, Node.Relation][] = [];
    const graph = Graph.make({
      registry,
      onExpand: (id, relation) => expandCalls.push([id, relation]),
    });
    const childId = 'child';
    expect(Option.isNone(registry.get(graph.node(childId)))).to.be.true;

    Graph.expandSync(graph, childId, 'child');
    expect(expandCalls).to.deep.equal([]);

    Graph.addNode(graph, { id: childId, type: EXAMPLE_TYPE });
    expect(expandCalls).to.deep.equal([[childId, Node.child]]);
  });
  test('waitForPath curried', async () => {
    const graph = Graph.make();
    Graph.addNode(graph, {
      id: GraphNode.RootId,
      type: Node.RootType,
      nodes: [{ id: exampleId(1), type: EXAMPLE_TYPE }],
    });
    const path = await Graph.waitForPath(graph, { target: exampleId(1) }, { timeout: 1000 });
    expect(path).to.deep.equal(['root', exampleId(1)]);
  });
});

describe('registry lifetime', () => {
  test('a graph pins its nodes only while retained', async () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNode(graph, { id: exampleId(1), type: EXAMPLE_TYPE, data: null, properties: {} });
    expect(registry.getNodes().has(graph.node(exampleId(1)))).toBe(false);

    const release = Graph.retain(graph);
    Graph.addNode(graph, { id: exampleId(2), type: EXAMPLE_TYPE, data: null, properties: {} });
    expect(registry.getNodes().has(graph.node(exampleId(1)))).toBe(true);
    expect(registry.getNodes().has(graph.node(exampleId(2)))).toBe(true);

    release();
    await new Promise((resolve) => setTimeout(resolve));
    expect(registry.getNodes().has(graph.node(exampleId(1)))).toBe(false);
    expect(registry.getNodes().has(graph.node(exampleId(2)))).toBe(false);
  });

  test('readers leave nothing in the registry once they unsubscribe', async () => {
    const registry = Registry.make();
    const graph = Graph.make({ registry });
    Graph.addNodes(graph, [
      { id: exampleId(1), type: EXAMPLE_TYPE, data: null, properties: {} },
      { id: exampleId(2), type: EXAMPLE_TYPE, data: null, properties: {} },
    ]);
    Graph.addEdges(graph, [{ source: GraphNode.RootId, target: exampleId(1), relation: 'child' }]);
    const before = registry.getNodes().size;
    const unsubscribe = registry.subscribe(graph.connections(GraphNode.RootId, 'child'), () => {});
    expect(registry.get(graph.connections(GraphNode.RootId, 'child')).map((node) => node.id)).toEqual([exampleId(1)]);

    unsubscribe();
    // The registry drops unobserved nodes on its scheduler, not synchronously.
    await new Promise((resolve) => setTimeout(resolve));
    expect(registry.getNodes().size).toBe(before);
  });
});