org.eclipse.rephraserengine.core/src/org/eclipse/rephraserengine/core/analysis/symtab/SymbolTable.java - ptp/org.eclipse.photran - Git at Google

 /*******************************************************************************
  * Copyright (c) 2010 University of Illinois at Urbana-Champaign 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:
  *    UIUC - Initial API and implementation
  *******************************************************************************/
 package org.eclipse.rephraserengine.core.analysis.symtab;

 import java.util.Collections;
 import java.util.ConcurrentModificationException;
 import java.util.HashMap;
 import java.util.Map;

 import org.eclipse.rephraserengine.core.util.TwoKeyHashMap;

 /**
  * A simple, generic symbol table with nested scopes.
  * <p>
  * THIS IS PRELIMINARY AND EXPERIMENTAL.  IT IS NOT APPROPRIATE FOR PRODUCTION USE.
  *
  * @author Jeff Overbey
  *
  * @param <N> namespace type
  * @param <S> symbol type
  *
  * @since 2.0
  */
 public class SymbolTable<N, S>
 {
     /**
      * Settings that determine how this symbol table and its children will operate.
      */
     public static class Settings<S>
     {
         /** Constructor.  See {@link #errorEntry}. */
         public Settings() { this.errorEntry = null; }

         /** Constructor.  See {@link #errorEntry}. */
         public Settings(S errorEntry) { this.errorEntry = errorEntry; }

         /**
          * A (unique) error symbol which will be returned whenever lookup fails.
          * May be <code>null</code>.
          * <p>
          * Failure will always be determined by comparing symbols <i>pointerwise</i>
          * with this value.
          * <p>
          * The value of this field is set via the {@link Settings#Settings(Object)}
          * constructor.
          */
         public final S errorEntry;

         /**
          * If a lookup fails in this scope, this setting determines whether the
          * {@link SymbolTable#lookup(Object, String)} method should fail immediately
          * (<code>false</code>) or if it should attempt to look up the name in an
          * outer scope (<code>true</code>).
          */
         public boolean resolveInOuterScopeIfLookupFails = true;

         /**
          * This determines whether {@link SymbolTable#enter(Object, String, Object)}
          * should allow a symbol to be added if it already exists in an outer scope.
          * <p>
          * If {@link #resolveInOuterScopeIfLookupFails} is <code>false</code>, this
          * setting has no effect, since a lookup will never search an outer scope.
          */
         public boolean allowShadowing = true;

         /**
          * This determines whether symbol names are case-sensitive.  If
          * <code>false</code>, all symbol names will be converted to lower case.
          */
         public boolean caseSensitive = true;
     }

     /**
      * Settings for this symbol table hierarchy, including what symbol will be
      * returned when a lookup fails and what scoping rules should apply.
      */
     protected final Settings<S> settings;

     /**
      * Symbol table representing the outer scope, or <code>null</code> if this is the
      * outermost (global) scope.
      */
     protected final SymbolTable<N, S> parent;

     /**
      * Entries in the scope represented by this symbol table.  Maps a namespace and
      * a name to a symbol.
      */
     protected final TwoKeyHashMap<N, String, S> entries;

     /**
      * Named scopes contained in this symbol table.  Maps a scope name to a symbol table.
      */
     protected final Map<String, SymbolTable<N, S>> namedScopes;

     public SymbolTable()
     {
         this.settings = new Settings<S>();
         this.entries = new TwoKeyHashMap<N, String, S>();
         this.namedScopes = new HashMap<String, SymbolTable<N, S>>();
         this.parent = null;
     }

     public SymbolTable(Settings<S> settings)
     {
         assert settings != null;

         this.settings = settings;
         this.entries = new TwoKeyHashMap<N, String, S>();
         this.namedScopes = new HashMap<String, SymbolTable<N, S>>();
         this.parent = null;
     }

     public SymbolTable(SymbolTable<N, S> parent)
     {
         assert parent != null;

         this.settings = parent.settings;
         this.entries = new TwoKeyHashMap<N, String, S>();
         this.namedScopes = new HashMap<String, SymbolTable<N, S>>();
         this.parent = parent;
     }

     protected String canonicalize(String name)
     {
         assert name != null;

         if (settings.caseSensitive)
             return name;
         else
             return name.toLowerCase();
     }

     /**
      * Looks up the given name in the given namespace.
      *
      * @param namespace
      * @param name
      * @return the corresponding symbol, or {@link Settings#errorEntry} if the symbol
      *         cannot be found
      */
     public S lookup(N namespace, String name)
     {
         assert namespace != null && name != null;

         name = canonicalize(name);

         if (entries.containsEntry(namespace, name))
             return entries.getEntry(namespace, name);
         else if (parent != null && settings.resolveInOuterScopeIfLookupFails)
             return parent.lookup(namespace, name);
         else
             return settings.errorEntry;
     }

     /**
      * @return <code>true</code> iff {@link #lookup(Object, String)} will succeed
      *         for the given namespace and name
      */
     public boolean contains(N namespace, String name)
     {
         assert namespace != null && name != null;

         return lookup(namespace, name) != settings.errorEntry;
     }

     /**
      * Adds an entry to the symbol type for the given name in the given namespace.
      *
      * @param namespace
      * @param name
      * @param symbol
      * @return the symbol iff entry succeeds, or <code>null</code> if the symbol
      *         cannot be added because it will conflict with an existing symbol
      */
     public S enter(N namespace, String name, S symbol)
     {
         assert namespace != null && name != null && symbol != null;

         name = canonicalize(name);

         if (!canEnter(namespace, name))
             return null;
         else
             return entries.put(namespace, name, symbol);
     }

     /**
      * Adds an entry to the symbol type if there is not already a symbol for the
      * given name in the given namespace; otherwise, returns the existing symbol.
      *
      * @param namespace
      * @param name
      * @param symbol
      * @return the symbol corresponding to the given name in the given namespace
      */
     public S ensure(N namespace, String name, S symbol)
     {
         assert namespace != null && name != null && symbol != null;

         name = canonicalize(name);

         if (!canEnter(namespace, name))
             return lookup(namespace, name);
         else
             return entries.put(namespace, name, symbol);
     }

     /**
      * @return <code>true</code> iff {@link #enter(Object, String, Object)} will
      *         succeed for the given namespace and name
      */
     public boolean canEnter(N namespace, String name)
     {
         assert namespace != null && name != null;

         name = canonicalize(name);

         if (entries.containsEntry(namespace, name))
             return false;
         else if (parent != null && settings.resolveInOuterScopeIfLookupFails)
             return settings.allowShadowing || parent.lookup(namespace, name) == settings.errorEntry;
         else
             return true;
     }

     /**
      * Returns a new symbol table for a child scope of this scope (i.e., a nested
      * scope).
      * <p>
      * Note that this does not modify this {@link SymbolTable} object; the correct
      * usage is <code>symtab = symtab.enterScope()</code>.
      *
      * @return a new symbol table for a child scope of this scope
      */
     public SymbolTable<N, S> enterScope()
     {
         return new SymbolTable<N, S>(this);
     }

     /**
      * Returns a new symbol table for a child scope of this scope (i.e., a nested
      * scope).
      * <p>
      * Note that this does not modify this {@link SymbolTable} object; the correct
      * usage is <code>symtab = symtab.enterScope()</code>.
      *
      * @return a new symbol table for a child scope of this scope
      */
     public SymbolTable<N, S> enterNamedScope(String name)
     {
         SymbolTable<N, S> namedScope = enterScope();
         namedScopes.put(name, namedScope);
         return namedScope;
     }

     /**
      * Returns the symbol table for the parent scope of this scope (i.e., the next
      * outermost scope).
      * <p>
      * Note that this does not modify this {@link SymbolTable} object; the correct
      * usage is <code>symtab = symtab.exitScope()</code>.
      *
      * @return the symbol table for the parent scope of this scope, or
      *         <code>null</code> iff this symbol table has no parent (i.e., it
      *         represents the outermost scope)
      */
     public SymbolTable<N, S> exitScope()
     {
         return parent;
     }

     /**
      * Returns a map containing all of the entries in the given namespace that
      * are defined in this scope.
      * <p>
      * This does <i>not</i> include any entries inherited from the parent scope.
      * <p>
      * An an API policy, this map may or may not be backed by the map supporting
      * this symbol table.  Therefore, it must not be modified, and the symbol
      * table must not be modified while iterating through the map (to prevent
      * {@link ConcurrentModificationException}s).
      *
      * @param namespace
      * @return a mapping from (canonicalized) symbol names to symbols
      */
     public Map<String, S> getLocalEntriesIn(N namespace)
     {
         Map<String, S> result = entries.getAllEntriesFor(namespace);

         if (result == null)
             return Collections.<String, S>emptyMap();
         else
             return result;
     }

     /**
      * Returns the symbol table for the outermost scope containing this scope (i.e.,
      * the ancester symbol table with a <code>null</code> parent symbol table).
      * <p>
      * Note that this does not modify this {@link SymbolTable} object; the most
      * common usage is <code>symtab.outermostScope().enter(...)</code>.
      *
      * @return the symbol table for the parent scope of this scope
      */
     public SymbolTable<N, S> outermostScope()
     {
         if (parent == null)
             return this;
         else
             return parent.outermostScope();
     }

     /**
      * Returns the symbol table corresponding to the given named scope.
      *
      * @return the symbol table associated with the named scope <code>scopeName</code>, or
      *         <code>null</code> iff no such named scope exists
      *
      * @since 3.0
      */
     public SymbolTable<N, S> getNamedScope(String scopeName)
     {
         if (namedScopes != null)
             return namedScopes.get(scopeName);
         else
             return null;
     }

     /**
      * Returns the nested symbol table found by traversing successively deeper named scopes, using
      * the given sequence of scope names.
      *
      * @return the symbol table corresponding to
      *         <code>getNamedScope(scopeNames[0]).getNamedScope(scopeNames[1]).getNamedScope(scopeNames[2])</code>
      *         ..., or <code>null</code> iff no such named scope exists
      *
      * @since 3.0
      */
     public SymbolTable<N, S> getNestedNamedScope(String... scopeNames)
     {
         SymbolTable<N, S> result = this;
         for (String scopeName : scopeNames)
            if (!scopeName.trim().equals("") && result != null) //$NON-NLS-1$
                result = result.getNamedScope(scopeName);
         return result;
     }

     @Override public String toString()
     {
         StringBuilder sb = new StringBuilder();

         for (N namespace : entries.keySet())
         {
             sb.append(namespace.toString().toUpperCase() + " NAMESPACE:\n"); //$NON-NLS-1$

             for (String name : entries.getAllEntriesFor(namespace).keySet())
                 sb.append("    " + name + " -> " + entries.getEntry(namespace, name) + "\n"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$

             sb.append("\n"); //$NON-NLS-1$
         }

         if (!namedScopes.isEmpty())
         {
             sb.append("This symbol table contains the following named scopes:\n"); //$NON-NLS-1$

             for (String name : namedScopes.keySet())
             {
                 sb.append("    "); //$NON-NLS-1$
                 sb.append(name);
                 sb.append("\n"); //$NON-NLS-1$
             }
         }

         if (parent != null)
         {
             sb.append("\n\n==================== PARENT ====================\n"); //$NON-NLS-1$
             sb.append(parent.toString());
         }

         return sb.toString();
     }
 }
	/*******************************************************************************
	* Copyright (c) 2010 University of Illinois at Urbana-Champaign 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:
	* UIUC - Initial API and implementation
	*******************************************************************************/
	package org.eclipse.rephraserengine.core.analysis.symtab;

	import java.util.Collections;
	import java.util.ConcurrentModificationException;
	import java.util.HashMap;
	import java.util.Map;

	import org.eclipse.rephraserengine.core.util.TwoKeyHashMap;

	/**
	* A simple, generic symbol table with nested scopes.
	* <p>
	* THIS IS PRELIMINARY AND EXPERIMENTAL. IT IS NOT APPROPRIATE FOR PRODUCTION USE.
	*
	* @author Jeff Overbey
	*
	* @param <N> namespace type
	* @param <S> symbol type
	*
	* @since 2.0
	*/
	public class SymbolTable<N, S>
	{
	/**
	* Settings that determine how this symbol table and its children will operate.
	*/
	public static class Settings<S>
	{
	/** Constructor. See {@link #errorEntry}. */
	public Settings() { this.errorEntry = null; }

	/** Constructor. See {@link #errorEntry}. */
	public Settings(S errorEntry) { this.errorEntry = errorEntry; }

	/**
	* A (unique) error symbol which will be returned whenever lookup fails.
	* May be <code>null</code>.
	* <p>
	* Failure will always be determined by comparing symbols <i>pointerwise</i>
	* with this value.
	* <p>
	* The value of this field is set via the {@link Settings#Settings(Object)}
	* constructor.
	*/
	public final S errorEntry;

	/**
	* If a lookup fails in this scope, this setting determines whether the
	* {@link SymbolTable#lookup(Object, String)} method should fail immediately
	* (<code>false</code>) or if it should attempt to look up the name in an
	* outer scope (<code>true</code>).
	*/
	public boolean resolveInOuterScopeIfLookupFails = true;

	/**
	* This determines whether {@link SymbolTable#enter(Object, String, Object)}
	* should allow a symbol to be added if it already exists in an outer scope.
	* <p>
	* If {@link #resolveInOuterScopeIfLookupFails} is <code>false</code>, this
	* setting has no effect, since a lookup will never search an outer scope.
	*/
	public boolean allowShadowing = true;

	/**
	* This determines whether symbol names are case-sensitive. If
	* <code>false</code>, all symbol names will be converted to lower case.
	*/
	public boolean caseSensitive = true;
	}

	/**
	* Settings for this symbol table hierarchy, including what symbol will be
	* returned when a lookup fails and what scoping rules should apply.
	*/
	protected final Settings<S> settings;

	/**
	* Symbol table representing the outer scope, or <code>null</code> if this is the
	* outermost (global) scope.
	*/
	protected final SymbolTable<N, S> parent;

	/**
	* Entries in the scope represented by this symbol table. Maps a namespace and
	* a name to a symbol.
	*/
	protected final TwoKeyHashMap<N, String, S> entries;

	/**
	* Named scopes contained in this symbol table. Maps a scope name to a symbol table.
	*/
	protected final Map<String, SymbolTable<N, S>> namedScopes;

	public SymbolTable()
	{
	this.settings = new Settings<S>();
	this.entries = new TwoKeyHashMap<N, String, S>();
	this.namedScopes = new HashMap<String, SymbolTable<N, S>>();
	this.parent = null;
	}

	public SymbolTable(Settings<S> settings)
	{
	assert settings != null;

	this.settings = settings;
	this.entries = new TwoKeyHashMap<N, String, S>();
	this.namedScopes = new HashMap<String, SymbolTable<N, S>>();
	this.parent = null;
	}

	public SymbolTable(SymbolTable<N, S> parent)
	{
	assert parent != null;

	this.settings = parent.settings;
	this.entries = new TwoKeyHashMap<N, String, S>();
	this.namedScopes = new HashMap<String, SymbolTable<N, S>>();
	this.parent = parent;
	}

	protected String canonicalize(String name)
	{
	assert name != null;

	if (settings.caseSensitive)
	return name;
	else
	return name.toLowerCase();
	}

	/**
	* Looks up the given name in the given namespace.
	*
	* @param namespace
	* @param name
	* @return the corresponding symbol, or {@link Settings#errorEntry} if the symbol
	* cannot be found
	*/
	public S lookup(N namespace, String name)
	{
	assert namespace != null && name != null;

	name = canonicalize(name);

	if (entries.containsEntry(namespace, name))
	return entries.getEntry(namespace, name);
	else if (parent != null && settings.resolveInOuterScopeIfLookupFails)
	return parent.lookup(namespace, name);
	else
	return settings.errorEntry;
	}

	/**
	* @return <code>true</code> iff {@link #lookup(Object, String)} will succeed
	* for the given namespace and name
	*/
	public boolean contains(N namespace, String name)
	{
	assert namespace != null && name != null;

	return lookup(namespace, name) != settings.errorEntry;
	}

	/**
	* Adds an entry to the symbol type for the given name in the given namespace.
	*
	* @param namespace
	* @param name
	* @param symbol
	* @return the symbol iff entry succeeds, or <code>null</code> if the symbol
	* cannot be added because it will conflict with an existing symbol
	*/
	public S enter(N namespace, String name, S symbol)
	{
	assert namespace != null && name != null && symbol != null;

	name = canonicalize(name);

	if (!canEnter(namespace, name))
	return null;
	else
	return entries.put(namespace, name, symbol);
	}

	/**
	* Adds an entry to the symbol type if there is not already a symbol for the
	* given name in the given namespace; otherwise, returns the existing symbol.
	*
	* @param namespace
	* @param name
	* @param symbol
	* @return the symbol corresponding to the given name in the given namespace
	*/
	public S ensure(N namespace, String name, S symbol)
	{
	assert namespace != null && name != null && symbol != null;

	name = canonicalize(name);

	if (!canEnter(namespace, name))
	return lookup(namespace, name);
	else
	return entries.put(namespace, name, symbol);
	}

	/**
	* @return <code>true</code> iff {@link #enter(Object, String, Object)} will
	* succeed for the given namespace and name
	*/
	public boolean canEnter(N namespace, String name)
	{
	assert namespace != null && name != null;

	name = canonicalize(name);

	if (entries.containsEntry(namespace, name))
	return false;
	else if (parent != null && settings.resolveInOuterScopeIfLookupFails)
	return settings.allowShadowing \|\| parent.lookup(namespace, name) == settings.errorEntry;
	else
	return true;
	}

	/**
	* Returns a new symbol table for a child scope of this scope (i.e., a nested
	* scope).
	* <p>
	* Note that this does not modify this {@link SymbolTable} object; the correct
	* usage is <code>symtab = symtab.enterScope()</code>.
	*
	* @return a new symbol table for a child scope of this scope
	*/
	public SymbolTable<N, S> enterScope()
	{
	return new SymbolTable<N, S>(this);
	}

	/**
	* Returns a new symbol table for a child scope of this scope (i.e., a nested
	* scope).
	* <p>
	* Note that this does not modify this {@link SymbolTable} object; the correct
	* usage is <code>symtab = symtab.enterScope()</code>.
	*
	* @return a new symbol table for a child scope of this scope
	*/
	public SymbolTable<N, S> enterNamedScope(String name)
	{
	SymbolTable<N, S> namedScope = enterScope();
	namedScopes.put(name, namedScope);
	return namedScope;
	}

	/**
	* Returns the symbol table for the parent scope of this scope (i.e., the next
	* outermost scope).
	* <p>
	* Note that this does not modify this {@link SymbolTable} object; the correct
	* usage is <code>symtab = symtab.exitScope()</code>.
	*
	* @return the symbol table for the parent scope of this scope, or
	* <code>null</code> iff this symbol table has no parent (i.e., it
	* represents the outermost scope)
	*/
	public SymbolTable<N, S> exitScope()
	{
	return parent;
	}

	/**
	* Returns a map containing all of the entries in the given namespace that
	* are defined in this scope.
	* <p>
	* This does <i>not</i> include any entries inherited from the parent scope.
	* <p>
	* An an API policy, this map may or may not be backed by the map supporting
	* this symbol table. Therefore, it must not be modified, and the symbol
	* table must not be modified while iterating through the map (to prevent
	* {@link ConcurrentModificationException}s).
	*
	* @param namespace
	* @return a mapping from (canonicalized) symbol names to symbols
	*/
	public Map<String, S> getLocalEntriesIn(N namespace)
	{
	Map<String, S> result = entries.getAllEntriesFor(namespace);

	if (result == null)
	return Collections.<String, S>emptyMap();
	else
	return result;
	}

	/**
	* Returns the symbol table for the outermost scope containing this scope (i.e.,
	* the ancester symbol table with a <code>null</code> parent symbol table).
	* <p>
	* Note that this does not modify this {@link SymbolTable} object; the most
	* common usage is <code>symtab.outermostScope().enter(...)</code>.
	*
	* @return the symbol table for the parent scope of this scope
	*/
	public SymbolTable<N, S> outermostScope()
	{
	if (parent == null)
	return this;
	else
	return parent.outermostScope();
	}

	/**
	* Returns the symbol table corresponding to the given named scope.
	*
	* @return the symbol table associated with the named scope <code>scopeName</code>, or
	* <code>null</code> iff no such named scope exists
	*
	* @since 3.0
	*/
	public SymbolTable<N, S> getNamedScope(String scopeName)
	{
	if (namedScopes != null)
	return namedScopes.get(scopeName);
	else
	return null;
	}

	/**
	* Returns the nested symbol table found by traversing successively deeper named scopes, using
	* the given sequence of scope names.
	*
	* @return the symbol table corresponding to
	* <code>getNamedScope(scopeNames[0]).getNamedScope(scopeNames[1]).getNamedScope(scopeNames[2])</code>
	* ..., or <code>null</code> iff no such named scope exists
	*
	* @since 3.0
	*/
	public SymbolTable<N, S> getNestedNamedScope(String... scopeNames)
	{
	SymbolTable<N, S> result = this;
	for (String scopeName : scopeNames)
	if (!scopeName.trim().equals("") && result != null) //$NON-NLS-1$
	result = result.getNamedScope(scopeName);
	return result;
	}

	@Override public String toString()
	{
	StringBuilder sb = new StringBuilder();

	for (N namespace : entries.keySet())
	{
	sb.append(namespace.toString().toUpperCase() + " NAMESPACE:\n"); //$NON-NLS-1$

	for (String name : entries.getAllEntriesFor(namespace).keySet())
	sb.append(" " + name + " -> " + entries.getEntry(namespace, name) + "\n"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$

	sb.append("\n"); //$NON-NLS-1$
	}

	if (!namedScopes.isEmpty())
	{
	sb.append("This symbol table contains the following named scopes:\n"); //$NON-NLS-1$

	for (String name : namedScopes.keySet())
	{
	sb.append(" "); //$NON-NLS-1$
	sb.append(name);
	sb.append("\n"); //$NON-NLS-1$
	}
	}

	if (parent != null)
	{
	sb.append("\n\n==================== PARENT ====================\n"); //$NON-NLS-1$
	sb.append(parent.toString());
	}

	return sb.toString();
	}
	}