diff options
Diffstat (limited to 'src/inc/CrstTypeTool.cs')
| -rw-r--r-- | src/inc/CrstTypeTool.cs | 990 |
1 files changed, 990 insertions, 0 deletions
diff --git a/src/inc/CrstTypeTool.cs b/src/inc/CrstTypeTool.cs new file mode 100644 index 0000000000..d6d90e427b --- /dev/null +++ b/src/inc/CrstTypeTool.cs @@ -0,0 +1,990 @@ +// 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. + +// +// This tool exists to transform a high level description of Crst dependencies (i.e. which Crst type may be +// acquired before or after other Crst types) into a header file that defines a enum to describe each Crst +// type and tables that map type to numerical ranking and a string based name. +// +// To use the tool, run "csc.exe CrstTypeTool.cs" and run the resulting executable. +// +// The Crst type definition file is written in a very simple language. Comments begin with '//' and continue +// to the end of the line. All remaining tokens after comment removal are simply sequences of non-whitespace +// characters separated by whitespace. Keywords are case-insensitive and identifiers (which are always Crst +// type names) are case sensitive. The language grammar is given below in EBNF-like form: +// +// TopLevel ::= CrstDefinition* +// +// CrstDefinition ::= 'Crst' <Crst type name> CrstDependency* 'End' +// +// CrstDependency ::= 'AcquiredBefore' <Crst type name>* +// | 'AcquiredAfter' <Crst type name>* +// | 'SameLevelAs' <Crst type name>* +// | 'Unordered' +// +// Crst type names match the CrstType enums used in the source code minus the 'Crst' prefix. For example +// CrstAppDomainCache is written as 'AppDomainCache' in the .def file. +// +// The dependency "A 'AcquiredBefore' B" indicates that CrstA may be legally held while CrstB is acquired. +// Similarly "A 'AcquiredAfter' B" indicates that CrstA may be legally acquired while CrstB is held. "A +// 'AcquiredBefore' B" is logically equivalent to "B 'AcquiredAfter' A" and authors may enter the dependency +// is whichever seems to make the most sense to them (or add both rules if they so desire). +// +// 'Unordered' indicates that the Crst type does not participate in ranking (there should be very few Crsts +// like this and those that are know how to avoid or deal with deadlocks manually). +// +// 'SameLevelAs' indicates the given Crst type may be acquired alongside any number of instances of the Crst +// types indicated. "A 'SameLevel' B" automatically implies "B 'SameLevel' A" so it's not necessary to specify +// the dependency both ways though authors can do so if they wish. +// +// Simple validation of the .def file (over and above syntax checking) is performed by this tool prior to +// emitting the header file. This will catch logic errors such as referencing a Crst type that is not +// defined or using the 'Unordered' attribute along with any other attribute within a single definition. It +// will also catch cycles in the dependency graph (i.e. definitions that logically describe a system where the +// Crst types can't be ranked). +// + +using System; +using System.Collections.Generic; +using System.Text; +using System.IO; +using System.Text.RegularExpressions; + +// The main application class containing the program entry point. +class CrstTypeTool +{ + // A hash containing every Crst type defined by the input .def file along with its attributes. Keyed by + // Crst type name (which is case sensitive and doesn't include the 'Crst' enum prefix). + Dictionary<string, CrstType> m_crsts = new Dictionary<string, CrstType>(); + + // The program entry point. + public static int Main() + { + try + { + // Calculate the filenames of the input and output files. + string inputFile = "CrstTypes.def"; + string outputFile = "CrstTypes.h"; + + // A common error is to forget to check out the CrstTypes.h file first. Handle this case specially + // so we can give a good error message. + if (File.Exists(outputFile) && (File.GetAttributes(outputFile) & FileAttributes.ReadOnly) != 0) + { + Console.WriteLine(outputFile + " is read-only, you must check it out of TFS/SD first"); + return 2; + } + + // Create an instance of our application class to store state in (specifically the collection of + // Crst type definitions). + CrstTypeTool app = new CrstTypeTool(); + + // Create a parser for the CrstTypes.def file and run it over the input file (errors are signalled + // via exception, in common with all the following steps except validation). + new TypeFileParser().ParseFile(inputFile, app.m_crsts); + + // Validate the collection of Crst type definitions we built up during parsing for common logic + // errors and the presence of dependency cycles. False is returned from ValidateCrsts if an error + // was detected (an error message will have already been output to the console at this point). + if (!app.ValidateCrsts()) + return 3; + + // Perform a topological sort to map each Crst type to a numeric ranking. + app.LevelCrsts(); + + // Emit the new header file containing Crst type definitions and ranking information. + app.WriteHeaderFile(outputFile); + + // If we get here the transformation was successful; inform the user and we're done. + Console.WriteLine(outputFile + " successfully updated"); + return 0; + } + catch (TypeFileParser.ParseError pe) + { + // Syntax errors specific to parsing the input file. + Console.WriteLine("ParseError: " + pe.Message); + return 4; + } + catch (Exception e) + { + // Any other general errors (file I/O problems, out of memory etc.). + Console.WriteLine("Unexpected exception:"); + Console.WriteLine(e); + return 5; + } + } + + // Emit the CrstTypes.h output file. + void WriteHeaderFile(string fileName) + { + FileStream stream = new FileStream(fileName, FileMode.Create, FileAccess.Write, FileShare.None); + StreamWriter writer = new StreamWriter(stream); + + // Create a collection based on all the Crst types we've stored in the hash. We do this so we can sort + // the Crst types we emit (lexically, based on type name). + Dictionary<string, CrstType>.ValueCollection crstCollection = m_crsts.Values; + CrstType[] crsts = new CrstType[crstCollection.Count]; + crstCollection.CopyTo(crsts, 0); + Array.Sort(crsts); + + // Emit the header. Contains copyright information, the usual goop to avoid multiple inclusion and a + // header comment to discourage direct editing and point the user at the CrstTypes.def file instead + // (where all will be explained in greater detail). + writer.WriteLine("//"); + writer.WriteLine("// Licensed to the .NET Foundation under one or more agreements."); + writer.WriteLine("// The .NET Foundation licenses this file to you under the MIT license."); + writer.WriteLine("// See the LICENSE file in the project root for more information."); + writer.WriteLine("//"); + writer.WriteLine(); + writer.WriteLine("#ifndef __CRST_TYPES_INCLUDED"); + writer.WriteLine("#define __CRST_TYPES_INCLUDED"); + writer.WriteLine(); + writer.WriteLine("// **** THIS IS AN AUTOMATICALLY GENERATED HEADER FILE -- DO NOT EDIT!!! ****"); + writer.WriteLine(); + writer.WriteLine("// This file describes the range of Crst types available and their mapping to a numeric level (used by the"); + writer.WriteLine("// runtime in debug mode to validate we're deadlock free). To modify these settings edit the"); + writer.WriteLine("// file:CrstTypes.def file and run the clr\\bin\\CrstTypeTool utility to generate a new version of this file."); + writer.WriteLine(); + + // Emit the CrstType enum to define a value for each crst type (along with the kNumberOfCrstTypes + // constant). + writer.WriteLine("// Each Crst type is declared as a value in the following CrstType enum."); + writer.WriteLine("enum CrstType"); + writer.WriteLine("{"); + for (int i = 0; i < crsts.Length; i++) + writer.WriteLine(" Crst" + crsts[i].Name + " = " + i.ToString() + ","); + writer.WriteLine(" kNumberOfCrstTypes = " + crsts.Length.ToString()); + writer.WriteLine("};"); + writer.WriteLine(); + + // This is the end of the regular part of the header included by most files. + writer.WriteLine("#endif // __CRST_TYPES_INCLUDED"); + writer.WriteLine(); + + // There is a second section of the header intended for inclusion only by vm\Crst.cpp. This contains + // some data tables used to map crst type to rank or name. We could instead define two separate + // headers, but on the whole it seems simpler to do it this way. + writer.WriteLine("// Define some debug data in one module only -- vm\\crst.cpp."); + writer.WriteLine("#if defined(__IN_CRST_CPP) && defined(_DEBUG)"); + writer.WriteLine(); + + // Emit the crst type to rank mapping table. + writer.WriteLine("// An array mapping CrstType to level."); + writer.WriteLine("int g_rgCrstLevelMap[] ="); + writer.WriteLine("{"); + foreach (CrstType crst in crsts) + writer.WriteLine(" " + crst.Level + ",\t\t\t// Crst" + crst.Name); + writer.WriteLine("};"); + writer.WriteLine(); + + // Emit the crst type to name mapping table. + writer.WriteLine("// An array mapping CrstType to a stringized name."); + writer.WriteLine("LPCSTR g_rgCrstNameMap[] ="); + writer.WriteLine("{"); + foreach (CrstType crst in crsts) + writer.WriteLine(" \"Crst" + crst.Name + "\","); + writer.WriteLine("};"); + writer.WriteLine(); + + // Emit the constant Crst.cpp uses to record an unordered rank. + writer.WriteLine("// Define a special level constant for unordered locks."); + writer.WriteLine("#define CRSTUNORDERED (-1)"); + writer.WriteLine(); + + // Emit a couple of inline helpers to map type to rank or name (and validate the type while they're at + // it). + writer.WriteLine("// Define inline helpers to map Crst types to names and levels."); + writer.WriteLine("inline static int GetCrstLevel(CrstType crstType)"); + writer.WriteLine("{"); + writer.WriteLine(" LIMITED_METHOD_CONTRACT;"); + writer.WriteLine(" _ASSERTE(crstType >= 0 && crstType < kNumberOfCrstTypes);"); + writer.WriteLine(" return g_rgCrstLevelMap[crstType];"); + writer.WriteLine("}"); + writer.WriteLine("inline static LPCSTR GetCrstName(CrstType crstType)"); + writer.WriteLine("{"); + writer.WriteLine(" LIMITED_METHOD_CONTRACT;"); + writer.WriteLine(" _ASSERTE(crstType >= 0 && crstType < kNumberOfCrstTypes);"); + writer.WriteLine(" return g_rgCrstNameMap[crstType];"); + writer.WriteLine("}"); + writer.WriteLine(); + + // And that's the end of the second section of the header file. + writer.WriteLine("#endif // defined(__IN_CRST_CPP) && defined(_DEBUG)"); + + writer.Close(); + stream.Close(); + } + + // Peform checking of the Crst type definitions we've read just read. Various forms of logic error are + // scanned for including cycles in the dependency graph. Returns true if no errors are found. If false is + // returned a descriptive error message will have already been written to the console. + bool ValidateCrsts() + { + // Look at each Crst type definition in turn. + foreach (CrstType crst in m_crsts.Values) + { + // Catch Crst types that are referenced but never defined. + if (!crst.Defined) + { + Console.WriteLine(String.Format("Error: CrstType 'Crst{0}' is referenced without being defined", + crst.Name)); + return false; + } + + // Catch the use of the 'Unordered' attribute alongside the 'AcquiredBefore' attribute (which + // indicates an ordering). + if (crst.Level == CrstType.CrstUnordered && (crst.AcquiredBeforeList.Count > 0 || + crst.Group != null)) + { + Console.WriteLine(String.Format("Error: CrstType 'Crst{0}' is declared as both unordered and acquired before 'Crst{1}'", + crst.Name, crst.AcquiredBeforeList[0].Name)); + return false; + } + + // Catch the use of the 'Unordered' attribute alongside the 'SameLevelAs' attribute (which + // indicates an ordering). + if (crst.Level == CrstType.CrstUnordered && crst.Group != null) + { + Console.WriteLine(String.Format("Error: CrstType 'Crst{0}' is declared as both unordered and in the same level as another CrstType", + crst.Name)); + return false; + } + + // Catch the simple cycle where the Crst type depends on itself. + if (crst.AcquiredBeforeList.Contains(crst)) + { + Console.WriteLine(String.Format("Error: CrstType 'Crst{0}' is declared as being acquired before itself", + crst.Name)); + return false; + } + + // Look for deeper cycles using a recursive algorithm in 'FindCycle()'. + List<CrstType> cycleList = new List<CrstType>(); + if (FindCycle(crst, crst, cycleList)) + { + Console.WriteLine(String.Format("Error: CrstType 'Crst{0}' is involved in a dependency cycle with the following CrstTypes:", + crst.Name)); + foreach (CrstType cycleCrst in cycleList) + Console.WriteLine(String.Format(" Crst{0}", cycleCrst.Name)); + return false; + } + } + + // Perform normalization of each set of Crst types that are included in the same group (i.e. have a + // 'SameLevelAs' relationship). Normalization means that each Crst type in a group will have exactly + // the same set of dependency rules as all the others. + CrstTypeGroup.NormalizeAllRules(); + + // The normalization process could have introduced cycles in the dependency graph so run the cycle + // detection pass again. We do separate passes like this since normalizing can lead to less intuitive + // error messages if a cycle is found: so if the cycle exists before normalization takes place we want + // to generate an error message then. + foreach (CrstType crst in m_crsts.Values) + { + List<CrstType> cycleList = new List<CrstType>(); + if (FindCycle(crst, crst, cycleList)) + { + Console.WriteLine(String.Format("Error: CrstType 'Crst{0}' is involved in a dependency cycle with the following CrstTypes:", + crst.Name)); + foreach (CrstType cycleCrst in cycleList) + Console.WriteLine(String.Format(" Crst{0}", cycleCrst)); + Console.WriteLine("Note that the cycle was detected only after 'SameLevelAs' processing was performed so some CrstType dependencies are implied by peer CrstTypes"); + return false; + } + } + + return true; + } + + // Recursively determine if a cycle exists in the Crst type dependency graph rooted at the 'rootCrst' + // type. The 'currCrst' indicates the next dependency to be examined (it will be the same as the + // 'rootCrst' when we're first called). The 'cycleList' argument contains a list of Crst types we've + // already examined in this branch of the algorithm and serves both to avoid checking the same node twice + // and to provide a list of the involved Crst types should a cycle be detected. + // Note that this algorithm is not designed to detect general cycles in the graph, only those that involve + // the 'rootCrst' directly. This is somewhat inefficient but gives us a simple way to generate clear error + // messages. + bool FindCycle(CrstType rootCrst, CrstType currCrst, List<CrstType> cycleList) + { + // Add the current Crst type to the list of those we've seen. + cycleList.Add(currCrst); + + // Look through all the dependencies of the current Crst type. + foreach (CrstType childCrst in currCrst.AcquiredBeforeList) + { + // If we find a reference back to the root Crst type then we've found a cycle. Start backing out + // from the recursion (keeping the list of nodes we visited intact) by returning true. + if (childCrst == rootCrst) + return true; + + // Otherwise iterate over the dependencies of the current node and for each one that we haven't + // already seen and recursively extend the search. + if (!cycleList.Contains(childCrst)) + if (FindCycle(rootCrst, childCrst, cycleList)) + return true; + } + + // Didn't find any cycles involving the root and this node; remove this node from the potential cycle + // list and return up to our caller indicating such. + cycleList.RemoveAt(cycleList.Count - 1); + + return false; + } + + // Topologically sort all the Crsts so we can assign a total ordering to them (in the form of a numeric + // ranking). Ranks start from 0 (Crst types that may be acquired at any time) and increment from there + // (Crst types that may only be acquired if a lower type is not already held). + // **** NOTE: The leveling process is destructive in that we will lose all dependency information from the + // Crst type definitions during the course of the algorithm. + void LevelCrsts() + { + // Note that Crst type dependency rules have been normalized (by the input parser) so that all + // AcquiredBefore/AcquiredAfter relationships have been reduced to AcquiredBefore relationships (i.e. + // any rule of the form "A AcquiredAfter B" has been converted to "B AcquiredBefore A". Any + // normalization makes the algorithm easier to program, but a normaliztion to AcquiredBefore + // relationships was chosen since it makes it particularly easy to implement an algorithm that assigns + // ranks beginning with zero and moving up to an arbitrary level. Any type that doesn't have any + // AcquiredBefore dependencies can always be ranked at a lower level than any remaining unranked types + // by definition and from this we can derive a simple iterative process to rank all the crst types. + + // Calculate how many Crst types we have left to rank (some are not included in this step because + // they've been marked as 'Unordered' in the input file). + int unsorted = 0; + foreach (CrstType crst in m_crsts.Values) + if (crst.Level == CrstType.CrstUnassigned) + unsorted++; + + // The ranking level we're going to assign to Crst types on the next pass of the algorithm. + int currLevel = 0; + + // Iterate while we still have Crst types left to rank. On each pass we'll assign a rank to those + // types that no longer have any dependencies forcing them to have a higher rank and then remove + // dependency rules involving those newly ranked types from the remaining types. + while (unsorted > 0) + { + // Record a flag indicating whether we manage to assign a rank to at least one Crst type on this + // pass. If we ever fail to do this we've hit a cycle (this is just paranoia, the Crst declaration + // validation performed in ValidateCrsts() should have detected such a cycle first). + bool madeProgress = false; + + // If we spot any types that are in a group (SameLevelAs relationship) then we defer assigning a + // rank till we've dealt with any non-group types (we wish to always place type groups in their + // very own rank else the Crst rank violation detection code won't detect violations between + // members of the group and singleton types that happened to be assigned rank on the same pass). + List<CrstTypeGroup> deferredGroups = new List<CrstTypeGroup>(); + + // Scan through all the Crst types. + foreach (CrstType crst in m_crsts.Values) + { + // Skip those types that already have a rank assigned. + if (crst.Level != CrstType.CrstUnassigned) + continue; + + // We're looking for Crst types that no longer have any types that can be acquired while they + // are already held. This indicates that it's safe to assign the current rank to them (since + // there are no remaining dependencies that need to be ranked first (i.e. with a lower rank + // value than this type). + if (crst.AcquiredBeforeList.Count == 0) + { + if (crst.Group == null) + { + // If this type is not part of the group we can go and assign the rank right away. + crst.Level = currLevel; + madeProgress = true; + unsorted--; + } + else if (!deferredGroups.Contains(crst.Group)) + // Otherwise we'll defer ranking this group member until all the singletons are + // processed. + deferredGroups.Add(crst.Group); + } + } + + // We've gone through the entire collection of Crst types and assigned the current rank level to + // any singleton Crst types that qualify. Now deal with any group members we detected (it's + // possible that more than one group qualifies for ranking at this level but we need to be careful + // to assign distinct rank values to each group to avoid hiding lock rank violations (since group + // members are always allowed to be acquired alongside any other type with the same rank value). + // Iterate over each distinct group that we found in this pass. + foreach (CrstTypeGroup group in deferredGroups) + { + // Look at our progress flag here. If it is false then we didn't have any singleton Crst types + // ranked at this level and we haven't processed any other groups at this level either. Thus + // we can rank this group at the current level. Otherwise at least one type was already ranked + // with this level so we need to increment to a new, distinct level to avoid ranking + // ambiguity. + if (madeProgress) + currLevel++; + + // Iterate through each Crst type that is a member of this group assigning them the (same) + // current rank. + foreach (CrstType crst in group.Members) + { + // Double check that each member has the same dependencies (i.e. they should all be empty + // by now). There should be no way that this error should ever occur, it's just paranoia + // on my part. + if (crst.AcquiredBeforeList.Count != 0) + throw new Exception("Internal error: SameLevel CrstTypes with differing rulesets"); + + crst.Level = currLevel; + unsorted--; + } + + // Once we've processed at least one group we've made progress this iteration. + madeProgress = true; + } + + // If we didn't manage to assign rank to at least one Crst type then we're not going to do any + // better next iteration either (because no state was updated in this iteration). This should only + // occur in the presence of a dependency cycle and we shouldn't get that here after a successful + // call to ValidateCrsts(), so this check is pure paranoia. + if (!madeProgress) + { + Console.WriteLine(String.Format("{0} unsorted remain", unsorted)); + throw new Exception("Cycle detected trying to assign level " + currLevel.ToString()); + } + + // Loop through all the unranked Crsts types and remove any AcquiredBefore relationships that + // involve types we've already leveled (since those types, by definition, have already been + // assigned a lower rank). + foreach (CrstType crst in m_crsts.Values) + { + if (crst.Level != CrstType.CrstUnassigned) + continue; + List<CrstType> prunedCrsts = crst.AcquiredBeforeList.FindAll(Unleveled); + crst.AcquiredBeforeList = prunedCrsts; + } + + // Done with this rank level, move to the next. + currLevel++; + } + } + + // Predicate method used with List<T>.FindAll() to locate Crst types that haven't had their rank assigned + // yet. + static bool Unleveled(CrstType crst) + { + return crst.Level == CrstType.CrstUnassigned; + } +} + +// Class used to parse a CrstTypes.def file into a dictionary of Crst type definitions. It uses a simple lexer +// that removes comments then forms tokens out of any consecutive non-whitespace characters. An equally simple +// recursive descent parser forms Crst instances by parsing the token stream. +class TypeFileParser +{ + // Remember the input file name and the dictionary we're meant to populate. + string m_typeFileName; + Dictionary<string, CrstType> m_crsts; + + // Compile regular expressions for detecting comments and tokens in the parser input. + Regex m_commentRegex = new Regex(@"//.*"); + Regex m_tokenRegex = new Regex(@"^(\s*(\S+)\s*)*"); + + // Input is lexed into an array of tokens. We record the index of the token being currently parsed. + Token[] m_tokens; + int m_currToken; + + // Parse the given file into Crst type definitions and place these definitions in the dictionary provided. + // Syntax errors are signalled via ParseError derived exceptions. + public void ParseFile(string typeFileName, Dictionary<string, CrstType> crsts) + { + m_typeFileName = typeFileName; + m_crsts = crsts; + + // Lex the file into tokens. + InitTokenStream(); + + // Parse the tokens according to the grammar set out at the top of this file. + // Loop until we have no further tokens to process. + while (!IsEof()) + { + // Grab the next token. + Token token = NextToken(); + + // We're at the top level, so the token had better be 'Crst'. + if (token.Id != KeywordId.Crst) + throw new UnexpectedTokenError(token, KeywordId.Crst); + + // OK, parse the rest of this single Crst type definition. + ParseCrst(); + } + } + + // Parse a single Crst type definition. + void ParseCrst() + { + // The next token had better be an identifier (the Crst type name). + Token token = NextToken(); + if (token.Id != KeywordId.Id) + throw new UnexpectedTokenError(token, KeywordId.Id); + + // The Crst instance might already exist in the dictionary (forward references to a Crst type cause + // these entries to auto-vivify). But in that case the entry better not be marked as 'Defined' which + // would indicate a double declaration. + CrstType crst; + if (m_crsts.ContainsKey(token.Text)) + { + crst = m_crsts[token.Text]; + if (crst.Defined) + throw new ParseError(String.Format("Duplicate definition for CrstType '{0}'", token.Text), token); + } + else + { + // Otherwise this Crst type hasn't been seen thus far so we allocate a new instance and add it to + // the dictionary. + crst = new CrstType(token.Text); + m_crsts.Add(crst.Name, crst); + } + + // We're defining, not just referencing this type. + crst.Defined = true; + + // Parse any attributes inside this definition (until we see an 'End' token). + bool parsingCrst = true; + while (parsingCrst) + { + // Get the next token. Either some attribute keyword or 'End'. + token = NextToken(); + List<CrstType> list; + + switch (token.Id) + { + + case KeywordId.AcquiredBefore: + // Simply parse the following list of Crst types into the current type's AcquiredBefore list. + ParseList(crst.AcquiredBeforeList); + break; + + case KeywordId.AcquiredAfter: + // AcquiredAfter is trickier. To make the ranking algorithm's life easier we actually + // normalize all rules to the AcquiredBefore form (see LevelCrsts() for the reasoning). So we + // capture the list of Crst types that follow the AcquiredAfter keyword and then append the + // current type to the AcquiredBefore list of each type found. + list = new List<CrstType>(); + ParseList(list); + foreach (CrstType priorCrst in list) + priorCrst.AcquiredBeforeList.Add(crst); + break; + + case KeywordId.SameLevelAs: + // Parse the following list of Crst types them let the CrstTypeGroup class handle the + // resulting updates to the type groups we're currently maintaining. See the comments for the + // CrstTypeGroup class for more details. + list = new List<CrstType>(); + ParseList(list); + foreach (CrstType sameLevelCrst in list) + CrstTypeGroup.Join(crst, sameLevelCrst); + break; + + case KeywordId.Unordered: + crst.Level = CrstType.CrstUnordered; + break; + + case KeywordId.End: + parsingCrst = false; + break; + + default: + throw new UnexpectedTokenError(token, + KeywordId.AcquiredBefore, + KeywordId.AcquiredAfter, + KeywordId.SameLevelAs, + KeywordId.Unordered); + } + } + } + + // Parse a list of Crst type names. Any other token terminates the list (without error and without + // consuming that token from the stream). The list of tokens is returned as a list of corresponding + // CrstTypes (which are auto-vivified in the output dictionary if they haven't been declared yet). + void ParseList(List<CrstType> list) + { + // Parse tokens until we find a non-indentifier. + while (true) + { + Token token = NextToken(); + if (token.Id != KeywordId.Id) + { + // We found the list terminator. Push the non-identifier token back into the stream for our + // caller to parse correctly. + UnwindToken(); + return; + } + + // Look up or add a new CrstType corresponding to this type name. + CrstType crst; + if (m_crsts.ContainsKey(token.Text)) + crst = m_crsts[token.Text]; + else + { + crst = new CrstType(token.Text); + m_crsts[crst.Name] = crst; + } + + // Add the type to the output list we're building. + list.Add(crst); + } + } + + // Lex the input file into an array of tokens. + void InitTokenStream() + { + StreamReader file = new StreamReader(m_typeFileName); + int lineNumber = 1; + List<Token> tokenList = new List<Token>(); + + // Read the file a line at a time. + string line; + while ((line = file.ReadLine()) != null) + { + // Remove comments from the current line. + line = m_commentRegex.Replace(line, ""); + + // Match all contiguous non-whitespace characters as individual tokens. + Match match = m_tokenRegex.Match(line); + if (match.Success) + { + // For each token captured build a token instance and record the token text and the file, line + // and column at which it was encountered (these latter in order to produce useful syntax + // error messages). + CaptureCollection cap = match.Groups[2].Captures; + for (int i = 0; i < cap.Count; i++) + tokenList.Add(new Token(m_typeFileName, cap[i].Value, lineNumber, cap[i].Index)); + } + + lineNumber++; + } + + // Record the list of tokens we captured as an array and reset the index of the next token to be + // handled by the parser. + m_tokens = tokenList.ToArray(); + m_currToken = 0; + } + + // Have we run out of tokens to parse? + bool IsEof() + { + return m_currToken >= m_tokens.Length; + } + + // Get the next token and throw an exception if we ran out. + Token NextToken() + { + if (m_currToken >= m_tokens.Length) + throw new UnexpectedEofError(); + return m_tokens[m_currToken++]; + } + + // Push the last token parsed back into the stream. + void UnwindToken() + { + if (m_currToken <= 0) + throw new InvalidOperationException(); + m_currToken--; + } + + // The various keywords we can encounter (plus Id for identifiers, which are currently always Crst type + // names). + internal enum KeywordId + { + Id, + Crst, + End, + AcquiredBefore, + AcquiredAfter, + Unordered, + SameLevelAs, + } + + // Class encapsulating a single token captured from the input file. + internal class Token + { + // Hash of keyword text to enum values. + static Dictionary<string, KeywordId> s_keywords; + + // The characters comprising the text of the token from the input file. + string m_text; + + // Where the token was found (for error messages). + string m_file; + int m_line; + int m_column; + + // The ID of the keyword this token represents (or KeywordId.Id). + KeywordId m_id; + + // Static class initialization. + static Token() + { + // Populate the keyword hash. No sense building complex finite state machines to improve the + // efficiency of keyword lexing here since the input file (and keyword set) is never going to be + // big enough to justify the extra work. + s_keywords = new Dictionary<string, KeywordId>(); + s_keywords.Add("crst", KeywordId.Crst); + s_keywords.Add("end", KeywordId.End); + s_keywords.Add("acquiredbefore", KeywordId.AcquiredBefore); + s_keywords.Add("acquiredafter", KeywordId.AcquiredAfter); + s_keywords.Add("unordered", KeywordId.Unordered); + s_keywords.Add("samelevelas", KeywordId.SameLevelAs); + } + + public Token(string file, string text, int line, int column) + { + m_file = file; + m_text = text; + m_line = line; + m_column = column; + + // Map token text to keyword ID. True keywords (not identifiers) are case insensitive so normalize + // the text to lower case before performing the keyword hash lookup. + string canonName = m_text.ToLower(); + if (s_keywords.ContainsKey(canonName)) + m_id = s_keywords[canonName]; + else + m_id = KeywordId.Id; + } + + public string Text {get { return m_text; }} + public string Location {get { return String.Format("{0} line {1}, column {2}", m_file, m_line, m_column); }} + public KeywordId Id {get { return m_id; }} + } + + // Base class for all syntax errors reported by the parser. + internal class ParseError : Exception + { + // A raw error message. + public ParseError(string message) + : base(message) + {} + + // An error message tagged with a file, line and column (coming from an error token). + public ParseError(string message, Token errorToken) + : base(String.Format("{0}: {1}", errorToken.Location, message)) + {} + + // Produce a textual name for the given keyword type. + protected static string IdToName(KeywordId id) + { + if (id == KeywordId.Id) + return "a CrstType name"; + return String.Format("'{0}'", id.ToString()); + } + } + + // Syntax error used when an unexpected token is encountered which further lists the valid tokens that + // would otherwise have been accepted. + internal class UnexpectedTokenError : ParseError + { + // Produce an unexpected token message with a file, line and column coming from an error token and + // optionally the names of zero or more tokens that would have been accepted. + public UnexpectedTokenError(Token errorToken, params KeywordId[] expected) + : base(FormatErrorMessage(errorToken, expected)) + {} + + static string FormatErrorMessage(Token errorToken, KeywordId[] expected) + { + StringBuilder message = new StringBuilder(String.Format("Unexpected token '{0}' at {1}", + errorToken.Text, errorToken.Location)); + if (expected.Length == 0) + { + } + else if (expected.Length == 1) + { + message.Append(String.Format("; expected {0}", IdToName(expected[0]))); + } + else + { + message.Append("; expected one of "); + for (int i = 0; i < expected.Length - 1; i++) + message.Append(String.Format("{0}, ", IdToName(expected[i]))); + message.Append(IdToName(expected[expected.Length - 1])); + + } + + return message.ToString(); + } + } + + // Syntax error used when we unexpectedly ran out of tokens. + internal class UnexpectedEofError : ParseError + { + public UnexpectedEofError() + : base("Unexpected end of file") + {} + } +} + +// This class represents an instance of a Crst type. These are unqiuely identified by case-sensitive name (the +// same as the enum name used in vm code, minus the 'Crst' prefix). +class CrstType : IComparable +{ + // Special level constants used to indicate unordered Crst types or those types we haven't gotten around + // to ranking yet. + public static readonly int CrstUnordered = -1; + public static readonly int CrstUnassigned = -2; + + // Name of the type, e.g. "AppDomainCache" for the CrstAppDomainCache type. + string m_name; + + // The numeric ranking assigned to this type. Starts as CrstUnassigned and then becomes either + // CrstUnordered (while parsing the input file) or a number >= 0 (during LevelCrsts()). + int m_level; + + // List of Crst types that can be legally acquired while this one is held. (AcquiredAfter relationships + // are by switching the terms and adding to the second type's AcquiredBefore list). + List<CrstType> m_acquiredBeforeCrsts; + + // Either null if this Crst type is not in (or has not yet been determined to be in) a SameLevelAs + // relationship or points to a CrstTypeGroup that records all the sibling types at the same level (that + // have been discovered thus far during parsing). + CrstTypeGroup m_group; + + // Set once a definition for this type has been discovered. Used to detect double definitions and types + // referenced without definitions. + bool m_defined; + + public CrstType(string name) + { + m_name = name; + m_level = CrstUnassigned; + m_acquiredBeforeCrsts = new List<CrstType>(); + m_group = null; + m_defined = false; + } + + public string Name {get { return m_name; }} + public int Level {get { return m_level; } set { m_level = value; }} + public List<CrstType> AcquiredBeforeList {get { return m_acquiredBeforeCrsts; } set { m_acquiredBeforeCrsts = value; }} + public CrstTypeGroup Group {get { return m_group; } set { m_group = value; }} + public bool Defined {get {return m_defined; } set { m_defined = value; }} + + // Helper used to sort CrstTypes. The sort order is lexical based on the type name. + public int CompareTo(object other) + { + return m_name.CompareTo(((CrstType)other).m_name); + } +} + +// Every time a SameLevelAs relationship is used we need to be careful to keep track of the transitive closure +// of all types bound in the relationship. That's because such a relationship impacts the other dependency +// rules (each member of a SameLevelAs group must behave as though it has exactly the same dependency rules as +// all the others). Identifying all the members is tricky because "A SameLevelAs B" and "B SameLevelAs C" +// implies "A SameLevelAs C". So we use a separate tracking structure, instances of the CrstTypeGroup type, to +// do the bookkeeping for us. Each Crst type belongs to either zero or one CrstTypeGroups. As we find new +// SameLevelAs relationships we create new groups, add types to existing groups or merge groups (as previous +// distinct groups are merged by the discovery of a SameLevelAs relationship that links them). By the time +// parsing has finished we are guaranteed to have discovered all the distinct, disjoint groups and to have +// fully populated them with the transitive closure of all related types. We can them normalize all groups +// members so they share the same AcquiredBefore relationships. +class CrstTypeGroup +{ + // We record every group that has been formed so far. This makes normalizing all groups easier. + static List<CrstTypeGroup> s_groups = new List<CrstTypeGroup>(); + + // Crst types that are members of the current group. There are no duplicates in this list. + List<CrstType> m_members = new List<CrstType>(); + + // Declare a SameLevelAs relationship between the two Crst types given. Groups will be assigned, created + // or merged as required to maintain our guarantees (each CrstType is a member of at most one group and + // all CrstTypes involved in the same transitive closure of a SameLevelAs relationship are members of one + // group). + public static void Join(CrstType crst1, CrstType crst2) + { + CrstTypeGroup group; + + if (crst1 == crst2) + { + // In this case the type refers to itself. Create a singleton group for this type if it doesn't + // already exist. + if (crst1.Group == null) + { + group = new CrstTypeGroup(); + group.m_members.Add(crst1); + + s_groups.Add(group); + + crst1.Group = group; + } + } + else if (crst1.Group == null && crst2.Group == null) + { + // Neither types belong to a group already. So we can create a new one and add both types to it. + group = new CrstTypeGroup(); + group.m_members.Add(crst1); + group.m_members.Add(crst2); + + s_groups.Add(group); + + crst1.Group = group; + crst2.Group = group; + } + else if (crst1.Group == null) + { + // The first type doesn't belong to a group yet but the second does. So we can simply add the + // first type to the second group. + group = crst2.Group; + group.m_members.Add(crst1); + + crst1.Group = group; + } + else if (crst2.Group == null) + { + // As for the case above but the group/no-group positions are reversed. + group = crst1.Group; + group.m_members.Add(crst2); + + crst2.Group = group; + } + else if (crst1.Group != crst2.Group) + { + // Both types belong to different groups so we'll have to merge them. Add the members of group 2 + // to group 1 and throw away group 2. + group = crst1.Group; + CrstTypeGroup absorbGroup = crst2.Group; + foreach (CrstType crst in absorbGroup.m_members) + { + group.m_members.Add(crst); + crst.Group = group; + } + + s_groups.Remove(absorbGroup); + } + + // The only case left is when both types are already in the same group and there's no work needed in + // this case. + } + + // Normalize all the groups we created during parsing. See below for the definition of normalization. + public static void NormalizeAllRules() + { + foreach (CrstTypeGroup group in s_groups) + group.NormalizeRules(); + } + + // Normalize this group. This involves adjusting the AcquiredBefore list of each member to be the union of + // all such rules within the group. This step allows us to detect cycles in the dependency graph that + // would otherwise remain hidden if we only examined the unnormalized AcquiredBefore rules. + void NormalizeRules() + { + // This local will contain the union of all AcquiredBefore rules. + List<CrstType> acquiredBeforeList = new List<CrstType>(); + + // Iterate through each member of the group. + foreach (CrstType crst in m_members) + { + // Add each AcquiredBefore rule we haven't already seen to the union. + foreach (CrstType afterCrst in crst.AcquiredBeforeList) + if (!acquiredBeforeList.Contains(afterCrst)) + acquiredBeforeList.Add(afterCrst); + } + + // Reset each member's AcquiredBefore list to a copy of the union we calculated. Note it's important + // to make a (shallow) copy because the ranking process modifies this list and so a shared copy would + // cause unexpected results. + foreach (CrstType crst in m_members) + crst.AcquiredBeforeList = acquiredBeforeList.GetRange(0, acquiredBeforeList.Count); + } + + public List<CrstType> Members {get { return m_members; }} +} |