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