KiCad PCB EDA Suite
Loading...
Searching...
No Matches
kicad_merge_engine.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 3
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/gpl-3.0.html
19 */
20
22
23#include <json_conversions.h>
24
25#include <nlohmann/json.hpp>
26
27#include <map>
28#include <set>
29#include <stdexcept>
30
31
32namespace KICAD_DIFF
33{
34
35const char* PropResToString( PROP_RES aRes )
36{
37 switch( aRes )
38 {
39 case PROP_RES::OURS: return "ours";
40 case PROP_RES::THEIRS: return "theirs";
41 case PROP_RES::ANCESTOR: return "ancestor";
42 case PROP_RES::CUSTOM: return "custom";
43 }
44
45 return "ours";
46}
47
48
49PROP_RES PropResFromString( const std::string& aStr )
50{
51 if( aStr == "ours" ) return PROP_RES::OURS;
52 if( aStr == "theirs" ) return PROP_RES::THEIRS;
53 if( aStr == "ancestor" ) return PROP_RES::ANCESTOR;
54 if( aStr == "custom" ) return PROP_RES::CUSTOM;
55
56 throw std::invalid_argument( "Unknown PROP_RES: " + aStr );
57}
58
59
60const char* ItemResToString( ITEM_RES aRes )
61{
62 switch( aRes )
63 {
64 case ITEM_RES::TAKE_OURS: return "take_ours";
65 case ITEM_RES::TAKE_THEIRS: return "take_theirs";
66 case ITEM_RES::TAKE_ANCESTOR: return "take_ancestor";
67 case ITEM_RES::MERGE_PROPS: return "merge_props";
68 case ITEM_RES::DELETE_ITEM: return "delete";
69 case ITEM_RES::KEEP: return "keep";
70 }
71
72 return "keep";
73}
74
75
76ITEM_RES ItemResFromString( const std::string& aStr )
77{
78 if( aStr == "take_ours" ) return ITEM_RES::TAKE_OURS;
79 if( aStr == "take_theirs" ) return ITEM_RES::TAKE_THEIRS;
80 if( aStr == "take_ancestor" ) return ITEM_RES::TAKE_ANCESTOR;
81 if( aStr == "merge_props" ) return ITEM_RES::MERGE_PROPS;
82 if( aStr == "delete" )
84 if( aStr == "keep" ) return ITEM_RES::KEEP;
85
86 throw std::invalid_argument( "Unknown ITEM_RES: " + aStr );
87}
88
89
90namespace
91{
92
93void indexChangeTree( const ITEM_CHANGE& aChange,
94 std::map<KIID_PATH, const ITEM_CHANGE*>& aIndex )
95{
96 aIndex[aChange.id] = &aChange;
97
98 for( const ITEM_CHANGE& child : aChange.children )
99 {
100 // A child without an id, such as a library symbol's field, belongs to its parent's resolution
101 // Indexed, every such child on both sides would collide into one conflict on the document
102 if( !child.id.empty() )
103 indexChangeTree( child, aIndex );
104 }
105}
106
107} // namespace
108
109
110std::map<KIID_PATH, const ITEM_CHANGE*> IndexChangesByKiid( const DOCUMENT_DIFF& aDiff )
111{
112 std::map<KIID_PATH, const ITEM_CHANGE*> index;
113
114 for( const ITEM_CHANGE& c : aDiff.changes )
115 indexChangeTree( c, index );
116
117 return index;
118}
119
120
121std::map<wxString, const PROPERTY_DELTA*> IndexPropertiesByName( const ITEM_CHANGE& aChange )
122{
123 std::map<wxString, const PROPERTY_DELTA*> index;
124
125 for( const PROPERTY_DELTA& d : aChange.properties )
126 index[d.name] = &d;
127
128 return index;
129}
130
131
133 const PROPERTY_DELTA* aTheirs,
134 const KICAD_MERGE_ENGINE::OPTIONS& aOptions )
135{
137
138 if( aOurs && !aTheirs )
139 {
140 out.kind = PROP_RES::OURS;
141 return out;
142 }
143
144 if( !aOurs && aTheirs )
145 {
147 return out;
148 }
149
150 // Both sides null is unreachable from PlanMerge (allNames is the union of
151 // present keys), but defend the deref-of-aOurs/aTheirs below: assert in
152 // debug builds so a broken caller fails QA via wxAssertThrower, and
153 // return a deterministic OURS in release builds so production doesn't
154 // crash on a contract violation.
155 wxASSERT( aOurs || aTheirs );
156
157 if( !aOurs && !aTheirs )
158 {
159 out.kind = PROP_RES::OURS;
160 return out;
161 }
162
163 // Branch order is load-bearing. autoResolveEqualValues runs FIRST so
164 // converging-edits (both sides reach the same end value) auto-merge under
165 // either option flag, even when ours' delta is a no-op against a stale
166 // baseline. The two no-op detectors that follow are gated on matching
167 // before values so a stale-baseline no-op doesn't silently override a
168 // real edit on the other side.
169
170 if( aOptions.autoResolveEqualValues && aOurs->after == aTheirs->after )
171 {
172 out.kind = PROP_RES::OURS; // same end value; pick either
173 return out;
174 }
175
176 // No-op detection requires both sides to share the same `before` value
177 // (the 3-way merge contract). A stale baseline on either side disables
178 // the auto-merge and falls through to the conflict path.
179 const bool baselinesMatch = aOurs->before == aTheirs->before;
180
181 if( aOptions.preferAutoMerge && baselinesMatch && aOurs->after == aOurs->before )
182 {
183 out.kind = PROP_RES::THEIRS; // ours didn't really change
184 return out;
185 }
186
187 if( aOptions.preferAutoMerge && baselinesMatch && aTheirs->after == aTheirs->before )
188 {
189 out.kind = PROP_RES::OURS; // theirs didn't really change
190 return out;
191 }
192
193 // True conflict — default to OURS but flag for user.
194 out.kind = PROP_RES::OURS;
195 out.isUnresolved = true;
196 return out;
197}
198
199
201{
202 return name == aOther.name && kind == aOther.kind && customValue == aOther.customValue;
203}
204
205
206nlohmann::json PROPERTY_RESOLUTION::ToJson() const
207{
208 nlohmann::json j;
209 j["name"] = name;
210 j["kind"] = PropResToString( kind );
211
212 if( kind == PROP_RES::CUSTOM )
213 j["custom"] = customValue.ToJson();
214
215 return j;
216}
217
218
220{
222 r.name = aJson.at( "name" ).get<wxString>();
223 r.kind = PropResFromString( aJson.at( "kind" ).get<std::string>() );
224
225 if( aJson.contains( "custom" ) )
226 r.customValue = DIFF_VALUE::FromJson( aJson.at( "custom" ) );
227
228 return r;
229}
230
231
233{
234 return id == aOther.id && kind == aOther.kind && props == aOther.props;
235}
236
237
238nlohmann::json ITEM_RESOLUTION::ToJson() const
239{
240 nlohmann::json j;
241 j["id"] = id.AsString();
242 j["kind"] = ItemResToString( kind );
243
244 nlohmann::json arr = nlohmann::json::array();
245
246 for( const PROPERTY_RESOLUTION& p : props )
247 arr.push_back( p.ToJson() );
248
249 j["props"] = std::move( arr );
250 return j;
251}
252
253
254ITEM_RESOLUTION ITEM_RESOLUTION::FromJson( const nlohmann::json& aJson )
255{
257 r.id = KIID_PATH( aJson.at( "id" ).get<wxString>() );
258 r.kind = ItemResFromString( aJson.at( "kind" ).get<std::string>() );
259
260 for( const auto& p : aJson.at( "props" ) )
261 r.props.push_back( PROPERTY_RESOLUTION::FromJson( p ) );
262
263 return r;
264}
265
266
267nlohmann::json MERGE_PLAN::ToJson() const
268{
269 nlohmann::json j;
270
271 nlohmann::json arr = nlohmann::json::array();
272
273 for( const ITEM_RESOLUTION& a : actions )
274 arr.push_back( a.ToJson() );
275
276 j["actions"] = std::move( arr );
277
278 nlohmann::json unr = nlohmann::json::array();
279
280 for( const KIID_PATH& u : unresolved )
281 unr.push_back( u.AsString() );
282
283 j["unresolved"] = std::move( unr );
284 j["requiresZoneRefill"] = requiresZoneRefill;
285 j["requiresConnectivityRebuild"] = requiresConnectivityRebuild;
286 return j;
287}
288
289
290MERGE_PLAN MERGE_PLAN::FromJson( const nlohmann::json& aJson )
291{
292 MERGE_PLAN p;
293
294 for( const auto& a : aJson.at( "actions" ) )
295 p.actions.push_back( ITEM_RESOLUTION::FromJson( a ) );
296
297 for( const auto& u : aJson.at( "unresolved" ) )
298 p.unresolved.push_back( KIID_PATH( u.get<wxString>() ) );
299
300 p.requiresZoneRefill = aJson.value( "requiresZoneRefill", false );
301 p.requiresConnectivityRebuild = aJson.value( "requiresConnectivityRebuild", false );
302 return p;
303}
304
305
307 const DOCUMENT_DIFF& aAncestorTheirs ) const
308{
310
311 auto ourIndex = IndexChangesByKiid( aAncestorOurs );
312 auto theirIndex = IndexChangesByKiid( aAncestorTheirs );
313
314 std::set<KIID_PATH> processed;
315
316 auto noteSideEffects = [&]( const ITEM_CHANGE& aChange )
317 {
318 if( ChangeInvalidatesZone( aChange ) )
319 plan.requiresZoneRefill = true;
320
321 if( ChangeRequiresConnectivityRebuild( aChange ) )
322 plan.requiresConnectivityRebuild = true;
323 };
324
325 // Pass 1: items touched on both sides.
326 for( const auto& [id, ourChange] : ourIndex )
327 {
328 auto it = theirIndex.find( id );
329
330 if( it == theirIndex.end() )
331 continue; // only ours touched it — Pass 2 handles those
332
333 const ITEM_CHANGE* theirChange = it->second;
334 processed.insert( id );
335 noteSideEffects( *ourChange );
336 noteSideEffects( *theirChange );
337
338 // Both deleted: take the deletion.
339 if( ourChange->kind == CHANGE_KIND::REMOVED
340 && theirChange->kind == CHANGE_KIND::REMOVED )
341 {
343 r.id = id;
345 plan.actions.push_back( std::move( r ) );
346 continue;
347 }
348
349 // One side deleted, the other modified: conflict (data loss risk).
350 if( ourChange->kind == CHANGE_KIND::REMOVED
351 && theirChange->kind == CHANGE_KIND::MODIFIED )
352 {
353 plan.unresolved.push_back( id );
355 r.id = id;
356 r.kind = ITEM_RES::KEEP; // safe default; user must resolve
357 plan.actions.push_back( std::move( r ) );
358 continue;
359 }
360
361 if( ourChange->kind == CHANGE_KIND::MODIFIED
362 && theirChange->kind == CHANGE_KIND::REMOVED )
363 {
364 plan.unresolved.push_back( id );
366 r.id = id;
368 plan.actions.push_back( std::move( r ) );
369 continue;
370 }
371
372 // Both added with the same id: explicit collision. Keep the default
373 // as KEEP so a downstream `kind == TAKE_*` check still reflects an
374 // explicit user choice; applier's KEEP path falls back to
375 // ancestor-or-ours.
376 if( ourChange->kind == CHANGE_KIND::ADDED
377 && theirChange->kind == CHANGE_KIND::ADDED )
378 {
379 plan.unresolved.push_back( id );
381 r.id = id;
383 plan.actions.push_back( std::move( r ) );
384 continue;
385 }
386
387 // Both modified: property-level merge.
388 if( ourChange->kind == CHANGE_KIND::MODIFIED
389 && theirChange->kind == CHANGE_KIND::MODIFIED )
390 {
391 // preferAutoMerge=false: every item touched on both sides
392 // conflicts, even if the property edits are orthogonal.
393 if( !m_options.preferAutoMerge )
394 {
395 plan.unresolved.push_back( id );
397 r.id = id;
399 plan.actions.push_back( std::move( r ) );
400 continue;
401 }
402
403 // A coarse MODIFIED record with no property deltas and no child
404 // edits means the change was caught by semantic operator== alone
405 // — something PROPERTY_MANAGER cannot serialize (e.g., raw cache
406 // state). Resolving as MERGE_PROPS with zero props would silently
407 // lose that change; flag a conflict instead.
408 if( ourChange->properties.empty() && theirChange->properties.empty()
409 && ourChange->children.empty() && theirChange->children.empty() )
410 {
411 plan.unresolved.push_back( id );
413 r.id = id;
415 plan.actions.push_back( std::move( r ) );
416 continue;
417 }
418
420 r.id = id;
422
423 auto ourProps = IndexPropertiesByName( *ourChange );
424 auto theirProps = IndexPropertiesByName( *theirChange );
425
426 // Union of property names touched on either side.
427 std::set<wxString> allNames;
428
429 for( const auto& [n, _] : ourProps ) allNames.insert( n );
430 for( const auto& [n, _] : theirProps ) allNames.insert( n );
431
432 bool hasUnresolvedProp = false;
433
434 for( const wxString& name : allNames )
435 {
436 auto ourIt = ourProps.find( name );
437 auto theirIt = theirProps.find( name );
438
439 const PROPERTY_DELTA* ourDelta = ourIt != ourProps.end() ? ourIt->second : nullptr;
440 const PROPERTY_DELTA* theirDelta = theirIt != theirProps.end() ? theirIt->second : nullptr;
441
442 const auto outcome = ResolvePropertyConflict( ourDelta, theirDelta, m_options );
443
445 p.name = name;
446 p.kind = outcome.kind;
447 r.props.push_back( std::move( p ) );
448
449 if( outcome.isUnresolved )
450 hasUnresolvedProp = true;
451 }
452
453 if( hasUnresolvedProp )
454 plan.unresolved.push_back( id );
455
456 plan.actions.push_back( std::move( r ) );
457 continue;
458 }
459
460 // Any remaining combination is conservative-conflict.
461 plan.unresolved.push_back( id );
463 r.id = id;
465 plan.actions.push_back( std::move( r ) );
466 }
467
468 // Pass 2: items touched only on one side — auto-take that side.
469 for( const auto& [id, ourChange] : ourIndex )
470 {
471 if( processed.count( id ) )
472 continue;
473
474 noteSideEffects( *ourChange );
475
477 r.id = id;
478
479 switch( ourChange->kind )
480 {
484 break;
485
487
491 plan.unresolved.push_back( id );
492 break;
493 }
494
495 plan.actions.push_back( std::move( r ) );
496 }
497
498 for( const auto& [id, theirChange] : theirIndex )
499 {
500 if( processed.count( id ) || ourIndex.count( id ) )
501 continue;
502
503 noteSideEffects( *theirChange );
504
506 r.id = id;
507
508 switch( theirChange->kind )
509 {
513 break;
514
516
520 plan.unresolved.push_back( id );
521 break;
522 }
523
524 plan.actions.push_back( std::move( r ) );
525 }
526
527 return plan;
528}
529
530} // namespace KICAD_DIFF
int index
const char * name
static DIFF_VALUE FromJson(const nlohmann::json &aJson)
MERGE_PLAN Plan(const DOCUMENT_DIFF &aAncestorOurs, const DOCUMENT_DIFF &aAncestorTheirs) const
Plan the merge given the canonical pair of diffs.
#define _(s)
static std::vector< PENDING_PROPERTY > plan(const EDA_ITEM &aSource, const EDA_ITEM &aTarget, const std::set< wxString > &aEnabledKeys)
Target properties to write, paired with values read off the source.
bool ChangeInvalidatesZone(const ITEM_CHANGE &aChange)
Whether a change to an item of the given type invalidates any overlapping filled zones.
ITEM_RES
Resolution kind for a whole item.
const char * PropResToString(PROP_RES aRes)
Canonical lower-case spellings for PROP_RES used inside the JSON serialization of PROPERTY_RESOLUTION...
PROP_RES PropResFromString(const std::string &aStr)
PROPERTY_RESOLUTION_OUTCOME ResolvePropertyConflict(const PROPERTY_DELTA *aOurs, const PROPERTY_DELTA *aTheirs, const KICAD_MERGE_ENGINE::OPTIONS &aOptions)
Decide how to resolve a single property edit between two sides.
ITEM_RES ItemResFromString(const std::string &aStr)
PROP_RES
Resolution kind for a single property of a single item.
bool ChangeRequiresConnectivityRebuild(const ITEM_CHANGE &aChange)
Whether a change to an item of the given type requires the connectivity graph to be rebuilt.
std::map< KIID_PATH, const ITEM_CHANGE * > IndexChangesByKiid(const DOCUMENT_DIFF &aDiff)
Flatten a DOCUMENT_DIFF's ITEM_CHANGE tree into a KIID_PATH -> ITEM_CHANGE* map, recursing into child...
const char * ItemResToString(ITEM_RES aRes)
Canonical snake_case spellings used in MERGE_PLAN JSON serialization (take_ours / take_theirs / take_...
std::map< wxString, const PROPERTY_DELTA * > IndexPropertiesByName(const ITEM_CHANGE &aChange)
Index property deltas inside one ITEM_CHANGE by property name.
The full set of changes between two parsed documents of one type.
std::vector< ITEM_CHANGE > changes
One change record on a single item.
std::vector< PROPERTY_DELTA > properties
std::vector< ITEM_CHANGE > children
std::vector< PROPERTY_RESOLUTION > props
static ITEM_RESOLUTION FromJson(const nlohmann::json &aJson)
bool operator==(const ITEM_RESOLUTION &aOther) const
bool preferAutoMerge
When true, property-orthogonal edits auto-merge silently.
bool autoResolveEqualValues
When true and a property edit conflicts but the side values are equal, the resolution is automaticall...
Result of planning a 3-way merge.
std::vector< ITEM_RESOLUTION > actions
nlohmann::json ToJson() const
std::vector< KIID_PATH > unresolved
static MERGE_PLAN FromJson(const nlohmann::json &aJson)
Single (name, before, after) triple for one mutated property on an item.
Per-property merge decision result.
static PROPERTY_RESOLUTION FromJson(const nlohmann::json &aJson)
bool operator==(const PROPERTY_RESOLUTION &aOther) const