blob: 6680338bbe58da60a841d7a237a869bd57e2c7d4 [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 *
Michal Vaskoe78faec2021-04-08 17:24:43 +02006 * Copyright (c) 2020 - 2021 CESNET, z.s.p.o.
Michal Vaskod59035b2020-07-08 12:00:06 +02007 *
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 */
Christian Hopps32874e12021-05-01 09:43:54 -040014#define _GNU_SOURCE /* asprintf, strdup */
Michal Vaskod59035b2020-07-08 12:00:06 +020015
16#include "diff.h"
17
18#include <assert.h>
19#include <stddef.h>
Michal Vaskoe78faec2021-04-08 17:24:43 +020020#include <stdint.h>
21#include <stdio.h>
Radek Krejci47fab892020-11-05 17:02:41 +010022#include <stdlib.h>
Michal Vaskod59035b2020-07-08 12:00:06 +020023#include <string.h>
24
25#include "common.h"
Michal Vaskoe78faec2021-04-08 17:24:43 +020026#include "compat.h"
Radek Krejci47fab892020-11-05 17:02:41 +010027#include "context.h"
Michal Vaskod59035b2020-07-08 12:00:06 +020028#include "log.h"
Radek Krejci47fab892020-11-05 17:02:41 +010029#include "plugins_types.h"
30#include "set.h"
31#include "tree.h"
32#include "tree_data.h"
Michal Vaskod59035b2020-07-08 12:00:06 +020033#include "tree_data_internal.h"
Radek Krejci859a15a2021-03-05 20:56:59 +010034#include "tree_edit.h"
Michal Vaskod59035b2020-07-08 12:00:06 +020035#include "tree_schema.h"
36#include "tree_schema_internal.h"
37
38static const char *
39lyd_diff_op2str(enum lyd_diff_op op)
40{
41 switch (op) {
42 case LYD_DIFF_OP_CREATE:
43 return "create";
44 case LYD_DIFF_OP_DELETE:
45 return "delete";
46 case LYD_DIFF_OP_REPLACE:
47 return "replace";
48 case LYD_DIFF_OP_NONE:
49 return "none";
50 }
51
52 LOGINT(NULL);
53 return NULL;
54}
55
Michal Vaskoe6323f62020-07-09 15:49:02 +020056static enum lyd_diff_op
57lyd_diff_str2op(const char *str)
58{
59 switch (str[0]) {
60 case 'c':
61 assert(!strcmp(str, "create"));
62 return LYD_DIFF_OP_CREATE;
63 case 'd':
64 assert(!strcmp(str, "delete"));
65 return LYD_DIFF_OP_DELETE;
66 case 'r':
67 assert(!strcmp(str, "replace"));
68 return LYD_DIFF_OP_REPLACE;
69 case 'n':
70 assert(!strcmp(str, "none"));
71 return LYD_DIFF_OP_NONE;
72 }
73
74 LOGINT(NULL);
75 return 0;
76}
77
Michal Vaskod59035b2020-07-08 12:00:06 +020078LY_ERR
79lyd_diff_add(const struct lyd_node *node, enum lyd_diff_op op, const char *orig_default, const char *orig_value,
Michal Vaskoe78faec2021-04-08 17:24:43 +020080 const char *key, const char *value, const char *position, const char *orig_key, const char *orig_position,
81 struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +020082{
83 struct lyd_node *dup, *siblings, *match = NULL, *diff_parent = NULL;
84 const struct lyd_node *parent = NULL;
85 const struct lys_module *yang_mod;
86
87 assert(diff);
88
Michal Vasko53d48422020-11-13 18:02:29 +010089 /* replace leaf always needs orig-default and orig-value */
90 assert((node->schema->nodetype != LYS_LEAF) || (op != LYD_DIFF_OP_REPLACE) || (orig_default && orig_value));
91
92 /* create on userord needs key/value */
93 assert((node->schema->nodetype != LYS_LIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_CREATE) ||
Michal Vaskoe78faec2021-04-08 17:24:43 +020094 (lysc_is_dup_inst_list(node->schema) && position) || key);
Michal Vasko53d48422020-11-13 18:02:29 +010095 assert((node->schema->nodetype != LYS_LEAFLIST) || !(node->schema->flags & LYS_ORDBY_USER) ||
Michal Vaskoe78faec2021-04-08 17:24:43 +020096 (op != LYD_DIFF_OP_CREATE) || (lysc_is_dup_inst_list(node->schema) && position) || value);
Michal Vasko53d48422020-11-13 18:02:29 +010097
98 /* move on userord needs both key and orig-key/value and orig-value */
99 assert((node->schema->nodetype != LYS_LIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_REPLACE) ||
Michal Vaskoe78faec2021-04-08 17:24:43 +0200100 (lysc_is_dup_inst_list(node->schema) && position && orig_position) || (key && orig_key));
Michal Vasko53d48422020-11-13 18:02:29 +0100101 assert((node->schema->nodetype != LYS_LEAFLIST) || !(node->schema->flags & LYS_ORDBY_USER) ||
Michal Vaskoe78faec2021-04-08 17:24:43 +0200102 (op != LYD_DIFF_OP_REPLACE) || (lysc_is_dup_inst_list(node->schema) && position && orig_position) ||
103 (value && orig_value));
Michal Vasko53d48422020-11-13 18:02:29 +0100104
Michal Vaskod59035b2020-07-08 12:00:06 +0200105 /* find the first existing parent */
106 siblings = *diff;
107 while (1) {
108 /* find next node parent */
109 parent = node;
110 while (parent->parent && (!diff_parent || (parent->parent->schema != diff_parent->schema))) {
Michal Vasko9e685082021-01-29 14:49:09 +0100111 parent = lyd_parent(parent);
Michal Vaskod59035b2020-07-08 12:00:06 +0200112 }
113 if (parent == node) {
114 /* no more parents to find */
115 break;
116 }
117
118 /* check whether it exists in the diff */
119 if (lyd_find_sibling_first(siblings, parent, &match)) {
120 break;
121 }
122
123 /* another parent found */
124 diff_parent = match;
125
126 /* move down in the diff */
Radek Krejcia1c1e542020-09-29 16:06:52 +0200127 siblings = lyd_child_no_keys(match);
Michal Vaskod59035b2020-07-08 12:00:06 +0200128 }
129
130 /* duplicate the subtree (and connect to the diff if possible) */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200131 LY_CHECK_RET(lyd_dup_single(node, (struct lyd_node_inner *)diff_parent,
Michal Vasko871a0252020-11-11 18:35:24 +0100132 LYD_DUP_RECURSIVE | LYD_DUP_NO_META | LYD_DUP_WITH_PARENTS | LYD_DUP_WITH_FLAGS, &dup));
Michal Vaskod59035b2020-07-08 12:00:06 +0200133
134 /* find the first duplicated parent */
135 if (!diff_parent) {
Michal Vasko9e685082021-01-29 14:49:09 +0100136 diff_parent = lyd_parent(dup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200137 while (diff_parent && diff_parent->parent) {
Michal Vasko9e685082021-01-29 14:49:09 +0100138 diff_parent = lyd_parent(diff_parent);
Michal Vaskod59035b2020-07-08 12:00:06 +0200139 }
140 } else {
Michal Vasko9e685082021-01-29 14:49:09 +0100141 diff_parent = dup;
Michal Vaskod59035b2020-07-08 12:00:06 +0200142 while (diff_parent->parent && (diff_parent->parent->schema == parent->schema)) {
Michal Vasko9e685082021-01-29 14:49:09 +0100143 diff_parent = lyd_parent(diff_parent);
Michal Vaskod59035b2020-07-08 12:00:06 +0200144 }
145 }
146
147 /* no parent existed, must be manually connected */
148 if (!diff_parent) {
149 /* there actually was no parent to duplicate */
Michal Vaskob104f112020-07-17 09:54:54 +0200150 lyd_insert_sibling(*diff, dup, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200151 } else if (!diff_parent->parent) {
Michal Vaskob104f112020-07-17 09:54:54 +0200152 lyd_insert_sibling(*diff, diff_parent, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200153 }
154
155 /* get module with the operation metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +0200156 yang_mod = LYD_CTX(node)->list.objs[1];
Michal Vaskod59035b2020-07-08 12:00:06 +0200157 assert(!strcmp(yang_mod->name, "yang"));
158
159 /* add parent operation, if any */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200160 if (diff_parent && (diff_parent != dup)) {
Michal Vasko871a0252020-11-11 18:35:24 +0100161 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), diff_parent, yang_mod, "operation", "none", 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200162 }
163
164 /* add subtree operation */
Michal Vasko871a0252020-11-11 18:35:24 +0100165 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 +0200166
167 /* orig-default */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200168 if (orig_default) {
Michal Vasko871a0252020-11-11 18:35:24 +0100169 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 +0200170 }
171
172 /* orig-value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200173 if (orig_value) {
Michal Vasko871a0252020-11-11 18:35:24 +0100174 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 +0200175 }
176
177 /* key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200178 if (key) {
Michal Vasko871a0252020-11-11 18:35:24 +0100179 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "key", key, 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200180 }
181
182 /* value */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200183 if (value) {
Michal Vasko871a0252020-11-11 18:35:24 +0100184 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "value", value, 0, NULL));
Michal Vaskod59035b2020-07-08 12:00:06 +0200185 }
186
Michal Vaskoe78faec2021-04-08 17:24:43 +0200187 /* position */
188 if (position) {
189 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "position", position, 0, NULL));
190 }
191
Michal Vaskod59035b2020-07-08 12:00:06 +0200192 /* orig-key */
Michal Vasko3a41dff2020-07-15 14:30:28 +0200193 if (orig_key) {
Michal Vasko871a0252020-11-11 18:35:24 +0100194 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 +0200195 }
196
Michal Vaskoe78faec2021-04-08 17:24:43 +0200197 /* orig-position */
198 if (orig_position) {
199 LY_CHECK_RET(lyd_new_meta(LYD_CTX(node), dup, yang_mod, "orig-position", orig_position, 0, NULL));
200 }
201
Michal Vaskod59035b2020-07-08 12:00:06 +0200202 return LY_SUCCESS;
203}
204
205/**
206 * @brief Get a userord entry for a specific user-ordered list/leaf-list. Create if does not exist yet.
207 *
Michal Vasko1dcd73b2020-12-08 10:04:33 +0100208 * @param[in] first Node from the first tree, can be NULL (on create).
Michal Vaskod59035b2020-07-08 12:00:06 +0200209 * @param[in] schema Schema node of the list/leaf-list.
210 * @param[in,out] userord Sized array of userord items.
211 * @return Userord item for all the user-ordered list/leaf-list instances.
212 */
213static struct lyd_diff_userord *
214lyd_diff_userord_get(const struct lyd_node *first, const struct lysc_node *schema, struct lyd_diff_userord **userord)
215{
216 struct lyd_diff_userord *item;
Michal Vaskoe78faec2021-04-08 17:24:43 +0200217 struct lyd_node *iter;
218 const struct lyd_node **node;
Michal Vaskod59035b2020-07-08 12:00:06 +0200219 LY_ARRAY_COUNT_TYPE u;
220
221 LY_ARRAY_FOR(*userord, u) {
222 if ((*userord)[u].schema == schema) {
223 return &(*userord)[u];
224 }
225 }
226
227 /* it was not added yet, add it now */
228 LY_ARRAY_NEW_RET(schema->module->ctx, *userord, item, NULL);
229
230 item->schema = schema;
231 item->pos = 0;
232 item->inst = NULL;
233
234 /* store all the instance pointers in the current order */
235 if (first) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200236 LYD_LIST_FOR_INST(lyd_first_sibling(first), first->schema, iter) {
237 LY_ARRAY_NEW_RET(schema->module->ctx, item->inst, node, NULL);
238 *node = iter;
Michal Vaskod59035b2020-07-08 12:00:06 +0200239 }
240 }
241
242 return item;
243}
244
245/**
246 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Can be used only for user-ordered
247 * lists/leaf-lists.
248 *
249 * @param[in] first Node from the first tree, can be NULL (on create).
250 * @param[in] second Node from the second tree, can be NULL (on delete).
251 * @param[in] options Diff options.
252 * @param[in,out] userord Sized array of userord items for keeping the current node order.
253 * @param[out] op Operation.
254 * @param[out] orig_default Original default metadata.
255 * @param[out] value Value metadata.
256 * @param[out] orig_value Original value metadata
257 * @param[out] key Key metadata.
258 * @param[out] orig_key Original key metadata.
Michal Vaskoe78faec2021-04-08 17:24:43 +0200259 * @param[out] position Position metadata.
260 * @param[out] orig_position Original position metadata.
Michal Vaskod59035b2020-07-08 12:00:06 +0200261 * @return LY_SUCCESS on success,
262 * @return LY_ENOT if there is no change to be added into diff,
263 * @return LY_ERR value on other errors.
264 */
265static LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200266lyd_diff_userord_attrs(const struct lyd_node *first, const struct lyd_node *second, uint16_t options,
Radek Krejci0f969882020-08-21 16:56:47 +0200267 struct lyd_diff_userord **userord, enum lyd_diff_op *op, const char **orig_default, char **value,
Michal Vaskoe78faec2021-04-08 17:24:43 +0200268 char **orig_value, char **key, char **orig_key, char **position, char **orig_position)
Michal Vaskod59035b2020-07-08 12:00:06 +0200269{
270 const struct lysc_node *schema;
Michal Vaskoe78faec2021-04-08 17:24:43 +0200271 size_t buflen, bufused;
272 uint32_t first_pos, second_pos;
Michal Vaskod59035b2020-07-08 12:00:06 +0200273 struct lyd_diff_userord *userord_item;
274
275 assert(first || second);
276
277 *orig_default = NULL;
278 *value = NULL;
279 *orig_value = NULL;
280 *key = NULL;
281 *orig_key = NULL;
Michal Vaskoe78faec2021-04-08 17:24:43 +0200282 *position = NULL;
283 *orig_position = NULL;
Michal Vaskod59035b2020-07-08 12:00:06 +0200284
285 schema = first ? first->schema : second->schema;
286 assert(lysc_is_userordered(schema));
287
288 /* get userord entry */
289 userord_item = lyd_diff_userord_get(first, schema, userord);
290 LY_CHECK_RET(!userord_item, LY_EMEM);
291
Michal Vaskod59035b2020-07-08 12:00:06 +0200292 /* find user-ordered first position */
293 if (first) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200294 for (first_pos = 0; first_pos < LY_ARRAY_COUNT(userord_item->inst); ++first_pos) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200295 if (userord_item->inst[first_pos] == first) {
296 break;
297 }
298 }
299 assert(first_pos < LY_ARRAY_COUNT(userord_item->inst));
300 } else {
301 first_pos = 0;
302 }
303
Michal Vaskoe78faec2021-04-08 17:24:43 +0200304 /* prepare position of the next instance */
305 second_pos = userord_item->pos++;
306
Michal Vaskod59035b2020-07-08 12:00:06 +0200307 /* learn operation first */
308 if (!second) {
309 *op = LYD_DIFF_OP_DELETE;
310 } else if (!first) {
311 *op = LYD_DIFF_OP_CREATE;
312 } else {
Michal Vasko8f359bf2020-07-28 10:41:15 +0200313 if (lyd_compare_single(second, userord_item->inst[second_pos], 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200314 /* in first, there is a different instance on the second position, we are going to move 'first' node */
315 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200316 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200317 /* default flag change */
318 *op = LYD_DIFF_OP_NONE;
319 } else {
320 /* no changes */
321 return LY_ENOT;
322 }
323 }
324
325 /*
326 * set each attribute correctly based on the operation and node type
327 */
328
329 /* orig-default */
Michal Vasko4b715ca2020-11-11 18:39:57 +0100330 if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200331 if (first->flags & LYD_DEFAULT) {
332 *orig_default = "true";
333 } else {
334 *orig_default = "false";
335 }
336 }
337
338 /* value */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200339 if ((schema->nodetype == LYS_LEAFLIST) && !lysc_is_dup_inst_list(schema) &&
340 ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200341 if (second_pos) {
Radek Krejci6d5ba0c2021-04-26 07:49:59 +0200342 *value = strdup(lyd_get_value(userord_item->inst[second_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200343 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200344 } else {
345 *value = strdup("");
346 LY_CHECK_ERR_RET(!*value, LOGMEM(schema->module->ctx), LY_EMEM);
347 }
348 }
349
350 /* orig-value */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200351 if ((schema->nodetype == LYS_LEAFLIST) && !lysc_is_dup_inst_list(schema) &&
352 ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200353 if (first_pos) {
Radek Krejci6d5ba0c2021-04-26 07:49:59 +0200354 *orig_value = strdup(lyd_get_value(userord_item->inst[first_pos - 1]));
Michal Vaskoba99a3e2020-08-18 15:50:05 +0200355 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200356 } else {
357 *orig_value = strdup("");
358 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
359 }
360 }
361
362 /* key */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200363 if ((schema->nodetype == LYS_LIST) && !lysc_is_dup_inst_list(schema) &&
364 ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200365 if (second_pos) {
366 buflen = bufused = 0;
367 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[second_pos - 1], key, &buflen, &bufused, 0));
368 } else {
369 *key = strdup("");
370 LY_CHECK_ERR_RET(!*key, LOGMEM(schema->module->ctx), LY_EMEM);
371 }
372 }
373
374 /* orig-key */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200375 if ((schema->nodetype == LYS_LIST) && !lysc_is_dup_inst_list(schema) &&
376 ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200377 if (first_pos) {
378 buflen = bufused = 0;
379 LY_CHECK_RET(lyd_path_list_predicate(userord_item->inst[first_pos - 1], orig_key, &buflen, &bufused, 0));
380 } else {
381 *orig_key = strdup("");
382 LY_CHECK_ERR_RET(!*orig_key, LOGMEM(schema->module->ctx), LY_EMEM);
383 }
384 }
385
Michal Vaskoe78faec2021-04-08 17:24:43 +0200386 /* position */
387 if (lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) {
388 if (second_pos) {
389 if (asprintf(position, "%" PRIu32, second_pos) == -1) {
390 LOGMEM(schema->module->ctx);
391 return LY_EMEM;
392 }
393 } else {
394 *position = strdup("");
395 LY_CHECK_ERR_RET(!*position, LOGMEM(schema->module->ctx), LY_EMEM);
396 }
397 }
398
399 /* orig-position */
400 if (lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) {
401 if (first_pos) {
402 if (asprintf(orig_position, "%" PRIu32, first_pos) == -1) {
403 LOGMEM(schema->module->ctx);
404 return LY_EMEM;
405 }
406 } else {
407 *orig_position = strdup("");
408 LY_CHECK_ERR_RET(!*orig_position, LOGMEM(schema->module->ctx), LY_EMEM);
409 }
410 }
411
Michal Vaskod59035b2020-07-08 12:00:06 +0200412 /*
413 * update our instances - apply the change
414 */
415 if (*op == LYD_DIFF_OP_CREATE) {
416 /* insert the instance */
Michal Vasko5cde11b2020-12-08 10:04:48 +0100417 LY_ARRAY_CREATE_RET(schema->module->ctx, userord_item->inst, 1, LY_EMEM);
Michal Vaskod59035b2020-07-08 12:00:06 +0200418 if (second_pos < LY_ARRAY_COUNT(userord_item->inst)) {
419 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
420 (LY_ARRAY_COUNT(userord_item->inst) - second_pos) * sizeof *userord_item->inst);
421 }
422 LY_ARRAY_INCREMENT(userord_item->inst);
423 userord_item->inst[second_pos] = second;
424
425 } else if (*op == LYD_DIFF_OP_DELETE) {
426 /* remove the instance */
427 if (first_pos + 1 < LY_ARRAY_COUNT(userord_item->inst)) {
428 memmove(userord_item->inst + first_pos, userord_item->inst + first_pos + 1,
429 (LY_ARRAY_COUNT(userord_item->inst) - first_pos - 1) * sizeof *userord_item->inst);
430 }
431 LY_ARRAY_DECREMENT(userord_item->inst);
432
433 } else if (*op == LYD_DIFF_OP_REPLACE) {
434 /* move the instances */
435 memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos,
436 (first_pos - second_pos) * sizeof *userord_item->inst);
437 userord_item->inst[second_pos] = first;
438 }
439
440 return LY_SUCCESS;
441}
442
443/**
444 * @brief Get all the metadata to be stored in a diff for the 2 nodes. Cannot be used for user-ordered
445 * lists/leaf-lists.
446 *
447 * @param[in] first Node from the first tree, can be NULL (on create).
448 * @param[in] second Node from the second tree, can be NULL (on delete).
449 * @param[in] options Diff options.
450 * @param[out] op Operation.
451 * @param[out] orig_default Original default metadata.
452 * @param[out] orig_value Original value metadata.
453 * @return LY_SUCCESS on success,
454 * @return LY_ENOT if there is no change to be added into diff,
455 * @return LY_ERR value on other errors.
456 */
457static LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200458lyd_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 +0200459 const char **orig_default, char **orig_value)
Michal Vaskod59035b2020-07-08 12:00:06 +0200460{
461 const struct lysc_node *schema;
Michal Vasko6ea6fe22021-10-08 09:57:01 +0200462 const char *str_val;
Michal Vaskod59035b2020-07-08 12:00:06 +0200463
464 assert(first || second);
465
466 *orig_default = NULL;
467 *orig_value = NULL;
468
469 schema = first ? first->schema : second->schema;
470 assert(!lysc_is_userordered(schema));
471
472 /* learn operation first */
473 if (!second) {
474 *op = LYD_DIFF_OP_DELETE;
475 } else if (!first) {
476 *op = LYD_DIFF_OP_CREATE;
477 } else {
478 switch (schema->nodetype) {
479 case LYS_CONTAINER:
480 case LYS_RPC:
481 case LYS_ACTION:
482 case LYS_NOTIF:
483 /* no changes */
484 return LY_ENOT;
485 case LYS_LIST:
486 case LYS_LEAFLIST:
Michal Vasko3a41dff2020-07-15 14:30:28 +0200487 if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200488 /* default flag change */
489 *op = LYD_DIFF_OP_NONE;
490 } else {
491 /* no changes */
492 return LY_ENOT;
493 }
494 break;
495 case LYS_LEAF:
496 case LYS_ANYXML:
497 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +0200498 if (lyd_compare_single(first, second, 0)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200499 /* different values */
500 *op = LYD_DIFF_OP_REPLACE;
Michal Vasko3a41dff2020-07-15 14:30:28 +0200501 } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200502 /* default flag change */
503 *op = LYD_DIFF_OP_NONE;
504 } else {
505 /* no changes */
506 return LY_ENOT;
507 }
508 break;
509 default:
510 LOGINT_RET(schema->module->ctx);
511 }
512 }
513
514 /*
515 * set each attribute correctly based on the operation and node type
516 */
517
518 /* orig-default */
Michal Vasko4b715ca2020-11-11 18:39:57 +0100519 if ((schema->nodetype & LYD_NODE_TERM) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200520 if (first->flags & LYD_DEFAULT) {
521 *orig_default = "true";
522 } else {
523 *orig_default = "false";
524 }
525 }
526
527 /* orig-value */
Michal Vaskobaba84e2021-02-05 16:33:30 +0100528 if ((schema->nodetype & (LYS_LEAF | LYS_ANYDATA)) && (*op == LYD_DIFF_OP_REPLACE)) {
529 if (schema->nodetype == LYS_LEAF) {
Michal Vasko6ea6fe22021-10-08 09:57:01 +0200530 str_val = lyd_get_value(first);
531 *orig_value = strdup(str_val ? str_val : "");
Michal Vaskobaba84e2021-02-05 16:33:30 +0100532 LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM);
533 } else {
534 LY_CHECK_RET(lyd_any_value_str(first, orig_value));
535 }
Michal Vaskod59035b2020-07-08 12:00:06 +0200536 }
537
538 return LY_SUCCESS;
539}
540
541/**
Michal Vaskoe78faec2021-04-08 17:24:43 +0200542 * @brief Find a matching instance of a node in a data tree.
543 *
544 * @param[in] siblings Siblings to search in.
545 * @param[in] target Target node to search for.
546 * @param[in] defaults Whether to consider (or ignore) default values.
547 * @param[in,out] dup_inst_cache Duplicate instance cache.
548 * @param[out] match Found match, NULL if no matching node found.
549 * @return LY_ERR value.
550 */
551static LY_ERR
552lyd_diff_find_match(const struct lyd_node *siblings, const struct lyd_node *target, ly_bool defaults,
Michal Vaskod7c048c2021-05-18 16:12:55 +0200553 struct lyd_dup_inst **dup_inst_cache, struct lyd_node **match)
Michal Vaskoe78faec2021-04-08 17:24:43 +0200554{
Michal Vaskoe78faec2021-04-08 17:24:43 +0200555 if (target->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
556 /* try to find the exact instance */
557 lyd_find_sibling_first(siblings, target, match);
558 } else {
559 /* try to simply find the node, there cannot be more instances */
560 lyd_find_sibling_val(siblings, target->schema, NULL, 0, match);
561 }
562
Michal Vaskod7c048c2021-05-18 16:12:55 +0200563 /* update match as needed */
564 LY_CHECK_RET(lyd_dup_inst_next(match, siblings, dup_inst_cache));
Michal Vaskoe78faec2021-04-08 17:24:43 +0200565
566 if (*match && ((*match)->flags & LYD_DEFAULT) && !defaults) {
567 /* ignore default nodes */
568 *match = NULL;
569 }
570 return LY_SUCCESS;
571}
572
573/**
Michal Vaskod59035b2020-07-08 12:00:06 +0200574 * @brief Perform diff for all siblings at certain depth, recursively.
575 *
576 * For user-ordered lists/leaf-lists a specific structure is used for storing
577 * the current order. The idea is to apply all the generated diff changes
578 * virtually on the first tree so that we can continue to generate correct
579 * changes after some were already generated.
580 *
581 * The algorithm then uses second tree position-based changes with a before
582 * (preceding) item anchor.
583 *
584 * Example:
585 *
586 * Virtual first tree leaf-list order:
587 * 1 2 [3] 4 5
588 *
589 * Second tree leaf-list order:
590 * 1 2 [5] 3 4
591 *
592 * We are at the 3rd node now. We look at whether the nodes on the 3rd position
593 * match - they do not - move nodes so that the 3rd position node is final ->
594 * -> move node 5 to the 3rd position -> move node 5 after node 2.
595 *
596 * Required properties:
597 * Stored operations (move) should not be affected by later operations -
598 * - would cause a redundantly long list of operations, possibly inifinite.
599 *
600 * Implemenation justification:
601 * First, all delete operations and only then move/create operations are stored.
602 * Also, preceding anchor is used and after each iteration another node is
603 * at its final position. That results in the invariant that all preceding
604 * nodes are final and will not be changed by the later operations, meaning
605 * they can safely be used as anchors for the later operations.
606 *
607 * @param[in] first First tree first sibling.
608 * @param[in] second Second tree first sibling.
609 * @param[in] options Diff options.
Michal Vasko3a41dff2020-07-15 14:30:28 +0200610 * @param[in] nosiblings Whether to skip following siblings.
Michal Vaskod59035b2020-07-08 12:00:06 +0200611 * @param[in,out] diff Diff to append to.
612 * @return LY_ERR value.
613 */
614static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200615lyd_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 +0200616 struct lyd_node **diff)
Michal Vaskod59035b2020-07-08 12:00:06 +0200617{
618 LY_ERR ret = LY_SUCCESS;
619 const struct lyd_node *iter_first, *iter_second;
620 struct lyd_node *match_second, *match_first;
Michal Vaskod59035b2020-07-08 12:00:06 +0200621 struct lyd_diff_userord *userord = NULL;
Michal Vaskod7c048c2021-05-18 16:12:55 +0200622 struct lyd_dup_inst *dup_inst_first = NULL, *dup_inst_second = NULL;
Michal Vaskod59035b2020-07-08 12:00:06 +0200623 LY_ARRAY_COUNT_TYPE u;
624 enum lyd_diff_op op;
625 const char *orig_default;
Michal Vaskoe78faec2021-04-08 17:24:43 +0200626 char *orig_value, *key, *value, *position, *orig_key, *orig_position;
Michal Vaskod59035b2020-07-08 12:00:06 +0200627
Michal Vaskod59035b2020-07-08 12:00:06 +0200628 /* compare first tree to the second tree - delete, replace, none */
629 LY_LIST_FOR(first, iter_first) {
Michal Vaskoc825ed72021-07-21 16:05:59 +0200630 if (!iter_first->schema) {
631 continue;
632 }
633
Michal Vaskod59035b2020-07-08 12:00:06 +0200634 assert(!(iter_first->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200635 if ((iter_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200636 /* skip default nodes */
637 continue;
638 }
639
Michal Vaskoe78faec2021-04-08 17:24:43 +0200640 /* find a match in the second tree */
641 LY_CHECK_GOTO(ret = lyd_diff_find_match(second, iter_first, options & LYD_DIFF_DEFAULTS, &dup_inst_second,
642 &match_second), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200643
644 if (lysc_is_userordered(iter_first->schema)) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200645 /* we are handling only user-ordered node delete now */
646 if (!match_second) {
647 /* get all the attributes */
648 LY_CHECK_GOTO(ret = lyd_diff_userord_attrs(iter_first, match_second, options, &userord, &op, &orig_default,
649 &value, &orig_value, &key, &orig_key, &position, &orig_position), cleanup);
650
651 /* there must be changes, it is deleted */
652 assert(op == LYD_DIFF_OP_DELETE);
653 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, key, value, position, orig_key, orig_position, diff);
654
655 free(orig_value);
656 free(key);
657 free(value);
658 free(position);
659 free(orig_key);
660 free(orig_position);
661 LY_CHECK_GOTO(ret, cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200662 }
Michal Vaskod59035b2020-07-08 12:00:06 +0200663 } else {
664 /* get all the attributes */
665 ret = lyd_diff_attrs(iter_first, match_second, options, &op, &orig_default, &orig_value);
666
667 /* add into diff if there are any changes */
668 if (!ret) {
669 if (op == LYD_DIFF_OP_DELETE) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200670 ret = lyd_diff_add(iter_first, op, orig_default, orig_value, NULL, NULL, NULL, NULL, NULL, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200671 } else {
Michal Vasko3c2dd6c2020-11-06 17:38:55 +0100672 assert(match_second);
Michal Vaskoe78faec2021-04-08 17:24:43 +0200673 ret = lyd_diff_add(match_second, op, orig_default, orig_value, NULL, NULL, NULL, NULL, NULL, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200674 }
675
676 free(orig_value);
677 LY_CHECK_GOTO(ret, cleanup);
678 } else if (ret == LY_ENOT) {
679 ret = LY_SUCCESS;
680 } else {
681 goto cleanup;
682 }
683 }
684
685 /* check descendants, if any, recursively */
686 if (match_second) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200687 LY_CHECK_GOTO(ret = lyd_diff_siblings_r(lyd_child_no_keys(iter_first), lyd_child_no_keys(match_second),
688 options, 0, diff), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200689 }
690
691 if (nosiblings) {
692 break;
693 }
694 }
695
696 /* reset all cached positions */
697 LY_ARRAY_FOR(userord, u) {
698 userord[u].pos = 0;
699 }
700
701 /* compare second tree to the first tree - create, user-ordered move */
702 LY_LIST_FOR(second, iter_second) {
Michal Vaskoc825ed72021-07-21 16:05:59 +0200703 if (!iter_second->schema) {
704 continue;
705 }
706
Michal Vaskod59035b2020-07-08 12:00:06 +0200707 assert(!(iter_second->schema->flags & LYS_KEY));
Michal Vasko3a41dff2020-07-15 14:30:28 +0200708 if ((iter_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200709 /* skip default nodes */
710 continue;
711 }
712
Michal Vaskoe78faec2021-04-08 17:24:43 +0200713 /* find a match in the first tree */
714 LY_CHECK_GOTO(ret = lyd_diff_find_match(first, iter_second, options & LYD_DIFF_DEFAULTS, &dup_inst_first,
715 &match_first), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200716
717 if (lysc_is_userordered(iter_second->schema)) {
718 /* get all the attributes */
719 ret = lyd_diff_userord_attrs(match_first, iter_second, options, &userord, &op, &orig_default,
Michal Vaskoe78faec2021-04-08 17:24:43 +0200720 &value, &orig_value, &key, &orig_key, &position, &orig_position);
Michal Vaskod59035b2020-07-08 12:00:06 +0200721
722 /* add into diff if there are any changes */
723 if (!ret) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200724 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, key, value, position, orig_key,
725 orig_position, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200726
727 free(orig_value);
728 free(key);
729 free(value);
Michal Vaskoe78faec2021-04-08 17:24:43 +0200730 free(position);
Michal Vaskod59035b2020-07-08 12:00:06 +0200731 free(orig_key);
Michal Vaskoe78faec2021-04-08 17:24:43 +0200732 free(orig_position);
Michal Vaskod59035b2020-07-08 12:00:06 +0200733 LY_CHECK_GOTO(ret, cleanup);
734 } else if (ret == LY_ENOT) {
735 ret = LY_SUCCESS;
736 } else {
737 goto cleanup;
738 }
739 } else if (!match_first) {
740 /* get all the attributes */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200741 LY_CHECK_GOTO(ret = lyd_diff_attrs(match_first, iter_second, options, &op, &orig_default, &orig_value), cleanup);
Michal Vaskod59035b2020-07-08 12:00:06 +0200742
743 /* there must be changes, it is created */
744 assert(op == LYD_DIFF_OP_CREATE);
Michal Vaskoe78faec2021-04-08 17:24:43 +0200745 ret = lyd_diff_add(iter_second, op, orig_default, orig_value, NULL, NULL, NULL, NULL, NULL, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200746
747 free(orig_value);
748 LY_CHECK_GOTO(ret, cleanup);
749 } /* else was handled */
750
751 if (nosiblings) {
752 break;
753 }
754 }
755
756cleanup:
Michal Vaskod7c048c2021-05-18 16:12:55 +0200757 lyd_dup_inst_free(dup_inst_first);
758 lyd_dup_inst_free(dup_inst_second);
Michal Vaskod59035b2020-07-08 12:00:06 +0200759 LY_ARRAY_FOR(userord, u) {
760 LY_ARRAY_FREE(userord[u].inst);
761 }
762 LY_ARRAY_FREE(userord);
763 return ret;
764}
765
Michal Vasko3a41dff2020-07-15 14:30:28 +0200766static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200767lyd_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 +0200768{
769 const struct ly_ctx *ctx;
770
771 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
772
773 if (first) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200774 ctx = LYD_CTX(first);
Michal Vaskod59035b2020-07-08 12:00:06 +0200775 } else if (second) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200776 ctx = LYD_CTX(second);
Michal Vaskod59035b2020-07-08 12:00:06 +0200777 } else {
778 ctx = NULL;
779 }
780
781 if (first && second && (lysc_data_parent(first->schema) != lysc_data_parent(second->schema))) {
782 LOGERR(ctx, LY_EINVAL, "Invalid arguments - cannot create diff for unrelated data (%s()).", __func__);
783 return LY_EINVAL;
784 }
785
786 *diff = NULL;
787
Michal Vasko3a41dff2020-07-15 14:30:28 +0200788 return lyd_diff_siblings_r(first, second, options, nosiblings, diff);
789}
790
791API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200792lyd_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 +0200793{
794 return lyd_diff(first, second, options, 1, diff);
795}
796
797API LY_ERR
Radek Krejci1deb5be2020-08-26 16:43:36 +0200798lyd_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 +0200799{
800 return lyd_diff(first, second, options, 0, diff);
Michal Vaskod59035b2020-07-08 12:00:06 +0200801}
802
803/**
Michal Vaskod59035b2020-07-08 12:00:06 +0200804 * @brief Learn operation of a diff node.
805 *
806 * @param[in] diff_node Diff node.
807 * @param[out] op Operation.
Michal Vaskod59035b2020-07-08 12:00:06 +0200808 * @return LY_ERR value.
809 */
810static LY_ERR
Michal Vaskoe6323f62020-07-09 15:49:02 +0200811lyd_diff_get_op(const struct lyd_node *diff_node, enum lyd_diff_op *op)
Michal Vaskod59035b2020-07-08 12:00:06 +0200812{
813 struct lyd_meta *meta = NULL;
814 const struct lyd_node *diff_parent;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200815 const char *str;
Michal Vaskod59035b2020-07-08 12:00:06 +0200816
Michal Vasko9e685082021-01-29 14:49:09 +0100817 for (diff_parent = diff_node; diff_parent; diff_parent = lyd_parent(diff_parent)) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200818 LY_LIST_FOR(diff_parent->meta, meta) {
819 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Radek Krejci6d5ba0c2021-04-26 07:49:59 +0200820 str = lyd_get_meta_value(meta);
Michal Vaskod59035b2020-07-08 12:00:06 +0200821 if ((str[0] == 'r') && (diff_parent != diff_node)) {
822 /* we do not care about this operation if it's in our parent */
823 continue;
824 }
Michal Vaskoe6323f62020-07-09 15:49:02 +0200825 *op = lyd_diff_str2op(str);
Michal Vaskod59035b2020-07-08 12:00:06 +0200826 break;
827 }
828 }
829 if (meta) {
830 break;
831 }
832 }
Michal Vaskob7be7a82020-08-20 09:09:04 +0200833 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_node)), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +0200834
Michal Vaskod59035b2020-07-08 12:00:06 +0200835 return LY_SUCCESS;
836}
837
838/**
839 * @brief Insert a diff node into a data tree.
840 *
841 * @param[in,out] first_node First sibling of the data tree.
842 * @param[in] parent_node Data tree sibling parent node.
843 * @param[in] new_node Node to insert.
Michal Vaskoe78faec2021-04-08 17:24:43 +0200844 * @param[in] userord_anchor Optional anchor (key, value, or position) of relative (leaf-)list instance. If not set,
845 * the user-ordered instance will be inserted at the first position.
Michal Vaskod59035b2020-07-08 12:00:06 +0200846 * @return err_info, NULL on success.
847 */
848static LY_ERR
849lyd_diff_insert(struct lyd_node **first_node, struct lyd_node *parent_node, struct lyd_node *new_node,
Michal Vaskoe78faec2021-04-08 17:24:43 +0200850 const char *userord_anchor)
Michal Vaskod59035b2020-07-08 12:00:06 +0200851{
852 LY_ERR ret;
853 struct lyd_node *anchor;
Michal Vaskoe78faec2021-04-08 17:24:43 +0200854 uint32_t pos, anchor_pos;
855 int found;
Michal Vaskod59035b2020-07-08 12:00:06 +0200856
857 assert(new_node);
858
859 if (!*first_node) {
860 if (!parent_node) {
861 /* no parent or siblings */
862 *first_node = new_node;
863 return LY_SUCCESS;
864 }
865
866 /* simply insert into parent, no other children */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200867 if (userord_anchor) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200868 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
Michal Vasko69730152020-10-09 16:30:07 +0200869 new_node->schema->name);
Michal Vaskod59035b2020-07-08 12:00:06 +0200870 return LY_EINVAL;
871 }
Michal Vaskob104f112020-07-17 09:54:54 +0200872 return lyd_insert_child(parent_node, new_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200873 }
874
Michal Vasko9e685082021-01-29 14:49:09 +0100875 assert(!(*first_node)->parent || (lyd_parent(*first_node) == parent_node));
Michal Vaskod59035b2020-07-08 12:00:06 +0200876
Michal Vaskod59035b2020-07-08 12:00:06 +0200877 if (!lysc_is_userordered(new_node->schema)) {
Michal Vaskob104f112020-07-17 09:54:54 +0200878 /* simple insert */
879 return lyd_insert_sibling(*first_node, new_node, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200880 }
881
Michal Vaskoe78faec2021-04-08 17:24:43 +0200882 if (userord_anchor) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200883 /* find the anchor sibling */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200884 if (lysc_is_dup_inst_list(new_node->schema)) {
885 anchor_pos = atoi(userord_anchor);
886 LY_CHECK_ERR_RET(!anchor_pos, LOGINT(LYD_CTX(new_node)), LY_EINT);
887
888 found = 0;
889 pos = 1;
890 LYD_LIST_FOR_INST(*first_node, new_node->schema, anchor) {
891 if (pos == anchor_pos) {
892 found = 1;
893 break;
894 }
895 ++pos;
896 }
897 if (!found) {
898 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
899 new_node->schema->name);
900 return LY_EINVAL;
901 }
902 } else {
903 ret = lyd_find_sibling_val(*first_node, new_node->schema, userord_anchor, 0, &anchor);
904 if (ret == LY_ENOTFOUND) {
905 LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.",
906 new_node->schema->name);
907 return LY_EINVAL;
908 } else if (ret) {
909 return ret;
910 }
Michal Vaskod59035b2020-07-08 12:00:06 +0200911 }
912
913 /* insert after */
914 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
915 assert(new_node->prev == anchor);
916 if (*first_node == new_node) {
917 *first_node = anchor;
918 }
919 } else {
920 if ((*first_node)->schema->flags & LYS_KEY) {
921 assert(parent_node && (parent_node->schema->nodetype == LYS_LIST));
922
923 /* find last key */
924 anchor = *first_node;
925 while (anchor->next && (anchor->next->schema->flags & LYS_KEY)) {
926 anchor = anchor->next;
927 }
928 /* insert after the last key */
929 LY_CHECK_RET(lyd_insert_after(anchor, new_node));
930 } else {
931 /* insert at the beginning */
932 LY_CHECK_RET(lyd_insert_before(*first_node, new_node));
933 *first_node = new_node;
934 }
935 }
936
937 return LY_SUCCESS;
938}
939
940/**
941 * @brief Apply diff subtree on data tree nodes, recursively.
942 *
943 * @param[in,out] first_node First sibling of the data tree.
944 * @param[in] parent_node Parent of the first sibling.
945 * @param[in] diff_node Current diff node.
Michal Vaskoe6323f62020-07-09 15:49:02 +0200946 * @param[in] diff_cb Optional diff callback.
947 * @param[in] cb_data User data for @p diff_cb.
Michal Vaskoe78faec2021-04-08 17:24:43 +0200948 * @param[in,out] dup_inst Duplicate instance cache for all @p diff_node siblings.
Michal Vaskod59035b2020-07-08 12:00:06 +0200949 * @return LY_ERR value.
950 */
951static LY_ERR
952lyd_diff_apply_r(struct lyd_node **first_node, struct lyd_node *parent_node, const struct lyd_node *diff_node,
Michal Vaskod7c048c2021-05-18 16:12:55 +0200953 lyd_diff_cb diff_cb, void *cb_data, struct lyd_dup_inst **dup_inst)
Michal Vaskod59035b2020-07-08 12:00:06 +0200954{
955 LY_ERR ret;
956 struct lyd_node *match, *diff_child;
Michal Vaskoe78faec2021-04-08 17:24:43 +0200957 const char *str_val, *meta_str;
Michal Vaskoe6323f62020-07-09 15:49:02 +0200958 enum lyd_diff_op op;
959 struct lyd_meta *meta;
Michal Vaskod7c048c2021-05-18 16:12:55 +0200960 struct lyd_dup_inst *child_dup_inst = NULL;
Michal Vaskob7be7a82020-08-20 09:09:04 +0200961 const struct ly_ctx *ctx = LYD_CTX(diff_node);
Michal Vaskod59035b2020-07-08 12:00:06 +0200962
963 /* read all the valid attributes */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200964 LY_CHECK_RET(lyd_diff_get_op(diff_node, &op));
Michal Vaskod59035b2020-07-08 12:00:06 +0200965
Michal Vaskoe6323f62020-07-09 15:49:02 +0200966 /* handle specific user-ordered (leaf-)lists operations separately */
967 if (lysc_is_userordered(diff_node->schema) && ((op == LYD_DIFF_OP_CREATE) || (op == LYD_DIFF_OP_REPLACE))) {
968 if (op == LYD_DIFF_OP_REPLACE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200969 /* find the node (we must have some siblings because the node was only moved) */
Michal Vaskoe78faec2021-04-08 17:24:43 +0200970 LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match));
971 LY_CHECK_ERR_RET(!match, LOGINT(ctx), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +0200972 } else {
Michal Vasko3a41dff2020-07-15 14:30:28 +0200973 /* duplicate the node */
974 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +0200975 }
976
Michal Vaskoe78faec2021-04-08 17:24:43 +0200977 /* get "key", "value", or "position" metadata string value */
978 if (lysc_is_dup_inst_list(diff_node->schema)) {
979 meta_str = "yang:position";
980 } else if (diff_node->schema->nodetype == LYS_LIST) {
981 meta_str = "yang:key";
982 } else {
983 meta_str = "yang:value";
984 }
985 meta = lyd_find_meta(diff_node->meta, NULL, meta_str);
986 LY_CHECK_ERR_RET(!meta, LOGINT(ctx), LY_EINT);
Radek Krejci6d5ba0c2021-04-26 07:49:59 +0200987 str_val = lyd_get_meta_value(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +0200988
Michal Vaskod59035b2020-07-08 12:00:06 +0200989 /* insert/move the node */
Michal Vaskoe6323f62020-07-09 15:49:02 +0200990 if (str_val[0]) {
991 ret = lyd_diff_insert(first_node, parent_node, match, str_val);
Michal Vaskod59035b2020-07-08 12:00:06 +0200992 } else {
993 ret = lyd_diff_insert(first_node, parent_node, match, NULL);
994 }
995 if (ret) {
Michal Vaskoe6323f62020-07-09 15:49:02 +0200996 if (op == LYD_DIFF_OP_CREATE) {
Michal Vaskod59035b2020-07-08 12:00:06 +0200997 lyd_free_tree(match);
998 }
999 return ret;
1000 }
1001
1002 goto next_iter_r;
1003 }
1004
1005 /* apply operation */
Michal Vaskoe6323f62020-07-09 15:49:02 +02001006 switch (op) {
1007 case LYD_DIFF_OP_NONE:
Michal Vaskod59035b2020-07-08 12:00:06 +02001008 /* find the node */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001009 LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match));
1010 LY_CHECK_ERR_RET(!match, LOGINT(ctx), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +02001011
1012 if (match->schema->nodetype & LYD_NODE_TERM) {
1013 /* special case of only dflt flag change */
1014 if (diff_node->flags & LYD_DEFAULT) {
1015 match->flags |= LYD_DEFAULT;
1016 } else {
1017 match->flags &= ~LYD_DEFAULT;
1018 }
1019 } else {
1020 /* none operation on nodes without children is redundant and hence forbidden */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001021 if (!lyd_child_no_keys(diff_node)) {
Michal Vaskod59035b2020-07-08 12:00:06 +02001022 LOGINT_RET(ctx);
1023 }
1024 }
1025 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001026 case LYD_DIFF_OP_CREATE:
Michal Vaskod59035b2020-07-08 12:00:06 +02001027 /* duplicate the node */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001028 LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match));
Michal Vaskod59035b2020-07-08 12:00:06 +02001029
1030 /* insert it at the end */
1031 ret = 0;
Michal Vaskob104f112020-07-17 09:54:54 +02001032 if (parent_node) {
1033 ret = lyd_insert_child(parent_node, match);
Michal Vaskod59035b2020-07-08 12:00:06 +02001034 } else {
Michal Vaskob104f112020-07-17 09:54:54 +02001035 ret = lyd_insert_sibling(*first_node, match, first_node);
Michal Vaskod59035b2020-07-08 12:00:06 +02001036 }
1037 if (ret) {
1038 lyd_free_tree(match);
1039 return ret;
1040 }
1041
1042 break;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001043 case LYD_DIFF_OP_DELETE:
Michal Vaskod59035b2020-07-08 12:00:06 +02001044 /* find the node */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001045 LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match));
1046 LY_CHECK_ERR_RET(!match, LOGINT(ctx), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +02001047
1048 /* remove it */
1049 if ((match == *first_node) && !match->parent) {
1050 assert(!parent_node);
1051 /* we have removed the top-level node */
1052 *first_node = (*first_node)->next;
1053 }
1054 lyd_free_tree(match);
1055
1056 /* we are not going recursively in this case, the whole subtree was already deleted */
1057 return LY_SUCCESS;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001058 case LYD_DIFF_OP_REPLACE:
Michal Vaskobaba84e2021-02-05 16:33:30 +01001059 LY_CHECK_ERR_RET(!(diff_node->schema->nodetype & (LYS_LEAF | LYS_ANYDATA)), LOGINT(ctx), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +02001060
1061 /* find the node */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001062 LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match));
1063 LY_CHECK_ERR_RET(!match, LOGINT(ctx), LY_EINT);
Michal Vaskod59035b2020-07-08 12:00:06 +02001064
Michal Vaskobaba84e2021-02-05 16:33:30 +01001065 /* update the value */
1066 if (diff_node->schema->nodetype == LYS_LEAF) {
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001067 ret = lyd_change_term(match, lyd_get_value(diff_node));
Michal Vaskobaba84e2021-02-05 16:33:30 +01001068 if (ret && (ret != LY_EEXIST)) {
1069 LOGINT_RET(ctx);
1070 }
1071 } else {
1072 struct lyd_node_any *any = (struct lyd_node_any *)diff_node;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001073 LY_CHECK_RET(lyd_any_copy_value(match, &any->value, any->value_type));
Michal Vaskod59035b2020-07-08 12:00:06 +02001074 }
1075
1076 /* with flags */
1077 match->flags = diff_node->flags;
1078 break;
1079 default:
1080 LOGINT_RET(ctx);
1081 }
1082
1083next_iter_r:
1084 if (diff_cb) {
1085 /* call callback */
1086 LY_CHECK_RET(diff_cb(diff_node, match, cb_data));
1087 }
1088
1089 /* apply diff recursively */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001090 ret = LY_SUCCESS;
Radek Krejcia1c1e542020-09-29 16:06:52 +02001091 LY_LIST_FOR(lyd_child_no_keys(diff_node), diff_child) {
Michal Vaskoe78faec2021-04-08 17:24:43 +02001092 ret = lyd_diff_apply_r(lyd_node_child_p(match), match, diff_child, diff_cb, cb_data, &child_dup_inst);
1093 if (ret) {
1094 break;
1095 }
Michal Vaskod59035b2020-07-08 12:00:06 +02001096 }
1097
Michal Vaskod7c048c2021-05-18 16:12:55 +02001098 lyd_dup_inst_free(child_dup_inst);
Michal Vaskoe78faec2021-04-08 17:24:43 +02001099 return ret;
Michal Vaskod59035b2020-07-08 12:00:06 +02001100}
1101
1102API LY_ERR
1103lyd_diff_apply_module(struct lyd_node **data, const struct lyd_node *diff, const struct lys_module *mod,
Radek Krejci0f969882020-08-21 16:56:47 +02001104 lyd_diff_cb diff_cb, void *cb_data)
Michal Vaskod59035b2020-07-08 12:00:06 +02001105{
1106 const struct lyd_node *root;
Michal Vaskod7c048c2021-05-18 16:12:55 +02001107 struct lyd_dup_inst *dup_inst = NULL;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001108 LY_ERR ret = LY_SUCCESS;
Michal Vaskod59035b2020-07-08 12:00:06 +02001109
1110 LY_LIST_FOR(diff, root) {
1111 if (mod && (lyd_owner_module(root) != mod)) {
1112 /* skip data nodes from different modules */
1113 continue;
1114 }
1115
1116 /* apply relevant nodes from the diff datatree */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001117 ret = lyd_diff_apply_r(data, NULL, root, diff_cb, cb_data, &dup_inst);
1118 if (ret) {
1119 break;
1120 }
Michal Vaskod59035b2020-07-08 12:00:06 +02001121 }
1122
Michal Vaskod7c048c2021-05-18 16:12:55 +02001123 lyd_dup_inst_free(dup_inst);
Michal Vaskoe78faec2021-04-08 17:24:43 +02001124 return ret;
Michal Vaskod59035b2020-07-08 12:00:06 +02001125}
1126
1127API LY_ERR
Michal Vasko3a41dff2020-07-15 14:30:28 +02001128lyd_diff_apply_all(struct lyd_node **data, const struct lyd_node *diff)
Michal Vaskod59035b2020-07-08 12:00:06 +02001129{
1130 return lyd_diff_apply_module(data, diff, NULL, NULL, NULL);
1131}
Michal Vaskoe6323f62020-07-09 15:49:02 +02001132
1133/**
1134 * @brief Update operations on a diff node when the new operation is NONE.
1135 *
1136 * @param[in] diff_match Node from the diff.
Michal Vaskoe78faec2021-04-08 17:24:43 +02001137 * @param[in] cur_op Current operation of @p diff_match.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001138 * @param[in] src_diff Current source diff node.
1139 * @return LY_ERR value.
1140 */
1141static LY_ERR
1142lyd_diff_merge_none(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1143{
1144 switch (cur_op) {
1145 case LYD_DIFF_OP_NONE:
1146 case LYD_DIFF_OP_CREATE:
1147 case LYD_DIFF_OP_REPLACE:
1148 if (src_diff->schema->nodetype & LYD_NODE_TERM) {
1149 /* NONE on a term means only its dflt flag was changed */
1150 diff_match->flags &= ~LYD_DEFAULT;
1151 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1152 }
1153 break;
1154 default:
1155 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001156 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001157 }
1158
1159 return LY_SUCCESS;
1160}
1161
1162/**
1163 * @brief Remove an attribute from a node.
1164 *
1165 * @param[in] node Node with the metadata.
1166 * @param[in] name Metadata name.
1167 */
1168static void
1169lyd_diff_del_meta(struct lyd_node *node, const char *name)
1170{
1171 struct lyd_meta *meta;
1172
1173 LY_LIST_FOR(node->meta, meta) {
1174 if (!strcmp(meta->name, name) && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001175 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001176 return;
1177 }
1178 }
1179
1180 assert(0);
1181}
1182
1183/**
1184 * @brief Set a specific operation of a node. Delete the previous operation, if any.
Michal Vasko871a0252020-11-11 18:35:24 +01001185 * Does not change the default flag.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001186 *
1187 * @param[in] node Node to change.
1188 * @param[in] op Operation to set.
1189 * @return LY_ERR value.
1190 */
1191static LY_ERR
1192lyd_diff_change_op(struct lyd_node *node, enum lyd_diff_op op)
1193{
1194 struct lyd_meta *meta;
1195
1196 LY_LIST_FOR(node->meta, meta) {
1197 if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) {
Michal Vasko3a41dff2020-07-15 14:30:28 +02001198 lyd_free_meta_single(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001199 break;
1200 }
1201 }
1202
Michal Vasko871a0252020-11-11 18:35:24 +01001203 return lyd_new_meta(LYD_CTX(node), node, NULL, "yang:operation", lyd_diff_op2str(op), 0, NULL);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001204}
1205
1206/**
1207 * @brief Update operations on a diff node when the new operation is REPLACE.
1208 *
1209 * @param[in] diff_match Node from the diff.
Michal Vaskoe78faec2021-04-08 17:24:43 +02001210 * @param[in] cur_op Current operation of @p diff_match.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001211 * @param[in] src_diff Current source diff node.
1212 * @return LY_ERR value.
1213 */
1214static LY_ERR
1215lyd_diff_merge_replace(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1216{
1217 LY_ERR ret;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001218 const char *str_val, *meta_name, *orig_meta_name;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001219 struct lyd_meta *meta;
1220 const struct lys_module *mod;
1221 const struct lyd_node_any *any;
1222
1223 /* get "yang" module for the metadata */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001224 mod = ly_ctx_get_module_latest(LYD_CTX(diff_match), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001225 assert(mod);
1226
1227 switch (cur_op) {
1228 case LYD_DIFF_OP_REPLACE:
1229 case LYD_DIFF_OP_CREATE:
1230 switch (diff_match->schema->nodetype) {
1231 case LYS_LIST:
1232 case LYS_LEAFLIST:
Michal Vasko4231fb62020-07-13 13:54:47 +02001233 /* it was created/moved somewhere, but now it will be created/moved somewhere else,
Michal Vaskoe6323f62020-07-09 15:49:02 +02001234 * keep orig_key/orig_value (only replace oper) and replace key/value */
1235 assert(lysc_is_userordered(diff_match->schema));
Michal Vaskoe78faec2021-04-08 17:24:43 +02001236 if (lysc_is_dup_inst_list(diff_match->schema)) {
1237 meta_name = "position";
1238 } else if (diff_match->schema->nodetype == LYS_LIST) {
1239 meta_name = "key";
1240 } else {
1241 meta_name = "value";
1242 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001243
1244 lyd_diff_del_meta(diff_match, meta_name);
1245 meta = lyd_find_meta(src_diff->meta, mod, meta_name);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001246 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001247 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001248 break;
1249 case LYS_LEAF:
1250 /* replaced with the exact same value, impossible */
Michal Vasko8f359bf2020-07-28 10:41:15 +02001251 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001252 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001253 }
1254
Michal Vaskoe6323f62020-07-09 15:49:02 +02001255 /* modify the node value */
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001256 if (lyd_change_term(diff_match, lyd_get_value(src_diff))) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001257 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001258 }
1259
Michal Vasko8caadab2020-11-05 17:38:15 +01001260 if (cur_op == LYD_DIFF_OP_REPLACE) {
1261 /* compare values whether there is any change at all */
1262 meta = lyd_find_meta(diff_match->meta, mod, "orig-value");
1263 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(diff_match)), LY_EINT);
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001264 str_val = lyd_get_meta_value(meta);
Michal Vasko8caadab2020-11-05 17:38:15 +01001265 ret = lyd_value_compare((struct lyd_node_term *)diff_match, str_val, strlen(str_val));
1266 if (!ret) {
1267 /* values are the same, remove orig-value meta and set oper to NONE */
1268 lyd_free_meta_single(meta);
1269 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1270 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001271 }
1272
1273 /* modify the default flag */
1274 diff_match->flags &= ~LYD_DEFAULT;
1275 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
1276 break;
1277 case LYS_ANYXML:
1278 case LYS_ANYDATA:
Michal Vasko8f359bf2020-07-28 10:41:15 +02001279 if (!lyd_compare_single(diff_match, src_diff, 0)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001280 /* replaced with the exact same value, impossible */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001281 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001282 }
1283
1284 /* modify the node value */
1285 any = (struct lyd_node_any *)src_diff;
1286 LY_CHECK_RET(lyd_any_copy_value(diff_match, &any->value, any->value_type));
1287 break;
1288 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001289 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001290 }
1291 break;
1292 case LYD_DIFF_OP_NONE:
1293 /* it is moved now */
1294 assert(lysc_is_userordered(diff_match->schema) && (diff_match->schema->nodetype == LYS_LIST));
1295
1296 /* change the operation */
1297 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1298
Michal Vaskoe78faec2021-04-08 17:24:43 +02001299 /* set orig-meta and meta */
1300 if (lysc_is_dup_inst_list(diff_match->schema)) {
1301 meta_name = "position";
1302 orig_meta_name = "orig-position";
1303 } else {
1304 meta_name = "key";
1305 orig_meta_name = "orig-key";
1306 }
1307
1308 meta = lyd_find_meta(src_diff->meta, mod, orig_meta_name);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001309 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001310 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001311
Michal Vaskoe78faec2021-04-08 17:24:43 +02001312 meta = lyd_find_meta(src_diff->meta, mod, meta_name);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001313 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Michal Vasko3a41dff2020-07-15 14:30:28 +02001314 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001315 break;
1316 default:
1317 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001318 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001319 }
1320
1321 return LY_SUCCESS;
1322}
1323
1324/**
1325 * @brief Update operations in a diff node when the new operation is CREATE.
1326 *
1327 * @param[in] diff_match Node from the diff.
Michal Vaskoe78faec2021-04-08 17:24:43 +02001328 * @param[in] cur_op Current operation of @p diff_match.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001329 * @param[in] src_diff Current source diff node.
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001330 * @param[in] options Diff merge options.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001331 * @return LY_ERR value.
1332 */
1333static LY_ERR
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001334lyd_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 +02001335{
1336 struct lyd_node *child;
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001337 const struct lysc_node_leaf *sleaf = NULL;
Michal Vasko871a0252020-11-11 18:35:24 +01001338 uint32_t trg_flags;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001339 const char *meta_name, *orig_meta_name;
1340 struct lyd_meta *meta, *orig_meta;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001341
1342 switch (cur_op) {
1343 case LYD_DIFF_OP_DELETE:
Michal Vasko871a0252020-11-11 18:35:24 +01001344 /* remember current flags */
1345 trg_flags = diff_match->flags;
1346
Michal Vaskoe78faec2021-04-08 17:24:43 +02001347 if (lysc_is_userordered(diff_match->schema)) {
1348 /* get anchor metadata */
1349 if (lysc_is_dup_inst_list(diff_match->schema)) {
1350 meta_name = "yang:position";
1351 orig_meta_name = "yang:orig-position";
1352 } else if (diff_match->schema->nodetype == LYS_LIST) {
1353 meta_name = "yang:key";
1354 orig_meta_name = "yang:orig-key";
1355 } else {
1356 meta_name = "yang:value";
1357 orig_meta_name = "yang:orig-value";
1358 }
1359 meta = lyd_find_meta(src_diff->meta, NULL, meta_name);
1360 orig_meta = lyd_find_meta(diff_match->meta, NULL, orig_meta_name);
1361 LY_CHECK_ERR_RET(!meta || !orig_meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
1362
1363 /* the (incorrect) assumption made here is that there are no previous diff nodes that would affect
1364 * the anchors stored in the metadata */
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001365 if (strcmp(lyd_get_meta_value(meta), lyd_get_meta_value(orig_meta))) {
Michal Vaskoe78faec2021-04-08 17:24:43 +02001366 /* deleted + created at another position -> operation REPLACE */
1367 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1368
1369 /* add anchor metadata */
1370 LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL));
1371 } else {
1372 /* deleted + created at the same position -> operation NONE */
1373 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1374
1375 /* delete anchor metadata */
1376 lyd_free_meta_single(orig_meta);
1377 }
1378 } else if (diff_match->schema->nodetype == LYS_LEAF) {
1379 if (options & LYD_DIFF_MERGE_DEFAULTS) {
1380 /* we are dealing with a leaf and are handling default values specially (as explicit nodes) */
1381 sleaf = (struct lysc_node_leaf *)diff_match->schema;
1382 }
1383
Radek Krejci55c4bd22021-04-26 08:09:04 +02001384 if (sleaf && sleaf->dflt && !sleaf->dflt->realtype->plugin->compare(sleaf->dflt,
1385 &((struct lyd_node_term *)src_diff)->value)) {
Michal Vaskoe78faec2021-04-08 17:24:43 +02001386 /* we deleted it, so a default value was in-use, and it matches the created value -> operation NONE */
1387 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1388 } else if (!lyd_compare_single(diff_match, src_diff, 0)) {
1389 /* deleted + created -> operation NONE */
1390 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1391 } else {
1392 /* we deleted it, but it was created with a different value -> operation REPLACE */
1393 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE));
1394
1395 /* current value is the previous one (meta) */
1396 LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-value",
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001397 lyd_get_value(diff_match), 0, NULL));
Michal Vaskoe78faec2021-04-08 17:24:43 +02001398
1399 /* update the value itself */
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001400 LY_CHECK_RET(lyd_change_term(diff_match, lyd_get_value(src_diff)));
Michal Vaskoe78faec2021-04-08 17:24:43 +02001401 }
1402 } else {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001403 /* deleted + created -> operation NONE */
1404 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001405 }
1406
1407 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
Michal Vasko4b715ca2020-11-11 18:39:57 +01001408 /* add orig-dflt metadata */
1409 LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-default",
1410 trg_flags & LYD_DEFAULT ? "true" : "false", 0, NULL));
1411
Michal Vaskoe6323f62020-07-09 15:49:02 +02001412 /* update dflt flag itself */
1413 diff_match->flags &= ~LYD_DEFAULT;
1414 diff_match->flags |= src_diff->flags & LYD_DEFAULT;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001415 }
1416
1417 /* but the operation of its children should remain DELETE */
1418 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
1419 LY_CHECK_RET(lyd_diff_change_op(child, LYD_DIFF_OP_DELETE));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001420 }
1421 break;
1422 default:
1423 /* create and replace operations are not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001424 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001425 }
1426
1427 return LY_SUCCESS;
1428}
1429
1430/**
1431 * @brief Update operations on a diff node when the new operation is DELETE.
1432 *
1433 * @param[in] diff_match Node from the diff.
Michal Vaskoe78faec2021-04-08 17:24:43 +02001434 * @param[in] cur_op Current operation of @p diff_match.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001435 * @param[in] src_diff Current source diff node.
1436 * @return LY_ERR value.
1437 */
1438static LY_ERR
1439lyd_diff_merge_delete(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff)
1440{
1441 struct lyd_node *next, *child;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001442 struct lyd_meta *meta;
1443 const char *meta_name;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001444
1445 /* we can delete only exact existing nodes */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001446 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 +02001447
1448 switch (cur_op) {
1449 case LYD_DIFF_OP_CREATE:
1450 /* it was created, but then deleted -> set NONE operation */
1451 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE));
1452
1453 if (diff_match->schema->nodetype & LYD_NODE_TERM) {
1454 /* add orig-default meta because it is expected */
Michal Vasko871a0252020-11-11 18:35:24 +01001455 LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-default",
1456 diff_match->flags & LYD_DEFAULT ? "true" : "false", 0, NULL));
Michal Vaskoe78faec2021-04-08 17:24:43 +02001457 } else if (!lysc_is_dup_inst_list(diff_match->schema)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001458 /* keep operation for all descendants (for now) */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001459 LY_LIST_FOR(lyd_child_no_keys(diff_match), child) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001460 LY_CHECK_RET(lyd_diff_change_op(child, cur_op));
1461 }
Michal Vaskoe78faec2021-04-08 17:24:43 +02001462 } /* else key-less list, for which all the descendants act as keys */
Michal Vaskoe6323f62020-07-09 15:49:02 +02001463 break;
1464 case LYD_DIFF_OP_REPLACE:
Michal Vaskoe78faec2021-04-08 17:24:43 +02001465 /* similar to none operation but also remove the redundant metadata */
1466 if (lysc_is_userordered(diff_match->schema)) {
1467 if (lysc_is_dup_inst_list(diff_match->schema)) {
1468 meta_name = "position";
1469 } else if (diff_match->schema->nodetype == LYS_LIST) {
1470 meta_name = "key";
1471 } else {
1472 meta_name = "value";
1473 }
1474 } else {
1475 assert(diff_match->schema->nodetype == LYS_LEAF);
1476
1477 /* switch value for the original one */
1478 meta = lyd_find_meta(diff_match->meta, NULL, "yang:orig-value");
1479 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001480 if (lyd_change_term(diff_match, lyd_get_meta_value(meta))) {
Michal Vaskoe78faec2021-04-08 17:24:43 +02001481 LOGINT_RET(LYD_CTX(src_diff));
1482 }
1483
1484 /* switch default for the original one, then remove the meta */
1485 meta = lyd_find_meta(diff_match->meta, NULL, "yang:orig-default");
1486 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(src_diff)), LY_EINT);
1487 diff_match->flags &= ~LYD_DEFAULT;
1488 if (meta->value.boolean) {
1489 diff_match->flags |= LYD_DEFAULT;
1490 }
1491 lyd_free_meta_single(meta);
1492
1493 meta_name = "orig-value";
1494 }
1495 lyd_diff_del_meta(diff_match, meta_name);
1496
Radek Krejcif13b87b2020-12-01 22:02:17 +01001497 /* fall through */
Michal Vaskoe6323f62020-07-09 15:49:02 +02001498 case LYD_DIFF_OP_NONE:
1499 /* it was not modified, but should be deleted -> set DELETE operation */
1500 LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_DELETE));
1501
Michal Vasko5632e0d2020-07-31 14:13:37 +02001502 /* all descendants not in the diff will be deleted and redundant in the diff, so remove them */
Radek Krejcia1c1e542020-09-29 16:06:52 +02001503 LY_LIST_FOR_SAFE(lyd_child_no_keys(diff_match), next, child) {
1504 if (lyd_find_sibling_first(lyd_child(src_diff), child, NULL) == LY_ENOTFOUND) {
Michal Vasko5632e0d2020-07-31 14:13:37 +02001505 lyd_free_tree(child);
1506 }
Michal Vaskoe6323f62020-07-09 15:49:02 +02001507 }
1508 break;
1509 default:
1510 /* delete operation is not valid */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001511 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001512 }
1513
1514 return LY_SUCCESS;
1515}
1516
1517/**
1518 * @brief Check whether this diff node is redundant (does not change data).
1519 *
1520 * @param[in] diff Diff node.
1521 * @return 0 if not, non-zero if it is.
1522 */
1523static int
1524lyd_diff_is_redundant(struct lyd_node *diff)
1525{
1526 enum lyd_diff_op op;
1527 struct lyd_meta *meta, *orig_val_meta = NULL, *val_meta = NULL;
1528 struct lyd_node *child;
1529 const struct lys_module *mod;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001530 const char *str, *orig_meta_name, *meta_name;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001531
1532 assert(diff);
1533
Michal Vaskoe78faec2021-04-08 17:24:43 +02001534 if (lysc_is_dup_inst_list(diff->schema)) {
1535 /* all descendants are keys */
1536 child = NULL;
1537 } else {
1538 child = lyd_child_no_keys(diff);
1539 }
Michal Vaskob7be7a82020-08-20 09:09:04 +02001540 mod = ly_ctx_get_module_latest(LYD_CTX(diff), "yang");
Michal Vaskoe6323f62020-07-09 15:49:02 +02001541 assert(mod);
1542
1543 /* get node operation */
Michal Vasko53bf6f22020-07-14 08:23:40 +02001544 LY_CHECK_RET(lyd_diff_get_op(diff, &op), 0);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001545
1546 if ((op == LYD_DIFF_OP_REPLACE) && lysc_is_userordered(diff->schema)) {
Michal Vaskoe78faec2021-04-08 17:24:43 +02001547 /* get metadata names */
1548 if (lysc_is_dup_inst_list(diff->schema)) {
1549 meta_name = "position";
1550 orig_meta_name = "orig-position";
1551 } else if (diff->schema->nodetype == LYS_LIST) {
1552 meta_name = "key";
1553 orig_meta_name = "orig-key";
1554 } else {
1555 meta_name = "value";
1556 orig_meta_name = "orig-value";
1557 }
1558
Michal Vaskoe6323f62020-07-09 15:49:02 +02001559 /* check for redundant move */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001560 orig_val_meta = lyd_find_meta(diff->meta, mod, orig_meta_name);
1561 val_meta = lyd_find_meta(diff->meta, mod, meta_name);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001562 assert(orig_val_meta && val_meta);
1563
1564 if (!lyd_compare_meta(orig_val_meta, val_meta)) {
1565 /* there is actually no move */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001566 lyd_free_meta_single(orig_val_meta);
1567 lyd_free_meta_single(val_meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001568 if (child) {
1569 /* change operation to NONE, we have siblings */
1570 lyd_diff_change_op(diff, LYD_DIFF_OP_NONE);
1571 return 0;
1572 }
1573
1574 /* redundant node, BUT !!
1575 * In diff the move operation is always converted to be INSERT_AFTER, which is fine
1576 * because the data that this is applied on should not change for the diff lifetime.
1577 * However, when we are merging 2 diffs, this conversion is actually lossy because
1578 * if the data change, the move operation can also change its meaning. In this specific
1579 * case the move operation will be lost. But it can be considered a feature, it is not supported.
1580 */
1581 return 1;
1582 }
1583 } else if ((op == LYD_DIFF_OP_NONE) && (diff->schema->nodetype & LYD_NODE_TERM)) {
1584 /* check whether at least the default flags are different */
1585 meta = lyd_find_meta(diff->meta, mod, "orig-default");
1586 assert(meta);
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001587 str = lyd_get_meta_value(meta);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001588
1589 /* if previous and current dflt flags are the same, this node is redundant */
1590 if ((!strcmp(str, "true") && (diff->flags & LYD_DEFAULT)) || (!strcmp(str, "false") && !(diff->flags & LYD_DEFAULT))) {
1591 return 1;
1592 }
1593 return 0;
1594 }
1595
1596 if (!child && (op == LYD_DIFF_OP_NONE)) {
1597 return 1;
1598 }
1599
1600 return 0;
1601}
1602
1603/**
Michal Vaskoe78faec2021-04-08 17:24:43 +02001604 * @brief Merge sysrepo diff subtree with another diff, recursively.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001605 *
1606 * @param[in] src_diff Source diff node.
1607 * @param[in] diff_parent Current sysrepo diff parent.
1608 * @param[in] diff_cb Optional diff callback.
1609 * @param[in] cb_data User data for @p diff_cb.
Michal Vaskoe78faec2021-04-08 17:24:43 +02001610 * @param[in,out] dup_inst Duplicate instance cache for all @p src_diff siblings.
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001611 * @param[in] options Diff merge options.
Michal Vaskoe6323f62020-07-09 15:49:02 +02001612 * @param[in,out] diff Diff root node.
1613 * @return LY_ERR value.
1614 */
1615static LY_ERR
1616lyd_diff_merge_r(const struct lyd_node *src_diff, struct lyd_node *diff_parent, lyd_diff_cb diff_cb, void *cb_data,
Michal Vaskod7c048c2021-05-18 16:12:55 +02001617 struct lyd_dup_inst **dup_inst, uint16_t options, struct lyd_node **diff)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001618{
1619 LY_ERR ret = LY_SUCCESS;
1620 struct lyd_node *child, *diff_node = NULL;
1621 enum lyd_diff_op src_op, cur_op;
Michal Vaskod7c048c2021-05-18 16:12:55 +02001622 struct lyd_dup_inst *child_dup_inst = NULL;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001623
1624 /* get source node operation */
1625 LY_CHECK_RET(lyd_diff_get_op(src_diff, &src_op));
1626
1627 /* find an equal node in the current diff */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001628 LY_CHECK_RET(lyd_diff_find_match(diff_parent ? lyd_child_no_keys(diff_parent) : *diff, src_diff, 1, dup_inst, &diff_node));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001629
1630 if (diff_node) {
1631 /* get target (current) operation */
1632 LY_CHECK_RET(lyd_diff_get_op(diff_node, &cur_op));
1633
1634 /* merge operations */
1635 switch (src_op) {
1636 case LYD_DIFF_OP_REPLACE:
1637 ret = lyd_diff_merge_replace(diff_node, cur_op, src_diff);
1638 break;
1639 case LYD_DIFF_OP_CREATE:
Michal Vasko1dc0a842021-02-04 11:04:57 +01001640 if ((cur_op == LYD_DIFF_OP_CREATE) && lysc_is_dup_inst_list(diff_node->schema)) {
Michal Vaskoe78faec2021-04-08 17:24:43 +02001641 /* special case of creating duplicate (leaf-)list instances */
Michal Vasko1dc0a842021-02-04 11:04:57 +01001642 goto add_diff;
1643 }
1644
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001645 ret = lyd_diff_merge_create(diff_node, cur_op, src_diff, options);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001646 break;
1647 case LYD_DIFF_OP_DELETE:
1648 ret = lyd_diff_merge_delete(diff_node, cur_op, src_diff);
1649 break;
1650 case LYD_DIFF_OP_NONE:
Michal Vaskoe78faec2021-04-08 17:24:43 +02001651 /* key-less list can never have "none" operation since all its descendants are acting as "keys" */
1652 assert((src_diff->schema->nodetype != LYS_LIST) || !lysc_is_dup_inst_list(src_diff->schema));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001653 ret = lyd_diff_merge_none(diff_node, cur_op, src_diff);
1654 break;
1655 default:
Michal Vaskob7be7a82020-08-20 09:09:04 +02001656 LOGINT_RET(LYD_CTX(src_diff));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001657 }
1658 if (ret) {
Michal Vaskob7be7a82020-08-20 09:09:04 +02001659 LOGERR(LYD_CTX(src_diff), LY_EOTHER, "Merging operation \"%s\" failed.", lyd_diff_op2str(src_op));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001660 return ret;
1661 }
1662
1663 if (diff_cb) {
1664 /* call callback */
Michal Vaskobc5fba92020-08-07 12:14:39 +02001665 LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001666 }
1667
1668 /* update diff parent */
1669 diff_parent = diff_node;
1670
Michal Vaskoe78faec2021-04-08 17:24:43 +02001671 /* for diff purposes, all key-less list descendants actually act as keys (identifying the same instances),
1672 * so there is nothing to merge for these "keys" */
1673 if (!lysc_is_dup_inst_list(src_diff->schema)) {
1674 /* merge src_diff recursively */
1675 LY_LIST_FOR(lyd_child_no_keys(src_diff), child) {
1676 ret = lyd_diff_merge_r(child, diff_parent, diff_cb, cb_data, &child_dup_inst, options, diff);
1677 if (ret) {
1678 break;
1679 }
1680 }
Michal Vaskod7c048c2021-05-18 16:12:55 +02001681 lyd_dup_inst_free(child_dup_inst);
Michal Vaskoe78faec2021-04-08 17:24:43 +02001682 LY_CHECK_RET(ret);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001683 }
1684 } else {
Michal Vasko1dc0a842021-02-04 11:04:57 +01001685add_diff:
Michal Vaskoe6323f62020-07-09 15:49:02 +02001686 /* add new diff node with all descendants */
Michal Vasko871a0252020-11-11 18:35:24 +01001687 LY_CHECK_RET(lyd_dup_single(src_diff, (struct lyd_node_inner *)diff_parent, LYD_DUP_RECURSIVE | LYD_DUP_WITH_FLAGS,
1688 &diff_node));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001689
1690 /* insert node into diff if not already */
1691 if (!diff_parent) {
Michal Vaskob104f112020-07-17 09:54:54 +02001692 lyd_insert_sibling(*diff, diff_node, diff);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001693 }
1694
1695 /* update operation */
1696 LY_CHECK_RET(lyd_diff_change_op(diff_node, src_op));
1697
1698 if (diff_cb) {
Michal Vaskoe2af8412020-12-03 14:11:38 +01001699 /* call callback with no source diff node since it was duplicated and just added */
1700 LY_CHECK_RET(diff_cb(NULL, diff_node, cb_data));
Michal Vaskoe6323f62020-07-09 15:49:02 +02001701 }
1702
1703 /* update diff parent */
1704 diff_parent = diff_node;
1705 }
1706
1707 /* remove any redundant nodes */
Michal Vaskob98d7082020-07-15 16:38:36 +02001708 if (lyd_diff_is_redundant(diff_parent)) {
Michal Vaskoe6323f62020-07-09 15:49:02 +02001709 if (diff_parent == *diff) {
1710 *diff = (*diff)->next;
1711 }
1712 lyd_free_tree(diff_parent);
1713 }
1714
1715 return LY_SUCCESS;
1716}
1717
1718API LY_ERR
Michal Vaskofb737aa2020-08-06 13:53:53 +02001719lyd_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 +01001720 lyd_diff_cb diff_cb, void *cb_data, uint16_t options)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001721{
1722 const struct lyd_node *src_root;
Michal Vaskod7c048c2021-05-18 16:12:55 +02001723 struct lyd_dup_inst *dup_inst = NULL;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001724 LY_ERR ret = LY_SUCCESS;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001725
1726 LY_LIST_FOR(src_diff, src_root) {
1727 if (mod && (lyd_owner_module(src_root) != mod)) {
1728 /* skip data nodes from different modules */
1729 continue;
1730 }
1731
1732 /* apply relevant nodes from the diff datatree */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001733 LY_CHECK_GOTO(ret = lyd_diff_merge_r(src_root, NULL, diff_cb, cb_data, &dup_inst, options, diff), cleanup);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001734 }
1735
Michal Vaskoe78faec2021-04-08 17:24:43 +02001736cleanup:
Michal Vaskod7c048c2021-05-18 16:12:55 +02001737 lyd_dup_inst_free(dup_inst);
Michal Vaskoe78faec2021-04-08 17:24:43 +02001738 return ret;
Michal Vaskoe6323f62020-07-09 15:49:02 +02001739}
1740
1741API LY_ERR
Michal Vasko04f85912020-08-07 12:14:58 +02001742lyd_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 +01001743 lyd_diff_cb diff_cb, void *cb_data, uint16_t options)
Michal Vasko04f85912020-08-07 12:14:58 +02001744{
Michal Vaskoe78faec2021-04-08 17:24:43 +02001745 LY_ERR ret;
Michal Vaskod7c048c2021-05-18 16:12:55 +02001746 struct lyd_dup_inst *dup_inst = NULL;
Michal Vaskoe78faec2021-04-08 17:24:43 +02001747
Michal Vasko04f85912020-08-07 12:14:58 +02001748 if (!src_sibling) {
1749 return LY_SUCCESS;
1750 }
1751
Michal Vaskoe78faec2021-04-08 17:24:43 +02001752 ret = lyd_diff_merge_r(src_sibling, diff_parent, diff_cb, cb_data, &dup_inst, options, diff_first);
Michal Vaskod7c048c2021-05-18 16:12:55 +02001753 lyd_dup_inst_free(dup_inst);
Michal Vaskoe78faec2021-04-08 17:24:43 +02001754 return ret;
Michal Vasko04f85912020-08-07 12:14:58 +02001755}
1756
1757API LY_ERR
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001758lyd_diff_merge_all(struct lyd_node **diff, const struct lyd_node *src_diff, uint16_t options)
Michal Vaskoe6323f62020-07-09 15:49:02 +02001759{
Michal Vaskoc0e58e82020-11-11 19:04:33 +01001760 return lyd_diff_merge_module(diff, src_diff, NULL, NULL, NULL, options);
Michal Vaskoe6323f62020-07-09 15:49:02 +02001761}
Michal Vasko4231fb62020-07-13 13:54:47 +02001762
1763static LY_ERR
Michal Vaskobaba84e2021-02-05 16:33:30 +01001764lyd_diff_reverse_value(struct lyd_node *node, const struct lys_module *mod)
Michal Vasko4231fb62020-07-13 13:54:47 +02001765{
1766 LY_ERR ret = LY_SUCCESS;
1767 struct lyd_meta *meta;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001768 const char *val1 = NULL;
1769 char *val2;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001770 uint32_t flags;
Michal Vasko4231fb62020-07-13 13:54:47 +02001771
Michal Vaskobaba84e2021-02-05 16:33:30 +01001772 assert(node->schema->nodetype & (LYS_LEAF | LYS_ANYDATA));
1773
1774 meta = lyd_find_meta(node->meta, mod, "orig-value");
1775 LY_CHECK_ERR_RET(!meta, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001776
1777 /* orig-value */
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001778 val1 = lyd_get_meta_value(meta);
Michal Vasko4231fb62020-07-13 13:54:47 +02001779
1780 /* current value */
Michal Vaskobaba84e2021-02-05 16:33:30 +01001781 if (node->schema->nodetype == LYS_LEAF) {
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001782 val2 = strdup(lyd_get_value(node));
Michal Vaskobaba84e2021-02-05 16:33:30 +01001783 } else {
1784 LY_CHECK_RET(lyd_any_value_str(node, &val2));
1785 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001786
1787 /* switch values, keep default flag */
Michal Vaskobaba84e2021-02-05 16:33:30 +01001788 flags = node->flags;
1789 if (node->schema->nodetype == LYS_LEAF) {
1790 LY_CHECK_GOTO(ret = lyd_change_term(node, val1), cleanup);
1791 } else {
1792 union lyd_any_value anyval = {.str = val1};
1793 LY_CHECK_GOTO(ret = lyd_any_copy_value(node, &anyval, LYD_ANYDATA_STRING), cleanup);
1794 }
1795 node->flags = flags;
Michal Vasko4231fb62020-07-13 13:54:47 +02001796 LY_CHECK_GOTO(ret = lyd_change_meta(meta, val2), cleanup);
1797
1798cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001799 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001800 return ret;
1801}
1802
1803static LY_ERR
1804lyd_diff_reverse_default(struct lyd_node *node, const struct lys_module *mod)
1805{
1806 struct lyd_meta *meta;
Radek Krejci1deb5be2020-08-26 16:43:36 +02001807 uint32_t flag1, flag2;
Michal Vasko4231fb62020-07-13 13:54:47 +02001808
1809 meta = lyd_find_meta(node->meta, mod, "orig-default");
Michal Vasko610e93b2020-11-09 20:58:32 +01001810 LY_CHECK_ERR_RET(!meta, LOGINT(mod->ctx), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001811
1812 /* orig-default */
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001813 if (meta->value.boolean) {
Michal Vasko4231fb62020-07-13 13:54:47 +02001814 flag1 = LYD_DEFAULT;
1815 } else {
1816 flag1 = 0;
1817 }
1818
1819 /* current default */
1820 flag2 = node->flags & LYD_DEFAULT;
1821
Michal Vasko610e93b2020-11-09 20:58:32 +01001822 if (flag1 == flag2) {
1823 /* no default state change so nothing to reverse */
1824 return LY_SUCCESS;
1825 }
1826
Michal Vasko4231fb62020-07-13 13:54:47 +02001827 /* switch defaults */
1828 node->flags &= ~LYD_DEFAULT;
1829 node->flags |= flag1;
1830 LY_CHECK_RET(lyd_change_meta(meta, flag2 ? "true" : "false"));
1831
1832 return LY_SUCCESS;
1833}
1834
1835static LY_ERR
1836lyd_diff_reverse_meta(struct lyd_node *node, const struct lys_module *mod, const char *name1, const char *name2)
1837{
1838 LY_ERR ret = LY_SUCCESS;
1839 struct lyd_meta *meta1, *meta2;
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001840 const char *val1 = NULL;
1841 char *val2 = NULL;
Michal Vasko4231fb62020-07-13 13:54:47 +02001842
1843 meta1 = lyd_find_meta(node->meta, mod, name1);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001844 LY_CHECK_ERR_RET(!meta1, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001845
1846 meta2 = lyd_find_meta(node->meta, mod, name2);
Michal Vaskob7be7a82020-08-20 09:09:04 +02001847 LY_CHECK_ERR_RET(!meta2, LOGINT(LYD_CTX(node)), LY_EINT);
Michal Vasko4231fb62020-07-13 13:54:47 +02001848
1849 /* value1 */
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001850 val1 = lyd_get_meta_value(meta1);
Michal Vasko4231fb62020-07-13 13:54:47 +02001851
1852 /* value2 */
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001853 val2 = strdup(lyd_get_meta_value(meta2));
Michal Vasko4231fb62020-07-13 13:54:47 +02001854
1855 /* switch values */
1856 LY_CHECK_GOTO(ret = lyd_change_meta(meta1, val2), cleanup);
1857 LY_CHECK_GOTO(ret = lyd_change_meta(meta2, val1), cleanup);
1858
1859cleanup:
Michal Vaskoba99a3e2020-08-18 15:50:05 +02001860 free(val2);
Michal Vasko4231fb62020-07-13 13:54:47 +02001861 return ret;
1862}
1863
Michal Vasko9a7e9d02021-03-09 13:52:25 +01001864/**
1865 * @brief Remove specific operation from all the nodes in a subtree.
1866 *
1867 * @param[in] diff Diff subtree to process.
1868 * @param[in] op Only expected operation.
1869 * @return LY_ERR value.
1870 */
1871static LY_ERR
1872lyd_diff_reverse_remove_op_r(struct lyd_node *diff, enum lyd_diff_op op)
1873{
1874 struct lyd_node *elem;
1875 struct lyd_meta *meta;
1876
1877 LYD_TREE_DFS_BEGIN(diff, elem) {
1878 meta = lyd_find_meta(elem->meta, NULL, "yang:operation");
1879 if (meta) {
Radek Krejci6d5ba0c2021-04-26 07:49:59 +02001880 LY_CHECK_ERR_RET(lyd_diff_str2op(lyd_get_meta_value(meta)) != op, LOGINT(LYD_CTX(diff)), LY_EINT);
Michal Vasko9a7e9d02021-03-09 13:52:25 +01001881 lyd_free_meta_single(meta);
1882 }
1883
1884 LYD_TREE_DFS_END(diff, elem);
1885 }
1886
1887 return LY_SUCCESS;
1888}
1889
Michal Vasko4231fb62020-07-13 13:54:47 +02001890API LY_ERR
Michal Vasko66535812020-08-11 08:44:22 +02001891lyd_diff_reverse_all(const struct lyd_node *src_diff, struct lyd_node **diff)
Michal Vasko4231fb62020-07-13 13:54:47 +02001892{
1893 LY_ERR ret = LY_SUCCESS;
1894 const struct lys_module *mod;
Michal Vasko9a7e9d02021-03-09 13:52:25 +01001895 struct lyd_node *root, *elem, *iter;
Michal Vasko4231fb62020-07-13 13:54:47 +02001896 enum lyd_diff_op op;
1897
1898 LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL);
1899
1900 if (!src_diff) {
1901 *diff = NULL;
1902 return LY_SUCCESS;
1903 }
1904
1905 /* duplicate diff */
Michal Vasko3a41dff2020-07-15 14:30:28 +02001906 LY_CHECK_RET(lyd_dup_siblings(src_diff, NULL, LYD_DUP_RECURSIVE, diff));
Michal Vasko4231fb62020-07-13 13:54:47 +02001907
1908 /* find module with metadata needed for later */
Michal Vaskob7be7a82020-08-20 09:09:04 +02001909 mod = ly_ctx_get_module_latest(LYD_CTX(src_diff), "yang");
1910 LY_CHECK_ERR_GOTO(!mod, LOGINT(LYD_CTX(src_diff)); ret = LY_EINT, cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001911
1912 LY_LIST_FOR(*diff, root) {
Michal Vasko56daf732020-08-10 10:57:18 +02001913 LYD_TREE_DFS_BEGIN(root, elem) {
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001914 /* skip all keys */
1915 if (!lysc_is_key(elem->schema)) {
1916 /* find operation attribute, if any */
1917 LY_CHECK_GOTO(ret = lyd_diff_get_op(elem, &op), cleanup);
Michal Vasko4231fb62020-07-13 13:54:47 +02001918
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001919 switch (op) {
1920 case LYD_DIFF_OP_CREATE:
1921 /* reverse create to delete */
1922 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_DELETE), cleanup);
Michal Vasko9e070522021-03-05 14:00:14 +01001923
Michal Vasko9a7e9d02021-03-09 13:52:25 +01001924 /* check all the children for the same operation, nothing else is expected */
1925 LY_LIST_FOR(lyd_child(elem), iter) {
1926 lyd_diff_reverse_remove_op_r(iter, LYD_DIFF_OP_CREATE);
1927 }
1928
Michal Vasko9e070522021-03-05 14:00:14 +01001929 LYD_TREE_DFS_continue = 1;
Michal Vasko4231fb62020-07-13 13:54:47 +02001930 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001931 case LYD_DIFF_OP_DELETE:
1932 /* reverse delete to create */
1933 LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_CREATE), cleanup);
Michal Vasko9e070522021-03-05 14:00:14 +01001934
Michal Vasko9a7e9d02021-03-09 13:52:25 +01001935 /* check all the children for the same operation, nothing else is expected */
1936 LY_LIST_FOR(lyd_child(elem), iter) {
1937 lyd_diff_reverse_remove_op_r(iter, LYD_DIFF_OP_DELETE);
1938 }
1939
Michal Vasko9e070522021-03-05 14:00:14 +01001940 LYD_TREE_DFS_continue = 1;
Michal Vasko4231fb62020-07-13 13:54:47 +02001941 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001942 case LYD_DIFF_OP_REPLACE:
1943 switch (elem->schema->nodetype) {
1944 case LYS_LEAF:
1945 /* leaf value change */
1946 LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup);
1947 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1948 break;
Michal Vaskobaba84e2021-02-05 16:33:30 +01001949 case LYS_ANYXML:
1950 case LYS_ANYDATA:
1951 /* any value change */
1952 LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup);
1953 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001954 case LYS_LEAFLIST:
1955 /* leaf-list move */
1956 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
Michal Vaskoe78faec2021-04-08 17:24:43 +02001957 if (lysc_is_dup_inst_list(elem->schema)) {
1958 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-position", "position"), cleanup);
1959 } else {
1960 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-value", "value"), cleanup);
1961 }
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001962 break;
1963 case LYS_LIST:
1964 /* list move */
Michal Vaskoe78faec2021-04-08 17:24:43 +02001965 if (lysc_is_dup_inst_list(elem->schema)) {
1966 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-position", "position"), cleanup);
1967 } else {
1968 LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-key", "key"), cleanup);
1969 }
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001970 break;
1971 default:
1972 LOGINT(LYD_CTX(src_diff));
1973 ret = LY_EINT;
1974 goto cleanup;
1975 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001976 break;
Michal Vasko0f5c6a52020-11-06 17:18:03 +01001977 case LYD_DIFF_OP_NONE:
1978 switch (elem->schema->nodetype) {
1979 case LYS_LEAF:
1980 case LYS_LEAFLIST:
1981 /* default flag change */
1982 LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup);
1983 break;
1984 default:
1985 /* nothing to do */
1986 break;
1987 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001988 break;
1989 }
Michal Vasko4231fb62020-07-13 13:54:47 +02001990 }
1991
Michal Vasko56daf732020-08-10 10:57:18 +02001992 LYD_TREE_DFS_END(root, elem);
Michal Vasko4231fb62020-07-13 13:54:47 +02001993 }
1994 }
1995
1996cleanup:
1997 if (ret) {
1998 lyd_free_siblings(*diff);
1999 *diff = NULL;
2000 }
2001 return ret;
2002}