/*
 * Copyright (c) 2001, 2006, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

package sun.jvm.hotspot.utilities;

import java.io.*;
import java.util.*;
import sun.jvm.hotspot.debugger.*;
import sun.jvm.hotspot.gc_interface.*;
import sun.jvm.hotspot.memory.*;
import sun.jvm.hotspot.oops.*;
import sun.jvm.hotspot.runtime.*;

/** Finds all paths from roots to the specified set of objects. NOTE:
    currently only a subset of the roots known to the VM is exposed to
    the SA: objects on the stack, static fields in classes, and JNI
    handles. These should be most of the user-level roots keeping
    objects alive. */

public class LivenessAnalysis {
  // Used for debugging this code
  private static final boolean DEBUG = false;

  private LivenessAnalysis() {}

  public static LivenessPathList computeAllLivenessPaths(Oop target) {
    LivenessPathList list = computeAllLivenessPaths(target, true);
    if ((list == null) || (list.size() == 0)) {
      // Dead object
      return null;
    }
    return list;
  }

  //---------------------------------------------------------------------------
  // Internals only below this point
  //

  // Returns true if a new path was completed, otherwise false
  // indicating there were no more paths to complete.
  //
  // The trimPathsThroughPopularObjects flag alters the behavior of
  // the returned results. If true, then if multiple paths to
  // different roots all go through a particular popular object, those
  // paths will be truncated and only one (arbitrary one) will be be
  // returned. On the other hand, if the target object itself is
  // popular and there are multiple distinct paths to it (indicating
  // that there are multiple objects pointing directly to it) then all
  // of those paths will be reported.
  private static LivenessPathList computeAllLivenessPaths(Oop target, boolean trimPathsThroughPopularObjects) {
    ReversePtrs rev = VM.getVM().getRevPtrs();
    if (rev == null) {
      throw new RuntimeException("LivenessAnalysis requires ReversePtrs to have been computed");
    }

    // Currently the reverse pointer analysis returns non-null results
    // only for live objects
    if (rev.get(target) == null) {
      // Object is dead
      return null;
    }

    // HashSet of Oops acting as a bit mask indicating which ones have
    // already been traversed
    Set/*<Oop>*/ visitedOops = new HashSet/*<Oop>*/();

      // IdentityHashMap of LivenessElements acting as a bit mask
      // indicating which roots have already been traversed
    Map/*<LivenessElement, LivenessElement>*/ visitedRoots =
      new IdentityHashMap/*<LivenessElement, LivenessElement>*/();

    visitedOops.add(target);

    // Construct the initial LivenessPath
    LivenessPathList list = new LivenessPathList();
    {
      LivenessPath path = new LivenessPath();
      path.push(new LivenessPathElement(target, null));
      list.add(path);
    }

    // Iterate until done
    while (true) {
      // See if there are any incomplete paths left
      LivenessPath path = null;

      for (int i = list.size() - 1; i >= 0; i--) {
        LivenessPath tmp = list.get(i);
        if (!tmp.isComplete()) {
          path = tmp;
          break;
        }
      }

      // If no incomplete paths left, return
      if (path == null) {
        return list;
      }

      // Try to complete this path

      // Remove the path from the list of reported ones in
      // anticipation of completing it
      list.remove(path);

      try {
        // Fetch next set of reverse pointers for the last object on
        // the list
        ArrayList/*<LivenessPathElement>*/ nextPtrs =
          rev.get(path.peek().getObj());

        // Depending on exactly what the reverse pointers analysis
        // yields, these results may be null, although currently they
        // won't be
        if (nextPtrs != null) {
          // Iterate these
          for (Iterator iter = nextPtrs.iterator(); iter.hasNext(); ) {
            LivenessPathElement nextElement = (LivenessPathElement) iter.next();
            // See whether we've visited this element yet
            if ((nextElement.isRoot() && (visitedRoots.get(nextElement) == null)) ||
                (!nextElement.isRoot() && !visitedOops.contains(nextElement.getObj()))) {
              // Show we've visited this one
              if (nextElement.isRoot()) {
                visitedRoots.put(nextElement, nextElement);
              } else {
                visitedOops.add(nextElement.getObj());
              }

              // Create a new LivenessPath for each one
              LivenessPath nextPath = path.copy();
              nextPath.push(nextElement);

              // Regardless of whether we found a root, put the
              // original path back on the list because we're going to
              // do depth-first searching rather than breadth-first
              list.add(path);
              list.add(nextPath);

              // See whether this path is complete (i.e., it
              // terminates in a root)
              if (trimPathsThroughPopularObjects && nextElement.isRoot()) {
                // Go back through the path list and remove all
                // incomplete paths ending in any of the intermediate
                // (non-root and non-terminal) nodes in this path.
                // This has the effect of removing multiple paths
                // going through popular objects.
                for (int i = 1; i < nextPath.size() - 1; i++) {
                  LivenessPathElement el = nextPath.get(i);
                  int j = 0;
                  while (j < list.size()) {
                    LivenessPath curPath = list.get(j);
                    // We can use an object identity since these
                    // intermediate nodes are canonicalized via the
                    // ReversePtrsAnalysis
                    if (curPath.peek() == el) {
                      list.remove(curPath);
                    } else {
                      j++;
                    }
                  }
                }
              }

              // Do depth-first searching, not breadth-first
              break;
            }
          }
        }
      } catch (Exception e) {
        System.err.println("LivenessAnalysis: WARNING: " + e +
                           " during traversal");
      }
    }
  }
}