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