Skip to content

Commit 87d312a

Browse files
author
Hendrik van Antwerpen
committed
Add support for stitcher configuration
1 parent ed9ce87 commit 87d312a

29 files changed

Lines changed: 200 additions & 16 deletions

‎languages/tree-sitter-stack-graphs-java/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,5 +36,6 @@ harness = false # need to provide own main function to handle running tests
3636
[dependencies]
3737
anyhow = "1.0"
3838
clap = { version = "4", features = ["derive"] }
39+
stack-graphs = { version = "0.12", path = "../../stack-graphs" }
3940
tree-sitter-stack-graphs = { version = "0.7", path = "../../tree-sitter-stack-graphs", features=["cli"] }
4041
tree-sitter-java = { version = "=0.20.0" }

‎languages/tree-sitter-stack-graphs-java/rust/lib.rs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
use tree_sitter_stack_graphs::loader::FileAnalyzers;
22
use tree_sitter_stack_graphs::loader::LanguageConfiguration;
33
use tree_sitter_stack_graphs::loader::LoadError;
4+
use tree_sitter_stack_graphs::loader::StitcherConfig;
45
use tree_sitter_stack_graphs::CancellationFlag;
56

67
/// The stacks graphs tsg path for this language.
@@ -40,6 +41,9 @@ pub fn try_language_configuration(
4041
)),
4142
Some(STACK_GRAPHS_BUILTINS_CONFIG),
4243
FileAnalyzers::new(),
44+
StitcherConfig {
45+
detect_similar_paths: true,
46+
},
4347
cancellation_flag,
4448
)
4549
}

‎languages/tree-sitter-stack-graphs-typescript/rust/lib.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
use tree_sitter_stack_graphs::loader::FileAnalyzers;
99
use tree_sitter_stack_graphs::loader::LanguageConfiguration;
1010
use tree_sitter_stack_graphs::loader::LoadError;
11+
use tree_sitter_stack_graphs::loader::StitcherConfig;
1112
use tree_sitter_stack_graphs::CancellationFlag;
1213

1314
use crate::npm_package::NpmPackageAnalyzer;
@@ -56,6 +57,7 @@ pub fn try_language_configuration(
5657
FileAnalyzers::new()
5758
.add("tsconfig.json".to_string(), TsConfigAnalyzer {})
5859
.add("package.json".to_string(), NpmPackageAnalyzer {}),
60+
StitcherConfig::default(),
5961
cancellation_flag,
6062
)
6163
}

‎stack-graphs/include/stack-graphs.h‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -437,6 +437,11 @@ struct sg_partial_path {
437437
struct sg_partial_path_edge_list edges;
438438
};
439439

440+
struct sg_stitcher_config {
441+
// Enables similar path detection during stiching.
442+
bool detect_similar_paths;
443+
};
444+
440445
// An array of all of the partial paths in a partial path database. Partial path handles are
441446
// indices into this array. There will never be a valid partial path at index 0; a handle with
442447
// the value 0 represents a missing partial path.
@@ -733,6 +738,7 @@ enum sg_result sg_partial_path_arena_find_partial_paths_in_file(const struct sg_
733738
struct sg_partial_path_arena *partials,
734739
sg_file_handle file,
735740
struct sg_partial_path_list *partial_path_list,
741+
struct sg_stitcher_config config,
736742
const size_t *cancellation_flag);
737743

738744
// Finds all complete paths reachable from a set of starting nodes, placing the result into the
@@ -748,6 +754,7 @@ enum sg_result sg_partial_path_arena_find_all_complete_paths(const struct sg_sta
748754
size_t starting_node_count,
749755
const sg_node_handle *starting_nodes,
750756
struct sg_partial_path_list *path_list,
757+
struct sg_stitcher_config config,
751758
const size_t *cancellation_flag);
752759

753760
// Returns a reference to the array of partial path data in this partial path database. The
@@ -805,14 +812,16 @@ struct sg_node_handle_set sg_partial_path_database_local_nodes(const struct sg_p
805812
struct sg_forward_partial_path_stitcher *sg_forward_partial_path_stitcher_from_nodes(const struct sg_stack_graph *graph,
806813
struct sg_partial_path_arena *partials,
807814
size_t count,
808-
const sg_node_handle *starting_nodes);
815+
const sg_node_handle *starting_nodes,
816+
struct sg_stitcher_config config);
809817

810818
// Creates a new forward partial path stitcher that is "seeded" with a set of initial partial
811819
// paths.
812820
struct sg_forward_partial_path_stitcher *sg_forward_partial_path_stitcher_from_partial_paths(const struct sg_stack_graph *graph,
813821
struct sg_partial_path_arena *partials,
814822
size_t count,
815-
const struct sg_partial_path *initial_partial_paths);
823+
const struct sg_partial_path *initial_partial_paths,
824+
struct sg_stitcher_config config);
816825

817826
// Sets whether similar path detection should be enabled during path stitching. Paths are similar
818827
// if start and end node, and pre- and postconditions are the same. The presence of similar paths

‎stack-graphs/src/assert.rs‎

Lines changed: 13 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ use crate::partial::PartialPaths;
2020
use crate::stitching::Database;
2121
use crate::stitching::DatabaseCandidates;
2222
use crate::stitching::ForwardPartialPathStitcher;
23+
use crate::stitching::StitcherConfig;
2324
use crate::CancellationError;
2425
use crate::CancellationFlag;
2526

@@ -149,12 +150,19 @@ impl Assertion {
149150
graph: &StackGraph,
150151
partials: &mut PartialPaths,
151152
db: &mut Database,
153+
stitcher_config: &StitcherConfig,
152154
cancellation_flag: &dyn CancellationFlag,
153155
) -> Result<(), AssertionError> {
154156
match self {
155-
Self::Defined { source, targets } => {
156-
self.run_defined(graph, partials, db, source, targets, cancellation_flag)
157-
}
157+
Self::Defined { source, targets } => self.run_defined(
158+
graph,
159+
partials,
160+
db,
161+
source,
162+
targets,
163+
stitcher_config,
164+
cancellation_flag,
165+
),
158166
Self::Defines { source, symbols } => self.run_defines(graph, source, symbols),
159167
Self::Refers { source, symbols } => self.run_refers(graph, source, symbols),
160168
}
@@ -167,6 +175,7 @@ impl Assertion {
167175
db: &mut Database,
168176
source: &AssertionSource,
169177
expected_targets: &Vec<AssertionTarget>,
178+
stitcher_config: &StitcherConfig,
170179
cancellation_flag: &dyn CancellationFlag,
171180
) -> Result<(), AssertionError> {
172181
let references = source.iter_references(graph).collect::<Vec<_>>();
@@ -182,6 +191,7 @@ impl Assertion {
182191
ForwardPartialPathStitcher::find_all_complete_partial_paths(
183192
&mut DatabaseCandidates::new(graph, partials, db),
184193
vec![*reference],
194+
stitcher_config,
185195
cancellation_flag,
186196
|_, _, p| {
187197
reference_paths.push(p.clone());

‎stack-graphs/src/c.rs‎

Lines changed: 27 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ use crate::stitching::Database;
3232
use crate::stitching::DatabaseCandidates;
3333
use crate::stitching::ForwardPartialPathStitcher;
3434
use crate::stitching::GraphEdgeCandidates;
35+
use crate::stitching::StitcherConfig;
3536
use crate::CancellationError;
3637
use crate::CancellationFlag;
3738

@@ -1173,6 +1174,7 @@ pub extern "C" fn sg_partial_path_arena_find_partial_paths_in_file(
11731174
partials: *mut sg_partial_path_arena,
11741175
file: sg_file_handle,
11751176
partial_path_list: *mut sg_partial_path_list,
1177+
config: sg_stitcher_config,
11761178
cancellation_flag: *const usize,
11771179
) -> sg_result {
11781180
let graph = unsafe { &(*graph).inner };
@@ -1185,6 +1187,7 @@ pub extern "C" fn sg_partial_path_arena_find_partial_paths_in_file(
11851187
graph,
11861188
partials,
11871189
file,
1190+
&config.into(),
11881191
&AtomicUsizeCancellationFlag(cancellation_flag),
11891192
|_graph, partials, path| {
11901193
let mut path = path.clone();
@@ -1210,6 +1213,7 @@ pub extern "C" fn sg_partial_path_arena_find_all_complete_paths(
12101213
starting_node_count: usize,
12111214
starting_nodes: *const sg_node_handle,
12121215
path_list: *mut sg_partial_path_list,
1216+
config: sg_stitcher_config,
12131217
cancellation_flag: *const usize,
12141218
) -> sg_result {
12151219
let graph = unsafe { &(*graph).inner };
@@ -1221,6 +1225,7 @@ pub extern "C" fn sg_partial_path_arena_find_all_complete_paths(
12211225
ForwardPartialPathStitcher::find_all_complete_partial_paths(
12221226
&mut GraphEdgeCandidates::new(graph, partials, None),
12231227
starting_nodes.iter().copied().map(sg_node_handle::into),
1228+
&config.into(),
12241229
&AtomicUsizeCancellationFlag(cancellation_flag),
12251230
|graph, _partials, path| {
12261231
if path.is_complete(graph) {
@@ -1391,6 +1396,19 @@ pub struct sg_forward_partial_path_stitcher {
13911396
pub is_complete: bool,
13921397
}
13931398

1399+
// Configuration for partial path stitchers.
1400+
#[repr(C)]
1401+
pub struct sg_stitcher_config {
1402+
/// Enables similar path detection during stiching.
1403+
pub detect_similar_paths: bool,
1404+
}
1405+
1406+
impl Into<StitcherConfig> for sg_stitcher_config {
1407+
fn into(self) -> StitcherConfig {
1408+
unsafe { std::mem::transmute(self) }
1409+
}
1410+
}
1411+
13941412
// This is the Rust equivalent of a common C trick, where you have two versions of a struct — a
13951413
// publicly visible one and a private one containing internal implementation details. In our case,
13961414
// `sg_forward_partial_path_stitcher` is the public struct, and
@@ -1443,6 +1461,7 @@ pub extern "C" fn sg_forward_partial_path_stitcher_from_nodes(
14431461
partials: *mut sg_partial_path_arena,
14441462
count: usize,
14451463
starting_nodes: *const sg_node_handle,
1464+
config: sg_stitcher_config,
14461465
) -> *mut sg_forward_partial_path_stitcher {
14471466
let graph = unsafe { &(*graph).inner };
14481467
let partials = unsafe { &mut (*partials).inner };
@@ -1457,7 +1476,12 @@ pub extern "C" fn sg_forward_partial_path_stitcher_from_nodes(
14571476
p
14581477
})
14591478
.collect::<Vec<_>>();
1460-
let stitcher = ForwardPartialPathStitcher::from_partial_paths(graph, partials, initial_paths);
1479+
let stitcher = ForwardPartialPathStitcher::from_partial_paths(
1480+
graph,
1481+
partials,
1482+
initial_paths,
1483+
&config.into(),
1484+
);
14611485
Box::into_raw(Box::new(InternalForwardPartialPathStitcher::new(
14621486
stitcher, partials,
14631487
))) as *mut _
@@ -1471,6 +1495,7 @@ pub extern "C" fn sg_forward_partial_path_stitcher_from_partial_paths(
14711495
partials: *mut sg_partial_path_arena,
14721496
count: usize,
14731497
initial_partial_paths: *const sg_partial_path,
1498+
config: sg_stitcher_config,
14741499
) -> *mut sg_forward_partial_path_stitcher {
14751500
let graph = unsafe { &(*graph).inner };
14761501
let partials = unsafe { &mut (*partials).inner };
@@ -1480,6 +1505,7 @@ pub extern "C" fn sg_forward_partial_path_stitcher_from_partial_paths(
14801505
graph,
14811506
partials,
14821507
initial_partial_paths.to_vec(),
1508+
&config.into(),
14831509
);
14841510
Box::into_raw(Box::new(InternalForwardPartialPathStitcher::new(
14851511
stitcher, partials,

‎stack-graphs/src/stitching.rs‎

Lines changed: 16 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -795,6 +795,13 @@ impl<'a> Display for DisplaySymbolStackKey<'a> {
795795
//-------------------------------------------------------------------------------------------------
796796
// Stitching partial paths together
797797

798+
/// Configuration for partial path stitchers.
799+
#[derive(Clone, Debug, Default)]
800+
pub struct StitcherConfig {
801+
/// Enables similar path detection during path stitching.
802+
pub detect_similar_paths: bool,
803+
}
804+
798805
/// Implements a phased forward partial path stitching algorithm.
799806
///
800807
/// Our overall goal is to start with a set of _seed_ partial paths, and to repeatedly extend each
@@ -851,6 +858,7 @@ impl<H> ForwardPartialPathStitcher<H> {
851858
_graph: &StackGraph,
852859
_partials: &mut PartialPaths,
853860
initial_partial_paths: I,
861+
config: &StitcherConfig,
854862
) -> Self
855863
where
856864
I: IntoIterator<Item = PartialPath>,
@@ -863,14 +871,16 @@ impl<H> ForwardPartialPathStitcher<H> {
863871
(p, c, false)
864872
})
865873
.multiunzip();
866-
Self {
874+
let similar_path_detector =
875+
Some(SimilarPathDetector::new()).filter(|_| config.detect_similar_paths);
876+
ForwardPartialPathStitcher {
867877
candidates: Vec::new(),
868878
extensions: Vec::new(),
869879
queue: VecDeque::new(),
870880
initial_paths: next_iteration.0.len(),
871881
next_iteration,
872882
appended_paths,
873-
similar_path_detector: Some(SimilarPathDetector::new()),
883+
similar_path_detector,
874884
// By default, all nodes are checked for cycles and (if enabled) similarity
875885
check_only_join_nodes: false,
876886
// By default, there's no artificial bound on the amount of work done per phase
@@ -1145,6 +1155,7 @@ impl ForwardPartialPathStitcher<Edge> {
11451155
graph: &StackGraph,
11461156
partials: &mut PartialPaths,
11471157
file: Handle<File>,
1158+
config: &StitcherConfig,
11481159
cancellation_flag: &dyn CancellationFlag,
11491160
mut visit: F,
11501161
) -> Result<(), CancellationError>
@@ -1163,7 +1174,7 @@ impl ForwardPartialPathStitcher<Edge> {
11631174
.map(|node| PartialPath::from_node(graph, partials, node))
11641175
.collect::<Vec<_>>();
11651176
let mut stitcher =
1166-
ForwardPartialPathStitcher::from_partial_paths(graph, partials, initial_paths);
1177+
ForwardPartialPathStitcher::from_partial_paths(graph, partials, initial_paths, config);
11671178
stitcher.set_check_only_join_nodes(true);
11681179
while !stitcher.is_complete() {
11691180
cancellation_flag.check("finding complete partial paths")?;
@@ -1196,6 +1207,7 @@ impl<H: Clone> ForwardPartialPathStitcher<H> {
11961207
pub fn find_all_complete_partial_paths<I, F, A, Db, C, Err>(
11971208
candidates: &mut C,
11981209
starting_nodes: I,
1210+
config: &StitcherConfig,
11991211
cancellation_flag: &dyn CancellationFlag,
12001212
mut visit: F,
12011213
) -> Result<(), Err>
@@ -1218,7 +1230,7 @@ impl<H: Clone> ForwardPartialPathStitcher<H> {
12181230
p
12191231
})
12201232
.collect::<Vec<_>>();
1221-
ForwardPartialPathStitcher::from_partial_paths(graph, partials, initial_paths)
1233+
ForwardPartialPathStitcher::from_partial_paths(graph, partials, initial_paths, config)
12221234
};
12231235
stitcher.set_check_only_join_nodes(true);
12241236
while !stitcher.is_complete() {

‎stack-graphs/tests/it/c/can_find_local_nodes.rs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ use stack_graphs::c::sg_partial_path_list_free;
2222
use stack_graphs::c::sg_partial_path_list_new;
2323
use stack_graphs::c::sg_partial_path_list_paths;
2424
use stack_graphs::c::sg_stack_graph_nodes;
25+
use stack_graphs::c::sg_stitcher_config;
2526
use stack_graphs::graph::Node;
2627

2728
use crate::c::test_graph::TestGraph;
@@ -33,11 +34,15 @@ fn check_local_nodes(graph: &TestGraph, file: &str, expected_local_nodes: &[&str
3334

3435
let partials = sg_partial_path_arena_new();
3536
let path_list = sg_partial_path_list_new();
37+
let config = sg_stitcher_config {
38+
detect_similar_paths: false,
39+
};
3640
sg_partial_path_arena_find_partial_paths_in_file(
3741
graph.graph,
3842
partials,
3943
file.as_u32(),
4044
path_list,
45+
config,
4146
std::ptr::null(),
4247
);
4348

‎stack-graphs/tests/it/c/can_find_partial_paths_in_file.rs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ use stack_graphs::c::sg_partial_path_list_new;
2222
use stack_graphs::c::sg_partial_path_list_paths;
2323
use stack_graphs::c::sg_partial_scope_stack;
2424
use stack_graphs::c::sg_partial_symbol_stack;
25+
use stack_graphs::c::sg_stitcher_config;
2526
use stack_graphs::c::SG_LIST_EMPTY_HANDLE;
2627
use stack_graphs::c::SG_NULL_HANDLE;
2728
use stack_graphs::partial::PartialPath;
@@ -77,11 +78,15 @@ fn check_partial_paths_in_file(graph: &TestGraph, file: &str, expected_paths: &[
7778

7879
let partials = sg_partial_path_arena_new();
7980
let path_list = sg_partial_path_list_new();
81+
let config = sg_stitcher_config {
82+
detect_similar_paths: false,
83+
};
8084
sg_partial_path_arena_find_partial_paths_in_file(
8185
graph.graph,
8286
partials,
8387
file.as_u32(),
8488
path_list,
89+
config,
8590
std::ptr::null(),
8691
);
8792

‎stack-graphs/tests/it/c/can_find_qualified_definitions_with_phased_partial_path_stitching.rs‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ use stack_graphs::c::sg_partial_path_list_free;
2828
use stack_graphs::c::sg_partial_path_list_new;
2929
use stack_graphs::c::sg_partial_path_list_paths;
3030
use stack_graphs::c::sg_stack_graph;
31+
use stack_graphs::c::sg_stitcher_config;
3132
use stack_graphs::copious_debugging;
3233
use stack_graphs::graph::StackGraph;
3334
use stack_graphs::partial::PartialPath;
@@ -55,11 +56,15 @@ impl StorageLayer {
5556
let rust_graph = unsafe { &(*graph).inner };
5657
let path_list = sg_partial_path_list_new();
5758
for file in rust_graph.iter_files() {
59+
let config = sg_stitcher_config {
60+
detect_similar_paths: false,
61+
};
5862
sg_partial_path_arena_find_partial_paths_in_file(
5963
graph,
6064
partials,
6165
file.as_u32(),
6266
path_list,
67+
config,
6368
std::ptr::null(),
6469
);
6570
}
@@ -117,6 +122,9 @@ fn check_find_qualified_definitions(
117122
let partials = sg_partial_path_arena_new();
118123
let rust_partials = unsafe { &mut (*partials).inner };
119124
let db = sg_partial_path_database_new();
125+
let config = sg_stitcher_config {
126+
detect_similar_paths: false,
127+
};
120128

121129
// Create a new external storage layer holding _all_ of the partial paths in the stack graph.
122130
let mut storage_layer = StorageLayer::new(graph.graph, partials);
@@ -149,6 +157,7 @@ fn check_find_qualified_definitions(
149157
partials,
150158
1,
151159
&initial_partial_path as *const PartialPath as *const _,
160+
config,
152161
);
153162
sg_forward_partial_path_stitcher_set_max_work_per_phase(stitcher, 1);
154163
let rust_stitcher = unsafe { &mut *stitcher };

0 commit comments

Comments
 (0)