ges/ges-timeline-tree.c

   1 /* GStreamer Editing Services
   2  * Copyright (C) 2019 Igalia S.L
   3  *     Author: 2019 Thibault Saunier <tsaunier@igalia.com>
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License along with this library; if not, write to the
  17  * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
  18  * Boston, MA 02110-1301, USA.
  19  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 #include "config.h"
  23 #endif
  24
  25 #include "ges-timeline-tree.h"
  26 #include "ges-internal.h"
  27 #include "ges-marker-list.h"
  28
  29 GST_DEBUG_CATEGORY_STATIC (tree_debug);
  30 #undef GST_CAT_DEFAULT
  31 #define GST_CAT_DEFAULT tree_debug
  32
  33 #define ELEMENT_EDGE_VALUE(e, edge) ((edge == GES_EDGE_END) ? _END (e) : _START (e))
  34
  35 typedef struct _SnappedPosition
  36 {
  37   /* the element that was being snapped */
  38   GESTrackElement *element;
  39   /* the position of element, and whether it is a negative position */
  40   gboolean negative;
  41   GstClockTime position;
  42   /* the element that was snapped to */
  43   GESTrackElement *snapped_to;
  44   /* the snapped positioned */
  45   GstClockTime snapped;
  46   /* the distance below which two elements can snap */
  47   GstClockTime distance;
  48 } SnappedPosition;
  49
  50 typedef enum
  51 {
  52   EDIT_MOVE,
  53   EDIT_TRIM_START,
  54   EDIT_TRIM_END,
  55   EDIT_TRIM_INPOINT_ONLY,
  56 } ElementEditMode;
  57
  58 typedef struct _EditData
  59 {
  60   /* offsets to use */
  61   GstClockTime offset;
  62   gint64 layer_offset;
  63   /* actual values */
  64   GstClockTime duration;
  65   GstClockTime start;
  66   GstClockTime inpoint;
  67   guint32 layer_priority;
  68   /* mode */
  69   ElementEditMode mode;
  70 } EditData;
  71
  72 typedef struct _PositionData
  73 {
  74   guint32 layer_priority;
  75   GstClockTime start;
  76   GstClockTime end;
  77 } PositionData;
  78
  79 /*  *INDENT-OFF* */
  80 struct _TreeIterationData
  81 {
  82   GNode *root;
  83   gboolean res;
  84   /* an error to set */
  85   GError **error;
  86
  87   /* The element we are visiting */
  88   GESTimelineElement *element;
  89   /* the position data of the visited element */
  90   PositionData *pos_data;
  91
  92   /* All the TrackElement currently moving: owned by data */
  93   GHashTable *moving;
  94
  95   /* Elements overlaping on the start/end of @element */
  96   GESTimelineElement *overlaping_on_start;
  97   GESTimelineElement *overlaping_on_end;
  98   GstClockTime overlap_start_final_time;
  99   GstClockTime overlap_end_first_time;
 100
 101   SnappedPosition *snap;
 102   GList *sources;
 103   GstClockTime position;
 104   GstClockTime negative;
 105
 106   GESEdge edge;
 107   GList *neighbours;
 108 } tree_iteration_data_init = {
 109    .root = NULL,
 110    .res = TRUE,
 111    .element = NULL,
 112    .pos_data = NULL,
 113    .moving = NULL,
 114    .overlaping_on_start = NULL,
 115    .overlaping_on_end = NULL,
 116    .overlap_start_final_time = GST_CLOCK_TIME_NONE,
 117    .overlap_end_first_time = GST_CLOCK_TIME_NONE,
 118    .snap = NULL,
 119    .sources = NULL,
 120    .position = GST_CLOCK_TIME_NONE,
 121    .negative = FALSE,
 122    .edge = GES_EDGE_NONE,
 123    .neighbours = NULL,
 124 };
 125 /*  *INDENT-ON* */
 126
 127 typedef struct _TreeIterationData TreeIterationData;
 128
 129 static EditData *
 130 new_edit_data (ElementEditMode mode, GstClockTimeDiff offset,
 131     gint64 layer_offset)
 132 {
 133   EditData *data = g_new (EditData, 1);
 134
 135   data->start = GST_CLOCK_TIME_NONE;
 136   data->duration = GST_CLOCK_TIME_NONE;
 137   data->inpoint = GST_CLOCK_TIME_NONE;
 138   data->layer_priority = GES_TIMELINE_ELEMENT_NO_LAYER_PRIORITY;
 139
 140   data->mode = mode;
 141   data->offset = offset;
 142   data->layer_offset = layer_offset;
 143
 144   return data;
 145 }
 146
 147 static SnappedPosition *
 148 new_snapped_position (GstClockTime distance)
 149 {
 150   SnappedPosition *snap;
 151
 152   if (distance == 0)
 153     return NULL;
 154
 155   snap = g_new0 (SnappedPosition, 1);
 156   snap->position = GST_CLOCK_TIME_NONE;
 157   snap->snapped = GST_CLOCK_TIME_NONE;
 158   snap->distance = distance;
 159
 160   return snap;
 161 }
 162
 163 static GHashTable *
 164 new_edit_table ()
 165 {
 166   return g_hash_table_new_full (NULL, NULL, NULL, g_free);
 167 }
 168
 169 static GHashTable *
 170 new_position_table ()
 171 {
 172   return g_hash_table_new_full (NULL, NULL, NULL, g_free);
 173 }
 174
 175 void
 176 timeline_tree_init_debug (void)
 177 {
 178   GST_DEBUG_CATEGORY_INIT (tree_debug, "gestree",
 179       GST_DEBUG_FG_YELLOW, "timeline tree");
 180 }
 181
 182
 183 static gboolean
 184 print_node (GNode * node, gpointer unused_data)
 185 {
 186   if (G_NODE_IS_ROOT (node)) {
 187     gst_print ("Timeline: %p\n", node->data);
 188     return FALSE;
 189   }
 190
 191   gst_print ("%*c- %" GES_FORMAT " - layer %" G_GINT32_FORMAT "\n",
 192       2 * g_node_depth (node), ' ', GES_ARGS (node->data),
 193       ges_timeline_element_get_layer_priority (node->data));
 194
 195   return FALSE;
 196 }
 197
 198 void
 199 timeline_tree_debug (GNode * root)
 200 {
 201   g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_ALL, -1,
 202       (GNodeTraverseFunc) print_node, NULL);
 203 }
 204
 205 static GNode *
 206 find_node (GNode * root, gpointer element)
 207 {
 208   return g_node_find (root, G_IN_ORDER, G_TRAVERSE_ALL, element);
 209 }
 210
 211 static void
 212 timeline_element_parent_cb (GESTimelineElement * child, GParamSpec * arg
 213     G_GNUC_UNUSED, GNode * root)
 214 {
 215   GNode *new_parent_node = NULL, *node = find_node (root, child);
 216
 217   if (child->parent)
 218     new_parent_node = find_node (root, child->parent);
 219
 220   if (!new_parent_node)
 221     new_parent_node = root;
 222
 223   g_node_unlink (node);
 224   g_node_prepend (new_parent_node, node);
 225 }
 226
 227 void
 228 timeline_tree_track_element (GNode * root, GESTimelineElement * element)
 229 {
 230   GNode *node;
 231   GNode *parent;
 232   GESTimelineElement *toplevel;
 233
 234   if (find_node (root, element)) {
 235     return;
 236   }
 237
 238   g_signal_connect (element, "notify::parent",
 239       G_CALLBACK (timeline_element_parent_cb), root);
 240
 241   toplevel = ges_timeline_element_peak_toplevel (element);
 242   if (toplevel == element) {
 243     GST_DEBUG ("Tracking toplevel element %" GES_FORMAT, GES_ARGS (element));
 244
 245     node = g_node_prepend_data (root, element);
 246   } else {
 247     parent = find_node (root, element->parent);
 248     GST_LOG ("%" GES_FORMAT "parent is %" GES_FORMAT, GES_ARGS (element),
 249         GES_ARGS (element->parent));
 250     g_assert (parent);
 251     node = g_node_prepend_data (parent, element);
 252   }
 253
 254   if (GES_IS_CONTAINER (element)) {
 255     GList *tmp;
 256
 257     for (tmp = GES_CONTAINER_CHILDREN (element); tmp; tmp = tmp->next) {
 258       GNode *child_node = find_node (root, tmp->data);
 259
 260       if (child_node) {
 261         g_node_unlink (child_node);
 262         g_node_prepend (node, child_node);
 263       } else {
 264         timeline_tree_track_element (root, tmp->data);
 265       }
 266     }
 267   }
 268
 269   timeline_update_duration (root->data);
 270 }
 271
 272 void
 273 timeline_tree_stop_tracking_element (GNode * root, GESTimelineElement * element)
 274 {
 275   GNode *node = find_node (root, element);
 276
 277   node = find_node (root, element);
 278
 279   /* Move children to the parent */
 280   while (node->children) {
 281     GNode *tmp = node->children;
 282     g_node_unlink (tmp);
 283     g_node_prepend (node->parent, tmp);
 284   }
 285
 286   g_assert (node);
 287   GST_DEBUG ("Stop tracking %" GES_FORMAT, GES_ARGS (element));
 288   g_signal_handlers_disconnect_by_func (element, timeline_element_parent_cb,
 289       root);
 290
 291   g_node_destroy (node);
 292   timeline_update_duration (root->data);
 293 }
 294
 295 /****************************************************
 296  *     GstClockTime with over/underflow checking    *
 297  ****************************************************/
 298
 299 static GstClockTime
 300 _clock_time_plus (GstClockTime time, GstClockTime add)
 301 {
 302   if (!GST_CLOCK_TIME_IS_VALID (time) || !GST_CLOCK_TIME_IS_VALID (add))
 303     return GST_CLOCK_TIME_NONE;
 304
 305   if (time >= (G_MAXUINT64 - add)) {
 306     GST_ERROR ("The time %" G_GUINT64_FORMAT " would overflow when "
 307         "adding %" G_GUINT64_FORMAT, time, add);
 308     return GST_CLOCK_TIME_NONE;
 309   }
 310   return time + add;
 311 }
 312
 313 static GstClockTime
 314 _clock_time_minus (GstClockTime time, GstClockTime minus, gboolean * negative)
 315 {
 316   if (negative)
 317     *negative = FALSE;
 318
 319   if (!GST_CLOCK_TIME_IS_VALID (time) || !GST_CLOCK_TIME_IS_VALID (minus))
 320     return GST_CLOCK_TIME_NONE;
 321
 322   if (time < minus) {
 323     if (negative) {
 324       *negative = TRUE;
 325       return minus - time;
 326     }
 327     /* otherwise don't allow negative */
 328     GST_INFO ("The time %" G_GUINT64_FORMAT " would underflow when "
 329         "subtracting %" G_GUINT64_FORMAT, time, minus);
 330     return GST_CLOCK_TIME_NONE;
 331   }
 332   return time - minus;
 333 }
 334
 335 static GstClockTime
 336 _clock_time_minus_diff (GstClockTime time, GstClockTimeDiff diff,
 337     gboolean * negative)
 338 {
 339   if (negative)
 340     *negative = FALSE;
 341
 342   if (!GST_CLOCK_TIME_IS_VALID (time))
 343     return GST_CLOCK_TIME_NONE;
 344
 345   if (diff < 0)
 346     return _clock_time_plus (time, -diff);
 347   else
 348     return _clock_time_minus (time, diff, negative);
 349 }
 350
 351 static GstClockTime
 352 _abs_clock_time_distance (GstClockTime time1, GstClockTime time2)
 353 {
 354   if (!GST_CLOCK_TIME_IS_VALID (time1) || !GST_CLOCK_TIME_IS_VALID (time2))
 355     return GST_CLOCK_TIME_NONE;
 356   if (time1 > time2)
 357     return time1 - time2;
 358   else
 359     return time2 - time1;
 360 }
 361
 362 static void
 363 get_start_end_from_offset (GESTimelineElement * element, ElementEditMode mode,
 364     GstClockTimeDiff offset, GstClockTime * start, gboolean * negative_start,
 365     GstClockTime * end, gboolean * negative_end)
 366 {
 367   GstClockTime current_end =
 368       _clock_time_plus (element->start, element->duration);
 369   GstClockTime new_start = GST_CLOCK_TIME_NONE, new_end = GST_CLOCK_TIME_NONE;
 370
 371   switch (mode) {
 372     case EDIT_MOVE:
 373       new_start =
 374           _clock_time_minus_diff (element->start, offset, negative_start);
 375       new_end = _clock_time_minus_diff (current_end, offset, negative_end);
 376       break;
 377     case EDIT_TRIM_START:
 378       new_start =
 379           _clock_time_minus_diff (element->start, offset, negative_start);
 380       new_end = current_end;
 381       if (negative_end)
 382         *negative_end = FALSE;
 383       break;
 384     case EDIT_TRIM_END:
 385       new_start = element->start;
 386       if (negative_start)
 387         *negative_start = FALSE;
 388       new_end = _clock_time_minus_diff (current_end, offset, negative_end);
 389       break;
 390     case EDIT_TRIM_INPOINT_ONLY:
 391       GST_ERROR_OBJECT (element, "Trim in-point only not handled");
 392       break;
 393   }
 394   if (start)
 395     *start = new_start;
 396   if (end)
 397     *end = new_end;
 398 }
 399
 400 /****************************************************
 401  *                   Snapping                       *
 402  ****************************************************/
 403
 404 static void
 405 snap_to_marker (GESTrackElement * element, GstClockTime position,
 406     gboolean negative, GstClockTime marker_timestamp,
 407     GESTrackElement * marker_parent, SnappedPosition * snap)
 408 {
 409   GstClockTime distance;
 410
 411   if (negative)
 412     distance = _clock_time_plus (position, marker_timestamp);
 413   else
 414     distance = _abs_clock_time_distance (position, marker_timestamp);
 415
 416   if (GST_CLOCK_TIME_IS_VALID (distance) && distance <= snap->distance) {
 417     snap->negative = negative;
 418     snap->position = position;
 419     snap->distance = distance;
 420     snap->snapped = marker_timestamp;
 421     snap->element = element;
 422     snap->snapped_to = marker_parent;
 423   }
 424 }
 425
 426 static void
 427 snap_to_edge (GESTrackElement * element, GstClockTime position,
 428     gboolean negative, GESTrackElement * snap_to, GESEdge edge,
 429     SnappedPosition * snap)
 430 {
 431   GstClockTime edge_pos = ELEMENT_EDGE_VALUE (snap_to, edge);
 432   GstClockTime distance;
 433
 434   if (negative)
 435     distance = _clock_time_plus (position, edge_pos);
 436   else
 437     distance = _abs_clock_time_distance (position, edge_pos);
 438
 439   if (GST_CLOCK_TIME_IS_VALID (distance) && distance <= snap->distance) {
 440     GESTimelineElement *parent = GES_TIMELINE_ELEMENT_PARENT (element);
 441     GESTimelineElement *snap_parent = GES_TIMELINE_ELEMENT_PARENT (snap_to);
 442     GST_LOG_OBJECT (element, "%s (under %s) snapped with %" GES_FORMAT
 443         "(under %s) from position %s%" GST_TIME_FORMAT " to %"
 444         GST_TIME_FORMAT, GES_TIMELINE_ELEMENT_NAME (element),
 445         parent ? parent->name : NULL, GES_ARGS (snap_to),
 446         snap_parent ? snap_parent->name : NULL, negative ? "-" : "",
 447         GST_TIME_ARGS (position), GST_TIME_ARGS (edge_pos));
 448     snap->negative = negative;
 449     snap->position = position;
 450     snap->distance = distance;
 451     snap->snapped = edge_pos;
 452     snap->element = element;
 453     snap->snapped_to = snap_to;
 454   }
 455 }
 456
 457 static void
 458 find_marker_snap (const GESMetaContainer * container, const gchar * key,
 459     const GValue * value, TreeIterationData * data)
 460 {
 461   GESTrackElement *marker_parent, *moving;
 462   GESClip *parent_clip;
 463   GstClockTime timestamp;
 464   GESMarkerList *marker_list;
 465   GESMarker *marker;
 466   GESMarkerFlags flags;
 467   GObject *obj;
 468
 469   if (!G_VALUE_HOLDS_OBJECT (value))
 470     return;
 471
 472   obj = g_value_get_object (value);
 473   if (!GES_IS_MARKER_LIST (obj))
 474     return;
 475
 476   marker_list = GES_MARKER_LIST (obj);
 477
 478   g_object_get (marker_list, "flags", &flags, NULL);
 479   if (!(flags & GES_MARKER_FLAG_SNAPPABLE))
 480     return;
 481
 482   marker_parent = GES_TRACK_ELEMENT ((gpointer) container);
 483   moving = GES_TRACK_ELEMENT (data->element);
 484   parent_clip = (GESClip *) GES_TIMELINE_ELEMENT_PARENT (marker_parent);
 485
 486   /* Translate current position into the target clip's time domain */
 487   timestamp =
 488       ges_clip_get_internal_time_from_timeline_time (parent_clip, marker_parent,
 489       data->position, NULL);
 490   marker = ges_marker_list_get_closest (marker_list, timestamp);
 491
 492   if (marker == NULL)
 493     return;
 494
 495   /* Make timestamp timeline-relative again */
 496   g_object_get (marker, "position", &timestamp, NULL);
 497   timestamp =
 498       ges_clip_get_timeline_time_from_internal_time (parent_clip, marker_parent,
 499       timestamp, NULL);
 500   snap_to_marker (moving, data->position, data->negative, timestamp,
 501       marker_parent, data->snap);
 502
 503   g_object_unref (marker);
 504 }
 505
 506 static gboolean
 507 find_snap (GNode * node, TreeIterationData * data)
 508 {
 509   GESTimelineElement *element = node->data;
 510   GESTrackElement *track_el, *moving;
 511
 512   /* Only snap to sources */
 513   /* Maybe we should allow snapping to anything that isn't an
 514    * auto-transition? */
 515   if (!GES_IS_SOURCE (element))
 516     return FALSE;
 517
 518   /* don't snap to anything we are moving */
 519   if (g_hash_table_contains (data->moving, element))
 520     return FALSE;
 521
 522   track_el = GES_TRACK_ELEMENT (element);
 523   moving = GES_TRACK_ELEMENT (data->element);
 524   snap_to_edge (moving, data->position, data->negative, track_el,
 525       GES_EDGE_END, data->snap);
 526   snap_to_edge (moving, data->position, data->negative, track_el,
 527       GES_EDGE_START, data->snap);
 528
 529   ges_meta_container_foreach (GES_META_CONTAINER (element),
 530       (GESMetaForeachFunc) find_marker_snap, data);
 531
 532   return FALSE;
 533 }
 534
 535 static void
 536 find_snap_for_element (GESTrackElement * element, GstClockTime position,
 537     gboolean negative, TreeIterationData * data)
 538 {
 539   data->element = GES_TIMELINE_ELEMENT (element);
 540   data->position = position;
 541   data->negative = negative;
 542   g_node_traverse (data->root, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
 543       (GNodeTraverseFunc) find_snap, data);
 544 }
 545
 546 /* find up to one source at the edge */
 547 static gboolean
 548 find_source_at_edge (GNode * node, TreeIterationData * data)
 549 {
 550   GESEdge edge = data->edge;
 551   GESTimelineElement *element = node->data;
 552   GESTimelineElement *ancestor = data->element;
 553
 554   if (!GES_IS_SOURCE (element))
 555     return FALSE;
 556
 557   if (ELEMENT_EDGE_VALUE (element, edge) == ELEMENT_EDGE_VALUE (ancestor, edge)) {
 558     data->sources = g_list_append (data->sources, element);
 559     return TRUE;
 560   }
 561   return FALSE;
 562 }
 563
 564 static gboolean
 565 find_sources (GNode * node, TreeIterationData * data)
 566 {
 567   GESTimelineElement *element = node->data;
 568   if (GES_IS_SOURCE (element))
 569     data->sources = g_list_append (data->sources, element);
 570   return FALSE;
 571 }
 572
 573 /* Tries to find a new snap to the start or end edge of one of the
 574  * descendant sources of @element, depending on @mode, and updates @offset
 575  * by the size of the jump.
 576  * Any elements in @moving are not snapped to.
 577  */
 578 static gboolean
 579 timeline_tree_snap (GNode * root, GESTimelineElement * element,
 580     ElementEditMode mode, GstClockTimeDiff * offset, GHashTable * moving,
 581     SnappedPosition * snap)
 582 {
 583   gboolean ret = FALSE;
 584   TreeIterationData data = tree_iteration_data_init;
 585   GList *tmp;
 586   GNode *node;
 587
 588   if (!snap)
 589     return TRUE;
 590
 591   /* get the sources we can snap to */
 592   data.root = root;
 593   data.moving = moving;
 594   data.sources = NULL;
 595   data.snap = snap;
 596   data.element = element;
 597
 598   node = find_node (root, element);
 599
 600   if (!node) {
 601     GST_ERROR_OBJECT (element, "Not being tracked");
 602     goto done;
 603   }
 604
 605   switch (mode) {
 606     case EDIT_MOVE:
 607       /* can snap with any source below the element, if any */
 608       g_node_traverse (node, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
 609           (GNodeTraverseFunc) find_sources, &data);
 610       break;
 611     case EDIT_TRIM_START:
 612       /* can only snap with sources at the start of the element.
 613        * only need one such source since all will share the same start.
 614        * if there is no source at the start edge, then snapping is not
 615        * possible */
 616       data.edge = GES_EDGE_START;
 617       g_node_traverse (node, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
 618           (GNodeTraverseFunc) find_source_at_edge, &data);
 619       break;
 620     case EDIT_TRIM_END:
 621       /* can only snap with sources at the end of the element.
 622        * only need one such source since all will share the same end.
 623        * if there is no source at the end edge, then snapping is not
 624        * possible */
 625       data.edge = GES_EDGE_END;
 626       g_node_traverse (node, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
 627           (GNodeTraverseFunc) find_source_at_edge, &data);
 628       break;
 629     case EDIT_TRIM_INPOINT_ONLY:
 630       GST_ERROR_OBJECT (element, "Trim in-point only not handled");
 631       goto done;
 632   }
 633
 634   for (tmp = data.sources; tmp; tmp = tmp->next) {
 635     GESTrackElement *source = tmp->data;
 636     GstClockTime end, start;
 637     gboolean negative_end, negative_start;
 638
 639     /* Allow negative start/end positions in case a snap makes them valid!
 640      * But we can still only snap to an existing edge in the timeline,
 641      * which should be a valid time */
 642     get_start_end_from_offset (GES_TIMELINE_ELEMENT (source), mode, *offset,
 643         &start, &negative_start, &end, &negative_end);
 644
 645     if (!GST_CLOCK_TIME_IS_VALID (start)) {
 646       GST_INFO_OBJECT (element, "Cannot edit element %" GES_FORMAT
 647           " with offset %" G_GINT64_FORMAT " because it would result in "
 648           "an invalid start", GES_ARGS (element), *offset);
 649       goto done;
 650     }
 651
 652     if (!GST_CLOCK_TIME_IS_VALID (end)) {
 653       GST_INFO_OBJECT (element, "Cannot edit element %" GES_FORMAT
 654           " with offset %" G_GINT64_FORMAT " because it would result in "
 655           "an invalid end", GES_ARGS (element), *offset);
 656       goto done;
 657     }
 658
 659     switch (mode) {
 660       case EDIT_MOVE:
 661         /* try snap start and end */
 662         find_snap_for_element (source, end, negative_end, &data);
 663         find_snap_for_element (source, start, negative_start, &data);
 664         break;
 665       case EDIT_TRIM_START:
 666         /* only snap the start of the source */
 667         find_snap_for_element (source, start, negative_start, &data);
 668         break;
 669       case EDIT_TRIM_END:
 670         /* only snap the start of the source */
 671         find_snap_for_element (source, end, negative_end, &data);
 672         break;
 673       case EDIT_TRIM_INPOINT_ONLY:
 674         GST_ERROR_OBJECT (element, "Trim in-point only not handled");
 675         goto done;
 676     }
 677   }
 678
 679   if (GST_CLOCK_TIME_IS_VALID (snap->snapped)) {
 680     if (snap->negative)
 681       *offset -= (snap->position + snap->snapped);
 682     else
 683       *offset += (snap->position - snap->snapped);
 684     GST_INFO_OBJECT (element, "Element %s under %s snapped with %" GES_FORMAT
 685         " from %s%" GST_TIME_FORMAT " to %" GST_TIME_FORMAT,
 686         GES_TIMELINE_ELEMENT_NAME (snap->element), element->name,
 687         GES_ARGS (snap->snapped_to), snap->negative ? "-" : "",
 688         GST_TIME_ARGS (snap->position), GST_TIME_ARGS (snap->snapped));
 689   } else {
 690     GST_INFO_OBJECT (element, "Nothing within snapping distance of %s",
 691         element->name);
 692   }
 693
 694   ret = TRUE;
 695
 696 done:
 697   g_list_free (data.sources);
 698
 699   return ret;
 700 }
 701
 702 /****************************************************
 703  *                 Check Overlaps                   *
 704  ****************************************************/
 705
 706 #define _SOURCE_FORMAT "\"%s\"%s%s%s"
 707 #define _SOURCE_ARGS(element) \
 708   element->name, element->parent ? " (parent: \"" : "", \
 709   element->parent ? element->parent->name : "", \
 710   element->parent ? "\")" : ""
 711
 712 static void
 713 set_full_overlap_error (GError ** error, GESTimelineElement * super,
 714     GESTimelineElement * sub, GESTrack * track)
 715 {
 716   if (error) {
 717     gchar *track_name = gst_object_get_name (GST_OBJECT (track));
 718     g_set_error (error, GES_ERROR, GES_ERROR_INVALID_OVERLAP_IN_TRACK,
 719         "The source " _SOURCE_FORMAT " would totally overlap the "
 720         "source " _SOURCE_FORMAT " in the track \"%s\"", _SOURCE_ARGS (super),
 721         _SOURCE_ARGS (sub), track_name);
 722     g_free (track_name);
 723   }
 724 }
 725
 726 static void
 727 set_triple_overlap_error (GError ** error, GESTimelineElement * first,
 728     GESTimelineElement * second, GESTimelineElement * third, GESTrack * track)
 729 {
 730   if (error) {
 731     gchar *track_name = gst_object_get_name (GST_OBJECT (track));
 732     g_set_error (error, GES_ERROR, GES_ERROR_INVALID_OVERLAP_IN_TRACK,
 733         "The sources " _SOURCE_FORMAT ", " _SOURCE_FORMAT " and "
 734         _SOURCE_FORMAT " would all overlap at the same point in the "
 735         "track \"%s\"", _SOURCE_ARGS (first), _SOURCE_ARGS (second),
 736         _SOURCE_ARGS (third), track_name);
 737     g_free (track_name);
 738   }
 739 }
 740
 741 #define _ELEMENT_FORMAT \
 742   "%s (under %s) [%" GST_TIME_FORMAT " - %" GST_TIME_FORMAT "] " \
 743   "(layer: %" G_GUINT32_FORMAT ") (track :%" GST_PTR_FORMAT ")"
 744 #define _E_ARGS e->name, e->parent ? e->parent->name : NULL, \
 745   GST_TIME_ARGS (start), GST_TIME_ARGS (end), layer_prio, track
 746 #define _CMP_ARGS cmp->name, cmp->parent ? cmp->parent->name : NULL, \
 747   GST_TIME_ARGS (cmp_start), GST_TIME_ARGS (cmp_end), cmp_layer_prio, \
 748   cmp_track
 749
 750 static gboolean
 751 check_overlap_with_element (GNode * node, TreeIterationData * data)
 752 {
 753   GESTimelineElement *e = node->data, *cmp = data->element;
 754   GstClockTime start, end, cmp_start, cmp_end;
 755   guint32 layer_prio, cmp_layer_prio;
 756   GESTrack *track, *cmp_track;
 757   PositionData *pos_data;
 758
 759   if (e == cmp)
 760     return FALSE;
 761
 762   if (!GES_IS_SOURCE (e) || !GES_IS_SOURCE (cmp))
 763     return FALSE;
 764
 765   /* get position of compared element */
 766   pos_data = data->pos_data;
 767   if (pos_data) {
 768     cmp_start = pos_data->start;
 769     cmp_end = pos_data->end;
 770     cmp_layer_prio = pos_data->layer_priority;
 771   } else {
 772     cmp_start = cmp->start;
 773     cmp_end = cmp_start + cmp->duration;
 774     cmp_layer_prio = ges_timeline_element_get_layer_priority (cmp);
 775   }
 776
 777   /* get position of the node */
 778   if (data->moving)
 779     pos_data = g_hash_table_lookup (data->moving, e);
 780   else
 781     pos_data = NULL;
 782
 783   if (pos_data) {
 784     start = pos_data->start;
 785     end = pos_data->end;
 786     layer_prio = pos_data->layer_priority;
 787   } else {
 788     start = e->start;
 789     end = start + e->duration;
 790     layer_prio = ges_timeline_element_get_layer_priority (e);
 791   }
 792
 793   track = ges_track_element_get_track (GES_TRACK_ELEMENT (e));
 794   cmp_track = ges_track_element_get_track (GES_TRACK_ELEMENT (cmp));
 795   GST_LOG ("Checking overlap between " _ELEMENT_FORMAT " and "
 796       _ELEMENT_FORMAT, _CMP_ARGS, _E_ARGS);
 797
 798   if (track != cmp_track || track == NULL || cmp_track == NULL) {
 799     GST_LOG (_ELEMENT_FORMAT " and " _ELEMENT_FORMAT " are not in the "
 800         "same track", _CMP_ARGS, _E_ARGS);
 801     return FALSE;
 802   }
 803
 804   if (layer_prio != cmp_layer_prio) {
 805     GST_LOG (_ELEMENT_FORMAT " and " _ELEMENT_FORMAT " are not in the "
 806         "same layer", _CMP_ARGS, _E_ARGS);
 807     return FALSE;
 808   }
 809
 810   if (start >= cmp_end || cmp_start >= end) {
 811     /* They do not overlap at all */
 812     GST_LOG (_ELEMENT_FORMAT " and " _ELEMENT_FORMAT " do not overlap",
 813         _CMP_ARGS, _E_ARGS);
 814     return FALSE;
 815   }
 816
 817   if (cmp_start <= start && cmp_end >= end) {
 818     /* cmp fully overlaps e */
 819     GST_INFO (_ELEMENT_FORMAT " and " _ELEMENT_FORMAT " fully overlap",
 820         _CMP_ARGS, _E_ARGS);
 821     set_full_overlap_error (data->error, cmp, e, track);
 822     goto error;
 823   }
 824
 825   if (cmp_start >= start && cmp_end <= end) {
 826     /* e fully overlaps cmp */
 827     GST_INFO (_ELEMENT_FORMAT " and " _ELEMENT_FORMAT " fully overlap",
 828         _CMP_ARGS, _E_ARGS);
 829     set_full_overlap_error (data->error, e, cmp, track);
 830     goto error;
 831   }
 832
 833   if (cmp_start < end && cmp_start > start) {
 834     /* cmp_start is between the start and end of the node */
 835     GST_LOG (_ELEMENT_FORMAT " is overlapped at its start by "
 836         _ELEMENT_FORMAT ". Overlap ends at %" GST_TIME_FORMAT,
 837         _CMP_ARGS, _E_ARGS, GST_TIME_ARGS (end));
 838     if (data->overlaping_on_start) {
 839       GST_INFO (_ELEMENT_FORMAT " is overlapped by %s and %s on its start",
 840           _CMP_ARGS, data->overlaping_on_start->name, e->name);
 841       set_triple_overlap_error (data->error, cmp, e, data->overlaping_on_start,
 842           track);
 843       goto error;
 844     }
 845     if (GST_CLOCK_TIME_IS_VALID (data->overlap_end_first_time) &&
 846         end > data->overlap_end_first_time) {
 847       GST_INFO (_ELEMENT_FORMAT " overlaps %s on its start and %s on its "
 848           "end, but they already overlap each other", _CMP_ARGS, e->name,
 849           data->overlaping_on_end->name);
 850       set_triple_overlap_error (data->error, cmp, e, data->overlaping_on_end,
 851           track);
 852       goto error;
 853     }
 854     /* record the time at which the overlapped ends */
 855     data->overlap_start_final_time = end;
 856     data->overlaping_on_start = e;
 857   }
 858
 859   if (cmp_end < end && cmp_end > start) {
 860     /* cmp_end is between the start and end of the node */
 861     GST_LOG (_ELEMENT_FORMAT " is overlapped at its end by "
 862         _ELEMENT_FORMAT ". Overlap starts at %" GST_TIME_FORMAT,
 863         _CMP_ARGS, _E_ARGS, GST_TIME_ARGS (start));
 864
 865     if (data->overlaping_on_end) {
 866       GST_INFO (_ELEMENT_FORMAT " is overlapped by %s and %s on its end",
 867           _CMP_ARGS, data->overlaping_on_end->name, e->name);
 868       set_triple_overlap_error (data->error, cmp, e, data->overlaping_on_end,
 869           track);
 870       goto error;
 871     }
 872     if (GST_CLOCK_TIME_IS_VALID (data->overlap_start_final_time) &&
 873         start < data->overlap_start_final_time) {
 874       GST_INFO (_ELEMENT_FORMAT " overlaps %s on its end and %s on its "
 875           "start, but they already overlap each other", _CMP_ARGS, e->name,
 876           data->overlaping_on_start->name);
 877       set_triple_overlap_error (data->error, cmp, e, data->overlaping_on_start,
 878           track);
 879       goto error;
 880     }
 881     /* record the time at which the overlapped starts */
 882     data->overlap_end_first_time = start;
 883     data->overlaping_on_end = e;
 884   }
 885
 886   return FALSE;
 887
 888 error:
 889   data->res = FALSE;
 890   return TRUE;
 891 }
 892
 893 /* check and find the overlaps with the element at node */
 894 static gboolean
 895 check_all_overlaps_with_element (GNode * node, TreeIterationData * data)
 896 {
 897   GESTimelineElement *element = node->data;
 898   if (GES_IS_SOURCE (element)) {
 899     data->element = element;
 900     data->overlaping_on_start = NULL;
 901     data->overlaping_on_end = NULL;
 902     data->overlap_start_final_time = GST_CLOCK_TIME_NONE;
 903     data->overlap_end_first_time = GST_CLOCK_TIME_NONE;
 904     if (data->moving)
 905       data->pos_data = g_hash_table_lookup (data->moving, element);
 906     else
 907       data->pos_data = NULL;
 908
 909     g_node_traverse (data->root, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
 910         (GNodeTraverseFunc) check_overlap_with_element, data);
 911
 912     return !data->res;
 913   }
 914   return FALSE;
 915 }
 916
 917 static gboolean
 918 check_moving_overlaps (GNode * node, TreeIterationData * data)
 919 {
 920   if (g_hash_table_contains (data->moving, node->data))
 921     return check_all_overlaps_with_element (node, data);
 922   return FALSE;
 923 }
 924
 925 /* whether the elements in moving can be moved to their corresponding
 926  * PositionData */
 927 static gboolean
 928 timeline_tree_can_move_elements (GNode * root, GHashTable * moving,
 929     GError ** error)
 930 {
 931   TreeIterationData data = tree_iteration_data_init;
 932   data.moving = moving;
 933   data.root = root;
 934   data.res = TRUE;
 935   data.error = error;
 936   /* sufficient to check the leaves, which is all the track elements or
 937    * empty clips
 938    * should also be sufficient to only check the moving elements */
 939   g_node_traverse (root, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
 940       (GNodeTraverseFunc) check_moving_overlaps, &data);
 941
 942   return data.res;
 943 }
 944
 945 /****************************************************
 946  *               Setting Edit Data                  *
 947  ****************************************************/
 948
 949 static void
 950 set_negative_start_error (GError ** error, GESTimelineElement * element,
 951     GstClockTime neg_start)
 952 {
 953   g_set_error (error, GES_ERROR, GES_ERROR_NEGATIVE_TIME,
 954       "The element \"%s\" would have a negative start of -%"
 955       GST_TIME_FORMAT, element->name, GST_TIME_ARGS (neg_start));
 956 }
 957
 958 static void
 959 set_negative_duration_error (GError ** error, GESTimelineElement * element,
 960     GstClockTime neg_duration)
 961 {
 962   g_set_error (error, GES_ERROR, GES_ERROR_NEGATIVE_TIME,
 963       "The element \"%s\" would have a negative duration of -%"
 964       GST_TIME_FORMAT, element->name, GST_TIME_ARGS (neg_duration));
 965 }
 966
 967 static void
 968 set_negative_inpoint_error (GError ** error, GESTimelineElement * element,
 969     GstClockTime neg_inpoint)
 970 {
 971   g_set_error (error, GES_ERROR, GES_ERROR_NEGATIVE_TIME,
 972       "The element \"%s\" would have a negative in-point of -%"
 973       GST_TIME_FORMAT, element->name, GST_TIME_ARGS (neg_inpoint));
 974 }
 975
 976 static void
 977 set_negative_layer_error (GError ** error, GESTimelineElement * element,
 978     gint64 neg_layer)
 979 {
 980   g_set_error (error, GES_ERROR, GES_ERROR_NEGATIVE_LAYER,
 981       "The element \"%s\" would have a negative layer priority of -%"
 982       G_GINT64_FORMAT, element->name, neg_layer);
 983 }
 984
 985 static void
 986 set_breaks_duration_limit_error (GError ** error, GESClip * clip,
 987     GstClockTime duration, GstClockTime duration_limit)
 988 {
 989   g_set_error (error, GES_ERROR, GES_ERROR_NOT_ENOUGH_INTERNAL_CONTENT,
 990       "The clip \"%s\" would have a duration of %" GST_TIME_FORMAT
 991       " that would break its duration-limit of %" GST_TIME_FORMAT,
 992       GES_TIMELINE_ELEMENT_NAME (clip), GST_TIME_ARGS (duration),
 993       GST_TIME_ARGS (duration_limit));
 994 }
 995
 996 static void
 997 set_inpoint_breaks_max_duration_error (GError ** error,
 998     GESTimelineElement * element, GstClockTime inpoint,
 999     GstClockTime max_duration)
1000 {
1001   g_set_error (error, GES_ERROR, GES_ERROR_NOT_ENOUGH_INTERNAL_CONTENT,
1002       "The element \"%s\" would have an in-point of %" GST_TIME_FORMAT
1003       " that would break its max-duration of %" GST_TIME_FORMAT,
1004       GES_TIMELINE_ELEMENT_NAME (element), GST_TIME_ARGS (inpoint),
1005       GST_TIME_ARGS (max_duration));
1006 }
1007
1008 static gboolean
1009 set_layer_priority (GESTimelineElement * element, EditData * data,
1010     GError ** error)
1011 {
1012   gint64 layer_offset = data->layer_offset;
1013   guint32 layer_prio = ges_timeline_element_get_layer_priority (element);
1014
1015   if (!layer_offset)
1016     return TRUE;
1017
1018   if (layer_prio == GES_TIMELINE_ELEMENT_NO_LAYER_PRIORITY) {
1019     GST_INFO_OBJECT (element, "Cannot shift %s to a new layer because it "
1020         "has no layer priority", element->name);
1021     return FALSE;
1022   }
1023
1024   if (layer_offset > (gint64) layer_prio) {
1025     GST_INFO_OBJECT (element, "%s would have a negative layer priority (%"
1026         G_GUINT32_FORMAT " - %" G_GINT64_FORMAT ")", element->name,
1027         layer_prio, layer_offset);
1028     set_negative_layer_error (error, element,
1029         layer_offset - (gint64) layer_prio);
1030     return FALSE;
1031   }
1032   if ((layer_prio - (gint64) layer_offset) >= G_MAXUINT32) {
1033     GST_ERROR_OBJECT (element, "%s would have an overflowing layer priority",
1034         element->name);
1035     return FALSE;
1036   }
1037
1038   data->layer_priority = (guint32) (layer_prio - (gint64) layer_offset);
1039
1040   if (ges_timeline_layer_priority_in_gap (element->timeline,
1041           data->layer_priority)) {
1042     GST_ERROR_OBJECT (element, "Edit layer %" G_GUINT32_FORMAT " would "
1043         "be within a gap in the timeline layers", data->layer_priority);
1044     return FALSE;
1045   }
1046
1047   GST_INFO_OBJECT (element, "%s will move to layer %" G_GUINT32_FORMAT,
1048       element->name, data->layer_priority);
1049
1050   return TRUE;
1051 }
1052
1053 #define _CHECK_END(element, start, duration) \
1054   if (!GST_CLOCK_TIME_IS_VALID (_clock_time_plus (start, duration))) { \
1055     GST_INFO_OBJECT (element, "Cannot edit %s because it would result in " \
1056         "an invalid end", element->name); \
1057     return FALSE; \
1058   }
1059
1060 static gboolean
1061 set_edit_move_values (GESTimelineElement * element, EditData * data,
1062     GError ** error)
1063 {
1064   gboolean negative = FALSE;
1065   GstClockTime new_start =
1066       _clock_time_minus_diff (element->start, data->offset, &negative);
1067   if (negative || !GST_CLOCK_TIME_IS_VALID (new_start)) {
1068     GST_INFO_OBJECT (element, "Cannot move %" GES_FORMAT " with offset %"
1069         G_GINT64_FORMAT " because it would result in an invalid start",
1070         GES_ARGS (element), data->offset);
1071     if (negative)
1072       set_negative_start_error (error, element, new_start);
1073     return FALSE;
1074   }
1075   _CHECK_END (element, new_start, element->duration);
1076   data->start = new_start;
1077
1078   if (GES_IS_GROUP (element))
1079     return TRUE;
1080
1081   GST_INFO_OBJECT (element, "%s will move by setting start to %"
1082       GST_TIME_FORMAT, element->name, GST_TIME_ARGS (data->start));
1083
1084   return set_layer_priority (element, data, error);
1085 }
1086
1087 static gboolean
1088 set_edit_trim_start_clip_inpoints (GESClip * clip, EditData * clip_data,
1089     GHashTable * edit_table, GError ** error)
1090 {
1091   gboolean ret = FALSE;
1092   GList *tmp;
1093   GstClockTime duration_limit;
1094   GstClockTime clip_inpoint;
1095   GstClockTime new_start = clip_data->start;
1096   gboolean no_core = FALSE;
1097   GHashTable *child_inpoints;
1098
1099   child_inpoints = g_hash_table_new_full (NULL, NULL, gst_object_unref, g_free);
1100
1101   clip_inpoint = ges_clip_get_core_internal_time_from_timeline_time (clip,
1102       new_start, &no_core, error);
1103
1104   if (no_core) {
1105     GST_INFO_OBJECT (clip, "Clip %" GES_FORMAT " has no active core "
1106         "children with an internal source. Not setting in-point during "
1107         "trim to start", GES_ARGS (clip));
1108     clip_inpoint = GES_TIMELINE_ELEMENT_INPOINT (clip);
1109   } else if (!GST_CLOCK_TIME_IS_VALID (clip_inpoint)) {
1110     GST_INFO_OBJECT (clip, "Cannot trim start of %" GES_FORMAT
1111         " with offset %" G_GINT64_FORMAT " because it would result in an "
1112         "invalid in-point for its core children", GES_ARGS (clip),
1113         clip_data->offset);
1114     goto done;
1115   } else {
1116     GST_INFO_OBJECT (clip, "Clip %" GES_FORMAT " will have its in-point "
1117         " set to %" GST_TIME_FORMAT " because its start is being trimmed "
1118         "to %" GST_TIME_FORMAT, GES_ARGS (clip),
1119         GST_TIME_ARGS (clip_inpoint), GST_TIME_ARGS (new_start));
1120     clip_data->inpoint = clip_inpoint;
1121   }
1122
1123   /* need to set in-point of active non-core children to keep their
1124    * internal content at the same timeline position */
1125   for (tmp = GES_CONTAINER_CHILDREN (clip); tmp; tmp = tmp->next) {
1126     GESTimelineElement *child = tmp->data;
1127     GESTrackElement *el = tmp->data;
1128     GstClockTime new_inpoint = child->inpoint;
1129     GstClockTime *inpoint_p;
1130
1131     if (ges_track_element_has_internal_source (el)) {
1132       if (ges_track_element_is_core (el)) {
1133         new_inpoint = clip_inpoint;
1134       } else if (ges_track_element_is_active (el)) {
1135         EditData *data;
1136
1137         if (g_hash_table_contains (edit_table, child)) {
1138           GST_ERROR_OBJECT (child, "Already set to be edited");
1139           goto done;
1140         }
1141
1142         new_inpoint = ges_clip_get_internal_time_from_timeline_time (clip, el,
1143             new_start, error);
1144
1145         if (!GST_CLOCK_TIME_IS_VALID (new_inpoint)) {
1146           GST_INFO_OBJECT (clip, "Cannot trim start of %" GES_FORMAT
1147               " to %" GST_TIME_FORMAT " because it would result in an "
1148               "invalid in-point for the non-core child %" GES_FORMAT,
1149               GES_ARGS (clip), GST_TIME_ARGS (new_start), GES_ARGS (child));
1150           goto done;
1151         }
1152
1153         GST_INFO_OBJECT (child, "Setting track element %s to trim "
1154             "in-point to %" GST_TIME_FORMAT " since the parent clip %"
1155             GES_FORMAT " is being trimmed to start %" GST_TIME_FORMAT,
1156             child->name, GST_TIME_ARGS (new_inpoint), GES_ARGS (clip),
1157             GST_TIME_ARGS (new_start));
1158
1159         data = new_edit_data (EDIT_TRIM_INPOINT_ONLY, 0, 0);
1160         data->inpoint = new_inpoint;
1161         g_hash_table_insert (edit_table, child, data);
1162       }
1163     }
1164
1165     if (GES_CLOCK_TIME_IS_LESS (child->maxduration, new_inpoint)) {
1166       GST_INFO_OBJECT (clip, "Cannot trim start of %" GES_FORMAT
1167           " to %" GST_TIME_FORMAT " because it would result in an "
1168           "in-point of %" GST_TIME_FORMAT " for the child %" GES_FORMAT
1169           ", which breaks its max-duration", GES_ARGS (clip),
1170           GST_TIME_ARGS (new_start), GST_TIME_ARGS (new_inpoint),
1171           GES_ARGS (child));
1172
1173       set_inpoint_breaks_max_duration_error (error, child, new_inpoint,
1174           child->maxduration);
1175       goto done;
1176     }
1177
1178     inpoint_p = g_new (GstClockTime, 1);
1179     *inpoint_p = new_inpoint;
1180     g_hash_table_insert (child_inpoints, gst_object_ref (child), inpoint_p);
1181   }
1182
1183   duration_limit =
1184       ges_clip_duration_limit_with_new_children_inpoints (clip, child_inpoints);
1185
1186   if (GES_CLOCK_TIME_IS_LESS (duration_limit, clip_data->duration)) {
1187     GST_INFO_OBJECT (clip, "Cannot trim start of %" GES_FORMAT
1188         " to %" GST_TIME_FORMAT " because it would result in a "
1189         "duration of %" GST_TIME_FORMAT " that breaks its new "
1190         "duration-limit of %" GST_TIME_FORMAT, GES_ARGS (clip),
1191         GST_TIME_ARGS (new_start), GST_TIME_ARGS (clip_data->duration),
1192         GST_TIME_ARGS (duration_limit));
1193
1194     set_breaks_duration_limit_error (error, clip, clip_data->duration,
1195         duration_limit);
1196     goto done;
1197   }
1198
1199   ret = TRUE;
1200
1201 done:
1202   g_hash_table_unref (child_inpoints);
1203
1204   return ret;
1205 }
1206
1207 /* trim the start of a clip or a track element */
1208 static gboolean
1209 set_edit_trim_start_values (GESTimelineElement * element, EditData * data,
1210     GHashTable * edit_table, GError ** error)
1211 {
1212   gboolean negative = FALSE;
1213   GstClockTime new_duration;
1214   GstClockTime new_start =
1215       _clock_time_minus_diff (element->start, data->offset, &negative);
1216
1217   if (negative || !GST_CLOCK_TIME_IS_VALID (new_start)) {
1218     GST_INFO_OBJECT (element, "Cannot trim start of %" GES_FORMAT
1219         " with offset %" G_GINT64_FORMAT " because it would result in an "
1220         "invalid start", GES_ARGS (element), data->offset);
1221     if (negative)
1222       set_negative_start_error (error, element, new_start);
1223     return FALSE;
1224   }
1225
1226   new_duration =
1227       _clock_time_minus_diff (element->duration, -data->offset, &negative);
1228
1229   if (negative || !GST_CLOCK_TIME_IS_VALID (new_duration)) {
1230     GST_INFO_OBJECT (element, "Cannot trim start of %" GES_FORMAT
1231         " with offset %" G_GINT64_FORMAT " because it would result in an "
1232         "invalid duration", GES_ARGS (element), data->offset);
1233     if (negative)
1234       set_negative_duration_error (error, element, new_duration);
1235     return FALSE;
1236   }
1237   _CHECK_END (element, new_start, new_duration);
1238
1239   data->start = new_start;
1240   data->duration = new_duration;
1241
1242   if (GES_IS_GROUP (element))
1243     return TRUE;
1244
1245   if (GES_IS_CLIP (element)) {
1246     if (!set_edit_trim_start_clip_inpoints (GES_CLIP (element), data,
1247             edit_table, error))
1248       return FALSE;
1249   } else if (GES_IS_TRACK_ELEMENT (element)
1250       && ges_track_element_has_internal_source (GES_TRACK_ELEMENT (element))) {
1251     GstClockTime new_inpoint =
1252         _clock_time_minus_diff (element->inpoint, data->offset, &negative);
1253
1254     if (negative || !GST_CLOCK_TIME_IS_VALID (new_inpoint)) {
1255       GST_INFO_OBJECT (element, "Cannot trim start of %" GES_FORMAT
1256           " with offset %" G_GINT64_FORMAT " because it would result in "
1257           "an invalid in-point", GES_ARGS (element), data->offset);
1258       if (negative)
1259         set_negative_inpoint_error (error, element, new_inpoint);
1260       return FALSE;
1261     }
1262   }
1263
1264   GST_INFO_OBJECT (element, "%s will trim start by setting start to %"
1265       GST_TIME_FORMAT ", in-point to %" GST_TIME_FORMAT " and duration "
1266       "to %" GST_TIME_FORMAT, element->name, GST_TIME_ARGS (data->start),
1267       GST_TIME_ARGS (data->inpoint), GST_TIME_ARGS (data->duration));
1268
1269   return set_layer_priority (element, data, error);
1270 }
1271
1272 /* trim the end of a clip or a track element */
1273 static gboolean
1274 set_edit_trim_end_values (GESTimelineElement * element, EditData * data,
1275     GError ** error)
1276 {
1277   gboolean negative = FALSE;
1278   GstClockTime new_duration =
1279       _clock_time_minus_diff (element->duration, data->offset, &negative);
1280   if (negative || !GST_CLOCK_TIME_IS_VALID (new_duration)) {
1281     GST_INFO_OBJECT (element, "Cannot trim end of %" GES_FORMAT
1282         " with offset %" G_GINT64_FORMAT " because it would result in an "
1283         "invalid duration", GES_ARGS (element), data->offset);
1284     if (negative)
1285       set_negative_duration_error (error, element, new_duration);
1286     return FALSE;
1287   }
1288   _CHECK_END (element, element->start, new_duration);
1289
1290   if (GES_IS_CLIP (element)) {
1291     GESClip *clip = GES_CLIP (element);
1292     GstClockTime limit = ges_clip_get_duration_limit (clip);
1293
1294     if (GES_CLOCK_TIME_IS_LESS (limit, new_duration)) {
1295       GST_INFO_OBJECT (element, "Cannot trim end of %" GES_FORMAT
1296           " with offset %" G_GINT64_FORMAT " because the duration would "
1297           "exceed the clip's duration-limit %" G_GINT64_FORMAT,
1298           GES_ARGS (element), data->offset, limit);
1299
1300       set_breaks_duration_limit_error (error, clip, new_duration, limit);
1301       return FALSE;
1302     }
1303   }
1304
1305   data->duration = new_duration;
1306
1307   if (GES_IS_GROUP (element))
1308     return TRUE;
1309
1310   GST_INFO_OBJECT (element, "%s will trim end by setting duration to %"
1311       GST_TIME_FORMAT, element->name, GST_TIME_ARGS (data->duration));
1312
1313   return set_layer_priority (element, data, error);
1314 }
1315
1316 static gboolean
1317 set_edit_values (GESTimelineElement * element, EditData * data,
1318     GHashTable * edit_table, GError ** error)
1319 {
1320   switch (data->mode) {
1321     case EDIT_MOVE:
1322       return set_edit_move_values (element, data, error);
1323     case EDIT_TRIM_START:
1324       return set_edit_trim_start_values (element, data, edit_table, error);
1325     case EDIT_TRIM_END:
1326       return set_edit_trim_end_values (element, data, error);
1327     case EDIT_TRIM_INPOINT_ONLY:
1328       GST_ERROR_OBJECT (element, "Trim in-point only not handled");
1329       return FALSE;
1330   }
1331   return FALSE;
1332 }
1333
1334 static gboolean
1335 add_clips_to_list (GNode * node, GList ** list)
1336 {
1337   GESTimelineElement *element = node->data;
1338   GESTimelineElement *clip = NULL;
1339
1340   if (GES_IS_CLIP (element))
1341     clip = element;
1342   else if (GES_IS_CLIP (element->parent))
1343     clip = element->parent;
1344
1345   if (clip && !g_list_find (*list, clip))
1346     *list = g_list_append (*list, clip);
1347
1348   return FALSE;
1349 }
1350
1351 static gboolean
1352 replace_group_with_clip_edits (GNode * root, GESTimelineElement * group,
1353     GHashTable * edit_table, GError ** err)
1354 {
1355   gboolean ret = TRUE;
1356   GList *tmp, *clips = NULL;
1357   GNode *node = find_node (root, group);
1358   GstClockTime new_end, new_start;
1359   ElementEditMode mode;
1360   gint64 layer_offset;
1361
1362   if (!node) {
1363     GST_ERROR_OBJECT (group, "Not being tracked");
1364     goto error;
1365   }
1366
1367   /* new context for the lifespan of group_data */
1368   {
1369     EditData *group_edit = g_hash_table_lookup (edit_table, group);
1370
1371     if (!group_edit) {
1372       GST_ERROR_OBJECT (group, "Edit data for group was missing");
1373       goto error;
1374     }
1375
1376     group_edit->start = group->start;
1377     group_edit->duration = group->duration;
1378
1379     /* should only set the start and duration fields, table should not be
1380      * needed, so we pass NULL */
1381     if (!set_edit_values (group, group_edit, NULL, err))
1382       goto error;
1383
1384     new_start = group_edit->start;
1385     new_end = _clock_time_plus (group_edit->start, group_edit->duration);
1386
1387     if (!GST_CLOCK_TIME_IS_VALID (new_start)
1388         || !GST_CLOCK_TIME_IS_VALID (new_end)) {
1389       GST_ERROR_OBJECT (group, "Edit data gave an invalid start or end");
1390       goto error;
1391     }
1392
1393     layer_offset = group_edit->layer_offset;
1394     mode = group_edit->mode;
1395
1396     /* can traverse leaves to find all the clips since they are at _most_
1397      * one step above the track elements */
1398     g_node_traverse (node, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
1399         (GNodeTraverseFunc) add_clips_to_list, &clips);
1400
1401     if (!clips) {
1402       GST_INFO_OBJECT (group, "Contains no clips, so cannot be edited");
1403       goto error;
1404     }
1405
1406     if (!g_hash_table_remove (edit_table, group)) {
1407       GST_ERROR_OBJECT (group, "Could not replace the group in the edit list");
1408       goto error;
1409     }
1410     /* removing the group from the table frees group_edit */
1411   }
1412
1413   for (tmp = clips; tmp; tmp = tmp->next) {
1414     GESTimelineElement *clip = tmp->data;
1415     gboolean edit = FALSE;
1416     GstClockTimeDiff offset = G_MAXINT64;
1417     ElementEditMode clip_mode = mode;
1418
1419     /* if at the edge of the group and being trimmed forward or backward */
1420     if (mode == EDIT_MOVE) {
1421       /* same offset as the group */
1422       edit = TRUE;
1423       offset = group->start - new_start;
1424
1425       GST_INFO_OBJECT (clip, "Setting clip %s to moving with offset %"
1426           G_GINT64_FORMAT " since an ancestor group %" GES_FORMAT
1427           " is moving to %" GST_TIME_FORMAT, clip->name, offset,
1428           GES_ARGS (group), GST_TIME_ARGS (new_start));
1429
1430     } else if ((mode == EDIT_TRIM_START)
1431         && (clip->start <= new_start || clip->start == group->start)) {
1432       /* trim to same start */
1433       edit = TRUE;
1434       offset = clip->start - new_start;
1435
1436       GST_INFO_OBJECT (clip, "Setting clip %s to trim start with offset %"
1437           G_GINT64_FORMAT " since an ancestor group %" GES_FORMAT " is "
1438           "being trimmed to start %" GST_TIME_FORMAT, clip->name, offset,
1439           GES_ARGS (group), GST_TIME_ARGS (new_start));
1440
1441     } else if (mode == EDIT_TRIM_END
1442         && (_END (clip) >= new_end || _END (clip) == _END (group))) {
1443       /* trim to same end */
1444       edit = TRUE;
1445       offset = _END (clip) - new_end;
1446
1447       GST_INFO_OBJECT (clip, "Setting clip %s to trim end with offset %"
1448           G_GINT64_FORMAT " since an ancestor group %" GES_FORMAT " is "
1449           "being trimmed to end %" GST_TIME_FORMAT, clip->name, offset,
1450           GES_ARGS (group), GST_TIME_ARGS (new_end));
1451
1452     } else if (layer_offset) {
1453       /* still need to move layer */
1454       edit = TRUE;
1455       clip_mode = EDIT_MOVE;
1456       offset = 0;
1457     }
1458     if (edit) {
1459       EditData *clip_data;
1460
1461       if (layer_offset)
1462         GST_INFO_OBJECT (clip, "Setting clip %s to move to new layer with "
1463             "offset %" G_GINT64_FORMAT " since an ancestor group %"
1464             GES_FORMAT " is being moved with the same offset", clip->name,
1465             layer_offset, GES_ARGS (group));
1466
1467       if (g_hash_table_contains (edit_table, clip)) {
1468         GST_ERROR_OBJECT (clip, "Already set to be edited");
1469         goto error;
1470       }
1471       clip_data = new_edit_data (clip_mode, offset, layer_offset);
1472       g_hash_table_insert (edit_table, clip, clip_data);
1473       if (!set_edit_values (clip, clip_data, edit_table, err))
1474         goto error;
1475     }
1476   }
1477
1478 done:
1479   g_list_free (clips);
1480   return ret;
1481
1482 error:
1483   ret = FALSE;
1484   goto done;
1485 }
1486
1487 /* set the edit values for the entries in @edits
1488  * any groups in @edits will be replaced by their clip children */
1489 static gboolean
1490 timeline_tree_set_element_edit_values (GNode * root, GHashTable * edits,
1491     GError ** err)
1492 {
1493   gboolean ret = TRUE;
1494   GESTimelineElement *element;
1495   EditData *edit_data;
1496   /* content of edit table may change when group edits are replaced by
1497    * clip edits and clip edits introduce edits for non-core children */
1498   GList *tmp, *elements = g_hash_table_get_keys (edits);
1499
1500   for (tmp = elements; tmp; tmp = tmp->next) {
1501     gboolean res;
1502     element = tmp->data;
1503     edit_data = g_hash_table_lookup (edits, element);
1504     if (!edit_data) {
1505       GST_ERROR_OBJECT (element, "No edit data for the element");
1506       goto error;
1507     }
1508     if (GES_IS_GROUP (element))
1509       res = replace_group_with_clip_edits (root, element, edits, err);
1510     else
1511       res = set_edit_values (element, edit_data, edits, err);
1512     if (!res)
1513       goto error;
1514   }
1515
1516 done:
1517   g_list_free (elements);
1518
1519   return ret;
1520
1521 error:
1522   ret = FALSE;
1523   goto done;
1524 }
1525
1526 /* set the moving PositionData by using their parent clips.
1527  * @edit_table should already have had its values set, and any group edits
1528  * replaced by clip edits. */
1529 static void
1530 set_moving_positions_from_edits (GHashTable * moving, GHashTable * edit_table)
1531 {
1532   GHashTableIter iter;
1533   gpointer key, value;
1534
1535   g_hash_table_iter_init (&iter, moving);
1536   while (g_hash_table_iter_next (&iter, &key, &value)) {
1537     GESTimelineElement *element = key;
1538     PositionData *pos = value;
1539     GESTimelineElement *parent;
1540     EditData *edit;
1541
1542     /* a track element will end up with the same start and end as its clip */
1543     /* if no parent, act as own parent */
1544     parent = element->parent ? element->parent : element;
1545     edit = g_hash_table_lookup (edit_table, parent);
1546
1547     if (edit && GST_CLOCK_TIME_IS_VALID (edit->start))
1548       pos->start = edit->start;
1549     else
1550       pos->start = element->start;
1551
1552     if (edit && GST_CLOCK_TIME_IS_VALID (edit->duration))
1553       pos->end = pos->start + edit->duration;
1554     else
1555       pos->end = pos->start + element->duration;
1556
1557     if (edit && edit->layer_priority != GES_TIMELINE_ELEMENT_NO_LAYER_PRIORITY)
1558       pos->layer_priority = edit->layer_priority;
1559     else
1560       pos->layer_priority = ges_timeline_element_get_layer_priority (element);
1561   }
1562 }
1563
1564 static void
1565 give_edits_same_offset (GHashTable * edits, GstClockTimeDiff offset,
1566     gint64 layer_offset)
1567 {
1568   GHashTableIter iter;
1569   gpointer value;
1570
1571   g_hash_table_iter_init (&iter, edits);
1572   while (g_hash_table_iter_next (&iter, NULL, &value)) {
1573     EditData *edit_data = value;
1574     edit_data->offset = offset;
1575     edit_data->layer_offset = layer_offset;
1576   }
1577 }
1578
1579 /****************************************************
1580  *         Initialise Edit Data and Moving          *
1581  ****************************************************/
1582
1583 static gboolean
1584 add_track_elements_to_moving (GNode * node, GHashTable * track_elements)
1585 {
1586   GESTimelineElement *element = node->data;
1587   if (GES_IS_TRACK_ELEMENT (element)) {
1588     GST_LOG_OBJECT (element, "%s set as moving", element->name);
1589     g_hash_table_insert (track_elements, element, g_new0 (PositionData, 1));
1590   }
1591   return FALSE;
1592 }
1593
1594 /* add all the track elements found under the elements in @edits to @moving,
1595  * but does not set their position data */
1596 static gboolean
1597 timeline_tree_add_edited_to_moving (GNode * root, GHashTable * edits,
1598     GHashTable * moving)
1599 {
1600   GHashTableIter iter;
1601   gpointer key;
1602
1603   g_hash_table_iter_init (&iter, edits);
1604   while (g_hash_table_iter_next (&iter, &key, NULL)) {
1605     GESTimelineElement *element = key;
1606     GNode *node = find_node (root, element);
1607     if (!node) {
1608       GST_ERROR_OBJECT (element, "Not being tracked");
1609       return FALSE;
1610     }
1611     g_node_traverse (node, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
1612         (GNodeTraverseFunc) add_track_elements_to_moving, moving);
1613   }
1614
1615   return TRUE;
1616 }
1617
1618 /* check we can handle the top and all of its children */
1619 static gboolean
1620 check_types (GESTimelineElement * element, gboolean is_top)
1621 {
1622   if (!GES_IS_CLIP (element) && !GES_IS_GROUP (element)
1623       && !GES_IS_TRACK_ELEMENT (element)) {
1624     GST_ERROR_OBJECT (element, "Cannot handle a GESTimelineElement of the "
1625         "type %s", G_OBJECT_TYPE_NAME (element));
1626     return FALSE;
1627   }
1628   if (!is_top && element->parent) {
1629     if ((GES_IS_CLIP (element) && !GES_IS_GROUP (element->parent))
1630         || (GES_IS_GROUP (element) && !GES_IS_GROUP (element->parent))
1631         || (GES_IS_TRACK_ELEMENT (element) && !GES_IS_CLIP (element->parent))) {
1632       GST_ERROR_OBJECT (element, "A parent of type %s is not handled",
1633           G_OBJECT_TYPE_NAME (element->parent));
1634       return FALSE;
1635     }
1636   }
1637   if (GES_IS_CONTAINER (element)) {
1638     GList *tmp;
1639     for (tmp = GES_CONTAINER_CHILDREN (element); tmp; tmp = tmp->next) {
1640       if (!check_types (tmp->data, FALSE))
1641         return FALSE;
1642     }
1643   }
1644
1645   return TRUE;
1646 }
1647
1648 /* @edits: The table to add the edit to
1649  * @element: The element to edit
1650  * @mode: The mode for editing @element
1651  *
1652  * Adds an edit for @element it to the table with its EditData only set
1653  * with @mode.
1654  *
1655  * The offsets for the edit will have to be set later.
1656  */
1657 static gboolean
1658 add_element_edit (GHashTable * edits, GESTimelineElement * element,
1659     ElementEditMode mode)
1660 {
1661   if (!check_types (element, TRUE))
1662     return FALSE;
1663
1664   if (g_hash_table_contains (edits, element)) {
1665     GST_ERROR_OBJECT (element, "Already set to be edited");
1666     return FALSE;
1667   }
1668
1669   switch (mode) {
1670     case EDIT_MOVE:
1671       GST_LOG_OBJECT (element, "%s set to move", element->name);
1672       break;
1673     case EDIT_TRIM_START:
1674       GST_LOG_OBJECT (element, "%s set to trim start", element->name);
1675       break;
1676     case EDIT_TRIM_END:
1677       GST_LOG_OBJECT (element, "%s set to trim end", element->name);
1678       break;
1679     case EDIT_TRIM_INPOINT_ONLY:
1680       GST_ERROR_OBJECT (element, "%s set to trim in-point only", element->name);
1681       return FALSE;
1682   }
1683
1684   g_hash_table_insert (edits, element, new_edit_data (mode, 0, 0));
1685
1686   return TRUE;
1687 }
1688
1689 /********************************************
1690  *   Check against current configuration    *
1691  ********************************************/
1692
1693 /* can move with no snapping or change in parent! */
1694 gboolean
1695 timeline_tree_can_move_element (GNode * root,
1696     GESTimelineElement * element, guint32 priority, GstClockTime start,
1697     GstClockTime duration, GError ** error)
1698 {
1699   gboolean ret = FALSE;
1700   guint32 layer_prio = ges_timeline_element_get_layer_priority (element);
1701   GstClockTime distance, new_end;
1702   GHashTable *move_edits, *trim_edits, *moving;
1703   GHashTableIter iter;
1704   gpointer key, value;
1705
1706   if (layer_prio == GES_TIMELINE_ELEMENT_NO_LAYER_PRIORITY
1707       && priority != layer_prio) {
1708     GST_INFO_OBJECT (element, "Cannot move to a layer when no layer "
1709         "priority to begin with");
1710     return FALSE;
1711   }
1712
1713   distance = _abs_clock_time_distance (start, element->start);
1714   if ((GstClockTimeDiff) distance >= G_MAXINT64) {
1715     GST_WARNING_OBJECT (element, "Move in start from %" GST_TIME_FORMAT
1716         " to %" GST_TIME_FORMAT " is too large to perform",
1717         GST_TIME_ARGS (element->start), GST_TIME_ARGS (start));
1718     return FALSE;
1719   }
1720
1721   distance = _abs_clock_time_distance (duration, element->duration);
1722   if ((GstClockTimeDiff) distance >= G_MAXINT64) {
1723     GST_WARNING_OBJECT (element, "Move in duration from %" GST_TIME_FORMAT
1724         " to %" GST_TIME_FORMAT " is too large to perform",
1725         GST_TIME_ARGS (element->duration), GST_TIME_ARGS (duration));
1726     return FALSE;
1727   }
1728
1729   new_end = _clock_time_plus (start, duration);
1730   if (!GST_CLOCK_TIME_IS_VALID (new_end)) {
1731     GST_WARNING_OBJECT (element, "Move in start and duration to %"
1732         GST_TIME_FORMAT " and %" GST_TIME_FORMAT " would produce an "
1733         "invalid end", GST_TIME_ARGS (start), GST_TIME_ARGS (duration));
1734     return FALSE;
1735   }
1736
1737   /* treat as an EDIT_MOVE to the new priority, except on the element
1738    * rather than the toplevel, followed by an EDIT_TRIM_END */
1739   move_edits = new_edit_table ();
1740   trim_edits = new_edit_table ();
1741   moving = new_position_table ();
1742
1743   if (!add_element_edit (move_edits, element, EDIT_MOVE))
1744     goto done;
1745   /* moving should remain the same */
1746   if (!add_element_edit (trim_edits, element, EDIT_TRIM_END))
1747     goto done;
1748
1749   if (!timeline_tree_add_edited_to_moving (root, move_edits, moving)
1750       || !timeline_tree_add_edited_to_moving (root, trim_edits, moving))
1751     goto done;
1752
1753   /* no snapping */
1754   give_edits_same_offset (move_edits, element->start - start,
1755       (gint64) layer_prio - (gint64) priority);
1756   give_edits_same_offset (trim_edits, element->duration - duration, 0);
1757
1758   /* assume both edits can be performed if each could occur individually */
1759   /* should not effect duration or in-point */
1760   if (!timeline_tree_set_element_edit_values (root, move_edits, error))
1761     goto done;
1762   /* should not effect start or in-point or layer */
1763   if (!timeline_tree_set_element_edit_values (root, trim_edits, error))
1764     goto done;
1765
1766   /* merge the two edits into moving positions */
1767   g_hash_table_iter_init (&iter, moving);
1768   while (g_hash_table_iter_next (&iter, &key, &value)) {
1769     GESTimelineElement *el = key;
1770     PositionData *pos_data = value;
1771     EditData *move = NULL;
1772     EditData *trim = NULL;
1773
1774     if (el->parent) {
1775       move = g_hash_table_lookup (move_edits, el->parent);
1776       trim = g_hash_table_lookup (trim_edits, el->parent);
1777     }
1778
1779     if (!move)
1780       move = g_hash_table_lookup (move_edits, el);
1781     if (!trim)
1782       trim = g_hash_table_lookup (trim_edits, el);
1783
1784     /* should always have move with a valid start */
1785     if (!move || !GST_CLOCK_TIME_IS_VALID (move->start)) {
1786       GST_ERROR_OBJECT (el, "Element set to moving but neither it nor its "
1787           "parent are being edited");
1788       goto done;
1789     }
1790     /* may not have trim if element is a group and the child is away
1791      * from the edit position, but if we do it should have a valid duration */
1792     if (trim && !GST_CLOCK_TIME_IS_VALID (trim->duration)) {
1793       GST_ERROR_OBJECT (el, "Element set to trim end but neither it nor its "
1794           "parent is being trimmed");
1795       goto done;
1796     }
1797
1798     pos_data->start = move->start;
1799
1800     if (move->layer_priority != GES_TIMELINE_ELEMENT_NO_LAYER_PRIORITY)
1801       pos_data->layer_priority = move->layer_priority;
1802     else
1803       pos_data->layer_priority = ges_timeline_element_get_layer_priority (el);
1804
1805     if (trim)
1806       pos_data->end = pos_data->start + trim->duration;
1807     else
1808       pos_data->end = pos_data->start + el->duration;
1809   }
1810
1811   /* check overlaps */
1812   if (!timeline_tree_can_move_elements (root, moving, error))
1813     goto done;
1814
1815   ret = TRUE;
1816
1817 done:
1818   g_hash_table_unref (trim_edits);
1819   g_hash_table_unref (move_edits);
1820   g_hash_table_unref (moving);
1821
1822   return ret;
1823 }
1824
1825 /********************************************
1826  *         Perform Element Edit             *
1827  ********************************************/
1828
1829 static gboolean
1830 perform_element_edit (GESTimelineElement * element, EditData * edit)
1831 {
1832   gboolean ret = FALSE;
1833   guint32 layer_prio = ges_timeline_element_get_layer_priority (element);
1834
1835   switch (edit->mode) {
1836     case EDIT_MOVE:
1837       GST_INFO_OBJECT (element, "Moving %s from %" GST_TIME_FORMAT " to %"
1838           GST_TIME_FORMAT, element->name, GST_TIME_ARGS (element->start),
1839           GST_TIME_ARGS (edit->start));
1840       break;
1841     case EDIT_TRIM_START:
1842       GST_INFO_OBJECT (element, "Trimming %s start from %" GST_TIME_FORMAT
1843           " to %" GST_TIME_FORMAT, element->name,
1844           GST_TIME_ARGS (element->start), GST_TIME_ARGS (edit->start));
1845       break;
1846     case EDIT_TRIM_END:
1847       GST_INFO_OBJECT (element, "Trimming %s end from %" GST_TIME_FORMAT
1848           " to %" GST_TIME_FORMAT, element->name,
1849           GST_TIME_ARGS (_END (element)),
1850           GST_TIME_ARGS (element->start + edit->duration));
1851       break;
1852     case EDIT_TRIM_INPOINT_ONLY:
1853       GST_INFO_OBJECT (element, "Trimming %s in-point from %"
1854           GST_TIME_FORMAT " to %" GST_TIME_FORMAT, element->name,
1855           GST_TIME_ARGS (element->inpoint), GST_TIME_ARGS (edit->inpoint));
1856       break;
1857   }
1858
1859   if (!GES_IS_CLIP (element) && !GES_IS_TRACK_ELEMENT (element)) {
1860     GST_ERROR_OBJECT (element, "Cannot perform edit on group");
1861     return FALSE;
1862   }
1863
1864   if (!GES_IS_CLIP (element)
1865       && edit->layer_priority != GES_TIMELINE_ELEMENT_NO_LAYER_PRIORITY) {
1866     GST_ERROR_OBJECT (element, "Cannot move an element that is not a "
1867         "clip to a new layer");
1868     return FALSE;
1869   }
1870
1871   GES_TIMELINE_ELEMENT_SET_BEING_EDITED (element);
1872   if (GST_CLOCK_TIME_IS_VALID (edit->start)) {
1873     if (!ges_timeline_element_set_start (element, edit->start)) {
1874       GST_ERROR_OBJECT (element, "Failed to set the start");
1875       goto done;
1876     }
1877   }
1878   if (GST_CLOCK_TIME_IS_VALID (edit->inpoint)) {
1879     if (!ges_timeline_element_set_inpoint (element, edit->inpoint)) {
1880       GST_ERROR_OBJECT (element, "Failed to set the in-point");
1881       goto done;
1882     }
1883   }
1884   if (GST_CLOCK_TIME_IS_VALID (edit->duration)) {
1885     if (!ges_timeline_element_set_duration (element, edit->duration)) {
1886       GST_ERROR_OBJECT (element, "Failed to set the duration");
1887       goto done;
1888     }
1889   }
1890   if (edit->layer_priority != GES_TIMELINE_ELEMENT_NO_LAYER_PRIORITY) {
1891     GESTimeline *timeline = GES_TIMELINE_ELEMENT_TIMELINE (element);
1892     GESLayer *layer = ges_timeline_get_layer (timeline, edit->layer_priority);
1893
1894     GST_INFO_OBJECT (element, "Moving %s from layer %" G_GUINT32_FORMAT
1895         " to layer %" G_GUINT32_FORMAT, element->name, layer_prio,
1896         edit->layer_priority);
1897
1898     if (layer == NULL) {
1899       /* make sure we won't loop forever */
1900       if (ges_timeline_layer_priority_in_gap (timeline, edit->layer_priority)) {
1901         GST_ERROR_OBJECT (element, "Requested layer %" G_GUINT32_FORMAT
1902             " is within a gap in the timeline layers", edit->layer_priority);
1903         goto done;
1904       }
1905
1906       do {
1907         layer = ges_timeline_append_layer (timeline);
1908       } while (ges_layer_get_priority (layer) < edit->layer_priority);
1909     } else {
1910       gst_object_unref (layer);
1911     }
1912
1913     if (!ges_clip_move_to_layer (GES_CLIP (element), layer)) {
1914       GST_ERROR_OBJECT (element, "Failed to move layers");
1915       goto done;
1916     }
1917   }
1918
1919   ret = TRUE;
1920
1921 done:
1922   GES_TIMELINE_ELEMENT_UNSET_BEING_EDITED (element);
1923
1924   return ret;
1925 }
1926
1927 /* perform all the element edits found in @edits.
1928  * These should only be clips of track elements. */
1929 static gboolean
1930 timeline_tree_perform_edits (GNode * root, GHashTable * edits)
1931 {
1932   gboolean no_errors = TRUE;
1933   GHashTableIter iter;
1934   gpointer key, value;
1935
1936   /* freeze the auto-transitions whilst we edit */
1937   ges_timeline_freeze_auto_transitions (root->data, TRUE);
1938
1939   g_hash_table_iter_init (&iter, edits);
1940   while (g_hash_table_iter_next (&iter, &key, &value)) {
1941     if (GES_IS_TRACK_ELEMENT (key))
1942       ges_track_element_freeze_control_sources (GES_TRACK_ELEMENT (key), TRUE);
1943   }
1944
1945   g_hash_table_iter_init (&iter, edits);
1946   while (g_hash_table_iter_next (&iter, &key, &value)) {
1947     GESTimelineElement *element = key;
1948     EditData *edit_data = value;
1949     if (!perform_element_edit (element, edit_data))
1950       no_errors = FALSE;
1951   }
1952
1953   g_hash_table_iter_init (&iter, edits);
1954   while (g_hash_table_iter_next (&iter, &key, &value)) {
1955     if (GES_IS_TRACK_ELEMENT (key))
1956       ges_track_element_freeze_control_sources (GES_TRACK_ELEMENT (key), FALSE);
1957   }
1958
1959   /* allow the transitions to update if they can */
1960   ges_timeline_freeze_auto_transitions (root->data, FALSE);
1961
1962   timeline_tree_create_transitions (root, ges_timeline_find_auto_transition);
1963   timeline_update_duration (root->data);
1964
1965   return no_errors;
1966 }
1967
1968 #define _REPLACE_TRACK_ELEMENT_WITH_PARENT(element) \
1969   element = (GES_IS_TRACK_ELEMENT (element) && element->parent) ? element->parent : element
1970
1971 /********************************************
1972  *                 Ripple                   *
1973  ********************************************/
1974
1975 gboolean
1976 timeline_tree_ripple (GNode * root, GESTimelineElement * element,
1977     gint64 layer_priority_offset, GstClockTimeDiff offset, GESEdge edge,
1978     GstClockTime snapping_distance, GError ** error)
1979 {
1980   gboolean res = TRUE;
1981   GNode *node;
1982   GESTimelineElement *ripple_toplevel;
1983   GstClockTime ripple_time;
1984   GHashTable *edits = new_edit_table ();
1985   GHashTable *moving = new_position_table ();
1986   ElementEditMode mode;
1987   SnappedPosition *snap = new_snapped_position (snapping_distance);
1988
1989   _REPLACE_TRACK_ELEMENT_WITH_PARENT (element);
1990
1991   ripple_toplevel = ges_timeline_element_peak_toplevel (element);
1992
1993   /* if EDGE_END:
1994    *   TRIM_END the element, and MOVE all toplevels whose start is after
1995    *   the current end of the element by the same amount
1996    * otherwise:
1997    *   MOVE the topevel of the element, and all other toplevel elements
1998    *   whose start is after the current start of the element */
1999
2000   switch (edge) {
2001     case GES_EDGE_END:
2002       GST_INFO_OBJECT (element, "Rippling end with offset %"
2003           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2004           layer_priority_offset);
2005       mode = EDIT_TRIM_END;
2006       break;
2007     case GES_EDGE_START:
2008       GST_INFO_OBJECT (element, "Rippling start with offset %"
2009           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2010           layer_priority_offset);
2011       mode = EDIT_MOVE;
2012       break;
2013     case GES_EDGE_NONE:
2014       GST_INFO_OBJECT (element, "Rippling with toplevel with offset %"
2015           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2016           layer_priority_offset);
2017       element = ripple_toplevel;
2018       mode = EDIT_MOVE;
2019       break;
2020     default:
2021       GST_WARNING_OBJECT (element, "Edge not supported");
2022       goto done;
2023   }
2024
2025   ripple_time = ELEMENT_EDGE_VALUE (element, edge);
2026
2027   /* add edits */
2028   if (!add_element_edit (edits, element, mode))
2029     goto error;
2030
2031   for (node = root->children; node; node = node->next) {
2032     GESTimelineElement *toplevel = node->data;
2033     if (toplevel == ripple_toplevel)
2034       continue;
2035
2036     if (toplevel->start >= ripple_time) {
2037       if (!add_element_edit (edits, toplevel, EDIT_MOVE))
2038         goto error;
2039     }
2040   }
2041
2042   if (!timeline_tree_add_edited_to_moving (root, edits, moving))
2043     goto error;
2044
2045   /* snap */
2046   if (!timeline_tree_snap (root, element, mode, &offset, moving, snap))
2047     goto error;
2048
2049   /* check and set edits using snapped values */
2050   give_edits_same_offset (edits, offset, layer_priority_offset);
2051   if (!timeline_tree_set_element_edit_values (root, edits, error))
2052     goto error;
2053
2054   /* check overlaps */
2055   set_moving_positions_from_edits (moving, edits);
2056   if (!timeline_tree_can_move_elements (root, moving, error))
2057     goto error;
2058
2059   /* emit snapping now. Edits should only fail if a programming error
2060    * occured */
2061   if (snap)
2062     ges_timeline_emit_snapping (root->data, snap->element, snap->snapped_to,
2063         snap->snapped);
2064
2065   res = timeline_tree_perform_edits (root, edits);
2066
2067 done:
2068   g_hash_table_unref (edits);
2069   g_hash_table_unref (moving);
2070   g_free (snap);
2071   return res;
2072
2073 error:
2074   res = FALSE;
2075   goto done;
2076 }
2077
2078 /********************************************
2079  *                  Trim                    *
2080  ********************************************/
2081
2082 gboolean
2083 timeline_tree_trim (GNode * root, GESTimelineElement * element,
2084     gint64 layer_priority_offset, GstClockTimeDiff offset, GESEdge edge,
2085     GstClockTime snapping_distance, GError ** error)
2086 {
2087   gboolean res = TRUE;
2088   GHashTable *edits = new_edit_table ();
2089   GHashTable *moving = new_position_table ();
2090   ElementEditMode mode;
2091   SnappedPosition *snap = new_snapped_position (snapping_distance);
2092
2093   _REPLACE_TRACK_ELEMENT_WITH_PARENT (element);
2094
2095   /* TODO: 2.0 remove this warning and simply fail if no edge is specified */
2096   if (edge == GES_EDGE_NONE) {
2097     g_warning ("No edge specified for trimming. Defaulting to GES_EDGE_START");
2098     edge = GES_EDGE_START;
2099   }
2100
2101   switch (edge) {
2102     case GES_EDGE_END:
2103       GST_INFO_OBJECT (element, "Trimming end with offset %"
2104           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2105           layer_priority_offset);
2106       mode = EDIT_TRIM_END;
2107       break;
2108     case GES_EDGE_START:
2109       GST_INFO_OBJECT (element, "Trimming start with offset %"
2110           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2111           layer_priority_offset);
2112       mode = EDIT_TRIM_START;
2113       break;
2114     default:
2115       GST_WARNING_OBJECT (element, "Edge not supported");
2116       goto done;
2117   }
2118
2119   /* add edits */
2120   if (!add_element_edit (edits, element, mode))
2121     goto error;
2122
2123   if (!timeline_tree_add_edited_to_moving (root, edits, moving))
2124     goto error;
2125
2126   /* snap */
2127   if (!timeline_tree_snap (root, element, mode, &offset, moving, snap))
2128     goto error;
2129
2130   /* check and set edits using snapped values */
2131   give_edits_same_offset (edits, offset, layer_priority_offset);
2132   if (!timeline_tree_set_element_edit_values (root, edits, error))
2133     goto error;
2134
2135   /* check overlaps */
2136   set_moving_positions_from_edits (moving, edits);
2137   if (!timeline_tree_can_move_elements (root, moving, error)) {
2138     goto error;
2139   }
2140
2141   /* emit snapping now. Edits should only fail if a programming error
2142    * occured */
2143   if (snap)
2144     ges_timeline_emit_snapping (root->data, snap->element, snap->snapped_to,
2145         snap->snapped);
2146
2147   res = timeline_tree_perform_edits (root, edits);
2148
2149 done:
2150   g_hash_table_unref (edits);
2151   g_hash_table_unref (moving);
2152   g_free (snap);
2153   return res;
2154
2155 error:
2156   res = FALSE;
2157   goto done;
2158 }
2159
2160 /********************************************
2161  *                  Move                    *
2162  ********************************************/
2163
2164 gboolean
2165 timeline_tree_move (GNode * root, GESTimelineElement * element,
2166     gint64 layer_priority_offset, GstClockTimeDiff offset, GESEdge edge,
2167     GstClockTime snapping_distance, GError ** error)
2168 {
2169   gboolean res = TRUE;
2170   GHashTable *edits = new_edit_table ();
2171   GHashTable *moving = new_position_table ();
2172   ElementEditMode mode;
2173   SnappedPosition *snap = new_snapped_position (snapping_distance);
2174
2175   _REPLACE_TRACK_ELEMENT_WITH_PARENT (element);
2176
2177   switch (edge) {
2178     case GES_EDGE_END:
2179       GST_INFO_OBJECT (element, "Moving end with offset %"
2180           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2181           layer_priority_offset);
2182       mode = EDIT_TRIM_END;
2183       break;
2184     case GES_EDGE_START:
2185       GST_INFO_OBJECT (element, "Moving start with offset %"
2186           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2187           layer_priority_offset);
2188       mode = EDIT_MOVE;
2189       break;
2190     case GES_EDGE_NONE:
2191       GST_INFO_OBJECT (element, "Moving with toplevel with offset %"
2192           G_GINT64_FORMAT " and layer offset %" G_GINT64_FORMAT, offset,
2193           layer_priority_offset);
2194       element = ges_timeline_element_peak_toplevel (element);
2195       mode = EDIT_MOVE;
2196       break;
2197     default:
2198       GST_WARNING_OBJECT (element, "Edge not supported");
2199       goto done;
2200   }
2201
2202   /* add edits */
2203   if (!add_element_edit (edits, element, mode))
2204     goto error;
2205
2206   if (!timeline_tree_add_edited_to_moving (root, edits, moving))
2207     goto error;
2208
2209   /* snap */
2210   if (!timeline_tree_snap (root, element, mode, &offset, moving, snap))
2211     goto error;
2212
2213   /* check and set edits using snapped values */
2214   give_edits_same_offset (edits, offset, layer_priority_offset);
2215   if (!timeline_tree_set_element_edit_values (root, edits, error))
2216     goto error;
2217
2218   /* check overlaps */
2219   set_moving_positions_from_edits (moving, edits);
2220   if (!timeline_tree_can_move_elements (root, moving, error)) {
2221     goto error;
2222   }
2223
2224   /* emit snapping now. Edits should only fail if a programming error
2225    * occured */
2226   if (snap)
2227     ges_timeline_emit_snapping (root->data, snap->element, snap->snapped_to,
2228         snap->snapped);
2229
2230   res = timeline_tree_perform_edits (root, edits);
2231
2232 done:
2233   g_hash_table_unref (edits);
2234   g_hash_table_unref (moving);
2235   g_free (snap);
2236   return res;
2237
2238 error:
2239   res = FALSE;
2240   goto done;
2241 }
2242
2243 /********************************************
2244  *                  Roll                    *
2245  ********************************************/
2246
2247 static gboolean
2248 is_descendant (GESTimelineElement * element, GESTimelineElement * ancestor)
2249 {
2250   GESTimelineElement *parent = element;
2251   while ((parent = parent->parent)) {
2252     if (parent == ancestor)
2253       return TRUE;
2254   }
2255   return FALSE;
2256 }
2257
2258 static gboolean
2259 find_neighbour (GNode * node, TreeIterationData * data)
2260 {
2261   GList *tmp;
2262   gboolean in_same_track = FALSE;
2263   GESTimelineElement *edge_element, *element = node->data;
2264
2265   if (!GES_IS_SOURCE (element))
2266     return FALSE;
2267
2268   /* if the element is controlled by the trimmed element (a group or a
2269    * clip) it is not a neighbour */
2270   if (is_descendant (element, data->element))
2271     return FALSE;
2272
2273   /* test if we share a track with one of the sources at the edge */
2274   for (tmp = data->sources; tmp; tmp = tmp->next) {
2275     if (ges_track_element_get_track (GES_TRACK_ELEMENT (element)) ==
2276         ges_track_element_get_track (tmp->data)) {
2277       in_same_track = TRUE;
2278       break;
2279     }
2280   }
2281
2282   if (!in_same_track)
2283     return FALSE;
2284
2285   /* get the most toplevel element whose edge touches the position */
2286   edge_element = NULL;
2287   while (element && ELEMENT_EDGE_VALUE (element, data->edge) == data->position) {
2288     edge_element = element;
2289     element = element->parent;
2290   }
2291
2292   if (edge_element && !g_list_find (data->neighbours, edge_element))
2293     data->neighbours = g_list_prepend (data->neighbours, edge_element);
2294
2295   return FALSE;
2296 }
2297
2298 static gboolean
2299 find_sources_at_position (GNode * node, TreeIterationData * data)
2300 {
2301   GESTimelineElement *element = node->data;
2302
2303   if (!GES_IS_SOURCE (element))
2304     return FALSE;
2305
2306   if (ELEMENT_EDGE_VALUE (element, data->edge) == data->position)
2307     data->sources = g_list_append (data->sources, element);
2308
2309   return FALSE;
2310 }
2311
2312 gboolean
2313 timeline_tree_roll (GNode * root, GESTimelineElement * element,
2314     GstClockTimeDiff offset, GESEdge edge, GstClockTime snapping_distance,
2315     GError ** error)
2316 {
2317   gboolean res = TRUE;
2318   GList *tmp;
2319   GNode *node;
2320   TreeIterationData data = tree_iteration_data_init;
2321   GHashTable *edits = new_edit_table ();
2322   GHashTable *moving = new_position_table ();
2323   ElementEditMode mode;
2324   SnappedPosition *snap = new_snapped_position (snapping_distance);
2325
2326   _REPLACE_TRACK_ELEMENT_WITH_PARENT (element);
2327
2328   /* if EDGE_END:
2329    *   TRIM_END the element, and TRIM_START the neighbouring clips to the
2330    *   end edge
2331    * otherwise:
2332    *   TRIM_START the element, and TRIM_END the neighbouring clips to the
2333    *   start edge */
2334
2335   switch (edge) {
2336     case GES_EDGE_END:
2337       GST_INFO_OBJECT (element, "Rolling end with offset %"
2338           G_GINT64_FORMAT, offset);
2339       mode = EDIT_TRIM_END;
2340       break;
2341     case GES_EDGE_START:
2342       GST_INFO_OBJECT (element, "Rolling start with offset %"
2343           G_GINT64_FORMAT, offset);
2344       mode = EDIT_TRIM_START;
2345       break;
2346     case GES_EDGE_NONE:
2347       GST_WARNING_OBJECT (element, "Need to select an edge when rolling.");
2348       goto done;
2349     default:
2350       GST_WARNING_OBJECT (element, "Edge not supported");
2351       goto done;
2352   }
2353
2354   /* add edits */
2355   if (!add_element_edit (edits, element, mode))
2356     goto error;
2357
2358   /* first, find all the sources at the edge */
2359   node = find_node (root, element);
2360   if (!node) {
2361     GST_ERROR_OBJECT (element, "Not being tracked");
2362     goto error;
2363   }
2364
2365   data.element = element;
2366   data.edge = (edge == GES_EDGE_END) ? GES_EDGE_END : GES_EDGE_START;
2367   data.position = ELEMENT_EDGE_VALUE (element, data.edge);
2368   data.sources = NULL;
2369
2370   g_node_traverse (node, G_IN_ORDER, G_TRAVERSE_LEAVES, -1,
2371       (GNodeTraverseFunc) find_sources_at_position, &data);
2372
2373   /* find elements that whose opposite edge touches the edge of the
2374    * element and shares a track with one of the found sources */
2375   data.edge = (edge == GES_EDGE_END) ? GES_EDGE_START : GES_EDGE_END;
2376   data.neighbours = NULL;
2377
2378   g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_LEAVES, -1,
2379       (GNodeTraverseFunc) find_neighbour, &data);
2380
2381   for (tmp = data.neighbours; tmp; tmp = tmp->next) {
2382     GESTimelineElement *clip = tmp->data;
2383     ElementEditMode opposite =
2384         (mode == EDIT_TRIM_END) ? EDIT_TRIM_START : EDIT_TRIM_END;
2385     if (!add_element_edit (edits, clip, opposite))
2386       goto error;
2387   }
2388
2389   if (!timeline_tree_add_edited_to_moving (root, edits, moving))
2390     goto error;
2391
2392   /* snap */
2393   if (!timeline_tree_snap (root, element, mode, &offset, moving, snap))
2394     goto error;
2395
2396   /* check and set edits using snapped values */
2397   give_edits_same_offset (edits, offset, 0);
2398   if (!timeline_tree_set_element_edit_values (root, edits, error))
2399     goto error;
2400
2401   /* check overlaps */
2402   set_moving_positions_from_edits (moving, edits);
2403   if (!timeline_tree_can_move_elements (root, moving, error)) {
2404     goto error;
2405   }
2406
2407   /* emit snapping now. Edits should only fail if a programming error
2408    * occured */
2409   if (snap)
2410     ges_timeline_emit_snapping (root->data, snap->element, snap->snapped_to,
2411         snap->snapped);
2412
2413   res = timeline_tree_perform_edits (root, edits);
2414
2415 done:
2416   g_hash_table_unref (edits);
2417   g_hash_table_unref (moving);
2418   g_list_free (data.neighbours);
2419   g_list_free (data.sources);
2420   g_free (snap);
2421   return res;
2422
2423 error:
2424   res = FALSE;
2425   goto done;
2426 }
2427
2428 static void
2429 create_transition_if_needed (GESTimeline * timeline, GESTrackElement * prev,
2430     GESTrackElement * next, GESTreeGetAutoTransitionFunc get_auto_transition)
2431 {
2432   GstClockTime duration = _END (prev) - _START (next);
2433   GESAutoTransition *trans =
2434       get_auto_transition (timeline, prev, next, duration);
2435
2436   if (!trans) {
2437     GESLayer *layer = ges_timeline_get_layer (timeline,
2438         GES_TIMELINE_ELEMENT_LAYER_PRIORITY (prev));
2439     gst_object_unref (layer);
2440
2441     GST_INFO ("Creating transition [%" G_GINT64_FORMAT " - %" G_GINT64_FORMAT
2442         "]", _START (next), duration);
2443     ges_timeline_create_transition (timeline, prev, next, NULL, layer,
2444         _START (next), duration);
2445   } else {
2446     GST_INFO ("Already have transition %" GST_PTR_FORMAT " between %" GES_FORMAT
2447         " and %" GES_FORMAT, trans, GES_ARGS (prev), GES_ARGS (next));
2448   }
2449 }
2450
2451 static gboolean
2452 create_transitions (GNode * node,
2453     GESTreeGetAutoTransitionFunc get_auto_transition)
2454 {
2455   TreeIterationData data = tree_iteration_data_init;
2456   GESTimeline *timeline;
2457   GESLayer *layer;
2458
2459   if (!GES_IS_SOURCE (node->data))
2460     return FALSE;
2461
2462   timeline = GES_TIMELINE_ELEMENT_TIMELINE (node->data);
2463
2464   if (!timeline) {
2465     GST_INFO ("%" GES_FORMAT " not in timeline yet", GES_ARGS (node->data));
2466
2467     return FALSE;
2468   }
2469
2470   layer =
2471       ges_timeline_get_layer (timeline,
2472       GES_TIMELINE_ELEMENT_LAYER_PRIORITY (node->data));
2473   gst_object_unref (layer);
2474
2475   if (!ges_layer_get_auto_transition (layer))
2476     return FALSE;
2477
2478   GST_LOG (node->data, "Checking for overlaps");
2479   data.root = g_node_get_root (node);
2480   check_all_overlaps_with_element (node, &data);
2481
2482   if (data.overlaping_on_start)
2483     create_transition_if_needed (timeline,
2484         GES_TRACK_ELEMENT (data.overlaping_on_start), node->data,
2485         get_auto_transition);
2486
2487   if (data.overlaping_on_end)
2488     create_transition_if_needed (timeline, node->data,
2489         GES_TRACK_ELEMENT (data.overlaping_on_end), get_auto_transition);
2490
2491   return FALSE;
2492 }
2493
2494 void
2495 timeline_tree_create_transitions_for_track_element (GNode * root,
2496     GESTrackElement * element, GESTreeGetAutoTransitionFunc get_auto_transition)
2497 {
2498   GNode *node = find_node (root, element);
2499   g_assert (node);
2500
2501   create_transitions (node, get_auto_transition);
2502 }
2503
2504 void
2505 timeline_tree_create_transitions (GNode * root,
2506     GESTreeGetAutoTransitionFunc get_auto_transition)
2507 {
2508   g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_LEAFS, -1,
2509       (GNodeTraverseFunc) create_transitions, get_auto_transition);
2510 }
2511
2512 static gboolean
2513 compute_duration (GNode * node, GstClockTime * duration)
2514 {
2515   *duration = MAX (_END (node->data), *duration);
2516
2517   return FALSE;
2518 }
2519
2520 GstClockTime
2521 timeline_tree_get_duration (GNode * root)
2522 {
2523   GstClockTime duration = 0;
2524
2525   if (root->children)
2526     g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_LEAFS, -1,
2527         (GNodeTraverseFunc) compute_duration, &duration);
2528
2529   return duration;
2530 }
2531
2532 static gboolean
2533 reset_layer_activness (GNode * node, GESLayer * layer)
2534 {
2535   GESTrack *track;
2536
2537
2538   if (!GES_IS_TRACK_ELEMENT (node->data))
2539     return FALSE;
2540
2541   track = ges_track_element_get_track (node->data);
2542   if (!track || (ges_timeline_element_get_layer_priority (node->data) !=
2543           ges_layer_get_priority (layer)))
2544     return FALSE;
2545
2546   ges_track_element_set_layer_active (node->data,
2547       ges_layer_get_active_for_track (layer, track));
2548
2549   return FALSE;
2550 }
2551
2552 void
2553 timeline_tree_reset_layer_active (GNode * root, GESLayer * layer)
2554 {
2555   g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_LEAFS, -1,
2556       (GNodeTraverseFunc) reset_layer_activness, layer);
2557 }
2558
2559 static gboolean
2560 set_is_smart_rendering (GNode * node, gboolean * is_rendering_smartly)
2561 {
2562   if (!GES_IS_SOURCE (node->data))
2563     return FALSE;
2564
2565   ges_source_set_rendering_smartly (GES_SOURCE (node->data),
2566       *is_rendering_smartly);
2567   return FALSE;
2568 }
2569
2570 void
2571 timeline_tree_set_smart_rendering (GNode * root, gboolean rendering_smartly)
2572 {
2573   g_node_traverse (root, G_PRE_ORDER, G_TRAVERSE_LEAFS, -1,
2574       (GNodeTraverseFunc) set_is_smart_rendering, &rendering_smartly);
2575 }