Incorrect assumption in `successor` and `predecessor` methods.

[mortenbekditlevsen]

firebase-android-sdk/firebase-database/src/main/java/com/google/firebase/database/core/utilities/PushIdGenerator.java

Line 69 in c56a976

public static final String predecessor(String key) {

The methods incorrectly assume that the keys are all in the style of the autogenerated RTDB keys, while in fact they may be any allowed key.

See the iOS SDK issue and solution (work in progress) here:

firebase/firebase-ios-sdk#8790

[google-oss-bot]

I couldn't figure out how to label this issue, so I've labeled it for a human to triage. Hang tight.

[argzdev]

Thanks for reporting @mortenbekditlevsen. I noticed in the conversation you've had in #8790 that you prepping an implementation, would you like to file a pull request?

As for the relevant code, I tried to convert it to Android however I wasn't able to replicate the issue. Am I missing anything?

String padding = " ";
for(int i = 0; i < 786; i++)
    padding += "z";

Query query = mDatabase.child("posts").orderByKey().startAfter(padding);

Hi @schmidt-sebastian, just an FYI, thanks!

[mortenbekditlevsen]

Hi @argzdev ,
So the actual crash in firebase-ios-sdk was due to the incorrect assumption together with an index out of bounds error.

The latter issue is likely not present in the android codebase, but the assumption is still incorrect:

For instance:

Getting the predecessor of "-" returns String.valueOf(Integer.MAX_VALUE);

But that is not the predecessor of "-", because " " is also a valid key character and should come somewhere between Integer.MAX_VALUE and "-"

What 'saves' successor from a crash is:

    char sourcePlusOne = PUSH_CHARS.charAt(PUSH_CHARS.indexOf(source) + 1);

Even if source is not a PUSH_CHAR, indexOf (from reading the documentation) returns -1, meaning that sourcePlusOne will just become the first PUSH_CHAR.

This is still incorrect, as the successor space padded with MAX_PUSH_CHAR should just have the last character increased by one - and the successor of space padded with the highest UTF16 encoding (0xFFFF) should be "!".

As I read it, you should be able to make predecessor throw an exception:
Getting the predecessor of " " would (if I read correctly) try to index into PUSH_CHARS at index -2.
As would the predecessor of any other single character not in the PUSH_CHARS set...

[argzdev]

Hi @mortenbekditlevsen, thanks for clarifying the issue. You are correct, the exception is indeed thrown.

Relevant code:
Query query = mDatabase.child("posts").orderByKey().endBefore(" ");

Error:
java.lang.StringIndexOutOfBoundsException: length=64; index=-2

Hi @schmidt-sebastian, since this is already being investigated by IanWyszynski. Should I assign this ticket to him as well?