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