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);
}
}