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