org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/text/java/ContentAssistHistory.java - jdt/eclipse.jdt.ui - Git at Google

 /*******************************************************************************
  * Copyright (c) 2005, 2006 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.jdt.internal.ui.text.java;

 import java.io.IOException;
 import java.io.StringReader;
 import java.io.StringWriter;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.Map.Entry;

 import javax.xml.parsers.DocumentBuilder;
 import javax.xml.parsers.DocumentBuilderFactory;
 import javax.xml.parsers.ParserConfigurationException;
 import javax.xml.transform.OutputKeys;
 import javax.xml.transform.Transformer;
 import javax.xml.transform.TransformerException;
 import javax.xml.transform.TransformerFactory;
 import javax.xml.transform.dom.DOMSource;
 import javax.xml.transform.stream.StreamResult;

 import org.eclipse.core.runtime.CoreException;
 import org.eclipse.core.runtime.IProgressMonitor;
 import org.eclipse.core.runtime.IStatus;
 import org.eclipse.core.runtime.NullProgressMonitor;
 import org.eclipse.core.runtime.Preferences;

 import org.eclipse.jface.text.Assert;

 import org.eclipse.jdt.core.Flags;
 import org.eclipse.jdt.core.IType;
 import org.eclipse.jdt.core.ITypeHierarchy;
 import org.eclipse.jdt.core.JavaModelException;

 import org.eclipse.jdt.internal.ui.JavaPlugin;
 import org.eclipse.jdt.internal.ui.JavaUIException;
 import org.eclipse.jdt.internal.ui.JavaUIStatus;

 import org.w3c.dom.Document;
 import org.w3c.dom.Element;
 import org.w3c.dom.Node;
 import org.w3c.dom.NodeList;
 import org.xml.sax.InputSource;
 import org.xml.sax.SAXException;

 /**
  * An LRU cache for code assist.
  *
  * @since 3.2
  */
 public final class ContentAssistHistory {
 	/**
 	 * Persistence implementation.
 	 *
 	 * @since 3.2
 	 */
 	private static final class ReaderWriter {

 		private static final String NODE_ROOT= "history"; //$NON-NLS-1$
 		private static final String NODE_LHS= "lhs"; //$NON-NLS-1$
 		private static final String NODE_RHS= "rhs"; //$NON-NLS-1$
 		private static final String ATTRIBUTE_NAME= "name"; //$NON-NLS-1$
 		private static final String ATTRIBUTE_MAX_LHS= "maxLHS"; //$NON-NLS-1$
 		private static final String ATTRIBUTE_MAX_RHS= "maxRHS"; //$NON-NLS-1$

 		public void store(ContentAssistHistory history, StreamResult result) throws CoreException {
 			try {
 				DocumentBuilderFactory factory= DocumentBuilderFactory.newInstance();
 				DocumentBuilder builder= factory.newDocumentBuilder();
 				Document document= builder.newDocument();

 				Element rootElement = document.createElement(NODE_ROOT);
 				rootElement.setAttribute(ATTRIBUTE_MAX_LHS, Integer.toString(history.fMaxLHS));
 				rootElement.setAttribute(ATTRIBUTE_MAX_RHS, Integer.toString(history.fMaxRHS));
 				document.appendChild(rootElement);

 				for (Iterator leftHandSides= history.fLHSCache.keySet().iterator(); leftHandSides.hasNext();) {
 					String lhs= (String) leftHandSides.next();
 					Element lhsElement= document.createElement(NODE_LHS);
 					lhsElement.setAttribute(ATTRIBUTE_NAME, lhs);
 					rootElement.appendChild(lhsElement);

 					Set rightHandSides= (Set) history.fLHSCache.get(lhs);
 					for (Iterator rhsIterator= rightHandSides.iterator(); rhsIterator.hasNext();) {
 						String rhs= (String) rhsIterator.next();
 						Element rhsElement= document.createElement(NODE_RHS);
 						rhsElement.setAttribute(ATTRIBUTE_NAME, rhs);
 						lhsElement.appendChild(rhsElement);
 					}
 				}

 				Transformer transformer=TransformerFactory.newInstance().newTransformer();
 				transformer.setOutputProperty(OutputKeys.METHOD, "xml"); //$NON-NLS-1$
 				transformer.setOutputProperty(OutputKeys.ENCODING, "UTF-8"); //$NON-NLS-1$
 				transformer.setOutputProperty(OutputKeys.INDENT, "no"); //$NON-NLS-1$
 				DOMSource source = new DOMSource(document);

 				transformer.transform(source, result);
 			} catch (TransformerException e) {
 				throw createException(e, JavaTextMessages.ContentAssistHistory_serialize_error);
 			} catch (ParserConfigurationException e) {
 				throw createException(e, JavaTextMessages.ContentAssistHistory_serialize_error);
 			}
 		}

 		public ContentAssistHistory load(InputSource source) throws CoreException {
 			Element root;
 			try {
 				DocumentBuilder parser = DocumentBuilderFactory.newInstance().newDocumentBuilder();
 				root = parser.parse(source).getDocumentElement();
 			} catch (SAXException e) {
 				throw createException(e, JavaTextMessages.ContentAssistHistory_deserialize_error);
 			} catch (ParserConfigurationException e) {
 				throw createException(e, JavaTextMessages.ContentAssistHistory_deserialize_error);
 			} catch (IOException e) {
 				throw createException(e, JavaTextMessages.ContentAssistHistory_deserialize_error);
 			}

 			if (root == null || !root.getNodeName().equalsIgnoreCase(NODE_ROOT))
 				return null;

 			int maxLHS= parseNaturalInt(root.getAttribute(ATTRIBUTE_MAX_LHS), DEFAULT_TRACKED_LHS);
 			int maxRHS= parseNaturalInt(root.getAttribute(ATTRIBUTE_MAX_RHS), DEFAULT_TRACKED_RHS);

 			ContentAssistHistory history= new ContentAssistHistory(maxLHS, maxRHS);

 			NodeList list= root.getChildNodes();
 			int length= list.getLength();
 			for (int i= 0; i < length; ++i) {
 				Node lhsNode= list.item(i);
 				if (lhsNode.getNodeType() == Node.ELEMENT_NODE) {
 					Element lhsElement= (Element) lhsNode;
 					if (lhsElement.getNodeName().equalsIgnoreCase(NODE_LHS)) {
 						String lhs= lhsElement.getAttribute(ATTRIBUTE_NAME);
 						if (lhs != null) {
 							Set cache= history.getCache(lhs);
 							NodeList children= lhsElement.getChildNodes();
 							int nRHS= children.getLength();
 							for (int j= 0; j < nRHS; j++) {
 								Node rhsNode= children.item(j);
 								if (rhsNode.getNodeType() == Node.ELEMENT_NODE) {
 									Element rhsElement= (Element) rhsNode;
 									if (rhsElement.getNodeName().equalsIgnoreCase(NODE_RHS)) {
 										String rhs= rhsElement.getAttribute(ATTRIBUTE_NAME);
 										if (rhs != null) {
 											cache.add(rhs);
 										}
 									}
 								}
 							}
 						}
 					}
 				}
 			}

 			return history;
 		}

 		private int parseNaturalInt(String attribute, int defaultValue) {
 			try {
 				int integer= Integer.parseInt(attribute);
 				if (integer > 0)
 					return integer;
 				return defaultValue;
 			} catch (NumberFormatException e) {
 				return defaultValue;
 			}
 		}

 		private JavaUIException createException(Exception e, String message) {
 			return new JavaUIException(JavaUIStatus.createError(IStatus.ERROR, message, e));
 		}
 	}

 	/**
 	 * Most recently used variant with capped size that only counts
 	 * {@linkplain #put(Object, Object) put} as access. This is implemented by always removing an
 	 * element before it gets put back.
 	 *
 	 * @since 3.2
 	 */
 	private static final class MRUMap extends LinkedHashMap {
 		private static final long serialVersionUID= 1L;
 		private final int fMaxSize;

 		/**
 		 * Creates a new <code>MRUMap</code> with the given size.
 		 *
 		 * @param maxSize the maximum size of the cache, must be &gt; 0
 		 */
 		public MRUMap(int maxSize) {
 			Assert.isLegal(maxSize > 0);
 			fMaxSize= maxSize;
 		}

 		/*
 		 * @see java.util.HashMap#put(java.lang.Object, java.lang.Object)
 		 */
 		public Object put(Object key, Object value) {
 			Object object= remove(key);
 			super.put(key, value);
 			return object;
 		}

 		/*
 		 * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry)
 		 */
 		protected boolean removeEldestEntry(Entry eldest) {
 			return size() > fMaxSize;
 		}
 	}

 	/**
 	 * Most recently used variant with capped size that orders the elements by addition.
 	 * This is implemented by always removing an element before it gets added back.
 	 *
 	 * @since 3.2
 	 */
 	private static final class MRUSet extends LinkedHashSet {
 		private static final long serialVersionUID= 1L;
 		private final int fMaxSize;

 		/**
 		 * Creates a new <code>MRUSet</code> with the given size.
 		 *
 		 * @param maxSize the maximum size of the cache, must be &gt; 0
 		 */
 		public MRUSet(int maxSize) {
 			Assert.isLegal(maxSize > 0);
 			fMaxSize= maxSize;
 		}

 		/*
 		 * @see java.util.HashSet#add(java.lang.Object)
 		 */
 		public boolean add(Object o) {
 			if (remove(o)) {
 				super.add(o);
 				return false;
 			}

 			if (size() >= fMaxSize)
 				remove(this.iterator().next());

 			super.add(o);
 			return true;
 		}
 	}

 	/**
 	 * A ranking of the most recently selected types.
 	 *
 	 * @since 3.2
 	 */
 	public static final class RHSHistory {
 		private final LinkedHashMap fHistory;
 		private List fList;

 		RHSHistory(LinkedHashMap history) {
 			fHistory= history;
 		}

 		/**
 		 * Returns the rank of a type in the history in [0.0,&nbsp;1.0]. The rank of the most
 		 * recently selected type is 1.0, the rank of any type that is not remembered is zero.
 		 *
 		 * @param type the fully qualified type name to get the rank for
 		 * @return the rank of <code>type</code>
 		 */
 		public float getRank(String type) {
 			if (fHistory == null)
 				return 0.0F;
 			Integer integer= (Integer) fHistory.get(type);
 			return integer == null ? 0.0F : integer.floatValue() / fHistory.size();
 		}

 		/**
 		 * Returns the size of the history.
 		 *
 		 * @return the size of the history
 		 */
 		public int size() {
 			return fHistory == null ? 0 : fHistory.size();
 		}

 		/**
 		 * Returns the list of remembered types ordered by recency. The first element is the
 		 * <i>least</i>, the last element the <i>most</i> recently remembered type.
 		 *
 		 * @return the list of remembered types as fully qualified type names (element type:
 		 *         {@link String})
 		 */
 		public List getTypes() {
 			if (fHistory == null)
 				return Collections.EMPTY_LIST;
 			if (fList == null) {
 				fList= Collections.unmodifiableList(new ArrayList(fHistory.keySet()));
 			}
 			return fList;
 		}
 	}

 	private static final RHSHistory EMPTY_HISTORY= new RHSHistory(null);
 	private static final int DEFAULT_TRACKED_LHS= 100;
 	private static final int DEFAULT_TRACKED_RHS= 10;

 	private static final Set UNCACHEABLE;
 	static {
 		Set uncacheable= new HashSet();
 		uncacheable.add("java.lang.Object"); //$NON-NLS-1$
 		uncacheable.add("java.lang.Comparable"); //$NON-NLS-1$
 		uncacheable.add("java.io.Serializable"); //$NON-NLS-1$
 		uncacheable.add("java.io.Externalizable"); //$NON-NLS-1$
 		UNCACHEABLE= Collections.unmodifiableSet(uncacheable);
 	}

 	private final LinkedHashMap/*<IType, MRUSet<IType>>*/ fLHSCache;
 	private final int fMaxLHS;
 	private final int fMaxRHS;

 	/**
 	 * Creates a new history.
 	 *
 	 * @param maxLHS the maximum number of tracked left hand sides (&gt; 0)
 	 * @param maxRHS the maximum number of tracked right hand sides per left hand side(&gt; 0)
 	 */
 	public ContentAssistHistory(int maxLHS, int maxRHS) {
 		Assert.isLegal(maxLHS > 0);
 		Assert.isLegal(maxRHS > 0);
 		fMaxLHS= maxLHS;
 		fMaxRHS= maxRHS;
 		fLHSCache= new MRUMap(fMaxLHS);
 	}

 	/**
 	 * Creates a new history, equivalent to
 	 * <code>ContentAssistHistory({@value #DEFAULT_TRACKED_LHS}, {@value #DEFAULT_TRACKED_RHS})</code>.
 	 */
 	public ContentAssistHistory() {
 		this(DEFAULT_TRACKED_LHS, DEFAULT_TRACKED_RHS);
 	}

 	/**
 	 * Remembers the selection of a right hand side type (proposal type) for a certain left hand side (expected
 	 * type) in content assist.
 	 *
 	 * @param lhs the left hand side / expected type
 	 * @param rhs the selected right hand side
 	 */
 	public void remember(IType lhs, IType rhs) {
 		Assert.isLegal(lhs != null);
 		Assert.isLegal(rhs != null);

 		try {
 			if (!isCacheableRHS(rhs))
 				return;
 			ITypeHierarchy hierarchy= rhs.newSupertypeHierarchy(getProgressMonitor());
 			if (hierarchy.contains(lhs)) {
 				// TODO remember for every member of the LHS hierarchy or not? Yes for now.
 				IType[] allLHSides= hierarchy.getAllSupertypes(lhs);
 				for (int i= 0; i < allLHSides.length; i++)
 					rememberInternal(allLHSides[i], rhs);
 				rememberInternal(lhs, rhs);
 			}
 		} catch (JavaModelException x) {
 			JavaPlugin.log(x);
 		}
 	}

 	/**
 	 * Returns the {@link RHSHistory history} of the types that have been selected most recently as
 	 * right hand sides for the given type.
 	 *
 	 * @param lhs the fully qualified type name of an expected type for which right hand sides are
 	 *        requested, or <code>null</code>
 	 * @return the right hand side history for the given type
 	 */
 	public RHSHistory getHistory(String lhs) {
 		MRUSet rhsCache= (MRUSet) fLHSCache.get(lhs);
 		if (rhsCache != null) {
 			int count= rhsCache.size();
 			LinkedHashMap history= new LinkedHashMap((int) (count / 0.75));
 			int rank= 1;
 			for (Iterator it= rhsCache.iterator(); it.hasNext(); rank++) {
 				String type= (String) it.next();
 				history.put(type, new Integer(rank));
 			}
 			return new RHSHistory(history);
 		}
 		return EMPTY_HISTORY;
 	}

 	/**
 	 * Returns a read-only map from {@link IType} to {@link RHSHistory}, where each value is the
 	 * history for the key type (see {@link #getHistory(String)}.
 	 *
 	 * @return the set of remembered right hand sides ordered by least recent selection
 	 */
 	public Map getEntireHistory() {
 		HashMap map= new HashMap((int) (fLHSCache.size() / 0.75));
 		for (Iterator it= fLHSCache.entrySet().iterator(); it.hasNext();) {
 			Entry entry= (Entry) it.next();
 			String lhs= (String) entry.getKey();
 			map.put(lhs, getHistory(lhs));
 		}
 		return Collections.unmodifiableMap(map);
 	}

 	private void rememberInternal(IType lhs, IType rhs) throws JavaModelException {
 		if (isCacheableLHS(lhs))
 			getCache(lhs.getFullyQualifiedName()).add(rhs.getFullyQualifiedName());
 	}

 	private boolean isCacheableLHS(IType type) throws JavaModelException {
 		return !Flags.isFinal(type.getFlags()) && !UNCACHEABLE.contains(type.getFullyQualifiedName());
 	}

 	private boolean isCacheableRHS(IType type) throws JavaModelException {
 		return !type.isInterface() && !Flags.isAbstract(type.getFlags());
 	}

 	private Set getCache(String lhs) {
 		MRUSet rhsCache= (MRUSet) fLHSCache.get(lhs);
 		if (rhsCache == null) {
 			rhsCache= new MRUSet(fMaxRHS);
 			fLHSCache.put(lhs, rhsCache);
 		}

 		return rhsCache;
 	}

 	private IProgressMonitor getProgressMonitor() {
 		return new NullProgressMonitor();
 	}

 	/**
 	 * Stores the history as XML document into the given preferences.
 	 *
 	 * @param history the history to store
 	 * @param preferences the preferences to store the history into
 	 * @param key the key under which to store the history
 	 * @throws CoreException if serialization fails
 	 * @see #load(Preferences, String) on how to restore a history stored by this method
 	 */
 	public static void store(ContentAssistHistory history, Preferences preferences, String key) throws CoreException {
 		StringWriter writer= new StringWriter();
 		new ReaderWriter().store(history, new StreamResult(writer));
 		preferences.setValue(key, writer.toString());
 	}

 	/**
 	 * Loads a history from an XML encoded preference value.
 	 *
 	 * @param preferences the preferences to retrieve the history from
 	 * @param key the key under which the history is stored
 	 * @return the deserialized history, or <code>null</code> if there is nothing stored under the
 	 *         given key
 	 * @throws CoreException if deserialization fails
 	 * @see #store(ContentAssistHistory, Preferences, String) on how to store a history such that it
 	 *      can be read by this method
 	 */
 	public static ContentAssistHistory load(Preferences preferences, String key) throws CoreException {
 		String value= preferences.getString(key);
 		if (value != null && value.length() > 0) {
 			return new ReaderWriter().load(new InputSource(new StringReader(value)));
 		}
 		return null;
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2005, 2006 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.jdt.internal.ui.text.java;

	import java.io.IOException;
	import java.io.StringReader;
	import java.io.StringWriter;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.LinkedHashMap;
	import java.util.LinkedHashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	import java.util.Map.Entry;

	import javax.xml.parsers.DocumentBuilder;
	import javax.xml.parsers.DocumentBuilderFactory;
	import javax.xml.parsers.ParserConfigurationException;
	import javax.xml.transform.OutputKeys;
	import javax.xml.transform.Transformer;
	import javax.xml.transform.TransformerException;
	import javax.xml.transform.TransformerFactory;
	import javax.xml.transform.dom.DOMSource;
	import javax.xml.transform.stream.StreamResult;

	import org.eclipse.core.runtime.CoreException;
	import org.eclipse.core.runtime.IProgressMonitor;
	import org.eclipse.core.runtime.IStatus;
	import org.eclipse.core.runtime.NullProgressMonitor;
	import org.eclipse.core.runtime.Preferences;

	import org.eclipse.jface.text.Assert;

	import org.eclipse.jdt.core.Flags;
	import org.eclipse.jdt.core.IType;
	import org.eclipse.jdt.core.ITypeHierarchy;
	import org.eclipse.jdt.core.JavaModelException;

	import org.eclipse.jdt.internal.ui.JavaPlugin;
	import org.eclipse.jdt.internal.ui.JavaUIException;
	import org.eclipse.jdt.internal.ui.JavaUIStatus;

	import org.w3c.dom.Document;
	import org.w3c.dom.Element;
	import org.w3c.dom.Node;
	import org.w3c.dom.NodeList;
	import org.xml.sax.InputSource;
	import org.xml.sax.SAXException;

	/**
	* An LRU cache for code assist.
	*
	* @since 3.2
	*/
	public final class ContentAssistHistory {
	/**
	* Persistence implementation.
	*
	* @since 3.2
	*/
	private static final class ReaderWriter {

	private static final String NODE_ROOT= "history"; //$NON-NLS-1$
	private static final String NODE_LHS= "lhs"; //$NON-NLS-1$
	private static final String NODE_RHS= "rhs"; //$NON-NLS-1$
	private static final String ATTRIBUTE_NAME= "name"; //$NON-NLS-1$
	private static final String ATTRIBUTE_MAX_LHS= "maxLHS"; //$NON-NLS-1$
	private static final String ATTRIBUTE_MAX_RHS= "maxRHS"; //$NON-NLS-1$

	public void store(ContentAssistHistory history, StreamResult result) throws CoreException {
	try {
	DocumentBuilderFactory factory= DocumentBuilderFactory.newInstance();
	DocumentBuilder builder= factory.newDocumentBuilder();
	Document document= builder.newDocument();

	Element rootElement = document.createElement(NODE_ROOT);
	rootElement.setAttribute(ATTRIBUTE_MAX_LHS, Integer.toString(history.fMaxLHS));
	rootElement.setAttribute(ATTRIBUTE_MAX_RHS, Integer.toString(history.fMaxRHS));
	document.appendChild(rootElement);

	for (Iterator leftHandSides= history.fLHSCache.keySet().iterator(); leftHandSides.hasNext();) {
	String lhs= (String) leftHandSides.next();
	Element lhsElement= document.createElement(NODE_LHS);
	lhsElement.setAttribute(ATTRIBUTE_NAME, lhs);
	rootElement.appendChild(lhsElement);

	Set rightHandSides= (Set) history.fLHSCache.get(lhs);
	for (Iterator rhsIterator= rightHandSides.iterator(); rhsIterator.hasNext();) {
	String rhs= (String) rhsIterator.next();
	Element rhsElement= document.createElement(NODE_RHS);
	rhsElement.setAttribute(ATTRIBUTE_NAME, rhs);
	lhsElement.appendChild(rhsElement);
	}
	}

	Transformer transformer=TransformerFactory.newInstance().newTransformer();
	transformer.setOutputProperty(OutputKeys.METHOD, "xml"); //$NON-NLS-1$
	transformer.setOutputProperty(OutputKeys.ENCODING, "UTF-8"); //$NON-NLS-1$
	transformer.setOutputProperty(OutputKeys.INDENT, "no"); //$NON-NLS-1$
	DOMSource source = new DOMSource(document);

	transformer.transform(source, result);
	} catch (TransformerException e) {
	throw createException(e, JavaTextMessages.ContentAssistHistory_serialize_error);
	} catch (ParserConfigurationException e) {
	throw createException(e, JavaTextMessages.ContentAssistHistory_serialize_error);
	}
	}

	public ContentAssistHistory load(InputSource source) throws CoreException {
	Element root;
	try {
	DocumentBuilder parser = DocumentBuilderFactory.newInstance().newDocumentBuilder();
	root = parser.parse(source).getDocumentElement();
	} catch (SAXException e) {
	throw createException(e, JavaTextMessages.ContentAssistHistory_deserialize_error);
	} catch (ParserConfigurationException e) {
	throw createException(e, JavaTextMessages.ContentAssistHistory_deserialize_error);
	} catch (IOException e) {
	throw createException(e, JavaTextMessages.ContentAssistHistory_deserialize_error);
	}

	if (root == null \|\| !root.getNodeName().equalsIgnoreCase(NODE_ROOT))
	return null;

	int maxLHS= parseNaturalInt(root.getAttribute(ATTRIBUTE_MAX_LHS), DEFAULT_TRACKED_LHS);
	int maxRHS= parseNaturalInt(root.getAttribute(ATTRIBUTE_MAX_RHS), DEFAULT_TRACKED_RHS);

	ContentAssistHistory history= new ContentAssistHistory(maxLHS, maxRHS);

	NodeList list= root.getChildNodes();
	int length= list.getLength();
	for (int i= 0; i < length; ++i) {
	Node lhsNode= list.item(i);
	if (lhsNode.getNodeType() == Node.ELEMENT_NODE) {
	Element lhsElement= (Element) lhsNode;
	if (lhsElement.getNodeName().equalsIgnoreCase(NODE_LHS)) {
	String lhs= lhsElement.getAttribute(ATTRIBUTE_NAME);
	if (lhs != null) {
	Set cache= history.getCache(lhs);
	NodeList children= lhsElement.getChildNodes();
	int nRHS= children.getLength();
	for (int j= 0; j < nRHS; j++) {
	Node rhsNode= children.item(j);
	if (rhsNode.getNodeType() == Node.ELEMENT_NODE) {
	Element rhsElement= (Element) rhsNode;
	if (rhsElement.getNodeName().equalsIgnoreCase(NODE_RHS)) {
	String rhs= rhsElement.getAttribute(ATTRIBUTE_NAME);
	if (rhs != null) {
	cache.add(rhs);
	}
	}
	}
	}
	}
	}
	}
	}

	return history;
	}

	private int parseNaturalInt(String attribute, int defaultValue) {
	try {
	int integer= Integer.parseInt(attribute);
	if (integer > 0)
	return integer;
	return defaultValue;
	} catch (NumberFormatException e) {
	return defaultValue;
	}
	}

	private JavaUIException createException(Exception e, String message) {
	return new JavaUIException(JavaUIStatus.createError(IStatus.ERROR, message, e));
	}
	}

	/**
	* Most recently used variant with capped size that only counts
	* {@linkplain #put(Object, Object) put} as access. This is implemented by always removing an
	* element before it gets put back.
	*
	* @since 3.2
	*/
	private static final class MRUMap extends LinkedHashMap {
	private static final long serialVersionUID= 1L;
	private final int fMaxSize;

	/**
	* Creates a new <code>MRUMap</code> with the given size.
	*
	* @param maxSize the maximum size of the cache, must be > 0
	*/
	public MRUMap(int maxSize) {
	Assert.isLegal(maxSize > 0);
	fMaxSize= maxSize;
	}

	/*
	* @see java.util.HashMap#put(java.lang.Object, java.lang.Object)
	*/
	public Object put(Object key, Object value) {
	Object object= remove(key);
	super.put(key, value);
	return object;
	}

	/*
	* @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry)
	*/
	protected boolean removeEldestEntry(Entry eldest) {
	return size() > fMaxSize;
	}
	}

	/**
	* Most recently used variant with capped size that orders the elements by addition.
	* This is implemented by always removing an element before it gets added back.
	*
	* @since 3.2
	*/
	private static final class MRUSet extends LinkedHashSet {
	private static final long serialVersionUID= 1L;
	private final int fMaxSize;

	/**
	* Creates a new <code>MRUSet</code> with the given size.
	*
	* @param maxSize the maximum size of the cache, must be > 0
	*/
	public MRUSet(int maxSize) {
	Assert.isLegal(maxSize > 0);
	fMaxSize= maxSize;
	}

	/*
	* @see java.util.HashSet#add(java.lang.Object)
	*/
	public boolean add(Object o) {
	if (remove(o)) {
	super.add(o);
	return false;
	}

	if (size() >= fMaxSize)
	remove(this.iterator().next());

	super.add(o);
	return true;
	}
	}

	/**
	* A ranking of the most recently selected types.
	*
	* @since 3.2
	*/
	public static final class RHSHistory {
	private final LinkedHashMap fHistory;
	private List fList;

	RHSHistory(LinkedHashMap history) {
	fHistory= history;
	}

	/**
	* Returns the rank of a type in the history in [0.0, 1.0]. The rank of the most
	* recently selected type is 1.0, the rank of any type that is not remembered is zero.
	*
	* @param type the fully qualified type name to get the rank for
	* @return the rank of <code>type</code>
	*/
	public float getRank(String type) {
	if (fHistory == null)
	return 0.0F;
	Integer integer= (Integer) fHistory.get(type);
	return integer == null ? 0.0F : integer.floatValue() / fHistory.size();
	}

	/**
	* Returns the size of the history.
	*
	* @return the size of the history
	*/
	public int size() {
	return fHistory == null ? 0 : fHistory.size();
	}

	/**
	* Returns the list of remembered types ordered by recency. The first element is the
	* <i>least</i>, the last element the <i>most</i> recently remembered type.
	*
	* @return the list of remembered types as fully qualified type names (element type:
	* {@link String})
	*/
	public List getTypes() {
	if (fHistory == null)
	return Collections.EMPTY_LIST;
	if (fList == null) {
	fList= Collections.unmodifiableList(new ArrayList(fHistory.keySet()));
	}
	return fList;
	}
	}

	private static final RHSHistory EMPTY_HISTORY= new RHSHistory(null);
	private static final int DEFAULT_TRACKED_LHS= 100;
	private static final int DEFAULT_TRACKED_RHS= 10;

	private static final Set UNCACHEABLE;
	static {
	Set uncacheable= new HashSet();
	uncacheable.add("java.lang.Object"); //$NON-NLS-1$
	uncacheable.add("java.lang.Comparable"); //$NON-NLS-1$
	uncacheable.add("java.io.Serializable"); //$NON-NLS-1$
	uncacheable.add("java.io.Externalizable"); //$NON-NLS-1$
	UNCACHEABLE= Collections.unmodifiableSet(uncacheable);
	}

	private final LinkedHashMap/<IType, MRUSet<IType>>/ fLHSCache;
	private final int fMaxLHS;
	private final int fMaxRHS;

	/**
	* Creates a new history.
	*
	* @param maxLHS the maximum number of tracked left hand sides (> 0)
	* @param maxRHS the maximum number of tracked right hand sides per left hand side(> 0)
	*/
	public ContentAssistHistory(int maxLHS, int maxRHS) {
	Assert.isLegal(maxLHS > 0);
	Assert.isLegal(maxRHS > 0);
	fMaxLHS= maxLHS;
	fMaxRHS= maxRHS;
	fLHSCache= new MRUMap(fMaxLHS);
	}

	/**
	* Creates a new history, equivalent to
	* <code>ContentAssistHistory({@value #DEFAULT_TRACKED_LHS}, {@value #DEFAULT_TRACKED_RHS})</code>.
	*/
	public ContentAssistHistory() {
	this(DEFAULT_TRACKED_LHS, DEFAULT_TRACKED_RHS);
	}

	/**
	* Remembers the selection of a right hand side type (proposal type) for a certain left hand side (expected
	* type) in content assist.
	*
	* @param lhs the left hand side / expected type
	* @param rhs the selected right hand side
	*/
	public void remember(IType lhs, IType rhs) {
	Assert.isLegal(lhs != null);
	Assert.isLegal(rhs != null);

	try {
	if (!isCacheableRHS(rhs))
	return;
	ITypeHierarchy hierarchy= rhs.newSupertypeHierarchy(getProgressMonitor());
	if (hierarchy.contains(lhs)) {
	// TODO remember for every member of the LHS hierarchy or not? Yes for now.
	IType[] allLHSides= hierarchy.getAllSupertypes(lhs);
	for (int i= 0; i < allLHSides.length; i++)
	rememberInternal(allLHSides[i], rhs);
	rememberInternal(lhs, rhs);
	}
	} catch (JavaModelException x) {
	JavaPlugin.log(x);
	}
	}

	/**
	* Returns the {@link RHSHistory history} of the types that have been selected most recently as
	* right hand sides for the given type.
	*
	* @param lhs the fully qualified type name of an expected type for which right hand sides are
	* requested, or <code>null</code>
	* @return the right hand side history for the given type
	*/
	public RHSHistory getHistory(String lhs) {
	MRUSet rhsCache= (MRUSet) fLHSCache.get(lhs);
	if (rhsCache != null) {
	int count= rhsCache.size();
	LinkedHashMap history= new LinkedHashMap((int) (count / 0.75));
	int rank= 1;
	for (Iterator it= rhsCache.iterator(); it.hasNext(); rank++) {
	String type= (String) it.next();
	history.put(type, new Integer(rank));
	}
	return new RHSHistory(history);
	}
	return EMPTY_HISTORY;
	}

	/**
	* Returns a read-only map from {@link IType} to {@link RHSHistory}, where each value is the
	* history for the key type (see {@link #getHistory(String)}.
	*
	* @return the set of remembered right hand sides ordered by least recent selection
	*/
	public Map getEntireHistory() {
	HashMap map= new HashMap((int) (fLHSCache.size() / 0.75));
	for (Iterator it= fLHSCache.entrySet().iterator(); it.hasNext();) {
	Entry entry= (Entry) it.next();
	String lhs= (String) entry.getKey();
	map.put(lhs, getHistory(lhs));
	}
	return Collections.unmodifiableMap(map);
	}

	private void rememberInternal(IType lhs, IType rhs) throws JavaModelException {
	if (isCacheableLHS(lhs))
	getCache(lhs.getFullyQualifiedName()).add(rhs.getFullyQualifiedName());
	}

	private boolean isCacheableLHS(IType type) throws JavaModelException {
	return !Flags.isFinal(type.getFlags()) && !UNCACHEABLE.contains(type.getFullyQualifiedName());
	}

	private boolean isCacheableRHS(IType type) throws JavaModelException {
	return !type.isInterface() && !Flags.isAbstract(type.getFlags());
	}

	private Set getCache(String lhs) {
	MRUSet rhsCache= (MRUSet) fLHSCache.get(lhs);
	if (rhsCache == null) {
	rhsCache= new MRUSet(fMaxRHS);
	fLHSCache.put(lhs, rhsCache);
	}

	return rhsCache;
	}

	private IProgressMonitor getProgressMonitor() {
	return new NullProgressMonitor();
	}

	/**
	* Stores the history as XML document into the given preferences.
	*
	* @param history the history to store
	* @param preferences the preferences to store the history into
	* @param key the key under which to store the history
	* @throws CoreException if serialization fails
	* @see #load(Preferences, String) on how to restore a history stored by this method
	*/
	public static void store(ContentAssistHistory history, Preferences preferences, String key) throws CoreException {
	StringWriter writer= new StringWriter();
	new ReaderWriter().store(history, new StreamResult(writer));
	preferences.setValue(key, writer.toString());
	}

	/**
	* Loads a history from an XML encoded preference value.
	*
	* @param preferences the preferences to retrieve the history from
	* @param key the key under which the history is stored
	* @return the deserialized history, or <code>null</code> if there is nothing stored under the
	* given key
	* @throws CoreException if deserialization fails
	* @see #store(ContentAssistHistory, Preferences, String) on how to store a history such that it
	* can be read by this method
	*/
	public static ContentAssistHistory load(Preferences preferences, String key) throws CoreException {
	String value= preferences.getString(key);
	if (value != null && value.length() > 0) {
	return new ReaderWriter().load(new InputSource(new StringReader(value)));
	}
	return null;
	}
	}