The recursive CTE: trail (relationship-unique, for Cypher) or shortest-path. */
| 7691 | |
| 7692 | /* The recursive CTE: trail (relationship-unique, for Cypher) or shortest-path. */ |
| 7693 | static int bfs_visit_sql(cbm_store_t *s, const bfs_query_t *q, bfs_rows_t *rows, int *cte_rows, |
| 7694 | int *cte_row_limit) { |
| 7695 | char sql[CBM_SZ_4K]; |
| 7696 | const char *join_cond = q->inbound ? "e.target_id = bfs.node_id" : "e.source_id = bfs.node_id"; |
| 7697 | const char *next_id = q->inbound ? "e.source_id" : "e.target_id"; |
| 7698 | if (q->trail) { |
| 7699 | *cte_row_limit = bfs_cte_row_limit_for_depth(q->max_results, q->max_depth); |
| 7700 | snprintf(sql, sizeof(sql), |
| 7701 | "WITH RECURSIVE bfs(node_id, hop, edge_path) AS (" |
| 7702 | " SELECT %lld, 0, ''" |
| 7703 | " UNION" |
| 7704 | " SELECT %s, bfs.hop + 1," |
| 7705 | " CASE WHEN bfs.edge_path = '' THEN CAST(e.id AS TEXT)" |
| 7706 | " ELSE bfs.edge_path || ',' || e.id END" |
| 7707 | " FROM bfs" |
| 7708 | " JOIN edges e ON %s" |
| 7709 | " WHERE e.type IN (%s) AND bfs.hop < %d" |
| 7710 | " AND instr(',' || bfs.edge_path || ',', ',' || e.id || ',') = 0" |
| 7711 | /* SQLite's recursive queue is breadth-first by default. A |
| 7712 | * bounded trail budget must reach the requested depth before |
| 7713 | * a wide shallow layer consumes every row, so prioritize the |
| 7714 | * recursive hop (depth-first) while retaining deterministic |
| 7715 | * ordering in the outer result query. */ |
| 7716 | " ORDER BY 2 DESC, 1 ASC, 3 ASC" |
| 7717 | " LIMIT %d" |
| 7718 | ")" |
| 7719 | "SELECT DISTINCT n.id, n.project, n.label, n.name, n.qualified_name, " |
| 7720 | "n.file_path, n.start_line, n.end_line, n.properties, bfs.hop, " |
| 7721 | "(SELECT count(*) FROM bfs) " |
| 7722 | "FROM bfs JOIN nodes n ON n.id = bfs.node_id " |
| 7723 | "WHERE bfs.hop > 0 ORDER BY bfs.hop, n.id LIMIT %d;", |
| 7724 | (long long)q->start_id, next_id, join_cond, q->types_clause, q->max_depth, |
| 7725 | *cte_row_limit + SKIP_ONE, q->probe_limit); |
| 7726 | } else { |
| 7727 | snprintf(sql, sizeof(sql), |
| 7728 | /* SHORTEST-PATH semantics: the UNION dedupes (node, hop) pairs. |
| 7729 | * MIN(hop) GROUP BY node returns each node once at its minimal |
| 7730 | * distance, while relationship-trail state remains scoped to |
| 7731 | * Cypher variable-length expansion. */ |
| 7732 | "WITH RECURSIVE bfs(node_id, hop) AS (" |
| 7733 | " SELECT %lld, 0" |
| 7734 | " UNION" |
| 7735 | " SELECT %s, bfs.hop + 1" |
| 7736 | " FROM bfs" |
| 7737 | " JOIN edges e ON %s" |
| 7738 | " WHERE e.type IN (%s) AND bfs.hop < %d" |
| 7739 | ")" |
| 7740 | "SELECT n.id, n.project, n.label, n.name, n.qualified_name, " |
| 7741 | "n.file_path, n.start_line, n.end_line, n.properties, MIN(bfs.hop) AS hop " |
| 7742 | "FROM bfs " |
| 7743 | "JOIN nodes n ON n.id = bfs.node_id " |
| 7744 | "WHERE bfs.hop > 0 " |
| 7745 | "GROUP BY n.id " |
| 7746 | "ORDER BY hop, n.id " |
| 7747 | "LIMIT %d;", |
| 7748 | (long long)q->start_id, next_id, join_cond, q->types_clause, q->max_depth, |
| 7749 | q->probe_limit); |
| 7750 | } |
no test coverage detected