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]

  • [PR] Fix BitList position... waw666waw666 (via GitHub) via notifications

Reply via email to