Merging r58475 through r58700 from trunk into soc-2013-depsgraph_mt
[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 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         int a = 0;
808         
809         if (ELEM3(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
810                 id = ((PointerRNA *)idv)->id.data;
811                 if (!id) id = ((PointerRNA *)idv)->data;
812         }
813
814         /* One exception */
815         if (type == TSE_ID_BASE) {
816                 /* pass */
817         }
818         else if (id == NULL) {
819                 return NULL;
820         }
821
822         te = MEM_callocN(sizeof(TreeElement), "tree elem");
823         /* add to the visual tree */
824         BLI_addtail(lb, te);
825         /* add to the storage */
826         check_persistent(soops, te, id, type, index);
827         tselem = TREESTORE(te);
828         
829         /* if we are searching for something expand to see child elements */
830         if (SEARCHING_OUTLINER(soops))
831                 tselem->flag |= TSE_CHILDSEARCH;
832         
833         te->parent = parent;
834         te->index = index;   // for data arays
835         if (ELEM3(type, TSE_SEQUENCE, TSE_SEQ_STRIP, TSE_SEQUENCE_DUP)) {
836                 /* pass */
837         }
838         else if (ELEM3(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
839                 /* pass */
840         }
841         else if (type == TSE_ANIM_DATA) {
842                 /* pass */
843         }
844         else if (type == TSE_ID_BASE) {
845                 /* pass */
846         }
847         else {
848                 /* do here too, for blend file viewer, own ID_LI then shows file name */
849                 if (GS(id->name) == ID_LI)
850                         te->name = ((Library *)id)->name;
851                 else
852                         te->name = id->name + 2; // default, can be overridden by Library or non-ID data
853                 te->idcode = GS(id->name);
854         }
855         
856         if (type == 0) {
857                 TreeStoreElem *tsepar = parent ? TREESTORE(parent) : NULL;
858                 
859                 /* ID datablock */
860                 if (tsepar == NULL || tsepar->type != TSE_ID_BASE)
861                         outliner_add_id_contents(soops, te, tselem, id);
862         }
863         else if (type == TSE_ANIM_DATA) {
864                 IdAdtTemplate *iat = (IdAdtTemplate *)idv;
865                 AnimData *adt = (AnimData *)iat->adt;
866                 
867                 /* this element's info */
868                 te->name = IFACE_("Animation");
869                 te->directdata = adt;
870                 
871                 /* Action */
872                 outliner_add_element(soops, &te->subtree, adt->action, te, 0, 0);
873                 
874                 /* Drivers */
875                 if (adt->drivers.first) {
876                         TreeElement *ted = outliner_add_element(soops, &te->subtree, adt, te, TSE_DRIVER_BASE, 0);
877                         ID *lastadded = NULL;
878                         FCurve *fcu;
879                         
880                         ted->name = IFACE_("Drivers");
881                 
882                         for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
883                                 if (fcu->driver && fcu->driver->variables.first) {
884                                         ChannelDriver *driver = fcu->driver;
885                                         DriverVar *dvar;
886                                         
887                                         for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
888                                                 /* loop over all targets used here */
889                                                 DRIVER_TARGETS_USED_LOOPER(dvar) 
890                                                 {
891                                                         if (lastadded != dtar->id) {
892                                                                 // XXX this lastadded check is rather lame, and also fails quite badly...
893                                                                 outliner_add_element(soops, &ted->subtree, dtar->id, ted, TSE_LINKED_OB, 0);
894                                                                 lastadded = dtar->id;
895                                                         }
896                                                 }
897                                                 DRIVER_TARGETS_LOOPER_END
898                                         }
899                                 }
900                         }
901                 }
902                 
903                 /* NLA Data */
904                 if (adt->nla_tracks.first) {
905                         TreeElement *tenla = outliner_add_element(soops, &te->subtree, adt, te, TSE_NLA, 0);
906                         NlaTrack *nlt;
907                         int a = 0;
908                         
909                         tenla->name = IFACE_("NLA Tracks");
910                         
911                         for (nlt = adt->nla_tracks.first; nlt; nlt = nlt->next) {
912                                 TreeElement *tenlt = outliner_add_element(soops, &tenla->subtree, nlt, tenla, TSE_NLA_TRACK, a);
913                                 NlaStrip *strip;
914                                 TreeElement *ten;
915                                 int b = 0;
916                                 
917                                 tenlt->name = nlt->name;
918                                 
919                                 for (strip = nlt->strips.first; strip; strip = strip->next, b++) {
920                                         ten = outliner_add_element(soops, &tenlt->subtree, strip->act, tenlt, TSE_NLA_ACTION, b);
921                                         if (ten) ten->directdata = strip;
922                                 }
923                         }
924                 }
925         }
926         else if (type == TSE_SEQUENCE) {
927                 Sequence *seq = (Sequence *) idv;
928                 Sequence *p;
929
930                 /*
931                  * The idcode is a little hack, but the outliner
932                  * only check te->idcode if te->type is equal to zero,
933                  * so this is "safe".
934                  */
935                 te->idcode = seq->type;
936                 te->directdata = seq;
937                 te->name = seq->name + 2;
938
939                 if (seq->type < SEQ_TYPE_EFFECT) {
940                         /*
941                          * This work like the sequence.
942                          * If the sequence have a name (not default name)
943                          * show it, in other case put the filename.
944                          */
945
946                         if (seq->type == SEQ_TYPE_META) {
947                                 p = seq->seqbase.first;
948                                 while (p) {
949                                         outliner_add_element(soops, &te->subtree, (void *)p, te, TSE_SEQUENCE, index);
950                                         p = p->next;
951                                 }
952                         }
953                         else
954                                 outliner_add_element(soops, &te->subtree, (void *)seq->strip, te, TSE_SEQ_STRIP, index);
955                 }
956         }
957         else if (type == TSE_SEQ_STRIP) {
958                 Strip *strip = (Strip *)idv;
959
960                 if (strip->dir[0] != '\0')
961                         te->name = strip->dir;
962                 else
963                         te->name = IFACE_("Strip None");
964                 te->directdata = strip;
965         }
966         else if (type == TSE_SEQUENCE_DUP) {
967                 Sequence *seq = (Sequence *)idv;
968
969                 te->idcode = seq->type;
970                 te->directdata = seq;
971                 te->name = seq->strip->stripdata->name;
972         }
973         else if (ELEM3(type, TSE_RNA_STRUCT, TSE_RNA_PROPERTY, TSE_RNA_ARRAY_ELEM)) {
974                 PointerRNA pptr, propptr, *ptr = (PointerRNA *)idv;
975                 PropertyRNA *prop, *iterprop;
976                 PropertyType proptype;
977                 int a, tot;
978
979                 /* we do lazy build, for speed and to avoid infinite recusion */
980
981                 if (ptr->data == NULL) {
982                         te->name = IFACE_("(empty)");
983                 }
984                 else if (type == TSE_RNA_STRUCT) {
985                         /* struct */
986                         te->name = RNA_struct_name_get_alloc(ptr, NULL, 0, NULL);
987
988                         if (te->name)
989                                 te->flag |= TE_FREE_NAME;
990                         else
991                                 te->name = RNA_struct_ui_name(ptr->type);
992
993                         /* If searching don't expand RNA entries */
994                         if (SEARCHING_OUTLINER(soops) && BLI_strcasecmp("RNA", te->name) == 0) tselem->flag &= ~TSE_CHILDSEARCH;
995
996                         iterprop = RNA_struct_iterator_property(ptr->type);
997                         tot = RNA_property_collection_length(ptr, iterprop);
998
999                         /* auto open these cases */
1000                         if (!parent || (RNA_property_type(parent->directdata)) == PROP_POINTER)
1001                                 if (!tselem->used)
1002                                         tselem->flag &= ~TSE_CLOSED;
1003
1004                         if (TSELEM_OPEN(tselem, soops)) {
1005                                 for (a = 0; a < tot; a++)
1006                                         outliner_add_element(soops, &te->subtree, (void *)ptr, te, TSE_RNA_PROPERTY, a);
1007                         }
1008                         else if (tot)
1009                                 te->flag |= TE_LAZY_CLOSED;
1010
1011                         te->rnaptr = *ptr;
1012                 }
1013                 else if (type == TSE_RNA_PROPERTY) {
1014                         /* property */
1015                         iterprop = RNA_struct_iterator_property(ptr->type);
1016                         RNA_property_collection_lookup_int(ptr, iterprop, index, &propptr);
1017
1018                         prop = propptr.data;
1019                         proptype = RNA_property_type(prop);
1020
1021                         te->name = RNA_property_ui_name(prop);
1022                         te->directdata = prop;
1023                         te->rnaptr = *ptr;
1024
1025                         /* If searching don't expand RNA entries */
1026                         if (SEARCHING_OUTLINER(soops) && BLI_strcasecmp("RNA", te->name) == 0) tselem->flag &= ~TSE_CHILDSEARCH;
1027
1028                         if (proptype == PROP_POINTER) {
1029                                 pptr = RNA_property_pointer_get(ptr, prop);
1030
1031                                 if (pptr.data) {
1032                                         if (TSELEM_OPEN(tselem, soops))
1033                                                 outliner_add_element(soops, &te->subtree, (void *)&pptr, te, TSE_RNA_STRUCT, -1);
1034                                         else
1035                                                 te->flag |= TE_LAZY_CLOSED;
1036                                 }
1037                         }
1038                         else if (proptype == PROP_COLLECTION) {
1039                                 tot = RNA_property_collection_length(ptr, prop);
1040
1041                                 if (TSELEM_OPEN(tselem, soops)) {
1042                                         for (a = 0; a < tot; a++) {
1043                                                 RNA_property_collection_lookup_int(ptr, prop, a, &pptr);
1044                                                 outliner_add_element(soops, &te->subtree, (void *)&pptr, te, TSE_RNA_STRUCT, a);
1045                                         }
1046                                 }
1047                                 else if (tot)
1048                                         te->flag |= TE_LAZY_CLOSED;
1049                         }
1050                         else if (ELEM3(proptype, PROP_BOOLEAN, PROP_INT, PROP_FLOAT)) {
1051                                 tot = RNA_property_array_length(ptr, prop);
1052
1053                                 if (TSELEM_OPEN(tselem, soops)) {
1054                                         for (a = 0; a < tot; a++)
1055                                                 outliner_add_element(soops, &te->subtree, (void *)ptr, te, TSE_RNA_ARRAY_ELEM, a);
1056                                 }
1057                                 else if (tot)
1058                                         te->flag |= TE_LAZY_CLOSED;
1059                         }
1060                 }
1061                 else if (type == TSE_RNA_ARRAY_ELEM) {
1062                         char c;
1063
1064                         prop = parent->directdata;
1065
1066                         te->directdata = prop;
1067                         te->rnaptr = *ptr;
1068                         te->index = index;
1069
1070                         c = RNA_property_array_item_char(prop, index);
1071
1072                         te->name = MEM_callocN(sizeof(char) * 20, "OutlinerRNAArrayName");
1073                         if (c) sprintf((char *)te->name, "  %c", c);
1074                         else sprintf((char *)te->name, "  %d", index + 1);
1075                         te->flag |= TE_FREE_NAME;
1076                 }
1077         }
1078         else if (type == TSE_KEYMAP) {
1079                 wmKeyMap *km = (wmKeyMap *)idv;
1080                 wmKeyMapItem *kmi;
1081                 char opname[OP_MAX_TYPENAME];
1082                 
1083                 te->directdata = idv;
1084                 te->name = km->idname;
1085                 
1086                 if (TSELEM_OPEN(tselem, soops)) {
1087                         a = 0;
1088                         
1089                         for (kmi = km->items.first; kmi; kmi = kmi->next, a++) {
1090                                 const char *key = WM_key_event_string(kmi->type);
1091                                 
1092                                 if (key[0]) {
1093                                         wmOperatorType *ot = NULL;
1094                                         
1095                                         if (kmi->propvalue) {
1096                                                 /* pass */
1097                                         }
1098                                         else {
1099                                                 ot = WM_operatortype_find(kmi->idname, 0);
1100                                         }
1101                                         
1102                                         if (ot || kmi->propvalue) {
1103                                                 TreeElement *ten = outliner_add_element(soops, &te->subtree, kmi, te, TSE_KEYMAP_ITEM, a);
1104                                                 
1105                                                 ten->directdata = kmi;
1106                                                 
1107                                                 if (kmi->propvalue) {
1108                                                         ten->name = IFACE_("Modal map, not yet");
1109                                                 }
1110                                                 else {
1111                                                         WM_operator_py_idname(opname, ot->idname);
1112                                                         ten->name = BLI_strdup(opname);
1113                                                         ten->flag |= TE_FREE_NAME;
1114                                                 }
1115                                         }
1116                                 }
1117                         }
1118                 }
1119                 else 
1120                         te->flag |= TE_LAZY_CLOSED;
1121         }
1122
1123         return te;
1124 }
1125
1126 /* ======================================================= */
1127 /* Sequencer mode tree building */
1128
1129 /* Helped function to put duplicate sequence in the same tree. */
1130 static int need_add_seq_dup(Sequence *seq)
1131 {
1132         Sequence *p;
1133
1134         if ((!seq->strip) || (!seq->strip->stripdata) || (!seq->strip->stripdata->name))
1135                 return(1);
1136
1137         /*
1138          * First check backward, if we found a duplicate
1139          * sequence before this, don't need it, just return.
1140          */
1141         p = seq->prev;
1142         while (p) {
1143                 if ((!p->strip) || (!p->strip->stripdata)) {
1144                         p = p->prev;
1145                         continue;
1146                 }
1147
1148                 if (!strcmp(p->strip->stripdata->name, seq->strip->stripdata->name))
1149                         return(2);
1150                 p = p->prev;
1151         }
1152
1153         p = seq->next;
1154         while (p) {
1155                 if ((!p->strip) || (!p->strip->stripdata)) {
1156                         p = p->next;
1157                         continue;
1158                 }
1159
1160                 if (!strcmp(p->strip->stripdata->name, seq->strip->stripdata->name))
1161                         return(0);
1162                 p = p->next;
1163         }
1164         return(1);
1165 }
1166
1167 static void outliner_add_seq_dup(SpaceOops *soops, Sequence *seq, TreeElement *te, short index)
1168 {
1169         /* TreeElement *ch; */ /* UNUSED */
1170         Sequence *p;
1171
1172         p = seq;
1173         while (p) {
1174                 if ((!p->strip) || (!p->strip->stripdata) || (p->strip->stripdata->name[0] == '\0')) {
1175                         p = p->next;
1176                         continue;
1177                 }
1178
1179                 if (!strcmp(p->strip->stripdata->name, seq->strip->stripdata->name))
1180                         /* ch = */ /* UNUSED */ outliner_add_element(soops, &te->subtree, (void *)p, te, TSE_SEQUENCE, index);
1181                 p = p->next;
1182         }
1183 }
1184
1185 /* ======================================================= */
1186 /* Generic Tree Building helpers - order these are called is top to bottom */
1187
1188 /* Hierarchy --------------------------------------------- */
1189
1190 /* make sure elements are correctly nested */
1191 static void outliner_make_hierarchy(SpaceOops *soops, ListBase *lb)
1192 {
1193         TreeElement *te, *ten, *tep;
1194         TreeStoreElem *tselem;
1195
1196         /* build hierarchy */
1197         // XXX also, set extents here...
1198         te = lb->first;
1199         while (te) {
1200                 ten = te->next;
1201                 tselem = TREESTORE(te);
1202                 
1203                 if (tselem->type == 0 && te->idcode == ID_OB) {
1204                         Object *ob = (Object *)tselem->id;
1205                         if (ob->parent && ob->parent->id.newid) {
1206                                 BLI_remlink(lb, te);
1207                                 tep = (TreeElement *)ob->parent->id.newid;
1208                                 BLI_addtail(&tep->subtree, te);
1209                                 // set correct parent pointers
1210                                 for (te = tep->subtree.first; te; te = te->next) te->parent = tep;
1211                         }
1212                 }
1213                 te = ten;
1214         }
1215 }
1216
1217 /* Sorting ------------------------------------------------------ */
1218
1219 typedef struct tTreeSort {
1220         TreeElement *te;
1221         ID *id;
1222         const char *name;
1223         short idcode;
1224 } tTreeSort;
1225
1226 /* alphabetical comparator, tryping to put objects first */
1227 static int treesort_alpha_ob(const void *v1, const void *v2)
1228 {
1229         const tTreeSort *x1 = v1, *x2 = v2;
1230         int comp;
1231         
1232         /* first put objects last (hierarchy) */
1233         comp = (x1->idcode == ID_OB);
1234         if (x2->idcode == ID_OB) comp += 2;
1235         
1236         if (comp == 1) return 1;
1237         else if (comp == 2) return -1;
1238         else if (comp == 3) {
1239                 comp = strcmp(x1->name, x2->name);
1240                 
1241                 if (comp > 0) return 1;
1242                 else if (comp < 0) return -1;
1243                 return 0;
1244         }
1245         return 0;
1246 }
1247
1248 /* alphabetical comparator */
1249 static int treesort_alpha(const void *v1, const void *v2)
1250 {
1251         const tTreeSort *x1 = v1, *x2 = v2;
1252         int comp;
1253         
1254         comp = strcmp(x1->name, x2->name);
1255         
1256         if (comp > 0) return 1;
1257         else if (comp < 0) return -1;
1258         return 0;
1259 }
1260
1261
1262 /* this is nice option for later? doesnt look too useful... */
1263 #if 0
1264 static int treesort_obtype_alpha(const void *v1, const void *v2)
1265 {
1266         const tTreeSort *x1 = v1, *x2 = v2;
1267         
1268         /* first put objects last (hierarchy) */
1269         if (x1->idcode == ID_OB && x2->idcode != ID_OB) {
1270                 return 1;
1271         }
1272         else if (x2->idcode == ID_OB && x1->idcode != ID_OB) {
1273                 return -1;
1274         }
1275         else {
1276                 /* 2nd we check ob type */
1277                 if (x1->idcode == ID_OB && x2->idcode == ID_OB) {
1278                         if      (((Object *)x1->id)->type > ((Object *)x2->id)->type) return  1;
1279                         else if (((Object *)x1->id)->type > ((Object *)x2->id)->type) return -1;
1280                         else return 0;
1281                 }
1282                 else {
1283                         int comp = strcmp(x1->name, x2->name);
1284                         
1285                         if      (comp > 0) return  1;
1286                         else if (comp < 0) return -1;
1287                         return 0;
1288                 }
1289         }
1290 }
1291 #endif
1292
1293 /* sort happens on each subtree individual */
1294 static void outliner_sort(SpaceOops *soops, ListBase *lb)
1295 {
1296         TreeElement *te;
1297         TreeStoreElem *tselem;
1298         int totelem = 0;
1299         
1300         te = lb->last;
1301         if (te == NULL) return;
1302         tselem = TREESTORE(te);
1303         
1304         /* sorting rules; only object lists, ID lists, or deformgroups */
1305         if ( ELEM(tselem->type, TSE_DEFGROUP, TSE_ID_BASE) || (tselem->type == 0 && te->idcode == ID_OB)) {
1306                 
1307                 /* count first */
1308                 for (te = lb->first; te; te = te->next) totelem++;
1309                 
1310                 if (totelem > 1) {
1311                         tTreeSort *tear = MEM_mallocN(totelem * sizeof(tTreeSort), "tree sort array");
1312                         tTreeSort *tp = tear;
1313                         int skip = 0;
1314
1315                         for (te = lb->first; te; te = te->next, tp++) {
1316                                 tselem = TREESTORE(te);
1317                                 tp->te = te;
1318                                 tp->name = te->name;
1319                                 tp->idcode = te->idcode;
1320                                 
1321                                 if (tselem->type && tselem->type != TSE_DEFGROUP)
1322                                         tp->idcode = 0;  // don't sort this
1323                                 if (tselem->type == TSE_ID_BASE)
1324                                         tp->idcode = 1; // do sort this
1325                                 
1326                                 tp->id = tselem->id;
1327                         }
1328                         
1329                         /* just sort alphabetically */
1330                         if (tear->idcode == 1) {
1331                                 qsort(tear, totelem, sizeof(tTreeSort), treesort_alpha);
1332                         }
1333                         else {
1334                                 /* keep beginning of list */
1335                                 for (tp = tear, skip = 0; skip < totelem; skip++, tp++)
1336                                         if (tp->idcode) break;
1337                                 
1338                                 if (skip < totelem)
1339                                         qsort(tear + skip, totelem - skip, sizeof(tTreeSort), treesort_alpha_ob);
1340                         }
1341                         
1342                         lb->first = lb->last = NULL;
1343                         tp = tear;
1344                         while (totelem--) {
1345                                 BLI_addtail(lb, tp->te);
1346                                 tp++;
1347                         }
1348                         MEM_freeN(tear);
1349                 }
1350         }
1351         
1352         for (te = lb->first; te; te = te->next) {
1353                 outliner_sort(soops, &te->subtree);
1354         }
1355 }
1356
1357 /* Filtering ----------------------------------------------- */
1358
1359 static int outliner_filter_has_name(TreeElement *te, const char *name, int flags)
1360 {
1361 #if 0
1362         int found = 0;
1363         
1364         /* determine if match */
1365         if (flags & SO_FIND_CASE_SENSITIVE) {
1366                 if (flags & SO_FIND_COMPLETE)
1367                         found = strcmp(te->name, name) == 0;
1368                 else
1369                         found = strstr(te->name, name) != NULL;
1370         }
1371         else {
1372                 if (flags & SO_FIND_COMPLETE)
1373                         found = BLI_strcasecmp(te->name, name) == 0;
1374                 else
1375                         found = BLI_strcasestr(te->name, name) != NULL;
1376         }
1377 #else
1378         
1379         int fn_flag = 0;
1380         int found = 0;
1381         
1382         if ((flags & SO_FIND_CASE_SENSITIVE) == 0)
1383                 fn_flag |= FNM_CASEFOLD;
1384
1385         if (flags & SO_FIND_COMPLETE) {
1386                 found = fnmatch(name, te->name, fn_flag) == 0;
1387         }
1388         else {
1389                 char fn_name[sizeof(((struct SpaceOops *)NULL)->search_string) + 2];
1390                 BLI_snprintf(fn_name, sizeof(fn_name), "*%s*", name);
1391                 found = fnmatch(fn_name, te->name, fn_flag) == 0;
1392         }
1393         return found;
1394 #endif
1395 }
1396
1397 static int outliner_filter_tree(SpaceOops *soops, ListBase *lb)
1398 {
1399         TreeElement *te, *ten;
1400         TreeStoreElem *tselem;
1401         
1402         /* although we don't have any search string, we return TRUE 
1403          * since the entire tree is ok then...
1404          */
1405         if (soops->search_string[0] == 0)
1406                 return 1;
1407
1408         for (te = lb->first; te; te = ten) {
1409                 ten = te->next;
1410                 
1411                 if (0 == outliner_filter_has_name(te, soops->search_string, soops->search_flags)) {
1412                         /* item isn't something we're looking for, but...
1413                          *  - if the subtree is expanded, check if there are any matches that can be easily found
1414                          *              so that searching for "cu" in the default scene will still match the Cube
1415                          *      - otherwise, we can't see within the subtree and the item doesn't match,
1416                          *              so these can be safely ignored (i.e. the subtree can get freed)
1417                          */
1418                         tselem = TREESTORE(te);
1419                         
1420                         /* flag as not a found item */
1421                         tselem->flag &= ~TSE_SEARCHMATCH;
1422                         
1423                         if ((!TSELEM_OPEN(tselem, soops)) || outliner_filter_tree(soops, &te->subtree) == 0) {
1424                                 outliner_free_tree(&te->subtree);
1425                                 BLI_remlink(lb, te);
1426                                 
1427                                 if (te->flag & TE_FREE_NAME) MEM_freeN((void *)te->name);
1428                                 MEM_freeN(te);
1429                         }
1430                 }
1431                 else {
1432                         tselem = TREESTORE(te);
1433                         
1434                         /* flag as a found item - we can then highlight it */
1435                         tselem->flag |= TSE_SEARCHMATCH;
1436                         
1437                         /* filter subtree too */
1438                         outliner_filter_tree(soops, &te->subtree);
1439                 }
1440         }
1441         
1442         /* if there are still items in the list, that means that there were still some matches */
1443         return (lb->first != NULL);
1444 }
1445
1446 static void outliner_add_library_contents(Main *mainvar, SpaceOops *soops, TreeElement *te, Library *lib)
1447 {
1448         TreeElement *ten;
1449         ListBase *lbarray[MAX_LIBARRAY];
1450         int a, tot;
1451         
1452         tot = set_listbasepointers(mainvar, lbarray);
1453         for (a = 0; a < tot; a++) {
1454                 if (lbarray[a]->first) {
1455                         ID *id = lbarray[a]->first;
1456                         
1457                         /* check if there's data in current lib */
1458                         for (; id; id = id->next)
1459                                 if (id->lib == lib)
1460                                         break;
1461                         
1462                         if (id) {
1463                                 
1464                                 ten = outliner_add_element(soops, &te->subtree, (void *)lbarray[a], NULL, TSE_ID_BASE, 0);
1465                                 ten->directdata = lbarray[a];
1466                                 
1467                                 ten->name = (char *)BKE_idcode_to_name_plural(GS(id->name));
1468                                 if (ten->name == NULL)
1469                                         ten->name = "UNKNOWN";
1470                                 
1471                                 for (id = lbarray[a]->first; id; id = id->next) {
1472                                         if (id->lib == lib)
1473                                                 outliner_add_element(soops, &ten->subtree, id, ten, 0, 0);
1474                                 }
1475                         }
1476                 }
1477         }
1478         
1479 }
1480
1481
1482 /* ======================================================= */
1483 /* Main Tree Building API */
1484
1485 /* Main entry point for building the tree data-structure that the outliner represents */
1486 // TODO: split each mode into its own function?
1487 void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
1488 {
1489         Base *base;
1490         Object *ob;
1491         TreeElement *te = NULL, *ten;
1492         TreeStoreElem *tselem;
1493         int show_opened = (soops->treestore == NULL); /* on first view, we open scenes */
1494
1495         /* Are we looking for something - we want to tag parents to filter child matches
1496          * - NOT in datablocks view - searching all datablocks takes way too long to be useful
1497          * - this variable is only set once per tree build */
1498         if (soops->search_string[0] != 0 && soops->outlinevis != SO_DATABLOCKS)
1499                 soops->search_flags |= SO_SEARCH_RECURSIVE;
1500         else
1501                 soops->search_flags &= ~SO_SEARCH_RECURSIVE;
1502
1503         if (soops->tree.first && (soops->storeflag & SO_TREESTORE_REDRAW))
1504                 return;
1505
1506         outliner_free_tree(&soops->tree);
1507         outliner_storage_cleanup(soops);
1508         
1509         /* clear ob id.new flags */
1510         for (ob = mainvar->object.first; ob; ob = ob->id.next) ob->id.newid = NULL;
1511         
1512         /* options */
1513         if (soops->outlinevis == SO_LIBRARIES) {
1514                 Library *lib;
1515                 
1516                 /* current file first - mainvar provides tselem with unique pointer - not used */
1517                 ten = outliner_add_element(soops, &soops->tree, mainvar, NULL, TSE_ID_BASE, 0);
1518                 ten->name = IFACE_("Current File");
1519
1520                 tselem = TREESTORE(ten);
1521                 if (!tselem->used)
1522                         tselem->flag &= ~TSE_CLOSED;
1523                 
1524                 outliner_add_library_contents(mainvar, soops, ten, NULL);
1525                 
1526                 for (lib = mainvar->library.first; lib; lib = lib->id.next) {
1527                         ten = outliner_add_element(soops, &soops->tree, lib, NULL, 0, 0);
1528                         lib->id.newid = (ID *)ten;
1529                         
1530                         outliner_add_library_contents(mainvar, soops, ten, lib);
1531
1532                 }
1533                 /* make hierarchy */
1534                 ten = soops->tree.first;
1535                 ten = ten->next;  /* first one is main */
1536                 while (ten) {
1537                         TreeElement *nten = ten->next, *par;
1538                         tselem = TREESTORE(ten);
1539                         lib = (Library *)tselem->id;
1540                         if (lib && lib->parent) {
1541                                 BLI_remlink(&soops->tree, ten);
1542                                 par = (TreeElement *)lib->parent->id.newid;
1543                                 BLI_addtail(&par->subtree, ten);
1544                                 ten->parent = par;
1545                         }
1546                         ten = nten;
1547                 }
1548                 /* restore newid pointers */
1549                 for (lib = mainvar->library.first; lib; lib = lib->id.next)
1550                         lib->id.newid = NULL;
1551                 
1552         }
1553         else if (soops->outlinevis == SO_ALL_SCENES) {
1554                 Scene *sce;
1555                 for (sce = mainvar->scene.first; sce; sce = sce->id.next) {
1556                         te = outliner_add_element(soops, &soops->tree, sce, NULL, 0, 0);
1557                         tselem = TREESTORE(te);
1558                         if (sce == scene && show_opened)
1559                                 tselem->flag &= ~TSE_CLOSED;
1560                         
1561                         for (base = sce->base.first; base; base = base->next) {
1562                                 ten = outliner_add_element(soops, &te->subtree, base->object, te, 0, 0);
1563                                 ten->directdata = base;
1564                         }
1565                         outliner_make_hierarchy(soops, &te->subtree);
1566                         /* clear id.newid, to prevent objects be inserted in wrong scenes (parent in other scene) */
1567                         for (base = sce->base.first; base; base = base->next) base->object->id.newid = NULL;
1568                 }
1569         }
1570         else if (soops->outlinevis == SO_CUR_SCENE) {
1571                 
1572                 outliner_add_scene_contents(soops, &soops->tree, scene, NULL);
1573                 
1574                 for (base = scene->base.first; base; base = base->next) {
1575                         ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1576                         ten->directdata = base;
1577                 }
1578                 outliner_make_hierarchy(soops, &soops->tree);
1579         }
1580         else if (soops->outlinevis == SO_VISIBLE) {
1581                 for (base = scene->base.first; base; base = base->next) {
1582                         if (base->lay & scene->lay)
1583                                 outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1584                 }
1585                 outliner_make_hierarchy(soops, &soops->tree);
1586         }
1587         else if (soops->outlinevis == SO_GROUPS) {
1588                 Group *group;
1589                 GroupObject *go;
1590                 
1591                 for (group = mainvar->group.first; group; group = group->id.next) {
1592                         if (group->gobject.first) {
1593                                 te = outliner_add_element(soops, &soops->tree, group, NULL, 0, 0);
1594                                 
1595                                 for (go = group->gobject.first; go; go = go->next) {
1596                                         ten = outliner_add_element(soops, &te->subtree, go->ob, te, 0, 0);
1597                                         ten->directdata = NULL; /* eh, why? */
1598                                 }
1599                                 outliner_make_hierarchy(soops, &te->subtree);
1600                                 /* clear id.newid, to prevent objects be inserted in wrong scenes (parent in other scene) */
1601                                 for (go = group->gobject.first; go; go = go->next) go->ob->id.newid = NULL;
1602                         }
1603                 }
1604         }
1605         else if (soops->outlinevis == SO_SAME_TYPE) {
1606                 Object *ob = OBACT;
1607                 if (ob) {
1608                         for (base = scene->base.first; base; base = base->next) {
1609                                 if (base->object->type == ob->type) {
1610                                         ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1611                                         ten->directdata = base;
1612                                 }
1613                         }
1614                         outliner_make_hierarchy(soops, &soops->tree);
1615                 }
1616         }
1617         else if (soops->outlinevis == SO_SELECTED) {
1618                 for (base = scene->base.first; base; base = base->next) {
1619                         if (base->lay & scene->lay) {
1620                                 if (base == BASACT || (base->flag & SELECT)) {
1621                                         ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
1622                                         ten->directdata = base;
1623                                 }
1624                         }
1625                 }
1626                 outliner_make_hierarchy(soops, &soops->tree);
1627         }
1628         else if (soops->outlinevis == SO_SEQUENCE) {
1629                 Sequence *seq;
1630                 Editing *ed = BKE_sequencer_editing_get(scene, FALSE);
1631                 int op;
1632
1633                 if (ed == NULL)
1634                         return;
1635
1636                 seq = ed->seqbasep->first;
1637                 if (!seq)
1638                         return;
1639
1640                 while (seq) {
1641                         op = need_add_seq_dup(seq);
1642                         if (op == 1) {
1643                                 /* ten = */ outliner_add_element(soops, &soops->tree, (void *)seq, NULL, TSE_SEQUENCE, 0);
1644                         }
1645                         else if (op == 0) {
1646                                 ten = outliner_add_element(soops, &soops->tree, (void *)seq, NULL, TSE_SEQUENCE_DUP, 0);
1647                                 outliner_add_seq_dup(soops, seq, ten, 0);
1648                         }
1649                         seq = seq->next;
1650                 }
1651         }
1652         else if (soops->outlinevis == SO_DATABLOCKS) {
1653                 PointerRNA mainptr;
1654
1655                 RNA_main_pointer_create(mainvar, &mainptr);
1656
1657                 ten = outliner_add_element(soops, &soops->tree, (void *)&mainptr, NULL, TSE_RNA_STRUCT, -1);
1658
1659                 if (show_opened) {
1660                         tselem = TREESTORE(ten);
1661                         tselem->flag &= ~TSE_CLOSED;
1662                 }
1663         }
1664         else if (soops->outlinevis == SO_USERDEF) {
1665                 PointerRNA userdefptr;
1666
1667                 RNA_pointer_create(NULL, &RNA_UserPreferences, &U, &userdefptr);
1668
1669                 ten = outliner_add_element(soops, &soops->tree, (void *)&userdefptr, NULL, TSE_RNA_STRUCT, -1);
1670
1671                 if (show_opened) {
1672                         tselem = TREESTORE(ten);
1673                         tselem->flag &= ~TSE_CLOSED;
1674                 }
1675         }
1676         else if (soops->outlinevis == SO_KEYMAP) {
1677                 wmWindowManager *wm = mainvar->wm.first;
1678                 wmKeyMap *km;
1679                 
1680                 for (km = wm->defaultconf->keymaps.first; km; km = km->next) {
1681                         /* ten = */ outliner_add_element(soops, &soops->tree, (void *)km, NULL, TSE_KEYMAP, 0);
1682                 }
1683         }
1684         else {
1685                 ten = outliner_add_element(soops, &soops->tree, OBACT, NULL, 0, 0);
1686                 if (ten) ten->directdata = BASACT;
1687         }
1688
1689         outliner_sort(soops, &soops->tree);
1690         outliner_filter_tree(soops, &soops->tree);
1691 }
1692
1693