# Copyright (C) 2014 Nippon Telegraph and Telephone Corporation.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#    http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
# implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""
 Defines base data types and models required specifically for VRF support.
"""

import abc
import logging
import six

from ryu.lib.packet.bgp import BGP_ATTR_TYPE_ORIGIN
from ryu.lib.packet.bgp import BGP_ATTR_TYPE_AS_PATH
from ryu.lib.packet.bgp import BGP_ATTR_TYPE_EXTENDED_COMMUNITIES
from ryu.lib.packet.bgp import BGP_ATTR_TYEP_PMSI_TUNNEL_ATTRIBUTE
from ryu.lib.packet.bgp import BGP_ATTR_TYPE_MULTI_EXIT_DISC
from ryu.lib.packet.bgp import BGPPathAttributeOrigin
from ryu.lib.packet.bgp import BGPPathAttributeAsPath
from ryu.lib.packet.bgp import BGPPathAttributeExtendedCommunities
from ryu.lib.packet.bgp import BGPTwoOctetAsSpecificExtendedCommunity
from ryu.lib.packet.bgp import BGPPathAttributeMultiExitDisc
from ryu.lib.packet.bgp import BGPEncapsulationExtendedCommunity
from ryu.lib.packet.bgp import BGPPathAttributePmsiTunnel
from ryu.lib.packet.bgp import PmsiTunnelIdIngressReplication
from ryu.lib.packet.bgp import RF_L2_EVPN
from ryu.lib.packet.bgp import EvpnMacIPAdvertisementNLRI

from ryu.services.protocols.bgp.base import OrderedDict
from ryu.services.protocols.bgp.constants import VPN_TABLE
from ryu.services.protocols.bgp.constants import VRF_TABLE
from ryu.services.protocols.bgp.info_base.base import Destination
from ryu.services.protocols.bgp.info_base.base import Path
from ryu.services.protocols.bgp.info_base.base import Table
from ryu.services.protocols.bgp.utils.stats import LOCAL_ROUTES
from ryu.services.protocols.bgp.utils.stats import REMOTE_ROUTES
from ryu.services.protocols.bgp.utils.stats import RESOURCE_ID
from ryu.services.protocols.bgp.utils.stats import RESOURCE_NAME

LOG = logging.getLogger('bgpspeaker.info_base.vrf')


@six.add_metaclass(abc.ABCMeta)
class VrfTable(Table):
    """Virtual Routing and Forwarding information base.
     Keeps destination imported to given vrf in represents.
     """

    ROUTE_FAMILY = None
    VPN_ROUTE_FAMILY = None
    NLRI_CLASS = None
    VRF_PATH_CLASS = None
    VRF_DEST_CLASS = None

    def __init__(self, vrf_conf, core_service, signal_bus):
        Table.__init__(self, vrf_conf.route_dist, core_service, signal_bus)
        self._vrf_conf = vrf_conf
        self._import_maps = []
        self.init_import_maps(vrf_conf.import_maps)

    def init_import_maps(self, import_maps):
        LOG.debug(
            "Initializing import maps (%s) for %r", import_maps, self
        )
        del self._import_maps[:]
        importmap_manager = self._core_service.importmap_manager
        for name in import_maps:
            import_map = importmap_manager.get_import_map_by_name(name)
            if import_map is None:
                raise KeyError('No import map with name %s' % name)
            self._import_maps.append(import_map)

    @property
    def import_rts(self):
        return self._vrf_conf.import_rts

    @property
    def vrf_conf(self):
        return self._vrf_conf

    def _table_key(self, nlri):
        """Return a key that will uniquely identify this NLRI inside
        this table.
        """
        # Note: We use `prefix` representation of the NLRI, because
        # BGP route can be identified without the route distinguisher
        # value in the VRF space.
        return nlri.prefix

    def _create_dest(self, nlri):
        return self.VRF_DEST_CLASS(self, nlri)

    def append_import_map(self, import_map):
        self._import_maps.append(import_map)

    def remove_import_map(self, import_map):
        self._import_maps.remove(import_map)

    def get_stats_summary_dict(self):
        """Returns count of local and remote paths."""

        remote_route_count = 0
        local_route_count = 0
        for dest in self.values():
            for path in dest.known_path_list:
                if (hasattr(path.source, 'version_num') or
                        path.source == VPN_TABLE):
                    remote_route_count += 1
                else:
                    local_route_count += 1
        return {RESOURCE_ID: self._vrf_conf.id,
                RESOURCE_NAME: self._vrf_conf.name,
                REMOTE_ROUTES: remote_route_count,
                LOCAL_ROUTES: local_route_count}

    def import_vpn_paths_from_table(self, vpn_table, import_rts=None):
        for vpn_dest in vpn_table.values():
            vpn_path = vpn_dest.best_path
            if not vpn_path:
                continue

            if import_rts is None:
                import_rts = set(self.import_rts)
            else:
                import_rts = set(import_rts)

            path_rts = vpn_path.get_rts()
            if import_rts.intersection(path_rts):
                # TODO(PH): When (re-)implementing extranet, check what should
                # be the label reported back to NC for local paths coming from
                # other VRFs.
                self.import_vpn_path(vpn_path)

    def import_vpn_path(self, vpn_path):
        """Imports `vpnv(4|6)_path` into `vrf(4|6)_table` or `evpn_path`
        into vrfevpn_table`.

        :Parameters:
            - `vpn_path`: (Path) VPN path that will be cloned and imported
            into VRF.
        Note: Does not do any checking if this import is valid.
        """
        assert vpn_path.route_family == self.VPN_ROUTE_FAMILY
        # If source of given vpnv4 path is NC we import it to given VRF
        # table because of extranet setting. Hence we identify source of
        # EXTRANET prefixes as VRF_TABLE, else VPN_TABLE.
        source = vpn_path.source
        if not source:
            source = VRF_TABLE

        if self.VPN_ROUTE_FAMILY == RF_L2_EVPN:
            # Because NLRI class is the same if the route family is EVPN,
            # we re-use the NLRI instance.
            vrf_nlri = vpn_path.nlri
        else:  # self.VPN_ROUTE_FAMILY in [RF_IPv4_VPN, RF_IPv6_VPN]
            # Copy NLRI instance
            ip, masklen = vpn_path.nlri.prefix.split('/')
            vrf_nlri = self.NLRI_CLASS(length=int(masklen), addr=ip)

        vrf_path = self.VRF_PATH_CLASS(
            puid=self.VRF_PATH_CLASS.create_puid(
                vpn_path.nlri.route_dist,
                vpn_path.nlri.prefix),
            source=source,
            nlri=vrf_nlri,
            src_ver_num=vpn_path.source_version_num,
            pattrs=vpn_path.pathattr_map,
            nexthop=vpn_path.nexthop,
            is_withdraw=vpn_path.is_withdraw,
            label_list=getattr(vpn_path.nlri, 'label_list', None),
        )
        if self._is_vrf_path_already_in_table(vrf_path):
            return None

        if self._is_vrf_path_filtered_out_by_import_maps(vrf_path):
            return None
        else:
            vrf_dest = self.insert(vrf_path)
            self._signal_bus.dest_changed(vrf_dest)

    def _is_vrf_path_filtered_out_by_import_maps(self, vrf_path):
        for import_map in self._import_maps:
            if import_map.match(vrf_path):
                return True

        return False

    def _is_vrf_path_already_in_table(self, vrf_path):
        dest = self._get_dest(vrf_path.nlri)
        if dest is None:
            return False
        return vrf_path in dest.known_path_list

    def apply_import_maps(self):
        changed_dests = []
        for dest in self.values():
            assert isinstance(dest, VrfDest)
            for import_map in self._import_maps:
                for path in dest.known_path_list:
                    if import_map.match(path):
                        dest.withdraw_path(path)
                        changed_dests.append(dest)
        return changed_dests

    def insert_vrf_path(self, nlri, next_hop=None,
                        gen_lbl=False, is_withdraw=False, **kwargs):
        assert nlri
        pattrs = None
        label_list = []
        vrf_conf = self.vrf_conf
        if not is_withdraw:
            # Create a dictionary for path-attrs.
            pattrs = OrderedDict()

            # MpReachNlri and/or MpUnReachNlri attribute info. is contained
            # in the path. Hence we do not add these attributes here.
            from ryu.services.protocols.bgp.core import EXPECTED_ORIGIN

            pattrs[BGP_ATTR_TYPE_ORIGIN] = BGPPathAttributeOrigin(
                EXPECTED_ORIGIN)
            pattrs[BGP_ATTR_TYPE_AS_PATH] = BGPPathAttributeAsPath([])
            communities = []
            for rt in vrf_conf.export_rts:
                as_num, local_admin = rt.split(':')
                subtype = 2
                communities.append(BGPTwoOctetAsSpecificExtendedCommunity(
                                   as_number=int(as_num),
                                   local_administrator=int(local_admin),
                                   subtype=subtype))
            for soo in vrf_conf.soo_list:
                as_num, local_admin = soo.split(':')
                subtype = 3
                communities.append(BGPTwoOctetAsSpecificExtendedCommunity(
                                   as_number=int(as_num),
                                   local_administrator=int(local_admin),
                                   subtype=subtype))

            # Set Tunnel Encapsulation Attribute
            tunnel_type = kwargs.get('tunnel_type', None)
            if tunnel_type:
                communities.append(
                    BGPEncapsulationExtendedCommunity.from_str(tunnel_type))

            pattrs[BGP_ATTR_TYPE_EXTENDED_COMMUNITIES] = \
                BGPPathAttributeExtendedCommunities(communities=communities)
            if vrf_conf.multi_exit_disc:
                pattrs[BGP_ATTR_TYPE_MULTI_EXIT_DISC] = \
                    BGPPathAttributeMultiExitDisc(vrf_conf.multi_exit_disc)

            table_manager = self._core_service.table_manager
            if gen_lbl and next_hop:
                # Label per next_hop demands we use a different label
                # per next_hop. Here connected interfaces are advertised per
                # VRF.
                label_key = (vrf_conf.route_dist, next_hop)
                nh_label = table_manager.get_nexthop_label(label_key)
                if not nh_label:
                    nh_label = table_manager.get_next_vpnv4_label()
                    table_manager.set_nexthop_label(label_key, nh_label)
                label_list.append(nh_label)

            elif gen_lbl:
                # If we do not have next_hop, get a new label.
                label_list.append(table_manager.get_next_vpnv4_label())

            # Set PMSI Tunnel Attribute
            pmsi_tunnel_type = kwargs.get('pmsi_tunnel_type', None)
            if pmsi_tunnel_type is not None:
                from ryu.services.protocols.bgp.api.prefix import (
                    PMSI_TYPE_INGRESS_REP)
                if pmsi_tunnel_type == PMSI_TYPE_INGRESS_REP:
                    tunnel_id = PmsiTunnelIdIngressReplication(
                        tunnel_endpoint_ip=self._core_service.router_id)
                else:  # pmsi_tunnel_type == PMSI_TYPE_NO_TUNNEL_INFO
                    tunnel_id = None
                pattrs[BGP_ATTR_TYEP_PMSI_TUNNEL_ATTRIBUTE] = \
                    BGPPathAttributePmsiTunnel(pmsi_flags=0,
                                               tunnel_type=pmsi_tunnel_type,
                                               tunnel_id=tunnel_id)

            # Set MPLS labels with the generated labels
            if gen_lbl and isinstance(nlri, EvpnMacIPAdvertisementNLRI):
                nlri.mpls_labels = label_list[:2]

        puid = self.VRF_PATH_CLASS.create_puid(
            vrf_conf.route_dist, nlri.prefix)

        path = self.VRF_PATH_CLASS(
            puid, None, nlri, 0, pattrs=pattrs,
            nexthop=next_hop, label_list=label_list,
            is_withdraw=is_withdraw
        )

        # Insert the path into VRF table, get affected destination so that we
        # can process it further.
        eff_dest = self.insert(path)
        # Enqueue the eff_dest for further processing.
        self._signal_bus.dest_changed(eff_dest)
        return label_list

    def clean_uninteresting_paths(self, interested_rts=None):
        if interested_rts is None:
            interested_rts = set(self.vrf_conf.import_rts)
        return super(VrfTable, self).clean_uninteresting_paths(interested_rts)


@six.add_metaclass(abc.ABCMeta)
class VrfDest(Destination):
    """Base class for VRF destination."""

    def __init__(self, table, nlri):
        super(VrfDest, self).__init__(table, nlri)
        self._route_dist = self._table.vrf_conf.route_dist

    @property
    def nlri_str(self):
        # Returns `prefix` without the route distinguisher value, because
        # a destination in VRF space can be identified without the route
        # distinguisher.
        return self._nlri.prefix

    def _best_path_lost(self):
        # Have to send update messages for withdraw of best-path to Network
        # controller or Global table.
        old_best_path = self._best_path
        self._best_path = None

        if old_best_path is None:
            return

        if old_best_path.source is not None:
            # Send update-withdraw msg. to Sink. Create withdraw path
            # out of old best path and queue it into flexinet sinks.
            old_best_path = old_best_path.clone(for_withdrawal=True)
            self._core_service.update_flexinet_peers(old_best_path,
                                                     self._route_dist)
        else:
            # Create withdraw-path out of old best path.
            gpath = old_best_path.clone_to_vpn(self._route_dist,
                                               for_withdrawal=True)
            # Insert withdraw into global table and enqueue the destination
            # for further processing.
            tm = self._core_service.table_manager
            tm.learn_path(gpath)

    def _new_best_path(self, best_path):
        LOG.debug('New best path selected for destination %s', self)

        old_best_path = self._best_path
        assert (best_path != old_best_path)
        self._best_path = best_path
        # Distribute new best-path to flexinet-peers.
        if best_path.source is not None:
            # Since route-refresh just causes the version number to
            # go up and this changes best-path, we check if new-
            # best-path is really different than old-best-path that
            # warrants sending update to flexinet peers.

            def really_diff():
                old_labels = old_best_path.label_list
                new_labels = best_path.label_list
                return old_best_path.nexthop != best_path.nexthop \
                    or set(old_labels) != set(new_labels)

            if not old_best_path or (old_best_path and really_diff()):
                # Create OutgoingRoute and queue it into NC sink.
                self._core_service.update_flexinet_peers(
                    best_path, self._route_dist
                )
        else:
            # If NC is source, we create new path and insert into global
            # table.
            gpath = best_path.clone_to_vpn(self._route_dist)
            tm = self._core_service.table_manager
            tm.learn_path(gpath)
            LOG.debug('VRF table %s has new best path: %s',
                      self._route_dist, self.best_path)

    def _remove_withdrawals(self):
        """Removes withdrawn paths.

        Note:
        We may have disproportionate number of withdraws compared to know paths
        since not all paths get installed into the table due to bgp policy and
        we can receive withdraws for such paths and withdrawals may not be
        stopped by the same policies.
        """

        LOG.debug('Removing %s withdrawals', len(self._withdraw_list))

        # If we have not withdrawals, we have nothing to do.
        if not self._withdraw_list:
            return

        # If we have some withdrawals and no know-paths, it means it is safe to
        # delete these withdraws.
        if not self._known_path_list:
            LOG.debug('Found %s withdrawals for path(s) that did not get'
                      ' installed.', len(self._withdraw_list))
            del (self._withdraw_list[:])
            return

        # If we have some known paths and some withdrawals, we find matches and
        # delete them first.
        matches = []
        w_matches = []
        # Match all withdrawals from destination paths.
        for withdraw in self._withdraw_list:
            match = None
            for path in self._known_path_list:
                # We have a match if the source are same.
                if path.puid == withdraw.puid:
                    match = path
                    matches.append(path)
                    w_matches.append(withdraw)
                    # One withdraw can remove only one path.
                    break
                # We do no have any match for this withdraw.
            if not match:
                LOG.debug('No matching path for withdraw found, may be path '
                          'was not installed into table: %s',
                          withdraw)
            # If we have partial match.
        if len(matches) != len(self._withdraw_list):
            LOG.debug('Did not find match for some withdrawals. Number of '
                      'matches(%s), number of withdrawals (%s)',
                      len(matches), len(self._withdraw_list))

        # Clear matching paths and withdrawals.
        for match in matches:
            self._known_path_list.remove(match)
        for w_match in w_matches:
            self._withdraw_list.remove(w_match)

    def _remove_old_paths(self):
        """Identifies which of known paths are old and removes them.

        Known paths will no longer have paths whose new version is present in
        new paths.
        """
        new_paths = self._new_path_list
        known_paths = self._known_path_list
        for new_path in new_paths:
            old_paths = []
            for path in known_paths:
                # Here we just check if source is same and not check if path
                # version num. as new_paths are implicit withdrawal of old
                # paths and when doing RouteRefresh (not EnhancedRouteRefresh)
                # we get same paths again.
                if new_path.puid == path.puid:
                    old_paths.append(path)
                    break

            for old_path in old_paths:
                known_paths.remove(old_path)
                LOG.debug('Implicit withdrawal of old path, since we have'
                          ' learned new path from same source: %s', old_path)

    def _validate_path(self, path):
        if not path or not hasattr(path, 'label_list'):
            raise ValueError('Invalid value of path. Expected type '
                             'with attribute label_list got %s' % path)


@six.add_metaclass(abc.ABCMeta)
class VrfPath(Path):
    """Represents a way of reaching an IP destination with a VPN.
    """
    __slots__ = ('_label_list', '_puid')

    ROUTE_FAMILY = None
    VPN_PATH_CLASS = None
    VPN_NLRI_CLASS = None

    def __init__(self, puid, source, nlri, src_ver_num,
                 pattrs=None, nexthop=None,
                 is_withdraw=False, label_list=None):
        """Initializes a Vrf path.

            Parameters:
                - `puid`: (str) path ID, identifies VPN path from which this
                VRF path was imported.
                - `label_list`: (list) List of labels for this path.
            Note: other parameters are as documented in super class.
        """
        Path.__init__(self, source, nlri, src_ver_num, pattrs, nexthop,
                      is_withdraw)
        if label_list is None:
            label_list = []
        self._label_list = label_list
        self._puid = puid

    @property
    def puid(self):
        return self._puid

    @property
    def origin_rd(self):
        tokens = self.puid.split(':')
        return tokens[0] + ':' + tokens[1]

    @property
    def label_list(self):
        return self._label_list[:]

    @property
    def nlri_str(self):
        # Returns `prefix` without the route distinguisher value, because
        # a destination in VRF space can be identified without the route
        # distinguisher.
        return self._nlri.prefix

    @staticmethod
    def create_puid(route_dist, ip_prefix):
        assert route_dist and ip_prefix
        return str(route_dist) + ':' + ip_prefix

    def clone(self, for_withdrawal=False):
        pathattrs = None
        if not for_withdrawal:
            pathattrs = self.pathattr_map

        clone = self.__class__(
            self.puid,
            self._source,
            self.nlri,
            self.source_version_num,
            pattrs=pathattrs,
            nexthop=self.nexthop,
            is_withdraw=for_withdrawal,
            label_list=self.label_list
        )
        return clone

    def clone_to_vpn(self, route_dist, for_withdrawal=False):
        if self.ROUTE_FAMILY == RF_L2_EVPN:
            # Because NLRI class is the same if the route family is EVPN,
            # we re-use the NLRI instance.
            vpn_nlri = self._nlri
        else:  # self.ROUTE_FAMILY in [RF_IPv4_UC, RF_IPv6_UC]
            ip, masklen = self._nlri.prefix.split('/')
            vpn_nlri = self.VPN_NLRI_CLASS(length=int(masklen),
                                           addr=ip,
                                           labels=self.label_list,
                                           route_dist=route_dist)

        pathattrs = None
        if not for_withdrawal:
            pathattrs = self.pathattr_map

        vpnv_path = self.VPN_PATH_CLASS(
            source=self.source,
            nlri=vpn_nlri,
            src_ver_num=self.source_version_num,
            pattrs=pathattrs,
            nexthop=self.nexthop,
            is_withdraw=for_withdrawal)

        return vpnv_path

    def __eq__(self, b_path):
        if not isinstance(b_path, self.__class__):
            return False
        if not self.route_family == b_path.route_family:
            return False
        if not self.puid == b_path.puid:
            return False
        if not self.label_list == b_path.label_list:
            return False
        if not self.nexthop == b_path.nexthop:
            return False
        if not self.pathattr_map == b_path.pathattr_map:
            return False

        return True


class ImportMap(object):
    def match(self, vrf_path):
        raise NotImplementedError()


class VrfNlriImportMap(ImportMap):
    VRF_PATH_CLASS = None
    NLRI_CLASS = None

    def __init__(self, prefix):
        assert self.VRF_PATH_CLASS is not None
        assert self.NLRI_CLASS is not None
        self._nlri = self.NLRI_CLASS(prefix)

    def match(self, vrf_path):
        if vrf_path.route_family != self.VRF_PATH_CLASS.ROUTE_FAMILY:
            LOG.error(
                "vrf_paths route_family does not match importmaps"
                "route_family. Applied to wrong table?")
            return False

        return vrf_path.nlri == self._nlri


class VrfRtImportMap(ImportMap):
    def __init__(self, rt):
        self._rt = rt

    def match(self, vrf_path):
        extcomm = vrf_path.pathattr_map.get(BGP_ATTR_TYPE_EXTENDED_COMMUNITIES)
        return extcomm is not None and self._rt in extcomm.rt_list
