mergiraf/mergiraf
mergiraf/mergiraf
9
213
Fork 45
Code Issues 50 Pull requests 6 Releases 19 Activity Actions

feat: Distinguish between exact and inexact initial matchings #523

Merged
ada4a merged 7 commits from wetneb/initial_exact_matching into main 2025-07-26 14:53:51 +02:00 AGit
Conversation 12 Commits 7 Files changed 10 +61 -82
10 changed files with 61 additions and 82 deletions
Download patch file Download diff file Expand all files Collapse all files

58
examples/rust/failing/undetected_use_statement_move/ExpectedCurrently.rs
View file

@ -1,58 +0,0 @@
use ic_nervous_system_canisters::{cmc::CMCCanister, ledger::IcpLedgerCanister};
use ic_nervous_system_clients::{
canister_status::CanisterStatusResultV2, ledger_client::LedgerCanister,
};
use ic_nervous_system_common::{
dfn_core_stable_mem_utils::{BufferedStableMemReader, BufferedStableMemWriter},
serve_logs, serve_logs_v2, serve_metrics,
};
use ic_nervous_system_proto::pb::v1::{
GetTimersRequest, GetTimersResponse, ResetTimersRequest, ResetTimersResponse, Timers,
};
use ic_nervous_system_runtime::CdkRuntime;
use ic_nns_constants::LEDGER_CANISTER_ID as NNS_LEDGER_CANISTER_ID;
use ic_sns_governance::{
governance::{
log_prefix, Governance, TimeWarp, ValidGovernanceProto, MATURITY_DISBURSEMENT_DELAY_SECONDS,
},
logs::{ERROR, INFO},
pb::v1 as sns_gov_pb,
types::{Environment, HeapGrowthPotential},
upgrade_journal::serve_journal,
};
use ic_sns_governance_api::pb::v1::{
get_running_sns_version_response::UpgradeInProgress, governance::Version,
ClaimSwapNeuronsRequest, ClaimSwapNeuronsResponse, FailStuckUpgradeInProgressRequest,
FailStuckUpgradeInProgressResponse, GetMaturityModulationRequest,
GetMaturityModulationResponse, GetMetadataRequest, GetMetadataResponse, GetMode,
GetModeResponse, GetNeuron, GetNeuronResponse, GetProposal, GetProposalResponse,
GetRunningSnsVersionRequest, GetRunningSnsVersionResponse,
GetSnsInitializationParametersRequest, GetSnsInitializationParametersResponse,
GetUpgradeJournalRequest, GetUpgradeJournalResponse, Governance as GovernanceApi,
ListNervousSystemFunctionsResponse, ListNeurons, ListNeuronsResponse, ListProposals,
ListProposalsResponse, ManageNeuron, ManageNeuronResponse, NervousSystemParameters,
RewardEvent, SetMode, SetModeResponse,
};
#[cfg(feature = "test")]
use ic_sns_governance_api::pb::v1::{
AddMaturityRequest, AddMaturityResponse, AdvanceTargetVersionRequest,
AdvanceTargetVersionResponse, GovernanceError, MintTokensRequest, MintTokensResponse, Neuron,
RefreshCachedUpgradeStepsRequest, RefreshCachedUpgradeStepsResponse,
};
use ic_sns_governance_api::{
pb::v1::{
get_running_sns_version_response::UpgradeInProgress, governance::Version,
ClaimSwapNeuronsRequest, ClaimSwapNeuronsResponse, FailStuckUpgradeInProgressRequest,
FailStuckUpgradeInProgressResponse, GetMaturityModulationRequest,
GetMaturityModulationResponse, GetMetadataRequest, GetMetadataResponse, GetMode,
GetModeResponse, GetNeuron, GetNeuronResponse, GetProposal, GetProposalResponse,
GetRunningSnsVersionRequest, GetRunningSnsVersionResponse,
GetSnsInitializationParametersRequest, GetSnsInitializationParametersResponse,
GetUpgradeJournalRequest, GetUpgradeJournalResponse, ListNervousSystemFunctionsResponse,
ListNeurons, ListNeuronsResponse, ListProposals, ListProposalsResponse, ManageNeuron,
ManageNeuronResponse, NervousSystemParameters, RewardEvent, SetMode, SetModeResponse,
},
topics::{ListTopicsRequest, ListTopicsResponse},
};
#[cfg(test)]
mod tests;

0
examples/rust/failing/undetected_use_statement_move/Base.rs → examples/rust/working/undetected_use_statement_move/Base.rs
View file

0
examples/rust/failing/undetected_use_statement_move/ExpectedIdeally.rs → examples/rust/working/undetected_use_statement_move/Expected.rs
View file

0
examples/rust/failing/undetected_use_statement_move/Left.rs → examples/rust/working/undetected_use_statement_move/Left.rs
View file

0
examples/rust/failing/undetected_use_statement_move/README → examples/rust/working/undetected_use_statement_move/README
View file

0
examples/rust/failing/undetected_use_statement_move/Right.rs → examples/rust/working/undetected_use_statement_move/Right.rs
View file

25
src/matching.rs
View file

@ -13,6 +13,31 @@ pub struct Matching<'tree> {
right_to_left: FxHashMap<&'tree AstNode<'tree>, &'tree AstNode<'tree>>,
}
/// A pair of matchings, one representing exact matches between isomorphic nodes,
/// and the other one representing approximate matches between nodes where the
/// subtrees might not be isomorphic.
#[derive(Debug, Clone)]
pub struct ApproxExactMatching<'a> {
pub exact: Matching<'a>,
pub approx: Matching<'a>,
}
impl<'a> ApproxExactMatching<'a> {
pub fn from_exact(exact: Matching<'a>) -> Self {
ApproxExactMatching {
exact,
approx: Matching::new(),
}
}
pub fn from_approx(approx: Matching<'a>) -> Self {
ApproxExactMatching {
approx,
exact: Matching::new(),
}
}
}
impl<'tree> Matching<'tree> {
/// Creates an empty matching.
pub fn new() -> Self {

12
src/merge_3dm.rs
View file

@ -7,7 +7,7 @@ use crate::{
changeset::ChangeSet,
class_mapping::{ClassMapping, RevNode},
line_based::line_based_merge_parsed,
matching::Matching,
matching::{ApproxExactMatching, Matching},
merged_tree::MergedTree,
pcs::Revision,
settings::DisplaySettings,
@ -34,7 +34,7 @@ pub fn three_way_merge<'a>(
base: &'a AstNode<'a>,
left: &'a AstNode<'a>,
right: &'a AstNode<'a>,
initial_matchings: Option<&(Matching<'a>, Matching<'a>)>,
initial_matchings: Option<&(ApproxExactMatching<'a>, ApproxExactMatching<'a>)>,
primary_matcher: &TreeMatcher,
auxiliary_matcher: &TreeMatcher,
settings: &DisplaySettings<'a>,
@ -86,7 +86,7 @@ fn generate_matchings<'a>(
base: &'a AstNode<'a>,
left: &'a AstNode<'a>,
right: &'a AstNode<'a>,
initial_matchings: Option<&(Matching<'a>, Matching<'a>)>,
initial_matchings: Option<&(ApproxExactMatching<'a>, ApproxExactMatching<'a>)>,
primary_matcher: &TreeMatcher,
auxiliary_matcher: &TreeMatcher,
debug_dir: Option<&Path>,
@ -127,7 +127,11 @@ fn generate_matchings<'a>(
&base_left_matching.full,
&base_right_matching.full,
);
let left_right_matching = auxiliary_matcher.match_trees(left, right, Some(&composed_matching));
let left_right_matching = auxiliary_matcher.match_trees(
left,
right,
Some(&ApproxExactMatching::from_approx(composed_matching)),
);
debug!("matching all three pairs took {:?}", start.elapsed());
// save the matchings for debugging purposes

21
src/structured.rs
View file

@ -4,8 +4,9 @@ use log::debug;
use typed_arena::Arena;
use crate::{
MergeResult, Revision, ast::AstNode, lang_profile::LangProfile, merge_3dm::three_way_merge,
parsed_merge::ParsedMerge, settings::DisplaySettings, tree_matcher::TreeMatcher,
MergeResult, Revision, ast::AstNode, lang_profile::LangProfile, matching::ApproxExactMatching,
merge_3dm::three_way_merge, parsed_merge::ParsedMerge, settings::DisplaySettings,
tree_matcher::TreeMatcher,
};
pub const STRUCTURED_RESOLUTION_METHOD: &str = "structured_resolution";
@ -67,12 +68,16 @@ pub fn structured_merge(
let initial_matchings = parsed_merge.map(|parsed_merge| {
(
parsed_merge
.generate_matching(Revision::Base, Revision::Left, tree_base, tree_left)
.add_submatches(),
parsed_merge
.generate_matching(Revision::Base, Revision::Right, tree_base, tree_right)
.add_submatches(),
ApproxExactMatching::from_exact(
parsed_merge
.generate_matching(Revision::Base, Revision::Left, tree_base, tree_left)
.add_submatches(),
),
ApproxExactMatching::from_exact(
parsed_merge
.generate_matching(Revision::Base, Revision::Right, tree_base, tree_right)
.add_submatches(),
),
)
});

27
src/tree_matcher.rs
View file

@ -9,7 +9,12 @@ use std::{
use tree_edit_distance::{Edit, diff};
use typed_arena::Arena;
use crate::{ast::AstNode, matching::Matching, multimap::MultiMap, signature::Signature};
use crate::{
ast::AstNode,
matching::{ApproxExactMatching, Matching},
multimap::MultiMap,
signature::Signature,
};
mod priority_list;
use priority_list::PriorityList;
@ -46,7 +51,7 @@ impl TreeMatcher {
&self,
left: &'a AstNode<'a>,
right: &'a AstNode<'a>,
initial_matching: Option<&Matching<'a>>,
initial_matching: Option<&ApproxExactMatching<'a>>,
) -> DetailedMatching<'a> {
let start = Instant::now();
@ -80,26 +85,24 @@ impl TreeMatcher {
}
}
// First pass of the GumTree classic algorithm, top down, creating the exact matchings between isomorphic subtrees
/// First pass of the GumTree classic algorithm, top down, creating the exact matchings between isomorphic subtrees.
/// It takes two initial matchings, an approximate and an exact one. The exact matching produced by this method
/// will include the initial exact one provided and is compatible with the approximate one supplied (meaning that it
/// doesn't match any nodes that are already approximately matched).
fn top_down_pass<'a>(
&self,
ada4a marked this conversation as resolved
ada4a commented 2025-07-24 17:17:36 +02:00
Copy link

The docs need to be updated then

The docs need to be updated then
👍 1
left: &'a AstNode<'a>,
right: &'a AstNode<'a>,
initial_matching: Option<&Matching<'a>>,
initial_matching: Option<&ApproxExactMatching<'a>>,
) -> (Matching<'a>, Matching<'a>) {
let mut matching = Matching::new();
let mut exact_matching = Matching::new();
let mut auxiliary = Matching::new();
if let Some(initial_matching) = initial_matching {
/*
exact_matching.add_matching(initial_matching);
for (right_match, left_match) in initial_matching.iter_right_to_left() {
for (left_descendant, right_descendant) in left_match.dfs().zip(right_match.dfs()) {
matching.add(left_descendant, right_descendant);
}
} */
matching.add_matching(initial_matching);
matching.add_matching(&initial_matching.approx);
matching.add_matching(&initial_matching.exact);
exact_matching.add_matching(&initial_matching.exact);
}
let mut l1 = PriorityList::new();