nip/tests/test_dependency_graph.nim

## Tests for Dependency Graph
##
## Tests the core graph operations: node/edge addition, cycle detection,
## and graph analysis functions.

import unittest
import tables
import sets
import options
import ../src/nip/resolver/dependency_graph
import ../src/nip/resolver/variant_types
import ../src/nip/manifest_parser

suite "Dependency Graph Tests":
  
  # Helper to create a dummy variant profile
  proc makeVariant(hash: string): VariantProfile =
    VariantProfile(
      domains: initTable[string, VariantDomain](),
      hash: hash
    )

  # Helper to create a dummy term
  proc makeTerm(name, ver, hash: string): PackageTerm =
    let id = createTermId(name, hash)
    PackageTerm(
      id: id,
      packageName: name,
      version: parseSemanticVersion(ver),
      variantHash: hash,
      variantProfile: makeVariant(hash),
      optional: false,
      source: "test"
    )

  test "Create empty graph":
    let graph = newDependencyGraph()
    check graph.nodeCount() == 0
    check graph.edgeCount() == 0
    check graph.getRoots().len == 0
    check graph.getLeaves().len == 0
  
  test "Add single node":
    var graph = newDependencyGraph()
    let term = makeTerm("nginx", "1.24.0", "abc123")
    graph.addTerm(term)
    
    check graph.nodeCount() == 1
    check graph.edgeCount() == 0
    check graph.getRoots().len == 1
    check graph.getLeaves().len == 1
  
  test "Add multiple nodes":
    var graph = newDependencyGraph()
    let nginx = makeTerm("nginx", "1.24.0", "abc123")
    let openssl = makeTerm("openssl", "3.0.0", "def456")
    let zlib = makeTerm("zlib", "1.2.13", "ghi789")
    
    graph.addTerm(nginx)
    graph.addTerm(openssl)
    graph.addTerm(zlib)
    
    check graph.nodeCount() == 3
    check graph.getRoots().len == 3
  
  test "Add edge between nodes":
    var graph = newDependencyGraph()
    let nginx = makeTerm("nginx", "1.24.0", "abc123")
    let openssl = makeTerm("openssl", "3.0.0", "def456")
    
    graph.addTerm(nginx)
    graph.addTerm(openssl)
    
    # Use explicit edge construction
    graph.addEdge(DependencyEdge(
      fromTerm: nginx.id,
      toTerm: openssl.id,
      dependencyType: Required
    ))
    
    check graph.nodeCount() == 2
    check graph.edgeCount() == 1
    check graph.getRoots().len == 1  # nginx is root
    check graph.getLeaves().len == 1  # openssl is leaf
    
    # Verify edge properties
    let edges = graph.getOutgoingEdges(nginx.id)
    check edges.len == 1
    check edges[0].fromTerm == nginx.id
    check edges[0].toTerm == openssl.id
  
  test "Get incoming edges":
    var graph = newDependencyGraph()
    let nginx = makeTerm("nginx", "1.24.0", "abc123")
    let openssl = makeTerm("openssl", "3.0.0", "def456")
    
    graph.addTerm(nginx)
    graph.addTerm(openssl)
    graph.addEdge(DependencyEdge(fromTerm: nginx.id, toTerm: openssl.id, dependencyType: Required))
    
    let incoming = graph.getIncomingEdges(openssl.id)
    check incoming.len == 1
    check incoming[0].fromTerm == nginx.id
    check incoming[0].toTerm == openssl.id
  
  test "Get outgoing edges":
    var graph = newDependencyGraph()
    let nginx = makeTerm("nginx", "1.24.0", "abc123")
    let openssl = makeTerm("openssl", "3.0.0", "def456")
    
    graph.addTerm(nginx)
    graph.addTerm(openssl)
    graph.addEdge(DependencyEdge(fromTerm: nginx.id, toTerm: openssl.id, dependencyType: Required))
    
    let outgoing = graph.getOutgoingEdges(nginx.id)
    check outgoing.len == 1
    check outgoing[0].fromTerm == nginx.id
    check outgoing[0].toTerm == openssl.id
  
  test "Get dependencies":
    var graph = newDependencyGraph()
    let nginx = makeTerm("nginx", "1.24.0", "abc123")
    let openssl = makeTerm("openssl", "3.0.0", "def456")
    let zlib = makeTerm("zlib", "1.2.13", "ghi789")
    
    graph.addTerm(nginx)
    graph.addTerm(openssl)
    graph.addTerm(zlib)
    
    graph.addEdge(DependencyEdge(fromTerm: nginx.id, toTerm: openssl.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: nginx.id, toTerm: zlib.id, dependencyType: Required))
    
    let deps = graph.getDependencies(nginx.id)
    check deps.len == 2
    check openssl in deps
    check zlib in deps
  
  test "Get dependents":
    var graph = newDependencyGraph()
    let nginx = makeTerm("nginx", "1.24.0", "abc123")
    let openssl = makeTerm("openssl", "3.0.0", "def456")
    let curl = makeTerm("curl", "8.0.0", "jkl012")
    
    graph.addTerm(nginx)
    graph.addTerm(openssl)
    graph.addTerm(curl)
    
    graph.addEdge(DependencyEdge(fromTerm: nginx.id, toTerm: openssl.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: curl.id, toTerm: openssl.id, dependencyType: Required))
    
    let dependents = graph.getDependents(openssl.id)
    check dependents.len == 2
    check nginx in dependents
    check curl in dependents
  
  test "Detect no cycle in simple chain":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    let c = makeTerm("c", "1.0.0", "c")
    
    graph.addTerm(a)
    graph.addTerm(b)
    graph.addTerm(c)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: b.id, toTerm: c.id, dependencyType: Required))
    
    check graph.hasCycle() == false
  
  test "Detect cycle in simple loop":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    
    graph.addTerm(a)
    graph.addTerm(b)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: b.id, toTerm: a.id, dependencyType: Required))
    
    check graph.hasCycle() == true
  
  test "Detect cycle in self-loop":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    
    graph.addTerm(a)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: a.id, dependencyType: Required))
    
    check graph.hasCycle() == true
  
  test "Detect cycle in complex graph":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    let c = makeTerm("c", "1.0.0", "c")
    let d = makeTerm("d", "1.0.0", "d")
    
    graph.addTerm(a)
    graph.addTerm(b)
    graph.addTerm(c)
    graph.addTerm(d)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: b.id, toTerm: c.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: c.id, toTerm: d.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: d.id, toTerm: b.id, dependencyType: Required))  # Creates cycle: b -> c -> d -> b
    
    check graph.hasCycle() == true
  
  test "Find cycle path":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    
    graph.addTerm(a)
    graph.addTerm(b)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: b.id, toTerm: a.id, dependencyType: Required))
    
    let cycle = graph.findCycle()
    check cycle.len >= 2
    # Check if terms are in cycle (by checking if any term in cycle has same ID)
    var foundA = false
    var foundB = false
    for term in cycle:
      if term.id == a.id: foundA = true
      if term.id == b.id: foundB = true
    
    check foundA
    check foundB
  
  test "Get roots":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    let c = makeTerm("c", "1.0.0", "c")
    
    graph.addTerm(a)
    graph.addTerm(b)
    graph.addTerm(c)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: c.id, dependencyType: Required))
    
    let roots = graph.getRoots()
    check roots.len == 1
    check roots[0].id == a.id
  
  test "Get leaves":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    let c = makeTerm("c", "1.0.0", "c")
    
    graph.addTerm(a)
    graph.addTerm(b)
    graph.addTerm(c)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: c.id, dependencyType: Required))
    
    let leaves = graph.getLeaves()
    check leaves.len == 2
    # Check IDs
    let leafIds = @[leaves[0].id, leaves[1].id]
    check b.id in leafIds
    check c.id in leafIds
  
  test "Get depth":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    let c = makeTerm("c", "1.0.0", "c")
    
    graph.addTerm(a)
    graph.addTerm(b)
    graph.addTerm(c)
    
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: b.id, toTerm: c.id, dependencyType: Required))
    
    check graph.getDepth(a.id) == 2
    check graph.getDepth(b.id) == 1
    check graph.getDepth(c.id) == 0
  
  test "Diamond dependency graph":
    var graph = newDependencyGraph()
    let a = makeTerm("a", "1.0.0", "a")
    let b = makeTerm("b", "1.0.0", "b")
    let c = makeTerm("c", "1.0.0", "c")
    let d = makeTerm("d", "1.0.0", "d")
    
    graph.addTerm(a)
    graph.addTerm(b)
    graph.addTerm(c)
    graph.addTerm(d)
    
    # Diamond: a -> b,c -> d
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: b.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: a.id, toTerm: c.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: b.id, toTerm: d.id, dependencyType: Required))
    graph.addEdge(DependencyEdge(fromTerm: c.id, toTerm: d.id, dependencyType: Required))
    
    check graph.nodeCount() == 4
    check graph.edgeCount() == 4
    check graph.hasCycle() == false
    check graph.getDependencies(a.id).len == 2
    check graph.getDependents(d.id).len == 2