lib: cache PID & TID in zlog code

[mirror_frr.git] / tools / frr-reload.py

#!/usr/bin/python
# Frr Reloader
# Copyright (C) 2014 Cumulus Networks, Inc.
#
# This file is part of Frr.
#
# Frr is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
# Free Software Foundation; either version 2, or (at your option) any
# later version.
#
# Frr is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Frr; see the file COPYING.  If not, write to the Free
# Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
#  02111-1307, USA.
#
"""
This program
- reads a frr configuration text file
- reads frr's current running configuration via "vtysh -c 'show running'"
- compares the two configs and determines what commands to execute to
  synchronize frr's running configuration with the configuation in the
  text file
"""

from __future__ import print_function, unicode_literals
import argparse
import copy
import logging
import os, os.path
import random
import re
import string
import subprocess
import sys
from collections import OrderedDict

try:
    from ipaddress import IPv6Address, ip_network
except ImportError:
    from ipaddr import IPv6Address, IPNetwork
from pprint import pformat

try:
    dict.iteritems
except AttributeError:
    # Python 3
    def iteritems(d):
        return iter(d.items())


else:
    # Python 2
    def iteritems(d):
        return d.iteritems()


log = logging.getLogger(__name__)


class VtyshException(Exception):
    pass


class Vtysh(object):
    def __init__(self, bindir=None, confdir=None, sockdir=None, pathspace=None):
        self.bindir = bindir
        self.confdir = confdir
        self.pathspace = pathspace
        self.common_args = [os.path.join(bindir or "", "vtysh")]
        if confdir:
            self.common_args.extend(["--config_dir", confdir])
        if sockdir:
            self.common_args.extend(["--vty_socket", sockdir])
        if pathspace:
            self.common_args.extend(["-N", pathspace])

    def _call(self, args, stdin=None, stdout=None, stderr=None):
        kwargs = {}
        if stdin is not None:
            kwargs["stdin"] = stdin
        if stdout is not None:
            kwargs["stdout"] = stdout
        if stderr is not None:
            kwargs["stderr"] = stderr
        return subprocess.Popen(self.common_args + args, **kwargs)

    def _call_cmd(self, command, stdin=None, stdout=None, stderr=None):
        if isinstance(command, list):
            args = [item for sub in command for item in ["-c", sub]]
        else:
            args = ["-c", command]
        return self._call(args, stdin, stdout, stderr)

    def __call__(self, command, stdouts=None):
        """
        Call a CLI command (e.g. "show running-config")

        Output text is automatically redirected, decoded and returned.
        Multiple commands may be passed as list.
        """
        proc = self._call_cmd(command, stdout=subprocess.PIPE)
        stdout, stderr = proc.communicate()
        if proc.wait() != 0:
            if stdouts is not None:
                stdouts.append(stdout.decode("UTF-8"))
            raise VtyshException(
                'vtysh returned status %d for command "%s"' % (proc.returncode, command)
            )
        return stdout.decode("UTF-8")

    def is_config_available(self):
        """
        Return False if no frr daemon is running or some other vtysh session is
        in 'configuration terminal' mode which will prevent us from making any
        configuration changes.
        """

        output = self("configure")

        if "VTY configuration is locked by other VTY" in output:
            log.error("vtysh 'configure' returned\n%s\n" % (output))
            return False

        return True

    def exec_file(self, filename):
        child = self._call(["-f", filename])
        if child.wait() != 0:
            raise VtyshException(
                "vtysh (exec file) exited with status %d" % (child.returncode)
            )

    def mark_file(self, filename, stdin=None):
        child = self._call(
            ["-m", "-f", filename],
            stdout=subprocess.PIPE,
            stdin=subprocess.PIPE,
            stderr=subprocess.PIPE,
        )
        try:
            stdout, stderr = child.communicate()
        except subprocess.TimeoutExpired:
            child.kill()
            stdout, stderr = child.communicate()
            raise VtyshException("vtysh call timed out!")

        if child.wait() != 0:
            raise VtyshException(
                "vtysh (mark file) exited with status %d:\n%s"
                % (child.returncode, stderr)
            )

        return stdout.decode("UTF-8")

    def mark_show_run(self, daemon=None):
        cmd = "show running-config"
        if daemon:
            cmd += " %s" % daemon
        cmd += " no-header"
        show_run = self._call_cmd(cmd, stdout=subprocess.PIPE)
        mark = self._call(
            ["-m", "-f", "-"], stdin=show_run.stdout, stdout=subprocess.PIPE
        )

        show_run.wait()
        stdout, stderr = mark.communicate()
        mark.wait()

        if show_run.returncode != 0:
            raise VtyshException(
                "vtysh (show running-config) exited with status %d:"
                % (show_run.returncode)
            )
        if mark.returncode != 0:
            raise VtyshException(
                "vtysh (mark running-config) exited with status %d" % (mark.returncode)
            )

        return stdout.decode("UTF-8")


class Context(object):

    """
        A Context object represents a section of frr configuration such as:
    !
    interface swp3
     description swp3 -> r8's swp1
     ipv6 nd suppress-ra
     link-detect
    !

    or a single line context object such as this:

    ip forwarding

    """

    def __init__(self, keys, lines):
        self.keys = keys
        self.lines = lines

        # Keep a dictionary of the lines, this is to make it easy to tell if a
        # line exists in this Context
        self.dlines = OrderedDict()

        for ligne in lines:
            self.dlines[ligne] = True

    def add_lines(self, lines):
        """
        Add lines to specified context
        """

        self.lines.extend(lines)

        for ligne in lines:
            self.dlines[ligne] = True


def get_normalized_es_id(line):
    """
    The es-id or es-sys-mac need to be converted to lower case
    """
    sub_strs = ["evpn mh es-id", "evpn mh es-sys-mac"]
    for sub_str in sub_strs:
        obj = re.match(sub_str + " (?P<esi>\S*)", line)
        if obj:
            line = "%s %s" % (sub_str, obj.group("esi").lower())
            break
    return line


def get_normalized_mac_ip_line(line):
    if line.startswith("evpn mh es"):
        return get_normalized_es_id(line)

    if not "ipv6 add" in line:
        return get_normalized_ipv6_line(line)

    return line


class Config(object):

    """
    A frr configuration is stored in a Config object. A Config object
    contains a dictionary of Context objects where the Context keys
    ('router ospf' for example) are our dictionary key.
    """

    def __init__(self, vtysh):
        self.lines = []
        self.contexts = OrderedDict()
        self.vtysh = vtysh

    def load_from_file(self, filename):
        """
        Read configuration from specified file and slurp it into internal memory
        The internal representation has been marked appropriately by passing it
        through vtysh with the -m parameter
        """
        log.info("Loading Config object from file %s", filename)

        file_output = self.vtysh.mark_file(filename)

        for line in file_output.split("\n"):
            line = line.strip()

            # Compress duplicate whitespaces
            line = " ".join(line.split())

            if ":" in line:
                line = get_normalized_mac_ip_line(line)

            """
              vrf static routes can be added in two ways. The old way is:

              "ip route x.x.x.x/x y.y.y.y vrf <vrfname>"

              but it's rendered in the configuration as the new way::

              vrf <vrf-name>
               ip route x.x.x.x/x y.y.y.y
               exit-vrf

              this difference causes frr-reload to not consider them a
              match and delete vrf static routes incorrectly.
              fix the old way to match new "show running" output so a
              proper match is found.
            """
            if (
                line.startswith("ip route ") or line.startswith("ipv6 route ")
            ) and " vrf " in line:
                newline = line.split(" ")
                vrf_index = newline.index("vrf")
                vrf_ctx = newline[vrf_index] + " " + newline[vrf_index + 1]
                del newline[vrf_index : vrf_index + 2]
                newline = " ".join(newline)
                self.lines.append(vrf_ctx)
                self.lines.append(newline)
                self.lines.append("exit-vrf")
                line = "end"

            self.lines.append(line)

        self.load_contexts()

    def load_from_show_running(self, daemon):
        """
        Read running configuration and slurp it into internal memory
        The internal representation has been marked appropriately by passing it
        through vtysh with the -m parameter
        """
        log.info("Loading Config object from vtysh show running")

        config_text = self.vtysh.mark_show_run(daemon)

        for line in config_text.split("\n"):
            line = line.strip()

            if (
                line == "Building configuration..."
                or line == "Current configuration:"
                or not line
            ):
                continue

            self.lines.append(line)

        self.load_contexts()

    def get_lines(self):
        """
        Return the lines read in from the configuration
        """

        return "\n".join(self.lines)

    def get_contexts(self):
        """
        Return the parsed context as strings for display, log etc.
        """

        for (_, ctx) in sorted(iteritems(self.contexts)):
            print(str(ctx) + "\n")

    def save_contexts(self, key, lines):
        """
        Save the provided key and lines as a context
        """

        if not key:
            return

        """
            IP addresses specified in "network" statements, "ip prefix-lists"
            etc. can differ in the host part of the specification the user
            provides and what the running config displays. For example, user
            can specify 11.1.1.1/24, and the running config displays this as
            11.1.1.0/24. Ensure we don't do a needless operation for such
            lines. IS-IS & OSPFv3 have no "network" support.
        """
        re_key_rt = re.match(r"(ip|ipv6)\s+route\s+([A-Fa-f:.0-9/]+)(.*)$", key[0])
        if re_key_rt:
            addr = re_key_rt.group(2)
            if "/" in addr:
                try:
                    if "ipaddress" not in sys.modules:
                        newaddr = IPNetwork(addr)
                        key[0] = "%s route %s/%s%s" % (
                            re_key_rt.group(1),
                            newaddr.network,
                            newaddr.prefixlen,
                            re_key_rt.group(3),
                        )
                    else:
                        newaddr = ip_network(addr, strict=False)
                        key[0] = "%s route %s/%s%s" % (
                            re_key_rt.group(1),
                            str(newaddr.network_address),
                            newaddr.prefixlen,
                            re_key_rt.group(3),
                        )
                except ValueError:
                    pass

        re_key_rt = re.match(
            r"(ip|ipv6)\s+prefix-list(.*)(permit|deny)\s+([A-Fa-f:.0-9/]+)(.*)$", key[0]
        )
        if re_key_rt:
            addr = re_key_rt.group(4)
            if "/" in addr:
                try:
                    if "ipaddress" not in sys.modules:
                        newaddr = "%s/%s" % (
                            IPNetwork(addr).network,
                            IPNetwork(addr).prefixlen,
                        )
                    else:
                        network_addr = ip_network(addr, strict=False)
                        newaddr = "%s/%s" % (
                            str(network_addr.network_address),
                            network_addr.prefixlen,
                        )
                except ValueError:
                    newaddr = addr
            else:
                newaddr = addr

            legestr = re_key_rt.group(5)
            re_lege = re.search(r"(.*)le\s+(\d+)\s+ge\s+(\d+)(.*)", legestr)
            if re_lege:
                legestr = "%sge %s le %s%s" % (
                    re_lege.group(1),
                    re_lege.group(3),
                    re_lege.group(2),
                    re_lege.group(4),
                )

            key[0] = "%s prefix-list%s%s %s%s" % (
                re_key_rt.group(1),
                re_key_rt.group(2),
                re_key_rt.group(3),
                newaddr,
                legestr,
            )

        if lines and key[0].startswith("router bgp"):
            newlines = []
            for line in lines:
                re_net = re.match(r"network\s+([A-Fa-f:.0-9/]+)(.*)$", line)
                if re_net:
                    addr = re_net.group(1)
                    if "/" not in addr and key[0].startswith("router bgp"):
                        # This is most likely an error because with no
                        # prefixlen, BGP treats the prefixlen as 8
                        addr = addr + "/8"

                    try:
                        if "ipaddress" not in sys.modules:
                            newaddr = IPNetwork(addr)
                            line = "network %s/%s %s" % (
                                newaddr.network,
                                newaddr.prefixlen,
                                re_net.group(2),
                            )
                        else:
                            network_addr = ip_network(addr, strict=False)
                            line = "network %s/%s %s" % (
                                str(network_addr.network_address),
                                network_addr.prefixlen,
                                re_net.group(2),
                            )
                        newlines.append(line)
                    except ValueError:
                        # Really this should be an error. Whats a network
                        # without an IP Address following it ?
                        newlines.append(line)
                else:
                    newlines.append(line)
            lines = newlines

        """
          More fixups in user specification and what running config shows.
          "null0" in routes must be replaced by Null0.
        """
        if (
            key[0].startswith("ip route")
            or key[0].startswith("ipv6 route")
            and "null0" in key[0]
        ):
            key[0] = re.sub(r"\s+null0(\s*$)", " Null0", key[0])

        """
          Similar to above, but when the static is in a vrf, it turns into a
          blackhole nexthop for both null0 and Null0.  Fix it accordingly
        """
        if lines and key[0].startswith("vrf "):
            newlines = []
            for line in lines:
                if line.startswith("ip route ") or line.startswith("ipv6 route "):
                    if "null0" in line:
                        line = re.sub(r"\s+null0(\s*$)", " blackhole", line)
                    elif "Null0" in line:
                        line = re.sub(r"\s+Null0(\s*$)", " blackhole", line)
                    newlines.append(line)
                else:
                    newlines.append(line)
            lines = newlines

        if lines:
            if tuple(key) not in self.contexts:
                ctx = Context(tuple(key), lines)
                self.contexts[tuple(key)] = ctx
            else:
                ctx = self.contexts[tuple(key)]
                ctx.add_lines(lines)

        else:
            if tuple(key) not in self.contexts:
                ctx = Context(tuple(key), [])
                self.contexts[tuple(key)] = ctx

    def load_contexts(self):
        """
        Parse the configuration and create contexts for each appropriate block
        """

        current_context_lines = []
        ctx_keys = []

        """
        The end of a context is flagged via the 'end' keyword:

!
interface swp52
 ipv6 nd suppress-ra
 link-detect
!
end
router bgp 10
 bgp router-id 10.0.0.1
 bgp log-neighbor-changes
 no bgp default ipv4-unicast
 neighbor EBGP peer-group
 neighbor EBGP advertisement-interval 1
 neighbor EBGP timers connect 10
 neighbor 2001:40:1:4::6 remote-as 40
 neighbor 2001:40:1:8::a remote-as 40
!
end
 address-family ipv6
 neighbor IBGPv6 activate
 neighbor 2001:10::2 peer-group IBGPv6
 neighbor 2001:10::3 peer-group IBGPv6
 exit-address-family
!
end
 address-family evpn
  neighbor LEAF activate
  advertise-all-vni
  vni 10100
   rd 65000:10100
   route-target import 10.1.1.1:10100
   route-target export 10.1.1.1:10100
  exit-vni
 exit-address-family
!
end
router ospf
 ospf router-id 10.0.0.1
 log-adjacency-changes detail
 timers throttle spf 0 50 5000
!
end
        """

        # The code assumes that its working on the output from the "vtysh -m"
        # command. That provides the appropriate markers to signify end of
        # a context. This routine uses that to build the contexts for the
        # config.
        #
        # There are single line contexts such as "log file /media/node/zebra.log"
        # and multi-line contexts such as "router ospf" and subcontexts
        # within a context such as "address-family" within "router bgp"
        # In each of these cases, the first line of the context becomes the
        # key of the context. So "router bgp 10" is the key for the non-address
        # family part of bgp, "router bgp 10, address-family ipv6 unicast" is
        # the key for the subcontext and so on.
        ctx_keys = []
        main_ctx_key = []
        new_ctx = True

        # the keywords that we know are single line contexts. bgp in this case
        # is not the main router bgp block, but enabling multi-instance
        oneline_ctx_keywords = (
            "access-list ",
            "agentx",
            "allow-external-route-update",
            "bgp ",
            "debug ",
            "domainname ",
            "dump ",
            "enable ",
            "frr ",
            "fpm ",
            "hostname ",
            "ip ",
            "ipv6 ",
            "log ",
            "mpls lsp",
            "mpls label",
            "no ",
            "password ",
            "ptm-enable",
            "router-id ",
            "service ",
            "table ",
            "username ",
            "zebra ",
            "vrrp autoconfigure",
            "evpn mh",
        )

        for line in self.lines:

            if not line:
                continue

            if line.startswith("!") or line.startswith("#"):
                continue

            if (
                len(ctx_keys) == 2
                and ctx_keys[0].startswith("bfd")
                and ctx_keys[1].startswith("profile ")
                and line == "end"
            ):
                log.debug("LINE %-50s: popping from sub context, %-50s", line, ctx_keys)

                if main_ctx_key:
                    self.save_contexts(ctx_keys, current_context_lines)
                    ctx_keys = copy.deepcopy(main_ctx_key)
                    current_context_lines = []
                    continue

            # one line contexts
            # there is one exception though: ldpd accepts a 'router-id' clause
            # as part of its 'mpls ldp' config context. If we are processing
            # ldp configuration and encounter a router-id we should NOT switch
            # to a new context
            if (
                new_ctx is True
                and any(line.startswith(keyword) for keyword in oneline_ctx_keywords)
                and not (
                    ctx_keys
                    and ctx_keys[0].startswith("mpls ldp")
                    and line.startswith("router-id ")
                )
            ):
                self.save_contexts(ctx_keys, current_context_lines)

                # Start a new context
                main_ctx_key = []
                ctx_keys = [
                    line,
                ]
                current_context_lines = []

                log.debug("LINE %-50s: entering new context, %-50s", line, ctx_keys)
                self.save_contexts(ctx_keys, current_context_lines)
                new_ctx = True

            elif line == "end":
                self.save_contexts(ctx_keys, current_context_lines)
                log.debug("LINE %-50s: exiting old context, %-50s", line, ctx_keys)

                # Start a new context
                new_ctx = True
                main_ctx_key = []
                ctx_keys = []
                current_context_lines = []

            elif line == "exit" and ctx_keys[0].startswith("rpki"):
                self.save_contexts(ctx_keys, current_context_lines)
                log.debug("LINE %-50s: exiting old context, %-50s", line, ctx_keys)

                # Start a new context
                new_ctx = True
                main_ctx_key = []
                ctx_keys = []
                current_context_lines = []

            elif line == "exit-vrf":
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines.append(line)
                log.debug(
                    "LINE %-50s: append to current_context_lines, %-50s", line, ctx_keys
                )

                # Start a new context
                new_ctx = True
                main_ctx_key = []
                ctx_keys = []
                current_context_lines = []

            elif (
                line == "exit"
                and len(ctx_keys) > 1
                and ctx_keys[0].startswith("segment-routing")
            ):
                self.save_contexts(ctx_keys, current_context_lines)

                # Start a new context
                ctx_keys = ctx_keys[:-1]
                current_context_lines = []
                log.debug(
                    "LINE %-50s: popping segment routing sub-context to ctx%-50s",
                    line,
                    ctx_keys,
                )

            elif line in ["exit-address-family", "exit", "exit-vnc"]:
                # if this exit is for address-family ipv4 unicast, ignore the pop
                if main_ctx_key:
                    self.save_contexts(ctx_keys, current_context_lines)

                    # Start a new context
                    ctx_keys = copy.deepcopy(main_ctx_key)
                    current_context_lines = []
                    log.debug(
                        "LINE %-50s: popping from subcontext to ctx%-50s",
                        line,
                        ctx_keys,
                    )

            elif line in ["exit-vni", "exit-ldp-if"]:
                if sub_main_ctx_key:
                    self.save_contexts(ctx_keys, current_context_lines)

                    # Start a new context
                    ctx_keys = copy.deepcopy(sub_main_ctx_key)
                    current_context_lines = []
                    log.debug(
                        "LINE %-50s: popping from sub-subcontext to ctx%-50s",
                        line,
                        ctx_keys,
                    )

            elif new_ctx is True:
                if not main_ctx_key:
                    ctx_keys = [
                        line,
                    ]
                else:
                    ctx_keys = copy.deepcopy(main_ctx_key)
                    main_ctx_key = []

                current_context_lines = []
                new_ctx = False
                log.debug("LINE %-50s: entering new context, %-50s", line, ctx_keys)

            elif (
                line.startswith("address-family ")
                or line.startswith("vnc defaults")
                or line.startswith("vnc l2-group")
                or line.startswith("vnc nve-group")
                or line.startswith("peer")
                or line.startswith("key ")
                or line.startswith("member pseudowire")
            ):
                main_ctx_key = []

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug("LINE %-50s: entering sub-context, append to ctx_keys", line)

                if line == "address-family ipv6" and not ctx_keys[0].startswith(
                    "mpls ldp"
                ):
                    ctx_keys.append("address-family ipv6 unicast")
                elif line == "address-family ipv4" and not ctx_keys[0].startswith(
                    "mpls ldp"
                ):
                    ctx_keys.append("address-family ipv4 unicast")
                elif line == "address-family evpn":
                    ctx_keys.append("address-family l2vpn evpn")
                else:
                    ctx_keys.append(line)

            elif (
                line.startswith("vni ")
                and len(ctx_keys) == 2
                and ctx_keys[0].startswith("router bgp")
                and ctx_keys[1] == "address-family l2vpn evpn"
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                sub_main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering sub-sub-context, append to ctx_keys", line
                )
                ctx_keys.append(line)

            elif (
                line.startswith("interface ")
                and len(ctx_keys) == 2
                and ctx_keys[0].startswith("mpls ldp")
                and ctx_keys[1].startswith("address-family")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                sub_main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering sub-sub-context, append to ctx_keys", line
                )
                ctx_keys.append(line)

            elif (
                line.startswith("traffic-eng")
                and len(ctx_keys) == 1
                and ctx_keys[0].startswith("segment-routing")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                log.debug(
                    "LINE %-50s: entering segment routing sub-context, append to ctx_keys",
                    line,
                )
                ctx_keys.append(line)

            elif (
                line.startswith("segment-list ")
                and len(ctx_keys) == 2
                and ctx_keys[0].startswith("segment-routing")
                and ctx_keys[1].startswith("traffic-eng")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                log.debug(
                    "LINE %-50s: entering segment routing sub-context, append to ctx_keys",
                    line,
                )
                ctx_keys.append(line)

            elif (
                line.startswith("policy ")
                and len(ctx_keys) == 2
                and ctx_keys[0].startswith("segment-routing")
                and ctx_keys[1].startswith("traffic-eng")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                log.debug(
                    "LINE %-50s: entering segment routing sub-context, append to ctx_keys",
                    line,
                )
                ctx_keys.append(line)

            elif (
                line.startswith("candidate-path ")
                and line.endswith(" dynamic")
                and len(ctx_keys) == 3
                and ctx_keys[0].startswith("segment-routing")
                and ctx_keys[1].startswith("traffic-eng")
                and ctx_keys[2].startswith("policy")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering candidate-path sub-context, append to ctx_keys",
                    line,
                )
                ctx_keys.append(line)

            elif (
                line.startswith("pcep")
                and len(ctx_keys) == 2
                and ctx_keys[0].startswith("segment-routing")
                and ctx_keys[1].startswith("traffic-eng")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering pcep sub-context, append to ctx_keys", line
                )
                ctx_keys.append(line)

            elif (
                line.startswith("pce-config ")
                and len(ctx_keys) == 3
                and ctx_keys[0].startswith("segment-routing")
                and ctx_keys[1].startswith("traffic-eng")
                and ctx_keys[2].startswith("pcep")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering pce-config sub-context, append to ctx_keys",
                    line,
                )
                ctx_keys.append(line)

            elif (
                line.startswith("pce ")
                and len(ctx_keys) == 3
                and ctx_keys[0].startswith("segment-routing")
                and ctx_keys[1].startswith("traffic-eng")
                and ctx_keys[2].startswith("pcep")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering pce sub-context, append to ctx_keys", line
                )
                ctx_keys.append(line)

            elif (
                line.startswith("pcc")
                and len(ctx_keys) == 3
                and ctx_keys[0].startswith("segment-routing")
                and ctx_keys[1].startswith("traffic-eng")
                and ctx_keys[2].startswith("pcep")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering pcc sub-context, append to ctx_keys", line
                )
                ctx_keys.append(line)

            elif (
                line.startswith("profile ")
                and len(ctx_keys) == 1
                and ctx_keys[0].startswith("bfd")
            ):

                # Save old context first
                self.save_contexts(ctx_keys, current_context_lines)
                current_context_lines = []
                main_ctx_key = copy.deepcopy(ctx_keys)
                log.debug(
                    "LINE %-50s: entering BFD profile sub-context, append to ctx_keys",
                    line,
                )
                ctx_keys.append(line)

            else:
                # Continuing in an existing context, add non-commented lines to it
                current_context_lines.append(line)
                log.debug(
                    "LINE %-50s: append to current_context_lines, %-50s", line, ctx_keys
                )

        # Save the context of the last one
        self.save_contexts(ctx_keys, current_context_lines)


def lines_to_config(ctx_keys, line, delete):
    """
    Return the command as it would appear in frr.conf
    """
    cmd = []

    if line:
        for (i, ctx_key) in enumerate(ctx_keys):
            cmd.append(" " * i + ctx_key)

        line = line.lstrip()
        indent = len(ctx_keys) * " "

        # There are some commands that are on by default so their "no" form will be
        # displayed in the config.  "no bgp default ipv4-unicast" is one of these.
        # If we need to remove this line we do so by adding "bgp default ipv4-unicast",
        # not by doing a "no no bgp default ipv4-unicast"
        if delete:
            if line.startswith("no "):
                cmd.append("%s%s" % (indent, line[3:]))
            else:
                cmd.append("%sno %s" % (indent, line))

        else:
            cmd.append(indent + line)

    # If line is None then we are typically deleting an entire
    # context ('no router ospf' for example)
    else:
        for i, ctx_key in enumerate(ctx_keys[:-1]):
            cmd.append("%s%s" % (" " * i, ctx_key))

        # Only put the 'no' on the last sub-context
        if delete:
            if ctx_keys[-1].startswith("no "):
                cmd.append("%s%s" % (" " * (len(ctx_keys) - 1), ctx_keys[-1][3:]))
            else:
                cmd.append("%sno %s" % (" " * (len(ctx_keys) - 1), ctx_keys[-1]))
        else:
            cmd.append("%s%s" % (" " * (len(ctx_keys) - 1), ctx_keys[-1]))

    return cmd


def get_normalized_ipv6_line(line):
    """
    Return a normalized IPv6 line as produced by frr,
    with all letters in lower case and trailing and leading
    zeros removed, and only the network portion present if
    the IPv6 word is a network
    """
    norm_line = ""
    words = line.split(" ")
    for word in words:
        if ":" in word:
            norm_word = None
            if "/" in word:
                try:
                    if "ipaddress" not in sys.modules:
                        v6word = IPNetwork(word)
                        norm_word = "%s/%s" % (v6word.network, v6word.prefixlen)
                    else:
                        v6word = ip_network(word, strict=False)
                        norm_word = "%s/%s" % (
                            str(v6word.network_address),
                            v6word.prefixlen,
                        )
                except ValueError:
                    pass
            if not norm_word:
                try:
                    norm_word = "%s" % IPv6Address(word)
                except ValueError:
                    norm_word = word
        else:
            norm_word = word
        norm_line = norm_line + " " + norm_word

    return norm_line.strip()


def line_exist(lines, target_ctx_keys, target_line, exact_match=True):
    for (ctx_keys, line) in lines:
        if ctx_keys == target_ctx_keys:
            if exact_match:
                if line == target_line:
                    return True
            else:
                if line.startswith(target_line):
                    return True
    return False


def check_for_exit_vrf(lines_to_add, lines_to_del):

    # exit-vrf is a bit tricky.  If the new config is missing it but we
    # have configs under a vrf, we need to add it at the end to do the
    # right context changes.  If exit-vrf exists in both the running and
    # new config, we cannot delete it or it will break context changes.
    add_exit_vrf = False
    index = 0

    for (ctx_keys, line) in lines_to_add:
        if add_exit_vrf == True:
            if ctx_keys[0] != prior_ctx_key:
                insert_key = ((prior_ctx_key),)
                lines_to_add.insert(index, ((insert_key, "exit-vrf")))
                add_exit_vrf = False

        if ctx_keys[0].startswith("vrf") and line:
            if line != "exit-vrf":
                add_exit_vrf = True
                prior_ctx_key = ctx_keys[0]
            else:
                add_exit_vrf = False
        index += 1

    for (ctx_keys, line) in lines_to_del:
        if line == "exit-vrf":
            if line_exist(lines_to_add, ctx_keys, line):
                lines_to_del.remove((ctx_keys, line))

    return (lines_to_add, lines_to_del)


"""
This method handles deletion of bgp peer group config.
The objective is to delete config lines related to peers
associated with the peer-group and move the peer-group
config line to the end of the lines_to_del list.
"""


def delete_move_lines(lines_to_add, lines_to_del):

    del_dict = dict()
    # Stores the lines to move to the end of the pending list.
    lines_to_del_to_del = []
    # Stores the lines to move to end of the pending list.
    lines_to_del_to_app = []
    found_pg_del_cmd = False

    """
    When "neighbor <pg_name> peer-group" under a bgp instance is removed,
    it also deletes the associated peer config. Any config line below no form of
    peer-group related to a peer are errored out as the peer no longer exists.
    To cleanup peer-group and associated peer(s) configs:
    - Remove all the peers config lines from the pending list (lines_to_del list).
    - Move peer-group deletion line to the end of the pending list, to allow
    removal of any of the peer-group specific configs.

    Create a dictionary of config context (i.e. router bgp vrf x).
    Under each context node, create a dictionary of a peer-group name.
    Append a peer associated to the peer-group into a list under a peer-group node.
    Remove all of the peer associated config lines from the pending list.
    Append peer-group deletion line to end of the pending list.

    Example:
      neighbor underlay peer-group
      neighbor underlay remote-as external
      neighbor underlay advertisement-interval 0
      neighbor underlay timers 3 9
      neighbor underlay timers connect 10
      neighbor swp1 interface peer-group underlay
      neighbor swp1 advertisement-interval 0
      neighbor swp1 timers 3 9
      neighbor swp1 timers connect 10
      neighbor swp2 interface peer-group underlay
      neighbor swp2 advertisement-interval 0
      neighbor swp2 timers 3 9
      neighbor swp2 timers connect 10
      neighbor swp3 interface peer-group underlay
      neighbor uplink1 interface remote-as internal
      neighbor uplink1 advertisement-interval 0
      neighbor uplink1 timers 3 9
      neighbor uplink1 timers connect 10

    New order:
      "router bgp 200  no bgp bestpath as-path multipath-relax"
      "router bgp 200  no neighbor underlay advertisement-interval 0"
      "router bgp 200  no neighbor underlay timers 3 9"
      "router bgp 200  no neighbor underlay timers connect 10"
      "router bgp 200  no neighbor uplink1 advertisement-interval 0"
      "router bgp 200  no neighbor uplink1 timers 3 9"
      "router bgp 200  no neighbor uplink1 timers connect 10"
      "router bgp 200  no neighbor underlay remote-as external"
      "router bgp 200  no neighbor uplink1 interface remote-as internal"
      "router bgp 200  no neighbor underlay peer-group"

    """

    for (ctx_keys, line) in lines_to_del:
        if (
            ctx_keys[0].startswith("router bgp")
            and line
            and line.startswith("neighbor ")
        ):
            """
            When 'neighbor <peer> remote-as <>' is removed it deletes the peer,
            there might be a peer associated config which also needs to be removed
            prior to peer.
            Append the 'neighbor <peer> remote-as <>' to the lines_to_del.
            Example:

             neighbor uplink1 interface remote-as internal
             neighbor uplink1 advertisement-interval 0
             neighbor uplink1 timers 3 9
             neighbor uplink1 timers connect 10

             Move to end:
             neighbor uplink1 advertisement-interval 0
             neighbor uplink1 timers 3 9
             neighbor uplink1 timers connect 10
             ...

             neighbor uplink1 interface remote-as internal

            """
            # 'no neighbor peer [interface] remote-as <>'
            nb_remoteas = "neighbor (\S+) .*remote-as (\S+)"
            re_nb_remoteas = re.search(nb_remoteas, line)
            if re_nb_remoteas:
                lines_to_del_to_app.append((ctx_keys, line))

            """
            {'router bgp 65001': {'PG': [], 'PG1': []},
            'router bgp 65001 vrf vrf1': {'PG': [], 'PG1': []}}
            """
            if ctx_keys[0] not in del_dict:
                del_dict[ctx_keys[0]] = dict()
            # find 'no neighbor <pg_name> peer-group'
            re_pg = re.match("neighbor (\S+) peer-group$", line)
            if re_pg and re_pg.group(1) not in del_dict[ctx_keys[0]]:
                del_dict[ctx_keys[0]][re_pg.group(1)] = list()

    for (ctx_keys, line) in lines_to_del_to_app:
        lines_to_del.remove((ctx_keys, line))
        lines_to_del.append((ctx_keys, line))

    if found_pg_del_cmd == False:
        return (lines_to_add, lines_to_del)

    """
    {'router bgp 65001': {'PG': ['10.1.1.2'], 'PG1': ['10.1.1.21']},
     'router bgp 65001 vrf vrf1': {'PG': ['10.1.1.2'], 'PG1': ['10.1.1.21']}}
    """
    for (ctx_keys, line) in lines_to_del:
        if (
            ctx_keys[0].startswith("router bgp")
            and line
            and line.startswith("neighbor ")
        ):
            if ctx_keys[0] in del_dict:
                for pg_key in del_dict[ctx_keys[0]]:
                    # 'neighbor <peer> [interface] peer-group <pg_name>'
                    nb_pg = "neighbor (\S+) .*peer-group %s$" % pg_key
                    re_nbr_pg = re.search(nb_pg, line)
                    if (
                        re_nbr_pg
                        and re_nbr_pg.group(1) not in del_dict[ctx_keys[0]][pg_key]
                    ):
                        del_dict[ctx_keys[0]][pg_key].append(re_nbr_pg.group(1))

    lines_to_del_to_app = []
    for (ctx_keys, line) in lines_to_del:
        if (
            ctx_keys[0].startswith("router bgp")
            and line
            and line.startswith("neighbor ")
        ):
            if ctx_keys[0] in del_dict:
                for pg in del_dict[ctx_keys[0]]:
                    for nbr in del_dict[ctx_keys[0]][pg]:
                        nb_exp = "neighbor %s .*" % nbr
                        re_nb = re.search(nb_exp, line)
                        # add peer configs to delete list.
                        if re_nb and line not in lines_to_del_to_del:
                            lines_to_del_to_del.append((ctx_keys, line))

                    pg_exp = "neighbor %s peer-group$" % pg
                    re_pg = re.match(pg_exp, line)
                    if re_pg:
                        lines_to_del_to_app.append((ctx_keys, line))

    for (ctx_keys, line) in lines_to_del_to_del:
        lines_to_del.remove((ctx_keys, line))

    for (ctx_keys, line) in lines_to_del_to_app:
        lines_to_del.remove((ctx_keys, line))
        lines_to_del.append((ctx_keys, line))

    return (lines_to_add, lines_to_del)


def ignore_delete_re_add_lines(lines_to_add, lines_to_del):

    # Quite possibly the most confusing (while accurate) variable names in history
    lines_to_add_to_del = []
    lines_to_del_to_del = []

    for (ctx_keys, line) in lines_to_del:
        deleted = False

        # If there is a change in the segment routing block ranges, do it
        # in-place, to avoid requesting spurious label chunks which might fail
        if line and "segment-routing global-block" in line:
            for (add_key, add_line) in lines_to_add:
                if (
                    ctx_keys[0] == add_key[0]
                    and add_line
                    and "segment-routing global-block" in add_line
                ):
                    lines_to_del_to_del.append((ctx_keys, line))
                    break
            continue

        if ctx_keys[0].startswith("router bgp") and line:

            if line.startswith("neighbor "):
                """
                BGP changed how it displays swpX peers that are part of peer-group. Older
                versions of frr would display these on separate lines:
                    neighbor swp1 interface
                    neighbor swp1 peer-group FOO

                but today we display via a single line
                    neighbor swp1 interface peer-group FOO

                This change confuses frr-reload.py so check to see if we are deleting
                    neighbor swp1 interface peer-group FOO

                and adding
                    neighbor swp1 interface
                    neighbor swp1 peer-group FOO

                If so then chop the del line and the corresponding add lines
                """

                re_swpx_int_peergroup = re.search(
                    "neighbor (\S+) interface peer-group (\S+)", line
                )
                re_swpx_int_v6only_peergroup = re.search(
                    "neighbor (\S+) interface v6only peer-group (\S+)", line
                )

                if re_swpx_int_peergroup or re_swpx_int_v6only_peergroup:
                    swpx_interface = None
                    swpx_peergroup = None

                    if re_swpx_int_peergroup:
                        swpx = re_swpx_int_peergroup.group(1)
                        peergroup = re_swpx_int_peergroup.group(2)
                        swpx_interface = "neighbor %s interface" % swpx
                    elif re_swpx_int_v6only_peergroup:
                        swpx = re_swpx_int_v6only_peergroup.group(1)
                        peergroup = re_swpx_int_v6only_peergroup.group(2)
                        swpx_interface = "neighbor %s interface v6only" % swpx

                    swpx_peergroup = "neighbor %s peer-group %s" % (swpx, peergroup)
                    found_add_swpx_interface = line_exist(
                        lines_to_add, ctx_keys, swpx_interface
                    )
                    found_add_swpx_peergroup = line_exist(
                        lines_to_add, ctx_keys, swpx_peergroup
                    )
                    tmp_ctx_keys = tuple(list(ctx_keys))

                    if not found_add_swpx_peergroup:
                        tmp_ctx_keys = list(ctx_keys)
                        tmp_ctx_keys.append("address-family ipv4 unicast")
                        tmp_ctx_keys = tuple(tmp_ctx_keys)
                        found_add_swpx_peergroup = line_exist(
                            lines_to_add, tmp_ctx_keys, swpx_peergroup
                        )

                        if not found_add_swpx_peergroup:
                            tmp_ctx_keys = list(ctx_keys)
                            tmp_ctx_keys.append("address-family ipv6 unicast")
                            tmp_ctx_keys = tuple(tmp_ctx_keys)
                            found_add_swpx_peergroup = line_exist(
                                lines_to_add, tmp_ctx_keys, swpx_peergroup
                            )

                    if found_add_swpx_interface and found_add_swpx_peergroup:
                        deleted = True
                        lines_to_del_to_del.append((ctx_keys, line))
                        lines_to_add_to_del.append((ctx_keys, swpx_interface))
                        lines_to_add_to_del.append((tmp_ctx_keys, swpx_peergroup))

                """
                Changing the bfd timers on neighbors is allowed without doing
                a delete/add process. Since doing a "no neighbor blah bfd ..."
                will cause the peer to bounce unnecessarily, just skip the delete
                and just do the add.
                """
                re_nbr_bfd_timers = re.search(
                    r"neighbor (\S+) bfd (\S+) (\S+) (\S+)", line
                )

                if re_nbr_bfd_timers:
                    nbr = re_nbr_bfd_timers.group(1)
                    bfd_nbr = "neighbor %s" % nbr
                    bfd_search_string = bfd_nbr + r" bfd (\S+) (\S+) (\S+)"

                    for (ctx_keys, add_line) in lines_to_add:
                        if ctx_keys[0].startswith("router bgp"):
                            re_add_nbr_bfd_timers = re.search(
                                bfd_search_string, add_line
                            )

                            if re_add_nbr_bfd_timers:
                                found_add_bfd_nbr = line_exist(
                                    lines_to_add, ctx_keys, bfd_nbr, False
                                )

                                if found_add_bfd_nbr:
                                    lines_to_del_to_del.append((ctx_keys, line))

                """
                We changed how we display the neighbor interface command. Older
                versions of frr would display the following:
                    neighbor swp1 interface
                    neighbor swp1 remote-as external
                    neighbor swp1 capability extended-nexthop

                but today we display via a single line
                    neighbor swp1 interface remote-as external

                and capability extended-nexthop is no longer needed because we
                automatically enable it when the neighbor is of type interface.

                This change confuses frr-reload.py so check to see if we are deleting
                    neighbor swp1 interface remote-as (external|internal|ASNUM)

                and adding
                    neighbor swp1 interface
                    neighbor swp1 remote-as (external|internal|ASNUM)
                    neighbor swp1 capability extended-nexthop

                If so then chop the del line and the corresponding add lines
                """
                re_swpx_int_remoteas = re.search(
                    "neighbor (\S+) interface remote-as (\S+)", line
                )
                re_swpx_int_v6only_remoteas = re.search(
                    "neighbor (\S+) interface v6only remote-as (\S+)", line
                )

                if re_swpx_int_remoteas or re_swpx_int_v6only_remoteas:
                    swpx_interface = None
                    swpx_remoteas = None

                    if re_swpx_int_remoteas:
                        swpx = re_swpx_int_remoteas.group(1)
                        remoteas = re_swpx_int_remoteas.group(2)
                        swpx_interface = "neighbor %s interface" % swpx
                    elif re_swpx_int_v6only_remoteas:
                        swpx = re_swpx_int_v6only_remoteas.group(1)
                        remoteas = re_swpx_int_v6only_remoteas.group(2)
                        swpx_interface = "neighbor %s interface v6only" % swpx

                    swpx_remoteas = "neighbor %s remote-as %s" % (swpx, remoteas)
                    found_add_swpx_interface = line_exist(
                        lines_to_add, ctx_keys, swpx_interface
                    )
                    found_add_swpx_remoteas = line_exist(
                        lines_to_add, ctx_keys, swpx_remoteas
                    )
                    tmp_ctx_keys = tuple(list(ctx_keys))

                    if found_add_swpx_interface and found_add_swpx_remoteas:
                        deleted = True
                        lines_to_del_to_del.append((ctx_keys, line))
                        lines_to_add_to_del.append((ctx_keys, swpx_interface))
                        lines_to_add_to_del.append((tmp_ctx_keys, swpx_remoteas))

            """
            We made the 'bgp bestpath as-path multipath-relax' command
            automatically assume 'no-as-set' since the lack of this option caused
            weird routing problems. When the running config is shown in
            releases with this change, the no-as-set keyword is not shown as it
            is the default. This causes frr-reload to unnecessarily unapply
            this option only to apply it back again, causing unnecessary session
            resets.
            """
            if "multipath-relax" in line:
                re_asrelax_new = re.search(
                    "^bgp\s+bestpath\s+as-path\s+multipath-relax$", line
                )
                old_asrelax_cmd = "bgp bestpath as-path multipath-relax no-as-set"
                found_asrelax_old = line_exist(lines_to_add, ctx_keys, old_asrelax_cmd)

                if re_asrelax_new and found_asrelax_old:
                    deleted = True
                    lines_to_del_to_del.append((ctx_keys, line))
                    lines_to_add_to_del.append((ctx_keys, old_asrelax_cmd))

            """
            If we are modifying the BGP table-map we need to avoid a del/add and
            instead modify the table-map in place via an add.  This is needed to
            avoid installing all routes in the RIB the second the 'no table-map'
            is issued.
            """
            if line.startswith("table-map"):
                found_table_map = line_exist(lines_to_add, ctx_keys, "table-map", False)

                if found_table_map:
                    lines_to_del_to_del.append((ctx_keys, line))

        """
        More old-to-new config handling. ip import-table no longer accepts
        distance, but we honor the old syntax. But 'show running' shows only
        the new syntax. This causes an unnecessary 'no import-table' followed
        by the same old 'ip import-table' which causes perturbations in
        announced routes leading to traffic blackholes. Fix this issue.
        """
        re_importtbl = re.search("^ip\s+import-table\s+(\d+)$", ctx_keys[0])
        if re_importtbl:
            table_num = re_importtbl.group(1)
            for ctx in lines_to_add:
                if ctx[0][0].startswith("ip import-table %s distance" % table_num):
                    lines_to_del_to_del.append(
                        (("ip import-table %s" % table_num,), None)
                    )
                    lines_to_add_to_del.append((ctx[0], None))

        """
        ip/ipv6 prefix-lists and access-lists can be specified without a seq number.
        However, the running config always adds 'seq x', where x is a number
        incremented by 5 for every element of the prefix/access list.
        So, ignore such lines as well. Sample prefix-list and acces-list lines:
             ip prefix-list PR-TABLE-2 seq 5 permit 20.8.2.0/24 le 32
             ip prefix-list PR-TABLE-2 seq 10 permit 20.8.2.0/24 le 32
             ipv6 prefix-list vrfdev6-12 permit 2000:9:2::/64 gt 64
             access-list FOO seq 5 permit 2.2.2.2/32
             ipv6 access-list BAR seq 5 permit 2:2:2::2/128
        """
        re_acl_pfxlst = re.search(
            "^(ip |ipv6 |)(prefix-list|access-list)(\s+\S+\s+)(seq \d+\s+)(permit|deny)(.*)$",
            ctx_keys[0],
        )
        if re_acl_pfxlst:
            found = False
            tmpline = (
                re_acl_pfxlst.group(1)
                + re_acl_pfxlst.group(2)
                + re_acl_pfxlst.group(3)
                + re_acl_pfxlst.group(5)
                + re_acl_pfxlst.group(6)
            )
            for ctx in lines_to_add:
                if ctx[0][0] == tmpline:
                    lines_to_del_to_del.append((ctx_keys, None))
                    lines_to_add_to_del.append(((tmpline,), None))
                    found = True
            """
            If prefix-lists or access-lists are being deleted and
            not added (see comment above), add command with 'no' to
            lines_to_add and remove from lines_to_del to improve
            scaling performance.
            """
            if found is False:
                add_cmd = ("no " + ctx_keys[0],)
                lines_to_add.append((add_cmd, None))
                lines_to_del_to_del.append((ctx_keys, None))

        if (
            len(ctx_keys) == 3
            and ctx_keys[0].startswith("router bgp")
            and ctx_keys[1] == "address-family l2vpn evpn"
            and ctx_keys[2].startswith("vni")
        ):

            re_route_target = (
                re.search("^route-target import (.*)$", line)
                if line is not None
                else False
            )

            if re_route_target:
                rt = re_route_target.group(1).strip()
                route_target_import_line = line
                route_target_export_line = "route-target export %s" % rt
                route_target_both_line = "route-target both %s" % rt

                found_route_target_export_line = line_exist(
                    lines_to_del, ctx_keys, route_target_export_line
                )
                found_route_target_both_line = line_exist(
                    lines_to_add, ctx_keys, route_target_both_line
                )

                """
                If the running configs has
                    route-target import 1:1
                    route-target export 1:1

                and the config we are reloading against has
                    route-target both 1:1

                then we can ignore deleting the import/export and ignore adding the 'both'
                """
                if found_route_target_export_line and found_route_target_both_line:
                    lines_to_del_to_del.append((ctx_keys, route_target_import_line))
                    lines_to_del_to_del.append((ctx_keys, route_target_export_line))
                    lines_to_add_to_del.append((ctx_keys, route_target_both_line))

        # Deleting static routes under a vrf can lead to time-outs if each is sent
        # as separate vtysh -c commands. Change them from being in lines_to_del and
        # put the "no" form in lines_to_add
        if ctx_keys[0].startswith("vrf ") and line:
            if line.startswith("ip route") or line.startswith("ipv6 route"):
                add_cmd = "no " + line
                lines_to_add.append((ctx_keys, add_cmd))
                lines_to_del_to_del.append((ctx_keys, line))

        if not deleted:
            found_add_line = line_exist(lines_to_add, ctx_keys, line)

            if found_add_line:
                lines_to_del_to_del.append((ctx_keys, line))
                lines_to_add_to_del.append((ctx_keys, line))
            else:
                """
                We have commands that used to be displayed in the global part
                of 'router bgp' that are now displayed under 'address-family ipv4 unicast'

                # old way
                router bgp 64900
                  neighbor ISL advertisement-interval 0

                vs.

                # new way
                router bgp 64900
                  address-family ipv4 unicast
                    neighbor ISL advertisement-interval 0

                Look to see if we are deleting it in one format just to add it back in the other
                """
                if (
                    ctx_keys[0].startswith("router bgp")
                    and len(ctx_keys) > 1
                    and ctx_keys[1] == "address-family ipv4 unicast"
                ):
                    tmp_ctx_keys = list(ctx_keys)[:-1]
                    tmp_ctx_keys = tuple(tmp_ctx_keys)

                    found_add_line = line_exist(lines_to_add, tmp_ctx_keys, line)

                    if found_add_line:
                        lines_to_del_to_del.append((ctx_keys, line))
                        lines_to_add_to_del.append((tmp_ctx_keys, line))

    for (ctx_keys, line) in lines_to_del_to_del:
        lines_to_del.remove((ctx_keys, line))

    for (ctx_keys, line) in lines_to_add_to_del:
        lines_to_add.remove((ctx_keys, line))

    return (lines_to_add, lines_to_del)


def ignore_unconfigurable_lines(lines_to_add, lines_to_del):
    """
    There are certain commands that cannot be removed.  Remove
    those commands from lines_to_del.
    """
    lines_to_del_to_del = []

    for (ctx_keys, line) in lines_to_del:

        if (
            ctx_keys[0].startswith("frr version")
            or ctx_keys[0].startswith("frr defaults")
            or ctx_keys[0].startswith("username")
            or ctx_keys[0].startswith("password")
            or ctx_keys[0].startswith("line vty")
            or
            # This is technically "no"able but if we did so frr-reload would
            # stop working so do not let the user shoot themselves in the foot
            # by removing this.
            ctx_keys[0].startswith("service integrated-vtysh-config")
        ):

            log.info('"%s" cannot be removed' % (ctx_keys[-1],))
            lines_to_del_to_del.append((ctx_keys, line))

    for (ctx_keys, line) in lines_to_del_to_del:
        lines_to_del.remove((ctx_keys, line))

    return (lines_to_add, lines_to_del)


def compare_context_objects(newconf, running):
    """
    Create a context diff for the two specified contexts
    """

    # Compare the two Config objects to find the lines that we need to add/del
    lines_to_add = []
    lines_to_del = []
    pollist_to_del = []
    seglist_to_del = []
    pceconf_to_del = []
    pcclist_to_del = []
    candidates_to_add = []
    delete_bgpd = False

    # Find contexts that are in newconf but not in running
    # Find contexts that are in running but not in newconf
    for (running_ctx_keys, running_ctx) in iteritems(running.contexts):

        if running_ctx_keys not in newconf.contexts:

            # We check that the len is 1 here so that we only look at ('router bgp 10')
            # and not ('router bgp 10', 'address-family ipv4 unicast'). The
            # latter could cause a false delete_bgpd positive if ipv4 unicast is in
            # running but not in newconf.
            if "router bgp" in running_ctx_keys[0] and len(running_ctx_keys) == 1:
                delete_bgpd = True
                lines_to_del.append((running_ctx_keys, None))

            # We cannot do 'no interface' or 'no vrf' in FRR, and so deal with it
            elif running_ctx_keys[0].startswith("interface") or running_ctx_keys[
                0
            ].startswith("vrf"):
                for line in running_ctx.lines:
                    lines_to_del.append((running_ctx_keys, line))

            # If this is an address-family under 'router bgp' and we are already deleting the
            # entire 'router bgp' context then ignore this sub-context
            elif (
                "router bgp" in running_ctx_keys[0]
                and len(running_ctx_keys) > 1
                and delete_bgpd
            ):
                continue

            # Delete an entire vni sub-context under "address-family l2vpn evpn"
            elif (
                "router bgp" in running_ctx_keys[0]
                and len(running_ctx_keys) > 2
                and running_ctx_keys[1].startswith("address-family l2vpn evpn")
                and running_ctx_keys[2].startswith("vni ")
            ):
                lines_to_del.append((running_ctx_keys, None))

            elif (
                "router bgp" in running_ctx_keys[0]
                and len(running_ctx_keys) > 1
                and running_ctx_keys[1].startswith("address-family")
            ):
                # There's no 'no address-family' support and so we have to
                # delete each line individually again
                for line in running_ctx.lines:
                    lines_to_del.append((running_ctx_keys, line))

            # Some commands can happen at higher counts that make
            # doing vtysh -c inefficient (and can time out.)  For
            # these commands, instead of adding them to lines_to_del,
            # add the "no " version to lines_to_add.
            elif running_ctx_keys[0].startswith("ip route") or running_ctx_keys[
                0
            ].startswith("ipv6 route"):
                add_cmd = ("no " + running_ctx_keys[0],)
                lines_to_add.append((add_cmd, None))

            # if this an interface sub-subcontext in an address-family block in ldpd and
            # we are already deleting the whole context, then ignore this
            elif (
                len(running_ctx_keys) > 2
                and running_ctx_keys[0].startswith("mpls ldp")
                and running_ctx_keys[1].startswith("address-family")
                and (running_ctx_keys[:2], None) in lines_to_del
            ):
                continue

            # same thing for a pseudowire sub-context inside an l2vpn context
            elif (
                len(running_ctx_keys) > 1
                and running_ctx_keys[0].startswith("l2vpn")
                and running_ctx_keys[1].startswith("member pseudowire")
                and (running_ctx_keys[:1], None) in lines_to_del
            ):
                continue

            # Segment routing and traffic engineering never need to be deleted
            elif (
                running_ctx_keys[0].startswith("segment-routing")
                and len(running_ctx_keys) < 3
            ):
                continue

            # Neither the pcep command
            elif (
                len(running_ctx_keys) == 3
                and running_ctx_keys[0].startswith("segment-routing")
                and running_ctx_keys[2].startswith("pcep")
            ):
                continue

            # Segment lists can only be deleted after we removed all the candidate paths that
            # use them, so add them to a separate array that is going to be appended at the end
            elif (
                len(running_ctx_keys) == 3
                and running_ctx_keys[0].startswith("segment-routing")
                and running_ctx_keys[2].startswith("segment-list")
            ):
                seglist_to_del.append((running_ctx_keys, None))

            # Policies must be deleted after there candidate path, to be sure
            # we add them to a separate array that is going to be appended at the end
            elif (
                len(running_ctx_keys) == 3
                and running_ctx_keys[0].startswith("segment-routing")
                and running_ctx_keys[2].startswith("policy")
            ):
                pollist_to_del.append((running_ctx_keys, None))

            # pce-config must be deleted after the pce, to be sure we add them
            # to a separate array that is going to be appended at the end
            elif (
                len(running_ctx_keys) >= 4
                and running_ctx_keys[0].startswith("segment-routing")
                and running_ctx_keys[3].startswith("pce-config")
            ):
                pceconf_to_del.append((running_ctx_keys, None))

            # pcc must be deleted after the pce and pce-config too
            elif (
                len(running_ctx_keys) >= 4
                and running_ctx_keys[0].startswith("segment-routing")
                and running_ctx_keys[3].startswith("pcc")
            ):
                pcclist_to_del.append((running_ctx_keys, None))

            # Non-global context
            elif running_ctx_keys and not any(
                "address-family" in key for key in running_ctx_keys
            ):
                lines_to_del.append((running_ctx_keys, None))

            elif running_ctx_keys and not any("vni" in key for key in running_ctx_keys):
                lines_to_del.append((running_ctx_keys, None))

            # Global context
            else:
                for line in running_ctx.lines:
                    lines_to_del.append((running_ctx_keys, line))

    # if we have some policies commands to delete, append them to lines_to_del
    if len(pollist_to_del) > 0:
        lines_to_del.extend(pollist_to_del)

    # if we have some segment list commands to delete, append them to lines_to_del
    if len(seglist_to_del) > 0:
        lines_to_del.extend(seglist_to_del)

    # if we have some pce list commands to delete, append them to lines_to_del
    if len(pceconf_to_del) > 0:
        lines_to_del.extend(pceconf_to_del)

    # if we have some pcc list commands to delete, append them to lines_to_del
    if len(pcclist_to_del) > 0:
        lines_to_del.extend(pcclist_to_del)

    # Find the lines within each context to add
    # Find the lines within each context to del
    for (newconf_ctx_keys, newconf_ctx) in iteritems(newconf.contexts):

        if newconf_ctx_keys in running.contexts:
            running_ctx = running.contexts[newconf_ctx_keys]

            for line in newconf_ctx.lines:
                if line not in running_ctx.dlines:

                    # candidate paths can only be added after the policy and segment list,
                    # so add them to a separate array that is going to be appended at the end
                    if (
                        len(newconf_ctx_keys) == 3
                        and newconf_ctx_keys[0].startswith("segment-routing")
                        and newconf_ctx_keys[2].startswith("policy ")
                        and line.startswith("candidate-path ")
                    ):
                        candidates_to_add.append((newconf_ctx_keys, line))

                    else:
                        lines_to_add.append((newconf_ctx_keys, line))

            for line in running_ctx.lines:
                if line not in newconf_ctx.dlines:
                    lines_to_del.append((newconf_ctx_keys, line))

    for (newconf_ctx_keys, newconf_ctx) in iteritems(newconf.contexts):

        if newconf_ctx_keys not in running.contexts:

            # candidate paths can only be added after the policy and segment list,
            # so add them to a separate array that is going to be appended at the end
            if (
                len(newconf_ctx_keys) == 4
                and newconf_ctx_keys[0].startswith("segment-routing")
                and newconf_ctx_keys[3].startswith("candidate-path")
            ):
                candidates_to_add.append((newconf_ctx_keys, None))
                for line in newconf_ctx.lines:
                    candidates_to_add.append((newconf_ctx_keys, line))

            else:
                lines_to_add.append((newconf_ctx_keys, None))

                for line in newconf_ctx.lines:
                    lines_to_add.append((newconf_ctx_keys, line))

    # if we have some candidate paths commands to add, append them to lines_to_add
    if len(candidates_to_add) > 0:
        lines_to_add.extend(candidates_to_add)

    (lines_to_add, lines_to_del) = check_for_exit_vrf(lines_to_add, lines_to_del)
    (lines_to_add, lines_to_del) = ignore_delete_re_add_lines(
        lines_to_add, lines_to_del
    )
    (lines_to_add, lines_to_del) = delete_move_lines(lines_to_add, lines_to_del)
    (lines_to_add, lines_to_del) = ignore_unconfigurable_lines(
        lines_to_add, lines_to_del
    )

    return (lines_to_add, lines_to_del)


if __name__ == "__main__":
    # Command line options
    parser = argparse.ArgumentParser(
        description="Dynamically apply diff in frr configs"
    )
    parser.add_argument(
        "--input", help='Read running config from file instead of "show running"'
    )
    group = parser.add_mutually_exclusive_group(required=True)
    group.add_argument(
        "--reload", action="store_true", help="Apply the deltas", default=False
    )
    group.add_argument(
        "--test", action="store_true", help="Show the deltas", default=False
    )
    level_group = parser.add_mutually_exclusive_group()
    level_group.add_argument(
        "--debug",
        action="store_true",
        help="Enable debugs (synonym for --log-level=debug)",
        default=False,
    )
    level_group.add_argument(
        "--log-level",
        help="Log level",
        default="info",
        choices=("critical", "error", "warning", "info", "debug"),
    )
    parser.add_argument(
        "--stdout", action="store_true", help="Log to STDOUT", default=False
    )
    parser.add_argument(
        "--pathspace",
        "-N",
        metavar="NAME",
        help="Reload specified path/namespace",
        default=None,
    )
    parser.add_argument("filename", help="Location of new frr config file")
    parser.add_argument(
        "--overwrite",
        action="store_true",
        help="Overwrite frr.conf with running config output",
        default=False,
    )
    parser.add_argument(
        "--bindir", help="path to the vtysh executable", default="/usr/bin"
    )
    parser.add_argument(
        "--confdir", help="path to the daemon config files", default="/etc/frr"
    )
    parser.add_argument(
        "--rundir", help="path for the temp config file", default="/var/run/frr"
    )
    parser.add_argument(
        "--vty_socket",
        help="socket to be used by vtysh to connect to the daemons",
        default=None,
    )
    parser.add_argument(
        "--daemon", help="daemon for which want to replace the config", default=""
    )

    args = parser.parse_args()

    # Logging
    # For --test log to stdout
    # For --reload log to /var/log/frr/frr-reload.log
    if args.test or args.stdout:
        logging.basicConfig(format="%(asctime)s %(levelname)5s: %(message)s")

        # Color the errors and warnings in red
        logging.addLevelName(
            logging.ERROR, "\033[91m  %s\033[0m" % logging.getLevelName(logging.ERROR)
        )
        logging.addLevelName(
            logging.WARNING, "\033[91m%s\033[0m" % logging.getLevelName(logging.WARNING)
        )

    elif args.reload:
        if not os.path.isdir("/var/log/frr/"):
            os.makedirs("/var/log/frr/")

        logging.basicConfig(
            filename="/var/log/frr/frr-reload.log",
            format="%(asctime)s %(levelname)5s: %(message)s",
        )

    # argparse should prevent this from happening but just to be safe...
    else:
        raise Exception("Must specify --reload or --test")
    log = logging.getLogger(__name__)

    if args.debug:
        log.setLevel(logging.DEBUG)
    else:
        log.setLevel(args.log_level.upper())

    if args.reload and not args.stdout:
        # Additionally send errors and above to STDOUT, with no metadata,
        # when we are logging to a file. This specifically does not follow
        # args.log_level, and is analagous to behaviour in earlier versions
        # which additionally logged most errors using print().

        stdout_hdlr = logging.StreamHandler(sys.stdout)
        stdout_hdlr.setLevel(logging.ERROR)
        stdout_hdlr.setFormatter(logging.Formatter())
        log.addHandler(stdout_hdlr)

    # Verify the new config file is valid
    if not os.path.isfile(args.filename):
        log.error("Filename %s does not exist" % args.filename)
        sys.exit(1)

    if not os.path.getsize(args.filename):
        log.error("Filename %s is an empty file" % args.filename)
        sys.exit(1)

    # Verify that confdir is correct
    if not os.path.isdir(args.confdir):
        log.error("Confdir %s is not a valid path" % args.confdir)
        sys.exit(1)

    # Verify that bindir is correct
    if not os.path.isdir(args.bindir) or not os.path.isfile(args.bindir + "/vtysh"):
        log.error("Bindir %s is not a valid path to vtysh" % args.bindir)
        sys.exit(1)

    # verify that the vty_socket, if specified, is valid
    if args.vty_socket and not os.path.isdir(args.vty_socket):
        log.error("vty_socket %s is not a valid path" % args.vty_socket)
        sys.exit(1)

    # verify that the daemon, if specified, is valid
    if args.daemon and args.daemon not in [
        "zebra",
        "bgpd",
        "fabricd",
        "isisd",
        "ospf6d",
        "ospfd",
        "pbrd",
        "pimd",
        "ripd",
        "ripngd",
        "sharpd",
        "staticd",
        "vrrpd",
        "ldpd",
        "pathd",
        "bfdd",
    ]:
        msg = "Daemon %s is not a valid option for 'show running-config'" % args.daemon
        print(msg)
        log.error(msg)
        sys.exit(1)

    vtysh = Vtysh(args.bindir, args.confdir, args.vty_socket, args.pathspace)

    # Verify that 'service integrated-vtysh-config' is configured
    if args.pathspace:
        vtysh_filename = args.confdir + "/" + args.pathspace + "/vtysh.conf"
    else:
        vtysh_filename = args.confdir + "/vtysh.conf"
    service_integrated_vtysh_config = True

    if os.path.isfile(vtysh_filename):
        with open(vtysh_filename, "r") as fh:
            for line in fh.readlines():
                line = line.strip()

                if line == "no service integrated-vtysh-config":
                    service_integrated_vtysh_config = False
                    break

    if not service_integrated_vtysh_config and not args.daemon:
        log.error(
            "'service integrated-vtysh-config' is not configured, this is required for 'service frr reload'"
        )
        sys.exit(1)

    log.info('Called via "%s"', str(args))

    # Create a Config object from the config generated by newconf
    newconf = Config(vtysh)
    try:
        newconf.load_from_file(args.filename)
        reload_ok = True
    except VtyshException as ve:
        log.error("vtysh failed to process new configuration: {}".format(ve))
        reload_ok = False

    if args.test:

        # Create a Config object from the running config
        running = Config(vtysh)

        if args.input:
            running.load_from_file(args.input)
        else:
            running.load_from_show_running(args.daemon)

        (lines_to_add, lines_to_del) = compare_context_objects(newconf, running)
        lines_to_configure = []

        if lines_to_del:
            print("\nLines To Delete")
            print("===============")

            for (ctx_keys, line) in lines_to_del:

                if line == "!":
                    continue

                cmd = "\n".join(lines_to_config(ctx_keys, line, True))
                lines_to_configure.append(cmd)
                print(cmd)

        if lines_to_add:
            print("\nLines To Add")
            print("============")

            for (ctx_keys, line) in lines_to_add:

                if line == "!":
                    continue

                cmd = "\n".join(lines_to_config(ctx_keys, line, False))
                lines_to_configure.append(cmd)
                print(cmd)

    elif args.reload:

        # We will not be able to do anything, go ahead and exit(1)
        if not vtysh.is_config_available():
            sys.exit(1)

        log.debug("New Frr Config\n%s", newconf.get_lines())

        # This looks a little odd but we have to do this twice...here is why
        # If the user had this running bgp config:
        #
        # router bgp 10
        #  neighbor 1.1.1.1 remote-as 50
        #  neighbor 1.1.1.1 route-map FOO out
        #
        # and this config in the newconf config file
        #
        # router bgp 10
        #  neighbor 1.1.1.1 remote-as 999
        #  neighbor 1.1.1.1 route-map FOO out
        #
        #
        # Then the script will do
        # - no neighbor 1.1.1.1 remote-as 50
        # - neighbor 1.1.1.1 remote-as 999
        #
        # The problem is the "no neighbor 1.1.1.1 remote-as 50" will also remove
        # the "neighbor 1.1.1.1 route-map FOO out" line...so we compare the
        # configs again to put this line back.

        # There are many keywords in FRR that can only appear one time under
        # a context, take "bgp router-id" for example. If the config that we are
        # reloading against has the following:
        #
        # router bgp 10
        #   bgp router-id 1.1.1.1
        #   bgp router-id 2.2.2.2
        #
        # The final config needs to contain "bgp router-id 2.2.2.2". On the
        # first pass we will add "bgp router-id 2.2.2.2" but then on the second
        # pass we will see that "bgp router-id 1.1.1.1" is missing and add that
        # back which cancels out the "bgp router-id 2.2.2.2". The fix is for the
        # second pass to include all of the "adds" from the first pass.
        lines_to_add_first_pass = []

        for x in range(2):
            running = Config(vtysh)
            running.load_from_show_running(args.daemon)
            log.debug("Running Frr Config (Pass #%d)\n%s", x, running.get_lines())

            (lines_to_add, lines_to_del) = compare_context_objects(newconf, running)

            if x == 0:
                lines_to_add_first_pass = lines_to_add
            else:
                lines_to_add.extend(lines_to_add_first_pass)

            # Only do deletes on the first pass. The reason being if we
            # configure a bgp neighbor via "neighbor swp1 interface" FRR
            # will automatically add:
            #
            # interface swp1
            #  ipv6 nd ra-interval 10
            #  no ipv6 nd suppress-ra
            # !
            #
            # but those lines aren't in the config we are reloading against so
            # on the 2nd pass they will show up in lines_to_del.  This could
            # apply to other scenarios as well where configuring FOO adds BAR
            # to the config.
            if lines_to_del and x == 0:
                for (ctx_keys, line) in lines_to_del:

                    if line == "!":
                        continue

                    # 'no' commands are tricky, we can't just put them in a file and
                    # vtysh -f that file. See the next comment for an explanation
                    # of their quirks
                    cmd = lines_to_config(ctx_keys, line, True)
                    original_cmd = cmd

                    # Some commands in frr are picky about taking a "no" of the entire line.
                    # OSPF is bad about this, you can't "no" the entire line, you have to "no"
                    # only the beginning. If we hit one of these command an exception will be
                    # thrown.  Catch it and remove the last '-c', 'FOO' from cmd and try again.
                    #
                    # Example:
                    # frr(config-if)# ip ospf authentication message-digest 1.1.1.1
                    # frr(config-if)# no ip ospf authentication message-digest 1.1.1.1
                    #  % Unknown command.
                    # frr(config-if)# no ip ospf authentication message-digest
                    #  % Unknown command.
                    # frr(config-if)# no ip ospf authentication
                    # frr(config-if)#

                    stdouts = []
                    while True:
                        try:
                            vtysh(["configure"] + cmd, stdouts)

                        except VtyshException:

                            # - Pull the last entry from cmd (this would be
                            #   'no ip ospf authentication message-digest 1.1.1.1' in
                            #   our example above
                            # - Split that last entry by whitespace and drop the last word
                            log.info("Failed to execute %s", " ".join(cmd))
                            last_arg = cmd[-1].split(" ")

                            if len(last_arg) <= 2:
                                log.error(
                                    '"%s" we failed to remove this command',
                                    " -- ".join(original_cmd),
                                )
                                # Log first error msg for original_cmd
                                if stdouts:
                                    log.error(stdouts[0])
                                reload_ok = False
                                break

                            new_last_arg = last_arg[0:-1]
                            cmd[-1] = " ".join(new_last_arg)
                        else:
                            log.info('Executed "%s"', " ".join(cmd))
                            break

            if lines_to_add:
                lines_to_configure = []

                for (ctx_keys, line) in lines_to_add:

                    if line == "!":
                        continue

                    # Don't run "no" commands twice since they can error
                    # out the second time due to first deletion
                    if x == 1 and ctx_keys[0].startswith("no "):
                        continue

                    cmd = "\n".join(lines_to_config(ctx_keys, line, False)) + "\n"
                    lines_to_configure.append(cmd)

                if lines_to_configure:
                    random_string = "".join(
                        random.SystemRandom().choice(
                            string.ascii_uppercase + string.digits
                        )
                        for _ in range(6)
                    )

                    filename = args.rundir + "/reload-%s.txt" % random_string
                    log.info("%s content\n%s" % (filename, pformat(lines_to_configure)))

                    with open(filename, "w") as fh:
                        for line in lines_to_configure:
                            fh.write(line + "\n")

                    try:
                        vtysh.exec_file(filename)
                    except VtyshException as e:
                        log.warning("frr-reload.py failed due to\n%s" % e.args)
                        reload_ok = False
                    os.unlink(filename)

        # Make these changes persistent
        target = str(args.confdir + "/frr.conf")
        if args.overwrite or (not args.daemon and args.filename != target):
            vtysh("write")

    if not reload_ok:
        sys.exit(1)