<commit_before>// Copyright (c) 2019 <NAME>
//
// This software is released under the MIT License.
// https://opensource.org/licenses/MIT

module Farkle.Builder.LALRBuild

open Farkle.Collections
open Farkle.Grammar
open System.Collections.Generic
open System.Collections.Immutable

type LR0Item = {
    Production: Production
    DotPosition: int
}
with
    static member Create prod = {Production = prod; DotPosition = 0}
    member x.IsAtEnd = x.Production.Handle.Length = x.DotPosition
    member x.CurrentSymbol = x.Production.Handle.[x.DotPosition]
    member x.AdvanceDot() =
        if x.IsAtEnd then
            x
        else
            {x with DotPosition = x.DotPosition + 1}
    override x.ToString() =
        [
            Seq.take x.DotPosition x.Production.Handle |> Seq.map string
            Seq.singleton "•"
            Seq.skip x.DotPosition x.Production.Handle |> Seq.map string
        ]
        |> Seq.concat
        |> String.concat " "
        |> sprintf "%O ::= %s" x.Production.Head

[<NoComparison; NoEquality>]
type LR0ItemSet = {
    Index: int
    Kernel: Set<LR0Item>
    Goto: Dictionary<LALRSymbol, int>
}
with
    static member Create idx kernel = {Index = idx; Kernel = kernel; Goto = Dictionary()}

/// A special type which represents the lookahead symbol.
type LookaheadSymbol =
    /// The lookahead symbol is a `Terminal`.
    | Terminal of Terminal
    /// The lookahead symbol is the EOF, AKA $.
    | [<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>] End

/// Creates the LR(0) kernel sets for a grammar.
/// A function that gets the corresponding productions for
/// a nonterminal and the start symbol are required.
let createLR0KernelItems fGetAllProductions startSymbol =

    let itemSets = ImmutableArray.CreateBuilder()

    let kernelMap = Dictionary()

    let newItemSet kernel =
        kernelMap.Add(kernel, itemSets.Count)
        let itemSet = LR0ItemSet.Create itemSets.Count kernel
        itemSets.Add(itemSet)
        itemSet

    let rec impl kernel =
        let itemSet = newItemSet kernel
        let q = Queue(kernel)
        // We could use a table of visited nonterminals, but it might create problems
        // when many productions of the kernel have the same head.
        // Forget what you saw before! We must keep a table of visited items.
        // It created problems when the same production appeared in the closure,
        // but with different dot position. See the calculator's state #10 (#2 in GOLD Parser).
        let visitedItems = HashSet()
        while q.Count <> 0 do
            let item = q.Dequeue()
            if visitedItems.Add(item) then
                if not item.IsAtEnd then
                    match item.CurrentSymbol with
                    | LALRSymbol.Terminal _ -> ()
                    | LALRSymbol.Nonterminal nont ->
                        nont
                        |> fGetAllProductions
                        |> Set.iter (LR0Item.Create >> q.Enqueue)
        visitedItems
        |> Seq.filter (fun x -> not x.IsAtEnd)
        |> Seq.groupBy (fun x -> x.CurrentSymbol)
        |> Seq.iter (fun (sym, kernelItems) ->
            // All these items are guaranteed to be kernel items; their dot is never at the beginning.
            let kernelSet = kernelItems |> Seq.map (fun x -> x.AdvanceDot()) |> set
            match kernelMap.TryGetValue(kernelSet) with
            | true, idx -> itemSet.Goto.Add(sym, idx)
            | false, _ -> itemSet.Goto.Add(sym, impl kernelSet))
        itemSet.Index

    startSymbol
    |> fGetAllProductions
    |> Set.map LR0Item.Create
    |> impl
    |> ignore

    itemSets.ToImmutable()

/// Computes the FIRST set of the `Nonterminal`s of the given sequence of `Production`s.
/// A `None` in the set of a nonterminal is the empty symbol, AKA Epsilon, or ε.
let computeFirstSetMap productions =
    let dict = MultiMap.create()
    let containsEmpty (x: LALRSymbol) =
        match x with
        | LALRSymbol.Terminal _ -> false
        | LALRSymbol.Nonterminal nont -> dict.Contains(nont, None)

    productions
    |> Seq.iter (fun {Head = x; Handle = xs} ->
        if xs.IsEmpty then
            dict.Add(x, None) |> ignore)

    let mutable changed = true

    while changed do
        changed <- false
        productions<commit_msg>Use an immutable dictionary to store the GOTO table of an item set.<commit_after>// Copyright (c) 2019 <NAME>
//
// This software is released under the MIT License.
// https://opensource.org/licenses/MIT

module Farkle.Builder.LALRBuild

open Farkle.Collections
open Farkle.Grammar
open System.Collections.Generic
open System.Collections.Immutable

type LR0Item = {
    Production: Production
    DotPosition: int
}
with
    static member Create prod = {Production = prod; DotPosition = 0}
    member x.IsAtEnd = x.Production.Handle.Length = x.DotPosition
    member x.CurrentSymbol = x.Production.Handle.[x.DotPosition]
    member x.AdvanceDot() =
        if x.IsAtEnd then
            x
        else
            {x with DotPosition = x.DotPosition + 1}
    override x.ToString() =
        [
            Seq.take x.DotPosition x.Production.Handle |> Seq.map string
            Seq.singleton "•"
            Seq.skip x.DotPosition x.Production.Handle |> Seq.map string
        ]
        |> Seq.concat
        |> String.concat " "
        |> sprintf "%O ::= %s" x.Production.Head

type LR0ItemSet = {
    Index: int
    Kernel: Set<LR0Item>
    Goto: ImmutableDictionary<LALRSymbol, int>
}
with
    static member Create idx kernel = {Index = idx; Kernel = kernel; Goto = ImmutableDictionary.Empty}

/// A special type which represents the lookahead symbol.
type LookaheadSymbol =
    /// The lookahead symbol is a `Terminal`.
    | Terminal of Terminal
    /// The lookahead symbol is the EOF, AKA $.
    | [<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>] End

/// Creates the LR(0) kernel sets for a grammar.
/// A function that gets the corresponding productions for
/// a nonterminal and the start symbol are required.
let createLR0KernelItems fGetAllProductions startSymbol =

    let itemSets = ImmutableArray.CreateBuilder()

    let kernelMap = Dictionary()

    let newItemSet kernel =
        kernelMap.Add(kernel, itemSets.Count)
        let itemSet = LR0ItemSet.Create itemSets.Count kernel
        itemSets.Add(itemSet)
        itemSet

    let rec impl kernel =
        let itemSet = newItemSet kernel
        let q = Queue(kernel)
        // We could use a table of visited nonterminals, but it might create problems
        // when many productions of the kernel have the same head.
        // Forget what you saw before! We must keep a table of visited items.
        // It created problems when the same production appeared in the closure,
        // but with different dot position. See the calculator's state #10 (#2 in GOLD Parser).
        let visitedItems = HashSet()
        while q.Count <> 0 do
            let item = q.Dequeue()
            if visitedItems.Add(item) then
                if not item.IsAtEnd then
                    match item.CurrentSymbol with
                    | LALRSymbol.Terminal _ -> ()
                    | LALRSymbol.Nonterminal nont ->
                        nont
                        |> fGetAllProductions
                        |> Set.iter (LR0Item.Create >> q.Enqueue)
        let goto =
            visitedItems
            |> Seq.filter (fun x -> not x.IsAtEnd)
            |> Seq.groupBy (fun x -> x.CurrentSymbol)
            |> Seq.map (fun (sym, kernelItems) ->
                // All these items are guaranteed to be kernel items; their dot is never at the beginning.
                let kernelSet = kernelItems |> Seq.map (fun x -> x.AdvanceDot()) |> set
                match kernelMap.TryGetValue(kernelSet) with
                | true, idx -> KeyValuePair(sym, idx)
                | false, _ -> KeyValuePair(sym, impl kernelSet))
            |> ImmutableDictionary.CreateRange
        itemSets.[itemSet.Index] <- {itemSet with Goto = goto}
        itemSet.Index

    startSymbol
    |> fGetAllProductions
    |> Set.map LR0Item.Create
    |> impl
    |> ignore

    itemSets.ToImmutable()

/// Computes the FIRST set of the `Nonterminal`s of the given sequence of `Production`s.
/// A `None` in the set of a nonterminal is the empty symbol, AKA Epsilon, or ε.
let computeFirstSetMap productions =
    let dict = MultiMap.create()
    let containsEmpty (x: LALRSymbol) =
        match x with
        | LALRSymbol.Terminal _ -> false
        | LALRSymbol.Nonterminal nont -> dict.Contains(nont, None)

    productions
    |> Seq.iter (fun {Head = x; Handle = xs} ->
        if xs.IsEmpty then
            dict.Add(x, None) |> ignore)

    let mutable changed = true

    while changed do
        changed <- false
        productions
{'fraction_non_alphanumeric': 0.0892796753466351, 'fraction_numerical': 0.004058167061210686, 'mean_word_length': 2.1810684833273575, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 77, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '498546', 'n_tokens_mistral': 2631, 'n_tokens_neox': 2451, 'n_words': 823}