<commit_before>package org.batfish.question.routes;

import static com.google.common.collect.ImmutableList.toImmutableList;
import static org.batfish.datamodel.table.TableDiff.COL_BASE_PREFIX;
import static org.batfish.datamodel.table.TableDiff.COL_DELTA_PREFIX;
import static org.batfish.question.routes.RoutesAnswerer.COL_ADMIN_DISTANCE;
import static org.batfish.question.routes.RoutesAnswerer.COL_AS_PATH;
import static org.batfish.question.routes.RoutesAnswerer.COL_COMMUNITIES;
import static org.batfish.question.routes.RoutesAnswerer.COL_LOCAL_PREF;
import static org.batfish.question.routes.RoutesAnswerer.COL_METRIC;
import static org.batfish.question.routes.RoutesAnswerer.COL_NETWORK;
import static org.batfish.question.routes.RoutesAnswerer.COL_NEXT_HOP;
import static org.batfish.question.routes.RoutesAnswerer.COL_NEXT_HOP_INTERFACE;
import static org.batfish.question.routes.RoutesAnswerer.COL_NEXT_HOP_IP;
import static org.batfish.question.routes.RoutesAnswerer.COL_NODE;
import static org.batfish.question.routes.RoutesAnswerer.COL_ORIGIN_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_ROUTE_DISTINGUISHER;
import static org.batfish.question.routes.RoutesAnswerer.COL_ROUTE_ENTRY_PRESENCE;
import static org.batfish.question.routes.RoutesAnswerer.COL_TAG;
import static org.batfish.question.routes.RoutesAnswerer.COL_VRF_NAME;
import static org.batfish.question.routes.RoutesAnswerer.getDiffTableMetadata;
import static org.batfish.question.routes.RoutesAnswerer.getTableMetadata;

import com.fasterxml.jackson.annotation.JsonCreator;
import com.fasterxml.jackson.annotation.JsonValue;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Multiset;
import com.google.common.collect.Table;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import javax.annotation.Nullable;
import org.batfish.common.BatfishException;
import org.batfish.datamodel.AbstractRoute;
import org.batfish.datamodel.AbstractRouteDecorator;
import org.batfish.datamodel.Bgpv4Route;
import org.batfish.datamodel.EvpnRoute;
import org.batfish.datamodel.GenericRib;
import org.batfish.datamodel.Ip;
import org.batfish.datamodel.Prefix;
import org.batfish.datamodel.Route;
import org.batfish.datamodel.bgp.community.Community;
import org.batfish.datamodel.pojo.Node;
import org.batfish.datamodel.table.ColumnMetadata;
import org.batfish.datamodel.table.Row;
import org.batfish.datamodel.table.Row.RowBuilder;
import org.batfish.datamodel.table.TableDiff;
import org.batfish.question.routes.DiffRoutesOutput.KeyPresenceStatus;
import org.batfish.question.routes.RoutesQuestion.RibProtocol;
import org.batfish.specifier.RoutingProtocolSpecifier;

public class RoutesAnswererUtil {

  /** IPs that are used internally and should not be exposed as next hop IPs */
  private static final Set<Ip> INTERNAL_USE_IPS =
      ImmutableSet.of(
          // BGP unnumbered IP
          Ip.parse("169.254.0.1"));

  public enum RouteEntryPresenceStatus {
    ONLY_IN_SNAPSHOT(TableDiff.COL_KEY_STATUS_ONLY_BASE),
    ONLY_IN_REFERENCE(TableDiff.COL_KEY_STATUS_ONLY_DELTA),
    CHANGED("Changed"),
    UNCHANGED("Unchanged");

    private static final Map<String, RouteEntryPresenceStatus> _map = buildMap();

    private static Map<String, RouteEntryPresenceStatus> buildMap() {
      ImmutableMap.Builder<String, RouteEntryPresenceStatus> map = ImmutableMap.builder();
      for (RouteEntryPresenceStatus value : RouteEntryPresenceStatus.values()) {
        map.put(value._name, value);
      }
      return map.build();
    }

    @JsonCreator
    public static RouteEntryPresenceStatus fromName(String name) {
      RouteEntryPresenceStatus instance = _map.get(name);
      if (instance == null) {
        throw new BatfishException(
            String.format(
                "No %s with name: '%s'", RouteEntryPresenceStatus.class.getSimpleName(), name));
      }
      return instance;
    }

    private final String _name;

    RouteEntryPresenceStatus(String name) {
      _name = name;
    }

    @JsonValue
    public String routeEntryPresenceName() {
      return _name;
    }
  }

  /** Compute the next hop node for a given next hop IP. */
  @Nullable
  static String computeNextHopNode(
      @Nullable Ip nextHopIp, @Nullable Map<Ip, Set<String>> ipOwners) {
    if (nextHopIp == null || ipOwners == null) {
      return null;
    }
    // TODO: https://github.com/batfish/batfish/issues/1862
    return ipOwners.getOrDefault(nextHopIp, ImmutableSet.of()).stream()
        .min(Comparator.naturalOrder())
        .orElse(null);
  }

  /**
   * Returns a {@link Multiset} of {@link Row}s for all routes present in all RIBs
   *
   * @param ribs {@link Map} representing all RIBs of all nodes
   * @param matchingNodes {@link Set} of hostnames of nodes whose routes are to be returned
   * @param network {@link Prefix} of the network used to filter the routes
   * @param protocolSpec {@link RoutingProtocolSpecifier} used to filter the routes
   * @param vrfRegex Regex used to filter the VRF of routes
   * @param ipOwners {@link Map} of {@link Ip} to {@link Set} of owner nodes
   * @return {@link Multiset} of {@link Row}s representing the routes
   */
  static <T extends AbstractRouteDecorator> Multiset<Row> getMainRibRoutes(
      SortedMap<String, SortedMap<String, GenericRib<T>>> ribs,
      Set<String> matchingNodes,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      String vrfRegex,
      @Nullable Map<Ip, Set<String>> ipOwners) {
    Multiset<Row> rows = HashMultiset.create();
    Pattern compiledVrfRegex = Pattern.compile(vrfRegex);
    Map<String, ColumnMetadata> columnMetadataMap =
        getTableMetadata(RibProtocol.MAIN).toColumnMap();
    ribs.forEach(
        (node, vrfMap) -> {
          if (matchingNodes.contains(node)) {
            vrfMap.forEach(
                (vrfName, rib) -> {
                  if (compiledVrfRegex.matcher(vrfName).matches()) {
                    rib.getRoutes().stream()
                        .filter(
                            route ->
                                (network == null || network.equals(route.getNetwork()))
                                    && protocolSpec.getProtocols().contains(route.getProtocol()))
                        .forEach(
                            route ->
                                rows.add(
                                    abstractRouteToRow(
                                        node, vrfName, route, columnMetadataMap, ipOwners)));
                  }
                });
          }
        });
    return rows;
  }

  /**
   * Filters a {@link Table} of {@link Bgpv4Route}s to produce a {@link Multiset} of rows
   *
   * @param bgpRoutes {@link Table} of all {@link Bgpv4Route}s
   * @param ribProtocol {@link RibProtocol}, either {@link RibProtocol#BGP}
   * @param matchingNodes {@link Set} of nodes from which {@link Bgpv4Route}s are to be selected
   * @param network {@link Prefix} of the network used to filter the routes
   * @param protocolSpec {@link RoutingProtocolSpecifier} used to filter the {@link Bgpv4Route}s
   * @param vrfRegex Regex used to filter the routes based on {@link org.batfish.datamodel.Vrf}
   * @return {@link Multiset} of {@link Row}s representing the routes
   */
  static Multiset<Row> getBgpRibRoutes(
      Table<String, String, Set<Bgpv4Route>> bgpRoutes,
      RibProtocol ribProtocol,
      Set<String> matchingNodes,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      String vrfRegex) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap = getTableMetadata(ribProtocol).toColumnMap();
    Pattern compiledVrfRegex = Pattern.compile(vrfRegex);
    matchingNodes.forEach(
        hostname ->
            bgpRoutes
                .row(hostname)
                .forEach(
                    (vrfName, routes) -> {
                      if (compiledVrfRegex.matcher(vrfName).matches()) {
                        routes.stream()
                            .filter(
                                route ->
                                    (network == null || network.equals(route.getNetwork()))
                                        && protocolSpec
                                            .getProtocols()
                                            .contains(route.getProtocol()))
                            .forEach(
                                route ->
                                    rows.add(
                                        bgpRouteToRow(
                                            hostname, vrfName, route, columnMetadataMap)));
                      }
                    }));
    return rows;
  }

  static Multiset<Row> getEvpnRoutes(
      Table<String, String, Set<EvpnRoute<?, ?>>> evpnRoutes,
      RibProtocol ribProtocol,
      Set<String> matchingNodes,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      String vrfRegex) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap = getTableMetadata(ribProtocol).toColumnMap();
    Pattern compiledVrfRegex = Pattern.compile(vrfRegex);
    matchingNodes.forEach(
        hostname ->
            evpnRoutes
                .row(hostname)
                .forEach(
                    (vrfName, routes) -> {
                      if (compiledVrfRegex.matcher(vrfName).matches()) {
                        routes.stream()
                            .filter(
                                route ->
                                    (network == null || network.equals(route.getNetwork()))
                                        && protocolSpec
                                            .getProtocols()
                                            .contains(route.getProtocol()))
                            .forEach(
                                route ->
                                    rows.add(
                                        evpnRouteToRow(
                                            hostname, vrfName, route, columnMetadataMap)));
                      }
                    }));
    return rows;
  }

  /**
   * Converts a {@link AbstractRoute} to a {@link Row}
   *
   * @param hostName {@link String} host-name of the node containing the route
   * @param vrfName {@link String} name of the VRF containing the route
   * @param abstractRoute {@link AbstractRoute} to convert
   * @param columnMetadataMap Column metadata of the columns for this {@link Row} c
   * @return {@link Row} representing the {@link AbstractRoute}
   */
  private static Row abstractRouteToRow(
      String hostName,
      String vrfName,
      AbstractRoute abstractRoute,
      Map<String, ColumnMetadata> columnMetadataMap,
      @Nullable Map<Ip, Set<String>> ipOwners) {
    // If the route's next hop IP is for internal use, do not show it in the row
    Ip nextHopIp =
        INTERNAL_USE_IPS.contains(abstractRoute.getNextHopIp())
            ? null
            : abstractRoute.getNextHopIp();
    return Row.builder(columnMetadataMap)
        .put(COL_NODE, new Node(hostName))
        .put(COL_VRF_NAME, vrfName)
        .put(COL_NETWORK, abstractRoute.getNetwork())
        .put(COL_NEXT_HOP_IP, nextHopIp)
        .put(COL_NEXT_HOP_INTERFACE, abstractRoute.getNextHopInterface())
        .put(COL_NEXT_HOP, computeNextHopNode(abstractRoute.getNextHopIp(), ipOwners))
        .put(COL_PROTOCOL, abstractRoute.getProtocol())
        .put(
            COL_TAG,
            abstractRoute.getTag() == Route.UNSET_ROUTE_TAG ? null : abstractRoute.getTag())
        .put(COL_ADMIN_DISTANCE, abstractRoute.getAdministrativeCost())
        .put(COL_METRIC, abstractRoute.getMetric())
        .build();
  }

  /**
   * Converts a {@link Bgpv4Route} to a {@link Row}
   *
   * @param hostName {@link String} host-name of the node containing the bgpv4Route
   * @param vrfName {@link String} name of the VRF containing the bgpv4Route
   * @param bgpv4Route {@link Bgpv4Route} BGP route to convert
   * @param columnMetadataMap Column metadata of the columns for this {@link Row}
   * @return {@link Row} representing the {@link Bgpv4Route}
   */
  static Row bgpRouteToRow(
      String hostName,
      String vrfName,
      Bgpv4Route bgpv4Route,
      Map<String, ColumnMetadata> columnMetadataMap) {
    // If the route's next hop IP is for internal use, do not show it in the row
    Ip nextHopIp =
        INTERNAL_USE_IPS.contains(bgpv4Route.getNextHopIp()) ? null : bgpv4Route.getNextHopIp();
    return Row.builder(columnMetadataMap)
        .put(COL_NODE, new Node(hostName))
        .put(COL_VRF_NAME, vrfName)
        .put(COL_NETWORK, bgpv4Route.getNetwork())
        .put(COL_NEXT_HOP_IP, nextHopIp)
        .put(COL_NEXT_HOP_INTERFACE, bgpv4Route.getNextHopInterface())
        .put(COL_PROTOCOL, bgpv4Route.getProtocol())
        .put(COL_AS_PATH, bgpv4Route.getAsPath().getAsPathString())
        .put(COL_METRIC, bgpv4Route.getMetric())
        .put(COL_LOCAL_PREF, bgpv4Route.getLocalPreference())
        .put(
            COL_COMMUNITIES,
            bgpv4Route.getCommunities().stream()
                .map(Community::toString)
                .collect(toImmutableList()))
        .put(COL_ORIGIN_PROTOCOL, bgpv4Route.getSrcProtocol())
        .put(COL_TAG, bgpv4Route.getTag() == Route.UNSET_ROUTE_TAG ? null : bgpv4Route.getTag())
        .build();
  }

  static Row evpnRouteToRow(
      String hostName,
      String vrfName,
      EvpnRoute<?, ?> evpnRoute,
      Map<String, ColumnMetadata> columnMetadataMap) {
    // If the route's next hop IP is for internal use, do not show it in the row
    Ip nextHopIp =
        INTERNAL_USE_IPS.contains(evpnRoute.getNextHopIp()) ? null : evpnRoute.getNextHopIp();
    return Row.builder(columnMetadataMap)
        .put(COL_NODE, new Node(hostName))
        .put(COL_VRF_NAME, vrfName)
        .put(COL_NETWORK, evpnRoute.getNetwork())
        .put(COL_NEXT_HOP_IP, nextHopIp)
        .put(COL_NEXT_HOP_INTERFACE, evpnRoute.getNextHopInterface())
        .put(COL_PROTOCOL, evpnRoute.getProtocol())
        .put(COL_AS_PATH, evpnRoute.getAsPath().getAsPathString())
        .put(COL_METRIC, evpnRoute.getMetric())
        .put(COL_LOCAL_PREF, evpnRoute.getLocalPreference())
        .put(
            COL_COMMUNITIES,
            evpnRoute.getCommunities().stream().map(Community::toString).collect(toImmutableList()))
        .put(COL_ORIGIN_PROTOCOL, evpnRoute.getSrcProtocol())
        .put(COL_TAG, evpnRoute.getTag() == Route.UNSET_ROUTE_TAG ? null : evpnRoute.getTag())
        .put(COL_ROUTE_DISTINGUISHER, evpnRoute.getRouteDistinguisher())
        .build();
  }

  /**
   * Converts {@link List} of {@link DiffRoutesOutput} to {@link Row}s with one row corresponding to
   * each {@link DiffRoutesOutput#_diffInAttributes} of the {@link DiffRoutesOutput}
   *
   * @param diffRoutesList {@link List} of {@link DiffRoutesOutput} for {@link Bgpv4Route}s
   * @return {@link Multiset} of {@link Row}s
   */
  static Multiset<Row> getBgpRouteRowsDiff(
      List<DiffRoutesOutput> diffRoutesList, RibProtocol ribProtocol) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap = getDiffTableMetadata(ribProtocol).toColumnMap();
    for (DiffRoutesOutput diffRoutesOutput : diffRoutesList) {
      RouteRowKey routeRowKey = diffRoutesOutput.getRouteRowKey();
      String hostName = routeRowKey.getHostName();
      String vrfName = routeRowKey.getVrfName();
      Prefix network = routeRowKey.getPrefix();
      RouteRowSecondaryKey routeRowSecondaryKey = diffRoutesOutput.getRouteRowSecondaryKey();
      KeyPresenceStatus secondaryKeyPresenceStatus =
          diffRoutesOutput.getRouteRowSecondaryKeyStatus();

      for (List<RouteRowAttribute> routeRowAttributeInBaseAndRef :
          diffRoutesOutput.getDiffInAttributes()) {
        Row.RowBuilder rowBuilder = Row.builder(columnMetadataMap);
        rowBuilder
            .put(COL_NODE, new Node(hostName))
            .put(COL_VRF_NAME, vrfName)
            .put(COL_NETWORK, network);

        RouteRowAttribute routeRowAttributeBase = routeRowAttributeInBaseAndRef.get(0);
        RouteRowAttribute routeRowAttributeRef = routeRowAttributeInBaseAndRef.get(1);

        rowBuilder.put(
            COL_ROUTE_ENTRY_PRESENCE,
            getRouteEntryPresence(
                secondaryKeyPresenceStatus, routeRowAttributeBase, routeRowAttributeRef));

        populateSecondaryKeyAttrs(routeRowSecondaryKey, secondaryKeyPresenceStatus, rowBuilder);
        populateBgpRouteAttributes(rowBuilder, routeRowAttributeBase, true);
        populateBgpRouteAttributes(rowBuilder, routeRowAttributeRef, false);

        rows.add(rowBuilder.build());
      }
    }
    return rows;
  }

  /**
   * Populates the {@link RowBuilder} for differential answer of {@link RoutesAnswerer} with
   * attributes of {@link RouteRowSecondaryKey} for base and reference snapshot
   *
   * @param routeRowSecondaryKey {@link RouteRowSecondaryKey} for the current {@link Row} of the
   *     differential answer
   * @param secondaryKeyPresence {@link KeyPresenceStatus} for the routeRowSecondaryKey
   * @param rowBuilder {@link RowBuilder} for the current row
   */
  private static void populateSecondaryKeyAttrs(
      RouteRowSecondaryKey routeRowSecondaryKey,
      KeyPresenceStatus secondaryKeyPresence,
      RowBuilder rowBuilder) {
    Ip nextHopIp = routeRowSecondaryKey.getNextHopIp();
    String protocol = routeRowSecondaryKey.getProtocol();
    // populating base columns for secondary key if it is present in base snapshot or in both
    // snapshots
    if (secondaryKeyPresence == KeyPresenceStatus.IN_BOTH
        || secondaryKeyPresence == KeyPresenceStatus.ONLY_IN_SNAPSHOT) {
      rowBuilder
          .put(COL_BASE_PREFIX + COL_NEXT_HOP_IP, nextHopIp)
          .put(COL_BASE_PREFIX + COL_PROTOCOL, protocol);
    }
    // populating reference columns for secondary key if it is present in reference snapshot or in
    // both snapshots
    if (secondaryKeyPresence == KeyPresenceStatus.IN_BOTH
        || secondaryKeyPresence == KeyPresenceStatus.ONLY_IN_REFERENCE) {
      rowBuilder
          .put(COL_DELTA_PREFIX + COL_NEXT_HOP_IP, nextHopIp)
          .put(COL_DELTA_PREFIX + COL_PROTOCOL, protocol);
    }
  }

  /**
   * Computes RoutePresenceEntryStatus using secondary key status and pairs of routeRowAttributes in
   * base and reference
   */
  private static RouteEntryPresenceStatus getRouteEntryPresence(
      KeyPresenceStatus secondaryKeyStatus,
      RouteRowAttribute routeRowAttributeBase,
      RouteRowAttribute routeRowAttributeReference) {
    RouteEntryPresenceStatus routeEntryPresenceStatus;
    if (secondaryKeyStatus.equals(KeyPresenceStatus.IN_BOTH)) {
      if (routeRowAttributeBase != null && routeRowAttributeReference != null) {
        routeEntryPresenceStatus =
            routeRowAttributeBase.equals(routeRowAttributeReference)
                ? RouteEntryPresenceStatus.UNCHANGED
                : RouteEntryPresenceStatus.CHANGED;

      } else {
        routeEntryPresenceStatus =
            routeRowAttributeBase != null
                ? RouteEntryPresenceStatus.ONLY_IN_SNAPSHOT
                : RouteEntryPresenceStatus.ONLY_IN_REFERENCE;
      }
    } else {
      routeEntryPresenceStatus =
          secondaryKeyStatus == KeyPresenceStatus.ONLY_IN_REFERENCE
              ? RouteEntryPresenceStatus.ONLY_IN_REFERENCE
              : RouteEntryPresenceStatus.ONLY_IN_SNAPSHOT;
    }
    return routeEntryPresenceStatus;
  }

  private static void populateBgpRouteAttributes(
      RowBuilder rowBuilder, @Nullable RouteRowAttribute routeRowAttribute, boolean base) {
    rowBuilder
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_AS_PATH,
            routeRowAttribute != null && routeRowAttribute.getAsPath() != null
                ? routeRowAttribute.getAsPath().getAsPathString()
                : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_METRIC,
            routeRowAttribute != null ? routeRowAttribute.getMetric() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_LOCAL_PREF,
            routeRowAttribute != null ? routeRowAttribute.getLocalPreference() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_COMMUNITIES,
            routeRowAttribute != null ? routeRowAttribute.getCommunities() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_ORIGIN_PROTOCOL,
            routeRowAttribute != null ? routeRowAttribute.getOriginProtocol() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_TAG,
            routeRowAttribute != null ? routeRowAttribute.getTag() : null);
  }

  /**
   * Converts {@link List} of {@link DiffRoutesOutput} to {@link Row}s with one row corresponding to
   * each {@link DiffRoutesOutput#_diffInAttributes} of the {@link DiffRoutesOutput}
   *
   * @param diffRoutesList {@link List} of {@link DiffRoutesOutput} for routes in Main RIB
   * @return {@link Multiset} of {@link Row}s
   */
  static Multiset<Row> getAbstractRouteRowsDiff(List<DiffRoutesOutput> diffRoutesList) {
    Map<String, ColumnMetadata> columnMetadataMap =
        getDiffTableMetadata(RibProtocol.MAIN).toColumnMap();
    Multiset<Row> rows = HashMultiset.create();
    for (DiffRoutesOutput diffRoutesOutput : diffRoutesList) {
      RouteRowKey routeRowKey = diffRoutesOutput.getRouteRowKey();<commit_msg>RoutesAnswererUtil: cleanup javadoc (#4741)<commit_after>package org.batfish.question.routes;

import static com.google.common.collect.ImmutableList.toImmutableList;
import static org.batfish.datamodel.table.TableDiff.COL_BASE_PREFIX;
import static org.batfish.datamodel.table.TableDiff.COL_DELTA_PREFIX;
import static org.batfish.question.routes.RoutesAnswerer.COL_ADMIN_DISTANCE;
import static org.batfish.question.routes.RoutesAnswerer.COL_AS_PATH;
import static org.batfish.question.routes.RoutesAnswerer.COL_COMMUNITIES;
import static org.batfish.question.routes.RoutesAnswerer.COL_LOCAL_PREF;
import static org.batfish.question.routes.RoutesAnswerer.COL_METRIC;
import static org.batfish.question.routes.RoutesAnswerer.COL_NETWORK;
import static org.batfish.question.routes.RoutesAnswerer.COL_NEXT_HOP;
import static org.batfish.question.routes.RoutesAnswerer.COL_NEXT_HOP_INTERFACE;
import static org.batfish.question.routes.RoutesAnswerer.COL_NEXT_HOP_IP;
import static org.batfish.question.routes.RoutesAnswerer.COL_NODE;
import static org.batfish.question.routes.RoutesAnswerer.COL_ORIGIN_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_ROUTE_DISTINGUISHER;
import static org.batfish.question.routes.RoutesAnswerer.COL_ROUTE_ENTRY_PRESENCE;
import static org.batfish.question.routes.RoutesAnswerer.COL_TAG;
import static org.batfish.question.routes.RoutesAnswerer.COL_VRF_NAME;
import static org.batfish.question.routes.RoutesAnswerer.getDiffTableMetadata;
import static org.batfish.question.routes.RoutesAnswerer.getTableMetadata;

import com.fasterxml.jackson.annotation.JsonCreator;
import com.fasterxml.jackson.annotation.JsonValue;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Multiset;
import com.google.common.collect.Table;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import javax.annotation.Nullable;
import org.batfish.common.BatfishException;
import org.batfish.datamodel.AbstractRoute;
import org.batfish.datamodel.AbstractRouteDecorator;
import org.batfish.datamodel.Bgpv4Route;
import org.batfish.datamodel.EvpnRoute;
import org.batfish.datamodel.GenericRib;
import org.batfish.datamodel.Ip;
import org.batfish.datamodel.Prefix;
import org.batfish.datamodel.Route;
import org.batfish.datamodel.bgp.community.Community;
import org.batfish.datamodel.pojo.Node;
import org.batfish.datamodel.table.ColumnMetadata;
import org.batfish.datamodel.table.Row;
import org.batfish.datamodel.table.Row.RowBuilder;
import org.batfish.datamodel.table.TableDiff;
import org.batfish.question.routes.DiffRoutesOutput.KeyPresenceStatus;
import org.batfish.question.routes.RoutesQuestion.RibProtocol;
import org.batfish.specifier.RoutingProtocolSpecifier;

public class RoutesAnswererUtil {

  /** IPs that are used internally and should not be exposed as next hop IPs */
  private static final Set<Ip> INTERNAL_USE_IPS =
      ImmutableSet.of(
          // BGP unnumbered IP
          Ip.parse("169.254.0.1"));

  public enum RouteEntryPresenceStatus {
    ONLY_IN_SNAPSHOT(TableDiff.COL_KEY_STATUS_ONLY_BASE),
    ONLY_IN_REFERENCE(TableDiff.COL_KEY_STATUS_ONLY_DELTA),
    CHANGED("Changed"),
    UNCHANGED("Unchanged");

    private static final Map<String, RouteEntryPresenceStatus> _map = buildMap();

    private static Map<String, RouteEntryPresenceStatus> buildMap() {
      ImmutableMap.Builder<String, RouteEntryPresenceStatus> map = ImmutableMap.builder();
      for (RouteEntryPresenceStatus value : RouteEntryPresenceStatus.values()) {
        map.put(value._name, value);
      }
      return map.build();
    }

    @JsonCreator
    public static RouteEntryPresenceStatus fromName(String name) {
      RouteEntryPresenceStatus instance = _map.get(name);
      if (instance == null) {
        throw new BatfishException(
            String.format(
                "No %s with name: '%s'", RouteEntryPresenceStatus.class.getSimpleName(), name));
      }
      return instance;
    }

    private final String _name;

    RouteEntryPresenceStatus(String name) {
      _name = name;
    }

    @JsonValue
    public String routeEntryPresenceName() {
      return _name;
    }
  }

  /** Compute the next hop node for a given next hop IP. */
  @Nullable
  static String computeNextHopNode(
      @Nullable Ip nextHopIp, @Nullable Map<Ip, Set<String>> ipOwners) {
    if (nextHopIp == null || ipOwners == null) {
      return null;
    }
    // TODO: https://github.com/batfish/batfish/issues/1862
    return ipOwners.getOrDefault(nextHopIp, ImmutableSet.of()).stream()
        .min(Comparator.naturalOrder())
        .orElse(null);
  }

  /**
   * Returns a {@link Multiset} of {@link Row}s for all routes present in all RIBs
   *
   * @param ribs {@link Map} representing all RIBs of all nodes
   * @param matchingNodes {@link Set} of hostnames of nodes whose routes are to be returned
   * @param network {@link Prefix} of the network used to filter the routes
   * @param protocolSpec {@link RoutingProtocolSpecifier} used to filter the routes
   * @param vrfRegex Regex used to filter the VRF of routes
   * @param ipOwners {@link Map} of {@link Ip} to {@link Set} of owner nodes
   * @return {@link Multiset} of {@link Row}s representing the routes
   */
  static <T extends AbstractRouteDecorator> Multiset<Row> getMainRibRoutes(
      SortedMap<String, SortedMap<String, GenericRib<T>>> ribs,
      Set<String> matchingNodes,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      String vrfRegex,
      @Nullable Map<Ip, Set<String>> ipOwners) {
    Multiset<Row> rows = HashMultiset.create();
    Pattern compiledVrfRegex = Pattern.compile(vrfRegex);
    Map<String, ColumnMetadata> columnMetadataMap =
        getTableMetadata(RibProtocol.MAIN).toColumnMap();
    ribs.forEach(
        (node, vrfMap) -> {
          if (matchingNodes.contains(node)) {
            vrfMap.forEach(
                (vrfName, rib) -> {
                  if (compiledVrfRegex.matcher(vrfName).matches()) {
                    rib.getRoutes().stream()
                        .filter(
                            route ->
                                (network == null || network.equals(route.getNetwork()))
                                    && protocolSpec.getProtocols().contains(route.getProtocol()))
                        .forEach(
                            route ->
                                rows.add(
                                    abstractRouteToRow(
                                        node, vrfName, route, columnMetadataMap, ipOwners)));
                  }
                });
          }
        });
    return rows;
  }

  /**
   * Filters a {@link Table} of {@link Bgpv4Route}s to produce a {@link Multiset} of rows
   *
   * @param bgpRoutes {@link Table} of all {@link Bgpv4Route}s
   * @param ribProtocol {@link RibProtocol}, either {@link RibProtocol#BGP}
   * @param matchingNodes {@link Set} of nodes from which {@link Bgpv4Route}s are to be selected
   * @param network {@link Prefix} of the network used to filter the routes
   * @param protocolSpec {@link RoutingProtocolSpecifier} used to filter the {@link Bgpv4Route}s
   * @param vrfRegex Regex used to filter the routes based on {@link org.batfish.datamodel.Vrf}
   * @return {@link Multiset} of {@link Row}s representing the routes
   */
  static Multiset<Row> getBgpRibRoutes(
      Table<String, String, Set<Bgpv4Route>> bgpRoutes,
      RibProtocol ribProtocol,
      Set<String> matchingNodes,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      String vrfRegex) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap = getTableMetadata(ribProtocol).toColumnMap();
    Pattern compiledVrfRegex = Pattern.compile(vrfRegex);
    matchingNodes.forEach(
        hostname ->
            bgpRoutes
                .row(hostname)
                .forEach(
                    (vrfName, routes) -> {
                      if (compiledVrfRegex.matcher(vrfName).matches()) {
                        routes.stream()
                            .filter(
                                route ->
                                    (network == null || network.equals(route.getNetwork()))
                                        && protocolSpec
                                            .getProtocols()
                                            .contains(route.getProtocol()))
                            .forEach(
                                route ->
                                    rows.add(
                                        bgpRouteToRow(
                                            hostname, vrfName, route, columnMetadataMap)));
                      }
                    }));
    return rows;
  }

  static Multiset<Row> getEvpnRoutes(
      Table<String, String, Set<EvpnRoute<?, ?>>> evpnRoutes,
      RibProtocol ribProtocol,
      Set<String> matchingNodes,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      String vrfRegex) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap = getTableMetadata(ribProtocol).toColumnMap();
    Pattern compiledVrfRegex = Pattern.compile(vrfRegex);
    matchingNodes.forEach(
        hostname ->
            evpnRoutes
                .row(hostname)
                .forEach(
                    (vrfName, routes) -> {
                      if (compiledVrfRegex.matcher(vrfName).matches()) {
                        routes.stream()
                            .filter(
                                route ->
                                    (network == null || network.equals(route.getNetwork()))
                                        && protocolSpec
                                            .getProtocols()
                                            .contains(route.getProtocol()))
                            .forEach(
                                route ->
                                    rows.add(
                                        evpnRouteToRow(
                                            hostname, vrfName, route, columnMetadataMap)));
                      }
                    }));
    return rows;
  }

  /**
   * Converts a {@link AbstractRoute} to a {@link Row}
   *
   * @param hostName {@link String} host-name of the node containing the route
   * @param vrfName {@link String} name of the VRF containing the route
   * @param abstractRoute {@link AbstractRoute} to convert
   * @param columnMetadataMap Column metadata of the columns for this {@link Row} c
   * @return {@link Row} representing the {@link AbstractRoute}
   */
  private static Row abstractRouteToRow(
      String hostName,
      String vrfName,
      AbstractRoute abstractRoute,
      Map<String, ColumnMetadata> columnMetadataMap,
      @Nullable Map<Ip, Set<String>> ipOwners) {
    // If the route's next hop IP is for internal use, do not show it in the row
    Ip nextHopIp =
        INTERNAL_USE_IPS.contains(abstractRoute.getNextHopIp())
            ? null
            : abstractRoute.getNextHopIp();
    return Row.builder(columnMetadataMap)
        .put(COL_NODE, new Node(hostName))
        .put(COL_VRF_NAME, vrfName)
        .put(COL_NETWORK, abstractRoute.getNetwork())
        .put(COL_NEXT_HOP_IP, nextHopIp)
        .put(COL_NEXT_HOP_INTERFACE, abstractRoute.getNextHopInterface())
        .put(COL_NEXT_HOP, computeNextHopNode(abstractRoute.getNextHopIp(), ipOwners))
        .put(COL_PROTOCOL, abstractRoute.getProtocol())
        .put(
            COL_TAG,
            abstractRoute.getTag() == Route.UNSET_ROUTE_TAG ? null : abstractRoute.getTag())
        .put(COL_ADMIN_DISTANCE, abstractRoute.getAdministrativeCost())
        .put(COL_METRIC, abstractRoute.getMetric())
        .build();
  }

  /**
   * Converts a {@link Bgpv4Route} to a {@link Row}
   *
   * @param hostName {@link String} host-name of the node containing the bgpv4Route
   * @param vrfName {@link String} name of the VRF containing the bgpv4Route
   * @param bgpv4Route {@link Bgpv4Route} BGP route to convert
   * @param columnMetadataMap Column metadata of the columns for this {@link Row}
   * @return {@link Row} representing the {@link Bgpv4Route}
   */
  static Row bgpRouteToRow(
      String hostName,
      String vrfName,
      Bgpv4Route bgpv4Route,
      Map<String, ColumnMetadata> columnMetadataMap) {
    // If the route's next hop IP is for internal use, do not show it in the row
    Ip nextHopIp =
        INTERNAL_USE_IPS.contains(bgpv4Route.getNextHopIp()) ? null : bgpv4Route.getNextHopIp();
    return Row.builder(columnMetadataMap)
        .put(COL_NODE, new Node(hostName))
        .put(COL_VRF_NAME, vrfName)
        .put(COL_NETWORK, bgpv4Route.getNetwork())
        .put(COL_NEXT_HOP_IP, nextHopIp)
        .put(COL_NEXT_HOP_INTERFACE, bgpv4Route.getNextHopInterface())
        .put(COL_PROTOCOL, bgpv4Route.getProtocol())
        .put(COL_AS_PATH, bgpv4Route.getAsPath().getAsPathString())
        .put(COL_METRIC, bgpv4Route.getMetric())
        .put(COL_LOCAL_PREF, bgpv4Route.getLocalPreference())
        .put(
            COL_COMMUNITIES,
            bgpv4Route.getCommunities().stream()
                .map(Community::toString)
                .collect(toImmutableList()))
        .put(COL_ORIGIN_PROTOCOL, bgpv4Route.getSrcProtocol())
        .put(COL_TAG, bgpv4Route.getTag() == Route.UNSET_ROUTE_TAG ? null : bgpv4Route.getTag())
        .build();
  }

  static Row evpnRouteToRow(
      String hostName,
      String vrfName,
      EvpnRoute<?, ?> evpnRoute,
      Map<String, ColumnMetadata> columnMetadataMap) {
    // If the route's next hop IP is for internal use, do not show it in the row
    Ip nextHopIp =
        INTERNAL_USE_IPS.contains(evpnRoute.getNextHopIp()) ? null : evpnRoute.getNextHopIp();
    return Row.builder(columnMetadataMap)
        .put(COL_NODE, new Node(hostName))
        .put(COL_VRF_NAME, vrfName)
        .put(COL_NETWORK, evpnRoute.getNetwork())
        .put(COL_NEXT_HOP_IP, nextHopIp)
        .put(COL_NEXT_HOP_INTERFACE, evpnRoute.getNextHopInterface())
        .put(COL_PROTOCOL, evpnRoute.getProtocol())
        .put(COL_AS_PATH, evpnRoute.getAsPath().getAsPathString())
        .put(COL_METRIC, evpnRoute.getMetric())
        .put(COL_LOCAL_PREF, evpnRoute.getLocalPreference())
        .put(
            COL_COMMUNITIES,
            evpnRoute.getCommunities().stream().map(Community::toString).collect(toImmutableList()))
        .put(COL_ORIGIN_PROTOCOL, evpnRoute.getSrcProtocol())
        .put(COL_TAG, evpnRoute.getTag() == Route.UNSET_ROUTE_TAG ? null : evpnRoute.getTag())
        .put(COL_ROUTE_DISTINGUISHER, evpnRoute.getRouteDistinguisher())
        .build();
  }

  /**
   * Converts {@link List} of {@link DiffRoutesOutput} to {@link Row}s with one row corresponding to
   * each {@link DiffRoutesOutput#getDiffInAttributes} of the {@link DiffRoutesOutput}
   *
   * @param diffRoutesList {@link List} of {@link DiffRoutesOutput} for {@link Bgpv4Route}s
   * @return {@link Multiset} of {@link Row}s
   */
  static Multiset<Row> getBgpRouteRowsDiff(
      List<DiffRoutesOutput> diffRoutesList, RibProtocol ribProtocol) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap = getDiffTableMetadata(ribProtocol).toColumnMap();
    for (DiffRoutesOutput diffRoutesOutput : diffRoutesList) {
      RouteRowKey routeRowKey = diffRoutesOutput.getRouteRowKey();
      String hostName = routeRowKey.getHostName();
      String vrfName = routeRowKey.getVrfName();
      Prefix network = routeRowKey.getPrefix();
      RouteRowSecondaryKey routeRowSecondaryKey = diffRoutesOutput.getRouteRowSecondaryKey();
      KeyPresenceStatus secondaryKeyPresenceStatus =
          diffRoutesOutput.getRouteRowSecondaryKeyStatus();

      for (List<RouteRowAttribute> routeRowAttributeInBaseAndRef :
          diffRoutesOutput.getDiffInAttributes()) {
        Row.RowBuilder rowBuilder = Row.builder(columnMetadataMap);
        rowBuilder
            .put(COL_NODE, new Node(hostName))
            .put(COL_VRF_NAME, vrfName)
            .put(COL_NETWORK, network);

        RouteRowAttribute routeRowAttributeBase = routeRowAttributeInBaseAndRef.get(0);
        RouteRowAttribute routeRowAttributeRef = routeRowAttributeInBaseAndRef.get(1);

        rowBuilder.put(
            COL_ROUTE_ENTRY_PRESENCE,
            getRouteEntryPresence(
                secondaryKeyPresenceStatus, routeRowAttributeBase, routeRowAttributeRef));

        populateSecondaryKeyAttrs(routeRowSecondaryKey, secondaryKeyPresenceStatus, rowBuilder);
        populateBgpRouteAttributes(rowBuilder, routeRowAttributeBase, true);
        populateBgpRouteAttributes(rowBuilder, routeRowAttributeRef, false);

        rows.add(rowBuilder.build());
      }
    }
    return rows;
  }

  /**
   * Populates the {@link RowBuilder} for differential answer of {@link RoutesAnswerer} with
   * attributes of {@link RouteRowSecondaryKey} for base and reference snapshot
   *
   * @param routeRowSecondaryKey {@link RouteRowSecondaryKey} for the current {@link Row} of the
   *     differential answer
   * @param secondaryKeyPresence {@link KeyPresenceStatus} for the routeRowSecondaryKey
   * @param rowBuilder {@link RowBuilder} for the current row
   */
  private static void populateSecondaryKeyAttrs(
      RouteRowSecondaryKey routeRowSecondaryKey,
      KeyPresenceStatus secondaryKeyPresence,
      RowBuilder rowBuilder) {
    Ip nextHopIp = routeRowSecondaryKey.getNextHopIp();
    String protocol = routeRowSecondaryKey.getProtocol();
    // populating base columns for secondary key if it is present in base snapshot or in both
    // snapshots
    if (secondaryKeyPresence == KeyPresenceStatus.IN_BOTH
        || secondaryKeyPresence == KeyPresenceStatus.ONLY_IN_SNAPSHOT) {
      rowBuilder
          .put(COL_BASE_PREFIX + COL_NEXT_HOP_IP, nextHopIp)
          .put(COL_BASE_PREFIX + COL_PROTOCOL, protocol);
    }
    // populating reference columns for secondary key if it is present in reference snapshot or in
    // both snapshots
    if (secondaryKeyPresence == KeyPresenceStatus.IN_BOTH
        || secondaryKeyPresence == KeyPresenceStatus.ONLY_IN_REFERENCE) {
      rowBuilder
          .put(COL_DELTA_PREFIX + COL_NEXT_HOP_IP, nextHopIp)
          .put(COL_DELTA_PREFIX + COL_PROTOCOL, protocol);
    }
  }

  /**
   * Computes RoutePresenceEntryStatus using secondary key status and pairs of routeRowAttributes in
   * base and reference
   */
  private static RouteEntryPresenceStatus getRouteEntryPresence(
      KeyPresenceStatus secondaryKeyStatus,
      RouteRowAttribute routeRowAttributeBase,
      RouteRowAttribute routeRowAttributeReference) {
    RouteEntryPresenceStatus routeEntryPresenceStatus;
    if (secondaryKeyStatus.equals(KeyPresenceStatus.IN_BOTH)) {
      if (routeRowAttributeBase != null && routeRowAttributeReference != null) {
        routeEntryPresenceStatus =
            routeRowAttributeBase.equals(routeRowAttributeReference)
                ? RouteEntryPresenceStatus.UNCHANGED
                : RouteEntryPresenceStatus.CHANGED;

      } else {
        routeEntryPresenceStatus =
            routeRowAttributeBase != null
                ? RouteEntryPresenceStatus.ONLY_IN_SNAPSHOT
                : RouteEntryPresenceStatus.ONLY_IN_REFERENCE;
      }
    } else {
      routeEntryPresenceStatus =
          secondaryKeyStatus == KeyPresenceStatus.ONLY_IN_REFERENCE
              ? RouteEntryPresenceStatus.ONLY_IN_REFERENCE
              : RouteEntryPresenceStatus.ONLY_IN_SNAPSHOT;
    }
    return routeEntryPresenceStatus;
  }

  private static void populateBgpRouteAttributes(
      RowBuilder rowBuilder, @Nullable RouteRowAttribute routeRowAttribute, boolean base) {
    rowBuilder
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_AS_PATH,
            routeRowAttribute != null && routeRowAttribute.getAsPath() != null
                ? routeRowAttribute.getAsPath().getAsPathString()
                : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_METRIC,
            routeRowAttribute != null ? routeRowAttribute.getMetric() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_LOCAL_PREF,
            routeRowAttribute != null ? routeRowAttribute.getLocalPreference() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_COMMUNITIES,
            routeRowAttribute != null ? routeRowAttribute.getCommunities() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_ORIGIN_PROTOCOL,
            routeRowAttribute != null ? routeRowAttribute.getOriginProtocol() : null)
        .put(
            (base ? COL_BASE_PREFIX : COL_DELTA_PREFIX) + COL_TAG,
            routeRowAttribute != null ? routeRowAttribute.getTag() : null);
  }

  /**
   * Converts {@link List} of {@link DiffRoutesOutput} to {@link Row}s with one row corresponding to
   * each {@link DiffRoutesOutput#getDiffInAttributes} of the {@link DiffRoutesOutput}
   *
   * @param diffRoutesList {@link List} of {@link DiffRoutesOutput} for routes in Main RIB
   * @return {@link Multiset} of {@link Row}s
   */
  static Multiset<Row> getAbstractRouteRowsDiff(List<DiffRoutesOutput> diffRoutesList) {
    Map<String, ColumnMetadata> columnMetadataMap =
        getDiffTableMetadata(RibProtocol.MAIN).toColumnMap();
    Multiset<Row> rows = HashMultiset.create();
    for (DiffRoutesOutput diffRoutesOutput : diffRoutesList) {
      RouteRowKey routeRowKey = diffRoutesOutput.getRouteRowKey();
{'fraction_non_alphanumeric': 0.09107672933345327, 'fraction_numerical': 0.0019339749932535755, 'mean_word_length': 2.819048436963243, 'pattern_counts': {'":': 0, '<': 91, '<?xml version=': 0, '>': 115, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 4}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 50, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6747481', 'n_tokens_mistral': 13059, 'n_tokens_neox': 12688, 'n_words': 2712}