Implementation of String.prototype.replace

Question

With just a brief look over I can think of a large amount of changes that would improve the clarity but I would love to see how someone else would refactor this mess.

Spec

Spec

Code

static Func<string, RegExpParser.MatchState, string> MakeReplacer(string format)
{
    var tokens =
        new Regex(@"[^\$]*(\$[\$&`']|\$\d{1,2})")
        .Matches(format)
        .Cast<Match>()
        .Select(m => (Capture)m.Groups[1])
        .ToList();

    if (tokens.Count == 0)
    {
        return (value, state) => format;
    }

    var appendMethod = typeof(StringBuilder).GetMethod("Append", new[] { typeof(string) });
    var toStringMethod = typeof(StringBuilder).GetMethod("ToString", new Type[0]);
    var substringMethod = typeof(string).GetMethod("Substring", new[] { typeof(int) });
    var substringWithLengthMethod = typeof(string).GetMethod("Substring", new[] { typeof(int), typeof(int) });
    var zero = Expression.Constant(0);
    var one = Expression.Constant(1);
    var dollarSign = Expression.Constant("$");
    var valueVariable = Expression.Parameter(typeof(string), "value");
    var stateVariable = Expression.Parameter(typeof(RegExpParser.MatchState), "state");
    var sbVariable = Expression.Variable(typeof(StringBuilder), "sb");
    var capturesProp = Expression.Property(stateVariable, "captures");
    var capturesLengthProp = Expression.Property(capturesProp, "Length");
    var endIndexProp = Expression.Property(stateVariable, "endIndex");
    var inputProp = Expression.Property(stateVariable, "input");
    var appendDollarSign = Expression.Call(sbVariable, appendMethod, Expression.Constant("$"));
    var getMatchedSubstring = Expression.ArrayIndex(capturesProp, zero);
    var appendMatchedSubstring = Expression.Call(sbVariable, appendMethod, getMatchedSubstring);
    var getBeforeSubstring = Expression.Call(inputProp, substringWithLengthMethod, zero, Expression.Subtract(endIndexProp, one));
    var appendBeforeSubstring = Expression.Call(sbVariable, appendMethod, getBeforeSubstring);
    var getAfterSubstring = Expression.Call(inputProp, substringMethod, endIndexProp);
    var appendAfterSubstring = Expression.Call(sbVariable, appendMethod, getAfterSubstring);
    var e = (Expression)Expression.New(typeof(StringBuilder));
    var index = 0;

    foreach (var token in tokens)
    {
        if (token.Index > 0)
        {
            e = Expression.Call(e, appendMethod, Expression.Constant(format.Substring(index, token.Index - index)));                   
        }
        index = token.Index + token.Length;
        if (token.Value == "$$")
        {
            e = Expression.Call(e, appendMethod, dollarSign);
        }
        else if (token.Value == "$&")
        {
            e = Expression.Call(e, appendMethod, valueVariable);
        }
        else if (token.Value == "$`")
        {
            e = Expression.Call(e, appendMethod, getBeforeSubstring);
        }
        else if (token.Value == "$'")
        {
            e = Expression.Call(e, appendMethod, getAfterSubstring);
        }
        else
        {
            var n = token.Value.Substring(1);
            if (n.Length == 2 && n[0] == '0')
            {
                n = n.Substring(1);
            }
            var i = int.Parse(n) - 1;
            var nConst = Expression.Constant(i);
            var t = Expression.Constant(token.Value);
            if (i < 0)
            {
                e = Expression.Call(e, appendMethod, t);  
            }
            else
            {
                var cond =
                    Expression.Condition(
                        Expression.GreaterThan(
                            capturesLengthProp,
                            nConst
                        ),
                        Expression.ArrayIndex(capturesProp, nConst),
                        t                                
                    );
                e = Expression.Call(e, appendMethod, cond);  
            }
        }
    }

    e = Expression.Call(e, toStringMethod);
    var lambda = Expression.Lambda<Func<string, RegExpParser.MatchState, string>>(e, valueVariable, stateVariable);
    return lambda.Compile();
}

IDynamic Replace(IEnvironment environment, IArgs args)
{
    var o = environment.Context.ThisBinding;
    var so = o.ConvertToString();
    var s = so.BaseValue;
    var matches = new List<Tuple<int, int, Func<string, string>>>();
    var searchValueArg = args[0];
    var replaceValueArg = args[1];
    var replaceValueFunc = replaceValueArg as ICallable;
    var replaceValueString = replaceValueArg.ConvertToString();

    if (searchValueArg is NRegExp)
    {
        var regExpObj = (NRegExp)searchValueArg;
        var matcher = regExpObj.RegExpMatcher;

        Func<int, RegExpParser.MatchState, Func<string, string>> makeReplacer = null;

        if (replaceValueFunc != null)
        {
            makeReplacer =
                (startIndex, state) =>
                    _ =>
                    {
                        var nullArg = (IDynamic)environment.Null;
                        var cArgs = new List<IDynamic>();
                        foreach (var c in state.captures)
                        {
                            if (c == null)
                            {
                                cArgs.Add(environment.Null);
                                continue;
                            }
                            cArgs.Add(c == null ? nullArg : environment.CreateString(c));
                        }
                        cArgs.Add(environment.CreateNumber(startIndex));
                        cArgs.Add(so);
                        var result = 
                            replaceValueFunc.Call(
                                environment, 
                                environment.Undefined, 
                                environment.CreateArgs(cArgs)
                            );
                        return result.ConvertToString().BaseValue;
                    };
        }
        else
        {
            var replacer = MakeReplacer(replaceValueString.BaseValue);
            makeReplacer =
                (_, state) =>
                    v => replacer(v, state);
        }

        if (!regExpObj.Flags.Contains("g"))
        {
            var index = 0;
            do
            {
                var r = matcher(s, index);
                if (!r.success)
                {
                    index++;
                    continue;
                }
                matches.Add(
                    Tuple.Create(
                        index,
                        r.matchState.endIndex - index,
                        makeReplacer(index, r.matchState)
                    )
                );
                break;
            } while (index < s.Length);
        }
        else
        {
            var index = (int)regExpObj.Get("lastIndex").ConvertToNumber().BaseValue;
            do
            {
                var r = matcher(s, index);
                if (!r.success)
                {
                    index++;
                    continue;
                }
                matches.Add(
                    Tuple.Create(
                        index,
                        r.matchState.endIndex - index,
                        makeReplacer(index, r.matchState)                                
                    )
                );
                index = r.matchState.endIndex;
                regExpObj.Put("lastIndex", environment.CreateNumber(index), false);
            } while (index < s.Length);
        }
    }
    else
    {
        Func<string, string> replace = null;

        if (replaceValueFunc == null)
        {
            replace =  _ => replaceValueString.BaseValue;
        }
        else
        {
            replace = 
                v =>
                {
                    var arg = environment.CreateString(v);
                    var result =
                        replaceValueFunc.Call(
                            environment,
                            environment.Undefined,
                            environment.CreateArgs(new[] { arg })
                        );
                    return result.ConvertToString().BaseValue;
                };
        }

        var searchValue = args[0].ConvertToString().BaseValue;
        var index = 0;

        do
        {
            var resultIndex = s.IndexOf(searchValue, index);
            if (resultIndex < 0)
            {
                index++;
                continue;
            }
            matches.Add(
                Tuple.Create<int, int, Func<string, string>>(
                    resultIndex, 
                    searchValue.Length,
                    replace
                )
            );
            index = resultIndex + 1;
        } while (index < s.Length);
    }

    if (matches.Count == 0)
        return so;

    var sb = new StringBuilder();
    var i = 0;
    foreach (var match in matches)
    {
        if (match.Item1 > 0) 
            sb.Append(s.Substring(i, match.Item1 - i));
        sb.Append(match.Item3(s.Substring(match.Item1, match.Item2)));
        i = match.Item1 + match.Item2;
    }
    if (i < s.Length)
        sb.Append(s.Substring(i));
    return environment.CreateString(sb.ToString());                
}

Timwi · Accepted Answer · 2011-04-08 02:17:02Z

My first instinct was “why do you construct all these expressions, only to compile it and return just the function — why not just use lambdas directly”... but after a second thought it seems that this wouldn’t be any clearer at all, so I think using expressions here is actually really nice :)

Things I notice that could be improved:

Instead of

var tokens =
    new Regex(@"[^\$]*(\$[\$&`']|\$\d{1,2})")
    .Matches(format)
    .Cast<Match>()
    .Select(m => (Capture)m.Groups[1])
    .ToList();

I think you could write

var items =
    Regex.Matches(format, @"([^\$]*)(\$[\$&`']|\$\d{1,2})")
    .Cast<Match>()
    .Select(m => new { TextBefore = m.Groups[1].Value,
                       Token = m.Groups[2].Value });

Notice that I’ve changed the Regex object instantiation to a static method call; it makes little difference, I just think it’s more readable. I’ve also removed the call to ToList() because it seems you are only iterating over it, you are not manipulating the list, so there is no need for this extra list instantiation.

Now you don’t need to care about the index anymore and can get rid of that variable:

foreach (var item in items)
{
    if (item.TextBefore.Length > 0)
    {
        e = Expression.Call(e, appendMethod, Expression.Constant(item.TextBefore));
    }

    // ... etc.

The next thing I notice is:

var n = token.Value.Substring(1);
if (n.Length == 2 && n[0] == '0')
{
    n = n.Substring(1);
}
var i = int.Parse(n) - 1;

You don’t need to remove the leading zero. It’s not going to throw int.Parse off (it doesn’t make it mean octal if that’s what you thought). So you can just write:

var i = int.Parse(item.Token.Substring(1)) - 1;

That’s all I notice in the first method. I cannot claim to fully understand the code that makes use of RegExpParser.MatchState, but it looks clean, if that means anything :)

As for the second method...

var nullArg = (IDynamic)environment.Null;
var cArgs = new List<IDynamic>();
foreach (var c in state.captures)
{
    if (c == null)
    {
        cArgs.Add(environment.Null);
        continue;
    }
    cArgs.Add(c == null ? nullArg : environment.CreateString(c));
}

Is it just me, or is all of that just a roundabout way of saying

var cArgs = state.captures
                 .Select(c => c == null ? (IDynamic)environment.Null
                                        : environment.CreateString(c))
                 .ToList();

Having too many local variables that are used only once does not always improve readability. The reader cannot tell instantly that the variable is used only once, so it is not obvious which variables they need to keep in their head while reading. This is why I inlined nullArg. If you disagree, of course you can change it back to a local variable.

In the if (!regExpObj.Flags.Contains("g")) block you seem to have a bit of duplicated code. It seems to me that it can easily be refactored:

var globalFlag = regExpObj.Flags.Contains("g");
var index = globalFlag ? (int)regExpObj.Get("lastIndex").ConvertToNumber().BaseValue : 0;
do
{
    var r = matcher(s, index);
    if (!r.success)
    {
        index++;
        continue;
    }
    matches.Add(
        Tuple.Create(
            index,
            r.matchState.endIndex - index,
            makeReplacer(index, r.matchState)
        )
    );

    if (!globalFlag)
        break;

    index = r.matchState.endIndex;
    regExpObj.Put("lastIndex", environment.CreateNumber(index), false);
}
while (index < s.Length);

Looking at it again, however, I’m beginning to wonder why you are populating this matches list; you are not returning it or otherwise passing it anywhere. It seems that you actually only need the resulting string, not the list of matches, right? If that is the case, then personally I would probably just generate the string and not bother with the list of matches. That also gets rid of the problem I see of using tuples: the names Item1, Item2, Item3 are really not very readable.

Also, this is a significant performance problem:

var resultIndex = s.IndexOf(searchValue, index);
if (resultIndex < 0)
{
    index++;
    continue;
}

You are searching the same string for the same substring many times even when you know it’s not there. If resultIndex < 0 you can stop:

var resultIndex = s.IndexOf(searchValue, index);
if (resultIndex < 0)
    break;

The same may apply to the regex-matching part of the block depending on what matcher does. If it only matches a regular expression anchored to the beginning of the string, then of course your existing code is correct. If it matches anywhere in the string, the same optimisation should be made there.

I believe this is a serious bug:

index = resultIndex + 1;

I think you want this to say

index = resultIndex + searchValue.Length;

Imagine the client wants to replace all instances of aa with x and the input string contains aaaa. If I read the code at the end correctly (the code that uses Item1/Item2/Item3 a lot), it would throw because you would be passing a negative value into Substring.

That’s all I could find that I would change if I had to maintain the code.

Talk about a thorough code review. To be honest I was not expecting anything this good. Thanks. Just in case you were curious (Shameless plug for my project: github.com/ChaosPandion/Machete) — ChaosPandion
– ChaosPandion, Commented Apr 8, 2011 at 15:35
I just posted my latest version of the code with your suggestions and it is really turning out well. Thanks again. — ChaosPandion
– ChaosPandion, Commented Apr 8, 2011 at 20:19

Stack Exchange Network

Implementation of String.prototype.replace

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Implementation of String.prototype.replace

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions