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