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

import static com.google.common.base.MoreObjects.firstNonNull;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.collect.ImmutableList.toImmutableList;
import static java.util.Comparator.comparingInt;
import static org.batfish.datamodel.questions.BgpRouteStatus.BACKUP;
import static org.batfish.datamodel.questions.BgpRouteStatus.BEST;
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_CLUSTER_LIST;
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_ORIGINATOR_ID;
import static org.batfish.question.routes.RoutesAnswerer.COL_ORIGIN_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_ORIGIN_TYPE;
import static org.batfish.question.routes.RoutesAnswerer.COL_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_RECEIVED_FROM_IP;
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_STATUS;
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.COL_WEIGHT;
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.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Multimap;
import com.google.common.collect.Multiset;
import com.google.common.collect.Table;
import java.util.ArrayList;
import java.util.EnumMap;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;
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.FinalMainRib;
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.questions.BgpRouteStatus;
import org.batfish.datamodel.route.nh.LegacyNextHops;
import org.batfish.datamodel.route.nh.NextHop;
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.PrefixMatchType;
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;
    }
    Set<String> nextNodes = ipOwners.getOrDefault(nextHopIp, ImmutableSet.of());
    if (nextNodes.size() == 1) {
      return Iterables.getOnlyElement(nextNodes);
    }
    // TODO: https://github.com/batfish/batfish/issues/1862 can try harder for multiple outs
    return 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 matchingVrfsByNode {@link Multimap} of vrfs grouped by node 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 routes
   * @param prefixMatchType {@link PrefixMatchType} used to select which prefixes are reported
   * @return {@link Multiset} of {@link Row}s representing the routes
   */
  static <T extends AbstractRouteDecorator> Multiset<Row> getMainRibRoutes(
      Table<String, String, FinalMainRib> ribs,
      Multimap<String, String> matchingVrfsByNode,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      PrefixMatchType prefixMatchType) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap =
        getTableMetadata(RibProtocol.MAIN).toColumnMap();
    matchingVrfsByNode.forEach(
        (hostname, vrfName) ->
            Optional.ofNullable(ribs.get(hostname, vrfName))
                .map(rib -> getMatchingPrefixRoutes(prefixMatchType, network, rib))
                .orElse(Stream.empty())
                .filter(route -> protocolSpec.getProtocols().contains(route.getProtocol()))
                .forEach(
                    route ->
                        rows.add(abstractRouteToRow(hostname, vrfName, route, columnMetadataMap))));
    return rows;
  }

  /**
   * Given the prefixMatchType and network (user input), returns routes from the {@code rib} that
   * match.
   */
  @VisibleForTesting
  static Stream<AbstractRoute> getMatchingPrefixRoutes(
      PrefixMatchType prefixMatchType, @Nullable Prefix network, FinalMainRib rib) {
    if (network == null) {
      // everything matches if there is not user input
      return rib.getRoutes().stream();
    }
    if (prefixMatchType == PrefixMatchType.LONGEST_PREFIX_MATCH) {
      return rib.longestPrefixMatch(network).stream();
    }
    return rib.getRoutes().stream()
        .filter(r -> prefixMatches(prefixMatchType, network, r.getNetwork()));
  }<commit_msg>RoutesAnswerer: faster main rib exact match (#8355)<commit_after>package org.batfish.question.routes;

import static com.google.common.base.MoreObjects.firstNonNull;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.collect.ImmutableList.toImmutableList;
import static java.util.Comparator.comparingInt;
import static org.batfish.datamodel.questions.BgpRouteStatus.BACKUP;
import static org.batfish.datamodel.questions.BgpRouteStatus.BEST;
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_CLUSTER_LIST;
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_ORIGINATOR_ID;
import static org.batfish.question.routes.RoutesAnswerer.COL_ORIGIN_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_ORIGIN_TYPE;
import static org.batfish.question.routes.RoutesAnswerer.COL_PROTOCOL;
import static org.batfish.question.routes.RoutesAnswerer.COL_RECEIVED_FROM_IP;
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_STATUS;
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.COL_WEIGHT;
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.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Multimap;
import com.google.common.collect.Multiset;
import com.google.common.collect.Table;
import java.util.ArrayList;
import java.util.EnumMap;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;
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.FinalMainRib;
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.questions.BgpRouteStatus;
import org.batfish.datamodel.route.nh.LegacyNextHops;
import org.batfish.datamodel.route.nh.NextHop;
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.PrefixMatchType;
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;
    }
    Set<String> nextNodes = ipOwners.getOrDefault(nextHopIp, ImmutableSet.of());
    if (nextNodes.size() == 1) {
      return Iterables.getOnlyElement(nextNodes);
    }
    // TODO: https://github.com/batfish/batfish/issues/1862 can try harder for multiple outs
    return 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 matchingVrfsByNode {@link Multimap} of vrfs grouped by node 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 routes
   * @param prefixMatchType {@link PrefixMatchType} used to select which prefixes are reported
   * @return {@link Multiset} of {@link Row}s representing the routes
   */
  static <T extends AbstractRouteDecorator> Multiset<Row> getMainRibRoutes(
      Table<String, String, FinalMainRib> ribs,
      Multimap<String, String> matchingVrfsByNode,
      @Nullable Prefix network,
      RoutingProtocolSpecifier protocolSpec,
      PrefixMatchType prefixMatchType) {
    Multiset<Row> rows = HashMultiset.create();
    Map<String, ColumnMetadata> columnMetadataMap =
        getTableMetadata(RibProtocol.MAIN).toColumnMap();
    matchingVrfsByNode.forEach(
        (hostname, vrfName) ->
            Optional.ofNullable(ribs.get(hostname, vrfName))
                .map(rib -> getMatchingPrefixRoutes(prefixMatchType, network, rib))
                .orElse(Stream.empty())
                .filter(route -> protocolSpec.getProtocols().contains(route.getProtocol()))
                .forEach(
                    route ->
                        rows.add(abstractRouteToRow(hostname, vrfName, route, columnMetadataMap))));
    return rows;
  }

  /**
   * Given the prefixMatchType and network (user input), returns routes from the {@code rib} that
   * match.
   */
  @VisibleForTesting
  static Stream<AbstractRoute> getMatchingPrefixRoutes(
      PrefixMatchType prefixMatchType, @Nullable Prefix network, FinalMainRib rib) {
    if (network == null) {
      // everything matches if there is not user input
      return rib.getRoutes().stream();
    }
    switch (prefixMatchType) {
      case EXACT:
        return rib.getRoutes(network).stream();
      case LONGEST_PREFIX_MATCH:
        return rib.longestPrefixMatch(network).stream();
      default:
        return rib.getRoutes().stream()
            .filter(r -> prefixMatches(prefixMatchType, network, r.getNetwork()));
    }
  }
{'fraction_non_alphanumeric': 0.09612054035330793, 'fraction_numerical': 0.0019628218450525345, 'mean_word_length': 4.508108108108108, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 41, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 4}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2501287', 'n_tokens_mistral': 5487, 'n_tokens_neox': 5385, 'n_words': 1048}