blob: e0b0b7b42b84c050430b954d3145fe31ae20c013 [file] [log] [blame]
Michal Vaskod59035b2020-07-08 12:00:06 +02001/**
2 * @file diff.c
3 * @author Michal Vasko <mvasko@cesnet.cz>
4 * @brief diff functions
5 *
6 * Copyright (c) 2020 CESNET, z.s.p.o.
7 *
8 * This source code is licensed under BSD 3-Clause License (the "License").
9 * You may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * https://opensource.org/licenses/BSD-3-Clause
13 */
14#define _XOPEN_SOURCE 500
Radek Krejci33185cb2020-07-11 23:15:22 +020015#define _POSIX_C_SOURCE 200809L
Michal Vaskod59035b2020-07-08 12:00:06 +020016
17#include "diff.h"
18
19#include <assert.h>
20#include <stddef.h>
21#include <string.h>
22
23#include "common.h"
24#include "log.h"
25#include "tree_data_internal.h"
26#include "tree_schema.h"
27#include "tree_schema_internal.h"
28
29static const char *
30lyd_diff_op2str(enum lyd_diff_op op)
31{
32 switch (op) {
33 case LYD_DIFF_OP_CREATE:
34 return "create";
35 case LYD_DIFF_OP_DELETE:
36 return "delete";
37 case LYD_DIFF_OP_REPLACE:
38 return "replace";
39 case LYD_DIFF_OP_NONE:
40 return "none";
41 }
42
43 LOGINT(NULL);
44 return NULL;
45}
46
Michal Vaskoe6323f62020-07-09 15:49:02 +020047static enum lyd_diff_op
48lyd_diff_str2op(const char *str)
49{
50 switch (str[0]) {
51 case 'c':
52 assert(!strcmp(str, "create"));
53 return LYD_DIFF_OP_CREATE;
54 case 'd':
55 assert(!strcmp(str, "delete"));
56 return LYD_DIFF_OP_DELETE;
57 case 'r':
58 assert(!strcmp(str, "replace"));
59 return LYD_DIFF_OP_REPLACE;
60 case 'n':
61 assert(!strcmp(str, "none"));
62 return LYD_DIFF_OP_NONE;
63 }
64
65 LOGINT(NULL);
66 return 0;
67}
68
Michal Vaskod59035b2020-07-08 12:00:06 +020069LY_ERR
70lyd_diff_add(const struct lyd_node *node, enum lyd_diff_op op, const char *orig_default, const char *orig_value,
Radek Krejci0f969882020-08-21 16:56:47 +020071 const char *key, const char *value, const char *orig_key, struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +020072{
73 struct lyd_node *dup, *siblings, *match = NULL, *diff_parent = NULL;
74 const struct lyd_node *parent = NULL;
75 const struct lys_module *yang_mod;
76
77 assert(diff);
78
79 /* find the first existing parent */
80 siblings = *diff;
81 while (1) {
82 /* find next node parent */
83 parent = node;
84 while (parent->parent && (!diff_parent || (parent->parent->schema != diff_parent->schema))) {
85 parent = (struct lyd_node *)parent->parent;
86 }
87 if (parent == node) {
88 /* no more parents to find */
89 break;
90 }
91
92 /* check whether it exists in the diff */
93 if (lyd_find_sibling_first(siblings, parent, &match)) {
94 break;
95 }
96
97 /* another parent found */
98 diff_parent = match;
99
100 /* move down in the diff */
Michal Vasko8ee464a2020-08-11 14:12:50 +0200101 siblings = LYD_CHILD_NO_KEYS(match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200102 }
103
104 /* duplicate the subtree (and connect to the diff if possible) */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200105 LY_CHECK_RET(lyd_dup_single(node, (struct lyd_node_inner *)diff_parent,
106 LYD_DUP_RECURSIVE | LYD_DUP_NO_META | LYD_DUP_WITH_PARENTS, &dup));
Michal Vaskod59035b2020-07-08 12:00:06 +0200107
108 /* find the first duplicated parent */
109 if (!diff_parent) {
110 diff_parent = (struct lyd_node *)dup->parent;
111 while (diff_parent && diff_parent->parent) {
112 diff_parent = (struct lyd_node *)diff_parent->parent;
113 }
114 } else {
115 diff_parent = (struct lyd_node *)dup;
116 while (diff_parent->parent && (diff_parent->parent->schema == parent->schema)) {
117 diff_parent = (struct lyd_node *)diff_parent->parent;
118 }
119 }
120
121 /* no parent existed, must be manually connected */
122 if (!diff_parent) {
123 /* there actually was no parent to duplicate */
Michal Vaskob104f112020-07-17 09:54:54 +0200124 lyd_insert_sibling(*diff, dup, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200125 } else if (!diff_parent->parent) {
Michal Vaskob104f112020-07-17 09:54:54 +0200126 lyd_insert_sibling(*diff, diff_parent, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200127 }
128
129 /* get module with the operation metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200130 yang_mod = LYD_CTX(node)->list.objs[1];
Michal Vaskod59035b2020-07-08 12:00:06 +0200131 assert(!strcmp(yang_mod->name, "yang"));
132
133 /* add parent operation, if any */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200134 if (diff_parent && (diff_parent != dup)) {
135 LY_CHECK_RET(lyd_new_meta(diff_parent, yang_mod, "operation", "none", NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200136 }
137
138 /* add subtree operation */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200139 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "operation", lyd_diff_op2str(op), NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200140
141 /* orig-default */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200142 if (orig_default) {
143 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "orig-default", orig_default, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200144 }
145
146 /* orig-value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200147 if (orig_value) {
148 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "orig-value", orig_value, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200149 }
150
151 /* key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200152 if (key) {
153 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "key", key, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200154 }
155
156 /* value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200157 if (value) {
158 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "value", value, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200159 }
160
161 /* orig-key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200162 if (orig_key) {
163 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "orig-key", orig_key, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200164 }
165
166 return LY_SUCCESS;
167}
168
169/**
170 * @brief Get a userord entry for a specific user-ordered list/leaf-list. Create if does not exist yet.
171 *
172 * @param[in] first
173 * @param[in] schema Schema node of the list/leaf-list.
174 * @param[in,out] userord Sized array of userord items.
175 * @return Userord item for all the user-ordered list/leaf-list instances.
176 */
177static struct lyd_diff_userord *
178lyd_diff_userord_get(const struct lyd_node *first, const struct lysc_node *schema, struct lyd_diff_userord **userord)
179{
180 struct lyd_diff_userord *item;
181 const struct lyd_node *iter, **node;
182 LY_ARRAY_COUNT_TYPE u;
183
184 LY_ARRAY_FOR(*userord, u) {
185 if ((*userord)[u].schema == schema) {
186 return &(*userord)[u];
187 }
188 }
189
190 /* it was not added yet, add it now */
191 LY_ARRAY_NEW_RET(schema->module->ctx, *userord, item, NULL);
192
193 item->schema = schema;
194 item->pos = 0;
195 item->inst = NULL;
196
197 /* store all the instance pointers in the current order */
198 if (first) {
199 if (first->parent) {
200 iter = first->parent->child;
201 } else {
Radek Krejci1e008d22020-08-17 11:37:37 +0200202 for (iter = first; iter->prev->next; iter = iter->prev) {}
Michal Vaskod59035b2020-07-08 12:00:06 +0200203 }
204 for (; iter; iter = iter->next) {
205 if (iter->schema == first->schema) {
206 LY_ARRAY_NEW_RET(schema->module->ctx, item->inst, node, NULL);
207 *node = iter;
208 }
209 }
210 }
211
212 return item;
213}
214
215/**
216 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Can be used only for user-ordered
217 * lists/leaf-lists.
218 *
219 * @param[in] first Node from the first tree, can be NULL (on create).
220 * @param[in] second Node from the second tree, can be NULL (on delete).
221 * @param[in] options Diff options.
222 * @param[in,out] userord Sized array of userord items for keeping the current node order.
223 * @param[out] op Operation.
224 * @param[out] orig_default Original default metadata.
225 * @param[out] value Value metadata.
226 * @param[out] orig_value Original value metadata
227 * @param[out] key Key metadata.
228 * @param[out] orig_key Original key metadata.
229 * @return LY_SUCCESS on success,
230 * @return LY_ENOT if there is no change to be added into diff,
231 * @return LY_ERR value on other errors.
232 */
233static LY_ERR
234lyd_diff_userord_attrs(const struct lyd_node *first, const struct lyd_node *second, int options,
Radek Krejci0f969882020-08-21 16:56:47 +0200235 struct lyd_diff_userord **userord, enum lyd_diff_op *op, const char **orig_default, char **value,
236 char **orig_value, char **key, char **orig_key)
Michal Vaskod59035b2020-07-08 12:00:06 +0200237{
238 const struct lysc_node *schema;
Michal Vaskod59035b2020-07-08 12:00:06 +0200239 size_t buflen, bufused, first_pos, second_pos;
240 struct lyd_diff_userord *userord_item;
241
242 assert(first || second);
243
244 *orig_default = NULL;
245 *value = NULL;
246 *orig_value = NULL;
247 *key = NULL;
248 *orig_key = NULL;
249
250 schema = first ? first->schema : second->schema;
251 assert(lysc_is_userordered(schema));
252
253 /* get userord entry */
254 userord_item = lyd_diff_userord_get(first, schema, userord);
255 LY_CHECK_RET(!userord_item, LY_EMEM);
256
257 /* prepare position of the next instance */
258 second_pos = userord_item->pos++;
259
260 /* find user-ordered first position */
261 if (first) {
262 for (first_pos = second_pos; first_pos < LY_ARRAY_COUNT(userord_item->inst); ++first_pos) {
263 if (userord_item->inst[first_pos] == first) {
264 break;
265 }
266 }
267 assert(first_pos < LY_ARRAY_COUNT(userord_item->inst));
268 } else {
269 first_pos = 0;
270 }
271
272 /* learn operation first */
273 if (!second) {
274 *op = LYD_DIFF_OP_DELETE;
275 } else if (!first) {
276 *op = LYD_DIFF_OP_CREATE;
277 } else {
278 assert(schema->nodetype & (LYS_LIST | LYS_LEAFLIST));
Michal Vasko8f359bf2020-07-28 10:41:15 +0200279 if (lyd_compare_single(second, userord_item->inst[second_pos], 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200280 /* in first, there is a different instance on the second position, we are going to move 'first' node */
281 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200282 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200283 /* default flag change */
284 *op = LYD_DIFF_OP_NONE;
285 } else {
286 /* no changes */
287 return LY_ENOT;
288 }
289 }
290
291 /*
292 * set each attribute correctly based on the operation and node type
293 */
294
295 /* orig-default */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200296 if ((options & LYD_DIFF_DEFAULTS) && (schema->nodetype == LYS_LEAFLIST)
Michal Vaskoe6323f62020-07-09 15:49:02 +0200297 && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))
298 && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200299 if (first->flags & LYD_DEFAULT) {
300 *orig_default = "true";
301 } else {
302 *orig_default = "false";
303 }
304 }
305
306 /* value */
307 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
308 if (second_pos) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200309 *value = strdup(LYD_CANON_VALUE(userord_item->inst[second_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200310 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200311 } else {
312 *value = strdup("");
313 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
314 }
315 }
316
317 /* orig-value */
318 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
319 if (first_pos) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200320 *orig_value = strdup(LYD_CANON_VALUE(userord_item->inst[first_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200321 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200322 } else {
323 *orig_value = strdup("");
324 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
325 }
326 }
327
328 /* key */
Michal Vasko44f3d2c2020-08-24 09:49:38 +0200329 if ((schema->nodetype == LYS_LIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200330 if (second_pos) {
331 buflen = bufused = 0;
332 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[second_pos - 1], key, &buflen, &bufused, 0));
333 } else {
334 *key = strdup("");
335 LY_CHECK_ERR_RET(!*key, LOGMEM(schema->module->ctx), LY_EMEM);
336 }
337 }
338
339 /* orig-key */
340 if ((schema->nodetype == LYS_LIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
341 if (first_pos) {
342 buflen = bufused = 0;
343 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[first_pos - 1], orig_key, &buflen, &bufused, 0));
344 } else {
345 *orig_key = strdup("");
346 LY_CHECK_ERR_RET(!*orig_key, LOGMEM(schema->module->ctx), LY_EMEM);
347 }
348 }
349
350 /*
351 * update our instances - apply the change
352 */
353 if (*op == LYD_DIFF_OP_CREATE) {
354 /* insert the instance */
355 LY_ARRAY_RESIZE_ERR_RET(schema->module->ctx, userord_item->inst, LY_ARRAY_COUNT(userord_item->inst) + 1,
356 ;, LY_EMEM);
357 if (second_pos < LY_ARRAY_COUNT(userord_item->inst)) {
358 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
359 (LY_ARRAY_COUNT(userord_item->inst) - second_pos) * sizeof *userord_item->inst);
360 }
361 LY_ARRAY_INCREMENT(userord_item->inst);
362 userord_item->inst[second_pos] = second;
363
364 } else if (*op == LYD_DIFF_OP_DELETE) {
365 /* remove the instance */
366 if (first_pos + 1 < LY_ARRAY_COUNT(userord_item->inst)) {
367 memmove(userord_item->inst + first_pos, userord_item->inst + first_pos + 1,
368 (LY_ARRAY_COUNT(userord_item->inst) - first_pos - 1) * sizeof *userord_item->inst);
369 }
370 LY_ARRAY_DECREMENT(userord_item->inst);
371
372 } else if (*op == LYD_DIFF_OP_REPLACE) {
373 /* move the instances */
374 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
375 (first_pos - second_pos) * sizeof *userord_item->inst);
376 userord_item->inst[second_pos] = first;
377 }
378
379 return LY_SUCCESS;
380}
381
382/**
383 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Cannot be used for user-ordered
384 * lists/leaf-lists.
385 *
386 * @param[in] first Node from the first tree, can be NULL (on create).
387 * @param[in] second Node from the second tree, can be NULL (on delete).
388 * @param[in] options Diff options.
389 * @param[out] op Operation.
390 * @param[out] orig_default Original default metadata.
391 * @param[out] orig_value Original value metadata.
392 * @return LY_SUCCESS on success,
393 * @return LY_ENOT if there is no change to be added into diff,
394 * @return LY_ERR value on other errors.
395 */
396static LY_ERR
397lyd_diff_attrs(const struct lyd_node *first, const struct lyd_node *second, int options, enum lyd_diff_op *op,
Radek Krejci0f969882020-08-21 16:56:47 +0200398 const char **orig_default, char **orig_value)
Michal Vaskod59035b2020-07-08 12:00:06 +0200399{
400 const struct lysc_node *schema;
Michal Vaskod59035b2020-07-08 12:00:06 +0200401
402 assert(first || second);
403
404 *orig_default = NULL;
405 *orig_value = NULL;
406
407 schema = first ? first->schema : second->schema;
408 assert(!lysc_is_userordered(schema));
409
410 /* learn operation first */
411 if (!second) {
412 *op = LYD_DIFF_OP_DELETE;
413 } else if (!first) {
414 *op = LYD_DIFF_OP_CREATE;
415 } else {
416 switch (schema->nodetype) {
417 case LYS_CONTAINER:
418 case LYS_RPC:
419 case LYS_ACTION:
420 case LYS_NOTIF:
421 /* no changes */
422 return LY_ENOT;
423 case LYS_LIST:
424 case LYS_LEAFLIST:
Michal Vasko3a41dff2020-07-15 14:30:28 +0200425 if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200426 /* default flag change */
427 *op = LYD_DIFF_OP_NONE;
428 } else {
429 /* no changes */
430 return LY_ENOT;
431 }
432 break;
433 case LYS_LEAF:
434 case LYS_ANYXML:
435 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +0200436 if (lyd_compare_single(first, second, 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200437 /* different values */
438 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200439 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200440 /* default flag change */
441 *op = LYD_DIFF_OP_NONE;
442 } else {
443 /* no changes */
444 return LY_ENOT;
445 }
446 break;
447 default:
448 LOGINT_RET(schema->module->ctx);
449 }
450 }
451
452 /*
453 * set each attribute correctly based on the operation and node type
454 */
455
456 /* orig-default */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200457 if ((options & LYD_DIFF_DEFAULTS) && (schema->nodetype & LYD_NODE_TERM)
Michal Vaskoe6323f62020-07-09 15:49:02 +0200458 && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))
459 && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200460 if (first->flags & LYD_DEFAULT) {
461 *orig_default = "true";
462 } else {
463 *orig_default = "false";
464 }
465 }
466
467 /* orig-value */
468 if ((schema->nodetype == LYS_LEAF) && (*op == LYD_DIFF_OP_REPLACE)) {
469 /* leaf */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200470 *orig_value = strdup(LYD_CANON_VALUE(first));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200471 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200472 }
473
474 return LY_SUCCESS;
475}
476
477/**
478 * @brief Perform diff for all siblings at certain depth, recursively.
479 *
480 * For user-ordered lists/leaf-lists a specific structure is used for storing
481 * the current order. The idea is to apply all the generated diff changes
482 * virtually on the first tree so that we can continue to generate correct
483 * changes after some were already generated.
484 *
485 * The algorithm then uses second tree position-based changes with a before
486 * (preceding) item anchor.
487 *
488 * Example:
489 *
490 * Virtual first tree leaf-list order:
491 * 1 2 [3] 4 5
492 *
493 * Second tree leaf-list order:
494 * 1 2 [5] 3 4
495 *
496 * We are at the 3rd node now. We look at whether the nodes on the 3rd position
497 * match - they do not - move nodes so that the 3rd position node is final ->
498 * -> move node 5 to the 3rd position -> move node 5 after node 2.
499 *
500 * Required properties:
501 * Stored operations (move) should not be affected by later operations -
502 * - would cause a redundantly long list of operations, possibly inifinite.
503 *
504 * Implemenation justification:
505 * First, all delete operations and only then move/create operations are stored.
506 * Also, preceding anchor is used and after each iteration another node is
507 * at its final position. That results in the invariant that all preceding
508 * nodes are final and will not be changed by the later operations, meaning
509 * they can safely be used as anchors for the later operations.
510 *
511 * @param[in] first First tree first sibling.
512 * @param[in] second Second tree first sibling.
513 * @param[in] options Diff options.
Michal Vasko3a41dff2020-07-15 14:30:28 +0200514 * @param[in] nosiblings Whether to skip following siblings.
Michal Vaskod59035b2020-07-08 12:00:06 +0200515 * @param[in,out] diff Diff to append to.
516 * @return LY_ERR value.
517 */
518static LY_ERR
Michal Vasko3a41dff2020-07-15 14:30:28 +0200519lyd_diff_siblings_r(const struct lyd_node *first, const struct lyd_node *second, int options, int nosiblings,
Radek Krejci0f969882020-08-21 16:56:47 +0200520 struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +0200521{
522 LY_ERR ret = LY_SUCCESS;
523 const struct lyd_node *iter_first, *iter_second;
524 struct lyd_node *match_second, *match_first;
Michal Vaskod59035b2020-07-08 12:00:06 +0200525 struct lyd_diff_userord *userord = NULL;
526 LY_ARRAY_COUNT_TYPE u;
527 enum lyd_diff_op op;
528 const char *orig_default;
529 char *orig_value, *key, *value, *orig_key;
530
Michal Vaskod59035b2020-07-08 12:00:06 +0200531 /* compare first tree to the second tree - delete, replace, none */
532 LY_LIST_FOR(first, iter_first) {
533 assert(!(iter_first->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200534 if ((iter_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200535 /* skip default nodes */
536 continue;
537 }
538
539 if (iter_first->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
540 /* try to find the exact instance */
541 lyd_find_sibling_first(second, iter_first, &match_second);
542 } else {
543 /* try to simply find the node, there cannot be more instances */
544 lyd_find_sibling_val(second, iter_first->schema, NULL, 0, &match_second);
545 }
546
Michal Vasko3a41dff2020-07-15 14:30:28 +0200547 if (match_second && (match_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200548 /* ignore default nodes */
549 match_second = NULL;
550 }
551
552 if (lysc_is_userordered(iter_first->schema)) {
553 if (match_second) {
554 /* we are handling only user-ordered node delete now */
555 continue;
556 }
557
558 /* get all the attributes */
559 LY_CHECK_GOTO(lyd_diff_userord_attrs(iter_first, match_second, options, &userord, &op, &orig_default,
560 &value, &orig_value, &key, &orig_key), cleanup);
561
562 /* there must be changes, it is deleted */
563 assert(op == LYD_DIFF_OP_DELETE);
564 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, key, value, orig_key, diff);
565
566 free(orig_value);
567 free(key);
568 free(value);
569 free(orig_key);
570 LY_CHECK_GOTO(ret, cleanup);
571 } else {
572 /* get all the attributes */
573 ret = lyd_diff_attrs(iter_first, match_second, options, &op, &orig_default, &orig_value);
574
575 /* add into diff if there are any changes */
576 if (!ret) {
577 if (op == LYD_DIFF_OP_DELETE) {
578 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, NULL, NULL, NULL, diff);
579 } else {
580 ret = lyd_diff_add(match_second, op, orig_default, orig_value, NULL, NULL, NULL, diff);
581 }
582
583 free(orig_value);
584 LY_CHECK_GOTO(ret, cleanup);
585 } else if (ret == LY_ENOT) {
586 ret = LY_SUCCESS;
587 } else {
588 goto cleanup;
589 }
590 }
591
592 /* check descendants, if any, recursively */
593 if (match_second) {
Michal Vasko8ee464a2020-08-11 14:12:50 +0200594 LY_CHECK_GOTO(lyd_diff_siblings_r(LYD_CHILD_NO_KEYS(iter_first), LYD_CHILD_NO_KEYS(match_second), options,
595 0, diff), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200596 }
597
598 if (nosiblings) {
599 break;
600 }
601 }
602
603 /* reset all cached positions */
604 LY_ARRAY_FOR(userord, u) {
605 userord[u].pos = 0;
606 }
607
608 /* compare second tree to the first tree - create, user-ordered move */
609 LY_LIST_FOR(second, iter_second) {
610 assert(!(iter_second->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200611 if ((iter_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200612 /* skip default nodes */
613 continue;
614 }
615
616 if (iter_second->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
617 lyd_find_sibling_first(first, iter_second, &match_first);
618 } else {
619 lyd_find_sibling_val(first, iter_second->schema, NULL, 0, &match_first);
620 }
621
Michal Vasko3a41dff2020-07-15 14:30:28 +0200622 if (match_first && (match_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200623 /* ignore default nodes */
624 match_first = NULL;
625 }
626
627 if (lysc_is_userordered(iter_second->schema)) {
628 /* get all the attributes */
629 ret = lyd_diff_userord_attrs(match_first, iter_second, options, &userord, &op, &orig_default,
630 &value, &orig_value, &key, &orig_key);
631
632 /* add into diff if there are any changes */
633 if (!ret) {
634 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, key, value, orig_key, diff);
635
636 free(orig_value);
637 free(key);
638 free(value);
639 free(orig_key);
640 LY_CHECK_GOTO(ret, cleanup);
641 } else if (ret == LY_ENOT) {
642 ret = LY_SUCCESS;
643 } else {
644 goto cleanup;
645 }
646 } else if (!match_first) {
647 /* get all the attributes */
648 LY_CHECK_GOTO(lyd_diff_attrs(match_first, iter_second, options, &op, &orig_default, &orig_value), cleanup);
649
650 /* there must be changes, it is created */
651 assert(op == LYD_DIFF_OP_CREATE);
652 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, NULL, NULL, NULL, diff);
653
654 free(orig_value);
655 LY_CHECK_GOTO(ret, cleanup);
656 } /* else was handled */
657
658 if (nosiblings) {
659 break;
660 }
661 }
662
663cleanup:
664 LY_ARRAY_FOR(userord, u) {
665 LY_ARRAY_FREE(userord[u].inst);
666 }
667 LY_ARRAY_FREE(userord);
668 return ret;
669}
670
Michal Vasko3a41dff2020-07-15 14:30:28 +0200671static LY_ERR
672lyd_diff(const struct lyd_node *first, const struct lyd_node *second, int options, int nosiblings, struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +0200673{
674 const struct ly_ctx *ctx;
675
676 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
677
678 if (first) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200679 ctx = LYD_CTX(first);
Michal Vaskod59035b2020-07-08 12:00:06 +0200680 } else if (second) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200681 ctx = LYD_CTX(second);
Michal Vaskod59035b2020-07-08 12:00:06 +0200682 } else {
683 ctx = NULL;
684 }
685
686 if (first && second && (lysc_data_parent(first->schema) != lysc_data_parent(second->schema))) {
687 LOGERR(ctx, LY_EINVAL, "Invalid arguments - cannot create diff for unrelated data (%s()).", __func__);
688 return LY_EINVAL;
689 }
690
691 *diff = NULL;
692
Michal Vasko3a41dff2020-07-15 14:30:28 +0200693 return lyd_diff_siblings_r(first, second, options, nosiblings, diff);
694}
695
696API LY_ERR
697lyd_diff_tree(const struct lyd_node *first, const struct lyd_node *second, int options, struct lyd_node **diff)
698{
699 return lyd_diff(first, second, options, 1, diff);
700}
701
702API LY_ERR
703lyd_diff_siblings(const struct lyd_node *first, const struct lyd_node *second, int options, struct lyd_node **diff)
704{
705 return lyd_diff(first, second, options, 0, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200706}
707
708/**
709 * @brief Find a matching node in data tree for a diff node.
710 *
711 * @param[in] first_node First sibling in the data tree.
712 * @param[in] diff_node Diff node to match.
Michal Vaskoe6323f62020-07-09 15:49:02 +0200713 * @param[out] match_p Matching node, NULL if no found.
Michal Vaskod59035b2020-07-08 12:00:06 +0200714 */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200715static void
Michal Vaskod59035b2020-07-08 12:00:06 +0200716lyd_diff_find_node(const struct lyd_node *first_node, const struct lyd_node *diff_node, struct lyd_node **match_p)
717{
718 if (diff_node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
719 /* try to find the exact instance */
720 lyd_find_sibling_first(first_node, diff_node, match_p);
721 } else {
722 /* try to simply find the node, there cannot be more instances */
723 lyd_find_sibling_val(first_node, diff_node->schema, NULL, 0, match_p);
724 }
Michal Vaskod59035b2020-07-08 12:00:06 +0200725}
726
727/**
728 * @brief Learn operation of a diff node.
729 *
730 * @param[in] diff_node Diff node.
731 * @param[out] op Operation.
Michal Vaskod59035b2020-07-08 12:00:06 +0200732 * @return LY_ERR value.
733 */
734static LY_ERR
Michal Vaskoe6323f62020-07-09 15:49:02 +0200735lyd_diff_get_op(const struct lyd_node *diff_node, enum lyd_diff_op *op)
Michal Vaskod59035b2020-07-08 12:00:06 +0200736{
737 struct lyd_meta *meta = NULL;
738 const struct lyd_node *diff_parent;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200739 const char *str;
Michal Vaskod59035b2020-07-08 12:00:06 +0200740
741 for (diff_parent = diff_node; diff_parent; diff_parent = (struct lyd_node *)diff_parent->parent) {
742 LY_LIST_FOR(diff_parent->meta, meta) {
743 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200744 str = meta->value.canonical;
Michal Vaskod59035b2020-07-08 12:00:06 +0200745 if ((str[0] == 'r') && (diff_parent != diff_node)) {
746 /* we do not care about this operation if it's in our parent */
747 continue;
748 }
Michal Vaskoe6323f62020-07-09 15:49:02 +0200749 *op = lyd_diff_str2op(str);
Michal Vaskod59035b2020-07-08 12:00:06 +0200750 break;
751 }
752 }
753 if (meta) {
754 break;
755 }
756 }
Michal Vaskob7be7a82020-08-20 09:09:04 +0200757 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_node)), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +0200758
Michal Vaskod59035b2020-07-08 12:00:06 +0200759 return LY_SUCCESS;
760}
761
762/**
763 * @brief Insert a diff node into a data tree.
764 *
765 * @param[in,out] first_node First sibling of the data tree.
766 * @param[in] parent_node Data tree sibling parent node.
767 * @param[in] new_node Node to insert.
768 * @param[in] keys_or_value Optional predicate of relative (leaf-)list instance. If not set, the user-ordered
769 * instance will be inserted at the first position.
770 * @return err_info, NULL on success.
771 */
772static LY_ERR
773lyd_diff_insert(struct lyd_node **first_node, struct lyd_node *parent_node, struct lyd_node *new_node,
Radek Krejci0f969882020-08-21 16:56:47 +0200774 const char *key_or_value)
Michal Vaskod59035b2020-07-08 12:00:06 +0200775{
776 LY_ERR ret;
777 struct lyd_node *anchor;
778
779 assert(new_node);
780
781 if (!*first_node) {
782 if (!parent_node) {
783 /* no parent or siblings */
784 *first_node = new_node;
785 return LY_SUCCESS;
786 }
787
788 /* simply insert into parent, no other children */
789 if (key_or_value) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200790 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
Michal Vaskod59035b2020-07-08 12:00:06 +0200791 new_node->schema->name);
792 return LY_EINVAL;
793 }
Michal Vaskob104f112020-07-17 09:54:54 +0200794 return lyd_insert_child(parent_node, new_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200795 }
796
797 assert(!(*first_node)->parent || ((struct lyd_node *)(*first_node)->parent == parent_node));
798
Michal Vaskod59035b2020-07-08 12:00:06 +0200799 if (!lysc_is_userordered(new_node->schema)) {
Michal Vaskob104f112020-07-17 09:54:54 +0200800 /* simple insert */
801 return lyd_insert_sibling(*first_node, new_node, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200802 }
803
804 if (key_or_value) {
805 /* find the anchor sibling */
806 ret = lyd_find_sibling_val(*first_node, new_node->schema, key_or_value, 0, &anchor);
807 if (ret == LY_ENOTFOUND) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200808 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
Michal Vaskod59035b2020-07-08 12:00:06 +0200809 new_node->schema->name);
810 return LY_EINVAL;
811 } else if (ret) {
812 return ret;
813 }
814
815 /* insert after */
816 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
817 assert(new_node->prev == anchor);
818 if (*first_node == new_node) {
819 *first_node = anchor;
820 }
821 } else {
822 if ((*first_node)->schema->flags & LYS_KEY) {
823 assert(parent_node && (parent_node->schema->nodetype == LYS_LIST));
824
825 /* find last key */
826 anchor = *first_node;
827 while (anchor->next && (anchor->next->schema->flags & LYS_KEY)) {
828 anchor = anchor->next;
829 }
830 /* insert after the last key */
831 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
832 } else {
833 /* insert at the beginning */
834 LY_CHECK_RET(lyd_insert_before(*first_node, new_node));
835 *first_node = new_node;
836 }
837 }
838
839 return LY_SUCCESS;
840}
841
842/**
843 * @brief Apply diff subtree on data tree nodes, recursively.
844 *
845 * @param[in,out] first_node First sibling of the data tree.
846 * @param[in] parent_node Parent of the first sibling.
847 * @param[in] diff_node Current diff node.
Michal Vaskoe6323f62020-07-09 15:49:02 +0200848 * @param[in] diff_cb Optional diff callback.
849 * @param[in] cb_data User data for @p diff_cb.
Michal Vaskod59035b2020-07-08 12:00:06 +0200850 * @return LY_ERR value.
851 */
852static LY_ERR
853lyd_diff_apply_r(struct lyd_node **first_node, struct lyd_node *parent_node, const struct lyd_node *diff_node,
Radek Krejci0f969882020-08-21 16:56:47 +0200854 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskod59035b2020-07-08 12:00:06 +0200855{
856 LY_ERR ret;
857 struct lyd_node *match, *diff_child;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200858 const char *str_val;
859 enum lyd_diff_op op;
860 struct lyd_meta *meta;
Michal Vaskob7be7a82020-08-20 09:09:04 +0200861 const struct ly_ctx *ctx = LYD_CTX(diff_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200862
863 /* read all the valid attributes */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200864 LY_CHECK_RET(lyd_diff_get_op(diff_node, &op));
Michal Vaskod59035b2020-07-08 12:00:06 +0200865
Michal Vaskoe6323f62020-07-09 15:49:02 +0200866 /* handle specific user-ordered (leaf-)lists operations separately */
867 if (lysc_is_userordered(diff_node->schema) && ((op == LYD_DIFF_OP_CREATE) || (op == LYD_DIFF_OP_REPLACE))) {
868 if (op == LYD_DIFF_OP_REPLACE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200869 /* find the node (we must have some siblings because the node was only moved) */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200870 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200871 } else {
Michal Vasko3a41dff2020-07-15 14:30:28 +0200872 /* duplicate the node */
873 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +0200874 }
875
Michal Vaskoe6323f62020-07-09 15:49:02 +0200876 /* get "key" or "value" metadata string value */
877 meta = lyd_find_meta(diff_node->meta, NULL, diff_node->schema->nodetype == LYS_LIST ? "yang:key" : "yang:value");
Michal Vaskob7be7a82020-08-20 09:09:04 +0200878 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_node)), LY_EINT);
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200879 str_val = meta->value.canonical;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200880
Michal Vaskod59035b2020-07-08 12:00:06 +0200881 /* insert/move the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200882 if (str_val[0]) {
883 ret = lyd_diff_insert(first_node, parent_node, match, str_val);
Michal Vaskod59035b2020-07-08 12:00:06 +0200884 } else {
885 ret = lyd_diff_insert(first_node, parent_node, match, NULL);
886 }
887 if (ret) {
Michal Vaskoe6323f62020-07-09 15:49:02 +0200888 if (op == LYD_DIFF_OP_CREATE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200889 lyd_free_tree(match);
890 }
891 return ret;
892 }
893
894 goto next_iter_r;
895 }
896
897 /* apply operation */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200898 switch (op) {
899 case LYD_DIFF_OP_NONE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200900 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200901 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200902
903 if (match->schema->nodetype & LYD_NODE_TERM) {
904 /* special case of only dflt flag change */
905 if (diff_node->flags & LYD_DEFAULT) {
906 match->flags |= LYD_DEFAULT;
907 } else {
908 match->flags &= ~LYD_DEFAULT;
909 }
910 } else {
911 /* none operation on nodes without children is redundant and hence forbidden */
Michal Vasko8ee464a2020-08-11 14:12:50 +0200912 if (!LYD_CHILD_NO_KEYS(diff_node)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200913 LOGINT_RET(ctx);
914 }
915 }
916 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200917 case LYD_DIFF_OP_CREATE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200918 /* duplicate the node */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200919 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +0200920
921 /* insert it at the end */
922 ret = 0;
Michal Vaskob104f112020-07-17 09:54:54 +0200923 if (parent_node) {
924 ret = lyd_insert_child(parent_node, match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200925 } else {
Michal Vaskob104f112020-07-17 09:54:54 +0200926 ret = lyd_insert_sibling(*first_node, match, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200927 }
928 if (ret) {
929 lyd_free_tree(match);
930 return ret;
931 }
932
933 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200934 case LYD_DIFF_OP_DELETE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200935 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200936 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200937
938 /* remove it */
939 if ((match == *first_node) && !match->parent) {
940 assert(!parent_node);
941 /* we have removed the top-level node */
942 *first_node = (*first_node)->next;
943 }
944 lyd_free_tree(match);
945
946 /* we are not going recursively in this case, the whole subtree was already deleted */
947 return LY_SUCCESS;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200948 case LYD_DIFF_OP_REPLACE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200949 LY_CHECK_ERR_RET(diff_node->schema->nodetype != LYS_LEAF, LOGINT(ctx), LY_EINT);
950
951 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200952 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200953
954 /* update its value */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200955 ret = lyd_change_term(match, LYD_CANON_VALUE(diff_node));
Michal Vaskod59035b2020-07-08 12:00:06 +0200956 if (ret && (ret != LY_EEXIST)) {
957 LOGINT_RET(ctx);
958 }
959
960 /* with flags */
961 match->flags = diff_node->flags;
962 break;
963 default:
964 LOGINT_RET(ctx);
965 }
966
967next_iter_r:
968 if (diff_cb) {
969 /* call callback */
970 LY_CHECK_RET(diff_cb(diff_node, match, cb_data));
971 }
972
973 /* apply diff recursively */
Michal Vasko8ee464a2020-08-11 14:12:50 +0200974 LY_LIST_FOR(LYD_CHILD_NO_KEYS(diff_node), diff_child) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200975 LY_CHECK_RET(lyd_diff_apply_r(lyd_node_children_p(match), match, diff_child, diff_cb, cb_data));
976 }
977
978 return LY_SUCCESS;
979}
980
981API LY_ERR
982lyd_diff_apply_module(struct lyd_node **data, const struct lyd_node *diff, const struct lys_module *mod,
Radek Krejci0f969882020-08-21 16:56:47 +0200983 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskod59035b2020-07-08 12:00:06 +0200984{
985 const struct lyd_node *root;
986
987 LY_LIST_FOR(diff, root) {
988 if (mod && (lyd_owner_module(root) != mod)) {
989 /* skip data nodes from different modules */
990 continue;
991 }
992
993 /* apply relevant nodes from the diff datatree */
994 LY_CHECK_RET(lyd_diff_apply_r(data, NULL, root, diff_cb, cb_data));
995 }
996
997 return LY_SUCCESS;
998}
999
1000API LY_ERR
Michal Vasko3a41dff2020-07-15 14:30:28 +02001001lyd_diff_apply_all(struct lyd_node **data, const struct lyd_node *diff)
Michal Vaskod59035b2020-07-08 12:00:06 +02001002{
1003 return lyd_diff_apply_module(data, diff, NULL, NULL, NULL);
1004}
Michal Vaskoe6323f62020-07-09 15:49:02 +02001005
1006/**
1007 * @brief Update operations on a diff node when the new operation is NONE.
1008 *
1009 * @param[in] diff_match Node from the diff.
1010 * @param[in] cur_op Current operation of the diff node.
1011 * @param[in] src_diff Current source diff node.
1012 * @return LY_ERR value.
1013 */
1014static LY_ERR
1015lyd_diff_merge_none(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1016{
1017 switch (cur_op) {
1018 case LYD_DIFF_OP_NONE:
1019 case LYD_DIFF_OP_CREATE:
1020 case LYD_DIFF_OP_REPLACE:
1021 if (src_diff->schema->nodetype & LYD_NODE_TERM) {
1022 /* NONE on a term means only its dflt flag was changed */
1023 diff_match->flags &= ~LYD_DEFAULT;
1024 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1025 }
1026 break;
1027 default:
1028 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001029 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001030 }
1031
1032 return LY_SUCCESS;
1033}
1034
1035/**
1036 * @brief Remove an attribute from a node.
1037 *
1038 * @param[in] node Node with the metadata.
1039 * @param[in] name Metadata name.
1040 */
1041static void
1042lyd_diff_del_meta(struct lyd_node *node, const char *name)
1043{
1044 struct lyd_meta *meta;
1045
1046 LY_LIST_FOR(node->meta, meta) {
1047 if (!strcmp(meta->name, name) && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001048 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001049 return;
1050 }
1051 }
1052
1053 assert(0);
1054}
1055
1056/**
1057 * @brief Set a specific operation of a node. Delete the previous operation, if any.
1058 *
1059 * @param[in] node Node to change.
1060 * @param[in] op Operation to set.
1061 * @return LY_ERR value.
1062 */
1063static LY_ERR
1064lyd_diff_change_op(struct lyd_node *node, enum lyd_diff_op op)
1065{
1066 struct lyd_meta *meta;
1067
1068 LY_LIST_FOR(node->meta, meta) {
1069 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001070 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001071 break;
1072 }
1073 }
1074
Michal Vasko3a41dff2020-07-15 14:30:28 +02001075 return lyd_new_meta(node, NULL, "yang:operation", lyd_diff_op2str(op), NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001076}
1077
1078/**
1079 * @brief Update operations on a diff node when the new operation is REPLACE.
1080 *
1081 * @param[in] diff_match Node from the diff.
1082 * @param[in] cur_op Current operation of the diff node.
1083 * @param[in] src_diff Current source diff node.
1084 * @return LY_ERR value.
1085 */
1086static LY_ERR
1087lyd_diff_merge_replace(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1088{
1089 LY_ERR ret;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001090 const char *str_val, *meta_name;
1091 struct lyd_meta *meta;
1092 const struct lys_module *mod;
1093 const struct lyd_node_any *any;
1094
1095 /* get "yang" module for the metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001096 mod = ly_ctx_get_module_latest(LYD_CTX(diff_match), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001097 assert(mod);
1098
1099 switch (cur_op) {
1100 case LYD_DIFF_OP_REPLACE:
1101 case LYD_DIFF_OP_CREATE:
1102 switch (diff_match->schema->nodetype) {
1103 case LYS_LIST:
1104 case LYS_LEAFLIST:
Michal Vasko4231fb62020-07-13 13:54:47 +02001105 /* it was created/moved somewhere, but now it will be created/moved somewhere else,
Michal Vaskoe6323f62020-07-09 15:49:02 +02001106 * keep orig_key/orig_value (only replace oper) and replace key/value */
1107 assert(lysc_is_userordered(diff_match->schema));
1108 meta_name = (diff_match->schema->nodetype == LYS_LIST ? "key" : "value");
1109
1110 lyd_diff_del_meta(diff_match, meta_name);
1111 meta = lyd_find_meta(src_diff->meta, mod, meta_name);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001112 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001113 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001114 break;
1115 case LYS_LEAF:
1116 /* replaced with the exact same value, impossible */
Michal Vasko8f359bf2020-07-28 10:41:15 +02001117 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001118 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001119 }
1120
Michal Vaskoe6323f62020-07-09 15:49:02 +02001121 /* modify the node value */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001122 if (lyd_change_term(diff_match, LYD_CANON_VALUE(src_diff))) {
1123 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001124 }
1125
1126 /* compare values whether there is any change at all */
1127 meta = lyd_find_meta(diff_match->meta, mod, "orig-value");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001128 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_match)), LY_EINT);
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001129 str_val = meta->value.canonical;
Michal Vaskof937cfe2020-08-03 16:07:12 +02001130 ret = lyd_value_compare((struct lyd_node_term *)diff_match, str_val, strlen(str_val), NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001131 if (!ret) {
1132 /* values are the same, remove orig-value meta and set oper to NONE */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001133 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001134 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1135 }
1136
1137 /* modify the default flag */
1138 diff_match->flags &= ~LYD_DEFAULT;
1139 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1140 break;
1141 case LYS_ANYXML:
1142 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +02001143 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001144 /* replaced with the exact same value, impossible */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001145 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001146 }
1147
1148 /* modify the node value */
1149 any = (struct lyd_node_any *)src_diff;
1150 LY_CHECK_RET(lyd_any_copy_value(diff_match, &any->value, any->value_type));
1151 break;
1152 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001153 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001154 }
1155 break;
1156 case LYD_DIFF_OP_NONE:
1157 /* it is moved now */
1158 assert(lysc_is_userordered(diff_match->schema) && (diff_match->schema->nodetype == LYS_LIST));
1159
1160 /* change the operation */
1161 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1162
1163 /* set orig-key and key metadata */
1164 meta = lyd_find_meta(src_diff->meta, mod, "orig-key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001165 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001166 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001167
1168 meta = lyd_find_meta(src_diff->meta, mod, "key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001169 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001170 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001171 break;
1172 default:
1173 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001174 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001175 }
1176
1177 return LY_SUCCESS;
1178}
1179
1180/**
1181 * @brief Update operations in a diff node when the new operation is CREATE.
1182 *
1183 * @param[in] diff_match Node from the diff.
1184 * @param[in] cur_op Current operation of the diff node.
1185 * @param[in] src_diff Current source diff node.
1186 * @return LY_ERR value.
1187 */
1188static LY_ERR
1189lyd_diff_merge_create(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1190{
1191 struct lyd_node *child;
Michal Vasko5632e0d2020-07-31 14:13:37 +02001192 const struct lysc_node_leaf *sleaf;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001193
1194 switch (cur_op) {
1195 case LYD_DIFF_OP_DELETE:
Michal Vasko5632e0d2020-07-31 14:13:37 +02001196 if (diff_match->schema->nodetype == LYS_LEAF) {
1197 sleaf = (struct lysc_node_leaf *)diff_match->schema;
1198 } else {
1199 sleaf = NULL;
1200 }
1201
1202 if (sleaf && sleaf->dflt
1203 && !sleaf->dflt->realtype->plugin->compare(sleaf->dflt, &((struct lyd_node_term *)src_diff)->value)) {
1204 /* we deleted it, so a default value was in-use, and it matches the created value -> operation NONE */
1205 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1206
1207 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1208 /* add orig-dflt metadata */
1209 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
1210 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
1211 }
1212 } else if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001213 /* deleted + created -> operation NONE */
1214 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1215
1216 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1217 /* add orig-dflt metadata */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001218 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
1219 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001220 }
1221 } else {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001222 assert(sleaf);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001223 /* we deleted it, but it was created with a different value -> operation REPLACE */
1224 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
Michal Vasko5632e0d2020-07-31 14:13:37 +02001225 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001226
Michal Vasko5632e0d2020-07-31 14:13:37 +02001227 if (lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001228 /* current value is the previous one (meta) */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001229 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-value", LYD_CANON_VALUE(diff_match), NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001230
1231 /* update the value itself */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001232 LY_CHECK_RET(lyd_change_term(diff_match, LYD_CANON_VALUE(src_diff)));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001233 }
1234
1235 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1236 /* update dflt flag itself */
1237 diff_match->flags &= ~LYD_DEFAULT;
1238 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1239 } else {
1240 /* but the operation of its children should remain DELETE */
Michal Vasko8ee464a2020-08-11 14:12:50 +02001241 LY_LIST_FOR(LYD_CHILD_NO_KEYS(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001242 LY_CHECK_RET(lyd_diff_change_op(child, LYD_DIFF_OP_DELETE));
1243 }
1244 }
1245 break;
1246 default:
1247 /* create and replace operations are not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001248 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001249 }
1250
1251 return LY_SUCCESS;
1252}
1253
1254/**
1255 * @brief Update operations on a diff node when the new operation is DELETE.
1256 *
1257 * @param[in] diff_match Node from the diff.
1258 * @param[in] cur_op Current operation of the diff node.
1259 * @param[in] src_diff Current source diff node.
1260 * @return LY_ERR value.
1261 */
1262static LY_ERR
1263lyd_diff_merge_delete(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1264{
1265 struct lyd_node *next, *child;
1266
1267 /* we can delete only exact existing nodes */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001268 LY_CHECK_ERR_RET(lyd_compare_single(diff_match, src_diff, 0), LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001269
1270 switch (cur_op) {
1271 case LYD_DIFF_OP_CREATE:
1272 /* it was created, but then deleted -> set NONE operation */
1273 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1274
1275 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1276 /* add orig-default meta because it is expected */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001277 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
1278 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001279 } else {
1280 /* keep operation for all descendants (for now) */
Michal Vasko8ee464a2020-08-11 14:12:50 +02001281 LY_LIST_FOR(LYD_CHILD_NO_KEYS(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001282 LY_CHECK_RET(lyd_diff_change_op(child, cur_op));
1283 }
1284 }
1285 break;
1286 case LYD_DIFF_OP_REPLACE:
1287 /* similar to none operation but also remove the redundant attribute */
1288 lyd_diff_del_meta(diff_match, "orig-value");
Radek Krejci0f969882020-08-21 16:56:47 +02001289 /* fallthrough */
Michal Vaskoe6323f62020-07-09 15:49:02 +02001290 case LYD_DIFF_OP_NONE:
1291 /* it was not modified, but should be deleted -> set DELETE operation */
1292 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_DELETE));
1293
Michal Vasko5632e0d2020-07-31 14:13:37 +02001294 /* all descendants not in the diff will be deleted and redundant in the diff, so remove them */
Michal Vasko8ee464a2020-08-11 14:12:50 +02001295 LY_LIST_FOR_SAFE(LYD_CHILD_NO_KEYS(diff_match), next, child) {
1296 if (lyd_find_sibling_first(LYD_CHILD(src_diff), child, NULL) == LY_ENOTFOUND) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001297 lyd_free_tree(child);
1298 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001299 }
1300 break;
1301 default:
1302 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001303 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001304 }
1305
1306 return LY_SUCCESS;
1307}
1308
1309/**
1310 * @brief Check whether this diff node is redundant (does not change data).
1311 *
1312 * @param[in] diff Diff node.
1313 * @return 0 if not, non-zero if it is.
1314 */
1315static int
1316lyd_diff_is_redundant(struct lyd_node *diff)
1317{
1318 enum lyd_diff_op op;
1319 struct lyd_meta *meta, *orig_val_meta = NULL, *val_meta = NULL;
1320 struct lyd_node *child;
1321 const struct lys_module *mod;
1322 const char *str;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001323
1324 assert(diff);
1325
Michal Vasko8ee464a2020-08-11 14:12:50 +02001326 child = LYD_CHILD_NO_KEYS(diff);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001327 mod = ly_ctx_get_module_latest(LYD_CTX(diff), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001328 assert(mod);
1329
1330 /* get node operation */
Michal Vasko53bf6f22020-07-14 08:23:40 +02001331 LY_CHECK_RET(lyd_diff_get_op(diff, &op), 0);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001332
1333 if ((op == LYD_DIFF_OP_REPLACE) && lysc_is_userordered(diff->schema)) {
1334 /* check for redundant move */
1335 orig_val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "orig-key" : "orig-value"));
1336 val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "key" : "value"));
1337 assert(orig_val_meta && val_meta);
1338
1339 if (!lyd_compare_meta(orig_val_meta, val_meta)) {
1340 /* there is actually no move */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001341 lyd_free_meta_single(orig_val_meta);
1342 lyd_free_meta_single(val_meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001343 if (child) {
1344 /* change operation to NONE, we have siblings */
1345 lyd_diff_change_op(diff, LYD_DIFF_OP_NONE);
1346 return 0;
1347 }
1348
1349 /* redundant node, BUT !!
1350 * In diff the move operation is always converted to be INSERT_AFTER, which is fine
1351 * because the data that this is applied on should not change for the diff lifetime.
1352 * However, when we are merging 2 diffs, this conversion is actually lossy because
1353 * if the data change, the move operation can also change its meaning. In this specific
1354 * case the move operation will be lost. But it can be considered a feature, it is not supported.
1355 */
1356 return 1;
1357 }
1358 } else if ((op == LYD_DIFF_OP_NONE) && (diff->schema->nodetype & LYD_NODE_TERM)) {
1359 /* check whether at least the default flags are different */
1360 meta = lyd_find_meta(diff->meta, mod, "orig-default");
1361 assert(meta);
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001362 str = meta->value.canonical;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001363
1364 /* if previous and current dflt flags are the same, this node is redundant */
1365 if ((!strcmp(str, "true") && (diff->flags & LYD_DEFAULT)) || (!strcmp(str, "false") && !(diff->flags & LYD_DEFAULT))) {
1366 return 1;
1367 }
1368 return 0;
1369 }
1370
1371 if (!child && (op == LYD_DIFF_OP_NONE)) {
1372 return 1;
1373 }
1374
1375 return 0;
1376}
1377
1378/**
1379 * @brief Merge sysrepo diff with another diff, recursively.
1380 *
1381 * @param[in] src_diff Source diff node.
1382 * @param[in] diff_parent Current sysrepo diff parent.
1383 * @param[in] diff_cb Optional diff callback.
1384 * @param[in] cb_data User data for @p diff_cb.
1385 * @param[in,out] diff Diff root node.
1386 * @return LY_ERR value.
1387 */
1388static LY_ERR
1389lyd_diff_merge_r(const struct lyd_node *src_diff, struct lyd_node *diff_parent, lyd_diff_cb diff_cb, void *cb_data,
Radek Krejci0f969882020-08-21 16:56:47 +02001390 struct lyd_node **diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001391{
1392 LY_ERR ret = LY_SUCCESS;
1393 struct lyd_node *child, *diff_node = NULL;
1394 enum lyd_diff_op src_op, cur_op;
1395
1396 /* get source node operation */
1397 LY_CHECK_RET(lyd_diff_get_op(src_diff, &src_op));
1398
1399 /* find an equal node in the current diff */
Michal Vasko8ee464a2020-08-11 14:12:50 +02001400 lyd_diff_find_node(diff_parent ? LYD_CHILD_NO_KEYS(diff_parent) : *diff, src_diff, &diff_node);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001401
1402 if (diff_node) {
1403 /* get target (current) operation */
1404 LY_CHECK_RET(lyd_diff_get_op(diff_node, &cur_op));
1405
1406 /* merge operations */
1407 switch (src_op) {
1408 case LYD_DIFF_OP_REPLACE:
1409 ret = lyd_diff_merge_replace(diff_node, cur_op, src_diff);
1410 break;
1411 case LYD_DIFF_OP_CREATE:
1412 ret = lyd_diff_merge_create(diff_node, cur_op, src_diff);
1413 break;
1414 case LYD_DIFF_OP_DELETE:
1415 ret = lyd_diff_merge_delete(diff_node, cur_op, src_diff);
1416 break;
1417 case LYD_DIFF_OP_NONE:
1418 ret = lyd_diff_merge_none(diff_node, cur_op, src_diff);
1419 break;
1420 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001421 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001422 }
1423 if (ret) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001424 LOGERR(LYD_CTX(src_diff), LY_EOTHER, "Merging operation \"%s\" failed.", lyd_diff_op2str(src_op));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001425 return ret;
1426 }
1427
1428 if (diff_cb) {
1429 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001430 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001431 }
1432
1433 /* update diff parent */
1434 diff_parent = diff_node;
1435
1436 /* merge src_diff recursively */
Michal Vasko8ee464a2020-08-11 14:12:50 +02001437 LY_LIST_FOR(LYD_CHILD_NO_KEYS(src_diff), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001438 LY_CHECK_RET(lyd_diff_merge_r(child, diff_parent, diff_cb, cb_data, diff));
1439 }
1440 } else {
1441 /* add new diff node with all descendants */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001442 LY_CHECK_RET(lyd_dup_single(src_diff, (struct lyd_node_inner *)diff_parent, LYD_DUP_RECURSIVE, &diff_node));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001443
1444 /* insert node into diff if not already */
1445 if (!diff_parent) {
Michal Vaskob104f112020-07-17 09:54:54 +02001446 lyd_insert_sibling(*diff, diff_node, diff);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001447 }
1448
1449 /* update operation */
1450 LY_CHECK_RET(lyd_diff_change_op(diff_node, src_op));
1451
1452 if (diff_cb) {
1453 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001454 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001455 }
1456
1457 /* update diff parent */
1458 diff_parent = diff_node;
1459 }
1460
1461 /* remove any redundant nodes */
Michal Vaskob98d7082020-07-15 16:38:36 +02001462 if (lyd_diff_is_redundant(diff_parent)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001463 if (diff_parent == *diff) {
1464 *diff = (*diff)->next;
1465 }
1466 lyd_free_tree(diff_parent);
1467 }
1468
1469 return LY_SUCCESS;
1470}
1471
1472API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001473lyd_diff_merge_module(struct lyd_node **diff, const struct lyd_node *src_diff, const struct lys_module *mod,
Radek Krejci0f969882020-08-21 16:56:47 +02001474 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001475{
1476 const struct lyd_node *src_root;
1477
1478 LY_LIST_FOR(src_diff, src_root) {
1479 if (mod && (lyd_owner_module(src_root) != mod)) {
1480 /* skip data nodes from different modules */
1481 continue;
1482 }
1483
1484 /* apply relevant nodes from the diff datatree */
1485 LY_CHECK_RET(lyd_diff_merge_r(src_root, NULL, diff_cb, cb_data, diff));
1486 }
1487
1488 return LY_SUCCESS;
1489}
1490
1491API LY_ERR
Michal Vasko04f85912020-08-07 12:14:58 +02001492lyd_diff_merge_tree(struct lyd_node **diff_first, struct lyd_node *diff_parent, const struct lyd_node *src_sibling,
Radek Krejci0f969882020-08-21 16:56:47 +02001493 lyd_diff_cb diff_cb, void *cb_data)
Michal Vasko04f85912020-08-07 12:14:58 +02001494{
1495 if (!src_sibling) {
1496 return LY_SUCCESS;
1497 }
1498
1499 return lyd_diff_merge_r(src_sibling, diff_parent, diff_cb, cb_data, diff_first);
1500}
1501
1502API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001503lyd_diff_merge_all(struct lyd_node **diff, const struct lyd_node *src_diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001504{
Michal Vaskofb737aa2020-08-06 13:53:53 +02001505 return lyd_diff_merge_module(diff, src_diff, NULL, NULL, NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001506}
Michal Vasko4231fb62020-07-13 13:54:47 +02001507
1508static LY_ERR
1509lyd_diff_reverse_value(struct lyd_node *leaf, const struct lys_module *mod)
1510{
1511 LY_ERR ret = LY_SUCCESS;
1512 struct lyd_meta *meta;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001513 const char *val1 = NULL;
1514 char *val2;
1515 int flags;
Michal Vasko4231fb62020-07-13 13:54:47 +02001516
1517 meta = lyd_find_meta(leaf->meta, mod, "orig-value");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001518 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(leaf)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001519
1520 /* orig-value */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001521 val1 = meta->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001522
1523 /* current value */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001524 val2 = strdup(LYD_CANON_VALUE(leaf));
Michal Vasko4231fb62020-07-13 13:54:47 +02001525
1526 /* switch values, keep default flag */
1527 flags = leaf->flags;
1528 LY_CHECK_GOTO(ret = lyd_change_term(leaf, val1), cleanup);
1529 leaf->flags = flags;
1530 LY_CHECK_GOTO(ret = lyd_change_meta(meta, val2), cleanup);
1531
1532cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001533 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001534 return ret;
1535}
1536
1537static LY_ERR
1538lyd_diff_reverse_default(struct lyd_node *node, const struct lys_module *mod)
1539{
1540 struct lyd_meta *meta;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001541 int flag1, flag2;
Michal Vasko4231fb62020-07-13 13:54:47 +02001542
1543 meta = lyd_find_meta(node->meta, mod, "orig-default");
1544 if (!meta) {
1545 /* default flag did not change */
1546 return LY_SUCCESS;
1547 }
1548
1549 /* orig-default */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001550 if (meta->value.boolean) {
Michal Vasko4231fb62020-07-13 13:54:47 +02001551 flag1 = LYD_DEFAULT;
1552 } else {
1553 flag1 = 0;
1554 }
1555
1556 /* current default */
1557 flag2 = node->flags & LYD_DEFAULT;
1558
1559 /* switch defaults */
1560 node->flags &= ~LYD_DEFAULT;
1561 node->flags |= flag1;
1562 LY_CHECK_RET(lyd_change_meta(meta, flag2 ? "true" : "false"));
1563
1564 return LY_SUCCESS;
1565}
1566
1567static LY_ERR
1568lyd_diff_reverse_meta(struct lyd_node *node, const struct lys_module *mod, const char *name1, const char *name2)
1569{
1570 LY_ERR ret = LY_SUCCESS;
1571 struct lyd_meta *meta1, *meta2;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001572 const char *val1 = NULL;
1573 char *val2 = NULL;
Michal Vasko4231fb62020-07-13 13:54:47 +02001574
1575 meta1 = lyd_find_meta(node->meta, mod, name1);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001576 LY_CHECK_ERR_RET(!meta1, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001577
1578 meta2 = lyd_find_meta(node->meta, mod, name2);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001579 LY_CHECK_ERR_RET(!meta2, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001580
1581 /* value1 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001582 val1 = meta1->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001583
1584 /* value2 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001585 val2 = strdup(meta2->value.canonical);
Michal Vasko4231fb62020-07-13 13:54:47 +02001586
1587 /* switch values */
1588 LY_CHECK_GOTO(ret = lyd_change_meta(meta1, val2), cleanup);
1589 LY_CHECK_GOTO(ret = lyd_change_meta(meta2, val1), cleanup);
1590
1591cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001592 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001593 return ret;
1594}
1595
1596API LY_ERR
Michal Vasko66535812020-08-11 08:44:22 +02001597lyd_diff_reverse_all(const struct lyd_node *src_diff, struct lyd_node **diff)
Michal Vasko4231fb62020-07-13 13:54:47 +02001598{
1599 LY_ERR ret = LY_SUCCESS;
1600 const struct lys_module *mod;
Michal Vasko56daf732020-08-10 10:57:18 +02001601 struct lyd_node *root, *elem;
Michal Vasko4231fb62020-07-13 13:54:47 +02001602 enum lyd_diff_op op;
1603
1604 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
1605
1606 if (!src_diff) {
1607 *diff = NULL;
1608 return LY_SUCCESS;
1609 }
1610
1611 /* duplicate diff */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001612 LY_CHECK_RET(lyd_dup_siblings(src_diff, NULL, LYD_DUP_RECURSIVE, diff));
Michal Vasko4231fb62020-07-13 13:54:47 +02001613
1614 /* find module with metadata needed for later */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001615 mod = ly_ctx_get_module_latest(LYD_CTX(src_diff), "yang");
1616 LY_CHECK_ERR_GOTO(!mod, LOGINT(LYD_CTX(src_diff)); ret = LY_EINT, cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001617
1618 LY_LIST_FOR(*diff, root) {
Michal Vasko56daf732020-08-10 10:57:18 +02001619 LYD_TREE_DFS_BEGIN(root, elem) {
Michal Vasko4231fb62020-07-13 13:54:47 +02001620 /* find operation attribute, if any */
1621 LY_CHECK_GOTO(ret = lyd_diff_get_op(elem, &op), cleanup);
1622
1623 switch (op) {
1624 case LYD_DIFF_OP_CREATE:
1625 /* reverse create to delete */
1626 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_DELETE), cleanup);
1627 break;
1628 case LYD_DIFF_OP_DELETE:
1629 /* reverse delete to create */
1630 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_CREATE), cleanup);
1631 break;
1632 case LYD_DIFF_OP_REPLACE:
1633 switch (elem->schema->nodetype) {
1634 case LYS_LEAF:
1635 /* leaf value change */
1636 LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup);
1637 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1638 break;
1639 case LYS_LEAFLIST:
1640 /* leaf-list move */
1641 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1642 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-value", "value"), cleanup);
1643 break;
1644 case LYS_LIST:
1645 /* list move */
1646 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-key", "key"), cleanup);
1647 break;
1648 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001649 LOGINT(LYD_CTX(src_diff));
Michal Vasko4231fb62020-07-13 13:54:47 +02001650 ret = LY_EINT;
1651 goto cleanup;
1652 }
1653 break;
1654 case LYD_DIFF_OP_NONE:
1655 switch (elem->schema->nodetype) {
1656 case LYS_LEAF:
1657 case LYS_LEAFLIST:
1658 /* default flag change */
1659 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1660 break;
1661 default:
1662 /* nothing to do */
1663 break;
1664 }
1665 break;
1666 default:
1667 /* nothing to do */
1668 break;
1669 }
1670
Michal Vasko56daf732020-08-10 10:57:18 +02001671 LYD_TREE_DFS_END(root, elem);
Michal Vasko4231fb62020-07-13 13:54:47 +02001672 }
1673 }
1674
1675cleanup:
1676 if (ret) {
1677 lyd_free_siblings(*diff);
1678 *diff = NULL;
1679 }
1680 return ret;
1681}