Author: etnu
Date: Wed Nov 19 15:10:26 2008
New Revision: 719122

URL: http://svn.apache.org/viewvc?rev=719122&view=rev
Log:
Dramatically improved performance of variable substitution code. In the 
included benchmark, this code executes in roughly 20% of the time taken by the 
old version.

There is a minor semantic change introduced here, which is that all 
substitutions will now be performed when calling substituteXxx. This is the 
same as calling substituteXxx(null, input) in the old code.


Modified:
    
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Icon.java
    
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/LinkSpec.java
    
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/ModulePrefs.java
    
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Preload.java
    
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/UserPref.java
    
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/View.java
    
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/variables/Substitutions.java
    
incubator/shindig/trunk/java/gadgets/src/test/java/org/apache/shindig/gadgets/variables/SubstitutionsTest.java

Modified: 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Icon.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Icon.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Icon.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Icon.java
 Wed Nov 19 15:10:26 2008
@@ -65,8 +65,7 @@
    */
   public Icon substitute(Substitutions substituter) {
     Icon icon = new Icon(this);
-    icon.content
-        = substituter.substituteString(Substitutions.Type.MESSAGE, content);
+    icon.content = substituter.substituteString(content);
     return icon;
   }
 

Modified: 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/LinkSpec.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/LinkSpec.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/LinkSpec.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/LinkSpec.java
 Wed Nov 19 15:10:26 2008
@@ -43,9 +43,9 @@
   }
 
   private LinkSpec(LinkSpec rhs, Substitutions substitutions) {
-    rel = substitutions.substituteString(null, rhs.rel);
+    rel = substitutions.substituteString(rhs.rel);
     base = rhs.base;
-    href = base.resolve(substitutions.substituteUri(null, rhs.href));
+    href = base.resolve(substitutions.substituteUri(rhs.href));
   }
 
   /**

Modified: 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/ModulePrefs.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/ModulePrefs.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/ModulePrefs.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/ModulePrefs.java
 Wed Nov 19 15:10:26 2008
@@ -146,7 +146,7 @@
     Map<String, String> attributes
         = new HashMap<String, String>(prefs.attributes.size());
     for (Map.Entry<String, String> attr : prefs.attributes.entrySet()) {
-      String substituted = substituter.substituteString(null, attr.getValue());
+      String substituted = substituter.substituteString(attr.getValue());
       attributes.put(attr.getKey(), substituted);
     }
     this.attributes = Collections.unmodifiableMap(attributes);

Modified: 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Preload.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Preload.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Preload.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/Preload.java
 Wed Nov 19 15:10:26 2008
@@ -89,10 +89,10 @@
     auth = preload.auth;
     signOwner = preload.signOwner;
     signViewer = preload.signViewer;
-    href = base.resolve(substituter.substituteUri(null, preload.href));
+    href = base.resolve(substituter.substituteUri(preload.href));
     Map<String, String> attributes = Maps.newHashMap();
     for (Map.Entry<String, String> entry : preload.attributes.entrySet()) {
-      attributes.put(entry.getKey(), substituter.substituteString(null, 
entry.getValue()));
+      attributes.put(entry.getKey(), 
substituter.substituteString(entry.getValue()));
     }
     this.attributes = Collections.unmodifiableMap(attributes);
   }

Modified: 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/UserPref.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/UserPref.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/UserPref.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/UserPref.java
 Wed Nov 19 15:10:26 2008
@@ -37,7 +37,7 @@
    * [EMAIL PROTECTED]
    * Message bundles
    */
-  private String name;
+  private final String name;
   public String getName() {
     return name;
   }
@@ -86,7 +86,7 @@
   public Map<String, String> getEnumValues() {
     return enumValues;
   }
-  
+
   /**
    * UserPref.EnumValue (ordered)
    * Useful for rendering ordered lists of user prefs with enum type.
@@ -105,17 +105,14 @@
    */
   public UserPref substitute(Substitutions substituter) {
     UserPref pref = new UserPref(this);
-    Substitutions.Type type = Substitutions.Type.MESSAGE;
-    pref.displayName = substituter.substituteString(type, displayName);
-    pref.defaultValue = substituter.substituteString(type, defaultValue);
+    pref.displayName = substituter.substituteString(displayName);
+    pref.defaultValue = substituter.substituteString(defaultValue);
     if (enumValues.isEmpty()) {
       pref.enumValues = Collections.emptyMap();
     } else {
-      Map<String, String> values
-          = new HashMap<String, String>(enumValues.size());
+      Map<String, String> values = new HashMap<String, 
String>(enumValues.size());
       for (Map.Entry<String, String> entry : enumValues.entrySet()) {
-        values.put(entry.getKey(),
-            substituter.substituteString(type, entry.getValue()));
+        values.put(entry.getKey(), 
substituter.substituteString(entry.getValue()));
       }
       pref.enumValues = Collections.unmodifiableMap(values);
     }
@@ -126,7 +123,7 @@
           = new LinkedList<EnumValuePair>();
       for (EnumValuePair evp : orderedEnumValues) {
         orderedValues.add(new EnumValuePair(evp.getValue(),
-            substituter.substituteString(type, evp.getDisplayValue())));
+            substituter.substituteString(evp.getDisplayValue())));
       }
       pref.orderedEnumValues = Collections.unmodifiableList(orderedValues);
     }
@@ -236,7 +233,7 @@
       return STRING;
     }
   }
-  
+
   /**
    * Simple data structure representing a value/displayValue pair
    * for UserPref enums. Value is [EMAIL PROTECTED], and DisplayValue is 
[EMAIL PROTECTED]
@@ -244,16 +241,16 @@
   public static class EnumValuePair {
     private final String value;
     private final String displayValue;
-    
+
     private EnumValuePair(String value, String displayValue) {
       this.value = value;
       this.displayValue = displayValue;
     }
-    
+
     public String getValue() {
       return value;
     }
-    
+
     public String getDisplayValue() {
       return displayValue;
     }

Modified: 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/View.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/View.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/View.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/spec/View.java
 Wed Nov 19 15:10:26 2008
@@ -129,12 +129,12 @@
     signOwner = view.signOwner;
     signViewer = view.signViewer;
 
-    content = substituter.substituteString(null, view.content);
+    content = substituter.substituteString(view.content);
     base = view.base;
-    href = base.resolve(substituter.substituteUri(null, view.href));
+    href = base.resolve(substituter.substituteUri(view.href));
     Map<String, String> attributes = Maps.newHashMap();
     for (Map.Entry<String, String> entry : view.attributes.entrySet()) {
-      attributes.put(entry.getKey(), substituter.substituteString(null, 
entry.getValue()));
+      attributes.put(entry.getKey(), 
substituter.substituteString(entry.getValue()));
     }
     this.attributes = Collections.unmodifiableMap(attributes);
   }

Modified: 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/variables/Substitutions.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/variables/Substitutions.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/variables/Substitutions.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/main/java/org/apache/shindig/gadgets/variables/Substitutions.java
 Wed Nov 19 15:10:26 2008
@@ -19,8 +19,8 @@
 
 import org.apache.shindig.common.uri.Uri;
 
-import java.util.EnumMap;
-import java.util.HashMap;
+import com.google.common.collect.Maps;
+
 import java.util.Map;
 
 /**
@@ -28,11 +28,11 @@
  * variables.
  */
 public class Substitutions {
-
   /**
    * Defines all of the valid types of message substitutions.
-   * Note: Order is important here, since the order of the enum is the
-   * order of evaluation. Don't change this unless you know what you're doing.
+   *
+   * NOTE: Order is critical here, since substitutions are only recursive on 
nodes with lower order
+   * this is to prevent infinite recursion in substitution logic.
    */
   public enum Type {
     /**
@@ -55,7 +55,7 @@
      */
     MODULE("MODULE");
 
-    private String prefix;
+    private final String prefix;
 
     /**
      * Creates a Type with the specified prefix.
@@ -64,26 +64,17 @@
      *        The placeholder prefix for substituted strings.
      */
     Type(String prefix) {
-      this.prefix = "__" + prefix + '_';
-    }
-
-    public String getPrefix() {
-      return prefix;
+      this.prefix = "__" + prefix +  "_";
     }
   }
 
-  private Map<Type, Map<String, String>> substitutions =
-      new EnumMap<Type, Map<String, String>>(Type.class);
+  private final Map<String, String> substitutions;
 
-  /**
-   * Create a basic substitution coordinator.
-   */
   public Substitutions() {
-    for (Type type : Type.values()) {
-      substitutions.put(type, new HashMap<String, String>());
-    }
+    substitutions = Maps.newHashMap();
   }
 
+
   /**
    * Adds a new substitution for the given type.
    *
@@ -92,7 +83,14 @@
    * @param value
    */
   public void addSubstitution(Type type, String key, String value) {
-    substitutions.get(type).put(key, value);
+    substitutions.put(type.prefix + key + "__", value);
+  }
+
+  /**
+   * @return The value stored for the given type and key, or null.
+   */
+  public String getSubstitution(Type type, String key) {
+    return substitutions.get(type.prefix + key + "__");
   }
 
   /**
@@ -102,87 +100,74 @@
    * @param entries
    */
   public void addSubstitutions(Type type, Map<String, String> entries) {
-    substitutions.get(type).putAll(entries);
+    for (Map.Entry<String, String> entry : entries.entrySet()) {
+      addSubstitution(type, entry.getKey(), entry.getValue());
+    }
   }
 
-  /**
-   * @param type
-   * @param name
-   * @return The substitution set under the given type / name, or null.
-   */
-  public String getSubstitution(Type type, String name) {
-    return substitutions.get(type).get(name);
+  private void performSubstitutions(String input, StringBuilder output, 
boolean isNested) {
+    int lastPosition = 0, i;
+    while ((i = input.indexOf("__", lastPosition)) != -1) {
+      int next = input.indexOf("__", i + 2);
+      if (next == -1) {
+        // No matches, we're done.
+        break;
+      }
+
+      output.append(input.substring(lastPosition, i));
+      lastPosition = next + 2;
+
+      String pattern = input.substring(i, lastPosition);
+
+      boolean isMessage = pattern.startsWith(Type.MESSAGE.prefix);
+      String replacement;
+      if (isMessage && isNested) {
+        replacement = pattern;
+      } else {
+        replacement = substitutions.get(pattern);
+      }
+
+      if (replacement == null) {
+        // Keep it.
+        output.append(pattern);
+      } else  if (isMessage && !isNested) {
+        // Messages can get recursive
+        performSubstitutions(replacement, output, true);
+      } else {
+        output.append(replacement);
+      }
+    }
+
+    output.append(input.substring(lastPosition));
   }
 
   /**
    * Performs string substitution only for the specified type. If no
    * substitution for [EMAIL PROTECTED] input} was provided or [EMAIL 
PROTECTED] input} is null,
    * the output is left untouched.
-   *
-   * @param type
-   *        The type you wish to perform substitutions for.
-   * @param input
-   *        The base string, with substitution markers.
+   * @param input The base string, with substitution markers.
    * @return The substituted string.
    */
-  public String substituteString(Type type, String input) {
-    if (input == null) {
-      return null;
+  public String substituteString(String input) {
+    if (input.contains("__")) {
+      StringBuilder output = new StringBuilder(input.length() * 120 / 100);
+      performSubstitutions(input, output, false);
+      return output.toString();
     }
-
-    if (type == null) {
-      for (Type t : Type.values()) {
-        input = substituteString(t, input);
-      }
-      return input;
-    }
-
-    if (substitutions.get(type).isEmpty() || !input.contains(type.prefix)) {
-      return input;
-    }
-
-    StringBuilder output = new StringBuilder();
-    for (int i = 0, j = input.length(); i < j; ++i) {
-      if (input.regionMatches(i, type.prefix, 0, type.prefix.length())) {
-        // Look for a trailing "__". If we don't find it, then this isn't a
-        // properly formed substitution.
-        int start = i + type.prefix.length();
-        int end = input.indexOf("__", start);
-        if (end != -1) {
-          String name = input.substring(start, end);
-          String replacement = substitutions.get(type).get(name);
-          if (replacement != null) {
-            output.append(replacement);
-          } else {
-            output.append(input.substring(i, end + 2));
-          }
-          i = end + 1;
-        } else {
-          // If we didn't find any occurances of "__", then the rest of the
-          // string can't contain any more valid translations.
-          output.append(input.substring(i));
-          break;
-        }
-      } else {
-        output.append(input.charAt(i));
-      }
-    }
-
-    return output.toString();
+    return input;
   }
 
   /**
    * Substitutes a uri
-   * @param type The type to substitute, or null for all types.
    * @param uri
    * @return The substituted uri, or a dummy value if the result is invalid.
    */
-  public Uri substituteUri(Type type, Uri uri) {
+  public Uri substituteUri(Uri uri) {
     if (uri == null) {
       return null;
     }
     try {
-      return Uri.parse(substituteString(type, uri.toString()));
+      return Uri.parse(substituteString(uri.toString()));
     } catch (IllegalArgumentException e) {
       return Uri.parse("");
     }

Modified: 
incubator/shindig/trunk/java/gadgets/src/test/java/org/apache/shindig/gadgets/variables/SubstitutionsTest.java
URL: 
http://svn.apache.org/viewvc/incubator/shindig/trunk/java/gadgets/src/test/java/org/apache/shindig/gadgets/variables/SubstitutionsTest.java?rev=719122&r1=719121&r2=719122&view=diff
==============================================================================
--- 
incubator/shindig/trunk/java/gadgets/src/test/java/org/apache/shindig/gadgets/variables/SubstitutionsTest.java
 (original)
+++ 
incubator/shindig/trunk/java/gadgets/src/test/java/org/apache/shindig/gadgets/variables/SubstitutionsTest.java
 Wed Nov 19 15:10:26 2008
@@ -18,30 +18,36 @@
  */
 package org.apache.shindig.gadgets.variables;
 
-import org.apache.shindig.gadgets.variables.Substitutions;
 import org.apache.shindig.gadgets.variables.Substitutions.Type;
 
 import junit.framework.TestCase;
 
+import org.apache.commons.lang.StringUtils;
+
 public class SubstitutionsTest extends TestCase {
-  private Substitutions subst = new Substitutions();
+  private Substitutions subst;
+
+  @Override
+  public void setUp() {
+    subst = new Substitutions();
+  }
 
   public void testMessages() throws Exception {
     String msg = "Hello, __MSG_world__!";
     subst.addSubstitution(Type.MESSAGE, "world", "planet");
-    assertEquals("Hello, planet!", subst.substituteString(null, msg));
+    assertEquals("Hello, planet!", subst.substituteString(msg));
   }
 
   public void testBidi() throws Exception {
     String msg = "Hello, __BIDI_DIR__-world!";
     subst.addSubstitution(Type.BIDI, "DIR", "rtl");
-    assertEquals("Hello, rtl-world!", subst.substituteString(null, msg));
+    assertEquals("Hello, rtl-world!", subst.substituteString(msg));
   }
 
   public void testUserPref() throws Exception {
     String msg = "__UP_hello__, world!";
     subst.addSubstitution(Type.USER_PREF, "hello", "Greetings");
-    assertEquals("Greetings, world!", subst.substituteString(null, msg));
+    assertEquals("Greetings, world!", subst.substituteString(msg));
   }
 
   public void testCorrectOrder() throws Exception {
@@ -51,8 +57,7 @@
     subst.addSubstitution(Type.BIDI, "DIR", "rtl");
     subst.addSubstitution(Type.USER_PREF, "hello", "Greetings");
     subst.addSubstitution(Type.USER_PREF, "planet", "Earth");
-    assertEquals("Greetings, planet rtl-Earth!",
-        subst.substituteString(null, msg));
+    assertEquals("Greetings, planet rtl-Earth!", subst.substituteString(msg));
   }
 
   public void testIncorrectOrder() throws Exception {
@@ -66,6 +71,32 @@
     subst.addSubstitution(Type.MESSAGE, "foo", "FOO!!!");
     subst.addSubstitution(Type.USER_PREF, "bar", "BAR!!!");
     assertEquals("Greetings __MSG_foo____UP_bar__, planet __MSG_earth__???",
-        subst.substituteString(null, msg));
+        subst.substituteString(msg));
+  }
+
+  public void loadTest() throws Exception {
+    String msg
+        = "Random text and __UP_hello__, amongst other words __MSG_world__ 
stuff __weeeeee";
+    subst.addSubstitution(Type.MESSAGE, "world",
+        "planet __MSG_earth____UP_punc__");
+    subst.addSubstitution(Type.MESSAGE, "earth", "Earth");
+    subst.addSubstitution(Type.USER_PREF, "punc", "???");
+    subst.addSubstitution(Type.USER_PREF, "hello",
+        "Greetings __MSG_foo____UP_bar__");
+    subst.addSubstitution(Type.MESSAGE, "foo", "FOO!!!");
+    subst.addSubstitution(Type.USER_PREF, "bar", "BAR!!!");
+
+    // Most real-world content contains very few substitutions.
+    msg += StringUtils.repeat("foo ", 1000);
+
+    String message = StringUtils.repeat(msg, 1000);
+
+    long now = System.nanoTime();
+    int cnt = 1000;
+    for (int i = 0; i < cnt; ++i) {
+      subst.substituteString(message);
+    }
+    long duration = System.nanoTime() - now;
+    System.out.println("Duration: " + duration + " avg: " + duration / cnt);
   }
 }


Reply via email to