• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Signature Class To Identify Symbols

Status
Not open for further replies.
Level 31
Joined
Jul 10, 2007
Messages
6,306
So, I originally coded a Signature class that was something of an abomination. I want to do something better this time ; ).


The Signature class should support any type of signature possible without accounting for anything. This means that it needs to be extremely flexible. Parameters for functions, names, generics, etc. It should also implicitly support polymorphism.

When matching signatures, you should be able to find the closest legal signature to your own signature. For example, if you want Test(unit) and you find Test(widget) and Test(handle), it should select Test(widget) : ).

Signatures should generate a hashcode for the initial search.


The original way I did this was by having components. Every Component would represent something, and they'd combine together to form a hash and validate with other components. The components would make up a signature. For example, a name component, a parameter list component, etc. This kind of turned Signature into an abomination of a class. Rather than using polymorphism and simple code, I created a crazy system. Let's not do that : P.


Ideas?


Here is old Signature code

Java:
package symboltable.component;

import symboltable.fuzzy.Fuzzy;

public interface Component extends Fuzzy
{
	@Override
	public int hashCode();

	@Override
	public boolean equals(Object object);
} // Component

Java:
package symboltable.component;

import symboltable.data.privilege.Privilege;
import symboltable.fuzzy.Fuzzy;

public class EmptyComponent implements Component
{
	@Override
	public int distance(Fuzzy fuzzy, Privilege privilege)
	{
		return -1;
	} // distance

	@Override
	public int distance(Fuzzy fuzzy)
	{
		return -1;
	} // distance

	@Override
	public boolean canBe(Fuzzy fuzzy)
	{
		return false;
	} // canBe

	@Override
	public boolean canBe(Fuzzy fuzzy, Privilege privilege)
	{
		return false;
	} // canBe

	@Override
	public int hashCode()
	{
		return 0;
	} // hashCode

	@Override
	public boolean equals(Object object)
	{
		return false;
	} // equals

	@Override
	public <T extends Fuzzy> T getKey()
	{
		return null;
	} // getKey

	@Override
	public int compare(Fuzzy o1, Fuzzy o2)
	{
		return 0;
	} // compare

	@Override
	public boolean equalsFuzzy(Fuzzy fuzzy)
	{
		return false;
	} // equalsFuzzy
} // EmptyComponent

Java:
package symboltable.fuzzy;

import java.util.Comparator;

import symboltable.data.privilege.Privilege;

/**
 * A value can be represented as another value. For example, 4
 * can be represented with the number 4. With rounding, 3.9 can
 * be represented with the number 4 as well.
 * 
 * A value x can be y if y can represent x
 * 		x.canBe(y)
 * 
 * Two values are equal when they can both represent each other
 * 		x.canBe(y) and y.canBe(x)
 * 
 * Two values are fuzzy when at least one can represent the other
 * 		x.canBe(y) or y.canBe(x)
 */
public interface Fuzzy extends Comparator<Fuzzy>
{
	@Override
	public int hashCode();

	/**
	 * This must be commutative!
	 */
	@Override
	public boolean equals(Object object);

	public boolean equalsFuzzy(Fuzzy fuzzy);

	/**
	 * Key comparison. Assume all privileges.
	 * <p>
	 * Calculates the distance from this object as the origin to the
	 * other object. Two objects may be fuzzy equal, but the distance
	 * from one to the other may be infinite. Can approach fuzzy equality
	 * from two sides. Fuzzy equality only requires that one side exist.
	 * <p>
	 * distance < 0 -   not equal
	 * distance = 0 -       equal
	 * distance > 0 - fuzzy equal
	 * 
	 * @return				how equal is this to the parameter?
	 */
	public int distance(Fuzzy fuzzy);

	/**
	 * Actual comparison.
	 */
	public int distance(Fuzzy fuzzy, Privilege privilege);

	/**
	 * Key comparison. Assume all privileges.
	 * <p>
	 * This states that this object can be represented by the other object.
	 * This is usually when the other object is a superclass of this object.
	 */
	public boolean canBe(Fuzzy fuzzy);

	/**
	 * Actual comparison.
	 */
	public boolean canBe(Fuzzy fuzzy, Privilege privilege);

	/**
	 * Fuzzy serving as a key for this Fuzzy.
	 */
	public <T extends Fuzzy> T getKey();
} // IFuzzy

Java:
package symboltable.signature;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Map.Entry;

import symboltable.component.Component;
import symboltable.component.EmptyComponent;
import symboltable.data.privilege.Privilege;
import symboltable.fuzzy.Fuzzy;
import symboltable.utils.Utils;

import com.google.common.collect.ImmutableMap;

/**
 * A signature is used to identify something.
 */
public class Signature implements Fuzzy
{
	// static fields
	private static Component													emptyComponent;
	private final static ImmutableMap<Class<? extends Component>, Component>	emptyComponentMap;
	public final static Signature												emptySignature;

	static
	{
		emptyComponent = new EmptyComponent();
		emptyComponentMap = ImmutableMap.of();
		emptySignature = new Signature();
	} // static

	// fields
	private final ImmutableMap<Class<? extends Component>, Component>			components;
	private final String														name;
	private final int															hashCode;

	/**
	 * This constructs an abstract signature. Abstract signatures can't be identified
	 * and have no name.
	 */
	public Signature()
	{
		components = emptyComponentMap;
		name = "";
		hashCode = 0;
	} // SymbolSignature

	/**
	 * This constructs a concrete signature. A concrete signature can be identified.
	 */
	public Signature(String name, Component... components)
	{
		this.name = name == null? "" : name;
		this.components = buildComponentMap(components);
		this.hashCode = buildHash(components);
	} // SymbolSignature

	// constructor methods
	private ImmutableMap<Class<? extends Component>, Component> buildComponentMap(Component... components)
	{
		ImmutableMap.Builder<Class<? extends Component>, Component> builder = ImmutableMap.builder();

		for (Component component : components)
		{
			if (component != null)
			{
				builder.put(component.getClass(), component);
			} // if
		} // for

		return builder.build();
	} // buildComponentMap

	private int buildHash(Component... components)
	{
		Arrays.sort(components, new Comparator<Fuzzy>()
		{

			@Override
			public int compare(Fuzzy o1, Fuzzy o2)
			{
				return o1.hashCode() - o2.hashCode();
			}
		});

		int hash = this.name.hashCode();

		for (Component component : components)
		{
			if (component != null)
			{
				hash = hash * 3 + component.hashCode();
			} // if
		} // for

		return hash;
	} // buildHash

	public static boolean isClass(Object object)
	{
		return Utils.isClass(Signature.class, object);
	} // isClass

	public ImmutableMap<Class<? extends Component>, Component> getComponents()
	{
		return components;
	} // getComponents

	public <T extends Component> T getComponent(Class<T> componentType)
	{
		return componentType.cast(components.getOrDefault(componentType, null));
	} // getComponent

	@Override
	public final String toString()
	{
		return name;
	} // toString

	@Override
	public final int hashCode()
	{
		return hashCode;
	} // hashCode

	public Signature cast(Object object)
	{
		if (!Utils.isClass(Fuzzy.class, object))
		{
			return emptySignature;
		} // if

		if (!Utils.isClass(Signature.class, ((Fuzzy) object).getKey()))
		{
			return emptySignature;
		} // if

		return (Signature) ((Fuzzy) object).getKey();
	} // cast

	protected boolean isEqual(Signature signature)
	{
		return !name.isEmpty() && toString().equals(signature.toString()) && getComponents().size() == signature.getComponents().size();
	} // isEqual

	public boolean equals(Signature signature)
	{
		if (!isEqual(signature))
		{
			return false;
		} // if

		for (Entry<?, Component> entry : components.entrySet())
		{
			if (!signature.components.getOrDefault(entry.getKey(), emptyComponent).equals(entry.getValue()))
			{
				return false;
			} // if
		} // for

		return true;
	} // equals

	@Override
	public boolean equals(Object object)
	{
		return equals(cast(object));
	} // equals

	public int distance(Signature signature, Privilege privilege)
	{
		if (!isEqual(signature))
		{
			return -1;
		} // if

		int distance = 0;
		int distanceResult;

		for (Entry<?, Component> entry : components.entrySet())
		{
			distanceResult = signature.components.getOrDefault(entry.getKey(), emptyComponent).distance(entry.getValue(), privilege);

			if (distanceResult == -1)
			{
				return -1;
			} // if

			distance += distanceResult;
		} // for

		return distance;
	} // distance

	@Override
	public int distance(Fuzzy fuzzy, Privilege privilege)
	{
		return distance(cast(fuzzy), privilege);
	} // distance

	public boolean canBe(Signature signature, Privilege privilege)
	{
		if (!isEqual(signature))
		{
			return false;
		} // if

		for (Entry<?, Component> entry : components.entrySet())
		{
			if (!signature.components.getOrDefault(entry.getKey(), emptyComponent).canBe(entry.getValue(), privilege))
			{
				return false;
			} // if
		} // for

		return true;
	} // canBe

	@Override
	public boolean canBe(Fuzzy fuzzy, Privilege privilege)
	{
		return canBe(cast(fuzzy), privilege);
	} // canBe

	public int distance(Signature signature)
	{
		if (!isEqual(signature))
		{
			return -1;
		} // if

		int distance = 0;
		int distanceResult;

		for (Entry<?, Component> entry : components.entrySet())
		{
			distanceResult = signature.components.getOrDefault(entry.getKey(), emptyComponent).distance(entry.getValue());

			if (distanceResult == -1)
			{
				return -1;
			} // if

			distance += distanceResult;
		} // for

		return distance;
	} // distance

	@Override
	public int distance(Fuzzy fuzzy)
	{
		return distance(cast(fuzzy));
	} // distance

	public boolean canBe(Signature signature)
	{
		if (!isEqual(signature))
		{
			return false;
		} // if

		for (Entry<?, Component> entry : components.entrySet())
		{
			if (!signature.components.getOrDefault(entry.getKey(), emptyComponent).canBe(entry.getValue()))
			{
				return false;
			} // if
		} // for

		return true;
	} // canBe

	@Override
	public boolean canBe(Fuzzy fuzzy)
	{
		return canBe(cast(fuzzy));
	} // canBe

	@SuppressWarnings("unchecked")
	@Override
	public <T extends Fuzzy> T getKey()
	{
		return (T) this;
	} // getKey

	@Override
	public int compare(Fuzzy o1, Fuzzy o2)
	{
		int distance = o1.getKey().distance(o2.getKey());

		if (distance == -1)
		{
			distance = o2.getKey().distance(o1.getKey());

			if (distance == -1)
			{
				distance = 0;
			} // if

			distance = -distance;
		} // if

		return distance;
	} // compare

	public boolean equalsFuzzy(Signature signature)
	{
		if (!isEqual(signature))
		{
			return false;
		} // if

		for (Entry<?, Component> entry : components.entrySet())
		{
			if (!signature.components.getOrDefault(entry.getKey(), emptyComponent).equalsFuzzy(entry.getValue()))
			{
				return false;
			} // if
		} // for

		return true;
	} // equalsFuzzy

	@Override
	public boolean equalsFuzzy(Fuzzy fuzzy)
	{
		return equalsFuzzy(cast(fuzzy));
	} // equalsFuzzy
} // SymbolSignature

Java:
package symboltable.signature;

import java.util.Iterator;
import java.util.LinkedList;

import symboltable.symbol.SymbolType;

public class SymbolSignatureFunction extends Signature
{
	private LinkedList<SymbolType>	types;

	private void initialize(SymbolType... types)
	{
		this.types = new LinkedList<SymbolType>();

		for (SymbolType type : types)
		{
			this.types.add(type);
		} // for
	} // initialize

	public SymbolSignatureFunction()
	{
		super();
		initialize();
	} // SymbolSignatureFunction

	public SymbolSignatureFunction(String name, SymbolType... types)
	{
		super(name);
		initialize(types);
	} // SymbolSignatureFunction

	public static boolean isFunctionSignature(Object signature)
	{
		return SymbolSignatureFunction.class.isAssignableFrom(signature.getClass());
	} // isScope

	// fuzzy equality
	public boolean equalsArguments(LinkedList<SymbolType> types)
	{
		Iterator<SymbolType> iterator1 = this.types.iterator();
		Iterator<SymbolType> iterator2 = types.iterator();

		SymbolType type1;
		SymbolType type2;

		while (iterator1.hasNext() && iterator2.hasNext())
		{
			type1 = iterator1.next();
			type2 = iterator2.next();

			if (type1 != type2 && !type2.inherits(type1))
			{
				break;
			} // if
		} // while

		return !iterator1.hasNext() && !iterator2.hasNext();
	} // equalsArgumentsFuzzy

	public LinkedList<SymbolType> getTypes()
	{
		return types;
	} // getTypes

	protected boolean superEquals(Object signature)
	{
		return super.equals(signature);
	} // superEquals

	// fuzzy equality
	@Override
	public boolean equals(Object signature)
	{
		/*
		 * Is the signature a function?
		 * Does the signature have the same name?
		 * Does the signature have the same arguments?
		 */
		return isFunctionSignature(signature) && super.equals(signature) && equalsArguments(((SymbolSignatureFunction) signature).types);
	} // equals

	public int calculateDistance(LinkedList<SymbolType> types)
	{
		int distance = 0;

		Iterator<SymbolType> iterator1 = this.types.iterator();
		Iterator<SymbolType> iterator2 = types.iterator();

		SymbolType type1;
		SymbolType type2;

		while (iterator1.hasNext() && iterator2.hasNext())
		{
			type1 = iterator1.next();
			type2 = iterator2.next();

			if (type1 != type2)
			{
				distance += type2.calculateInheritDistance(type1);
			} // if
		} // while

		return distance;
	} // calculateDistance

	// calculateInheritDistance between two function declarations
	// used to find closest match to a function
	// if the distance is 0, it's a perfect match
	public int calculateDistance(SymbolSignatureFunction signature)
	{
		return calculateDistance(signature.getTypes());
	} // calculateDistance
} // SymbolSignatureFunction

Java:
package symboltable.signature;

import symboltable.symbol.SymbolType;

// this class will match with either a regular signature or a function signature
// useful for type resolution in typecast expression
public class SymbolSignatureFunctionType extends SymbolSignatureFunction
{
	public SymbolSignatureFunctionType()
	{
		super();
	} // SymbolSignatureFunctionType

	public SymbolSignatureFunctionType(String name, SymbolType type)
	{
		super(name, type);
	} // SymbolSignatureFunctionType

	// fuzzy equality
	@Override
	public boolean equals(Object signature)
	{
		return isSymbolSignature(signature) && signature.equals(this);
	} // equals
} // SymbolSignatureFunctionType

Java:
package symboltable.signature;

import symboltable.symbol.SymbolType;

// this is identical to SymbolSignatureFunctionType except that it is used for
// a different purpose
// the classification here must be noted
public class SymbolSignatureTypecast extends SymbolSignatureFunction
{
	public SymbolSignatureTypecast()
	{
		super();
	} // SymbolSignatureTypecast

	public SymbolSignatureTypecast(String name, SymbolType type)
	{
		super(name, type);
	} // SymbolSignatureTypecast

	public static boolean isTypecastSignature(Object signature)
	{
		return SymbolSignatureTypecast.class.isAssignableFrom(signature.getClass());
	} // isScope
} // SymbolSignatureTypecast
 
Last edited:

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,180
I think keeping signatures as a single class just is not possible due to the functionality required.

Each signature comprises of two parts. First is the definitive part which is all the signature properties which are always present and clear. This would be things like the name, number of arguments, type of signature, modifier etc. The other is the dynamic part of the signature which are all the properties which are not clear. These would be your types which hierarchy needs to be resolved. These make a great splitting point for signature functionality.

One could start with dynamic properties which require resolution. These are what would be processed for inheritance and compatibility etc. This makes the lowest level class which represents each individual signature declared. Due to the nature of this class one would want to avoid a lot of comparisons as they are non-trivial.

Then have the definitive properties. This defines the definitive part of the signature in a way that allows fast trivial comparisons. For example all the definitive properties could be used to produce a hash which can be compared for equality very easily. It also acts as a container for 0 or more dynamic properties. Methods are defined that allow one to test if one signature (in the form of a definitive property object) matches another signature (in the form of a definitive property object) and return the specific signature property which was matched. Internally the dynamic properties should be ordered from least abstract to most abstract such that the best match is found first.

Finally the signature pool container class. Here is where matching (finding) is fully defined in that you can give it a signature and it will return which signature it matches (hopefully allowing you to do something with it). This uses the definitive part of a given signature to find the definitive part of signatures inside the pool if any. This is very efficient since missing or incompatible signatures can be rejected straight away. If a match is found inside the pool you then have to search through the dynamic entries to find any possible matches.

The pool would probably come in the form of a singleton per compilation unit which is filled with all signature declarations. As a signature is encountered it then resolves it from the pool. One might or might not need to reference some form of functionality with each signature property so that you can do more than simply testing if a matching signature exists or not.
 
Status
Not open for further replies.
Top