waw666waw666 opened a new pull request, #16578:
URL: https://github.com/apache/dubbo/pull/16578
## What is the purpose of the change?
`BitList` stores the live elements of `originList` as set bits in `rootSet`.
Once an element has been removed, for example an invoker filtered out by a
state router (the normal state of a routed invoker list), a position in the
list is no longer the same as an index in `originList`. `get(int)`,
`remove(int)` and `indexOf` handle this already. These `java.util.List`
operations don't:
- **`subList(from, to)`** clears bits `[0, from)` and `[to, ...)` of
`rootSet`. It treats list positions as `originList` indexes, so it returns
elements that are not in the list and drops elements that are.
- **`new BitList<>(bitList)`** sets bits `[0, bitList.size())` instead of
copying `rootSet`. The copy brings back removed elements and loses live ones.
It also shares the source's `tailList`, so changes to the copy leak into the
source. With a tail list, iterating the copy can throw
`IndexOutOfBoundsException`.
- **`BitListIterator`**:
- `remove()` does not reset its state, so a second `remove()` doesn't
throw `IllegalStateException`. It silently removes another element instead.
- After removing the element returned by `next()`, the cursor still points
at that element, so `hasPrevious()` and `previous()` still return it.
- `nextIndex()` returns `size - 1` at the end of the list.
- `listIterator(index)` does not check its bounds and doesn't position
correctly inside the tail list.
Reproduction on current `3.3` (2d9730c):
```java
BitList<String> invokers = new BitList<>(Arrays.asList("A", "B", "C", "D",
"E"));
invokers.remove("B"); // [A, C, D, E]
invokers.subList(1, 3); // [C] expected [C, D]
new BitList<>(invokers); // [A, B, C, D] expected [A, C, D, E]
ListIterator<String> it = invokers.listIterator();
it.next();
it.remove(); // [C, D, E]
it.hasPrevious(); // true expected false
it.remove(); // no exception, list is now [D, E]
```
Code that treats a routed `BitList` as a plain `List` can therefore get
invokers that were routed away, or lose valid ones. That includes
`RouterSnapshotNode`, which prints `subList(0, 5)` of each node's invokers, and
custom routers or load balancers.
What this PR changes:
- Adds a `bitIndexOf(int)` helper that maps a list position to its
`originList` index. `get(int)` and `remove(int)` now use it instead of
repeating the loop, and `remove(int)` rejects negative indexes like `get(int)`
does.
- `subList` translates `from`/`to` through `rootSet`, copies only the needed
part of the tail list, and checks its bounds the way `List.subList` requires.
- The copy constructor copies `rootSet` and `tailList` when the source is a
`BitList`.
- `BitListIterator` keeps the `originList` index of the last returned
element. `remove()` clears exactly that bit (no more O(n) scan per removal),
steps the cursor back when the removed element was returned by `next()`, and
resets its state. `nextIndex()` is always `previousIndex() + 1`. The
constructor positions the cursor directly, including inside the tail list.
`removeIf` and plain forward iteration, which the routers use, behave as
before. They just no longer scan the bit set on every `remove()`.
Tests: `BitListTest` gets four new tests: `subList` over every range of a
list with removed elements and a tail, the copy constructor and its
independence from the source, `ListIterator.remove()` semantics, and a seeded
randomized comparison of `BitList.listIterator(i)` against `ArrayList`
(next/previous/remove/nextIndex/previousIndex, with and without tail elements).
All four fail on `3.3` and pass with this change. `mvn -pl dubbo-cluster test`
passes (314 tests), and so do `spotless:check` and `checkstyle:check`.
## Checklist
- [x] Make sure there is a
[GitHub_issue](https://github.com/apache/dubbo/issues) field for the change.
(No existing issue; the problem and reproduction are described above.)
- [x] Write a pull request description that is detailed enough to understand
what the pull request does, how, and why.
- [x] Write necessary unit-test to verify your logic correction. If the new
feature or significant change is committed, please remember to add sample in
[dubbo samples](https://github.com/apache/dubbo-samples) project.
- [x] Make sure gitHub actions can pass. [Why the workflow is failing and
how to fix it?](../CONTRIBUTING.md)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]