private static IASTNode MakeIdent(IASTNode source, string text)
 {
     var ident = source.DupNode();
     ident.Type = HqlSqlWalker.IDENT;
     ident.Text = text;
     return ident;
 }

		/// <summary>
		/// Insert a new node into both the Tree and the Node Array. Add DOWN and UP nodes if needed.
		/// </summary>
		/// <param name="parent">The parent node</param>
		/// <param name="child">The child node</param>
		public void InsertChild(IASTNode parent, IASTNode child)
		{
			if (child.ChildCount > 0)
			{
				throw new InvalidOperationException("Currently do not support adding nodes with children");
			}

			int parentIndex = nodes.IndexOf(parent);
			int numberOfChildNodes = NumberOfChildNodes(parentIndex);
			int insertPoint;
			
			if (numberOfChildNodes == 0)
			{
				insertPoint = parentIndex + 1;  // We want to insert immediately after the parent
				nodes.Insert(insertPoint, down);
				insertPoint++;  // We've just added a new node
			}
			else
			{
				insertPoint = parentIndex + numberOfChildNodes;
			}

			parent.AddChild(child);
			nodes.Insert(insertPoint, child);
			insertPoint++;

			if (numberOfChildNodes == 0)
			{
				nodes.Insert(insertPoint, up);
			}
		}

		private static void AddImpliedFromToFromNode(IASTNode fromClause, string collectionRole, ISessionFactoryImplementor factory)
		{
			SessionFactoryHelperExtensions _sessionFactoryHelper = new SessionFactoryHelperExtensions(factory);
			IQueryableCollection persister = _sessionFactoryHelper.GetCollectionPersister(collectionRole);
			IType collectionElementType = persister.ElementType;
			if (!collectionElementType.IsEntityType)
			{
				throw new QueryException("collection of values in filter: this");
			}

			string collectionElementEntityName = persister.ElementPersister.EntityName;

			ITreeAdaptor adaptor = new ASTTreeAdaptor();

			IASTNode fromElement = (IASTNode)adaptor.Create(HqlParser.FILTER_ENTITY, collectionElementEntityName);
			IASTNode alias = (IASTNode)adaptor.Create(HqlParser.ALIAS, "this");

			fromClause.AddChild(fromElement);
			fromClause.AddChild(alias);

			// Show the modified AST.
			if (log.IsDebugEnabled)
			{
				log.Debug("AddImpliedFormToFromNode() : Filter - Added 'this' as a from element...");
			}
		}

		public void Visit(IASTNode node)
		{
			if (predicate == null || predicate(node))
			{
				collectedNodes.Add(node);
			}
		}

 public void Visit(IASTNode node)
 {
     if (node.Type == HqlSqlWalker.FROM)
     {
         _nodes.AddRange(node.Where(child => child.Type == HqlSqlWalker.RANGE).Select(range => range.GetChild(0)));
     }
 }

		protected SqlString GenerateIdInsertSelect(IQueryable persister, string tableAlias, IASTNode whereClause)
		{
			var select = new SqlSelectBuilder(Factory);
			SelectFragment selectFragment = new SelectFragment(Factory.Dialect)
				.AddColumns(tableAlias, persister.IdentifierColumnNames, persister.IdentifierColumnNames);
			select.SetSelectClause(selectFragment.ToFragmentString().Substring(2));

			string rootTableName = persister.TableName;
			SqlString fromJoinFragment = persister.FromJoinFragment(tableAlias, true, false);
			SqlString whereJoinFragment = persister.WhereJoinFragment(tableAlias, true, false);

			select.SetFromClause(rootTableName + ' ' + tableAlias + fromJoinFragment);

			if (whereJoinFragment == null)
			{
				whereJoinFragment = SqlString.Empty;
			}
			else
			{
				whereJoinFragment = whereJoinFragment.Trim();
				if (whereJoinFragment.StartsWithCaseInsensitive("and "))
				{
					whereJoinFragment = whereJoinFragment.Substring(4);
				}
			}

			SqlString userWhereClause = SqlString.Empty;
			if (whereClause.ChildCount != 0)
			{
				// If a where clause was specified in the update/delete query, use it to limit the
				// returned ids here...
				try
				{
					var nodes = new CommonTreeNodeStream(whereClause);
					var gen = new SqlGenerator(Factory, nodes);
					gen.whereClause();
					userWhereClause = gen.GetSQL().Substring(7);
				}
				catch (RecognitionException e)
				{
					throw new HibernateException("Unable to generate id select for DML operation", e);
				}
				if (whereJoinFragment.Length > 0)
				{
					whereJoinFragment.Append(" and ");
				}
			}

			select.SetWhereClause(whereJoinFragment + userWhereClause);

			var insert = new InsertSelect();
			if (Factory.Settings.IsCommentsEnabled)
			{
				insert.SetComment("insert-select for " + persister.EntityName + " ids");
			}
			insert.SetTableName(persister.TemporaryIdTableName);
			insert.SetSelect(select);
			return insert.ToSqlString();
		}

		/// <summary>
		/// Returns the 'list' representation with some brackets around it for debugging.
		/// </summary>
		/// <param name="n">The tree.</param>
		/// <returns>The list representation of the tree.</returns>
		public static string GetDebugstring(IASTNode n)
		{
			StringBuilder buf = new StringBuilder();
			buf.Append("[ ");
			buf.Append((n == null) ? "{null}" : n.ToStringTree());
			buf.Append(" ]");
			return buf.ToString();
		}

		public virtual void ReplaceBy(IASTNode node)
		{
			if (Parent != null)
			{
				throw new ApplicationException("Couldn't find a parent node to delegate");
			}

			Parent.ReplaceChild(this, node);
		}

				private void AddImplementorsToMap(IASTNode querySource, string className, string[] implementors)
				{
					if (implementors.Length == 1 && implementors[0] == className)
					{
						// No need to change things
						return;
					}

					_map.Add(querySource,
					         implementors.Select(implementor => MakeIdent(querySource, implementor)).ToArray());
				}

				public Dictionary<IASTNode, IASTNode[]> Process(IASTNode tree)
				{
					foreach (var querySource in new QuerySourceDetector(tree).LocateQuerySources())
					{
						var className = GetClassName(querySource);
						string[] implementors = _sfi.GetImplementors(className);
						AddImplementorsToMap(querySource, className, implementors);
					}

					return _map;
				}

		/// <summary>
		/// Traverse the AST tree depth first. Note that the AST passed in is not visited itself.  Visitation starts
		/// with its children.
		/// </summary>
		/// <param name="ast">ast</param>
		public void TraverseDepthFirst(IASTNode ast)
		{
			if (ast == null)
			{
				throw new ArgumentNullException("ast");
			}

			for (int i = 0; i < ast.ChildCount; i++)
			{
				VisitDepthFirst(ast.GetChild(i));
			}
		}

        public Dictionary<IASTNode, IASTNode[]> Process(IASTNode tree)
        {
            foreach (var querySource in new QuerySourceDetector(tree).LocateQuerySources())
            {
                var className = GetClassName(querySource);
                var classType = _sessionFactoryHelper.GetImportedClass(className);

                AddImplementorsToMap(querySource, classType == null ? className : classType.FullName);
            }

            return _map;
        }

    	private static string GetClassName(IASTNode querySource)
        {
            switch (querySource.Type)
            {
                case HqlSqlWalker.IDENT:
                    return querySource.Text;
                case HqlSqlWalker.DOT:
                    return BuildPath(querySource);
            }

            // TODO
            throw new NotSupportedException();
        }

		/// <summary>
		/// Creates a new AST-based query translator.
		/// </summary>
		/// <param name="queryIdentifier">The query-identifier (used in stats collection)</param>
        /// <param name="parsedQuery">The hql query to translate</param>
		/// <param name="enabledFilters">Currently enabled filters</param>
		/// <param name="factory">The session factory constructing this translator instance.</param>
		public QueryTranslatorImpl(
				string queryIdentifier,
				IASTNode parsedQuery,
				IDictionary<string, IFilter> enabledFilters,
				ISessionFactoryImplementor factory)
		{
			_queryIdentifier = queryIdentifier;
            _stageOneAst = parsedQuery;
			_compiled = false;
			_shallowQuery = false;
			_enabledFilters = enabledFilters;
			_factory = factory;
		}

        private IEnumerable<IASTNode> DuplicateTree()
        {
            var replacements = CrossJoinDictionaryArrays.PerformCrossJoin(_nodeMapping);

            var dups = new IASTNode[replacements.Count()];

            for (var i = 0; i < replacements.Count(); i++)
            {
                dups[i] = DuplicateTree(_ast, replacements[i]);
            }

            return dups;
        }

		/// <summary>
		/// Handles HQL AST transformation for collection filters (which are created with <see cref="ISession.CreateFilter"/>).
		/// 
		/// Adds FROM elements to implicit FROM clause.
		/// E.g., 
		/// <code>
		/// ( query ( SELECT_FROM {filter-implied FROM} ) ( where ( = X 10 ) ) )
		/// </code>
		/// gets converted to 
		/// <code>
		/// ( query ( SELECT_FROM ( FROM NHibernate.DomainModel.Many this ) ) ( where ( = X 10 ) ) )
		/// </code>
		/// </summary>
		/// <param name="ast">The root node of HQL query</param>
		/// <param name="collectionRole">Collection that is being filtered</param>
		/// <param name="factory">Session factory</param>
		internal static void AddImpliedFromToQuery(IASTNode ast, string collectionRole, ISessionFactoryImplementor factory)
		{
			if (ast.Type != HqlParser.QUERY)
			{
				var msg = string.Format(CultureInfo.InvariantCulture,
					"invalid query type for collection filtering: expected {0}, got {1}", HqlParser.tokenNames[HqlParser.QUERY], HqlParser.tokenNames[ast.Type]);
				throw new QueryException(msg);
			}
			var selectFromClause = ast.Where(x => x.Type == HqlParser.SELECT_FROM).Single();
			var fromClause = selectFromClause.Where(x => x.Type == HqlParser.FROM).Single();
			
			fromClause.Text = "FROM"; // Just for prettier debug output
			AddImpliedFromToFromNode(fromClause, collectionRole, factory);
		}

		private void VisitDepthFirst(IASTNode ast)
		{
			if (ast == null)
			{
				return;
			}

			_visitor.Visit(ast);

			for (int i = 0; i < ast.ChildCount; i++)
			{
				VisitDepthFirst(ast.GetChild(i));
			}
		}

        private static void BuildPath(IASTNode node, StringBuilder sb)
        {
            if (node.Type == HqlSqlWalker.DOT)
            {
                BuildPath(node.GetChild(0), sb);

                sb.Append('.');
                sb.Append(node.GetChild(1).Text);
            }
            else
            {
                sb.Append(node.Text);
            }
        }

		public void RecursiveResolve(int level, bool impliedAtRoot, string classAlias, IASTNode parent)
		{
			IASTNode lhs = GetFirstChild();
			int nextLevel = level + 1;
			if ( lhs != null ) 
			{
				FromReferenceNode n = ( FromReferenceNode ) lhs;
				n.RecursiveResolve( nextLevel, impliedAtRoot, null, this );
			}

			ResolveFirstChild();
			bool impliedJoin = !(level == RootLevel && !impliedAtRoot);

			Resolve( true, impliedJoin, classAlias, parent );
		}

		private static void Check(IASTNode check, IASTNode first, IASTNode second)
		{
			if (typeof(IExpectedTypeAwareNode).IsAssignableFrom(check.GetType()))
			{
				IType expectedType = null;
				if (typeof(SqlNode).IsAssignableFrom(first.GetType()))
				{
					expectedType = ((SqlNode)first).DataType;
				}
				if (expectedType == null && typeof(SqlNode).IsAssignableFrom(second.GetType()))
				{
					expectedType = ((SqlNode)second).DataType;
				}
				((IExpectedTypeAwareNode)check).ExpectedType = expectedType;
			}
		}