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