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