Blender Git Loki

handle not-found linked groups better

Cleanup: in ID name management code: root_name -> base_name.

`root_name` did not really meant much here, `base_name` is much more
accurate.

ID Management: Improve speed of code used when creating/renaming and ID.

This commit affects `id_sort_by_name()` and `check_for_dupid()` helper:
* Add a new parameter, `ID *id_sorting_hint`, to `id_sort_by_name()`,
and when non-NULL, check if we can insert `id` immediately before or
after it. This can dramatically reduce time spent in that function.
* Use loop over whole list in `check_for_dupid()` to also define the
likely ID pointer that will be neighbor with our new one.

This gives another decent speedup to all massive addition cases:

| Number and type of names of IDs | old code | new code | speed improvement |
| -------------------------------- | -------- | -------- | ----------------- |
| 40K, mixed (14k rand, 26k const) | 39s | 33s | 18% |
| 40K, fully random | 51s | 42s | 21% |
| 40K, fully constant | 40s | 34s | 18% |

Combined with the previous commits, this makes massive addition of IDs more
than twice as fast as previously.

ID Management: Improve speed of code used when creating/renaming and ID.

This commit affects `check_for_dupid()` helper:
* Add a special, quicker code path dedicated to sequential addition of a
large number of IDs using the same base name.

This gives a significant speedup to adding 'randomly'-named IDs:

| Number and type of names of IDs | old code | new code | speed improvement |
| -------------------------------- | -------- | -------- | ----------------- |
| 40K, mixed (14k rand, 26k const) | 49s | 39s | 26% |
| 40K, fully random | 51s | 51s | 0% |
| 40K, fully constant | 71s | 40s | 78% |

Note that 'random' names give no improvement as expected, since this new code
path will never be used in such cases.

ID Management: Improve speed of code used when creating/renaming and ID.

This commit affects `check_for_dupid()` helper:
* Further simplify the general logic of the code (we now typically only do
one loop over the list of data-blocks, instead of two).

This gives a significant speedup to adding 'randomly'-named IDs:

| Number and type of names of IDs | old code | new code | speed improvement |
| -------------------------------- | -------- | -------- | ----------------- |
| 40K, mixed (14k rand, 26k const) | 62s | 49s | 27% |
| 40K, fully random | 76s | 51s | 49% |
| 40K, fully constant | 77s | 71s | 8% |

Note that 'constant' names give little improvement, as in that case the first
loop over the list of IDs (checking whether base given name was already in use)
was aborting very quickly.

ID Management: Fix/Sanitize code used when creating or renaming an ID.

This commit affects `check_for_dupid()` helper:
* Fix (serious though rare) bug where several IDs could end up with
exact same name (happened with over 10k IDs with same very long name).
* Fix (relatively harmless) func reporting it did not change the given
name when it actually had truncated it.
* Sanitize handling of supported min/max number suffixes (it now handles
between 1 and 1 billion, which should be way more than enough).
* Sanitize general logic to (hopefully!) make it easier to follow.
* General cleanup (naming, comments, variables scope, remove dead code, etc.).

Note that general performances here remain the same, there is no
measurable gain or loss. Algorithm remain also the same globally.

Attempt to use a GHash to speed up checks of used names proved to be
much worse, just building the GHash would already take as much time as
the whole process with current code...

ID Management: Improve speed of code used when creating/renaming and ID.

This alone can make e.g. adding 40k IDs with default name (i.e. 'fully
constant' case in table below) about 15-20% faster:

| Number and type of names of IDs | old code | new code | speed improvement |
| -------------------------------- | -------- | -------- | ----------------- |
| 40K, mixed (14k rand, 26k const) | 75s | 62s | 21% |
| 40K, fully random | 90s | 76s | 18% |
| 40K, fully constant | 94s | 77s | 22% |

Idea is to use a first pass, where we just check one item every nth ones,
until we have found the chunk in which we want to insert the new item,
then do a basic linear comparison with all items in that chunk as before.

Also, list is now walked backward, as in most common 'massive insertion'
cases new ID's names have higher number, hence ends up towards the end of
the list.

This new sorting function can be between a few percents and 50% quicker than
original code, depending on various factors (like length of common parts of
ID names, whether new IDs should be added towards the end or not, how high
in numbering we are, etc.).

Note: another, full bisecting approach was also tried, which gives a massive
reduction of comparisons (from n items to log2(n)), but it only gave minor
improvements of speed from original fully linear code, while adding a fair
amount of complexity to the logic. Only case it was shining was the unlikely
'very long, almost similar ID names' case (since `strcasecmp()` is rather
costly then).

ID Management: Add some basic tests regarding name handling.

Those tests are here mostsly to ensure ID name management is working as
expected (the code ensuring we never have two ilocal data-blocks of the
same type with the same name in a .blend file).

Note: Currently fails in some cases, fixes are incoming.

Note: Ideally this would be in C, but we already have too many tests
linking the whole Blender and its libraries, this is becoming a real
pain to link debug + ASAN + tests build these days... So until we find a
better way to handle those dependencies, sticking to simple python
scripts.

Merge branch 'master' into functions

GPencil: fix compilation error

Remove empty header added by accident

Fix T71844: Outliner: show_active doesn't expand armature to show active bone

Since rB6bc6d016c5e7, outliner was not opening back up from the found
active element (but only its ID instead -- all occurances of this ID in
any collection).

Now expand from the active element as well (but only do this for the
first occurance of the corresponding ID)

Maniphest Tasks: T71844

Differential Revision: https://developer.blender.org/D6329

Merge branch 'greasepencil-object' into greasepencil-refactor

Merge branch 'master' into greasepencil-object

GPencil: Remove temp color conversion to Linear

GPencil: Patch old files color to Linear

Still pending to review VFX and Modifiers.

Cleanup: simplify transform cursor DPI scaling

Cleanup: split transform cursor drawing into their own files

Fix T71817: Preferences tagged dirty by 'Enabled Add-ons Only'

Fix T72577: vert/weight paint 'Orbit Around' & 'Frame Selected' fail

Caused by 14acac0bb7f3