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