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