3
\$\begingroup\$

I have a simple program that "minimizes" a file path. Minimizing simply means replacing unnecessary file entries with entries that mean the same thing:

  • path1/path2/../path3 is replaced with path1/path3
  • path1/./path2 is replaced with path1/path2

I've achieved this using regex and it seems to cover all cases, but it also feels very slow and I have a hunch it might be prone to infinite loops:

private static final Pattern ONE_DOT = Pattern.compile("/\\./");
private static final Pattern TWO_DOTS = Pattern.compile("[^/]+/\\.\\./?");

public static String minimize(final String in) {
    String tmp = in;
    while (!stringIsMinimized(tmp)) {
        tmp = ONE_DOT.matcher(tmp).replaceAll("/");
        tmp = TWO_DOTS.matcher(tmp).replaceAll("");
    }
    return tmp;
}

public static boolean stringIsMinimized(final String str) {
    return !(ONE_DOT.matcher(str).find() || TWO_DOTS.matcher(str).find());
}
\$\endgroup\$
  • \$\begingroup\$ "path1/..../path2/" yields "../path2/" \$\endgroup\$ – dfhwze Jun 14 at 20:15
1
\$\begingroup\$

Your code actually doesn't work, because you use replaceAll. This means that your pattern will allow you to match ../../ and replace it with , resulting in a lost double-back. You can fix this two ways:

  1. You could change the replaceAll to replaceFirst
  2. You could change the pattern to exclude ../../ ([^/.]+/\\.\\./? works)

You can then simplify your loop since the ONE_DOT case will be matched properly so you don't need to split out a check for minimization.

Thus I would suggest:

private static final Pattern ONE_DOT = Pattern.compile("/\\./");
private static final Pattern TWO_DOTS = Pattern.compile("([^/.]+/\\.\\.)+/?");

public static String minimize(final String in) {
    String tmp = in;

    tmp = ONE_DOT.matcher(tmp).replaceAll("/");

    while (TWO_DOTS.matcher(tmp).matches())
        tmp = TWO_DOTS.matcher(tmp).replaceAll("");

    return tmp;
}

At least as a first-pass improvement. There may be a way to do it without the loop using some kind of counting regular expression, but off the top of my head I'm not sure.

\$\endgroup\$
  • \$\begingroup\$ The fastest solution would probably be an iterator, a stack and some look-around. \$\endgroup\$ – dfhwze Jun 14 at 20:17
  • \$\begingroup\$ Yeah, fastest would probably be something like Arrays.stream(in.split("/")).filter(x -> !x.equals(".")).reduce("", {some lambda here}) \$\endgroup\$ – LambdaBeta Jun 14 at 20:21
1
\$\begingroup\$

Your code looks great!

Here, maybe another option that we might exercise would be to possibly do the entire task with an expression, maybe something similar to these:

^(.+?\/).+\/(.+)$
(.+?\/).+\/(.+)

Our first capturing group is non-greedy, collects our desired path1 for both inputs, followed by a greedy .+ that'd continue upto the last slash, and our path2 and path3 are in this group: (.+), and our desired output can be called using \1\2.

Escaping might be unnecessary, just following based on the demo.

Test

import java.util.regex.Matcher;
import java.util.regex.Pattern;

final String regex = "^(.+?\\/).+\\/(.+)$";
final String string = "path1/path2/../path3\n"
     + "path1/./path2";
final String subst = "$1$2";

final Pattern pattern = Pattern.compile(regex, Pattern.MULTILINE);
final Matcher matcher = pattern.matcher(string);

final String result = matcher.replaceAll(subst);

System.out.println(result);

Demo

console.log(`path1/path2/../path3
path1/./path2`.replace(/^(.+?\/).+\/(.+)$/gm, `$1$2`));

Performance

const repeat = 1000000;
const start = Date.now();

for (var i = repeat; i >= 0; i--) {
	const regex = '/^(.+?/).+/(.+)$/gm';
	const str = `path1/path2/../path3`;
	const subst = `$1$2`;

	var match = str.replace(regex, subst);
}

const end = Date.now() - start;
console.log("YAAAY! \"" + match + "\" is a match 💚💚💚 ");
console.log(end / 1000 + " is the runtime of " + repeat + " times benchmark test. 😳 ");

RegEx Circuit

jex.im visualizes regular expressions:

enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.