Blender  V3.3
main_namemap.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include "BKE_idtype.h"
8 #include "BKE_lib_id.h"
9 #include "BKE_main.h"
10 #include "BKE_main_namemap.h"
11 
12 #include "BLI_assert.h"
13 #include "BLI_bitmap.h"
14 #include "BLI_ghash.h"
15 #include "BLI_listbase.h"
16 #include "BLI_map.hh"
17 #include "BLI_math_base.hh"
18 #include "BLI_set.hh"
19 #include "BLI_string_utf8.h"
20 #include "BLI_string_utils.h"
21 
22 #include "DNA_ID.h"
23 
24 #include "MEM_guardedalloc.h"
25 
26 #include "CLG_log.h"
27 
28 static CLG_LogRef LOG = {"bke.main_namemap"};
29 
30 //#define DEBUG_PRINT_MEMORY_USAGE
31 
32 using namespace blender;
33 
34 /* Assumes and ensure that the suffix number can never go beyond 1 billion. */
35 #define MAX_NUMBER 1000000000
36 /* We do not want to get "name.000", so minimal number is 1. */
37 #define MIN_NUMBER 1
38 
47 static bool id_name_final_build(char *name, char *base_name, size_t base_name_len, int number)
48 {
49  char number_str[11]; /* Dot + nine digits + NULL terminator. */
50  size_t number_str_len = BLI_snprintf_rlen(number_str, ARRAY_SIZE(number_str), ".%.3d", number);
51 
52  /* If the number would lead to an overflow of the maximum ID name length, we need to truncate
53  * the base name part and do all the number checks again. */
54  if (base_name_len + number_str_len >= MAX_NAME || number >= MAX_NUMBER) {
55  if (base_name_len + number_str_len >= MAX_NAME) {
56  base_name_len = MAX_NAME - number_str_len - 1;
57  }
58  else {
59  base_name_len--;
60  }
61  base_name[base_name_len] = '\0';
62 
63  /* Code above may have generated invalid utf-8 string, due to raw truncation.
64  * Ensure we get a valid one now. */
65  base_name_len -= (size_t)BLI_str_utf8_invalid_strip(base_name, base_name_len);
66 
67  /* Also truncate orig name, and start the whole check again. */
68  name[base_name_len] = '\0';
69  return false;
70  }
71 
72  /* We have our final number, we can put it in name and exit the function. */
73  BLI_strncpy(name + base_name_len, number_str, number_str_len + 1);
74  return true;
75 }
76 
77 /* Key used in set/map lookups: just a string name. */
79  char name[MAX_NAME];
80  uint64_t hash() const
81  {
82  return BLI_ghashutil_strhash_n(name, MAX_NAME);
83  }
84  bool operator==(const UniqueName_Key &o) const
85  {
86  return !BLI_ghashutil_strcmp(name, o.name);
87  }
88 };
89 
90 /* Tracking of used numeric suffixes. For each base name:
91  *
92  * - Exactly track which of the lowest 1024 suffixes are in use,
93  * whenever there is a name collision we pick the lowest "unused"
94  * one. This is done with a bit map.
95  * - Above 1024, do not track them exactly, just track the maximum
96  * suffix value seen so far. Upon collision, assign number that is
97  * one larger.
98  */
100  static constexpr unsigned max_exact_tracking = 1024;
101  BLI_BITMAP_DECLARE(mask, max_exact_tracking);
102  int max_value = 0;
103 
104  void mark_used(int number)
105  {
106  if (number >= 0 && number < max_exact_tracking) {
107  BLI_BITMAP_ENABLE(mask, number);
108  }
109  if (number < MAX_NUMBER) {
110  math::max_inplace(max_value, number);
111  }
112  }
113 
114  void mark_unused(int number)
115  {
116  if (number >= 0 && number < max_exact_tracking) {
117  BLI_BITMAP_DISABLE(mask, number);
118  }
119  if (number > 0 && number == max_value) {
120  --max_value;
121  }
122  }
123 
124  bool use_if_unused(int number)
125  {
126  if (number >= 0 && number < max_exact_tracking) {
127  if (!BLI_BITMAP_TEST_BOOL(mask, number)) {
128  BLI_BITMAP_ENABLE(mask, number);
129  math::max_inplace(max_value, number);
130  return true;
131  }
132  }
133  return false;
134  }
135 
137  {
138  /* Find the smallest available one <1k.
139  * However we never want to pick zero ("none") suffix, even if it is
140  * available, e.g. if Foo.001 was used and we want to create another
141  * Foo.001, we should return Foo.002 and not Foo.
142  * So while searching, mark #0 as "used" to make sure we don't find it,
143  * and restore the value afterwards. */
144 
145  BLI_bitmap prev_first = mask[0];
146  mask[0] |= 1;
147  int result = BLI_bitmap_find_first_unset(mask, max_exact_tracking);
148  if (result >= 0) {
150  math::max_inplace(max_value, result);
151  }
152  mask[0] |= prev_first & 1; /* Restore previous value of #0 bit. */
153  return result;
154  }
155 };
156 
157 /* Tracking of names for a single ID type. */
159  /* Set of full names that are in use. */
161  /* For each base name (i.e. without numeric suffix), track the
162  * numeric suffixes that are in use. */
164 };
165 
168 
170  {
171  int index = BKE_idtype_idcode_to_index(id_type);
172  return index >= 0 ? &type_maps[index] : nullptr;
173  }
174 };
175 
177 {
178  struct UniqueName_Map *map = MEM_new<UniqueName_Map>(__func__);
179  return map;
180 }
181 
182 void BKE_main_namemap_destroy(struct UniqueName_Map **r_name_map)
183 {
184 #ifdef DEBUG_PRINT_MEMORY_USAGE
185  int64_t size_sets = 0;
186  int64_t size_maps = 0;
187  for (const UniqueName_TypeMap &type_map : (*r_name_map)->type_maps) {
188  size_sets += type_map.full_names.size_in_bytes();
189  size_maps += type_map.base_name_to_num_suffix.size_in_bytes();
190  }
191  printf(
192  "NameMap memory usage: sets %.1fKB, maps %.1fKB\n", size_sets / 1024.0, size_maps / 1024.0);
193 #endif
194  MEM_delete<UniqueName_Map>(*r_name_map);
195  *r_name_map = nullptr;
196 }
197 
198 static void main_namemap_populate(UniqueName_Map *name_map, struct Main *bmain, ID *ignore_id)
199 {
200  BLI_assert_msg(name_map != nullptr, "name_map should not be null");
201  for (UniqueName_TypeMap &type_map : name_map->type_maps) {
202  type_map.base_name_to_num_suffix.clear();
203  }
204  Library *library = ignore_id->lib;
205  ID *id;
206  FOREACH_MAIN_ID_BEGIN (bmain, id) {
207  if ((id == ignore_id) || (id->lib != library)) {
208  continue;
209  }
210  UniqueName_TypeMap *type_map = name_map->find_by_type(GS(id->name));
211  BLI_assert(type_map != nullptr);
212 
213  /* Insert the full name into the set. */
214  UniqueName_Key key;
215  BLI_strncpy(key.name, id->name + 2, MAX_NAME);
216  type_map->full_names.add(key);
217 
218  /* Get the name and number parts ("name.number"). */
219  int number = MIN_NUMBER;
220  BLI_split_name_num(key.name, &number, id->name + 2, '.');
221 
222  /* Get and update the entry for this base name. */
224  val.mark_used(number);
225  }
227 }
228 
229 /* Get the name map object used for the given Main/ID.
230  * Lazily creates and populates the contents of the name map, if ensure_created is true.
231  * Note: if the contents are populated, the name of the given ID itself is not added. */
232 static UniqueName_Map *get_namemap_for(Main *bmain, ID *id, bool ensure_created)
233 {
234  if (id->lib != nullptr) {
235  if (ensure_created && id->lib->runtime.name_map == nullptr) {
236  id->lib->runtime.name_map = BKE_main_namemap_create();
238  }
239  return id->lib->runtime.name_map;
240  }
241  if (ensure_created && bmain->name_map == nullptr) {
243  main_namemap_populate(bmain->name_map, bmain, id);
244  }
245  return bmain->name_map;
246 }
247 
248 bool BKE_main_namemap_get_name(struct Main *bmain, struct ID *id, char *name)
249 {
250 #ifndef __GNUC__ /* GCC warns with `nonull-compare`. */
251  BLI_assert(bmain != nullptr);
252  BLI_assert(id != nullptr);
253 #endif
254  UniqueName_Map *name_map = get_namemap_for(bmain, id, true);
255  BLI_assert(name_map != nullptr);
256  BLI_assert(strlen(name) < MAX_NAME);
257  UniqueName_TypeMap *type_map = name_map->find_by_type(GS(id->name));
258  BLI_assert(type_map != nullptr);
259 
260  bool is_name_changed = false;
261 
262  UniqueName_Key key;
263  while (true) {
264  /* Check if the full original name has a duplicate. */
265  BLI_strncpy(key.name, name, MAX_NAME);
266  const bool has_dup = type_map->full_names.contains(key);
267 
268  /* Get the name and number parts ("name.number"). */
269  int number = MIN_NUMBER;
270  size_t base_name_len = BLI_split_name_num(key.name, &number, name, '.');
271 
272  bool added_new = false;
273  UniqueName_Value &val = type_map->base_name_to_num_suffix.lookup_or_add_cb(key, [&]() {
274  added_new = true;
275  return UniqueName_Value();
276  });
277  if (added_new || !has_dup) {
278  /* This base name is not used at all yet, or the full original
279  * name has no duplicates. The latter could happen if splitting
280  * by number would produce the same values, for different name
281  * strings (e.g. Foo.001 and Foo.1). */
282  val.mark_used(number);
283 
284  if (!has_dup) {
285  BLI_strncpy(key.name, name, MAX_NAME);
286  type_map->full_names.add(key);
287  }
288  return is_name_changed;
289  }
290 
291  /* The base name is already used. But our number suffix might not be used yet. */
292  int number_to_use = -1;
293  if (val.use_if_unused(number)) {
294  /* Our particular number suffix is not used yet: use it. */
295  number_to_use = number;
296  }
297  else {
298  /* Find lowest free under 1k and use it. */
299  number_to_use = val.use_smallest_unused();
300 
301  /* Did not find one under 1k. */
302  if (number_to_use == -1) {
303  if (number >= MIN_NUMBER && number > val.max_value) {
304  val.max_value = number;
305  number_to_use = number;
306  }
307  else {
308  val.max_value++;
309  number_to_use = val.max_value;
310  }
311  }
312  }
313 
314  /* Try to build final name from the current base name and the number.
315  * Note that this can fail due to too long base name, or a too large number,
316  * in which case it will shorten the base name, and we'll start again. */
317  BLI_assert(number_to_use >= MIN_NUMBER);
318  if (id_name_final_build(name, key.name, base_name_len, number_to_use)) {
319  /* All good, add final name to the set. */
320  BLI_strncpy(key.name, name, MAX_NAME);
321  type_map->full_names.add(key);
322  break;
323  }
324 
325  /* Name had to be truncated, or number too large: mark
326  * the output name as definitely changed, and proceed with the
327  * truncated name again. */
328  is_name_changed = true;
329  }
330  return is_name_changed;
331 }
332 
333 void BKE_main_namemap_remove_name(struct Main *bmain, struct ID *id, const char *name)
334 {
335 #ifndef __GNUC__ /* GCC warns with `nonull-compare`. */
336  BLI_assert(bmain != nullptr);
337  BLI_assert(id != nullptr);
338  BLI_assert(name != nullptr);
339 #endif
340  /* Name is empty or not initialized yet, nothing to remove. */
341  if (name[0] == '\0') {
342  return;
343  }
344 
345  struct UniqueName_Map *name_map = get_namemap_for(bmain, id, false);
346  if (name_map == nullptr) {
347  return;
348  }
349  BLI_assert(strlen(name) < MAX_NAME);
350  UniqueName_TypeMap *type_map = name_map->find_by_type(GS(id->name));
351  BLI_assert(type_map != nullptr);
352 
353  UniqueName_Key key;
354  /* Remove full name from the set. */
355  BLI_strncpy(key.name, name, MAX_NAME);
356  type_map->full_names.remove(key);
357 
358  int number = MIN_NUMBER;
359  BLI_split_name_num(key.name, &number, name, '.');
361  if (val == nullptr) {
362  return;
363  }
364  if (number == 0 && val->max_value == 0) {
365  /* This was the only base name usage, remove whole key. */
366  type_map->base_name_to_num_suffix.remove(key);
367  return;
368  }
369  val->mark_unused(number);
370 }
371 
373  char name[MAX_ID_NAME];
375  uint64_t hash() const
376  {
379  }
380  bool operator==(const Uniqueness_Key &o) const
381  {
382  return lib == o.lib && !BLI_ghashutil_strcmp(name, o.name);
383  }
384 };
385 
386 static bool main_namemap_validate_and_fix(Main *bmain, const bool do_fix)
387 {
388  Set<Uniqueness_Key> id_names_libs;
389  bool is_valid = true;
390  ListBase *lb_iter;
391  FOREACH_MAIN_LISTBASE_BEGIN (bmain, lb_iter) {
392  LISTBASE_FOREACH_MUTABLE (ID *, id_iter, lb_iter) {
393  Uniqueness_Key key;
394  BLI_strncpy(key.name, id_iter->name, MAX_ID_NAME);
395  key.lib = id_iter->lib;
396  if (!id_names_libs.add(key)) {
397  is_valid = false;
398  CLOG_ERROR(&LOG,
399  "ID name '%s' (from library '%s') is found more than once",
400  id_iter->name,
401  id_iter->lib != nullptr ? id_iter->lib->filepath : "<None>");
402  if (do_fix) {
403  /* NOTE: this may imply moving this ID in its listbase, however re-checking it later is
404  * not really an issue. */
406  bmain, which_libbase(bmain, GS(id_iter->name)), id_iter, nullptr, true);
407  BLI_strncpy(key.name, id_iter->name, MAX_ID_NAME);
408  if (!id_names_libs.add(key)) {
409  CLOG_ERROR(&LOG,
410  "\tID has been renamed to '%s', but it still seems to be already in use",
411  id_iter->name);
412  }
413  else {
414  CLOG_WARN(&LOG, "\tID has been renamed to '%s'", id_iter->name);
415  }
416  }
417  }
418 
419  UniqueName_Map *name_map = get_namemap_for(bmain, id_iter, false);
420  if (name_map == nullptr) {
421  continue;
422  }
423  UniqueName_TypeMap *type_map = name_map->find_by_type(GS(id_iter->name));
424  BLI_assert(type_map != nullptr);
425 
426  UniqueName_Key key_namemap;
427  /* Remove full name from the set. */
428  BLI_strncpy(key_namemap.name, id_iter->name + 2, MAX_NAME);
429  if (!type_map->full_names.contains(key_namemap)) {
430  is_valid = false;
431  CLOG_ERROR(&LOG,
432  "ID name '%s' (from library '%s') exists in current Main, but is not listed in "
433  "the namemap",
434  id_iter->name,
435  id_iter->lib != nullptr ? id_iter->lib->filepath : "<None>");
436  }
437  }
438  }
440 
441  Library *lib = nullptr;
442  UniqueName_Map *name_map = bmain->name_map;
443  do {
444  if (name_map != nullptr) {
445  int i = 0;
446  for (short idcode = BKE_idtype_idcode_iter_step(&i); idcode != 0;
447  idcode = BKE_idtype_idcode_iter_step(&i)) {
448  UniqueName_TypeMap *type_map = name_map->find_by_type(idcode);
449  if (type_map != nullptr) {
450  for (const UniqueName_Key &id_name : type_map->full_names) {
451  Uniqueness_Key key;
452  *(reinterpret_cast<short *>(key.name)) = idcode;
453  BLI_strncpy(key.name + 2, id_name.name, MAX_NAME);
454  key.lib = lib;
455  if (!id_names_libs.contains(key)) {
456  is_valid = false;
457  CLOG_ERROR(&LOG,
458  "ID name '%s' (from library '%s') is listed in the namemap, but does not "
459  "exists in current Main",
460  key.name,
461  lib != nullptr ? lib->filepath : "<None>");
462  }
463  }
464  }
465  }
466  }
467  lib = static_cast<Library *>((lib == nullptr) ? bmain->libraries.first : lib->id.next);
468  name_map = (lib != nullptr) ? lib->runtime.name_map : nullptr;
469  } while (lib != nullptr);
470 
471  if (is_valid || !do_fix) {
472  return is_valid;
473  }
474 
475  /* Clear all existing namemaps. */
476  lib = nullptr;
477  UniqueName_Map **name_map_p = &bmain->name_map;
478  do {
479  BLI_assert(name_map_p != nullptr);
480  if (*name_map_p != nullptr) {
481  BKE_main_namemap_destroy(name_map_p);
482  }
483  lib = static_cast<Library *>((lib == nullptr) ? bmain->libraries.first : lib->id.next);
484  name_map_p = (lib != nullptr) ? &lib->runtime.name_map : nullptr;
485  } while (lib != nullptr);
486 
487  return is_valid;
488 }
489 
491 {
492  const bool is_valid = main_namemap_validate_and_fix(bmain, true);
494  return is_valid;
495 }
496 
498 {
499  return main_namemap_validate_and_fix(bmain, false);
500 }
short BKE_idtype_idcode_iter_step(int *index)
Definition: idtype.c:442
int BKE_idtype_idcode_to_index(short idcode)
Definition: idtype.c:324
bool BKE_id_new_name_validate(struct Main *bmain, struct ListBase *lb, struct ID *id, const char *name, bool do_linked_data) ATTR_NONNULL(1
#define FOREACH_MAIN_ID_END
Definition: BKE_main.h:367
#define FOREACH_MAIN_LISTBASE_END
Definition: BKE_main.h:348
#define FOREACH_MAIN_LISTBASE_BEGIN(_bmain, _lb)
Definition: BKE_main.h:341
#define FOREACH_MAIN_ID_BEGIN(_bmain, _id)
Definition: BKE_main.h:361
struct ListBase * which_libbase(struct Main *bmain, short type)
Definition: main.c:567
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_assert_msg(a, msg)
Definition: BLI_assert.h:53
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition: BLI_bitmap.h:81
#define BLI_BITMAP_DISABLE(_bitmap, _index)
Definition: BLI_bitmap.h:88
int BLI_bitmap_find_first_unset(const BLI_bitmap *bitmap, size_t bits)
Definition: bitmap.c:51
#define BLI_BITMAP_TEST_BOOL(_bitmap, _index)
Definition: BLI_bitmap.h:74
unsigned int BLI_bitmap
Definition: BLI_bitmap.h:16
bool BLI_ghashutil_strcmp(const void *a, const void *b)
size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b)
unsigned int BLI_ghashutil_strhash_n(const char *key, size_t n)
unsigned int BLI_ghashutil_ptrhash(const void *key)
#define LISTBASE_FOREACH_MUTABLE(type, var, list)
Definition: BLI_listbase.h:354
size_t BLI_snprintf_rlen(char *__restrict dst, size_t maxncpy, const char *__restrict format,...) ATTR_NONNULL(1
char * BLI_strncpy(char *__restrict dst, const char *__restrict src, size_t maxncpy) ATTR_NONNULL()
Definition: string.c:64
int BLI_str_utf8_invalid_strip(char *str, size_t length) ATTR_NONNULL(1)
Definition: string_utf8.c:181
size_t BLI_split_name_num(char *left, int *nr, const char *name, char delim)
Definition: string_utils.c:25
#define ARRAY_SIZE(arr)
#define CLOG_ERROR(clg_ref,...)
Definition: CLG_log.h:190
#define CLOG_WARN(clg_ref,...)
Definition: CLG_log.h:189
ID and Library types, which are fundamental for sdna.
@ INDEX_ID_MAX
Definition: DNA_ID.h:1058
#define MAX_ID_NAME
Definition: DNA_ID.h:337
#define MAX_NAME
Definition: DNA_defs.h:48
Read Guarded memory(de)allocation.
void clear()
Definition: BLI_map.hh:963
int64_t size_in_bytes() const
Definition: BLI_map.hh:944
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition: BLI_map.hh:561
Value & lookup_or_add_default(const Key &key)
Definition: BLI_map.hh:580
bool remove(const Key &key)
Definition: BLI_map.hh:323
const Value * lookup_ptr(const Key &key) const
Definition: BLI_map.hh:463
int64_t size_in_bytes() const
Definition: BLI_set.hh:580
bool contains(const Key &key) const
Definition: BLI_set.hh:296
bool add(const Key &key)
Definition: BLI_set.hh:253
bool remove(const Key &key)
Definition: BLI_set.hh:371
std::string id_name(void *id)
bool is_valid
DRWShaderLibrary * lib
#define GS(x)
Definition: iris.c:225
bool BKE_main_namemap_validate_and_fix(Main *bmain)
static UniqueName_Map * get_namemap_for(Main *bmain, ID *id, bool ensure_created)
#define MIN_NUMBER
Definition: main_namemap.cc:37
void BKE_main_namemap_remove_name(struct Main *bmain, struct ID *id, const char *name)
static bool id_name_final_build(char *name, char *base_name, size_t base_name_len, int number)
Definition: main_namemap.cc:47
bool BKE_main_namemap_get_name(struct Main *bmain, struct ID *id, char *name)
bool BKE_main_namemap_validate(Main *bmain)
void BKE_main_namemap_destroy(struct UniqueName_Map **r_name_map)
static bool main_namemap_validate_and_fix(Main *bmain, const bool do_fix)
static void main_namemap_populate(UniqueName_Map *name_map, struct Main *bmain, ID *ignore_id)
struct UniqueName_Map * BKE_main_namemap_create()
#define MAX_NUMBER
Definition: main_namemap.cc:35
static CLG_LogRef LOG
Definition: main_namemap.cc:28
ccl_device_inline float4 mask(const int4 &mask, const float4 &a)
Definition: math_float4.h:513
void max_inplace(T &a, const T &b)
SocketIndexByIdentifierMap * map
__int64 int64_t
Definition: stdint.h:89
unsigned __int64 uint64_t
Definition: stdint.h:90
Definition: DNA_ID.h:368
struct Library * lib
Definition: DNA_ID.h:372
char name[66]
Definition: DNA_ID.h:378
struct UniqueName_Map * name_map
Definition: DNA_ID.h:450
struct Library_Runtime runtime
Definition: DNA_ID.h:486
void * first
Definition: DNA_listBase.h:31
Definition: BKE_main.h:121
ListBase libraries
Definition: BKE_main.h:169
struct UniqueName_Map * name_map
Definition: BKE_main.h:224
uint64_t hash() const
Definition: main_namemap.cc:80
char name[MAX_NAME]
Definition: main_namemap.cc:79
bool operator==(const UniqueName_Key &o) const
Definition: main_namemap.cc:84
UniqueName_TypeMap * find_by_type(short id_type)
UniqueName_TypeMap type_maps[INDEX_ID_MAX]
Set< UniqueName_Key > full_names
Map< UniqueName_Key, UniqueName_Value > base_name_to_num_suffix
void mark_used(int number)
BLI_BITMAP_DECLARE(mask, max_exact_tracking)
void mark_unused(int number)
bool use_if_unused(int number)
uint64_t hash() const
bool operator==(const Uniqueness_Key &o) const
char name[MAX_ID_NAME]
static FT_Library library