1/*
2 * Copyright (C) 2006, 2010 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "Element.h"
28#include "InsertListCommand.h"
29#include "DocumentFragment.h"
30#include "htmlediting.h"
31#include "HTMLElement.h"
32#include "HTMLNames.h"
33#include "TextIterator.h"
34#include "visible_units.h"
35
36namespace WebCore {
37
38using namespace HTMLNames;
39
40static Node* enclosingListChild(Node* node, Node* listNode)
41{
42    Node* listChild = enclosingListChild(node);
43    while (listChild && enclosingList(listChild) != listNode)
44        listChild = enclosingListChild(listChild->parentNode());
45    return listChild;
46}
47
48PassRefPtr<HTMLElement> InsertListCommand::insertList(Document* document, Type type)
49{
50    RefPtr<InsertListCommand> insertCommand = create(document, type);
51    insertCommand->apply();
52    return insertCommand->m_listElement;
53}
54
55HTMLElement* InsertListCommand::fixOrphanedListChild(Node* node)
56{
57    RefPtr<HTMLElement> listElement = createUnorderedListElement(document());
58    insertNodeBefore(listElement, node);
59    removeNode(node);
60    appendNode(node, listElement);
61    m_listElement = listElement;
62    return listElement.get();
63}
64
65PassRefPtr<HTMLElement> InsertListCommand::mergeWithNeighboringLists(PassRefPtr<HTMLElement> passedList)
66{
67    RefPtr<HTMLElement> list = passedList;
68    Element* previousList = list->previousElementSibling();
69    if (canMergeLists(previousList, list.get()))
70        mergeIdenticalElements(previousList, list);
71
72    if (!list || !list->nextElementSibling() || !list->nextElementSibling()->isHTMLElement())
73        return list.release();
74
75    RefPtr<HTMLElement> nextList = toHTMLElement(list->nextElementSibling());
76    if (canMergeLists(list.get(), nextList.get())) {
77        mergeIdenticalElements(list, nextList);
78        return nextList.release();
79    }
80    return list.release();
81}
82
83bool InsertListCommand::selectionHasListOfType(const VisibleSelection& selection, const QualifiedName& listTag)
84{
85    VisiblePosition start = selection.visibleStart();
86
87    if (!enclosingList(start.deepEquivalent().deprecatedNode()))
88        return false;
89
90    VisiblePosition end = selection.visibleEnd();
91    while (start.isNotNull() && start != end) {
92        Element* listNode = enclosingList(start.deepEquivalent().deprecatedNode());
93        if (!listNode || !listNode->hasTagName(listTag))
94            return false;
95        start = startOfNextParagraph(start);
96    }
97
98    return true;
99}
100
101InsertListCommand::InsertListCommand(Document* document, Type type)
102    : CompositeEditCommand(document), m_type(type)
103{
104}
105
106void InsertListCommand::doApply()
107{
108    if (!endingSelection().isNonOrphanedCaretOrRange())
109        return;
110
111    if (!endingSelection().rootEditableElement())
112        return;
113
114    VisiblePosition visibleEnd = endingSelection().visibleEnd();
115    VisiblePosition visibleStart = endingSelection().visibleStart();
116    // When a selection ends at the start of a paragraph, we rarely paint
117    // the selection gap before that paragraph, because there often is no gap.
118    // In a case like this, it's not obvious to the user that the selection
119    // ends "inside" that paragraph, so it would be confusing if InsertUn{Ordered}List
120    // operated on that paragraph.
121    // FIXME: We paint the gap before some paragraphs that are indented with left
122    // margin/padding, but not others.  We should make the gap painting more consistent and
123    // then use a left margin/padding rule here.
124    if (visibleEnd != visibleStart && isStartOfParagraph(visibleEnd, CanSkipOverEditingBoundary))
125        setEndingSelection(VisibleSelection(visibleStart, visibleEnd.previous(CannotCrossEditingBoundary)));
126
127    const QualifiedName& listTag = (m_type == OrderedList) ? olTag : ulTag;
128    if (endingSelection().isRange()) {
129        VisibleSelection selection = selectionForParagraphIteration(endingSelection());
130        ASSERT(selection.isRange());
131        VisiblePosition startOfSelection = selection.visibleStart();
132        VisiblePosition endOfSelection = selection.visibleEnd();
133        VisiblePosition startOfLastParagraph = startOfParagraph(endOfSelection, CanSkipOverEditingBoundary);
134
135        if (startOfParagraph(startOfSelection, CanSkipOverEditingBoundary) != startOfLastParagraph) {
136            bool forceCreateList = !selectionHasListOfType(selection, listTag);
137
138            RefPtr<Range> currentSelection = endingSelection().firstRange();
139            VisiblePosition startOfCurrentParagraph = startOfSelection;
140            while (!inSameParagraph(startOfCurrentParagraph, startOfLastParagraph, CanCrossEditingBoundary)) {
141                // doApply() may operate on and remove the last paragraph of the selection from the document
142                // if it's in the same list item as startOfCurrentParagraph.  Return early to avoid an
143                // infinite loop and because there is no more work to be done.
144                // FIXME(<rdar://problem/5983974>): The endingSelection() may be incorrect here.  Compute
145                // the new location of endOfSelection and use it as the end of the new selection.
146                if (!startOfLastParagraph.deepEquivalent().anchorNode()->inDocument())
147                    return;
148                setEndingSelection(startOfCurrentParagraph);
149
150                // Save and restore endOfSelection and startOfLastParagraph when necessary
151                // since moveParagraph and movePragraphWithClones can remove nodes.
152                // FIXME: This is an inefficient way to keep selection alive because indexForVisiblePosition walks from
153                // the beginning of the document to the endOfSelection everytime this code is executed.
154                // But not using index is hard because there are so many ways we can lose selection inside doApplyForSingleParagraph.
155                int indexForEndOfSelection = indexForVisiblePosition(endOfSelection);
156                doApplyForSingleParagraph(forceCreateList, listTag, currentSelection.get());
157                if (endOfSelection.isNull() || endOfSelection.isOrphan() || startOfLastParagraph.isNull() || startOfLastParagraph.isOrphan()) {
158                    RefPtr<Range> lastSelectionRange = TextIterator::rangeFromLocationAndLength(document()->documentElement(), indexForEndOfSelection, 0, true);
159                    // If lastSelectionRange is null, then some contents have been deleted from the document.
160                    // This should never happen and if it did, exit early immediately because we've lost the loop invariant.
161                    ASSERT(lastSelectionRange);
162                    if (!lastSelectionRange)
163                        return;
164                    endOfSelection = lastSelectionRange->startPosition();
165                    startOfLastParagraph = startOfParagraph(endOfSelection, CanSkipOverEditingBoundary);
166                }
167
168                // Fetch the start of the selection after moving the first paragraph,
169                // because moving the paragraph will invalidate the original start.
170                // We'll use the new start to restore the original selection after
171                // we modified all selected paragraphs.
172                if (startOfCurrentParagraph == startOfSelection)
173                    startOfSelection = endingSelection().visibleStart();
174
175                startOfCurrentParagraph = startOfNextParagraph(endingSelection().visibleStart());
176            }
177            setEndingSelection(endOfSelection);
178            doApplyForSingleParagraph(forceCreateList, listTag, currentSelection.get());
179            // Fetch the end of the selection, for the reason mentioned above.
180            endOfSelection = endingSelection().visibleEnd();
181            setEndingSelection(VisibleSelection(startOfSelection, endOfSelection));
182            return;
183        }
184    }
185
186    doApplyForSingleParagraph(false, listTag, endingSelection().firstRange().get());
187}
188
189void InsertListCommand::doApplyForSingleParagraph(bool forceCreateList, const QualifiedName& listTag, Range* currentSelection)
190{
191    // FIXME: This will produce unexpected results for a selection that starts just before a
192    // table and ends inside the first cell, selectionForParagraphIteration should probably
193    // be renamed and deployed inside setEndingSelection().
194    Node* selectionNode = endingSelection().start().deprecatedNode();
195    Node* listChildNode = enclosingListChild(selectionNode);
196    bool switchListType = false;
197    if (listChildNode) {
198        // Remove the list chlild.
199        RefPtr<HTMLElement> listNode = enclosingList(listChildNode);
200        if (!listNode) {
201            listNode = fixOrphanedListChild(listChildNode);
202            listNode = mergeWithNeighboringLists(listNode);
203        }
204        if (!listNode->hasTagName(listTag))
205            // listChildNode will be removed from the list and a list of type m_type will be created.
206            switchListType = true;
207
208        // If the list is of the desired type, and we are not removing the list, then exit early.
209        if (!switchListType && forceCreateList)
210            return;
211
212        // If the entire list is selected, then convert the whole list.
213        if (switchListType && isNodeVisiblyContainedWithin(listNode.get(), currentSelection)) {
214            bool rangeStartIsInList = visiblePositionBeforeNode(listNode.get()) == currentSelection->startPosition();
215            bool rangeEndIsInList = visiblePositionAfterNode(listNode.get()) == currentSelection->endPosition();
216
217            RefPtr<HTMLElement> newList = createHTMLElement(document(), listTag);
218            insertNodeBefore(newList, listNode);
219
220            Node* firstChildInList = enclosingListChild(VisiblePosition(firstPositionInNode(listNode.get())).deepEquivalent().deprecatedNode(), listNode.get());
221            Node* outerBlock = firstChildInList->isBlockFlow() ? firstChildInList : listNode.get();
222
223            moveParagraphWithClones(firstPositionInNode(listNode.get()), lastPositionInNode(listNode.get()), newList.get(), outerBlock);
224
225            // Manually remove listNode because moveParagraphWithClones sometimes leaves it behind in the document.
226            // See the bug 33668 and editing/execCommand/insert-list-orphaned-item-with-nested-lists.html.
227            // FIXME: This might be a bug in moveParagraphWithClones or deleteSelection.
228            if (listNode && listNode->inDocument())
229                removeNode(listNode);
230
231            newList = mergeWithNeighboringLists(newList);
232
233            // Restore the start and the end of current selection if they started inside listNode
234            // because moveParagraphWithClones could have removed them.
235            ExceptionCode ec;
236            if (rangeStartIsInList && newList)
237                currentSelection->setStart(newList, 0, ec);
238            if (rangeEndIsInList && newList)
239                currentSelection->setEnd(newList, lastOffsetInNode(newList.get()), ec);
240
241            setEndingSelection(VisiblePosition(firstPositionInNode(newList.get())));
242
243            return;
244        }
245
246        unlistifyParagraph(endingSelection().visibleStart(), listNode.get(), listChildNode);
247    }
248
249    if (!listChildNode || switchListType || forceCreateList)
250        m_listElement = listifyParagraph(endingSelection().visibleStart(), listTag);
251}
252
253void InsertListCommand::unlistifyParagraph(const VisiblePosition& originalStart, HTMLElement* listNode, Node* listChildNode)
254{
255    Node* nextListChild;
256    Node* previousListChild;
257    VisiblePosition start;
258    VisiblePosition end;
259    if (listChildNode->hasTagName(liTag)) {
260        start = firstPositionInNode(listChildNode);
261        end = lastPositionInNode(listChildNode);
262        nextListChild = listChildNode->nextSibling();
263        previousListChild = listChildNode->previousSibling();
264    } else {
265        // A paragraph is visually a list item minus a list marker.  The paragraph will be moved.
266        start = startOfParagraph(originalStart, CanSkipOverEditingBoundary);
267        end = endOfParagraph(start, CanSkipOverEditingBoundary);
268        nextListChild = enclosingListChild(end.next().deepEquivalent().deprecatedNode(), listNode);
269        ASSERT(nextListChild != listChildNode);
270        previousListChild = enclosingListChild(start.previous().deepEquivalent().deprecatedNode(), listNode);
271        ASSERT(previousListChild != listChildNode);
272    }
273    // When removing a list, we must always create a placeholder to act as a point of insertion
274    // for the list content being removed.
275    RefPtr<Element> placeholder = createBreakElement(document());
276    RefPtr<Element> nodeToInsert = placeholder;
277    // If the content of the list item will be moved into another list, put it in a list item
278    // so that we don't create an orphaned list child.
279    if (enclosingList(listNode)) {
280        nodeToInsert = createListItemElement(document());
281        appendNode(placeholder, nodeToInsert);
282    }
283
284    if (nextListChild && previousListChild) {
285        // We want to pull listChildNode out of listNode, and place it before nextListChild
286        // and after previousListChild, so we split listNode and insert it between the two lists.
287        // But to split listNode, we must first split ancestors of listChildNode between it and listNode,
288        // if any exist.
289        // FIXME: We appear to split at nextListChild as opposed to listChildNode so that when we remove
290        // listChildNode below in moveParagraphs, previousListChild will be removed along with it if it is
291        // unrendered. But we ought to remove nextListChild too, if it is unrendered.
292        splitElement(listNode, splitTreeToNode(nextListChild, listNode));
293        insertNodeBefore(nodeToInsert, listNode);
294    } else if (nextListChild || listChildNode->parentNode() != listNode) {
295        // Just because listChildNode has no previousListChild doesn't mean there isn't any content
296        // in listNode that comes before listChildNode, as listChildNode could have ancestors
297        // between it and listNode. So, we split up to listNode before inserting the placeholder
298        // where we're about to move listChildNode to.
299        if (listChildNode->parentNode() != listNode)
300            splitElement(listNode, splitTreeToNode(listChildNode, listNode).get());
301        insertNodeBefore(nodeToInsert, listNode);
302    } else
303        insertNodeAfter(nodeToInsert, listNode);
304
305    VisiblePosition insertionPoint = VisiblePosition(positionBeforeNode(placeholder.get()));
306    moveParagraphs(start, end, insertionPoint, true);
307}
308
309static Element* adjacentEnclosingList(const VisiblePosition& pos, const VisiblePosition& adjacentPos, const QualifiedName& listTag)
310{
311    Element* listNode = outermostEnclosingList(adjacentPos.deepEquivalent().deprecatedNode());
312
313    if (!listNode)
314        return 0;
315
316    Node* previousCell = enclosingTableCell(pos.deepEquivalent());
317    Node* currentCell = enclosingTableCell(adjacentPos.deepEquivalent());
318
319    if (!listNode->hasTagName(listTag)
320        || listNode->contains(pos.deepEquivalent().deprecatedNode())
321        || previousCell != currentCell
322        || enclosingList(listNode) != enclosingList(pos.deepEquivalent().deprecatedNode()))
323        return 0;
324
325    return listNode;
326}
327
328PassRefPtr<HTMLElement> InsertListCommand::listifyParagraph(const VisiblePosition& originalStart, const QualifiedName& listTag)
329{
330    VisiblePosition start = startOfParagraph(originalStart, CanSkipOverEditingBoundary);
331    VisiblePosition end = endOfParagraph(start, CanSkipOverEditingBoundary);
332
333    if (start.isNull() || end.isNull())
334        return 0;
335
336    // Check for adjoining lists.
337    RefPtr<HTMLElement> listItemElement = createListItemElement(document());
338    RefPtr<HTMLElement> placeholder = createBreakElement(document());
339    appendNode(placeholder, listItemElement);
340
341    // Place list item into adjoining lists.
342    Element* previousList = adjacentEnclosingList(start.deepEquivalent(), start.previous(CannotCrossEditingBoundary), listTag);
343    Element* nextList = adjacentEnclosingList(start.deepEquivalent(), end.next(CannotCrossEditingBoundary), listTag);
344    RefPtr<HTMLElement> listElement;
345    if (previousList)
346        appendNode(listItemElement, previousList);
347    else if (nextList)
348        insertNodeAt(listItemElement, positionBeforeNode(nextList));
349    else {
350        // Create the list.
351        listElement = createHTMLElement(document(), listTag);
352        appendNode(listItemElement, listElement);
353
354        if (start == end && isBlock(start.deepEquivalent().deprecatedNode())) {
355            // Inserting the list into an empty paragraph that isn't held open
356            // by a br or a '\n', will invalidate start and end.  Insert
357            // a placeholder and then recompute start and end.
358            RefPtr<Node> placeholder = insertBlockPlaceholder(start.deepEquivalent());
359            start = positionBeforeNode(placeholder.get());
360            end = start;
361        }
362
363        // Insert the list at a position visually equivalent to start of the
364        // paragraph that is being moved into the list.
365        // Try to avoid inserting it somewhere where it will be surrounded by
366        // inline ancestors of start, since it is easier for editing to produce
367        // clean markup when inline elements are pushed down as far as possible.
368        Position insertionPos(start.deepEquivalent().upstream());
369        // Also avoid the containing list item.
370        Node* listChild = enclosingListChild(insertionPos.deprecatedNode());
371        if (listChild && listChild->hasTagName(liTag))
372            insertionPos = positionInParentBeforeNode(listChild);
373
374        insertNodeAt(listElement, insertionPos);
375
376        // We inserted the list at the start of the content we're about to move
377        // Update the start of content, so we don't try to move the list into itself.  bug 19066
378        // Layout is necessary since start's node's inline renderers may have been destroyed by the insertion
379        if (insertionPos == start.deepEquivalent()) {
380            listElement->document()->updateLayoutIgnorePendingStylesheets();
381            start = startOfParagraph(originalStart, CanSkipOverEditingBoundary);
382        }
383    }
384
385    moveParagraph(start, end, positionBeforeNode(placeholder.get()), true);
386
387    if (listElement)
388        return mergeWithNeighboringLists(listElement);
389
390    if (canMergeLists(previousList, nextList))
391        mergeIdenticalElements(previousList, nextList);
392
393    return listElement;
394}
395
396}
397