blob: ee63e7146df44ebd8f0344362de98237efe80d3d [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 */
Radek Krejcia1c1e542020-09-29 16:06:52 +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,
Michal Vasko69730152020-10-09 16:30:07 +0200106 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 }
Michal Vaskod989ba02020-08-24 10:59:24 +0200204 for ( ; iter; iter = iter->next) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200205 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
Radek Krejci1deb5be2020-08-26 16:43:36 +0200234lyd_diff_userord_attrs(const struct lyd_node *first, const struct lyd_node *second, uint16_t 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 Vasko69730152020-10-09 16:30:07 +0200296 if ((options & LYD_DIFF_DEFAULTS) && (schema->nodetype == LYS_LEAFLIST) &&
297 ((*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,
Michal Vasko69730152020-10-09 16:30:07 +0200356 ; , LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200357 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
Radek Krejci1deb5be2020-08-26 16:43:36 +0200397lyd_diff_attrs(const struct lyd_node *first, const struct lyd_node *second, uint16_t 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 Vasko69730152020-10-09 16:30:07 +0200457 if ((options & LYD_DIFF_DEFAULTS) && (schema->nodetype & LYD_NODE_TERM) &&
458 ((*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
Radek Krejci857189e2020-09-01 13:26:36 +0200519lyd_diff_siblings_r(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, ly_bool 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,
Michal Vasko69730152020-10-09 16:30:07 +0200560 &value, &orig_value, &key, &orig_key), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200561
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) {
Radek Krejcia1c1e542020-09-29 16:06:52 +0200594 LY_CHECK_GOTO(lyd_diff_siblings_r(lyd_child_no_keys(iter_first), lyd_child_no_keys(match_second), options,
Michal Vasko69730152020-10-09 16:30:07 +0200595 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,
Michal Vasko69730152020-10-09 16:30:07 +0200630 &value, &orig_value, &key, &orig_key);
Michal Vaskod59035b2020-07-08 12:00:06 +0200631
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
Radek Krejci857189e2020-09-01 13:26:36 +0200672lyd_diff(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, ly_bool 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
Radek Krejci1deb5be2020-08-26 16:43:36 +0200697lyd_diff_tree(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, struct lyd_node **diff)
Michal Vasko3a41dff2020-07-15 14:30:28 +0200698{
699 return lyd_diff(first, second, options, 1, diff);
700}
701
702API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200703lyd_diff_siblings(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, struct lyd_node **diff)
Michal Vasko3a41dff2020-07-15 14:30:28 +0200704{
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 Vasko69730152020-10-09 16:30:07 +0200791 new_node->schema->name);
Michal Vaskod59035b2020-07-08 12:00:06 +0200792 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 Vasko69730152020-10-09 16:30:07 +0200809 new_node->schema->name);
Michal Vaskod59035b2020-07-08 12:00:06 +0200810 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 */
Radek Krejcia1c1e542020-09-29 16:06:52 +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 */
Radek Krejcia1c1e542020-09-29 16:06:52 +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
Michal Vasko8caadab2020-11-05 17:38:15 +01001126 if (cur_op == LYD_DIFF_OP_REPLACE) {
1127 /* compare values whether there is any change at all */
1128 meta = lyd_find_meta(diff_match->meta, mod, "orig-value");
1129 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_match)), LY_EINT);
1130 str_val = meta->value.canonical;
1131 ret = lyd_value_compare((struct lyd_node_term *)diff_match, str_val, strlen(str_val));
1132 if (!ret) {
1133 /* values are the same, remove orig-value meta and set oper to NONE */
1134 lyd_free_meta_single(meta);
1135 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1136 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001137 }
1138
1139 /* modify the default flag */
1140 diff_match->flags &= ~LYD_DEFAULT;
1141 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1142 break;
1143 case LYS_ANYXML:
1144 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +02001145 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001146 /* replaced with the exact same value, impossible */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001147 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001148 }
1149
1150 /* modify the node value */
1151 any = (struct lyd_node_any *)src_diff;
1152 LY_CHECK_RET(lyd_any_copy_value(diff_match, &any->value, any->value_type));
1153 break;
1154 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001155 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001156 }
1157 break;
1158 case LYD_DIFF_OP_NONE:
1159 /* it is moved now */
1160 assert(lysc_is_userordered(diff_match->schema) && (diff_match->schema->nodetype == LYS_LIST));
1161
1162 /* change the operation */
1163 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1164
1165 /* set orig-key and key metadata */
1166 meta = lyd_find_meta(src_diff->meta, mod, "orig-key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001167 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001168 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001169
1170 meta = lyd_find_meta(src_diff->meta, mod, "key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001171 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001172 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001173 break;
1174 default:
1175 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001176 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001177 }
1178
1179 return LY_SUCCESS;
1180}
1181
1182/**
1183 * @brief Update operations in a diff node when the new operation is CREATE.
1184 *
1185 * @param[in] diff_match Node from the diff.
1186 * @param[in] cur_op Current operation of the diff node.
1187 * @param[in] src_diff Current source diff node.
1188 * @return LY_ERR value.
1189 */
1190static LY_ERR
1191lyd_diff_merge_create(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1192{
1193 struct lyd_node *child;
Michal Vasko5632e0d2020-07-31 14:13:37 +02001194 const struct lysc_node_leaf *sleaf;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001195
1196 switch (cur_op) {
1197 case LYD_DIFF_OP_DELETE:
Michal Vasko5632e0d2020-07-31 14:13:37 +02001198 if (diff_match->schema->nodetype == LYS_LEAF) {
1199 sleaf = (struct lysc_node_leaf *)diff_match->schema;
1200 } else {
1201 sleaf = NULL;
1202 }
1203
Michal Vasko69730152020-10-09 16:30:07 +02001204 if (sleaf && sleaf->dflt &&
1205 !sleaf->dflt->realtype->plugin->compare(sleaf->dflt, &((struct lyd_node_term *)src_diff)->value)) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001206 /* we deleted it, so a default value was in-use, and it matches the created value -> operation NONE */
1207 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1208
1209 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1210 /* add orig-dflt metadata */
1211 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
Michal Vasko69730152020-10-09 16:30:07 +02001212 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vasko5632e0d2020-07-31 14:13:37 +02001213 }
1214 } else if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001215 /* deleted + created -> operation NONE */
1216 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1217
1218 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1219 /* add orig-dflt metadata */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001220 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
Michal Vasko69730152020-10-09 16:30:07 +02001221 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001222 }
1223 } else {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001224 assert(sleaf);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001225 /* we deleted it, but it was created with a different value -> operation REPLACE */
1226 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
Michal Vasko5632e0d2020-07-31 14:13:37 +02001227 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001228
Michal Vasko5632e0d2020-07-31 14:13:37 +02001229 if (lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001230 /* current value is the previous one (meta) */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001231 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 +02001232
1233 /* update the value itself */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001234 LY_CHECK_RET(lyd_change_term(diff_match, LYD_CANON_VALUE(src_diff)));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001235 }
1236
1237 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1238 /* update dflt flag itself */
1239 diff_match->flags &= ~LYD_DEFAULT;
1240 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1241 } else {
1242 /* but the operation of its children should remain DELETE */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001243 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001244 LY_CHECK_RET(lyd_diff_change_op(child, LYD_DIFF_OP_DELETE));
1245 }
1246 }
1247 break;
1248 default:
1249 /* create and replace operations are not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001250 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001251 }
1252
1253 return LY_SUCCESS;
1254}
1255
1256/**
1257 * @brief Update operations on a diff node when the new operation is DELETE.
1258 *
1259 * @param[in] diff_match Node from the diff.
1260 * @param[in] cur_op Current operation of the diff node.
1261 * @param[in] src_diff Current source diff node.
1262 * @return LY_ERR value.
1263 */
1264static LY_ERR
1265lyd_diff_merge_delete(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1266{
1267 struct lyd_node *next, *child;
1268
1269 /* we can delete only exact existing nodes */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001270 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 +02001271
1272 switch (cur_op) {
1273 case LYD_DIFF_OP_CREATE:
1274 /* it was created, but then deleted -> set NONE operation */
1275 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1276
1277 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1278 /* add orig-default meta because it is expected */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001279 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
Michal Vasko69730152020-10-09 16:30:07 +02001280 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001281 } else {
1282 /* keep operation for all descendants (for now) */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001283 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001284 LY_CHECK_RET(lyd_diff_change_op(child, cur_op));
1285 }
1286 }
1287 break;
1288 case LYD_DIFF_OP_REPLACE:
1289 /* similar to none operation but also remove the redundant attribute */
1290 lyd_diff_del_meta(diff_match, "orig-value");
Radek Krejci0f969882020-08-21 16:56:47 +02001291 /* fallthrough */
Michal Vaskoe6323f62020-07-09 15:49:02 +02001292 case LYD_DIFF_OP_NONE:
1293 /* it was not modified, but should be deleted -> set DELETE operation */
1294 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_DELETE));
1295
Michal Vasko5632e0d2020-07-31 14:13:37 +02001296 /* all descendants not in the diff will be deleted and redundant in the diff, so remove them */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001297 LY_LIST_FOR_SAFE(lyd_child_no_keys(diff_match), next, child) {
1298 if (lyd_find_sibling_first(lyd_child(src_diff), child, NULL) == LY_ENOTFOUND) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001299 lyd_free_tree(child);
1300 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001301 }
1302 break;
1303 default:
1304 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001305 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001306 }
1307
1308 return LY_SUCCESS;
1309}
1310
1311/**
1312 * @brief Check whether this diff node is redundant (does not change data).
1313 *
1314 * @param[in] diff Diff node.
1315 * @return 0 if not, non-zero if it is.
1316 */
1317static int
1318lyd_diff_is_redundant(struct lyd_node *diff)
1319{
1320 enum lyd_diff_op op;
1321 struct lyd_meta *meta, *orig_val_meta = NULL, *val_meta = NULL;
1322 struct lyd_node *child;
1323 const struct lys_module *mod;
1324 const char *str;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001325
1326 assert(diff);
1327
Radek Krejcia1c1e542020-09-29 16:06:52 +02001328 child = lyd_child_no_keys(diff);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001329 mod = ly_ctx_get_module_latest(LYD_CTX(diff), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001330 assert(mod);
1331
1332 /* get node operation */
Michal Vasko53bf6f22020-07-14 08:23:40 +02001333 LY_CHECK_RET(lyd_diff_get_op(diff, &op), 0);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001334
1335 if ((op == LYD_DIFF_OP_REPLACE) && lysc_is_userordered(diff->schema)) {
1336 /* check for redundant move */
1337 orig_val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "orig-key" : "orig-value"));
1338 val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "key" : "value"));
1339 assert(orig_val_meta && val_meta);
1340
1341 if (!lyd_compare_meta(orig_val_meta, val_meta)) {
1342 /* there is actually no move */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001343 lyd_free_meta_single(orig_val_meta);
1344 lyd_free_meta_single(val_meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001345 if (child) {
1346 /* change operation to NONE, we have siblings */
1347 lyd_diff_change_op(diff, LYD_DIFF_OP_NONE);
1348 return 0;
1349 }
1350
1351 /* redundant node, BUT !!
1352 * In diff the move operation is always converted to be INSERT_AFTER, which is fine
1353 * because the data that this is applied on should not change for the diff lifetime.
1354 * However, when we are merging 2 diffs, this conversion is actually lossy because
1355 * if the data change, the move operation can also change its meaning. In this specific
1356 * case the move operation will be lost. But it can be considered a feature, it is not supported.
1357 */
1358 return 1;
1359 }
1360 } else if ((op == LYD_DIFF_OP_NONE) && (diff->schema->nodetype & LYD_NODE_TERM)) {
1361 /* check whether at least the default flags are different */
1362 meta = lyd_find_meta(diff->meta, mod, "orig-default");
1363 assert(meta);
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001364 str = meta->value.canonical;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001365
1366 /* if previous and current dflt flags are the same, this node is redundant */
1367 if ((!strcmp(str, "true") && (diff->flags & LYD_DEFAULT)) || (!strcmp(str, "false") && !(diff->flags & LYD_DEFAULT))) {
1368 return 1;
1369 }
1370 return 0;
1371 }
1372
1373 if (!child && (op == LYD_DIFF_OP_NONE)) {
1374 return 1;
1375 }
1376
1377 return 0;
1378}
1379
1380/**
1381 * @brief Merge sysrepo diff with another diff, recursively.
1382 *
1383 * @param[in] src_diff Source diff node.
1384 * @param[in] diff_parent Current sysrepo diff parent.
1385 * @param[in] diff_cb Optional diff callback.
1386 * @param[in] cb_data User data for @p diff_cb.
1387 * @param[in,out] diff Diff root node.
1388 * @return LY_ERR value.
1389 */
1390static LY_ERR
1391lyd_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 +02001392 struct lyd_node **diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001393{
1394 LY_ERR ret = LY_SUCCESS;
1395 struct lyd_node *child, *diff_node = NULL;
1396 enum lyd_diff_op src_op, cur_op;
1397
1398 /* get source node operation */
1399 LY_CHECK_RET(lyd_diff_get_op(src_diff, &src_op));
1400
1401 /* find an equal node in the current diff */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001402 lyd_diff_find_node(diff_parent ? lyd_child_no_keys(diff_parent) : *diff, src_diff, &diff_node);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001403
1404 if (diff_node) {
1405 /* get target (current) operation */
1406 LY_CHECK_RET(lyd_diff_get_op(diff_node, &cur_op));
1407
1408 /* merge operations */
1409 switch (src_op) {
1410 case LYD_DIFF_OP_REPLACE:
1411 ret = lyd_diff_merge_replace(diff_node, cur_op, src_diff);
1412 break;
1413 case LYD_DIFF_OP_CREATE:
1414 ret = lyd_diff_merge_create(diff_node, cur_op, src_diff);
1415 break;
1416 case LYD_DIFF_OP_DELETE:
1417 ret = lyd_diff_merge_delete(diff_node, cur_op, src_diff);
1418 break;
1419 case LYD_DIFF_OP_NONE:
1420 ret = lyd_diff_merge_none(diff_node, cur_op, src_diff);
1421 break;
1422 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001423 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001424 }
1425 if (ret) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001426 LOGERR(LYD_CTX(src_diff), LY_EOTHER, "Merging operation \"%s\" failed.", lyd_diff_op2str(src_op));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001427 return ret;
1428 }
1429
1430 if (diff_cb) {
1431 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001432 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001433 }
1434
1435 /* update diff parent */
1436 diff_parent = diff_node;
1437
1438 /* merge src_diff recursively */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001439 LY_LIST_FOR(lyd_child_no_keys(src_diff), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001440 LY_CHECK_RET(lyd_diff_merge_r(child, diff_parent, diff_cb, cb_data, diff));
1441 }
1442 } else {
1443 /* add new diff node with all descendants */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001444 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 +02001445
1446 /* insert node into diff if not already */
1447 if (!diff_parent) {
Michal Vaskob104f112020-07-17 09:54:54 +02001448 lyd_insert_sibling(*diff, diff_node, diff);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001449 }
1450
1451 /* update operation */
1452 LY_CHECK_RET(lyd_diff_change_op(diff_node, src_op));
1453
1454 if (diff_cb) {
1455 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001456 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001457 }
1458
1459 /* update diff parent */
1460 diff_parent = diff_node;
1461 }
1462
1463 /* remove any redundant nodes */
Michal Vaskob98d7082020-07-15 16:38:36 +02001464 if (lyd_diff_is_redundant(diff_parent)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001465 if (diff_parent == *diff) {
1466 *diff = (*diff)->next;
1467 }
1468 lyd_free_tree(diff_parent);
1469 }
1470
1471 return LY_SUCCESS;
1472}
1473
1474API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001475lyd_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 +02001476 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001477{
1478 const struct lyd_node *src_root;
1479
1480 LY_LIST_FOR(src_diff, src_root) {
1481 if (mod && (lyd_owner_module(src_root) != mod)) {
1482 /* skip data nodes from different modules */
1483 continue;
1484 }
1485
1486 /* apply relevant nodes from the diff datatree */
1487 LY_CHECK_RET(lyd_diff_merge_r(src_root, NULL, diff_cb, cb_data, diff));
1488 }
1489
1490 return LY_SUCCESS;
1491}
1492
1493API LY_ERR
Michal Vasko04f85912020-08-07 12:14:58 +02001494lyd_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 +02001495 lyd_diff_cb diff_cb, void *cb_data)
Michal Vasko04f85912020-08-07 12:14:58 +02001496{
1497 if (!src_sibling) {
1498 return LY_SUCCESS;
1499 }
1500
1501 return lyd_diff_merge_r(src_sibling, diff_parent, diff_cb, cb_data, diff_first);
1502}
1503
1504API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001505lyd_diff_merge_all(struct lyd_node **diff, const struct lyd_node *src_diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001506{
Michal Vaskofb737aa2020-08-06 13:53:53 +02001507 return lyd_diff_merge_module(diff, src_diff, NULL, NULL, NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001508}
Michal Vasko4231fb62020-07-13 13:54:47 +02001509
1510static LY_ERR
1511lyd_diff_reverse_value(struct lyd_node *leaf, const struct lys_module *mod)
1512{
1513 LY_ERR ret = LY_SUCCESS;
1514 struct lyd_meta *meta;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001515 const char *val1 = NULL;
1516 char *val2;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001517 uint32_t flags;
Michal Vasko4231fb62020-07-13 13:54:47 +02001518
1519 meta = lyd_find_meta(leaf->meta, mod, "orig-value");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001520 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(leaf)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001521
1522 /* orig-value */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001523 val1 = meta->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001524
1525 /* current value */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001526 val2 = strdup(LYD_CANON_VALUE(leaf));
Michal Vasko4231fb62020-07-13 13:54:47 +02001527
1528 /* switch values, keep default flag */
1529 flags = leaf->flags;
1530 LY_CHECK_GOTO(ret = lyd_change_term(leaf, val1), cleanup);
1531 leaf->flags = flags;
1532 LY_CHECK_GOTO(ret = lyd_change_meta(meta, val2), cleanup);
1533
1534cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001535 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001536 return ret;
1537}
1538
1539static LY_ERR
1540lyd_diff_reverse_default(struct lyd_node *node, const struct lys_module *mod)
1541{
1542 struct lyd_meta *meta;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001543 uint32_t flag1, flag2;
Michal Vasko4231fb62020-07-13 13:54:47 +02001544
1545 meta = lyd_find_meta(node->meta, mod, "orig-default");
1546 if (!meta) {
1547 /* default flag did not change */
1548 return LY_SUCCESS;
1549 }
1550
1551 /* orig-default */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001552 if (meta->value.boolean) {
Michal Vasko4231fb62020-07-13 13:54:47 +02001553 flag1 = LYD_DEFAULT;
1554 } else {
1555 flag1 = 0;
1556 }
1557
1558 /* current default */
1559 flag2 = node->flags & LYD_DEFAULT;
1560
1561 /* switch defaults */
1562 node->flags &= ~LYD_DEFAULT;
1563 node->flags |= flag1;
1564 LY_CHECK_RET(lyd_change_meta(meta, flag2 ? "true" : "false"));
1565
1566 return LY_SUCCESS;
1567}
1568
1569static LY_ERR
1570lyd_diff_reverse_meta(struct lyd_node *node, const struct lys_module *mod, const char *name1, const char *name2)
1571{
1572 LY_ERR ret = LY_SUCCESS;
1573 struct lyd_meta *meta1, *meta2;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001574 const char *val1 = NULL;
1575 char *val2 = NULL;
Michal Vasko4231fb62020-07-13 13:54:47 +02001576
1577 meta1 = lyd_find_meta(node->meta, mod, name1);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001578 LY_CHECK_ERR_RET(!meta1, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001579
1580 meta2 = lyd_find_meta(node->meta, mod, name2);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001581 LY_CHECK_ERR_RET(!meta2, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001582
1583 /* value1 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001584 val1 = meta1->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001585
1586 /* value2 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001587 val2 = strdup(meta2->value.canonical);
Michal Vasko4231fb62020-07-13 13:54:47 +02001588
1589 /* switch values */
1590 LY_CHECK_GOTO(ret = lyd_change_meta(meta1, val2), cleanup);
1591 LY_CHECK_GOTO(ret = lyd_change_meta(meta2, val1), cleanup);
1592
1593cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001594 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001595 return ret;
1596}
1597
1598API LY_ERR
Michal Vasko66535812020-08-11 08:44:22 +02001599lyd_diff_reverse_all(const struct lyd_node *src_diff, struct lyd_node **diff)
Michal Vasko4231fb62020-07-13 13:54:47 +02001600{
1601 LY_ERR ret = LY_SUCCESS;
1602 const struct lys_module *mod;
Michal Vasko56daf732020-08-10 10:57:18 +02001603 struct lyd_node *root, *elem;
Michal Vasko4231fb62020-07-13 13:54:47 +02001604 enum lyd_diff_op op;
1605
1606 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
1607
1608 if (!src_diff) {
1609 *diff = NULL;
1610 return LY_SUCCESS;
1611 }
1612
1613 /* duplicate diff */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001614 LY_CHECK_RET(lyd_dup_siblings(src_diff, NULL, LYD_DUP_RECURSIVE, diff));
Michal Vasko4231fb62020-07-13 13:54:47 +02001615
1616 /* find module with metadata needed for later */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001617 mod = ly_ctx_get_module_latest(LYD_CTX(src_diff), "yang");
1618 LY_CHECK_ERR_GOTO(!mod, LOGINT(LYD_CTX(src_diff)); ret = LY_EINT, cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001619
1620 LY_LIST_FOR(*diff, root) {
Michal Vasko56daf732020-08-10 10:57:18 +02001621 LYD_TREE_DFS_BEGIN(root, elem) {
Michal Vasko4231fb62020-07-13 13:54:47 +02001622 /* find operation attribute, if any */
1623 LY_CHECK_GOTO(ret = lyd_diff_get_op(elem, &op), cleanup);
1624
1625 switch (op) {
1626 case LYD_DIFF_OP_CREATE:
1627 /* reverse create to delete */
1628 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_DELETE), cleanup);
1629 break;
1630 case LYD_DIFF_OP_DELETE:
1631 /* reverse delete to create */
1632 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_CREATE), cleanup);
1633 break;
1634 case LYD_DIFF_OP_REPLACE:
1635 switch (elem->schema->nodetype) {
1636 case LYS_LEAF:
1637 /* leaf value change */
1638 LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup);
1639 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1640 break;
1641 case LYS_LEAFLIST:
1642 /* leaf-list move */
1643 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1644 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-value", "value"), cleanup);
1645 break;
1646 case LYS_LIST:
1647 /* list move */
1648 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-key", "key"), cleanup);
1649 break;
1650 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001651 LOGINT(LYD_CTX(src_diff));
Michal Vasko4231fb62020-07-13 13:54:47 +02001652 ret = LY_EINT;
1653 goto cleanup;
1654 }
1655 break;
1656 case LYD_DIFF_OP_NONE:
1657 switch (elem->schema->nodetype) {
1658 case LYS_LEAF:
1659 case LYS_LEAFLIST:
1660 /* default flag change */
1661 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1662 break;
1663 default:
1664 /* nothing to do */
1665 break;
1666 }
1667 break;
1668 default:
1669 /* nothing to do */
1670 break;
1671 }
1672
Michal Vasko56daf732020-08-10 10:57:18 +02001673 LYD_TREE_DFS_END(root, elem);
Michal Vasko4231fb62020-07-13 13:54:47 +02001674 }
1675 }
1676
1677cleanup:
1678 if (ret) {
1679 lyd_free_siblings(*diff);
1680 *diff = NULL;
1681 }
1682 return ret;
1683}