svn merge ^/trunk/blender -r45927:HEAD --accept=theirs-full
[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