| Summary: | KConfig::groupList() returns deleted group | ||
|---|---|---|---|
| Product: | [Frameworks and Libraries] frameworks-kconfig | Reporter: | Michel Ludwig <michel.ludwig> |
| Component: | general | Assignee: | Matthew Dawson <matthew> |
| Status: | RESOLVED FIXED | ||
| Severity: | normal | CC: | igorkuo, kdelibs-bugs |
| Priority: | NOR | ||
| Version: | 5.37.0 | ||
| Target Milestone: | --- | ||
| Platform: | Other | ||
| OS: | All | ||
| Latest Commit: | https://invent.kde.org/frameworks/kconfig/commit/295ea7632ac7cc2cc3eda79b7af8614d5ff95a41 | Version Fixed In: | 5.91 |
| Sentry Crash Report: | |||
| Attachments: |
Example code demonstrating the problem
Accompanying CMakeLists.txt Patch for solving the issue |
||
Created attachment 107529 [details]
Accompanying CMakeLists.txt
Created attachment 107530 [details]
Patch for solving the issue
To upload patches, use https://phabricator.kde.org/differential/diff/create/ A possibly relevant merge request was started @ https://invent.kde.org/frameworks/kconfig/-/merge_requests/95 Git commit 295ea7632ac7cc2cc3eda79b7af8614d5ff95a41 by David Faure, on behalf of Igor Kushnir. Committed on 02/01/2022 at 08:31. Pushed by dfaure into branch 'master'. Exclude deleted groups from groupList() This commit is an alternative to the earlier incorrect and reverted b3dc879e8b108c26c929bfbe551bcdf77f140e94. That commit contained several mistakes and an algorithmic complexity increase: 1) the added conditions were inverted: should have been `hasNonDeletedEntries` (without `!`); 2) KConfigPrivate::groupList() passed group instead of key.mGroup to hasNonDeletedEntries(); 3) The complexity of hasNonDeletedEntries() is O(entryMap.size()). Calls to this function were added into loops that iterated entryMap.size() times. So the overall complexity of groupList() increased from linear to quadratic. This fix collects `mGroup`s of non-deleted key entries instead of `mGroup`s of group entries. The number of key entries can be much greater than the number of group entries, so this fix hurts performance. But at least the algorithmic complexity of groupList() stays linear. Future commits can optimize the loops and make them almost as fast or even faster than before this fix. The `!key.mKey.isNull() && !entryMapIt->bDeleted` checks added in this commit are consistent with the check in KConfigPrivate::hasNonDeletedEntries(). KConfig::hasGroupImpl() forwards its argument to hasNonDeletedEntries() with the following comment: // No need to look for the actual group entry anymore, or for subgroups: // a group exists if it contains any non-deleted entry. FIXED-IN: 5.90 M +7 -1 autotests/kconfigtest.cpp M +2 -2 src/core/kconfig.cpp https://invent.kde.org/frameworks/kconfig/commit/295ea7632ac7cc2cc3eda79b7af8614d5ff95a41 Changing the "Version Fixed In" field from 5.90 to 5.91 because the fix was merged later than the commit message anticipated. |
Created attachment 107528 [details] Example code demonstrating the problem After deleting a group with KConfig::deleteGroup, the affected group is still returned in KConfig::groupList(), while at the same time KConfig::hasGroup for that group returns false. The attached sample code demonstrates the problem.