anchor.diff:  module internal FsLexYacc.FsLex.AST
   
   open System.Collections.Generic
  -open FSharp.Text
  +open System.Globalization
   open Microsoft.FSharp.Collections
  -open Internal.Utilities
   open Internal.Utilities.Text.Lexing
   
   let (|KeyValue|) (kvp:KeyValuePair<_,_>) = kvp.Key,kvp.Value
  
positive.code: 
  type NodeSetSet = Set<NfaNodeIdSet>
  
  let newDfaNodeId = 
      let i = ref 0 
      fun () -> let res = !i in incr i; res
     
  let NfaToDfa (nfaNodeMap:NfaNodeMap) nfaStartNode = 
      let numNfaNodes = nfaNodeMap.Count
      let rec EClosure1 (acc:NfaNodeIdSetBuilder) (n:NfaNode) = 
          if not (acc.Contains(n.Id)) then 
              acc.Add(n.Id) |> ignore;
              if n.Transitions.ContainsKey(Epsilon) then
                  match n.Transitions.[Epsilon] with 
                  | [] -> () // this Clause is an optimization - the list is normally empty
                  | tr -> 
                      //printfn "n.Id = %A, #Epsilon = %d" n.Id tr.Length
                      tr |> List.iter (EClosure1 acc) 
  
      let EClosure (moves:list<NodeId>) = 
          let acc = new NfaNodeIdSetBuilder(HashIdentity.Structural)
          for i in moves do
              EClosure1 acc nfaNodeMap.[i];
          new NfaNodeIdSet(acc)
  
      // Compute all the immediate one-step moves for a set of NFA states, as a dictionary
      // mapping inputs to destination lists
      let ComputeMoves (nset:NfaNodeIdSet) = 
          let moves = new MultiMap<_,_>()
          nset.Iterate(fun nodeId -> 
              for (KeyValue(inp,dests)) in nfaNodeMap.[nodeId].Transitions do
                  if inp <> Epsilon then 
                      match dests with 
                      | [] -> ()  // this Clause is an optimization - the list is normally empty
                      | tr -> tr |> List.iter(fun dest -> AddToMultiMap moves inp dest.Id))
          moves
  
      let acc = new NfaNodeIdSetBuilder(HashIdentity.Structural)
      EClosure1 acc nfaStartNode;
      let nfaSet0 = new NfaNodeIdSet(acc)
  
      let dfaNodes = Dictionary<NfaNodeIdSet,DfaNode>()
  
      let GetDfaNode nfaSet = 
          if dfaNodes.ContainsKey(nfaSet) then 
              dfaNodes.[nfaSet]
          else 
              let dfaNode =
                  { Id= newDfaNodeId(); 
                    Name = nfaSet.Fold (fun s nid -> nfaNodeMap.[nid].Name+"-"+s) ""; 
                    Transitions=[];
                    Accepted= nfaSet.Elements 
                              |> Seq.map (fun nid -> nfaNodeMap.[nid].Accepted)
                              |> List.concat }
              //Printf.printfn "id = %d" dfaNode.Id;
  
              dfaNodes.Add(nfaSet,dfaNode); 
              dfaNode
              
      let workList = Stack()
      workList.Push nfaSet0
      let doneSet = HashSet()
  
negative.code:     let prev = LookupMultiMap trDict a
      trDict.[a] <- b::prev
  
  type NfaNodeMap() =
      let map = new Dictionary<int,NfaNode>(100)
      member x.Item with get(nid) = map.[nid]
      member x.Count = map.Count
  
      member x.NewNfaNode(trs,ac) =
          let nodeId = map.Count+1 // ID zero is reserved
          let trDict = new Dictionary<_,_>(List.length trs)
          for (a,b) in trs do
             AddToMultiMap trDict a b
  
          let node : NfaNode = {Id=nodeId; Name=string nodeId; Transitions=trDict; Accepted=ac}
          map.[nodeId] <-node
          node
  
  let LexerStateToNfa (macros: Map<string,_>) (clauses: Clause list) =
  
      /// Table allocating node ids
      let nfaNodeMap = new NfaNodeMap()
  
      /// Compile a regular expression into the NFA
      let rec CompileRegexp re dest =
          match re with
          | Alt res ->
              let trs = res |> List.map (fun re -> (Epsilon,CompileRegexp re dest))
              nfaNodeMap.NewNfaNode(trs,[])
          | Seq res ->
              List.foldBack (CompileRegexp) res dest
          | Inp (Alphabet c) ->
              nfaNodeMap.NewNfaNode([(c, dest)],[])
  
          | Star re ->
              let nfaNode = nfaNodeMap.NewNfaNode([(Epsilon, dest)],[])
              let sre = CompileRegexp re nfaNode
              AddToMultiMap nfaNode.Transitions Epsilon sre
              nfaNodeMap.NewNfaNode([(Epsilon,sre); (Epsilon,dest)],[])
          | Macro m ->
              if not (macros.ContainsKey(m)) then failwithf "The macro %s is not defined" m
              CompileRegexp (macros.[m]) dest
  
          // These cases unwind the difficult cases in the syntax that rely on knowing the
          // entire alphabet.
          //
          // Note we've delayed the expension of these until we've worked out all the 'special' Unicode characters
          // mentioned in the entire lexer spec, i.e. we wait until GetAlphabet returns a reliable and stable answer.
          | Inp (UnicodeCategory uc) ->
              let re = Alt([ yield Inp(Alphabet(EncodeUnicodeCategory uc))
                             // Also include any specific characters in this category
                             for c in GetSingleCharAlphabet() do
                                 if System.Char.GetUnicodeCategory(c) = unicodeCategories.[uc] then
                                      yield Inp(Alphabet(EncodeChar(c))) ])
              CompileRegexp re dest
  
          | Inp Any ->
              let re = Alt([ for n in GetAlphabet() do yield Inp(Alphabet(n)) ])
              CompileRegexp re dest
  
          | Inp (NotCharSet chars) ->
              let re = Alt [ // Include any characters from those in the alphabet besides those that are not immediately excluded
                             for c in GetSingleCharAlphabet() do
                                 let ec = EncodeChar c
                                 if not (chars.Contains(ec)) then
                                     yield Inp(Alphabet(ec))
  
                             // Include all unicode categories
                             // That is, negations _only_ exclude precisely the given set of characters. You can't
                             // exclude whole classes of characters as yet
                             if !unicode then
                                 let ucs = chars |> Set.map(DecodeChar >> System.Char.GetUnicodeCategory)
                                 for KeyValue(nm,uc) in unicodeCategories do
                                     //if ucs.Contains(uc) then
                                     //    printfn "warning: the unicode category '\\%s' ('%O') is automatically excluded by this character set negation. Consider adding this to the negation." nm uc
                                     //else
                                         yield Inp(Alphabet(EncodeUnicodeCategory nm))
                           ]
              CompileRegexp re dest
  
      let actions = new System.Collections.Generic.List<_>()
  
      /// Compile an acceptance of a regular expression into the NFA
      let sTrans macros nodeId (regexp,code) =
          let actionId = actions.Count
          actions.Add(code)
          let sAccept = nfaNodeMap.NewNfaNode([],[(nodeId,actionId)])
          CompileRegexp regexp sAccept
  
      let trs = clauses |> List.mapi (fun n x -> (Epsilon,sTrans macros n x))
      let nfaStartNode = nfaNodeMap.NewNfaNode(trs,[])
      nfaStartNode,(actions |> Seq.readonly), nfaNodeMap
  
  // TODO: consider a better representation here.
  type internal NfaNodeIdSetBuilder = HashSet<NodeId>
  
  type internal NfaNodeIdSet(nodes: NfaNodeIdSetBuilder) =
      // BEWARE: the next line is performance critical
      let s = nodes |> Seq.toArray
      do Array.sortInPlaceWith compare s // 19
  
      // These are all surprisingly slower (because they create two arrays):
      //let s = nodes |> Seq.toArray |> Array.sort
      //let s = nodes |> Seq.toArray |> Array.sortWith compare // 76
      //let s = nodes |> Seq.toArray |> (fun arr -> Array.sortInPlace arr; arr) // 76
  
      member x.Representation = s
      member x.Elements = s
      member x.Fold f z = Array.fold f z s
      interface System.IComparable with
          member x.CompareTo(y:obj) =
              let y = (y :?> NfaNodeIdSet)
              let xr = x.Representation
              let yr = y.Representation
              let c = compare xr.Length yr.Length
              if c <> 0 then c else
              let n = yr.Length
              let rec go i =
                  if i >= n then 0 else
                  let c = compare xr.[i] yr.[i]
                  if c <> 0 then c else
                  go (i+1)
              go 0
  
      override x.Equals(y:obj) =
          match y with
          | :? NfaNodeIdSet as y ->
              let xr = x.Representation
              let yr = y.Representation
              let n = yr.Length
              xr.Length = n &&
              (let rec go i = (i < n) && xr.[i] = yr.[i] && go (i+1)
               go 0)
          | _ -> false
  
  