• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/*
2 * Copyright (C) 2007 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 *
8 * 1.  Redistributions of source code must retain the above copyright
9 *     notice, this list of conditions and the following disclaimer.
10 * 2.  Redistributions in binary form must reproduce the above copyright
11 *     notice, this list of conditions and the following disclaimer in the
12 *     documentation and/or other materials provided with the distribution.
13 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14 *     its contributors may be used to endorse or promote products derived
15 *     from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/**
30 * @constructor
31 * @param {!Element} listNode
32 * @param {boolean=} nonFocusable
33 */
34function TreeOutline(listNode, nonFocusable)
35{
36    /** @type {!Array.<!TreeElement>} */
37    this.children = [];
38    this.selectedTreeElement = null;
39    this._childrenListNode = listNode;
40    this.childrenListElement = this._childrenListNode;
41    this._childrenListNode.removeChildren();
42    this.expandTreeElementsWhenArrowing = false;
43    this.root = true;
44    this.hasChildren = false;
45    this.expanded = true;
46    this.selected = false;
47    this.treeOutline = this;
48    /** @type {?function(!TreeElement, !TreeElement):number} */
49    this.comparator = null;
50
51    this.setFocusable(!nonFocusable);
52    this._childrenListNode.addEventListener("keydown", this._treeKeyDown.bind(this), true);
53
54    /** @type {!Map.<!Object, !Array.<!TreeElement>>} */
55    this._treeElementsMap = new Map();
56    /** @type {!Map.<!Object, boolean>} */
57    this._expandedStateMap = new Map();
58}
59
60TreeOutline.prototype.setFocusable = function(focusable)
61{
62    if (focusable)
63        this._childrenListNode.setAttribute("tabIndex", 0);
64    else
65        this._childrenListNode.removeAttribute("tabIndex");
66}
67
68/**
69 * @param {!TreeElement} child
70 */
71TreeOutline.prototype.appendChild = function(child)
72{
73    var insertionIndex;
74    if (this.treeOutline.comparator)
75        insertionIndex = insertionIndexForObjectInListSortedByFunction(child, this.children, this.treeOutline.comparator);
76    else
77        insertionIndex = this.children.length;
78    this.insertChild(child, insertionIndex);
79}
80
81/**
82 * @param {!TreeElement} child
83 * @param {!TreeElement} beforeChild
84 */
85TreeOutline.prototype.insertBeforeChild = function(child, beforeChild)
86{
87    if (!child)
88        throw("child can't be undefined or null");
89
90    if (!beforeChild)
91        throw("beforeChild can't be undefined or null");
92
93    var childIndex = this.children.indexOf(beforeChild);
94    if (childIndex === -1)
95        throw("beforeChild not found in this node's children");
96
97    this.insertChild(child, childIndex);
98}
99
100/**
101 * @param {!TreeElement} child
102 * @param {number} index
103 */
104TreeOutline.prototype.insertChild = function(child, index)
105{
106    if (!child)
107        throw("child can't be undefined or null");
108
109    var previousChild = (index > 0 ? this.children[index - 1] : null);
110    if (previousChild) {
111        previousChild.nextSibling = child;
112        child.previousSibling = previousChild;
113    } else {
114        child.previousSibling = null;
115    }
116
117    var nextChild = this.children[index];
118    if (nextChild) {
119        nextChild.previousSibling = child;
120        child.nextSibling = nextChild;
121    } else {
122        child.nextSibling = null;
123    }
124
125    this.children.splice(index, 0, child);
126    this.hasChildren = true;
127    child.parent = this;
128    child.treeOutline = this.treeOutline;
129    child.treeOutline._rememberTreeElement(child);
130
131    var current = child.children[0];
132    while (current) {
133        current.treeOutline = this.treeOutline;
134        current.treeOutline._rememberTreeElement(current);
135        current = current.traverseNextTreeElement(false, child, true);
136    }
137
138    if (child.hasChildren && typeof(child.treeOutline._expandedStateMap.get(child.representedObject)) !== "undefined")
139        child.expanded = child.treeOutline._expandedStateMap.get(child.representedObject);
140
141    if (!this._childrenListNode) {
142        this._childrenListNode = this.treeOutline._childrenListNode.ownerDocument.createElement("ol");
143        this._childrenListNode.parentTreeElement = this;
144        this._childrenListNode.classList.add("children");
145        if (this.hidden)
146            this._childrenListNode.classList.add("hidden");
147    }
148
149    child._attach();
150}
151
152/**
153 * @param {number} childIndex
154 */
155TreeOutline.prototype.removeChildAtIndex = function(childIndex)
156{
157    if (childIndex < 0 || childIndex >= this.children.length)
158        throw("childIndex out of range");
159
160    var child = this.children[childIndex];
161    this.children.splice(childIndex, 1);
162
163    var parent = child.parent;
164    if (child.deselect()) {
165        if (child.previousSibling)
166            child.previousSibling.select();
167        else if (child.nextSibling)
168            child.nextSibling.select();
169        else
170            parent.select();
171    }
172
173    if (child.previousSibling)
174        child.previousSibling.nextSibling = child.nextSibling;
175    if (child.nextSibling)
176        child.nextSibling.previousSibling = child.previousSibling;
177
178    if (child.treeOutline) {
179        child.treeOutline._forgetTreeElement(child);
180        child.treeOutline._forgetChildrenRecursive(child);
181    }
182
183    child._detach();
184    child.treeOutline = null;
185    child.parent = null;
186    child.nextSibling = null;
187    child.previousSibling = null;
188}
189
190/**
191 * @param {!TreeElement} child
192 */
193TreeOutline.prototype.removeChild = function(child)
194{
195    if (!child)
196        throw("child can't be undefined or null");
197
198    var childIndex = this.children.indexOf(child);
199    if (childIndex === -1)
200        throw("child not found in this node's children");
201
202    this.removeChildAtIndex.call(this, childIndex);
203}
204
205TreeOutline.prototype.removeChildren = function()
206{
207    for (var i = 0; i < this.children.length; ++i) {
208        var child = this.children[i];
209        child.deselect();
210
211        if (child.treeOutline) {
212            child.treeOutline._forgetTreeElement(child);
213            child.treeOutline._forgetChildrenRecursive(child);
214        }
215
216        child._detach();
217        child.treeOutline = null;
218        child.parent = null;
219        child.nextSibling = null;
220        child.previousSibling = null;
221    }
222
223    this.children = [];
224}
225
226/**
227 * @param {!TreeElement} element
228 */
229TreeOutline.prototype._rememberTreeElement = function(element)
230{
231    if (!this._treeElementsMap.get(element.representedObject))
232        this._treeElementsMap.put(element.representedObject, []);
233
234    // check if the element is already known
235    var elements = this._treeElementsMap.get(element.representedObject);
236    if (elements.indexOf(element) !== -1)
237        return;
238
239    // add the element
240    elements.push(element);
241}
242
243/**
244 * @param {!TreeElement} element
245 */
246TreeOutline.prototype._forgetTreeElement = function(element)
247{
248    if (this._treeElementsMap.get(element.representedObject)) {
249        var elements = this._treeElementsMap.get(element.representedObject);
250        elements.remove(element, true);
251        if (!elements.length)
252            this._treeElementsMap.remove(element.representedObject);
253    }
254}
255
256/**
257 * @param {!TreeElement} parentElement
258 */
259TreeOutline.prototype._forgetChildrenRecursive = function(parentElement)
260{
261    var child = parentElement.children[0];
262    while (child) {
263        this._forgetTreeElement(child);
264        child = child.traverseNextTreeElement(false, parentElement, true);
265    }
266}
267
268/**
269 * @param {?Object} representedObject
270 * @return {?TreeElement}
271 */
272TreeOutline.prototype.getCachedTreeElement = function(representedObject)
273{
274    if (!representedObject)
275        return null;
276
277    var elements = this._treeElementsMap.get(representedObject);
278    if (elements && elements.length)
279        return elements[0];
280    return null;
281}
282
283/**
284 * @param {?Object} representedObject
285 * @return {?TreeElement}
286 */
287TreeOutline.prototype.findTreeElement = function(representedObject, isAncestor, getParent)
288{
289    if (!representedObject)
290        return null;
291
292    var cachedElement = this.getCachedTreeElement(representedObject);
293    if (cachedElement)
294        return cachedElement;
295
296    // Walk up the parent pointers from the desired representedObject
297    var ancestors = [];
298    for (var currentObject = getParent(representedObject); currentObject;  currentObject = getParent(currentObject)) {
299        ancestors.push(currentObject);
300        if (this.getCachedTreeElement(currentObject))  // stop climbing as soon as we hit
301            break;
302    }
303
304    if (!currentObject)
305        return null;
306
307    // Walk down to populate each ancestor's children, to fill in the tree and the cache.
308    for (var i = ancestors.length - 1; i >= 0; --i) {
309        var treeElement = this.getCachedTreeElement(ancestors[i]);
310        if (treeElement)
311            treeElement.onpopulate();  // fill the cache with the children of treeElement
312    }
313
314    return this.getCachedTreeElement(representedObject);
315}
316
317/**
318 * @param {number} x
319 * @param {number} y
320 * @return {?TreeElement}
321 */
322TreeOutline.prototype.treeElementFromPoint = function(x, y)
323{
324    var node = this._childrenListNode.ownerDocument.elementFromPoint(x, y);
325    if (!node)
326        return null;
327
328    var listNode = node.enclosingNodeOrSelfWithNodeNameInArray(["ol", "li"]);
329    if (listNode)
330        return listNode.parentTreeElement || listNode.treeElement;
331    return null;
332}
333
334TreeOutline.prototype._treeKeyDown = function(event)
335{
336    if (event.target !== this._childrenListNode)
337        return;
338
339    if (!this.selectedTreeElement || event.shiftKey || event.metaKey || event.ctrlKey)
340        return;
341
342    var handled = false;
343    var nextSelectedElement;
344    if (event.keyIdentifier === "Up" && !event.altKey) {
345        nextSelectedElement = this.selectedTreeElement.traversePreviousTreeElement(true);
346        while (nextSelectedElement && !nextSelectedElement.selectable)
347            nextSelectedElement = nextSelectedElement.traversePreviousTreeElement(!this.expandTreeElementsWhenArrowing);
348        handled = nextSelectedElement ? true : false;
349    } else if (event.keyIdentifier === "Down" && !event.altKey) {
350        nextSelectedElement = this.selectedTreeElement.traverseNextTreeElement(true);
351        while (nextSelectedElement && !nextSelectedElement.selectable)
352            nextSelectedElement = nextSelectedElement.traverseNextTreeElement(!this.expandTreeElementsWhenArrowing);
353        handled = nextSelectedElement ? true : false;
354    } else if (event.keyIdentifier === "Left") {
355        if (this.selectedTreeElement.expanded) {
356            if (event.altKey)
357                this.selectedTreeElement.collapseRecursively();
358            else
359                this.selectedTreeElement.collapse();
360            handled = true;
361        } else if (this.selectedTreeElement.parent && !this.selectedTreeElement.parent.root) {
362            handled = true;
363            if (this.selectedTreeElement.parent.selectable) {
364                nextSelectedElement = this.selectedTreeElement.parent;
365                while (nextSelectedElement && !nextSelectedElement.selectable)
366                    nextSelectedElement = nextSelectedElement.parent;
367                handled = nextSelectedElement ? true : false;
368            } else if (this.selectedTreeElement.parent)
369                this.selectedTreeElement.parent.collapse();
370        }
371    } else if (event.keyIdentifier === "Right") {
372        if (!this.selectedTreeElement.revealed()) {
373            this.selectedTreeElement.reveal();
374            handled = true;
375        } else if (this.selectedTreeElement.hasChildren) {
376            handled = true;
377            if (this.selectedTreeElement.expanded) {
378                nextSelectedElement = this.selectedTreeElement.children[0];
379                while (nextSelectedElement && !nextSelectedElement.selectable)
380                    nextSelectedElement = nextSelectedElement.nextSibling;
381                handled = nextSelectedElement ? true : false;
382            } else {
383                if (event.altKey)
384                    this.selectedTreeElement.expandRecursively();
385                else
386                    this.selectedTreeElement.expand();
387            }
388        }
389    } else if (event.keyCode === 8 /* Backspace */ || event.keyCode === 46 /* Delete */)
390        handled = this.selectedTreeElement.ondelete();
391    else if (isEnterKey(event))
392        handled = this.selectedTreeElement.onenter();
393    else if (event.keyCode === WebInspector.KeyboardShortcut.Keys.Space.code)
394        handled = this.selectedTreeElement.onspace();
395
396    if (nextSelectedElement) {
397        nextSelectedElement.reveal();
398        nextSelectedElement.select(false, true);
399    }
400
401    if (handled)
402        event.consume(true);
403}
404
405TreeOutline.prototype.expand = function()
406{
407    // this is the root, do nothing
408}
409
410TreeOutline.prototype.collapse = function()
411{
412    // this is the root, do nothing
413}
414
415TreeOutline.prototype.revealed = function()
416{
417    return true;
418}
419
420TreeOutline.prototype.reveal = function()
421{
422    // this is the root, do nothing
423}
424
425TreeOutline.prototype.select = function()
426{
427    // this is the root, do nothing
428}
429
430/**
431 * @param {boolean=} omitFocus
432 */
433TreeOutline.prototype.revealAndSelect = function(omitFocus)
434{
435    // this is the root, do nothing
436}
437
438/**
439 * @constructor
440 * @param {string|!Node} title
441 * @param {?Object=} representedObject
442 * @param {boolean=} hasChildren
443 */
444function TreeElement(title, representedObject, hasChildren)
445{
446    this._title = title;
447    this.representedObject = (representedObject || {});
448
449    this.root = false;
450    this._hidden = false;
451    this._selectable = true;
452    this.expanded = false;
453    this.selected = false;
454    this.hasChildren = hasChildren;
455    this.children = [];
456    this.treeOutline = null;
457    this.parent = null;
458    this.previousSibling = null;
459    this.nextSibling = null;
460    this._listItemNode = null;
461}
462
463TreeElement.prototype = {
464    arrowToggleWidth: 10,
465
466    get selectable() {
467        if (this._hidden)
468            return false;
469        return this._selectable;
470    },
471
472    set selectable(x) {
473        this._selectable = x;
474    },
475
476    get listItemElement() {
477        return this._listItemNode;
478    },
479
480    get childrenListElement() {
481        return this._childrenListNode;
482    },
483
484    get title() {
485        return this._title;
486    },
487
488    set title(x) {
489        this._title = x;
490        this._setListItemNodeContent();
491    },
492
493    get tooltip() {
494        return this._tooltip;
495    },
496
497    set tooltip(x) {
498        this._tooltip = x;
499        if (this._listItemNode)
500            this._listItemNode.title = x ? x : "";
501    },
502
503    get hasChildren() {
504        return this._hasChildren;
505    },
506
507    set hasChildren(x) {
508        if (this._hasChildren === x)
509            return;
510
511        this._hasChildren = x;
512
513        if (!this._listItemNode)
514            return;
515
516        if (x)
517            this._listItemNode.classList.add("parent");
518        else {
519            this._listItemNode.classList.remove("parent");
520            this.collapse();
521        }
522    },
523
524    get hidden() {
525        return this._hidden;
526    },
527
528    set hidden(x) {
529        if (this._hidden === x)
530            return;
531
532        this._hidden = x;
533
534        if (x) {
535            if (this._listItemNode)
536                this._listItemNode.classList.add("hidden");
537            if (this._childrenListNode)
538                this._childrenListNode.classList.add("hidden");
539        } else {
540            if (this._listItemNode)
541                this._listItemNode.classList.remove("hidden");
542            if (this._childrenListNode)
543                this._childrenListNode.classList.remove("hidden");
544        }
545    },
546
547    get shouldRefreshChildren() {
548        return this._shouldRefreshChildren;
549    },
550
551    set shouldRefreshChildren(x) {
552        this._shouldRefreshChildren = x;
553        if (x && this.expanded)
554            this.expand();
555    },
556
557    _setListItemNodeContent: function()
558    {
559        if (!this._listItemNode)
560            return;
561
562        if (typeof this._title === "string")
563            this._listItemNode.textContent = this._title;
564        else {
565            this._listItemNode.removeChildren();
566            if (this._title)
567                this._listItemNode.appendChild(this._title);
568        }
569    }
570}
571
572TreeElement.prototype.appendChild = TreeOutline.prototype.appendChild;
573TreeElement.prototype.insertChild = TreeOutline.prototype.insertChild;
574TreeElement.prototype.insertBeforeChild = TreeOutline.prototype.insertBeforeChild;
575TreeElement.prototype.removeChild = TreeOutline.prototype.removeChild;
576TreeElement.prototype.removeChildAtIndex = TreeOutline.prototype.removeChildAtIndex;
577TreeElement.prototype.removeChildren = TreeOutline.prototype.removeChildren;
578
579TreeElement.prototype._attach = function()
580{
581    if (!this._listItemNode || this.parent._shouldRefreshChildren) {
582        if (this._listItemNode && this._listItemNode.parentNode)
583            this._listItemNode.parentNode.removeChild(this._listItemNode);
584
585        this._listItemNode = this.treeOutline._childrenListNode.ownerDocument.createElement("li");
586        this._listItemNode.treeElement = this;
587        this._setListItemNodeContent();
588        this._listItemNode.title = this._tooltip ? this._tooltip : "";
589
590        if (this.hidden)
591            this._listItemNode.classList.add("hidden");
592        if (this.hasChildren)
593            this._listItemNode.classList.add("parent");
594        if (this.expanded)
595            this._listItemNode.classList.add("expanded");
596        if (this.selected)
597            this._listItemNode.classList.add("selected");
598
599        this._listItemNode.addEventListener("mousedown", TreeElement.treeElementMouseDown, false);
600        this._listItemNode.addEventListener("click", TreeElement.treeElementToggled, false);
601        this._listItemNode.addEventListener("dblclick", TreeElement.treeElementDoubleClicked, false);
602
603        this.onattach();
604    }
605
606    var nextSibling = null;
607    if (this.nextSibling && this.nextSibling._listItemNode && this.nextSibling._listItemNode.parentNode === this.parent._childrenListNode)
608        nextSibling = this.nextSibling._listItemNode;
609    this.parent._childrenListNode.insertBefore(this._listItemNode, nextSibling);
610    if (this._childrenListNode)
611        this.parent._childrenListNode.insertBefore(this._childrenListNode, this._listItemNode.nextSibling);
612    if (this.selected)
613        this.select();
614    if (this.expanded)
615        this.expand();
616}
617
618TreeElement.prototype._detach = function()
619{
620    if (this._listItemNode && this._listItemNode.parentNode)
621        this._listItemNode.parentNode.removeChild(this._listItemNode);
622    if (this._childrenListNode && this._childrenListNode.parentNode)
623        this._childrenListNode.parentNode.removeChild(this._childrenListNode);
624}
625
626TreeElement.treeElementMouseDown = function(event)
627{
628    var element = event.currentTarget;
629    if (!element || !element.treeElement || !element.treeElement.selectable)
630        return;
631
632    if (element.treeElement.isEventWithinDisclosureTriangle(event))
633        return;
634
635    element.treeElement.selectOnMouseDown(event);
636}
637
638TreeElement.treeElementToggled = function(event)
639{
640    var element = event.currentTarget;
641    if (!element || !element.treeElement)
642        return;
643
644    var toggleOnClick = element.treeElement.toggleOnClick && !element.treeElement.selectable;
645    var isInTriangle = element.treeElement.isEventWithinDisclosureTriangle(event);
646    if (!toggleOnClick && !isInTriangle)
647        return;
648
649    if (element.treeElement.expanded) {
650        if (event.altKey)
651            element.treeElement.collapseRecursively();
652        else
653            element.treeElement.collapse();
654    } else {
655        if (event.altKey)
656            element.treeElement.expandRecursively();
657        else
658            element.treeElement.expand();
659    }
660    event.consume();
661}
662
663TreeElement.treeElementDoubleClicked = function(event)
664{
665    var element = event.currentTarget;
666    if (!element || !element.treeElement)
667        return;
668
669    var handled = element.treeElement.ondblclick.call(element.treeElement, event);
670    if (handled)
671        return;
672    if (element.treeElement.hasChildren && !element.treeElement.expanded)
673        element.treeElement.expand();
674}
675
676TreeElement.prototype.collapse = function()
677{
678    if (this._listItemNode)
679        this._listItemNode.classList.remove("expanded");
680    if (this._childrenListNode)
681        this._childrenListNode.classList.remove("expanded");
682
683    this.expanded = false;
684
685    if (this.treeOutline)
686        this.treeOutline._expandedStateMap.put(this.representedObject, false);
687
688    this.oncollapse();
689}
690
691TreeElement.prototype.collapseRecursively = function()
692{
693    var item = this;
694    while (item) {
695        if (item.expanded)
696            item.collapse();
697        item = item.traverseNextTreeElement(false, this, true);
698    }
699}
700
701TreeElement.prototype.expand = function()
702{
703    if (!this.hasChildren || (this.expanded && !this._shouldRefreshChildren && this._childrenListNode))
704        return;
705
706    // Set this before onpopulate. Since onpopulate can add elements, this makes
707    // sure the expanded flag is true before calling those functions. This prevents the possibility
708    // of an infinite loop if onpopulate were to call expand.
709
710    this.expanded = true;
711    if (this.treeOutline)
712        this.treeOutline._expandedStateMap.put(this.representedObject, true);
713
714    if (this.treeOutline && (!this._childrenListNode || this._shouldRefreshChildren)) {
715        if (this._childrenListNode && this._childrenListNode.parentNode)
716            this._childrenListNode.parentNode.removeChild(this._childrenListNode);
717
718        this._childrenListNode = this.treeOutline._childrenListNode.ownerDocument.createElement("ol");
719        this._childrenListNode.parentTreeElement = this;
720        this._childrenListNode.classList.add("children");
721
722        if (this.hidden)
723            this._childrenListNode.classList.add("hidden");
724
725        this.onpopulate();
726
727        for (var i = 0; i < this.children.length; ++i)
728            this.children[i]._attach();
729
730        delete this._shouldRefreshChildren;
731    }
732
733    if (this._listItemNode) {
734        this._listItemNode.classList.add("expanded");
735        if (this._childrenListNode && this._childrenListNode.parentNode != this._listItemNode.parentNode)
736            this.parent._childrenListNode.insertBefore(this._childrenListNode, this._listItemNode.nextSibling);
737    }
738
739    if (this._childrenListNode)
740        this._childrenListNode.classList.add("expanded");
741
742    this.onexpand();
743}
744
745TreeElement.prototype.expandRecursively = function(maxDepth)
746{
747    var item = this;
748    var info = {};
749    var depth = 0;
750
751    // The Inspector uses TreeOutlines to represents object properties, so recursive expansion
752    // in some case can be infinite, since JavaScript objects can hold circular references.
753    // So default to a recursion cap of 3 levels, since that gives fairly good results.
754    if (isNaN(maxDepth))
755        maxDepth = 3;
756
757    while (item) {
758        if (depth < maxDepth)
759            item.expand();
760        item = item.traverseNextTreeElement(false, this, (depth >= maxDepth), info);
761        depth += info.depthChange;
762    }
763}
764
765TreeElement.prototype.hasAncestor = function(ancestor) {
766    if (!ancestor)
767        return false;
768
769    var currentNode = this.parent;
770    while (currentNode) {
771        if (ancestor === currentNode)
772            return true;
773        currentNode = currentNode.parent;
774    }
775
776    return false;
777}
778
779TreeElement.prototype.reveal = function()
780{
781    var currentAncestor = this.parent;
782    while (currentAncestor && !currentAncestor.root) {
783        if (!currentAncestor.expanded)
784            currentAncestor.expand();
785        currentAncestor = currentAncestor.parent;
786    }
787
788    this.onreveal();
789}
790
791TreeElement.prototype.revealed = function()
792{
793    var currentAncestor = this.parent;
794    while (currentAncestor && !currentAncestor.root) {
795        if (!currentAncestor.expanded)
796            return false;
797        currentAncestor = currentAncestor.parent;
798    }
799
800    return true;
801}
802
803TreeElement.prototype.selectOnMouseDown = function(event)
804{
805    if (this.select(false, true))
806        event.consume(true);
807}
808
809/**
810 * @param {boolean=} omitFocus
811 * @param {boolean=} selectedByUser
812 * @return {boolean}
813 */
814TreeElement.prototype.select = function(omitFocus, selectedByUser)
815{
816    if (!this.treeOutline || !this.selectable || this.selected)
817        return false;
818
819    if (this.treeOutline.selectedTreeElement)
820        this.treeOutline.selectedTreeElement.deselect();
821
822    this.selected = true;
823
824    if (!omitFocus)
825        this.treeOutline._childrenListNode.focus();
826
827    // Focusing on another node may detach "this" from tree.
828    if (!this.treeOutline)
829        return false;
830    this.treeOutline.selectedTreeElement = this;
831    if (this._listItemNode)
832        this._listItemNode.classList.add("selected");
833
834    return this.onselect(selectedByUser);
835}
836
837/**
838 * @param {boolean=} omitFocus
839 */
840TreeElement.prototype.revealAndSelect = function(omitFocus)
841{
842    this.reveal();
843    this.select(omitFocus);
844}
845
846/**
847 * @param {boolean=} supressOnDeselect
848 */
849TreeElement.prototype.deselect = function(supressOnDeselect)
850{
851    if (!this.treeOutline || this.treeOutline.selectedTreeElement !== this || !this.selected)
852        return false;
853
854    this.selected = false;
855    this.treeOutline.selectedTreeElement = null;
856    if (this._listItemNode)
857        this._listItemNode.classList.remove("selected");
858    return true;
859}
860
861// Overridden by subclasses.
862TreeElement.prototype.onpopulate = function() { }
863
864/**
865 * @return {boolean}
866 */
867TreeElement.prototype.onenter = function() { return false; }
868
869/**
870 * @return {boolean}
871 */
872TreeElement.prototype.ondelete = function() { return false; }
873
874/**
875 * @return {boolean}
876 */
877TreeElement.prototype.onspace = function() { return false; }
878
879TreeElement.prototype.onattach = function() { }
880
881TreeElement.prototype.onexpand = function() { }
882
883TreeElement.prototype.oncollapse = function() { }
884
885/**
886 * @param {!MouseEvent} e
887 * @return {boolean}
888 */
889TreeElement.prototype.ondblclick = function(e) { return false; }
890
891TreeElement.prototype.onreveal = function() { }
892
893/**
894 * @param {boolean=} selectedByUser
895 * @return {boolean}
896 */
897TreeElement.prototype.onselect = function(selectedByUser) { return false; }
898
899/**
900 * @param {boolean} skipUnrevealed
901 * @param {(!TreeOutline|!TreeElement|null)=} stayWithin
902 * @param {boolean=} dontPopulate
903 * @param {!Object=} info
904 * @return {?TreeElement}
905 */
906TreeElement.prototype.traverseNextTreeElement = function(skipUnrevealed, stayWithin, dontPopulate, info)
907{
908    if (!dontPopulate && this.hasChildren)
909        this.onpopulate();
910
911    if (info)
912        info.depthChange = 0;
913
914    var element = skipUnrevealed ? (this.revealed() ? this.children[0] : null) : this.children[0];
915    if (element && (!skipUnrevealed || (skipUnrevealed && this.expanded))) {
916        if (info)
917            info.depthChange = 1;
918        return element;
919    }
920
921    if (this === stayWithin)
922        return null;
923
924    element = skipUnrevealed ? (this.revealed() ? this.nextSibling : null) : this.nextSibling;
925    if (element)
926        return element;
927
928    element = this;
929    while (element && !element.root && !(skipUnrevealed ? (element.revealed() ? element.nextSibling : null) : element.nextSibling) && element.parent !== stayWithin) {
930        if (info)
931            info.depthChange -= 1;
932        element = element.parent;
933    }
934
935    if (!element)
936        return null;
937
938    return (skipUnrevealed ? (element.revealed() ? element.nextSibling : null) : element.nextSibling);
939}
940
941/**
942 * @param {boolean} skipUnrevealed
943 * @param {boolean=} dontPopulate
944 * @return {?TreeElement}
945 */
946TreeElement.prototype.traversePreviousTreeElement = function(skipUnrevealed, dontPopulate)
947{
948    var element = skipUnrevealed ? (this.revealed() ? this.previousSibling : null) : this.previousSibling;
949    if (!dontPopulate && element && element.hasChildren)
950        element.onpopulate();
951
952    while (element && (skipUnrevealed ? (element.revealed() && element.expanded ? element.children[element.children.length - 1] : null) : element.children[element.children.length - 1])) {
953        if (!dontPopulate && element.hasChildren)
954            element.onpopulate();
955        element = (skipUnrevealed ? (element.revealed() && element.expanded ? element.children[element.children.length - 1] : null) : element.children[element.children.length - 1]);
956    }
957
958    if (element)
959        return element;
960
961    if (!this.parent || this.parent.root)
962        return null;
963
964    return this.parent;
965}
966
967TreeElement.prototype.isEventWithinDisclosureTriangle = function(event)
968{
969    // FIXME: We should not use getComputedStyle(). For that we need to get rid of using ::before for disclosure triangle. (http://webk.it/74446)
970    var paddingLeftValue = window.getComputedStyle(this._listItemNode).getPropertyCSSValue("padding-left");
971    var computedLeftPadding = paddingLeftValue ? paddingLeftValue.getFloatValue(CSSPrimitiveValue.CSS_PX) : 0;
972    var left = this._listItemNode.totalOffsetLeft() + computedLeftPadding;
973    return event.pageX >= left && event.pageX <= left + this.arrowToggleWidth && this.hasChildren;
974}
975