/** * @file diff.c * @author Michal Vasko * @brief diff functions * * Copyright (c) 2020 - 2021 CESNET, z.s.p.o. * * This source code is licensed under BSD 3-Clause License (the "License"). * You may not use this file except in compliance with the License. * You may obtain a copy of the License at * * https://opensource.org/licenses/BSD-3-Clause */ #define _GNU_SOURCE /* asprintf, strdup */ #include "diff.h" #include #include #include #include #include #include #include "common.h" #include "compat.h" #include "context.h" #include "log.h" #include "plugins_exts.h" #include "plugins_exts/metadata.h" #include "plugins_types.h" #include "set.h" #include "tree.h" #include "tree_data.h" #include "tree_data_internal.h" #include "tree_edit.h" #include "tree_schema.h" #include "tree_schema_internal.h" #define LOGERR_META(ctx, meta_name, node) \ { \ char *__path = lyd_path(node, LYD_PATH_STD, NULL, 0); \ LOGERR(ctx, LY_EINVAL, "Failed to find metadata \"%s\" for node \"%s\".", meta_name, __path); \ free(__path); \ } #define LOGERR_NOINST(ctx, node) \ { \ char *__path = lyd_path(node, LYD_PATH_STD, NULL, 0); \ LOGERR(ctx, LY_EINVAL, "Failed to find node \"%s\" instance in data.", __path); \ free(__path); \ } #define LOGERR_UNEXPVAL(ctx, node, data_source) \ { \ char *__path = lyd_path(node, LYD_PATH_STD, NULL, 0); \ LOGERR(ctx, LY_EINVAL, "Unexpected value of node \"%s\" in %s.", __path, data_source); \ free(__path); \ } #define LOGERR_MERGEOP(ctx, node, src_op, trg_op) \ { \ char *__path = lyd_path(node, LYD_PATH_STD, NULL, 0); \ LOGERR(ctx, LY_EINVAL, "Unable to merge operation \"%s\" with \"%s\" for node \"%s\".", \ lyd_diff_op2str(trg_op), lyd_diff_op2str(src_op), __path); \ free(__path); \ } static const char * lyd_diff_op2str(enum lyd_diff_op op) { switch (op) { case LYD_DIFF_OP_CREATE: return "create"; case LYD_DIFF_OP_DELETE: return "delete"; case LYD_DIFF_OP_REPLACE: return "replace"; case LYD_DIFF_OP_NONE: return "none"; } LOGINT(NULL); return NULL; } static enum lyd_diff_op lyd_diff_str2op(const char *str) { switch (str[0]) { case 'c': assert(!strcmp(str, "create")); return LYD_DIFF_OP_CREATE; case 'd': assert(!strcmp(str, "delete")); return LYD_DIFF_OP_DELETE; case 'r': assert(!strcmp(str, "replace")); return LYD_DIFF_OP_REPLACE; case 'n': assert(!strcmp(str, "none")); return LYD_DIFF_OP_NONE; } LOGINT(NULL); return 0; } /** * @brief Create diff metadata for a nested user-ordered node with the effective operation "create". * * @param[in] node User-rodered node to update. * @return LY_ERR value. */ static LY_ERR lyd_diff_add_create_nested_userord(struct lyd_node *node) { LY_ERR rc = LY_SUCCESS; const char *meta_name, *meta_val; size_t buflen = 0, bufused = 0; uint32_t pos; char *dyn = NULL; assert(lysc_is_userordered(node->schema)); /* get correct metadata name and value */ if (lysc_is_dup_inst_list(node->schema)) { meta_name = "yang:position"; pos = lyd_list_pos(node); if (asprintf(&dyn, "%" PRIu32, pos) == -1) { LOGMEM(LYD_CTX(node)); rc = LY_EMEM; goto cleanup; } meta_val = dyn; } else if (node->schema->nodetype == LYS_LIST) { meta_name = "yang:key"; if (node->prev->next && (node->prev->schema == node->schema)) { LY_CHECK_GOTO(rc = lyd_path_list_predicate(node->prev, &dyn, &buflen, &bufused, 0), cleanup); meta_val = dyn; } else { meta_val = ""; } } else { meta_name = "yang:value"; if (node->prev->next && (node->prev->schema == node->schema)) { meta_val = lyd_get_value(node->prev); } else { meta_val = ""; } } /* create the metadata */ LY_CHECK_GOTO(rc = lyd_new_meta(NULL, node, NULL, meta_name, meta_val, 0, NULL), cleanup); cleanup: free(dyn); return rc; } LY_ERR lyd_diff_add(const struct lyd_node *node, enum lyd_diff_op op, const char *orig_default, const char *orig_value, const char *key, const char *value, const char *position, const char *orig_key, const char *orig_position, struct lyd_node **diff) { struct lyd_node *dup, *siblings, *match = NULL, *diff_parent = NULL, *elem; const struct lyd_node *parent = NULL; assert(diff); /* replace leaf always needs orig-default and orig-value */ assert((node->schema->nodetype != LYS_LEAF) || (op != LYD_DIFF_OP_REPLACE) || (orig_default && orig_value)); /* create on userord needs key/value */ assert((node->schema->nodetype != LYS_LIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_CREATE) || (lysc_is_dup_inst_list(node->schema) && position) || key); assert((node->schema->nodetype != LYS_LEAFLIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_CREATE) || (lysc_is_dup_inst_list(node->schema) && position) || value); /* move on userord needs both key and orig-key/value and orig-value */ assert((node->schema->nodetype != LYS_LIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_REPLACE) || (lysc_is_dup_inst_list(node->schema) && position && orig_position) || (key && orig_key)); assert((node->schema->nodetype != LYS_LEAFLIST) || !(node->schema->flags & LYS_ORDBY_USER) || (op != LYD_DIFF_OP_REPLACE) || (lysc_is_dup_inst_list(node->schema) && position && orig_position) || (value && orig_value)); /* find the first existing parent */ siblings = *diff; while (1) { /* find next node parent */ parent = node; while (parent->parent && (!diff_parent || (parent->parent->schema != diff_parent->schema))) { parent = lyd_parent(parent); } if (parent == node) { /* no more parents to find */ break; } /* check whether it exists in the diff */ if (lyd_find_sibling_first(siblings, parent, &match)) { break; } /* another parent found */ diff_parent = match; /* move down in the diff */ siblings = lyd_child_no_keys(match); } /* duplicate the subtree (and connect to the diff if possible) */ LY_CHECK_RET(lyd_dup_single(node, (struct lyd_node_inner *)diff_parent, LYD_DUP_RECURSIVE | LYD_DUP_NO_META | LYD_DUP_WITH_PARENTS | LYD_DUP_WITH_FLAGS, &dup)); /* find the first duplicated parent */ if (!diff_parent) { diff_parent = lyd_parent(dup); while (diff_parent && diff_parent->parent) { diff_parent = lyd_parent(diff_parent); } } else { diff_parent = dup; while (diff_parent->parent && (diff_parent->parent->schema == parent->schema)) { diff_parent = lyd_parent(diff_parent); } } /* no parent existed, must be manually connected */ if (!diff_parent) { /* there actually was no parent to duplicate */ lyd_insert_sibling(*diff, dup, diff); } else if (!diff_parent->parent) { lyd_insert_sibling(*diff, diff_parent, diff); } /* add parent operation, if any */ if (diff_parent && (diff_parent != dup)) { LY_CHECK_RET(lyd_new_meta(NULL, diff_parent, NULL, "yang:operation", "none", 0, NULL)); } /* add subtree operation */ LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:operation", lyd_diff_op2str(op), 0, NULL)); if (op == LYD_DIFF_OP_CREATE) { /* all nested user-ordered (leaf-)lists need special metadata for create op */ LYD_TREE_DFS_BEGIN(dup, elem) { if ((elem != dup) && lysc_is_userordered(elem->schema)) { LY_CHECK_RET(lyd_diff_add_create_nested_userord(elem)); } LYD_TREE_DFS_END(dup, elem); } } /* orig-default */ if (orig_default) { LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:orig-default", orig_default, 0, NULL)); } /* orig-value */ if (orig_value) { LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:orig-value", orig_value, 0, NULL)); } /* key */ if (key) { LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:key", key, 0, NULL)); } /* value */ if (value) { LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:value", value, 0, NULL)); } /* position */ if (position) { LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:position", position, 0, NULL)); } /* orig-key */ if (orig_key) { LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:orig-key", orig_key, 0, NULL)); } /* orig-position */ if (orig_position) { LY_CHECK_RET(lyd_new_meta(NULL, dup, NULL, "yang:orig-position", orig_position, 0, NULL)); } return LY_SUCCESS; } /** * @brief Get a userord entry for a specific user-ordered list/leaf-list. Create if does not exist yet. * * @param[in] first Node from the first tree, can be NULL (on create). * @param[in] schema Schema node of the list/leaf-list. * @param[in,out] userord Sized array of userord items. * @return Userord item for all the user-ordered list/leaf-list instances. */ static struct lyd_diff_userord * lyd_diff_userord_get(const struct lyd_node *first, const struct lysc_node *schema, struct lyd_diff_userord **userord) { struct lyd_diff_userord *item; struct lyd_node *iter; const struct lyd_node **node; LY_ARRAY_COUNT_TYPE u; LY_ARRAY_FOR(*userord, u) { if ((*userord)[u].schema == schema) { return &(*userord)[u]; } } /* it was not added yet, add it now */ LY_ARRAY_NEW_RET(schema->module->ctx, *userord, item, NULL); item->schema = schema; item->pos = 0; item->inst = NULL; /* store all the instance pointers in the current order */ if (first) { LYD_LIST_FOR_INST(lyd_first_sibling(first), first->schema, iter) { LY_ARRAY_NEW_RET(schema->module->ctx, item->inst, node, NULL); *node = iter; } } return item; } /** * @brief Get all the metadata to be stored in a diff for the 2 nodes. Can be used only for user-ordered * lists/leaf-lists. * * @param[in] first Node from the first tree, can be NULL (on create). * @param[in] second Node from the second tree, can be NULL (on delete). * @param[in] options Diff options. * @param[in] userord_item Userord item of @p first and/or @p second node. * @param[out] op Operation. * @param[out] orig_default Original default metadata. * @param[out] value Value metadata. * @param[out] orig_value Original value metadata * @param[out] key Key metadata. * @param[out] orig_key Original key metadata. * @param[out] position Position metadata. * @param[out] orig_position Original position metadata. * @return LY_SUCCESS on success, * @return LY_ENOT if there is no change to be added into diff, * @return LY_ERR value on other errors. */ static LY_ERR lyd_diff_userord_attrs(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, struct lyd_diff_userord *userord_item, enum lyd_diff_op *op, const char **orig_default, char **value, char **orig_value, char **key, char **orig_key, char **position, char **orig_position) { LY_ERR rc = LY_SUCCESS; const struct lysc_node *schema; size_t buflen, bufused; uint32_t first_pos, second_pos; assert(first || second); *orig_default = NULL; *value = NULL; *orig_value = NULL; *key = NULL; *orig_key = NULL; *position = NULL; *orig_position = NULL; schema = first ? first->schema : second->schema; assert(lysc_is_userordered(schema)); /* find user-ordered first position */ if (first) { for (first_pos = 0; first_pos < LY_ARRAY_COUNT(userord_item->inst); ++first_pos) { if (userord_item->inst[first_pos] == first) { break; } } assert(first_pos < LY_ARRAY_COUNT(userord_item->inst)); } else { first_pos = 0; } /* prepare position of the next instance */ second_pos = userord_item->pos++; /* learn operation first */ if (!second) { *op = LYD_DIFF_OP_DELETE; } else if (!first) { *op = LYD_DIFF_OP_CREATE; } else { if (lyd_compare_single(second, userord_item->inst[second_pos], 0)) { /* in first, there is a different instance on the second position, we are going to move 'first' node */ *op = LYD_DIFF_OP_REPLACE; } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) { /* default flag change */ *op = LYD_DIFF_OP_NONE; } else { /* no changes */ return LY_ENOT; } } /* * set each attribute correctly based on the operation and node type */ /* orig-default */ if ((schema->nodetype == LYS_LEAFLIST) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))) { if (first->flags & LYD_DEFAULT) { *orig_default = "true"; } else { *orig_default = "false"; } } /* value */ if ((schema->nodetype == LYS_LEAFLIST) && !lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) { if (second_pos) { *value = strdup(lyd_get_value(userord_item->inst[second_pos - 1])); LY_CHECK_ERR_GOTO(!*value, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } else { *value = strdup(""); LY_CHECK_ERR_GOTO(!*value, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } } /* orig-value */ if ((schema->nodetype == LYS_LEAFLIST) && !lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) { if (first_pos) { *orig_value = strdup(lyd_get_value(userord_item->inst[first_pos - 1])); LY_CHECK_ERR_GOTO(!*orig_value, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } else { *orig_value = strdup(""); LY_CHECK_ERR_GOTO(!*orig_value, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } } /* key */ if ((schema->nodetype == LYS_LIST) && !lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) { if (second_pos) { buflen = bufused = 0; LY_CHECK_GOTO(rc = lyd_path_list_predicate(userord_item->inst[second_pos - 1], key, &buflen, &bufused, 0), cleanup); } else { *key = strdup(""); LY_CHECK_ERR_GOTO(!*key, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } } /* orig-key */ if ((schema->nodetype == LYS_LIST) && !lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) { if (first_pos) { buflen = bufused = 0; LY_CHECK_GOTO(rc = lyd_path_list_predicate(userord_item->inst[first_pos - 1], orig_key, &buflen, &bufused, 0), cleanup); } else { *orig_key = strdup(""); LY_CHECK_ERR_GOTO(!*orig_key, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } } /* position */ if (lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_CREATE))) { if (second_pos) { if (asprintf(position, "%" PRIu32, second_pos) == -1) { LOGMEM(schema->module->ctx); rc = LY_EMEM; goto cleanup; } } else { *position = strdup(""); LY_CHECK_ERR_GOTO(!*position, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } } /* orig-position */ if (lysc_is_dup_inst_list(schema) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_DELETE))) { if (first_pos) { if (asprintf(orig_position, "%" PRIu32, first_pos) == -1) { LOGMEM(schema->module->ctx); rc = LY_EMEM; goto cleanup; } } else { *orig_position = strdup(""); LY_CHECK_ERR_GOTO(!*orig_position, LOGMEM(schema->module->ctx); rc = LY_EMEM, cleanup); } } /* * update our instances - apply the change */ if (*op == LYD_DIFF_OP_CREATE) { /* insert the instance */ LY_ARRAY_CREATE_GOTO(schema->module->ctx, userord_item->inst, 1, rc, cleanup); if (second_pos < LY_ARRAY_COUNT(userord_item->inst)) { memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos, (LY_ARRAY_COUNT(userord_item->inst) - second_pos) * sizeof *userord_item->inst); } LY_ARRAY_INCREMENT(userord_item->inst); userord_item->inst[second_pos] = second; } else if (*op == LYD_DIFF_OP_DELETE) { /* remove the instance */ if (first_pos + 1 < LY_ARRAY_COUNT(userord_item->inst)) { memmove(userord_item->inst + first_pos, userord_item->inst + first_pos + 1, (LY_ARRAY_COUNT(userord_item->inst) - first_pos - 1) * sizeof *userord_item->inst); } LY_ARRAY_DECREMENT(userord_item->inst); } else if (*op == LYD_DIFF_OP_REPLACE) { /* move the instances */ memmove(userord_item->inst + second_pos + 1, userord_item->inst + second_pos, (first_pos - second_pos) * sizeof *userord_item->inst); userord_item->inst[second_pos] = first; } cleanup: if (rc) { free(*value); *value = NULL; free(*orig_value); *orig_value = NULL; free(*key); *key = NULL; free(*orig_key); *orig_key = NULL; free(*position); *position = NULL; free(*orig_position); *orig_position = NULL; } return rc; } /** * @brief Get all the metadata to be stored in a diff for the 2 nodes. Cannot be used for user-ordered * lists/leaf-lists. * * @param[in] first Node from the first tree, can be NULL (on create). * @param[in] second Node from the second tree, can be NULL (on delete). * @param[in] options Diff options. * @param[out] op Operation. * @param[out] orig_default Original default metadata. * @param[out] orig_value Original value metadata. * @return LY_SUCCESS on success, * @return LY_ENOT if there is no change to be added into diff, * @return LY_ERR value on other errors. */ static LY_ERR lyd_diff_attrs(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, enum lyd_diff_op *op, const char **orig_default, char **orig_value) { const struct lysc_node *schema; const char *str_val; assert(first || second); *orig_default = NULL; *orig_value = NULL; schema = first ? first->schema : second->schema; assert(!lysc_is_userordered(schema)); /* learn operation first */ if (!second) { *op = LYD_DIFF_OP_DELETE; } else if (!first) { *op = LYD_DIFF_OP_CREATE; } else { switch (schema->nodetype) { case LYS_CONTAINER: case LYS_RPC: case LYS_ACTION: case LYS_NOTIF: /* no changes */ return LY_ENOT; case LYS_LIST: case LYS_LEAFLIST: if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) { /* default flag change */ *op = LYD_DIFF_OP_NONE; } else { /* no changes */ return LY_ENOT; } break; case LYS_LEAF: case LYS_ANYXML: case LYS_ANYDATA: if (lyd_compare_single(first, second, 0)) { /* different values */ *op = LYD_DIFF_OP_REPLACE; } else if ((options & LYD_DIFF_DEFAULTS) && ((first->flags & LYD_DEFAULT) != (second->flags & LYD_DEFAULT))) { /* default flag change */ *op = LYD_DIFF_OP_NONE; } else { /* no changes */ return LY_ENOT; } break; default: LOGINT_RET(schema->module->ctx); } } /* * set each attribute correctly based on the operation and node type */ /* orig-default */ if ((schema->nodetype & LYD_NODE_TERM) && ((*op == LYD_DIFF_OP_REPLACE) || (*op == LYD_DIFF_OP_NONE))) { if (first->flags & LYD_DEFAULT) { *orig_default = "true"; } else { *orig_default = "false"; } } /* orig-value */ if ((schema->nodetype & (LYS_LEAF | LYS_ANYDATA)) && (*op == LYD_DIFF_OP_REPLACE)) { if (schema->nodetype == LYS_LEAF) { str_val = lyd_get_value(first); *orig_value = strdup(str_val ? str_val : ""); LY_CHECK_ERR_RET(!*orig_value, LOGMEM(schema->module->ctx), LY_EMEM); } else { LY_CHECK_RET(lyd_any_value_str(first, orig_value)); } } return LY_SUCCESS; } /** * @brief Find a matching instance of a node in a data tree. * * @param[in] siblings Siblings to search in. * @param[in] target Target node to search for. * @param[in] defaults Whether to consider (or ignore) default values. * @param[in,out] dup_inst_cache Duplicate instance cache. * @param[out] match Found match, NULL if no matching node found. * @return LY_ERR value. */ static LY_ERR lyd_diff_find_match(const struct lyd_node *siblings, const struct lyd_node *target, ly_bool defaults, struct lyd_dup_inst **dup_inst_cache, struct lyd_node **match) { LY_ERR r; if (target->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) { /* try to find the exact instance */ r = lyd_find_sibling_first(siblings, target, match); } else { /* try to simply find the node, there cannot be more instances */ r = lyd_find_sibling_val(siblings, target->schema, NULL, 0, match); } if (r && (r != LY_ENOTFOUND)) { return r; } /* update match as needed */ LY_CHECK_RET(lyd_dup_inst_next(match, siblings, dup_inst_cache)); if (*match && ((*match)->flags & LYD_DEFAULT) && !defaults) { /* ignore default nodes */ *match = NULL; } return LY_SUCCESS; } /** * @brief Perform diff for all siblings at certain depth, recursively. * * For user-ordered lists/leaf-lists a specific structure is used for storing * the current order. The idea is to apply all the generated diff changes * virtually on the first tree so that we can continue to generate correct * changes after some were already generated. * * The algorithm then uses second tree position-based changes with a before * (preceding) item anchor. * * Example: * * Virtual first tree leaf-list order: * 1 2 [3] 4 5 * * Second tree leaf-list order: * 1 2 [5] 3 4 * * We are at the 3rd node now. We look at whether the nodes on the 3rd position * match - they do not - move nodes so that the 3rd position node is final -> * -> move node 5 to the 3rd position -> move node 5 after node 2. * * Required properties: * Stored operations (move) should not be affected by later operations - * - would cause a redundantly long list of operations, possibly inifinite. * * Implemenation justification: * First, all delete operations and only then move/create operations are stored. * Also, preceding anchor is used and after each iteration another node is * at its final position. That results in the invariant that all preceding * nodes are final and will not be changed by the later operations, meaning * they can safely be used as anchors for the later operations. * * @param[in] first First tree first sibling. * @param[in] second Second tree first sibling. * @param[in] options Diff options. * @param[in] nosiblings Whether to skip following siblings. * @param[in,out] diff Diff to append to. * @return LY_ERR value. */ static LY_ERR lyd_diff_siblings_r(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, ly_bool nosiblings, struct lyd_node **diff) { LY_ERR ret = LY_SUCCESS; const struct lyd_node *iter_first, *iter_second; struct lyd_node *match_second, *match_first; struct lyd_diff_userord *userord = NULL, *userord_item; struct lyd_dup_inst *dup_inst_first = NULL, *dup_inst_second = NULL; LY_ARRAY_COUNT_TYPE u; enum lyd_diff_op op; const char *orig_default; char *orig_value, *key, *value, *position, *orig_key, *orig_position; /* compare first tree to the second tree - delete, replace, none */ LY_LIST_FOR(first, iter_first) { if (!iter_first->schema) { continue; } assert(!(iter_first->schema->flags & LYS_KEY)); if ((iter_first->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) { /* skip default nodes */ continue; } /* find a match in the second tree */ LY_CHECK_GOTO(ret = lyd_diff_find_match(second, iter_first, options & LYD_DIFF_DEFAULTS, &dup_inst_second, &match_second), cleanup); if (lysc_is_userordered(iter_first->schema)) { /* get (create) userord entry */ userord_item = lyd_diff_userord_get(iter_first, iter_first->schema, &userord); LY_CHECK_ERR_GOTO(!userord_item, LOGMEM(LYD_CTX(iter_first)); ret = LY_EMEM, cleanup); /* we are handling only user-ordered node delete now */ if (!match_second) { /* get all the attributes */ LY_CHECK_GOTO(ret = lyd_diff_userord_attrs(iter_first, match_second, options, userord_item, &op, &orig_default, &value, &orig_value, &key, &orig_key, &position, &orig_position), cleanup); /* there must be changes, it is deleted */ assert(op == LYD_DIFF_OP_DELETE); ret = lyd_diff_add(iter_first, op, orig_default, orig_value, key, value, position, orig_key, orig_position, diff); free(orig_value); free(key); free(value); free(position); free(orig_key); free(orig_position); LY_CHECK_GOTO(ret, cleanup); } } else { /* get all the attributes */ ret = lyd_diff_attrs(iter_first, match_second, options, &op, &orig_default, &orig_value); /* add into diff if there are any changes */ if (!ret) { if (op == LYD_DIFF_OP_DELETE) { ret = lyd_diff_add(iter_first, op, orig_default, orig_value, NULL, NULL, NULL, NULL, NULL, diff); } else { assert(match_second); ret = lyd_diff_add(match_second, op, orig_default, orig_value, NULL, NULL, NULL, NULL, NULL, diff); } free(orig_value); LY_CHECK_GOTO(ret, cleanup); } else if (ret == LY_ENOT) { ret = LY_SUCCESS; } else { goto cleanup; } } /* check descendants, if any, recursively */ if (match_second) { LY_CHECK_GOTO(ret = lyd_diff_siblings_r(lyd_child_no_keys(iter_first), lyd_child_no_keys(match_second), options, 0, diff), cleanup); } if (nosiblings) { break; } } /* reset all cached positions */ LY_ARRAY_FOR(userord, u) { userord[u].pos = 0; } /* compare second tree to the first tree - create, user-ordered move */ LY_LIST_FOR(second, iter_second) { if (!iter_second->schema) { continue; } assert(!(iter_second->schema->flags & LYS_KEY)); if ((iter_second->flags & LYD_DEFAULT) && !(options & LYD_DIFF_DEFAULTS)) { /* skip default nodes */ continue; } /* find a match in the first tree */ LY_CHECK_GOTO(ret = lyd_diff_find_match(first, iter_second, options & LYD_DIFF_DEFAULTS, &dup_inst_first, &match_first), cleanup); if (lysc_is_userordered(iter_second->schema)) { /* get userord entry */ userord_item = lyd_diff_userord_get(match_first, iter_second->schema, &userord); LY_CHECK_ERR_GOTO(!userord_item, LOGMEM(LYD_CTX(iter_second)); ret = LY_EMEM, cleanup); /* get all the attributes */ ret = lyd_diff_userord_attrs(match_first, iter_second, options, userord_item, &op, &orig_default, &value, &orig_value, &key, &orig_key, &position, &orig_position); /* add into diff if there are any changes */ if (!ret) { ret = lyd_diff_add(iter_second, op, orig_default, orig_value, key, value, position, orig_key, orig_position, diff); free(orig_value); free(key); free(value); free(position); free(orig_key); free(orig_position); LY_CHECK_GOTO(ret, cleanup); } else if (ret == LY_ENOT) { ret = LY_SUCCESS; } else { goto cleanup; } } else if (!match_first) { /* get all the attributes */ LY_CHECK_GOTO(ret = lyd_diff_attrs(match_first, iter_second, options, &op, &orig_default, &orig_value), cleanup); /* there must be changes, it is created */ assert(op == LYD_DIFF_OP_CREATE); ret = lyd_diff_add(iter_second, op, orig_default, orig_value, NULL, NULL, NULL, NULL, NULL, diff); free(orig_value); LY_CHECK_GOTO(ret, cleanup); } /* else was handled */ if (nosiblings) { break; } } cleanup: lyd_dup_inst_free(dup_inst_first); lyd_dup_inst_free(dup_inst_second); LY_ARRAY_FOR(userord, u) { LY_ARRAY_FREE(userord[u].inst); } LY_ARRAY_FREE(userord); return ret; } static LY_ERR lyd_diff(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, ly_bool nosiblings, struct lyd_node **diff) { const struct ly_ctx *ctx; LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL); if (first) { ctx = LYD_CTX(first); } else if (second) { ctx = LYD_CTX(second); } else { ctx = NULL; } if (first && second && (lysc_data_parent(first->schema) != lysc_data_parent(second->schema))) { LOGERR(ctx, LY_EINVAL, "Invalid arguments - cannot create diff for unrelated data (%s()).", __func__); return LY_EINVAL; } *diff = NULL; return lyd_diff_siblings_r(first, second, options, nosiblings, diff); } LIBYANG_API_DEF LY_ERR lyd_diff_tree(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, struct lyd_node **diff) { return lyd_diff(first, second, options, 1, diff); } LIBYANG_API_DEF LY_ERR lyd_diff_siblings(const struct lyd_node *first, const struct lyd_node *second, uint16_t options, struct lyd_node **diff) { return lyd_diff(first, second, options, 0, diff); } /** * @brief Learn operation of a diff node. * * @param[in] diff_node Diff node. * @param[out] op Operation. * @return LY_ERR value. */ static LY_ERR lyd_diff_get_op(const struct lyd_node *diff_node, enum lyd_diff_op *op) { struct lyd_meta *meta = NULL; const struct lyd_node *diff_parent; const char *str; char *path; for (diff_parent = diff_node; diff_parent; diff_parent = lyd_parent(diff_parent)) { LY_LIST_FOR(diff_parent->meta, meta) { if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) { str = lyd_get_meta_value(meta); if ((str[0] == 'r') && (diff_parent != diff_node)) { /* we do not care about this operation if it's in our parent */ continue; } *op = lyd_diff_str2op(str); break; } } if (meta) { break; } } if (!meta) { path = lyd_path(diff_node, LYD_PATH_STD, NULL, 0); LOGERR(LYD_CTX(diff_node), LY_EINVAL, "Node \"%s\" without an operation.", path); free(path); return LY_EINT; } return LY_SUCCESS; } /** * @brief Insert a diff node into a data tree. * * @param[in,out] first_node First sibling of the data tree. * @param[in] parent_node Data tree sibling parent node. * @param[in] new_node Node to insert. * @param[in] userord_anchor Optional anchor (key, value, or position) of relative (leaf-)list instance. If not set, * the user-ordered instance will be inserted at the first position. * @return err_info, NULL on success. */ static LY_ERR lyd_diff_insert(struct lyd_node **first_node, struct lyd_node *parent_node, struct lyd_node *new_node, const char *userord_anchor) { LY_ERR ret; struct lyd_node *anchor; uint32_t pos, anchor_pos; int found; assert(new_node); if (!*first_node) { if (!parent_node) { /* no parent or siblings */ *first_node = new_node; return LY_SUCCESS; } /* simply insert into parent, no other children */ if (userord_anchor) { LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.", new_node->schema->name); return LY_EINVAL; } return lyd_insert_child(parent_node, new_node); } assert(!(*first_node)->parent || (lyd_parent(*first_node) == parent_node)); if (!lysc_is_userordered(new_node->schema)) { /* simple insert */ return lyd_insert_sibling(*first_node, new_node, first_node); } if (userord_anchor) { /* find the anchor sibling */ if (lysc_is_dup_inst_list(new_node->schema)) { anchor_pos = atoi(userord_anchor); if (!anchor_pos) { LOGERR(LYD_CTX(new_node), LY_EINVAL, "Invalid user-ordered anchor value \"%s\".", userord_anchor); return LY_EINVAL; } found = 0; pos = 1; LYD_LIST_FOR_INST(*first_node, new_node->schema, anchor) { if (pos == anchor_pos) { found = 1; break; } ++pos; } if (!found) { LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.", new_node->schema->name); return LY_EINVAL; } } else { ret = lyd_find_sibling_val(*first_node, new_node->schema, userord_anchor, 0, &anchor); if (ret == LY_ENOTFOUND) { LOGERR(LYD_CTX(new_node), LY_EINVAL, "Node \"%s\" instance to insert next to not found.", new_node->schema->name); return LY_EINVAL; } else if (ret) { return ret; } } /* insert after */ LY_CHECK_RET(lyd_insert_after(anchor, new_node)); assert(new_node->prev == anchor); if (*first_node == new_node) { *first_node = anchor; } } else { /* find the first instance */ ret = lyd_find_sibling_val(*first_node, new_node->schema, NULL, 0, &anchor); LY_CHECK_RET(ret && (ret != LY_ENOTFOUND), ret); if (anchor) { /* insert before the first instance */ LY_CHECK_RET(lyd_insert_before(anchor, new_node)); if ((*first_node)->prev->next) { assert(!new_node->prev->next); *first_node = new_node; } } else { /* insert anywhere */ LY_CHECK_RET(lyd_insert_sibling(*first_node, new_node, first_node)); } } return LY_SUCCESS; } /** * @brief Apply diff subtree on data tree nodes, recursively. * * @param[in,out] first_node First sibling of the data tree. * @param[in] parent_node Parent of the first sibling. * @param[in] diff_node Current diff node. * @param[in] diff_cb Optional diff callback. * @param[in] cb_data User data for @p diff_cb. * @param[in,out] dup_inst Duplicate instance cache for all @p diff_node siblings. * @return LY_ERR value. */ static LY_ERR lyd_diff_apply_r(struct lyd_node **first_node, struct lyd_node *parent_node, const struct lyd_node *diff_node, lyd_diff_cb diff_cb, void *cb_data, struct lyd_dup_inst **dup_inst) { LY_ERR ret; struct lyd_node *match, *diff_child; const char *str_val, *meta_str; enum lyd_diff_op op; struct lyd_meta *meta; struct lyd_dup_inst *child_dup_inst = NULL; const struct ly_ctx *ctx = LYD_CTX(diff_node); /* read all the valid attributes */ LY_CHECK_RET(lyd_diff_get_op(diff_node, &op)); /* handle specific user-ordered (leaf-)lists operations separately */ if (lysc_is_userordered(diff_node->schema) && ((op == LYD_DIFF_OP_CREATE) || (op == LYD_DIFF_OP_REPLACE))) { if (op == LYD_DIFF_OP_REPLACE) { /* find the node (we must have some siblings because the node was only moved) */ LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match)); LY_CHECK_ERR_RET(!match, LOGERR_NOINST(ctx, diff_node), LY_EINVAL); } else { /* duplicate the node */ LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match)); } /* get "key", "value", or "position" metadata string value */ if (lysc_is_dup_inst_list(diff_node->schema)) { meta_str = "yang:position"; } else if (diff_node->schema->nodetype == LYS_LIST) { meta_str = "yang:key"; } else { meta_str = "yang:value"; } meta = lyd_find_meta(diff_node->meta, NULL, meta_str); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, meta_str, diff_node), LY_EINVAL); str_val = lyd_get_meta_value(meta); /* insert/move the node */ if (str_val[0]) { ret = lyd_diff_insert(first_node, parent_node, match, str_val); } else { ret = lyd_diff_insert(first_node, parent_node, match, NULL); } if (ret) { if (op == LYD_DIFF_OP_CREATE) { lyd_free_tree(match); } return ret; } goto next_iter_r; } /* apply operation */ switch (op) { case LYD_DIFF_OP_NONE: /* find the node */ LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match)); LY_CHECK_ERR_RET(!match, LOGERR_NOINST(ctx, diff_node), LY_EINVAL); if (match->schema->nodetype & LYD_NODE_TERM) { /* special case of only dflt flag change */ if (diff_node->flags & LYD_DEFAULT) { match->flags |= LYD_DEFAULT; } else { match->flags &= ~LYD_DEFAULT; } } else { /* none operation on nodes without children is redundant and hence forbidden */ if (!lyd_child_no_keys(diff_node)) { LOGERR(ctx, LY_EINVAL, "Operation \"none\" is invalid for node \"%s\" without children.", LYD_NAME(diff_node)); return LY_EINVAL; } } break; case LYD_DIFF_OP_CREATE: /* duplicate the node */ LY_CHECK_RET(lyd_dup_single(diff_node, NULL, LYD_DUP_NO_META, &match)); /* insert it at the end */ ret = 0; if (parent_node) { if (match->flags & LYD_EXT) { ret = lyplg_ext_insert(parent_node, match); } else { ret = lyd_insert_child(parent_node, match); } } else { ret = lyd_insert_sibling(*first_node, match, first_node); } if (ret) { lyd_free_tree(match); return ret; } break; case LYD_DIFF_OP_DELETE: /* find the node */ LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match)); LY_CHECK_ERR_RET(!match, LOGERR_NOINST(ctx, diff_node), LY_EINVAL); /* remove it */ if ((match == *first_node) && !match->parent) { assert(!parent_node); /* we have removed the top-level node */ *first_node = (*first_node)->next; } lyd_free_tree(match); /* we are not going recursively in this case, the whole subtree was already deleted */ return LY_SUCCESS; case LYD_DIFF_OP_REPLACE: if (!(diff_node->schema->nodetype & (LYS_LEAF | LYS_ANYDATA))) { LOGERR(ctx, LY_EINVAL, "Operation \"replace\" is invalid for %s node \"%s\".", lys_nodetype2str(diff_node->schema->nodetype), LYD_NAME(diff_node)); return LY_EINVAL; } /* find the node */ LY_CHECK_RET(lyd_diff_find_match(*first_node, diff_node, 1, dup_inst, &match)); LY_CHECK_ERR_RET(!match, LOGERR_NOINST(ctx, diff_node), LY_EINVAL); /* update the value */ if (diff_node->schema->nodetype == LYS_LEAF) { ret = lyd_change_term(match, lyd_get_value(diff_node)); LY_CHECK_ERR_RET(ret && (ret != LY_EEXIST), LOGERR_UNEXPVAL(ctx, match, "data"), LY_EINVAL); } else { struct lyd_node_any *any = (struct lyd_node_any *)diff_node; LY_CHECK_RET(lyd_any_copy_value(match, &any->value, any->value_type)); } /* with flags */ match->flags = diff_node->flags; break; default: LOGINT_RET(ctx); } next_iter_r: if (diff_cb) { /* call callback */ LY_CHECK_RET(diff_cb(diff_node, match, cb_data)); } /* apply diff recursively */ ret = LY_SUCCESS; LY_LIST_FOR(lyd_child_no_keys(diff_node), diff_child) { ret = lyd_diff_apply_r(lyd_node_child_p(match), match, diff_child, diff_cb, cb_data, &child_dup_inst); if (ret) { break; } } lyd_dup_inst_free(child_dup_inst); return ret; } LIBYANG_API_DEF LY_ERR lyd_diff_apply_module(struct lyd_node **data, const struct lyd_node *diff, const struct lys_module *mod, lyd_diff_cb diff_cb, void *cb_data) { const struct lyd_node *root; struct lyd_dup_inst *dup_inst = NULL; LY_ERR ret = LY_SUCCESS; LY_LIST_FOR(diff, root) { if (mod && (lyd_owner_module(root) != mod)) { /* skip data nodes from different modules */ continue; } /* apply relevant nodes from the diff datatree */ ret = lyd_diff_apply_r(data, NULL, root, diff_cb, cb_data, &dup_inst); if (ret) { break; } } lyd_dup_inst_free(dup_inst); return ret; } LIBYANG_API_DEF LY_ERR lyd_diff_apply_all(struct lyd_node **data, const struct lyd_node *diff) { return lyd_diff_apply_module(data, diff, NULL, NULL, NULL); } /** * @brief Update operations on a diff node when the new operation is NONE. * * @param[in] diff_match Node from the diff. * @param[in] cur_op Current operation of @p diff_match. * @param[in] src_diff Current source diff node. * @return LY_ERR value. */ static LY_ERR lyd_diff_merge_none(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff) { switch (cur_op) { case LYD_DIFF_OP_NONE: case LYD_DIFF_OP_CREATE: case LYD_DIFF_OP_REPLACE: if (src_diff->schema->nodetype & LYD_NODE_TERM) { /* NONE on a term means only its dflt flag was changed */ diff_match->flags &= ~LYD_DEFAULT; diff_match->flags |= src_diff->flags & LYD_DEFAULT; } break; default: /* delete operation is not valid */ LOGERR_MERGEOP(LYD_CTX(diff_match), diff_match, cur_op, LYD_DIFF_OP_NONE); return LY_EINVAL; } return LY_SUCCESS; } /** * @brief Remove an attribute from a node. * * @param[in] node Node with the metadata. * @param[in] name Metadata name. */ static void lyd_diff_del_meta(struct lyd_node *node, const char *name) { struct lyd_meta *meta; LY_LIST_FOR(node->meta, meta) { if (!strcmp(meta->name, name) && !strcmp(meta->annotation->module->name, "yang")) { lyd_free_meta_single(meta); return; } } assert(0); } /** * @brief Set a specific operation of a node. Delete the previous operation, if any. * Does not change the default flag. * * @param[in] node Node to change. * @param[in] op Operation to set. * @return LY_ERR value. */ static LY_ERR lyd_diff_change_op(struct lyd_node *node, enum lyd_diff_op op) { struct lyd_meta *meta; LY_LIST_FOR(node->meta, meta) { if (!strcmp(meta->name, "operation") && !strcmp(meta->annotation->module->name, "yang")) { lyd_free_meta_single(meta); break; } } return lyd_new_meta(LYD_CTX(node), node, NULL, "yang:operation", lyd_diff_op2str(op), 0, NULL); } /** * @brief Update operations on a diff node when the new operation is REPLACE. * * @param[in] diff_match Node from the diff. * @param[in] cur_op Current operation of @p diff_match. * @param[in] src_diff Current source diff node. * @return LY_ERR value. */ static LY_ERR lyd_diff_merge_replace(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff) { LY_ERR ret; const char *str_val, *meta_name, *orig_meta_name; struct lyd_meta *meta; const struct lys_module *mod; const struct lyd_node_any *any; const struct ly_ctx *ctx = LYD_CTX(diff_match); /* get "yang" module for the metadata */ mod = ly_ctx_get_module_latest(LYD_CTX(diff_match), "yang"); assert(mod); switch (cur_op) { case LYD_DIFF_OP_REPLACE: case LYD_DIFF_OP_CREATE: switch (diff_match->schema->nodetype) { case LYS_LIST: case LYS_LEAFLIST: /* it was created/moved somewhere, but now it will be created/moved somewhere else, * keep orig_key/orig_value (only replace oper) and replace key/value */ assert(lysc_is_userordered(diff_match->schema)); if (lysc_is_dup_inst_list(diff_match->schema)) { meta_name = "position"; } else if (diff_match->schema->nodetype == LYS_LIST) { meta_name = "key"; } else { meta_name = "value"; } lyd_diff_del_meta(diff_match, meta_name); meta = lyd_find_meta(src_diff->meta, mod, meta_name); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, meta_name, src_diff), LY_EINVAL); LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL)); break; case LYS_LEAF: /* replaced with the exact same value, impossible */ if (!lyd_compare_single(diff_match, src_diff, 0)) { LOGERR_UNEXPVAL(ctx, diff_match, "target diff"); return LY_EINVAL; } /* modify the node value */ if (lyd_change_term(diff_match, lyd_get_value(src_diff))) { LOGINT_RET(LYD_CTX(src_diff)); } if (cur_op == LYD_DIFF_OP_REPLACE) { /* compare values whether there is any change at all */ meta = lyd_find_meta(diff_match->meta, mod, "orig-value"); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, "orig-value", diff_match), LY_EINVAL); str_val = lyd_get_meta_value(meta); ret = lyd_value_compare((struct lyd_node_term *)diff_match, str_val, strlen(str_val)); if (!ret) { /* values are the same, remove orig-value meta and set oper to NONE */ lyd_free_meta_single(meta); LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE)); } } /* modify the default flag */ diff_match->flags &= ~LYD_DEFAULT; diff_match->flags |= src_diff->flags & LYD_DEFAULT; break; case LYS_ANYXML: case LYS_ANYDATA: if (!lyd_compare_single(diff_match, src_diff, 0)) { LOGERR_UNEXPVAL(ctx, diff_match, "target diff"); return LY_EINVAL; } /* modify the node value */ any = (struct lyd_node_any *)src_diff; LY_CHECK_RET(lyd_any_copy_value(diff_match, &any->value, any->value_type)); break; default: LOGINT_RET(LYD_CTX(src_diff)); } break; case LYD_DIFF_OP_NONE: /* it is moved now */ assert(lysc_is_userordered(diff_match->schema) && (diff_match->schema->nodetype == LYS_LIST)); /* change the operation */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE)); /* set orig-meta and meta */ if (lysc_is_dup_inst_list(diff_match->schema)) { meta_name = "position"; orig_meta_name = "orig-position"; } else { meta_name = "key"; orig_meta_name = "orig-key"; } meta = lyd_find_meta(src_diff->meta, mod, orig_meta_name); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, orig_meta_name, src_diff), LY_EINVAL); LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL)); meta = lyd_find_meta(src_diff->meta, mod, meta_name); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, meta_name, src_diff), LY_EINVAL); LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL)); break; default: /* delete operation is not valid */ LOGERR_MERGEOP(ctx, diff_match, cur_op, LYD_DIFF_OP_REPLACE); return LY_EINVAL; } return LY_SUCCESS; } /** * @brief Update operations in a diff node when the new operation is CREATE. * * @param[in] diff_match Node from the diff. * @param[in] cur_op Current operation of @p diff_match. * @param[in] src_diff Current source diff node. * @param[in] options Diff merge options. * @return LY_ERR value. */ static LY_ERR lyd_diff_merge_create(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff, uint16_t options) { struct lyd_node *child; const struct lysc_node_leaf *sleaf = NULL; uint32_t trg_flags; const char *meta_name, *orig_meta_name; struct lyd_meta *meta, *orig_meta; const struct ly_ctx *ctx = LYD_CTX(diff_match); switch (cur_op) { case LYD_DIFF_OP_DELETE: /* remember current flags */ trg_flags = diff_match->flags; if (lysc_is_userordered(diff_match->schema)) { /* get anchor metadata */ if (lysc_is_dup_inst_list(diff_match->schema)) { meta_name = "yang:position"; orig_meta_name = "yang:orig-position"; } else if (diff_match->schema->nodetype == LYS_LIST) { meta_name = "yang:key"; orig_meta_name = "yang:orig-key"; } else { meta_name = "yang:value"; orig_meta_name = "yang:orig-value"; } meta = lyd_find_meta(src_diff->meta, NULL, meta_name); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, meta_name, src_diff), LY_EINVAL); orig_meta = lyd_find_meta(diff_match->meta, NULL, orig_meta_name); LY_CHECK_ERR_RET(!orig_meta, LOGERR_META(ctx, orig_meta_name, diff_match), LY_EINVAL); /* the (incorrect) assumption made here is that there are no previous diff nodes that would affect * the anchors stored in the metadata */ if (strcmp(lyd_get_meta_value(meta), lyd_get_meta_value(orig_meta))) { /* deleted + created at another position -> operation REPLACE */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE)); /* add anchor metadata */ LY_CHECK_RET(lyd_dup_meta_single(meta, diff_match, NULL)); } else { /* deleted + created at the same position -> operation NONE */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE)); /* delete anchor metadata */ lyd_free_meta_single(orig_meta); } } else if (diff_match->schema->nodetype == LYS_LEAF) { if (options & LYD_DIFF_MERGE_DEFAULTS) { /* we are dealing with a leaf and are handling default values specially (as explicit nodes) */ sleaf = (struct lysc_node_leaf *)diff_match->schema; } if (sleaf && sleaf->dflt && !sleaf->dflt->realtype->plugin->compare(sleaf->dflt, &((struct lyd_node_term *)src_diff)->value)) { /* we deleted it, so a default value was in-use, and it matches the created value -> operation NONE */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE)); } else if (!lyd_compare_single(diff_match, src_diff, 0)) { /* deleted + created -> operation NONE */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE)); } else { /* we deleted it, but it was created with a different value -> operation REPLACE */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_REPLACE)); /* current value is the previous one (meta) */ LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-value", lyd_get_value(diff_match), 0, NULL)); /* update the value itself */ LY_CHECK_RET(lyd_change_term(diff_match, lyd_get_value(src_diff))); } } else { /* deleted + created -> operation NONE */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE)); } if (diff_match->schema->nodetype & LYD_NODE_TERM) { /* add orig-dflt metadata */ LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-default", trg_flags & LYD_DEFAULT ? "true" : "false", 0, NULL)); /* update dflt flag itself */ diff_match->flags &= ~LYD_DEFAULT; diff_match->flags |= src_diff->flags & LYD_DEFAULT; } /* but the operation of its children should remain DELETE */ LY_LIST_FOR(lyd_child_no_keys(diff_match), child) { LY_CHECK_RET(lyd_diff_change_op(child, LYD_DIFF_OP_DELETE)); } break; default: /* create and replace operations are not valid */ LOGERR_MERGEOP(LYD_CTX(src_diff), diff_match, cur_op, LYD_DIFF_OP_CREATE); return LY_EINVAL; } return LY_SUCCESS; } /** * @brief Update operations on a diff node when the new operation is DELETE. * * @param[in] diff_match Node from the diff. * @param[in] cur_op Current operation of @p diff_match. * @param[in] src_diff Current source diff node. * @return LY_ERR value. */ static LY_ERR lyd_diff_merge_delete(struct lyd_node *diff_match, enum lyd_diff_op cur_op, const struct lyd_node *src_diff) { struct lyd_node *child; struct lyd_meta *meta; const char *meta_name; const struct ly_ctx *ctx = LYD_CTX(diff_match); /* we can delete only exact existing nodes */ LY_CHECK_ERR_RET(lyd_compare_single(diff_match, src_diff, 0), LOGINT(LYD_CTX(src_diff)), LY_EINT); switch (cur_op) { case LYD_DIFF_OP_CREATE: /* it was created, but then deleted -> set NONE operation */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_NONE)); if (diff_match->schema->nodetype & LYD_NODE_TERM) { /* add orig-default meta because it is expected */ LY_CHECK_RET(lyd_new_meta(LYD_CTX(src_diff), diff_match, NULL, "yang:orig-default", diff_match->flags & LYD_DEFAULT ? "true" : "false", 0, NULL)); } else if (!lysc_is_dup_inst_list(diff_match->schema)) { /* keep operation for all descendants (for now) */ LY_LIST_FOR(lyd_child_no_keys(diff_match), child) { LY_CHECK_RET(lyd_diff_change_op(child, cur_op)); } } /* else key-less list, for which all the descendants act as keys */ break; case LYD_DIFF_OP_REPLACE: /* remove the redundant metadata */ if (lysc_is_userordered(diff_match->schema)) { if (lysc_is_dup_inst_list(diff_match->schema)) { meta_name = "position"; } else if (diff_match->schema->nodetype == LYS_LIST) { meta_name = "key"; } else { meta_name = "value"; } } else { assert(diff_match->schema->nodetype == LYS_LEAF); /* switch value for the original one */ meta = lyd_find_meta(diff_match->meta, NULL, "yang:orig-value"); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, "yang:orig-value", diff_match), LY_EINVAL); if (lyd_change_term(diff_match, lyd_get_meta_value(meta))) { LOGERR_UNEXPVAL(ctx, diff_match, "target diff"); return LY_EINVAL; } /* switch default for the original one, then remove the meta */ meta = lyd_find_meta(diff_match->meta, NULL, "yang:orig-default"); LY_CHECK_ERR_RET(!meta, LOGERR_META(ctx, "yang:orig-default", diff_match), LY_EINVAL); diff_match->flags &= ~LYD_DEFAULT; if (meta->value.boolean) { diff_match->flags |= LYD_DEFAULT; } lyd_free_meta_single(meta); meta_name = "orig-value"; } lyd_diff_del_meta(diff_match, meta_name); /* it was being changed, but should be deleted instead -> set DELETE operation */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_DELETE)); break; case LYD_DIFF_OP_NONE: /* it was not modified, but should be deleted -> set DELETE operation */ LY_CHECK_RET(lyd_diff_change_op(diff_match, LYD_DIFF_OP_DELETE)); break; default: /* delete operation is not valid */ LOGERR_MERGEOP(LYD_CTX(diff_match), diff_match, cur_op, LYD_DIFF_OP_DELETE); return LY_EINVAL; } return LY_SUCCESS; } /** * @brief Check whether this diff node is redundant (does not change data). * * @param[in] diff Diff node. * @return 0 if not, non-zero if it is. */ static int lyd_diff_is_redundant(struct lyd_node *diff) { enum lyd_diff_op op; struct lyd_meta *meta, *orig_val_meta = NULL, *val_meta = NULL; struct lyd_node *child; const struct lys_module *mod; const char *str, *orig_meta_name, *meta_name; assert(diff); if (lysc_is_dup_inst_list(diff->schema)) { /* all descendants are keys */ child = NULL; } else { child = lyd_child_no_keys(diff); } mod = ly_ctx_get_module_latest(LYD_CTX(diff), "yang"); assert(mod); /* get node operation */ LY_CHECK_RET(lyd_diff_get_op(diff, &op), 0); if ((op == LYD_DIFF_OP_REPLACE) && lysc_is_userordered(diff->schema)) { /* get metadata names */ if (lysc_is_dup_inst_list(diff->schema)) { meta_name = "position"; orig_meta_name = "orig-position"; } else if (diff->schema->nodetype == LYS_LIST) { meta_name = "key"; orig_meta_name = "orig-key"; } else { meta_name = "value"; orig_meta_name = "orig-value"; } /* check for redundant move */ orig_val_meta = lyd_find_meta(diff->meta, mod, orig_meta_name); val_meta = lyd_find_meta(diff->meta, mod, meta_name); assert(orig_val_meta && val_meta); if (!lyd_compare_meta(orig_val_meta, val_meta)) { /* there is actually no move */ lyd_free_meta_single(orig_val_meta); lyd_free_meta_single(val_meta); if (child) { /* change operation to NONE, we have siblings */ lyd_diff_change_op(diff, LYD_DIFF_OP_NONE); return 0; } /* redundant node, BUT !! * In diff the move operation is always converted to be INSERT_AFTER, which is fine * because the data that this is applied on should not change for the diff lifetime. * However, when we are merging 2 diffs, this conversion is actually lossy because * if the data change, the move operation can also change its meaning. In this specific * case the move operation will be lost. But it can be considered a feature, it is not supported. */ return 1; } } else if ((op == LYD_DIFF_OP_NONE) && (diff->schema->nodetype & LYD_NODE_TERM)) { /* check whether at least the default flags are different */ meta = lyd_find_meta(diff->meta, mod, "orig-default"); assert(meta); str = lyd_get_meta_value(meta); /* if previous and current dflt flags are the same, this node is redundant */ if ((!strcmp(str, "true") && (diff->flags & LYD_DEFAULT)) || (!strcmp(str, "false") && !(diff->flags & LYD_DEFAULT))) { return 1; } return 0; } if (!child && (op == LYD_DIFF_OP_NONE)) { return 1; } return 0; } /** * @brief Merge sysrepo diff subtree with another diff, recursively. * * @param[in] src_diff Source diff node. * @param[in] diff_parent Current sysrepo diff parent. * @param[in] diff_cb Optional diff callback. * @param[in] cb_data User data for @p diff_cb. * @param[in,out] dup_inst Duplicate instance cache for all @p src_diff siblings. * @param[in] options Diff merge options. * @param[in,out] diff Diff root node. * @return LY_ERR value. */ static LY_ERR lyd_diff_merge_r(const struct lyd_node *src_diff, struct lyd_node *diff_parent, lyd_diff_cb diff_cb, void *cb_data, struct lyd_dup_inst **dup_inst, uint16_t options, struct lyd_node **diff) { LY_ERR ret = LY_SUCCESS; struct lyd_node *child, *diff_node = NULL; enum lyd_diff_op src_op, cur_op; struct lyd_dup_inst *child_dup_inst = NULL; /* get source node operation */ LY_CHECK_RET(lyd_diff_get_op(src_diff, &src_op)); /* find an equal node in the current diff */ LY_CHECK_RET(lyd_diff_find_match(diff_parent ? lyd_child_no_keys(diff_parent) : *diff, src_diff, 1, dup_inst, &diff_node)); if (diff_node) { /* get target (current) operation */ LY_CHECK_RET(lyd_diff_get_op(diff_node, &cur_op)); /* merge operations */ switch (src_op) { case LYD_DIFF_OP_REPLACE: ret = lyd_diff_merge_replace(diff_node, cur_op, src_diff); break; case LYD_DIFF_OP_CREATE: if ((cur_op == LYD_DIFF_OP_CREATE) && lysc_is_dup_inst_list(diff_node->schema)) { /* special case of creating duplicate (leaf-)list instances */ goto add_diff; } ret = lyd_diff_merge_create(diff_node, cur_op, src_diff, options); break; case LYD_DIFF_OP_DELETE: ret = lyd_diff_merge_delete(diff_node, cur_op, src_diff); break; case LYD_DIFF_OP_NONE: /* key-less list can never have "none" operation since all its descendants are acting as "keys" */ assert((src_diff->schema->nodetype != LYS_LIST) || !lysc_is_dup_inst_list(src_diff->schema)); ret = lyd_diff_merge_none(diff_node, cur_op, src_diff); break; default: LOGINT_RET(LYD_CTX(src_diff)); } if (ret) { LOGERR(LYD_CTX(src_diff), LY_EOTHER, "Merging operation \"%s\" failed.", lyd_diff_op2str(src_op)); return ret; } if (diff_cb) { /* call callback */ LY_CHECK_RET(diff_cb(src_diff, diff_node, cb_data)); } /* update diff parent */ diff_parent = diff_node; /* for diff purposes, all key-less list descendants actually act as keys (identifying the same instances), * so there is nothing to merge for these "keys" */ if (!lysc_is_dup_inst_list(src_diff->schema)) { /* merge src_diff recursively */ LY_LIST_FOR(lyd_child_no_keys(src_diff), child) { ret = lyd_diff_merge_r(child, diff_parent, diff_cb, cb_data, &child_dup_inst, options, diff); if (ret) { break; } } lyd_dup_inst_free(child_dup_inst); LY_CHECK_RET(ret); } } else { add_diff: /* add new diff node with all descendants */ if ((src_diff->flags & LYD_EXT) && diff_parent) { LY_CHECK_RET(lyd_dup_single_to_ctx(src_diff, LYD_CTX(diff_parent), (struct lyd_node_inner *)diff_parent, LYD_DUP_RECURSIVE | LYD_DUP_WITH_FLAGS, &diff_node)); } else { LY_CHECK_RET(lyd_dup_single(src_diff, (struct lyd_node_inner *)diff_parent, LYD_DUP_RECURSIVE | LYD_DUP_WITH_FLAGS, &diff_node)); } /* insert node into diff if not already */ if (!diff_parent) { lyd_insert_sibling(*diff, diff_node, diff); } /* update operation */ LY_CHECK_RET(lyd_diff_change_op(diff_node, src_op)); if (diff_cb) { /* call callback with no source diff node since it was duplicated and just added */ LY_CHECK_RET(diff_cb(NULL, diff_node, cb_data)); } /* update diff parent */ diff_parent = diff_node; } /* remove any redundant nodes */ if (lyd_diff_is_redundant(diff_parent)) { if (diff_parent == *diff) { *diff = (*diff)->next; } lyd_free_tree(diff_parent); } return LY_SUCCESS; } LIBYANG_API_DEF LY_ERR lyd_diff_merge_module(struct lyd_node **diff, const struct lyd_node *src_diff, const struct lys_module *mod, lyd_diff_cb diff_cb, void *cb_data, uint16_t options) { const struct lyd_node *src_root; struct lyd_dup_inst *dup_inst = NULL; LY_ERR ret = LY_SUCCESS; LY_LIST_FOR(src_diff, src_root) { if (mod && (lyd_owner_module(src_root) != mod)) { /* skip data nodes from different modules */ continue; } /* apply relevant nodes from the diff datatree */ LY_CHECK_GOTO(ret = lyd_diff_merge_r(src_root, NULL, diff_cb, cb_data, &dup_inst, options, diff), cleanup); } cleanup: lyd_dup_inst_free(dup_inst); return ret; } LIBYANG_API_DEF LY_ERR lyd_diff_merge_tree(struct lyd_node **diff_first, struct lyd_node *diff_parent, const struct lyd_node *src_sibling, lyd_diff_cb diff_cb, void *cb_data, uint16_t options) { LY_ERR ret; struct lyd_dup_inst *dup_inst = NULL; if (!src_sibling) { return LY_SUCCESS; } ret = lyd_diff_merge_r(src_sibling, diff_parent, diff_cb, cb_data, &dup_inst, options, diff_first); lyd_dup_inst_free(dup_inst); return ret; } LIBYANG_API_DEF LY_ERR lyd_diff_merge_all(struct lyd_node **diff, const struct lyd_node *src_diff, uint16_t options) { return lyd_diff_merge_module(diff, src_diff, NULL, NULL, NULL, options); } static LY_ERR lyd_diff_reverse_value(struct lyd_node *node, const struct lys_module *mod) { LY_ERR ret = LY_SUCCESS; struct lyd_meta *meta; const char *val1 = NULL; char *val2; uint32_t flags; assert(node->schema->nodetype & (LYS_LEAF | LYS_ANYDATA)); meta = lyd_find_meta(node->meta, mod, "orig-value"); LY_CHECK_ERR_RET(!meta, LOGERR_META(LYD_CTX(node), "orig-value", node), LY_EINVAL); /* orig-value */ val1 = lyd_get_meta_value(meta); /* current value */ if (node->schema->nodetype == LYS_LEAF) { val2 = strdup(lyd_get_value(node)); } else { LY_CHECK_RET(lyd_any_value_str(node, &val2)); } /* switch values, keep default flag */ flags = node->flags; if (node->schema->nodetype == LYS_LEAF) { LY_CHECK_GOTO(ret = lyd_change_term(node, val1), cleanup); } else { union lyd_any_value anyval = {.str = val1}; LY_CHECK_GOTO(ret = lyd_any_copy_value(node, &anyval, LYD_ANYDATA_STRING), cleanup); } node->flags = flags; LY_CHECK_GOTO(ret = lyd_change_meta(meta, val2), cleanup); cleanup: free(val2); return ret; } static LY_ERR lyd_diff_reverse_default(struct lyd_node *node, const struct lys_module *mod) { struct lyd_meta *meta; uint32_t flag1, flag2; meta = lyd_find_meta(node->meta, mod, "orig-default"); LY_CHECK_ERR_RET(!meta, LOGINT(mod->ctx), LY_EINT); /* orig-default */ if (meta->value.boolean) { flag1 = LYD_DEFAULT; } else { flag1 = 0; } /* current default */ flag2 = node->flags & LYD_DEFAULT; if (flag1 == flag2) { /* no default state change so nothing to reverse */ return LY_SUCCESS; } /* switch defaults */ node->flags &= ~LYD_DEFAULT; node->flags |= flag1; LY_CHECK_RET(lyd_change_meta(meta, flag2 ? "true" : "false")); return LY_SUCCESS; } static LY_ERR lyd_diff_reverse_meta(struct lyd_node *node, const struct lys_module *mod, const char *name1, const char *name2) { LY_ERR ret = LY_SUCCESS; struct lyd_meta *meta1, *meta2; const char *val1 = NULL; char *val2 = NULL; meta1 = lyd_find_meta(node->meta, mod, name1); LY_CHECK_ERR_RET(!meta1, LOGERR_META(LYD_CTX(node), name1, node), LY_EINVAL); meta2 = lyd_find_meta(node->meta, mod, name2); LY_CHECK_ERR_RET(!meta2, LOGERR_META(LYD_CTX(node), name2, node), LY_EINVAL); /* value1 */ val1 = lyd_get_meta_value(meta1); /* value2 */ val2 = strdup(lyd_get_meta_value(meta2)); /* switch values */ LY_CHECK_GOTO(ret = lyd_change_meta(meta1, val2), cleanup); LY_CHECK_GOTO(ret = lyd_change_meta(meta2, val1), cleanup); cleanup: free(val2); return ret; } /** * @brief Remove specific operation from all the nodes in a subtree. * * @param[in] diff Diff subtree to process. * @param[in] op Only expected operation. * @return LY_ERR value. */ static LY_ERR lyd_diff_reverse_remove_op_r(struct lyd_node *diff, enum lyd_diff_op op) { struct lyd_node *elem; struct lyd_meta *meta; LYD_TREE_DFS_BEGIN(diff, elem) { meta = lyd_find_meta(elem->meta, NULL, "yang:operation"); if (meta) { LY_CHECK_ERR_RET(lyd_diff_str2op(lyd_get_meta_value(meta)) != op, LOGINT(LYD_CTX(diff)), LY_EINT); lyd_free_meta_single(meta); } LYD_TREE_DFS_END(diff, elem); } return LY_SUCCESS; } LIBYANG_API_DEF LY_ERR lyd_diff_reverse_all(const struct lyd_node *src_diff, struct lyd_node **diff) { LY_ERR ret = LY_SUCCESS; const struct lys_module *mod; struct lyd_node *root, *elem, *iter; enum lyd_diff_op op; LY_CHECK_ARG_RET(NULL, diff, LY_EINVAL); if (!src_diff) { *diff = NULL; return LY_SUCCESS; } /* duplicate diff */ LY_CHECK_RET(lyd_dup_siblings(src_diff, NULL, LYD_DUP_RECURSIVE, diff)); /* find module with metadata needed for later */ mod = ly_ctx_get_module_latest(LYD_CTX(src_diff), "yang"); LY_CHECK_ERR_GOTO(!mod, LOGINT(LYD_CTX(src_diff)); ret = LY_EINT, cleanup); LY_LIST_FOR(*diff, root) { LYD_TREE_DFS_BEGIN(root, elem) { /* skip all keys */ if (!lysc_is_key(elem->schema)) { /* find operation attribute, if any */ LY_CHECK_GOTO(ret = lyd_diff_get_op(elem, &op), cleanup); switch (op) { case LYD_DIFF_OP_CREATE: /* reverse create to delete */ LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_DELETE), cleanup); /* check all the children for the same operation, nothing else is expected */ LY_LIST_FOR(lyd_child(elem), iter) { lyd_diff_reverse_remove_op_r(iter, LYD_DIFF_OP_CREATE); } LYD_TREE_DFS_continue = 1; break; case LYD_DIFF_OP_DELETE: /* reverse delete to create */ LY_CHECK_GOTO(ret = lyd_diff_change_op(elem, LYD_DIFF_OP_CREATE), cleanup); /* check all the children for the same operation, nothing else is expected */ LY_LIST_FOR(lyd_child(elem), iter) { lyd_diff_reverse_remove_op_r(iter, LYD_DIFF_OP_DELETE); } LYD_TREE_DFS_continue = 1; break; case LYD_DIFF_OP_REPLACE: switch (elem->schema->nodetype) { case LYS_LEAF: /* leaf value change */ LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup); LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup); break; case LYS_ANYXML: case LYS_ANYDATA: /* any value change */ LY_CHECK_GOTO(ret = lyd_diff_reverse_value(elem, mod), cleanup); break; case LYS_LEAFLIST: /* leaf-list move */ LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup); if (lysc_is_dup_inst_list(elem->schema)) { LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-position", "position"), cleanup); } else { LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-value", "value"), cleanup); } break; case LYS_LIST: /* list move */ if (lysc_is_dup_inst_list(elem->schema)) { LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-position", "position"), cleanup); } else { LY_CHECK_GOTO(ret = lyd_diff_reverse_meta(elem, mod, "orig-key", "key"), cleanup); } break; default: LOGINT(LYD_CTX(src_diff)); ret = LY_EINT; goto cleanup; } break; case LYD_DIFF_OP_NONE: switch (elem->schema->nodetype) { case LYS_LEAF: case LYS_LEAFLIST: /* default flag change */ LY_CHECK_GOTO(ret = lyd_diff_reverse_default(elem, mod), cleanup); break; default: /* nothing to do */ break; } break; } } LYD_TREE_DFS_END(root, elem); } } cleanup: if (ret) { lyd_free_siblings(*diff); *diff = NULL; } return ret; }