2015-07-06 21:06:30 +00:00
|
|
|
/*
|
|
|
|
* Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
|
|
|
|
*
|
|
|
|
* Redistribution and use in source and binary forms, with or without
|
|
|
|
* modification, are permitted provided that the following conditions
|
|
|
|
* are met:
|
|
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
|
|
* notice, this list of conditions and the following disclaimer.
|
|
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
|
|
* documentation and/or other materials provided with the distribution.
|
|
|
|
*
|
|
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
|
|
|
|
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
|
|
|
|
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
|
|
|
|
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
|
|
|
|
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
|
|
|
|
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
|
|
|
|
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
|
|
|
|
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
|
|
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
|
|
|
|
* THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
*/
|
|
|
|
|
|
|
|
#include "config.h"
|
|
|
|
#include "DFANode.h"
|
|
|
|
|
|
|
|
#include "DFA.h"
|
Non-unified build fixes, late-ish May 2021 edition
https://bugs.webkit.org/show_bug.cgi?id=225990
Unreviewed non-unified build fixes.
Source/JavaScriptCore:
* jit/CCallHelpers.cpp: Add missing LinkBuffer.h header.
Source/WebCore:
No new tests needed.
* Modules/indexeddb/server/MemoryObjectStore.cpp: Add missing pal/SessioID.h header.
* Modules/webaudio/OfflineAudioContext.cpp: Add missing OfflineAudioCompletionEvent.h header.
* Modules/webaudio/OfflineAudioContext.h: Add missing wtf/UniqueRef.h header.
* Modules/websockets/WebSocketDeflateFramer.h: Add missing WebSocketExtensionProcessor.h
header, remove wtf/text/WTFString.h as it is already included by the former.
* bindings/js/JSDOMConvertEnumeration.h: Add missing JSDOMGlobalObject.h header.
* contentextensions/DFANode.cpp: Add missing wtf/HashMap.h header.
* html/HTMLFrameElement.cpp: Add missing HTMLParserIdioms.h header.
* html/HTMLHRElement.cpp: Ditto.
* html/HTMLIFrameElement.cpp: Ditto.
* html/HTMLLIElement.cpp: Ditto.
* html/HTMLMetaElement.cpp: Add missing HTMLParserIdioms.h, Frame.h, and FrameView.h headers.
* html/HTMLOutputElement.cpp:
(WebCore::HTMLOutputElement::parseAttribute): Add missing HTMLNames:: namespace prefix in
usage of HTMLNames::forAttr.
(WebCore::HTMLOutputElement::htmlFor): Ditto.
* html/OffscreenCanvas.cpp: Add missing RuntimeEnabledFeatures.h header.
* layout/formattingContexts/FormattingGeometry.cpp: Add missing FormattingQuirks.h header.
* layout/formattingContexts/FormattingQuirks.cpp: Add missing FormattingGeometry.h header.
* layout/formattingContexts/block/BlockFormattingGeometry.cpp: Add missing
BlockFormattingContext.h, BlockFormattingQuirks.h, and BlockMarginCollapse.h headers;
remove unneeded BlockFormattingState.h and FormattingContext.h headers.
* layout/formattingContexts/block/BlockFormattingGeometry.h: Add missing forward
declaration for BlockFormattingContext.
* layout/formattingContexts/block/BlockFormattingQuirks.cpp: Add missing
BlockFormattingContext.h and BlockMarginCollapse.h headers, remove unneeded
BlockFormattingState.h header.
* layout/formattingContexts/block/PrecomputedBlockMarginCollapse.cpp: Add missing
BlockFormattingContext.h and BlockFormattingQuirks.h headers, remove unneeded
BlockFormattingState.h header.
* layout/formattingContexts/block/tablewrapper/TableWrapperBlockFormattingContext.cpp:
Add missing BlockMarginCollapse.h header.
* layout/formattingContexts/block/tablewrapper/TableWrapperBlockFormattingQuirks.cpp:
Add missing TableWrapperBlockFormattingContext.h header.
* layout/formattingContexts/block/tablewrapper/TableWrapperBlockFormattingQuirks.h:
Add missing forward declaration for TableWrapperBlockFormattingContext.
* layout/formattingContexts/flex/FlexFormattingGeometry.cpp: Add missing
FlexFormattingContext.h header, remove unneeded FlexFormattingState.h and
FormattingContext.h headers.
* layout/formattingContexts/flex/FlexFormattingGeometry.h: Add missing forward declaration
for FlexFormattingContext.
* layout/formattingContexts/inline/InlineFormattingGeometry.cpp: Add missing
InlineFormattingContext.h header, remove unneeded InlineLineBox.h header.
* layout/formattingContexts/inline/InlineFormattingGeometry.h: Add missing InlineLineBox.h
and InlineLineBuilder.h headers, add missing forward declaration for
InlineFormattingContext.
* layout/formattingContexts/inline/InlineFormattingQuirks.cpp: Add missing
InlineFormattingContext.h header.
* layout/formattingContexts/inline/InlineFormattingQuirks.h: Add missing InlineLineBox.h
header, add missing forward declaration for InlineFormattingContext.
* layout/formattingContexts/inline/InlineLineBuilder.cpp: Add missing
InlineFormattingQuirks.h header.
* layout/formattingContexts/table/TableFormattingGeometry.cpp: Add missing
TableFormattingContext.h header, remove unneeded TableFormattingState.h header.
* layout/formattingContexts/table/TableFormattingGeometry.h: Add missing TableGrid.h
header, add missing forward declaration for TableFormattingContext.
* layout/formattingContexts/table/TableFormattingQuirks.cpp: Add missing
TableFormattingContext.h header.
* layout/formattingContexts/table/TableFormattingQuirks.h: Add missing forward declaration
for TableFormattingContext.
* layout/formattingContexts/table/TableLayout.cpp: Add missing TableFormattingGeometry.h
header.
* page/FrameViewLayoutContext.cpp: Add missing StyleScope.h header.
* page/ImageOverlayController.h: Add missing LayoutRect.h header.
* page/PageConfiguration.h: Add missing wtf/HashSet.h header.
* platform/network/soup/SoupNetworkSession.cpp: Add missing wtf/text/StringHash.h header.
* style/StyleScopeRuleSets.cpp: Add missing StyleScope.h header.
* style/Styleable.cpp: Ditto.
* svg/SVGDocumentExtensions.cpp: Add missing SVGUseElement.h header.
* svg/SVGDocumentExtensions.h: Add missing wtf/WeakHashSet.h header, add missing
forward declaration for SVGUseElement.
* workers/WorkerGlobalScope.cpp: Add missing FontCustomPlatformData.h header.
Source/WebKit:
* NetworkProcess/PreconnectTask.h: Add missing forward declaration for NetworkSession.
* NetworkProcess/WebStorage/LocalStorageDatabase.h: Add missing wtf/HashMap.h header,
remove unneeded wtf/RefCounted.h header.
* Shared/WebPageCreationParameters.cpp:
(WebKit::WebPageCreationParameters::decode): Add missing WebCore:: namespace prefix to
usage of WebCore::MediaProducer::MutedStateFlags.
Canonical link: https://commits.webkit.org/238000@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@277858 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2021-05-21 13:52:45 +00:00
|
|
|
#include <wtf/HashMap.h>
|
2015-07-06 21:06:30 +00:00
|
|
|
|
|
|
|
#if ENABLE(CONTENT_EXTENSIONS)
|
|
|
|
|
|
|
|
namespace WebCore {
|
|
|
|
|
|
|
|
namespace ContentExtensions {
|
|
|
|
|
|
|
|
Vector<uint64_t> DFANode::actions(const DFA& dfa) const
|
|
|
|
{
|
|
|
|
// FIXME: Use iterators instead of copying the Vector elements.
|
|
|
|
Vector<uint64_t> vector;
|
|
|
|
vector.reserveInitialCapacity(m_actionsLength);
|
|
|
|
for (uint32_t i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
|
|
|
|
vector.uncheckedAppend(dfa.actions[i]);
|
|
|
|
return vector;
|
|
|
|
}
|
|
|
|
|
|
|
|
bool DFANode::containsTransition(char transition, const DFA& dfa) const
|
|
|
|
{
|
|
|
|
// Called from DFAMinimizer, this loops though a maximum of 128 transitions, so it's not too slow.
|
|
|
|
ASSERT(m_transitionsLength <= 128);
|
|
|
|
for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
|
|
|
|
if (dfa.transitionRanges[i].first <= transition
|
|
|
|
&& dfa.transitionRanges[i].last >= transition)
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
void DFANode::kill(DFA& dfa)
|
|
|
|
{
|
|
|
|
ASSERT(m_flags != IsKilled);
|
|
|
|
m_flags = IsKilled; // Killed nodes don't have any other flags.
|
|
|
|
|
|
|
|
// Invalidate the now-unused memory in the DFA to make finding bugs easier.
|
|
|
|
for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
|
|
|
|
dfa.transitionRanges[i] = { -1, -1 };
|
|
|
|
dfa.transitionDestinations[i] = std::numeric_limits<uint32_t>::max();
|
|
|
|
}
|
|
|
|
for (unsigned i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
|
|
|
|
dfa.actions[i] = std::numeric_limits<uint64_t>::max();
|
|
|
|
|
|
|
|
m_actionsStart = 0;
|
|
|
|
m_actionsLength = 0;
|
|
|
|
m_transitionsStart = 0;
|
|
|
|
m_transitionsLength = 0;
|
|
|
|
};
|
|
|
|
|
|
|
|
bool DFANode::canUseFallbackTransition(const DFA& dfa) const
|
|
|
|
{
|
|
|
|
// Transitions can contain '\0' if the expression has a end-of-line marker.
|
|
|
|
// Fallback transitions cover 1-127. We have to be careful with the first.
|
|
|
|
|
|
|
|
IterableConstRange iterableTransitions = transitions(dfa);
|
|
|
|
auto iterator = iterableTransitions.begin();
|
|
|
|
auto end = iterableTransitions.end();
|
|
|
|
if (iterator == end)
|
|
|
|
return false;
|
|
|
|
|
|
|
|
char lastSeenCharacter = 0;
|
|
|
|
if (!iterator.first()) {
|
|
|
|
lastSeenCharacter = iterator.last();
|
|
|
|
if (lastSeenCharacter == 127)
|
|
|
|
return true;
|
|
|
|
++iterator;
|
|
|
|
}
|
|
|
|
|
|
|
|
for (;iterator != end; ++iterator) {
|
|
|
|
ASSERT(iterator.first() > lastSeenCharacter);
|
|
|
|
if (iterator.first() != lastSeenCharacter + 1)
|
|
|
|
return false;
|
|
|
|
|
|
|
|
if (iterator.range().last == 127)
|
|
|
|
return true;
|
|
|
|
lastSeenCharacter = iterator.last();
|
|
|
|
}
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
uint32_t DFANode::bestFallbackTarget(const DFA& dfa) const
|
|
|
|
{
|
|
|
|
ASSERT(canUseFallbackTransition(dfa));
|
|
|
|
|
2020-07-17 00:33:37 +00:00
|
|
|
HashMap<uint32_t, unsigned, DefaultHash<uint32_t>, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> histogram;
|
2015-07-06 21:06:30 +00:00
|
|
|
|
|
|
|
IterableConstRange iterableTransitions = transitions(dfa);
|
|
|
|
auto iterator = iterableTransitions.begin();
|
|
|
|
auto end = iterableTransitions.end();
|
|
|
|
ASSERT_WITH_MESSAGE(iterator != end, "An empty range list cannot use a fallback transition.");
|
|
|
|
|
|
|
|
if (!iterator.first() && !iterator.last())
|
|
|
|
++iterator;
|
|
|
|
ASSERT_WITH_MESSAGE(iterator != end, "An empty range list matching only zero cannot use a fallback transition.");
|
|
|
|
|
|
|
|
uint32_t bestTarget = iterator.target();
|
|
|
|
unsigned bestTargetScore = !iterator.range().first ? iterator.range().size() - 1 : iterator.range().size();
|
|
|
|
histogram.add(bestTarget, bestTargetScore);
|
|
|
|
++iterator;
|
|
|
|
|
|
|
|
for (;iterator != end; ++iterator) {
|
|
|
|
unsigned rangeSize = iterator.range().size();
|
|
|
|
uint32_t target = iterator.target();
|
|
|
|
auto addResult = histogram.add(target, rangeSize);
|
|
|
|
if (!addResult.isNewEntry)
|
|
|
|
addResult.iterator->value += rangeSize;
|
|
|
|
if (addResult.iterator->value > bestTargetScore) {
|
|
|
|
bestTargetScore = addResult.iterator->value;
|
|
|
|
bestTarget = target;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return bestTarget;
|
|
|
|
}
|
|
|
|
|
|
|
|
} // namespace ContentExtensions
|
|
|
|
|
|
|
|
} // namespace WebCore
|
|
|
|
|
|
|
|
#endif // ENABLE(CONTENT_EXTENSIONS)
|