Return the leaf that the path points to and the expanded path arg,
    or None on error.

def validate_leafref_path(ctx, stmt, path_spec, path,
                          accept_non_leaf_target=False,
                          accept_non_config_target=False):
    """Return the leaf that the path points to and the expanded path arg,
    or None on error."""

    pathpos = path.pos

    # Unprefixed paths in typedefs in YANG 1 were underspecified.  In
    # YANG 1.1 the semantics are defined.  The code below is compatible
    # with old pyang for YANG 1 modules.

    # If an un-prefixed identifier is found, it defaults to the
    # module where the path is defined, except if found within
    # a grouping, in which case it defaults to the module where the
    # grouping is used.
    if (path.parent.parent is not None and
        path.parent.parent.keyword == 'typedef'):
        if path.i_module.i_version == '1':
            local_module = path.i_module
        else:
            local_module = stmt.i_module
    elif stmt.keyword == 'module':
        local_module = stmt
    else:
        local_module = stmt.i_module
    if stmt.keyword == 'typedef':
        in_typedef = True
    else:
        in_typedef = False

    def find_identifier(identifier):
        if util.is_prefixed(identifier):
            (prefix, name) = identifier
            pmodule = prefix_to_module(path.i_module, prefix, stmt.pos,
                                       ctx.errors)
            if pmodule is None:
                raise NotFound
            return (pmodule, name)
        elif in_typedef and stmt.i_module.i_version != '1':
            raise Abort
        else: # local identifier
            return (local_module, identifier)

    def is_identifier(x):
        if util.is_local(x):
            return True
        if type(x) == type(()) and len(x) == 2:
            return True
        return False

    def is_predicate(x):
        if type(x) == type(()) and len(x) == 4 and x[0] == 'predicate':
            return True
        return False

    def follow_path(ptr, up, dn):
        path_list = []
        last_skipped = None
        if up == -1: # absolute path
            (pmodule, name) = find_identifier(dn[0])
            ptr = search_child(pmodule.i_children, pmodule.i_modulename, name)
            if not is_submodule_included(path, ptr):
                ptr = None
            if ptr is None:
                # check all our submodules
                for inc in path.i_orig_module.search('include'):
                    submod = ctx.get_module(inc.arg)
                    if submod is not None:
                        ptr = search_child(submod.i_children,
                                           submod.arg, name)
                        if ptr is not None:
                            break
                if ptr is None:
                    err_add(ctx.errors, pathpos, 'LEAFREF_IDENTIFIER_NOT_FOUND',
                            (pmodule.arg, name, stmt.arg, stmt.pos))
                    raise NotFound
            path_list.append(('dn', ptr))
            dn = dn[1:]
        else:
            while up > 0:
                if ptr is None:
                    err_add(ctx.errors, pathpos, 'LEAFREF_TOO_MANY_UP',
                            (stmt.arg, stmt.pos))
                    raise NotFound
                if ptr.keyword in ('augment', 'grouping'):
                    # don't check the path here - check in the expanded tree
                    raise Abort
                ptr = ptr.parent
                if ptr is None:
                    err_add(ctx.errors, pathpos, 'LEAFREF_TOO_MANY_UP',
                            (stmt.arg, stmt.pos))
                    raise NotFound
                while ptr.keyword in ['case', 'choice', 'input', 'output']:
                    if ptr.keyword in ['input', 'output']:
                        last_skipped = ptr.keyword
                    ptr = ptr.parent
                    if ptr is None:
                        err_add(ctx.errors, pathpos, 'LEAFREF_TOO_MANY_UP',
                                (stmt.arg, stmt.pos))
                        raise NotFound
                    # continue after the case, maybe also skip the choice
                if ptr is None:
                    err_add(ctx.errors, pathpos, 'LEAFREF_TOO_MANY_UP',
                            (stmt.arg, stmt.pos))
                    raise NotFound
                path_list.append(('up', ptr))
                up = up - 1
            if ptr is None: # or ptr.keyword == 'grouping':
                err_add(ctx.errors, pathpos, 'LEAFREF_TOO_MANY_UP',
                        (stmt.arg, stmt.pos))
                raise NotFound
        if ptr.keyword in ('augment', 'grouping'):
            # don't check the path here - check in the expanded tree
            raise Abort
        i = 0
        key_list = None
        keys = []
        while i < len(dn):
            if is_identifier(dn[i]) == True:
                (pmodule, name) = find_identifier(dn[i])
                module_name = pmodule.i_modulename
            elif ptr.keyword == 'list': # predicate on a list, good
                key_list = ptr
                keys = []
                # check each predicate
                while i < len(dn) and is_predicate(dn[i]) == True:
                    # unpack the predicate
                    (_tag, keyleaf, pup, pdn) = dn[i]
                    (pmodule, pname) = find_identifier(keyleaf)
                    # make sure the keyleaf is really a key in the list
                    pleaf = search_child(ptr.i_key, pmodule.i_modulename, pname)
                    if pleaf is None:
                        err_add(ctx.errors, pathpos, 'LEAFREF_NO_KEY',
                                (pmodule.arg, pname, stmt.arg, stmt.pos))
                        raise NotFound
                    # make sure it's not already referenced
                    if keyleaf in keys:
                        err_add(ctx.errors, pathpos, 'LEAFREF_MULTIPLE_KEYS',
                                (pmodule.arg, pname, stmt.arg, stmt.pos))
                        raise NotFound
                    keys.append((pmodule.arg, pname))
                    if pup == 0:
                        i = i + 1
                        break
                    # check what this predicate refers to; make sure it's
                    # another leaf; either of type leafref to keyleaf, OR same
                    # type as the keyleaf
                    (xkey_list, x_key, xleaf, _x) = follow_path(stmt, pup, pdn)
                    stmt.i_derefed_leaf = xleaf
                    if xleaf.keyword != 'leaf':
                        err_add(ctx.errors, pathpos,
                                'LEAFREF_BAD_PREDICATE_PTR',
                                (pmodule.arg, pname, xleaf.arg, xleaf.pos))
                        raise NotFound
                    i = i + 1
                continue
            else:
                err_add(ctx.errors, pathpos, 'LEAFREF_BAD_PREDICATE',
                        (ptr.i_module.arg, ptr.arg, stmt.arg, stmt.pos))
                raise NotFound
            if ptr.keyword in _keyword_with_children:
                ptr = search_data_node(ptr.i_children, module_name, name,
                                       last_skipped)
                if not is_submodule_included(path, ptr):
                    ptr = None
                if ptr is None:
                    err_add(ctx.errors, pathpos, 'LEAFREF_IDENTIFIER_NOT_FOUND',
                            (module_name, name, stmt.arg, stmt.pos))
                    raise NotFound
            else:
                err_add(ctx.errors, pathpos, 'LEAFREF_IDENTIFIER_BAD_NODE',
                        (module_name, name, stmt.arg, stmt.pos,
                         util.keyword_to_str(ptr.keyword)))
                raise NotFound
            path_list.append(('dn', ptr))
            i = i + 1
        return (key_list, keys, ptr, path_list)

    try:
        if path_spec is None: # e.g. invalid path
            return None
        (up, dn, derefup, derefdn) = path_spec
        if derefup > 0:
            # first follow the deref
            (key_list, keys, ptr, _x) = follow_path(stmt, derefup, derefdn)
            if ptr.keyword != 'leaf':
                err_add(ctx.errors, pathpos, 'LEAFREF_DEREF_NOT_LEAFREF',
                        (ptr.arg, ptr.pos))
                return None
            if ptr.i_leafref is None:
                err_add(ctx.errors, pathpos, 'LEAFREF_DEREF_NOT_LEAFREF',
                        (ptr.arg, ptr.pos))
                return None
            stmt.i_derefed_leaf = ptr
            # make sure the referenced leaf is expanded
            if ptr.i_leafref_expanded is False:
                v_reference_leaf_leafref(ctx, ptr)
            if ptr.i_leafref_ptr is None:
                return None
            (derefed_stmt, _pos) = ptr.i_leafref_ptr
            if derefed_stmt is None:
                # FIXME: what is this??
                return None
            if not hasattr(derefed_stmt, 'i_is_key'):
                # it follows from the YANG spec which says that predicates
                # are only used for constraining keys that the derefed stmt
                # must be a key
                err_add(ctx.errors, pathpos, 'LEAFREF_DEREF_NOT_KEY',
                        (ptr.arg, ptr.pos,
                         derefed_stmt.arg, derefed_stmt.pos))
                return None
            # split ptr's leafref path into two parts:
            # '/a/b/c' --> '/a/b', 'c'
            m = re_path.match(ptr.i_leafref.i_expanded_path)
            s1 = m.group(1)
            s2 = m.group(2)
            # split the deref path into two parts:
            # 'deref(../a)/b' --> '../a', 'b'
            m = re_deref.match(path.arg)
            d1 = m.group(1)
            d2 = m.group(2)
            expanded_path = "%s[%s = current()/%s]/%s" % \
                (s1, s2, d1, d2)
            (key_list, keys, ptr, path_list) = follow_path(derefed_stmt, up, dn)
        else:
            (key_list, keys, ptr, path_list) = follow_path(stmt, up, dn)
            expanded_path = path.arg
        # ptr is now the node that the leafref path points to
        # check that it is a leaf
        if (ptr.keyword not in ('leaf', 'leaf-list') and
            not accept_non_leaf_target):
            err_add(ctx.errors, pathpos, 'LEAFREF_NOT_LEAF',
                    (stmt.arg, stmt.pos))
            return None
        if (key_list == ptr.parent and
            (ptr.i_module.i_modulename, ptr.arg) in keys):
            err_add(ctx.errors, pathpos, 'LEAFREF_MULTIPLE_KEYS',
                    (ptr.i_module.i_modulename, ptr.arg, stmt.arg, stmt.pos))
        if ((hasattr(stmt, 'i_config') and stmt.i_config == True) and
            hasattr(ptr, 'i_config') and ptr.i_config == False
            and not accept_non_config_target):
            err_add(ctx.errors, pathpos, 'LEAFREF_BAD_CONFIG',
                    (stmt.arg, ptr.arg, ptr.pos))
        if ptr == stmt:
            err_add(ctx.errors, pathpos, 'CIRCULAR_DEPENDENCY',
                    ('leafref', path.arg))
            return None
        return ptr, expanded_path, path_list
    except NotFound:
        return None
    except Abort:
        return None