/*******************************************************************************
 * Copyright (c) 2003, 2007 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 * 
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.core.internal.jobs;

//don't use ICU because this is used for debugging only (see bug 135785)
import java.text.*;
import java.util.*;
import org.eclipse.core.internal.runtime.RuntimeLog;
import org.eclipse.core.runtime.*;
import org.eclipse.core.runtime.jobs.*;
import org.eclipse.osgi.util.NLS;

/**
 * Implementation of API type IJobManager
 * 
 * Implementation note: all the data structures of this class are protected
 * by a single lock object held as a private field in this class.  The JobManager
 * instance itself is not used because this class is publicly reachable, and third
 * party clients may try to synchronize on it.
 * 
 * The WorkerPool class uses its own monitor for synchronizing its data
 * structures. To avoid deadlock between the two classes, the JobManager
 * must NEVER call the worker pool while its own monitor is held.
 */
public class JobManager implements IJobManager {

	/**
	 * The unique identifier constant of this plug-in.
	 */
	public static final String PI_JOBS = "org.eclipse.core.jobs"; //$NON-NLS-1$

	/**
	 * Status code constant indicating an error occurred while running a plug-in.
	 * For backward compatibility with Platform.PLUGIN_ERROR left at (value = 2).
	 */
	public static final int PLUGIN_ERROR = 2;

	private static final String OPTION_DEADLOCK_ERROR = PI_JOBS + "/jobs/errorondeadlock"; //$NON-NLS-1$
	private static final String OPTION_DEBUG_BEGIN_END = PI_JOBS + "/jobs/beginend"; //$NON-NLS-1$
	private static final String OPTION_DEBUG_JOBS = PI_JOBS + "/jobs"; //$NON-NLS-1$
	private static final String OPTION_DEBUG_JOBS_TIMING = PI_JOBS + "/jobs/timing"; //$NON-NLS-1$
	private static final String OPTION_LOCKS = PI_JOBS + "/jobs/locks"; //$NON-NLS-1$
	private static final String OPTION_SHUTDOWN = PI_JOBS + "/jobs/shutdown"; //$NON-NLS-1$

	static boolean DEBUG = false;
	static boolean DEBUG_BEGIN_END = false;
	static boolean DEBUG_DEADLOCK = false;
	static boolean DEBUG_LOCKS = false;
	static boolean DEBUG_TIMING = false;
	static boolean DEBUG_SHUTDOWN = false;
	private static DateFormat DEBUG_FORMAT;

	/**
	 * The singleton job manager instance. It must be a singleton because
	 * all job instances maintain a reference (as an optimization) and have no way 
	 * of updating it.
	 */
	private static JobManager instance;
	/**
	 * Scheduling rule used for validation of client-defined rules.
	 */
	private static final ISchedulingRule nullRule = new ISchedulingRule() {
		public boolean contains(ISchedulingRule rule) {
			return rule == this;
		}

		public boolean isConflicting(ISchedulingRule rule) {
			return rule == this;
		}
	};

	/**
	 * True if this manager is active, and false otherwise.  A job manager
	 * starts out active, and becomes inactive if it has been shutdown
	 * and not restarted.
	 */
	private volatile boolean active = true;

	final ImplicitJobs implicitJobs = new ImplicitJobs(this);

	private final JobListeners jobListeners = new JobListeners();

	/**
	 * The lock for synchronizing all activity in the job manager.  To avoid deadlock,
	 * this lock must never be held for extended periods, and must never be
	 * held while third party code is being called.
	 */
	private final Object lock = new Object();

	private final LockManager lockManager = new LockManager();

	/**
	 * The pool of worker threads.
	 */
	private WorkerPool pool;

	private ProgressProvider progressProvider = null;
	/**
	 * Jobs that are currently running. Should only be modified from changeState
	 */
	private final HashSet running;

	/**
	 * Jobs that are sleeping.  Some sleeping jobs are scheduled to wake
	 * up at a given start time, while others will sleep indefinitely until woken.
	 * Should only be modified from changeState
	 */
	private final JobQueue sleeping;
	/**
	 * True if this manager has been suspended, and false otherwise.  A job manager
	 * starts out not suspended, and becomes suspended when <code>suspend</code>
	 * is invoked. Once suspended, no jobs will start running until <code>resume</code>
	 * is called.
	 */
	private boolean suspended = false;

	/**
	 * jobs that are waiting to be run. Should only be modified from changeState
	 */
	private final JobQueue waiting;

	public static void debug(String msg) {
		StringBuffer msgBuf = new StringBuffer(msg.length() + 40);
		if (DEBUG_TIMING) {
			//lazy initialize to avoid overhead when not debugging
			if (DEBUG_FORMAT == null)
				DEBUG_FORMAT = new SimpleDateFormat("HH:mm:ss.SSS"); //$NON-NLS-1$
			DEBUG_FORMAT.format(new Date(), msgBuf, new FieldPosition(0));
			msgBuf.append('-');
		}
		msgBuf.append('[').append(Thread.currentThread()).append(']').append(msg);
		System.out.println(msgBuf.toString());
	}

	/**
	 * Returns the job manager singleton. For internal use only.
	 */
	static synchronized JobManager getInstance() {
		if (instance == null)
			new JobManager();
		return instance;
	}

	/**
	 * For debugging purposes only
	 */
	private static String printJobName(Job job) {
		if (job instanceof ThreadJob) {
			Job realJob = ((ThreadJob) job).realJob;
			if (realJob != null)
				return realJob.getClass().getName();
			return "ThreadJob on rule: " + job.getRule(); //$NON-NLS-1$
		}
		return job.getClass().getName();
	}

	/**
	 * For debugging purposes only
	 */
	public static String printState(int state) {
		switch (state) {
			case Job.NONE :
				return "NONE"; //$NON-NLS-1$
			case Job.WAITING :
				return "WAITING"; //$NON-NLS-1$
			case Job.SLEEPING :
				return "SLEEPING"; //$NON-NLS-1$
			case Job.RUNNING :
				return "RUNNING"; //$NON-NLS-1$
			case InternalJob.BLOCKED :
				return "BLOCKED"; //$NON-NLS-1$
			case InternalJob.ABOUT_TO_RUN :
				return "ABOUT_TO_RUN"; //$NON-NLS-1$
			case InternalJob.ABOUT_TO_SCHEDULE :
				return "ABOUT_TO_SCHEDULE";//$NON-NLS-1$
		}
		return "UNKNOWN"; //$NON-NLS-1$
	}

	/**
	 * Note that although this method is not API, clients have historically used
	 * it to force jobs shutdown in cases where OSGi shutdown does not occur.
	 * For this reason, this method should be considered near-API and should not 
	 * be changed if at all possible. 
	 */
	public static void shutdown() {
		if (instance != null) {
			instance.doShutdown();
			instance = null;
		}
	}

	private JobManager() {
		instance = this;
		initDebugOptions();
		synchronized (lock) {
			waiting = new JobQueue(false);
			sleeping = new JobQueue(true);
			running = new HashSet(10);
			pool = new WorkerPool(this);
		}
		pool.setDaemon(JobOSGiUtils.getDefault().useDaemonThreads());
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#addJobListener(org.eclipse.core.runtime.jobs.IJobChangeListener)
	 */
	public void addJobChangeListener(IJobChangeListener listener) {
		jobListeners.add(listener);
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#beginRule(org.eclipse.core.runtime.jobs.ISchedulingRule, org.eclipse.core.runtime.IProgressMonitor)
	 */
	public void beginRule(ISchedulingRule rule, IProgressMonitor monitor) {
		validateRule(rule);
		implicitJobs.begin(rule, monitorFor(monitor), false);
	}

	/**
	 * Cancels a job
	 */
	protected boolean cancel(InternalJob job) {
		IProgressMonitor monitor = null;
		synchronized (lock) {
			switch (job.getState()) {
				case Job.NONE :
					return true;
				case Job.RUNNING :
					//cannot cancel a job that has already started (as opposed to ABOUT_TO_RUN)
					if (job.internalGetState() == Job.RUNNING) {
						monitor = job.getProgressMonitor();
						break;
					}
					//signal that the job should be canceled before it gets a chance to run
					job.setAboutToRunCanceled(true);
					return true;
				default :
					changeState(job, Job.NONE);
			}
		}
		//call monitor outside sync block
		if (monitor != null) {
			if (!monitor.isCanceled()) {
				monitor.setCanceled(true);
				job.canceling();
			}
			return false;
		}
		//only notify listeners if the job was waiting or sleeping
		jobListeners.done((Job) job, Status.CANCEL_STATUS, false);
		return true;
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#cancel(java.lang.String)
	 */
	public void cancel(Object family) {
		//don't synchronize because cancel calls listeners
		for (Iterator it = select(family).iterator(); it.hasNext();)
			cancel((Job) it.next());
	}

	/**
	 * Atomically updates the state of a job, adding or removing from the
	 * necessary queues or sets.
	 */
	private void changeState(InternalJob job, int newState) {
		boolean blockedJobs = false;
		synchronized (lock) {
			int oldState = job.internalGetState();
			switch (oldState) {
				case Job.NONE :
				case InternalJob.ABOUT_TO_SCHEDULE :
					break;
				case InternalJob.BLOCKED :
					//remove this job from the linked list of blocked jobs
					job.remove();
					break;
				case Job.WAITING :
					try {
						waiting.remove(job);
					} catch (RuntimeException e) {
						Assert.isLegal(false, "Tried to remove a job that wasn't in the queue"); //$NON-NLS-1$
					}
					break;
				case Job.SLEEPING :
					try {
						sleeping.remove(job);
					} catch (RuntimeException e) {
						Assert.isLegal(false, "Tried to remove a job that wasn't in the queue"); //$NON-NLS-1$
					}
					break;
				case Job.RUNNING :
				case InternalJob.ABOUT_TO_RUN :
					running.remove(job);
					//add any blocked jobs back to the wait queue
					InternalJob blocked = job.previous();
					job.remove();
					blockedJobs = blocked != null;
					while (blocked != null) {
						InternalJob previous = blocked.previous();
						changeState(blocked, Job.WAITING);
						blocked = previous;
					}
					break;
				default :
					Assert.isLegal(false, "Invalid job state: " + job + ", state: " + oldState); //$NON-NLS-1$ //$NON-NLS-2$
			}
			job.internalSetState(newState);
			switch (newState) {
				case Job.NONE :
					job.setStartTime(InternalJob.T_NONE);
				case InternalJob.BLOCKED :
					break;
				case Job.WAITING :
					waiting.enqueue(job);
					break;
				case Job.SLEEPING :
					try {
						sleeping.enqueue(job);
					} catch (RuntimeException e) {
						throw new RuntimeException("Error changing from state: " + oldState); //$NON-NLS-1$
					}
					break;
				case Job.RUNNING :
				case InternalJob.ABOUT_TO_RUN :
					job.setStartTime(InternalJob.T_NONE);
					running.add(job);
					break;
				case InternalJob.ABOUT_TO_SCHEDULE :
					break;
				default :
					Assert.isLegal(false, "Invalid job state: " + job + ", state: " + newState); //$NON-NLS-1$ //$NON-NLS-2$
			}
		}
		//notify queue outside sync block
		if (blockedJobs)
			pool.jobQueued();
	}

	/**
	 * Returns a new progress monitor for this job, belonging to the given
	 * progress group.  Returns null if it is not a valid time to set the job's group.
	 */
	protected IProgressMonitor createMonitor(InternalJob job, IProgressMonitor group, int ticks) {
		synchronized (lock) {
			//group must be set before the job is scheduled
			//this includes the ABOUT_TO_SCHEDULE state, during which it is still
			//valid to set the progress monitor
			if (job.getState() != Job.NONE)
				return null;
			IProgressMonitor monitor = null;
			if (progressProvider != null)
				monitor = progressProvider.createMonitor((Job) job, group, ticks);
			if (monitor == null)
				monitor = new NullProgressMonitor();
			return monitor;
		}
	}

	/**
	 * Returns a new progress monitor for this job.  Never returns null.
	 */
	private IProgressMonitor createMonitor(Job job) {
		IProgressMonitor monitor = null;
		if (progressProvider != null)
			monitor = progressProvider.createMonitor(job);
		if (monitor == null)
			monitor = new NullProgressMonitor();
		return monitor;
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#createProgressGroup()
	 */
	public IProgressMonitor createProgressGroup() {
		if (progressProvider != null)
			return progressProvider.createProgressGroup();
		return new NullProgressMonitor();
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#currentJob()
	 */
	public Job currentJob() {
		Thread current = Thread.currentThread();
		if (current instanceof Worker)
			return ((Worker) current).currentJob();
		synchronized (lock) {
			for (Iterator it = running.iterator(); it.hasNext();) {
				Job job = (Job) it.next();
				if (job.getThread() == current)
					return job;
			}
		}
		return null;
	}

	/**
	 * Returns the delay in milliseconds that a job with a given priority can
	 * tolerate waiting.
	 */
	private long delayFor(int priority) {
		//these values may need to be tweaked based on machine speed
		switch (priority) {
			case Job.INTERACTIVE :
				return 0L;
			case Job.SHORT :
				return 50L;
			case Job.LONG :
				return 100L;
			case Job.BUILD :
				return 500L;
			case Job.DECORATE :
				return 1000L;
			default :
				Assert.isTrue(false, "Job has invalid priority: " + priority); //$NON-NLS-1$
				return 0;
		}
	}

	/**
	 * Performs the scheduling of a job.  Does not perform any notifications.
	 */
	private void doSchedule(InternalJob job, long delay) {
		synchronized (lock) {
			//if it's a decoration job, don't run it right now if the system is busy
			if (job.getPriority() == Job.DECORATE) {
				long minDelay = running.size() * 100;
				delay = Math.max(delay, minDelay);
			}
			if (delay > 0) {
				job.setStartTime(System.currentTimeMillis() + delay);
				changeState(job, Job.SLEEPING);
			} else {
				job.setStartTime(System.currentTimeMillis() + delayFor(job.getPriority()));
				changeState(job, Job.WAITING);
			}
		}
	}

	/**
	 * Shuts down the job manager.  Currently running jobs will be told
	 * to stop, but worker threads may still continue processing.
	 * (note: This implemented IJobManager.shutdown which was removed
	 * due to problems caused by premature shutdown)
	 */
	private void doShutdown() {
		Job[] toCancel = null;
		synchronized (lock) {
			if (active) {
				active = false;
				//cancel all running jobs
				toCancel = (Job[]) running.toArray(new Job[running.size()]);
				//clean up
				sleeping.clear();
				waiting.clear();
				running.clear();
			}
		}

		// Give running jobs a chance to finish. Wait 0.1 seconds for up to 3 times.
		if (toCancel != null && toCancel.length > 0) {
			for (int i = 0; i < toCancel.length; i++) {
				cancel(toCancel[i]); // cancel jobs outside sync block to avoid deadlock
			}

			for (int waitAttempts = 0; waitAttempts < 3; waitAttempts++) {
				Thread.yield();
				synchronized (lock) {
					if (running.isEmpty())
						break;
				}
				if (DEBUG_SHUTDOWN) {
					JobManager.debug("Shutdown - job wait cycle #" + (waitAttempts + 1)); //$NON-NLS-1$
					Job[] stillRunning = null;
					synchronized (lock) {
						stillRunning = (Job[]) running.toArray(new Job[running.size()]);
					}
					if (stillRunning != null) {
						for (int j = 0; j < stillRunning.length; j++) {
							JobManager.debug("\tJob: " + printJobName(stillRunning[j])); //$NON-NLS-1$
						}
					}
				}
				try {
					Thread.sleep(100);
				} catch (InterruptedException e) {
					//ignore
				}
				Thread.yield();
			}

			synchronized (lock) { // retrieve list of the jobs that are still running
				toCancel = (Job[]) running.toArray(new Job[running.size()]);
			}
		}

		if (toCancel != null) {
			for (int i = 0; i < toCancel.length; i++) {
				String jobName = printJobName(toCancel[i]);
				//this doesn't need to be translated because it's just being logged
				String msg = "Job found still running after platform shutdown.  Jobs should be canceled by the plugin that scheduled them during shutdown: " + jobName; //$NON-NLS-1$
				RuntimeLog.log(new Status(IStatus.WARNING, JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, msg, null));

				// TODO the RuntimeLog.log in its current implementation won't produce a log 
				// during this stage of shutdown. For now add a standard error output.
				// One the logging story is improved, the System.err output below can be removed:
				System.err.println(msg);
			}
		}

		pool.shutdown();
	}

	/**
	 * Indicates that a job was running, and has now finished.  Note that this method 
	 * can be called under OutOfMemoryError conditions and thus must be paranoid 
	 * about allocating objects.
	 */
	protected void endJob(InternalJob job, IStatus result, boolean notify) {
		long rescheduleDelay = InternalJob.T_NONE;
		synchronized (lock) {
			//if the job is finishing asynchronously, there is nothing more to do for now
			if (result == Job.ASYNC_FINISH)
				return;
			//if job is not known then it cannot be done
			if (job.getState() == Job.NONE)
				return;
			if (JobManager.DEBUG && notify)
				JobManager.debug("Ending job: " + job); //$NON-NLS-1$
			job.setResult(result);
			job.setProgressMonitor(null);
			job.setThread(null);
			rescheduleDelay = job.getStartTime();
			changeState(job, Job.NONE);
		}
		//notify listeners outside sync block
		final boolean reschedule = active && rescheduleDelay > InternalJob.T_NONE && job.shouldSchedule();
		if (notify)
			jobListeners.done((Job) job, result, reschedule);
		//reschedule the job if requested and we are still active
		if (reschedule)
			schedule(job, rescheduleDelay, reschedule);
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#endRule(org.eclipse.core.runtime.jobs.ISchedulingRule)
	 */
	public void endRule(ISchedulingRule rule) {
		implicitJobs.end(rule, false);
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#find(java.lang.String)
	 */
	public Job[] find(Object family) {
		List members = select(family);
		return (Job[]) members.toArray(new Job[members.size()]);
	}

	/**
	 * Returns a running or blocked job whose scheduling rule conflicts with the 
	 * scheduling rule of the given waiting job.  Returns null if there are no 
	 * conflicting jobs.  A job can only run if there are no running jobs and no blocked
	 * jobs whose scheduling rule conflicts with its rule.
	 */
	protected InternalJob findBlockingJob(InternalJob waitingJob) {
		if (waitingJob.getRule() == null)
			return null;
		synchronized (lock) {
			if (running.isEmpty())
				return null;
			//check the running jobs
			boolean hasBlockedJobs = false;
			for (Iterator it = running.iterator(); it.hasNext();) {
				InternalJob job = (InternalJob) it.next();
				if (waitingJob.isConflicting(job))
					return job;
				if (!hasBlockedJobs)
					hasBlockedJobs = job.previous() != null;
			}
			//there are no blocked jobs, so we are done
			if (!hasBlockedJobs)
				return null;
			//check all jobs blocked by running jobs
			for (Iterator it = running.iterator(); it.hasNext();) {
				InternalJob job = (InternalJob) it.next();
				while (true) {
					job = job.previous();
					if (job == null)
						break;
					if (waitingJob.isConflicting(job))
						return job;
				}
			}
		}
		return null;
	}

	public LockManager getLockManager() {
		return lockManager;
	}

	private void initDebugOptions() {
		DEBUG = JobOSGiUtils.getDefault().getBooleanDebugOption(OPTION_DEBUG_JOBS, false);
		DEBUG_BEGIN_END = JobOSGiUtils.getDefault().getBooleanDebugOption(OPTION_DEBUG_BEGIN_END, false);
		DEBUG_DEADLOCK = JobOSGiUtils.getDefault().getBooleanDebugOption(OPTION_DEADLOCK_ERROR, false);
		DEBUG_LOCKS = JobOSGiUtils.getDefault().getBooleanDebugOption(OPTION_LOCKS, false);
		DEBUG_TIMING = JobOSGiUtils.getDefault().getBooleanDebugOption(OPTION_DEBUG_JOBS_TIMING, false);
		DEBUG_SHUTDOWN = JobOSGiUtils.getDefault().getBooleanDebugOption(OPTION_SHUTDOWN, false);
	}

	/**
	 * Returns whether the job manager is active (has not been shutdown).
	 */
	protected boolean isActive() {
		return active;
	}

	/**
	 * Returns true if the given job is blocking the execution of a non-system
	 * job.
	 */
	protected boolean isBlocking(InternalJob runningJob) {
		synchronized (lock) {
			// if this job isn't running, it can't be blocking anyone
			if (runningJob.getState() != Job.RUNNING)
				return false;
			// if any job is queued behind this one, it is blocked by it
			InternalJob previous = runningJob.previous();
			while (previous != null) {
				// ignore jobs of lower priority (higher priority value means lower priority)
				if (previous.getPriority() < runningJob.getPriority()) {
					if (!previous.isSystem())
						return true;
					// implicit jobs should interrupt unless they act on behalf of system jobs
					if (previous instanceof ThreadJob && ((ThreadJob) previous).shouldInterrupt())
						return true;
				}
				previous = previous.previous();
			}
			// none found
			return false;
		}
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#isIdle()
	 */
	public boolean isIdle() {
		synchronized (lock) {
			return running.isEmpty() && waiting.isEmpty();
		}
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.Job#job(org.eclipse.core.runtime.jobs.Job)
	 */
	protected void join(InternalJob job) {
		final IJobChangeListener listener;
		final Semaphore barrier;
		synchronized (lock) {
			int state = job.getState();
			if (state == Job.NONE)
				return;
			//don't join a waiting or sleeping job when suspended (deadlock risk)
			if (suspended && state != Job.RUNNING)
				return;
			//it's an error for a job to join itself
			if (state == Job.RUNNING && job.getThread() == Thread.currentThread())
				throw new IllegalStateException("Job attempted to join itself"); //$NON-NLS-1$
			//the semaphore will be released when the job is done
			barrier = new Semaphore(null);
			listener = new JobChangeAdapter() {
				public void done(IJobChangeEvent event) {
					barrier.release();
				}
			};
			job.addJobChangeListener(listener);
			//compute set of all jobs that must run before this one
			//add a listener that removes jobs from the blocking set when they finish
		}
		//wait until listener notifies this thread.
		try {
			while (true) {
				//notify hook to service pending syncExecs before falling asleep
				lockManager.aboutToWait(job.getThread());
				try {
					if (barrier.acquire(Long.MAX_VALUE))
						break;
				} catch (InterruptedException e) {
					//loop and keep trying
				}
			}
		} finally {
			lockManager.aboutToRelease();
			job.removeJobChangeListener(listener);
		}
	}

	/* (non-Javadoc)
	 * @see IJobManager#join(String, IProgressMonitor)
	 */
	public void join(final Object family, IProgressMonitor monitor) throws InterruptedException, OperationCanceledException {
		monitor = monitorFor(monitor);
		IJobChangeListener listener = null;
		final Set jobs;
		int jobCount;
		Job blocking = null;
		synchronized (lock) {
			//don't join a waiting or sleeping job when suspended (deadlock risk)
			int states = suspended ? Job.RUNNING : Job.RUNNING | Job.WAITING | Job.SLEEPING;
			jobs = Collections.synchronizedSet(new HashSet(select(family, states)));
			jobCount = jobs.size();
			if (jobCount > 0) {
				//if there is only one blocking job, use it in the blockage callback below
				if (jobCount == 1)
					blocking = (Job) jobs.iterator().next();
				listener = new JobChangeAdapter() {
					public void done(IJobChangeEvent event) {
						//don't remove from list if job is being rescheduled
						if (!((JobChangeEvent) event).reschedule)
							jobs.remove(event.getJob());
					}

					//update the list of jobs if new ones are added during the join
					public void scheduled(IJobChangeEvent event) {
						//don't add to list if job is being rescheduled
						if (((JobChangeEvent) event).reschedule)
							return;
						Job job = event.getJob();
						if (job.belongsTo(family))
							jobs.add(job);
					}
				};
				addJobChangeListener(listener);
			}
		}
		if (jobCount == 0) {
			//use up the monitor outside synchronized block because monitors call untrusted code
			monitor.beginTask(JobMessages.jobs_blocked0, 1);
			monitor.done();
			return;
		}
		//spin until all jobs are completed
		try {
			monitor.beginTask(JobMessages.jobs_blocked0, jobCount);
			monitor.subTask(NLS.bind(JobMessages.jobs_waitFamSub, Integer.toString(jobCount)));
			reportBlocked(monitor, blocking);
			int jobsLeft;
			int reportedWorkDone = 0;
			while ((jobsLeft = jobs.size()) > 0) {
				//don't let there be negative work done if new jobs have
				//been added since the join began
				int actualWorkDone = Math.max(0, jobCount - jobsLeft);
				if (reportedWorkDone < actualWorkDone) {
					monitor.worked(actualWorkDone - reportedWorkDone);
					reportedWorkDone = actualWorkDone;
					monitor.subTask(NLS.bind(JobMessages.jobs_waitFamSub, Integer.toString(jobsLeft)));
				}
				if (Thread.interrupted())
					throw new InterruptedException();
				if (monitor.isCanceled())
					throw new OperationCanceledException();
				//notify hook to service pending syncExecs before falling asleep
				lockManager.aboutToWait(null);
				Thread.sleep(100);
			}
		} finally {
			removeJobChangeListener(listener);
			reportUnblocked(monitor);
			monitor.done();
		}
	}

	/**
	 * Returns a non-null progress monitor instance.  If the monitor is null,
	 * returns the default monitor supplied by the progress provider, or a 
	 * NullProgressMonitor if no default monitor is available.
	 */
	private IProgressMonitor monitorFor(IProgressMonitor monitor) {
		if (monitor == null || (monitor instanceof NullProgressMonitor)) {
			if (progressProvider != null) {
				try {
					monitor = progressProvider.getDefaultMonitor();
				} catch (Exception e) {
					String msg = NLS.bind(JobMessages.meta_pluginProblems, JobManager.PI_JOBS);
					RuntimeLog.log(new Status(IStatus.ERROR, JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, msg, e));
				}
			}
		}

		if (monitor == null)
			return new NullProgressMonitor();
		return monitor;
	}

	/* (non-Javadoc)
	 * @see IJobManager#newLock(java.lang.String)
	 */
	public ILock newLock() {
		return lockManager.newLock();
	}

	/**
	 * Removes and returns the first waiting job in the queue. Returns null if there
	 * are no items waiting in the queue.  If an item is removed from the queue,
	 * it is moved to the running jobs list.
	 */
	private Job nextJob() {
		synchronized (lock) {
			//do nothing if the job manager is suspended
			if (suspended)
				return null;
			//tickle the sleep queue to see if anyone wakes up
			long now = System.currentTimeMillis();
			InternalJob job = sleeping.peek();
			while (job != null && job.getStartTime() < now) {
				job.setStartTime(now + delayFor(job.getPriority()));
				changeState(job, Job.WAITING);
				job = sleeping.peek();
			}
			//process the wait queue until we find a job whose rules are satisfied.
			while ((job = waiting.peek()) != null) {
				InternalJob blocker = findBlockingJob(job);
				if (blocker == null)
					break;
				//queue this job after the job that's blocking it
				changeState(job, InternalJob.BLOCKED);
				//assert job does not already belong to some other data structure
				Assert.isTrue(job.next() == null);
				Assert.isTrue(job.previous() == null);
				blocker.addLast(job);
			}
			//the job to run must be in the running list before we exit
			//the sync block, otherwise two jobs with conflicting rules could start at once
			if (job != null) {
				changeState(job, InternalJob.ABOUT_TO_RUN);
				if (JobManager.DEBUG)
					JobManager.debug("Starting job: " + job); //$NON-NLS-1$
			}
			return (Job) job;
		}
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#removeJobListener(org.eclipse.core.runtime.jobs.IJobChangeListener)
	 */
	public void removeJobChangeListener(IJobChangeListener listener) {
		jobListeners.remove(listener);
	}

	/**
	 * Report to the progress monitor that this thread is blocked, supplying
	 * an information message, and if possible the job that is causing the blockage.
	 * Important: An invocation of this method MUST be followed eventually be
	 * an invocation of reportUnblocked.
	 * @param monitor The monitor to report blocking to
	 * @param blockingJob The job that is blocking this thread, or <code>null</code>
	 * @see #reportUnblocked
	 */
	final void reportBlocked(IProgressMonitor monitor, InternalJob blockingJob) {
		if (!(monitor instanceof IProgressMonitorWithBlocking))
			return;
		IStatus reason;
		if (blockingJob == null || blockingJob instanceof ThreadJob || blockingJob.isSystem()) {
			reason = new Status(IStatus.INFO, JobManager.PI_JOBS, 1, JobMessages.jobs_blocked0, null);
		} else {
			String msg = NLS.bind(JobMessages.jobs_blocked1, blockingJob.getName());
			reason = new JobStatus(IStatus.INFO, (Job) blockingJob, msg);
		}
		((IProgressMonitorWithBlocking) monitor).setBlocked(reason);
	}

	/**
	 * Reports that this thread was blocked, but is no longer blocked and is able
	 * to proceed.
	 * @param monitor The monitor to report unblocking to.
	 * @see #reportBlocked
	 */
	final void reportUnblocked(IProgressMonitor monitor) {
		if (monitor instanceof IProgressMonitorWithBlocking)
			((IProgressMonitorWithBlocking) monitor).clearBlocked();
	}

	/*(non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#resume()
	 */
	public final void resume() {
		synchronized (lock) {
			suspended = false;
			//poke the job pool
			pool.jobQueued();
		}
	}

	/** (non-Javadoc)
	 * @deprecated this method should not be used
	 * @see org.eclipse.core.runtime.jobs.IJobManager#resume(org.eclipse.core.runtime.jobs.ISchedulingRule)
	 */
	public final void resume(ISchedulingRule rule) {
		implicitJobs.resume(rule);
	}

	/**
	 * Attempts to immediately start a given job.  Returns true if the job was
	 * successfully started, and false if it could not be started immediately
	 * due to a currently running job with a conflicting rule.  Listeners will never
	 * be notified of jobs that are run in this way.
	 */
	protected boolean runNow(InternalJob job) {
		synchronized (lock) {
			//cannot start if there is a conflicting job
			if (findBlockingJob(job) != null)
				return false;
			changeState(job, Job.RUNNING);
			job.setProgressMonitor(new NullProgressMonitor());
			job.run(null);
		}
		return true;
	}

	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.Job#schedule(long)
	 */
	protected void schedule(InternalJob job, long delay, boolean reschedule) {
		if (!active)
			throw new IllegalStateException("Job manager has been shut down."); //$NON-NLS-1$
		Assert.isNotNull(job, "Job is null"); //$NON-NLS-1$
		Assert.isLegal(delay >= 0, "Scheduling delay is negative"); //$NON-NLS-1$
		synchronized (lock) {
			//if the job is already running, set it to be rescheduled when done
			if (job.getState() == Job.RUNNING) {
				job.setStartTime(delay);
				return;
			}
			//can't schedule a job that is waiting or sleeping
			if (job.internalGetState() != Job.NONE)
				return;
			if (JobManager.DEBUG)
				JobManager.debug("Scheduling job: " + job); //$NON-NLS-1$
			//remember that we are about to schedule the job
			//to prevent multiple schedule attempts from succeeding (bug 68452)
			changeState(job, InternalJob.ABOUT_TO_SCHEDULE);
		}
		//notify listeners outside sync block
		jobListeners.scheduled((Job) job, delay, reschedule);
		//schedule the job
		doSchedule(job, delay);
		//call the pool outside sync block to avoid deadlock
		pool.jobQueued();
	}

	/**
	 * Adds all family members in the list of jobs to the collection
	 */
	private void select(List members, Object family, InternalJob firstJob, int stateMask) {
		if (firstJob == null)
			return;
		InternalJob job = firstJob;
		do {
			//note that job state cannot be NONE at this point
			if ((family == null || job.belongsTo(family)) && ((job.getState() & stateMask) != 0))
				members.add(job);
			job = job.previous();
		} while (job != null && job != firstJob);
	}

	/**
	 * Returns a list of all jobs known to the job manager that belong to the given family.
	 */
	private List select(Object family) {
		return select(family, Job.WAITING | Job.SLEEPING | Job.RUNNING);
	}

	/**
	 * Returns a list of all jobs known to the job manager that belong to the given 
	 * family and are in one of the provided states.
	 */
	private List select(Object family, int stateMask) {
		List members = new ArrayList();
		synchronized (lock) {
			if ((stateMask & Job.RUNNING) != 0) {
				for (Iterator it = running.iterator(); it.hasNext();) {
					select(members, family, (InternalJob) it.next(), stateMask);
				}
			}
			if ((stateMask & Job.WAITING) != 0)
				select(members, family, waiting.peek(), stateMask);
			if ((stateMask & Job.SLEEPING) != 0)
				select(members, family, sleeping.peek(), stateMask);
		}
		return members;
	}

	/* (non-Javadoc)
	 * @see IJobManager#setLockListener(LockListener)
	 */
	public void setLockListener(LockListener listener) {
		lockManager.setLockListener(listener);
	}

	/**
	 * Changes a job priority.
	 */
	protected void setPriority(InternalJob job, int newPriority) {
		synchronized (lock) {
			int oldPriority = job.getPriority();
			if (oldPriority == newPriority)
				return;
			job.internalSetPriority(newPriority);
			//if the job is waiting to run, re-shuffle the queue
			if (job.getState() == Job.WAITING) {
				long oldStart = job.getStartTime();
				job.setStartTime(oldStart + (delayFor(newPriority) - delayFor(oldPriority)));
				waiting.resort(job);
			}
		}
	}

	/* (non-Javadoc)
	 * @see IJobManager#setProgressProvider(IProgressProvider)
	 */
	public void setProgressProvider(ProgressProvider provider) {
		progressProvider = provider;
	}

	/* (non-Javadoc)
	 * @see Job#setRule
	 */
	public void setRule(InternalJob job, ISchedulingRule rule) {
		synchronized (lock) {
			//cannot change the rule of a job that is already running
			Assert.isLegal(job.getState() == Job.NONE);
			validateRule(rule);
			job.internalSetRule(rule);
		}
	}

	/**
	 * Puts a job to sleep. Returns true if the job was successfully put to sleep.
	 */
	protected boolean sleep(InternalJob job) {
		synchronized (lock) {
			switch (job.getState()) {
				case Job.RUNNING :
					//cannot be paused if it is already running (as opposed to ABOUT_TO_RUN)
					if (job.internalGetState() == Job.RUNNING)
						return false;
					//job hasn't started running yet (aboutToRun listener)
					break;
				case Job.SLEEPING :
					//update the job wake time
					job.setStartTime(InternalJob.T_INFINITE);
					//change state again to re-shuffle the sleep queue
					changeState(job, Job.SLEEPING);
					return true;
				case Job.NONE :
					return true;
				case Job.WAITING :
					//put the job to sleep
					break;
			}
			job.setStartTime(InternalJob.T_INFINITE);
			changeState(job, Job.SLEEPING);
		}
		jobListeners.sleeping((Job) job);
		return true;
	}

	/* (non-Javadoc)
	 * @see IJobManager#sleep(String)
	 */
	public void sleep(Object family) {
		//don't synchronize because sleep calls listeners
		for (Iterator it = select(family).iterator(); it.hasNext();) {
			sleep((InternalJob) it.next());
		}
	}

	/**
	 * Returns the estimated time in milliseconds before the next job is scheduled
	 * to wake up. The result may be negative.  Returns InternalJob.T_INFINITE if
	 * there are no sleeping or waiting jobs.
	 */
	protected long sleepHint() {
		synchronized (lock) {
			//wait forever if job manager is suspended
			if (suspended)
				return InternalJob.T_INFINITE;
			if (!waiting.isEmpty())
				return 0L;
			//return the anticipated time that the next sleeping job will wake
			InternalJob next = sleeping.peek();
			if (next == null)
				return InternalJob.T_INFINITE;
			return next.getStartTime() - System.currentTimeMillis();
		}
	}

	/**
	 * Returns the next job to be run, or null if no jobs are waiting to run.
	 * The worker must call endJob when the job is finished running.  
	 */
	protected Job startJob() {
		Job job = null;
		while (true) {
			job = nextJob();
			if (job == null)
				return null;
			//must perform this outside sync block because it is third party code
			if (job.shouldRun()) {
				//check for listener veto
				jobListeners.aboutToRun(job);
				//listeners may have canceled or put the job to sleep
				synchronized (lock) {
					if (job.getState() == Job.RUNNING) {
						InternalJob internal = job;
						if (internal.isAboutToRunCanceled()) {
							internal.setAboutToRunCanceled(false);
							//fall through and end the job below
						} else {
							internal.setProgressMonitor(createMonitor(job));
							//change from ABOUT_TO_RUN to RUNNING
							internal.internalSetState(Job.RUNNING);
							break;
						}
					}
				}
			}
			if (job.getState() != Job.SLEEPING) {
				//job has been vetoed or canceled, so mark it as done
				endJob(job, Status.CANCEL_STATUS, true);
				continue;
			}
		}
		jobListeners.running(job);
		return job;

	}

	/* non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#suspend()
	 */
	public final void suspend() {
		synchronized (lock) {
			suspended = true;
		}
	}

	/** (non-Javadoc)
	 * @deprecated this method should not be used
	 * @see org.eclipse.core.runtime.jobs.IJobManager#suspend(org.eclipse.core.runtime.jobs.ISchedulingRule, org.eclipse.core.runtime.IProgressMonitor)
	 */
	public final void suspend(ISchedulingRule rule, IProgressMonitor monitor) {
		Assert.isNotNull(rule);
		implicitJobs.suspend(rule, monitorFor(monitor));
	}

	/* non-Javadoc)
	 * @see org.eclipse.core.runtime.jobs.IJobManager#transferRule()
	 */
	public void transferRule(ISchedulingRule rule, Thread destinationThread) {
		implicitJobs.transfer(rule, destinationThread);
	}

	/**
	 * Validates that the given scheduling rule obeys the constraints of
	 * scheduling rules as described in the <code>ISchedulingRule</code>
	 * javadoc specification.
	 */
	private void validateRule(ISchedulingRule rule) {
		//null rule always valid
		if (rule == null)
			return;
		//contains method must be reflexive
		Assert.isLegal(rule.contains(rule));
		//contains method must return false when given an unknown rule
		Assert.isLegal(!rule.contains(nullRule));
		//isConflicting method must be reflexive
		Assert.isLegal(rule.isConflicting(rule));
		//isConflicting method must return false when given an unknown rule
		Assert.isLegal(!rule.isConflicting(nullRule));
	}

	/* (non-Javadoc)
	 * @see Job#wakeUp(long)
	 */
	protected void wakeUp(InternalJob job, long delay) {
		Assert.isLegal(delay >= 0, "Scheduling delay is negative"); //$NON-NLS-1$
		synchronized (lock) {
			//cannot wake up if it is not sleeping
			if (job.getState() != Job.SLEEPING)
				return;
			doSchedule(job, delay);
		}
		//call the pool outside sync block to avoid deadlock
		pool.jobQueued();

		//only notify of wake up if immediate
		if (delay == 0)
			jobListeners.awake((Job) job);
	}

	/* (non-Javadoc)
	 * @see IJobFamily#wakeUp(String)
	 */
	public void wakeUp(Object family) {
		//don't synchronize because wakeUp calls listeners
		for (Iterator it = select(family).iterator(); it.hasNext();) {
			wakeUp((InternalJob) it.next(), 0L);
		}
	}
}
