/**
 * <copyright>
 *
 * Copyright (c) 2012 Willink Transformations and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v2.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v20.html
 *
 * Contributors:
 *     E.D.Willink - initial API and implementation
 *
 * </copyright>
 */
/*
http://lampwww.epfl.ch/teaching/archive/compilation-ssc/2000/part4/parsing/node3.html

For building parsers (especially bottom-up) a BNF grammar is often better, than EBNF. But it's easy to convert an EBNF Grammar to BNF:

    Convert every repetition { E } to a fresh non-terminal X and add
    X = $\epsilon$ | X E.
    Convert every option [ E ] to a fresh non-terminal X and add
    X = $\epsilon$ | E.
    (We can convert X = A [ E ] B. to X = A E B | A B.)
    Convert every group ( E ) to a fresh non-terminal X and add
    X = E.
    We can even do away with alternatives by having several productions with the same non-terminal.
    X = E | E'. becomes X = E. X = E'. 
    
---
	As above, also normalize so that the output is a
	rule comprising
	-- a disjunction of
	-- one or more conjunctions comprising
	-- zero or more elements.
	
	Additional rules for multiplicities and alternatives are created as sub-rules, some
	of which may be inlined by a subsequent inline transformation.
*/
modeltype ECORE uses 'http://www.eclipse.org/emf/2002/Ecore';
modeltype XBNF uses 'http://www.eclipse.org/ocl/XBNF';
modeltype XBNFwc uses 'http://www.eclipse.org/ocl/XBNFwithCardinality';

transformation normalize(in xtext : XBNFwc, out XBNF);

main() {
	xtext.rootObjects()[XBNF::Syntax]->map syntax2syntax();
}

mapping XBNF::Syntax::syntax2syntax() : XBNF::Syntax {
	var allRules : Sequence(TypedRule) = self.grammars->collect(rules->sortedBy(name));
	var firstRules : OrderedSet(TypedRule) = allRules->collect(r1 | allRules->select(r2 | r1.name = r2.name)->first())->asOrderedSet();
	name := self.name;
	grammars := Sequence { self.map grammars2lexerGrammar(firstRules), self.map grammars2parserGrammar(firstRules) };
	var untypedRules : Sequence(UntypedRule) := grammars.allSubobjectsOfKind(UntypedRule)->selectByKind(UntypedRule);
	untypedRules->forEach(untypedRule) {
		untypedRule.name := untypedRule.typedRule.name + '_' + untypedRule.typedRule.subrules->indexOf(untypedRule).toString();
	};
}

---------------------------------------------------------------------------------------
--	Copy the lexer rules
---------------------------------------------------------------------------------------

mapping XBNF::Syntax::grammars2lexerGrammar(firstRules : Set(TypedRule)) : XBNF::LexerGrammar {
	name := self.name;
	rules := self.grammars.rules->selectByKind(TerminalRule)->map terminalRule2rule(firstRules);
	goals := self.grammars.goals.resolveone(TypedRule);
}

mapping XBNF::TerminalRule::terminalRule2rule(firstRules : Set(TypedRule)) : XBNF::TerminalRule
{
	var subRules : List(XBNF::UntypedRule) = List{};
	name := self.name;
	type := self.type;
	var candidate := self.element.map element2element(subRules, null, self, firstRules);
	element := if candidate.oclIsKindOf(Disjunction)
				then candidate
				else if candidate.oclIsKindOf(Conjunction)
				then object Disjunction {
					debug := self.debug;
					conjunctions += candidate.oclAsType(Conjunction);
				}
				else object Disjunction {
					debug := self.debug;
					conjunctions += object Conjunction {
						debug := self.debug;
						elements += candidate;
					};
				}
				endif
				endif;
	debug := subRules->size().toString();
	subrules := subRules->iterate(r; acc : Sequence(XBNF::UntypedRule) = Sequence{} | acc->append(r));
} 

---------------------------------------------------------------------------------------
--	Create the extra parser rules for XBNF compounds
---------------------------------------------------------------------------------------

mapping XBNF::Syntax::grammars2parserGrammar(firstRules : Set(TypedRule)) : XBNF::ParserGrammar {
	name := self.name;
	var parserRules : Sequence(ParserRule) = self.grammars.rules->selectByKind(ParserRule);
	var parserRuleNames : OrderedSet(String) = parserRules.name->asSet()->sortedBy(n | n);
	var sortedParserRules : Sequence(ParserRule) = parserRules->sortedBy(name);
	rules := parserRuleNames->iterate(prn; acc : OrderedSet(ParserRule) = OrderedSet{} |
		let pr : ParserRule = parserRules->select(name = prn)->any(true) in acc->append(pr.map parserRule2rule(firstRules)));
	goals := self.grammars->selectByKind(ParserGrammar).goals->first().resolveone(TypedRule);
}

mapping XBNF::ParserRule::parserRule2rule(firstRules : Set(TypedRule)) : XBNF::ParserRule
{
	var subRules : List(XBNF::UntypedRule) = List{};
	var theElement : AbstractElement = self.element.map element2element(subRules, null, self, firstRules);
	var disjunction : Disjunction = theElement.asDisjunction();
	name := self.name;
	debug := self.debug;
	type := self.type;
	element := disjunction;
	subrules := subRules->iterate(r; acc : Sequence(XBNF::UntypedRule) = Sequence{} | acc->append(r));
} 

mapping XBNF::AbstractElement::element2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement
disjuncts
ActionAssignment::actionAssignment2element,
Alternatives::alternativesAtRoot2element,
Alternatives::alternativesNested2element,
CharacterRange::characterRange2element,
KeywordAssignment::keywordAssignment2element,
Keyword::keyword2element,
NegatedToken::negatedToken2element,
OneOrMore::oneOrMore2element,
RuleCallAssignment::ruleCallAssignment2element,
RuleCall::ruleCall2element,
Succession::succession2element,
UntilToken::untilToken2element,
Wildcard::wildcard2element,
ZeroOrMore::zeroOrMore2element,
ZeroOrOne::zeroOrOne2element,
AbstractElement::element2element_default
{}

mapping XBNF::AbstractElement::element2element_default(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object Wildcard {
			debug := 'default';
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNF::ActionAssignment::actionAssignment2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object ActionAssignment {
			debug := self.debug;
			feature := self.feature;
			operator := self.operator;
			type := self.type;
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNFwc::Alternatives::alternativesAtRoot2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement
when { self.parentRule <> null }
{
	init {
		result := object Disjunction {
			debug := self.debug;
			conjunctions := self.elements->iterate(e; acc : Sequence(Conjunction) = Sequence {} |
					let eFlat = e.flattenAndMap(subRules, null, firstRules) in
					acc->append(eFlat.asConjunction()));
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNFwc::Alternatives::alternativesNested2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement
{
	init {
		var me : Alternatives = self;
		var alternatives : OrderedSet(AbstractElement) = self.elements;
		var oneRule : XBNF::UntypedRule = object Disjunction {
				debug := '1 : ' + alternatives->size().toString();
				conjunctions := alternatives->iterate(e; acc : Sequence(Conjunction) = Sequence{} | 
					let eFlat = e.flattenAndMap(subRules, null, firstRules) in
					acc->append(eFlat.asConjunction()));
			}.asRule();
		subRules->add(oneRule);
		result := oneRule.asRuleCall().appendAsConjunctions(tailElement);
	}
}

mapping XBNF::CharacterRange::characterRange2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object CharacterRange {
			debug := self.debug;
			left := self.left;
			right := self.right;
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNF::Keyword::keyword2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object Keyword {
			debug := self.debug;
			value := self.value;
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNF::KeywordAssignment::keywordAssignment2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object KeywordAssignment {
			debug := self.debug;
			feature := self.feature;
			operator := self.operator;
			value := self.value;
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNF::NegatedToken::negatedToken2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object NegatedToken {
			debug := self.debug;
			terminal := self.terminal.map element2element(subRules, null, disambiguator, firstRules);
		}.appendAsConjunctions(tailElement);
	}
}

//
//		x+ Y
//
//		X1: x
//		X2: X1 Y
//		X3: X1 X2
//		X: X2 | X3
// - we must handle Y to avoid shift reduce conflicts
//
mapping XBNFwc::OneOrMore::oneOrMore2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		var eFlat := self.element.flattenAndMap(subRules, null, firstRules);
		var oneRule : XBNF::UntypedRule = eFlat.asRule();
		subRules->add(oneRule);
		var oneOrMoreRule := object UntypedRule {};
		oneOrMoreRule.element := object Disjunction { debug := '1 or +';
				conjunctions := Sequence {
					object Conjunction {
						elements := Sequence { oneRule.asRuleCall() };
						if (tailElement <> null) {
							elements += tailElement;
						};
					},
					object Conjunction {
						elements := Sequence { oneRule.asRuleCall(), oneOrMoreRule.asRuleCall() };
					}
				};
			};
		subRules->add(oneOrMoreRule);
		result := oneOrMoreRule.asRuleCall();
	}
}

mapping XBNF::RuleCall::ruleCall2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object RuleCall {
			debug := self.debug;
			referredRule := firstRules->select(r | r.name = self.referredRule.name)->any(true).late resolveone(XBNF::AbstractRule);
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNF::RuleCallAssignment::ruleCallAssignment2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object RuleCallAssignment {
			debug := self.debug;
			feature := self.feature;
			operator := self.operator;
			referredRule := firstRules->select(r | r.name = self.referredRule.name)->any(true).late resolveone(XBNF::AbstractRule);
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNFwc::Succession::succession2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		var mappedTailElement : AbstractElement := if tailElement <> null then tailElement.map element2element(subRules, null, disambiguator, firstRules) else null endif;
		var element : AbstractElement := self.flattenAndMap(subRules, mappedTailElement, firstRules);
		result := element.asConjunction();
	}
}

mapping XBNF::UntilToken::untilToken2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object UntilToken {
			debug := self.debug;
			terminal := self.terminal.map element2element(subRules, null, disambiguator, firstRules);
		}.appendAsConjunctions(tailElement);
	}
}

mapping XBNF::Wildcard::wildcard2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		result := object Wildcard {
			debug := self.debug;
		}.appendAsConjunctions(tailElement);
	}
}

//
//		x* Y
//
//		X1: x
//		X2: Y
//		X3: X1 X2
//		X: X2 | X3
//
mapping XBNFwc::ZeroOrMore::zeroOrMore2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		var eFlat := self.element.flattenAndMap(subRules, null, firstRules);
		var oneRule = eFlat.asRule();
		subRules->add(oneRule);
		var oneOrMoreRule := object UntypedRule {};
		oneOrMoreRule.element := object Disjunction { debug := '1 or +';
			conjunctions := Sequence {
				object Conjunction {
					elements := Sequence { oneRule.asRuleCall() };
				},
				object Conjunction {
					elements := Sequence { oneOrMoreRule.asRuleCall(), oneRule.asRuleCall() };
				}
			};
		};
		subRules->add(oneOrMoreRule);
		var zeroOrMoreRule = object Disjunction { debug := '0 or +';
			conjunctions := Sequence {
				object XBNF::Epsilon {}.asConjunction(),
				oneOrMoreRule.asRuleCall().asConjunction()
			};
		}.asRule();
		subRules->add(zeroOrMoreRule);
		result := zeroOrMoreRule.asRuleCall().appendAsConjunctions(tailElement);
	}
}

//
//		x?
//
//		X1: x
//		X: epsilon | X1
//
mapping XBNFwc::ZeroOrOne::zeroOrOne2element(inout subRules : List(XBNF::UntypedRule), tailElement : AbstractElement, disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement {
	init {
		var eFlat := self.element.flattenAndMap(subRules, null, firstRules);
		var zeroOrOneRule : UntypedRule = object Disjunction {
				debug := '0 or 1';
				conjunctions := Sequence { object XBNF::Epsilon {}.asConjunction(), eFlat.asConjunction() };
			}.asRule();
		subRules->add(zeroOrOneRule);
		result := zeroOrOneRule.asRuleCall().appendAsConjunctions(tailElement);
	}
}

-- Helpers

---------------------------------------------------------------------------------------
--	Return the conjunction of this element and tailElement which may be null.
---------------------------------------------------------------------------------------
helper XBNF::AbstractElement::appendAsConjunctions(tailElement : AbstractElement) : AbstractElement {
	return	if tailElement = null then
				self
			else if tailElement.oclIsKindOf(Conjunction) then
				object Conjunction { elements := tailElement.oclAsType(Conjunction).elements->prepend(self); }
			else
				object Conjunction { elements := Sequence{self, tailElement}; }
			endif
			endif;
}

helper XBNF::Conjunction::appendAsConjunctions(tailElement : AbstractElement) : AbstractElement {
	return	if tailElement = null then
				self
			else if tailElement.oclIsKindOf(Conjunction) then
				object Conjunction { elements := tailElement.oclAsType(Conjunction).elements
					->iterate(e; acc : Sequence(AbstractElement) = self.elements->asSequence() | acc->append(e));}
			else 
				object Conjunction { elements := self.elements->append(tailElement);}
			endif
			endif;
}

---------------------------------------------------------------------------------------
--	Return a conjunction containing thos element.
---------------------------------------------------------------------------------------
helper AbstractElement::asConjunction() : Conjunction {
	return object Conjunction { debug := '1'; elements := self->asSequence(); };
}

helper Conjunction::asConjunction() : Conjunction {
	return self;
}

---------------------------------------------------------------------------------------
--	Return a disjunction containing thos element.
---------------------------------------------------------------------------------------
helper AbstractElement::asDisjunction() : Disjunction {
	return object Disjunction { debug := '1'; conjunctions := self.asConjunction()->asSequence(); };
}

helper Disjunction::asDisjunction() : Disjunction {
	return self;
}

---------------------------------------------------------------------------------------
--	Return a rule containing thos element.
---------------------------------------------------------------------------------------
helper AbstractElement::asRule() : UntypedRule {
	return object UntypedRule {
		element := self.asDisjunction();
	};
}

helper AbstractRule::asRuleCall() : RuleCall {
	return object RuleCall {
		debug := self.name;
		referredRule := self;
	};
}

---------------------------------------------------------------------------------------
--	Return an in-order sequence of the flattened terms comprising head followed by self.
---------------------------------------------------------------------------------------
helper AbstractElement::flattenAndMap(inout subRules : List(XBNF::UntypedRule), outerTailElement : AbstractElement, firstRules : Set(TypedRule)) : AbstractElement {
	var flatElements : Sequence(AbstractElement) := self.flatten(Sequence{}, self);
	var flatSize : Integer = flatElements->size();
	return Sequence{1..flatSize}->iterate(i; innerTailElement : AbstractElement = outerTailElement |
		let iReverse = flatSize-i+1 in
		let flatElement = flatElements->at(iReverse) in
		flatElement.map element2element(subRules, innerTailElement, self, firstRules));
}

helper XBNF::AbstractElement::flatten(head : Sequence(AbstractElement), disambiguator : OclAny) : Sequence(AbstractElement)
{
	return head->append(self);
}

helper XBNFwc::Succession::flatten(head : Sequence(AbstractElement), disambiguator : OclAny) : Sequence(AbstractElement)
{
	return self.elements->iterate(e; acc : Sequence(AbstractElement) = head | e.flatten(acc, disambiguator));
}