1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/layout/style/CSSVariableResolver.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,263 @@
1.4 +/* vim: set shiftwidth=2 tabstop=8 autoindent cindent expandtab: */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +/* object that resolves CSS variables using specified and inherited variable
1.10 + * values
1.11 + */
1.12 +
1.13 +#include "CSSVariableResolver.h"
1.14 +
1.15 +#include "CSSVariableDeclarations.h"
1.16 +#include "CSSVariableValues.h"
1.17 +#include "mozilla/PodOperations.h"
1.18 +#include <algorithm>
1.19 +
1.20 +namespace mozilla {
1.21 +
1.22 +/**
1.23 + * Data used by the EnumerateVariableReferences callback. Reset must be called
1.24 + * on it before it is used.
1.25 + */
1.26 +class EnumerateVariableReferencesData
1.27 +{
1.28 +public:
1.29 + EnumerateVariableReferencesData(CSSVariableResolver& aResolver)
1.30 + : mResolver(aResolver)
1.31 + , mReferences(new bool[aResolver.mVariables.Length()])
1.32 + {
1.33 + }
1.34 +
1.35 + /**
1.36 + * Resets the data so that it can be passed to another call of
1.37 + * EnumerateVariableReferences for a different variable.
1.38 + */
1.39 + void Reset()
1.40 + {
1.41 + PodZero(mReferences.get(), mResolver.mVariables.Length());
1.42 + mReferencesNonExistentVariable = false;
1.43 + }
1.44 +
1.45 + void RecordVariableReference(const nsAString& aVariableName)
1.46 + {
1.47 + size_t id;
1.48 + if (mResolver.mVariableIDs.Get(aVariableName, &id)) {
1.49 + mReferences[id] = true;
1.50 + } else {
1.51 + mReferencesNonExistentVariable = true;
1.52 + }
1.53 + }
1.54 +
1.55 + bool HasReferenceToVariable(size_t aID) const
1.56 + {
1.57 + return mReferences[aID];
1.58 + }
1.59 +
1.60 + bool ReferencesNonExistentVariable() const
1.61 + {
1.62 + return mReferencesNonExistentVariable;
1.63 + }
1.64 +
1.65 +private:
1.66 + CSSVariableResolver& mResolver;
1.67 +
1.68 + // Array of booleans, where each index is a variable ID. If an element is
1.69 + // true, it indicates that the variable we have called
1.70 + // EnumerateVariableReferences for has a reference to the variable with
1.71 + // that ID.
1.72 + nsAutoArrayPtr<bool> mReferences;
1.73 +
1.74 + // Whether the variable we have called EnumerateVariableReferences for
1.75 + // references a variable that does not exist in the resolver.
1.76 + bool mReferencesNonExistentVariable;
1.77 +};
1.78 +
1.79 +static void
1.80 +RecordVariableReference(const nsAString& aVariableName,
1.81 + void* aData)
1.82 +{
1.83 + static_cast<EnumerateVariableReferencesData*>(aData)->
1.84 + RecordVariableReference(aVariableName);
1.85 +}
1.86 +
1.87 +void
1.88 +CSSVariableResolver::RemoveCycles(size_t v)
1.89 +{
1.90 + mVariables[v].mIndex = mNextIndex;
1.91 + mVariables[v].mLowLink = mNextIndex;
1.92 + mVariables[v].mInStack = true;
1.93 + mStack.AppendElement(v);
1.94 + mNextIndex++;
1.95 +
1.96 + for (size_t i = 0, n = mReferences[v].Length(); i < n; i++) {
1.97 + size_t w = mReferences[v][i];
1.98 + if (!mVariables[w].mIndex) {
1.99 + RemoveCycles(w);
1.100 + mVariables[v].mLowLink = std::min(mVariables[v].mLowLink,
1.101 + mVariables[w].mLowLink);
1.102 + } else if (mVariables[w].mInStack) {
1.103 + mVariables[v].mLowLink = std::min(mVariables[v].mLowLink,
1.104 + mVariables[w].mIndex);
1.105 + }
1.106 + }
1.107 +
1.108 + if (mVariables[v].mLowLink == mVariables[v].mIndex) {
1.109 + if (mStack.LastElement() == v) {
1.110 + // A strongly connected component consisting of a single variable is not
1.111 + // necessarily invalid. We handle variables that reference themselves
1.112 + // earlier, in CSSVariableResolver::Resolve.
1.113 + mVariables[mStack.LastElement()].mInStack = false;
1.114 + mStack.TruncateLength(mStack.Length() - 1);
1.115 + } else {
1.116 + size_t w;
1.117 + do {
1.118 + w = mStack.LastElement();
1.119 + mVariables[w].mValue.Truncate(0);
1.120 + mVariables[w].mInStack = false;
1.121 + mStack.TruncateLength(mStack.Length() - 1);
1.122 + } while (w != v);
1.123 + }
1.124 + }
1.125 +}
1.126 +
1.127 +void
1.128 +CSSVariableResolver::ResolveVariable(size_t aID)
1.129 +{
1.130 + if (mVariables[aID].mValue.IsEmpty() || mVariables[aID].mWasInherited) {
1.131 + // The variable is invalid or was inherited. We can just copy the value
1.132 + // and its first/last token information across.
1.133 + mOutput->Put(mVariables[aID].mVariableName,
1.134 + mVariables[aID].mValue,
1.135 + mVariables[aID].mFirstToken,
1.136 + mVariables[aID].mLastToken);
1.137 + } else {
1.138 + // Otherwise we need to resolve the variable references, after resolving
1.139 + // all of our dependencies first. We do this even for variables that we
1.140 + // know do not reference other variables so that we can find their
1.141 + // first/last token.
1.142 + //
1.143 + // XXX We might want to do this first/last token finding during
1.144 + // EnumerateVariableReferences, so that we can avoid calling
1.145 + // ResolveVariableValue and parsing the value again.
1.146 + for (size_t i = 0, n = mReferences[aID].Length(); i < n; i++) {
1.147 + size_t j = mReferences[aID][i];
1.148 + if (aID != j && !mVariables[j].mResolved) {
1.149 + ResolveVariable(j);
1.150 + }
1.151 + }
1.152 + nsString resolvedValue;
1.153 + nsCSSTokenSerializationType firstToken, lastToken;
1.154 + if (!mParser.ResolveVariableValue(mVariables[aID].mValue, mOutput,
1.155 + resolvedValue, firstToken, lastToken)) {
1.156 + resolvedValue.Truncate(0);
1.157 + }
1.158 + mOutput->Put(mVariables[aID].mVariableName, resolvedValue,
1.159 + firstToken, lastToken);
1.160 + }
1.161 + mVariables[aID].mResolved = true;
1.162 +}
1.163 +
1.164 +void
1.165 +CSSVariableResolver::Resolve(const CSSVariableValues* aInherited,
1.166 + const CSSVariableDeclarations* aSpecified)
1.167 +{
1.168 + MOZ_ASSERT(!mResolved);
1.169 +
1.170 + // The only time we would be worried about having a null aInherited is
1.171 + // for the root, but in that case nsRuleNode::ComputeVariablesData will
1.172 + // happen to pass in whatever we're using as mOutput for aInherited,
1.173 + // which will initially be empty.
1.174 + MOZ_ASSERT(aInherited);
1.175 + MOZ_ASSERT(aSpecified);
1.176 +
1.177 + aInherited->AddVariablesToResolver(this);
1.178 + aSpecified->AddVariablesToResolver(this);
1.179 +
1.180 + // First we look at each variable's value and record which other variables
1.181 + // it references.
1.182 + size_t n = mVariables.Length();
1.183 + mReferences.SetLength(n);
1.184 + EnumerateVariableReferencesData data(*this);
1.185 + for (size_t id = 0; id < n; id++) {
1.186 + data.Reset();
1.187 + if (!mVariables[id].mWasInherited &&
1.188 + !mVariables[id].mValue.IsEmpty()) {
1.189 + if (mParser.EnumerateVariableReferences(mVariables[id].mValue,
1.190 + RecordVariableReference,
1.191 + &data)) {
1.192 + // Convert the boolean array of dependencies in |data| to a list
1.193 + // of dependencies.
1.194 + for (size_t i = 0; i < n; i++) {
1.195 + if (data.HasReferenceToVariable(i)) {
1.196 + mReferences[id].AppendElement(i);
1.197 + }
1.198 + }
1.199 + // If a variable references itself, it is invalid. (RemoveCycles
1.200 + // does not check for cycles consisting of a single variable, so we
1.201 + // check here.)
1.202 + if (data.HasReferenceToVariable(id)) {
1.203 + mVariables[id].mValue.Truncate();
1.204 + }
1.205 + // Also record whether it referenced any variables that don't exist
1.206 + // in the resolver, so that we can ensure we still resolve its value
1.207 + // in ResolveVariable, even though its mReferences list is empty.
1.208 + mVariables[id].mReferencesNonExistentVariable =
1.209 + data.ReferencesNonExistentVariable();
1.210 + } else {
1.211 + MOZ_ASSERT(false, "EnumerateVariableReferences should not have failed "
1.212 + "if we previously parsed the specified value");
1.213 + mVariables[id].mValue.Truncate(0);
1.214 + }
1.215 + }
1.216 + }
1.217 +
1.218 + // Next we remove any cycles in variable references using Tarjan's strongly
1.219 + // connected components finding algorithm, setting variables in cycles to
1.220 + // have an invalid value.
1.221 + mNextIndex = 1;
1.222 + for (size_t id = 0; id < n; id++) {
1.223 + if (!mVariables[id].mIndex) {
1.224 + RemoveCycles(id);
1.225 + MOZ_ASSERT(mStack.IsEmpty());
1.226 + }
1.227 + }
1.228 +
1.229 + // Finally we construct the computed value for the variable by substituting
1.230 + // any variable references.
1.231 + for (size_t id = 0; id < n; id++) {
1.232 + if (!mVariables[id].mResolved) {
1.233 + ResolveVariable(id);
1.234 + }
1.235 + }
1.236 +
1.237 + mResolved = true;
1.238 +}
1.239 +
1.240 +void
1.241 +CSSVariableResolver::Put(const nsAString& aVariableName,
1.242 + nsString aValue,
1.243 + nsCSSTokenSerializationType aFirstToken,
1.244 + nsCSSTokenSerializationType aLastToken,
1.245 + bool aWasInherited)
1.246 +{
1.247 + MOZ_ASSERT(!mResolved);
1.248 +
1.249 + size_t id;
1.250 + if (mVariableIDs.Get(aVariableName, &id)) {
1.251 + MOZ_ASSERT(mVariables[id].mWasInherited && !aWasInherited,
1.252 + "should only overwrite inherited variables with specified "
1.253 + "variables");
1.254 + mVariables[id].mValue = aValue;
1.255 + mVariables[id].mFirstToken = aFirstToken;
1.256 + mVariables[id].mLastToken = aLastToken;
1.257 + mVariables[id].mWasInherited = aWasInherited;
1.258 + } else {
1.259 + id = mVariables.Length();
1.260 + mVariableIDs.Put(aVariableName, id);
1.261 + mVariables.AppendElement(Variable(aVariableName, aValue,
1.262 + aFirstToken, aLastToken, aWasInherited));
1.263 + }
1.264 +}
1.265 +
1.266 +}
