using System;
using System.Text;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using Immutable;
using S = Lexer.S;
using Lexeme = Lexer.Lexeme;
using PrecedenceDAG = ImmutableDefaultDictionary<string, MixFix.DAGNode>;
using PrecedenceGroupName = System.String;
using Hole = System.Collections.Immutable.ImmutableHashSet<
               string /* PrecedenceGroupName */>;
using static Global;
using static MixFix.Fixity;

public static partial class MixFix {
  public partial class Grammar1 {
    public static Grammar1 Sequence(params Grammar1[] xs)
      => Sequence(xs.ToImmutableList());

    public static Grammar1 Or(params Grammar1[] xs)
      => Or(xs.ToImmutableList());

    public static Grammar1 Empty
      = new Grammar1.Cases.Sequence(Enumerable.Empty<Grammar1>());
      
    public static Grammar1 Impossible
      = new Grammar1.Cases.Or(Enumerable.Empty<Grammar1>());

    // TODO: inline the OR, detect impossible cases (Or of 0)
    public static Grammar1 Sequence(IEnumerable<Grammar1> xs) {
      var filteredXs = xs.Where(x => !x.IsEmpty);
      if (filteredXs.Any(x => x.IsImpossible)) {
        return Impossible;
      } else if (filteredXs.Count() == 0) {
        return Empty;
      } else if (filteredXs.Count() == 1) {
        return filteredXs.Single().ElseThrow(() => new Exception("TODO: use an either to prove that this is safe."));
      } else {
        return new Grammar1.Cases.Sequence(filteredXs);
      }
    }

    public static Grammar1 Or(IEnumerable<Grammar1> xs) {
      var filteredXsNoEmpty = 
        xs.Where(x => !x.IsImpossible)
          .Where(x => !x.IsEmpty);
      var filteredXs =
        (   xs.Any(x => x.IsEmpty)
         && !filteredXsNoEmpty.Any(x => x.AllowsEmpty))
        ? Empty.Cons(filteredXsNoEmpty)
        : filteredXsNoEmpty;
      if (filteredXs.All(x => x.IsImpossible)) {
        return new Grammar1.Cases.Or(Enumerable.Empty<Grammar1>());
      } else if (filteredXs.Count() == 1) {
        return filteredXs.Single().ElseThrow(() => new Exception("TODO: use an either to prove that this is safe."));
      } else {
        return new Grammar1.Cases.Or(filteredXs);
      }
    }

    public static Grammar1 RepeatOnePlus(Grammar1 g)
      => g.IsEmpty
        ? Grammar1.Empty
        : g.IsImpossible
        ? Grammar1.Impossible
        : new Grammar1.Cases.RepeatOnePlus(g);

    public bool IsEmpty {
      get => this.Match(
        Or: l => l.Count() > 0 && l.All(g => g.IsEmpty),
        Sequence: l => l.All(g => g.IsEmpty),
        RepeatOnePlus: g => g.IsEmpty,
        Terminal: t => false,
        Annotated: a => a.Item2.IsEmpty,
        // TODO: when converting to Grammar2, make sure to recompute the .IsEmpty and .IsImpossible and .AllowsEmpty
        Rule: r => false
      );
    }

    // TODO: cache this!
    public bool AllowsEmpty {
      get => this.Match(
        Or: l => l.Count() > 0 && l.Any(g => g.AllowsEmpty),
        Sequence: l => l.All(g => g.IsEmpty),
        // This one should not be true, if it is
        // then the precedence graph may be ill-formed?
        RepeatOnePlus: g => g.AllowsEmpty,
        Terminal: t => false,
        Annotated: a => a.Item2.AllowsEmpty,
        Rule: r => false
      );
    }

    public bool IsImpossible {
      get => this.Match(
        Or: l => l.All(g => g.IsImpossible),
        Sequence: l => l.Any(g => g.IsImpossible),
        RepeatOnePlus: g => g.IsImpossible,
        Terminal: t => false,
        Annotated: a => a.Item2.IsImpossible,
        Rule: r => false
      );
    }

    public static Grammar1 operator |(Grammar1 a, Grammar1 b)
      => Or(a, b);

    public static implicit operator Grammar1((Grammar1 a, Grammar1 b) gs)
      => Sequence(gs.a, gs.b);

    public static implicit operator Grammar1((Grammar1 a, Grammar1 b, Grammar1 c) gs)
      => Sequence(gs.a, gs.b, gs.c);

    public static bool operator true(Grammar1 g) => !g.IsImpossible;
    public static bool operator false(Grammar1 g) => g.IsImpossible;

    public Grammar1 this[string multiplicity] {
      get {
        if (multiplicity != "+") {
          throw new Exception("Unexpected multiplicity");
        } else {
          if (this.IsEmpty) {
            return Or();
          } else {
            return RepeatOnePlus(this);
          }
        }
      }
    }

    private string Paren(bool paren, string s)
      => paren ? $"({s})" : s;

    string CustomToString()
      => this.Match<string>(
        Or: l =>
          l.Count() == 0
          ? "ImpossibleOr"
          : Paren(l.Count() != 1, l.Select(x => x.Str()).JoinWith(" | ")),
        Sequence: l =>
          l.Count() == 0
          ? "EmptySequence"
          : Paren(l.Count() != 1, l.Select(x => x.Str()).JoinWith(", ")),
        RepeatOnePlus: g => $"{g.Str()}+",
        Terminal: t => t.Str(),
        Annotated: a => $"{a.Item1}: {a.Item2}",
        Rule: r => r
      );
  }

  public partial class Grammar2 {
    public bool IsEmpty {
      get => this.Match(
        Or: l => l.All(g => g.IsEmpty),
        Sequence: l => l.All(g => g.IsEmpty),
        RepeatOnePlus: g => g.IsEmpty,
        Terminal: t => false,
        Annotated: a => a.Item2.IsEmpty
      );
    }

    public bool IsImpossible {
      get => this.Match(
        Or: l => l.All(g => g.IsImpossible),
        Sequence: l => l.Any(g => g.IsImpossible),
        RepeatOnePlus: g => g.IsImpossible,
        Terminal: t => false,
        Annotated: a => a.Item2.IsImpossible
      );
    }

    private string Paren(bool paren, string s)
      => paren ? $"({s})" : s;

    string CustomToString()
      => this.Match<string>(
        Or: l =>
          l.Count() == 0
          ? "ImpossibleOr"
          : Paren(l.Count() != 1, l.Select(x => x.Str()).JoinWith(" | ")),
        Sequence: l =>
          l.Count() == 0
          ? "EmptySequence"
          : Paren(l.Count() != 1, l.Select(x => x.Str()).JoinWith(", ")),
        RepeatOnePlus: g => $"{g.Str()}+",
        Terminal: t => t.Str(),
        Annotated: a =>
          //$"Annotated({a.Item1.Str()}, {a.Item2.Str()})"
          $"~{a.Item2.Str()}"
      );
  }

  public partial class Operator {
    private string CustomToString()
    => $"Operator(\"{precedenceGroup}\", {fixity}, {parts.Select(x => x.Match(Hole: h => h.Select(g => g.ToString()).JoinWith("|"), Name: n => $"\"{n}\"")).JoinWith(", ")})";
  }

  public abstract partial class Part {
    public static implicit operator Part(S s)
      => Part.Name(s);
    public static implicit operator Part(string s)
      => Part.Hole(s.Split("|").ToImmutableHashSet());
  }

  public partial class Fixity {
    // Used in the fixity table below.
    public static implicit operator Func<Fixity>(Fixity fixity) => () => fixity;
  }

  public partial class Operator {
    // TODO: cache this for improved complexity
    public Option<ImmutableHashSet<string>> leftmostHole {
      get => parts.First().Bind(firstPart => firstPart.AsHole);
    }

    // TODO: cache this for improved complexity
    public Option<ImmutableHashSet<string>> rightmostHole {
      get => parts.Last().Bind(lastPart => lastPart.AsHole);
    }

    // TODO: does this need any caching?
    public IEnumerable<Part> internalParts {
      get => parts.SkipWhile(part => part.IsHole)
                  .SkipLastWhile(part => part.IsHole);
    }

    private static Func<Fixity> error =
      () => throw new Exception("Internal error: unexpected fixity.");

    private static Func<Fixity> notYet =
      () => throw new NotImplementedException(
        "NonAssociative prefix and postfix operators are not supported for now.");

    private ImmutableList<ImmutableList<Func<Fixity>>> fixityTable = new [] {
      //     neither start    end     both              ←Hole//↓Associativity
      new[]{ Closed, notYet,  notYet, InfixNonAssociative   },//NonAssociative
      new[]{ error,  Postfix, error,  InfixLeftAssociative  },//LeftAssociative
      new[]{ error,  error,   Prefix, InfixRightAssociative },//RightAssociative
    }.Select(ImmutableList.ToImmutableList).ToImmutableList();
    
    public Fixity fixity {
      get {
        var startsWithHole = parts.First()
                                  .Bind(lastPart => lastPart.AsHole)
                                  .IsSome;

        var endsWithHole = parts.First()
                                .Bind(lastPart => lastPart.AsHole)
                                .IsSome;

        var row = associativity.Match(
          NonAssociative: () => 0,
          LeftAssociative: () => 1,
          RightAssociative: () => 2);

        var column = ((!startsWithHole) && (!endsWithHole)) ? 0
                   : (( startsWithHole) && (!endsWithHole)) ? 1
                   : ((!startsWithHole) && ( endsWithHole)) ? 2
                   : (( startsWithHole) && ( endsWithHole)) ? 3
                   : throw new Exception("impossible");

        return fixityTable[row][column]();
      }
    }
  }

  public partial class DAGNode {
    // TODO: cache this for improved complexity
    public IEnumerable<Operator> allOperators {
      get => ImmutableList(
          closed,
          prefix,
          postfix,
          infixNonAssociative,
          infixRightAssociative,
          infixLeftAssociative
        ).SelectMany(x => x);
    }

    // TODO: cache this for improved complexity
    public Option<ImmutableHashSet<string>> leftmostHole {
      get => allOperators.First(@operator => @operator.leftmostHole);
    }

    // TODO: cache this for improved complexity
    public Option<ImmutableHashSet<string>> rightmostHole {
      get => allOperators.First(@operator => @operator.rightmostHole);
    }

    // TODO: cache this for improved complexity
    // TODO: find a better name
    public ImmutableHashSet<string> leftmostHole_ {
      get => leftmostHole.Else(ImmutableHashSet<string>.Empty);
    }

    // TODO: cache this for improved complexity
    // TODO: find a better name
    public ImmutableHashSet<string> rightmostHole_ {
      get => rightmostHole.Else(ImmutableHashSet<string>.Empty);
    }
  }

  public static DAGNode EmptyDAGNode = new DAGNode(
       closed:                ImmutableList<Operator>.Empty,
       prefix:                ImmutableList<Operator>.Empty,
       postfix:               ImmutableList<Operator>.Empty,
       infixNonAssociative:   ImmutableList<Operator>.Empty,
       infixRightAssociative: ImmutableList<Operator>.Empty,
       infixLeftAssociative:  ImmutableList<Operator>.Empty
     );

  public static PrecedenceDAG EmptyPrecedenceDAG
    = new PrecedenceDAG(EmptyDAGNode);

  public static Whole Add<Whole>(this ILens<DAGNode, Whole> node, Operator @operator) {
    return @operator.Cons(@operator.fixity.Match(
      Closed:
        () => node.Closed(),
      Prefix:
        () => node.Prefix(),
      Postfix:
        () => node.Postfix(),
      InfixNonAssociative:
        () => node.InfixNonAssociative(),
      InfixRightAssociative:
        () => node.InfixRightAssociative(),
      InfixLeftAssociative:
        () => node.InfixLeftAssociative()
    ));
  }

  public static void CheckHole(PrecedenceDAG precedenceDAG, Operator @operator, string name, Option<Hole> existing, Option<Hole> @new) {
    existing.IfSome(existingHole =>
      @new.IfSome(newHole => {
        if (! newHole.SetEquals(existingHole)) {
          throw new ParserExtensionException($"Cannot extend parser with operator {@operator}, its {name} hole ({newHole.ToString()}) must either be absent or else use the same precedence groups as the existing operators in {@operator.precedenceGroup}, i.e. {existingHole}.");
        }
        return unit;
      })
    );
  }

  public static void CheckLeftmostHole(PrecedenceDAG precedenceDAG, Operator @operator)
    => CheckHole(
      precedenceDAG,
      @operator,
      "leftmost",
      precedenceDAG[@operator.precedenceGroup].leftmostHole,
      @operator.leftmostHole);

  public static void CheckRightmostHole(PrecedenceDAG precedenceDAG, Operator @operator)
    => CheckHole(
      precedenceDAG,
      @operator,
      "rightmost",
      precedenceDAG[@operator.precedenceGroup].rightmostHole,
      @operator.rightmostHole);

  public static void CheckNonEmpty(PrecedenceDAG precedenceDAG, Operator @operator) {
    if (@operator.parts.Count == 0) {
      throw new ParserExtensionException($"Cannot extend parser with operator {@operator}, it has no parts.");
    }
  }

  public static void CheckConsecutiveHoles(PrecedenceDAG precedenceDAG, Operator @operator) {
    @operator.parts.Aggregate((previous, current) => {
      if (previous.IsHole && current.IsHole) {
        throw new ParserExtensionException($"Cannot extend parser with operator {@operator}, it has two consecutive holes. This is not supported for now.");
      }
      return current;
    });
  }

  public static void CheckSingleUseOfNames(PrecedenceDAG precedenceDAG, Operator @operator) {
    // TODO: check that each name part isn't used elsewhere in a way that adding this operator would could cause ambiguity (use in a different namespace which is bracketed is okay, etc.). Probably something to do with paths reachable from the root.
  }

  public static void CheckNotAlias(PrecedenceDAG precedenceDAG, Operator @operator) {
    if (@operator.parts.Single().Bind(part => part.AsHole).IsSome) {
      throw new ParserExtensionException($"Cannot extend parser with operator {@operator}, it only contains a single hole. Aliases built like this are not supported for now.");
    }
  }

  public static void CheckAcyclic(PrecedenceDAG precedenceDAG, Operator @operator) {
    // TODO: check that the DAG stays acyclic after adding this operator
  }

  public static PrecedenceDAG With(this PrecedenceDAG precedenceDAG, Operator @operator) {
    // This is where all the checks are done to ensure that the
    //   resulting grammar1 is well-formed and assuredly unambiguous.
    // Future extension idea: add an "ambiguous" keyword to
    //   alleviate some restrictions.
    CheckLeftmostHole(precedenceDAG, @operator);
    CheckRightmostHole(precedenceDAG, @operator);
    CheckNonEmpty(precedenceDAG, @operator);
    CheckConsecutiveHoles(precedenceDAG, @operator);
    CheckSingleUseOfNames(precedenceDAG, @operator);
    CheckNotAlias(precedenceDAG, @operator);
    CheckAcyclic(precedenceDAG, @operator);
    return precedenceDAG.lens[@operator.precedenceGroup].Add(@operator);
  }

  public static PrecedenceDAG WithOperator(this PrecedenceDAG precedenceDAG, string precedenceGroup, Semantics semantics, Associativity associativity, params Part[] parts)
    => precedenceDAG.With(
      new Operator(
        precedenceGroup: precedenceGroup,
        semantics: semantics,
        associativity: associativity,
        parts: parts.ToImmutableList()));

  public static Grammar1 ToGrammar1(this Hole precedenceGroups)
    => Grammar1.Or(
         precedenceGroups.Select(precedenceGroup =>
           Grammar1.Rule(precedenceGroup)));

  public static Grammar1 ToGrammar1(this Part part)
    => part.Match(
      Name: name => Grammar1.Terminal(name), 
      Hole: precedenceGroups => precedenceGroups.ToGrammar1());

  public static Grammar1 ToGrammar1(this Operator @operator)
    => Grammar1.Annotated(
         (Annotation.Operator(@operator),
          Grammar1.Sequence(
            @operator.internalParts.Select(
              part => part.ToGrammar1()))));

  public static Grammar1 ToGrammar1(this IEnumerable<Operator> operators)
    => Grammar1.Or(
      operators.Select(@operator => @operator.ToGrammar1()));

  public static Grammar1 ToGrammar1(this DAGNode node) {
    Func<Associativity, Grammar1, Grammar1> SamePrecedence = (a, g)
      => Grammar1.Annotated((Annotation.SamePrecedence(a), g));
    Func<Grammar1, Grammar1> R = g => SamePrecedence(Associativity.RightAssociative, g);
    Func<Grammar1, Grammar1> L = g => SamePrecedence(Associativity.LeftAssociative, g);
    Func<Grammar1, Grammar1> N = g => SamePrecedence(Associativity.NonAssociative, g);
    Func<Grammar1, Grammar1> H = g => Grammar1.Annotated((Annotation.Hole, g));

    var lsucc = H(node.leftmostHole_.ToGrammar1());
    var rsucc = H(node.rightmostHole_.ToGrammar1());
    var closed = node.closed.ToGrammar1();
    var nonAssoc = node.infixNonAssociative.ToGrammar1();
    var prefix = node.prefix.ToGrammar1();
    var postfix = node.postfix.ToGrammar1();
    var infixl = node.infixLeftAssociative.ToGrammar1();
    var infixr = node.infixRightAssociative.ToGrammar1();

    return
        N(closed)
      | N( (lsucc, nonAssoc, rsucc) )
      | R( ((prefix | (lsucc, infixr))["+"], rsucc) )
      | L( (lsucc, (postfix || (infixl, rsucc))["+"]) );
  }

  public static EquatableDictionary<string, Grammar1> ToGrammar1(this PrecedenceDAG precedenceDAG)
    => precedenceDAG.ToEquatableDictionary(
      node => node.Key,
      node => node.Value.ToGrammar1());

  private static Grammar2 Recur(Func<Grammar1, EquatableDictionary<string, Grammar1>, Grammar2> recur, Grammar1 grammar1, EquatableDictionary<string, Grammar1> labeled)
    => grammar1.Match<Grammar2>(
      // TODO: throw exception if lookup fails
      Rule:          r => {
        Grammar1 lr = null;
        try {
          lr = labeled[r];
        } catch (Exception) {
          throw new ParserExtensionException($"Internal error: could not find node {r} in labeled grammar. It only contains labels for: {labeled.Select(kvp => kvp.Key.ToString()).JoinWith(", ")}.");
        }
        return recur(labeled[r], labeled);
      },
      Annotated:     a => Grammar2.Annotated((a.Item1, recur(a.Item2, labeled))),
      Terminal:      t => Grammar2.Terminal(t),
      Sequence:      l => Grammar2.Sequence(l.Select(g => recur(g, labeled))),
      Or:            l => Grammar2.Or(l.Select(g => recur(g, labeled))),
      RepeatOnePlus: g => Grammar2.RepeatOnePlus(recur(g, labeled))
    );

  public static Grammar2 ToGrammar2(this EquatableDictionary<string, Grammar1> labeled)
    => Func.YMemoize<Grammar1, EquatableDictionary<string, Grammar1>, Grammar2>(Recur)(Grammar1.Rule("program"), labeled);

  public static Grammar2 ToGrammar2(this PrecedenceDAG precedenceDAG)
    => precedenceDAG.ToGrammar1().ToGrammar2();
}