|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
#nullable disable
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.Xaml;
using System.Xaml.MS.Impl;
using System.Xaml.Schema;
namespace MS.Internal.Xaml.Context
{
// Graph of unresolved forward references, and the objects that depend on them.
// The nodes are objects and names. The edges (NameFixupTokens) are dependencies from an object to
// a set of unresolved names, or from an object to another object that has unresolved dependencies.
internal class NameFixupGraph
{
// Node -> out-edges (other objects the parent is dependent on)
Dictionary<object, FrugalObjectList<NameFixupToken>> _dependenciesByParentObject;
// Node -> in-edge (other object that is dependent on this child)
Dictionary<object, NameFixupToken> _dependenciesByChildObject;
// Node -> in-edges (other objects that are dependent on this name)
Dictionary<string, FrugalObjectList<NameFixupToken>> _dependenciesByName;
// Queue of tokens whose dependencies have been resolved, and are awaiting processing
Queue<NameFixupToken> _resolvedTokensPendingProcessing;
// Token for a pending call to ProvideValue on the root object. Can't store this in
// _dependenciesByParentObject because it has no parent.
NameFixupToken _deferredRootProvideValue;
// At the end of the parse, we start running reparses on partially initialized objects,
// and remove those dependencies. But we still want to be able to inform MEs/TCs that
// the named objects they're getting aren't actually fully initialized. So we save this list
// of incompletely initialized objects at the point we start completing references.
HashSet <object> _uninitializedObjectsAtParseEnd;
public NameFixupGraph()
{
var referenceComparer = ReferenceEqualityComparer.Instance;
_dependenciesByChildObject = new Dictionary<object, NameFixupToken>(referenceComparer);
_dependenciesByName = new Dictionary<string, FrugalObjectList<NameFixupToken>>(StringComparer.Ordinal);
_dependenciesByParentObject = new Dictionary<object, FrugalObjectList<NameFixupToken>>(referenceComparer);
_resolvedTokensPendingProcessing = new Queue<NameFixupToken>();
_uninitializedObjectsAtParseEnd = new HashSet<object>(referenceComparer);
}
// Add an edge to the graph. We need to look up edges in both directions, so each edge is
// stored in two dictionaries.
public void AddDependency(NameFixupToken fixupToken)
{
// Need to special case a deferred ProvideValue at the root, because it has no parent
if (fixupToken.Target.Property == null)
{
Debug.Assert(fixupToken.Target.Instance == null &&
fixupToken.Target.InstanceType == null &&
fixupToken.FixupType == FixupType.MarkupExtensionFirstRun);
Debug.Assert(_deferredRootProvideValue == null);
_deferredRootProvideValue = fixupToken;
return;
}
object parentObject = fixupToken.Target.Instance;
// References aren't allowed in non-instantiating directives, except for:
// - Initialization, in which case FixupTarget.Instance is the object whose property the
// initialized object will be assigned to; and
// - Key, in which case the FixupTarget.Instance is the dictionary
Debug.Assert(parentObject != null);
AddToMultiDict(_dependenciesByParentObject, parentObject, fixupToken);
if (fixupToken.ReferencedObject != null)
{
Debug.Assert(fixupToken.FixupType == FixupType.UnresolvedChildren ||
fixupToken.FixupType == FixupType.MarkupExtensionFirstRun);
// These fixups are only used for the immediate parent of the object, so there can
// only be one per child instance
Debug.Assert(!_dependenciesByChildObject.ContainsKey(fixupToken.ReferencedObject));
_dependenciesByChildObject.Add(fixupToken.ReferencedObject, fixupToken);
}
else
{
Debug.Assert(fixupToken.FixupType != FixupType.UnresolvedChildren &&
fixupToken.FixupType != FixupType.MarkupExtensionFirstRun);
foreach (string name in fixupToken.NeededNames)
{
AddToMultiDict(_dependenciesByName, name, fixupToken);
}
}
}
public bool HasUnresolvedChildren(object parent)
{
if (parent == null)
{
return false;
}
return _dependenciesByParentObject.ContainsKey(parent);
}
public bool HasUnresolvedOrPendingChildren(object instance)
{
if (HasUnresolvedChildren(instance))
{
return true;
}
foreach (NameFixupToken pendingToken in _resolvedTokensPendingProcessing)
{
if (pendingToken.Target.Instance == instance)
{
return true;
}
}
return false;
}
public bool WasUninitializedAtEndOfParse(object instance)
{
return _uninitializedObjectsAtParseEnd.Contains(instance);
}
// Finds the names that this object's subtree is blocked on.
public void GetDependentNames(object instance, List<string> result)
{
// We're only interested in the immediate subtree, not named-references to other subtrees
// that might exist but not be fully initialized. So we only follow UnresolvedChildren and
// MarkupExtensionFirstRun edges, which means there is no risk of cycles
FrugalObjectList<NameFixupToken> dependencies;
if (!_dependenciesByParentObject.TryGetValue(instance, out dependencies))
{
return;
}
for (int i = 0; i < dependencies.Count; i++)
{
NameFixupToken token = dependencies[i];
if (token.FixupType == FixupType.MarkupExtensionFirstRun ||
token.FixupType == FixupType.UnresolvedChildren)
{
GetDependentNames(token.ReferencedObject, result);
}
else if (token.NeededNames != null)
{
foreach (string name in token.NeededNames)
{
if (!result.Contains(name))
{
result.Add(name);
}
}
}
}
}
// Remove a resolved dependency from the graph.
// Enqueues all removed edges so that the ObjectWriter can process the dependents
// (rerun converters, apply simple fixups, call EndInit on parent ojects, etc).
public void ResolveDependenciesTo(object instance, string name)
{
// Remove any dependency on this instance
NameFixupToken token = null;
if (instance != null)
{
if (_dependenciesByChildObject.Remove(instance, out token))
{
RemoveTokenByParent(token);
_resolvedTokensPendingProcessing.Enqueue(token);
}
}
// Remove any dependencies on this name, and return any tokens whose dependencies
// have all been resolved.
FrugalObjectList<NameFixupToken> nameDependencies;
if (name != null && _dependenciesByName.TryGetValue(name, out nameDependencies))
{
int i = 0;
while (i < nameDependencies.Count)
{
token = nameDependencies[i];
// The same name can occur in multiple namescopes, so we need to make sure that
// this named object is visible in the scope of the token.
object resolvedName = token.ResolveName(name);
if (instance != resolvedName)
{
i++;
continue;
}
if (token.CanAssignDirectly)
{
// For simple fixups, we need to return the resolved object
token.ReferencedObject = instance;
}
token.NeededNames.Remove(name);
nameDependencies.RemoveAt(i);
if (nameDependencies.Count == 0)
{
_dependenciesByName.Remove(name);
}
if (token.NeededNames.Count == 0)
{
RemoveTokenByParent(token);
_resolvedTokensPendingProcessing.Enqueue(token);
}
}
}
}
public bool HasResolvedTokensPendingProcessing
{
get { return _resolvedTokensPendingProcessing.Count > 0; }
}
public NameFixupToken GetNextResolvedTokenPendingProcessing()
{
return _resolvedTokensPendingProcessing.Dequeue();
}
// ObjectWriter calls this whenever an object that has pending fixups goes off the stack.
public void IsOffTheStack(object instance, string name, int lineNumber, int linePosition)
{
FrugalObjectList<NameFixupToken> dependencies;
if (_dependenciesByParentObject.TryGetValue(instance, out dependencies))
{
for (int i = 0; i < dependencies.Count; i++)
{
dependencies[i].Target.InstanceIsOnTheStack = false;
dependencies[i].Target.InstanceName = name;
dependencies[i].Target.EndInstanceLineNumber = lineNumber;
dependencies[i].Target.EndInstanceLinePosition = linePosition;
}
}
}
public void AddEndOfParseDependency(object childThatHasUnresolvedChildren, FixupTarget parentObject)
{
NameFixupToken token = new NameFixupToken();
token.Target = parentObject;
token.FixupType = FixupType.UnresolvedChildren;
token.ReferencedObject = childThatHasUnresolvedChildren;
AddToMultiDict(_dependenciesByParentObject, parentObject.Instance, token);
// We don't add to the _dependenciesByChildObject, because at end-of-parse, a single
// child object can be a dependency of multiple parents
}
// At end of parse, removes and returns all remaining simple fixups, whether or not they
// are resolved
public IEnumerable<NameFixupToken> GetRemainingSimpleFixups()
{
foreach (object key in _dependenciesByParentObject.Keys)
{
_uninitializedObjectsAtParseEnd.Add(key);
}
List<string> names = new List<string>(_dependenciesByName.Keys);
foreach (string name in names)
{
FrugalObjectList<NameFixupToken> dependencies = _dependenciesByName[name];
int i = 0;
while (i < dependencies.Count)
{
NameFixupToken token = dependencies[i];
if (!token.CanAssignDirectly)
{
i++;
continue;
}
dependencies.RemoveAt(i);
if (dependencies.Count == 0)
{
_dependenciesByName.Remove(name);
}
RemoveTokenByParent(token);
yield return token;
}
}
}
// At end of parse, removes and returns all remaining reparse fixups, whether or not they
// are resolved. Assumes that all simple fixups have already been removed.
public IEnumerable<NameFixupToken> GetRemainingReparses()
{
List<object> parentObjs = new List<object>(_dependenciesByParentObject.Keys);
foreach (object parentObj in parentObjs)
{
FrugalObjectList<NameFixupToken> dependencies = _dependenciesByParentObject[parentObj];
int i = 0;
while (i < dependencies.Count)
{
NameFixupToken token = dependencies[i];
if (token.FixupType == FixupType.MarkupExtensionFirstRun ||
token.FixupType == FixupType.UnresolvedChildren)
{
i++;
continue;
}
// Remove this token from the _dependenciesByParentObject dictionary
dependencies.RemoveAt(i);
if (dependencies.Count == 0)
{
_dependenciesByParentObject.Remove(parentObj);
}
// Remove this token from the _dependenciesByName dictionary
foreach (string name in token.NeededNames)
{
FrugalObjectList<NameFixupToken> nameDependencies = _dependenciesByName[name];
if (nameDependencies.Count == 1)
{
nameDependencies.Remove(token);
}
else
{
_dependenciesByName.Remove(name);
}
}
yield return token;
}
}
}
// At end of parse, removes and returns all remaining MarkupExtensionFirstRun and UnresolvedChildren
// tokens, even if they are not fully initialized. Assumes that all simple fixups and reparses have
// already been removed.
public IEnumerable<NameFixupToken> GetRemainingObjectDependencies()
{
// We'd like to return dependencies in a topologically sorted order, but the graph is
// not acylic. (If it were, all references would have been resolved during the regular parse.)
// However, we don't allow ProvideValue cycles. So find a MarkupExtension that doesn't have
// dependencies on any other MarkupExtension.
// Note: at this point we can't use _dependenciesByChildObject for general traversal,
// because it's not updated by AddEndOfParseDependency. However, AddEndOfParseDependency
// doesn't add MarkupExtension edges, so we can still use _dependenciesByChildObject for that.
List<NameFixupToken> markupExtensionTokens = new List<NameFixupToken>();
foreach (NameFixupToken curToken in _dependenciesByChildObject.Values)
{
if (curToken.FixupType == FixupType.MarkupExtensionFirstRun)
{
markupExtensionTokens.Add(curToken);
}
}
while (markupExtensionTokens.Count > 0)
{
bool found = false;
int i = 0;
while (i < markupExtensionTokens.Count)
{
NameFixupToken meToken = markupExtensionTokens[i];
List<NameFixupToken> dependencies = new List<NameFixupToken>();
if (!FindDependencies(meToken, dependencies))
{
i++;
continue;
}
// Iterate the list in backwards order, so we return the deepest first
for (int j = dependencies.Count - 1; j >= 0; j--)
{
NameFixupToken token = dependencies[j];
RemoveTokenByParent(token);
yield return token;
}
found = true;
markupExtensionTokens.RemoveAt(i);
}
if (!found)
{
// We have MEs left, but they all have dependencies on other MEs.
// That means we have a cycle.
ThrowProvideValueCycle(markupExtensionTokens);
}
}
// For the remaining EndInits, we pick an arbitrary point and return a DFS of its dependencies
while (_dependenciesByParentObject.Count > 0)
{
FrugalObjectList<NameFixupToken> startNodeOutEdges = null;
foreach (FrugalObjectList<NameFixupToken> list in _dependenciesByParentObject.Values)
{
startNodeOutEdges = list;
break;
}
for (int i = 0; i < startNodeOutEdges.Count; i++)
{
List<NameFixupToken> dependencies = new List<NameFixupToken>();
FindDependencies(startNodeOutEdges[i], dependencies);
// Iterate the list in backwards order, so we return the deepest first
for (int j = dependencies.Count - 1; j >= 0; j--)
{
NameFixupToken token = dependencies[j];
RemoveTokenByParent(token);
yield return token;
}
}
}
// Finally, if there was a deferred ProvideValue at the root, return it
if (_deferredRootProvideValue != null)
{
yield return _deferredRootProvideValue;
}
}
// Depth-first traversal of the graph starting at a given edge. Ignores edges that would cause cycles.
// Returns true if the dependency list is complete, false if we aborted because we found an ME.
private bool FindDependencies(NameFixupToken inEdge, List<NameFixupToken> alreadyTraversed)
{
if (alreadyTraversed.Contains(inEdge))
{
// Cycle, skip it
return true;
}
alreadyTraversed.Add(inEdge);
FrugalObjectList<NameFixupToken> outEdges;
if (inEdge.ReferencedObject == null ||
!_dependenciesByParentObject.TryGetValue(inEdge.ReferencedObject, out outEdges))
{
// No dependencies, we're done with this subgraph
return true;
}
for (int i = 0; i < outEdges.Count; i++)
{
NameFixupToken outEdge = outEdges[i];
if (outEdge.FixupType == FixupType.MarkupExtensionFirstRun)
{
return false;
}
Debug.Assert(outEdge.FixupType == FixupType.UnresolvedChildren);
if (!FindDependencies(outEdge, alreadyTraversed))
{
return false;
}
}
return true;
}
private void RemoveTokenByParent(NameFixupToken token)
{
object parentInstance = token.Target.Instance;
FrugalObjectList<NameFixupToken> parentDependencies = _dependenciesByParentObject[parentInstance];
Debug.Assert(parentDependencies.Contains(token));
if (parentDependencies.Count == 1)
{
_dependenciesByParentObject.Remove(parentInstance);
}
else
{
parentDependencies.Remove(token);
}
}
private static void AddToMultiDict<TKey>(Dictionary<TKey, FrugalObjectList<NameFixupToken>> dict,
TKey key, NameFixupToken value)
{
FrugalObjectList<NameFixupToken> tokenList;
if (!dict.TryGetValue(key, out tokenList))
{
tokenList = new FrugalObjectList<NameFixupToken>(1);
dict.Add(key, tokenList);
}
tokenList.Add(value);
}
private static void ThrowProvideValueCycle(IEnumerable<NameFixupToken> markupExtensionTokens)
{
StringBuilder exceptionMessage = new StringBuilder();
exceptionMessage.Append(SR.ProvideValueCycle);
foreach (NameFixupToken token in markupExtensionTokens)
{
exceptionMessage.AppendLine();
string meName = token.ReferencedObject.ToString();
if (token.LineNumber != 0)
{
if (token.LinePosition != 0)
{
exceptionMessage.Append(SR.Format(SR.LineNumberAndPosition, meName, token.LineNumber, token.LinePosition));
}
else
{
exceptionMessage.Append(SR.Format(SR.LineNumberOnly, meName, token.LineNumber));
}
}
else
{
exceptionMessage.Append(meName);
}
}
throw new XamlObjectWriterException(exceptionMessage.ToString());
}
}
}
|