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