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