code: /**
   * This file is part of Eclipse Steady.
   *
   * 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.
   *
   * SPDX-License-Identifier: Apache-2.0
   * SPDX-FileCopyrightText: Copyright (c) 2018-2020 SAP SE or an SAP affiliate company and Eclipse Steady contributors
   */
  package org.eclipse.steady.cg;
  
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.Map;
  
  import org.apache.logging.log4j.Logger;
  import org.eclipse.steady.shared.json.model.ConstructId;
  
  import com.ibm.wala.util.graph.Graph;
  
  /**
   * <p>PrunedGraphGetPaths class.</p>
   */
  public class PrunedGraphGetPaths extends AbstractGetPaths {
  
    private static final Logger log = org.apache.logging.log4j.LogManager.getLogger();
  
    private long start_millis = System.currentTimeMillis(), end_millis = System.currentTimeMillis();
  
    private Map<Integer, HashSet<Integer>> edges = new HashMap<Integer, HashSet<Integer>>();
  
    /**
     * <p>Constructor for PrunedGraphGetPaths.</p>
     *
     * @param _graph a {@link com.ibm.wala.util.graph.Graph} object.
     * @param _nodeid a {@link java.util.ArrayList} object.
     */
    public PrunedGraphGetPaths(Graph<Integer> _graph, ArrayList<ConstructId> _nodeid) {
      super(_graph, _nodeid);
    }
  
    /** {@inheritDoc} */
    public HashSet<LinkedList<ConstructId>> getAllPaths(ConstructId _src, ConstructId _tgt) {
      this.start_millis = System.currentTimeMillis();
      int src_id = this.nodeId.indexOf(_src), tgt_id = this.nodeId.indexOf(_tgt);
      this.getAllEdges(tgt_id);
      this.end_millis = System.currentTimeMillis();
      PrunedGraphGetPaths.log.info(
          "Finished computing all edges in [ "
              + (this.end_millis - this.start_millis)
              + " millisecs]");
      LinkedList<Integer> singlepath = new LinkedList<Integer>();
      HashSet<LinkedList<Integer>> allpaths = new HashSet<LinkedList<Integer>>();
      this.assemblePath(src_id, tgt_id, singlepath, allpaths);
      HashSet<LinkedList<ConstructId>> result = new HashSet<LinkedList<ConstructId>>();
      for (LinkedList<Integer> p : allpaths) {
        LinkedList<ConstructId> newp = new LinkedList<ConstructId>();
        for (Integer i : p) newp.add(this.nodeId.get(i));
        result.add(newp);
      }
      return result;
    }
  
    private void assemblePath(
        Integer _src,
        Integer _tgt,
        LinkedList<Integer> _path,
        HashSet<LinkedList<Integer>> _allpaths) {
      if (_src.equals(_tgt)) {
        LinkedList<Integer> newPath = new LinkedList<Integer>();
        newPath.addAll(_path);
        _allpaths.add(newPath);
        _path.removeLast();
        if ((!_allpaths.isEmpty()) && _allpaths.size() % 5 == 0) {
          this.end_millis = System.currentTimeMillis();
          PrunedGraphGetPaths.log.info(
              "Found 5 more paths in [ " + (this.end_millis - this.start_millis) + " millisecs]");
        }
        return;
      } else {
        HashSet<Integer> edges = this.edges.get(_src);
        if (edges != null) {
          for (Integer i : edges) {
            if (!_path.contains(i)) {
              _path.add(i);
              assemblePath(i, _tgt, _path, _allpaths);
            }
          }
        }
      }
      if (_path != null && !_path.isEmpty()) _path.removeLast();
    }
  
    /**
     * Prune the callgraph, make it only contain all edges heading to the target
     * (_tgt)
     *
     * @param _tgt
     * @return
     */
    private void getAllEdges(Integer _tgt) {
      Iterator<Integer> nodes = this.graph.iterator();
      Integer node = null;
      // Intialization: no edge at all in the pruned callgraph
      while (nodes.hasNext()) {
        node = nodes.next();
        if (node.equals(_tgt)) {
          this.edges.put(node, new HashSet<Integer>());
        } else this.edges.put(node, null);
      }
      computeAllEdges(_tgt);
    }
  
    /**
     * Recursive method of getAllEdges, update the Map _edges
     *
     * @param _tgt
     * @param _edges
     * @return
     */
    private void computeAllEdges(Integer _tgt) {
      Iterator<Integer> predNodes = this.graph.getPredNodes(_tgt);
      Integer prednode = null;
      while (predNodes.hasNext()) {
        prednode = predNodes.next();
        HashSet<Integer> newedge = this.edges.get(prednode);
        if (newedge == null) {
          newedge = new HashSet<Integer>();
        }
        if (!newedge.contains(_tgt)) {
          newedge.add(_tgt);
          this.edges.put(prednode, newedge);
          computeAllEdges(prednode);
        }
      }
    }
  }
  