public class Instances
{
	private static final Logger logger = LoggerFactory.getLogger(Instances.class);
	private final Accessor sourceAccessor;
	private final Object working;
	private final Object base;
	private final Object fresh;

	Instances(final Accessor sourceAccessor,
			  final Object working,
			  final Object base,
			  final Object fresh)
	{
		Assert.notNull(sourceAccessor, "sourceAccessor");
		this.sourceAccessor = sourceAccessor;
		this.working = working;
		this.base = base;
		this.fresh = fresh;
	}

	public static <T> Instances of(final Accessor sourceAccessor,
								   final T working,
								   final T base,
								   final T fresh)
	{
		return new Instances(sourceAccessor, working, base, fresh);
	}

	public static <T> Instances of(final Accessor sourceAccessor, final T working, final T base)
	{
		final Object fresh = (working != null) ? Classes.freshInstanceOf(working.getClass()) : null;
		return new Instances(sourceAccessor, working, base, fresh);
	}

	public static <T> Instances of(final T working, final T base)
	{
		final Object fresh = (working != null) ? Classes.freshInstanceOf(working.getClass()) : null;
		return new Instances(RootAccessor.getInstance(), working, base, fresh);
	}

	/**
	 * @return The {@link Accessor} that has been used to get to these instances.
	 */
	public Accessor getSourceAccessor()
	{
		return sourceAccessor;
	}

	public Instances access(final Accessor accessor)
	{
		Assert.notNull(accessor, "accessor");
		return new Instances(accessor, accessor.get(working), accessor.get(base), accessor.get(fresh));
	}

	public Object getWorking()
	{
		return working;
	}

	public <T> T getWorking(final Class<T> type)
	{
		return working != null ? type.cast(working) : null;
	}

	public Object getBase()
	{
		return base;
	}

	public <T> T getBase(final Class<T> type)
	{
		return base != null ? type.cast(base) : null;
	}

	public Object getFresh()
	{
		if (fresh == null)
		{
			if (isPrimitiveNumericType())
			{
				return 0;
			}
			else if (isPrimitiveBooleanType())
			{
				return false;
			}
		}
		return fresh;
	}

	@SuppressWarnings("UnusedDeclaration")
	public <T> T getFresh(final Class<T> type)
	{
		final Object o = getFresh();
		return o != null ? type.cast(o) : null;
	}

	public boolean hasBeenAdded()
	{
		if (working != null && base == null)
		{
			return true;
		}
		if (isPrimitiveType() && isEqual(getFresh(), base) && !isEqual(base, working))
		{
			return true;
		}
		return false;
	}

	public boolean hasBeenRemoved()
	{
		if (base != null && working == null)
		{
			return true;
		}
		if (isPrimitiveType() && isEqual(getFresh(), working) && !isEqual(base, working))
		{
			return true;
		}
		return false;
	}

	public boolean isPrimitiveType()
	{
		return Classes.isPrimitiveType(getType());
	}

	@SuppressWarnings("UnusedDeclaration")
	public boolean isPrimitiveWrapperType()
	{
		return Classes.isPrimitiveWrapperType(getType());
	}

	public Class<?> getType()
	{
		final Set<Class<?>> types = Classes.typesOf(working, base, fresh);
		final Class<?> sourceAccessorType = tryToGetTypeFromSourceAccessor();
		if (Classes.isPrimitiveType(sourceAccessorType))
		{
			return sourceAccessorType;
		}
		if (types.isEmpty())
		{
			return null;
		}
		if (types.size() == 1)
		{
			return Collections.firstElementOf(types);
		}
		if (types.size() > 1)
		{
// 			The following lines could be added if more precise type resolution is required:
//
//			if (Classes.allAssignableFrom(SortedSet.class, types))
//			{
//				return SortedSet.class;
//			}
//			if (Classes.allAssignableFrom(Set.class, types))
//			{
//				return Set.class;
//			}
//			if (Classes.allAssignableFrom(Queue.class, types))
//			{
//				return Queue.class;
//			}
//			if (Classes.allAssignableFrom(Deque.class, types))
//			{
//				return Deque.class;
//			}
//			if (Classes.allAssignableFrom(List.class, types))
//			{
//				return List.class;
//			}
//			else if (Classes.allAssignableFrom(SortedMap.class, types))
//			{
//				return SortedMap.class;
//			}
			if (Classes.allAssignableFrom(Collection.class, types))
			{
				return Collection.class;
			}
			else if (Classes.allAssignableFrom(Map.class, types))
			{
				return Map.class;
			}
			else
			{
				final Class<?> sharedType = Classes.mostSpecificSharedType(types);
				if (sharedType != null)
				{
					return sharedType;
				}
				else if (sourceAccessorType != null)
				{
					return sourceAccessorType;
				}
				// special handling for beans and arrays should go here
			}
		}

		logger.info("Detected instances of different types " + types + ". " +
			    "These objects will only be compared via equals method.");
		return Object.class;
	}

	private Class<?> tryToGetTypeFromSourceAccessor()
	{
		if (sourceAccessor instanceof TypeAwareAccessor)
		{
			return ((TypeAwareAccessor) sourceAccessor).getType();
		}
		return null;
	}

	public boolean isPrimitiveNumericType()
	{
		return Classes.isPrimitiveNumericType(getType());
	}

	private boolean isPrimitiveBooleanType()
	{
		return getType() == boolean.class;
	}

	public boolean areEqual()
	{
		return isEqual(base, working);
	}

	public boolean areSame()
	{
		return working == base;
	}

	public boolean areNull()
	{
		return working == null && base == null;
	}

} public interface CategoryResolver
{
	Set<String> resolveCategories(DiffNode node);
} public class PropertyReadException extends PropertyAccessException
{
	private static final long serialVersionUID = 1L;

	public PropertyReadException(final String propertyName, final Class<?> targetType, final Throwable cause)
	{
		super(propertyName, targetType, cause);
	}

	@Override
	public String getMessage()
	{
		return String.format("Failed to read value from property '%s' of type '%s'", getPropertyName(), getTargetType().getCanonicalName());
	}
} public class CircularReferenceDetector
{
	/**
	 * It would be better to use <code>java.util.Deque</code> instead of the linked list, but that was first
	 * introduced in Java 6 and would break compatibility with Java 5.
	 */
	@SuppressWarnings("TypeMayBeWeakened")
	private final LinkedList<Entry> stack = new LinkedList<Entry>();

	private ReferenceMatchingMode referenceMatchingMode = ReferenceMatchingMode.EQUALITY_OPERATOR;

	public CircularReferenceDetector(final ReferenceMatchingMode referenceMatchingMode)
	{
		Assert.notNull(referenceMatchingMode, "referenceMatchingMode");
		this.referenceMatchingMode = referenceMatchingMode;
	}

	public void push(final Object instance, final NodePath nodePath)
	{
		if (instance == null)
		{
			return;
		}
		if (knows(instance))
		{
			throw new CircularReferenceException(entryForInstance(instance).getNodePath());
		}
		final Entry entry = new Entry(nodePath, instance);
		stack.addLast(entry);
	}

	public boolean knows(final Object needle)
	{
		for (final Entry entry : stack)
		{
			final Object instance = entry.getInstance();
			if (isMatch(needle, instance))
			{
				return true;
			}
		}
		return false;
	}

	private Entry entryForInstance(final Object instance)
	{
		for (final Entry entry : stack)
		{
			if (isMatch(instance, entry.getInstance()))
			{
				return entry;
			}
		}
		return null;
	}

	protected boolean isMatch(final Object anObject, final Object anotherObject)
	{
		if (referenceMatchingMode == ReferenceMatchingMode.EQUALITY_OPERATOR)
		{
			return anotherObject == anObject;
		}
		else if (referenceMatchingMode == ReferenceMatchingMode.EQUALS_METHOD)
		{
			return (anotherObject == anObject) || isEqual(anObject, anotherObject);
		}
		else
		{
			throw new IllegalStateException("Missing reference matching mode");
		}
	}

	public void remove(final Object instance)
	{
		if (instance == null)
		{
			return;
		}
		if (isMatch(instance, stack.getLast().getInstance()))
		{
			stack.removeLast();
		}
		else
		{
			throw new IllegalArgumentException("Detected inconsistency in enter/leave sequence. Must always be LIFO.");
		}
	}

	public int size()
	{
		return stack.size();
	}

	public static enum ReferenceMatchingMode
	{
		/**
		 * Compares objects using the <code>==</code> operator.
		 */
		EQUALITY_OPERATOR,

		/**
		 * Compares objects using {@linkplain Object#equals(Object)}.
		 */
		EQUALS_METHOD
	}

	private static class Entry
	{
		private final NodePath nodePath;
		private final Object instance;

		private Entry(final NodePath nodePath, final Object instance)
		{
			this.nodePath = nodePath;
			this.instance = instance;
		}

		public NodePath getNodePath()
		{
			return nodePath;
		}

		public Object getInstance()
		{
			return instance;
		}

		@Override
		public String toString()
		{
			return nodePath.toString() + "{" + instance.toString() + "}";
		}
	}

	public static class CircularReferenceException extends RuntimeException
	{
		private static final long serialVersionUID = 1L;

		@SuppressWarnings("NonSerializableFieldInSerializableClass")
		private final NodePath nodePath;

		public CircularReferenceException(final NodePath nodePath)
		{
			this.nodePath = nodePath;
		}

		public NodePath getNodePath()
		{
			return nodePath;
		}

		@Override
		public Throwable fillInStackTrace()
		{
			return this;
		}
	}
} public interface CircularReferenceDetectorFactory
{
	CircularReferenceDetector createCircularReferenceDetector();
} public interface CircularReferenceExceptionHandler
{
	void onCircularReferenceException(DiffNode node);
} public interface IsReturnableResolver
{
	boolean isReturnable(DiffNode node);
} public interface PropertyAccessExceptionHandler
{
	/**
	 * Will be called whenever the value of a property could not be retrieved due to an underlying exception.
	 *
	 * @param exception This exception object contains more details about the property.
	 * @param node      The {@link DiffNode} for which the exception occured.
	 */
	void onPropertyReadException(PropertyReadException exception, DiffNode node);
} public interface PropertyAccessExceptionHandlerResolver
{
	/**
	 * @param parentType   The type of the object to which the property belongs.
	 * @param propertyName The name of the property.
	 */
	PropertyAccessExceptionHandler resolvePropertyAccessExceptionHandler(Class<?> parentType, String propertyName);
} @SuppressWarnings("UnusedDeclaration")
public class DiffNode
{
	public static final DiffNode ROOT = null;

	private final Accessor accessor;
	private final Map<ElementSelector, DiffNode> children = new LinkedHashMap<ElementSelector, DiffNode>(10);

	private State state = State.UNTOUCHED;
	private DiffNode parentNode;
	private NodePath circleStartPath;
	private DiffNode circleStartNode;
	private Class<?> valueType;
	private TypeInfo valueTypeInfo;
	private IdentityStrategy childIdentityStrategy;
	private final Collection<String> additionalCategories = new TreeSet<String>();

	public void setChildIdentityStrategy(final IdentityStrategy identityStrategy)
	{
		this.childIdentityStrategy = identityStrategy;
	}

	public static DiffNode newRootNode()
	{
		return new DiffNode();
	}

	public static DiffNode newRootNodeWithType(final Class<?> valueType)
	{
		final DiffNode rootNode = newRootNode();
		rootNode.setType(valueType);
		return rootNode;
	}

	public DiffNode(final DiffNode parentNode, final Accessor accessor, final Class<?> valueType)
	{
		Assert.notNull(accessor, "accessor");
		this.accessor = accessor;
		this.valueType = valueType;
		setParentNode(parentNode);
	}

	public DiffNode(final DiffNode parentNode, final Accessor accessor)
	{
		this(parentNode, accessor, null);
	}

	private DiffNode()
	{
		this.parentNode = ROOT;
		this.accessor = RootAccessor.getInstance();
	}

	/**
	 * @return The state of this node.
	 */
	public State getState()
	{
		return this.state;
	}

	/**
	 * @param state The state of this node.
	 */
	public void setState(final State state)
	{
		Assert.notNull(state, "state");
		this.state = state;
	}

	public boolean matches(final NodePath path)
	{
		return path.matches(getPath());
	}

	public boolean hasChanges()
	{
		if (isAdded() || isChanged() || isRemoved())
		{
			return true;
		}
		final AtomicBoolean result = new AtomicBoolean(false);
		visitChildren(new Visitor()
		{
			public void node(final DiffNode node, final Visit visit)
			{
				if (node.hasChanges())
				{
					result.set(true);
					visit.stop();
				}
			}
		});
		return result.get();
	}

	/**
	 * Convenience method for <code>{@link #getState()} == {@link DiffNode.State#ADDED}</code>
	 */
	public final boolean isAdded()
	{
		return state == State.ADDED;
	}

	/**
	 * Convenience method for <code>{@link #getState()} == {@link DiffNode.State#CHANGED}</code>
	 */
	public final boolean isChanged()
	{
		return state == State.CHANGED;
	}

	/**
	 * Convenience method for <code>{@link #getState()} == {@link DiffNode.State#REMOVED}</code>
	 */
	public final boolean isRemoved()
	{
		return state == State.REMOVED;
	}

	/**
	 * Convenience method for <code>{@link #getState()} == {@link DiffNode.State#UNTOUCHED}</code>
	 */
	public final boolean isUntouched()
	{
		return state == State.UNTOUCHED;
	}

	/**
	 * Convenience method for <code>{@link #getState()} == {@link DiffNode.State#CIRCULAR}</code>
	 */
	public boolean isCircular()
	{
		return state == State.CIRCULAR;
	}

	/**
	 * @return The absolute property path from the object root up to this node.
	 */
	public NodePath getPath()
	{
		if (parentNode != null)
		{
			return NodePath.startBuildingFrom(parentNode.getPath())
					.element(accessor.getElementSelector())
					.build();
		}
		else if (accessor instanceof RootAccessor)
		{
			return NodePath.withRoot();
		}
		else
		{
			return NodePath.startBuilding().element(accessor.getElementSelector()).build();
		}
	}

	public ElementSelector getElementSelector()
	{
		return accessor.getElementSelector();
	}

	/**
	 * @return Returns the type of the property represented by this node, or null if unavailable.
	 */
	public Class<?> getValueType()
	{
		if (valueType != null)
		{
			return valueType;
		}
		if (valueTypeInfo != null)
		{
			return valueTypeInfo.getType();
		}
		if (accessor instanceof TypeAwareAccessor)
		{
			return ((TypeAwareAccessor) accessor).getType();
		}
		return null;
	}

	/**
	 * Allows to explicity set the type of this node. This will overshadow the type returned by {@linkplain
	 * #getValueTypeInfo()} as well as the one returned by the accessor.
	 *
	 * @param aClass The type of the value represented by this node.
	 */
	public final void setType(final Class<?> aClass)
	{
		this.valueType = aClass;
	}

	public TypeInfo getValueTypeInfo()
	{
		return valueTypeInfo;
	}

	public void setValueTypeInfo(final TypeInfo typeInfo)
	{
		this.valueTypeInfo = typeInfo;
	}

	/**
	 * @return <code>true</code> if this node has children.
	 */
	public boolean hasChildren()
	{
		return !children.isEmpty();
	}

	public int childCount()
	{
		return children.size();
	}

	/**
	 * Retrieve a child with the given property name relative to this node.
	 *
	 * @param propertyName The name of the property represented by the child node.
	 * @return The requested child node or <code>null</code>.
	 */
	public DiffNode getChild(final String propertyName)
	{
		return getChild(new BeanPropertyElementSelector(propertyName));
	}

	/**
	 * Retrieve a child that matches the given path element relative to this node.
	 *
	 * @param elementSelector The path element of the child node to get.
	 * @return The requested child node or <code>null</code>.
	 */
	public DiffNode getChild(final ElementSelector elementSelector)
	{
		if (elementSelector instanceof CollectionItemElementSelector && childIdentityStrategy != null)
		{
			return children.get(((CollectionItemElementSelector) elementSelector).copyWithIdentityStrategy(childIdentityStrategy));
		}
		else
		{
			return children.get(elementSelector);
		}
	}

	/**
	 * Retrieve a child that matches the given absolute path, starting from the current node.
	 *
	 * @param nodePath The path from the object root to the requested child node.
	 * @return The requested child node or <code>null</code>.
	 */
	public DiffNode getChild(final NodePath nodePath)
	{
		if (parentNode != null)
		{
			return parentNode.getChild(nodePath.getElementSelectors());
		}
		else
		{
			return getChild(nodePath.getElementSelectors());
		}
	}

	/**
	 * Retrieve a child that matches the given path element relative to this node.
	 *
	 * @param selectors The path element of the child node to get.
	 * @return The requested child node or <code>null</code>.
	 */
	public DiffNode getChild(final List<ElementSelector> selectors)
	{
		Assert.notEmpty(selectors, "selectors");
		final ElementSelector selector = selectors.get(0);
		if (selectors.size() == 1)
		{
			if (selector == RootElementSelector.getInstance())
			{
				return isRootNode() ? this : null;
			}
			else
			{
				return getChild(selector);
			}
		}
		else if (selectors.size() > 1)
		{
			final DiffNode child;
			if (selector == RootElementSelector.getInstance())
			{
				child = isRootNode() ? this : null;
			}
			else
			{
				child = getChild(selector);
			}
			if (child != null)
			{
				return child.getChild(selectors.subList(1, selectors.size()));
			}
		}
		return null;
	}

	/**
	 * Adds a child to this node and sets this node as its parent node.
	 *
	 * @param node The node to add.
	 */
	public void addChild(final DiffNode node)
	{
		if (node == this)
		{
			throw new IllegalArgumentException("Detected attempt to add a node to itself. " +
					"This would cause inifite loops and must never happen.");
		}
		else if (node.isRootNode())
		{
			throw new IllegalArgumentException("Detected attempt to add root node as child. " +
					"This is not allowed and must be a mistake.");
		}
		else if (node.getParentNode() != null && node.getParentNode() != this)
		{
			throw new IllegalArgumentException("Detected attempt to add child node that is already the " +
					"child of another node. Adding nodes multiple times is not allowed, since it could " +
					"cause infinite loops.");
		}
		if (node.getParentNode() == null)
		{
			node.setParentNode(this);
		}
		children.put(node.getElementSelector(), node);
		if (state == State.UNTOUCHED && node.hasChanges())
		{
			state = State.CHANGED;
		}
	}

	/**
	 * Visit this and all child nodes.
	 *
	 * @param visitor The visitor to use.
	 */
	public final void visit(final Visitor visitor)
	{
		final Visit visit = new Visit();
		try
		{
			visit(visitor, visit);
		}
		catch (final StopVisitationException ignored)
		{
		}
	}

	protected final void visit(final Visitor visitor, final Visit visit)
	{
		try
		{
			visitor.node(this, visit);
		}
		catch (final StopVisitationException e)
		{
			visit.stop();
		}
		if (visit.isAllowedToGoDeeper() && hasChildren())
		{
			visitChildren(visitor);
		}
		if (visit.isStopped())
		{
			throw new StopVisitationException();
		}
	}

	/**
	 * Visit all child nodes but not this one.
	 *
	 * @param visitor The visitor to use.
	 */
	public final void visitChildren(final Visitor visitor)
	{
		for (final DiffNode child : children.values())
		{
			try
			{
				child.visit(visitor);
			}
			catch (final StopVisitationException e)
			{
				return;
			}
		}
	}

	public final void visitParents(final Visitor visitor)
	{
		final Visit visit = new Visit();
		if (parentNode != null)
		{
			visitor.node(parentNode, visit);
			if (!visit.isStopped())
			{
				parentNode.visitParents(visitor);
			}
		}
	}

	/**
	 * If this node represents a bean property this method returns all annotations of its field.
	 * <p/>
	 * Only works for fields having a name that matches the name derived from the getter.
	 *
	 * @return The annotations of the field, or an empty set if there is no field with the name derived from the getter.
	 */
	public Set<Annotation> getFieldAnnotations()
	{
		if (accessor instanceof PropertyAwareAccessor)
		{
			return unmodifiableSet(((PropertyAwareAccessor) accessor).getFieldAnnotations());
		}
		return unmodifiableSet(Collections.<Annotation>emptySet());
	}

	/**
	 * @param annotationClass the annotation we are looking for
	 * @param <T>
	 * @return The given annotation of the field, or null if not annotated or if there is no field with the name derived
	 * from the getter.
	 */
	public <T extends Annotation> T getFieldAnnotation(final Class<T> annotationClass)
	{
		if (accessor instanceof PropertyAwareAccessor)
		{
			return ((PropertyAwareAccessor) accessor).getFieldAnnotation(annotationClass);
		}
		return null;
	}

	/**
	 * If this node represents a bean property this method returns all annotations of its getter.
	 *
	 * @return A set of annotations of this nodes property getter or an empty set.
	 */
	public Set<Annotation> getPropertyAnnotations()
	{
		if (accessor instanceof PropertyAwareAccessor)
		{
			return unmodifiableSet(((PropertyAwareAccessor) accessor).getReadMethodAnnotations());
		}
		return unmodifiableSet(Collections.<Annotation>emptySet());
	}

	public <T extends Annotation> T getPropertyAnnotation(final Class<T> annotationClass)
	{
		if (accessor instanceof PropertyAwareAccessor)
		{
			return ((PropertyAwareAccessor) accessor).getReadMethodAnnotation(annotationClass);
		}
		return null;
	}

	/**
	 * If this node represents a bean property, this method will simply return its name. Otherwise it will return the
	 * property name of its closest bean property representing ancestor. This way intermediate nodes like those
	 * representing collection, map or array items will be semantically tied to their container objects.
	 * <p/>
	 * That is especially useful for inclusion and exclusion rules. For example, when a List is explicitly included by
	 * property name, it would be weird if the inclusion didn't also apply to its items.
	 */
	public String getPropertyName()
	{
		if (isPropertyAware())
		{
			return ((PropertyAwareAccessor) accessor).getPropertyName();
		}
		else if (parentNode != null)
		{
			return parentNode.getPropertyName();
		}
		return null;
	}

	/**
	 * Returns <code>true</code> when this node represents a bean property and can therefore be queried for property
	 * specific information like annotations or property types. But there will also be nodes that represent collection
	 * items, map entries, etc. In those cases this method will return <code>false</code>.
	 */
	public final boolean isPropertyAware()
	{
		return accessor instanceof PropertyAwareAccessor;
	}

	public final boolean isRootNode()
	{
		return accessor instanceof RootAccessor;
	}

	/**
	 * Convenience method for <code>{@link #getState()} == {@link DiffNode.State#IGNORED}</code>
	 */
	public final boolean isIgnored()
	{
		return state == State.IGNORED;
	}

	/**
	 * @see de.danielbechler.diff.inclusion.TypePropertyAnnotationInclusionResolver
	 * @deprecated This method was a shortcut to extract the "exclude" flag from the ObjectDiffProperty
	 * annotation. Since we found a better way to do that, it is not needed anymore and will be removed in future
	 * versions. The name is also misleading. It implies that here lies the truth about the exclusion, but only the
	 * InclusionService can tell for sure. This flag is just only little piece of the puzzle.
	 */
	@Deprecated
	public boolean isExcluded()
	{
		if (accessor instanceof ExclusionAware)
		{
			return ((ExclusionAware) accessor).isExcludedByAnnotation();
		}
		return false;
	}

	/**
	 * Returns an unmodifiable {@link java.util.Set} of {@link java.lang.String} with the categories of this node.
	 *
	 * @return an unmodifiable {@link java.util.Set} of {@link java.lang.String} with the categories of this node
	 */
	public final Set<String> getCategories()
	{
		final Set<String> categories = new TreeSet<String>();
		if (parentNode != null)
		{
			categories.addAll(parentNode.getCategories());
		}
		if (accessor instanceof CategoryAware)
		{
			final Set<String> categoriesFromAccessor = ((CategoryAware) accessor).getCategoriesFromAnnotation();
			if (categoriesFromAccessor != null)
			{
				categories.addAll(categoriesFromAccessor);
			}
		}
		categories.addAll(additionalCategories);

		return unmodifiableSet(categories);
	}

	/**
	 * @return The parent node, if any.
	 */
	public DiffNode getParentNode()
	{
		return parentNode;
	}

	/**
	 * Sets the parent node.
	 *
	 * @param parentNode The parent of this node. May be null, if this is a root node.
	 */
	protected final void setParentNode(final DiffNode parentNode)
	{
		if (this.parentNode != null && this.parentNode != parentNode)
		{
			throw new IllegalStateException("The parent of a node cannot be changed, once it's set.");
		}
		this.parentNode = parentNode;
	}

	public Object get(final Object target)
	{
		return accessor.get(target);
	}

	public void set(final Object target, final Object value)
	{
		accessor.set(target, value);
	}

	public void unset(final Object target)
	{
		accessor.unset(target);
	}

	public Object canonicalGet(Object target)
	{
		if (parentNode != null)
		{
			target = parentNode.canonicalGet(target);
		}
		return get(target);
	}

	public void canonicalSet(Object target, final Object value)
	{
		if (parentNode != null)
		{
			Object parent = parentNode.canonicalGet(target);
			if (parent == null)
			{
				parent = parentNode.newInstance();
				parentNode.canonicalSet(target, parent);
			}
			target = parent;
		}
		set(target, value);
	}

	private Object newInstance()
	{
		if (valueTypeInfo != null)
		{
			return valueTypeInfo.newInstance();
		}
		return null;
	}

	public void canonicalUnset(Object target)
	{
		if (parentNode != null)
		{
			target = parentNode.canonicalGet(target);
		}
		unset(target);
	}

	@Override
	public int hashCode()
	{
		return accessor.hashCode();
	}

	@Override
	public boolean equals(final Object o)
	{
		if (this == o)
		{
			return true;
		}
		if (o == null || getClass() != o.getClass())
		{
			return false;
		}

		final DiffNode that = (DiffNode) o;

		if (!accessor.equals(that.accessor))
		{
			return false;
		}

		return true;
	}

	@Override
	public String toString()
	{
		final StringBuilder sb = new StringBuilder();
		sb.append(getClass().getSimpleName());
		sb.append("(");
		sb.append("state=");
		sb.append(getState().toString());
		if (getValueType() != null)
		{
			sb.append(", type=").append(getValueType().getCanonicalName());
		}
		if (childCount() == 1)
		{
			sb.append(", ").append(childCount()).append(" child");
		}
		else if (childCount() > 1)
		{
			sb.append(", ").append(childCount()).append(" children");
		}
		else
		{
			sb.append(", no children");
		}
		if (!getCategories().isEmpty())
		{
			sb.append(", categorized as ").append(getCategories());
		}
		sb.append(", accessed via ").append(accessor);
		sb.append(')');
		return sb.toString();
	}

	public void addCategories(final Collection<String> additionalCategories)
	{
		Assert.notNull(additionalCategories, "additionalCategories");
		this.additionalCategories.addAll(additionalCategories);
	}

	/**
	 * @return Returns the path to the first node in the hierarchy that represents the same object instance as
	 * this one. (Only if {@link #isCircular()} returns <code>true</code>.
	 */
	public NodePath getCircleStartPath()
	{
		return circleStartPath;
	}

	public void setCircleStartPath(final NodePath circularStartPath)
	{
		this.circleStartPath = circularStartPath;
	}

	public DiffNode getCircleStartNode()
	{
		return circleStartNode;
	}

	public void setCircleStartNode(final DiffNode circleStartNode)
	{
		this.circleStartNode = circleStartNode;
	}

	/**
	 * The state of a {@link DiffNode} representing the difference between two objects.
	 */
	public enum State
	{
		ADDED("The value has been added to the working object"),
		CHANGED("The value exists but differs between the base and working object"),
		REMOVED("The value has been removed from the working object"),
		UNTOUCHED("The value is identical in the working and base object"),
		CIRCULAR("Special state to mark circular references"),
		IGNORED("The value has not been looked at and has been ignored"),
		INACCESSIBLE("When a comparison was not possible because the underlying value was not accessible");

		private final String reason;

		State(final String reason)
		{
			this.reason = reason;
		}

		public String getReason()
		{
			return reason;
		}
	}

	/**
	 * Visitor to traverse a node graph.
	 */
	public interface Visitor
	{
		void node(DiffNode node, Visit visit);
	}
} public final class NodePath implements Comparable<NodePath>
{
	private final List<ElementSelector> elementSelectors;

	private NodePath(final List<ElementSelector> elementSelectors)
	{
		this.elementSelectors = Collections.unmodifiableList(elementSelectors);
	}

	public boolean isParentOf(final NodePath nodePath)
	{
		final List<ElementSelector> otherElementSelectors = nodePath.getElementSelectors();
		if (elementSelectors.size() < otherElementSelectors.size())
		{
			return otherElementSelectors.subList(0, elementSelectors.size()).equals(elementSelectors);
		}
		return false;
	}

	public List<ElementSelector> getElementSelectors()
	{
		return elementSelectors;
	}

	public boolean isChildOf(final NodePath nodePath)
	{
		final List<ElementSelector> otherElementSelectors = nodePath.getElementSelectors();
		if (elementSelectors.size() > otherElementSelectors.size())
		{
			return elementSelectors.subList(0, otherElementSelectors.size()).equals(otherElementSelectors);
		}
		return false;
	}

	public ElementSelector getLastElementSelector()
	{
		return elementSelectors.get(elementSelectors.size() - 1);
	}

	@Override
	public int hashCode()
	{
		return elementSelectors.hashCode();
	}

	@Override
	public boolean equals(final Object o)
	{
		if (this == o)
		{
			return true;
		}
		if (o == null || getClass() != o.getClass())
		{
			return false;
		}

		final NodePath that = (NodePath) o;

		if (!elementSelectors.equals(that.elementSelectors))
		{
			return false;
		}

		return true;
	}

	@Override
	public String toString()
	{
		final StringBuilder sb = new StringBuilder();
		final Iterator<ElementSelector> iterator = elementSelectors.iterator();
		ElementSelector previousElementSelector = null;
		while (iterator.hasNext())
		{
			final ElementSelector elementSelector = iterator.next();
			if (elementSelector instanceof RootElementSelector)
			{
				sb.append("/");
			}
			else if (elementSelector instanceof CollectionItemElementSelector || elementSelector instanceof MapKeyElementSelector)
			{
				sb.append(elementSelector);
			}
			else if (previousElementSelector instanceof RootElementSelector)
			{
				sb.append(elementSelector);
			}
			else
			{
				sb.append('/');
				sb.append(elementSelector);
			}
			previousElementSelector = elementSelector;
		}
		return sb.toString();
	}

	public int compareTo(final NodePath that)
	{
		final int distance = getElementSelectors().size() - that.getElementSelectors().size();
		if (distance == 0)
		{
			return matches(that) ? 0 : 1;
		}
		else if (distance > 0)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}

	public boolean matches(final NodePath nodePath)
	{
		return nodePath.equals(this);
	}

	public static AppendableBuilder startBuildingFrom(final NodePath nodePath)
	{
		Assert.notNull(nodePath, "propertyPath");
		return new AppendableBuilderImpl(new ArrayList<ElementSelector>(nodePath.getElementSelectors()));
	}

	public static NodePath with(final String propertyName, final String... additionalPropertyNames)
	{
		return startBuilding().propertyName(propertyName, additionalPropertyNames).build();
	}

	public static AppendableBuilder startBuilding()
	{
		final List<ElementSelector> elementSelectors1 = new LinkedList<ElementSelector>();
		elementSelectors1.add(RootElementSelector.getInstance());
		return new AppendableBuilderImpl(elementSelectors1);
	}

	public static NodePath withRoot()
	{
		return startBuilding().build();
	}

	public static interface AppendableBuilder
	{
		AppendableBuilder element(ElementSelector elementSelector);

		AppendableBuilder propertyName(String name, String... names);

		<T> AppendableBuilder collectionItem(T item);

		<K> AppendableBuilder mapKey(K key);

		NodePath build();
	}

	private static final class AppendableBuilderImpl implements AppendableBuilder
	{
		private final List<ElementSelector> elementSelectors;

		public AppendableBuilderImpl(final List<ElementSelector> elementSelectors)
		{
			Assert.notEmpty(elementSelectors, "elementSelectors");
			this.elementSelectors = new LinkedList<ElementSelector>(elementSelectors);
		}

		public AppendableBuilder element(final ElementSelector elementSelector)
		{
			Assert.notNull(elementSelector, "elementSelector");
			elementSelectors.add(elementSelector);
			return this;
		}

		public AppendableBuilder propertyName(final String name, final String... names)
		{
			elementSelectors.add(new BeanPropertyElementSelector(name));
			for (final String s : names)
			{
				elementSelectors.add(new BeanPropertyElementSelector(s));
			}
			return this;
		}

		public <T> AppendableBuilder collectionItem(final T item)
		{
			elementSelectors.add(new CollectionItemElementSelector(item));
			return this;
		}

		public <K> AppendableBuilder mapKey(final K key)
		{
			Assert.notNull(key, "key");
			elementSelectors.add(new MapKeyElementSelector(key));
			return this;
		}

		public NodePath build()
		{
			if (elementSelectors.isEmpty())
			{
				throw new IllegalStateException("A property path cannot be empty");
			}
			else if (!(elementSelectors.get(0) instanceof RootElementSelector))
			{
				throw new IllegalStateException("A property path must start with a root element");
			}
			else if (elementCount(RootElementSelector.class) > 1)
			{
				throw new IllegalStateException("A property path cannot contain multiple root elements");
			}
			return new NodePath(elementSelectors);
		}

		private int elementCount(final Class<? extends ElementSelector> type)
		{
			assert type != null : "Type must not be null";
			int count = 0;
			for (final ElementSelector elementSelector : elementSelectors)
			{
				if (type.isAssignableFrom(elementSelector.getClass()))
				{
					count++;
				}
			}
			return count;
		}
	}
} public abstract class ElementSelector
{
	public abstract String toHumanReadableString();

	/**
	 * Must be implemented in a way so that this element can be distinguished from the other ones.
	 *
	 * @param obj The object to check equality against.
	 * @return <code>true</code> is the given object equals this one, otherwise <code>false</code>.
	 */
	public abstract boolean equals(Object obj);

	/**
	 * Make sure to implement this properly. If two elements are equal, their hash code must be equal as well.
	 * However, it is absolutely okay if two unequal elements return the same hash code. A simple implementation
	 * could just return <code>0</code>.
	 *
	 * @return The hash code of this element.
	 */
	public abstract int hashCode();

	/**
	 * The string representation will only be used to print readable property paths for debug purposes.
	 *
	 * @return A string representation of this element for debug purposes.
	 */
	public final String toString()
	{
		return toHumanReadableString();
	}
} public class Assert
{
	private Assert()
	{
	}

	public static void equalTypesOrNull(final Object... objects)
	{
		final Collection<Class<?>> types = Classes.typesOf(objects);
		Class<?> previousType = null;
		for (final Class<?> type : types)
		{
			if (previousType != null && !type.equals(previousType))
			{
				throw new IllegalArgumentException("The given objects should be either null or of the same type ('" + previousType + "') = " + types);
			}
			previousType = type;
		}
	}

	public static void notNull(final Object object, final String name)
	{
		if (object == null)
		{
			throw new IllegalArgumentException("'" + name + "' must not be null");
		}
	}

	public static void notEmpty(final Collection<?> collection, final String name)
	{
		if (Collections.isEmpty(collection))
		{
			throw new IllegalArgumentException("'" + name + "' must not be null or empty");
		}
	}

	/**
	 * Same as {@link #hasText(String, String)}.
	 *
	 * @see #hasText(String, String)
	 */
	public static void notEmpty(final String text, final String name) throws IllegalArgumentException
	{
		hasText(text, name);
	}

	/**
	 * Ensures that the given <code>value</code> contains characters.
	 *
	 * @param value The value to check.
	 * @param name  The name of the variable (used for the exception message).
	 *
	 * @throws IllegalArgumentException If the given value is <code>null</code> or doesn't contain any non-whitespace
	 *                                  characters.
	 */
	public static void hasText(final String value, final String name) throws IllegalArgumentException
	{
		if (Strings.isEmpty(name)) // Yo dawg, I heard you like assertions, so I put an assertion in your assertion
		{
			throw new IllegalArgumentException("'name' must not be null or empty");
		}
		if (Strings.isEmpty(value))
		{
			throw new IllegalArgumentException("'" + name + "' must not be null or empty");
		}
	}
} public static class CircularReferenceException extends RuntimeException
{
	private static final long serialVersionUID = 1L;

	@SuppressWarnings("NonSerializableFieldInSerializableClass")
	private final NodePath nodePath;

	public CircularReferenceException(final NodePath nodePath)
	{
		this.nodePath = nodePath;
	}

	public NodePath getNodePath()
	{
		return nodePath;
	}

	@Override
	public Throwable fillInStackTrace()
	{
		return this;
	}
}
import de.danielbechler.diff.access.Accessor;
import de.danielbechler.diff.access.Instances;
import de.danielbechler.diff.access.PropertyAwareAccessor;
import de.danielbechler.diff.category.CategoryResolver;
import de.danielbechler.diff.introspection.PropertyReadException;
import de.danielbechler.diff.circular.CircularReferenceDetector;
import de.danielbechler.diff.circular.CircularReferenceDetectorFactory;
import de.danielbechler.diff.circular.CircularReferenceExceptionHandler;
import de.danielbechler.diff.filtering.IsReturnableResolver;
import de.danielbechler.diff.inclusion.IsIgnoredResolver;
import de.danielbechler.diff.introspection.PropertyAccessExceptionHandler;
import de.danielbechler.diff.introspection.PropertyAccessExceptionHandlerResolver;
import de.danielbechler.diff.node.DiffNode;
import de.danielbechler.diff.path.NodePath;
import de.danielbechler.diff.selector.ElementSelector;
import de.danielbechler.util.Assert;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import static de.danielbechler.diff.circular.CircularReferenceDetector.CircularReferenceException;
/*
 * Copyright 2014 Daniel Bechler
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package de.danielbechler.diff.differ;



/**
 * @author Daniel Bechler
 */
public class DifferDispatcher
{
	private static final Logger logger = LoggerFactory.getLogger(DifferDispatcher.class);
	private final DifferProvider differProvider;
	private final CircularReferenceDetectorFactory circularReferenceDetectorFactory;
	private final CircularReferenceExceptionHandler circularReferenceExceptionHandler;
	private final IsIgnoredResolver isIgnoredResolver;
	private final CategoryResolver categoryResolver;
	private final IsReturnableResolver isReturnableResolver;
	private final PropertyAccessExceptionHandlerResolver propertyAccessExceptionHandlerResolver;
	private static final ThreadLocal<CircularReferenceDetector> workingThreadLocal = new ThreadLocal<CircularReferenceDetector>();
	private static final ThreadLocal<CircularReferenceDetector> baseThreadLocal = new ThreadLocal<CircularReferenceDetector>();

	public DifferDispatcher(final DifferProvider differProvider,
							final CircularReferenceDetectorFactory circularReferenceDetectorFactory,
							final CircularReferenceExceptionHandler circularReferenceExceptionHandler,
							final IsIgnoredResolver ignoredResolver,
							final IsReturnableResolver returnableResolver,
							final PropertyAccessExceptionHandlerResolver propertyAccessExceptionHandlerResolver,
							final CategoryResolver categoryResolver)
	{
		Assert.notNull(differProvider, "differFactory");
		this.differProvider = differProvider;

		Assert.notNull(ignoredResolver, "ignoredResolver");
		this.isIgnoredResolver = ignoredResolver;

		Assert.notNull(categoryResolver, "categoryResolver");
		this.categoryResolver = categoryResolver;

		this.circularReferenceDetectorFactory = circularReferenceDetectorFactory;
		this.circularReferenceExceptionHandler = circularReferenceExceptionHandler;
		this.isReturnableResolver = returnableResolver;
		this.propertyAccessExceptionHandlerResolver = propertyAccessExceptionHandlerResolver;

		resetInstanceMemory();
	}

	public final void resetInstanceMemory()
	{
		workingThreadLocal.set(circularReferenceDetectorFactory.createCircularReferenceDetector());
		baseThreadLocal.set(circularReferenceDetectorFactory.createCircularReferenceDetector());
	}

	public final void clearInstanceMemory()
	{
		workingThreadLocal.remove();
		baseThreadLocal.remove();
	}

	/**
	 * Delegates the call to an appropriate {@link Differ}.
	 *
	 * @return A node representing the difference between the given {@link Instances}.
	 */
	public DiffNode dispatch(final DiffNode parentNode,
							 final Instances parentInstances,