command.hippieCompletion.description = Context insensitive completion

command.hippieCompletion.name = Hippie Completion

      <command

            name="%command.hippieCompletion.name"

            description="%command.hippieCompletion.description"

            categoryId="org.eclipse.ui.category.edit"

            id="org.eclipse.ui.edit.text.hippieCompletion">

      </command>

      <!-- TODO Keybinding -->

      <keyBinding

            commandId="org.eclipse.ui.edit.text.hippieCompletion"

            contextId="org.eclipse.ui.textEditorScope"

            keySequence="Alt+/"

            keyConfigurationId="org.eclipse.ui.defaultAcceleratorConfiguration">

       </keyBinding>

		action = new HippieCompleteAction(EditorMessages.getResourceBundle(), "Editor.HippieCompletion.", this); //$NON-NLS-1$

		// TODO action.setHelpContextId(IAbstractTextEditorHelpContextIds.HIPPIE_COMPLETION_ACTION);

		action.setActionDefinitionId(ITextEditorActionDefinitionIds.HIPPIE_COMPLETION);

		setAction(ITextEditorActionConstants.HIPPIE_COMPLETION, action);

	/** 

	 * Name of the action for emacs style hippie completion. 

	 * Value: <code>"HIPPIE_COMPLETION"</code>

	 * @since 3.1

	 */

	static final String HIPPIE_COMPLETION= "HIPPIE_COMPLETION"; //$NON-NLS-1$

	/**

	 * Action definition ID of the edit -> text complete action

	 * Value: <code>"org.eclipse.ui.edit.text.hippieCompletion"</code>).

	 * @since 3.1

	 */

	public static final String HIPPIE_COMPLETION= "org.eclipse.ui.edit.text.hippieCompletion"; //$NON-NLS-1$

/*******************************************************************************

 * Copyright (c) 2000, 2005 IBM Corporation and others.

 * All rights reserved. This program and the accompanying materials 

 * are made available under the terms of the Common Public License v1.0

 * which accompanies this distribution, and is available at

 * http://www.eclipse.org/legal/cpl-v10.html

 * 

 * Contributors:

 *     Genady Beryozkin, me@genady.org - initial API and implementation

 *     IBM Corporation - fixes and cleaning

 *******************************************************************************/

package org.eclipse.ui.texteditor;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.ResourceBundle;

import org.eclipse.core.runtime.IStatus;

import org.eclipse.core.runtime.Status;

import org.eclipse.jface.text.Assert;

import org.eclipse.jface.text.BadLocationException;

import org.eclipse.jface.text.DocumentEvent;

import org.eclipse.jface.text.FindReplaceDocumentAdapter;

import org.eclipse.jface.text.IDocument;

import org.eclipse.jface.text.IDocumentListener;

import org.eclipse.jface.text.IRegion;

import org.eclipse.jface.text.ITextSelection;

import org.eclipse.jface.viewers.ISelectionChangedListener;

import org.eclipse.jface.viewers.SelectionChangedEvent;

import org.eclipse.ui.IEditorInput;

import org.eclipse.ui.IEditorPart;

import org.eclipse.ui.IEditorReference;

import org.eclipse.ui.IWorkbenchWindow;

import org.eclipse.ui.internal.texteditor.TextEditorPlugin;

/**

 * This class implements the emacs style completion action.

 * Completion action is a stateful action, as the user may invoke

 * it several times in a row in order to scroll the possible completions.

 * 

 * TODO: Sort by editor type

 * TODO: Provide history option

 * 

 * @since 3.1

 * @author Genady Beryozkin, me@genady.org

 */

public class HippieCompleteAction extends TextEditorAction {

	/**

	 * Regular expression that is used to find words.

	 */

	// unicode identifier part

//	private static final String COMPLETION_WORD_REGEX= "[\\p{L}[\\p{Mn}[\\p{Pc}[\\p{Nd}[\\p{Nl}]]]]]+"; //$NON-NLS-1$

	// java identifier part (unicode id part + currency symbols)

	private static final String COMPLETION_WORD_REGEX= "[\\p{L}[\\p{Mn}[\\p{Pc}[\\p{Nd}[\\p{Nl}[\\p{Sc}]]]]]]+"; //$NON-NLS-1$

	// with a 1.5 JRE, you can do this:

//	private static final String COMPLETION_WORD_REGEX= "\\p{javaUnicodeIdentifierPart}+"; //$NON-NLS-1$

//	private static final String COMPLETION_WORD_REGEX= "\\p{javaJavaIdentifierPart}+"; //$NON-NLS-1$

	/**

	 * Is completion case sensitive? Even if set to <code>false</code>, the case of the prefix

	 * won't be changed.

	 */

	private static final boolean CASE_SENSITIVE= true;

	/**

     * The document that will be manipulated

	 */

	private IDocument fDocument;

	/** 

	 * The completion state that is used to continue the iteration over suggestions

	 */

	private CompletionState fLastCompletion= null;

	/**

	 * Modification lock that will prevent invalidation of the completion state when the

	 * completion action modifies the document

	 */

	private boolean fModifyingLock= false;

	SelectionChangeListener fSelectionListener;

	DocumentChangeListener fDocumentListener;

	/*

	 * @see org.eclipse.ui.texteditor.TextEditorAction#setEditor(org.eclipse.ui.texteditor.ITextEditor)

	 */

	public void setEditor(ITextEditor editor) {

		clearState(); // make sure to remove listers before the editor changes!

		super.setEditor(editor);

	}

	/**

	 * This class accompanies the {@link HippieCompleteAction#updateState()} method

	 * to invalidate completion state when the selection changes.

	 */

	class SelectionChangeListener implements ISelectionChangedListener {

		public void selectionChanged(SelectionChangedEvent event) {

			if (!fModifyingLock) {

				clearState();

			}

		}

	}

	/**

	 * Invalidate the completion state when the document contents changes not

	 * as the result of the completion action itself. This is needed since

	 * the {@link HippieCompleteAction#update()} method is only called when the

	 * {@link HippieCompleteAction#fModifyingLock} is already false.

	 */

	class DocumentChangeListener implements IDocumentListener {

		public void documentAboutToBeChanged(DocumentEvent event) {

		}

		public void documentChanged(DocumentEvent event) {

			if (!fModifyingLock) {

				clearState();

			}

		}

	}

	/**

	 * Perform the next completion.

	 */

	private void completeNext() {

		// we don't wish to receive events on our own changes

		fModifyingLock= true;

		try {

			try {

				fDocument.replace(fLastCompletion.startOffset, fLastCompletion.length, fLastCompletion.suggestions[fLastCompletion.nextSuggestion]);

			} catch (BadLocationException e) {

				// we should never get here. different from other places to notify the user.

				log(e);

				clearState();

				return;

			}

			// advance the suggestion state

			fLastCompletion.advance();

			// move the caret to the insertion point

			((AbstractTextEditor) getTextEditor()).getSourceViewer().setSelectedRange(fLastCompletion.startOffset + fLastCompletion.length, 0);

		} finally {

			// allow changes

			fModifyingLock= false;

		}

	}	

	/**

	 * This class represents the state of the last completion process. Each time

	 * the user moves to a new position and calls this action an instance of

	 * this inner class is created and saved in {@link #fLastCompletion}.

	 */

	private static class CompletionState {

		/** The list of suggestions that was computed when the completion

		 * action was first invoked 

		 */

		final String[] suggestions;

		/** The caret position at which we insert the suggestions */

		final int startOffset;

		/** The length of the last suggestion string */

		int length;

		/** The index of next suggestion (index into the suggestion array) */

		int nextSuggestion;

		CompletionState(String[] suggestions, int startOffset) {

			this.suggestions= suggestions;

			this.startOffset= startOffset;

			length= 0;

			nextSuggestion= 0;

		}

		public void advance() {

			length= suggestions[nextSuggestion].length();

			nextSuggestion= (nextSuggestion + 1) % suggestions.length;	

		}

	}

	/**

	 * @param bundle the resource bundle

	 * @param prefix a prefix to be prepended to the various resource keys

	 *        (described in <code>ResourceAction</code> constructor), or

	 *        <code>null</code> if none

	 * @param editor the text editor

	 */

	protected HippieCompleteAction(ResourceBundle bundle, String prefix, ITextEditor editor) {

		super(bundle, prefix, editor);

	}

	/**

	 * Invalidates the cached completions, removes all registered listeners and

	 * sets the cached document to <code>null</code>.

	 */

	private void clearState() {

		fLastCompletion= null;

		ITextEditor editor= getTextEditor();

		if (editor != null && fSelectionListener != null)

			editor.getSelectionProvider().removeSelectionChangedListener(fSelectionListener);

		if (fDocument != null && fDocumentListener != null)

			fDocument.removeDocumentListener(fDocumentListener);

		fDocument= null;

	}

	/*

	 * @see org.eclipse.jface.action.Action#run()

	 */

	public void run() {

		if (!isStateValid())

			updateState();

		if (isStateValid())

			completeNext();

	}

	/**

	 * Update the completion state. The completion cache is updated with the

	 * completions based on the currently displayed document and the current

	 * selection. To track the validity of the cached state, listeners are

	 * registered with the editor and document, and the current document is

	 * cached.

	 */

	private void updateState() {

		Assert.isNotNull(getTextEditor());

		clearState();

		IDocument document= getCurrentDocument();

		if (document != null) {

			fDocument= document;

			String[] suggestions;

			try {

				String prefix= getCurrentPrefix();

				if (prefix == null) {

					notifyUser();

					return;

				}

				suggestions= getSuggestions(prefix);

			} catch (BadLocationException e) {

				log(e);

				return;

			}

			// if it is single empty suggestion

			if (suggestions.length == 1) {

				notifyUser();

				return;

			}

			installListeners();

			fLastCompletion= new CompletionState(suggestions, getSelectionOffset());

		}

	}

	/**

	 * Returns <code>true</code> if the current completion state is still

	 * valid given the current document and selection.

	 * 

	 * @return <code>true</code> if the cached state is valid,

	 *         <code>false</code> otherwise

	 */

	private boolean isStateValid() {

		return fDocument != null 

				&& fDocument.equals(getCurrentDocument()) 

				&& fLastCompletion != null 

				&& fLastCompletion.startOffset + fLastCompletion.length == getSelectionOffset();

	}

	/**

	 * Returns the document currently displayed in the editor, or

	 * <code>null</code>

	 * 

	 * @return the document currently displayed in the editor, or

	 *         <code>null</code>

	 */

	private IDocument getCurrentDocument() {

		ITextEditor editor= getTextEditor();

		if (editor == null)

			return null;

		IDocumentProvider provider= editor.getDocumentProvider();

		if (provider == null)

			return null;

		IDocument document= provider.getDocument(editor.getEditorInput());

		return document;

	}

	/**

	 * Returns the current selection (or caret) offset.

	 * 

	 * @return the current selection (or caret) offset

	 */

	private int getSelectionOffset() {

		return ((ITextSelection) getTextEditor().getSelectionProvider().getSelection()).getOffset();

	}

	/**

	 * Installs the selection and document listeners. Both editor and cached

	 * document must be valid.

	 */

	private void installListeners() {

		ITextEditor editor= getTextEditor();

		Assert.isNotNull(editor);

		Assert.isNotNull(fDocument);

		if (fSelectionListener == null)

			fSelectionListener= new SelectionChangeListener();

		editor.getSelectionProvider().addSelectionChangedListener(fSelectionListener);

		if (fDocumentListener == null)

			fDocumentListener= new DocumentChangeListener();

		fDocument.addDocumentListener(fDocumentListener);

	}

	/**

	 * Notifies the user that there are no suggestions.

	 */

	private void notifyUser() {

		// TODO notify via status line?

		getTextEditor().getSite().getShell().getDisplay().beep();

	}

	/**

	 * Create the array of suggestions. It scans all open text editors and

	 * prefers suggestions from the currently open editor. It also adds the

	 * empty suggestion at the end.

	 * @param prefix the prefix to search for

	 * @return the list of all possible suggestions in the currently open editors

	 * @throws BadLocationException if accessing the current document fails

	 */

	public String[] getSuggestions(String prefix) throws BadLocationException {

		IWorkbenchWindow window= getTextEditor().getSite().getWorkbenchWindow();

		IEditorReference editorsArray[]= window.getActivePage().getEditorReferences();

		ArrayList documentsVector= new ArrayList();

		for (int i= 0; i < editorsArray.length; i++) {

			IEditorPart realEditor= editorsArray[i].getEditor(false);

			if (realEditor instanceof ITextEditor) {

				ITextEditor textEditor= (ITextEditor)realEditor;

				IEditorInput input= textEditor.getEditorInput();

				IDocument doc= textEditor.getDocumentProvider().getDocument(input);

				documentsVector.add(doc);

			}

		}

		documentsVector.remove(fDocument);

		ArrayList suggestions= createSuggestionsFromOpenDocument(prefix);

		suggestions.addAll(createSuggestions(prefix, documentsVector));

		// add the empty suggestion

		suggestions.add(""); //$NON-NLS-1$

		ArrayList uniqueSuggestions= getUnique(suggestions);

		return (String[]) uniqueSuggestions.toArray(new String[0]);

	}

	/**

     * Return the list of suggestions from the current document. First the document is searched

     * backwards from the caret position and then forwards. 

	 * @param prefix the completion prefix

	 * @return all possible completions that were found in the current document

	 * @throws BadLocationException if accessing the document fails

	 */

	private ArrayList createSuggestionsFromOpenDocument(String prefix) throws BadLocationException {

		int selectionOffset= getSelectionOffset();

		ArrayList completions= new ArrayList();

		completions.addAll(getBackwardsSuggestions(fDocument, prefix, selectionOffset));

		completions.addAll(getForwardSuggestions(fDocument, prefix, selectionOffset));

		return completions;

	}

	/**

     * Create the suggestions list based on the provided prefix and the documents list.

     * Suggestions will be sorted such that the first suggestions come from the first document, 

     * etc.

	 * @param prefix the completion prefix

	 * @param documentsVector {@link ArrayList} of {@link IDocument}s.

	 * @return the list of completions, excluding the empty completion

	 */

    public static List createSuggestions(String prefix, ArrayList documentsVector) {

		// collect the suggestions from all the documents

		LinkedList suggestions= new LinkedList();

		for (int i= 0; i < documentsVector.size(); i++) {

			IDocument doc= (IDocument) documentsVector.get(i);

			try {

				suggestions.addAll(getForwardSuggestions(doc, prefix));

			} catch (BadLocationException e) {

				// log & ignore - a different document than the current has 

				// been concurrently modified

				log(e);

			}

		}

		return suggestions;

	}

	/**

	 * Remove duplicate suggestions (excluding the prefix), leaving the closest to list head. 

	 * @param suggestions a list of suggestions.

	 * @return a list of unique completion suggestions.

	 */

	public static ArrayList getUnique(List suggestions) {

		HashSet seenAlready= new HashSet();

		ArrayList uniqueSuggestions= new ArrayList();

		for (Iterator i= suggestions.iterator(); i.hasNext();) {

			String suggestion= (String) i.next();

			if (!seenAlready.contains(suggestion)) {

				seenAlready.add(suggestion);

				uniqueSuggestions.add(suggestion);

			}

		}

		return uniqueSuggestions;

	}

	/**

	 * Copied from {@link FindReplaceDocumentAdapter}.

	 * 

	 * Converts a non-regex string to a pattern

	 * that can be used with the regex search engine.

	 * 

	 * @param string the non-regex pattern

	 * @return the string converted to a regex pattern

	 */

	private static String asRegPattern(String string) {

		StringBuffer out= new StringBuffer(string.length());

		boolean quoting= false;

		for (int i= 0, length= string.length(); i < length; i++) {

			char ch= string.charAt(i);

			if (ch == '\\') {

				if (quoting) {

					out.append("\\E"); //$NON-NLS-1$

					quoting= false;

				}

				out.append("\\\\"); //$NON-NLS-1$

				continue;								

			}

			if (!quoting) {

				out.append("\\Q"); //$NON-NLS-1$

				quoting= true;

			}

			out.append(ch);

		}

		if (quoting)

			out.append("\\E"); //$NON-NLS-1$

		return out.toString();

	}

	/**

	 * Return the list of completion suggestions the correspond to the provided

	 * prefix

	 * 

	 * @param document the document to be scanned

	 * @param prefix the prefix to search for

	 * @param firstPosition the initial position in the document that

     *          the search will start from. In order to search from

     *          the beginning of the document use <code>firstPosition=0</code>.

	 * @return an {@link ArrayList} of possible completions, excluding the common prefix

	 * @throws BadLocationException if there is some error scanning the document.

     * 

	 * @see #getForwardSuggestions(IDocument, String)

	 */

	public static ArrayList getForwardSuggestions(IDocument document, 

			String prefix, int firstPosition) throws BadLocationException {

		ArrayList res= new ArrayList();

		FindReplaceDocumentAdapter searcher= new FindReplaceDocumentAdapter(document);

		// search only at word boundaries 

		String searchPattern= "\\b" + asRegPattern(prefix); //$NON-NLS-1$

		IRegion reg= searcher.find(firstPosition, searchPattern, true, CASE_SENSITIVE, false, true);

		while (reg != null) {

			// try to complete to a word. case is irrelevant here.

			IRegion word= searcher.find(reg.getOffset(), COMPLETION_WORD_REGEX, true, true, false, true);

			if (word.getLength() > reg.getLength() ) { // empty suggestion will be added later

				String found= document.get(word.getOffset(), word.getLength());

				res.add(found.substring(prefix.length()));

			}

			int nextPos= word.getOffset() + word.getLength();

			if (nextPos >= document.getLength() ) {

				break;

			}

			reg= searcher.find(nextPos, searchPattern, true, CASE_SENSITIVE, false, true);

		}

		return res;

	}

	/**

	 * Search for possible completions in the backward direction.

	 * @param document the document to be scanned

	 * @param prefix the completion prefix

	 * @param firstPosition the caret position

     * @return a list of suggestions from the caret position to the beginning of the document.

	 * @throws BadLocationException if any error occurs

	 */

    public static ArrayList getBackwardsSuggestions(IDocument document, String prefix, int firstPosition) throws BadLocationException {

		ArrayList res= new ArrayList();

		FindReplaceDocumentAdapter searcher= new FindReplaceDocumentAdapter(document);

		// search only at word boundaries 

		String searchPattern= "\\b" + asRegPattern(prefix); //$NON-NLS-1$

		IRegion reg= searcher.find(firstPosition, searchPattern, false, CASE_SENSITIVE, false, true);

		while (reg != null) {

			// try to complete to a word. case is of no matter here

			IRegion word= searcher.find(reg.getOffset(), COMPLETION_WORD_REGEX, true, true, false, true);

			if (word.getLength() > reg.getLength() ) { // empty suggestion will be added later

				String found= document.get(word.getOffset(), word.getLength());

				res.add(found.substring(prefix.length()));

			}

			int nextPos= word.getOffset() - 1;

			if (nextPos < 0 ) {

				break;

			}

			reg= searcher.find(nextPos, searchPattern, false, CASE_SENSITIVE, false, true);

		}

		return res;

	}

	/**

     * The method is equivalent to <code>getForwardSuggestions(document, prefix, 0)</code> 

	 * @param document the document to scan

	 * @param prefix the completion prefix

     * @return the list of completions that are result of this document scan.

     * @throws BadLocationException if some error occurs. Should not be ever thrown.

     * 

	 * @see #getForwardSuggestions(IDocument, String, int)

	 */

    public static ArrayList getForwardSuggestions(IDocument document, 

            String prefix) throws BadLocationException {

		return getForwardSuggestions(document, prefix, 0);

	}

	/**

	 * Return the part of a word before the caret.

	 * If the caret is not at a middle/end of a word, 

	 * returns null.

	 * @return the prefix at the current cursor position that 

     *      will be used in the search for possible completions

	 * @throws BadLocationException if accessing the document fails

	 */

	private String getCurrentPrefix() throws BadLocationException {

		ITextSelection selection= (ITextSelection) getTextEditor().getSelectionProvider().getSelection();

		if (selection.getLength() > 0) {

			return null;

		}

		int pos= selection.getOffset();

		int prevNonAlpha= pos;

		while (prevNonAlpha > 0 && Character.isJavaIdentifierPart(fDocument.getChar(prevNonAlpha-1))) {

			prevNonAlpha--;

		}

		if (prevNonAlpha != pos) {

			return fDocument.get(prevNonAlpha, pos - prevNonAlpha);

		}

		return null;

	}

	/**

	 * Logs the exception.

	 * 

	 * @param e the exception

	 */

	private static void log(BadLocationException e) {

		String msg= e.getLocalizedMessage();

		if (msg == null)

			msg= "unable to access the document"; //$NON-NLS-1$

		TextEditorPlugin.getDefault().getLog().log(new Status(IStatus.ERROR, TextEditorPlugin.PLUGIN_ID, IStatus.OK, msg, e));

	}

}