gramatica 0.2.1

/*!
This crate provides a binary to compile grammars into Rust code and a library implementing Earley's parsing algorithm to parse the grammars specified.

# Usage

This crate is `gramatica`. To use it you should install it in order to acquire the `gramatica_compiler` binary and also add `gramatica` to your dependencies in your project's `Cargo.toml`.

```toml
[dependencies]
gramatica = "0.2"
```

Then, if you have made a grammar file `example.rsg` execute `gramatica_compiler example.rsg > example.rs`. Afterwards you may use the generated file `example.rs` as a source Rust file.

# Recent changes

* Now it is possible to use bindings and mutable references. Like in a rule `(LPar, a @ Left(_), Right(ref mut b), RPar) => (std::mem::take(a),std::mem::take(b))`.
* Added `parser::cursor` to be used instead of `source_index` to avoid indexing over unicode strings.
* Improved management of large files.

# Example: calculator
The classical example is to implement a calculator.

```rust
//This is a just Rust header that it is copied literally
extern crate gramatica;
use std::cmp::Ordering;
use gramatica::{Associativity,EarleyKind,State,Parser,ParsingTablesTrait,AmbiguityInfo};

//Here the proper grammar begins.
//These lines are processed by gramatica_compiler to generate the Token enum and the parsing tables.
//We begin by terminal tokens (symbols that are not in the left of any rule but have a literal representation).
//For this example all terminals are regular expressions. The first argument of re_terminal! is the type entry, as used in a enum.
re_terminal!(Num(f64),"[0-9]*\\.?[0-9]+([eE][-+]?[0-9]+)?");
re_terminal!(Plus,"\\+");
re_terminal!(Minus,"-");
re_terminal!(Star,"\\*");
re_terminal!(Slash,"/");
re_terminal!(Caret,"\\^");
re_terminal!(LPar,"\\(");
re_terminal!(RPar,"\\)");
re_terminal!(NewLine,"\\n");
re_terminal!(_,"\\s+");//Otherwise skip spaces

//Now is the turn of nonterminal tokens. The first one is the default start symbol.
//These have rules written as match clauses, with the pattern being the reduction of the nonterminal token and the expression being the value the token takes when reducing.
//In this case the type of the symbol is empty and so is the expression
nonterminal Input
{
	() => (),
	(Input,Line) => (),
}

//Although the value type of Line is empty we may have code executed on the reduction
nonterminal Line
{
	(NewLine) => (),
	(Expression(value), NewLine) =>
	{
		println!("{}",value);
	},
}

//Finally a token with value type. Each rule creates the value in a different way.
//Most rules are annotated to avoid ambiguities
nonterminal Expression(f64)
{
	(Num(value)) => value,
	#[priority(addition)]
	#[associativity(left)]
	(Expression(l),Plus,Expression(r)) => l+r,
	#[priority(addition)]
	#[associativity(left)]
	(Expression(l),Minus,Expression(r)) => l-r,
	#[priority(multiplication)]
	#[associativity(left)]
	(Expression(l),Star,Expression(r)) => l*r,
	#[priority(multiplication)]
	#[associativity(left)]
	(Expression(l),Slash,Expression(r)) => l/r,
	#[priority(addition)]
	#[associativity(left)]
	(Minus,Expression(value)) => -value,
	#[priority(exponentiation)]
	#[associativity(right)]
	(Expression(l),Caret,Expression(r)) => l.powf(r),
	(LPar,Expression(value),RPar) => value,
}

//The ordering macro-like sets the order of application of the previously annotated rules
ordering!(exponentiation,multiplication,addition);

//Finally an example of using the grammar to parse some lines from stdin.
//We could do this or something similar in a different file if we desired to.
use std::io::BufRead;
fn main()
{
	let stdin=std::io::stdin();
	for rline in stdin.lock().lines()
	{
		let line=rline.unwrap()+"\n";
		println!("line={}",line);
		match Parser::<Token,ParsingTables>::parse(&line,None)
		{
			Err(x) => println!("error parsing: {:?}",x),
			Ok(x) => println!("parsed correctly: {:?}",x),
		};
	}
}
```

# Advanced Lexer

To define terminal tokens not expressable with regular expressions you may use the following. It must containg a _match function returning an option containing the number of chars mathed and the value of the token.

```rust
terminal LitChar(char)
{
	fn _match(parser: &mut Parser<Token,ParsingTables>, source:&str) -> Option<(usize,char)>
	{
		let mut characters=source.chars();
		if (characters.next())==(Some('\''))
		{
			let mut c=characters.next().unwrap();
			let mut size=3;
			if c=='\\'
			{
				c=(characters.next().unwrap());
				size=4;
			}
			if characters.next().unwrap()=='\''
			{
				Some((size,c))
			}
			else
			{
				None
			}
		}
		else
		{
			None
		}
	}
}
```

Since version 0.1.1 there is also a `keyword_terminal!` macro:

```rust
keyword_terminal!(Const,"const");
```

# Parsing values as match clauses

Each rule is written as a match clause, whose ending expression is the value that the nonterminal token gets after being parsed. For example, to parse a list of statements:

```rust
nonterminal Stmts(Vec<StmtKind>)
{
	(Stmt(ref stmt)) => vec![stmt.clone()],
	(Stmts(ref stmts),Stmt(ref stmt)) =>
	{
		let mut new=(stmts.clone());
		new.push(stmt.clone());
		new
	},
}
```

Reductions only execute if they are part of the final syntactic tree.

# Precedence by annotations
To avoid ambiguities you have two options: to ensure the grammar does not contain them or to priorize rules by introducing annotations. In the example of the calculator we have seen two kinds:
- `#[priority(p_name)]` to declare a rule with priority `p_name`. Later there should be a `ordering!(p_0,p_1,p_2,...)` macro-like to indicate that `p_0` should reduce before `p_1`.
- `#[associativity(left/right)]` to decide how to proceed when nesting the same rule.

# Example: Parsing JSON

```rust
extern crate gramatica;

use std::cmp::Ordering;
use gramatica::{Associativity,EarleyKind,State,Parser,ParsingTablesTrait,AmbiguityInfo};

//See https://www.json.org/

use std::rc::Rc;

//We define an auxiliar type to store JSON values
#[derive(Clone,Debug,PartialEq)]
enum JsonValue
{
	Literal(String),
	Number(f64),
	Object(Vec<(String,JsonValue)>),
	Array(Vec<JsonValue>),
	True,
	False,
	Null,
}


// ---- Start of the grammar ----
keyword_terminal!(True,"true");
keyword_terminal!(False,"false");
keyword_terminal!(Null,"null");

re_terminal!(Number(f64),"[0-9]*\\.?[0-9]+([eE][-+]?[0-9]+)?");

terminal LitStr(String)
{
	//This function has limited escaping capabilities
	fn _match(parser: &mut Parser<Token,ParsingTables>, source:&str) -> Option<(usize,String)>
	{
		let mut ret=None;
		let mut characters=source.chars();
		if (characters.next())!=(Some('"'))
		{
		}
		else
		{
			let mut size=1;
			let mut r=String::from("\"");
			while true
			{
				match characters.next()
				{
					None => break,
					Some('"') =>
					{
						ret=(Some((size+1,r+&"\"")));
						break;
					},
					Some('\\') =>
					{
						match characters.next()
						{
							None => break,
							//Some(c) => r+='\\'+c,
							Some(c) =>
							{
								r.push('\\');
								r.push(c);
							}
						};
						size+=2;
					},
					Some(c) =>
					{
						//r+=&String::from(c);
						r.push(c);
						size+=1;
					},
				};
			}
		}
		ret
	}
}

re_terminal!(LBrace,"\\{");
re_terminal!(RBrace,"\\}");
re_terminal!(LBracket,"\\[");
re_terminal!(RBracket,"\\]");
re_terminal!(Comma,",");
re_terminal!(Colon,":");
re_terminal!(_,"\\s+|\n");//Otherwise skip spaces

nonterminal Object(JsonValue)
{
	(LBrace,RBrace) => JsonValue::Object(vec![]),
	(LBrace,Members(ref list),RBrace) => JsonValue::Object(list.clone()),
}

nonterminal Members(Vec<(String,JsonValue)>)
{
	(Pair(ref s,ref value)) => vec![(s.clone(),value.clone())],
	//(Pair,Comma,Members) => (),
	(Members(ref list),Comma,Pair(ref s,ref value)) =>
	{
		let mut new=(list.clone());
		new.push((s.clone(),value.clone()));
		new
	},
}

nonterminal Pair(String,JsonValue)
{
	(LitStr(ref s),Colon,Value(ref value)) => (s.clone(),value.clone()),
}

nonterminal Array(Vec<JsonValue>)
{
	(LBracket,RBracket) => vec![],
	(LBracket,Elements(ref list),RBracket) => list.clone(),
}

nonterminal Elements(Vec<JsonValue>)
{
	(Value(ref value)) => vec![value.clone()],
	//(Value,Comma,Elements) => (),
	(Elements(ref list),Comma,Value(ref value)) =>
	{
		let mut new=(list.clone());
		new.push(value.clone());
		new
	},
}

nonterminal Value(JsonValue)
{
	(LitStr(ref s)) => JsonValue::Literal(s.clone()),
	(Number(v)) => JsonValue::Number(v),
	(Object(ref value)) => value.clone(),
	(Array(ref list)) => JsonValue::Array(list.clone()),
	(True) => JsonValue::True,
	(False) => JsonValue::False,
	(Null) => JsonValue::Null,
}

// ---- End of the grammar ----

use std::io::{BufRead,Read};

//As example, we parse stdin for a JSON object
fn main()
{
	let stdin=std::io::stdin();
	let mut buf=String::new();
	stdin.lock().read_to_string(&mut buf);
	match Parser::<Token,ParsingTables>::parse(&buf,None)
	{
		Err(x) => println!("error parsing: {:?}",x),
		Ok(x) => println!("parsed correctly: {:?}",x),
	};
}
```

# Example: Parsing basic XML

```rust
//A very basic xml grammar

extern crate gramatica;

use std::cmp::Ordering;
use gramatica::{Associativity,EarleyKind,State,Parser,ParsingTablesTrait,AmbiguityInfo};

// see https://www.w3.org/People/Bos/meta-bnf
// also http://cs.lmu.edu/~ray/notes/xmlgrammar/

use std::rc::Rc;

//We define an auxiliar type to store XML elements
#[derive(Clone,Debug,PartialEq)]
struct XMLElement
{
	name: String,
	attrs: Vec<(String,String)>,
	contents: Vec<XMLContent>,
}

#[derive(Clone,Debug,PartialEq)]
enum XMLContent
{
	Element(XMLElement),
	Data(String),
}


// ---- Start of the grammar ----

re_terminal!(Space(String),"(\\s|\n)+");
re_terminal!(Ident(String),"[a-zA-Z\\x80-\\xff_][a-zA-Z0-9\\x80-\\xff_]*");

terminal LitStr(String)
{
	fn _match(parser: &mut Parser<Token,ParsingTables>, source:&str) -> Option<(usize,String)>
	{
		let mut ret=None;
		let mut characters=source.chars();
		if (characters.next())!=(Some('"'))
		{
		}
		else
		{
			let mut size=1;
			let mut r=String::from("\"");
			while true
			{
				match characters.next()
				{
					None => break,
					Some('"') =>
					{
						ret=(Some((size+1,r+&"\"")));
						break;
					},
					Some('\\') =>
					{
						match characters.next()
						{
							None => break,
							//Some(c) => r+='\\'+c,
							Some(c) =>
							{
								r.push('\\');
								r.push(c);
							}
						};
						size+=2;
					},
					Some(c) =>
					{
						//r+=&String::from(c);
						r.push(c);
						size+=1;
					},
				};
			}
		}
		ret
	}
}

re_terminal!(CloseEmpty,"/>");
re_terminal!(BeginClose,"</");

re_terminal!(Equal,"=");
re_terminal!(LT,"<");
re_terminal!(GT,">");

re_terminal!(Other(char),".");

nonterminal Document(XMLElement)
{
	(Element(ref elem)) => elem.clone(),
}

nonterminal Element(XMLElement)
{
	(EmptyElemTag(ref name,ref attrs)) => XMLElement{name:name.clone(),attrs:attrs.clone(),contents:vec![]},
	(STag(ref name, ref attrs),Content(ref content),ETag) => XMLElement{name:name.clone(),attrs:attrs.clone(),contents:content.clone()},
}

nonterminal EmptyElemTag(String,Vec<(String,String)>)
{
	(LT,Ident(ref name),Attributes(ref attrs),MaybeSpace,CloseEmpty) => (name.clone(),attrs.clone()),
}

nonterminal Attributes(Vec<(String,String)>)
{
	() => vec![],
	(Attributes(ref attrs),Space,Attribute(ref a, ref b)) =>
	{
		let mut new=(attrs.clone());
		new.push((a.clone(),b.clone()));
		new
	},
}

nonterminal Attribute(String,String)
{
	(Ident(ref a),Equal,LitStr(ref b)) => (a.clone(),b.clone()),
}

nonterminal STag(String,Vec<(String,String)>)
{
	(LT,Ident(ref name),Attributes(ref attrs),MaybeSpace,GT) => (name.clone(),attrs.clone()),
}

nonterminal ETag(String)
{
	(BeginClose,Ident(ref s),MaybeSpace,GT) => s.clone(),
}

nonterminal Content(Vec<XMLContent>)
{
	(CharData(ref s)) => vec![XMLContent::Data(s.clone())],
	(CharData(ref s),Contents(ref list)) =>
	{
		let mut new=vec![XMLContent::Data(s.clone())];
		new.extend(list.iter().map(|x|x.clone()));
		new
	},
}

nonterminal Contents(Vec<XMLContent>)
{
	() => vec![],
	(Contents(ref list),Element(ref elem),CharData(ref s)) =>
	{
		let mut new=(list.clone());
		new.push(XMLContent::Element(elem.clone()));
		if s!=""
		{
			new.push(XMLContent::Data(s.clone()));
		}
		new
	},
}

nonterminal MaybeSpace
{
	() => (),
	(Space) => (),
}

nonterminal CharData(String)
{
	() => String::new(),
	(CharData(ref s),Space(ref o)) => format!("{}{}",s,o),
	(CharData(ref s),Ident(ref o)) => format!("{}{}",s,o),
	(CharData(ref s),Equal) => format!("{}=",s),
	(CharData(ref s),Other(o)) => format!("{}{}",s,o),
}

// ---- End of the grammar ----

use std::io::{BufRead,Read};

//As example, we parse stdin for a XML element
fn main()
{
	let stdin=std::io::stdin();
	let mut buf=String::new();
	stdin.lock().read_to_string(&mut buf);
	match Parser::<Token,ParsingTables>::parse(&buf,None)
	{
		Err(x) => println!("error parsing: {:?}",x),
		Ok(x) => println!("parsed correctly: {:?}",x),
	};
}
```

*/

extern crate regex;

use std::collections::HashMap;
use regex::Regex;
use std::cmp::Ordering;
use std::marker::PhantomData;
use std::fmt::Debug;

#[derive(Debug)]
pub enum Associativity
{
	Left,
	Right,
}

#[derive(Debug)]
pub enum ParsingError
{
	NotInGrammar,
	Ambiguous,
	BadToken,
}

///Record on how a state was produced.
#[derive(Clone,Debug)]
pub enum EarleyKind
{
	///State created by advancing state self.2 from set self.1 by completing the state self.0.
	Complete(usize,usize,usize),//reduced state, set,  state
	///State created by a scan procedure while advancing over token self.0 and while in state self.1.
	Scan(usize,usize),//set, state
	///State created by expanding a grammar rule while in state self.0.
	Predict(usize),//state index
}

#[derive(Clone,Debug)]
pub struct AmbiguityInfo<T>
{
	///States involved in the ambiguity.
	states: Vec<State<T>>,
	///Token index at which the ambiguity occurs.
	index: usize,
}

impl<T> Default for AmbiguityInfo<T>
{
	fn default() -> Self
	{
		AmbiguityInfo{
			states: vec![],
			index: 0,
		}
	}
}

#[derive(Clone,Debug)]
pub struct State<T>
{
	///The associate rule to this state.
	pub rule: usize,
	///Token in the left.
	pub left: usize,
	///Tokens in the right.
	pub right: Vec<usize>,
	///The state boundary. I.e., number of tokens in the right already processed. Equals `right.len()` when already processed.
	pub position: usize,
	///The state set from where this state was predicted.
	pub original_set: usize,
	///A record of which produced the state and used to compute the final value.
	pub kind: EarleyKind,
	//values: Vec<Token>,
	pub values: Vec<T>,
	//computed_value: Token,
	///When we have a computed value it is stored here.
	pub computed_value: Option<T>,
	///Stores information about ambiguities when they happen.
	pub ambiguity_info: AmbiguityInfo<T>,
}

impl<T:Clone+Default> State<T>
{
	///Whether all tokens in the rule has been processed.
	pub fn finished(&self)->bool
	{
		self.position==self.right.len()
	}
	///Get the next token in the rule, unchecked.
	pub fn next(&self)->usize
	{
		self.right[self.position]
	}
	///Get the next token in the rule. But checking if finished.
	pub fn try_next(&self)->Option<usize>
	{
		if self.position==self.right.len()
		{
			None
		}
		else
		{
			Some(self.right[self.position])
		}
	}
	//pub fn is_next_terminal(&self)->bool
	//{
	//	table_terminal(self.next())
	//}
	///Creates a copy state pointing to the next token in the rule.
	pub fn advance(&self)->State<T>
	{
		State{
			rule: self.rule,
			left:self.left,
			right:self.right.clone(),
			position:self.position+1,
			original_set: self.original_set,
			kind: self.kind.clone(),
			//values: self.values.clone(),
			values: Vec::default(),
			//computed_value: Token::DummyStart,
			//computed_value: T::default(),
			computed_value: None,
			ambiguity_info: self.ambiguity_info.clone(),
		}
	}
}

impl<T:Default> State<T>
{
	pub fn new(rule:usize, left:usize, right:Vec<usize>, set:usize, kind:EarleyKind) -> State<T>
	{
		State{
			rule,
			left,
			right,
			position:0,
			original_set:set,
			kind,
			values:Vec::new(),
			//computed_value:T::default(),
			computed_value: None,
			ambiguity_info:AmbiguityInfo::default(),
		}
	}
}

pub struct StateSet<T>
{
	pub states: Vec<State<T>>,
}

impl<T> StateSet<T>
{
	pub fn predict(&mut self, mut state: State<T>)
	{
		for s in self.states.iter()
		{
			//if s.left==state.left && s.position==state.position && s.right==state.right
			if s.rule==state.rule && s.position==state.position
			{
				return;
			}
		}
		//TODO: why do we even allow the grammar to fill this?
		state.values.clear();
		self.states.push(state);
	}
}

///The functions defining the grammar to use.
pub trait ParsingTablesTrait<T>
{
	///Give the initial state.
	fn initial()->usize;
	///Extract a token.
	fn match_some(parser:&mut Parser<T,Self>) -> Option<(usize,T)> where Self:Sized;
	///for each token->right in grammar, add the rule to self.sets[index]
	fn predict(parser:&mut Parser<T,Self>,index:usize,state_index:usize,token:usize) where Self:Sized;
	///Compute the value of a state. Assumes all dependencies are already been computed.
	fn compute_value(state:&mut State<T>);
	///Says whether a token is a terminal token.
	fn table_terminal(token_index:usize)->bool;
	///Compares the priority of two rules.
	fn table_priority(a:usize, b:usize) -> Option<Ordering>;
	///Check whether we resolve ambiguity and how.
	fn table_associativity(rule:usize) -> Option<Associativity>;
	///Bring a token into `usize` type.
	fn to_usize(token:&T) -> usize;
	///Clone a terminal and otherwise std::mem::take it.
	fn take_token(token:&mut T) -> T where T:Clone+Default,
	{
		if Self::table_terminal(Self::to_usize(token)){
			token.clone()
		} else {
			std::mem::take(token)
		}
	}
}

///The main structure, containing the intermediate data.
pub struct Parser<'a,T,Tables:ParsingTablesTrait<T>>
{
	///A list of state groups with shared rules.
	pub sets: Vec<StateSet<T>>,
	///The string being parsed.
	pub source: &'a str,
	///The current position at the source string while tokenizing.
	///TODO: this is very inadequate, as they are unicode strings...
	pub source_index: usize,
	///A cursor to current position.
	pub cursor: &'a str,
	///The list of tokens after tokenization.
	pub tokens: Vec<T>,
	///For each token we keep its being index and end index relative to the string.
	///TODO: again, bad idea for unicode strings...
	pub tokens_range: Vec<(usize,usize)>,
	///A collection of compiled regular expressions, for repeated use.
	pub regex_map: HashMap<String,Regex>,
	///0 for no output
	///1 for for some output on errors
	///2 for some little info
	///3 for quite some text
	pub verbosity: u8,
	pub phantom: PhantomData<Tables>,
}

impl<'a,T:Default+PartialEq+Clone+Debug,Tables:ParsingTablesTrait<T>> Parser<'a,T,Tables>
{
	/**
	Direct call to the parsing algorithm. Builds the parser and performs tokenization and parsing itself.
	`source` is the string being parsed.
	`initial` is initial state, None to use the default.
	`verbosity` is one of the following
	- 0 for no output,
	- 1 for for some output on errors,
	- 2 for some little info,
	- 3 for quite some text.
	**/
	pub fn parse(source:&str, initial:Option<usize>, verbosity:u8) -> Result<T,ParsingError>
	{
		let mut initial_state=Tables::initial();
		if let Some(x)=initial
		{
			initial_state=x;
		}
		let n = source.len();//we could prefer to count actual chars.
		let mut sets = Vec::with_capacity(n+1);
		sets.push(
			StateSet{
				states:vec![ State{
					rule:0,
					left:0,
					right:vec![initial_state],
					position:0,
					original_set: 0,
					kind: EarleyKind::Predict(0),
					//values: vec![Token::DummyStart],
					//computed_value: Token::DummyStart,
					values: vec![T::default()],
					//computed_value: T::default(),
					computed_value: None,
					ambiguity_info: AmbiguityInfo::default(),
				}]
			}
		);
		let mut parser=Parser::<T,Tables>{
			sets,
			source,
			source_index:0,
			cursor: source,
			tokens: Vec::with_capacity(n),
			tokens_range: Vec::with_capacity(n),
			regex_map: HashMap::new(),
			verbosity,
			phantom: PhantomData,
		};
		if verbosity >= 2 { println!("gramatica: Parser::parse created parser"); }
		parser.tokenize()?;
		if verbosity>=2 {
			println!("gramatica: Parser::parse tokenized");
			println!("gramatica: Parser::parse tokenized with {} tokens, filling {} bytes",parser.tokens.len(),parser.tokens.len()*std::mem::size_of::<T>());
		}
		parser.earley()
	}
	pub fn re(&mut self, regex:&'a str, source:&str) -> Option<(usize,String)>
	{
		//let s=String::from("^")+regex;
		let s=format!("^({})",regex);
		let r=
		{
			if !self.regex_map.contains_key(&s)
			{
				let x=Regex::new(&s).expect("gramatica: could not build regex.");
				self.regex_map.insert(s.clone(),x);
			}
			self.regex_map.get(&s).expect("gramatica: regex not in map even after inserting")
		};
		match r.captures(source)
		{
			Some(cap) =>
			{
				let m=cap.get(0).expect("gramatica: regex failed to capture, but said it did.");
				Some((m.end(),m.as_str().to_string()))
			},
			None => None,
		}
	}
	pub fn keyword(&mut self, key:&str, source:&str) -> Option<(usize,String)>
	{
		let mut key_chars=key.chars();
		let mut source_chars=source.chars();
		loop
		{
			match (key_chars.next(),source_chars.next())
			{
				//None => match source_chars.next()
				//{
				//	Some('a'...'z' | 'A'...'Z' | '_') => return None,
				//	_ => return Some((key.len(),key.to_string())),
				//},
				//Some(c) =>

				//(None,Some('a'...'z' | 'A'...'Z' | '_')) => return None,
				(None,Some(d)) => match d
				{
					'a'..='z' | 'A'..='Z' | '_' => return None,
					_ => return Some((key.len(),key.to_string())),
				},
				(None,None) => return Some((key.len(),key.to_string())),
				(Some(c),Some(d)) => if c!=d { return None;},
				_ => return None,
			};
		}
	}
	pub fn tokenize(&mut self) -> Result<(),ParsingError>
	{
		while self.source_index<self.source.len()
		{
			if self.verbosity>=3 { println!("gramatica: Parser::tokenize {index}/{total}",index=self.source_index,total=self.source.len()); }
			//match self.match_some()
			//match ParsingTables::match_some(self)
			match Tables::match_some(self)
			{
				None =>
				{
					let end = self.source_index+100.min(self.source.len());
					let s=self.source[self.source_index..end].to_string();
					println!("gramatica: Did not match anything '{}'",s);
					return Err(ParsingError::BadToken);
				},
				Some((size,token)) =>
				{
					//println!("Got token {:?} with size {}",token,size);
					//if let Token::DummyStart=token {}
					//else
					//{
					//	self.tokens.push(token);
					//}
					if T::default()!=token
					{
						self.tokens.push(token);
						self.tokens_range.push((self.source_index,self.source_index+size));
					}
					self.source_index+=size;
					self.cursor = self.cursor.split_at(size).1;
					//Could this be a cause of the bad performance?
					//It seems fine.
					//self.cursor = unsafe {
					//	self.cursor.get_unchecked(size..)
					//};
				},
			};
		}
		Ok(())
	}
	///Perform the Earley parser over the internal tokenized string.
	pub fn earley(&mut self) -> Result<T,ParsingError>
	{
		let n=self.tokens.len();
		for index in 0..n+1
		{
			if self.verbosity>=3{ println!("gramatica: index={index}/{n}"); }
			if self.sets[index].states.len()==0
			{
				println!("gramatica: unexpected token {:?}",self.tokens[index-1]);
				let (start,end)=self.tokens_range[index-1];
				let showing_start= if start>100 {start-100} else {0};
				let showing_end= if end+100>=self.source.len() {self.source.len()} else {start+100};
				println!("BEFORE<{}>",self.source[showing_start..start].to_string());
				println!("THEN<{}>",self.source[start..end].to_string());
				println!("AFTER<{}>",self.source[end..showing_end].to_string());
				print!("Tokens=...");
				let token_start = if index>20 { index-20 } else {0};
				let token_end = if index+20>self.tokens.len() {self.tokens.len()} else { index+20 };
				for i in token_start..index-1
				{
					print!("{:?},",self.tokens[i]);
				}
				print!("[{:?}],",self.tokens[index-1]);
				for i in index..token_end
				{
					print!("{:?},",self.tokens[i]);
				}
				println!("");
				return Err(ParsingError::NotInGrammar);
			}
			let last=index==n;
			//if last
			//{
			//	println!("At index={} END",index);
			//}
			//else
			//{
			//	println!("At index={} token={:?}",index,self.tokens[index]);
			//}
			let mut state_index=0;// increasing index over growing vector.
			let mut newset=StateSet{states:vec![]};
			while state_index < self.sets[index].states.len()
			{
				let state=self.sets[index].states[state_index].clone();
				//println!("\tAt index={} state_index={} state={:?}",index,state_index,state);
				if state.finished()
				{
					//Completer
					//This adds states later in the same set.
					let token=state.left;
					let x=state.original_set;
					let mut priority=true;//true when this state.rule has more priority than others.
					let mut ambiguity=vec![state.clone()];
					for i in 0..self.sets[index].states.len()
					{
						if i==state_index
						{
							continue;
						}
						let other=&self.sets[index].states[i];
						if token!=other.left || x!=other.original_set || !other.finished()
						{
							continue;
						}
						//Two rules parse the same text to the same token, apply priority
						match Tables::table_priority(state.rule,other.rule)
						{
							None =>
							{
								ambiguity.push(other.clone());
								if i<state_index
								{
									priority=false;
									break;
								}
							},
							Some(Ordering::Less) =>
							{
								priority=false;
								//println!("set priority=false for {} because of {}",state_index,i);
								break;
							},
							Some(Ordering::Equal) =>
							{
								//Same priority, use associativity
								//match table_associativity(state.rule)
								match Tables::table_associativity(state.rule)
								{
									None =>
									{
										ambiguity.push(other.clone());
										if i<state_index
										{
											priority=false;
											break;
										}
									},
									Some(Associativity::Left) => if state_index>i
									{
										priority=false;
										//println!("set priority=false for {} because of {} [left associativity]",state_index,i);
										break;
									},
									Some(Associativity::Right) => if state_index<i
									{
										priority=false;
										//println!("set priority=false for {} because of {} [right associativity]",state_index,i);
										break;
									},
								}
							},
							Some(Ordering::Greater) => continue,
						};
					}
					if priority
					{
						//for each state with next=token in set x, advance it to current set
						let mut i=0;
						while i<self.sets[x].states.len()
						{
							//if self.sets[x].states[i].next()==token
							if let Some(t)=self.sets[x].states[i].try_next()
							{
								if token==t
								{
									//self.sets[index].states.push(self.sets[x].states[i].advance());
									let mut new=self.sets[x].states[i].advance();
									//new.values=std::mem::take(&mut );
									//new.values=self.sets[x].states[i].values.clone();
									new.kind=EarleyKind::Complete(state_index,x,i);
									//if ambiguity.len()>1
									//{
									//	println!("Some ambiguity {} at index {}",ambiguity.len(),index);
									//	new.ambiguity_info.states=ambiguity.clone();
									//	new.ambiguity_info.index=index;
									//}
									//if new.values.len()<new.right.len()
									//{
									//	panic!("new state = {:?} at set index={} from reducing {} and advancing ({},{})",new,index,state_index,x,i);
									//}
									self.sets[index].states.push(new);
								}
							}
							i+=1;
						}
					}
				}
				else
				{
					//if state.is_next_terminal()
					//if table_terminal(state.next())
					if Tables::table_terminal(state.next())
					{
						//Scanner
						//If the next token in the rule is a terminal and there is a matching token, just advance.
						//New states are pushed into the next group.
						//if !last && state.next()==self.tokens[index].to_usize()
						if !last && state.next()==Tables::to_usize(&self.tokens[index])
						{
							//newset.states.push(state.advance());
							let mut new=state.advance();
							//new.values=std::mem::take(&mut state.values);
							//new.values=state.values.clone();
							new.kind=EarleyKind::Scan(index,state_index);
							//new.value=self.tokens[index].clone();
							//if new.values.len()==0
							//{
							//	println!("new state = {:?}",new);
							//}
							//new.values[new.position-1]=self.tokens[index].clone();
							newset.states.push(new);
						}
					}
					else
					{
						//Predictor
						//If it is not a terminal token then we query the grammar to add `EarleyKind::Predict` states.
						//These states are added to the final of the current group.
						//They are pusehed through `StateSet.predict`.
						let token=state.next();
						//for each token->right in grammar, add the rule to self.sets[index]
						//ParsingTables::predict(self,index,state_index,token);
						Tables::predict(self,index,state_index,token);
					}
				}
				state_index+=1;
			}
			//self.clean(index);
			self.sets.push(newset);
		}
		if self.verbosity>=2 {
			let total_states=self.sets.iter().map(|set|set.states.len()).sum::<usize>();
			println!("gramatica: Total of {} states, filling {} bytes",total_states,total_states*std::mem::size_of::<State<T>>());
		}
		let mut values=vec![];
		for state_index in 0..self.sets[n].states.len()
		{
			if self.sets[n].states[state_index].left==0 && self.sets[n].states[state_index].finished()
			{
				self.compute_value(n,state_index);
				if self.sets[n].states[state_index].ambiguity_info.states.len()>1
				{
					if self.verbosity>=1 {
						let a=&self.sets[n].states[state_index].ambiguity_info;
						println!("gramatica: Ambiguity at index={} token={:?}",a.index,self.tokens[a.index-1]);
						let (start,end)=self.tokens_range[a.index-1];
						let showing_start= if start>100 {start-100} else {0};
						let showing_end= if end+100>=self.source.len() {self.source.len()} else {start+100};
						println!("BEFORE<{}>",self.source[showing_start..start].to_string());
						println!("THEN<{}>",self.source[start..end].to_string());
						println!("AFTER<{}>",self.source[end..showing_end].to_string());
					}
					return Err(ParsingError::Ambiguous);
				}
				values.push(self.sets[n].states[state_index].computed_value.clone());
			}
		}
		if self.verbosity>= 2{ println!("gramatica: values={:?}",values); }
		if values.len()==0
		{
			Err(ParsingError::NotInGrammar)
		}
		else if values.len()==1
		{
			//Ok(values[0].clone())
			Ok(values[0].take().unwrap())
		}
		else
		{
			Err(ParsingError::Ambiguous)
		}
	}
	///Compute the value of some state, computing other states as needed.
	pub fn compute_value(&mut self, set_index:usize, state_index:usize)
	{
		//println!(">>compute_value set_index={} state_index={} state={:?}",set_index,state_index,self.sets[set_index].states[state_index]);
		let mut pending = vec![(false, set_index,state_index)];
		//let default_token = T::default();
		//let default_usize = Tables::to_usize(&default_token);
		while pending.len()>0
		{
			let (expanded, top_set, top_state) = pending.pop().unwrap();
			//println!("::compute_value pending.len={} set-id={} state-id={} state={:?} computed={:?}",pending.len(),top_set,top_state,self.sets[top_set].states[top_state],self.sets[top_set].states[top_state].computed_value);
			//if Tables::to_usize(&self.sets[top_set].states[top_state].computed_value) != default_usize
			//{
			//	//Already computed, skipping
			//	pending.pop();
			//	continue;
			//}
			let right_size = self.sets[top_set].states[top_state].right.len();
			match self.sets[top_set].states[top_state].kind
			{
				EarleyKind::Complete(reduced,prev_set_index,prev_state_index) =>
				{
					//self.compute_value_recursive(top_set,reduced);
					//self.compute_value_recursive(prev_set_index,prev_state_index);
					//let has_reduced = Tables::to_usize(&self.sets[top_set].states[reduced].computed_value) != default_usize;
					//let has_previous = Tables::to_usize(&self.sets[prev_set_index].states[prev_state_index].computed_value) != default_usize;
					//if !has_reduced || !has_previous
					//{
					//	//Some value is not yet computed pushing it.
					//	if !has_reduced
					//	{
					//		pending.push( (top_set,reduced) );
					//	}
					//	if !has_previous
					//	{
					//		pending.push( (prev_set_index,prev_state_index) );
					//	}
					//	continue;
					//}
					if !expanded
					{
						pending.push( (true,top_set,top_state) );
						pending.push( (false,top_set,reduced) );
						pending.push( (false,prev_set_index,prev_state_index) );
						continue;
					}
					//let current=&mut self.sets[top_set].states[top_state];
					let mut prop_ambiguity=None;
					self.sets[top_set].states[top_state].values=
					{
						let mut values=std::mem::take(&mut self.sets[prev_set_index].states[prev_state_index].values);
						//let mut values: Vec<T> = self.sets[prev_set_index].states[prev_state_index].values.iter_mut().map(Tables::take_token).collect();
						if values.len() < right_size
						{
							values.resize(right_size,Default::default());
						}
						//values[self.sets[top_set].states[top_state].position-1]=Tables::take_token(&mut self.sets[top_set].states[reduced].computed_value);
						values[self.sets[top_set].states[top_state].position-1]=self.sets[top_set].states[reduced].computed_value.take().unwrap();
						let prev=&self.sets[prev_set_index].states[prev_state_index];
						let red=&self.sets[top_set].states[reduced];
						//let mut values=prev.values.clone();
						//values[self.sets[top_set].states[top_state].position-1]=red.computed_value.clone();
						if prev.ambiguity_info.states.len()>1
						{
							prop_ambiguity=Some(prev.ambiguity_info.clone());
						}
						else if red.ambiguity_info.states.len()>1
						{
							prop_ambiguity=Some(red.ambiguity_info.clone());
						}
						values
					};
					if let Some(a)=prop_ambiguity
					{
						//panic!("debugging...");
						self.sets[top_set].states[top_state].ambiguity_info=a;
					}
				},
				EarleyKind::Scan(prev_set_index,prev_state_index) =>
				{
					//if Tables::to_usize(&self.sets[prev_set_index].states[prev_state_index].computed_value) == default_usize
					if !expanded
					{
						//Value is not yet computed, pushing it.
						pending.push( (true,top_set,top_state) );
						pending.push( (false,prev_set_index,prev_state_index) );
						continue;
					}
					let position = self.sets[top_set].states[top_state].position;
					//for i in 0..position-1
					//{
					//	//Simple terminal can be copied. We take more complex ones. These laters can be computed again if needed.
					//	//if Tables::table_terminal(Tables::to_usize(&self.sets[prev_set_index].states[prev_state_index].values[i]))
					//	//{
					//	//	self.sets[top_set].states[top_state].values[i]=self.sets[prev_set_index].states[prev_state_index].values[i].clone();
					//	//} else {
					//	//	self.sets[top_set].states[top_state].values[i]= std::mem::take(&mut self.sets[prev_set_index].states[prev_state_index].values[i]);
					//	//}
					//	self.sets[top_set].states[top_state].values[i]= Tables::take_token(&mut self.sets[prev_set_index].states[prev_state_index].values[i]);
					//}
					let mut values = std::mem::take(&mut self.sets[prev_set_index].states[prev_state_index].values);
					if values.len() < right_size
					{
						values.resize(right_size,Default::default());
					}
					let token = self.tokens[top_set-1].clone();
					values[position-1] = token;
					self.sets[top_set].states[top_state].values = values;
					// //Instead, to avoid misusing memory, we take off the whole array from the previous.
					// //let mut values = self.sets[prev_set_index].states[prev_state_index].values.split_off(0);
					// let mut values = std::mem::take(&mut self.sets[prev_set_index].states[prev_state_index].values);
					// let position = self.sets[top_set].states[top_state].position;
					// //update it
					// //if position < self.sets[top_set].states[top_state].values.len()
					// if position > 0
					// {
					// 	values[position-1] = std::mem::take(&mut self.sets[top_set].states[top_state].values[position-1]);
					// }
					// and insert it as the new one.
					// self.sets[top_set].states[top_state].values = values;
					
					self.sets[top_set].states[top_state].ambiguity_info=self.sets[prev_set_index].states[prev_state_index].ambiguity_info.clone();
				},
				EarleyKind::Predict(_harbinger_state_index) =>
				{
				},
			}
			let current=&mut self.sets[top_set].states[top_state];
			if current.finished()
			{
				//Compute its value
				//ParsingTables::compute_value_recursive(current);
				//println!("Calling grammar to compute {:?}",current);
				Tables::compute_value(current);
				current.values.clear();
			}
			//pending.pop();
		}
		//println!("<<compute_value set_index={} state_index={} state={:?}",set_index,state_index,self.sets[set_index].states[state_index]);
	}
	///Compute the value of some state, computing other states as needed.
	///TODO: avoid recursion, which reaches stacks overflow sometimes.
	pub fn compute_value_recursive(&mut self, set_index:usize, state_index:usize)
	{
		//println!(">>compute_value_recursive set_index={} state_index={} state={:?}",set_index,state_index,self.sets[set_index].states[state_index]);
		match self.sets[set_index].states[state_index].kind
		{
			EarleyKind::Complete(reduced,prev_set_index,prev_state_index) =>
			{
				self.compute_value_recursive(set_index,reduced);
				self.compute_value_recursive(prev_set_index,prev_state_index);
				//let current=&mut self.sets[set_index].states[state_index];
				let mut prop_ambiguity=None;
				self.sets[set_index].states[state_index].values=
				{
					let prev=&self.sets[prev_set_index].states[prev_state_index];
					let red=&self.sets[set_index].states[reduced];
					let mut current_values=prev.values.clone();
					//current_values[self.sets[set_index].states[state_index].position-1]=red.computed_value.clone();
					current_values[self.sets[set_index].states[state_index].position-1]=red.computed_value.clone().unwrap();
					if prev.ambiguity_info.states.len()>1
					{
						prop_ambiguity=Some(prev.ambiguity_info.clone());
					}
					else if red.ambiguity_info.states.len()>1
					{
						prop_ambiguity=Some(red.ambiguity_info.clone());
					}
					current_values
				};
				if let Some(a)=prop_ambiguity
				{
					self.sets[set_index].states[state_index].ambiguity_info=a;
				}
			},
			EarleyKind::Scan(prev_set_index,prev_state_index) =>
			{
				//They have the value already
				self.compute_value_recursive(prev_set_index,prev_state_index);
				for i in 0..self.sets[set_index].states[state_index].position-1
				{
					self.sets[set_index].states[state_index].values[i]=self.sets[prev_set_index].states[prev_state_index].values[i].clone();
				}
				self.sets[set_index].states[state_index].ambiguity_info=self.sets[prev_set_index].states[prev_state_index].ambiguity_info.clone();
			},
			EarleyKind::Predict(_harbinger_state_index) =>
			{
			},
		}
		let current=&mut self.sets[set_index].states[state_index];
		if current.finished()
		{
			//Compute its value
			//ParsingTables::compute_value_recursive(current);
			Tables::compute_value(current);
		}
	}
	// ///Look for states without children and deallocate as much data as possible.
	// ///Children are found initially at the given set.
	// fn clean(&mut self, last_children_set_index:usize)
	// {
	// 	let mut set_index = last_children_set_index;
	// 	let mut alive_indication = vec![1;self.sets[set_index].states.len()];
	// 	let mut clean_count = 1;
	// 	while set_index>1 && clean_count>=1
	// 	{
	// 		clean_count = 0;
	// 		let n = self.sets[set_index-1].states.len();
	// 		let mut children_count = vec![0;n];
	// 		for (state_index,state) in self.sets[set_index].states.iter().enumerate()
	// 		{
	// 			//Get parents in previous set
	// 			if alive_indication[state_index]>0
	// 			{
	// 				match state.kind
	// 				{
	// 					EarleyKind::Complete(_reduced,_prev_set_index,_prev_state_index) =>
	// 					{
	// 						//parent in current set
	// 					},
	// 					EarleyKind::Scan(_prev_set_index,prev_state_index) =>
	// 					{
	// 						children_count[prev_state_index]+=1;
	// 					},
	// 					EarleyKind::Predict(_harbinger_state_index) =>
	// 					{
	// 						//parent in current set
	// 					},
	// 				}
	// 			}
	// 		}
	// 		//for (state_index,state) in self.sets[set_index-1].states.iter_mut().enumerate().rev()
	// 		for state_index in (0..self.sets[set_index-1].states.len()).rev()
	// 		{
	// 			//Get parents in same set
	// 			if children_count[state_index]>0
	// 			{
	// 				//match state.kind
	// 				match self.sets[set_index-1].states[state_index].kind
	// 				{
	// 					EarleyKind::Complete(reduced,_prev_set_index,_prev_state_index) =>
	// 					{
	// 						children_count[reduced]+=1;
	// 						//prev_state should be fine because of the other line of succession.
	// 					},
	// 					EarleyKind::Scan(_prev_set_index,_prev_state_index) =>
	// 					{
	// 					},
	// 					EarleyKind::Predict(_harbinger_state_index) =>
	// 					{
	// 						//children_count[harbinger_state_index]+=1;
	// 						//let token = state.left;
	// 						let token = self.sets[set_index-1].states[state_index].left;
	// 						for (other_state_index,other_state) in self.sets[set_index-1].states.iter_mut().enumerate()
	// 						{
	// 							if let Some(next) = other_state.try_next()
	// 							{
	// 								if next == token
	// 								{
	// 									children_count[other_state_index]+=1;
	// 								}
	// 							}
	// 						}
	// 					},
	// 				}
	// 			}
	// 			else
	// 			{
	// 				//actual clean up
	// 				let state = &mut self.sets[set_index-1].states[state_index];
	// 				if state.values.len()>0
	// 				{
	// 					println!("Clean state {:?} at ({},{})",state,set_index-1,state_index);
	// 					state.values.clear();
	// 					clean_count += 1;
	// 				}
	// 			}
	// 		}
	// 		if clean_count>0
	// 		{
	// 			println!("set_index={} clean_count={}",set_index,clean_count);
	// 		}
	// 		alive_indication=children_count;
	// 		set_index -= 1;
	// 	}
	// }
}

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }
}