/* Author: Jeff Dalton <J.Dalton@ed.ac.uk>
 * Updated: Wed May 30 17:23:58 2001 by Jeff Dalton
 * Copyright: (c) 2001, AIAI, University of Edinburgh
 */

package ix.util.context;

import java.lang.ref.WeakReference;
import java.util.*;

import ix.util.Debug;

/**
 * A Context is an object that is used as an additional, often
 * implicit, parameter when accessing values, such as in a "get"-method.
 * Instead of a value being stored directly in a field, the field contains
 * a list of associations from contexts to values.  The conventions for
 * this implementation are that the associations are held in a chain of
 * ContextLinks, and the relevant context is obtained from an implementation
 * of ContextHolder.  So instead of writing something like this in a
 * class definition:
 * 
 * <pre>
 *   Object field = new FieldValue();
 *
 *   Object getField() { return field; }
 *   void setField(Object value) { field = value; }
 * </pre>
 *
 * you would write something like this:
 *
 * <pre>
 *   Object field = new ContextLink(new FieldValue());
 *
 *   // One holder used with all fields
 *   ContextHolder contextHolder = Context.getContextHolder();
 *
 *   Object getField() {
 *       Context c = contextHolder.getContext();
 *       return Context.getInContext(field, c);
 *   }
 *
 *   void setField(Object value) {
 *       Context c = contextHolder.getContext();
 *       Context.setInContext(field, c, value);
 *   }
 * </pre>
 *
 * A context has few properties of its own.  It is simply an object
 * with which the values obtained by context-relative accessors may be
 * associated.  Contexts are arranged in a tree: each context has a
 * single parent and a list of children.  When there is no value directly
 * associated with a context, a value is inherited from the nearest
 * ancestor context that does have a directly associated value.
 * However, when a value is assigned in a context, it is always
 * associated directly with that context, and the associations between
 * ancestor contexts and values are not changed.  This makes it
 * possible to protect the values associated with a context, while
 * still being able to access them, by moving to a descendent context. <p>
 *
 * An efficient search for the value associated with a context, or
 * inherited from an ancestor, is accomplished by exploiting context
 * numbers.  Every context has a number which is assigned when it is
 * created, and newer contexts have higher numbers than older ones.  In
 * particular, a context has a higher number than any of its ancestors.
 * The chain of ContextLinks for a given field has links for 
 * higher-numbered (newer) contexts first.  The algorithm for finding
 * the right value is therefore as follows:
 *
 * <ol>
 * <li>Initialize <i>target</i> to the desired context and <i>chain</i>
 *     to the relevant chain of ContextLinks.
 *
 * <li>Discard entries for contexts newer than <i>target</i> from the
 *     front of <i>chain</i>.  If <i>chain</i> becomes null, then there
 *     is no value for the current context.
 *
 * <li>At this point, the first of the remaining entries in <i>chain</i>
 *     should be for <i>target</i> or for a context older than <i>target</i>.
 *     If it's for <i>target</i>, then we're done: return the associated
 *     value.  Otherwise, set <i>target</i> to the parent of <i>target</i>
 *     and return to step 2.
 * </ol>
 *
 * The getInContext method implements that algorithm. <p>
 *
 * Context-holders are used for two reasons.  First, they make it unnecessary
 * to pass contexts as parameters to "get"- and "set"-methods.  This makes
 * "context-layered" objects look much more like ordinary objects.  Second,
 * a context-holder may be shared by many objects, so that they all change
 * context at once. <p>
 *
 * However, there is no single way of managing context-holders that
 * is right for every case.  In some applications, a single, global
 * context-holder can be used.  In others, a number of more local
 * context-holders will be needed.  Moreover, even when a system needs
 * only one context for itself, it may be running in the same Java VM
 * as other software that should be independent and that may also use
 * contexts. <p>
 *
 * These problems are partly addressed by context-holding "strategies".
 * A holding strategy provides a method that returns a context-holder,
 * and the Context class holds a current (global) strategy.  The static
 * method Context.getContextHolder() asks the current strategy for a
 * holder.
 *
 * @see ContextLink
 * @see #getContextHolder()
 * @See ContextHolder
 * @see ContextHoldingStrategy
 */
public final class Context {

    // N.B. count and numberToContextTable must be
    // initialized before rootContext.

    /**
     * The number of contexts that have been created.
     */
    static long count = 0;

    /**
     * A mapping from context numbers to (weak references to) contexts.
     */
    static HashMap numberToContextTable = new HashMap();

    /**
     * A context that is an ancestor of all others.
     * The root context is often used for default values. <p>
     *
     * Unlike any other context, the root context's parent is null.
     */
    public static final Context rootContext = new Context();

    /**
     * The current context-holding strategy.
     *
     * @see #getContextHoldingStrategy()
     * @see #setContextHoldingStrategy(ContextHoldingStrategy s)
     * @see #getContextHolder()
     */
    static ContextHoldingStrategy contextHoldingStrategy =
	new GlobalHoldingStrategy();


    /**
     * A number, unique to this context and larger than the number
     * of any context created earlier.
     */
    final long number;

    /**
     * This context's parent context.
     */
    final Context parent;

    /**
     * A collection of this context's children.
     */
    final List children = new ArrayList();


    /**
     * Create a context with the root context as its parent. <p>
     *
     * The constructor is also used once to create the root context
     * itself, and then it's arranged for the root context's parent
     * to be null.
     */
    public Context() {
	this(null);
    }

    /**
     * Create a context with a given parent.  If the parent is null,
     * the root context will be used.
     */
    public Context(Context parent) {
	synchronized (Context.class) {
	    number = count++;
	    if (parent == null && rootContext != null)
		this.parent = rootContext;
	    else
		this.parent = parent;
	    if (this.parent != null)
		this.parent.children.add(this);
	    numberToContextTable.put(new Long(this.number),
				     new WeakReference(this));
	    Debug.assert(getContext(number) == this);
	}
    }

    /**
     * Returns this context's number.
     */
    public long getNumber() {
	return number;
    }

    /**
     * Returns this context's parent context.
     */
    public Context getParent() {
	return parent;
    }

    /**
     * Returns an unmodifiable view of this context's children.
     */
    public List getChildren() {
	return Collections.unmodifiableList(children);
    }

    /**
     * Remove this context and all of its descendents from the
     * context tree and the number-to-context table.
     */
    public void discard() {
	synchronized (Context.class) {
	    // Remove this from parent's children
	    if (parent != null) {
		parent.children.remove(this);
	    }
	    // Recursively discard.
	    discardSubtree(this);
	}
    }

    private static void discardSubtree(Context c) {
	// Discard child subtrees.
	for (Iterator i = c.children.iterator(); i.hasNext();) {
	    Context child = (Context)i.next();
	    discardSubtree(child);
	}
	// Forget the children
	c.children.clear();
	// Remove from number-to-context table.
	Long n = new Long(c.number);
	WeakReference r = (WeakReference)numberToContextTable.get(n);
	r.clear();		// need we bother?
	numberToContextTable.remove(n);
	Debug.assert(getContext(c.number) == null);
    }

    public String toString() {
	return "#<Context " + number + ">";
    }


    /*
     * Useful static methods.
     */

    /**
     * Returns the context that has the indicated number, or null
     * if that context has been discarded or has ceased to exist.
     */
    public static Context getContext(long n) {
	WeakReference r = (WeakReference)
	    numberToContextTable.get(new Long(n));
	return (r == null) ? null : (Context)r.get();
    }

    /**
     * Returns the current context-holding strategy. <p>
     *
     * Initially, the strategy provides a single, global context
     * holder.
     *
     * @see GlobalHoldingStrategy
     */
    public static ContextHoldingStrategy getContextHoldingStrategy() {
	return contextHoldingStrategy;
    }

    /**
     * Sets the current context-holding strategy.
     */
    public static void setContextHoldingStrategy(ContextHoldingStrategy s) {
	contextHoldingStrategy = s;
    }

    /**
     * Returns the context-holder provided by the current context-holding
     * strategy.
     *
     * @see #getContextHoldingStrategy()
     */
    public static ContextHolder getContextHolder() {
	return contextHoldingStrategy.getContextHolder();
    }

    /**
     * Searches a chain of ContextLinks to find the value associated
     * with a given context.
     *
     * @throws Error (for now) if no value can be found
     */
    public static Object getInContext(ContextLink cl, Context c) {
	for (Context target = c; target != null; target = target.parent) {
	    // Skip entries for contexts newer than target
	    long target_n = target.number;
	    while (cl != null && cl.contextNumber > target_n) {
		cl = cl.next;
	    }
	    if (cl == null)
		throw new Error("Couldn't find value in " + c);
	    else if (cl.contextNumber == target_n)
		return cl.value;
	    // At this point, all remaining entries are for contexts
	    // older than the target but perhaps not older than the
	    // target's parent.
	}
	throw new Error("No value in " + c);
    }

    /**
     * Modifies a chain of ContextLinks to associate a value directly
     * with a given context.
     */
    public static void setInContext(ContextLink cl, Context c, Object value) {
	Context target = c;
	long target_n = target.number;
	ContextLink at = cl;
	while (true) {
	    if (at.contextNumber == target_n) {
		at.value = value;
		return;
	    }
	    else if (at.contextNumber < target_n) {
		at.next = new ContextLink
		    (at.contextNumber, at.value, at.next);
		at.contextNumber = target_n;
		at.value = value;
		return;
	    }
	    else if (at.next == null) {
		at.next = new ContextLink(target, value, null);
		return;
	    }
	    else {
		at = at.next;
	    }
	}
    }

    /**
     * Temporarily changes a context-holder's current context around
     * a call to a Runnable's run() method.
     */
    public static void inContext(ContextHolder h, Context c, Runnable r) {
	Context saved = h.getContext();
	try {
	    h.setContext(c);
	    r.run();
	}
	finally {
	    h.setContext(saved);
	}
    }

    /**
     * Moves the specified context-holder to a new child of its
     * current context.
     */
    public static void pushContext(ContextHolder h) {
	h.setContext(new Context(h.getContext()));
    }

    /**
     * Moves the specified context-holder to the parent of its current
     * context.
     */
    public static Context popContext(ContextHolder h) {
	Context c = h.getContext();
	if (c == null)
	    throw new Error("Trying to pop null context");
	else if (c.parent == null)
	    throw new Error("Trying to pop to null context");
	else
	    h.setContext(c.parent);
	return c;
    }

}