michael@0: /* vim: set shiftwidth=2 tabstop=8 autoindent cindent expandtab: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /* object that resolves CSS variables using specified and inherited variable
michael@0:  * values
michael@0:  */
michael@0: 
michael@0: #include "CSSVariableResolver.h"
michael@0: 
michael@0: #include "CSSVariableDeclarations.h"
michael@0: #include "CSSVariableValues.h"
michael@0: #include "mozilla/PodOperations.h"
michael@0: #include <algorithm>
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: /**
michael@0:  * Data used by the EnumerateVariableReferences callback.  Reset must be called
michael@0:  * on it before it is used.
michael@0:  */
michael@0: class EnumerateVariableReferencesData
michael@0: {
michael@0: public:
michael@0:   EnumerateVariableReferencesData(CSSVariableResolver& aResolver)
michael@0:     : mResolver(aResolver)
michael@0:     , mReferences(new bool[aResolver.mVariables.Length()])
michael@0:   {
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Resets the data so that it can be passed to another call of
michael@0:    * EnumerateVariableReferences for a different variable.
michael@0:    */
michael@0:   void Reset()
michael@0:   {
michael@0:     PodZero(mReferences.get(), mResolver.mVariables.Length());
michael@0:     mReferencesNonExistentVariable = false;
michael@0:   }
michael@0: 
michael@0:   void RecordVariableReference(const nsAString& aVariableName)
michael@0:   {
michael@0:     size_t id;
michael@0:     if (mResolver.mVariableIDs.Get(aVariableName, &id)) {
michael@0:       mReferences[id] = true;
michael@0:     } else {
michael@0:       mReferencesNonExistentVariable = true;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   bool HasReferenceToVariable(size_t aID) const
michael@0:   {
michael@0:     return mReferences[aID];
michael@0:   }
michael@0: 
michael@0:   bool ReferencesNonExistentVariable() const
michael@0:   {
michael@0:    return mReferencesNonExistentVariable;
michael@0:   }
michael@0: 
michael@0: private:
michael@0:   CSSVariableResolver& mResolver;
michael@0: 
michael@0:   // Array of booleans, where each index is a variable ID.  If an element is
michael@0:   // true, it indicates that the variable we have called
michael@0:   // EnumerateVariableReferences for has a reference to the variable with
michael@0:   // that ID.
michael@0:   nsAutoArrayPtr<bool> mReferences;
michael@0: 
michael@0:   // Whether the variable we have called EnumerateVariableReferences for
michael@0:   // references a variable that does not exist in the resolver.
michael@0:   bool mReferencesNonExistentVariable;
michael@0: };
michael@0: 
michael@0: static void
michael@0: RecordVariableReference(const nsAString& aVariableName,
michael@0:                         void* aData)
michael@0: {
michael@0:   static_cast<EnumerateVariableReferencesData*>(aData)->
michael@0:     RecordVariableReference(aVariableName);
michael@0: }
michael@0: 
michael@0: void
michael@0: CSSVariableResolver::RemoveCycles(size_t v)
michael@0: {
michael@0:   mVariables[v].mIndex = mNextIndex;
michael@0:   mVariables[v].mLowLink = mNextIndex;
michael@0:   mVariables[v].mInStack = true;
michael@0:   mStack.AppendElement(v);
michael@0:   mNextIndex++;
michael@0: 
michael@0:   for (size_t i = 0, n = mReferences[v].Length(); i < n; i++) {
michael@0:     size_t w = mReferences[v][i];
michael@0:     if (!mVariables[w].mIndex) {
michael@0:       RemoveCycles(w);
michael@0:       mVariables[v].mLowLink = std::min(mVariables[v].mLowLink,
michael@0:                                         mVariables[w].mLowLink);
michael@0:     } else if (mVariables[w].mInStack) {
michael@0:       mVariables[v].mLowLink = std::min(mVariables[v].mLowLink,
michael@0:                                         mVariables[w].mIndex);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (mVariables[v].mLowLink == mVariables[v].mIndex) {
michael@0:     if (mStack.LastElement() == v) {
michael@0:       // A strongly connected component consisting of a single variable is not
michael@0:       // necessarily invalid.  We handle variables that reference themselves
michael@0:       // earlier, in CSSVariableResolver::Resolve.
michael@0:       mVariables[mStack.LastElement()].mInStack = false;
michael@0:       mStack.TruncateLength(mStack.Length() - 1);
michael@0:     } else {
michael@0:       size_t w;
michael@0:       do {
michael@0:         w = mStack.LastElement();
michael@0:         mVariables[w].mValue.Truncate(0);
michael@0:         mVariables[w].mInStack = false;
michael@0:         mStack.TruncateLength(mStack.Length() - 1);
michael@0:       } while (w != v);
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: void
michael@0: CSSVariableResolver::ResolveVariable(size_t aID)
michael@0: {
michael@0:   if (mVariables[aID].mValue.IsEmpty() || mVariables[aID].mWasInherited) {
michael@0:     // The variable is invalid or was inherited.   We can just copy the value
michael@0:     // and its first/last token information across.
michael@0:     mOutput->Put(mVariables[aID].mVariableName,
michael@0:                  mVariables[aID].mValue,
michael@0:                  mVariables[aID].mFirstToken,
michael@0:                  mVariables[aID].mLastToken);
michael@0:   } else {
michael@0:     // Otherwise we need to resolve the variable references, after resolving
michael@0:     // all of our dependencies first.  We do this even for variables that we
michael@0:     // know do not reference other variables so that we can find their
michael@0:     // first/last token.
michael@0:     //
michael@0:     // XXX We might want to do this first/last token finding during
michael@0:     // EnumerateVariableReferences, so that we can avoid calling
michael@0:     // ResolveVariableValue and parsing the value again.
michael@0:     for (size_t i = 0, n = mReferences[aID].Length(); i < n; i++) {
michael@0:       size_t j = mReferences[aID][i];
michael@0:       if (aID != j && !mVariables[j].mResolved) {
michael@0:         ResolveVariable(j);
michael@0:       }
michael@0:     }
michael@0:     nsString resolvedValue;
michael@0:     nsCSSTokenSerializationType firstToken, lastToken;
michael@0:     if (!mParser.ResolveVariableValue(mVariables[aID].mValue, mOutput,
michael@0:                                       resolvedValue, firstToken, lastToken)) {
michael@0:       resolvedValue.Truncate(0);
michael@0:     }
michael@0:     mOutput->Put(mVariables[aID].mVariableName, resolvedValue,
michael@0:                  firstToken, lastToken);
michael@0:   }
michael@0:   mVariables[aID].mResolved = true;
michael@0: }
michael@0: 
michael@0: void
michael@0: CSSVariableResolver::Resolve(const CSSVariableValues* aInherited,
michael@0:                              const CSSVariableDeclarations* aSpecified)
michael@0: {
michael@0:   MOZ_ASSERT(!mResolved);
michael@0: 
michael@0:   // The only time we would be worried about having a null aInherited is
michael@0:   // for the root, but in that case nsRuleNode::ComputeVariablesData will
michael@0:   // happen to pass in whatever we're using as mOutput for aInherited,
michael@0:   // which will initially be empty.
michael@0:   MOZ_ASSERT(aInherited);
michael@0:   MOZ_ASSERT(aSpecified);
michael@0: 
michael@0:   aInherited->AddVariablesToResolver(this);
michael@0:   aSpecified->AddVariablesToResolver(this);
michael@0: 
michael@0:   // First we look at each variable's value and record which other variables
michael@0:   // it references.
michael@0:   size_t n = mVariables.Length();
michael@0:   mReferences.SetLength(n);
michael@0:   EnumerateVariableReferencesData data(*this);
michael@0:   for (size_t id = 0; id < n; id++) {
michael@0:     data.Reset();
michael@0:     if (!mVariables[id].mWasInherited &&
michael@0:         !mVariables[id].mValue.IsEmpty()) {
michael@0:       if (mParser.EnumerateVariableReferences(mVariables[id].mValue,
michael@0:                                               RecordVariableReference,
michael@0:                                               &data)) {
michael@0:         // Convert the boolean array of dependencies in |data| to a list
michael@0:         // of dependencies.
michael@0:         for (size_t i = 0; i < n; i++) {
michael@0:           if (data.HasReferenceToVariable(i)) {
michael@0:             mReferences[id].AppendElement(i);
michael@0:           }
michael@0:         }
michael@0:         // If a variable references itself, it is invalid.  (RemoveCycles
michael@0:         // does not check for cycles consisting of a single variable, so we
michael@0:         // check here.)
michael@0:         if (data.HasReferenceToVariable(id)) {
michael@0:           mVariables[id].mValue.Truncate();
michael@0:         }
michael@0:         // Also record whether it referenced any variables that don't exist
michael@0:         // in the resolver, so that we can ensure we still resolve its value
michael@0:         // in ResolveVariable, even though its mReferences list is empty.
michael@0:         mVariables[id].mReferencesNonExistentVariable =
michael@0:           data.ReferencesNonExistentVariable();
michael@0:       } else {
michael@0:         MOZ_ASSERT(false, "EnumerateVariableReferences should not have failed "
michael@0:                           "if we previously parsed the specified value");
michael@0:         mVariables[id].mValue.Truncate(0);
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Next we remove any cycles in variable references using Tarjan's strongly
michael@0:   // connected components finding algorithm, setting variables in cycles to
michael@0:   // have an invalid value.
michael@0:   mNextIndex = 1;
michael@0:   for (size_t id = 0; id < n; id++) {
michael@0:     if (!mVariables[id].mIndex) {
michael@0:       RemoveCycles(id);
michael@0:       MOZ_ASSERT(mStack.IsEmpty());
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Finally we construct the computed value for the variable by substituting
michael@0:   // any variable references.
michael@0:   for (size_t id = 0; id < n; id++) {
michael@0:     if (!mVariables[id].mResolved) {
michael@0:       ResolveVariable(id);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   mResolved = true;
michael@0: }
michael@0: 
michael@0: void
michael@0: CSSVariableResolver::Put(const nsAString& aVariableName,
michael@0:                          nsString aValue,
michael@0:                          nsCSSTokenSerializationType aFirstToken,
michael@0:                          nsCSSTokenSerializationType aLastToken,
michael@0:                          bool aWasInherited)
michael@0: {
michael@0:   MOZ_ASSERT(!mResolved);
michael@0: 
michael@0:   size_t id;
michael@0:   if (mVariableIDs.Get(aVariableName, &id)) {
michael@0:     MOZ_ASSERT(mVariables[id].mWasInherited && !aWasInherited,
michael@0:                "should only overwrite inherited variables with specified "
michael@0:                "variables");
michael@0:     mVariables[id].mValue = aValue;
michael@0:     mVariables[id].mFirstToken = aFirstToken;
michael@0:     mVariables[id].mLastToken = aLastToken;
michael@0:     mVariables[id].mWasInherited = aWasInherited;
michael@0:   } else {
michael@0:     id = mVariables.Length();
michael@0:     mVariableIDs.Put(aVariableName, id);
michael@0:     mVariables.AppendElement(Variable(aVariableName, aValue,
michael@0:                                       aFirstToken, aLastToken, aWasInherited));
michael@0:   }
michael@0: }
michael@0: 
michael@0: }