blob: c2e3935e8cc0277e91d5812eb9883ab21c418ffa [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>
Radek Krejci47fab892020-11-05 17:02:41 +010021#include <stdlib.h>
Michal Vaskod59035b2020-07-08 12:00:06 +020022#include <string.h>
23
24#include "common.h"
Radek Krejci47fab892020-11-05 17:02:41 +010025#include "context.h"
Michal Vaskod59035b2020-07-08 12:00:06 +020026#include "log.h"
Radek Krejci47fab892020-11-05 17:02:41 +010027#include "plugins_types.h"
28#include "set.h"
29#include "tree.h"
30#include "tree_data.h"
Michal Vaskod59035b2020-07-08 12:00:06 +020031#include "tree_data_internal.h"
32#include "tree_schema.h"
33#include "tree_schema_internal.h"
34
35static const char *
36lyd_diff_op2str(enum lyd_diff_op op)
37{
38 switch (op) {
39 case LYD_DIFF_OP_CREATE:
40 return "create";
41 case LYD_DIFF_OP_DELETE:
42 return "delete";
43 case LYD_DIFF_OP_REPLACE:
44 return "replace";
45 case LYD_DIFF_OP_NONE:
46 return "none";
47 }
48
49 LOGINT(NULL);
50 return NULL;
51}
52
Michal Vaskoe6323f62020-07-09 15:49:02 +020053static enum lyd_diff_op
54lyd_diff_str2op(const char *str)
55{
56 switch (str[0]) {
57 case 'c':
58 assert(!strcmp(str, "create"));
59 return LYD_DIFF_OP_CREATE;
60 case 'd':
61 assert(!strcmp(str, "delete"));
62 return LYD_DIFF_OP_DELETE;
63 case 'r':
64 assert(!strcmp(str, "replace"));
65 return LYD_DIFF_OP_REPLACE;
66 case 'n':
67 assert(!strcmp(str, "none"));
68 return LYD_DIFF_OP_NONE;
69 }
70
71 LOGINT(NULL);
72 return 0;
73}
74
Michal Vaskod59035b2020-07-08 12:00:06 +020075LY_ERR
76lyd_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 +020077 const char *key, const char *value, const char *orig_key, struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +020078{
79 struct lyd_node *dup, *siblings, *match = NULL, *diff_parent = NULL;
80 const struct lyd_node *parent = NULL;
81 const struct lys_module *yang_mod;
82
83 assert(diff);
84
85 /* find the first existing parent */
86 siblings = *diff;
87 while (1) {
88 /* find next node parent */
89 parent = node;
90 while (parent->parent && (!diff_parent || (parent->parent->schema != diff_parent->schema))) {
91 parent = (struct lyd_node *)parent->parent;
92 }
93 if (parent == node) {
94 /* no more parents to find */
95 break;
96 }
97
98 /* check whether it exists in the diff */
99 if (lyd_find_sibling_first(siblings, parent, &match)) {
100 break;
101 }
102
103 /* another parent found */
104 diff_parent = match;
105
106 /* move down in the diff */
Radek Krejcia1c1e542020-09-29 16:06:52 +0200107 siblings = lyd_child_no_keys(match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200108 }
109
110 /* duplicate the subtree (and connect to the diff if possible) */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200111 LY_CHECK_RET(lyd_dup_single(node, (struct lyd_node_inner *)diff_parent,
Michal Vasko69730152020-10-09 16:30:07 +0200112 LYD_DUP_RECURSIVE | LYD_DUP_NO_META | LYD_DUP_WITH_PARENTS, &dup));
Michal Vaskod59035b2020-07-08 12:00:06 +0200113
114 /* find the first duplicated parent */
115 if (!diff_parent) {
116 diff_parent = (struct lyd_node *)dup->parent;
117 while (diff_parent && diff_parent->parent) {
118 diff_parent = (struct lyd_node *)diff_parent->parent;
119 }
120 } else {
121 diff_parent = (struct lyd_node *)dup;
122 while (diff_parent->parent && (diff_parent->parent->schema == parent->schema)) {
123 diff_parent = (struct lyd_node *)diff_parent->parent;
124 }
125 }
126
127 /* no parent existed, must be manually connected */
128 if (!diff_parent) {
129 /* there actually was no parent to duplicate */
Michal Vaskob104f112020-07-17 09:54:54 +0200130 lyd_insert_sibling(*diff, dup, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200131 } else if (!diff_parent->parent) {
Michal Vaskob104f112020-07-17 09:54:54 +0200132 lyd_insert_sibling(*diff, diff_parent, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200133 }
134
135 /* get module with the operation metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200136 yang_mod = LYD_CTX(node)->list.objs[1];
Michal Vaskod59035b2020-07-08 12:00:06 +0200137 assert(!strcmp(yang_mod->name, "yang"));
138
139 /* add parent operation, if any */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200140 if (diff_parent && (diff_parent != dup)) {
141 LY_CHECK_RET(lyd_new_meta(diff_parent, yang_mod, "operation", "none", NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200142 }
143
144 /* add subtree operation */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200145 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "operation", lyd_diff_op2str(op), NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200146
147 /* orig-default */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200148 if (orig_default) {
149 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "orig-default", orig_default, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200150 }
151
152 /* orig-value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200153 if (orig_value) {
154 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "orig-value", orig_value, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200155 }
156
157 /* key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200158 if (key) {
159 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "key", key, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200160 }
161
162 /* value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200163 if (value) {
164 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "value", value, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200165 }
166
167 /* orig-key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200168 if (orig_key) {
169 LY_CHECK_RET(lyd_new_meta(dup, yang_mod, "orig-key", orig_key, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200170 }
171
172 return LY_SUCCESS;
173}
174
175/**
176 * @brief Get a userord entry for a specific user-ordered list/leaf-list. Create if does not exist yet.
177 *
178 * @param[in] first
179 * @param[in] schema Schema node of the list/leaf-list.
180 * @param[in,out] userord Sized array of userord items.
181 * @return Userord item for all the user-ordered list/leaf-list instances.
182 */
183static struct lyd_diff_userord *
184lyd_diff_userord_get(const struct lyd_node *first, const struct lysc_node *schema, struct lyd_diff_userord **userord)
185{
186 struct lyd_diff_userord *item;
187 const struct lyd_node *iter, **node;
188 LY_ARRAY_COUNT_TYPE u;
189
190 LY_ARRAY_FOR(*userord, u) {
191 if ((*userord)[u].schema == schema) {
192 return &(*userord)[u];
193 }
194 }
195
196 /* it was not added yet, add it now */
197 LY_ARRAY_NEW_RET(schema->module->ctx, *userord, item, NULL);
198
199 item->schema = schema;
200 item->pos = 0;
201 item->inst = NULL;
202
203 /* store all the instance pointers in the current order */
204 if (first) {
205 if (first->parent) {
206 iter = first->parent->child;
207 } else {
Radek Krejci1e008d22020-08-17 11:37:37 +0200208 for (iter = first; iter->prev->next; iter = iter->prev) {}
Michal Vaskod59035b2020-07-08 12:00:06 +0200209 }
Michal Vaskod989ba02020-08-24 10:59:24 +0200210 for ( ; iter; iter = iter->next) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200211 if (iter->schema == first->schema) {
212 LY_ARRAY_NEW_RET(schema->module->ctx, item->inst, node, NULL);
213 *node = iter;
214 }
215 }
216 }
217
218 return item;
219}
220
221/**
222 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Can be used only for user-ordered
223 * lists/leaf-lists.
224 *
225 * @param[in] first Node from the first tree, can be NULL (on create).
226 * @param[in] second Node from the second tree, can be NULL (on delete).
227 * @param[in] options Diff options.
228 * @param[in,out] userord Sized array of userord items for keeping the current node order.
229 * @param[out] op Operation.
230 * @param[out] orig_default Original default metadata.
231 * @param[out] value Value metadata.
232 * @param[out] orig_value Original value metadata
233 * @param[out] key Key metadata.
234 * @param[out] orig_key Original key metadata.
235 * @return LY_SUCCESS on success,
236 * @return LY_ENOT if there is no change to be added into diff,
237 * @return LY_ERR value on other errors.
238 */
239static LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200240lyd_diff_userord_attrs(const struct lyd_node *first, const struct lyd_node *second, uint16_t options,
Radek Krejci0f969882020-08-21 16:56:47 +0200241 struct lyd_diff_userord **userord, enum lyd_diff_op *op, const char **orig_default, char **value,
242 char **orig_value, char **key, char **orig_key)
Michal Vaskod59035b2020-07-08 12:00:06 +0200243{
244 const struct lysc_node *schema;
Michal Vaskod59035b2020-07-08 12:00:06 +0200245 size_t buflen, bufused, first_pos, second_pos;
246 struct lyd_diff_userord *userord_item;
247
248 assert(first || second);
249
250 *orig_default = NULL;
251 *value = NULL;
252 *orig_value = NULL;
253 *key = NULL;
254 *orig_key = NULL;
255
256 schema = first ? first->schema : second->schema;
257 assert(lysc_is_userordered(schema));
258
259 /* get userord entry */
260 userord_item = lyd_diff_userord_get(first, schema, userord);
261 LY_CHECK_RET(!userord_item, LY_EMEM);
262
263 /* prepare position of the next instance */
264 second_pos = userord_item->pos++;
265
266 /* find user-ordered first position */
267 if (first) {
268 for (first_pos = second_pos; first_pos < LY_ARRAY_COUNT(userord_item->inst); ++first_pos) {
269 if (userord_item->inst[first_pos] == first) {
270 break;
271 }
272 }
273 assert(first_pos < LY_ARRAY_COUNT(userord_item->inst));
274 } else {
275 first_pos = 0;
276 }
277
278 /* learn operation first */
279 if (!second) {
280 *op = LYD_DIFF_OP_DELETE;
281 } else if (!first) {
282 *op = LYD_DIFF_OP_CREATE;
283 } else {
284 assert(schema->nodetype & (LYS_LIST | LYS_LEAFLIST));
Michal Vasko8f359bf2020-07-28 10:41:15 +0200285 if (lyd_compare_single(second, userord_item->inst[second_pos], 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200286 /* in first, there is a different instance on the second position, we are going to move 'first' node */
287 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200288 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200289 /* default flag change */
290 *op = LYD_DIFF_OP_NONE;
291 } else {
292 /* no changes */
293 return LY_ENOT;
294 }
295 }
296
297 /*
298 * set each attribute correctly based on the operation and node type
299 */
300
301 /* orig-default */
Michal Vasko69730152020-10-09 16:30:07 +0200302 if ((options & LYD_DIFF_DEFAULTS) && (schema->nodetype == LYS_LEAFLIST) &&
303 ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE)) &&
304 ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200305 if (first->flags & LYD_DEFAULT) {
306 *orig_default = "true";
307 } else {
308 *orig_default = "false";
309 }
310 }
311
312 /* value */
313 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
314 if (second_pos) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200315 *value = strdup(LYD_CANON_VALUE(userord_item->inst[second_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200316 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200317 } else {
318 *value = strdup("");
319 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
320 }
321 }
322
323 /* orig-value */
324 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
325 if (first_pos) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200326 *orig_value = strdup(LYD_CANON_VALUE(userord_item->inst[first_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200327 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200328 } else {
329 *orig_value = strdup("");
330 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
331 }
332 }
333
334 /* key */
Michal Vasko44f3d2c2020-08-24 09:49:38 +0200335 if ((schema->nodetype == LYS_LIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200336 if (second_pos) {
337 buflen = bufused = 0;
338 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[second_pos - 1], key, &buflen, &bufused, 0));
339 } else {
340 *key = strdup("");
341 LY_CHECK_ERR_RET(!*key, LOGMEM(schema->module->ctx), LY_EMEM);
342 }
343 }
344
345 /* orig-key */
346 if ((schema->nodetype == LYS_LIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
347 if (first_pos) {
348 buflen = bufused = 0;
349 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[first_pos - 1], orig_key, &buflen, &bufused, 0));
350 } else {
351 *orig_key = strdup("");
352 LY_CHECK_ERR_RET(!*orig_key, LOGMEM(schema->module->ctx), LY_EMEM);
353 }
354 }
355
356 /*
357 * update our instances - apply the change
358 */
359 if (*op == LYD_DIFF_OP_CREATE) {
360 /* insert the instance */
361 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 +0200362 ; , LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200363 if (second_pos < LY_ARRAY_COUNT(userord_item->inst)) {
364 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
365 (LY_ARRAY_COUNT(userord_item->inst) - second_pos) * sizeof *userord_item->inst);
366 }
367 LY_ARRAY_INCREMENT(userord_item->inst);
368 userord_item->inst[second_pos] = second;
369
370 } else if (*op == LYD_DIFF_OP_DELETE) {
371 /* remove the instance */
372 if (first_pos + 1 < LY_ARRAY_COUNT(userord_item->inst)) {
373 memmove(userord_item->inst + first_pos, userord_item->inst + first_pos + 1,
374 (LY_ARRAY_COUNT(userord_item->inst) - first_pos - 1) * sizeof *userord_item->inst);
375 }
376 LY_ARRAY_DECREMENT(userord_item->inst);
377
378 } else if (*op == LYD_DIFF_OP_REPLACE) {
379 /* move the instances */
380 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
381 (first_pos - second_pos) * sizeof *userord_item->inst);
382 userord_item->inst[second_pos] = first;
383 }
384
385 return LY_SUCCESS;
386}
387
388/**
389 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Cannot be used for user-ordered
390 * lists/leaf-lists.
391 *
392 * @param[in] first Node from the first tree, can be NULL (on create).
393 * @param[in] second Node from the second tree, can be NULL (on delete).
394 * @param[in] options Diff options.
395 * @param[out] op Operation.
396 * @param[out] orig_default Original default metadata.
397 * @param[out] orig_value Original value metadata.
398 * @return LY_SUCCESS on success,
399 * @return LY_ENOT if there is no change to be added into diff,
400 * @return LY_ERR value on other errors.
401 */
402static LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200403lyd_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 +0200404 const char **orig_default, char **orig_value)
Michal Vaskod59035b2020-07-08 12:00:06 +0200405{
406 const struct lysc_node *schema;
Michal Vaskod59035b2020-07-08 12:00:06 +0200407
408 assert(first || second);
409
410 *orig_default = NULL;
411 *orig_value = NULL;
412
413 schema = first ? first->schema : second->schema;
414 assert(!lysc_is_userordered(schema));
415
416 /* learn operation first */
417 if (!second) {
418 *op = LYD_DIFF_OP_DELETE;
419 } else if (!first) {
420 *op = LYD_DIFF_OP_CREATE;
421 } else {
422 switch (schema->nodetype) {
423 case LYS_CONTAINER:
424 case LYS_RPC:
425 case LYS_ACTION:
426 case LYS_NOTIF:
427 /* no changes */
428 return LY_ENOT;
429 case LYS_LIST:
430 case LYS_LEAFLIST:
Michal Vasko3a41dff2020-07-15 14:30:28 +0200431 if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200432 /* default flag change */
433 *op = LYD_DIFF_OP_NONE;
434 } else {
435 /* no changes */
436 return LY_ENOT;
437 }
438 break;
439 case LYS_LEAF:
440 case LYS_ANYXML:
441 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +0200442 if (lyd_compare_single(first, second, 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200443 /* different values */
444 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200445 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200446 /* default flag change */
447 *op = LYD_DIFF_OP_NONE;
448 } else {
449 /* no changes */
450 return LY_ENOT;
451 }
452 break;
453 default:
454 LOGINT_RET(schema->module->ctx);
455 }
456 }
457
458 /*
459 * set each attribute correctly based on the operation and node type
460 */
461
462 /* orig-default */
Michal Vasko69730152020-10-09 16:30:07 +0200463 if ((options & LYD_DIFF_DEFAULTS) && (schema->nodetype & LYD_NODE_TERM) &&
464 ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE)) &&
465 ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200466 if (first->flags & LYD_DEFAULT) {
467 *orig_default = "true";
468 } else {
469 *orig_default = "false";
470 }
471 }
472
473 /* orig-value */
474 if ((schema->nodetype == LYS_LEAF) && (*op == LYD_DIFF_OP_REPLACE)) {
475 /* leaf */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200476 *orig_value = strdup(LYD_CANON_VALUE(first));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200477 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200478 }
479
480 return LY_SUCCESS;
481}
482
483/**
484 * @brief Perform diff for all siblings at certain depth, recursively.
485 *
486 * For user-ordered lists/leaf-lists a specific structure is used for storing
487 * the current order. The idea is to apply all the generated diff changes
488 * virtually on the first tree so that we can continue to generate correct
489 * changes after some were already generated.
490 *
491 * The algorithm then uses second tree position-based changes with a before
492 * (preceding) item anchor.
493 *
494 * Example:
495 *
496 * Virtual first tree leaf-list order:
497 * 1 2 [3] 4 5
498 *
499 * Second tree leaf-list order:
500 * 1 2 [5] 3 4
501 *
502 * We are at the 3rd node now. We look at whether the nodes on the 3rd position
503 * match - they do not - move nodes so that the 3rd position node is final ->
504 * -> move node 5 to the 3rd position -> move node 5 after node 2.
505 *
506 * Required properties:
507 * Stored operations (move) should not be affected by later operations -
508 * - would cause a redundantly long list of operations, possibly inifinite.
509 *
510 * Implemenation justification:
511 * First, all delete operations and only then move/create operations are stored.
512 * Also, preceding anchor is used and after each iteration another node is
513 * at its final position. That results in the invariant that all preceding
514 * nodes are final and will not be changed by the later operations, meaning
515 * they can safely be used as anchors for the later operations.
516 *
517 * @param[in] first First tree first sibling.
518 * @param[in] second Second tree first sibling.
519 * @param[in] options Diff options.
Michal Vasko3a41dff2020-07-15 14:30:28 +0200520 * @param[in] nosiblings Whether to skip following siblings.
Michal Vaskod59035b2020-07-08 12:00:06 +0200521 * @param[in,out] diff Diff to append to.
522 * @return LY_ERR value.
523 */
524static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200525lyd_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 +0200526 struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +0200527{
528 LY_ERR ret = LY_SUCCESS;
529 const struct lyd_node *iter_first, *iter_second;
530 struct lyd_node *match_second, *match_first;
Michal Vaskod59035b2020-07-08 12:00:06 +0200531 struct lyd_diff_userord *userord = NULL;
532 LY_ARRAY_COUNT_TYPE u;
533 enum lyd_diff_op op;
534 const char *orig_default;
535 char *orig_value, *key, *value, *orig_key;
536
Michal Vaskod59035b2020-07-08 12:00:06 +0200537 /* compare first tree to the second tree - delete, replace, none */
538 LY_LIST_FOR(first, iter_first) {
539 assert(!(iter_first->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200540 if ((iter_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200541 /* skip default nodes */
542 continue;
543 }
544
545 if (iter_first->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
546 /* try to find the exact instance */
547 lyd_find_sibling_first(second, iter_first, &match_second);
548 } else {
549 /* try to simply find the node, there cannot be more instances */
550 lyd_find_sibling_val(second, iter_first->schema, NULL, 0, &match_second);
551 }
552
Michal Vasko3a41dff2020-07-15 14:30:28 +0200553 if (match_second && (match_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200554 /* ignore default nodes */
555 match_second = NULL;
556 }
557
558 if (lysc_is_userordered(iter_first->schema)) {
559 if (match_second) {
560 /* we are handling only user-ordered node delete now */
561 continue;
562 }
563
564 /* get all the attributes */
565 LY_CHECK_GOTO(lyd_diff_userord_attrs(iter_first, match_second, options, &userord, &op, &orig_default,
Michal Vasko69730152020-10-09 16:30:07 +0200566 &value, &orig_value, &key, &orig_key), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200567
568 /* there must be changes, it is deleted */
569 assert(op == LYD_DIFF_OP_DELETE);
570 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, key, value, orig_key, diff);
571
572 free(orig_value);
573 free(key);
574 free(value);
575 free(orig_key);
576 LY_CHECK_GOTO(ret, cleanup);
577 } else {
578 /* get all the attributes */
579 ret = lyd_diff_attrs(iter_first, match_second, options, &op, &orig_default, &orig_value);
580
581 /* add into diff if there are any changes */
582 if (!ret) {
583 if (op == LYD_DIFF_OP_DELETE) {
584 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, NULL, NULL, NULL, diff);
585 } else {
Michal Vasko3c2dd6c2020-11-06 17:38:55 +0100586 assert(match_second);
Michal Vaskod59035b2020-07-08 12:00:06 +0200587 ret = lyd_diff_add(match_second, op, orig_default, orig_value, NULL, NULL, NULL, diff);
588 }
589
590 free(orig_value);
591 LY_CHECK_GOTO(ret, cleanup);
592 } else if (ret == LY_ENOT) {
593 ret = LY_SUCCESS;
594 } else {
595 goto cleanup;
596 }
597 }
598
599 /* check descendants, if any, recursively */
600 if (match_second) {
Radek Krejcia1c1e542020-09-29 16:06:52 +0200601 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 +0200602 0, diff), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200603 }
604
605 if (nosiblings) {
606 break;
607 }
608 }
609
610 /* reset all cached positions */
611 LY_ARRAY_FOR(userord, u) {
612 userord[u].pos = 0;
613 }
614
615 /* compare second tree to the first tree - create, user-ordered move */
616 LY_LIST_FOR(second, iter_second) {
617 assert(!(iter_second->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200618 if ((iter_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200619 /* skip default nodes */
620 continue;
621 }
622
623 if (iter_second->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
624 lyd_find_sibling_first(first, iter_second, &match_first);
625 } else {
626 lyd_find_sibling_val(first, iter_second->schema, NULL, 0, &match_first);
627 }
628
Michal Vasko3a41dff2020-07-15 14:30:28 +0200629 if (match_first && (match_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200630 /* ignore default nodes */
631 match_first = NULL;
632 }
633
634 if (lysc_is_userordered(iter_second->schema)) {
635 /* get all the attributes */
636 ret = lyd_diff_userord_attrs(match_first, iter_second, options, &userord, &op, &orig_default,
Michal Vasko69730152020-10-09 16:30:07 +0200637 &value, &orig_value, &key, &orig_key);
Michal Vaskod59035b2020-07-08 12:00:06 +0200638
639 /* add into diff if there are any changes */
640 if (!ret) {
641 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, key, value, orig_key, diff);
642
643 free(orig_value);
644 free(key);
645 free(value);
646 free(orig_key);
647 LY_CHECK_GOTO(ret, cleanup);
648 } else if (ret == LY_ENOT) {
649 ret = LY_SUCCESS;
650 } else {
651 goto cleanup;
652 }
653 } else if (!match_first) {
654 /* get all the attributes */
655 LY_CHECK_GOTO(lyd_diff_attrs(match_first, iter_second, options, &op, &orig_default, &orig_value), cleanup);
656
657 /* there must be changes, it is created */
658 assert(op == LYD_DIFF_OP_CREATE);
659 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, NULL, NULL, NULL, diff);
660
661 free(orig_value);
662 LY_CHECK_GOTO(ret, cleanup);
663 } /* else was handled */
664
665 if (nosiblings) {
666 break;
667 }
668 }
669
670cleanup:
671 LY_ARRAY_FOR(userord, u) {
672 LY_ARRAY_FREE(userord[u].inst);
673 }
674 LY_ARRAY_FREE(userord);
675 return ret;
676}
677
Michal Vasko3a41dff2020-07-15 14:30:28 +0200678static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200679lyd_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 +0200680{
681 const struct ly_ctx *ctx;
682
683 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
684
685 if (first) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200686 ctx = LYD_CTX(first);
Michal Vaskod59035b2020-07-08 12:00:06 +0200687 } else if (second) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200688 ctx = LYD_CTX(second);
Michal Vaskod59035b2020-07-08 12:00:06 +0200689 } else {
690 ctx = NULL;
691 }
692
693 if (first && second && (lysc_data_parent(first->schema) != lysc_data_parent(second->schema))) {
694 LOGERR(ctx, LY_EINVAL, "Invalid arguments - cannot create diff for unrelated data (%s()).", __func__);
695 return LY_EINVAL;
696 }
697
698 *diff = NULL;
699
Michal Vasko3a41dff2020-07-15 14:30:28 +0200700 return lyd_diff_siblings_r(first, second, options, nosiblings, diff);
701}
702
703API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200704lyd_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 +0200705{
706 return lyd_diff(first, second, options, 1, diff);
707}
708
709API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200710lyd_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 +0200711{
712 return lyd_diff(first, second, options, 0, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200713}
714
715/**
716 * @brief Find a matching node in data tree for a diff node.
717 *
718 * @param[in] first_node First sibling in the data tree.
719 * @param[in] diff_node Diff node to match.
Michal Vaskoe6323f62020-07-09 15:49:02 +0200720 * @param[out] match_p Matching node, NULL if no found.
Michal Vaskod59035b2020-07-08 12:00:06 +0200721 */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200722static void
Michal Vaskod59035b2020-07-08 12:00:06 +0200723lyd_diff_find_node(const struct lyd_node *first_node, const struct lyd_node *diff_node, struct lyd_node **match_p)
724{
725 if (diff_node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
726 /* try to find the exact instance */
727 lyd_find_sibling_first(first_node, diff_node, match_p);
728 } else {
729 /* try to simply find the node, there cannot be more instances */
730 lyd_find_sibling_val(first_node, diff_node->schema, NULL, 0, match_p);
731 }
Michal Vaskod59035b2020-07-08 12:00:06 +0200732}
733
734/**
735 * @brief Learn operation of a diff node.
736 *
737 * @param[in] diff_node Diff node.
738 * @param[out] op Operation.
Michal Vaskod59035b2020-07-08 12:00:06 +0200739 * @return LY_ERR value.
740 */
741static LY_ERR
Michal Vaskoe6323f62020-07-09 15:49:02 +0200742lyd_diff_get_op(const struct lyd_node *diff_node, enum lyd_diff_op *op)
Michal Vaskod59035b2020-07-08 12:00:06 +0200743{
744 struct lyd_meta *meta = NULL;
745 const struct lyd_node *diff_parent;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200746 const char *str;
Michal Vaskod59035b2020-07-08 12:00:06 +0200747
748 for (diff_parent = diff_node; diff_parent; diff_parent = (struct lyd_node *)diff_parent->parent) {
749 LY_LIST_FOR(diff_parent->meta, meta) {
750 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200751 str = meta->value.canonical;
Michal Vaskod59035b2020-07-08 12:00:06 +0200752 if ((str[0] == 'r') && (diff_parent != diff_node)) {
753 /* we do not care about this operation if it's in our parent */
754 continue;
755 }
Michal Vaskoe6323f62020-07-09 15:49:02 +0200756 *op = lyd_diff_str2op(str);
Michal Vaskod59035b2020-07-08 12:00:06 +0200757 break;
758 }
759 }
760 if (meta) {
761 break;
762 }
763 }
Michal Vaskob7be7a82020-08-20 09:09:04 +0200764 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_node)), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +0200765
Michal Vaskod59035b2020-07-08 12:00:06 +0200766 return LY_SUCCESS;
767}
768
769/**
770 * @brief Insert a diff node into a data tree.
771 *
772 * @param[in,out] first_node First sibling of the data tree.
773 * @param[in] parent_node Data tree sibling parent node.
774 * @param[in] new_node Node to insert.
775 * @param[in] keys_or_value Optional predicate of relative (leaf-)list instance. If not set, the user-ordered
776 * instance will be inserted at the first position.
777 * @return err_info, NULL on success.
778 */
779static LY_ERR
780lyd_diff_insert(struct lyd_node **first_node, struct lyd_node *parent_node, struct lyd_node *new_node,
Radek Krejci0f969882020-08-21 16:56:47 +0200781 const char *key_or_value)
Michal Vaskod59035b2020-07-08 12:00:06 +0200782{
783 LY_ERR ret;
784 struct lyd_node *anchor;
785
786 assert(new_node);
787
788 if (!*first_node) {
789 if (!parent_node) {
790 /* no parent or siblings */
791 *first_node = new_node;
792 return LY_SUCCESS;
793 }
794
795 /* simply insert into parent, no other children */
796 if (key_or_value) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200797 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
Michal Vasko69730152020-10-09 16:30:07 +0200798 new_node->schema->name);
Michal Vaskod59035b2020-07-08 12:00:06 +0200799 return LY_EINVAL;
800 }
Michal Vaskob104f112020-07-17 09:54:54 +0200801 return lyd_insert_child(parent_node, new_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200802 }
803
804 assert(!(*first_node)->parent || ((struct lyd_node *)(*first_node)->parent == parent_node));
805
Michal Vaskod59035b2020-07-08 12:00:06 +0200806 if (!lysc_is_userordered(new_node->schema)) {
Michal Vaskob104f112020-07-17 09:54:54 +0200807 /* simple insert */
808 return lyd_insert_sibling(*first_node, new_node, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200809 }
810
811 if (key_or_value) {
812 /* find the anchor sibling */
813 ret = lyd_find_sibling_val(*first_node, new_node->schema, key_or_value, 0, &anchor);
814 if (ret == LY_ENOTFOUND) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200815 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
Michal Vasko69730152020-10-09 16:30:07 +0200816 new_node->schema->name);
Michal Vaskod59035b2020-07-08 12:00:06 +0200817 return LY_EINVAL;
818 } else if (ret) {
819 return ret;
820 }
821
822 /* insert after */
823 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
824 assert(new_node->prev == anchor);
825 if (*first_node == new_node) {
826 *first_node = anchor;
827 }
828 } else {
829 if ((*first_node)->schema->flags & LYS_KEY) {
830 assert(parent_node && (parent_node->schema->nodetype == LYS_LIST));
831
832 /* find last key */
833 anchor = *first_node;
834 while (anchor->next && (anchor->next->schema->flags & LYS_KEY)) {
835 anchor = anchor->next;
836 }
837 /* insert after the last key */
838 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
839 } else {
840 /* insert at the beginning */
841 LY_CHECK_RET(lyd_insert_before(*first_node, new_node));
842 *first_node = new_node;
843 }
844 }
845
846 return LY_SUCCESS;
847}
848
849/**
850 * @brief Apply diff subtree on data tree nodes, recursively.
851 *
852 * @param[in,out] first_node First sibling of the data tree.
853 * @param[in] parent_node Parent of the first sibling.
854 * @param[in] diff_node Current diff node.
Michal Vaskoe6323f62020-07-09 15:49:02 +0200855 * @param[in] diff_cb Optional diff callback.
856 * @param[in] cb_data User data for @p diff_cb.
Michal Vaskod59035b2020-07-08 12:00:06 +0200857 * @return LY_ERR value.
858 */
859static LY_ERR
860lyd_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 +0200861 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskod59035b2020-07-08 12:00:06 +0200862{
863 LY_ERR ret;
864 struct lyd_node *match, *diff_child;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200865 const char *str_val;
866 enum lyd_diff_op op;
867 struct lyd_meta *meta;
Michal Vaskob7be7a82020-08-20 09:09:04 +0200868 const struct ly_ctx *ctx = LYD_CTX(diff_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200869
870 /* read all the valid attributes */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200871 LY_CHECK_RET(lyd_diff_get_op(diff_node, &op));
Michal Vaskod59035b2020-07-08 12:00:06 +0200872
Michal Vaskoe6323f62020-07-09 15:49:02 +0200873 /* handle specific user-ordered (leaf-)lists operations separately */
874 if (lysc_is_userordered(diff_node->schema) && ((op == LYD_DIFF_OP_CREATE) || (op == LYD_DIFF_OP_REPLACE))) {
875 if (op == LYD_DIFF_OP_REPLACE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200876 /* find the node (we must have some siblings because the node was only moved) */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200877 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200878 } else {
Michal Vasko3a41dff2020-07-15 14:30:28 +0200879 /* duplicate the node */
880 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +0200881 }
882
Michal Vaskoe6323f62020-07-09 15:49:02 +0200883 /* get "key" or "value" metadata string value */
884 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 +0200885 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_node)), LY_EINT);
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200886 str_val = meta->value.canonical;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200887
Michal Vaskod59035b2020-07-08 12:00:06 +0200888 /* insert/move the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200889 if (str_val[0]) {
890 ret = lyd_diff_insert(first_node, parent_node, match, str_val);
Michal Vaskod59035b2020-07-08 12:00:06 +0200891 } else {
892 ret = lyd_diff_insert(first_node, parent_node, match, NULL);
893 }
894 if (ret) {
Michal Vaskoe6323f62020-07-09 15:49:02 +0200895 if (op == LYD_DIFF_OP_CREATE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200896 lyd_free_tree(match);
897 }
898 return ret;
899 }
900
901 goto next_iter_r;
902 }
903
904 /* apply operation */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200905 switch (op) {
906 case LYD_DIFF_OP_NONE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200907 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200908 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200909
910 if (match->schema->nodetype & LYD_NODE_TERM) {
911 /* special case of only dflt flag change */
912 if (diff_node->flags & LYD_DEFAULT) {
913 match->flags |= LYD_DEFAULT;
914 } else {
915 match->flags &= ~LYD_DEFAULT;
916 }
917 } else {
918 /* none operation on nodes without children is redundant and hence forbidden */
Radek Krejcia1c1e542020-09-29 16:06:52 +0200919 if (!lyd_child_no_keys(diff_node)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200920 LOGINT_RET(ctx);
921 }
922 }
923 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200924 case LYD_DIFF_OP_CREATE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200925 /* duplicate the node */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200926 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +0200927
928 /* insert it at the end */
929 ret = 0;
Michal Vaskob104f112020-07-17 09:54:54 +0200930 if (parent_node) {
931 ret = lyd_insert_child(parent_node, match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200932 } else {
Michal Vaskob104f112020-07-17 09:54:54 +0200933 ret = lyd_insert_sibling(*first_node, match, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200934 }
935 if (ret) {
936 lyd_free_tree(match);
937 return ret;
938 }
939
940 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200941 case LYD_DIFF_OP_DELETE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200942 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200943 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200944
945 /* remove it */
946 if ((match == *first_node) && !match->parent) {
947 assert(!parent_node);
948 /* we have removed the top-level node */
949 *first_node = (*first_node)->next;
950 }
951 lyd_free_tree(match);
952
953 /* we are not going recursively in this case, the whole subtree was already deleted */
954 return LY_SUCCESS;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200955 case LYD_DIFF_OP_REPLACE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200956 LY_CHECK_ERR_RET(diff_node->schema->nodetype != LYS_LEAF, LOGINT(ctx), LY_EINT);
957
958 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200959 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200960
961 /* update its value */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200962 ret = lyd_change_term(match, LYD_CANON_VALUE(diff_node));
Michal Vaskod59035b2020-07-08 12:00:06 +0200963 if (ret && (ret != LY_EEXIST)) {
964 LOGINT_RET(ctx);
965 }
966
967 /* with flags */
968 match->flags = diff_node->flags;
969 break;
970 default:
971 LOGINT_RET(ctx);
972 }
973
974next_iter_r:
975 if (diff_cb) {
976 /* call callback */
977 LY_CHECK_RET(diff_cb(diff_node, match, cb_data));
978 }
979
980 /* apply diff recursively */
Radek Krejcia1c1e542020-09-29 16:06:52 +0200981 LY_LIST_FOR(lyd_child_no_keys(diff_node), diff_child) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200982 LY_CHECK_RET(lyd_diff_apply_r(lyd_node_children_p(match), match, diff_child, diff_cb, cb_data));
983 }
984
985 return LY_SUCCESS;
986}
987
988API LY_ERR
989lyd_diff_apply_module(struct lyd_node **data, const struct lyd_node *diff, const struct lys_module *mod,
Radek Krejci0f969882020-08-21 16:56:47 +0200990 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskod59035b2020-07-08 12:00:06 +0200991{
992 const struct lyd_node *root;
993
994 LY_LIST_FOR(diff, root) {
995 if (mod && (lyd_owner_module(root) != mod)) {
996 /* skip data nodes from different modules */
997 continue;
998 }
999
1000 /* apply relevant nodes from the diff datatree */
1001 LY_CHECK_RET(lyd_diff_apply_r(data, NULL, root, diff_cb, cb_data));
1002 }
1003
1004 return LY_SUCCESS;
1005}
1006
1007API LY_ERR
Michal Vasko3a41dff2020-07-15 14:30:28 +02001008lyd_diff_apply_all(struct lyd_node **data, const struct lyd_node *diff)
Michal Vaskod59035b2020-07-08 12:00:06 +02001009{
1010 return lyd_diff_apply_module(data, diff, NULL, NULL, NULL);
1011}
Michal Vaskoe6323f62020-07-09 15:49:02 +02001012
1013/**
1014 * @brief Update operations on a diff node when the new operation is NONE.
1015 *
1016 * @param[in] diff_match Node from the diff.
1017 * @param[in] cur_op Current operation of the diff node.
1018 * @param[in] src_diff Current source diff node.
1019 * @return LY_ERR value.
1020 */
1021static LY_ERR
1022lyd_diff_merge_none(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1023{
1024 switch (cur_op) {
1025 case LYD_DIFF_OP_NONE:
1026 case LYD_DIFF_OP_CREATE:
1027 case LYD_DIFF_OP_REPLACE:
1028 if (src_diff->schema->nodetype & LYD_NODE_TERM) {
1029 /* NONE on a term means only its dflt flag was changed */
1030 diff_match->flags &= ~LYD_DEFAULT;
1031 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1032 }
1033 break;
1034 default:
1035 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001036 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001037 }
1038
1039 return LY_SUCCESS;
1040}
1041
1042/**
1043 * @brief Remove an attribute from a node.
1044 *
1045 * @param[in] node Node with the metadata.
1046 * @param[in] name Metadata name.
1047 */
1048static void
1049lyd_diff_del_meta(struct lyd_node *node, const char *name)
1050{
1051 struct lyd_meta *meta;
1052
1053 LY_LIST_FOR(node->meta, meta) {
1054 if (!strcmp(meta->name, name) && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001055 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001056 return;
1057 }
1058 }
1059
1060 assert(0);
1061}
1062
1063/**
1064 * @brief Set a specific operation of a node. Delete the previous operation, if any.
1065 *
1066 * @param[in] node Node to change.
1067 * @param[in] op Operation to set.
1068 * @return LY_ERR value.
1069 */
1070static LY_ERR
1071lyd_diff_change_op(struct lyd_node *node, enum lyd_diff_op op)
1072{
1073 struct lyd_meta *meta;
1074
1075 LY_LIST_FOR(node->meta, meta) {
1076 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001077 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001078 break;
1079 }
1080 }
1081
Michal Vasko3a41dff2020-07-15 14:30:28 +02001082 return lyd_new_meta(node, NULL, "yang:operation", lyd_diff_op2str(op), NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001083}
1084
1085/**
1086 * @brief Update operations on a diff node when the new operation is REPLACE.
1087 *
1088 * @param[in] diff_match Node from the diff.
1089 * @param[in] cur_op Current operation of the diff node.
1090 * @param[in] src_diff Current source diff node.
1091 * @return LY_ERR value.
1092 */
1093static LY_ERR
1094lyd_diff_merge_replace(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1095{
1096 LY_ERR ret;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001097 const char *str_val, *meta_name;
1098 struct lyd_meta *meta;
1099 const struct lys_module *mod;
1100 const struct lyd_node_any *any;
1101
1102 /* get "yang" module for the metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001103 mod = ly_ctx_get_module_latest(LYD_CTX(diff_match), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001104 assert(mod);
1105
1106 switch (cur_op) {
1107 case LYD_DIFF_OP_REPLACE:
1108 case LYD_DIFF_OP_CREATE:
1109 switch (diff_match->schema->nodetype) {
1110 case LYS_LIST:
1111 case LYS_LEAFLIST:
Michal Vasko4231fb62020-07-13 13:54:47 +02001112 /* it was created/moved somewhere, but now it will be created/moved somewhere else,
Michal Vaskoe6323f62020-07-09 15:49:02 +02001113 * keep orig_key/orig_value (only replace oper) and replace key/value */
1114 assert(lysc_is_userordered(diff_match->schema));
1115 meta_name = (diff_match->schema->nodetype == LYS_LIST ? "key" : "value");
1116
1117 lyd_diff_del_meta(diff_match, meta_name);
1118 meta = lyd_find_meta(src_diff->meta, mod, meta_name);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001119 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001120 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001121 break;
1122 case LYS_LEAF:
1123 /* replaced with the exact same value, impossible */
Michal Vasko8f359bf2020-07-28 10:41:15 +02001124 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001125 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001126 }
1127
Michal Vaskoe6323f62020-07-09 15:49:02 +02001128 /* modify the node value */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001129 if (lyd_change_term(diff_match, LYD_CANON_VALUE(src_diff))) {
1130 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001131 }
1132
Michal Vasko8caadab2020-11-05 17:38:15 +01001133 if (cur_op == LYD_DIFF_OP_REPLACE) {
1134 /* compare values whether there is any change at all */
1135 meta = lyd_find_meta(diff_match->meta, mod, "orig-value");
1136 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_match)), LY_EINT);
1137 str_val = meta->value.canonical;
1138 ret = lyd_value_compare((struct lyd_node_term *)diff_match, str_val, strlen(str_val));
1139 if (!ret) {
1140 /* values are the same, remove orig-value meta and set oper to NONE */
1141 lyd_free_meta_single(meta);
1142 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1143 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001144 }
1145
1146 /* modify the default flag */
1147 diff_match->flags &= ~LYD_DEFAULT;
1148 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1149 break;
1150 case LYS_ANYXML:
1151 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +02001152 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001153 /* replaced with the exact same value, impossible */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001154 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001155 }
1156
1157 /* modify the node value */
1158 any = (struct lyd_node_any *)src_diff;
1159 LY_CHECK_RET(lyd_any_copy_value(diff_match, &any->value, any->value_type));
1160 break;
1161 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001162 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001163 }
1164 break;
1165 case LYD_DIFF_OP_NONE:
1166 /* it is moved now */
1167 assert(lysc_is_userordered(diff_match->schema) && (diff_match->schema->nodetype == LYS_LIST));
1168
1169 /* change the operation */
1170 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1171
1172 /* set orig-key and key metadata */
1173 meta = lyd_find_meta(src_diff->meta, mod, "orig-key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001174 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001175 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001176
1177 meta = lyd_find_meta(src_diff->meta, mod, "key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001178 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001179 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001180 break;
1181 default:
1182 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001183 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001184 }
1185
1186 return LY_SUCCESS;
1187}
1188
1189/**
1190 * @brief Update operations in a diff node when the new operation is CREATE.
1191 *
1192 * @param[in] diff_match Node from the diff.
1193 * @param[in] cur_op Current operation of the diff node.
1194 * @param[in] src_diff Current source diff node.
1195 * @return LY_ERR value.
1196 */
1197static LY_ERR
1198lyd_diff_merge_create(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1199{
1200 struct lyd_node *child;
Michal Vasko5632e0d2020-07-31 14:13:37 +02001201 const struct lysc_node_leaf *sleaf;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001202
1203 switch (cur_op) {
1204 case LYD_DIFF_OP_DELETE:
Michal Vasko5632e0d2020-07-31 14:13:37 +02001205 if (diff_match->schema->nodetype == LYS_LEAF) {
1206 sleaf = (struct lysc_node_leaf *)diff_match->schema;
1207 } else {
1208 sleaf = NULL;
1209 }
1210
Michal Vasko69730152020-10-09 16:30:07 +02001211 if (sleaf && sleaf->dflt &&
1212 !sleaf->dflt->realtype->plugin->compare(sleaf->dflt, &((struct lyd_node_term *)src_diff)->value)) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001213 /* we deleted it, so a default value was in-use, and it matches the created value -> 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 */
1218 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
Michal Vasko69730152020-10-09 16:30:07 +02001219 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vasko5632e0d2020-07-31 14:13:37 +02001220 }
1221 } else if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001222 /* deleted + created -> operation NONE */
1223 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1224
1225 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1226 /* add orig-dflt metadata */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001227 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
Michal Vasko69730152020-10-09 16:30:07 +02001228 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001229 }
1230 } else {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001231 assert(sleaf);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001232 /* we deleted it, but it was created with a different value -> operation REPLACE */
1233 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
Michal Vasko5632e0d2020-07-31 14:13:37 +02001234 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001235
Michal Vasko5632e0d2020-07-31 14:13:37 +02001236 if (lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001237 /* current value is the previous one (meta) */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001238 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 +02001239
1240 /* update the value itself */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001241 LY_CHECK_RET(lyd_change_term(diff_match, LYD_CANON_VALUE(src_diff)));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001242 }
1243
1244 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1245 /* update dflt flag itself */
1246 diff_match->flags &= ~LYD_DEFAULT;
1247 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1248 } else {
1249 /* but the operation of its children should remain DELETE */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001250 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001251 LY_CHECK_RET(lyd_diff_change_op(child, LYD_DIFF_OP_DELETE));
1252 }
1253 }
1254 break;
1255 default:
1256 /* create and replace operations are not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001257 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001258 }
1259
1260 return LY_SUCCESS;
1261}
1262
1263/**
1264 * @brief Update operations on a diff node when the new operation is DELETE.
1265 *
1266 * @param[in] diff_match Node from the diff.
1267 * @param[in] cur_op Current operation of the diff node.
1268 * @param[in] src_diff Current source diff node.
1269 * @return LY_ERR value.
1270 */
1271static LY_ERR
1272lyd_diff_merge_delete(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1273{
1274 struct lyd_node *next, *child;
1275
1276 /* we can delete only exact existing nodes */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001277 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 +02001278
1279 switch (cur_op) {
1280 case LYD_DIFF_OP_CREATE:
1281 /* it was created, but then deleted -> set NONE operation */
1282 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1283
1284 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1285 /* add orig-default meta because it is expected */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001286 LY_CHECK_RET(lyd_new_meta(diff_match, NULL, "yang:orig-default",
Michal Vasko69730152020-10-09 16:30:07 +02001287 diff_match->flags & LYD_DEFAULT ? "true" : "false", NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001288 } else {
1289 /* keep operation for all descendants (for now) */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001290 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001291 LY_CHECK_RET(lyd_diff_change_op(child, cur_op));
1292 }
1293 }
1294 break;
1295 case LYD_DIFF_OP_REPLACE:
1296 /* similar to none operation but also remove the redundant attribute */
1297 lyd_diff_del_meta(diff_match, "orig-value");
Radek Krejci0f969882020-08-21 16:56:47 +02001298 /* fallthrough */
Michal Vaskoe6323f62020-07-09 15:49:02 +02001299 case LYD_DIFF_OP_NONE:
1300 /* it was not modified, but should be deleted -> set DELETE operation */
1301 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_DELETE));
1302
Michal Vasko5632e0d2020-07-31 14:13:37 +02001303 /* all descendants not in the diff will be deleted and redundant in the diff, so remove them */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001304 LY_LIST_FOR_SAFE(lyd_child_no_keys(diff_match), next, child) {
1305 if (lyd_find_sibling_first(lyd_child(src_diff), child, NULL) == LY_ENOTFOUND) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001306 lyd_free_tree(child);
1307 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001308 }
1309 break;
1310 default:
1311 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001312 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001313 }
1314
1315 return LY_SUCCESS;
1316}
1317
1318/**
1319 * @brief Check whether this diff node is redundant (does not change data).
1320 *
1321 * @param[in] diff Diff node.
1322 * @return 0 if not, non-zero if it is.
1323 */
1324static int
1325lyd_diff_is_redundant(struct lyd_node *diff)
1326{
1327 enum lyd_diff_op op;
1328 struct lyd_meta *meta, *orig_val_meta = NULL, *val_meta = NULL;
1329 struct lyd_node *child;
1330 const struct lys_module *mod;
1331 const char *str;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001332
1333 assert(diff);
1334
Radek Krejcia1c1e542020-09-29 16:06:52 +02001335 child = lyd_child_no_keys(diff);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001336 mod = ly_ctx_get_module_latest(LYD_CTX(diff), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001337 assert(mod);
1338
1339 /* get node operation */
Michal Vasko53bf6f22020-07-14 08:23:40 +02001340 LY_CHECK_RET(lyd_diff_get_op(diff, &op), 0);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001341
1342 if ((op == LYD_DIFF_OP_REPLACE) && lysc_is_userordered(diff->schema)) {
1343 /* check for redundant move */
1344 orig_val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "orig-key" : "orig-value"));
1345 val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "key" : "value"));
1346 assert(orig_val_meta && val_meta);
1347
1348 if (!lyd_compare_meta(orig_val_meta, val_meta)) {
1349 /* there is actually no move */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001350 lyd_free_meta_single(orig_val_meta);
1351 lyd_free_meta_single(val_meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001352 if (child) {
1353 /* change operation to NONE, we have siblings */
1354 lyd_diff_change_op(diff, LYD_DIFF_OP_NONE);
1355 return 0;
1356 }
1357
1358 /* redundant node, BUT !!
1359 * In diff the move operation is always converted to be INSERT_AFTER, which is fine
1360 * because the data that this is applied on should not change for the diff lifetime.
1361 * However, when we are merging 2 diffs, this conversion is actually lossy because
1362 * if the data change, the move operation can also change its meaning. In this specific
1363 * case the move operation will be lost. But it can be considered a feature, it is not supported.
1364 */
1365 return 1;
1366 }
1367 } else if ((op == LYD_DIFF_OP_NONE) && (diff->schema->nodetype & LYD_NODE_TERM)) {
1368 /* check whether at least the default flags are different */
1369 meta = lyd_find_meta(diff->meta, mod, "orig-default");
1370 assert(meta);
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001371 str = meta->value.canonical;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001372
1373 /* if previous and current dflt flags are the same, this node is redundant */
1374 if ((!strcmp(str, "true") && (diff->flags & LYD_DEFAULT)) || (!strcmp(str, "false") && !(diff->flags & LYD_DEFAULT))) {
1375 return 1;
1376 }
1377 return 0;
1378 }
1379
1380 if (!child && (op == LYD_DIFF_OP_NONE)) {
1381 return 1;
1382 }
1383
1384 return 0;
1385}
1386
1387/**
1388 * @brief Merge sysrepo diff with another diff, recursively.
1389 *
1390 * @param[in] src_diff Source diff node.
1391 * @param[in] diff_parent Current sysrepo diff parent.
1392 * @param[in] diff_cb Optional diff callback.
1393 * @param[in] cb_data User data for @p diff_cb.
1394 * @param[in,out] diff Diff root node.
1395 * @return LY_ERR value.
1396 */
1397static LY_ERR
1398lyd_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 +02001399 struct lyd_node **diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001400{
1401 LY_ERR ret = LY_SUCCESS;
1402 struct lyd_node *child, *diff_node = NULL;
1403 enum lyd_diff_op src_op, cur_op;
1404
1405 /* get source node operation */
1406 LY_CHECK_RET(lyd_diff_get_op(src_diff, &src_op));
1407
1408 /* find an equal node in the current diff */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001409 lyd_diff_find_node(diff_parent ? lyd_child_no_keys(diff_parent) : *diff, src_diff, &diff_node);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001410
1411 if (diff_node) {
1412 /* get target (current) operation */
1413 LY_CHECK_RET(lyd_diff_get_op(diff_node, &cur_op));
1414
1415 /* merge operations */
1416 switch (src_op) {
1417 case LYD_DIFF_OP_REPLACE:
1418 ret = lyd_diff_merge_replace(diff_node, cur_op, src_diff);
1419 break;
1420 case LYD_DIFF_OP_CREATE:
1421 ret = lyd_diff_merge_create(diff_node, cur_op, src_diff);
1422 break;
1423 case LYD_DIFF_OP_DELETE:
1424 ret = lyd_diff_merge_delete(diff_node, cur_op, src_diff);
1425 break;
1426 case LYD_DIFF_OP_NONE:
1427 ret = lyd_diff_merge_none(diff_node, cur_op, src_diff);
1428 break;
1429 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001430 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001431 }
1432 if (ret) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001433 LOGERR(LYD_CTX(src_diff), LY_EOTHER, "Merging operation \"%s\" failed.", lyd_diff_op2str(src_op));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001434 return ret;
1435 }
1436
1437 if (diff_cb) {
1438 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001439 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001440 }
1441
1442 /* update diff parent */
1443 diff_parent = diff_node;
1444
1445 /* merge src_diff recursively */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001446 LY_LIST_FOR(lyd_child_no_keys(src_diff), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001447 LY_CHECK_RET(lyd_diff_merge_r(child, diff_parent, diff_cb, cb_data, diff));
1448 }
1449 } else {
1450 /* add new diff node with all descendants */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001451 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 +02001452
1453 /* insert node into diff if not already */
1454 if (!diff_parent) {
Michal Vaskob104f112020-07-17 09:54:54 +02001455 lyd_insert_sibling(*diff, diff_node, diff);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001456 }
1457
1458 /* update operation */
1459 LY_CHECK_RET(lyd_diff_change_op(diff_node, src_op));
1460
1461 if (diff_cb) {
1462 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001463 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001464 }
1465
1466 /* update diff parent */
1467 diff_parent = diff_node;
1468 }
1469
1470 /* remove any redundant nodes */
Michal Vaskob98d7082020-07-15 16:38:36 +02001471 if (lyd_diff_is_redundant(diff_parent)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001472 if (diff_parent == *diff) {
1473 *diff = (*diff)->next;
1474 }
1475 lyd_free_tree(diff_parent);
1476 }
1477
1478 return LY_SUCCESS;
1479}
1480
1481API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001482lyd_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 +02001483 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001484{
1485 const struct lyd_node *src_root;
1486
1487 LY_LIST_FOR(src_diff, src_root) {
1488 if (mod && (lyd_owner_module(src_root) != mod)) {
1489 /* skip data nodes from different modules */
1490 continue;
1491 }
1492
1493 /* apply relevant nodes from the diff datatree */
1494 LY_CHECK_RET(lyd_diff_merge_r(src_root, NULL, diff_cb, cb_data, diff));
1495 }
1496
1497 return LY_SUCCESS;
1498}
1499
1500API LY_ERR
Michal Vasko04f85912020-08-07 12:14:58 +02001501lyd_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 +02001502 lyd_diff_cb diff_cb, void *cb_data)
Michal Vasko04f85912020-08-07 12:14:58 +02001503{
1504 if (!src_sibling) {
1505 return LY_SUCCESS;
1506 }
1507
1508 return lyd_diff_merge_r(src_sibling, diff_parent, diff_cb, cb_data, diff_first);
1509}
1510
1511API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001512lyd_diff_merge_all(struct lyd_node **diff, const struct lyd_node *src_diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001513{
Michal Vaskofb737aa2020-08-06 13:53:53 +02001514 return lyd_diff_merge_module(diff, src_diff, NULL, NULL, NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001515}
Michal Vasko4231fb62020-07-13 13:54:47 +02001516
1517static LY_ERR
1518lyd_diff_reverse_value(struct lyd_node *leaf, const struct lys_module *mod)
1519{
1520 LY_ERR ret = LY_SUCCESS;
1521 struct lyd_meta *meta;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001522 const char *val1 = NULL;
1523 char *val2;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001524 uint32_t flags;
Michal Vasko4231fb62020-07-13 13:54:47 +02001525
1526 meta = lyd_find_meta(leaf->meta, mod, "orig-value");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001527 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(leaf)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001528
1529 /* orig-value */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001530 val1 = meta->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001531
1532 /* current value */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001533 val2 = strdup(LYD_CANON_VALUE(leaf));
Michal Vasko4231fb62020-07-13 13:54:47 +02001534
1535 /* switch values, keep default flag */
1536 flags = leaf->flags;
1537 LY_CHECK_GOTO(ret = lyd_change_term(leaf, val1), cleanup);
1538 leaf->flags = flags;
1539 LY_CHECK_GOTO(ret = lyd_change_meta(meta, val2), cleanup);
1540
1541cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001542 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001543 return ret;
1544}
1545
1546static LY_ERR
1547lyd_diff_reverse_default(struct lyd_node *node, const struct lys_module *mod)
1548{
1549 struct lyd_meta *meta;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001550 uint32_t flag1, flag2;
Michal Vasko4231fb62020-07-13 13:54:47 +02001551
1552 meta = lyd_find_meta(node->meta, mod, "orig-default");
Michal Vasko610e93b2020-11-09 20:58:32 +01001553 LY_CHECK_ERR_RET(!meta, LOGINT(mod->ctx), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001554
1555 /* orig-default */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001556 if (meta->value.boolean) {
Michal Vasko4231fb62020-07-13 13:54:47 +02001557 flag1 = LYD_DEFAULT;
1558 } else {
1559 flag1 = 0;
1560 }
1561
1562 /* current default */
1563 flag2 = node->flags & LYD_DEFAULT;
1564
Michal Vasko610e93b2020-11-09 20:58:32 +01001565 if (flag1 == flag2) {
1566 /* no default state change so nothing to reverse */
1567 return LY_SUCCESS;
1568 }
1569
Michal Vasko4231fb62020-07-13 13:54:47 +02001570 /* switch defaults */
1571 node->flags &= ~LYD_DEFAULT;
1572 node->flags |= flag1;
1573 LY_CHECK_RET(lyd_change_meta(meta, flag2 ? "true" : "false"));
1574
1575 return LY_SUCCESS;
1576}
1577
1578static LY_ERR
1579lyd_diff_reverse_meta(struct lyd_node *node, const struct lys_module *mod, const char *name1, const char *name2)
1580{
1581 LY_ERR ret = LY_SUCCESS;
1582 struct lyd_meta *meta1, *meta2;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001583 const char *val1 = NULL;
1584 char *val2 = NULL;
Michal Vasko4231fb62020-07-13 13:54:47 +02001585
1586 meta1 = lyd_find_meta(node->meta, mod, name1);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001587 LY_CHECK_ERR_RET(!meta1, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001588
1589 meta2 = lyd_find_meta(node->meta, mod, name2);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001590 LY_CHECK_ERR_RET(!meta2, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001591
1592 /* value1 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001593 val1 = meta1->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001594
1595 /* value2 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001596 val2 = strdup(meta2->value.canonical);
Michal Vasko4231fb62020-07-13 13:54:47 +02001597
1598 /* switch values */
1599 LY_CHECK_GOTO(ret = lyd_change_meta(meta1, val2), cleanup);
1600 LY_CHECK_GOTO(ret = lyd_change_meta(meta2, val1), cleanup);
1601
1602cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001603 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001604 return ret;
1605}
1606
1607API LY_ERR
Michal Vasko66535812020-08-11 08:44:22 +02001608lyd_diff_reverse_all(const struct lyd_node *src_diff, struct lyd_node **diff)
Michal Vasko4231fb62020-07-13 13:54:47 +02001609{
1610 LY_ERR ret = LY_SUCCESS;
1611 const struct lys_module *mod;
Michal Vasko56daf732020-08-10 10:57:18 +02001612 struct lyd_node *root, *elem;
Michal Vasko4231fb62020-07-13 13:54:47 +02001613 enum lyd_diff_op op;
1614
1615 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
1616
1617 if (!src_diff) {
1618 *diff = NULL;
1619 return LY_SUCCESS;
1620 }
1621
1622 /* duplicate diff */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001623 LY_CHECK_RET(lyd_dup_siblings(src_diff, NULL, LYD_DUP_RECURSIVE, diff));
Michal Vasko4231fb62020-07-13 13:54:47 +02001624
1625 /* find module with metadata needed for later */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001626 mod = ly_ctx_get_module_latest(LYD_CTX(src_diff), "yang");
1627 LY_CHECK_ERR_GOTO(!mod, LOGINT(LYD_CTX(src_diff)); ret = LY_EINT, cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001628
1629 LY_LIST_FOR(*diff, root) {
Michal Vasko56daf732020-08-10 10:57:18 +02001630 LYD_TREE_DFS_BEGIN(root, elem) {
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001631 /* skip all keys */
1632 if (!lysc_is_key(elem->schema)) {
1633 /* find operation attribute, if any */
1634 LY_CHECK_GOTO(ret = lyd_diff_get_op(elem, &op), cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001635
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001636 switch (op) {
1637 case LYD_DIFF_OP_CREATE:
1638 /* reverse create to delete */
1639 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_DELETE), cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001640 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001641 case LYD_DIFF_OP_DELETE:
1642 /* reverse delete to create */
1643 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_CREATE), cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001644 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001645 case LYD_DIFF_OP_REPLACE:
1646 switch (elem->schema->nodetype) {
1647 case LYS_LEAF:
1648 /* leaf value change */
1649 LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup);
1650 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1651 break;
1652 case LYS_LEAFLIST:
1653 /* leaf-list move */
1654 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1655 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-value", "value"), cleanup);
1656 break;
1657 case LYS_LIST:
1658 /* list move */
1659 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-key", "key"), cleanup);
1660 break;
1661 default:
1662 LOGINT(LYD_CTX(src_diff));
1663 ret = LY_EINT;
1664 goto cleanup;
1665 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001666 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001667 case LYD_DIFF_OP_NONE:
1668 switch (elem->schema->nodetype) {
1669 case LYS_LEAF:
1670 case LYS_LEAFLIST:
1671 /* default flag change */
1672 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1673 break;
1674 default:
1675 /* nothing to do */
1676 break;
1677 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001678 break;
1679 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001680 }
1681
Michal Vasko56daf732020-08-10 10:57:18 +02001682 LYD_TREE_DFS_END(root, elem);
Michal Vasko4231fb62020-07-13 13:54:47 +02001683 }
1684 }
1685
1686cleanup:
1687 if (ret) {
1688 lyd_free_siblings(*diff);
1689 *diff = NULL;
1690 }
1691 return ret;
1692}