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