Dependency Graph Utilities

/**
 * Represents a node in a dependency graph
 */
interface DependencyNode {
  name: string;
  dependencies: string[];
}

/**
 * Detects circular dependencies in a dependency graph using depth-first search.
 * Throws an error if a circular dependency is found.
 * @param dependencies - Array of nodes with their dependencies
 * @param errorPrefix - Prefix for the error message (e.g., "table calculations", "metrics")
 * @throws Error if a circular dependency is detected, with the full cycle path
 */
function detectCircularDependencies(
  dependencies: DependencyNode[],
  errorPrefix?: string
): void;

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

// Check for circular dependencies in table calculations
const tableCalculations: DependencyNode[] = [
  { name: 'profit', dependencies: ['revenue', 'cost'] },
  { name: 'margin', dependencies: ['profit', 'revenue'] },
  { name: 'revenue', dependencies: [] },
  { name: 'cost', dependencies: [] },
];

try {
  detectCircularDependencies(tableCalculations, 'table calculations');
  console.log('No circular dependencies found');
} catch (error) {
  console.error(error.message);
}

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

// Example with circular dependency
const circularDeps: DependencyNode[] = [
  { name: 'A', dependencies: ['B'] },
  { name: 'B', dependencies: ['C'] },
  { name: 'C', dependencies: ['A'] }, // Creates cycle: A -> B -> C -> A
];

try {
  detectCircularDependencies(circularDeps, 'metrics');
} catch (error) {
  console.error(error.message);
  // Error: "Circular dependency detected in metrics: A -> B -> C -> A"
}

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

// Use with custom metrics
const customMetrics: DependencyNode[] = metricQuery.additionalMetrics.map(metric => ({
  name: metric.name,
  dependencies: extractDependencies(metric.sql), // Extract field references
}));

detectCircularDependencies(customMetrics, 'custom metrics');

// Helper function to extract dependencies from SQL
function extractDependencies(sql: string): string[] {
  const regex = /\$\{([^}]+)\}/g;
  const matches = [];
  let match;

  while ((match = regex.exec(sql)) !== null) {
    matches.push(match[1]);
  }

  return matches;
}

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

function validateTableCalculations(calculations: TableCalculation[]): void {
  // Build dependency graph
  const dependencies: DependencyNode[] = calculations.map(calc => ({
    name: calc.name,
    dependencies: extractFieldReferences(calc.sql),
  }));

  // Check for circular dependencies
  try {
    detectCircularDependencies(dependencies, 'table calculations');
  } catch (error) {
    throw new Error(`Invalid table calculations: ${error.message}`);
  }
}

// Extract field references from SQL expression
function extractFieldReferences(sql: string): string[] {
  const references: string[] = [];
  const regex = /\$\{([^}]+)\}/g;
  let match;

  while ((match = regex.exec(sql)) !== null) {
    references.push(match[1]);
  }

  return references;
}

// Usage
const calculations: TableCalculation[] = [
  {
    name: 'total_revenue',
    sql: '${unit_price} * ${quantity}',
  },
  {
    name: 'profit',
    sql: '${total_revenue} - ${cost}',
  },
  {
    name: 'margin',
    sql: '${profit} / ${total_revenue}',
  },
];

validateTableCalculations(calculations); // No circular dependencies

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

function validateCustomDimensions(dimensions: CustomDimension[]): void {
  const dependencies: DependencyNode[] = dimensions.map(dim => ({
    name: dim.name,
    dependencies: extractDimensionDependencies(dim),
  }));

  detectCircularDependencies(dependencies, 'custom dimensions');
}

function extractDimensionDependencies(dimension: CustomDimension): string[] {
  if (dimension.type === 'sql') {
    return extractFieldReferences(dimension.sql);
  } else if (dimension.type === 'bin') {
    return [dimension.dimensionId];
  }
  return [];
}

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

// Validate metric query before execution
app.post('/api/queries', async (req, res) => {
  const { metricQuery } = req.body;

  try {
    // Validate custom metrics don't have circular dependencies
    if (metricQuery.additionalMetrics?.length > 0) {
      const dependencies: DependencyNode[] = metricQuery.additionalMetrics.map(
        (metric: AdditionalMetric) => ({
          name: metric.name,
          dependencies: extractFieldReferences(metric.sql),
        })
      );

      detectCircularDependencies(dependencies, 'custom metrics');
    }

    // Execute query
    const results = await executeMetricQuery(metricQuery);
    res.json(results);
  } catch (error) {
    res.status(400).json({ error: error.message });
  }
});

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

// Complex calculation dependencies
const complexCalculations: DependencyNode[] = [
  // Base metrics
  { name: 'revenue', dependencies: [] },
  { name: 'cost', dependencies: [] },
  { name: 'quantity', dependencies: [] },

  // Derived metrics
  { name: 'profit', dependencies: ['revenue', 'cost'] },
  { name: 'unit_profit', dependencies: ['profit', 'quantity'] },
  { name: 'margin_percent', dependencies: ['profit', 'revenue'] },

  // High-level metrics
  { name: 'roi', dependencies: ['profit', 'cost'] },
  { name: 'efficiency', dependencies: ['unit_profit', 'cost'] },
];

try {
  detectCircularDependencies(complexCalculations, 'business metrics');
  console.log('All metrics are valid - no circular dependencies');
} catch (error) {
  console.error('Invalid metric structure:', error.message);
}

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

async function saveMetricDefinition(metric: MetricDefinition) {
  // Get all existing metrics
  const existingMetrics = await getExistingMetrics();

  // Build dependency graph including new metric
  const allMetrics: DependencyNode[] = [
    ...existingMetrics.map(m => ({
      name: m.name,
      dependencies: extractFieldReferences(m.sql),
    })),
    {
      name: metric.name,
      dependencies: extractFieldReferences(metric.sql),
    },
  ];

  // Validate before saving
  try {
    detectCircularDependencies(allMetrics, 'metrics');
    await database.metrics.insert(metric);
    console.log(`Metric '${metric.name}' saved successfully`);
  } catch (error) {
    throw new Error(`Cannot save metric: ${error.message}`);
  }
}

import { detectCircularDependencies, type DependencyNode } from '@lightdash/common';

describe('Dependency graph validation', () => {
  it('should detect simple circular dependency', () => {
    const deps: DependencyNode[] = [
      { name: 'A', dependencies: ['B'] },
      { name: 'B', dependencies: ['A'] },
    ];

    expect(() => {
      detectCircularDependencies(deps);
    }).toThrow('Circular dependency detected');
  });

  it('should detect complex circular dependency', () => {
    const deps: DependencyNode[] = [
      { name: 'A', dependencies: ['B'] },
      { name: 'B', dependencies: ['C'] },
      { name: 'C', dependencies: ['D'] },
      { name: 'D', dependencies: ['B'] }, // Cycle: B -> C -> D -> B
    ];

    expect(() => {
      detectCircularDependencies(deps, 'metrics');
    }).toThrow('Circular dependency detected in metrics: B -> C -> D -> B');
  });

  it('should allow valid dependency graph', () => {
    const deps: DependencyNode[] = [
      { name: 'A', dependencies: ['B', 'C'] },
      { name: 'B', dependencies: ['D'] },
      { name: 'C', dependencies: ['D'] },
      { name: 'D', dependencies: [] },
    ];

    expect(() => {
      detectCircularDependencies(deps);
    }).not.toThrow();
  });
});

Circular dependency detected in table calculations: profit -> margin -> profit_margin -> profit