text: /*
   * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
   */
  
  #include "ifmap/ifmap_graph_walker.h"
  
  #include <boost/bind.hpp>
  #include "base/logging.h"
  #include "base/task_trigger.h"
  #include "db/db_graph.h"
  #include "db/db_table.h"
  #include "ifmap/ifmap_client.h"
  #include "ifmap/ifmap_exporter.h"
  #include "ifmap/ifmap_link.h"
  #include "ifmap/ifmap_log.h"
  #include "ifmap/ifmap_table.h"
  #include "ifmap/ifmap_server.h"
  #include "ifmap/ifmap_log_types.h"
  #include "ifmap/ifmap_update.h"
  #include "ifmap/ifmap_util.h"
  #include "ifmap/ifmap_whitelist.h"
  #include "schema/vnc_cfg_types.h"
  
  class GraphPropagateFilter : public DBGraph::VisitorFilter {
  public:
      GraphPropagateFilter(IFMapExporter *exporter,
                           const IFMapTypenameWhiteList *type_filter,
                           const BitSet &bitset)
              : exporter_(exporter),
                type_filter_(type_filter),
                bset_(bitset) {
      }
  
      bool VertexFilter(const DBGraphVertex *vertex) const {
          return type_filter_->VertexFilter(vertex);
      }
  
      bool EdgeFilter(const DBGraphVertex *source, const DBGraphVertex *target,
                      const DBGraphEdge *edge) const {
          bool accept = type_filter_->EdgeFilter(source, target, edge);
          if (!accept) {
              return false;
          }
          const IFMapNode *tgt = static_cast<const IFMapNode *>(target);
          const IFMapNodeState *state = NodeStateLookup(tgt);
          if (state != NULL && state->interest().Contains(bset_)) {
              return false;
          }
  
          return true;
      }
  
      const IFMapNodeState *NodeStateLookup(const IFMapNode *node) const {
          const DBTable *table = node->table();
          const DBState *state =
                  node->GetState(table, exporter_->TableListenerId(table));
          return static_cast<const IFMapNodeState *>(state);
      }
  
  private:
      IFMapExporter *exporter_;
      const IFMapTypenameWhiteList *type_filter_;
      const BitSet &bset_;
  };
  
  IFMapGraphWalker::IFMapGraphWalker(DBGraph *graph, IFMapExporter *exporter)
      : graph_(graph),
        exporter_(exporter),
        link_delete_walk_trigger_(new TaskTrigger(
                          boost::bind(&IFMapGraphWalker::LinkDeleteWalk, this),
                          TaskScheduler::GetInstance()->GetTaskId("db::DBTable"), 0)),
        walk_client_index_(BitSet::npos) {
      traversal_white_list_.reset(new IFMapTypenameWhiteList());
      AddNodesToWhitelist();
      AddLinksToWhitelist();
  }
  
  IFMapGraphWalker::~IFMapGraphWalker() {
  }
  
  void IFMapGraphWalker::JoinVertex(DBGraphVertex *vertex, const BitSet &bset) {
      IFMapNode *node = static_cast<IFMapNode *>(vertex);
      IFMapNodeState *state = exporter_->NodeStateLocate(node);
      IFMAP_DEBUG(JoinVertex, vertex->ToString(), state->interest().ToString(),
                  bset.ToString());
      exporter_->StateInterestOr(state, bset);
      node->table()->Change(node);
      // Mark all dependent links as potentially modified.
      for (IFMapNodeState::iterator iter = state->begin(); iter != state->end();
           ++iter) {
          DBTable *table = exporter_->link_table();
          table->Change(iter.operator->());
      }
  }
  
  void IFMapGraphWalker::ProcessLinkAdd(IFMapNode *lnode, IFMapNode *rnode,
                                        const BitSet &bset) {
      GraphPropagateFilter filter(exporter_, traversal_white_list_.get(), bset);
      graph_->Visit(rnode,
                    boost::bind(&IFMapGraphWalker::JoinVertex, this, _1, bset),
                    0,
                    filter);
  }
  
  void IFMapGraphWalker::LinkAdd(IFMapNode *lnode, const BitSet &lhs,
                                 IFMapNode *rnode, const BitSet &rhs) {
      IFMAP_DEBUG(LinkOper, "LinkAdd", lnode->ToString(), rnode->ToString(),
                  lhs.ToString(), rhs.ToString());
      if (!lhs.empty() && !rhs.Contains(lhs) &&
          traversal_white_list_->VertexFilter(rnode) &&
          traversal_white_list_->EdgeFilter(lnode, rnode, NULL)) {
          ProcessLinkAdd(lnode, rnode, lhs);
      }
      if (!rhs.empty() && !lhs.Contains(rhs) &&
          traversal_white_list_->VertexFilter(lnode) &&
          traversal_white_list_->EdgeFilter(rnode, lnode, NULL)) {
          ProcessLinkAdd(rnode, lnode, rhs);
      }
  }
  
  void IFMapGraphWalker::LinkRemove(const BitSet &bset) {
      OrLinkDeleteClients(bset);          // link_delete_clients_ | bset
      link_delete_walk_trigger_->Set();
  }
  
  // Check if the neighbor or link to neighbor should be filtered. Returns true 
  // if rnode or link to rnode should be filtered.
  bool IFMapGraphWalker::FilterNeighbor(IFMapNode *lnode, IFMapNode *rnode) {
      if (!traversal_white_list_->VertexFilter(rnode) ||
          !traversal_white_list_->EdgeFilter(lnode, rnode, NULL)) {
          return true;
      }
      return false;
  }
  
  void IFMapGraphWalker::RecomputeInterest(DBGraphVertex *vertex, int bit) {
      IFMapNode *node = static_cast<IFMapNode *>(vertex);
      IFMapNodeState *state = exporter_->NodeStateLocate(node);
      state->nmask_set(bit);
      UpdateNewReachableNodesTracker(bit, state);
  }
  
  bool IFMapGraphWalker::LinkDeleteWalk() {
      if (link_delete_clients_.empty()) {
          walk_client_index_ = BitSet::npos;
          return true;
      }
  
      IFMapServer *server = exporter_->server();
      size_t i;
  
      // Get the index of the client we want to start with.
      if (walk_client_index_ == BitSet::npos) {
          i = link_delete_clients_.find_first();
      } else {
          // walk_client_index_ was the last client that we finished processing.
          i = link_delete_clients_.find_next(walk_client_index_);
      }
      int count = 0;
      BitSet done_set;
      while (i != BitSet::npos) {
          IFMapClient *client = server->GetClient(i);
          assert(client);
          AddNewReachableNodesTracker(client->index());
  
          IFMapTable *table = IFMapTable::FindTable(server->database(),
                                                    "virtual-router");
          IFMapNode *node = table->FindNode(client->identifier());
          if ((node != NULL) && node->IsVertexValid()) {
              graph_->Visit(node,
                  boost::bind(&IFMapGraphWalker::RecomputeInterest, this, _1, i),
                  0, *traversal_white_list_.get());
          }
          done_set.set(i);
          if (++count == kMaxLinkDeleteWalks) {
              // client 'i' has been processed. If 'i' is the last bit set, we
              // will return true below. Else we will return false and there
              // is atleast one more bit left to process.
              break;
          }
  
          i = link_delete_clients_.find_next(i);
      }
      // Remove the subset of clients that we have finished processing.
      ResetLinkDeleteClients(done_set);
  
      LinkDeleteWalkBatchEnd(done_set);
  
      if (link_delete_clients_.empty()) {
          walk_client_index_ = BitSet::npos;
          return true;
      } else {
          walk_client_index_ = i;
          return false;
      }
  }
  
  void IFMapGraphWalker::OrLinkDeleteClients(const BitSet &bset) {
      link_delete_clients_.Set(bset);     // link_delete_clients_ | bset
  }
  
  void IFMapGraphWalker::ResetLinkDeleteClients(const BitSet &bset) {
      link_delete_clients_.Reset(bset);
  }
  
  void IFMapGraphWalker::CleanupInterest(int client_index, IFMapNode *node,
                                         IFMapNodeState *state) {
      BitSet rm_mask;
      rm_mask.set(client_index);
  
      // interest = interest - rm_mask + nmask
  
      if (!state->interest().empty() && !state->nmask().empty()) {
          IFMAP_DEBUG(CleanupInterest, node->ToString(),
                      state->interest().ToString(), rm_mask.ToString(),
                      state->nmask().ToString());
      }
      BitSet ninterest;
      ninterest.BuildComplement(state->interest(), rm_mask);
      ninterest |= state->nmask();
      state->nmask_clear();
      if (state->interest() == ninterest) {
          return;
      }
  
      exporter_->StateInterestSet(state, ninterest);
      node->table()->Change(node);
  
      // Mark all dependent links as potentially modified.
      for (IFMapNodeState::iterator iter = state->begin();
           iter != state->end(); ++iter) {
          DBTable *table = exporter_->link_table();
          table->Change(iter.operator->());
      }
  }
  
  // Cleanup all the graph nodes that were reachable before this link delete.
  // After this link delete, these nodes may still be reachable. But, its
  // also possible that the link delete has made them unreachable.
  void IFMapGraphWalker::OldReachableNodesCleanupInterest(int client_index) {
      IFMapState *state = NULL;
      IFMapNode *node = NULL;
      IFMapExporter::Cs_citer iter =
          exporter_->ClientConfigTrackerBegin(client_index);
      IFMapExporter::Cs_citer end_iter =
          exporter_->ClientConfigTrackerEnd(client_index);
  
      while (iter != end_iter) {
          state = *iter;
          // Get the iterator to the next element before calling
          // CleanupInterest() since the state might be removed from the
          // client's config-tracker, thereby invalidating the iterator of the
          // container we are iterating over.
          ++iter;
          if (state->IsNode()) {
              node = state->GetIFMapNode();
              assert(node);
              IFMapNodeState *nstate = exporter_->NodeStateLookup(node);
              assert(state == nstate);
              CleanupInterest(client_index, node, nstate);
          }
      }
  }
  
  // Cleanup all the graph nodes that were not reachable before the link delete
  // but are reachable now. Note, we store nodes in new_reachable_nodes_tracker_
  // only if we visited them during the graph-walk via RecomputeInterest() and if
  // their interest bit was not set i.e. they were not reachable before we
  // started the walk.
  void IFMapGraphWalker::NewReachableNodesCleanupInterest(int client_index) {
      IFMapState *state = NULL;
      IFMapNode *node = NULL;
      ReachableNodesSet *rnset = new_reachable_nodes_tracker_.at(client_index);
  
      for (Rns_citer iter = rnset->begin(); iter != rnset->end(); ++iter) {
          state = *iter;
          assert(state->IsNode());
          node = state->GetIFMapNode();
          assert(node);
          IFMapNodeState *nstate = exporter_->NodeStateLookup(node);
          assert(state == nstate);
          CleanupInterest(client_index, node, nstate);
      }
      DeleteNewReachableNodesTracker(client_index);
  }
  
  void IFMapGraphWalker::LinkDeleteWalkBatchEnd(const BitSet &done_set) {
      for (size_t i = done_set.find_first(); i != BitSet::npos;
              i = done_set.find_next(i)) {
          // Examine all the nodes that were reachable before the link delete.
          OldReachableNodesCleanupInterest(i);
          // Examine all the nodes that were not reachable before the link
          // delete but are now reachable.
          NewReachableNodesCleanupInterest(i);
      }
  }
  
  void IFMapGraphWalker::AddNewReachableNodesTracker(int client_index) {
      if (client_index >= (int)new_reachable_nodes_tracker_.size()) {
          new_reachable_nodes_tracker_.resize(client_index + 1, NULL);
      }
      assert(new_reachable_nodes_tracker_[client_index] == NULL);
      ReachableNodesSet *rnset = new ReachableNodesSet();
      new_reachable_nodes_tracker_[client_index] = rnset;
  }
  
  void IFMapGraphWalker::DeleteNewReachableNodesTracker(int client_index) {
      ReachableNodesSet *rnset = new_reachable_nodes_tracker_.at(client_index);
      assert(rnset);
      delete rnset;
      new_reachable_nodes_tracker_[client_index] = NULL;
  }
  
  // Keep track of this node if it was unreachable earlier.
  void IFMapGraphWalker::UpdateNewReachableNodesTracker(int client_index,
                                                        IFMapState *state) {
      ReachableNodesSet *rnset = new_reachable_nodes_tracker_.at(client_index);
      assert(rnset);
      // If the interest is not set, the node was not reachable earlier but is
      // reachable now.
      if (!state->interest().test(client_index)) {
          rnset->insert(state);
      }
  }
  
  const IFMapTypenameWhiteList &IFMapGraphWalker::get_traversal_white_list()
          const {
      return *traversal_white_list_.get();
  }
  
  // The nodes listed below and the nodes in 
  // IFMapGraphTraversalFilterCalculator::CreateNodeBlackList() are mutually 
  // exclusive
  void IFMapGraphWalker::AddNodesToWhitelist() {
      traversal_white_list_->include_vertex.insert("virtual-router");
      traversal_white_list_->include_vertex.insert("virtual-machine");
      traversal_white_list_->include_vertex.insert("bgp-router");
      traversal_white_list_->include_vertex.insert("global-system-config");
      traversal_white_list_->include_vertex.insert("provider-attachment");
      traversal_white_list_->include_vertex.insert("service-instance");
      traversal_white_list_->include_vertex.insert("global-vrouter-config");
      traversal_white_list_->include_vertex.insert(
          "virtual-machine-interface");
      traversal_white_list_->include_vertex.insert("security-group");
      traversal_white_list_->include_vertex.insert("physical-router");
      traversal_white_list_->include_vertex.insert("service-template");
      traversal_white_list_->include_vertex.insert("instance-ip");
      traversal_white_list_->include_vertex.insert("virtual-network");
      traversal_white_list_->include_vertex.insert("floating-ip");
      traversal_white_list_->include_vertex.insert("customer-attachment");
      traversal_white_list_->include_vertex.insert(
          "virtual-machine-interface-routing-instance");
      traversal_white_list_->include_vertex.insert("physical-interface");
      traversal_white_list_->include_vertex.insert("domain");
      traversal_white_list_->include_vertex.insert("floating-ip-pool");
      traversal_white_list_->include_vertex.insert("logical-interface");
      traversal_white_list_->include_vertex.insert(
          "virtual-network-network-ipam");
      traversal_white_list_->include_vertex.insert("access-control-list");
      traversal_white_list_->include_vertex.insert("routing-instance");
      traversal_white_list_->include_vertex.insert("namespace");
      traversal_white_list_->include_vertex.insert("virtual-DNS");
      traversal_white_list_->include_vertex.insert("network-ipam");
      traversal_white_list_->include_vertex.insert("virtual-DNS-record");
      traversal_white_list_->include_vertex.insert("interface-route-table");
      traversal_white_list_->include_vertex.insert("virtual-ip");
      traversal_white_list_->include_vertex.insert("loadbalancer");
      traversal_white_list_->include_vertex.insert("loadbalancer-listener");
      traversal_white_list_->include_vertex.insert("loadbalancer-pool");
      traversal_white_list_->include_vertex.insert("loadbalancer-member");
      traversal_white_list_->include_vertex.insert("loadbalancer-healthmonitor");
      traversal_white_list_->include_vertex.insert("subnet");
      traversal_white_list_->include_vertex.insert("service-health-check");
      traversal_white_list_->include_vertex.insert("bgp-as-a-service");
  }
  
  void IFMapGraphWalker::AddLinksToWhitelist() {
      traversal_white_list_->include_edge.insert(
          "source=virtual-router,target=virtual-machine");
      traversal_white_list_->include_edge.insert(
          "source=virtual-router,target=bgp-router");
      traversal_white_list_->include_edge.insert(
          "source=virtual-router,target=global-system-config");
      traversal_white_list_->include_edge.insert(
          "source=virtual-router,target=provider-attachment");
      traversal_white_list_->include_edge.insert(
          "source=virtual-router,target=physical-router");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine,target=service-instance");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine,target=virtual-machine-interface");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=virtual-machine");
      traversal_white_list_->include_edge.insert(
          "source=bgp-router,target=physical-router");
      traversal_white_list_->include_edge.insert(
          "source=service-instance,target=service-template");
      traversal_white_list_->include_edge.insert(
          "source=global-system-config,target=global-vrouter-config");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=virtual-machine-interface");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=instance-ip");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=virtual-network");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=security-group");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=floating-ip");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=customer-attachment");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=virtual-machine-interface-routing-instance");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=interface-route-table");       
      traversal_white_list_->include_edge.insert(
          "source=logical-interface,target=virtual-machine-interface");
      traversal_white_list_->include_edge.insert(
          "source=physical-router,target=physical-interface");
      traversal_white_list_->include_edge.insert(
          "source=physical-router,target=logical-interface");
      traversal_white_list_->include_edge.insert(
          "source=physical-router,target=virtual-network");
      traversal_white_list_->include_edge.insert(
          "source=physical-interface,target=logical-interface");
      traversal_white_list_->include_edge.insert(
          "source=service-template,target=domain");
      traversal_white_list_->include_edge.insert(
          "source=virtual-network,target=floating-ip-pool");
      traversal_white_list_->include_edge.insert(
          "source=virtual-network,target=virtual-network-network-ipam");
      traversal_white_list_->include_edge.insert(
          "source=virtual-network,target=access-control-list");
      traversal_white_list_->include_edge.insert(
          "source=virtual-network,target=routing-instance");
      traversal_white_list_->include_edge.insert(
          "source=domain,target=namespace");
      traversal_white_list_->include_edge.insert(
          "source=domain,target=virtual-DNS");
      traversal_white_list_->include_edge.insert(
          "source=virtual-network-network-ipam,target=network-ipam");
      traversal_white_list_->include_edge.insert(
          "source=virtual-DNS,target=virtual-DNS-record");
      traversal_white_list_->include_edge.insert(
          "source=security-group,target=access-control-list");
      traversal_white_list_->include_edge.insert(
          "source=service-instance,target=loadbalancer-pool");
      traversal_white_list_->include_edge.insert(
          "source=loadbalancer-pool,target=loadbalancer-healthmonitor");
      traversal_white_list_->include_edge.insert(
          "source=loadbalancer-pool,target=virtual-ip");
      traversal_white_list_->include_edge.insert(
          "source=loadbalancer-pool,target=loadbalancer-member");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=subnet");
      traversal_white_list_->include_edge.insert(
          "source=service-instance,target=loadbalancer");
      traversal_white_list_->include_edge.insert(
          "source=loadbalancer,target=loadbalancer-listener");
      traversal_white_list_->include_edge.insert(
          "source=loadbalancer-listener,target=loadbalancer-pool");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=loadbalancer");
  
      // Manually add required links not picked by the
      // IFMapGraphTraversalFilterCalculator
      traversal_white_list_->include_edge.insert(
          "source=floating-ip,target=floating-ip-pool");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface-routing-instance,target=routing-instance");
      // VDNS needs dns/dhcp info from IPAM and FQN from Domain.
      traversal_white_list_->include_edge.insert(
          "source=network-ipam,target=virtual-DNS");
      // Need this to get from floating-ip-pool to the virtual-network we are
      // getting the pool from. EG: public-network (might not have any VMs)
      traversal_white_list_->include_edge.insert(
          "source=floating-ip-pool,target=virtual-network");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=service-health-check");
      traversal_white_list_->include_edge.insert(
          "source=virtual-machine-interface,target=bgp-as-a-service");
      traversal_white_list_->include_edge.insert(
          "source=bgp-as-a-service,target=bgp-router");
      traversal_white_list_->include_edge.insert(
          "source=bgp-router,target=routing-instance");
  }
  
  