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