5
\$\begingroup\$

I'm looking for feedback on my URLEncoder implementation, which is a drop-in replacement for Apache Tomcat's URLEncoder. It was completely ignored by the project committers (and I got no feedback why) and I'm curious if it's just that bad, or I failed to communicate why it's better than the original one.

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.catalina.util;

import java.nio.Buffer;
import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.charset.Charset;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.CoderResult;
import java.nio.charset.CodingErrorAction;
import java.util.BitSet;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

/**
 *
 */
public class URLEncoder {
    /**
     * This constant determines how many characters
     * the encoder can process at once
     */
    private static final int CHAR_BUFFER_SIZE = 8;

    /**
     * On one hand, the output buffer should be large
     * enough to avoid most overflow conditions when
     * possible. On the other hand too large buffer
     * is a waste of space
     */
    private static final int BYTE_BUFFER_SIZE = CHAR_BUFFER_SIZE * 2;

    /**
     * How many encoding entries should be cached in each pool
     */
    private static final int DEFAULT_POOL_CAPACITY = 16;

    /**
     * Do not cache StringBuilders with larger capacity because it's a
     * waste of heap space
     */
    private static final int MAX_STRING_BUILDER_CAPACITY = 1024;

    /**
     * The initial capacity of the newly allocated StringBuilders.
     */
    private static final int INITIAL_STRING_BUILDER_CAPACITY = 64;

    /**
     * Mask for extracting the lower four bits of a byte
     */
    private static final int MASK_LOW = 0x0f;

    /**
     * Mask for extracting the higher four bits of a byte
     */
    private static final int MASK_HIGH = 0xf0;

    /**
     * Each encoded byte must be prefixed with the percent sign
     */
    private static final char PERCENT = '%';

    /**
     * The hexadecimal alphabet
     */
    private static final char[] HEXADECIMAL = {
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
    };

    /**
     * This class is to hold together all objects
     * needed for an encoding operation, in order
     * to use a single pool instead of several
     */
    private static class PoolEntry {
        CharsetEncoder charsetEncoder;
        CharBuffer charBuffer;
        ByteBuffer byteBuffer;
        StringBuilder stringBuilder;
    }

    /**
     * Efficiently remember which characters should not be encoded
     */
    protected final BitSet safeCharacters = new BitSet(256);

    /**
     * Cache the already created encoders and buffers
     * in order to avoid excessive memory allocation
     *
     * The more pools there are, the less lock contention
     * there will be. The number of pools must be a power
     * of two, in order to be able to quickly choose
     * the pool index.
     */
    private final BlockingQueue<PoolEntry>[] pools;

    /**
     * The pool index is calculated by INTEGER & (NUMBER_OF_POOLS - 1) == POOL INDEX.
     * This is actually a very fast modulus division, but works only for
     * number of pools that is a power of two
     */
    private final int maskPoolIndex;

    /**
     * A default instance with number of pools equal to the number of available processors
     * and with the default pool capacity
     */
    public static final URLEncoder DEFAULT = new URLEncoder();

    static {
        DEFAULT.addSafeCharacter('~');
        DEFAULT.addSafeCharacter('-');
        DEFAULT.addSafeCharacter('_');
        DEFAULT.addSafeCharacter('.');
        DEFAULT.addSafeCharacter('*');
        DEFAULT.addSafeCharacter('/');
    }

    /**
     * Create a new encoder instance with the
     * ASCII alphanumeric characters added to the
     * safe characters list and number of pools
     * equal to the nearest power of two that is
     * bigger than or equal to the number of
     * available processors
     */
    public URLEncoder() {
        this(getNumberOfProcessors(), DEFAULT_POOL_CAPACITY);
    }

    private static int getNumberOfProcessors() {
        return Runtime.getRuntime().availableProcessors();
    }

    /**
     * Create a new encoder instance with the
     * ASCII alphanumeric characters added to the
     * safe characters list and number of pools equal
     * to the nearest power of two that is bigger
     * than or equal to <code>numberOfPools</code>
     *
     * @param numberOfPools How many object pools to create
     * @param poolCapacity  The capacity of each pool
     */
    public URLEncoder(int numberOfPools, int poolCapacity) {
        if (numberOfPools <= 0) {
            throw new IllegalArgumentException("The number of pools must be > 0, but the requested number is: " + numberOfPools);
        }

        final int actualNumberOfPools = nextPowerOfTwo(numberOfPools);
        pools = new BlockingQueue[actualNumberOfPools];
        for (int i = 0; i < pools.length; i++) {
            pools[i] = new ArrayBlockingQueue<PoolEntry>(poolCapacity);
        }
        maskPoolIndex = actualNumberOfPools - 1;

        for (char i = 'a'; i <= 'z'; i++) {
            addSafeCharacter(i);
        }
        for (char i = 'A'; i <= 'Z'; i++) {
            addSafeCharacter(i);
        }
        for (char i = '0'; i <= '9'; i++) {
            addSafeCharacter(i);
        }
    }

    /**
     * Calculate the nearest power of two bigger or equal to <code>v</code>
     *
     * @return the nearest power of two bigger or equal to <code>v</code>
     */
    private static int nextPowerOfTwo(int v) {
        v--;
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        return v + 1;
    }

    /**
     * Add a character to the safe list. Those characters
     * will not be encoded. This method is not thread safe
     * and must not be called while an encoding operation
     * is in progress
     *
     * @param c The character to add
     */
    public void addSafeCharacter(char c) {
        /*
            The older encoder was not thread safe as well,
            if there is a chance that this method might be
            called during encode(), then a ReadWriteLock
            should set in place
         */
        safeCharacters.set(c);
    }

    /**
     * URL encode the given string using the UTF-8 charset
     * <p>
     * This method is deprecated. Either encode(String, String)
     * or encode()String, Charset) should be used instead.
     *
     * @param string The String to encode
     * @return The encoded string
     */
    @Deprecated
    public String encode(String string) {
        //Or better java.nio.charset.StandardCharsets.UTF_8 in java >= 7
        return encode(string, Charset.forName("UTF-8"));
    }

    /**
     * URL encode the given string using the selected charset
     * <p>
     * This method is deprecated. Either encode(String, String)
     * or encode()String, Charset) should be used instead.
     *
     * @param string  The String to encode
     * @param charset The name of the charset which will be used to convert the string to bytes
     * @return The encoded string
     * @throws java.nio.charset.IllegalCharsetNameException If the given charset name is illegal
     * @throws IllegalArgumentException                     If the given charset name is null
     * @throws java.nio.charset.UnsupportedCharsetException If there is no support for the given charset
     *                                                      in this instance of the JVM
     */
    public String encode(String string, String charset) {
        return encode(string, Charset.forName(charset));
    }

    /**
     * URL encode the given string using the selected charset
     * <p>
     * This method is deprecated. Either encode(String, String)
     * or encode()String, Charset) should be used instead.
     *
     * @param string  The String to encode
     * @param charset The charset which will be used to convert the strings to byes
     * @return The encoded string
     */
    public String encode(String string, Charset charset) {
        final PoolEntry poolEntry = retrievePoolEntryForCharset(charset);
        final CharsetEncoder encoder = poolEntry.charsetEncoder;
        final CharBuffer inputBuffer = poolEntry.charBuffer;
        final ByteBuffer outputBuffer = poolEntry.byteBuffer;
        final StringBuilder result = poolEntry.stringBuilder;

        for (int nextCharacterIndex = 0; nextCharacterIndex < string.length(); ) {
            final char character = string.charAt(nextCharacterIndex);
            if (safeCharacters.get(character)) {
                result.append(character);
                nextCharacterIndex++;
            } else {
                /*
                 * Recycle the char buffer, because the last fillInputBuffer()
                 * call may have flipped an empty buffer, hence making the
                 * position and limit equal to 0. No need to recycle the
                 * byte buffer, as flushOutputBuffer() always recycles it
                 */
                recycle(inputBuffer);

                int charsRead;
                while ((charsRead = fillInputBuffer(string, inputBuffer, nextCharacterIndex)) != 0) {
                    nextCharacterIndex += charsRead;

                    CoderResult encodingResult;
                    do {
                        final boolean endOfInput = isEndOfInput(string, nextCharacterIndex, inputBuffer);
                        encodingResult = encoder.encode(inputBuffer, outputBuffer, endOfInput);
                        requireCorrectEncodingResult(encodingResult, string, charsRead, nextCharacterIndex);
                        flushOutputBuffer(outputBuffer, result);
                    } while (encodingResult.isOverflow());

                    /*
                     * If the buffer has any remaining unprocessed characters
                     * they must be preserved for the next encoding operation.
                     */
                    inputBuffer.compact();
                }

                //Make sure that everything has been encoded and written to the output buffer
                CoderResult flushResult;
                do {
                    flushResult = encoder.flush(outputBuffer);
                    requireCorrectEncodingResult(flushResult, string, charsRead, nextCharacterIndex);
                    flushOutputBuffer(outputBuffer, result);
                } while (flushResult.isOverflow());

                //Prepare the encoder for the next set of encode() operations if any
                encoder.reset();
            }
        }

        final String encodedString = result.toString();
        returnToPool(poolEntry);
        return encodedString;
    }

    /**
     * Fill in the character buffer with the characters to be encoded.
     * This method flips the char buffer and prepares it for reading.
     *
     * @param source   The original string that is to be encoded
     * @param dest     The CharBuffer to fill with unsafe characters
     * @param readFrom The index of the first unsafe character
     * @return The number of read consecutive, unsafe characters.
     */
    private int fillInputBuffer(String source, CharBuffer dest, int readFrom) {
        int charsRead = 0;
        if (source.length() > readFrom) {
            for (int i = readFrom; dest.hasRemaining() & i < source.length(); i++) {
                final char c = source.charAt(i);
                if (safeCharacters.get(c)) {
                    break;
                }

                dest.put(c);
                charsRead++;
            }
        }

        dest.flip();
        return charsRead;
    }

    /**
     * Peek one character ahead to check if there is
     * more input waiting to be encoded
     *
     * @param string    The string argument passed to teh encode() method
     * @param nextIndex The index of the first unprocessed character
     * @param inputBuffer The input buffer
     * @return true if there is an unsafe character at nextIndex
     */
    private boolean isEndOfInput(String string, int nextIndex, CharBuffer inputBuffer) {
        //If the buffer is not full, it means that we've met safe character
        if (inputBuffer.limit() < inputBuffer.capacity()) {
            return true;
        }

        //Even if it's full, we might have reached the end of the string
        if (nextIndex >= string.length()) {
            return true;
        }

        //The buffer is full and we are not at the end of the string -> check for next unsafe character
        final char nextCharacter = string.charAt(nextIndex);
        return safeCharacters.get(nextCharacter);
    }

    /**
     * Write the content of the ByteBuffer to
     * the StringBuilder as percent encoded
     * hexadecimal string representation.
     * <p>
     * This method flips the ByteBuffer to prepares it for reading
     * and recycles it in order to prepare it for writing
     *
     * @param source The buffer containing the data to be written
     * @param dest   The buffer that will store the result of the encoding operation
     */
    private void flushOutputBuffer(ByteBuffer source, StringBuilder dest) {
        source.flip();
        while (source.hasRemaining()) {
            final byte toEncode = source.get();
            final int low = toEncode & MASK_LOW;
            final int high = (toEncode & MASK_HIGH) >> 4;
            dest.append(PERCENT);
            dest.append(HEXADECIMAL[high]);
            dest.append(HEXADECIMAL[low]);
        }
        recycle(source);
    }

    private void requireCorrectEncodingResult(CoderResult result, String source, int charsRead, int nextCharIndex) {
        if (result.isError()) {
            final String errorDetails = "\tSource: '" + source + "'" +
                    "\tNext character index: '" + nextCharIndex + "'" +
                    "\tChars read: '" + charsRead + "'" +
                    "\tCoder result: '" + result + "'";

            if (result.isUnmappable()) {
                throw new IllegalArgumentException("Non mappable input. " + errorDetails);
            } else if (result.isMalformed()) {
                throw new IllegalArgumentException("Malformed input." + errorDetails);
            } else {
                throw new IllegalStateException("Unknown coder state. " + errorDetails);
            }
        }
    }

    /**
     * Recycle the buffer. Set the limit to the capacity,
     * discard the mark and set the position to zero
     *
     * @param buffer The buffer to be recycled
     * @return The given buffer
     */
    private <T extends Buffer> T recycle(T buffer) {
        buffer.rewind();
        buffer.limit(buffer.capacity());
        return buffer;
    }

    /**
     * Either take from the pool or create a new pool entry.
     *
     * @param charset The charset of teh encoder
     * @return The retrieved PoolEntry
     */
    private PoolEntry retrievePoolEntryForCharset(Charset charset) {
        final int poolIndex = getPoolIndex();
        PoolEntry poolEntry = pools[poolIndex].poll();
        if (null == poolEntry) {
            poolEntry = createPoolEntryForCharset(charset);
        } else {
            poolEntry = recyclePoolEntryForCharset(poolEntry, charset);
        }
        return poolEntry;
    }

    private PoolEntry createPoolEntryForCharset(Charset charset) {
        PoolEntry poolEntry = new PoolEntry();
        poolEntry.charsetEncoder = createCharsetEncoder(charset);
        poolEntry.charBuffer = CharBuffer.allocate(CHAR_BUFFER_SIZE);
        poolEntry.byteBuffer = ByteBuffer.allocate(BYTE_BUFFER_SIZE);
        poolEntry.stringBuilder = new StringBuilder(INITIAL_STRING_BUILDER_CAPACITY);
        return poolEntry;
    }

    private PoolEntry recyclePoolEntryForCharset(PoolEntry poolEntry, Charset charset) {
        /*
            The cached encoder might be for different than the requested charset.
            If that's the case, just get rid of the old charset. At the moment of this writing
            teh encoder is used only with one charset.
         */
        if (!poolEntry.charsetEncoder.charset().equals(charset)) {
            poolEntry.charsetEncoder = createCharsetEncoder(charset);
        } else {
            poolEntry.charsetEncoder.reset();
        }

        /*
            If the string builder was too large, it might have been discarded
         */
        if (null == poolEntry.stringBuilder) {
            poolEntry.stringBuilder = new StringBuilder(INITIAL_STRING_BUILDER_CAPACITY);
        } else {
            poolEntry.stringBuilder.setLength(0);
        }

        recycle(poolEntry.charBuffer);
        recycle(poolEntry.byteBuffer);

        return poolEntry;
    }


    private CharsetEncoder createCharsetEncoder(Charset charset) {
        final CharsetEncoder charsetEncoder = charset.newEncoder();
        /*
         * Preserve the behaviour of the old URLEncoder
         */
        charsetEncoder.onMalformedInput(CodingErrorAction.REPLACE);
        charsetEncoder.onUnmappableCharacter(CodingErrorAction.REPLACE);
        return charsetEncoder;
    }

    private void returnToPool(PoolEntry poolEntry) {
        if (poolEntry.stringBuilder.capacity() > MAX_STRING_BUILDER_CAPACITY) {
            poolEntry.stringBuilder = null;
        }
        final int poolIndex = getPoolIndex();
        pools[poolIndex].offer(poolEntry);
    }

    private int getPoolIndex() {
        final long threadId = Thread.currentThread().getId();
        return (int) (threadId & maskPoolIndex);
    }
}

It's a lot more complicated than the current encoder, but encodes 2-5 times faster and has an almost zero allocation rate (which is the actual reason I wrote it).

\$\endgroup\$
  • \$\begingroup\$ Note that although you've included a license header, by posting here the content of your post is also licensed under cc by-sa 3.0 \$\endgroup\$ – janos Sep 25 '16 at 17:18
  • \$\begingroup\$ Did you provide reproducible benchmarks to support your performance claim? \$\endgroup\$ – Jeroen Vannevel Sep 25 '16 at 17:27
  • \$\begingroup\$ Yes, I had a parameterized JMH benchmark that tested strings with different lengths and characters that had to be encoded. I didn't provide tests for the memory usage though, because it was enough just to run the encoder in a simple loop for let's say 1_000_000 iterations and compare the GC logs. \$\endgroup\$ – Svetlin Zarev Sep 25 '16 at 17:35
  • \$\begingroup\$ Did you also write some unit tests ? \$\endgroup\$ – Spotted Sep 26 '16 at 6:45
  • \$\begingroup\$ Yes, I had unit tests checking encoding for ASCII, Cyrillic, Arabic, Chinese and Japanese characters. \$\endgroup\$ – Svetlin Zarev Sep 26 '16 at 7:05
2
\$\begingroup\$

Regarding the fact that it was ignored: Of course we don't know the whole background, but you already mentioned a lot of possible reasons yourself. I just want to highlight that "a lot more complicated" is actually an excellent rejection reason since this is a conceptually very simple component (so their focus might be on completely different features) and understanding and maintaining a much more complicated piece of code is a pretty big burden to drop on any team.

If you haven't done it already it would need a whole lot of test cases to ensure that it works properly under all circumstances and some proof of the performance impact for (semi-)realistic use cases(!) for me to consider it. Point being that its superior performance might just be drowned out by a whole lot of other effects.

If that's all not the case, maybe you just need to persist.

IMO it's nice and gives me a few ideas for another project, so thanks as well as good luck!


  • The encode method is relatively big, consider splitting off the inner else branch if possible.
  • The docstrings are sometimes missing periods at the of sentences and have some typos. (Yes, nitpicky, just saying.)
  • The main docstring for the class is empty, that should definitely have a summary or be removed.
\$\endgroup\$
0
\$\begingroup\$
  1. The fields of PoolEntry are default and could be changed from classes outside but in same package. Why is that? Someone else could set fields to null.

  2. The encode methods should have a NPE-documentation as you documentate ICNE/IAE/UCE for the encode(String,String)-method. The encode(String) method should have also documentations about the ICNE/IAE/UCE.

  3. Why is the class PoolEntry static? You (should)never create it without a instance of URLEncoder IMO.

  4. The javadoc of encode(String) should use the javadoc-method linking. Sometimes your javadoc use <p> sometimes only a simple line-break (not a hard-problem, just a advice for acceptance by other programmers in the collective).

  5. Except the static fields HEXADECIMAL and DEFAULT all static fields are private that could be public. Why is it forbidden to know the constant value?

  6. Charset.forName("UTF-8") should be a constant initialized by static{} to not do the same work over and over again (i guess it is not DRY, i guess it is more SSOT).

  7. You should make the class final or rethink about the access-modifiers because superclasses can not override PoolEntry.

  8. Assuming the charset is UTF8, should a ü not be a safeCharacter? This way I look to a big range of work I guess.

There are some more but after all i think that: even without my hints, your work is a good contribution to the catalina project. Shake pompons in air.

\$\endgroup\$
  • \$\begingroup\$ btw, the number of availableprocessors could change in runtime. \$\endgroup\$ – Peter Rader Sep 27 '16 at 2:24
  • \$\begingroup\$ Thanks for your comments! 1) Well, they cannot, because first they need to get an instance of PoolEntry. that's inside URLEncoder's pool. 3.) It;s static because it does not need access to the members of URLEncoder. Also it's private which means that it cannot be instantiated outside of URLEncoder. \$\endgroup\$ – Svetlin Zarev Sep 27 '16 at 6:05
  • 1
    \$\begingroup\$ 5) They are private because they must not be part of the public interface of the class. Suppose that the old encoder had such public constants - then I would have to refactor each piece of tomcat that was using them, and still that would break anyone who was using that class outside of tomcat - for instance any third party extensions to tomcat that were using those constants. So I do not want to create a new public API, especialy one that will bind users to a specific implementation. \$\endgroup\$ – Svetlin Zarev Sep 27 '16 at 6:09
  • \$\begingroup\$ 7) I did not make the class final, because the original encoder was not, otherwise I'm a great supporter of "Design for extension or explicitly forbid it". PS: I guess you meant "sub classes". 8) No, there is a RFC about which characters should be encoded.;;; About the processors - that's the intention - the encoder to adapt to the current system. There i sno need to create 64 pools on uniprocessor system - it will not improve anything, but will only consume more memory. Also there will be more lock contention if there were 2 pools on 64 processor system. SO it's better to decide at runtime \$\endgroup\$ – Svetlin Zarev Sep 27 '16 at 6:14
  • \$\begingroup\$ @SvetlinZarev Ah, i see there is no way to get an instance of PoolEntry, but lets talk about why should people inherit the class if they can not access PoolEntry!? You see, there is no OO way to extend the functionality via inherition, is its behave designed for extension? Did anyone else inherit the old implementation? Why should we do this? \$\endgroup\$ – Peter Rader Sep 27 '16 at 15:26
0
\$\begingroup\$

I'm looking for feedback on my URLEncoder implementation, which is a drop-in replacement for Apache Tomcat's URLEncoder.

That's a lie.

You didn't even try to compile the existing unit tests, otherwise you would have noticed that:

  • your class doesn't implement Cloneable
  • it removes some public methods that are called from elsewhere
  • it newly introduces deprecated methods (what could ever be the point of that?)

Therefore it's perfectly valid to just ignore your proposal, because fixing these things would be just too much work for the maintainers.

\$\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.