Graph Utilities

/**
 * Creates a test model for model-based testing of state machines
 * @param logic - Actor logic (typically a state machine) to create test model from
 * @param options - Optional configuration for test model behavior
 * @returns TestModel instance with path generation and testing capabilities
 */
function createTestModel<TLogic extends AnyActorLogic>(
  logic: TLogic,
  options?: TestModelOptions
): TestModel<TLogic>;

class TestModel<TLogic extends AnyActorLogic> {
  /** Actor logic being tested */
  readonly logic: TLogic;
  /** Test model options */
  readonly options: TestModelOptions;

  /**
   * Generate paths using a specified path generator
   * @param pathGenerator - Function that generates paths from the logic
   * @param options - Optional traversal configuration
   * @returns Array of test paths
   */
  getPaths(
    pathGenerator: PathGenerator<TLogic>,
    options?: TraversalOptions
  ): TestPath[];

  /**
   * Get shortest paths to all reachable states
   * @param options - Optional traversal configuration  
   * @returns Array of shortest paths to each state
   */
  getShortestPaths(options?: TraversalOptions): TestPath[];

  /**
   * Get shortest paths from specified starting paths
   * @param paths - Starting paths to extend
   * @param options - Optional traversal configuration
   * @returns Extended shortest paths
   */
  getShortestPathsFrom(paths: TestPath[], options?: TraversalOptions): TestPath[];

  /**
   * Get simple paths (without cycles) to all reachable states
   * @param options - Optional traversal configuration
   * @returns Array of simple paths to each state
   */
  getSimplePaths(options?: TraversalOptions): TestPath[];

  /**
   * Get simple paths from specified starting paths
   * @param paths - Starting paths to extend
   * @param options - Optional traversal configuration
   * @returns Extended simple paths
   */
  getSimplePathsFrom(paths: TestPath[], options?: TraversalOptions): TestPath[];

  /**
   * Generate paths from a sequence of events
   * @param events - Array of events to process
   * @param options - Optional traversal configuration
   * @returns Generated paths from event sequence
   */
  getPathsFromEvents(events: EventFromLogic<TLogic>[], options?: TraversalOptions): TestPath[];

  /**
   * Get adjacency map representation of the state machine
   * @returns Adjacency map showing all state transitions
   */
  getAdjacencyMap(): AdjacencyMap;

  /**
   * Execute and test a specific path
   * @param path - Path to test
   * @param params - Test parameters with executors
   * @param options - Optional test configuration
   */
  testPath(path: TestPath, params: TestParam, options?: TestOptions): void;

  /**
   * Test a specific state
   * @param params - Test parameters
   * @param state - State to test
   * @param options - Optional test configuration
   */
  testState(params: TestParam, state: any, options?: TestOptions): void;

  /**
   * Test a specific transition step
   * @param params - Test parameters
   * @param step - Transition step to test
   */
  testTransition(params: TestParam, step: Step): void;
}

interface TestModelOptions {
  /** Custom state serializer */
  serializeState?: (state: any) => string;
  /** Custom event serializer */
  serializeEvent?: (event: any) => string;
  /** Maximum number of events to process */
  events?: { [eventType: string]: Array<{ type: string; [key: string]: any }> };
}

import { createTestModel } from "xstate/graph";

// Create test model from machine
const testModel = createTestModel(toggleMachine);

// Generate shortest paths to all states
const paths = testModel.getShortestPaths();

// Test each path
paths.forEach(path => {
  testModel.testPath(path, {
    states: {
      // Test state assertions
      inactive: (state) => {
        expect(state.value).toBe("inactive");
        expect(state.context.count).toBeGreaterThanOrEqual(0);
      },
      active: (state) => {
        expect(state.value).toBe("active");
      }
    },
    events: {
      // Test event execution
      TOGGLE: () => {
        // Simulate user clicking toggle button
        fireEvent.click(toggleButton);
      }
    }
  });
});

/**
 * Generates shortest paths to all reachable states using Dijkstra's algorithm
 * @param logic - Actor logic to analyze
 * @param options - Optional traversal configuration
 * @returns Array of shortest paths to each reachable state
 */
function getShortestPaths<TLogic extends AnyActorLogic>(
  logic: TLogic,
  options?: TraversalOptions
): StatePath[];

/**
 * Generates simple paths (without cycles) to all reachable states
 * @param logic - Actor logic to analyze 
 * @param options - Optional traversal configuration
 * @returns Array of simple paths to each reachable state
 */
function getSimplePaths<TLogic extends AnyActorLogic>(
  logic: TLogic,
  options?: TraversalOptions
): StatePath[];

/**
 * Generates paths by executing a sequence of events
 * @param logic - Actor logic to execute events on
 * @param events - Array of events to process in sequence
 * @param options - Optional traversal configuration
 * @returns Generated state paths from event sequence
 */
function getPathsFromEvents<TLogic extends AnyActorLogic>(
  logic: TLogic,
  events: EventFromLogic<TLogic>[],
  options?: TraversalOptions
): StatePath[];

/**
 * Creates a path generator that produces shortest paths
 * @returns PathGenerator function for shortest paths
 */
function createShortestPathsGen<TLogic extends AnyActorLogic>(): PathGenerator<TLogic>;

/**
 * Creates a path generator that produces simple paths (no cycles)
 * @returns PathGenerator function for simple paths  
 */
function createSimplePathsGen<TLogic extends AnyActorLogic>(): PathGenerator<TLogic>;

type PathGenerator<TLogic extends AnyActorLogic> = (
  logic: TLogic,
  options?: TraversalOptions
) => StatePath[];

/**
 * Converts a state machine or state node to a directed graph representation
 * @param stateMachine - State machine or state node to convert
 * @returns Directed graph representation with nodes and edges
 */
function toDirectedGraph(stateMachine: AnyStateMachine | AnyStateNode): DirectedGraph;

/**
 * Gets all state nodes recursively from a state machine or state node
 * @param stateNode - State machine or state node to traverse
 * @returns Array of all state nodes in the hierarchy
 */
function getStateNodes(stateNode: AnyStateMachine | AnyStateNode): AnyStateNode[];

/**
 * Creates an adjacency map representation of state transitions
 * @param logic - Actor logic to analyze
 * @param options - Optional traversal configuration
 * @returns Adjacency map showing all possible transitions
 */
function getAdjacencyMap<TLogic extends AnyActorLogic>(
  logic: TLogic,
  options?: TraversalOptions
): AdjacencyMap;

/**
 * Converts an adjacency map to an array of state-event-nextState tuples
 * @param adjMap - Adjacency map to convert
 * @returns Array of transition tuples
 */
function adjacencyMapToArray(adjMap: AdjacencyMap): Array<{
  state: SerializedSnapshot;
  event: SerializedEvent;
  nextState: SerializedSnapshot;
}>;

/**
 * Joins two state paths together, combining their steps
 * @param headPath - First path (beginning portion)
 * @param tailPath - Second path (ending portion)  
 * @returns Combined path with steps from both input paths
 */
function joinPaths(headPath: StatePath, tailPath: StatePath): StatePath;

/**
 * Serializes a snapshot to a string representation
 * @param snapshot - Snapshot to serialize
 * @returns String representation containing value and context
 */
function serializeSnapshot(snapshot: AnyMachineSnapshot): SerializedSnapshot;

interface StatePath {
  /** Final state reached by this path */
  state: any;
  /** Array of steps taken to reach the final state */
  steps: Step[];
  /** Total weight/cost of the path */
  weight: number;
}

interface Step {
  /** Event that triggered this step */
  event: EventObject;
  /** Resulting state after processing the event */
  state: any;
}

interface TestPath extends StatePath {
  /** Human-readable description of the path */
  description: string;
  /** Test-specific metadata */
  test?: (state: any) => void;
}

interface TestParam {
  /** State testing functions */
  states?: {
    [stateKey: string]: (state: any, step?: Step) => void;
  };
  /** Event execution functions */
  events?: {
    [eventType: string]: (step: Step) => void | Promise<void>;
  };
}

interface TestOptions {
  /** Timeout for test execution */
  timeout?: number;
  /** Skip specific states */
  skip?: string[];
  /** Only test specific states */
  only?: string[];
}

interface DirectedGraph {
  /** Graph identifier */
  id: string;
  /** Root nodes of the graph */
  children: DirectedGraphNode[];
  /** All edges in the graph */
  edges: DirectedGraphEdge[];
}

interface DirectedGraphNode {
  /** Node identifier */
  id: string;
  /** Node type */
  type: string;
  /** Child nodes */
  children: DirectedGraphNode[];
  /** Outgoing edges */
  edges: DirectedGraphEdge[];
  /** Node metadata */
  data?: any;
}

interface DirectedGraphEdge {
  /** Source node ID */
  source: string;
  /** Target node ID */
  target: string;
  /** Edge label (typically event type) */
  label: string;
  /** Transition data */
  data?: any;
}

interface AdjacencyMap {
  [serializedState: string]: AdjacencyValue;
}

interface AdjacencyValue {
  /** The state snapshot */
  state: any;
  /** Possible transitions from this state */
  transitions: {
    [eventType: string]: {
      /** Target state after transition */
      state: any;
      /** Transition event */
      event: EventObject;
      /** Actions executed during transition */
      actions: any[];
    };
  };
}

interface TraversalOptions {
  /** Custom state serializer function */
  serializeState?: (state: any) => string;
  /** Custom event serializer function */  
  serializeEvent?: (event: EventObject) => string;
  /** Maximum depth to traverse */
  depth?: number;
  /** Filter function for events */
  filter?: (state: any) => boolean;
  /** Maximum number of paths to generate */
  limit?: number;
  /** Events to explore at each state */
  events?: EventObject[];
}

type SerializedSnapshot = string & { _brand: "SerializedSnapshot" };
type SerializedEvent = string & { _brand: "SerializedEvent" };

import { createTestModel } from "xstate/graph";
import { render, fireEvent } from "@testing-library/react";

const testModel = createTestModel(formMachine);

describe("Form Machine Integration", () => {
  testModel.getShortestPaths().forEach(path => {
    it(`should handle path: ${path.description}`, async () => {
      const { getByRole, getByLabelText } = render(<FormComponent />);
      
      testModel.testPath(path, {
        states: {
          editing: (state) => {
            expect(getByRole("form")).toBeInTheDocument();
            expect(state.context.isEditing).toBe(true);
          },
          validating: (state) => {
            expect(getByRole("status")).toHaveTextContent("Validating...");
          },
          success: (state) => {
            expect(getByRole("status")).toHaveTextContent("Success!");
          }
        },
        events: {
          INPUT_CHANGE: (step) => {
            const input = getByLabelText("Email");
            fireEvent.change(input, { target: { value: step.event.value } });
          },
          SUBMIT: () => {
            fireEvent.click(getByRole("button", { name: "Submit" }));
          }
        }
      });
    });
  });
});

// Generate comprehensive test coverage
const testModel = createTestModel(complexMachine);

// Test all simple paths for full coverage
const simplePaths = testModel.getSimplePaths();
console.log(`Testing ${simplePaths.length} paths for full coverage`);

// Analyze adjacency for missing transitions
const adjacency = testModel.getAdjacencyMap();
const coverage = adjacencyMapToArray(adjacency);
console.log(`Found ${coverage.length} possible transitions`);

// Test path performance
const performanceModel = createTestModel(heavyMachine);

const shortestPaths = performanceModel.getShortestPaths({ 
  limit: 100,
  depth: 10 
});

shortestPaths.forEach(path => {
  const startTime = performance.now();
  performanceModel.testPath(path, testParams);
  const duration = performance.now() - startTime;
  
  if (duration > 1000) {
    console.warn(`Slow path detected: ${path.description} (${duration}ms)`);
  }
});