blob: f0dcbda0f4d8b74d38446360cc58885f0c8c3b4e [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 */
Radek Krejcif8dc59a2020-11-25 13:47:44 +010014#define _POSIX_C_SOURCE 200809L /* strdup */
Michal Vaskod59035b2020-07-08 12:00:06 +020015
16#include "diff.h"
17
18#include <assert.h>
19#include <stddef.h>
Radek Krejci47fab892020-11-05 17:02:41 +010020#include <stdlib.h>
Michal Vaskod59035b2020-07-08 12:00:06 +020021#include <string.h>
22
23#include "common.h"
Radek Krejci47fab892020-11-05 17:02:41 +010024#include "context.h"
Michal Vaskod59035b2020-07-08 12:00:06 +020025#include "log.h"
Radek Krejci47fab892020-11-05 17:02:41 +010026#include "plugins_types.h"
27#include "set.h"
28#include "tree.h"
29#include "tree_data.h"
Michal Vaskod59035b2020-07-08 12:00:06 +020030#include "tree_data_internal.h"
31#include "tree_schema.h"
32#include "tree_schema_internal.h"
33
34static const char *
35lyd_diff_op2str(enum lyd_diff_op op)
36{
37 switch (op) {
38 case LYD_DIFF_OP_CREATE:
39 return "create";
40 case LYD_DIFF_OP_DELETE:
41 return "delete";
42 case LYD_DIFF_OP_REPLACE:
43 return "replace";
44 case LYD_DIFF_OP_NONE:
45 return "none";
46 }
47
48 LOGINT(NULL);
49 return NULL;
50}
51
Michal Vaskoe6323f62020-07-09 15:49:02 +020052static enum lyd_diff_op
53lyd_diff_str2op(const char *str)
54{
55 switch (str[0]) {
56 case 'c':
57 assert(!strcmp(str, "create"));
58 return LYD_DIFF_OP_CREATE;
59 case 'd':
60 assert(!strcmp(str, "delete"));
61 return LYD_DIFF_OP_DELETE;
62 case 'r':
63 assert(!strcmp(str, "replace"));
64 return LYD_DIFF_OP_REPLACE;
65 case 'n':
66 assert(!strcmp(str, "none"));
67 return LYD_DIFF_OP_NONE;
68 }
69
70 LOGINT(NULL);
71 return 0;
72}
73
Michal Vaskod59035b2020-07-08 12:00:06 +020074LY_ERR
75lyd_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 +020076 const char *key, const char *value, const char *orig_key, struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +020077{
78 struct lyd_node *dup, *siblings, *match = NULL, *diff_parent = NULL;
79 const struct lyd_node *parent = NULL;
80 const struct lys_module *yang_mod;
81
82 assert(diff);
83
Michal Vasko53d48422020-11-13 18:02:29 +010084 /* replace leaf always needs orig-default and orig-value */
85 assert((node->schema->nodetype != LYS_LEAF) || (op != LYD_DIFF_OP_REPLACE) || (orig_default && orig_value));
86
87 /* create on userord needs key/value */
88 assert((node->schema->nodetype != LYS_LIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_CREATE) ||
89 key);
90 assert((node->schema->nodetype != LYS_LEAFLIST) || !(node->schema->flags & LYS_ORDBY_USER) ||
91 (op != LYD_DIFF_OP_CREATE) || value);
92
93 /* move on userord needs both key and orig-key/value and orig-value */
94 assert((node->schema->nodetype != LYS_LIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_REPLACE) ||
95 (key && orig_key));
96 assert((node->schema->nodetype != LYS_LEAFLIST) || !(node->schema->flags & LYS_ORDBY_USER) ||
97 (op != LYD_DIFF_OP_REPLACE) || (value && orig_value));
98
Michal Vaskod59035b2020-07-08 12:00:06 +020099 /* find the first existing parent */
100 siblings = *diff;
101 while (1) {
102 /* find next node parent */
103 parent = node;
104 while (parent->parent && (!diff_parent || (parent->parent->schema != diff_parent->schema))) {
105 parent = (struct lyd_node *)parent->parent;
106 }
107 if (parent == node) {
108 /* no more parents to find */
109 break;
110 }
111
112 /* check whether it exists in the diff */
113 if (lyd_find_sibling_first(siblings, parent, &match)) {
114 break;
115 }
116
117 /* another parent found */
118 diff_parent = match;
119
120 /* move down in the diff */
Radek Krejcia1c1e542020-09-29 16:06:52 +0200121 siblings = lyd_child_no_keys(match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200122 }
123
124 /* duplicate the subtree (and connect to the diff if possible) */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200125 LY_CHECK_RET(lyd_dup_single(node, (struct lyd_node_inner *)diff_parent,
Michal Vasko871a0252020-11-11 18:35:24 +0100126 LYD_DUP_RECURSIVE | LYD_DUP_NO_META | LYD_DUP_WITH_PARENTS | LYD_DUP_WITH_FLAGS, &dup));
Michal Vaskod59035b2020-07-08 12:00:06 +0200127
128 /* find the first duplicated parent */
129 if (!diff_parent) {
130 diff_parent = (struct lyd_node *)dup->parent;
131 while (diff_parent && diff_parent->parent) {
132 diff_parent = (struct lyd_node *)diff_parent->parent;
133 }
134 } else {
135 diff_parent = (struct lyd_node *)dup;
136 while (diff_parent->parent && (diff_parent->parent->schema == parent->schema)) {
137 diff_parent = (struct lyd_node *)diff_parent->parent;
138 }
139 }
140
141 /* no parent existed, must be manually connected */
142 if (!diff_parent) {
143 /* there actually was no parent to duplicate */
Michal Vaskob104f112020-07-17 09:54:54 +0200144 lyd_insert_sibling(*diff, dup, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200145 } else if (!diff_parent->parent) {
Michal Vaskob104f112020-07-17 09:54:54 +0200146 lyd_insert_sibling(*diff, diff_parent, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200147 }
148
149 /* get module with the operation metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200150 yang_mod = LYD_CTX(node)->list.objs[1];
Michal Vaskod59035b2020-07-08 12:00:06 +0200151 assert(!strcmp(yang_mod->name, "yang"));
152
153 /* add parent operation, if any */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200154 if (diff_parent && (diff_parent != dup)) {
Michal Vasko871a0252020-11-11 18:35:24 +0100155 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), diff_parent, yang_mod, "operation", "none", 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200156 }
157
158 /* add subtree operation */
Michal Vasko871a0252020-11-11 18:35:24 +0100159 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "operation", lyd_diff_op2str(op), 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200160
161 /* orig-default */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200162 if (orig_default) {
Michal Vasko871a0252020-11-11 18:35:24 +0100163 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "orig-default", orig_default, 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200164 }
165
166 /* orig-value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200167 if (orig_value) {
Michal Vasko871a0252020-11-11 18:35:24 +0100168 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "orig-value", orig_value, 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200169 }
170
171 /* key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200172 if (key) {
Michal Vasko871a0252020-11-11 18:35:24 +0100173 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "key", key, 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200174 }
175
176 /* value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200177 if (value) {
Michal Vasko871a0252020-11-11 18:35:24 +0100178 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "value", value, 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200179 }
180
181 /* orig-key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200182 if (orig_key) {
Michal Vasko871a0252020-11-11 18:35:24 +0100183 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "orig-key", orig_key, 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200184 }
185
186 return LY_SUCCESS;
187}
188
189/**
190 * @brief Get a userord entry for a specific user-ordered list/leaf-list. Create if does not exist yet.
191 *
192 * @param[in] first
193 * @param[in] schema Schema node of the list/leaf-list.
194 * @param[in,out] userord Sized array of userord items.
195 * @return Userord item for all the user-ordered list/leaf-list instances.
196 */
197static struct lyd_diff_userord *
198lyd_diff_userord_get(const struct lyd_node *first, const struct lysc_node *schema, struct lyd_diff_userord **userord)
199{
200 struct lyd_diff_userord *item;
201 const struct lyd_node *iter, **node;
202 LY_ARRAY_COUNT_TYPE u;
203
204 LY_ARRAY_FOR(*userord, u) {
205 if ((*userord)[u].schema == schema) {
206 return &(*userord)[u];
207 }
208 }
209
210 /* it was not added yet, add it now */
211 LY_ARRAY_NEW_RET(schema->module->ctx, *userord, item, NULL);
212
213 item->schema = schema;
214 item->pos = 0;
215 item->inst = NULL;
216
217 /* store all the instance pointers in the current order */
218 if (first) {
219 if (first->parent) {
220 iter = first->parent->child;
221 } else {
Radek Krejci1e008d22020-08-17 11:37:37 +0200222 for (iter = first; iter->prev->next; iter = iter->prev) {}
Michal Vaskod59035b2020-07-08 12:00:06 +0200223 }
Michal Vaskod989ba02020-08-24 10:59:24 +0200224 for ( ; iter; iter = iter->next) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200225 if (iter->schema == first->schema) {
226 LY_ARRAY_NEW_RET(schema->module->ctx, item->inst, node, NULL);
227 *node = iter;
228 }
229 }
230 }
231
232 return item;
233}
234
235/**
236 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Can be used only for user-ordered
237 * lists/leaf-lists.
238 *
239 * @param[in] first Node from the first tree, can be NULL (on create).
240 * @param[in] second Node from the second tree, can be NULL (on delete).
241 * @param[in] options Diff options.
242 * @param[in,out] userord Sized array of userord items for keeping the current node order.
243 * @param[out] op Operation.
244 * @param[out] orig_default Original default metadata.
245 * @param[out] value Value metadata.
246 * @param[out] orig_value Original value metadata
247 * @param[out] key Key metadata.
248 * @param[out] orig_key Original key metadata.
249 * @return LY_SUCCESS on success,
250 * @return LY_ENOT if there is no change to be added into diff,
251 * @return LY_ERR value on other errors.
252 */
253static LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200254lyd_diff_userord_attrs(const struct lyd_node *first, const struct lyd_node *second, uint16_t options,
Radek Krejci0f969882020-08-21 16:56:47 +0200255 struct lyd_diff_userord **userord, enum lyd_diff_op *op, const char **orig_default, char **value,
256 char **orig_value, char **key, char **orig_key)
Michal Vaskod59035b2020-07-08 12:00:06 +0200257{
258 const struct lysc_node *schema;
Michal Vaskod59035b2020-07-08 12:00:06 +0200259 size_t buflen, bufused, first_pos, second_pos;
260 struct lyd_diff_userord *userord_item;
261
262 assert(first || second);
263
264 *orig_default = NULL;
265 *value = NULL;
266 *orig_value = NULL;
267 *key = NULL;
268 *orig_key = NULL;
269
270 schema = first ? first->schema : second->schema;
271 assert(lysc_is_userordered(schema));
272
273 /* get userord entry */
274 userord_item = lyd_diff_userord_get(first, schema, userord);
275 LY_CHECK_RET(!userord_item, LY_EMEM);
276
277 /* prepare position of the next instance */
278 second_pos = userord_item->pos++;
279
280 /* find user-ordered first position */
281 if (first) {
282 for (first_pos = second_pos; first_pos < LY_ARRAY_COUNT(userord_item->inst); ++first_pos) {
283 if (userord_item->inst[first_pos] == first) {
284 break;
285 }
286 }
287 assert(first_pos < LY_ARRAY_COUNT(userord_item->inst));
288 } else {
289 first_pos = 0;
290 }
291
292 /* learn operation first */
293 if (!second) {
294 *op = LYD_DIFF_OP_DELETE;
295 } else if (!first) {
296 *op = LYD_DIFF_OP_CREATE;
297 } else {
298 assert(schema->nodetype & (LYS_LIST | LYS_LEAFLIST));
Michal Vasko8f359bf2020-07-28 10:41:15 +0200299 if (lyd_compare_single(second, userord_item->inst[second_pos], 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200300 /* in first, there is a different instance on the second position, we are going to move 'first' node */
301 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200302 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200303 /* default flag change */
304 *op = LYD_DIFF_OP_NONE;
305 } else {
306 /* no changes */
307 return LY_ENOT;
308 }
309 }
310
311 /*
312 * set each attribute correctly based on the operation and node type
313 */
314
315 /* orig-default */
Michal Vasko4b715ca2020-11-11 18:39:57 +0100316 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200317 if (first->flags & LYD_DEFAULT) {
318 *orig_default = "true";
319 } else {
320 *orig_default = "false";
321 }
322 }
323
324 /* value */
325 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
326 if (second_pos) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200327 *value = strdup(LYD_CANON_VALUE(userord_item->inst[second_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200328 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200329 } else {
330 *value = strdup("");
331 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
332 }
333 }
334
335 /* orig-value */
336 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
337 if (first_pos) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200338 *orig_value = strdup(LYD_CANON_VALUE(userord_item->inst[first_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200339 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200340 } else {
341 *orig_value = strdup("");
342 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
343 }
344 }
345
346 /* key */
Michal Vasko44f3d2c2020-08-24 09:49:38 +0200347 if ((schema->nodetype == LYS_LIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200348 if (second_pos) {
349 buflen = bufused = 0;
350 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[second_pos - 1], key, &buflen, &bufused, 0));
351 } else {
352 *key = strdup("");
353 LY_CHECK_ERR_RET(!*key, LOGMEM(schema->module->ctx), LY_EMEM);
354 }
355 }
356
357 /* orig-key */
358 if ((schema->nodetype == LYS_LIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
359 if (first_pos) {
360 buflen = bufused = 0;
361 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[first_pos - 1], orig_key, &buflen, &bufused, 0));
362 } else {
363 *orig_key = strdup("");
364 LY_CHECK_ERR_RET(!*orig_key, LOGMEM(schema->module->ctx), LY_EMEM);
365 }
366 }
367
368 /*
369 * update our instances - apply the change
370 */
371 if (*op == LYD_DIFF_OP_CREATE) {
372 /* insert the instance */
373 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 +0200374 ; , LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200375 if (second_pos < LY_ARRAY_COUNT(userord_item->inst)) {
376 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
377 (LY_ARRAY_COUNT(userord_item->inst) - second_pos) * sizeof *userord_item->inst);
378 }
379 LY_ARRAY_INCREMENT(userord_item->inst);
380 userord_item->inst[second_pos] = second;
381
382 } else if (*op == LYD_DIFF_OP_DELETE) {
383 /* remove the instance */
384 if (first_pos + 1 < LY_ARRAY_COUNT(userord_item->inst)) {
385 memmove(userord_item->inst + first_pos, userord_item->inst + first_pos + 1,
386 (LY_ARRAY_COUNT(userord_item->inst) - first_pos - 1) * sizeof *userord_item->inst);
387 }
388 LY_ARRAY_DECREMENT(userord_item->inst);
389
390 } else if (*op == LYD_DIFF_OP_REPLACE) {
391 /* move the instances */
392 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
393 (first_pos - second_pos) * sizeof *userord_item->inst);
394 userord_item->inst[second_pos] = first;
395 }
396
397 return LY_SUCCESS;
398}
399
400/**
401 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Cannot be used for user-ordered
402 * lists/leaf-lists.
403 *
404 * @param[in] first Node from the first tree, can be NULL (on create).
405 * @param[in] second Node from the second tree, can be NULL (on delete).
406 * @param[in] options Diff options.
407 * @param[out] op Operation.
408 * @param[out] orig_default Original default metadata.
409 * @param[out] orig_value Original value metadata.
410 * @return LY_SUCCESS on success,
411 * @return LY_ENOT if there is no change to be added into diff,
412 * @return LY_ERR value on other errors.
413 */
414static LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200415lyd_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 +0200416 const char **orig_default, char **orig_value)
Michal Vaskod59035b2020-07-08 12:00:06 +0200417{
418 const struct lysc_node *schema;
Michal Vaskod59035b2020-07-08 12:00:06 +0200419
420 assert(first || second);
421
422 *orig_default = NULL;
423 *orig_value = NULL;
424
425 schema = first ? first->schema : second->schema;
426 assert(!lysc_is_userordered(schema));
427
428 /* learn operation first */
429 if (!second) {
430 *op = LYD_DIFF_OP_DELETE;
431 } else if (!first) {
432 *op = LYD_DIFF_OP_CREATE;
433 } else {
434 switch (schema->nodetype) {
435 case LYS_CONTAINER:
436 case LYS_RPC:
437 case LYS_ACTION:
438 case LYS_NOTIF:
439 /* no changes */
440 return LY_ENOT;
441 case LYS_LIST:
442 case LYS_LEAFLIST:
Michal Vasko3a41dff2020-07-15 14:30:28 +0200443 if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200444 /* default flag change */
445 *op = LYD_DIFF_OP_NONE;
446 } else {
447 /* no changes */
448 return LY_ENOT;
449 }
450 break;
451 case LYS_LEAF:
452 case LYS_ANYXML:
453 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +0200454 if (lyd_compare_single(first, second, 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200455 /* different values */
456 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200457 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200458 /* default flag change */
459 *op = LYD_DIFF_OP_NONE;
460 } else {
461 /* no changes */
462 return LY_ENOT;
463 }
464 break;
465 default:
466 LOGINT_RET(schema->module->ctx);
467 }
468 }
469
470 /*
471 * set each attribute correctly based on the operation and node type
472 */
473
474 /* orig-default */
Michal Vasko4b715ca2020-11-11 18:39:57 +0100475 if ((schema->nodetype & LYD_NODE_TERM) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200476 if (first->flags & LYD_DEFAULT) {
477 *orig_default = "true";
478 } else {
479 *orig_default = "false";
480 }
481 }
482
483 /* orig-value */
484 if ((schema->nodetype == LYS_LEAF) && (*op == LYD_DIFF_OP_REPLACE)) {
485 /* leaf */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200486 *orig_value = strdup(LYD_CANON_VALUE(first));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200487 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200488 }
489
490 return LY_SUCCESS;
491}
492
493/**
494 * @brief Perform diff for all siblings at certain depth, recursively.
495 *
496 * For user-ordered lists/leaf-lists a specific structure is used for storing
497 * the current order. The idea is to apply all the generated diff changes
498 * virtually on the first tree so that we can continue to generate correct
499 * changes after some were already generated.
500 *
501 * The algorithm then uses second tree position-based changes with a before
502 * (preceding) item anchor.
503 *
504 * Example:
505 *
506 * Virtual first tree leaf-list order:
507 * 1 2 [3] 4 5
508 *
509 * Second tree leaf-list order:
510 * 1 2 [5] 3 4
511 *
512 * We are at the 3rd node now. We look at whether the nodes on the 3rd position
513 * match - they do not - move nodes so that the 3rd position node is final ->
514 * -> move node 5 to the 3rd position -> move node 5 after node 2.
515 *
516 * Required properties:
517 * Stored operations (move) should not be affected by later operations -
518 * - would cause a redundantly long list of operations, possibly inifinite.
519 *
520 * Implemenation justification:
521 * First, all delete operations and only then move/create operations are stored.
522 * Also, preceding anchor is used and after each iteration another node is
523 * at its final position. That results in the invariant that all preceding
524 * nodes are final and will not be changed by the later operations, meaning
525 * they can safely be used as anchors for the later operations.
526 *
527 * @param[in] first First tree first sibling.
528 * @param[in] second Second tree first sibling.
529 * @param[in] options Diff options.
Michal Vasko3a41dff2020-07-15 14:30:28 +0200530 * @param[in] nosiblings Whether to skip following siblings.
Michal Vaskod59035b2020-07-08 12:00:06 +0200531 * @param[in,out] diff Diff to append to.
532 * @return LY_ERR value.
533 */
534static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200535lyd_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 +0200536 struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +0200537{
538 LY_ERR ret = LY_SUCCESS;
539 const struct lyd_node *iter_first, *iter_second;
540 struct lyd_node *match_second, *match_first;
Michal Vaskod59035b2020-07-08 12:00:06 +0200541 struct lyd_diff_userord *userord = NULL;
542 LY_ARRAY_COUNT_TYPE u;
543 enum lyd_diff_op op;
544 const char *orig_default;
545 char *orig_value, *key, *value, *orig_key;
546
Michal Vaskod59035b2020-07-08 12:00:06 +0200547 /* compare first tree to the second tree - delete, replace, none */
548 LY_LIST_FOR(first, iter_first) {
549 assert(!(iter_first->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200550 if ((iter_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200551 /* skip default nodes */
552 continue;
553 }
554
555 if (iter_first->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
556 /* try to find the exact instance */
557 lyd_find_sibling_first(second, iter_first, &match_second);
558 } else {
559 /* try to simply find the node, there cannot be more instances */
560 lyd_find_sibling_val(second, iter_first->schema, NULL, 0, &match_second);
561 }
562
Michal Vasko3a41dff2020-07-15 14:30:28 +0200563 if (match_second && (match_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200564 /* ignore default nodes */
565 match_second = NULL;
566 }
567
568 if (lysc_is_userordered(iter_first->schema)) {
569 if (match_second) {
570 /* we are handling only user-ordered node delete now */
571 continue;
572 }
573
574 /* get all the attributes */
575 LY_CHECK_GOTO(lyd_diff_userord_attrs(iter_first, match_second, options, &userord, &op, &orig_default,
Michal Vasko69730152020-10-09 16:30:07 +0200576 &value, &orig_value, &key, &orig_key), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200577
578 /* there must be changes, it is deleted */
579 assert(op == LYD_DIFF_OP_DELETE);
580 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, key, value, orig_key, diff);
581
582 free(orig_value);
583 free(key);
584 free(value);
585 free(orig_key);
586 LY_CHECK_GOTO(ret, cleanup);
587 } else {
588 /* get all the attributes */
589 ret = lyd_diff_attrs(iter_first, match_second, options, &op, &orig_default, &orig_value);
590
591 /* add into diff if there are any changes */
592 if (!ret) {
593 if (op == LYD_DIFF_OP_DELETE) {
594 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, NULL, NULL, NULL, diff);
595 } else {
Michal Vasko3c2dd6c2020-11-06 17:38:55 +0100596 assert(match_second);
Michal Vaskod59035b2020-07-08 12:00:06 +0200597 ret = lyd_diff_add(match_second, op, orig_default, orig_value, NULL, NULL, NULL, diff);
598 }
599
600 free(orig_value);
601 LY_CHECK_GOTO(ret, cleanup);
602 } else if (ret == LY_ENOT) {
603 ret = LY_SUCCESS;
604 } else {
605 goto cleanup;
606 }
607 }
608
609 /* check descendants, if any, recursively */
610 if (match_second) {
Radek Krejcia1c1e542020-09-29 16:06:52 +0200611 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 +0200612 0, diff), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200613 }
614
615 if (nosiblings) {
616 break;
617 }
618 }
619
620 /* reset all cached positions */
621 LY_ARRAY_FOR(userord, u) {
622 userord[u].pos = 0;
623 }
624
625 /* compare second tree to the first tree - create, user-ordered move */
626 LY_LIST_FOR(second, iter_second) {
627 assert(!(iter_second->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200628 if ((iter_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200629 /* skip default nodes */
630 continue;
631 }
632
633 if (iter_second->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
634 lyd_find_sibling_first(first, iter_second, &match_first);
635 } else {
636 lyd_find_sibling_val(first, iter_second->schema, NULL, 0, &match_first);
637 }
638
Michal Vasko3a41dff2020-07-15 14:30:28 +0200639 if (match_first && (match_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200640 /* ignore default nodes */
641 match_first = NULL;
642 }
643
644 if (lysc_is_userordered(iter_second->schema)) {
645 /* get all the attributes */
646 ret = lyd_diff_userord_attrs(match_first, iter_second, options, &userord, &op, &orig_default,
Michal Vasko69730152020-10-09 16:30:07 +0200647 &value, &orig_value, &key, &orig_key);
Michal Vaskod59035b2020-07-08 12:00:06 +0200648
649 /* add into diff if there are any changes */
650 if (!ret) {
651 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, key, value, orig_key, diff);
652
653 free(orig_value);
654 free(key);
655 free(value);
656 free(orig_key);
657 LY_CHECK_GOTO(ret, cleanup);
658 } else if (ret == LY_ENOT) {
659 ret = LY_SUCCESS;
660 } else {
661 goto cleanup;
662 }
663 } else if (!match_first) {
664 /* get all the attributes */
665 LY_CHECK_GOTO(lyd_diff_attrs(match_first, iter_second, options, &op, &orig_default, &orig_value), cleanup);
666
667 /* there must be changes, it is created */
668 assert(op == LYD_DIFF_OP_CREATE);
669 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, NULL, NULL, NULL, diff);
670
671 free(orig_value);
672 LY_CHECK_GOTO(ret, cleanup);
673 } /* else was handled */
674
675 if (nosiblings) {
676 break;
677 }
678 }
679
680cleanup:
681 LY_ARRAY_FOR(userord, u) {
682 LY_ARRAY_FREE(userord[u].inst);
683 }
684 LY_ARRAY_FREE(userord);
685 return ret;
686}
687
Michal Vasko3a41dff2020-07-15 14:30:28 +0200688static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200689lyd_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 +0200690{
691 const struct ly_ctx *ctx;
692
693 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
694
695 if (first) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200696 ctx = LYD_CTX(first);
Michal Vaskod59035b2020-07-08 12:00:06 +0200697 } else if (second) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200698 ctx = LYD_CTX(second);
Michal Vaskod59035b2020-07-08 12:00:06 +0200699 } else {
700 ctx = NULL;
701 }
702
703 if (first && second && (lysc_data_parent(first->schema) != lysc_data_parent(second->schema))) {
704 LOGERR(ctx, LY_EINVAL, "Invalid arguments - cannot create diff for unrelated data (%s()).", __func__);
705 return LY_EINVAL;
706 }
707
708 *diff = NULL;
709
Michal Vasko3a41dff2020-07-15 14:30:28 +0200710 return lyd_diff_siblings_r(first, second, options, nosiblings, diff);
711}
712
713API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200714lyd_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 +0200715{
716 return lyd_diff(first, second, options, 1, diff);
717}
718
719API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200720lyd_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 +0200721{
722 return lyd_diff(first, second, options, 0, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200723}
724
725/**
726 * @brief Find a matching node in data tree for a diff node.
727 *
728 * @param[in] first_node First sibling in the data tree.
729 * @param[in] diff_node Diff node to match.
Michal Vaskoe6323f62020-07-09 15:49:02 +0200730 * @param[out] match_p Matching node, NULL if no found.
Michal Vaskod59035b2020-07-08 12:00:06 +0200731 */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200732static void
Michal Vaskod59035b2020-07-08 12:00:06 +0200733lyd_diff_find_node(const struct lyd_node *first_node, const struct lyd_node *diff_node, struct lyd_node **match_p)
734{
735 if (diff_node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
736 /* try to find the exact instance */
737 lyd_find_sibling_first(first_node, diff_node, match_p);
738 } else {
739 /* try to simply find the node, there cannot be more instances */
740 lyd_find_sibling_val(first_node, diff_node->schema, NULL, 0, match_p);
741 }
Michal Vaskod59035b2020-07-08 12:00:06 +0200742}
743
744/**
745 * @brief Learn operation of a diff node.
746 *
747 * @param[in] diff_node Diff node.
748 * @param[out] op Operation.
Michal Vaskod59035b2020-07-08 12:00:06 +0200749 * @return LY_ERR value.
750 */
751static LY_ERR
Michal Vaskoe6323f62020-07-09 15:49:02 +0200752lyd_diff_get_op(const struct lyd_node *diff_node, enum lyd_diff_op *op)
Michal Vaskod59035b2020-07-08 12:00:06 +0200753{
754 struct lyd_meta *meta = NULL;
755 const struct lyd_node *diff_parent;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200756 const char *str;
Michal Vaskod59035b2020-07-08 12:00:06 +0200757
758 for (diff_parent = diff_node; diff_parent; diff_parent = (struct lyd_node *)diff_parent->parent) {
759 LY_LIST_FOR(diff_parent->meta, meta) {
760 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200761 str = meta->value.canonical;
Michal Vaskod59035b2020-07-08 12:00:06 +0200762 if ((str[0] == 'r') && (diff_parent != diff_node)) {
763 /* we do not care about this operation if it's in our parent */
764 continue;
765 }
Michal Vaskoe6323f62020-07-09 15:49:02 +0200766 *op = lyd_diff_str2op(str);
Michal Vaskod59035b2020-07-08 12:00:06 +0200767 break;
768 }
769 }
770 if (meta) {
771 break;
772 }
773 }
Michal Vaskob7be7a82020-08-20 09:09:04 +0200774 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_node)), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +0200775
Michal Vaskod59035b2020-07-08 12:00:06 +0200776 return LY_SUCCESS;
777}
778
779/**
780 * @brief Insert a diff node into a data tree.
781 *
782 * @param[in,out] first_node First sibling of the data tree.
783 * @param[in] parent_node Data tree sibling parent node.
784 * @param[in] new_node Node to insert.
785 * @param[in] keys_or_value Optional predicate of relative (leaf-)list instance. If not set, the user-ordered
786 * instance will be inserted at the first position.
787 * @return err_info, NULL on success.
788 */
789static LY_ERR
790lyd_diff_insert(struct lyd_node **first_node, struct lyd_node *parent_node, struct lyd_node *new_node,
Radek Krejci0f969882020-08-21 16:56:47 +0200791 const char *key_or_value)
Michal Vaskod59035b2020-07-08 12:00:06 +0200792{
793 LY_ERR ret;
794 struct lyd_node *anchor;
795
796 assert(new_node);
797
798 if (!*first_node) {
799 if (!parent_node) {
800 /* no parent or siblings */
801 *first_node = new_node;
802 return LY_SUCCESS;
803 }
804
805 /* simply insert into parent, no other children */
806 if (key_or_value) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200807 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
Michal Vasko69730152020-10-09 16:30:07 +0200808 new_node->schema->name);
Michal Vaskod59035b2020-07-08 12:00:06 +0200809 return LY_EINVAL;
810 }
Michal Vaskob104f112020-07-17 09:54:54 +0200811 return lyd_insert_child(parent_node, new_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200812 }
813
814 assert(!(*first_node)->parent || ((struct lyd_node *)(*first_node)->parent == parent_node));
815
Michal Vaskod59035b2020-07-08 12:00:06 +0200816 if (!lysc_is_userordered(new_node->schema)) {
Michal Vaskob104f112020-07-17 09:54:54 +0200817 /* simple insert */
818 return lyd_insert_sibling(*first_node, new_node, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200819 }
820
821 if (key_or_value) {
822 /* find the anchor sibling */
823 ret = lyd_find_sibling_val(*first_node, new_node->schema, key_or_value, 0, &anchor);
824 if (ret == LY_ENOTFOUND) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200825 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
Michal Vasko69730152020-10-09 16:30:07 +0200826 new_node->schema->name);
Michal Vaskod59035b2020-07-08 12:00:06 +0200827 return LY_EINVAL;
828 } else if (ret) {
829 return ret;
830 }
831
832 /* insert after */
833 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
834 assert(new_node->prev == anchor);
835 if (*first_node == new_node) {
836 *first_node = anchor;
837 }
838 } else {
839 if ((*first_node)->schema->flags & LYS_KEY) {
840 assert(parent_node && (parent_node->schema->nodetype == LYS_LIST));
841
842 /* find last key */
843 anchor = *first_node;
844 while (anchor->next && (anchor->next->schema->flags & LYS_KEY)) {
845 anchor = anchor->next;
846 }
847 /* insert after the last key */
848 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
849 } else {
850 /* insert at the beginning */
851 LY_CHECK_RET(lyd_insert_before(*first_node, new_node));
852 *first_node = new_node;
853 }
854 }
855
856 return LY_SUCCESS;
857}
858
859/**
860 * @brief Apply diff subtree on data tree nodes, recursively.
861 *
862 * @param[in,out] first_node First sibling of the data tree.
863 * @param[in] parent_node Parent of the first sibling.
864 * @param[in] diff_node Current diff node.
Michal Vaskoe6323f62020-07-09 15:49:02 +0200865 * @param[in] diff_cb Optional diff callback.
866 * @param[in] cb_data User data for @p diff_cb.
Michal Vaskod59035b2020-07-08 12:00:06 +0200867 * @return LY_ERR value.
868 */
869static LY_ERR
870lyd_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 +0200871 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskod59035b2020-07-08 12:00:06 +0200872{
873 LY_ERR ret;
874 struct lyd_node *match, *diff_child;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200875 const char *str_val;
876 enum lyd_diff_op op;
877 struct lyd_meta *meta;
Michal Vaskob7be7a82020-08-20 09:09:04 +0200878 const struct ly_ctx *ctx = LYD_CTX(diff_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200879
880 /* read all the valid attributes */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200881 LY_CHECK_RET(lyd_diff_get_op(diff_node, &op));
Michal Vaskod59035b2020-07-08 12:00:06 +0200882
Michal Vaskoe6323f62020-07-09 15:49:02 +0200883 /* handle specific user-ordered (leaf-)lists operations separately */
884 if (lysc_is_userordered(diff_node->schema) && ((op == LYD_DIFF_OP_CREATE) || (op == LYD_DIFF_OP_REPLACE))) {
885 if (op == LYD_DIFF_OP_REPLACE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200886 /* find the node (we must have some siblings because the node was only moved) */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200887 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200888 } else {
Michal Vasko3a41dff2020-07-15 14:30:28 +0200889 /* duplicate the node */
890 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +0200891 }
892
Michal Vaskoe6323f62020-07-09 15:49:02 +0200893 /* get "key" or "value" metadata string value */
894 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 +0200895 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_node)), LY_EINT);
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200896 str_val = meta->value.canonical;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200897
Michal Vaskod59035b2020-07-08 12:00:06 +0200898 /* insert/move the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200899 if (str_val[0]) {
900 ret = lyd_diff_insert(first_node, parent_node, match, str_val);
Michal Vaskod59035b2020-07-08 12:00:06 +0200901 } else {
902 ret = lyd_diff_insert(first_node, parent_node, match, NULL);
903 }
904 if (ret) {
Michal Vaskoe6323f62020-07-09 15:49:02 +0200905 if (op == LYD_DIFF_OP_CREATE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200906 lyd_free_tree(match);
907 }
908 return ret;
909 }
910
911 goto next_iter_r;
912 }
913
914 /* apply operation */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200915 switch (op) {
916 case LYD_DIFF_OP_NONE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200917 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200918 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200919
920 if (match->schema->nodetype & LYD_NODE_TERM) {
921 /* special case of only dflt flag change */
922 if (diff_node->flags & LYD_DEFAULT) {
923 match->flags |= LYD_DEFAULT;
924 } else {
925 match->flags &= ~LYD_DEFAULT;
926 }
927 } else {
928 /* none operation on nodes without children is redundant and hence forbidden */
Radek Krejcia1c1e542020-09-29 16:06:52 +0200929 if (!lyd_child_no_keys(diff_node)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200930 LOGINT_RET(ctx);
931 }
932 }
933 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200934 case LYD_DIFF_OP_CREATE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200935 /* duplicate the node */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200936 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +0200937
938 /* insert it at the end */
939 ret = 0;
Michal Vaskob104f112020-07-17 09:54:54 +0200940 if (parent_node) {
941 ret = lyd_insert_child(parent_node, match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200942 } else {
Michal Vaskob104f112020-07-17 09:54:54 +0200943 ret = lyd_insert_sibling(*first_node, match, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200944 }
945 if (ret) {
946 lyd_free_tree(match);
947 return ret;
948 }
949
950 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200951 case LYD_DIFF_OP_DELETE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200952 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200953 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200954
955 /* remove it */
956 if ((match == *first_node) && !match->parent) {
957 assert(!parent_node);
958 /* we have removed the top-level node */
959 *first_node = (*first_node)->next;
960 }
961 lyd_free_tree(match);
962
963 /* we are not going recursively in this case, the whole subtree was already deleted */
964 return LY_SUCCESS;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200965 case LYD_DIFF_OP_REPLACE:
Michal Vaskod59035b2020-07-08 12:00:06 +0200966 LY_CHECK_ERR_RET(diff_node->schema->nodetype != LYS_LEAF, LOGINT(ctx), LY_EINT);
967
968 /* find the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200969 lyd_diff_find_node(*first_node, diff_node, &match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200970
971 /* update its value */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200972 ret = lyd_change_term(match, LYD_CANON_VALUE(diff_node));
Michal Vaskod59035b2020-07-08 12:00:06 +0200973 if (ret && (ret != LY_EEXIST)) {
974 LOGINT_RET(ctx);
975 }
976
977 /* with flags */
978 match->flags = diff_node->flags;
979 break;
980 default:
981 LOGINT_RET(ctx);
982 }
983
984next_iter_r:
985 if (diff_cb) {
986 /* call callback */
987 LY_CHECK_RET(diff_cb(diff_node, match, cb_data));
988 }
989
990 /* apply diff recursively */
Radek Krejcia1c1e542020-09-29 16:06:52 +0200991 LY_LIST_FOR(lyd_child_no_keys(diff_node), diff_child) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200992 LY_CHECK_RET(lyd_diff_apply_r(lyd_node_children_p(match), match, diff_child, diff_cb, cb_data));
993 }
994
995 return LY_SUCCESS;
996}
997
998API LY_ERR
999lyd_diff_apply_module(struct lyd_node **data, const struct lyd_node *diff, const struct lys_module *mod,
Radek Krejci0f969882020-08-21 16:56:47 +02001000 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskod59035b2020-07-08 12:00:06 +02001001{
1002 const struct lyd_node *root;
1003
1004 LY_LIST_FOR(diff, root) {
1005 if (mod && (lyd_owner_module(root) != mod)) {
1006 /* skip data nodes from different modules */
1007 continue;
1008 }
1009
1010 /* apply relevant nodes from the diff datatree */
1011 LY_CHECK_RET(lyd_diff_apply_r(data, NULL, root, diff_cb, cb_data));
1012 }
1013
1014 return LY_SUCCESS;
1015}
1016
1017API LY_ERR
Michal Vasko3a41dff2020-07-15 14:30:28 +02001018lyd_diff_apply_all(struct lyd_node **data, const struct lyd_node *diff)
Michal Vaskod59035b2020-07-08 12:00:06 +02001019{
1020 return lyd_diff_apply_module(data, diff, NULL, NULL, NULL);
1021}
Michal Vaskoe6323f62020-07-09 15:49:02 +02001022
1023/**
1024 * @brief Update operations on a diff node when the new operation is NONE.
1025 *
1026 * @param[in] diff_match Node from the diff.
1027 * @param[in] cur_op Current operation of the diff node.
1028 * @param[in] src_diff Current source diff node.
1029 * @return LY_ERR value.
1030 */
1031static LY_ERR
1032lyd_diff_merge_none(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1033{
1034 switch (cur_op) {
1035 case LYD_DIFF_OP_NONE:
1036 case LYD_DIFF_OP_CREATE:
1037 case LYD_DIFF_OP_REPLACE:
1038 if (src_diff->schema->nodetype & LYD_NODE_TERM) {
1039 /* NONE on a term means only its dflt flag was changed */
1040 diff_match->flags &= ~LYD_DEFAULT;
1041 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1042 }
1043 break;
1044 default:
1045 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001046 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001047 }
1048
1049 return LY_SUCCESS;
1050}
1051
1052/**
1053 * @brief Remove an attribute from a node.
1054 *
1055 * @param[in] node Node with the metadata.
1056 * @param[in] name Metadata name.
1057 */
1058static void
1059lyd_diff_del_meta(struct lyd_node *node, const char *name)
1060{
1061 struct lyd_meta *meta;
1062
1063 LY_LIST_FOR(node->meta, meta) {
1064 if (!strcmp(meta->name, name) && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001065 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001066 return;
1067 }
1068 }
1069
1070 assert(0);
1071}
1072
1073/**
1074 * @brief Set a specific operation of a node. Delete the previous operation, if any.
Michal Vasko871a0252020-11-11 18:35:24 +01001075 * Does not change the default flag.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001076 *
1077 * @param[in] node Node to change.
1078 * @param[in] op Operation to set.
1079 * @return LY_ERR value.
1080 */
1081static LY_ERR
1082lyd_diff_change_op(struct lyd_node *node, enum lyd_diff_op op)
1083{
1084 struct lyd_meta *meta;
1085
1086 LY_LIST_FOR(node->meta, meta) {
1087 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001088 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001089 break;
1090 }
1091 }
1092
Michal Vasko871a0252020-11-11 18:35:24 +01001093 return lyd_new_meta(LYD_CTX(node), node, NULL, "yang:operation", lyd_diff_op2str(op), 0, NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001094}
1095
1096/**
1097 * @brief Update operations on a diff node when the new operation is REPLACE.
1098 *
1099 * @param[in] diff_match Node from the diff.
1100 * @param[in] cur_op Current operation of the diff node.
1101 * @param[in] src_diff Current source diff node.
1102 * @return LY_ERR value.
1103 */
1104static LY_ERR
1105lyd_diff_merge_replace(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1106{
1107 LY_ERR ret;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001108 const char *str_val, *meta_name;
1109 struct lyd_meta *meta;
1110 const struct lys_module *mod;
1111 const struct lyd_node_any *any;
1112
1113 /* get "yang" module for the metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001114 mod = ly_ctx_get_module_latest(LYD_CTX(diff_match), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001115 assert(mod);
1116
1117 switch (cur_op) {
1118 case LYD_DIFF_OP_REPLACE:
1119 case LYD_DIFF_OP_CREATE:
1120 switch (diff_match->schema->nodetype) {
1121 case LYS_LIST:
1122 case LYS_LEAFLIST:
Michal Vasko4231fb62020-07-13 13:54:47 +02001123 /* it was created/moved somewhere, but now it will be created/moved somewhere else,
Michal Vaskoe6323f62020-07-09 15:49:02 +02001124 * keep orig_key/orig_value (only replace oper) and replace key/value */
1125 assert(lysc_is_userordered(diff_match->schema));
1126 meta_name = (diff_match->schema->nodetype == LYS_LIST ? "key" : "value");
1127
1128 lyd_diff_del_meta(diff_match, meta_name);
1129 meta = lyd_find_meta(src_diff->meta, mod, meta_name);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001130 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001131 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001132 break;
1133 case LYS_LEAF:
1134 /* replaced with the exact same value, impossible */
Michal Vasko8f359bf2020-07-28 10:41:15 +02001135 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001136 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001137 }
1138
Michal Vaskoe6323f62020-07-09 15:49:02 +02001139 /* modify the node value */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001140 if (lyd_change_term(diff_match, LYD_CANON_VALUE(src_diff))) {
1141 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001142 }
1143
Michal Vasko8caadab2020-11-05 17:38:15 +01001144 if (cur_op == LYD_DIFF_OP_REPLACE) {
1145 /* compare values whether there is any change at all */
1146 meta = lyd_find_meta(diff_match->meta, mod, "orig-value");
1147 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_match)), LY_EINT);
1148 str_val = meta->value.canonical;
1149 ret = lyd_value_compare((struct lyd_node_term *)diff_match, str_val, strlen(str_val));
1150 if (!ret) {
1151 /* values are the same, remove orig-value meta and set oper to NONE */
1152 lyd_free_meta_single(meta);
1153 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1154 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001155 }
1156
1157 /* modify the default flag */
1158 diff_match->flags &= ~LYD_DEFAULT;
1159 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1160 break;
1161 case LYS_ANYXML:
1162 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +02001163 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001164 /* replaced with the exact same value, impossible */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001165 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001166 }
1167
1168 /* modify the node value */
1169 any = (struct lyd_node_any *)src_diff;
1170 LY_CHECK_RET(lyd_any_copy_value(diff_match, &any->value, any->value_type));
1171 break;
1172 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001173 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001174 }
1175 break;
1176 case LYD_DIFF_OP_NONE:
1177 /* it is moved now */
1178 assert(lysc_is_userordered(diff_match->schema) && (diff_match->schema->nodetype == LYS_LIST));
1179
1180 /* change the operation */
1181 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1182
1183 /* set orig-key and key metadata */
1184 meta = lyd_find_meta(src_diff->meta, mod, "orig-key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001185 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001186 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001187
1188 meta = lyd_find_meta(src_diff->meta, mod, "key");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001189 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001190 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001191 break;
1192 default:
1193 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001194 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001195 }
1196
1197 return LY_SUCCESS;
1198}
1199
1200/**
1201 * @brief Update operations in a diff node when the new operation is CREATE.
1202 *
1203 * @param[in] diff_match Node from the diff.
1204 * @param[in] cur_op Current operation of the diff node.
1205 * @param[in] src_diff Current source diff node.
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001206 * @param[in] options Diff merge options.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001207 * @return LY_ERR value.
1208 */
1209static LY_ERR
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001210lyd_diff_merge_create(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff, uint16_t options)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001211{
1212 struct lyd_node *child;
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001213 const struct lysc_node_leaf *sleaf = NULL;
Michal Vasko871a0252020-11-11 18:35:24 +01001214 uint32_t trg_flags;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001215
1216 switch (cur_op) {
1217 case LYD_DIFF_OP_DELETE:
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001218 if ((options & LYD_DIFF_MERGE_DEFAULTS) && (diff_match->schema->nodetype == LYS_LEAF)) {
1219 /* we are dealing with a leaf and are handling default values specially (as explicit nodes) */
Michal Vasko5632e0d2020-07-31 14:13:37 +02001220 sleaf = (struct lysc_node_leaf *)diff_match->schema;
Michal Vasko5632e0d2020-07-31 14:13:37 +02001221 }
1222
Michal Vasko871a0252020-11-11 18:35:24 +01001223 /* remember current flags */
1224 trg_flags = diff_match->flags;
1225
Michal Vasko69730152020-10-09 16:30:07 +02001226 if (sleaf && sleaf->dflt &&
1227 !sleaf->dflt->realtype->plugin->compare(sleaf->dflt, &((struct lyd_node_term *)src_diff)->value)) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001228 /* we deleted it, so a default value was in-use, and it matches the created value -> operation NONE */
1229 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
Michal Vasko5632e0d2020-07-31 14:13:37 +02001230 } else if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001231 /* deleted + created -> operation NONE */
1232 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001233 } else {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001234 /* we deleted it, but it was created with a different value -> operation REPLACE */
1235 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1236
1237 /* current value is the previous one (meta) */
Michal Vasko871a0252020-11-11 18:35:24 +01001238 LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-value",
1239 LYD_CANON_VALUE(diff_match), 0, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001240
1241 /* update the value itself */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001242 LY_CHECK_RET(lyd_change_term(diff_match, LYD_CANON_VALUE(src_diff)));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001243 }
1244
1245 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
Michal Vasko4b715ca2020-11-11 18:39:57 +01001246 /* add orig-dflt metadata */
1247 LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-default",
1248 trg_flags & LYD_DEFAULT ? "true" : "false", 0, NULL));
1249
Michal Vaskoe6323f62020-07-09 15:49:02 +02001250 /* update dflt flag itself */
1251 diff_match->flags &= ~LYD_DEFAULT;
1252 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1253 } else {
1254 /* but the operation of its children should remain DELETE */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001255 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001256 LY_CHECK_RET(lyd_diff_change_op(child, LYD_DIFF_OP_DELETE));
1257 }
1258 }
1259 break;
1260 default:
1261 /* create and replace operations are not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001262 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001263 }
1264
1265 return LY_SUCCESS;
1266}
1267
1268/**
1269 * @brief Update operations on a diff node when the new operation is DELETE.
1270 *
1271 * @param[in] diff_match Node from the diff.
1272 * @param[in] cur_op Current operation of the diff node.
1273 * @param[in] src_diff Current source diff node.
1274 * @return LY_ERR value.
1275 */
1276static LY_ERR
1277lyd_diff_merge_delete(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1278{
1279 struct lyd_node *next, *child;
1280
1281 /* we can delete only exact existing nodes */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001282 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 +02001283
1284 switch (cur_op) {
1285 case LYD_DIFF_OP_CREATE:
1286 /* it was created, but then deleted -> set NONE operation */
1287 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1288
1289 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1290 /* add orig-default meta because it is expected */
Michal Vasko871a0252020-11-11 18:35:24 +01001291 LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-default",
1292 diff_match->flags & LYD_DEFAULT ? "true" : "false", 0, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001293 } else {
1294 /* keep operation for all descendants (for now) */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001295 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001296 LY_CHECK_RET(lyd_diff_change_op(child, cur_op));
1297 }
1298 }
1299 break;
1300 case LYD_DIFF_OP_REPLACE:
1301 /* similar to none operation but also remove the redundant attribute */
1302 lyd_diff_del_meta(diff_match, "orig-value");
Radek Krejcif13b87b2020-12-01 22:02:17 +01001303 /* fall through */
Michal Vaskoe6323f62020-07-09 15:49:02 +02001304 case LYD_DIFF_OP_NONE:
1305 /* it was not modified, but should be deleted -> set DELETE operation */
1306 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_DELETE));
1307
Michal Vasko5632e0d2020-07-31 14:13:37 +02001308 /* all descendants not in the diff will be deleted and redundant in the diff, so remove them */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001309 LY_LIST_FOR_SAFE(lyd_child_no_keys(diff_match), next, child) {
1310 if (lyd_find_sibling_first(lyd_child(src_diff), child, NULL) == LY_ENOTFOUND) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001311 lyd_free_tree(child);
1312 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001313 }
1314 break;
1315 default:
1316 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001317 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001318 }
1319
1320 return LY_SUCCESS;
1321}
1322
1323/**
1324 * @brief Check whether this diff node is redundant (does not change data).
1325 *
1326 * @param[in] diff Diff node.
1327 * @return 0 if not, non-zero if it is.
1328 */
1329static int
1330lyd_diff_is_redundant(struct lyd_node *diff)
1331{
1332 enum lyd_diff_op op;
1333 struct lyd_meta *meta, *orig_val_meta = NULL, *val_meta = NULL;
1334 struct lyd_node *child;
1335 const struct lys_module *mod;
1336 const char *str;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001337
1338 assert(diff);
1339
Radek Krejcia1c1e542020-09-29 16:06:52 +02001340 child = lyd_child_no_keys(diff);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001341 mod = ly_ctx_get_module_latest(LYD_CTX(diff), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001342 assert(mod);
1343
1344 /* get node operation */
Michal Vasko53bf6f22020-07-14 08:23:40 +02001345 LY_CHECK_RET(lyd_diff_get_op(diff, &op), 0);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001346
1347 if ((op == LYD_DIFF_OP_REPLACE) && lysc_is_userordered(diff->schema)) {
1348 /* check for redundant move */
1349 orig_val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "orig-key" : "orig-value"));
1350 val_meta = lyd_find_meta(diff->meta, mod, (diff->schema->nodetype == LYS_LIST ? "key" : "value"));
1351 assert(orig_val_meta && val_meta);
1352
1353 if (!lyd_compare_meta(orig_val_meta, val_meta)) {
1354 /* there is actually no move */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001355 lyd_free_meta_single(orig_val_meta);
1356 lyd_free_meta_single(val_meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001357 if (child) {
1358 /* change operation to NONE, we have siblings */
1359 lyd_diff_change_op(diff, LYD_DIFF_OP_NONE);
1360 return 0;
1361 }
1362
1363 /* redundant node, BUT !!
1364 * In diff the move operation is always converted to be INSERT_AFTER, which is fine
1365 * because the data that this is applied on should not change for the diff lifetime.
1366 * However, when we are merging 2 diffs, this conversion is actually lossy because
1367 * if the data change, the move operation can also change its meaning. In this specific
1368 * case the move operation will be lost. But it can be considered a feature, it is not supported.
1369 */
1370 return 1;
1371 }
1372 } else if ((op == LYD_DIFF_OP_NONE) && (diff->schema->nodetype & LYD_NODE_TERM)) {
1373 /* check whether at least the default flags are different */
1374 meta = lyd_find_meta(diff->meta, mod, "orig-default");
1375 assert(meta);
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001376 str = meta->value.canonical;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001377
1378 /* if previous and current dflt flags are the same, this node is redundant */
1379 if ((!strcmp(str, "true") && (diff->flags & LYD_DEFAULT)) || (!strcmp(str, "false") && !(diff->flags & LYD_DEFAULT))) {
1380 return 1;
1381 }
1382 return 0;
1383 }
1384
1385 if (!child && (op == LYD_DIFF_OP_NONE)) {
1386 return 1;
1387 }
1388
1389 return 0;
1390}
1391
1392/**
1393 * @brief Merge sysrepo diff with another diff, recursively.
1394 *
1395 * @param[in] src_diff Source diff node.
1396 * @param[in] diff_parent Current sysrepo diff parent.
1397 * @param[in] diff_cb Optional diff callback.
1398 * @param[in] cb_data User data for @p diff_cb.
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001399 * @param[in] options Diff merge options.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001400 * @param[in,out] diff Diff root node.
1401 * @return LY_ERR value.
1402 */
1403static LY_ERR
1404lyd_diff_merge_r(const struct lyd_node *src_diff, struct lyd_node *diff_parent, lyd_diff_cb diff_cb, void *cb_data,
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001405 uint16_t options, struct lyd_node **diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001406{
1407 LY_ERR ret = LY_SUCCESS;
1408 struct lyd_node *child, *diff_node = NULL;
1409 enum lyd_diff_op src_op, cur_op;
1410
1411 /* get source node operation */
1412 LY_CHECK_RET(lyd_diff_get_op(src_diff, &src_op));
1413
1414 /* find an equal node in the current diff */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001415 lyd_diff_find_node(diff_parent ? lyd_child_no_keys(diff_parent) : *diff, src_diff, &diff_node);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001416
1417 if (diff_node) {
1418 /* get target (current) operation */
1419 LY_CHECK_RET(lyd_diff_get_op(diff_node, &cur_op));
1420
1421 /* merge operations */
1422 switch (src_op) {
1423 case LYD_DIFF_OP_REPLACE:
1424 ret = lyd_diff_merge_replace(diff_node, cur_op, src_diff);
1425 break;
1426 case LYD_DIFF_OP_CREATE:
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001427 ret = lyd_diff_merge_create(diff_node, cur_op, src_diff, options);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001428 break;
1429 case LYD_DIFF_OP_DELETE:
1430 ret = lyd_diff_merge_delete(diff_node, cur_op, src_diff);
1431 break;
1432 case LYD_DIFF_OP_NONE:
1433 ret = lyd_diff_merge_none(diff_node, cur_op, src_diff);
1434 break;
1435 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001436 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001437 }
1438 if (ret) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001439 LOGERR(LYD_CTX(src_diff), LY_EOTHER, "Merging operation \"%s\" failed.", lyd_diff_op2str(src_op));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001440 return ret;
1441 }
1442
1443 if (diff_cb) {
1444 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001445 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001446 }
1447
1448 /* update diff parent */
1449 diff_parent = diff_node;
1450
1451 /* merge src_diff recursively */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001452 LY_LIST_FOR(lyd_child_no_keys(src_diff), child) {
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001453 LY_CHECK_RET(lyd_diff_merge_r(child, diff_parent, diff_cb, cb_data, options, diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001454 }
1455 } else {
1456 /* add new diff node with all descendants */
Michal Vasko871a0252020-11-11 18:35:24 +01001457 LY_CHECK_RET(lyd_dup_single(src_diff, (struct lyd_node_inner *)diff_parent, LYD_DUP_RECURSIVE | LYD_DUP_WITH_FLAGS,
1458 &diff_node));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001459
1460 /* insert node into diff if not already */
1461 if (!diff_parent) {
Michal Vaskob104f112020-07-17 09:54:54 +02001462 lyd_insert_sibling(*diff, diff_node, diff);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001463 }
1464
1465 /* update operation */
1466 LY_CHECK_RET(lyd_diff_change_op(diff_node, src_op));
1467
1468 if (diff_cb) {
1469 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001470 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001471 }
1472
1473 /* update diff parent */
1474 diff_parent = diff_node;
1475 }
1476
1477 /* remove any redundant nodes */
Michal Vaskob98d7082020-07-15 16:38:36 +02001478 if (lyd_diff_is_redundant(diff_parent)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001479 if (diff_parent == *diff) {
1480 *diff = (*diff)->next;
1481 }
1482 lyd_free_tree(diff_parent);
1483 }
1484
1485 return LY_SUCCESS;
1486}
1487
1488API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001489lyd_diff_merge_module(struct lyd_node **diff, const struct lyd_node *src_diff, const struct lys_module *mod,
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001490 lyd_diff_cb diff_cb, void *cb_data, uint16_t options)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001491{
1492 const struct lyd_node *src_root;
1493
1494 LY_LIST_FOR(src_diff, src_root) {
1495 if (mod && (lyd_owner_module(src_root) != mod)) {
1496 /* skip data nodes from different modules */
1497 continue;
1498 }
1499
1500 /* apply relevant nodes from the diff datatree */
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001501 LY_CHECK_RET(lyd_diff_merge_r(src_root, NULL, diff_cb, cb_data, options, diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001502 }
1503
1504 return LY_SUCCESS;
1505}
1506
1507API LY_ERR
Michal Vasko04f85912020-08-07 12:14:58 +02001508lyd_diff_merge_tree(struct lyd_node **diff_first, struct lyd_node *diff_parent, const struct lyd_node *src_sibling,
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001509 lyd_diff_cb diff_cb, void *cb_data, uint16_t options)
Michal Vasko04f85912020-08-07 12:14:58 +02001510{
1511 if (!src_sibling) {
1512 return LY_SUCCESS;
1513 }
1514
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001515 return lyd_diff_merge_r(src_sibling, diff_parent, diff_cb, cb_data, options, diff_first);
Michal Vasko04f85912020-08-07 12:14:58 +02001516}
1517
1518API LY_ERR
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001519lyd_diff_merge_all(struct lyd_node **diff, const struct lyd_node *src_diff, uint16_t options)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001520{
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001521 return lyd_diff_merge_module(diff, src_diff, NULL, NULL, NULL, options);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001522}
Michal Vasko4231fb62020-07-13 13:54:47 +02001523
1524static LY_ERR
1525lyd_diff_reverse_value(struct lyd_node *leaf, const struct lys_module *mod)
1526{
1527 LY_ERR ret = LY_SUCCESS;
1528 struct lyd_meta *meta;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001529 const char *val1 = NULL;
1530 char *val2;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001531 uint32_t flags;
Michal Vasko4231fb62020-07-13 13:54:47 +02001532
1533 meta = lyd_find_meta(leaf->meta, mod, "orig-value");
Michal Vaskob7be7a82020-08-20 09:09:04 +02001534 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(leaf)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001535
1536 /* orig-value */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001537 val1 = meta->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001538
1539 /* current value */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001540 val2 = strdup(LYD_CANON_VALUE(leaf));
Michal Vasko4231fb62020-07-13 13:54:47 +02001541
1542 /* switch values, keep default flag */
1543 flags = leaf->flags;
1544 LY_CHECK_GOTO(ret = lyd_change_term(leaf, val1), cleanup);
1545 leaf->flags = flags;
1546 LY_CHECK_GOTO(ret = lyd_change_meta(meta, val2), cleanup);
1547
1548cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001549 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001550 return ret;
1551}
1552
1553static LY_ERR
1554lyd_diff_reverse_default(struct lyd_node *node, const struct lys_module *mod)
1555{
1556 struct lyd_meta *meta;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001557 uint32_t flag1, flag2;
Michal Vasko4231fb62020-07-13 13:54:47 +02001558
1559 meta = lyd_find_meta(node->meta, mod, "orig-default");
Michal Vasko610e93b2020-11-09 20:58:32 +01001560 LY_CHECK_ERR_RET(!meta, LOGINT(mod->ctx), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001561
1562 /* orig-default */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001563 if (meta->value.boolean) {
Michal Vasko4231fb62020-07-13 13:54:47 +02001564 flag1 = LYD_DEFAULT;
1565 } else {
1566 flag1 = 0;
1567 }
1568
1569 /* current default */
1570 flag2 = node->flags & LYD_DEFAULT;
1571
Michal Vasko610e93b2020-11-09 20:58:32 +01001572 if (flag1 == flag2) {
1573 /* no default state change so nothing to reverse */
1574 return LY_SUCCESS;
1575 }
1576
Michal Vasko4231fb62020-07-13 13:54:47 +02001577 /* switch defaults */
1578 node->flags &= ~LYD_DEFAULT;
1579 node->flags |= flag1;
1580 LY_CHECK_RET(lyd_change_meta(meta, flag2 ? "true" : "false"));
1581
1582 return LY_SUCCESS;
1583}
1584
1585static LY_ERR
1586lyd_diff_reverse_meta(struct lyd_node *node, const struct lys_module *mod, const char *name1, const char *name2)
1587{
1588 LY_ERR ret = LY_SUCCESS;
1589 struct lyd_meta *meta1, *meta2;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001590 const char *val1 = NULL;
1591 char *val2 = NULL;
Michal Vasko4231fb62020-07-13 13:54:47 +02001592
1593 meta1 = lyd_find_meta(node->meta, mod, name1);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001594 LY_CHECK_ERR_RET(!meta1, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001595
1596 meta2 = lyd_find_meta(node->meta, mod, name2);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001597 LY_CHECK_ERR_RET(!meta2, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001598
1599 /* value1 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001600 val1 = meta1->value.canonical;
Michal Vasko4231fb62020-07-13 13:54:47 +02001601
1602 /* value2 */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001603 val2 = strdup(meta2->value.canonical);
Michal Vasko4231fb62020-07-13 13:54:47 +02001604
1605 /* switch values */
1606 LY_CHECK_GOTO(ret = lyd_change_meta(meta1, val2), cleanup);
1607 LY_CHECK_GOTO(ret = lyd_change_meta(meta2, val1), cleanup);
1608
1609cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001610 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001611 return ret;
1612}
1613
1614API LY_ERR
Michal Vasko66535812020-08-11 08:44:22 +02001615lyd_diff_reverse_all(const struct lyd_node *src_diff, struct lyd_node **diff)
Michal Vasko4231fb62020-07-13 13:54:47 +02001616{
1617 LY_ERR ret = LY_SUCCESS;
1618 const struct lys_module *mod;
Michal Vasko56daf732020-08-10 10:57:18 +02001619 struct lyd_node *root, *elem;
Michal Vasko4231fb62020-07-13 13:54:47 +02001620 enum lyd_diff_op op;
1621
1622 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
1623
1624 if (!src_diff) {
1625 *diff = NULL;
1626 return LY_SUCCESS;
1627 }
1628
1629 /* duplicate diff */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001630 LY_CHECK_RET(lyd_dup_siblings(src_diff, NULL, LYD_DUP_RECURSIVE, diff));
Michal Vasko4231fb62020-07-13 13:54:47 +02001631
1632 /* find module with metadata needed for later */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001633 mod = ly_ctx_get_module_latest(LYD_CTX(src_diff), "yang");
1634 LY_CHECK_ERR_GOTO(!mod, LOGINT(LYD_CTX(src_diff)); ret = LY_EINT, cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001635
1636 LY_LIST_FOR(*diff, root) {
Michal Vasko56daf732020-08-10 10:57:18 +02001637 LYD_TREE_DFS_BEGIN(root, elem) {
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001638 /* skip all keys */
1639 if (!lysc_is_key(elem->schema)) {
1640 /* find operation attribute, if any */
1641 LY_CHECK_GOTO(ret = lyd_diff_get_op(elem, &op), cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001642
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001643 switch (op) {
1644 case LYD_DIFF_OP_CREATE:
1645 /* reverse create to delete */
1646 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_DELETE), cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001647 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001648 case LYD_DIFF_OP_DELETE:
1649 /* reverse delete to create */
1650 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_CREATE), cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001651 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001652 case LYD_DIFF_OP_REPLACE:
1653 switch (elem->schema->nodetype) {
1654 case LYS_LEAF:
1655 /* leaf value change */
1656 LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup);
1657 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1658 break;
1659 case LYS_LEAFLIST:
1660 /* leaf-list move */
1661 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1662 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-value", "value"), cleanup);
1663 break;
1664 case LYS_LIST:
1665 /* list move */
1666 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-key", "key"), cleanup);
1667 break;
1668 default:
1669 LOGINT(LYD_CTX(src_diff));
1670 ret = LY_EINT;
1671 goto cleanup;
1672 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001673 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001674 case LYD_DIFF_OP_NONE:
1675 switch (elem->schema->nodetype) {
1676 case LYS_LEAF:
1677 case LYS_LEAFLIST:
1678 /* default flag change */
1679 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1680 break;
1681 default:
1682 /* nothing to do */
1683 break;
1684 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001685 break;
1686 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001687 }
1688
Michal Vasko56daf732020-08-10 10:57:18 +02001689 LYD_TREE_DFS_END(root, elem);
Michal Vasko4231fb62020-07-13 13:54:47 +02001690 }
1691 }
1692
1693cleanup:
1694 if (ret) {
1695 lyd_free_siblings(*diff);
1696 *diff = NULL;
1697 }
1698 return ret;
1699}