Index: trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/commands/CMDparseXML.java =================================================================== --- trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/commands/CMDparseXML.java (revision 412) +++ trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/commands/CMDparseXML.java (revision 413) @@ -9,4 +9,5 @@ import de.ugoe.cs.eventbench.data.GlobalDataContainer; import de.ugoe.cs.eventbench.windows.MFCLogParser; +import de.ugoe.cs.eventbench.windows.data.MFCTargetComparator; import de.ugoe.cs.eventbench.windows.data.WindowTree; import de.ugoe.cs.eventbench.windows.data.WindowsEvent; @@ -63,4 +64,16 @@ Collection> sequences = parser.getSequences(); + + Console.traceln("Pre-computing event target equalities."); + // compare all Events to a dummy event to make sure they are known by + // the MFCTargetComparator + WindowsEvent dummyEvent = new WindowsEvent("dummy"); + for (List sequence : sequences) { + for (WindowsEvent event : sequence) { + event.equals(dummyEvent); + } + } + MFCTargetComparator.setMutable(false); + SortedSet targets = WindowTree.getInstance().getTargets(); Index: trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/data/MFCTargetComparator.java =================================================================== --- trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/data/MFCTargetComparator.java (revision 413) +++ trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/data/MFCTargetComparator.java (revision 413) @@ -0,0 +1,412 @@ +package de.ugoe.cs.eventbench.windows.data; + +import java.io.ByteArrayInputStream; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import javax.xml.parsers.DocumentBuilder; +import javax.xml.parsers.DocumentBuilderFactory; + +import org.apache.commons.collections15.CollectionUtils; +import org.w3c.dom.Document; +import org.w3c.dom.Element; +import org.w3c.dom.NodeList; + +/** + *

+ * This class implements a comparator for target strings of MFC GUIs. It + * internally maintains a collection of all targets that have been compared to + * ensure the transitivity of the equals relation. This memory can always be + * deleted by calling {@link #reset()}. + *

+ * + * @author Steffen Herbold + * @version 1.0 + */ +public class MFCTargetComparator { + + /** + *

+ * If mutable is true, new target strings can be added to the internal + * memory. This leads to a very expensive {@link #compare(String, String)} + * operation. + *

+ *

+ * if mutable is set to false, currently possible equal targets are + * pre-computed. This pre-computation is expensive and might take a while. + * In turn, the {@link #compare(String, String)} operation becomes very + * cheap. + *

+ */ + private static boolean mutable = true; + + /** + *

+ * Set of all currently known targets. + *

+ */ + private static Set knownTargets = new LinkedHashSet(); + + /** + *

+ * Map that contains for all known target strings all equal target strings. + * Pre-computed when {@link #mutable} is set to false. + *

+ */ + private static Map> equalTargets; + + /** + *

+ * Changes the mutability of the comparator. If the mutability is changed + * from true to false, the map {@link #equalTargets} is computed. + *

+ * + * @param mutable + * new mutability of the comparator + */ + public static void setMutable(boolean mutable) { + if (MFCTargetComparator.mutable == true && mutable == false) { + equalTargets = new HashMap>(); + for (String target1 : knownTargets) { + Set curEqualTargets = new HashSet(); + for (String target2 : knownTargets) { + if (compare(target1, target2)) { + curEqualTargets.add(target2); + } + } + equalTargets.put(target1, curEqualTargets); + } + } + MFCTargetComparator.mutable = mutable; + } + + /** + *

+ * Compares to target strings. The strings are equal, if TODO + *

    + *
  • the class, resourceId, and modality of all widgets are equal
    • + *
  • either the name or the hashCode of all widgets are equal
    • + *
  • either the name or the hashCode has been observed in one equal + * instance of a widget, for all widgets.
    • + *
+ *

+ *

+ * All target strings are remembered internally, to be able to test for the + * third property. + *

+ * + * @param target1 + * first target string + * @param target2 + * second target string + * @return true, if both targets are equal; false otherwise + */ + public static boolean compare(String target1, String target2) { + boolean result = false; + if (mutable) { + try { + MFCWidget widget1 = null; + MFCWidget widget2 = null; + if (!"dummy".equals(target1)) { + instance.addTarget(target1); + knownTargets.add(target1); + widget1 = instance.find(target1); + } + if (!"dummy".equals(target2)) { + instance.addTarget(target2); + knownTargets.add(target2); + widget2 = instance.find(target2); + } + if (widget1 == null) { + return false; + } + result = (widget1 == widget2); + } catch (Exception e) { + e.printStackTrace(); + } + } + + if (!mutable) { + Set curEquals = equalTargets.get(target1); + if (curEquals != null) { + result = curEquals.contains(target2); + } + } + + return result; + } + + /** + *

+ * Resets the internal memory of targets. + *

+ */ + public static void reset() { + instance = new MFCTargetComparator(); + } + + /** + *

+ * Internal handle to the instance of this class (implemented as + * Singleton!). + *

+ */ + private static MFCTargetComparator instance = new MFCTargetComparator(); + + /** + *

+ * Private Constructor. Creates a new instance of the class and prevents + * instantiation from outside of this class. + *

+ */ + private MFCTargetComparator() { + } + + /** + *

+ * List of the root widgets found in the target string. + *

+ */ + private List rootWidgets = new ArrayList(); + + /** + *

+ * Adds a target to the memory. + *

+ * + * @param target + * target to be added + */ + private void addTarget(String target) throws Exception { + if (target != null) { + DocumentBuilder documentBuilder = DocumentBuilderFactory + .newInstance().newDocumentBuilder(); + Document doc = documentBuilder.parse(new ByteArrayInputStream( + ("" + target + "").getBytes("UTF-8"))); + doc.getDocumentElement().normalize(); + NodeList widgets = doc.getElementsByTagName("window"); + + MFCWidget parent = null; + for (int i = 0; i < widgets.getLength(); i++) { + Element currentWidget = (Element) widgets.item(i); + parent = addWidget(currentWidget, parent); + } + } + } + + /** + *

+ * Adds a widget extracted from a target to the memory. The widget is placed + * as a child/parent of other widget according to the GUI hierarchy of the + * application. + *

+ *

+ * In case the widget already exists, the existing widget is returned and + * the known targets and hashCodes of the existing widget are updated. + *

+ * + * @param widgetString + * string identifying the widget + * @param parent + * parent widget; if null, it is a root widget and added to + * {@link #rootWidgets} + * @return the created widget. + */ + private MFCWidget addWidget(Element widgetElement, MFCWidget parent) { + MFCWidget widget = generateWidget(widgetElement); + + if (parent == null) { + int index = rootWidgets.indexOf(widget); + if (index >= 0) { + widget = rootWidgets.get(index); + widget.names.add(widgetElement.getAttribute("name")); + widget.hwnds.add(widgetElement.getAttribute("hwnd")); + } else { + rootWidgets.add(widget); + } + } else { + int index = parent.children.indexOf(widget); + if (index >= 0) { + widget = parent.children.get(index); + widget.names.add(widgetElement.getAttribute("name")); + widget.hwnds.add(widgetElement.getAttribute("hwnd")); + } else { + parent.children.add(widget); + } + } + return widget; + } + + /** + *

+ * Creates a new {@link MFCWidget} from a widget XML element. + *

+ * + * @param widgetElement + * XML element containing information about the widget + * @return created {@link MFCWidget} + */ + private MFCWidget generateWidget(Element widgetElement) { + MFCWidget widget = new MFCWidget(); + widget.names.add(widgetElement.getAttribute("name")); + widget.hwnds.add(widgetElement.getAttribute("hwnd")); + widget.widgetClass = widgetElement.getAttribute("class"); + widget.resourceId = widgetElement.getAttribute("resourceId"); + widget.modality = widgetElement.getAttribute("isModal"); + return widget; + } + + /** + *

+ * Tries to find the {@link MFCWidget} that the target string identifies in + * the known GUI hierarchy, by traversing the known widgets starting with + * the {@link #rootWidgets}. + * + * @param target + * target string whose widget is searched for + * @return respective {@link MFCWidget} instance if it is found; null + * otherwise + */ + private MFCWidget find(String target) throws Exception { + MFCWidget widget = null; + if (target != null) { + DocumentBuilder documentBuilder = DocumentBuilderFactory + .newInstance().newDocumentBuilder(); + Document doc = documentBuilder.parse(new ByteArrayInputStream( + ("" + target + "").getBytes("UTF-8"))); + doc.getDocumentElement().normalize(); + NodeList widgets = doc.getElementsByTagName("window"); + + MFCWidget parent = null; + for (int i = 0; i < widgets.getLength(); i++) { + Element currentWidget = (Element) widgets.item(i); + MFCWidget generatedWidget = generateWidget(currentWidget); + if (parent == null) { + int index = rootWidgets.indexOf(generatedWidget); + if (index >= 0) { + parent = rootWidgets.get(index); + } else { + return null; + } + } else { + int index = parent.children.indexOf(generatedWidget); + if (index >= 0) { + parent = parent.children.get(index); + } else { + return null; + } + } + } + widget = parent; + } + return widget; + } + + /** + *

+ * Internal class used to store MFCWidget. The implementation is more like a + * C-style structure, than an actual class. + *

+ * + * @author Steffen Herbold + * @version 1.0 + */ + private static class MFCWidget { + + /** + *

+ * Set of all known name strings of the widget. + *

+ */ + Set names = new LinkedHashSet(); + + /** + *

+ * Set of all known hwnds of the widget. + *

+ */ + Set hwnds = new LinkedHashSet(); + + /** + *

+ * Class of the widget. + *

+ */ + String widgetClass; + + /** + *

+ * Resource id of the widget. + *

+ */ + String resourceId; + + /** + *

+ * Modality of the widget. + *

+ */ + String modality; + + /** + *

+ * Pre-computed hash code of the widget. + *

+ */ + int hashCode = 0; + + /** + *

+ * List of children of the widget. + *

+ */ + List children = new ArrayList(); + + /** + *

+ * Two widgets are equal, if {@link #widgetClass}, {@link #resourceId}, + * and {@link #modality} are equal and the intersection of either the + * {@link #hwnds}, the {@link #names}, or both of them is not empty. + *

+ * + * @see java.lang.Object#equals(java.lang.Object) + */ + @Override + public boolean equals(Object obj) { + if (obj instanceof MFCWidget) { + MFCWidget other = (MFCWidget) obj; + boolean titleEqual = CollectionUtils.containsAny(names, + other.names); + boolean hashEqual = CollectionUtils.containsAny(hwnds, + other.hwnds); + + return widgetClass.equals(other.widgetClass) + && resourceId.equals(other.resourceId) + && modality.equals(other.modality) + && (titleEqual || hashEqual); + } + return false; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + if (hashCode == 0) { + int multiplier = 17; + hashCode = multiplier * hashCode + widgetClass.hashCode(); + hashCode = multiplier * hashCode + resourceId.hashCode(); + hashCode = multiplier * hashCode + modality.hashCode(); + } + return hashCode; + } + } +} Index: trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/data/WindowsEvent.java =================================================================== --- trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/data/WindowsEvent.java (revision 412) +++ trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/windows/data/WindowsEvent.java (revision 413) @@ -1,3 +1,12 @@ package de.ugoe.cs.eventbench.windows.data; + +import java.io.ByteArrayInputStream; + +import javax.xml.parsers.DocumentBuilder; +import javax.xml.parsers.DocumentBuilderFactory; + +import org.w3c.dom.Document; +import org.w3c.dom.Element; +import org.w3c.dom.NodeList; import de.ugoe.cs.eventbench.data.ReplayableEvent; @@ -33,3 +42,45 @@ } + @Override + protected boolean targetEquals(String otherTarget) { + return MFCTargetComparator.compare(target, otherTarget); + } + + int targetHash = 0; + + @Override + protected int targetHashCode() { + if( targetHash==0 ) { + int multiplier = 17; + if (target != null) { + Document doc; + try { + DocumentBuilder documentBuilder = DocumentBuilderFactory + .newInstance().newDocumentBuilder(); + doc = documentBuilder.parse(new ByteArrayInputStream( + ("" + target + "").getBytes("UTF-8"))); + } catch (Exception e) { + e.printStackTrace(); + return 0; + } + doc.getDocumentElement().normalize(); + NodeList widgets = doc.getElementsByTagName("window"); + + for (int i = 0; i < widgets.getLength(); i++) { + Element currentWidget = (Element) widgets.item(i); + targetHash = targetHash* multiplier + widgetHashCode(currentWidget); + } + } + } + return targetHash; + } + + private int widgetHashCode(Element currentWidget) { + int hashCode = 0; + int multiplier = 41; + hashCode = hashCode * multiplier + currentWidget.getAttribute("class").hashCode(); + hashCode = hashCode * multiplier + currentWidget.getAttribute("resourceId").hashCode(); + hashCode = hashCode * multiplier + currentWidget.getAttribute("isModal").hashCode(); + return hashCode; + } }