/*
 * FindBugs - Find Bugs in Java programs
 * Copyright (C) 2003-2008, University of Maryland
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package edu.umd.cs.findbugs.ba.jsr305;

import java.lang.annotation.ElementType;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import javax.annotation.meta.When;

import org.objectweb.asm.Type;

import edu.umd.cs.findbugs.SystemProperties;
import edu.umd.cs.findbugs.annotations.CheckForNull;
import edu.umd.cs.findbugs.ba.AnalysisContext;
import edu.umd.cs.findbugs.ba.XClass;
import edu.umd.cs.findbugs.ba.XMethod;
import edu.umd.cs.findbugs.classfile.ClassDescriptor;
import edu.umd.cs.findbugs.classfile.DescriptorFactory;
import edu.umd.cs.findbugs.classfile.analysis.AnnotatedObject;
import edu.umd.cs.findbugs.classfile.analysis.AnnotationValue;
import edu.umd.cs.findbugs.classfile.analysis.EnumValue;
import edu.umd.cs.findbugs.util.DualKeyHashMap;

/**
 * Figure out where and how type qualifier annotations are applied.
 *
 * @author William Pugh
 * @author David Hovemeyer
 */
public class TypeQualifierApplications {
	static final boolean DEBUG = SystemProperties.getBoolean("ctq.applications.debug");
	static final String DEBUG_METHOD = SystemProperties.getProperty("ctq.applications.method");
	static final boolean DEBUG_DEFAULT_ANNOTATION = SystemProperties.getBoolean("ctq.applications.default.debug");
	
	/**
	 * Should exclusive type qualifiers be handled?
	 */
	static final boolean CHECK_EXCLUSIVE = true;//SystemProperties.getBoolean("ctq.applications.checkexclusive");
	static final boolean CHECK_EXHAUSTIVE = true; //SystemProperties.getBoolean("ctq.applications.checkexhaustive");

	static class Data {
		/** Type qualifier annotations applied directly to methods/fields/classes/etc. */
		private  Map<AnnotatedObject, Collection<AnnotationValue>> directObjectAnnotations =
			new HashMap<AnnotatedObject, Collection<AnnotationValue>>();

		/** Type qualifier annotations applied directly to method parameters. */
		private HashMap<XMethod, Map<Integer, Collection<AnnotationValue>>> directParameterAnnotations =
			new HashMap<XMethod, Map<Integer, Collection<AnnotationValue>>>();

		/**
		 * Map of TypeQualifierValues to maps containing, for each AnnotatedObject,
		 * the effective TypeQualifierAnnotation (if any) for that AnnotatedObject.
		 */
		private  Map<TypeQualifierValue, Map<AnnotatedObject, TypeQualifierAnnotation>> effectiveObjectAnnotations =
			new HashMap<TypeQualifierValue, Map<AnnotatedObject,TypeQualifierAnnotation>>();

		/**
		 * Map of TypeQualifierValues to maps containing, for each XMethod/parameter,
		 * the effective TypeQualifierAnnotation (if any) for that XMethod/parameter.
		 */
		private  Map<TypeQualifierValue, DualKeyHashMap<XMethod, Integer, TypeQualifierAnnotation>> effectiveParameterAnnotations =
			new HashMap<TypeQualifierValue, DualKeyHashMap<XMethod,Integer,TypeQualifierAnnotation>>();
	}

	private static ThreadLocal<Data> instance =
		new ThreadLocal<Data>() {
			@Override
			protected Data initialValue() {
				return new Data();
			}
		};

	public static void clearInstance() {
		if (DEBUG) {
			System.out.println("Clearing TypeQualifier application cache");
		}
		instance.remove();
	}

	private static Map<TypeQualifierValue, DualKeyHashMap<XMethod, Integer, TypeQualifierAnnotation>> getEffectiveParameterAnnotations() {
		return instance.get().effectiveParameterAnnotations;
	}

	private static Map<TypeQualifierValue, Map<AnnotatedObject, TypeQualifierAnnotation>> getEffectiveObjectAnnotations() {
		return instance.get().effectiveObjectAnnotations;
	}

	private static HashMap<XMethod,  Map<Integer, Collection<AnnotationValue>>> getDirectParameterAnnotations() {
		return instance.get().directParameterAnnotations;
	}

	private static Map<AnnotatedObject, Collection<AnnotationValue>> getDirectObjectAnnotations() {
		return instance.get().directObjectAnnotations;
	}
	
	/**
	 * Callback interface to compute effective TypeQualifierAnnotation on an
	 * AnnotatedObject or method parameter.
	 */
	private interface ComputeEffectiveTypeQualifierAnnotation {
		public TypeQualifierAnnotation compute(TypeQualifierValue tqv);
	}

	/**
	 * Get the direct annotations (if any) on given AnnotatedObject.
	 *
	 * @param m an AnnotatedObject
	 * @return Collection of AnnotationValues representing annotations directly
	 *         applied to this AnnotatedObject
	 */
	private static Collection<AnnotationValue> getDirectAnnotation(AnnotatedObject m) {
		Collection<AnnotationValue> result = getDirectObjectAnnotations().get(m);
		if (result != null) return result;
		if (m.getAnnotationDescriptors().isEmpty()) return Collections.<AnnotationValue>emptyList();
		result = TypeQualifierResolver.resolveTypeQualifiers(m.getAnnotations());
		if (result.size() == 0) result = Collections.<AnnotationValue>emptyList();
		getDirectObjectAnnotations().put(m, result);
		return result;
	}

	/**
	 * Get the direct annotations (if any) on given method parameter.
	 *
	 * @param m         a method
	 * @param parameter a parameter (0 == first parameter)
	 * @return Collection of AnnotationValues representing annotations directly
	 *         applied to this parameter
	 */
	private static Collection<AnnotationValue> getDirectAnnotation(XMethod m, int parameter) {
		HashMap<XMethod, Map<Integer, Collection<AnnotationValue>>> directParameterAnnotations = getDirectParameterAnnotations();
		Map<Integer, Collection<AnnotationValue>> map =  directParameterAnnotations.get(m);
		if (map == null) {
			int n = m.getNumParams();
			map = new HashMap<Integer, Collection<AnnotationValue>>(n+2);
			for(int i = 0; i < n; i++) {
				Collection<AnnotationValue> a = TypeQualifierResolver.resolveTypeQualifiers(m.getParameterAnnotations(i));
				if (!a.isEmpty())
					map.put(i, a);
			}
			if (map.isEmpty()) map = Collections.emptyMap();
			directParameterAnnotations.put(m, map);
		} else if (false) {
			int n = m.getNumParams();
			for(int i = 0; i < n; i++) {
				Collection<AnnotationValue> a = TypeQualifierResolver.resolveTypeQualifiers(m.getParameterAnnotations(i));
				Collection<AnnotationValue> a2 = map.get(i);
				boolean ok = a2 == null ?  a.isEmpty() : a.equals(a2);
				if (!ok) {
					Collection<AnnotationValue> a3 = TypeQualifierResolver.resolveTypeQualifiers(m.getParameterAnnotations(i));
					System.out.println("huh");
				}
			}
		}
		
		Collection<AnnotationValue> result = map.get(parameter);
		if (result != null) return result;
		return Collections.emptyList();
	}

	/**
	 * Populate a Set of TypeQualifierAnnotations representing
	 * directly-applied type qualifier annotations on given
	 * method parameter.
	 *
	 * @param result    Set of TypeQualifierAnnotations
	 * @param o         a method
	 * @param parameter a parameter (0 == first parameter)
	 */
	public static void getDirectApplications(Set<TypeQualifierAnnotation> result, XMethod o, int parameter) {
		Collection<AnnotationValue> values = getDirectAnnotation(o, parameter);
		for(AnnotationValue v : values) 
			constructTypeQualifierAnnotation(result, v);
		
	}

	/**
	 * Populate a Set of TypeQualifierAnnotations representing
	 * directly-applied type qualifier annotations on given
	 * AnnotatedObject.
	 *
	 * @param result Set of TypeQualifierAnnotations
	 * @param o      an AnnotatedObject
	 * @param e      ElementType representing kind of annotated object
	 */
	public static void getDirectApplications(Set<TypeQualifierAnnotation> result, AnnotatedObject o, ElementType e) {
		if (!o.getElementType().equals(e)) return;
		Collection<AnnotationValue> values = getDirectAnnotation(o);
		for(AnnotationValue v : values) 
				constructTypeQualifierAnnotation(result, v);
		
	}

	/**
	 * Resolve a raw AnnotationValue into a TypeQualifierAnnotation.
	 *
	 * @param v   a raw AnnotationValue
	 * @return a constructed TypeQualifierAnnotation
	 */
	public static TypeQualifierAnnotation constructTypeQualifierAnnotation(AnnotationValue v) {
		assert v != null;
		EnumValue whenValue = (EnumValue) v.getValue("when");
		When when = whenValue == null ? When.ALWAYS : When.valueOf(whenValue.value);
		ClassDescriptor annotationClass = v.getAnnotationClass();
		TypeQualifierValue tqv = TypeQualifierValue.getValue(annotationClass, v.getValue("value"));
		TypeQualifierAnnotation tqa = TypeQualifierAnnotation.getValue(tqv, when);
		return tqa;
	}

	/**
	 * Resolve a raw AnnotationValue into a TypeQualifierAnnotation,
	 * storing result in given Set.
	 *
	 * @param set Set of resolved TypeQualifierAnnotations
	 * @param v   a raw AnnotationValue
	 */
	public static void constructTypeQualifierAnnotation(Set<TypeQualifierAnnotation> set, AnnotationValue v) {
		assert set != null;
		TypeQualifierAnnotation tqa = constructTypeQualifierAnnotation(v);
		set.add(tqa);
	}

	/**
	 * Populate Set of TypeQualifierAnnotations
	 * for given AnnotatedObject,
	 * taking into account annotations
	 * applied to outer scopes (e.g., enclosing classes and packages.)
	 *
	 * @param result Set of TypeQualifierAnnotations
	 * @param o      an AnnotatedObject
	 * @param e      ElementType representing kind of AnnotatedObject
	 */
	private static void getApplicableScopedApplications(Set<TypeQualifierAnnotation> result, AnnotatedObject o, ElementType e) {
		if (!o.isSynthetic()) {
			AnnotatedObject outer = o.getContainingScope();
			if (outer != null)
				getApplicableScopedApplications(result, outer, e);
		}
		getDirectApplications(result, o, e);
	}

	/**
	 * Get the collection of resolved TypeQualifierAnnotations for
	 * a given AnnotatedObject,
	 * taking into account annotations
	 * applied to outer scopes (e.g., enclosing classes and packages.)
	 *
	 * @param o an AnnotatedObject
	 * @param e ElementType representing kind of AnnotatedObject
	 * @return Collection of resolved TypeQualifierAnnotations
	 */
	private static Collection<TypeQualifierAnnotation> getApplicableScopedApplications(AnnotatedObject o, ElementType e) {
		Set<TypeQualifierAnnotation> result = new HashSet<TypeQualifierAnnotation>();
		getApplicableScopedApplications(result, o, e);
		return result;
	}

	/**
	 * Get the collection of resolved TypeQualifierAnnotations for
	 * a given parameter,
	 * taking into account annotations
	 * applied to outer scopes (e.g., enclosing classes and packages.)
	 *
	 * @param o         a method
	 * @param parameter a parameter (0 == first parameter)
	 * @return Collection of resolved TypeQualifierAnnotations
	 */
	private static Collection<TypeQualifierAnnotation> getApplicableScopedApplications(XMethod o, int parameter) {
		Set<TypeQualifierAnnotation> result = new HashSet<TypeQualifierAnnotation>();
		ElementType e = ElementType.PARAMETER;
		getApplicableScopedApplications(result, o, e);
		getDirectApplications(result, o, parameter);
		return result;
	}

	/**
	 * Get the Collection of resolved TypeQualifierAnnotations representing
	 * directly applied and default (outer scope) type qualifier annotations
	 * for given AnnotatedObject.
	 *
	 * <p>NOTE: does not properly account for inherited annotations
	 * on instance methods.
	 * It is ok to call this method to find out generally-relevant TypeQualifierAnnotations,
	 * but not to find the effective TypeQualifierAnnotation.</p>
	 *
	 * @param o an AnnotatedObject
	 * @return Collection of TypeQualifierAnnotations applicable to the AnnotatedObject
	 */
	public static Collection<TypeQualifierAnnotation> getApplicableApplications(AnnotatedObject o) {
		return getApplicableScopedApplications(o, o.getElementType());
	}

	/**
	 * Get the Collection of resolved TypeQualifierAnnotations representing
	 * directly applied and default (outer scope) type qualifier annotations
	 * for given method parameter.
	 *
	 * <p>NOTE: does not properly account for inherited annotations
	 * on instance method parameters.
	 * It is ok to call this method to find out generally-relevant TypeQualifierAnnotations,
	 * but not to find the effective TypeQualifierAnnotation.</p>
	 *
	 * @param o         a method
	 * @param parameter a parameter (0 == first parameter)
	 * @return Collection of TypeQualifierAnnotations applicable to the method parameter
	 */
	public static Collection<TypeQualifierAnnotation> getApplicableApplications(XMethod o, int parameter) {
		return getApplicableScopedApplications(o, parameter);
	}

	/**
	 * Look up a TypeQualifierAnnotation matching given TypeQualifierValue.
	 *
	 * @param typeQualifierAnnotations a Collection of TypeQualifierAnnotations
	 * @param typeQualifierValue       a TypeQualifierValue
	 * @return matching TypeQualifierAnnotation, or null if none
	 */
	private static @CheckForNull TypeQualifierAnnotation findMatchingTypeQualifierAnnotation(
			Collection<TypeQualifierAnnotation> typeQualifierAnnotations,
			TypeQualifierValue typeQualifierValue) {
		for (TypeQualifierAnnotation typeQualifierAnnotation : typeQualifierAnnotations) {
			if (typeQualifierAnnotation.typeQualifier.equals(typeQualifierValue)) {
				return typeQualifierAnnotation;
			}
		}
		return null;
	}

	/**
	 * Look for a default type qualifier annotation.
	 *
	 * @param o                  an AnnotatedObject
	 * @param typeQualifierValue a TypeQualifierValue
	 * @param elementType        type of element for which we're looking for a default annotation
	 * @return default TypeQualifierAnnotation, or null if none
	 */
	private static @CheckForNull TypeQualifierAnnotation getDefaultAnnotation(AnnotatedObject o, TypeQualifierValue typeQualifierValue, ElementType elementType) {
		//
		// Try to find a default annotation using the standard JSR-305
		// default annotation mechanism.
		//
		TypeQualifierAnnotation result;
		Collection<AnnotationValue> values =  TypeQualifierResolver.resolveTypeQualifierDefaults(o.getAnnotations(), elementType);
		TypeQualifierAnnotation tqa = extractAnnotation(values, typeQualifierValue);
		
		if (tqa != null) {
			// System.out.println("Found default annotation of " + tqa + " for element " + elementType + " in " + o);
			return tqa;
		}

		//
		// Try one of the FindBugs-specific default annotation mechanisms.
		//
		
		if ((result = checkFindBugsDefaultAnnotation(FindBugsDefaultAnnotations.DEFAULT_ANNOTATION, o, typeQualifierValue)) != null) {
			return result;
		}

		switch (elementType) {
		case FIELD:
			result = checkFindBugsDefaultAnnotation(FindBugsDefaultAnnotations.DEFAULT_ANNOTATION_FOR_FIELDS, o, typeQualifierValue);
			break;
		case METHOD:
			result = checkFindBugsDefaultAnnotation(FindBugsDefaultAnnotations.DEFAULT_ANNOTATION_FOR_METHODS, o, typeQualifierValue);
			break;
		case PARAMETER:
			result = checkFindBugsDefaultAnnotation(FindBugsDefaultAnnotations.DEFAULT_ANNOTATION_FOR_PARAMETERS, o, typeQualifierValue);
			break;
		default:
			// ignore
		}

		return result;
	}

	private static @CheckForNull TypeQualifierAnnotation checkFindBugsDefaultAnnotation(ClassDescriptor defaultAnnotation, AnnotatedObject o,
			TypeQualifierValue typeQualifierValue) {

		if (DEBUG_DEFAULT_ANNOTATION) {
			System.out.println("Checking for " + defaultAnnotation + " containing " + typeQualifierValue + " on " + o);
		}
		// - check to see if default annotation is present; if not, return null
		AnnotationValue annotationValue = o.getAnnotation(defaultAnnotation);
		if (annotationValue == null) {
			if (DEBUG_DEFAULT_ANNOTATION) {
				System.out.println("   ===> no " + defaultAnnotation);
			}
			return null;
		}

		// - get value - should be Type or array of Type
		Object value = annotationValue.getValue("value");
		if (value == null) {
			if (DEBUG_DEFAULT_ANNOTATION) {
				System.out.println("   ===> value is null");
			}
			return null;
		}
		Object[] types;
		if (value instanceof Object[]) {
			types = (Object[]) value;
		} else {
			types = new Object[]{ value };
		}

		// - scan through array elements; see if any match the TypeQualifierValue (including type qualifier nicknames)
		for (Object obj : types) {
			if (!(obj instanceof Type)) {
				if (DEBUG_DEFAULT_ANNOTATION) {
					System.out.println("Found a non-Type value in value array of " + defaultAnnotation.toString() + " annotation");
				}
				continue;
			}

			Type type = (Type) obj;
			if (DEBUG_DEFAULT_ANNOTATION) {
				System.out.println("  ===> checking " + type.getDescriptor());
			}
			if (type.getDescriptor().startsWith("[")) {
				continue;
			}
			ClassDescriptor typeDesc = DescriptorFactory.instance().getClassDescriptor(type.getInternalName());

			// There is no general way to figure out whether a particular
			// type is a type qualifier we're interested in without
			// resolving it.
			AnnotationValue annotation = new AnnotationValue(typeDesc);
			Collection<AnnotationValue> resolvedTypeQualifiers = TypeQualifierResolver.resolveTypeQualifiers(annotation);
			TypeQualifierAnnotation tqa = extractAnnotation(resolvedTypeQualifiers, typeQualifierValue);
			if (tqa != null) return tqa;

		}

		return null;
	}
	
	private static TypeQualifierAnnotation extractAnnotation(Collection<AnnotationValue> resolvedTypeQualifiers, TypeQualifierValue typeQualifierValue) {
		for (AnnotationValue typeQualifier : resolvedTypeQualifiers) {
			TypeQualifierAnnotation tqa = constructTypeQualifierAnnotation(typeQualifier);
			if (tqa.typeQualifier.equals(typeQualifierValue)) {
				if (DEBUG) {
					System.out.println("  ===> Found match " + tqa);
				}
				return tqa;
			}
		}
		return null;
	}
	
	/**
	 * Get the effective TypeQualifierAnnotation on given
	 * AnnotatedObject.  Takes into account inherited and
	 * default (outer scope) annotations.
	 * Also takes exclusive qualifiers into account.
	 *
	 * @param o                  an AnnotatedObject
	 * @param typeQualifierValue a TypeQualifierValue specifying kind of annotation
	 *                           we want to look up
	 * @return the effective TypeQualifierAnnotation, or null if
	 *         there is no effective TypeQualifierAnnotation on this
	 *         AnnotatedObject
	 */
	public static TypeQualifierAnnotation getEffectiveTypeQualifierAnnotation(
			final AnnotatedObject o,
			TypeQualifierValue typeQualifierValue) {

		TypeQualifierAnnotation tqa = computeEffectiveTypeQualifierAnnotation(typeQualifierValue, o);

		if (CHECK_EXCLUSIVE && tqa == null && typeQualifierValue.isExclusiveQualifier()) {
			tqa = computeExclusiveQualifier(typeQualifierValue, new ComputeEffectiveTypeQualifierAnnotation() {
				public TypeQualifierAnnotation compute(TypeQualifierValue tqv) {
					return computeEffectiveTypeQualifierAnnotation(tqv, o);
				}

				@Override
				public String toString() {
					return o.toString();
				}
			});
		}
		
		return tqa;
	}

	private static TypeQualifierAnnotation computeEffectiveTypeQualifierAnnotation(TypeQualifierValue typeQualifierValue, AnnotatedObject o) {
		
		Map<AnnotatedObject, TypeQualifierAnnotation> map = getEffectiveObjectAnnotations().get(typeQualifierValue);
		if (map == null) {
			map = new HashMap<AnnotatedObject, TypeQualifierAnnotation>();
			getEffectiveObjectAnnotations().put(typeQualifierValue, map);
		}

		// Check cached answer
		TypeQualifierAnnotation result;

		if (map.containsKey(o)) {
			result = map.get(o);
		} else {
			if (DEBUG) {
				System.out.println("Looking up application of " + typeQualifierValue + " on " + o);
			}

			// Compute answer
			TypeQualifierAnnotation tqa;

			// See if there is a direct application
			tqa = getDirectTypeQualifierAnnotation(o, typeQualifierValue);

			// If it's an instance method, check for an inherited annotation
			if (tqa == null && (o instanceof XMethod) && !((XMethod) o).isStatic() 
					&& !((XMethod) o).isPrivate() && !((XMethod) o).getName().equals("<init>") ) {
				tqa = getInheritedTypeQualifierAnnotation((XMethod) o, typeQualifierValue);
			}

			boolean methodOverrides = false;
			if (tqa == TypeQualifierAnnotation.OVERRIDES_BUT_NO_ANNOTATION) {
				methodOverrides = true;
				tqa = null;
			}
			// Check for a default (outer scope) annotation
			if (tqa == null) {
				tqa = getDefaultTypeQualifierAnnotation(o, typeQualifierValue, methodOverrides);
			}

			// Cache computed answer
			result = tqa;
			map.put(o, result);
			if (DEBUG && result != null) {
					System.out.println("  => Answer: " + result.when  + " on " + o);
			}

		}

		// Return cached answer
		return result;
	}

	/**
	 * Get a directly-applied TypeQualifierAnnotation on given AnnotatedObject.
	 *
	 * @param o                  an AnnotatedObject
	 * @param typeQualifierValue the kind of TypeQualifierValue we are looking for
	 * @return directly-applied TypeQualifierAnnotation, or null if there is no
	 *         such annotation on the AnnotatedObject
	 */
	private static TypeQualifierAnnotation getDirectTypeQualifierAnnotation(AnnotatedObject o,
			TypeQualifierValue typeQualifierValue) {
		TypeQualifierAnnotation result;

		Set<TypeQualifierAnnotation> applications = new HashSet<TypeQualifierAnnotation>();
		getDirectApplications(applications, o, o.getElementType());

		result = findMatchingTypeQualifierAnnotation(applications, typeQualifierValue);

		return result;
	}

	/**
	 * Get the effective inherited TypeQualifierAnnotation on given
	 * instance method.
	 *
	 * @param o                  an XMethod
	 * @param typeQualifierValue the kind of TypeQualifierValue we are looking for
	 * @return effective TypeQualifierAnnotation inherited from overridden supertype methods,
	 *         or null if there is no inherited TypeQualifierAnnotation
	 */
	private static TypeQualifierAnnotation getInheritedTypeQualifierAnnotation(XMethod o, TypeQualifierValue typeQualifierValue) {
		assert !o.isStatic();

		ReturnTypeAnnotationAccumulator accumulator = new ReturnTypeAnnotationAccumulator(typeQualifierValue, o);
		try {
			AnalysisContext.currentAnalysisContext().getSubtypes2().traverseSupertypes(o.getClassDescriptor(), accumulator);
			TypeQualifierAnnotation result = accumulator.getResult().getEffectiveTypeQualifierAnnotation();
			if (result == null && accumulator.overrides()) 
				return TypeQualifierAnnotation.OVERRIDES_BUT_NO_ANNOTATION;
			return result;
		} catch (ClassNotFoundException e) {
			AnalysisContext.currentAnalysisContext().getLookupFailureCallback().reportMissingClass(e);
			return null;
		}
	}

	/**
	 * Get the default (outer scope) annotation applicable to given
	 * AnnotatedObject.
	 *
	 * @param o                  an AnnotatedObject
	 * @param typeQualifierValue the kind of TypeQualifierValue we are looking for
	 * @return the applicable default TypeQualifierAnnotation, or null
	 *         if there is no default TypeQualifierAnnotation
	 */
	private static TypeQualifierAnnotation getDefaultTypeQualifierAnnotation(AnnotatedObject o,
			TypeQualifierValue typeQualifierValue, boolean stopAtClassScope) {

		if (o.isSynthetic())
				return null; // synthetic objects don't get default annotations
		
		ElementType elementType = o.getElementType();
		while (true) {
			o = o.getContainingScope();
			if (o == null) 
				return null;
			if (stopAtClassScope && o instanceof XClass)
				return null;
			TypeQualifierAnnotation result;

			// Check direct applications of the type qualifier
			Set<TypeQualifierAnnotation> applications = new HashSet<TypeQualifierAnnotation>();
			getDirectApplications(applications, o, elementType);
			result = findMatchingTypeQualifierAnnotation(applications, typeQualifierValue);
			if (result != null) {
				// Great - found an outer scope with a relevant annotation
				assert false : "I don't think we should be looking here";
				return result;
			}

			// Check default annotations
			result = getDefaultAnnotation(o, typeQualifierValue, elementType);
			if (result != null) {
				return result;
			}
		}
	}
	
	/**
	 * Get the effective TypeQualifierAnnotation on given method parameter.
	 * Takes into account inherited and default (outer scope) annotations.
	 * Also takes exclusive qualifiers into account.
	 *
	 * @param xmethod            a method
	 * @param parameter          a parameter (0 == first parameter)
	 * @param typeQualifierValue the kind of TypeQualifierValue we are looking for
	 * @return effective TypeQualifierAnnotation on the parameter,
	 *         or null if there is no effective TypeQualifierAnnotation
	 */
	public static @CheckForNull TypeQualifierAnnotation getEffectiveTypeQualifierAnnotation(
			final XMethod xmethod,
			final int parameter,
			TypeQualifierValue typeQualifierValue) {

		
		TypeQualifierAnnotation tqa = computeEffectiveTypeQualifierAnnotation(typeQualifierValue, xmethod, parameter);
		
		if (CHECK_EXCLUSIVE && tqa == null && typeQualifierValue.isExclusiveQualifier()) {
			tqa = computeExclusiveQualifier(typeQualifierValue, new ComputeEffectiveTypeQualifierAnnotation() {
				public TypeQualifierAnnotation compute(TypeQualifierValue tqv) {
					return computeEffectiveTypeQualifierAnnotation(tqv, xmethod, parameter);
				}

				@Override
				public String toString() {
					return "parameter " + parameter + " of " + xmethod;
				}
			});
		}
		
		return tqa;
	}
	
//	static Map<String, Throwable> checked = new HashMap<String, Throwable>();

	private static TypeQualifierAnnotation computeEffectiveTypeQualifierAnnotation(TypeQualifierValue typeQualifierValue, XMethod xmethod, int parameter) {
		if (DEBUG) {
//			System.out.println("XX: " +System.identityHashCode(typeQualifierValue));
			if (typeQualifierValue.value != null) {
				System.out.println("  Value is " + typeQualifierValue.value +"("+typeQualifierValue.value.getClass().toString()+")");
			}
		}
		Map<TypeQualifierValue, DualKeyHashMap<XMethod, Integer, TypeQualifierAnnotation>> effectiveParameterAnnotations = getEffectiveParameterAnnotations();
		DualKeyHashMap<XMethod, Integer, TypeQualifierAnnotation> map = effectiveParameterAnnotations.get(typeQualifierValue);
		if (map == null) {
			if (DEBUG) {
				System.out.println("computeEffectiveTypeQualifierAnnotation: Creating map for " + typeQualifierValue);
			}
			map = new DualKeyHashMap<XMethod, Integer, TypeQualifierAnnotation>();
			effectiveParameterAnnotations.put(typeQualifierValue, map);
		}

		// Check cached answer
		TypeQualifierAnnotation result;
		if (map.containsKey(xmethod, parameter)) {
			result = map.get(xmethod, parameter);
		} else {
			if (DEBUG) {
				System.out.println("Looking up application of " + typeQualifierValue + " on " + xmethod + " parameter " + parameter);
				if (false && xmethod.getName().equals("assertIncreasing"))
					System.out.println("Found it");
			}

//			String desc = xmethod.toString()+":"+parameter+":"+typeQualifierValue;
//			if (checked.containsKey(desc)) {
//				//throw new IllegalStateException("Repeating computation of " + desc, checked.get(desc));
//				System.out.println("Repeating computation of " + desc);
//				System.out.println("Previously computed:");
//				checked.get(desc).printStackTrace(System.out);
//				throw new IllegalStateException();
//			}
//			checked.put(desc, new Throwable().fillInStackTrace());

			// Compute answer
			TypeQualifierAnnotation tqa;

			// Check direct application
			if (DEBUG) {
				System.out.print("  (1) Checking direct application...");
			}
			tqa = getDirectTypeQualifierAnnotation(xmethod, parameter, typeQualifierValue);
			if (DEBUG) {
				System.out.println(tqa != null ? "FOUND" : "none");
			}

			
			// If it's an instance method, check for inherited annotation
			if (tqa == null && !xmethod.isStatic() 	&& !xmethod.isPrivate() && !xmethod.getName().equals("<init>")) {
				if (DEBUG) {
					System.out.print("  (2) Checking inherited...");
				}
				tqa = getInheritedTypeQualifierAnnotation(xmethod, parameter, typeQualifierValue);
				if (DEBUG) {
					if (tqa == TypeQualifierAnnotation.OVERRIDES_BUT_NO_ANNOTATION) 
						System.out.println("Overridden, no annotation inherited");
					else if (tqa != null)
						System.out.println("Inherited " + tqa.when);
					else System.out.println("Nothing inherited");
				}
			}
			boolean overriddenMethod = false;
			if (tqa == TypeQualifierAnnotation.OVERRIDES_BUT_NO_ANNOTATION) {
				overriddenMethod = true;
				tqa = null;
			}
			// Check for default (outer scope) annotation
			if (tqa == null) {
				if (DEBUG) {
					System.out.print("  (3) Checking default...");
				}

				tqa = getDefaultTypeQualifierAnnotationForParameters(xmethod, typeQualifierValue, overriddenMethod);

				if (DEBUG) {
					System.out.println(tqa != null ? "FOUND" : "none");
				}
			}

			// Cache answer
			result = tqa;
			map.put(xmethod, parameter, result);

			if (DEBUG ) {
				if (result == null)
					System.out.println("  => Answer: no annotation on parameter " + parameter + " of " + xmethod);
				else 
					System.out.println("  => Answer: " + result.when + " on parameter " + parameter + " of " + xmethod);
			}
		}
		
		if (!map.containsKey(xmethod, parameter)) {
			throw new IllegalStateException("Did not populate cache?");
		}

		// Return cached answer
		return result;
	}

	/**
	 * Get the TypeQualifierAnnotation directly applied to given
	 * method parameter.
	 *
	 * @param xmethod            a method
	 * @param parameter          a parameter (0 == first parameter)
	 * @param typeQualifierValue the kind of TypeQualifierValue we are looking for
	 * @return TypeQualifierAnnotation directly applied to the parameter,
	 *         or null if there is no directly applied TypeQualifierAnnotation
	 */
	public static @CheckForNull TypeQualifierAnnotation getDirectTypeQualifierAnnotation(XMethod xmethod, int parameter,
			TypeQualifierValue typeQualifierValue) {
		Set<TypeQualifierAnnotation> applications = new HashSet<TypeQualifierAnnotation>();
		getDirectApplications(applications, xmethod, parameter);
		if (DEBUG_METHOD != null && DEBUG_METHOD.equals(xmethod.getName())) {
			System.out.println("  Direct applications are: " + applications);
		}

		return findMatchingTypeQualifierAnnotation(applications, typeQualifierValue);
	}

	/**
	 * Get the effective inherited TypeQualifierAnnotation on the given
	 * instance method parameter.
	 *
	 * @param xmethod            an instance method
	 * @param parameter          a parameter (0 == first parameter)
	 * @param typeQualifierValue the kind of TypeQualifierValue we are looking for
	 * @return effective inherited TypeQualifierAnnotation on the parameter,
	 *         or null if there is not effective TypeQualifierAnnotation
	 */
	private static @CheckForNull TypeQualifierAnnotation getInheritedTypeQualifierAnnotation(XMethod xmethod, int parameter,
			TypeQualifierValue typeQualifierValue) {
		assert !xmethod.isStatic();

		ParameterAnnotationAccumulator accumulator = new ParameterAnnotationAccumulator(typeQualifierValue, xmethod, parameter);
		try {
			AnalysisContext.currentAnalysisContext().getSubtypes2().traverseSupertypes(xmethod.getClassDescriptor(), accumulator);
			TypeQualifierAnnotation result = accumulator.getResult().getEffectiveTypeQualifierAnnotation();
			if (result == null && accumulator.overrides()) 
				return TypeQualifierAnnotation.OVERRIDES_BUT_NO_ANNOTATION;
			return result;
		} catch (ClassNotFoundException e) {
			AnalysisContext.currentAnalysisContext().getLookupFailureCallback().reportMissingClass(e);
			return null;
		}
	}

	/**
	 * Get the default (outer-scope) TypeQualifierAnnotation on given method parameter.
	 *
	 * @param xmethod            a method
	 * @param typeQualifierValue the kind of TypeQualifierValue we are looking for
	 * @param stopAtMethodScope TODO
	 * @return the default (outer scope) TypeQualifierAnnotation on the parameter,
	 *         or null if there is no default TypeQualifierAnnotation
	 */
	private static @CheckForNull TypeQualifierAnnotation getDefaultTypeQualifierAnnotationForParameters(
			XMethod xmethod,
			TypeQualifierValue typeQualifierValue, boolean stopAtMethodScope) {

		if (xmethod.isSynthetic())
			return null;  // synthetic methods don't get default annotations
		// System.out.println("Looking for default " + typeQualifierValue + " annotation of parameters of " + xmethod);
		if (xmethod.getName().equals("<init>") && xmethod.getClassDescriptor().isAnonymousClass())
			return null; // constructors for anonymous inner classes don't get default annotations
		AnnotatedObject o = xmethod;
		while (true) {
			o =  o.getContainingScope();
			if (o == null) return null;
			
			if (stopAtMethodScope && o instanceof XClass)
				return null;
			// Check for direct type qualifier annotation
			Set<TypeQualifierAnnotation> applications = new HashSet<TypeQualifierAnnotation>();
			getDirectApplications(applications, o, ElementType.PARAMETER);
			TypeQualifierAnnotation tqa = findMatchingTypeQualifierAnnotation(applications, typeQualifierValue);
			if (tqa != null) {
				// Found matching annotation in outer scope
				assert false : "I think this code is dead; it shouldn't find anything";
				return tqa;
			}

			// Check for default annotation
			tqa = getDefaultAnnotation(o, typeQualifierValue, ElementType.PARAMETER);
			if (tqa != null) {
				if (DEBUG) 
					System.out.println("Found default of " + tqa + " @ " + o);
				return tqa;
			}
		}

	}

	private static TypeQualifierAnnotation computeExclusiveQualifier(TypeQualifierValue typeQualifierValue, ComputeEffectiveTypeQualifierAnnotation c) {
		assert typeQualifierValue.isExclusiveQualifier();
		
		boolean isExhaustive = CHECK_EXHAUSTIVE && typeQualifierValue.isExhaustiveQualifier();
		
		// Exclusive qualifiers:
		// - if there is an effective application of
		//   a "complementary" TypeQualifierValue in which
		//   when=ALWAYS.  If so, then it's effectively
		//   the same as the asked-for TypeQualifierValue,
		//   but with when=NEVER.
		//
		// Exhaustive qualifiers:
		// - if all effective applications of "complementary" TypeQualifierValues
		//   are when=NEVER, then the asked-for TypeQualifierValue
		//   is effectively when=ALWAYS.
		
		boolean allComplementaryValuesAreWhenEqualsNever = true;

		Collection<TypeQualifierValue> complementaryTypeQualifierValues =
			TypeQualifierValue.getComplementaryExclusiveTypeQualifierValue(typeQualifierValue);

		for (TypeQualifierValue complementaryTypeQualifierValue : complementaryTypeQualifierValues) {
			TypeQualifierAnnotation complementaryTqa = c.compute(complementaryTypeQualifierValue);
			if (complementaryTqa != null) {
				if (complementaryTqa.when == When.ALWAYS) {
					// Exclusive qualifier where a complementary qualifier
					// was observed effectively when=ALWAYS.
					return TypeQualifierAnnotation.getValue(typeQualifierValue, When.NEVER);
				} else if (complementaryTqa.when != When.NEVER) {
					allComplementaryValuesAreWhenEqualsNever = false;
				}
			} else {
				allComplementaryValuesAreWhenEqualsNever = false;
			}
		}
		
		if (isExhaustive && allComplementaryValuesAreWhenEqualsNever) {
			// It's an exhaustive qualifier, and all complementary
			// qualifiers were effectively when=NEVER.
			if (TypeQualifierValue.DEBUG) {
				System.out.println("*** application of " + typeQualifierValue + " on " + c + " is when=ALWAYS due to exhaustion");
			}
			return TypeQualifierAnnotation.getValue(typeQualifierValue, When.ALWAYS);
		}
		
		return null;
	}
}
