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