in src/main/software/amazon/event/ruler/ByteMachine.java [290:429]
private void deleteRangePattern(Range range) {
// if range to be deleted does not exist, just return
if (findRangePattern(range) == null) {
return;
}
// Inside Range pattern, there are bottom value and top value, this function will traverse each byte of bottom
// and top value separately to hunt down all matches eligible to be deleted.
// The ArrayDequeue is used to save all byteStates in transition path since state associated with first byte of
// value to state associated with last byte of value. Then, checkAndDeleteStateAlongTraversedPath function will
// check each state saved in ArrayDequeue along reverse direction of traversing path and recursively check and
// delete match and state if it is eligible.
// Note: byteState is deletable only when it has no match and no transition to next byteState.
// Refer to definition of class ComparableNumber, the max length in bytes for Number type is 16,
// so here we take 16 as ArrayDeque capacity which is defined as ComparableNumber.MAX_BYTE_LENGTH.
final ArrayDeque<AbstractMap.SimpleImmutableEntry<Byte, ByteTransition>> byteStatesTraversePathAlongRangeBottomValue =
new ArrayDeque<>(ComparableNumber.MAX_LENGTH_IN_BYTES);
final ArrayDeque<AbstractMap.SimpleImmutableEntry<Byte, ByteTransition>> byteStatesTraversePathAlongRangeTopValue =
new ArrayDeque<>(ComparableNumber.MAX_LENGTH_IN_BYTES);
ByteTransition forkState = startState;
int forkOffset = 0;
byteStatesTraversePathAlongRangeBottomValue.addFirst(new AbstractMap.SimpleImmutableEntry<>(range.bottom[0], forkState));
byteStatesTraversePathAlongRangeTopValue.addFirst(new AbstractMap.SimpleImmutableEntry<>(range.top[0], forkState));
// bypass common prefix of range's bottom and top patterns
// we need move forward the state and save all states traversed for checking later.
while (range.bottom[forkOffset] == range.top[forkOffset]) {
forkState = findNextByteStateForRangePattern(forkState, range.bottom[forkOffset]);
assert forkState != null : "forkState != null";
byteStatesTraversePathAlongRangeBottomValue.addFirst(new AbstractMap.SimpleImmutableEntry<>(range.bottom[forkOffset], forkState));
byteStatesTraversePathAlongRangeTopValue.addFirst(new AbstractMap.SimpleImmutableEntry<>(range.top[forkOffset], forkState));
forkOffset++;
}
// when bottom byte on forkOffset position < top byte in same position, there must be matches existing
// in this state, go ahead to delete matches in the fork state.
for (byte bb : Range.digitSequence(range.bottom[forkOffset], range.top[forkOffset], false, false, range.isCIDR)) {
deleteMatches(getParser().parse(bb), forkState, range);
}
// process all the transitions on the bottom range bytes
ByteTransition state = forkState;
int lastMatchOffset = forkOffset;
// see explanation in addRangePattern(), we need delete state and match accordingly.
for (int offsetB = forkOffset + 1; offsetB < (range.bottom.length - 1); offsetB++) {
byte b = range.bottom[offsetB];
if (b < range.maxDigit()) {
while (lastMatchOffset < offsetB) {
state = findNextByteStateForRangePattern(state, range.bottom[lastMatchOffset]);
assert state != null : "state must be existing for this pattern";
byteStatesTraversePathAlongRangeBottomValue.addFirst(
new AbstractMap.SimpleImmutableEntry<>(range.bottom[lastMatchOffset], state));
lastMatchOffset++;
}
assert lastMatchOffset == offsetB : "lastMatchOffset == offsetB";
for (byte bb : Range.digitSequence(b, range.maxDigit(), false, true, range.isCIDR)) {
deleteMatches(getParser().parse(bb), state, range);
}
}
}
// now for last "bottom" digit
// see explanation in addRangePattern(), we need to delete states and matches accordingly.
final byte lastBottom = range.bottom[range.bottom.length - 1];
final byte lastTop = range.top[range.top.length - 1];
if ((lastBottom < range.maxDigit()) || !range.openBottom) {
while (lastMatchOffset < range.bottom.length - 1) {
state = findNextByteStateForRangePattern(state, range.bottom[lastMatchOffset]);
assert state != null : "state != null";
byteStatesTraversePathAlongRangeBottomValue.addFirst(new AbstractMap.SimpleImmutableEntry<>(range.bottom[lastMatchOffset], state));
lastMatchOffset++;
}
assert lastMatchOffset == range.bottom.length - 1 : "lastMatchOffset == range.bottom.length - 1";
if (!range.openBottom) {
deleteMatches(getParser().parse(lastBottom), state, range);
}
// unless the last digit is also at the fork position, fill in the extra matches due to
// the strictly-less-than condition (see discussion above)
if (forkOffset < (range.bottom.length - 1)) {
for (byte bb : Range.digitSequence(lastBottom, range.maxDigit(), false, true, range.isCIDR)) {
deleteMatches(getParser().parse(bb), state, range);
}
}
}
// now process transitions along the top range bytes
// see explanation in addRangePattern(), we need to delete states and matches accordingly.
state = forkState;
lastMatchOffset = forkOffset;
for (int offsetT = forkOffset + 1; offsetT < (range.top.length - 1); offsetT++) {
byte b = range.top[offsetT];
if (b > range.minDigit()) {
while (lastMatchOffset < offsetT) {
state = findNextByteStateForRangePattern(state, range.top[lastMatchOffset]);
assert state != null : "state must be existing for this pattern";
byteStatesTraversePathAlongRangeTopValue.addFirst(new AbstractMap.SimpleImmutableEntry<>(range.top[lastMatchOffset], state));
lastMatchOffset++;
}
assert lastMatchOffset == offsetT : "lastMatchOffset == offsetT";
for (byte bb : Range.digitSequence((byte) range.minDigit(), range.top[offsetT], true, false, range.isCIDR)) {
deleteMatches(getParser().parse(bb), state, range);
}
}
}
// now for last "top" digit.
// see explanation in addRangePattern(), we need to delete states and matches accordingly.
if ((lastTop > range.minDigit()) || !range.openTop) {
while (lastMatchOffset < range.top.length - 1) {
state = findNextByteStateForRangePattern(state, range.top[lastMatchOffset]);
assert state != null : "state != null";
byteStatesTraversePathAlongRangeTopValue.addFirst(new AbstractMap.SimpleImmutableEntry<>(range.top[lastMatchOffset], state));
lastMatchOffset++;
}
assert lastMatchOffset == range.top.length - 1 : "lastMatchOffset == range.top.length - 1";
if (!range.openTop) {
deleteMatches(getParser().parse(lastTop), state, range);
}
// unless the last digit is also at the fork position, fill in the extra matches due to
// the strictly-less-than condition (see discussion above)
if (forkOffset < (range.top.length - 1)) {
for (byte bb : Range.digitSequence((byte) range.minDigit(), lastTop, true, false, range.isCIDR)) {
deleteMatches(getParser().parse(bb), state, range);
}
}
}
// by now we should have deleted all matches in all associated byteStates,
// now we start cleaning up ineffective byteSates along states traversed path we saved before.
checkAndDeleteStateAlongTraversedPath(byteStatesTraversePathAlongRangeBottomValue);
checkAndDeleteStateAlongTraversedPath(byteStatesTraversePathAlongRangeTopValue);
// well done now, we have deleted all matches pattern matched and cleaned all empty state as if that pattern
// wasn't added into machine before.
}