Merge branch 'master' into blender2.8
[blender.git] / source / blender / editors / space_outliner / outliner_tree.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Joshua Leung
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/space_outliner/outliner_tree.c
29  *  \ingroup spoutliner
30  */
31
32 #include <math.h>
33 #include <string.h>
34
35 #include "MEM_guardedalloc.h"
36
37 #include "DNA_anim_types.h"
38 #include "DNA_armature_types.h"
39 #include "DNA_constraint_types.h"
40 #include "DNA_camera_types.h"
41 #include "DNA_cachefile_types.h"
42 #include "DNA_gpencil_types.h"
43 #include "DNA_group_types.h"
44 #include "DNA_key_types.h"
45 #include "DNA_lamp_types.h"
46 #include "DNA_material_types.h"
47 #include "DNA_mesh_types.h"
48 #include "DNA_meta_types.h"
49 #include "DNA_lightprobe_types.h"
50 #include "DNA_particle_types.h"
51 #include "DNA_scene_types.h"
52 #include "DNA_world_types.h"
53 #include "DNA_sequence_types.h"
54 #include "DNA_speaker_types.h"
55 #include "DNA_object_types.h"
56 #include "DNA_linestyle_types.h"
57
58 #include "BLI_blenlib.h"
59 #include "BLI_utildefines.h"
60 #include "BLI_mempool.h"
61 #include "BLI_fnmatch.h"
62
63 #include "BLT_translation.h"
64
65 #include "BKE_fcurve.h"
66 #include "BKE_main.h"
67 #include "BKE_layer.h"
68 #include "BKE_library.h"
69 #include "BKE_modifier.h"
70 #include "BKE_sequencer.h"
71 #include "BKE_idcode.h"
72 #include "BKE_outliner_treehash.h"
73
74 #include "DEG_depsgraph.h"
75 #include "DEG_depsgraph_build.h"
76
77 #include "ED_armature.h"
78 #include "ED_screen.h"
79
80 #include "WM_api.h"
81 #include "WM_types.h"
82
83 #include "RNA_access.h"
84
85 #include "UI_interface.h"
86
87 #include "outliner_intern.h"
88
89 #ifdef WIN32
90 #  include "BLI_math_base.h" /* M_PI */
91 #endif
92
93 /* prototypes */
94 static TreeElement *outliner_add_collection_recursive(
95         SpaceOops *soops, Collection *collection, TreeElement *ten);
96 static void outliner_make_object_parent_hierarchy(ListBase *lb);
97
98 /* ********************************************************* */
99 /* Persistent Data */
100
101 static void outliner_storage_cleanup(SpaceOops *soops)
102 {
103         BLI_mempool *ts = soops->treestore;
104
105         if (ts) {
106                 TreeStoreElem *tselem;
107                 int unused = 0;
108
109                 /* each element used once, for ID blocks with more users to have each a treestore */
110                 BLI_mempool_iter iter;
111
112                 BLI_mempool_iternew(ts, &iter);
113                 while ((tselem = BLI_mempool_iterstep(&iter))) {
114                         tselem->used = 0;
115                 }
116
117                 /* cleanup only after reading file or undo step, and always for
118                  * RNA datablocks view in order to save memory */
119                 if (soops->storeflag & SO_TREESTORE_CLEANUP) {
120                         soops->storeflag &= ~SO_TREESTORE_CLEANUP;
121
122                         BLI_mempool_iternew(ts, &iter);
123                         while ((tselem = BLI_mempool_iterstep(&iter))) {
124                                 if (tselem->id == NULL) unused++;
125                         }
126
127                         if (unused) {
128                                 if (BLI_mempool_len(ts) == unused) {
129                                         BLI_mempool_destroy(ts);
130                                         soops->treestore = NULL;
131                                         if (soops->treehash) {
132                                                 BKE_outliner_treehash_free(soops->treehash);
133                                                 soops->treehash = NULL;
134                                         }
135                                 }
136                                 else {
137                                         TreeStoreElem *tsenew;
138                                         BLI_mempool *new_ts = BLI_mempool_create(sizeof(TreeStoreElem), BLI_mempool_len(ts) - unused,
139                                                                                  512, BLI_MEMPOOL_ALLOW_ITER);
140                                         BLI_mempool_iternew(ts, &iter);
141                                         while ((tselem = BLI_mempool_iterstep(&iter))) {
142                                                 if (tselem->id) {
143                                                         tsenew = BLI_mempool_alloc(new_ts);
144                                                         *tsenew = *tselem;
145                                                 }
146                                         }
147                                         BLI_mempool_destroy(ts);
148                                         soops->treestore = new_ts;
149                                         if (soops->treehash) {
150                                                 /* update hash table to fix broken pointers */
151                                                 BKE_outliner_treehash_rebuild_from_treestore(soops->treehash, soops->treestore);
152                                         }
153                                 }
154                         }
155                 }
156                 else if (soops->treehash) {
157                         BKE_outliner_treehash_clear_used(soops->treehash);
158                 }
159         }
160 }
161
162 static void check_persistent(SpaceOops *soops, TreeElement *te, ID *id, short type, short nr)
163 {
164         TreeStoreElem *tselem;
165
166         if (soops->treestore == NULL) {
167                 /* if treestore was not created in readfile.c, create it here */
168                 soops->treestore = BLI_mempool_create(sizeof(TreeStoreElem), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
169
170         }
171         if (soops->treehash == NULL) {
172                 soops->treehash = BKE_outliner_treehash_create_from_treestore(soops->treestore);
173         }
174
175         /* find any unused tree element in treestore and mark it as used
176          * (note that there may be multiple unused elements in case of linked objects) */
177         tselem = BKE_outliner_treehash_lookup_unused(soops->treehash, type, nr, id);
178         if (tselem) {
179                 te->store_elem = tselem;
180                 tselem->used = 1;
181                 return;
182         }
183
184         /* add 1 element to treestore */
185         tselem = BLI_mempool_alloc(soops->treestore);
186         tselem->type = type;
187         tselem->nr = type ? nr : 0;
188         tselem->id = id;
189         tselem->used = 0;
190         tselem->flag = TSE_CLOSED;
191         te->store_elem = tselem;
192         BKE_outliner_treehash_add_element(soops->treehash, tselem);
193 }
194
195 /* ********************************************************* */
196 /* Tree Management */
197
198 void outliner_free_tree(ListBase *tree)
199 {
200         for (TreeElement *element = tree->first, *element_next; element; element = element_next) {
201                 element_next = element->next;
202                 outliner_free_tree_element(element, tree);
203         }
204 }
205
206 void outliner_cleanup_tree(SpaceOops *soops)
207 {
208         outliner_free_tree(&soops->tree);
209         outliner_storage_cleanup(soops);
210 }
211
212 /**
213  * Free \a element and its sub-tree and remove its link in \a parent_subtree.
214  *
215  * \note Does not remove the TreeStoreElem of \a element!
216  * \param parent_subtree Subtree of the parent element, so the list containing \a element.
217  */
218 void outliner_free_tree_element(TreeElement *element, ListBase *parent_subtree)
219 {
220         BLI_assert(BLI_findindex(parent_subtree, element) > -1);
221         BLI_remlink(parent_subtree, element);
222
223         outliner_free_tree(&element->subtree);
224
225         if (element->flag & TE_FREE_NAME) {
226                 MEM_freeN((void *)element->name);
227         }
228         MEM_freeN(element);
229 }
230
231
232 /* ********************************************************* */
233
234 /* Prototype, see functions below */
235 static TreeElement *outliner_add_element(SpaceOops *soops, ListBase *lb, void *idv,
236                                          TreeElement *parent, short type, short index);
237
238 /* -------------------------------------------------------- */
239
240 /* special handling of hierarchical non-lib data */
241 static void outliner_add_bone(SpaceOops *soops, ListBase *lb, ID *id, Bone *curBone,
242                               TreeElement *parent, int *a)
243 {
244         TreeElement *te = outliner_add_element(soops, lb, id, parent, TSE_BONE, *a);
245
246         (*a)++;
247         te->name = curBone->name;
248         te->directdata = curBone;
249
250         for (curBone = curBone->childbase.first; curBone; curBone = curBone->next) {
251                 outliner_add_bone(soops, &te->subtree, id, curBone, te, a);
252         }
253 }
254
255 static bool outliner_animdata_test(AnimData *adt)
256 {
257         if (adt)
258                 return (adt->action || adt->drivers.first || adt->nla_tracks.first);
259         return false;
260 }
261
262 #ifdef WITH_FREESTYLE
263 static void outliner_add_line_styles(SpaceOops *soops, ListBase *lb, Scene *sce, TreeElement *te)
264 {
265         ViewLayer *view_layer;
266         FreestyleLineSet *lineset;
267
268         for (view_layer = sce->view_layers.first; view_layer; view_layer = view_layer->next) {
269                 for (lineset = view_layer->freestyle_config.linesets.first; lineset; lineset = lineset->next) {
270                         FreestyleLineStyle *linestyle = lineset->linestyle;
271                         if (linestyle) {
272                                 linestyle->id.tag |= LIB_TAG_DOIT;
273                         }
274                 }
275         }
276         for (view_layer = sce->view_layers.first; view_layer; view_layer = view_layer->next) {
277                 for (lineset = view_layer->freestyle_config.linesets.first; lineset; lineset = lineset->next) {
278                         FreestyleLineStyle *linestyle = lineset->linestyle;
279                         if (linestyle) {
280                                 if (!(linestyle->id.tag & LIB_TAG_DOIT))
281                                         continue;
282                                 linestyle->id.tag &= ~LIB_TAG_DOIT;
283                                 outliner_add_element(soops, lb, linestyle, te, 0, 0);
284                         }
285                 }
286         }
287 }
288 #endif
289
290 static void outliner_add_scene_contents(SpaceOops *soops, ListBase *lb, Scene *sce, TreeElement *te)
291 {
292         /* View layers */
293         TreeElement *ten = outliner_add_element(soops, lb, sce, te, TSE_R_LAYER_BASE, 0);
294         ten->name = IFACE_("View Layers");
295
296         ViewLayer *view_layer;
297         for (view_layer = sce->view_layers.first; view_layer; view_layer = view_layer->next) {
298                 TreeElement *tenlay = outliner_add_element(soops, &ten->subtree, sce, te, TSE_R_LAYER, 0);
299                 tenlay->name = view_layer->name;
300                 tenlay->directdata = view_layer;
301         }
302
303         /* Collections */
304         ten = outliner_add_element(soops, lb, &sce->id, te, TSE_SCENE_COLLECTION_BASE, 0);
305         ten->name = IFACE_("Scene Collection");
306         outliner_add_collection_recursive(soops, sce->master_collection, ten);
307
308         /* Objects */
309         ten = outliner_add_element(soops, lb, sce, te, TSE_SCENE_OBJECTS_BASE, 0);
310         ten->name = IFACE_("Objects");
311         FOREACH_SCENE_OBJECT_BEGIN(sce, ob)
312         {
313                 outliner_add_element(soops, &ten->subtree, ob, NULL, 0, 0);
314         }
315         FOREACH_SCENE_OBJECT_END;
316         outliner_make_object_parent_hierarchy(&ten->subtree);
317
318         /* Animation Data */
319         if (outliner_animdata_test(sce->adt))
320                 outliner_add_element(soops, lb, sce, te, TSE_ANIM_DATA, 0);
321
322         /* Grease Pencil */
323         outliner_add_element(soops, lb, sce->gpd, te, 0, 0);
324 }
325
326 TreeTraversalAction outliner_find_selected_objects(TreeElement *te, void *customdata)
327 {
328         struct ObjectsSelectedData *data = customdata;
329         TreeStoreElem *tselem = TREESTORE(te);
330
331         if (outliner_is_collection_tree_element(te)) {
332                 return TRAVERSE_CONTINUE;
333         }
334
335         if (tselem->type || (tselem->id == NULL) || (GS(tselem->id->name) != ID_OB)) {
336                 return TRAVERSE_SKIP_CHILDS;
337         }
338
339         BLI_addtail(&data->objects_selected_array, BLI_genericNodeN(te));
340
341         return TRAVERSE_CONTINUE;
342 }
343
344 /**
345  * Move objects from a collection to another.
346  * We ignore the original object being inserted, we used it for polling only.
347  * Instead we move all the selected objects around.
348  */
349 static void outliner_object_reorder(
350         Main *bmain, Scene *scene,
351         SpaceOops *soops,
352         TreeElement *insert_element,
353         TreeElement *insert_handle, TreeElementInsertType action,
354         const wmEvent *event)
355 {
356         Collection *collection = outliner_collection_from_tree_element(insert_handle);
357         Collection *collection_ob_parent = NULL;
358         ID *id = insert_handle->store_elem->id;
359
360         BLI_assert(action == TE_INSERT_INTO);
361         UNUSED_VARS_NDEBUG(action);
362
363         struct ObjectsSelectedData data = {
364                 .objects_selected_array  = {NULL, NULL},
365         };
366
367         const bool is_append = event->ctrl;
368
369         /* Make sure we include the originally inserted element as well. */
370         TREESTORE(insert_element)->flag |= TSE_SELECTED;
371
372         outliner_tree_traverse(soops, &soops->tree, 0, TSE_SELECTED, outliner_find_selected_objects, &data);
373         LISTBASE_FOREACH (LinkData *, link, &data.objects_selected_array) {
374                 TreeElement *ten_selected = (TreeElement *)link->data;
375                 Object *ob = (Object *)TREESTORE(ten_selected)->id;
376
377                 if (is_append) {
378                         BKE_collection_object_add(bmain, collection, ob);
379                         continue;
380                 }
381
382                 /* Find parent collection of object. */
383                 if (ten_selected->parent) {
384                         for (TreeElement *te_ob_parent = ten_selected->parent; te_ob_parent; te_ob_parent = te_ob_parent->parent) {
385                                 if (outliner_is_collection_tree_element(te_ob_parent)) {
386                                         collection_ob_parent = outliner_collection_from_tree_element(te_ob_parent);
387                                         break;
388                                 }
389                         }
390                 }
391                 else {
392                         collection_ob_parent = BKE_collection_master(scene);
393                 }
394
395                 BKE_collection_object_move(bmain, scene, collection, collection_ob_parent, ob);
396         }
397
398         BLI_freelistN(&data.objects_selected_array);
399
400         DEG_relations_tag_update(bmain);
401
402         /* TODO(sergey): Use proper flag for tagging here. */
403         DEG_id_tag_update(id, 0);
404
405         WM_main_add_notifier(NC_SCENE | ND_LAYER, NULL);
406 }
407
408 static bool outliner_object_reorder_poll(
409         const TreeElement *insert_element,
410         TreeElement **io_insert_handle, TreeElementInsertType *io_action)
411 {
412         if (outliner_is_collection_tree_element(*io_insert_handle) &&
413             (insert_element->parent != *io_insert_handle))
414         {
415                 *io_action = TE_INSERT_INTO;
416                 return true;
417         }
418
419         return false;
420 }
421
422 // can be inlined if necessary
423 static void outliner_add_object_contents(SpaceOops *soops, TreeElement *te, TreeStoreElem *tselem, Object *ob)
424 {
425         te->reinsert = outliner_object_reorder;
426         te->reinsert_poll = outliner_object_reorder_poll;
427
428         if (outliner_animdata_test(ob->adt))
429                 outliner_add_element(soops, &te->subtree, ob, te, TSE_ANIM_DATA, 0);
430
431         outliner_add_element(soops, &te->subtree, ob->poselib, te, 0, 0); // XXX FIXME.. add a special type for this
432
433         if (ob->proxy && !ID_IS_LINKED(ob))
434                 outliner_add_element(soops, &te->subtree, ob->proxy, te, TSE_PROXY, 0);
435
436         outliner_add_element(soops, &te->subtree, ob->gpd, te, 0, 0);
437
438         outliner_add_element(soops, &te->subtree, ob->data, te, 0, 0);
439
440         if (ob->pose) {
441                 bArmature *arm = ob->data;
442                 bPoseChannel *pchan;
443                 TreeElement *tenla = outliner_add_element(soops, &te->subtree, ob, te, TSE_POSE_BASE, 0);
444
445                 tenla->name = IFACE_("Pose");
446
447                 /* channels undefined in editmode, but we want the 'tenla' pose icon itself */
448                 if ((arm->edbo == NULL) && (ob->mode & OB_MODE_POSE)) {
449                         TreeElement *ten;
450                         int a = 0, const_index = 1000;    /* ensure unique id for bone constraints */
451
452                         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next, a++) {
453                                 ten = outliner_add_element(soops, &tenla->subtree, ob, tenla, TSE_POSE_CHANNEL, a);
454                                 ten->name = pchan->name;
455                                 ten->directdata = pchan;
456                                 pchan->temp = (void *)ten;
457
458                                 if (pchan->constraints.first) {
459                                         //Object *target;
460                                         bConstraint *con;
461                                         TreeElement *ten1;
462                                         TreeElement *tenla1 = outliner_add_element(soops, &ten->subtree, ob, ten, TSE_CONSTRAINT_BASE, 0);
463                                         //char *str;
464
465                                         tenla1->name = IFACE_("Constraints");
466                                         for (con = pchan->constraints.first; con; con = con->next, const_index++) {
467                                                 ten1 = outliner_add_element(soops, &tenla1->subtree, ob, tenla1, TSE_CONSTRAINT, const_index);
468 #if 0 /* disabled as it needs to be reworked for recoded constraints system */
469                                                 target = get_constraint_target(con, &str);
470                                                 if (str && str[0]) ten1->name = str;
471                                                 else if (target) ten1->name = target->id.name + 2;
472                                                 else ten1->name = con->name;
473 #endif
474                                                 ten1->name = con->name;
475                                                 ten1->directdata = con;
476                                                 /* possible add all other types links? */
477                                         }
478                                 }
479                         }
480                         /* make hierarchy */
481                         ten = tenla->subtree.first;
482                         while (ten) {
483                                 TreeElement *nten = ten->next, *par;
484                                 tselem = TREESTORE(ten);
485                                 if (tselem->type == TSE_POSE_CHANNEL) {
486                                         pchan = (bPoseChannel *)ten->directdata;
487                                         if (pchan->parent) {
488                                                 BLI_remlink(&tenla->subtree, ten);
489                                                 par = (TreeElement *)pchan->parent->temp;
490                                                 BLI_addtail(&par->subtree, ten);
491                                                 ten->parent = par;
492                                         }
493                                 }
494                                 ten = nten;
495                         }
496                 }
497
498                 /* Pose Groups */
499                 if (ob->pose->agroups.first) {
500                         bActionGroup *agrp;
501                         TreeElement *ten_bonegrp = outliner_add_element(soops, &te->subtree, ob, te, TSE_POSEGRP_BASE, 0);
502                         int a = 0;
503
504                         ten_bonegrp->name = IFACE_("Bone Groups");
505                         for (agrp = ob->pose->agroups.first; agrp; agrp = agrp->next, a++) {
506                                 TreeElement *ten;
507                                 ten = outliner_add_element(soops, &ten_bonegrp->subtree, ob, ten_bonegrp, TSE_POSEGRP, a);
508                                 ten->name = agrp->name;
509                                 ten->directdata = agrp;
510                         }
511                 }
512         }
513
514         for (int a = 0; a < ob->totcol; a++) {
515                 outliner_add_element(soops, &te->subtree, ob->mat[a], te, 0, a);
516         }
517
518         if (ob->constraints.first) {
519                 //Object *target;
520                 bConstraint *con;
521                 TreeElement *ten;
522                 TreeElement *tenla = outliner_add_element(soops, &te->subtree, ob, te, TSE_CONSTRAINT_BASE, 0);
523                 //char *str;
524                 int a;
525
526                 tenla->name = IFACE_("Constraints");
527                 for (con = ob->constraints.first, a = 0; con; con = con->next, a++) {
528                         ten = outliner_add_element(soops, &tenla->subtree, ob, tenla, TSE_CONSTRAINT, a);
529 #if 0 /* disabled due to constraints system targets recode... code here needs review */
530                         target = get_constraint_target(con, &str);
531                         if (str && str[0]) ten->name = str;
532                         else if (target) ten->name = target->id.name + 2;
533                         else ten->name = con->name;
534 #endif
535                         ten->name = con->name;
536                         ten->directdata = con;
537                         /* possible add all other types links? */
538                 }
539         }
540
541         if (ob->modifiers.first) {
542                 ModifierData *md;
543                 TreeElement *ten_mod = outliner_add_element(soops, &te->subtree, ob, te, TSE_MODIFIER_BASE, 0);
544                 int index;
545
546                 ten_mod->name = IFACE_("Modifiers");
547                 for (index = 0, md = ob->modifiers.first; md; index++, md = md->next) {
548                         TreeElement *ten = outliner_add_element(soops, &ten_mod->subtree, ob, ten_mod, TSE_MODIFIER, index);
549                         ten->name = md->name;
550                         ten->directdata = md;
551
552                         if (md->type == eModifierType_Lattice) {
553                                 outliner_add_element(soops, &ten->subtree, ((LatticeModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
554                         }
555                         else if (md->type == eModifierType_Curve) {
556                                 outliner_add_element(soops, &ten->subtree, ((CurveModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
557                         }
558                         else if (md->type == eModifierType_Armature) {
559                                 outliner_add_element(soops, &ten->subtree, ((ArmatureModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
560                         }
561                         else if (md->type == eModifierType_Hook) {
562                                 outliner_add_element(soops, &ten->subtree, ((HookModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
563                         }
564                         else if (md->type == eModifierType_ParticleSystem) {
565                                 ParticleSystem *psys = ((ParticleSystemModifierData *) md)->psys;
566                                 TreeElement *ten_psys;
567
568                                 ten_psys = outliner_add_element(soops, &ten->subtree, ob, te, TSE_LINKED_PSYS, 0);
569                                 ten_psys->directdata = psys;
570                                 ten_psys->name = psys->part->id.name + 2;
571                         }
572                 }
573         }
574
575         /* vertex groups */
576         if (ob->defbase.first) {
577                 bDeformGroup *defgroup;
578                 TreeElement *ten;
579                 TreeElement *tenla = outliner_add_element(soops, &te->subtree, ob, te, TSE_DEFGROUP_BASE, 0);
580                 int a;
581
582                 tenla->name = IFACE_("Vertex Groups");
583                 for (defgroup = ob->defbase.first, a = 0; defgroup; defgroup = defgroup->next, a++) {
584                         ten = outliner_add_element(soops, &tenla->subtree, ob, tenla, TSE_DEFGROUP, a);
585                         ten->name = defgroup->name;
586                         ten->directdata = defgroup;
587                 }
588         }
589
590         /* duplicated group */
591         if (ob->dup_group)
592                 outliner_add_element(soops, &te->subtree, ob->dup_group, te, 0, 0);
593 }
594
595
596 // can be inlined if necessary
597 static void outliner_add_id_contents(SpaceOops *soops, TreeElement *te, TreeStoreElem *tselem, ID *id)
598 {
599         /* tuck pointer back in object, to construct hierarchy */
600         if (GS(id->name) == ID_OB) id->newid = (ID *)te;
601
602         /* expand specific data always */
603         switch (GS(id->name)) {
604                 case ID_LI:
605                 {
606                         te->name = ((Library *)id)->name;
607                         break;
608                 }
609                 case ID_SCE:
610                 {
611                         outliner_add_scene_contents(soops, &te->subtree, (Scene *)id, te);
612                         break;
613                 }
614                 case ID_OB:
615                 {
616                         outliner_add_object_contents(soops, te, tselem, (Object *)id);
617                         break;
618                 }
619                 case ID_ME:
620                 {
621                         Mesh *me = (Mesh *)id;
622                         int a;
623
624                         if (outliner_animdata_test(me->adt))
625                                 outliner_add_element(soops, &te->subtree, me, te, TSE_ANIM_DATA, 0);
626
627                         outliner_add_element(soops, &te->subtree, me->key, te, 0, 0);
628                         for (a = 0; a < me->totcol; a++)
629                                 outliner_add_element(soops, &te->subtree, me->mat[a], te, 0, a);
630                         /* could do tfaces with image links, but the images are not grouped nicely.
631                          * would require going over all tfaces, sort images in use. etc... */
632                         break;
633                 }
634                 case ID_CU:
635                 {
636                         Curve *cu = (Curve *)id;
637                         int a;
638
639                         if (outliner_animdata_test(cu->adt))
640                                 outliner_add_element(soops, &te->subtree, cu, te, TSE_ANIM_DATA, 0);
641
642                         for (a = 0; a < cu->totcol; a++)
643                                 outliner_add_element(soops, &te->subtree, cu->mat[a], te, 0, a);
644                         break;
645                 }
646                 case ID_MB:
647                 {
648                         MetaBall *mb = (MetaBall *)id;
649                         int a;
650
651                         if (outliner_animdata_test(mb->adt))
652                                 outliner_add_element(soops, &te->subtree, mb, te, TSE_ANIM_DATA, 0);
653
654                         for (a = 0; a < mb->totcol; a++)
655                                 outliner_add_element(soops, &te->subtree, mb->mat[a], te, 0, a);
656                         break;
657                 }
658                 case ID_MA:
659                 {
660                         Material *ma = (Material *)id;
661
662                         if (outliner_animdata_test(ma->adt))
663                                 outliner_add_element(soops, &te->subtree, ma, te, TSE_ANIM_DATA, 0);
664                         break;
665                 }
666                 case ID_TE:
667                 {
668                         Tex *tex = (Tex *)id;
669
670                         if (outliner_animdata_test(tex->adt))
671                                 outliner_add_element(soops, &te->subtree, tex, te, TSE_ANIM_DATA, 0);
672
673                         outliner_add_element(soops, &te->subtree, tex->ima, te, 0, 0);
674                         break;
675                 }
676                 case ID_CA:
677                 {
678                         Camera *ca = (Camera *)id;
679
680                         if (outliner_animdata_test(ca->adt))
681                                 outliner_add_element(soops, &te->subtree, ca, te, TSE_ANIM_DATA, 0);
682                         break;
683                 }
684                 case ID_CF:
685                 {
686                         CacheFile *cache_file = (CacheFile *)id;
687
688                         if (outliner_animdata_test(cache_file->adt)) {
689                                 outliner_add_element(soops, &te->subtree, cache_file, te, TSE_ANIM_DATA, 0);
690                         }
691
692                         break;
693                 }
694                 case ID_LA:
695                 {
696                         Lamp *la = (Lamp *)id;
697
698                         if (outliner_animdata_test(la->adt))
699                                 outliner_add_element(soops, &te->subtree, la, te, TSE_ANIM_DATA, 0);
700                         break;
701                 }
702                 case ID_SPK:
703                 {
704                         Speaker *spk = (Speaker *)id;
705
706                         if (outliner_animdata_test(spk->adt))
707                                 outliner_add_element(soops, &te->subtree, spk, te, TSE_ANIM_DATA, 0);
708                         break;
709                 }
710                 case ID_LP:
711                 {
712                         LightProbe *prb = (LightProbe *)id;
713
714                         if (outliner_animdata_test(prb->adt))
715                                 outliner_add_element(soops, &te->subtree, prb, te, TSE_ANIM_DATA, 0);
716                         break;
717                 }
718                 case ID_WO:
719                 {
720                         World *wrld = (World *)id;
721
722                         if (outliner_animdata_test(wrld->adt))
723                                 outliner_add_element(soops, &te->subtree, wrld, te, TSE_ANIM_DATA, 0);
724                         break;
725                 }
726                 case ID_KE:
727                 {
728                         Key *key = (Key *)id;
729
730                         if (outliner_animdata_test(key->adt))
731                                 outliner_add_element(soops, &te->subtree, key, te, TSE_ANIM_DATA, 0);
732                         break;
733                 }
734                 case ID_AC:
735                 {
736                         // XXX do we want to be exposing the F-Curves here?
737                         //bAction *act = (bAction *)id;
738                         break;
739                 }
740                 case ID_AR:
741                 {
742                         bArmature *arm = (bArmature *)id;
743                         int a = 0;
744
745                         if (outliner_animdata_test(arm->adt))
746                                 outliner_add_element(soops, &te->subtree, arm, te, TSE_ANIM_DATA, 0);
747
748                         if (arm->edbo) {
749                                 EditBone *ebone;
750                                 TreeElement *ten;
751
752                                 for (ebone = arm->edbo->first; ebone; ebone = ebone->next, a++) {
753                                         ten = outliner_add_element(soops, &te->subtree, id, te, TSE_EBONE, a);
754                                         ten->directdata = ebone;
755                                         ten->name = ebone->name;
756                                         ebone->temp.p = ten;
757                                 }
758                                 /* make hierarchy */
759                                 ten = arm->edbo->first ? ((EditBone *)arm->edbo->first)->temp.p : NULL;
760                                 while (ten) {
761                                         TreeElement *nten = ten->next, *par;
762                                         ebone = (EditBone *)ten->directdata;
763                                         if (ebone->parent) {
764                                                 BLI_remlink(&te->subtree, ten);
765                                                 par = ebone->parent->temp.p;
766                                                 BLI_addtail(&par->subtree, ten);
767                                                 ten->parent = par;
768                                         }
769                                         ten = nten;
770                                 }
771                         }
772                         else {
773                                 /* do not extend Armature when we have posemode */
774                                 tselem = TREESTORE(te->parent);
775                                 if (GS(tselem->id->name) == ID_OB && ((Object *)tselem->id)->mode & OB_MODE_POSE) {
776                                         /* pass */
777                                 }
778                                 else {
779                                         Bone *curBone;
780                                         for (curBone = arm->bonebase.first; curBone; curBone = curBone->next) {
781                                                 outliner_add_bone(soops, &te->subtree, id, curBone, te, &a);
782                                         }
783                                 }
784                         }
785                         break;
786                 }
787                 case ID_LS:
788                 {
789                         FreestyleLineStyle *linestyle = (FreestyleLineStyle *)id;
790                         int a;
791
792                         if (outliner_animdata_test(linestyle->adt))
793                                 outliner_add_element(soops, &te->subtree, linestyle, te, TSE_ANIM_DATA, 0);
794
795                         for (a = 0; a < MAX_MTEX; a++) {
796                                 if (linestyle->mtex[a])
797                                         outliner_add_element(soops, &te->subtree, linestyle->mtex[a]->tex, te, 0, a);
798                         }
799                         break;
800                 }
801                 case ID_GD:
802                 {
803                         bGPdata *gpd = (bGPdata *)id;
804                         bGPDlayer *gpl;
805                         int a = 0;
806
807                         if (outliner_animdata_test(gpd->adt))
808                                 outliner_add_element(soops, &te->subtree, gpd, te, TSE_ANIM_DATA, 0);
809
810                         // TODO: base element for layers?
811                         for (gpl = gpd->layers.first; gpl; gpl = gpl->next) {
812                                 outliner_add_element(soops, &te->subtree, gpl, te, TSE_GP_LAYER, a);
813                                 a++;
814                         }
815                         break;
816                 }
817                 case ID_GR:
818                 {
819                         /* Don't expand for instances, creates too many elements. */
820                         if (!(te->parent && te->parent->idcode == ID_OB)) {
821                                 Collection *collection = (Collection *)id;
822                                 outliner_add_collection_recursive(soops, collection, te);
823                         }
824                 }
825                 default:
826                         break;
827         }
828 }
829
830 // TODO: this function needs to be split up! It's getting a bit too large...
831 // Note: "ID" is not always a real ID
832 static TreeElement *outliner_add_element(SpaceOops *soops, ListBase *lb, void *idv,
833                                          TreeElement *parent, short type, short index)
834 {
835         TreeElement *te;
836         TreeStoreElem *tselem;
837         ID *id = idv;
838
839         if (ELEM(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
840                 id = ((PointerRNA *)idv)->id.data;
841                 if (!id) id = ((PointerRNA *)idv)->data;
842         }
843         else if (type == TSE_GP_LAYER) {
844                 /* idv is the layer its self */
845                 id = TREESTORE(parent)->id;
846         }
847
848         /* exceptions */
849         if (type == TSE_ID_BASE) {
850                 /* pass */
851         }
852         else if (id == NULL) {
853                 return NULL;
854         }
855
856         if (type == 0) {
857                 /* Zero type means real ID, ensure we do not get non-outliner ID types here... */
858                 BLI_assert(TREESTORE_ID_TYPE(id));
859         }
860
861         te = MEM_callocN(sizeof(TreeElement), "tree elem");
862         /* add to the visual tree */
863         BLI_addtail(lb, te);
864         /* add to the storage */
865         check_persistent(soops, te, id, type, index);
866         tselem = TREESTORE(te);
867
868         /* if we are searching for something expand to see child elements */
869         if (SEARCHING_OUTLINER(soops))
870                 tselem->flag |= TSE_CHILDSEARCH;
871
872         te->parent = parent;
873         te->index = index;   // for data arays
874         if (ELEM(type, TSE_SEQUENCE, TSE_SEQ_STRIP, TSE_SEQUENCE_DUP)) {
875                 /* pass */
876         }
877         else if (ELEM(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
878                 /* pass */
879         }
880         else if (type == TSE_ANIM_DATA) {
881                 /* pass */
882         }
883         else if (type == TSE_GP_LAYER) {
884                 /* pass */
885         }
886         else if (ELEM(type, TSE_LAYER_COLLECTION, TSE_SCENE_COLLECTION_BASE, TSE_VIEW_COLLECTION_BASE)) {
887                 /* pass */
888         }
889         else if (type == TSE_ID_BASE) {
890                 /* pass */
891         }
892         else {
893                 /* do here too, for blend file viewer, own ID_LI then shows file name */
894                 if (GS(id->name) == ID_LI)
895                         te->name = ((Library *)id)->name;
896                 else
897                         te->name = id->name + 2; // default, can be overridden by Library or non-ID data
898                 te->idcode = GS(id->name);
899         }
900
901         if (type == 0) {
902                 TreeStoreElem *tsepar = parent ? TREESTORE(parent) : NULL;
903
904                 /* ID datablock */
905                 if (tsepar == NULL || tsepar->type != TSE_ID_BASE || soops->filter_id_type) {
906                         outliner_add_id_contents(soops, te, tselem, id);
907                 }
908         }
909         else if (type == TSE_ANIM_DATA) {
910                 IdAdtTemplate *iat = (IdAdtTemplate *)idv;
911                 AnimData *adt = (AnimData *)iat->adt;
912
913                 /* this element's info */
914                 te->name = IFACE_("Animation");
915                 te->directdata = adt;
916
917                 /* Action */
918                 outliner_add_element(soops, &te->subtree, adt->action, te, 0, 0);
919
920                 /* Drivers */
921                 if (adt->drivers.first) {
922                         TreeElement *ted = outliner_add_element(soops, &te->subtree, adt, te, TSE_DRIVER_BASE, 0);
923                         ID *lastadded = NULL;
924                         FCurve *fcu;
925
926                         ted->name = IFACE_("Drivers");
927
928                         for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
929                                 if (fcu->driver && fcu->driver->variables.first) {
930                                         ChannelDriver *driver = fcu->driver;
931                                         DriverVar *dvar;
932
933                                         for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
934                                                 /* loop over all targets used here */
935                                                 DRIVER_TARGETS_USED_LOOPER(dvar)
936                                                 {
937                                                         if (lastadded != dtar->id) {
938                                                                 // XXX this lastadded check is rather lame, and also fails quite badly...
939                                                                 outliner_add_element(soops, &ted->subtree, dtar->id, ted, TSE_LINKED_OB, 0);
940                                                                 lastadded = dtar->id;
941                                                         }
942                                                 }
943                                                 DRIVER_TARGETS_LOOPER_END
944                                         }
945                                 }
946                         }
947                 }
948
949                 /* NLA Data */
950                 if (adt->nla_tracks.first) {
951                         TreeElement *tenla = outliner_add_element(soops, &te->subtree, adt, te, TSE_NLA, 0);
952                         NlaTrack *nlt;
953                         int a = 0;
954
955                         tenla->name = IFACE_("NLA Tracks");
956
957                         for (nlt = adt->nla_tracks.first; nlt; nlt = nlt->next) {
958                                 TreeElement *tenlt = outliner_add_element(soops, &tenla->subtree, nlt, tenla, TSE_NLA_TRACK, a);
959                                 NlaStrip *strip;
960                                 TreeElement *ten;
961                                 int b = 0;
962
963                                 tenlt->name = nlt->name;
964
965                                 for (strip = nlt->strips.first; strip; strip = strip->next, b++) {
966                                         ten = outliner_add_element(soops, &tenlt->subtree, strip->act, tenlt, TSE_NLA_ACTION, b);
967                                         if (ten) ten->directdata = strip;
968                                 }
969                         }
970                 }
971         }
972         else if (type == TSE_GP_LAYER) {
973                 bGPDlayer *gpl = (bGPDlayer *)idv;
974
975                 te->name = gpl->info;
976                 te->directdata = gpl;
977         }
978         else if (type == TSE_SEQUENCE) {
979                 Sequence *seq = (Sequence *) idv;
980                 Sequence *p;
981
982                 /*
983                  * The idcode is a little hack, but the outliner
984                  * only check te->idcode if te->type is equal to zero,
985                  * so this is "safe".
986                  */
987                 te->idcode = seq->type;
988                 te->directdata = seq;
989                 te->name = seq->name + 2;
990
991                 if (!(seq->type & SEQ_TYPE_EFFECT)) {
992                         /*
993                          * This work like the sequence.
994                          * If the sequence have a name (not default name)
995                          * show it, in other case put the filename.
996                          */
997
998                         if (seq->type == SEQ_TYPE_META) {
999                                 p = seq->seqbase.first;
1000                                 while (p) {
1001                                         outliner_add_element(soops, &te->subtree, (void *)p, te, TSE_SEQUENCE, index);
1002                                         p = p->next;
1003                                 }
1004                         }
1005                         else
1006                                 outliner_add_element(soops, &te->subtree, (void *)seq->strip, te, TSE_SEQ_STRIP, index);
1007                 }
1008         }
1009         else if (type == TSE_SEQ_STRIP) {
1010                 Strip *strip = (Strip *)idv;
1011
1012                 if (strip->dir[0] != '\0')
1013                         te->name = strip->dir;
1014                 else
1015                         te->name = IFACE_("Strip None");
1016                 te->directdata = strip;
1017         }
1018         else if (type == TSE_SEQUENCE_DUP) {
1019                 Sequence *seq = (Sequence *)idv;
1020
1021                 te->idcode = seq->type;
1022                 te->directdata = seq;
1023                 te->name = seq->strip->stripdata->name;
1024         }
1025         else if (ELEM(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
1026                 PointerRNA pptr, propptr, *ptr = (PointerRNA *)idv;
1027                 PropertyRNA *prop, *iterprop;
1028                 PropertyType proptype;
1029
1030                 /* Don't display arrays larger, weak but index is stored as a short,
1031                  * also the outliner isn't intended for editing such large data-sets. */
1032                 BLI_STATIC_ASSERT(sizeof(te->index) == 2, "Index is no longer short!");
1033                 const int tot_limit = SHRT_MAX;
1034
1035                 int a, tot;
1036
1037                 /* we do lazy build, for speed and to avoid infinite recusion */
1038
1039                 if (ptr->data == NULL) {
1040                         te->name = IFACE_("(empty)");
1041                 }
1042                 else if (type == TSE_RNA_STRUCT) {
1043                         /* struct */
1044                         te->name = RNA_struct_name_get_alloc(ptr, NULL, 0, NULL);
1045
1046                         if (te->name)
1047                                 te->flag |= TE_FREE_NAME;
1048                         else
1049                                 te->name = RNA_struct_ui_name(ptr->type);
1050
1051                         /* If searching don't expand RNA entries */
1052                         if (SEARCHING_OUTLINER(soops) && BLI_strcasecmp("RNA", te->name) == 0) tselem->flag &= ~TSE_CHILDSEARCH;
1053
1054                         iterprop = RNA_struct_iterator_property(ptr->type);
1055                         tot = RNA_property_collection_length(ptr, iterprop);
1056                         CLAMP_MAX(tot, tot_limit);
1057
1058                         /* auto open these cases */
1059                         if (!parent || (RNA_property_type(parent->directdata)) == PROP_POINTER)
1060                                 if (!tselem->used)
1061                                         tselem->flag &= ~TSE_CLOSED;
1062
1063                         if (TSELEM_OPEN(tselem, soops)) {
1064                                 for (a = 0; a < tot; a++) {
1065                                         RNA_property_collection_lookup_int(ptr, iterprop, a, &propptr);
1066                                         if (!(RNA_property_flag(propptr.data) & PROP_HIDDEN)) {
1067                                                 outliner_add_element(soops, &te->subtree, (void *)ptr, te, TSE_RNA_PROPERTY, a);
1068                                         }
1069                                 }
1070                         }
1071                         else if (tot)
1072                                 te->flag |= TE_LAZY_CLOSED;
1073
1074                         te->rnaptr = *ptr;
1075                 }
1076                 else if (type == TSE_RNA_PROPERTY) {
1077                         /* property */
1078                         iterprop = RNA_struct_iterator_property(ptr->type);
1079                         RNA_property_collection_lookup_int(ptr, iterprop, index, &propptr);
1080
1081                         prop = propptr.data;
1082                         proptype = RNA_property_type(prop);
1083
1084                         te->name = RNA_property_ui_name(prop);
1085                         te->directdata = prop;
1086                         te->rnaptr = *ptr;
1087
1088                         /* If searching don't expand RNA entries */
1089                         if (SEARCHING_OUTLINER(soops) && BLI_strcasecmp("RNA", te->name) == 0) tselem->flag &= ~TSE_CHILDSEARCH;
1090
1091                         if (proptype == PROP_POINTER) {
1092                                 pptr = RNA_property_pointer_get(ptr, prop);
1093
1094                                 if (pptr.data) {
1095                                         if (TSELEM_OPEN(tselem, soops))
1096                                                 outliner_add_element(soops, &te->subtree, (void *)&pptr, te, TSE_RNA_STRUCT, -1);
1097                                         else
1098                                                 te->flag |= TE_LAZY_CLOSED;
1099                                 }
1100                         }
1101                         else if (proptype == PROP_COLLECTION) {
1102                                 tot = RNA_property_collection_length(ptr, prop);
1103                                 CLAMP_MAX(tot, tot_limit);
1104
1105                                 if (TSELEM_OPEN(tselem, soops)) {
1106                                         for (a = 0; a < tot; a++) {
1107                                                 RNA_property_collection_lookup_int(ptr, prop, a, &pptr);
1108                                                 outliner_add_element(soops, &te->subtree, (void *)&pptr, te, TSE_RNA_STRUCT, a);
1109                                         }
1110                                 }
1111                                 else if (tot)
1112                                         te->flag |= TE_LAZY_CLOSED;
1113                         }
1114                         else if (ELEM(proptype, PROP_BOOLEAN, PROP_INT, PROP_FLOAT)) {
1115                                 tot = RNA_property_array_length(ptr, prop);
1116                                 CLAMP_MAX(tot, tot_limit);
1117
1118                                 if (TSELEM_OPEN(tselem, soops)) {
1119                                         for (a = 0; a < tot; a++)
1120                                                 outliner_add_element(soops, &te->subtree, (void *)ptr, te, TSE_RNA_ARRAY_ELEM, a);
1121                                 }
1122                                 else if (tot)
1123                                         te->flag |= TE_LAZY_CLOSED;
1124                         }
1125                 }
1126                 else if (type == TSE_RNA_ARRAY_ELEM) {
1127                         char c;
1128
1129                         prop = parent->directdata;
1130
1131                         te->directdata = prop;
1132                         te->rnaptr = *ptr;
1133                         te->index = index;
1134
1135                         c = RNA_property_array_item_char(prop, index);
1136
1137                         te->name = MEM_callocN(sizeof(char) * 20, "OutlinerRNAArrayName");
1138                         if (c) sprintf((char *)te->name, "  %c", c);
1139                         else sprintf((char *)te->name, "  %d", index + 1);
1140                         te->flag |= TE_FREE_NAME;
1141                 }
1142         }
1143         else if (type == TSE_KEYMAP) {
1144                 wmKeyMap *km = (wmKeyMap *)idv;
1145                 wmKeyMapItem *kmi;
1146                 char opname[OP_MAX_TYPENAME];
1147
1148                 te->directdata = idv;
1149                 te->name = km->idname;
1150
1151                 if (TSELEM_OPEN(tselem, soops)) {
1152                         int a = 0;
1153
1154                         for (kmi = km->items.first; kmi; kmi = kmi->next, a++) {
1155                                 const char *key = WM_key_event_string(kmi->type, false);
1156
1157                                 if (key[0]) {
1158                                         wmOperatorType *ot = NULL;
1159
1160                                         if (kmi->propvalue) {
1161                                                 /* pass */
1162                                         }
1163                                         else {
1164                                                 ot = WM_operatortype_find(kmi->idname, 0);
1165                                         }
1166
1167                                         if (ot || kmi->propvalue) {
1168                                                 TreeElement *ten = outliner_add_element(soops, &te->subtree, kmi, te, TSE_KEYMAP_ITEM, a);
1169
1170                                                 ten->directdata = kmi;
1171
1172                                                 if (kmi->propvalue) {
1173                                                         ten->name = IFACE_("Modal map, not yet");
1174                                                 }
1175                                                 else {
1176                                                         WM_operator_py_idname(opname, ot->idname);
1177                                                         ten->name = BLI_strdup(opname);
1178                                                         ten->flag |= TE_FREE_NAME;
1179                                                 }
1180                                         }
1181                                 }
1182                         }
1183                 }
1184                 else
1185                         te->flag |= TE_LAZY_CLOSED;
1186         }
1187
1188         return te;
1189 }
1190
1191 /* ======================================================= */
1192 /* Sequencer mode tree building */
1193
1194 /* Helped function to put duplicate sequence in the same tree. */
1195 static int need_add_seq_dup(Sequence *seq)
1196 {
1197         Sequence *p;
1198
1199         if ((!seq->strip) || (!seq->strip->stripdata))
1200                 return(1);
1201
1202         /*
1203          * First check backward, if we found a duplicate
1204          * sequence before this, don't need it, just return.
1205          */
1206         p = seq->prev;
1207         while (p) {
1208                 if ((!p->strip) || (!p->strip->stripdata)) {
1209                         p = p->prev;
1210                         continue;
1211                 }
1212
1213                 if (STREQ(p->strip->stripdata->name, seq->strip->stripdata->name))
1214                         return(2);
1215                 p = p->prev;
1216         }
1217
1218         p = seq->next;
1219         while (p) {
1220                 if ((!p->strip) || (!p->strip->stripdata)) {
1221                         p = p->next;
1222                         continue;
1223                 }
1224
1225                 if (STREQ(p->strip->stripdata->name, seq->strip->stripdata->name))
1226                         return(0);
1227                 p = p->next;
1228         }
1229         return(1);
1230 }
1231
1232 static void outliner_add_seq_dup(SpaceOops *soops, Sequence *seq, TreeElement *te, short index)
1233 {
1234         /* TreeElement *ch; */ /* UNUSED */
1235         Sequence *p;
1236
1237         p = seq;
1238         while (p) {
1239                 if ((!p->strip) || (!p->strip->stripdata) || (p->strip->stripdata->name[0] == '\0')) {
1240                         p = p->next;
1241                         continue;
1242                 }
1243
1244                 if (STREQ(p->strip->stripdata->name, seq->strip->stripdata->name))
1245                         /* ch = */ /* UNUSED */ outliner_add_element(soops, &te->subtree, (void *)p, te, TSE_SEQUENCE, index);
1246                 p = p->next;
1247         }
1248 }
1249
1250
1251 /* ----------------------------------------------- */
1252
1253 static const char *outliner_idcode_to_plural(short idcode)
1254 {
1255         const char *propname = BKE_idcode_to_name_plural(idcode);
1256         PropertyRNA *prop = RNA_struct_type_find_property(&RNA_BlendData, propname);
1257         return (prop) ? RNA_property_ui_name(prop) : "UNKNOWN";
1258 }
1259
1260 static bool outliner_library_id_show(Library *lib, ID *id, short filter_id_type)
1261 {
1262         if (id->lib != lib) {
1263                 return false;
1264         }
1265
1266         if (filter_id_type == ID_GR) {
1267                 /* Don't show child collections of non-scene master collection,
1268                  * they are already shown as children. */
1269                 Collection *collection = (Collection *)id;
1270                 bool has_non_scene_parent = false;
1271
1272                 for (CollectionParent *cparent = collection->parents.first; cparent; cparent = cparent->next) {
1273                         if (!(cparent->collection->flag & COLLECTION_IS_MASTER)) {
1274                                 has_non_scene_parent = true;
1275                         }
1276                 }
1277
1278                 if (has_non_scene_parent) {
1279                         return false;
1280                 }
1281         }
1282
1283         return true;
1284 }
1285
1286 static TreeElement *outliner_add_library_contents(Main *mainvar, SpaceOops *soops, ListBase *lb, Library *lib)
1287 {
1288         TreeElement *ten, *tenlib = NULL;
1289         ListBase *lbarray[MAX_LIBARRAY];
1290         int a, tot;
1291         short filter_id_type = (soops->filter & SO_FILTER_ID_TYPE) ? soops->filter_id_type : 0;
1292
1293         if (filter_id_type) {
1294                 lbarray[0] = which_libbase(mainvar, soops->filter_id_type);
1295                 tot = 1;
1296         }
1297         else {
1298                 tot = set_listbasepointers(mainvar, lbarray);
1299         }
1300
1301         for (a = 0; a < tot; a++) {
1302                 if (lbarray[a] && lbarray[a]->first) {
1303                         ID *id = lbarray[a]->first;
1304
1305                         /* check if there's data in current lib */
1306                         for (; id; id = id->next)
1307                                 if (id->lib == lib)
1308                                         break;
1309
1310                         if (id) {
1311                                 if (!tenlib) {
1312                                         /* Create library tree element on demand, depending if there are any datablocks. */
1313                                         if (lib) {
1314                                                 tenlib = outliner_add_element(soops, lb, lib, NULL, 0, 0);
1315                                         }
1316                                         else {
1317                                                 tenlib = outliner_add_element(soops, lb, mainvar, NULL, TSE_ID_BASE, 0);
1318                                                 tenlib->name = IFACE_("Current File");
1319                                         }
1320                                 }
1321
1322                                 /* Create datablock list parent element on demand. */
1323                                 if (filter_id_type) {
1324                                         ten = tenlib;
1325                                 }
1326                                 else {
1327                                         ten = outliner_add_element(soops, &tenlib->subtree, lbarray[a], NULL, TSE_ID_BASE, 0);
1328                                         ten->directdata = lbarray[a];
1329                                         ten->name = outliner_idcode_to_plural(GS(id->name));
1330                                 }
1331
1332                                 for (id = lbarray[a]->first; id; id = id->next) {
1333                                         if (outliner_library_id_show(lib, id, filter_id_type)) {
1334                                                 outliner_add_element(soops, &ten->subtree, id, ten, 0, 0);
1335                                         }
1336                                 }
1337                         }
1338                 }
1339         }
1340
1341         return tenlib;
1342 }
1343
1344 static void outliner_add_orphaned_datablocks(Main *mainvar, SpaceOops *soops)
1345 {
1346         TreeElement *ten;
1347         ListBase *lbarray[MAX_LIBARRAY];
1348         int a, tot;
1349         short filter_id_type = (soops->filter & SO_FILTER_ID_TYPE) ? soops->filter_id_type : 0;
1350
1351         if (filter_id_type) {
1352                 lbarray[0] = which_libbase(mainvar, soops->filter_id_type);
1353                 tot = 1;
1354         }
1355         else {
1356                 tot = set_listbasepointers(mainvar, lbarray);
1357         }
1358
1359         for (a = 0; a < tot; a++) {
1360                 if (lbarray[a] && lbarray[a]->first) {
1361                         ID *id = lbarray[a]->first;
1362
1363                         /* check if there are any datablocks of this type which are orphans */
1364                         for (; id; id = id->next) {
1365                                 if (ID_REAL_USERS(id) <= 0)
1366                                         break;
1367                         }
1368
1369                         if (id) {
1370                                 /* header for this type of datablock */
1371                                 if (filter_id_type) {
1372                                         ten = NULL;
1373                                 }
1374                                 else {
1375                                         ten = outliner_add_element(soops, &soops->tree, lbarray[a], NULL, TSE_ID_BASE, 0);
1376                                         ten->directdata = lbarray[a];
1377                                         ten->name = outliner_idcode_to_plural(GS(id->name));
1378                                 }
1379
1380                                 /* add the orphaned datablocks - these will not be added with any subtrees attached */
1381                                 for (id = lbarray[a]->first; id; id = id->next) {
1382                                         if (ID_REAL_USERS(id) <= 0)
1383                                                 outliner_add_element(soops, (ten) ? &ten->subtree : &soops->tree, id, ten, 0, 0);
1384                                 }
1385                         }
1386                 }
1387         }
1388 }
1389
1390 static void outliner_collections_reorder(
1391         Main *bmain,
1392         Scene *UNUSED(scene),
1393         SpaceOops *soops,
1394         TreeElement *insert_element,
1395         TreeElement *insert_handle,
1396         TreeElementInsertType action,
1397         const wmEvent *UNUSED(event))
1398 {
1399         TreeElement *from_parent_te, *to_parent_te;
1400         Collection *from_parent, *to_parent;
1401
1402         Collection *collection = outliner_collection_from_tree_element(insert_element);
1403         Collection *relative = NULL;
1404         bool relative_after = false;
1405
1406         from_parent_te = outliner_find_parent_element(&soops->tree, NULL, insert_element);
1407         from_parent = (from_parent_te) ? outliner_collection_from_tree_element(from_parent_te) : NULL;
1408
1409         if (ELEM(action, TE_INSERT_BEFORE, TE_INSERT_AFTER)) {
1410                 to_parent_te = outliner_find_parent_element(&soops->tree, NULL, insert_handle);
1411                 to_parent = (to_parent_te) ? outliner_collection_from_tree_element(to_parent_te) : NULL;
1412
1413                 relative = outliner_collection_from_tree_element(insert_handle);
1414                 relative_after = (action == TE_INSERT_AFTER);
1415         }
1416         else if (action == TE_INSERT_INTO) {
1417                 to_parent = outliner_collection_from_tree_element(insert_handle);
1418         }
1419         else {
1420                 BLI_assert(0);
1421                 return;
1422         }
1423
1424         if (!to_parent) {
1425                 return;
1426         }
1427
1428         BKE_collection_move(bmain, to_parent, from_parent, relative, relative_after, collection);
1429
1430         DEG_relations_tag_update(bmain);
1431 }
1432
1433 static bool outliner_collections_reorder_poll(
1434         const TreeElement *insert_element,
1435         TreeElement **io_insert_handle,
1436         TreeElementInsertType *io_action)
1437 {
1438         /* Can't move master collection. */
1439         Collection *collection = outliner_collection_from_tree_element(insert_element);
1440         if (collection->flag & COLLECTION_IS_MASTER) {
1441                 return false;
1442         }
1443
1444         /* Can only move into collections. */
1445         Collection *collection_handle = outliner_collection_from_tree_element(*io_insert_handle);
1446         if (collection_handle == NULL) {
1447                 return false;
1448         }
1449
1450         /* We can't insert/before after master collection. */
1451         if (collection_handle->flag & COLLECTION_IS_MASTER) {
1452                 if (*io_action == TE_INSERT_BEFORE) {
1453                         /* can't go higher than master collection, insert into it */
1454                         *io_action = TE_INSERT_INTO;
1455                 }
1456                 else if (*io_action == TE_INSERT_AFTER) {
1457                         *io_insert_handle = (*io_insert_handle)->subtree.last;
1458                 }
1459         }
1460
1461         return true;
1462 }
1463
1464 static void outliner_add_layer_collection_objects(
1465         SpaceOops *soops, ListBase *tree, ViewLayer *layer,
1466         LayerCollection *lc, TreeElement *ten)
1467 {
1468         for (CollectionObject *cob = lc->collection->gobject.first; cob; cob = cob->next) {
1469                 Base *base = BKE_view_layer_base_find(layer, cob->ob);
1470                 TreeElement *te_object = outliner_add_element(soops, tree, base->object, ten, 0, 0);
1471                 te_object->directdata = base;
1472         }
1473 }
1474
1475 static void outliner_add_layer_collections_recursive(
1476         SpaceOops *soops, ListBase *tree, ViewLayer *layer,
1477         ListBase *layer_collections, TreeElement *parent_ten,
1478         const bool show_objects)
1479 {
1480         for (LayerCollection *lc = layer_collections->first; lc; lc = lc->next) {
1481                 ID *id = &lc->collection->id;
1482                 TreeElement *ten = outliner_add_element(soops, tree, id, parent_ten, TSE_LAYER_COLLECTION, 0);
1483
1484                 ten->name = id->name + 2;
1485                 ten->directdata = lc;
1486                 ten->reinsert = outliner_collections_reorder;
1487                 ten->reinsert_poll = outliner_collections_reorder_poll;
1488
1489                 const bool exclude = (lc->flag & LAYER_COLLECTION_EXCLUDE) != 0;
1490                 if (exclude) {
1491                         ten->flag |= TE_DISABLED;
1492                 }
1493
1494                 outliner_add_layer_collections_recursive(soops, &ten->subtree, layer, &lc->layer_collections, ten, show_objects);
1495                 if (!exclude && show_objects) {
1496                         outliner_add_layer_collection_objects(soops, &ten->subtree, layer, lc, ten);
1497                 }
1498         }
1499 }
1500
1501 static void outliner_add_view_layer(SpaceOops *soops, ListBase *tree, TreeElement *parent,
1502                                     ViewLayer *layer, const bool show_objects)
1503 {
1504         /* First layer collection is for master collection, don't show it. */
1505         LayerCollection *lc = layer->layer_collections.first;
1506         if (lc == NULL) {
1507                 return;
1508         }
1509
1510         outliner_add_layer_collections_recursive(soops, tree, layer, &lc->layer_collections, parent, show_objects);
1511         if (show_objects) {
1512                 outliner_add_layer_collection_objects(soops, tree, layer, lc, parent);
1513         }
1514 }
1515
1516 BLI_INLINE void outliner_add_collection_init(TreeElement *te, Collection *collection)
1517 {
1518         if (collection->flag & COLLECTION_IS_MASTER) {
1519                 te->name = IFACE_("Scene Collection");
1520         }
1521         else {
1522                 te->name = collection->id.name + 2;
1523         }
1524
1525         te->directdata = collection;
1526         te->reinsert = outliner_collections_reorder;
1527         te->reinsert_poll = outliner_collections_reorder_poll;
1528 }
1529
1530 BLI_INLINE void outliner_add_collection_objects(
1531         SpaceOops *soops, ListBase *tree, Collection *collection, TreeElement *parent)
1532 {
1533         for (CollectionObject *cob = collection->gobject.first; cob; cob = cob->next) {
1534                 outliner_add_element(soops, tree, cob->ob, parent, 0, 0);
1535         }
1536 }
1537
1538 static TreeElement *outliner_add_collection_recursive(
1539         SpaceOops *soops, Collection *collection, TreeElement *ten)
1540 {
1541         outliner_add_collection_init(ten, collection);
1542
1543         for (CollectionChild *child = collection->children.first; child; child = child->next) {
1544                 outliner_add_element(soops, &ten->subtree, &child->collection->id, ten, 0, 0);
1545         }
1546
1547         if (soops->outlinevis != SO_SCENES) {
1548                 outliner_add_collection_objects(soops, &ten->subtree, collection, ten);
1549         }
1550
1551         return ten;
1552 }
1553
1554 /* ======================================================= */
1555 /* Generic Tree Building helpers - order these are called is top to bottom */
1556
1557 /* Hierarchy --------------------------------------------- */
1558
1559 /* make sure elements are correctly nested */
1560 static void outliner_make_object_parent_hierarchy(ListBase *lb)
1561 {
1562         TreeElement *te, *ten, *tep;
1563         TreeStoreElem *tselem;
1564
1565         /* build hierarchy */
1566         // XXX also, set extents here...
1567         te = lb->first;
1568         while (te) {
1569                 ten = te->next;
1570                 tselem = TREESTORE(te);
1571
1572                 if (tselem->type == 0 && te->idcode == ID_OB) {
1573                         Object *ob = (Object *)tselem->id;
1574                         if (ob->parent && ob->parent->id.newid) {
1575                                 BLI_remlink(lb, te);
1576                                 tep = (TreeElement *)ob->parent->id.newid;
1577                                 BLI_addtail(&tep->subtree, te);
1578                                 // set correct parent pointers
1579                                 for (te = tep->subtree.first; te; te = te->next) te->parent = tep;
1580                         }
1581                 }
1582                 te = ten;
1583         }
1584 }
1585
1586 /* Sorting ------------------------------------------------------ */
1587
1588 typedef struct tTreeSort {
1589         TreeElement *te;
1590         ID *id;
1591         const char *name;
1592         short idcode;
1593 } tTreeSort;
1594
1595 /* alphabetical comparator, tryping to put objects first */
1596 static int treesort_alpha_ob(const void *v1, const void *v2)
1597 {
1598         const tTreeSort *x1 = v1, *x2 = v2;
1599         int comp;
1600
1601         /* first put objects last (hierarchy) */
1602         comp = (x1->idcode == ID_OB);
1603         if (x2->idcode == ID_OB) comp += 2;
1604
1605         if (comp == 1) return 1;
1606         else if (comp == 2) return -1;
1607         else if (comp == 3) {
1608                 comp = strcmp(x1->name, x2->name);
1609
1610                 if (comp > 0) return 1;
1611                 else if (comp < 0) return -1;
1612                 return 0;
1613         }
1614         return 0;
1615 }
1616
1617 /* alphabetical comparator */
1618 static int treesort_alpha(const void *v1, const void *v2)
1619 {
1620         const tTreeSort *x1 = v1, *x2 = v2;
1621         int comp;
1622
1623         comp = strcmp(x1->name, x2->name);
1624
1625         if (comp > 0) return 1;
1626         else if (comp < 0) return -1;
1627         return 0;
1628 }
1629
1630
1631 /* this is nice option for later? doesnt look too useful... */
1632 #if 0
1633 static int treesort_obtype_alpha(const void *v1, const void *v2)
1634 {
1635         const tTreeSort *x1 = v1, *x2 = v2;
1636
1637         /* first put objects last (hierarchy) */
1638         if (x1->idcode == ID_OB && x2->idcode != ID_OB) {
1639                 return 1;
1640         }
1641         else if (x2->idcode == ID_OB && x1->idcode != ID_OB) {
1642                 return -1;
1643         }
1644         else {
1645                 /* 2nd we check ob type */
1646                 if (x1->idcode == ID_OB && x2->idcode == ID_OB) {
1647                         if      (((Object *)x1->id)->type > ((Object *)x2->id)->type) return  1;
1648                         else if (((Object *)x1->id)->type > ((Object *)x2->id)->type) return -1;
1649                         else return 0;
1650                 }
1651                 else {
1652                         int comp = strcmp(x1->name, x2->name);
1653
1654                         if      (comp > 0) return  1;
1655                         else if (comp < 0) return -1;
1656                         return 0;
1657                 }
1658         }
1659 }
1660 #endif
1661
1662 /* sort happens on each subtree individual */
1663 static void outliner_sort(ListBase *lb)
1664 {
1665         TreeElement *te;
1666         TreeStoreElem *tselem;
1667
1668         te = lb->last;
1669         if (te == NULL) return;
1670         tselem = TREESTORE(te);
1671
1672         /* sorting rules; only object lists, ID lists, or deformgroups */
1673         if (ELEM(tselem->type, TSE_DEFGROUP, TSE_ID_BASE) || (tselem->type == 0 && te->idcode == ID_OB)) {
1674                 int totelem = BLI_listbase_count(lb);
1675
1676                 if (totelem > 1) {
1677                         tTreeSort *tear = MEM_mallocN(totelem * sizeof(tTreeSort), "tree sort array");
1678                         tTreeSort *tp = tear;
1679                         int skip = 0;
1680
1681                         for (te = lb->first; te; te = te->next, tp++) {
1682                                 tselem = TREESTORE(te);
1683                                 tp->te = te;
1684                                 tp->name = te->name;
1685                                 tp->idcode = te->idcode;
1686
1687                                 if (tselem->type && tselem->type != TSE_DEFGROUP)
1688                                         tp->idcode = 0;  // don't sort this
1689                                 if (tselem->type == TSE_ID_BASE)
1690                                         tp->idcode = 1; // do sort this
1691
1692                                 tp->id = tselem->id;
1693                         }
1694
1695                         /* just sort alphabetically */
1696                         if (tear->idcode == 1) {
1697                                 qsort(tear, totelem, sizeof(tTreeSort), treesort_alpha);
1698                         }
1699                         else {
1700                                 /* keep beginning of list */
1701                                 for (tp = tear, skip = 0; skip < totelem; skip++, tp++)
1702                                         if (tp->idcode) break;
1703
1704                                 if (skip < totelem)
1705                                         qsort(tear + skip, totelem - skip, sizeof(tTreeSort), treesort_alpha_ob);
1706                         }
1707
1708                         BLI_listbase_clear(lb);
1709                         tp = tear;
1710                         while (totelem--) {
1711                                 BLI_addtail(lb, tp->te);
1712                                 tp++;
1713                         }
1714                         MEM_freeN(tear);
1715                 }
1716         }
1717
1718         for (te = lb->first; te; te = te->next) {
1719                 outliner_sort(&te->subtree);
1720         }
1721 }
1722
1723 /* Filtering ----------------------------------------------- */
1724
1725 typedef struct OutlinerTreeElementFocus {
1726         TreeStoreElem *tselem;
1727         int ys;
1728 } OutlinerTreeElementFocus;
1729
1730 /**
1731  * Bring the outliner scrolling back to where it was in relation to the original focus element
1732  * Caller is expected to handle redrawing of ARegion.
1733  */
1734 static void outliner_restore_scrolling_position(SpaceOops *soops, ARegion *ar, OutlinerTreeElementFocus *focus)
1735 {
1736         View2D *v2d = &ar->v2d;
1737         int ytop;
1738
1739         if (focus->tselem != NULL) {
1740                 outliner_set_coordinates(ar, soops);
1741
1742                 TreeElement *te_new = outliner_find_tree_element(&soops->tree, focus->tselem);
1743
1744                 if (te_new != NULL) {
1745                         int ys_new, ys_old;
1746
1747                         ys_new = te_new->ys;
1748                         ys_old = focus->ys;
1749
1750                         ytop = v2d->cur.ymax + (ys_new - ys_old) -1;
1751                         if (ytop > 0) ytop = 0;
1752
1753                         v2d->cur.ymax = (float)ytop;
1754                         v2d->cur.ymin = (float)(ytop - BLI_rcti_size_y(&v2d->mask));
1755                 }
1756                 else {
1757                         return;
1758                 }
1759         }
1760 }
1761
1762 static bool test_collection_callback(TreeElement *te)
1763 {
1764         return outliner_is_collection_tree_element(te);
1765 }
1766
1767 static bool test_object_callback(TreeElement *te)
1768 {
1769         TreeStoreElem *tselem = TREESTORE(te);
1770         return ((tselem->type == 0) && (te->idcode == ID_OB));
1771 }
1772
1773 /**
1774  * See if TreeElement or any of its children pass the callback_test.
1775  */
1776 static TreeElement *outliner_find_first_desired_element_at_y_recursive(
1777         const SpaceOops *soops,
1778         TreeElement *te,
1779         const float limit,
1780         bool (*callback_test)(TreeElement *))
1781 {
1782         if (callback_test(te)) {
1783                 return te;
1784         }
1785
1786         if (TSELEM_OPEN(te->store_elem, soops)) {
1787                 TreeElement *te_iter, *te_sub;
1788                 for (te_iter = te->subtree.first; te_iter; te_iter = te_iter->next) {
1789                         te_sub = outliner_find_first_desired_element_at_y_recursive(soops, te_iter, limit, callback_test);
1790                         if (te_sub != NULL) {
1791                                 return te_sub;
1792                         }
1793                 }
1794         }
1795
1796         return NULL;
1797 }
1798
1799 /**
1800  * Find the first element that passes a test starting from a reference vertical coordinate
1801  *
1802  * If the element that is in the position is not what we are looking for, keep looking for its
1803  * children, siblings, and eventually, aunts, cousins, disntant families, ...
1804  *
1805  * Basically we keep going up and down the outliner tree from that point forward, until we find
1806  * what we are looking for. If we are past the visible range and we can't find a valid element
1807  * we return NULL.
1808  */
1809 static TreeElement *outliner_find_first_desired_element_at_y(
1810         const SpaceOops *soops,
1811         const float view_co,
1812         const float view_co_limit)
1813 {
1814         TreeElement *te, *te_sub;
1815         te = outliner_find_item_at_y(soops, &soops->tree, view_co);
1816
1817         bool (*callback_test)(TreeElement *);
1818         if ((soops->outlinevis == SO_VIEW_LAYER) &&
1819              (soops->filter & SO_FILTER_NO_COLLECTION))
1820         {
1821                 callback_test = test_object_callback;
1822         }
1823         else {
1824                 callback_test = test_collection_callback;
1825         }
1826
1827         while (te != NULL) {
1828                 te_sub = outliner_find_first_desired_element_at_y_recursive(soops, te, view_co_limit, callback_test);
1829                 if (te_sub != NULL) {
1830                         /* Skip the element if it was not visible to start with. */
1831                         if (te->ys + UI_UNIT_Y > view_co_limit) {
1832                                 return te_sub;
1833                         }
1834                         else {
1835                                 return NULL;
1836                         }
1837                 }
1838
1839                 if (te->next) {
1840                         te = te->next;
1841                         continue;
1842                 }
1843
1844                 if (te->parent == NULL) {
1845                         break;
1846                 }
1847
1848                 while (te->parent) {
1849                         if (te->parent->next) {
1850                                 te = te->parent->next;
1851                                 break;
1852                         }
1853                         te = te->parent;
1854                 }
1855         }
1856
1857         return NULL;
1858 }
1859
1860 /**
1861  * Store information of current outliner scrolling status to be restored later
1862  *
1863  * Finds the top-most collection visible in the outliner and populates the OutlinerTreeElementFocus
1864  * struct to retrieve this element later to make sure it is in the same original position as before filtering
1865  */
1866 static void outliner_store_scrolling_position(SpaceOops *soops, ARegion *ar, OutlinerTreeElementFocus *focus)
1867 {
1868         TreeElement *te;
1869         float limit = ar->v2d.cur.ymin;
1870
1871         outliner_set_coordinates(ar, soops);
1872
1873         te = outliner_find_first_desired_element_at_y(soops, ar->v2d.cur.ymax, limit);
1874
1875         if (te != NULL) {
1876                 focus->tselem = TREESTORE(te);
1877                 focus->ys = te->ys;
1878         }
1879         else {
1880                 focus->tselem = NULL;
1881         }
1882 }
1883
1884 static int outliner_exclude_filter_get(SpaceOops *soops)
1885 {
1886         int exclude_filter = soops->filter & ~SO_FILTER_OB_STATE;
1887
1888         if (soops->filter & SO_FILTER_SEARCH) {
1889                 if (soops->search_string[0] == 0) {
1890                         exclude_filter &= ~SO_FILTER_SEARCH;
1891                 }
1892         }
1893
1894         /* Let's have this for the collection options at first. */
1895         if (!SUPPORT_FILTER_OUTLINER(soops)) {
1896                 return (exclude_filter & SO_FILTER_SEARCH);
1897         }
1898
1899         if (soops->filter & SO_FILTER_NO_OBJECT) {
1900                 exclude_filter |= SO_FILTER_OB_TYPE;
1901         }
1902
1903         switch (soops->filter_state) {
1904                 case SO_FILTER_OB_VISIBLE:
1905                         exclude_filter |= SO_FILTER_OB_STATE_VISIBLE;
1906                         break;
1907                 case SO_FILTER_OB_SELECTED:
1908                         exclude_filter |= SO_FILTER_OB_STATE_SELECTED;
1909                         break;
1910                 case SO_FILTER_OB_ACTIVE:
1911                         exclude_filter |= SO_FILTER_OB_STATE_ACTIVE;
1912                         break;
1913         }
1914
1915         return exclude_filter;
1916 }
1917
1918 static bool outliner_element_visible_get(ViewLayer *view_layer, TreeElement *te, const int exclude_filter)
1919 {
1920         if ((exclude_filter & SO_FILTER_ANY) == 0) {
1921                 return true;
1922         }
1923
1924         TreeStoreElem *tselem = TREESTORE(te);
1925         if ((tselem->type == 0) && (te->idcode == ID_OB)) {
1926                 if ((exclude_filter & SO_FILTER_OB_TYPE) == SO_FILTER_OB_TYPE) {
1927                         return false;
1928                 }
1929
1930                 Object *ob = (Object *)tselem->id;
1931                 Base *base = (Base *)te->directdata;
1932                 BLI_assert((base == NULL) || (base->object == ob));
1933
1934                 if (exclude_filter & SO_FILTER_OB_TYPE) {
1935                         switch (ob->type) {
1936                                 case OB_MESH:
1937                                         if (exclude_filter & SO_FILTER_NO_OB_MESH) {
1938                                                 return false;
1939                                         }
1940                                         break;
1941                                 case OB_ARMATURE:
1942                                         if (exclude_filter & SO_FILTER_NO_OB_ARMATURE) {
1943                                                 return false;
1944                                         }
1945                                         break;
1946                                 case OB_EMPTY:
1947                                         if (exclude_filter & SO_FILTER_NO_OB_EMPTY) {
1948                                                 return false;
1949                                         }
1950                                         break;
1951                                 case OB_LAMP:
1952                                         if (exclude_filter & SO_FILTER_NO_OB_LAMP) {
1953                                                 return false;
1954                                         }
1955                                         break;
1956                                 case OB_CAMERA:
1957                                         if (exclude_filter & SO_FILTER_NO_OB_CAMERA) {
1958                                                 return false;
1959                                         }
1960                                         break;
1961                                 default:
1962                                         if (exclude_filter & SO_FILTER_NO_OB_OTHERS) {
1963                                                 return false;
1964                                         }
1965                                         break;
1966                         }
1967                 }
1968
1969                 if (exclude_filter & SO_FILTER_OB_STATE) {
1970                         if (base == NULL) {
1971                                 base = BKE_view_layer_base_find(view_layer, ob);
1972
1973                                 if (base == NULL) {
1974                                         return false;
1975                                 }
1976                         }
1977
1978                         if (exclude_filter & SO_FILTER_OB_STATE_VISIBLE) {
1979                                 if ((base->flag & BASE_VISIBLED) == 0) {
1980                                         return false;
1981                                 }
1982                         }
1983                         else if (exclude_filter & SO_FILTER_OB_STATE_SELECTED) {
1984                                 if ((base->flag & BASE_SELECTED) == 0) {
1985                                         return false;
1986                                 }
1987                         }
1988                         else {
1989                                 BLI_assert(exclude_filter & SO_FILTER_OB_STATE_ACTIVE);
1990                                 if (base != BASACT(view_layer)) {
1991                                         return false;
1992                                 }
1993                         }
1994                 }
1995
1996                 if ((te->parent != NULL) &&
1997                     (TREESTORE(te->parent)->type == 0) && (te->parent->idcode == ID_OB))
1998                 {
1999                         if (exclude_filter & SO_FILTER_NO_CHILDREN) {
2000                                 return false;
2001                         }
2002                 }
2003         }
2004         else if (te->parent != NULL &&
2005                  TREESTORE(te->parent)->type == 0 && te->parent->idcode == ID_OB)
2006         {
2007                 if (exclude_filter & SO_FILTER_NO_OB_CONTENT) {
2008                         return false;
2009                 }
2010         }
2011
2012         return true;
2013 }
2014
2015 static bool outliner_filter_has_name(TreeElement *te, const char *name, int flags)
2016 {
2017         int fn_flag = 0;
2018
2019         if ((flags & SO_FIND_CASE_SENSITIVE) == 0)
2020                 fn_flag |= FNM_CASEFOLD;
2021
2022         return fnmatch(name, te->name, fn_flag) == 0;
2023 }
2024
2025 static int outliner_filter_subtree(
2026         SpaceOops *soops, ViewLayer *view_layer, ListBase *lb, const char *search_string, const int exclude_filter)
2027 {
2028         TreeElement *te, *te_next;
2029         TreeStoreElem *tselem;
2030
2031         for (te = lb->first; te; te = te_next) {
2032                 te_next = te->next;
2033
2034                 if ((outliner_element_visible_get(view_layer, te, exclude_filter) == false)) {
2035                         outliner_free_tree_element(te, lb);
2036                         continue;
2037                 }
2038                 else if ((exclude_filter & SO_FILTER_SEARCH) == 0) {
2039                         /* Filter subtree too. */
2040                         outliner_filter_subtree(soops, view_layer, &te->subtree, search_string, exclude_filter);
2041                         continue;
2042                 }
2043
2044                 if (!outliner_filter_has_name(te, search_string, soops->search_flags)) {
2045                         /* item isn't something we're looking for, but...
2046                          *  - if the subtree is expanded, check if there are any matches that can be easily found
2047                          *              so that searching for "cu" in the default scene will still match the Cube
2048                          *      - otherwise, we can't see within the subtree and the item doesn't match,
2049                          *              so these can be safely ignored (i.e. the subtree can get freed)
2050                          */
2051                         tselem = TREESTORE(te);
2052
2053                         /* flag as not a found item */
2054                         tselem->flag &= ~TSE_SEARCHMATCH;
2055
2056                         if ((!TSELEM_OPEN(tselem, soops)) ||
2057                             outliner_filter_subtree(soops, view_layer, &te->subtree, search_string, exclude_filter) == 0)
2058                         {
2059                                 outliner_free_tree_element(te, lb);
2060                         }
2061                 }
2062                 else {
2063                         tselem = TREESTORE(te);
2064
2065                         /* flag as a found item - we can then highlight it */
2066                         tselem->flag |= TSE_SEARCHMATCH;
2067
2068                         /* filter subtree too */
2069                         outliner_filter_subtree(soops, view_layer, &te->subtree, search_string, exclude_filter);
2070                 }
2071         }
2072
2073         /* if there are still items in the list, that means that there were still some matches */
2074         return (BLI_listbase_is_empty(lb) == false);
2075 }
2076
2077 static void outliner_filter_tree(SpaceOops *soops, ViewLayer *view_layer)
2078 {
2079         char search_buff[sizeof(((struct SpaceOops *)NULL)->search_string) + 2];
2080         char *search_string;
2081
2082         const int exclude_filter = outliner_exclude_filter_get(soops);
2083
2084         if (exclude_filter == 0) {
2085                 return;
2086         }
2087
2088         if (soops->search_flags & SO_FIND_COMPLETE) {
2089                 search_string = soops->search_string;
2090         }
2091         else {
2092                 /* Implicitly add heading/trailing wildcards if needed. */
2093                 BLI_strncpy_ensure_pad(search_buff, soops->search_string, '*', sizeof(search_buff));
2094                 search_string = search_buff;
2095         }
2096
2097         outliner_filter_subtree(soops, view_layer, &soops->tree, search_string, exclude_filter);
2098 }
2099
2100 /* ======================================================= */
2101 /* Main Tree Building API */
2102
2103 /* Main entry point for building the tree data-structure that the outliner represents */
2104 // TODO: split each mode into its own function?
2105 void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, SpaceOops *soops, ARegion *ar)
2106 {
2107         TreeElement *te = NULL, *ten;
2108         TreeStoreElem *tselem;
2109         int show_opened = !soops->treestore || !BLI_mempool_len(soops->treestore); /* on first view, we open scenes */
2110
2111         /* Are we looking for something - we want to tag parents to filter child matches
2112          * - NOT in datablocks view - searching all datablocks takes way too long to be useful
2113          * - this variable is only set once per tree build */
2114         if (soops->search_string[0] != 0 && soops->outlinevis != SO_DATA_API)
2115                 soops->search_flags |= SO_SEARCH_RECURSIVE;
2116         else
2117                 soops->search_flags &= ~SO_SEARCH_RECURSIVE;
2118
2119         if (soops->treehash && (soops->storeflag & SO_TREESTORE_REBUILD)) {
2120                 soops->storeflag &= ~SO_TREESTORE_REBUILD;
2121                 BKE_outliner_treehash_rebuild_from_treestore(soops->treehash, soops->treestore);
2122         }
2123
2124         if (ar->do_draw & RGN_DRAW_NO_REBUILD) {
2125                 return;
2126         }
2127
2128         OutlinerTreeElementFocus focus;
2129         outliner_store_scrolling_position(soops, ar, &focus);
2130
2131         outliner_free_tree(&soops->tree);
2132         outliner_storage_cleanup(soops);
2133
2134         /* options */
2135         if (soops->outlinevis == SO_LIBRARIES) {
2136                 Library *lib;
2137
2138                 /* current file first - mainvar provides tselem with unique pointer - not used */
2139                 ten = outliner_add_library_contents(mainvar, soops, &soops->tree, NULL);
2140                 if (ten) {
2141                         tselem = TREESTORE(ten);
2142                         if (!tselem->used)
2143                                 tselem->flag &= ~TSE_CLOSED;
2144                 }
2145
2146                 for (lib = mainvar->library.first; lib; lib = lib->id.next) {
2147                         ten = outliner_add_library_contents(mainvar, soops, &soops->tree, lib);
2148                         if (ten) {
2149                                 lib->id.newid = (ID *)ten;
2150                         }
2151
2152                 }
2153                 /* make hierarchy */
2154                 ten = soops->tree.first;
2155                 ten = ten->next;  /* first one is main */
2156                 while (ten) {
2157                         TreeElement *nten = ten->next, *par;
2158                         tselem = TREESTORE(ten);
2159                         lib = (Library *)tselem->id;
2160                         if (lib && lib->parent) {
2161                                 par = (TreeElement *)lib->parent->id.newid;
2162                                 if (tselem->id->tag & LIB_TAG_INDIRECT) {
2163                                         /* Only remove from 'first level' if lib is not also directly used. */
2164                                         BLI_remlink(&soops->tree, ten);
2165                                         BLI_addtail(&par->subtree, ten);
2166                                         ten->parent = par;
2167                                 }
2168                                 else {
2169                                         /* Else, make a new copy of the libtree for our parent. */
2170                                         TreeElement *dupten = outliner_add_library_contents(mainvar, soops, &par->subtree, lib);
2171                                         if (dupten) {
2172                                                 dupten->parent = par;
2173                                         }
2174                                 }
2175                         }
2176                         ten = nten;
2177                 }
2178                 /* restore newid pointers */
2179                 for (lib = mainvar->library.first; lib; lib = lib->id.next)
2180                         lib->id.newid = NULL;
2181
2182         }
2183         else if (soops->outlinevis == SO_SCENES) {
2184                 Scene *sce;
2185                 for (sce = mainvar->scene.first; sce; sce = sce->id.next) {
2186                         te = outliner_add_element(soops, &soops->tree, sce, NULL, 0, 0);
2187                         tselem = TREESTORE(te);
2188
2189                         if (sce == scene && show_opened) {
2190                                 tselem->flag &= ~TSE_CLOSED;
2191                         }
2192
2193                         outliner_make_object_parent_hierarchy(&te->subtree);
2194                 }
2195         }
2196         else if (soops->outlinevis == SO_SEQUENCE) {
2197                 Sequence *seq;
2198                 Editing *ed = BKE_sequencer_editing_get(scene, false);
2199                 int op;
2200
2201                 if (ed == NULL)
2202                         return;
2203
2204                 seq = ed->seqbasep->first;
2205                 if (!seq)
2206                         return;
2207
2208                 while (seq) {
2209                         op = need_add_seq_dup(seq);
2210                         if (op == 1) {
2211                                 /* ten = */ outliner_add_element(soops, &soops->tree, (void *)seq, NULL, TSE_SEQUENCE, 0);
2212                         }
2213                         else if (op == 0) {
2214                                 ten = outliner_add_element(soops, &soops->tree, (void *)seq, NULL, TSE_SEQUENCE_DUP, 0);
2215                                 outliner_add_seq_dup(soops, seq, ten, 0);
2216                         }
2217                         seq = seq->next;
2218                 }
2219         }
2220         else if (soops->outlinevis == SO_DATA_API) {
2221                 PointerRNA mainptr;
2222
2223                 RNA_main_pointer_create(mainvar, &mainptr);
2224
2225                 ten = outliner_add_element(soops, &soops->tree, (void *)&mainptr, NULL, TSE_RNA_STRUCT, -1);
2226
2227                 if (show_opened) {
2228                         tselem = TREESTORE(ten);
2229                         tselem->flag &= ~TSE_CLOSED;
2230                 }
2231         }
2232         else if (soops->outlinevis == SO_ID_ORPHANS) {
2233                 outliner_add_orphaned_datablocks(mainvar, soops);
2234         }
2235         else if (soops->outlinevis == SO_VIEW_LAYER) {
2236                 if (soops->filter & SO_FILTER_NO_COLLECTION) {
2237                         /* Show objects in the view layer. */
2238                         for (Base *base = view_layer->object_bases.first; base; base = base->next) {
2239                                 TreeElement *te_object = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
2240                                 te_object->directdata = base;
2241                         }
2242
2243                         outliner_make_object_parent_hierarchy(&soops->tree);
2244                 }
2245                 else {
2246                         /* Show collections in the view layer. */
2247                         ten = outliner_add_element(soops, &soops->tree, scene, NULL, TSE_VIEW_COLLECTION_BASE, 0);
2248                         ten->name = IFACE_("Scene Collection");
2249                         TREESTORE(ten)->flag &= ~TSE_CLOSED;
2250
2251                         bool show_objects = !(soops->filter & SO_FILTER_NO_OBJECT);
2252                         outliner_add_view_layer(soops, &ten->subtree, ten, view_layer, show_objects);
2253                 }
2254         }
2255
2256         if ((soops->flag & SO_SKIP_SORT_ALPHA) == 0) {
2257                 outliner_sort(&soops->tree);
2258         }
2259
2260         outliner_filter_tree(soops, view_layer);
2261         outliner_restore_scrolling_position(soops, ar, &focus);
2262
2263         BKE_main_id_clear_newpoins(mainvar);
2264 }
2265
2266