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