Merge branch 'master' into blender2.8
[blender.git] / source / blender / editors / space_outliner / outliner_tree.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version. 
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Joshua Leung
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/space_outliner/outliner_tree.c
29  *  \ingroup spoutliner
30  */
31  
32 #include <math.h>
33 #include <string.h>
34
35 #include "MEM_guardedalloc.h"
36
37 #include "DNA_anim_types.h"
38 #include "DNA_armature_types.h"
39 #include "DNA_constraint_types.h"
40 #include "DNA_camera_types.h"
41 #include "DNA_cachefile_types.h"
42 #include "DNA_gpencil_types.h"
43 #include "DNA_group_types.h"
44 #include "DNA_key_types.h"
45 #include "DNA_lamp_types.h"
46 #include "DNA_material_types.h"
47 #include "DNA_mesh_types.h"
48 #include "DNA_meta_types.h"
49 #include "DNA_scene_types.h"
50 #include "DNA_world_types.h"
51 #include "DNA_sequence_types.h"
52 #include "DNA_speaker_types.h"
53 #include "DNA_object_types.h"
54 #include "DNA_linestyle_types.h"
55
56 #include "BLI_blenlib.h"
57 #include "BLI_utildefines.h"
58 #include "BLI_mempool.h"
59 #include "BLI_fnmatch.h"
60
61 #include "BLT_translation.h"
62
63 #include "BKE_fcurve.h"
64 #include "BKE_main.h"
65 #include "BKE_library.h"
66 #include "BKE_modifier.h"
67 #include "BKE_sequencer.h"
68 #include "BKE_idcode.h"
69 #include "BKE_outliner_treehash.h"
70
71 #include "ED_armature.h"
72 #include "ED_screen.h"
73
74 #include "WM_api.h"
75 #include "WM_types.h"
76
77 #include "RNA_access.h"
78
79 #include "outliner_intern.h"
80
81 #ifdef WIN32
82 #  include "BLI_math_base.h" /* M_PI */
83 #endif
84
85 /* ********************************************************* */
86 /* Persistent Data */
87
88 static void outliner_storage_cleanup(SpaceOops *soops)
89 {
90         BLI_mempool *ts = soops->treestore;
91         
92         if (ts) {
93                 TreeStoreElem *tselem;
94                 int unused = 0;
95                 
96                 /* each element used once, for ID blocks with more users to have each a treestore */
97                 BLI_mempool_iter iter;
98
99                 BLI_mempool_iternew(ts, &iter);
100                 while ((tselem = BLI_mempool_iterstep(&iter))) {
101                         tselem->used = 0;
102                 }
103                 
104                 /* cleanup only after reading file or undo step, and always for
105                  * RNA datablocks view in order to save memory */
106                 if (soops->storeflag & SO_TREESTORE_CLEANUP) {
107                         soops->storeflag &= ~SO_TREESTORE_CLEANUP;
108
109                         BLI_mempool_iternew(ts, &iter);
110                         while ((tselem = BLI_mempool_iterstep(&iter))) {
111                                 if (tselem->id == NULL) unused++;
112                         }
113                         
114                         if (unused) {
115                                 if (BLI_mempool_count(ts) == unused) {
116                                         BLI_mempool_destroy(ts);
117                                         soops->treestore = NULL;
118                                         if (soops->treehash) {
119                                                 BKE_outliner_treehash_free(soops->treehash);
120                                                 soops->treehash = NULL;
121                                         }
122                                 }
123                                 else {
124                                         TreeStoreElem *tsenew;
125                                         BLI_mempool *new_ts = BLI_mempool_create(sizeof(TreeStoreElem), BLI_mempool_count(ts) - unused,
126                                                                                  512, BLI_MEMPOOL_ALLOW_ITER);
127                                         BLI_mempool_iternew(ts, &iter);
128                                         while ((tselem = BLI_mempool_iterstep(&iter))) {
129                                                 if (tselem->id) {
130                                                         tsenew = BLI_mempool_alloc(new_ts);
131                                                         *tsenew = *tselem;
132                                                 }
133                                         }
134                                         BLI_mempool_destroy(ts);
135                                         soops->treestore = new_ts;
136                                         if (soops->treehash) {
137                                                 /* update hash table to fix broken pointers */
138                                                 BKE_outliner_treehash_rebuild_from_treestore(soops->treehash, soops->treestore);
139                                         }
140                                 }
141                         }
142                 }
143         }
144 }
145
146 static void check_persistent(SpaceOops *soops, TreeElement *te, ID *id, short type, short nr)
147 {
148         TreeStoreElem *tselem;
149         
150         if (soops->treestore == NULL) {
151                 /* if treestore was not created in readfile.c, create it here */
152                 soops->treestore = BLI_mempool_create(sizeof(TreeStoreElem), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
153                 
154         }
155         if (soops->treehash == NULL) {
156                 soops->treehash = BKE_outliner_treehash_create_from_treestore(soops->treestore);
157         }
158
159         /* find any unused tree element in treestore and mark it as used
160          * (note that there may be multiple unused elements in case of linked objects) */
161         tselem = BKE_outliner_treehash_lookup_unused(soops->treehash, type, nr, id);
162         if (tselem) {
163                 te->store_elem = tselem;
164                 tselem->used = 1;
165                 return;
166         }
167
168         /* add 1 element to treestore */
169         tselem = BLI_mempool_alloc(soops->treestore);
170         tselem->type = type;
171         tselem->nr = type ? nr : 0;
172         tselem->id = id;
173         tselem->used = 0;
174         tselem->flag = TSE_CLOSED;
175         te->store_elem = tselem;
176         BKE_outliner_treehash_add_element(soops->treehash, tselem);
177 }
178
179 /* ********************************************************* */
180 /* Tree Management */
181
182 void outliner_free_tree(ListBase *lb)
183 {
184         while (lb->first) {
185                 TreeElement *te = lb->first;
186                 
187                 outliner_free_tree(&te->subtree);
188                 BLI_remlink(lb, te);
189                 
190                 if (te->flag & TE_FREE_NAME) MEM_freeN((void *)te->name);
191                 MEM_freeN(te);
192         }
193 }
194
195 void outliner_cleanup_tree(SpaceOops *soops)
196 {
197         outliner_free_tree(&soops->tree);
198         outliner_storage_cleanup(soops);
199 }
200
201 /* Find specific item from the treestore */
202 TreeElement *outliner_find_tree_element(ListBase *lb, const TreeStoreElem *store_elem)
203 {
204         TreeElement *te, *tes;
205         for (te = lb->first; te; te = te->next) {
206                 if (te->store_elem == store_elem) return te;
207                 tes = outliner_find_tree_element(&te->subtree, store_elem);
208                 if (tes) return tes;
209         }
210         return NULL;
211 }
212
213 /* tse is not in the treestore, we use its contents to find a match */
214 TreeElement *outliner_find_tse(SpaceOops *soops, const TreeStoreElem *tse)
215 {
216         TreeStoreElem *tselem;
217
218         if (tse->id == NULL) return NULL;
219         
220         /* check if 'tse' is in treestore */
221         tselem = BKE_outliner_treehash_lookup_any(soops->treehash, tse->type, tse->nr, tse->id);
222         if (tselem) 
223                 return outliner_find_tree_element(&soops->tree, tselem);
224         
225         return NULL;
226 }
227
228 /* Find treestore that refers to given ID */
229 TreeElement *outliner_find_id(SpaceOops *soops, ListBase *lb, const ID *id)
230 {
231         for (TreeElement *te = lb->first; te; te = te->next) {
232                 TreeStoreElem *tselem = TREESTORE(te);
233                 if (tselem->type == 0) {
234                         if (tselem->id == id) {
235                                 return te;
236                         }
237                         /* only deeper on scene or object */
238                         if (ELEM(te->idcode, ID_OB, ID_SCE) ||
239                             ((soops->outlinevis == SO_GROUPS) && (te->idcode == ID_GR)))
240                         {
241                                 TreeElement *tes = outliner_find_id(soops, &te->subtree, id);
242                                 if (tes) {
243                                         return tes;
244                                 }
245                         }
246                 }
247         }
248         return NULL;
249 }
250
251 TreeElement *outliner_find_posechannel(ListBase *lb, const bPoseChannel *pchan)
252 {
253         for (TreeElement *te = lb->first; te; te = te->next) {
254                 if (te->directdata == pchan) {
255                         return te;
256                 }
257
258                 TreeStoreElem *tselem = TREESTORE(te);
259                 if (ELEM(tselem->type, TSE_POSE_BASE, TSE_POSE_CHANNEL)) {
260                         TreeElement *tes = outliner_find_posechannel(&te->subtree, pchan);
261                         if (tes) {
262                                 return tes;
263                         }
264                 }
265         }
266         return NULL;
267 }
268
269 TreeElement *outliner_find_editbone(ListBase *lb, const EditBone *ebone)
270 {
271         for (TreeElement *te = lb->first; te; te = te->next) {
272                 if (te->directdata == ebone) {
273                         return te;
274                 }
275
276                 TreeStoreElem *tselem = TREESTORE(te);
277                 if (ELEM(tselem->type, 0, TSE_EBONE)) {
278                         TreeElement *tes = outliner_find_editbone(&te->subtree, ebone);
279                         if (tes) {
280                                 return tes;
281                         }
282                 }
283         }
284         return NULL;
285 }
286
287 ID *outliner_search_back(SpaceOops *UNUSED(soops), TreeElement *te, short idcode)
288 {
289         TreeStoreElem *tselem;
290         te = te->parent;
291         
292         while (te) {
293                 tselem = TREESTORE(te);
294                 if (tselem->type == 0 && te->idcode == idcode) return tselem->id;
295                 te = te->parent;
296         }
297         return NULL;
298 }
299
300
301 /* ********************************************************* */
302
303 /* Prototype, see functions below */
304 static TreeElement *outliner_add_element(SpaceOops *soops, ListBase *lb, void *idv, 
305                                          TreeElement *parent, short type, short index);
306
307 /* -------------------------------------------------------- */
308
309 /* special handling of hierarchical non-lib data */
310 static void outliner_add_bone(SpaceOops *soops, ListBase *lb, ID *id, Bone *curBone,
311                               TreeElement *parent, int *a)
312 {
313         TreeElement *te = outliner_add_element(soops, lb, id, parent, TSE_BONE, *a);
314         
315         (*a)++;
316         te->name = curBone->name;
317         te->directdata = curBone;
318         
319         for (curBone = curBone->childbase.first; curBone; curBone = curBone->next) {
320                 outliner_add_bone(soops, &te->subtree, id, curBone, te, a);
321         }
322 }
323
324 /* -------------------------------------------------------- */
325
326 #define LOG2I(x) (int)(log(x) / M_LN2)
327
328 static void outliner_add_passes(SpaceOops *soops, TreeElement *tenla, ID *id, SceneRenderLayer *srl)
329 {
330         TreeStoreElem *tselem = NULL;
331         TreeElement *te = NULL;
332
333         /* log stuff is to convert bitflags (powers of 2) to small integers,
334          * in order to not overflow short tselem->nr */
335         
336         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_COMBINED));
337         te->name = IFACE_("Combined");
338         te->directdata = &srl->passflag;
339         
340         /* save cpu cycles, but we add the first to invoke an open/close triangle */
341         tselem = TREESTORE(tenla);
342         if (tselem->flag & TSE_CLOSED)
343                 return;
344         
345         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_Z));
346         te->name = IFACE_("Z");
347         te->directdata = &srl->passflag;
348
349         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_VECTOR));
350         te->name = IFACE_("Vector");
351         te->directdata = &srl->passflag;
352
353         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_NORMAL));
354         te->name = IFACE_("Normal");
355         te->directdata = &srl->passflag;
356
357         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_UV));
358         te->name = IFACE_("UV");
359         te->directdata = &srl->passflag;
360
361         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_MIST));
362         te->name = IFACE_("Mist");
363         te->directdata = &srl->passflag;
364
365         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_INDEXOB));
366         te->name = IFACE_("Index Object");
367         te->directdata = &srl->passflag;
368
369         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_INDEXMA));
370         te->name = IFACE_("Index Material");
371         te->directdata = &srl->passflag;
372
373         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_RGBA));
374         te->name = IFACE_("Color");
375         te->directdata = &srl->passflag;
376
377         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_DIFFUSE));
378         te->name = IFACE_("Diffuse");
379         te->directdata = &srl->passflag;
380
381         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_SPEC));
382         te->name = IFACE_("Specular");
383         te->directdata = &srl->passflag;
384
385         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_SHADOW));
386         te->name = IFACE_("Shadow");
387         te->directdata = &srl->passflag;
388
389         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_AO));
390         te->name = IFACE_("AO");
391         te->directdata = &srl->passflag;
392
393         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_REFLECT));
394         te->name = IFACE_("Reflection");
395         te->directdata = &srl->passflag;
396
397         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_REFRACT));
398         te->name = IFACE_("Refraction");
399         te->directdata = &srl->passflag;
400
401         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_INDIRECT));
402         te->name = IFACE_("Indirect");
403         te->directdata = &srl->passflag;
404
405         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_ENVIRONMENT));
406         te->name = IFACE_("Environment");
407         te->directdata = &srl->passflag;
408
409         te = outliner_add_element(soops, &tenla->subtree, id, tenla, TSE_R_PASS, LOG2I(SCE_PASS_EMIT));
410         te->name = IFACE_("Emit");
411         te->directdata = &srl->passflag;
412 }
413
414 #undef LOG2I
415
416 static bool outliner_animdata_test(AnimData *adt)
417 {
418         if (adt)
419                 return (adt->action || adt->drivers.first || adt->nla_tracks.first);
420         return false;
421 }
422
423 #ifdef WITH_FREESTYLE
424 static void outliner_add_line_styles(SpaceOops *soops, ListBase *lb, Scene *sce, TreeElement *te)
425 {
426         SceneRenderLayer *srl;
427         FreestyleLineSet *lineset;
428
429         for (srl = sce->r.layers.first; srl; srl = srl->next) {
430                 for (lineset = srl->freestyleConfig.linesets.first; lineset; lineset = lineset->next) {
431                         FreestyleLineStyle *linestyle = lineset->linestyle;
432                         if (linestyle) {
433                                 linestyle->id.tag |= LIB_TAG_DOIT;
434                         }
435                 }
436         }
437         for (srl = sce->r.layers.first; srl; srl = srl->next) {
438                 for (lineset = srl->freestyleConfig.linesets.first; lineset; lineset = lineset->next) {
439                         FreestyleLineStyle *linestyle = lineset->linestyle;
440                         if (linestyle) {
441                                 if (!(linestyle->id.tag & LIB_TAG_DOIT))
442                                         continue;
443                                 linestyle->id.tag &= ~LIB_TAG_DOIT;
444                                 outliner_add_element(soops, lb, linestyle, te, 0, 0);
445                         }
446                 }
447         }
448 }
449 #endif
450
451 static void outliner_add_scene_contents(SpaceOops *soops, ListBase *lb, Scene *sce, TreeElement *te)
452 {
453         SceneRenderLayer *srl;
454         TreeElement *tenla = outliner_add_element(soops, lb, sce, te, TSE_R_LAYER_BASE, 0);
455         int a;
456         
457         tenla->name = IFACE_("RenderLayers");
458         for (a = 0, srl = sce->r.layers.first; srl; srl = srl->next, a++) {
459                 TreeElement *tenlay = outliner_add_element(soops, &tenla->subtree, sce, te, TSE_R_LAYER, a);
460                 tenlay->name = srl->name;
461                 tenlay->directdata = &srl->layflag;
462                 
463                 if (srl->light_override)
464                         outliner_add_element(soops, &tenlay->subtree, srl->light_override, tenlay, TSE_LINKED_LAMP, 0);
465                 if (srl->mat_override)
466                         outliner_add_element(soops, &tenlay->subtree, srl->mat_override, tenlay, TSE_LINKED_MAT, 0);
467                 
468                 outliner_add_passes(soops, tenlay, &sce->id, srl);
469         }
470         
471         // TODO: move this to the front?
472         if (outliner_animdata_test(sce->adt))
473                 outliner_add_element(soops, lb, sce, te, TSE_ANIM_DATA, 0);
474                 
475         outliner_add_element(soops, lb, sce->gpd, te, 0, 0);
476         
477         outliner_add_element(soops,  lb, sce->world, te, 0, 0);
478
479 #ifdef WITH_FREESTYLE
480         if (STREQ(sce->r.engine, RE_engine_id_BLENDER_RENDER) && (sce->r.mode & R_EDGE_FRS))
481                 outliner_add_line_styles(soops, lb, sce, te);
482 #endif
483 }
484
485 // can be inlined if necessary
486 static void outliner_add_object_contents(SpaceOops *soops, TreeElement *te, TreeStoreElem *tselem, Object *ob)
487 {
488         if (outliner_animdata_test(ob->adt))
489                 outliner_add_element(soops, &te->subtree, ob, te, TSE_ANIM_DATA, 0);
490         
491         outliner_add_element(soops, &te->subtree, ob->poselib, te, 0, 0); // XXX FIXME.. add a special type for this
492         
493         if (ob->proxy && !ID_IS_LINKED_DATABLOCK(ob))
494                 outliner_add_element(soops, &te->subtree, ob->proxy, te, TSE_PROXY, 0);
495                 
496         outliner_add_element(soops, &te->subtree, ob->gpd, te, 0, 0);
497         
498         outliner_add_element(soops, &te->subtree, ob->data, te, 0, 0);
499         
500         if (ob->pose) {
501                 bArmature *arm = ob->data;
502                 bPoseChannel *pchan;
503                 TreeElement *tenla = outliner_add_element(soops, &te->subtree, ob, te, TSE_POSE_BASE, 0);
504                 
505                 tenla->name = IFACE_("Pose");
506                 
507                 /* channels undefined in editmode, but we want the 'tenla' pose icon itself */
508                 if ((arm->edbo == NULL) && (ob->mode & OB_MODE_POSE)) {
509                         TreeElement *ten;
510                         int a = 0, const_index = 1000;    /* ensure unique id for bone constraints */
511                         
512                         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next, a++) {
513                                 ten = outliner_add_element(soops, &tenla->subtree, ob, tenla, TSE_POSE_CHANNEL, a);
514                                 ten->name = pchan->name;
515                                 ten->directdata = pchan;
516                                 pchan->temp = (void *)ten;
517                                 
518                                 if (pchan->constraints.first) {
519                                         //Object *target;
520                                         bConstraint *con;
521                                         TreeElement *ten1;
522                                         TreeElement *tenla1 = outliner_add_element(soops, &ten->subtree, ob, ten, TSE_CONSTRAINT_BASE, 0);
523                                         //char *str;
524                                         
525                                         tenla1->name = IFACE_("Constraints");
526                                         for (con = pchan->constraints.first; con; con = con->next, const_index++) {
527                                                 ten1 = outliner_add_element(soops, &tenla1->subtree, ob, tenla1, TSE_CONSTRAINT, const_index);
528 #if 0 /* disabled as it needs to be reworked for recoded constraints system */
529                                                 target = get_constraint_target(con, &str);
530                                                 if (str && str[0]) ten1->name = str;
531                                                 else if (target) ten1->name = target->id.name + 2;
532                                                 else ten1->name = con->name;
533 #endif
534                                                 ten1->name = con->name;
535                                                 ten1->directdata = con;
536                                                 /* possible add all other types links? */
537                                         }
538                                 }
539                         }
540                         /* make hierarchy */
541                         ten = tenla->subtree.first;
542                         while (ten) {
543                                 TreeElement *nten = ten->next, *par;
544                                 tselem = TREESTORE(ten);
545                                 if (tselem->type == TSE_POSE_CHANNEL) {
546                                         pchan = (bPoseChannel *)ten->directdata;
547                                         if (pchan->parent) {
548                                                 BLI_remlink(&tenla->subtree, ten);
549                                                 par = (TreeElement *)pchan->parent->temp;
550                                                 BLI_addtail(&par->subtree, ten);
551                                                 ten->parent = par;
552                                         }
553                                 }
554                                 ten = nten;
555                         }
556                 }
557                 
558                 /* Pose Groups */
559                 if (ob->pose->agroups.first) {
560                         bActionGroup *agrp;
561                         TreeElement *ten_bonegrp = outliner_add_element(soops, &te->subtree, ob, te, TSE_POSEGRP_BASE, 0);
562                         int a = 0;
563
564                         ten_bonegrp->name = IFACE_("Bone Groups");
565                         for (agrp = ob->pose->agroups.first; agrp; agrp = agrp->next, a++) {
566                                 TreeElement *ten;
567                                 ten = outliner_add_element(soops, &ten_bonegrp->subtree, ob, ten_bonegrp, TSE_POSEGRP, a);
568                                 ten->name = agrp->name;
569                                 ten->directdata = agrp;
570                         }
571                 }
572         }
573         
574         for (int a = 0; a < ob->totcol; a++) {
575                 outliner_add_element(soops, &te->subtree, ob->mat[a], te, 0, a);
576         }
577         
578         if (ob->constraints.first) {
579                 //Object *target;
580                 bConstraint *con;
581                 TreeElement *ten;
582                 TreeElement *tenla = outliner_add_element(soops, &te->subtree, ob, te, TSE_CONSTRAINT_BASE, 0);
583                 //char *str;
584                 int a;
585                 
586                 tenla->name = IFACE_("Constraints");
587                 for (con = ob->constraints.first, a = 0; con; con = con->next, a++) {
588                         ten = outliner_add_element(soops, &tenla->subtree, ob, tenla, TSE_CONSTRAINT, a);
589 #if 0 /* disabled due to constraints system targets recode... code here needs review */
590                         target = get_constraint_target(con, &str);
591                         if (str && str[0]) ten->name = str;
592                         else if (target) ten->name = target->id.name + 2;
593                         else ten->name = con->name;
594 #endif
595                         ten->name = con->name;
596                         ten->directdata = con;
597                         /* possible add all other types links? */
598                 }
599         }
600         
601         if (ob->modifiers.first) {
602                 ModifierData *md;
603                 TreeElement *ten_mod = outliner_add_element(soops, &te->subtree, ob, te, TSE_MODIFIER_BASE, 0);
604                 int index;
605                 
606                 ten_mod->name = IFACE_("Modifiers");
607                 for (index = 0, md = ob->modifiers.first; md; index++, md = md->next) {
608                         TreeElement *ten = outliner_add_element(soops, &ten_mod->subtree, ob, ten_mod, TSE_MODIFIER, index);
609                         ten->name = md->name;
610                         ten->directdata = md;
611                         
612                         if (md->type == eModifierType_Lattice) {
613                                 outliner_add_element(soops, &ten->subtree, ((LatticeModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
614                         }
615                         else if (md->type == eModifierType_Curve) {
616                                 outliner_add_element(soops, &ten->subtree, ((CurveModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
617                         }
618                         else if (md->type == eModifierType_Armature) {
619                                 outliner_add_element(soops, &ten->subtree, ((ArmatureModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
620                         }
621                         else if (md->type == eModifierType_Hook) {
622                                 outliner_add_element(soops, &ten->subtree, ((HookModifierData *) md)->object, ten, TSE_LINKED_OB, 0);
623                         }
624                 }
625         }
626         
627         /* vertex groups */
628         if (ob->defbase.first) {
629                 bDeformGroup *defgroup;
630                 TreeElement *ten;
631                 TreeElement *tenla = outliner_add_element(soops, &te->subtree, ob, te, TSE_DEFGROUP_BASE, 0);
632                 int a;
633                 
634                 tenla->name = IFACE_("Vertex Groups");
635                 for (defgroup = ob->defbase.first, a = 0; defgroup; defgroup = defgroup->next, a++) {
636                         ten = outliner_add_element(soops, &tenla->subtree, ob, tenla, TSE_DEFGROUP, a);
637                         ten->name = defgroup->name;
638                         ten->directdata = defgroup;
639                 }
640         }
641         
642         /* duplicated group */
643         if (ob->dup_group)
644                 outliner_add_element(soops, &te->subtree, ob->dup_group, te, 0, 0);
645 }
646
647
648 // can be inlined if necessary
649 static void outliner_add_id_contents(SpaceOops *soops, TreeElement *te, TreeStoreElem *tselem, ID *id)
650 {
651         /* tuck pointer back in object, to construct hierarchy */
652         if (GS(id->name) == ID_OB) id->newid = (ID *)te;
653         
654         /* expand specific data always */
655         switch (GS(id->name)) {
656                 case ID_LI:
657                 {
658                         te->name = ((Library *)id)->name;
659                         break;
660                 }
661                 case ID_SCE:
662                 {
663                         outliner_add_scene_contents(soops, &te->subtree, (Scene *)id, te);
664                         break;
665                 }
666                 case ID_OB:
667                 {
668                         outliner_add_object_contents(soops, te, tselem, (Object *)id);
669                         break;
670                 }
671                 case ID_ME:
672                 {
673                         Mesh *me = (Mesh *)id;
674                         int a;
675                         
676                         if (outliner_animdata_test(me->adt))
677                                 outliner_add_element(soops, &te->subtree, me, te, TSE_ANIM_DATA, 0);
678                         
679                         outliner_add_element(soops, &te->subtree, me->key, te, 0, 0);
680                         for (a = 0; a < me->totcol; a++)
681                                 outliner_add_element(soops, &te->subtree, me->mat[a], te, 0, a);
682                         /* could do tfaces with image links, but the images are not grouped nicely.
683                          * would require going over all tfaces, sort images in use. etc... */
684                         break;
685                 }
686                 case ID_CU:
687                 {
688                         Curve *cu = (Curve *)id;
689                         int a;
690                         
691                         if (outliner_animdata_test(cu->adt))
692                                 outliner_add_element(soops, &te->subtree, cu, te, TSE_ANIM_DATA, 0);
693                         
694                         for (a = 0; a < cu->totcol; a++)
695                                 outliner_add_element(soops, &te->subtree, cu->mat[a], te, 0, a);
696                         break;
697                 }
698                 case ID_MB:
699                 {
700                         MetaBall *mb = (MetaBall *)id;
701                         int a;
702                         
703                         if (outliner_animdata_test(mb->adt))
704                                 outliner_add_element(soops, &te->subtree, mb, te, TSE_ANIM_DATA, 0);
705                         
706                         for (a = 0; a < mb->totcol; a++)
707                                 outliner_add_element(soops, &te->subtree, mb->mat[a], te, 0, a);
708                         break;
709                 }
710                 case ID_MA:
711                 {
712                         Material *ma = (Material *)id;
713                         int a;
714                         
715                         if (outliner_animdata_test(ma->adt))
716                                 outliner_add_element(soops, &te->subtree, ma, te, TSE_ANIM_DATA, 0);
717                         
718                         for (a = 0; a < MAX_MTEX; a++) {
719                                 if (ma->mtex[a]) outliner_add_element(soops, &te->subtree, ma->mtex[a]->tex, te, 0, a);
720                         }
721                         break;
722                 }
723                 case ID_TE:
724                 {
725                         Tex *tex = (Tex *)id;
726                         
727                         if (outliner_animdata_test(tex->adt))
728                                 outliner_add_element(soops, &te->subtree, tex, te, TSE_ANIM_DATA, 0);
729                         
730                         outliner_add_element(soops, &te->subtree, tex->ima, te, 0, 0);
731                         break;
732                 }
733                 case ID_CA:
734                 {
735                         Camera *ca = (Camera *)id;
736                         
737                         if (outliner_animdata_test(ca->adt))
738                                 outliner_add_element(soops, &te->subtree, ca, te, TSE_ANIM_DATA, 0);
739                         break;
740                 }
741                 case ID_CF:
742                 {
743                         CacheFile *cache_file = (CacheFile *)id;
744
745                         if (outliner_animdata_test(cache_file->adt)) {
746                                 outliner_add_element(soops, &te->subtree, cache_file, te, TSE_ANIM_DATA, 0);
747                         }
748
749                         break;
750                 }
751                 case ID_LA:
752                 {
753                         Lamp *la = (Lamp *)id;
754                         int a;
755                         
756                         if (outliner_animdata_test(la->adt))
757                                 outliner_add_element(soops, &te->subtree, la, te, TSE_ANIM_DATA, 0);
758                         
759                         for (a = 0; a < MAX_MTEX; a++) {
760                                 if (la->mtex[a]) outliner_add_element(soops, &te->subtree, la->mtex[a]->tex, te, 0, a);
761                         }
762                         break;
763                 }
764                 case ID_SPK:
765                 {
766                         Speaker *spk = (Speaker *)id;
767
768                         if (outliner_animdata_test(spk->adt))
769                                 outliner_add_element(soops, &te->subtree, spk, te, TSE_ANIM_DATA, 0);
770                         break;
771                 }
772                 case ID_WO:
773                 {
774                         World *wrld = (World *)id;
775                         int a;
776                         
777                         if (outliner_animdata_test(wrld->adt))
778                                 outliner_add_element(soops, &te->subtree, wrld, te, TSE_ANIM_DATA, 0);
779                         
780                         for (a = 0; a < MAX_MTEX; a++) {
781                                 if (wrld->mtex[a]) outliner_add_element(soops, &te->subtree, wrld->mtex[a]->tex, te, 0, a);
782                         }
783                         break;
784                 }
785                 case ID_KE:
786                 {
787                         Key *key = (Key *)id;
788                         
789                         if (outliner_animdata_test(key->adt))
790                                 outliner_add_element(soops, &te->subtree, key, te, TSE_ANIM_DATA, 0);
791                         break;
792                 }
793                 case ID_AC:
794                 {
795                         // XXX do we want to be exposing the F-Curves here?
796                         //bAction *act = (bAction *)id;
797                         break;
798                 }
799                 case ID_AR:
800                 {
801                         bArmature *arm = (bArmature *)id;
802                         int a = 0;
803                         
804                         if (outliner_animdata_test(arm->adt))
805                                 outliner_add_element(soops, &te->subtree, arm, te, TSE_ANIM_DATA, 0);
806                         
807                         if (arm->edbo) {
808                                 EditBone *ebone;
809                                 TreeElement *ten;
810                                 
811                                 for (ebone = arm->edbo->first; ebone; ebone = ebone->next, a++) {
812                                         ten = outliner_add_element(soops, &te->subtree, id, te, TSE_EBONE, a);
813                                         ten->directdata = ebone;
814                                         ten->name = ebone->name;
815                                         ebone->temp.p = ten;
816                                 }
817                                 /* make hierarchy */
818                                 ten = arm->edbo->first ? ((EditBone *)arm->edbo->first)->temp.p : NULL;
819                                 while (ten) {
820                                         TreeElement *nten = ten->next, *par;
821                                         ebone = (EditBone *)ten->directdata;
822                                         if (ebone->parent) {
823                                                 BLI_remlink(&te->subtree, ten);
824                                                 par = ebone->parent->temp.p;
825                                                 BLI_addtail(&par->subtree, ten);
826                                                 ten->parent = par;
827                                         }
828                                         ten = nten;
829                                 }
830                         }
831                         else {
832                                 /* do not extend Armature when we have posemode */
833                                 tselem = TREESTORE(te->parent);
834                                 if (GS(tselem->id->name) == ID_OB && ((Object *)tselem->id)->mode & OB_MODE_POSE) {
835                                         /* pass */
836                                 }
837                                 else {
838                                         Bone *curBone;
839                                         for (curBone = arm->bonebase.first; curBone; curBone = curBone->next) {
840                                                 outliner_add_bone(soops, &te->subtree, id, curBone, te, &a);
841                                         }
842                                 }
843                         }
844                         break;
845                 }
846                 case ID_LS:
847                 {
848                         FreestyleLineStyle *linestyle = (FreestyleLineStyle *)id;
849                         int a;
850                         
851                         if (outliner_animdata_test(linestyle->adt))
852                                 outliner_add_element(soops, &te->subtree, linestyle, te, TSE_ANIM_DATA, 0);
853
854                         for (a = 0; a < MAX_MTEX; a++) {
855                                 if (linestyle->mtex[a])
856                                         outliner_add_element(soops, &te->subtree, linestyle->mtex[a]->tex, te, 0, a);
857                         }
858                         break;
859                 }
860                 case ID_GD:
861                 {
862                         bGPdata *gpd = (bGPdata *)id;
863                         bGPDlayer *gpl;
864                         int a = 0;
865                         
866                         if (outliner_animdata_test(gpd->adt))
867                                 outliner_add_element(soops, &te->subtree, gpd, te, TSE_ANIM_DATA, 0);
868                         
869                         // TODO: base element for layers?
870                         for (gpl = gpd->layers.first; gpl; gpl = gpl->next) {
871                                 outliner_add_element(soops, &te->subtree, gpl, te, TSE_GP_LAYER, a);
872                                 a++;
873                         }
874                         break;
875                 }
876         }
877 }
878
879 // TODO: this function needs to be split up! It's getting a bit too large...
880 // Note: "ID" is not always a real ID
881 static TreeElement *outliner_add_element(SpaceOops *soops, ListBase *lb, void *idv,
882                                          TreeElement *parent, short type, short index)
883 {
884         TreeElement *te;
885         TreeStoreElem *tselem;
886         ID *id = idv;
887         
888         if (ELEM(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
889                 id = ((PointerRNA *)idv)->id.data;
890                 if (!id) id = ((PointerRNA *)idv)->data;
891         }
892         else if (type == TSE_GP_LAYER) {
893                 /* idv is the layer its self */
894                 id = TREESTORE(parent)->id;
895         }
896
897         /* One exception */
898         if (type == TSE_ID_BASE) {
899                 /* pass */
900         }
901         else if (id == NULL) {
902                 return NULL;
903         }
904
905         if (type == 0) {
906                 /* Zero type means real ID, ensure we do not get non-outliner ID types here... */
907                 BLI_assert(TREESTORE_ID_TYPE(id));
908         }
909
910         te = MEM_callocN(sizeof(TreeElement), "tree elem");
911         /* add to the visual tree */
912         BLI_addtail(lb, te);
913         /* add to the storage */
914         check_persistent(soops, te, id, type, index);
915         tselem = TREESTORE(te);
916         
917         /* if we are searching for something expand to see child elements */
918         if (SEARCHING_OUTLINER(soops))
919                 tselem->flag |= TSE_CHILDSEARCH;
920         
921         te->parent = parent;
922         te->index = index;   // for data arays
923         if (ELEM(type, TSE_SEQUENCE, TSE_SEQ_STRIP, TSE_SEQUENCE_DUP)) {
924                 /* pass */
925         }
926         else if (ELEM(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
927                 /* pass */
928         }
929         else if (type == TSE_ANIM_DATA) {
930                 /* pass */
931         }
932         else if (type == TSE_GP_LAYER) {
933                 /* pass */
934         }
935         else if (type == TSE_ID_BASE) {
936                 /* pass */
937         }
938         else {
939                 /* do here too, for blend file viewer, own ID_LI then shows file name */
940                 if (GS(id->name) == ID_LI)
941                         te->name = ((Library *)id)->name;
942                 else
943                         te->name = id->name + 2; // default, can be overridden by Library or non-ID data
944                 te->idcode = GS(id->name);
945         }
946         
947         if (type == 0) {
948                 TreeStoreElem *tsepar = parent ? TREESTORE(parent) : NULL;
949                 
950                 /* ID datablock */
951                 if (tsepar == NULL || tsepar->type != TSE_ID_BASE)
952                         outliner_add_id_contents(soops, te, tselem, id);
953         }
954         else if (type == TSE_ANIM_DATA) {
955                 IdAdtTemplate *iat = (IdAdtTemplate *)idv;
956                 AnimData *adt = (AnimData *)iat->adt;
957                 
958                 /* this element's info */
959                 te->name = IFACE_("Animation");
960                 te->directdata = adt;
961                 
962                 /* Action */
963                 outliner_add_element(soops, &te->subtree, adt->action, te, 0, 0);
964                 
965                 /* Drivers */
966                 if (adt->drivers.first) {
967                         TreeElement *ted = outliner_add_element(soops, &te->subtree, adt, te, TSE_DRIVER_BASE, 0);
968                         ID *lastadded = NULL;
969                         FCurve *fcu;
970                         
971                         ted->name = IFACE_("Drivers");
972                 
973                         for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
974                                 if (fcu->driver && fcu->driver->variables.first) {
975                                         ChannelDriver *driver = fcu->driver;
976                                         DriverVar *dvar;
977                                         
978                                         for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
979                                                 /* loop over all targets used here */
980                                                 DRIVER_TARGETS_USED_LOOPER(dvar) 
981                                                 {
982                                                         if (lastadded != dtar->id) {
983                                                                 // XXX this lastadded check is rather lame, and also fails quite badly...
984                                                                 outliner_add_element(soops, &ted->subtree, dtar->id, ted, TSE_LINKED_OB, 0);
985                                                                 lastadded = dtar->id;
986                                                         }
987                                                 }
988                                                 DRIVER_TARGETS_LOOPER_END
989                                         }
990                                 }
991                         }
992                 }
993                 
994                 /* NLA Data */
995                 if (adt->nla_tracks.first) {
996                         TreeElement *tenla = outliner_add_element(soops, &te->subtree, adt, te, TSE_NLA, 0);
997                         NlaTrack *nlt;
998                         int a = 0;
999                         
1000                         tenla->name = IFACE_("NLA Tracks");
1001                         
1002                         for (nlt = adt->nla_tracks.first; nlt; nlt = nlt->next) {
1003                                 TreeElement *tenlt = outliner_add_element(soops, &tenla->subtree, nlt, tenla, TSE_NLA_TRACK, a);
1004                                 NlaStrip *strip;
1005                                 TreeElement *ten;
1006                                 int b = 0;
1007                                 
1008                                 tenlt->name = nlt->name;
1009                                 
1010                                 for (strip = nlt->strips.first; strip; strip = strip->next, b++) {
1011                                         ten = outliner_add_element(soops, &tenlt->subtree, strip->act, tenlt, TSE_NLA_ACTION, b);
1012                                         if (ten) ten->directdata = strip;
1013                                 }
1014                         }
1015                 }
1016         }
1017         else if (type == TSE_GP_LAYER) {
1018                 bGPDlayer *gpl = (bGPDlayer *)idv;
1019                 
1020                 te->name = gpl->info;
1021                 te->directdata = gpl;
1022         }
1023         else if (type == TSE_SEQUENCE) {
1024                 Sequence *seq = (Sequence *) idv;
1025                 Sequence *p;
1026
1027                 /*
1028                  * The idcode is a little hack, but the outliner
1029                  * only check te->idcode if te->type is equal to zero,
1030                  * so this is "safe".
1031                  */
1032                 te->idcode = seq->type;
1033                 te->directdata = seq;
1034                 te->name = seq->name + 2;
1035
1036                 if (!(seq->type & SEQ_TYPE_EFFECT)) {
1037                         /*
1038                          * This work like the sequence.
1039                          * If the sequence have a name (not default name)
1040                          * show it, in other case put the filename.
1041                          */
1042
1043                         if (seq->type == SEQ_TYPE_META) {
1044                                 p = seq->seqbase.first;
1045                                 while (p) {
1046                                         outliner_add_element(soops, &te->subtree, (void *)p, te, TSE_SEQUENCE, index);
1047                                         p = p->next;
1048                                 }
1049                         }
1050                         else
1051                                 outliner_add_element(soops, &te->subtree, (void *)seq->strip, te, TSE_SEQ_STRIP, index);
1052                 }
1053         }
1054         else if (type == TSE_SEQ_STRIP) {
1055                 Strip *strip = (Strip *)idv;
1056
1057                 if (strip->dir[0] != '\0')
1058                         te->name = strip->dir;
1059                 else
1060                         te->name = IFACE_("Strip None");
1061                 te->directdata = strip;
1062         }
1063         else if (type == TSE_SEQUENCE_DUP) {
1064                 Sequence *seq = (Sequence *)idv;
1065
1066                 te->idcode = seq->type;
1067                 te->directdata = seq;
1068                 te->name = seq->strip->stripdata->name;
1069         }
1070         else if (ELEM(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
1071                 PointerRNA pptr, propptr, *ptr = (PointerRNA *)idv;
1072                 PropertyRNA *prop, *iterprop;
1073                 PropertyType proptype;
1074                 int a, tot;
1075
1076                 /* we do lazy build, for speed and to avoid infinite recusion */
1077
1078                 if (ptr->data == NULL) {
1079                         te->name = IFACE_("(empty)");
1080                 }
1081                 else if (type == TSE_RNA_STRUCT) {
1082                         /* struct */
1083                         te->name = RNA_struct_name_get_alloc(ptr, NULL, 0, NULL);
1084
1085                         if (te->name)
1086                                 te->flag |= TE_FREE_NAME;
1087                         else
1088                                 te->name = RNA_struct_ui_name(ptr->type);
1089
1090                         /* If searching don't expand RNA entries */
1091                         if (SEARCHING_OUTLINER(soops) && BLI_strcasecmp("RNA", te->name) == 0) tselem->flag &= ~TSE_CHILDSEARCH;
1092
1093                         iterprop = RNA_struct_iterator_property(ptr->type);
1094                         tot = RNA_property_collection_length(ptr, iterprop);
1095
1096                         /* auto open these cases */
1097                         if (!parent || (RNA_property_type(parent->directdata)) == PROP_POINTER)
1098                                 if (!tselem->used)
1099                                         tselem->flag &= ~TSE_CLOSED;
1100
1101                         if (TSELEM_OPEN(tselem, soops)) {
1102                                 for (a = 0; a < tot; a++) {
1103                                         RNA_property_collection_lookup_int(ptr, iterprop, a, &propptr);
1104                                         if (!(RNA_property_flag(propptr.data) & PROP_HIDDEN)) {
1105                                                 outliner_add_element(soops, &te->subtree, (void *)ptr, te, TSE_RNA_PROPERTY, a);
1106                                         }
1107                                 }
1108                         }
1109                         else if (tot)
1110                                 te->flag |= TE_LAZY_CLOSED;
1111
1112                         te->rnaptr = *ptr;
1113                 }
1114                 else if (type == TSE_RNA_PROPERTY) {
1115                         /* property */
1116                         iterprop = RNA_struct_iterator_property(ptr->type);
1117                         RNA_property_collection_lookup_int(ptr, iterprop, index, &propptr);
1118
1119                         prop = propptr.data;
1120                         proptype = RNA_property_type(prop);
1121
1122                         te->name = RNA_property_ui_name(prop);
1123                         te->directdata = prop;
1124                         te->rnaptr = *ptr;
1125
1126                         /* If searching don't expand RNA entries */
1127                         if (SEARCHING_OUTLINER(soops) && BLI_strcasecmp("RNA", te->name) == 0) tselem->flag &= ~TSE_CHILDSEARCH;
1128
1129                         if (proptype == PROP_POINTER) {
1130                                 pptr = RNA_property_pointer_get(ptr, prop);
1131
1132                                 if (pptr.data) {
1133                                         if (TSELEM_OPEN(tselem, soops))
1134                                                 outliner_add_element(soops, &te->subtree, (void *)&pptr, te, TSE_RNA_STRUCT, -1);
1135                                         else
1136                                                 te->flag |= TE_LAZY_CLOSED;
1137                                 }
1138                         }
1139                         else if (proptype == PROP_COLLECTION) {
1140                                 tot = RNA_property_collection_length(ptr, prop);
1141
1142                                 if (TSELEM_OPEN(tselem, soops)) {
1143                                         for (a = 0; a < tot; a++) {
1144                                                 RNA_property_collection_lookup_int(ptr, prop, a, &pptr);
1145                                                 outliner_add_element(soops, &te->subtree, (void *)&pptr, te, TSE_RNA_STRUCT, a);
1146                                         }
1147                                 }
1148                                 else if (tot)
1149                                         te->flag |= TE_LAZY_CLOSED;
1150                         }
1151                         else if (ELEM(proptype, PROP_BOOLEAN, PROP_INT, PROP_FLOAT)) {
1152                                 tot = RNA_property_array_length(ptr, prop);
1153
1154                                 if (TSELEM_OPEN(tselem, soops)) {
1155                                         for (a = 0; a < tot; a++)
1156                                                 outliner_add_element(soops, &te->subtree, (void *)ptr, te, TSE_RNA_ARRAY_ELEM, a);
1157                                 }
1158                                 else if (tot)
1159                                         te->flag |= TE_LAZY_CLOSED;
1160                         }
1161                 }
1162                 else if (type == TSE_RNA_ARRAY_ELEM) {
1163                         char c;
1164
1165                         prop = parent->directdata;
1166
1167                         te->directdata = prop;
1168                         te->rnaptr = *ptr;
1169                         te->index = index;
1170
1171                         c = RNA_property_array_item_char(prop, index);
1172
1173                         te->name = MEM_callocN(sizeof(char) * 20, "OutlinerRNAArrayName");
1174                         if (c) sprintf((char *)te->name, "  %c", c);
1175                         else sprintf((char *)te->name, "  %d", index + 1);
1176                         te->flag |= TE_FREE_NAME;
1177                 }
1178         }
1179         else if (type == TSE_KEYMAP) {
1180                 wmKeyMap *km = (wmKeyMap *)idv;
1181                 wmKeyMapItem *kmi;
1182                 char opname[OP_MAX_TYPENAME];
1183                 
1184                 te->directdata = idv;
1185                 te->name = km->idname;
1186                 
1187                 if (TSELEM_OPEN(tselem, soops)) {
1188                         int a = 0;
1189                         
1190                         for (kmi = km->items.first; kmi; kmi = kmi->next, a++) {
1191                                 const char *key = WM_key_event_string(kmi->type, false);
1192                                 
1193                                 if (key[0]) {
1194                                         wmOperatorType *ot = NULL;
1195                                         
1196                                         if (kmi->propvalue) {
1197                                                 /* pass */
1198                                         }
1199                                         else {
1200                                                 ot = WM_operatortype_find(kmi->idname, 0);
1201                                         }
1202                                         
1203                                         if (ot || kmi->propvalue) {
1204                                                 TreeElement *ten = outliner_add_element(soops, &te->subtree, kmi, te, TSE_KEYMAP_ITEM, a);
1205                                                 
1206                                                 ten->directdata = kmi;
1207                                                 
1208                                                 if (kmi->propvalue) {
1209                                                         ten->name = IFACE_("Modal map, not yet");
1210                                                 }
1211                                                 else {
1212                                                         WM_operator_py_idname(opname, ot->idname);
1213                                                         ten->name = BLI_strdup(opname);
1214                                                         ten->flag |= TE_FREE_NAME;
1215                                                 }
1216                                         }
1217                                 }
1218                         }
1219                 }
1220                 else 
1221                         te->flag |= TE_LAZY_CLOSED;
1222         }
1223
1224         return te;
1225 }
1226
1227 /* ======================================================= */
1228 /* Sequencer mode tree building */
1229
1230 /* Helped function to put duplicate sequence in the same tree. */
1231 static int need_add_seq_dup(Sequence *seq)
1232 {
1233         Sequence *p;
1234
1235         if ((!seq->strip) || (!seq->strip->stripdata))
1236                 return(1);
1237
1238         /*
1239          * First check backward, if we found a duplicate
1240          * sequence before this, don't need it, just return.
1241          */
1242         p = seq->prev;
1243         while (p) {
1244                 if ((!p->strip) || (!p->strip->stripdata)) {
1245                         p = p->prev;
1246                         continue;
1247                 }
1248
1249                 if (STREQ(p->strip->stripdata->name, seq->strip->stripdata->name))
1250                         return(2);
1251                 p = p->prev;
1252         }
1253
1254         p = seq->next;
1255         while (p) {
1256                 if ((!p->strip) || (!p->strip->stripdata)) {
1257                         p = p->next;
1258                         continue;
1259                 }
1260
1261                 if (STREQ(p->strip->stripdata->name, seq->strip->stripdata->name))
1262                         return(0);
1263                 p = p->next;
1264         }
1265         return(1);
1266 }
1267
1268 static void outliner_add_seq_dup(SpaceOops *soops, Sequence *seq, TreeElement *te, short index)
1269 {
1270         /* TreeElement *ch; */ /* UNUSED */
1271         Sequence *p;
1272
1273         p = seq;
1274         while (p) {
1275                 if ((!p->strip) || (!p->strip->stripdata) || (p->strip->stripdata->name[0] == '\0')) {
1276                         p = p->next;
1277                         continue;
1278                 }
1279
1280                 if (STREQ(p->strip->stripdata->name, seq->strip->stripdata->name))
1281                         /* ch = */ /* UNUSED */ outliner_add_element(soops, &te->subtree, (void *)p, te, TSE_SEQUENCE, index);
1282                 p = p->next;
1283         }
1284 }
1285
1286
1287 /* ----------------------------------------------- */
1288
1289
1290 static void outliner_add_library_contents(Main *mainvar, SpaceOops *soops, TreeElement *te, Library *lib)
1291 {
1292         TreeElement *ten;
1293         ListBase *lbarray[MAX_LIBARRAY];
1294         int a, tot;
1295         
1296         tot = set_listbasepointers(mainvar, lbarray);
1297         for (a = 0; a < tot; a++) {
1298                 if (lbarray[a]->first) {
1299                         ID *id = lbarray[a]->first;
1300                         
1301                         /* check if there's data in current lib */
1302                         for (; id; id = id->next)
1303                                 if (id->lib == lib)
1304                                         break;
1305                         
1306                         if (id) {
1307                                 ten = outliner_add_element(soops, &te->subtree, lbarray[a], NULL, TSE_ID_BASE, 0);
1308                                 ten->directdata = lbarray[a];
1309                                 
1310                                 ten->name = (char *)BKE_idcode_to_name_plural(GS(id->name));
1311                                 if (ten->name == NULL)
1312                                         ten->name = "UNKNOWN";
1313                                 
1314                                 for (id = lbarray[a]->first; id; id = id->next) {
1315                                         if (id->lib == lib)
1316                                                 outliner_add_element(soops, &ten->subtree, id, ten, 0, 0);
1317                                 }
1318                         }
1319                 }
1320         }
1321         
1322 }
1323
1324 static void outliner_add_orphaned_datablocks(Main *mainvar, SpaceOops *soops)
1325 {
1326         TreeElement *ten;
1327         ListBase *lbarray[MAX_LIBARRAY];
1328         int a, tot;
1329         
1330         tot = set_listbasepointers(mainvar, lbarray);
1331         for (a = 0; a < tot; a++) {
1332                 if (lbarray[a]->first) {
1333                         ID *id = lbarray[a]->first;
1334                         
1335                         /* check if there are any datablocks of this type which are orphans */
1336                         for (; id; id = id->next) {
1337                                 if (ID_REAL_USERS(id) <= 0)
1338                                         break;
1339                         }
1340                         
1341                         if (id) {
1342                                 /* header for this type of datablock */
1343                                 /* TODO's:
1344                                  *   - Add a parameter to BKE_idcode_to_name_plural to get a sane "user-visible" name instead?
1345                                  *   - Ensure that this uses nice icons for the datablock type involved instead of the dot?
1346                                  */
1347                                 ten = outliner_add_element(soops, &soops->tree, lbarray[a], NULL, TSE_ID_BASE, 0);
1348                                 ten->directdata = lbarray[a];
1349                                 
1350                                 ten->name = (char *)BKE_idcode_to_name_plural(GS(id->name));
1351                                 if (ten->name == NULL)
1352                                         ten->name = "UNKNOWN";
1353                                 
1354                                 /* add the orphaned datablocks - these will not be added with any subtrees attached */
1355                                 for (id = lbarray[a]->first; id; id = id->next) {
1356                                         if (ID_REAL_USERS(id) <= 0)
1357                                                 outliner_add_element(soops, &ten->subtree, id, ten, 0, 0);
1358                                 }
1359                         }
1360                 }
1361         }
1362 }
1363
1364 /* ======================================================= */
1365 /* Generic Tree Building helpers - order these are called is top to bottom */
1366
1367 /* Hierarchy --------------------------------------------- */
1368
1369 /* make sure elements are correctly nested */
1370 static void outliner_make_hierarchy(ListBase *lb)
1371 {
1372         TreeElement *te, *ten, *tep;
1373         TreeStoreElem *tselem;
1374
1375         /* build hierarchy */
1376         // XXX also, set extents here...
1377         te = lb->first;
1378         while (te) {
1379                 ten = te->next;
1380                 tselem = TREESTORE(te);
1381                 
1382                 if (tselem->type == 0 && te->idcode == ID_OB) {
1383                         Object *ob = (Object *)tselem->id;
1384                         if (ob->parent && ob->parent->id.newid) {
1385                                 BLI_remlink(lb, te);
1386                                 tep = (TreeElement *)ob->parent->id.newid;
1387                                 BLI_addtail(&tep->subtree, te);
1388                                 // set correct parent pointers
1389                                 for (te = tep->subtree.first; te; te = te->next) te->parent = tep;
1390                         }
1391                 }
1392                 te = ten;
1393         }
1394 }
1395
1396 /* Sorting ------------------------------------------------------ */
1397
1398 typedef struct tTreeSort {
1399         TreeElement *te;
1400         ID *id;
1401         const char *name;
1402         short idcode;
1403 } tTreeSort;
1404
1405 /* alphabetical comparator, tryping to put objects first */
1406 static int treesort_alpha_ob(const void *v1, const void *v2)
1407 {
1408         const tTreeSort *x1 = v1, *x2 = v2;
1409         int comp;
1410         
1411         /* first put objects last (hierarchy) */
1412         comp = (x1->idcode == ID_OB);
1413         if (x2->idcode == ID_OB) comp += 2;
1414         
1415         if (comp == 1) return 1;
1416         else if (comp == 2) return -1;
1417         else if (comp == 3) {
1418                 comp = strcmp(x1->name, x2->name);
1419                 
1420                 if (comp > 0) return 1;
1421                 else if (comp < 0) return -1;
1422                 return 0;
1423         }
1424         return 0;
1425 }
1426
1427 /* alphabetical comparator */
1428 static int treesort_alpha(const void *v1, const void *v2)
1429 {
1430         const tTreeSort *x1 = v1, *x2 = v2;
1431         int comp;
1432         
1433         comp = strcmp(x1->name, x2->name);
1434         
1435         if (comp > 0) return 1;
1436         else if (comp < 0) return -1;
1437         return 0;
1438 }
1439
1440
1441 /* this is nice option for later? doesnt look too useful... */
1442 #if 0
1443 static int treesort_obtype_alpha(const void *v1, const void *v2)
1444 {
1445         const tTreeSort *x1 = v1, *x2 = v2;
1446         
1447         /* first put objects last (hierarchy) */
1448         if (x1->idcode == ID_OB && x2->idcode != ID_OB) {
1449                 return 1;
1450         }
1451         else if (x2->idcode == ID_OB && x1->idcode != ID_OB) {
1452                 return -1;
1453         }
1454         else {
1455                 /* 2nd we check ob type */
1456                 if (x1->idcode == ID_OB && x2->idcode == ID_OB) {
1457                         if      (((Object *)x1->id)->type > ((Object *)x2->id)->type) return  1;
1458                         else if (((Object *)x1->id)->type > ((Object *)x2->id)->type) return -1;
1459                         else return 0;
1460                 }
1461                 else {
1462                         int comp = strcmp(x1->name, x2->name);
1463                         
1464                         if      (comp > 0) return  1;
1465                         else if (comp < 0) return -1;
1466                         return 0;
1467                 }
1468         }
1469 }
1470 #endif
1471
1472 /* sort happens on each subtree individual */
1473 static void outliner_sort(ListBase *lb)
1474 {
1475         TreeElement *te;
1476         TreeStoreElem *tselem;
1477         int totelem = 0;
1478
1479         te = lb->last;
1480         if (te == NULL) return;
1481         tselem = TREESTORE(te);
1482         
1483         /* sorting rules; only object lists, ID lists, or deformgroups */
1484         if ( ELEM(tselem->type, TSE_DEFGROUP, TSE_ID_BASE) || (tselem->type == 0 && te->idcode == ID_OB)) {
1485                 
1486                 /* count first */
1487                 for (te = lb->first; te; te = te->next) totelem++;
1488                 
1489                 if (totelem > 1) {
1490                         tTreeSort *tear = MEM_mallocN(totelem * sizeof(tTreeSort), "tree sort array");
1491                         tTreeSort *tp = tear;
1492                         int skip = 0;
1493
1494                         for (te = lb->first; te; te = te->next, tp++) {
1495                                 tselem = TREESTORE(te);
1496                                 tp->te = te;
1497                                 tp->name = te->name;
1498                                 tp->idcode = te->idcode;
1499                                 
1500                                 if (tselem->type && tselem->type != TSE_DEFGROUP)
1501                                         tp->idcode = 0;  // don't sort this
1502                                 if (tselem->type == TSE_ID_BASE)
1503                                         tp->idcode = 1; // do sort this
1504                                 
1505                                 tp->id = tselem->id;
1506                         }
1507                         
1508                         /* just sort alphabetically */
1509                         if (tear->idcode == 1) {
1510                                 qsort(tear, totelem, sizeof(tTreeSort), treesort_alpha);
1511                         }
1512                         else {
1513                                 /* keep beginning of list */
1514                                 for (tp = tear, skip = 0; skip < totelem; skip++, tp++)
1515                                         if (tp->idcode) break;
1516                                 
1517                                 if (skip < totelem)
1518                                         qsort(tear + skip, totelem - skip, sizeof(tTreeSort), treesort_alpha_ob);
1519                         }
1520                         
1521                         BLI_listbase_clear(lb);
1522                         tp = tear;
1523                         while (totelem--) {
1524                                 BLI_addtail(lb, tp->te);
1525                                 tp++;
1526                         }
1527                         MEM_freeN(tear);
1528                 }
1529         }
1530         
1531         for (te = lb->first; te; te = te->next) {
1532                 outliner_sort(&te->subtree);
1533         }
1534 }
1535
1536 /* Filtering ----------------------------------------------- */
1537
1538 static bool outliner_filter_has_name(TreeElement *te, const char *name, int flags)
1539 {
1540         int fn_flag = 0;
1541
1542         if ((flags & SO_FIND_CASE_SENSITIVE) == 0)
1543                 fn_flag |= FNM_CASEFOLD;
1544
1545         return fnmatch(name, te->name, fn_flag) == 0;
1546 }
1547
1548 static int outliner_filter_tree(SpaceOops *soops, ListBase *lb)
1549 {
1550         TreeElement *te, *ten;
1551         TreeStoreElem *tselem;
1552         char search_buff[sizeof(((struct SpaceOops *)NULL)->search_string) + 2];
1553         char *search_string;
1554
1555         /* although we don't have any search string, we return true 
1556          * since the entire tree is ok then...
1557          */
1558         if (soops->search_string[0] == 0)
1559                 return 1;
1560
1561         if (soops->search_flags & SO_FIND_COMPLETE) {
1562                 search_string = soops->search_string;
1563         }
1564         else {
1565                 /* Implicitly add heading/trailing wildcards if needed. */
1566                 BLI_strncpy_ensure_pad(search_buff, soops->search_string, '*', sizeof(search_buff));
1567                 search_string = search_buff;
1568         }
1569
1570         for (te = lb->first; te; te = ten) {
1571                 ten = te->next;
1572                 
1573                 if (!outliner_filter_has_name(te, search_string, soops->search_flags)) {
1574                         /* item isn't something we're looking for, but...
1575                          *  - if the subtree is expanded, check if there are any matches that can be easily found
1576                          *              so that searching for "cu" in the default scene will still match the Cube
1577                          *      - otherwise, we can't see within the subtree and the item doesn't match,
1578                          *              so these can be safely ignored (i.e. the subtree can get freed)
1579                          */
1580                         tselem = TREESTORE(te);
1581                         
1582                         /* flag as not a found item */
1583                         tselem->flag &= ~TSE_SEARCHMATCH;
1584                         
1585                         if ((!TSELEM_OPEN(tselem, soops)) || outliner_filter_tree(soops, &te->subtree) == 0) {
1586                                 outliner_free_tree(&te->subtree);
1587                                 BLI_remlink(lb, te);
1588                                 
1589                                 if (te->flag & TE_FREE_NAME) MEM_freeN((void *)te->name);
1590                                 MEM_freeN(te);
1591                         }
1592                 }
1593                 else {
1594                         tselem = TREESTORE(te);
1595                         
1596                         /* flag as a found item - we can then highlight it */
1597                         tselem->flag |= TSE_SEARCHMATCH;
1598                         
1599                         /* filter subtree too */
1600                         outliner_filter_tree(soops, &te->subtree);
1601                 }
1602         }
1603         
1604         /* if there are still items in the list, that means that there were still some matches */
1605         return (BLI_listbase_is_empty(lb) == false);
1606 }
1607
1608 /* ======================================================= */
1609 /* Main Tree Building API */
1610
1611 /* Main entry point for building the tree data-structure that the outliner represents */
1612 // TODO: split each mode into its own function?
1613 void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
1614 {
1615         Base *base;
1616         TreeElement *te = NULL, *ten;
1617         TreeStoreElem *tselem;
1618         int show_opened = !soops->treestore || !BLI_mempool_count(soops->treestore); /* on first view, we open scenes */
1619
1620         /* Are we looking for something - we want to tag parents to filter child matches
1621          * - NOT in datablocks view - searching all datablocks takes way too long to be useful
1622          * - this variable is only set once per tree build */
1623         if (soops->search_string[0] != 0 && soops->outlinevis != SO_DATABLOCKS)
1624                 soops->search_flags |= SO_SEARCH_RECURSIVE;
1625         else
1626                 soops->search_flags &= ~SO_SEARCH_RECURSIVE;
1627
1628         if (soops->treehash && (soops->storeflag & SO_TREESTORE_REBUILD)) {
1629                 soops->storeflag &= ~SO_TREESTORE_REBUILD;
1630                 BKE_outliner_treehash_rebuild_from_treestore(soops->treehash, soops->treestore);
1631         }
1632
1633         if (soops->tree.first && (soops->storeflag & SO_TREESTORE_REDRAW))
1634                 return;
1635
1636         outliner_free_tree(&soops->tree);
1637         outliner_storage_cleanup(soops);
1638         
1639         /* options */
1640         if (soops->outlinevis == SO_LIBRARIES) {
1641                 Library *lib;
1642                 
1643                 /* current file first - mainvar provides tselem with unique pointer - not used */
1644                 ten = outliner_add_element(soops, &soops->tree, mainvar, NULL, TSE_ID_BASE, 0);
1645                 ten->name = IFACE_("Current File");
1646
1647                 tselem = TREESTORE(ten);
1648                 if (!tselem->used)
1649                         tselem->flag &= ~TSE_CLOSED;
1650                 
1651                 outliner_add_library_contents(mainvar, soops, ten, NULL);
1652                 
1653                 for (lib = mainvar->library.first; lib; lib = lib->id.next) {
1654                         ten = outliner_add_element(soops, &soops->tree, lib, NULL, 0, 0);
1655                         lib->id.newid = (ID *)ten;
1656                         
1657                         outliner_add_library_contents(mainvar, soops, ten, lib);
1658
1659                 }
1660                 /* make hierarchy */
1661                 ten = soops->tree.first;
1662                 ten = ten->next;  /* first one is main */
1663                 while (ten) {
1664                         TreeElement *nten = ten->next, *par;
1665                         tselem = TREESTORE(ten);
1666                         lib = (Library *)tselem->id;
1667                         if (lib && lib->parent) {
1668                                 par = (TreeElement *)lib->parent->id.newid;
1669                                 if (tselem->id->tag & LIB_TAG_INDIRECT) {
1670                                         /* Only remove from 'first level' if lib is not also directly used. */
1671                                         BLI_remlink(&soops->tree, ten);
1672                                         BLI_addtail(&par->subtree, ten);
1673                                         ten->parent = par;
1674                                 }
1675                                 else {
1676                                         /* Else, make a new copy of the libtree for our parent. */
1677                                         TreeElement *dupten = outliner_add_element(soops, &par->subtree, lib, NULL, 0, 0);
1678                                         outliner_add_library_contents(mainvar, soops, dupten, lib);
1679                                         dupten->parent = par;
1680                                 }
1681                         }
1682                         ten = nten;
1683                 }
1684                 /* restore newid pointers */
1685                 for (lib = mainvar->library.first; lib; lib = lib->id.next)
1686                         lib->id.newid = NULL;
1687                 
1688         }
1689         else if (soops->outlinevis == SO_ALL_SCENES) {
1690                 Scene *sce;
1691                 for (sce = mainvar->scene.first; sce; sce = sce->id.next) {
1692                         te = outliner_add_element(soops, &soops->tree, sce, NULL, 0, 0);
1693                         tselem = TREESTORE(te);
1694                         if (sce == scene && show_opened)
1695                                 tselem->flag &= ~TSE_CLOSED;
1696                         
1697                         for (base = sce->base.first; base; base = base->next) {
1698                                 ten = outliner_add_element(soops, &te->subtree, base->object, te, 0, 0);
1699                                 ten->directdata = base;
1700                         }
1701                         outliner_make_hierarchy(&te->subtree);
1702                         /* clear id.newid, to prevent objects be inserted in wrong scenes (parent in other scene) */
1703                         for (base = sce->base.first; base; base = base->next) base->object->id.newid = NULL;
1704                 }
1705         }
1706         else if (soops->outlinevis == SO_CUR_SCENE) {
1707                 
1708                 outliner_add_scene_contents(soops, &soops->tree, scene, NULL);
1709                 
1710                 for (base = scene->base.first; base; base = base->next) {
1711                         ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1712                         ten->directdata = base;
1713                 }
1714                 outliner_make_hierarchy(&soops->tree);
1715         }
1716         else if (soops->outlinevis == SO_VISIBLE) {
1717                 for (base = scene->base.first; base; base = base->next) {
1718                         if (base->lay & scene->lay)
1719                                 outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1720                 }
1721                 outliner_make_hierarchy(&soops->tree);
1722         }
1723         else if (soops->outlinevis == SO_GROUPS) {
1724                 Group *group;
1725                 GroupObject *go;
1726                 
1727                 for (group = mainvar->group.first; group; group = group->id.next) {
1728                         if (group->gobject.first) {
1729                                 te = outliner_add_element(soops, &soops->tree, group, NULL, 0, 0);
1730                                 
1731                                 for (go = group->gobject.first; go; go = go->next) {
1732                                         ten = outliner_add_element(soops, &te->subtree, go->ob, te, 0, 0);
1733                                         ten->directdata = NULL; /* eh, why? */
1734                                 }
1735                                 outliner_make_hierarchy(&te->subtree);
1736                                 /* clear id.newid, to prevent objects be inserted in wrong scenes (parent in other scene) */
1737                                 for (go = group->gobject.first; go; go = go->next) go->ob->id.newid = NULL;
1738                         }
1739                 }
1740         }
1741         else if (soops->outlinevis == SO_SAME_TYPE) {
1742                 Object *ob = OBACT;
1743                 if (ob) {
1744                         for (base = scene->base.first; base; base = base->next) {
1745                                 if (base->object->type == ob->type) {
1746                                         ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1747                                         ten->directdata = base;
1748                                 }
1749                         }
1750                         outliner_make_hierarchy(&soops->tree);
1751                 }
1752         }
1753         else if (soops->outlinevis == SO_SELECTED) {
1754                 for (base = scene->base.first; base; base = base->next) {
1755                         if (base->lay & scene->lay) {
1756                                 if (base->flag & SELECT) {
1757                                         ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1758                                         ten->directdata = base;
1759                                 }
1760                         }
1761                 }
1762                 outliner_make_hierarchy(&soops->tree);
1763         }
1764         else if (soops->outlinevis == SO_SEQUENCE) {
1765                 Sequence *seq;
1766                 Editing *ed = BKE_sequencer_editing_get(scene, false);
1767                 int op;
1768
1769                 if (ed == NULL)
1770                         return;
1771
1772                 seq = ed->seqbasep->first;
1773                 if (!seq)
1774                         return;
1775
1776                 while (seq) {
1777                         op = need_add_seq_dup(seq);
1778                         if (op == 1) {
1779                                 /* ten = */ outliner_add_element(soops, &soops->tree, (void *)seq, NULL, TSE_SEQUENCE, 0);
1780                         }
1781                         else if (op == 0) {
1782                                 ten = outliner_add_element(soops, &soops->tree, (void *)seq, NULL, TSE_SEQUENCE_DUP, 0);
1783                                 outliner_add_seq_dup(soops, seq, ten, 0);
1784                         }
1785                         seq = seq->next;
1786                 }
1787         }
1788         else if (soops->outlinevis == SO_DATABLOCKS) {
1789                 PointerRNA mainptr;
1790
1791                 RNA_main_pointer_create(mainvar, &mainptr);
1792
1793                 ten = outliner_add_element(soops, &soops->tree, (void *)&mainptr, NULL, TSE_RNA_STRUCT, -1);
1794
1795                 if (show_opened) {
1796                         tselem = TREESTORE(ten);
1797                         tselem->flag &= ~TSE_CLOSED;
1798                 }
1799         }
1800         else if (soops->outlinevis == SO_USERDEF) {
1801                 PointerRNA userdefptr;
1802
1803                 RNA_pointer_create(NULL, &RNA_UserPreferences, &U, &userdefptr);
1804
1805                 ten = outliner_add_element(soops, &soops->tree, (void *)&userdefptr, NULL, TSE_RNA_STRUCT, -1);
1806
1807                 if (show_opened) {
1808                         tselem = TREESTORE(ten);
1809                         tselem->flag &= ~TSE_CLOSED;
1810                 }
1811         }
1812         else if (soops->outlinevis == SO_ID_ORPHANS) {
1813                 outliner_add_orphaned_datablocks(mainvar, soops);
1814         }
1815         else {
1816                 ten = outliner_add_element(soops, &soops->tree, OBACT, NULL, 0, 0);
1817                 if (ten) ten->directdata = BASACT;
1818         }
1819
1820         if ((soops->flag & SO_SKIP_SORT_ALPHA) == 0) {
1821                 outliner_sort(&soops->tree);
1822         }
1823         outliner_filter_tree(soops, &soops->tree);
1824
1825         BKE_main_id_clear_newpoins(mainvar);
1826 }
1827
1828