#30179: Merging 3 or more media objects can throw unnecessary
MediaOrderConflictWarnings
-------------------------------+------------------------------------
Reporter: Matt Westcott | Owner: nobody
Type: Bug | Status: new
Component: Forms | Version: master
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------+------------------------------------
Comment (by Matt Westcott):
To summarise: Even with the new strategy in #30153 of holding on to the
un-merged lists as long as possible, the final merging is still done by
adding one list at a time. The intermediate results are lists, which are
assumed to be order-critical; this means the intermediate results have
additional constraints that are not present in the original lists, causing
it to see conflicts where there aren't any. Additionally, we should try to
preserve the original sequence of files as much as possible, to avoid
unnecessarily breaking user code that hasn't fully specified its
dependencies and is relying on the 1.x behaviour.
I think we need to approach this as a graph problem (which I realise might
sound like overkill, but I'd rather start with something formally correct
and optimise later as necessary): a conflict occurs whenever the
dependency graph is cyclic. #30153 is a useful step towards this, as it
ensures we have the accurate dependency graph up until the point where we
need to assemble the final list.
I suggest we replace `Media.merge` with a new method that accepts any
number of lists (using `*args` if we want to preserve the existing method
signature for backwards compatibility). This would work as follows:
* Iterate over all items in all sub-lists, building a dependency graph
(where a dependency is any item that immediately precedes it within a sub-
list) and a de-duplicated list containing all items indexed in the order
they are first encountered
* Starting from the first item in the de-duplicated list, backtrack
through the dependency graph, following the lowest-indexed dependency each
time until we reach an item with no dependencies. While backtracking,
maintain a stack of visited items. If we encounter an item already on the
stack, this is a dependency loop; throw a `MediaOrderConflictWarning` and
break out of the backtracking loop
* Output the resulting item, then remove it from the dependency graph and
the de-duplicated list
* If the 'visited items' stack is non-empty, pop the last item off it and
repeat the backtracking step from there. Otherwise, repeat the
backtracking step starting from the next item in the de-duplicated list
* Repeat until no items remain
--
Ticket URL: <https://code.djangoproject.com/ticket/30179#comment:11>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.
--
You received this message because you are subscribed to the Google Groups
"Django updates" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to django-updates+unsubscr...@googlegroups.com.
To post to this group, send email to django-updates@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/django-updates/064.4f56f9d497c842bfe7acf86d258b4d56%40djangoproject.com.
For more options, visit https://groups.google.com/d/optout.
