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