/*
 *
  ***** BEGIN LICENSE BLOCK *****
 
  Copyright (C) 2009-2019 Olof Hagsand
  Copyright (C) 2020-2022 Olof Hagsand and Rubicon Communications, LLC(Netgate)

  This file is part of CLIXON.

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.

  Alternatively, the contents of this file may be used under the terms of
  the GNU General Public License Version 3 or later (the "GPL"),
  in which case the provisions of the GPL are applicable instead
  of those above. If you wish to allow use of your version of this file only
  under the terms of the GPL, and not to allow others to
  use your version of this file under the terms of Apache License version 2, 
  indicate your decision by deleting the provisions above and replace them with
  the  notice and other provisions required by the GPL. If you do not delete
  the provisions above, a recipient may use your version of this file under
  the terms of any one of the Apache License version 2 or the GPL.

  ***** END LICENSE BLOCK *****

 * Yang functions
 * @see https://tools.ietf.org/html/rfc6020 YANG 1.0
 * @see https://tools.ietf.org/html/rfc7950 YANG 1.1
 *
 * CALLING ORDER OF YANG PARSE FILES
 *                                      yang_spec_parse_module
 *                                     |                       | 
 *                                     v                       v   v
 * yang_spec_parse_file-> yang_parse_post->yang_parse_recurse->yang_parse_module
 *                    \   /                                         v
 * yang_spec_load_dir ------------------------------------> yang_parse_filename
 *                                                                 v  
 *                                                          yang_parse_file
 *                                                                 v  
 *                                                          yang_parse_str
 */

#ifdef HAVE_CONFIG_H
#include "clixon_config.h" /* generated by config & autoconf */
#endif

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <limits.h>
#include <ctype.h>
#include <unistd.h>
#include <string.h>
#include <arpa/inet.h>
#include <regex.h>
#include <dirent.h>
#include <sys/types.h>
#include <fcntl.h>
#include <syslog.h>
#include <sys/stat.h>
#include <sys/param.h>
#include <netinet/in.h>
#include <libgen.h>

/* cligen */
#include <cligen/cligen.h>

/* clicon */
#include "clixon_log.h"
#include "clixon_err.h"
#include "clixon_string.h"
#include "clixon_queue.h"
#include "clixon_hash.h"
#include "clixon_handle.h"
#include "clixon_file.h"
#include "clixon_yang.h"
#include "clixon_hash.h"
#include "clixon_xml.h"
#include "clixon_xml_nsctx.h"
#include "clixon_xpath_ctx.h"
#include "clixon_xpath.h"
#include "clixon_yang_module.h"
#include "clixon_plugin.h"
#include "clixon_data.h"
#include "clixon_options.h"
#include "clixon_yang_type.h"
#include "clixon_yang_parse.h"
#include "clixon_yang_cardinality.h"
#include "clixon_plugin.h"
#include "clixon_yang_internal.h"
#include "clixon_yang_sub_parse.h"
#include "clixon_yang_parse_lib.h"

/* Size of json read buffer when reading from file*/
#define BUFLEN 1024

/* Forward */
static int yang_expand_grouping(yang_stmt *yn);

/*! Resolve a grouping name from a module, includes looking in submodules
 */
static yang_stmt *
ys_grouping_module_resolve(yang_stmt *ymod,
                           yang_stmt *yspec,
                           char      *name)
{
    yang_stmt *yinc;
    yang_stmt *ysubm;
    yang_stmt *yrealmod = NULL;
    yang_stmt *ygrouping = NULL;
    char      *submname;

    /* Find grouping from own sub/module */
    if ((ygrouping = yang_find(ymod, Y_GROUPING, name)) != NULL)
        goto done;
    /* Find top-level module */
    if (ys_real_module(ymod, &yrealmod) < 0)
        goto done;
    if (yrealmod == ymod) /* skip if module, continue if submodule */
        goto done;
    /* Find grouping from real module */
    if ((ygrouping = yang_find(yrealmod, Y_GROUPING, name)) != NULL)
        goto done;
    /* Find grouping from sub-modules */
    yinc = NULL;
    while ((yinc = yn_each(yrealmod, yinc)) != NULL){
        if (yang_keyword_get(yinc) != Y_INCLUDE)
            continue;
        submname = yang_argument_get(yinc);                 
        if ((ysubm = yang_find_module_by_name(yspec, submname)) == NULL)
            continue;
        if (ysubm == ymod)
            continue;
        if ((ygrouping = yang_find(ysubm, Y_GROUPING, name)) != NULL)
            break;
    }
 done:
    return ygrouping;
}

/*! Resolve a grouping name from a point in the yang tree 
 * @param[in]  ys         Yang statement of "uses" statement doing the lookup
 * @param[in]  prefix     Prefix of grouping to look for
 * @param[in]  name       Name of grouping to look for
 * @param[out] ygrouping0 A found grouping yang structure as result
 * @retval     0          OK, ygrouping may be NULL
 * @retval    -1          Error, with clicon_err called
 */
static int
ys_grouping_resolve(yang_stmt  *yuses, 
                    char       *prefix, 
                    char       *name,
                    yang_stmt **ygrouping0)
{
    int             retval = -1;
    yang_stmt      *ymod;
    yang_stmt      *ygrouping = NULL;
    yang_stmt      *yp;
    yang_stmt      *ys;
    yang_stmt      *yspec;
    enum rfc_6020   keyw;

    yspec = ys_spec(yuses);
    /* find the grouping associated with argument and expand(?) */
    if (prefix){ /* Go to top and find import that matches */
        if ((ymod = yang_find_module_by_prefix(yuses, prefix)) != NULL)
            ygrouping = ys_grouping_module_resolve(ymod, yspec, name);
    }
    else { 
        ys = yuses;         /* Check upwards in hierarchy for matching groupings */
        while (1){
            if ((yp = yang_parent_get(ys)) == NULL)
                break;
            if ((keyw = yang_keyword_get(yp)) == Y_SPEC)
                break;
            else if (keyw == Y_MODULE || keyw == Y_SUBMODULE){ /* Try submodules */
                ygrouping = ys_grouping_module_resolve(yp, yspec, name);
                break;
            }
            else if ((ygrouping = yang_find(yp, Y_GROUPING, name)) != NULL) /* Here find grouping */
                break;
            ys = (yang_stmt*)yp;            /* Proceed to next level */
        }
    }
    *ygrouping0 = ygrouping;
    retval = 0;
    // done:
    return retval;
}

/*! This is an augment node, augment the original datamodel. 
 *
 * @param[in]  h    Clicon handle
 * @param[in]  ys   The augment statement
 * @see RFC7950 Sec 7.17
 * The target node MUST be either a container, list, choice, case, input,
 * output, or notification node.
 * If the "augment" statement is on the top level the absolute form MUST be 
 * used.
 * All data nodes defined in the "augment" statement are defined as XML
 * elements in the XML namespace of the module where the "augment" is
 * specified.
 * 
 * @note If the augment has a when statement, which is commonplace, the when statement is not copied as 
 * datanodes are, since it should not apply to the target node. Instead it is added as a special "when"
 * struct to the yang statements being inserted.
 */
static int
yang_augment_node(clicon_handle h,
                  yang_stmt    *ys)
{
    int           retval = -1;
    char         *schema_nodeid;
    yang_stmt    *ytarget = NULL;
    yang_stmt    *yc0;
    yang_stmt    *yc;
    yang_stmt    *ymod;
    yang_stmt    *ywhen;
    char         *wxpath = NULL; /* xpath of when statement */
    cvec         *wnsc = NULL;   /* namespace context of when statement */
    enum rfc_6020 targetkey;
    enum rfc_6020 childkey;

    if ((ymod = ys_module(ys)) == NULL){
        clicon_err(OE_YANG, 0, "My yang module not found");
        goto done;
    }
    /* */
    schema_nodeid = yang_argument_get(ys);
    clicon_debug(CLIXON_DBG_DETAIL, "%s %s", __FUNCTION__, schema_nodeid);
    /* Find the target */
    if (yang_abs_schema_nodeid(ys, schema_nodeid, &ytarget) < 0)
        goto done;

    if (ytarget == NULL){
        if (clicon_option_bool(h, "CLICON_YANG_AUGMENT_ACCEPT_BROKEN")){
            /* Log a warning and proceed if augment target not found 
             * This may be necessary with some broken models
             */
            clicon_log(LOG_WARNING, "Warning: Augment failed in module %s: target node %s not found",
                       yang_argument_get(ys_module(ys)),
                       schema_nodeid);
            goto ok;
        }
        else{
            /* Fail with fatal error if augment target not found 
             * This is "correct"
             */
            clicon_err(OE_YANG, 0, "Augment failed in module %s: target node %s not found",
                       yang_argument_get(ys_module(ys)),
                       schema_nodeid);
            goto done; 
        }
    }
    /* The target node MUST be either a container, list, choice, case, input, output, or notification node.
     * which means it is slightly different than a schema-nodeid ? */
    targetkey = yang_keyword_get(ytarget);
    if (targetkey == Y_ANYDATA)
        goto ok;

    /* Find when statement, if present */
    if ((ywhen = yang_find(ys, Y_WHEN, NULL)) != NULL){
        wxpath = yang_argument_get(ywhen);
        if (xml_nsctx_yang(ywhen, &wnsc) < 0)
            goto done;
    }
    /* Extend ytarget with ys' schemanode children */
    yc0 = NULL;
    while ((yc0 = yn_each(ys, yc0)) != NULL) {
        childkey = yang_keyword_get(yc0);
        /* Only shemanodes and extensions */
        if (!yang_schemanode(yc0) && childkey != Y_UNKNOWN) 
            continue;
        switch (targetkey){
        case Y_CONTAINER:
        case Y_LIST:
            /* If the target node is a container or list node, the "action" and
               "notification" statements can be used within the "augment" statement.
            */
            if (childkey != Y_ACTION && childkey != Y_NOTIFICATION && childkey != Y_UNKNOWN &&
                childkey != Y_CONTAINER && childkey != Y_LEAF && childkey != Y_LIST &&
                childkey != Y_LEAF_LIST && childkey != Y_USES && childkey != Y_CHOICE){
                /* Special case if yc0 is disabled by if-feature=false, then it is transformed to ANYDATA
                 */
                if (yang_flag_get(yc0, YANG_FLAG_DISABLED) == 0)
                    clicon_log(LOG_WARNING, "Warning: Augment failed in module %s: node %s of type %s cannot be added to target node %s (see RFC 7950 Sec 17)",
                           yang_argument_get(ys_module(ys)),
                           yang_argument_get(yc0),
                           yang_key2str(childkey),
                           schema_nodeid);
                goto ok;
            }
            break;
        case Y_CASE:
        case Y_INPUT:
        case Y_OUTPUT:
        case Y_NOTIFICATION:
            /* If the target node is a container, list, case, input, output, or
               notification node, the "container", "leaf", "list", "leaf-list",
               "uses", and "choice" statements can be used within the "augment"
               statement. */
            if (childkey != Y_CONTAINER && childkey != Y_LEAF && childkey != Y_LIST && 
                childkey != Y_LEAF_LIST && childkey != Y_USES && childkey != Y_CHOICE &&
                childkey != Y_UNKNOWN){
                clicon_log(LOG_WARNING, "Warning: Augment failed in module %s: node %s %d cannot be added to target node %s",
                           yang_argument_get(ys_module(ys)),
                           yang_key2str(childkey),
                           childkey,
                           schema_nodeid);
                goto ok;
            }
            break;
        case Y_CHOICE:
            /* If the target node is a choice node, the "case" statement or a
               shorthand "case" statement (see Section 7.9.2) can be used within the
               "augment" statement.
               XXX could be more or less anything?
               As a shorthand, the "case" statement can be omitted if the branch
               contains a single "anydata", "anyxml", "choice", "container", "leaf",
               "list", or "leaf-list" statement. 
            */
            if (childkey != Y_CASE && childkey != Y_ANYDATA && childkey != Y_ANYXML &&
                childkey != Y_CHOICE && childkey != Y_CONTAINER && childkey != Y_LEAF &&
                childkey != Y_LIST && childkey != Y_LEAF_LIST){

                clicon_log(LOG_WARNING, "Warning: Augment failed in module %s: node %s %d cannot be added to target node %s",
                           yang_argument_get(ys_module(ys)),
                           yang_key2str(childkey),
                           childkey,
                           schema_nodeid);
                goto ok;
            }
            break;
        default:
            break;
        }

        if ((yc = ys_dup(yc0)) == NULL)
            goto done;
        yc->ys_mymodule = ymod;

        if (yn_insert(ytarget, yc) < 0)
            goto done;
        /* If there is an associated when statement, add a special when struct to the yang 
         * see xml_yang_validate_all
         */
        if (ywhen){
            if (yang_when_xpath_set(yc, wxpath) < 0) 
                goto done;
            if (yang_when_nsc_set(yc, wnsc) < 0) 
                goto done;
        }
        /* Note: ys_populate2 called as a special case here since the inserted child is
         * not covered by Step 9 in yang_parse_post
         */
        if (ys_populate2(yc, h) < 0)
            goto done;
        if (yang_apply(yc, -1, ys_populate2, 1, (void*)h) < 0)
            goto done;
    }
 ok:
   retval = 0;
 done:
    if (wnsc)
        cvec_free(wnsc);
    return retval;
}

/*! Find all top-level augments in a module and change original datamodels. 
 *
 * @param[in]  h     Clicon handle
 * @param[in]  ymod  Yang statement of type module/sub-module
 * @retval     0     OK
 * @retval    -1     Error
 * Note there is an ordering problem, where an augment in one module depends on an augment in
 * another module not yet augmented.
 */
static int
yang_augment_module(clicon_handle h,
                    yang_stmt    *ymod)

{
    int        retval = -1;
    yang_stmt *ys;

    ys = NULL;
    while ((ys = yn_each(ymod, ys)) != NULL){
        switch (yang_keyword_get(ys)){
        case Y_AUGMENT: /* top-level */
            if (yang_augment_node(h, ys) < 0)
                goto done;
            break;
        default:
            break;
        }
    }
    retval = 0;
 done:
    return retval;
}

/*! Given a refine node, perform the refinement action on the target refine node
 * The RFC is somewhat complicate in the rules for refine.
 * Most nodes will be replaced, but some are added
 * @param[in]  yr   Refine node
 * @param[in]  yt   Refine target node (will be modified)
 * @see RFC7950 Sec 7.13.2
 * There may be some missed cornercases
 */
static int
ys_do_refine(yang_stmt *yr,
             yang_stmt *yt)
{
    int           retval = -1;
    yang_stmt    *yrc; /* refine child */
    yang_stmt    *yrc1;
    yang_stmt    *ytc; /* target child */
    enum rfc_6020 keyw;
    int           i;
    
    /* Loop through refine node children. First if remove do that first 
     * In some cases remove a set of nodes.
     */
    yrc = NULL;
    while ((yrc = yn_each(yr, yrc)) != NULL) {
        keyw = yang_keyword_get(yrc);
        switch (keyw){
        case Y_DEFAULT: /* remove old, add new */
        case Y_DESCRIPTION:
        case Y_REFERENCE:
        case Y_CONFIG:
        case Y_MANDATORY:
        case Y_PRESENCE:
        case Y_MIN_ELEMENTS:
        case Y_MAX_ELEMENTS:
        case Y_EXTENSION:
            /* Remove old matching, dont increment due to prune in loop */
            for (i=0; i<yang_len_get(yt); ){
                ytc = yt->ys_stmt[i];
                if (keyw != yang_keyword_get(ytc)){
                    i++;
                    continue;
                }
                ys_prune(yt, i);
                ys_free(ytc);
            }
            /* fall through and add if not found */
        case Y_MUST:   /* keep old, add new */
        case Y_IF_FEATURE:  
            break;
        default:
            break;
        }
    }
    /* Second, add the node(s) */
    yrc = NULL;
    while ((yrc = yn_each(yr, yrc)) != NULL) {
        keyw = yang_keyword_get(yrc);
        /* Make copy */
        if ((yrc1 = ys_dup(yrc)) == NULL)
            goto done;
        if (yn_insert(yt, yrc1) < 0)
            goto done;
    }
    retval = 0;
 done:
    return retval;
}

/*! Check if Yang node y is a leaf in yang node list yp
 * Could be made to a generic function used elsewhere as well
 * @param[in]  y    Yang leaf
 * @param[in]  yp   Yang list parent 
 * @retval     0    No, y is not a key leaf in list yp
 * @retval     1    Yes, y is a key leaf in list yp
 */
static int
ys_iskey(yang_stmt *y,
         yang_stmt *yp)
{
    cvec      *cvv;
    cg_var    *cv;
    char     *name;    

    if (yang_keyword_get(y) != Y_LEAF)
        return 0;
    if (yang_keyword_get(yp) != Y_LIST)
        return 0;
    if ((cvv = yang_cvec_get(yp)) == NULL)
        return 0;
    name = yang_argument_get(y);
    cv = NULL;
    while ((cv = cvec_each(cvv, cv)) != NULL) {
        if (strcmp(name, cv_string_get(cv)) == 0)
            return 1;
    }
    return 0;
}

/*! Helper function to yang_expand_grouping
 * @param[in] yn     Yang parent node of uses ststement
 * @param[in] ys     Uses statement
 * @retval    0      OK
 * @retval    -1     Error
 */
static int
yang_expand_uses_node(yang_stmt *yn,
                      yang_stmt *ys,
                      int i)
{
    int        retval = -1;
    char      *id = NULL;
    char      *prefix = NULL;
    yang_stmt *ygrouping;  /* grouping original */
    yang_stmt *ygrouping2; /* grouping copy */
    yang_stmt *yg;         /* grouping child */
    yang_stmt *yr;         /* refinement */
    yang_stmt *yp;
    int        glen;
    size_t     size;
    int        j;
    int        k;
    yang_stmt *ywhen;
    char      *wxpath = NULL; /* xpath of when statement */
    cvec      *wnsc = NULL;   /* namespace context of when statement */
    
    /* Split argument into prefix and name */
    if (nodeid_split(yang_argument_get(ys), &prefix, &id) < 0)
        goto done;
    if (ys_grouping_resolve(ys, prefix, id, &ygrouping) < 0)
        goto done;
    if (ygrouping == NULL){
        clicon_log(LOG_NOTICE, "%s: Yang error : grouping \"%s\" not found in module \"%s\"", 
                   __FUNCTION__, yang_argument_get(ys), yang_argument_get(ys_module(ys)));
        goto done;
    }
    /* Check so that this uses statement is not a descendant of the grouping
     */
    yp = yn;
    do {
        if (yp == ygrouping){
            clicon_err(OE_YANG, EFAULT, "Yang use of grouping %s in module %s is defined inside the grouping (recursion), see RFC 7950 Sec 7.12: A grouping MUST NOT reference itself",
                       yang_argument_get(ys),
                       yang_argument_get(ys_module(yn))
                       );
            goto done;
        }
    } while((yp = yang_parent_get(yp)) != NULL);
    if (yang_flag_get(ygrouping, YANG_FLAG_MARK) == 0){ 
        /* Check mark flag to see if this grouping has been expanded before, 
         * here below in the traverse section 
         * A mark could be completely normal (several uses) or it could be a recursion.
         */
        yang_flag_set(ygrouping, YANG_FLAG_MARK); /* Mark as (being)  expanded */
        if (yang_expand_grouping(ygrouping) < 0)
            goto done;
    }
    /* Make a copy of the grouping, then make refinements to this copy
     * Note this ygrouping2 object does not have a parent and does not work in many
     * functions which assume a full hierarchy, use the original ygrouping in those cases.
     */
    if ((ygrouping2 = ys_dup(ygrouping)) == NULL)
        goto done;

    /* Only replace data/schemanodes and unknowns:
     * Compute the number of such nodes, and extend the child vector with that below
     */
    glen = 0;
    yg = NULL;
    while ((yg = yn_each(ygrouping2, yg)) != NULL) {
        if (yang_schemanode(yg) || yang_keyword_get(yg) == Y_UNKNOWN)
            glen++;
    }
    /* 
     * yn is parent: the children of ygrouping replaces ys.
     * Is there a case when glen == 0?  YES AND THIS BREAKS
     */
    if (glen != 1){
        size = (yang_len_get(yn) - i - 1)*sizeof(struct yang_stmt *);
        yn->ys_len += glen - 1;
        if (glen && (yn->ys_stmt = realloc(yn->ys_stmt, (yang_len_get(yn))*sizeof(yang_stmt *))) == 0){
            clicon_err(OE_YANG, errno, "realloc");
            goto done;
        }
        /* Then move all existing elements up from i+1 (not uses-stmt) */
        if (size)
            memmove(&yn->ys_stmt[i+glen],
                    &yn->ys_stmt[i+1],
                    size);
    }
    /* Find when statement, if present */
    if ((ywhen = yang_find(ys, Y_WHEN, NULL)) != NULL){
        wxpath = yang_argument_get(ywhen);
        if (xml_nsctx_yang(ywhen, &wnsc) < 0)
            goto done;
    }
    /* Note: yang_desc_schema_nodeid() requires ygrouping2 to be in yspec tree,
     * cannot be dangling, insert into tree here and then prune immediately after while loop
     */
    if (yn_insert(yang_parent_get(ygrouping), ygrouping2) < 0)
        goto done;
    /* Iterate through refinements and modify grouping copy 
     * See RFC 7950 7.13.2 yrt is the refine target node
     */
    yr = NULL;
    while ((yr = yn_each(ys, yr)) != NULL) {
        yang_stmt *yrt; /* refine target node */
        if (yang_keyword_get(yr) != Y_REFINE)
            continue;
        /* Find a node */
        if (yang_desc_schema_nodeid(ygrouping2,
                                    yang_argument_get(yr),
                                    &yrt) < 0)
            goto done;
        /* Not found, try next */
        if (yrt == NULL)                
            continue;
        /* Refine ANYDATA does not make sense */
        if (yang_keyword_get(yrt) == Y_ANYDATA || yang_keyword_get(yrt) == Y_ANYXML)
            continue;
        /* Do the actual refinement */
        if (ys_do_refine(yr, yrt) < 0)
            goto done;
    } /* while yr */
    /* Note: prune here to make dangling again after while loop */
    if (ys_prune_self(ygrouping2) < 0)
        goto done;
    /* Then copy and insert each child element from ygrouping2 to yn */
    k=0;
    for (j=0; j<yang_len_get(ygrouping2); j++){
        yg = ygrouping2->ys_stmt[j]; /* Child of refined copy */
        /* Only replace data/schemanodes */
        if (!yang_schemanode(yg) && yang_keyword_get(yg) != Y_UNKNOWN){
            ys_free(yg);
            continue;
        }
        /* If there is an associated when statement, add a special when struct to the yang 
         * see xml_yang_validate_all
         */
        if (ywhen){
            if (ys_iskey(yg, yn)){
                /* RFC 7950 Sec 7.21.5:
                 * If a key leaf is defined in a grouping that is used in a list, the
                 * "uses" statement MUST NOT have a "when" statement.
                 */
                
                clicon_err(OE_YANG, 0, "Key leaf '%s' defined in grouping '%s' is used in a 'uses' statement, This is not allowed according to RFC 7950 Sec 7.21.5",
                       yang_argument_get(yg),
                       yang_argument_get(ygrouping)
                       );
                goto done;
            }
            if (yang_when_xpath_set(yg, wxpath) < 0) 
                goto done;
            if (yang_when_nsc_set(yg, wnsc) < 0) 
                goto done;
        }
        /* This is for extensions that allow list keys to be optional, see restconf_main_extension_cb */
        if (yang_flag_get(ys, YANG_FLAG_NOKEY))
            yang_flag_set(yg, YANG_FLAG_NOKEY);
        yn->ys_stmt[i+k] = yg;
        yg->ys_parent = yn;
        k++;
    }
    /* Remove 'uses' node */
    ys_free(ys); 
    /* Remove the grouping copy */
    ygrouping2->ys_len = 0; /* Cant do with get access function */
    ys_free(ygrouping2);

    retval = 0;
 done:
    if (wnsc)
        cvec_free(wnsc);
    if (prefix)
        free(prefix); 
    if (id)
        free(id); 
    return retval;
}

/*! Macro expansion of grouping/uses done in step 2 of yang parsing 
 * RFC7950:
 * Identifiers appearing inside the grouping are resolved
 * relative to the scope in which the  grouping is defined, not where it is
 * used.  Prefix mappings, type names, grouping  names, and extension usage are
 * evaluated in the hierarchy where the "grouping" statement appears. 
 *   The identifiers defined in the grouping are not bound to a namespace
 * until the contents of the grouping are added to the schema tree via a
 * "uses" statement that does not appear inside a "grouping" statement,
 * at which point they are bound to the namespace of the current module.
 * @param[in] yn     Yang node for recursive iteration
 * @retval    0      OK
 * @retval    -1     Error
 */
static int
yang_expand_grouping(yang_stmt *yn)
{
    int        retval = -1;
    yang_stmt *ys = NULL;
    int        i;

    /* Cannot use yang_apply here since child-list is modified (is destructive) */
    i = 0;
    while (i < yang_len_get(yn)){
        ys = yn->ys_stmt[i]; 
        switch (yang_keyword_get(ys)){
        case Y_USES:
            if (yang_expand_uses_node(yn, ys, i) < 0)
                goto done;
            break; /* Note same child is re-iterated since it may be changed */
        default:
            i++;
            break;
        }
    }
    /* Second pass since length may have changed */
    for (i=0; i<yang_len_get(yn); i++){
        ys = yn->ys_stmt[i];
        if (yang_keyword_get(ys) == Y_GROUPING){
            /* Check mark flag to see if this grouping has been expanded before, here or in the
             * 'uses' section 
             * A mark could be completely normal (several uses) or it could be a recursion.
             */
            if (yang_flag_get(ys, YANG_FLAG_MARK) == 0){
                yang_flag_set(ys, YANG_FLAG_MARK); /* Mark as (being)  expanded */
                if (yang_expand_grouping(ys) < 0)
                    goto done;
            }
        }
        else{
            if (yang_expand_grouping(ys) < 0)
                goto done;
        }
    }
    retval = 0;
 done:
    return retval;
}

/*! Parse a string containing a YANG spec into a parse-tree
 * 
 * Syntax parsing. A string is input and a YANG syntax-tree is returned (or error). 
 * As a side-effect, Yang modules present in the text will be inserted under the global Yang 
 * specification
 * @param[in] str    String of yang statements
 * @param[in] name   Log string, typically filename
 * @param[in] yspec  Yang specification. 
 * @retval    ymod   Top-level yang (sub)module
 * @retval    NULL   Error encountered
 * See top of file for diagram of calling order
 */
yang_stmt *
yang_parse_str(char         *str,
               const char   *name, /* just for errs */
               yang_stmt    *yspec)
{
    clixon_yang_yacc yy = {0,};
    yang_stmt       *ymod = NULL;

    if (yspec == NULL){
        clicon_err(OE_YANG, 0, "Yang parse need top level yang spec");
        goto done;
    }
    yy.yy_name         = (char*)name;
    yy.yy_linenum      = 1;
    yy.yy_parse_string = str;
    yy.yy_stack        = NULL;
    yy.yy_module       = NULL; /* this is the return value - the module/sub-module */
    if (ystack_push(&yy, yspec) == NULL)
        goto done;
    if (strlen(str)){ /* Not empty */
        if (yang_scan_init(&yy) < 0)
            goto done;
        if (yang_parse_init(&yy) < 0)
            goto done;
        if (clixon_yang_parseparse(&yy) != 0) { /* yacc returns 1 on error */
            clicon_log(LOG_NOTICE, "Yang error: %s on line %d", name, yy.yy_linenum);
            if (clicon_errno == 0)
                clicon_err(OE_YANG, 0, "yang parser error with no error code (should not happen)");
            yang_parse_exit(&yy);
            yang_scan_exit(&yy);
            goto done;
        }
        if (yang_parse_exit(&yy) < 0)
            goto done;          
        if (yang_scan_exit(&yy) < 0)
            goto done;          
    }
    if ((ymod = yy.yy_module) == NULL){
        clicon_err(OE_YANG, 0, "No module in YANG %s", name);
        goto done;
    }
    /* Add filename for debugging and errors, see also ys_linenum on (each symbol?) */
    if (yang_filename_set(ymod, name) < 0)
        goto done;
  done:
    ystack_pop(&yy);
    if (yy.yy_stack)
        free (yy.yy_stack);
    return ymod;  /* top-level (sub)module */
}

/*! Parse yang spec from an open file descriptor
 * @param[in] fd     File descriptor containing the YANG file as ASCII characters
 * @param[in] name   For debug, eg filename
 * @param[in] yspec  Yang specification. Should have been created by caller using yspec_new
 * @retval ymod      Top-level yang (sub)module
 * @retval NULL      Error 
 * @note this function simply parse a yang spec, no dependencies or checks
 */
yang_stmt *
yang_parse_file(FILE       *fp,
                const char *name,
                yang_stmt  *yspec)
{
    char         *buf = NULL;
    int           i;
    char          c;
    int           len;
    yang_stmt    *ymod = NULL;
    int           ret;

    len = BUFLEN; /* any number is fine */
    if ((buf = malloc(len)) == NULL){
        clicon_err(OE_XML, errno, "malloc");
        goto done;
    }
    memset(buf, 0, len);
    i = 0; /* position in buf */
    while (1){ /* read the whole file */
        if ((ret = fread(&c, 1, 1, fp)) < 0){
            clicon_err(OE_XML, errno, "read");
            break;
        }
        if (ret == 0)
            break; /* eof */
        if (i == len-1){
            if ((buf = realloc(buf, 2*len)) == NULL){
                clicon_err(OE_XML, errno, "realloc");
                goto done;
            }       
            memset(buf+len, 0, len);
            len *= 2;
        }
        buf[i++] = (char)(c&0xff);
    } /* read a line */
    if ((ymod = yang_parse_str(buf, name, yspec)) < 0)
        goto done;
  done:
    if (buf != NULL)
        free(buf);
    return ymod; /* top-level (sub)module */
}

/*! Given a yang filename, extract the revision as an integer as YYYYMMDD
 * @param[in]  filename  Filename on the form: name [+ @rev ] + .yang  
 * @param[out] basep     "Base" filename, stripped: [+ @rev ] + .yang (malloced)
 * @param[out] revp      Revision as YYYYMMDD (0 if not found)
 */
static int
filename2revision(const char *filename,
                  char      **basep,
                  uint32_t   *revp)
{
    int      retval = -1;
    char    *base = NULL;
    char    *p;
    
    /* base = module name [+ @rev ] + .yang */
    if ((base = strdup(filename)) == NULL){
        clicon_err(OE_UNIX, errno, "strdup");
        goto done;
    }
    clicon_debug(CLIXON_DBG_DETAIL, "%s %s", __FUNCTION__, base);
    if ((p = rindex(base, '.')) != NULL) /* strip postfix .yang */
        *p = '\0';
    if ((p = index(base, '@')) != NULL){ /* extract revision date */
        *p++ = '\0';
        if (revp && ys_parse_date_arg(p, revp) < 0)
            goto done;
    }
    if (basep){
        *basep = base;
        base = NULL;
    }
    retval = 0;
 done:
    if (base)
        free(base);
    return retval;
}

/*! No specific revision give. Match a yang file given module 
 * @param[in]  h        CLICON handle
 * @param[in]  module   Name of main YANG module. 
 * @param[in]  revision Revision or NULL
 * @param[out] fbuf     Buffer containing filename or NULL (if retval=1)
 * @retval     1        Match found, Most recent entry returned in fbuf
 * @retval     0        No matching entry found
 * @retval    -1        Error 
 * @note for bootstrapping, dir may have to be set.
*/
int
yang_file_find_match(clicon_handle h, 
                     const char   *module,
                     const char   *revision,
                     cbuf         *fbuf)    
{
    int           retval = -1;
    cbuf         *regex = NULL;
    cxobj        *x;
    cxobj        *xc;
    char         *dir;
    cvec         *cvv = NULL;
    cg_var       *cv = NULL;
    cg_var       *bestcv = NULL;

    /* get clicon config file in xml form */
    if ((x = clicon_conf_xml(h)) == NULL)
        goto ok;
    if ((regex = cbuf_new()) == NULL){
        clicon_err(OE_YANG, errno, "cbuf_new");
        goto done;
    }
    /* RFC 6020: The name of the file SHOULD be of the form:
     * module-or-submodule-name ['@' revision-date] ( '.yang' / '.yin' )
     * revision-date ::= 4DIGIT "-" 2DIGIT "-" 2DIGIT
     */
    if (revision)
        cprintf(regex, "^%s@%s(.yang)$", module, revision);
    else
        cprintf(regex, "^%s(@[0-9][0-9][0-9][0-9]-[0-9][0-9]-[0-9][0-9])?(.yang)$",
                module);
    xc = NULL;

    while ((xc = xml_child_each(x, xc, CX_ELMNT)) != NULL) {
        if (strcmp(xml_name(xc), "CLICON_YANG_MAIN_DIR") == 0){
            struct dirent *dp = NULL;
            int ndp;

            dir = xml_body(xc);
            /* get all matching files in this directory */
            if ((ndp = clicon_file_dirent(dir, 
                                          &dp, 
                                          cbuf_get(regex),
                                          S_IFREG)) < 0)
                goto done;
            /* Entries are sorted, last entry should be most recent date 
             */
            if (ndp != 0){
                if (fbuf)
                    cprintf(fbuf, "%s/%s", dir, dp[ndp-1].d_name);
                if (dp)
                    free(dp);
                retval = 1;
                goto done;
            }
            if (dp)
                free(dp);
        }
        else if (strcmp(xml_name(xc), "CLICON_YANG_DIR") == 0 &&
                 (dir = xml_body(xc)) != NULL){
            /* get all matching files in this directory recursively */
            if ((cvv = cvec_new(0)) == NULL){
                clicon_err(OE_UNIX, errno, "cvec_new");
                goto done;
            }
            if (clicon_files_recursive(dir, cbuf_get(regex), cvv) < 0)
                goto done;

            /* Entries are not sorted and come in a vector: <name,path>.
             * Find latest name and use path as return value
             */
            bestcv = NULL;
            while ((cv = cvec_each(cvv, cv)) != NULL){
                if (bestcv == NULL)
                    bestcv = cv;
                else if (strcoll(cv_name_get(cv), cv_name_get(bestcv)) > 0)
                    bestcv = cv;
            }
            if (bestcv){
                if (fbuf)
                    cprintf(fbuf, "%s", cv_string_get(bestcv));      /* file path */
                retval = 1; /* found */
                goto done;
            }
            if (cvv){
                cvec_free(cvv);
                cvv = NULL;
            }
        }
    }
ok:
    retval = 0;
done:
    if (cvv)
        cvec_free(cvv);
    if (regex)
        cbuf_free(regex);
    return retval;
}

/*! Open a file, read into a string and invoke yang parsing
 *
 * Similar to clicon_yang_str(), just read a file first
 * @param[in] h        Clixon handle (can be NULL, but then no callbacks)
 * @param[in] filename Name of file
 * @param[in] yspec    Yang specification. Should have been created by caller using yspec_new
 * @retval ymod        Top-level yang (sub)module
 * @retval NULL        Error encountered

 * The database symbols are inserted in alphabetical order.
 * See top of file for diagram of calling order
 */
yang_stmt *
yang_parse_filename(clicon_handle h,
                    const char   *filename, 
                    yang_stmt    *yspec)
{
    yang_stmt    *ymod = NULL;
    FILE         *fp = NULL;
    struct stat   st;

    clicon_debug(1, "%s %s", __FUNCTION__, filename);
    if (stat(filename, &st) < 0){
        clicon_err(OE_YANG, errno, "%s not found", filename);
        goto done;
    }
    if ((fp = fopen(filename, "r")) == NULL){
        clicon_err(OE_YANG, errno, "fopen(%s)", filename);      
        goto done;
    }
    if ((ymod = yang_parse_file(fp, filename, yspec)) < 0)
        goto done;
    /* YANG patch hook */
    if (ymod && h && clixon_plugin_yang_patch_all(h, ymod) < 0)
        goto done;
  done:
    if (fp)
        fclose(fp);
    return ymod; /* top-level (sub)module */
}

/*! Given a (sub)module, parse all (sub)modules in turn recursively
 *
 * Find a yang module file, and then recursively parse all its imported modules.
 * @param[in] h        CLICON handle
 * @param[in] module   Module name
 * @param[in] revision Revision (or NULL)
 * @param[in] yspec    Yang statement
 * @param[in] origname Name of yang module triggering this parsing, for logging
 * @retval    0        OK
 * @retval   -1        Error
 *
 * See top of file for diagram of calling order
 * @note does not check wether the module is already loaded
 */
yang_stmt *
yang_parse_module(clicon_handle h,
                  const char   *module, 
                  const char   *revision, 
                  yang_stmt    *yspec,
                  char         *origname)
{
    cbuf      *fbuf = NULL;
    char      *filename;
    int        nr;
    yang_stmt *ymod = NULL;
    yang_stmt *yrev; /* yang revision */
    uint32_t   revf = 0; /* revision in filename */
    uint32_t   revm = 0; /* revision in parsed new module (should be same as revf) */
    cbuf      *cb = NULL;

    if ((fbuf = cbuf_new()) == NULL){
        clicon_err(OE_UNIX, errno, "cbuf_new");
        goto done;
    }
    /* Match a yang file with or without revision in yang-dir list */
    if ((nr = yang_file_find_match(h, module, revision, fbuf)) < 0)
        goto done;
    if (nr == 0){
        if ((cb = cbuf_new()) == NULL){
            clicon_err(OE_UNIX, errno, "cbuf_new");
            goto done;
        }
        cprintf(cb, "%s", module);
        if (revision)
            cprintf(cb, "@%s", revision);
        if (origname)
            clicon_err(OE_YANG, ENOENT, "No yang files found matching \"%s\" in the list of CLICON_YANG_DIRs when loading %s.yang", cbuf_get(cb), origname);
        else
            clicon_err(OE_YANG, ENOENT, "No yang files found matching \"%s\" in the list of CLICON_YANG_DIRs", cbuf_get(cb));
        goto done;
    }
    filename = cbuf_get(fbuf);
    if ((ymod = yang_parse_filename(h, filename, yspec)) == NULL)
        goto done;
    /* Sanity check that requested module name matches loaded module
     * If this does not match, the filename and containing module do not match
     * RFC 7950 Sec 5.2 
     */
    if (strcmp(yang_argument_get(ymod), module) != 0){
        clicon_err(OE_YANG, EINVAL, "File %s contains yang module \"%s\" which does not match expected module %s",
                   filename,
                   yang_argument_get(ymod),
                   module);
        ymod = NULL;
        goto done;
    }
    /* Sanity check that requested module name matches loaded module
     * If this does not match, the filename and containing module do not match
     * RFC 7950 Sec 5.2 
     */
    if ((yrev = yang_find(ymod, Y_REVISION, NULL)) != NULL)
        revm = cv_uint32_get(yang_cv_get(yrev));
    if (filename2revision(filename, NULL, &revf) < 0)
        goto done;
    /* Sanity check that file revision does not match internal rev stmt */
    if (revf && revm && revm != revf){ 
        clicon_err(OE_YANG, EINVAL, "Yang module file revision and in yang does not match: %s vs %u", filename, revm); 
        ymod = NULL;
        goto done;
    }
  done:
    if (cb)
        cbuf_free(cb);
    if (fbuf)
        cbuf_free(fbuf);
    return ymod; /* top-level (sub)module */
}

/*! Given a (sub)module, parse all (sub)modules in turn recursively
 *
 * Find a yang module file, and then recursively parse all its imported modules.
 * @param[in] h        CLICON handle
 * @param[in] ymod     Yang module. 
 * @param[in] yspec    Yang specification.
 * @retval    0        OK
 * @retval   -1        Error
 *
 * See top of file for diagram of calling order
 */
static int
yang_parse_recurse(clicon_handle h,
                   yang_stmt    *ymod,
                   yang_stmt    *ysp)
{
    int           retval = -1;
    yang_stmt    *yi = NULL; /* import */
    yang_stmt    *yrev;
    yang_stmt    *ybelongto;
    yang_stmt    *yrealmod;
    char         *submodule;
    char         *subrevision;
    yang_stmt    *subymod;
    enum rfc_6020 keyw;

    if (ys_real_module(ymod, &yrealmod) < 0)
        goto done;
    /* go through all import (modules) and include(submodules) of ysp */
    while ((yi = yn_each(ymod, yi)) != NULL){
        keyw = yang_keyword_get(yi);
        if (keyw != Y_IMPORT && keyw != Y_INCLUDE)
            continue;
        /* common part */
        submodule = yang_argument_get(yi);
        /* Is there a specific revision (or just latest)? */
        if ((yrev = yang_find(yi, Y_REVISION_DATE, NULL)) != NULL)
            subrevision = yang_argument_get(yrev);
        else
            subrevision = NULL;
        /* if already loaded, ignore, else parse the file */
        if (yang_find(ysp,
                      keyw==Y_IMPORT?Y_MODULE:Y_SUBMODULE,
                      submodule) == NULL){
            /* recursive call */
            if ((subymod = yang_parse_module(h, submodule, subrevision, ysp, yang_argument_get(ymod))) == NULL)
                goto done;
            /* Sanity check: if submodule, its belongs-to statement shall point to the module */
            if (keyw == Y_INCLUDE){
                ybelongto = yang_find(subymod, Y_BELONGS_TO, NULL);
                if (ybelongto == NULL){
                    clicon_err(OE_YANG, ENOENT, "Sub-module \"%s\" does not have a belongs-to statement", submodule); /* shouldnt happen */
                    goto done;
                }
                if (strcmp(yang_argument_get(ybelongto), yang_argument_get(yrealmod)) != 0){
                    clicon_err(OE_YANG, ENOENT, "Sub-module \"%s\" references module \"%s\" in its belongs-to statement but should reference \"%s\"",
                               submodule,
                               yang_argument_get(ybelongto),
                               yang_argument_get(yrealmod));
                    goto done;
                }
            }
            /* Go through its sub-modules recursively */
            if (yang_parse_recurse(h, subymod, ysp) < 0){
                ymod = NULL;
                goto done;
            }
        }
    }
    retval = 0;
  done:  
    return retval; /* top-level (sub)module */
}

/*!
 * @param[in] ys      Yang statement
 * @param[in] dummy   Necessary for called in yang_apply
 * @see yang_applyfn_t
 */
static int 
ys_schemanode_check(yang_stmt *ys, 
                    void      *dummy)
{
    int           retval = -1;
    yang_stmt    *yres = NULL;
    yang_stmt    *yp;
    char         *arg;
    enum rfc_6020 keyword;
    char **vec = NULL;
    char  *v;
    int    nvec;
    int    i;

    yp = yang_parent_get(ys);
    arg = yang_argument_get(ys);
    keyword = yang_keyword_get(ys);
    switch (yang_keyword_get(ys)){
    case Y_AUGMENT:
        if (yang_keyword_get(yp) == Y_MODULE || /* Not top-level */
            yang_keyword_get(yp) == Y_SUBMODULE) 
            break;
        /* fallthru */
    case Y_REFINE:
        if (yang_desc_schema_nodeid(yp, arg, &yres) < 0)
            goto done;
        if (yres == NULL){
            clicon_err(OE_YANG, 0, "schemanode sanity check of %s %s", 
                       yang_key2str(keyword), arg);
            goto done;
        }
        break;
    case Y_UNIQUE:{
        /* Unique: Sec 7.8.3 It takes as an argument a string that contains a space-
           separated list of schema node identifiers */
        if ((vec = clicon_strsep(arg, " \t\n", &nvec)) == NULL)
            goto done;
        for (i=0; i<nvec; i++){
            v = vec[i]; 
            if (yang_desc_schema_nodeid(yp, v, &yres) < 0)
                goto done;
            if (yres == NULL){
                clicon_err(OE_YANG, 0, "schemanode sanity check of %s %s", 
                           yang_key2str(yang_keyword_get(ys)), v);
                goto done;
            }
        }
        break;
    }
    default:
        break;
    }
    retval = 0;
 done:
    if (vec)
        free(vec);
    return retval;
}

/*! Check lists: config lists MUST have keys
 * @param[in] h   Clicon handle
 * @param[in] ys  Yang statement
 * Verify the following rule:
 * RFC 7950 7.8.2: The "key" statement, which MUST be present if the list represents
 *                 configuration and MAY be present otherwise
 * Unless it is the "errors" rule of the ietf-restconf spec which seems to be a special case.
 */
static int 
ys_list_check(clicon_handle h,
              yang_stmt    *ys)
{
    int           retval = -1;
    yang_stmt    *ymod;
    yang_stmt    *yc = NULL;
    enum rfc_6020 keyw;
    yang_stmt    *yroot;
    
    /* This node is state, not config */
    if (yang_config_ancestor(ys) == 0)
        goto ok;
    /* Find root, examine if this node is part of a rpc declaration */
    if ((yroot = yang_myroot(ys)) != NULL &&
        yang_keyword_get(yroot) == Y_RPC)
        goto ok;
    
    keyw = yang_keyword_get(ys);
    /* Check if list and if keys do not exist */
    if (keyw == Y_LIST &&
        yang_find(ys, Y_KEY, NULL) == 0){
        ymod = ys_module(ys);
        /* Except nokey exceptions such as rrc 8040 yang-data */
        if (!yang_flag_get(yroot, YANG_FLAG_NOKEY)){
            /* Note obsolete */
            clicon_log(LOG_ERR, "Error: LIST \"%s\" in module \"%s\" lacks key statement which MUST be present (See RFC 7950 Sec 7.8.2)", 
                       yang_argument_get(ys),
                       yang_argument_get(ymod)
                       );
            goto done;
        }
    }
    /* Traverse subs */
    if (yang_schemanode(ys) || keyw == Y_MODULE || keyw == Y_SUBMODULE){
        yc = NULL;
        while ((yc = yn_each(ys, yc)) != NULL){
            if (ys_list_check(h, yc) < 0)
                goto done;
        }
    }
 ok:
    retval = 0;
 done:
    return retval;
}

/*! Depth-first topological sort
 * Topological sort of a DAG
 * @param[in]  yn    Yang module node
 * @param[out] ylist Result list of sorted nodes with "least significant" first
 * @param[out] ylen  Length of ylist
 * @retval     0     OK
 * @retval    -1     Error. Eg circular
 * see eg https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
 */
static int
ys_visit(struct yang_stmt   *yn,
         struct yang_stmt ***ylist,
         int                *ylen)
{
    int               retval = -1;
    int               i;
    struct yang_stmt *yi; /* import / include */
    struct yang_stmt *yspec;
    struct yang_stmt *ymod;
    
    if (yn == NULL ||
        (yang_keyword_get(yn) != Y_MODULE && yang_keyword_get(yn) != Y_SUBMODULE)){
        clicon_err(OE_YANG, EINVAL, "Expected module or submodule");
        goto done;
    }
    yspec = ys_spec(yn);
    /* if n has a permanent mark then return */
    if (yang_flag_get(yn, YANG_FLAG_MARK))
        return 0;
    /* if n has a temporary mark then stop (not a DAG) */
    if (yang_flag_get(yn, YANG_FLAG_TMP)){
        clicon_err(OE_YANG, EFAULT, "Yang module %s import/include is circular", yang_argument_get(yn));
        goto done;
    }
    /* mark n with a temporary mark */
    yang_flag_set(yn, YANG_FLAG_TMP);

    /* Loop through import and include statements and visit each */
    yi = NULL;
    for (i=0; i<yang_len_get(yn); i++){
        yi = yang_child_i(yn, i);
        if (yang_keyword_get(yi) != Y_IMPORT &&
            yang_keyword_get(yi) != Y_INCLUDE)
            continue;
        if ((ymod = yang_find(yspec, Y_MODULE, yang_argument_get(yi))) == NULL &&
            (ymod = yang_find(yspec, Y_SUBMODULE, yang_argument_get(yi))) == NULL){
            clicon_err(OE_YANG, EFAULT, "Yang module %s import/include not found",
                       yang_argument_get(yi)); /* shouldnt happen */
            goto done;
        }
        if (ys_visit(ymod, ylist, ylen) < 0)
            goto done;
    }
    /* remove temporary mark from n */
    yang_flag_reset(yn, YANG_FLAG_TMP);
    /* mark n with a permanent mark */
    yang_flag_set(yn, YANG_FLAG_MARK);
    /* add n to head of L. NB reversed */
    (*ylen)++;
    if ((*ylist = realloc(*ylist, (*ylen)*sizeof(yang_stmt *))) == 0){
        clicon_err(OE_YANG, errno, "realloc");
        goto done;
    }
    (*ylist)[*ylen - 1] = yn;
    retval = 0;
 done:
    return retval;
}

/*! Sort module/submodules according to import/include order and cycle detect
 * Topological sort of a DAG
 * @param[in]  yspec   Yang specification. 
 * @param[in]  modmin  Start of interval of yspec:s module children 
 * @param[in]  modmax  End of interval
 * @param[out] ylist   Result list of sorted nodes with "least significant" first
 * @param[out] ylen    Length of ylist
 * see eg https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
 */
static int
yang_sort_modules(yang_stmt          *yspec,
                  int                 modmin,
                  int                 modmax,
                  struct yang_stmt ***ylist,
                  int                *ylen)
{
    int               retval = -1;
    int               i;
    struct yang_stmt *yn;


    for (i=modmin; i<modmax; i++){
        yn = yang_child_i(yspec, i);
        /* select an unmarked node n */
        if (yang_flag_get(yn, YANG_FLAG_MARK|YANG_FLAG_TMP) == 0){
            if (ys_visit(yn, ylist, ylen) < 0)
                goto done;
        }
    }
    if (*ylen != modmax-modmin){
        clicon_err(OE_YANG, EFAULT, "Internal error: mismatch sort vector lengths");
    }
    retval = 0;
 done:
    return retval;
}

/*! Parse top yang module including all its sub-modules. Expand and populate yang tree
 *
 * Perform secondary actions after yang parsing. These actions cannot be made at
 * parse-time for various reasons:
 * - Detect imported yang specs that are not loaded and load and parse them too
 * - Check cardinality of yang (that nr of children match)
 * - Check features: remove disabled
 * - "Populate" yang, which means things like initiating caches, resolving references
 * - Resolve types
 * - Augments
 * - Defaults
 * There is some complexity in how modules are loaded vs how they need to be augmented
 * Therefore, after full loading, a topological sort is made to ensure the modules are 
 * non-circular (a DAG) and that the rest of the operations are made in the topology order.
 * The loading order of the yang models (under yang spec) is kept.
 * 
 * @param[in] h      CLICON handle
 * @param[in] yspec  Yang specification. 
 * @param[in] modmin Perform checks after this number, prior are already complete
 * @retval    0      Everything OK
 * @retval   -1      Error encountered
 */
int
yang_parse_post(clicon_handle h,
                yang_stmt    *yspec,
                int           modmin)
{
    int                retval = -1;
    int                i;
    int                modmax;
    struct yang_stmt **ylist = NULL; /* Topology sorted modules */
    int                ylen = 0;     /* Length of ylist */
    
    /* 1: Parse from text to yang parse-tree. 
     * Iterate through modules and detect module/submodules to parse
     * NOTE: the list may grow on each iteration */
    for (i=modmin; i<yang_len_get(yspec); i++)
        if (yang_parse_recurse(h, yang_child_i(yspec, i), yspec) < 0)
            goto done;
    
    modmax = yang_len_get(yspec);
    /* The set of modules [modmin..maxmax] is here complete wrt imports/includes and is a DAG
     * Example: A imports B, C and D, and C and D imports B
     * In some operations below (eg augment) need to be in topology order, eg B first.
     * Therefore the modules are sorted into a separate list that is used henceforth
     */
    if (yang_sort_modules(yspec, modmin, yang_len_get(yspec), &ylist, &ylen) < 0)
        goto done;

    /* 2. Check cardinality a first time (done again last) */
    for (i=modmin; i<modmax; i++) 
        if (yang_cardinality(h, yang_child_i(yspec, i), yang_argument_get(yspec->ys_stmt[i])) < 0)
            goto done;
    
    /* 3: Check features/if-features: check if enabled and remove disabled features */
    for (i=modmin; i<modmax; i++) 
        if (yang_features(h, yang_child_i(yspec, i)) < 0)
            goto done;

    /* 4: Go through parse tree and populate it with cv types */
    for (i=modmin; i<modmax; i++){
        if (yang_apply(yang_child_i(yspec, i), -1, ys_populate, 0, (void*)h) < 0)
            goto done;
    }

    /* 5: Resolve all types: populate type caches. Requires eg length/range cvecs
     * from ys_populate step.
     * Must be done using static binding.
     */
    for (i=modmin; i<modmax; i++)
        if (yang_apply(yang_child_i(yspec, i), Y_TYPE, ys_resolve_type, 1, h) < 0)
            goto done;

    /* Up to here resolving is made in the context they are defined, rather 
     * than the context they are used (except for submodules being merged w 
     * modules). Like static scoping. 
     * After this we expand all grouping/uses and unfold all macros into a
     * single tree as they are used.
     */

    /* 6: Macro expansion of all grouping/uses pairs. Expansion needs marking */
    for (i=0; i<ylen; i++){
        if (yang_expand_grouping(ylist[i]) < 0)
            goto done;
        yang_apply(ylist[i], -1, (yang_applyfn_t*)yang_flag_reset, 1, (void*)YANG_FLAG_MARK);
    }

    /* 7: Top-level augmentation of all modules. 
     * Note: Clixon does not implement augment in USES 
     * Note: There is an ordering problem, where an augment in one module depends on an augment in
     * another module not yet augmented.
     */
    for (i=0; i<ylen; i++)
        if (yang_augment_module(h, ylist[i]) < 0)
            goto done;

    /* 8: Check deviations: not-supported add/delete/replace statements 
     *    done late since eg groups must be expanded
     */
    for (i=modmin; i<modmax; i++) /* Really only under (sub)modules no need to traverse whole tree */
        if (yang_apply(yang_child_i(yspec, i), -1, yang_deviation, 1, (void*)h) < 0)
            goto done;
    
    /* 9: Go through parse tree and do 2nd step populate (eg default) 
     *    Note that augments in step 7 are not covered here since they apply to
     *    modules already loaded. Therefore the call to ys_populate2 is made inline in
     *    yang_augment_node()
     */
    for (i=0; i<ylen; i++)
        if (yang_apply(ylist[i], -1, ys_populate2, 1, (void*)h) < 0)
            goto done;

    /* 10: sanity checks of expanded yangs need more here */
    for (i=0; i<ylen; i++){
        /* Check schemanode references */
        if (yang_apply(ylist[i], -1, ys_schemanode_check, 1, NULL) < 0)
            goto done;
        /* Check list key values */
        if (ys_list_check(h, ylist[i]) < 0)
            goto done;
    }
    /* 11. Check cardinality a second time after grouping/augment etc */
    for (i=0; i<ylen; i++)
        if (yang_cardinality(h, ylist[i], yang_argument_get(ylist[i])) < 0)
            goto done;
    retval = 0;
 done:
    if (ylist)
        free(ylist);
    return retval;
}

/*! Parse yang specification and its dependencies recursively given module
 * @param[in]  h         clicon handle
 * @param[in]  module    Module name, or absolute filename (including dir)
 * @param[in]  revision  Revision, or NULL
 * @param[in]  yspec     Modules parse are added to this yangspec
 * @retval     0         OK
 * @retval    -1         Error
 * @see yang_spec_parse_file
 */
int
yang_spec_parse_module(clicon_handle h, 
                       const char   *name,
                       const char   *revision, 
                       yang_stmt    *yspec)
{
    int         retval = -1;
    int         modmin;       /* Existing number of modules */
    char       *base = NULL;;

    if (yspec == NULL){
        clicon_err(OE_YANG, EINVAL, "yang spec is NULL");
        goto done;
    }
    if (name == NULL){
        clicon_err(OE_YANG, EINVAL, "yang module not set");
        goto done;
    }
    /* Apply steps 2.. on new modules, ie ones after modmin. */
    modmin = yang_len_get(yspec);
    /* Do not load module if it already exists */
    if (yang_find_module_by_name_revision(yspec, name, revision) != NULL)
        goto ok;
    /* Find a yang module and parse it and all its submodules */
    if (yang_parse_module(h, name, revision, yspec, NULL) == NULL)
        goto done;
    if (yang_parse_post(h, yspec, modmin) < 0)
        goto done;
 ok:
    retval = 0;
 done:
    if (base)
        free(base);
    return retval;
}

/*! Parse yang specification and its dependencies recursively given filename
 * @param[in]  h         clicon handle
 * @param[in]  filename  Actual filename (including dir and revision)
 * @param[in]  yspec     Modules parse are added to this yangspec
 * @retval     0         OK
 * @retval    -1         Error
 * @see yang_spec_parse_module for yang dir,module,revision instead of 
 *       actual filename
 * @see yang_spec_load_dir For loading all files in a directory
 */
int
yang_spec_parse_file(clicon_handle h, 
                     char         *filename, 
                     yang_stmt    *yspec)
{
    int         retval = -1;
    int         modmin;       /* Existing number of modules */
    char       *base = NULL;;

    /* Apply steps 2.. on new modules, ie ones after modmin. */
    modmin = yang_len_get(yspec);
    /* Find module, and do not load file if module already exists */
    if (basename(filename) == NULL){
        clicon_err(OE_YANG, errno, "No basename");
        goto done;
    }
    if ((base = strdup(basename(filename))) == NULL){
        clicon_err(OE_YANG, errno, "strdup");
        goto done;
    }
    if (index(base, '@') != NULL)
        *index(base, '@') = '\0';
    if (yang_find(yspec, Y_MODULE, base) != NULL)
        goto ok;
    if (yang_parse_filename(h, filename, yspec) == NULL)
        goto done;
    if (yang_parse_post(h, yspec, modmin) < 0)
        goto done;
 ok:
    retval = 0;
 done:
    if (base)
        free(base);
    return retval;
}

/*! Load all yang modules in directory
 * @param[in]  h     Clicon handle
 * @param[in]  dir   Load all yang modules in this directory
 * @param[in]  yspec Modules parse are added to this yangspec
 * @retval     0     OK
 * @retval    -1     Error
 * @see yang_spec_parse_file
 * Load all yang files in a directory as primary objects.
 * Some details if several same yang module x exists:
 * 1) If x is already loaded (eg via direct file loading) skip it
 * 2) Prefer x.yang over x@rev.yang (no revision)
 * 3) If only x@rev.yang's found, prefer newest (newest revision)
 * There is also an extra failsafe which may not be necessary, which removes
 * the oldest module if 1-3 for some reason fails.
 */
int
yang_spec_load_dir(clicon_handle h,
                   char         *dir,
                   yang_stmt    *yspec)
{
    int            retval = -1;
    int            ndp;
    struct dirent *dp = NULL;
    int            i;
    int            j;
    char           filename[MAXPATHLEN];
    char          *base = NULL; /* filename without dir */
    int            modmin;
    yang_stmt     *ym;   /* yang module */
    yang_stmt     *ym0;  /* (existing) yang module */
    yang_stmt     *yrev; /* yang revision */
    uint32_t       revf = 0; /* revision in filename */
    uint32_t       revm = 0; /* revision in parsed new module (should be same as revf) */
    uint32_t       rev0; /* revision in existing module */
    char          *oldbase = NULL;
    int            taken = 0;
    
    /* Get yang files names from yang module directory. Note that these
     * are sorted alphatetically:
     * a.yang, 
     * a@2000-01-01.yang, 
     * a@2111-11-11.yang
     */
    if((ndp = clicon_file_dirent(dir, &dp, "(.yang)$", S_IFREG)) < 0)
        goto done;
    if (ndp == 0)
        goto ok;
    /* Apply post steps on new modules, ie ones after modmin. */
    modmin = yang_len_get(yspec);
    /* Load all yang files in dir */
    for (i = 0; i < ndp; i++) {
        /* base = module name [+ @rev ] + .yang */
       if (oldbase)
           free(oldbase);
        oldbase = base;
        base = NULL;
        revf = 0;
        if (filename2revision(dp[i].d_name, &base, &revf) < 0)
            goto done;
        if (oldbase && strcmp(base, oldbase)) /* new yang file basename */
            taken = 0;
        if (revf == 0) /* No revision: a.yang - take that */
            taken = 1;
        else{ /* a@xxx.yang */
            if (taken)
                continue; /* skip if already taken */
            /* Look forward: is there anyone else later? (assume sorted revision dates) */
            if (i+1 < ndp){ /* not last in list */
                char *nextbase = NULL; /* XXX suboptimal algorithm, could combione old/next/base */
                if (filename2revision(dp[i+1].d_name, &nextbase, NULL) < 0)
                    goto done;
                if (nextbase && strcmp(base, nextbase) == 0){
                    free(nextbase);
                    nextbase = NULL;
                    continue; /* same base: skip; */
                }
                if (nextbase)
                    free(nextbase);
            }
            taken = 1; /* last in line and not taken */
        }
        /* Here only a single file is reached(taken)
         * Check if module already exists -> ym0/rev0 */
        rev0 = 0;
        if ((ym0 = yang_find(yspec, Y_MODULE, base)) != NULL ||
            (ym0 = yang_find(yspec, Y_SUBMODULE, base)) != NULL){
            yrev = yang_find(ym0, Y_REVISION, NULL);
            rev0 = cv_uint32_get(yang_cv_get(yrev));
            continue; /* skip if already added by specific file or module */
        }
        /* Create full filename */
        snprintf(filename, MAXPATHLEN-1, "%s/%s", dir, dp[i].d_name);
        if ((ym = yang_parse_filename(h, filename, yspec)) == NULL)
            goto done;
        revm = 0;
        if ((yrev = yang_find(ym, Y_REVISION, NULL)) != NULL)
            revm = cv_uint32_get(yang_cv_get(yrev));
        /* Sanity check that file revision does not match internal rev stmt */
        if (revf && revm && revm != revf){ /* XXX */
            clicon_err(OE_YANG, EINVAL, "Yang module file revision and in yang does not match: %s(%u) vs %u", filename, revf, revm); 
            goto done;
        }
        /* If ym0 and ym exists, delete the yang with oldest revision 
         * This is a failsafe in case anything else fails
         */
        if (revm && rev0){
            if (revm > rev0) /* Loaded module is older or eq -> remove ym */
                ym = ym0;
            for (j=0; j<yang_len_get(yspec); j++)
                if (yspec->ys_stmt[j] == ym)
                    break;
            ys_prune(yspec, j);
            ys_free(ym);
        }
    }
    if (yang_parse_post(h, yspec, modmin) < 0)
        goto done;
 ok:
    retval = 0;
  done:
    if (dp)
        free(dp);
    if (base)
        free(base);
    if (oldbase)
        free(oldbase);
    return retval;
}

/*! parse yang date-arg string and return a uint32 useful for arithmetics
 * @param[in]  datearg  yang revision string as "YYYY-MM-DD"
 * @param[out] dateint  Integer version as YYYYMMDD
 * @retval     0        OK
 * @retval    -1        Error, eg str is not on the format "YYYY-MM-DD"
 */
int
ys_parse_date_arg(char     *datearg,
                  uint32_t *dateint)
{
    int      retval = -1;
    int      i;
    uint32_t d = 0;
    
    if (strlen(datearg) != 10 || datearg[4] != '-' || datearg[7] != '-'){
        clicon_err(OE_YANG, EINVAL, "Revision date %s, but expected: YYYY-MM-DD", datearg);
        goto done;
    }
    if ((i = cligen_tonum(4, datearg)) < 0){
        clicon_err(OE_YANG, EINVAL, "Revision date %s, but expected: YYYY-MM-DD", datearg);
        goto done;
    }
    d = i*10000; /* year */
    if ((i = cligen_tonum(2, &datearg[5])) < 0){
        clicon_err(OE_YANG, EINVAL, "Revision date %s, but expected: YYYY-MM-DD", datearg);
        goto done;
    }
    d += i*100; /* month */
    if ((i = cligen_tonum(2, &datearg[8])) < 0){
        clicon_err(OE_YANG, EINVAL, "Revision date %s, but expected: YYYY-MM-DD", datearg);
        goto done;
    }
    d += i; /* day */
    *dateint = d;
    retval = 0;
 done:
    return retval;
}

/*! Parse argument as CV and save result in yang cv variable
 *
 * Note that some CV:s are parsed directly (eg fraction-digits) while others are parsed 
 * in third pass (ys_populate). The reason being that all information is not 
 * available in the first pass. Prefer to do stuff in ys_populate
 */
cg_var *
ys_parse(yang_stmt   *ys, 
         enum cv_type cvtype)
{
    int     cvret;
    char   *reason = NULL;
    cg_var *cv = NULL;

    if ((cv = yang_cv_get(ys)) != NULL){
        /* eg mandatory in uses is already set and then copied */
        cv_free(cv);
        yang_cv_set(ys, NULL);
    }
    if ((cv = cv_new(cvtype)) == NULL){
        clicon_err(OE_YANG, errno, "cv_new"); 
        goto done;
    }
    if ((cvret = cv_parse1(yang_argument_get(ys), cv, &reason)) < 0){ /* error */
        clicon_err(OE_YANG, errno, "parsing cv");
        goto done;
    }
    if (cvret == 0){ /* parsing failed */
        clicon_err(OE_YANG, errno, "Parsing CV: %s", reason);
        goto done;
    }
    yang_cv_set(ys, cv);
    /* cvret == 1 means parsing is OK */
  done:
    if (reason)
        free(reason);
    return yang_cv_get(ys);
}

/*! First round yang syntactic statement specific checks. No context checks.
 *
 * Specific syntax checks  and variable creation for stand-alone yang statements.
 * That is, siblings, etc, may not be there. Complete checks are made in
 * ys_populate instead.
 * @param[in] ys       yang statement
 * @param[in] filename Name of parsed file, if any
 * @param[in] extra    Yang extra for cornercases (unknown/extension). Is consumed
 * @retval    0        OK
 * @retval   -1        Error
 *
 * The cv:s created in parse-tree as follows:
 * fraction-digits : Create cv as uint8, check limits [1:8] (must be made in 1st pass)
 * revision: cv as uint32 date: Integer version as YYYYMMDD
 * min-elements: cv as uint32
 * max-elements: cv as uint32, '0' means unbounded
 * @see ys_populate
 */
int
ys_parse_sub(yang_stmt  *ys,
             const char *filename,
             char       *extra)
{
    int        retval = -1;
    uint8_t    fd;
    uint32_t   date = 0;
    char      *arg;
    enum rfc_6020 keyword;
    char      *reason = NULL;
    int        ret;
    uint32_t   minmax;
    cg_var    *cv = NULL;
    yang_stmt *yp;
    
    arg = yang_argument_get(ys);
    keyword = yang_keyword_get(ys);
    switch (keyword){
    case Y_BASE:
    case Y_TYPE:
    case Y_USES:
        /* Invoke next level parser 
         */
        if (yang_schema_nodeid_subparse(yang_argument_get(ys), YA_ID_REF, filename, yang_linenum_get(ys)) < 0)
            goto done;
        break;
    case Y_FRACTION_DIGITS:
        if (ys_parse(ys, CGV_UINT8) == NULL) 
            goto done;
        if ((cv = yang_cv_get(ys)) == NULL){
            clicon_err(OE_YANG, ENOENT, "Unexpected NULL cv");
            goto done;
        }
        fd = cv_uint8_get(cv);
        if (fd < 1 || fd > 18){
            clicon_err(OE_YANG, errno, "%u: Out of range, should be [1:18]", fd);
            goto done;
        }
        break;
    case Y_MUST:
    case Y_WHEN:
        if (xpath_parse(yang_argument_get(ys), NULL) < 0)
            goto done;
        break;
    case Y_REVISION:
    case Y_REVISION_DATE:  /* YYYY-MM-DD encoded as uint32 YYYYMMDD */
        if (ys_parse_date_arg(arg, &date) < 0)
            goto done;
        if ((cv = cv_new(CGV_UINT32)) == NULL){
            clicon_err(OE_YANG, errno, "cv_new"); 
            goto done;
        }
        yang_cv_set(ys, cv);
        cv_uint32_set(cv, date);
        break;
    case Y_STATUS: /* RFC7950 7.21.2: "current", "deprecated", or "obsolete". */
        if (strcmp(arg, "current") &&
            strcmp(arg, "deprecated") &&
            strcmp(arg, "obsolete")){
            clicon_err(OE_YANG, errno, "Invalid status: \"%s\", expected current, deprecated, or obsolete", arg); 
            goto done;

        }
        break;
    case Y_MAX_ELEMENTS:
    case Y_MIN_ELEMENTS:
        if ((cv = cv_new(CGV_UINT32)) == NULL){
            clicon_err(OE_YANG, errno, "cv_new"); 
            goto done;
        }
        yang_cv_set(ys, cv);
        if (keyword == Y_MAX_ELEMENTS &&
            strcmp(arg, "unbounded") == 0)
            cv_uint32_set(cv, 0); /* 0 means unbounded for max */
        else{
            if ((ret = parse_uint32(arg, &minmax, &reason)) < 0){
                clicon_err(OE_YANG, errno, "parse_uint32"); 
                goto done;
            }
            if (ret == 0){
                clicon_err(OE_YANG, EINVAL, "element-min/max parse error: %s", reason); 
                if (reason)
                    free(reason);
                goto done;
            }
            cv_uint32_set(cv, minmax);
        }
        break;
    case Y_MODIFIER:
        if (strcmp(yang_argument_get(ys), "invert-match")){
            clicon_err(OE_YANG, EINVAL, "modifier %s, expected invert-match", yang_argument_get(ys));
            goto done;
        }
        break;
    case Y_IF_FEATURE:
        /* Invoke next level parser on if-feature-expr string. Note do not send ys since 
         * pass 1 is not yet resolved, only check syntax, actual feature check made in next pass
         * @see yang_features
         */
        if (yang_subparse(yang_argument_get(ys), ys, YA_IF_FEATURE, filename, yang_linenum_get(ys), NULL, NULL) < 0)
            goto done;
        break;
    case Y_AUGMENT: /* If parent is module/submodule: absolute-schema-nodeid
                     * If parent is uses: descendant-schema-nodeid 
                     */
        if ((yp = yang_parent_get(ys)) &&
            yang_keyword_get(yp) != Y_USES){
            if (yang_schema_nodeid_subparse(yang_argument_get(ys), YA_ABS_SCHEMANODEID, filename, yang_linenum_get(ys)) < 0)
                goto done;
            break;
        }
        // fall through
    case Y_REFINE:
        /* Invoke next level parser on refine-arg-str / descendant-schema-nodeid
         */
        if (yang_schema_nodeid_subparse(yang_argument_get(ys), YA_DESC_SCHEMANODEID, filename, yang_linenum_get(ys)) < 0)
            goto done;
        break;
    case Y_UNKNOWN:{ /* save (optional) argument in ys_cv */
        if (extra == NULL)
            break;
        if ((cv = cv_new(CGV_STRING)) == NULL){
            clicon_err(OE_YANG, errno, "cv_new"); 
            goto done;
        }
        yang_cv_set(ys, cv);
        if ((ret = cv_parse1(extra, cv, &reason)) < 0){ /* error */
            clicon_err(OE_YANG, errno, "parsing cv");
            goto done;
        }
        if (ret == 0){ /* parsing failed */
            clicon_err(OE_YANG, errno, "Parsing CV: %s", reason);
            goto done;
        }
        break;
    }
    default:
        break;
    }
    retval = 0;
  done:
    if (extra)
        free(extra);
    return retval;
}
