Comment contradicts code (in all run-times)?

[niccroad]

In this function of PredictionContext.

public static PredictionContext mergeRoot(SingletonPredictionContext a,
											  SingletonPredictionContext b,
											  boolean rootIsWildcard)
	{
		if ( rootIsWildcard ) {
			if ( a == EMPTY ) return EMPTY;  // * + b = *
			if ( b == EMPTY ) return EMPTY;  // a + * = *
		}
		else {
			if ( a == EMPTY && b == EMPTY ) return EMPTY; // $ + $ = $
			if ( a == EMPTY ) { // $ + x = [$,x]
				int[] payloads = {b.returnState, EMPTY_RETURN_STATE};
				PredictionContext[] parents = {b.parent, null};
				PredictionContext joined =
					new ArrayPredictionContext(parents, payloads);
				return joined;
			}
			if ( b == EMPTY ) { // x + $ = [$,x] ($ is always first if present)
				int[] payloads = {a.returnState, EMPTY_RETURN_STATE};
				PredictionContext[] parents = {a.parent, null};
				PredictionContext joined =
					new ArrayPredictionContext(parents, payloads);
				return joined;
			}
		}
		return null;
	}

The comments // $ + x = [$,x]
and more explicitly // x + $ = [$,x] ($ is always first if present)

Seem to contradict the implementation. This was done 6 years ago by @parrt.
Should the order in the comments not be [x,$], ($ is always second if present)?

[parrt]

Indeed that looks weird. @sharwell note that we create

int[] payloads = {b.returnState, EMPTY_RETURN_STATE};
...
PredictionContext joined = new ArrayPredictionContext(parents, payloads);

but ArrayPredictionContext.isEmpty() tests

// since EMPTY_RETURN_STATE can only appear in the last position, we
// don't need to verify that size==1
return returnStates[0]==EMPTY_RETURN_STATE;

That seems like a glaring problem but we've not seen any weird bugs have we?

[parrt]

Actually, now I see something else in PredictionContext:

public boolean hasEmptyPath() {
	// since EMPTY_RETURN_STATE can only appear in the last position, we check last one
	return getReturnState(size() - 1) == EMPTY_RETURN_STATE;
}

[sharwell]

The implementations of isEmpty and hasEmptyPath seem correct.

• For isEmpty: the first item is EMPTY_RETURN_STATE (explicit check) plus only the last item can be EMPTY_RETURN_STATE (invariant) implies size is 1
• For hasEmptyPath: The last item is checked by reading size()

So this is just a bug to update the comment in code?

[parrt]

Actually, it looks like a bug. Test for ArrayPredictionContext.isEmpty expects EMPTY_RETURN_STATE in position 0 but mergeRoot() is putting it at position 1

[sharwell]

Actually, it looks like a bug. Test for ArrayPredictionContext.isEmpty expects EMPTY_RETURN_STATE in position 0 but mergeRoot() is putting it at position 1

The result of mergeRoot is not empty. Updated my previous comment too.

[parrt]

Doesn't it create an array context with int[] payloads = {b.returnState, EMPTY_RETURN_STATE}; putting the empty in 2nd position? Right. not completely empty but looks like we test for a different condition.

[sharwell]

isEmpty is a combination of (hasEmptyPath) and (size() == 1). The "weird" indexing is an optimization leveraging an invariant of the data structure to eliminate a call to size() on a hot path.

[parrt]

interesting. ok, so is the "fix" just changing this comment?

// x + $ = [$,x] ($ is always first if present)

to

// x + $ = [x,$] ($ is always last if present)

[sharwell]

interesting. ok, so is the "fix" just changing this comment?

I believe that is correct.

[parrt]

ok, cool. thanks!