/*

 * Copyright (c) 1999, 2015, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package com.sun.tools.javac.code;

import com.sun.tools.javac.code.Kinds.Kind;

import java.util.*;

import com.sun.tools.javac.code.Symbol.TypeSymbol;

import com.sun.tools.javac.tree.JCTree.JCImport;

import com.sun.tools.javac.util.*;

import com.sun.tools.javac.util.List;

import static com.sun.tools.javac.code.Scope.LookupKind.NON_RECURSIVE;

import static com.sun.tools.javac.code.Scope.LookupKind.RECURSIVE;

import java.util.stream.Stream;

import java.util.stream.StreamSupport;

/** A scope represents an area of visibility in a Java program. The

 *  Scope class is a container for symbols which provides

 *  efficient access to symbols given their names. Scopes are implemented

 *  as hash tables with "open addressing" and "double hashing".

 *  Scopes can be nested. Nested scopes can share their hash tables.

 *

 *  <p><b>This is NOT part of any supported API.

 *  If you write code that depends on this, you do so at your own risk.

 *  This code and its internal interfaces are subject to change or

 *  deletion without notice.</b>

 */

public abstract class Scope {

    /** The scope's owner.

     */

    public final Symbol owner;

    protected Scope(Symbol owner) {

        this.owner = owner;

    }

    /**Returns all Symbols in this Scope. Symbols from outward Scopes are included.

     */

    public final Iterable<Symbol> getSymbols() {

        return getSymbols(noFilter);

    }

    /**Returns Symbols that match the given filter. Symbols from outward Scopes are included.

     */

    public final Iterable<Symbol> getSymbols(Filter<Symbol> sf) {

        return getSymbols(sf, RECURSIVE);

    }

    /**Returns all Symbols in this Scope. Symbols from outward Scopes are included

     * iff lookupKind == RECURSIVE.

     */

    public final Iterable<Symbol> getSymbols(LookupKind lookupKind) {

        return getSymbols(noFilter, lookupKind);

    }

    /**Returns Symbols that match the given filter. Symbols from outward Scopes are included

     * iff lookupKind == RECURSIVE.

     */

    public abstract Iterable<Symbol> getSymbols(Filter<Symbol> sf, LookupKind lookupKind);

    /**Returns Symbols with the given name. Symbols from outward Scopes are included.

     */

    public final Iterable<Symbol> getSymbolsByName(Name name) {

        return getSymbolsByName(name, RECURSIVE);

    }

    /**Returns Symbols with the given name that match the given filter.

     * Symbols from outward Scopes are included.

     */

    public final Iterable<Symbol> getSymbolsByName(final Name name, final Filter<Symbol> sf) {

        return getSymbolsByName(name, sf, RECURSIVE);

    }

    /**Returns Symbols with the given name. Symbols from outward Scopes are included

     * iff lookupKind == RECURSIVE.

     */

    public final Iterable<Symbol> getSymbolsByName(Name name, LookupKind lookupKind) {

        return getSymbolsByName(name, noFilter, lookupKind);

    }

    /**Returns Symbols with the given name that match the given filter.

     * Symbols from outward Scopes are included iff lookupKind == RECURSIVE.

     */

    public abstract Iterable<Symbol> getSymbolsByName(final Name name, final Filter<Symbol> sf,

            final LookupKind lookupKind);

    /** Return the first Symbol from this or outward scopes with the given name.

     * Returns null if none.

     */

    public final Symbol findFirst(Name name) {

        return findFirst(name, noFilter);

    }

    /** Return the first Symbol from this or outward scopes with the given name that matches the

     *  given filter. Returns null if none.

     */

    public Symbol findFirst(Name name, Filter<Symbol> sf) {

        Iterator<Symbol> it = getSymbolsByName(name, sf).iterator();

        return it.hasNext() ? it.next() : null;

    }

    /** Returns true iff there are is at least one Symbol in this scope matching the given filter.

     *  Does not inspect outward scopes.

     */

    public boolean anyMatch(Filter<Symbol> filter) {

        return getSymbols(filter, NON_RECURSIVE).iterator().hasNext();

    }

    /** Returns true iff the given Symbol is in this scope or any outward scope.

     */

    public boolean includes(final Symbol sym) {

        return getSymbolsByName(sym.name, new Filter<Symbol>() {

            @Override

            public boolean accepts(Symbol t) {

                return t == sym;

            }

        }).iterator().hasNext();

    }

    /** Returns true iff this scope does not contain any Symbol. Does not inspect outward scopes.

     */

    public boolean isEmpty() {

        return !getSymbols(NON_RECURSIVE).iterator().hasNext();

    }

    /** Returns the Scope from which the givins Symbol originates in this scope.

     */

    public abstract Scope getOrigin(Symbol byName);

    /** Returns true iff the given Symbol is part of this scope due to a static import.

     */

    public abstract boolean isStaticallyImported(Symbol byName);

    private static final Filter<Symbol> noFilter = null;

    /** A list of scopes to be notified if items are to be removed from this scope.

     */

    List<ScopeListener> listeners = List.nil();

    public void addScopeListener(ScopeListener sl) {

        listeners = listeners.prepend(sl);

    }

    public interface ScopeListener {

        public void symbolAdded(Symbol sym, Scope s);

        public void symbolRemoved(Symbol sym, Scope s);

    }

    public enum LookupKind {

        RECURSIVE,

        NON_RECURSIVE;

    }

    /**A scope into which Symbols can be added.*/

    public abstract static class WriteableScope extends Scope {

        public WriteableScope(Symbol owner) {

            super(owner);

        }

        /** Enter the given Symbol into this scope.

         */

        public abstract void enter(Symbol c);

        /** Enter symbol sym in this scope if not already there.

         */

        public abstract void enterIfAbsent(Symbol c);

        public abstract void remove(Symbol c);

        /** Construct a fresh scope within this scope, with same owner. The new scope may

         *  shares internal structures with the this scope. Used in connection with

         *  method leave if scope access is stack-like in order to avoid allocation

         *  of fresh tables.

         */

        public final WriteableScope dup() {

            return dup(this.owner);

        }

        /** Construct a fresh scope within this scope, with new owner. The new scope may

         *  shares internal structures with the this scope. Used in connection with

         *  method leave if scope access is stack-like in order to avoid allocation

         *  of fresh tables.

         */

        public abstract WriteableScope dup(Symbol newOwner);

        /** Must be called on dup-ed scopes to be able to work with the outward scope again.

         */

        public abstract WriteableScope leave();

        /** Construct a fresh scope within this scope, with same owner. The new scope

         *  will not share internal structures with this scope.

         */

        public final WriteableScope dupUnshared() {

            return dupUnshared(owner);

        }

        /** Construct a fresh scope within this scope, with new owner. The new scope

         *  will not share internal structures with this scope.

         */

        public abstract WriteableScope dupUnshared(Symbol newOwner);

        /** Create a new WriteableScope.

         */

        public static WriteableScope create(Symbol owner) {

            return new ScopeImpl(owner);

        }

    }

    private static class ScopeImpl extends WriteableScope {

        /** The number of scopes that share this scope's hash table.

         */

        private int shared;

        /** Next enclosing scope (with whom this scope may share a hashtable)

         */

        public ScopeImpl next;

        /** A hash table for the scope's entries.

         */

        Entry[] table;

        /** Mask for hash codes, always equal to (table.length - 1).

         */

        int hashMask;

        /** A linear list that also contains all entries in

         *  reverse order of appearance (i.e later entries are pushed on top).

         */

        public Entry elems;

        /** The number of elements in this scope.

         * This includes deleted elements, whose value is the sentinel.

         */

        int nelems = 0;

        /** Use as a "not-found" result for lookup.

         * Also used to mark deleted entries in the table.

         */

        private static final Entry sentinel = new Entry(null, null, null, null);

        /** The hash table's initial size.

         */

        private static final int INITIAL_SIZE = 0x10;

        /** Construct a new scope, within scope next, with given owner, using

         *  given table. The table's length must be an exponent of 2.

         */

        private ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table) {

            super(owner);

            this.next = next;

            Assert.check(owner != null);

            this.table = table;

            this.hashMask = table.length - 1;

        }

        /** Convenience constructor used for dup and dupUnshared. */

        private ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table, int nelems) {

            this(next, owner, table);

            this.nelems = nelems;

        }

        /** Construct a new scope, within scope next, with given owner,

         *  using a fresh table of length INITIAL_SIZE.

         */

        public ScopeImpl(Symbol owner) {

            this(null, owner, new Entry[INITIAL_SIZE]);

        }

        /** Construct a fresh scope within this scope, with new owner,

         *  which shares its table with the outer scope. Used in connection with

         *  method leave if scope access is stack-like in order to avoid allocation

         *  of fresh tables.

         */

        public WriteableScope dup(Symbol newOwner) {

            ScopeImpl result = new ScopeImpl(this, newOwner, this.table, this.nelems);

            shared++;

            // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode());

            // new Error().printStackTrace(System.out);

            return result;

        }

        /** Construct a fresh scope within this scope, with new owner,

         *  with a new hash table, whose contents initially are those of

         *  the table of its outer scope.

         */

        public WriteableScope dupUnshared(Symbol newOwner) {

            if (shared > 0) {

                //The nested Scopes might have already added something to the table, so all items

                //that don't originate in this Scope or any of its outer Scopes need to be cleared:

                Set<Scope> acceptScopes = Collections.newSetFromMap(new IdentityHashMap<>());

                ScopeImpl c = this;

                while (c != null) {

                    acceptScopes.add(c);

                    c = c.next;

                }

                int n = 0;

                Entry[] oldTable = this.table;

                Entry[] newTable = new Entry[this.table.length];

                for (int i = 0; i < oldTable.length; i++) {

                    Entry e = oldTable[i];

                    while (e != null && e != sentinel && !acceptScopes.contains(e.scope)) {

                        e = e.shadowed;

                    }

                    if (e != null) {

                        n++;

                        newTable[i] = e;

                    }

                }

                return new ScopeImpl(this, newOwner, newTable, n);

            } else {

                return new ScopeImpl(this, newOwner, this.table.clone(), this.nelems);

            }

        }

        /** Remove all entries of this scope from its table, if shared

         *  with next.

         */

        public WriteableScope leave() {

            Assert.check(shared == 0);

            if (table != next.table) return next;

            while (elems != null) {

                int hash = getIndex(elems.sym.name);

                Entry e = table[hash];

                Assert.check(e == elems, elems.sym);

                table[hash] = elems.shadowed;

                elems = elems.sibling;

            }

            Assert.check(next.shared > 0);

            next.shared--;

            next.nelems = nelems;

            // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode());

            // new Error().printStackTrace(System.out);

            return next;

        }

        /** Double size of hash table.

         */

        private void dble() {

            Assert.check(shared == 0);

            Entry[] oldtable = table;

            Entry[] newtable = new Entry[oldtable.length * 2];

            for (ScopeImpl s = this; s != null; s = s.next) {

                if (s.table == oldtable) {

                    Assert.check(s == this || s.shared != 0);

                    s.table = newtable;

                    s.hashMask = newtable.length - 1;

                }

            }

            int n = 0;

            for (int i = oldtable.length; --i >= 0; ) {

                Entry e = oldtable[i];

                if (e != null && e != sentinel) {

                    table[getIndex(e.sym.name)] = e;

                    n++;

                }

            }

            // We don't need to update nelems for shared inherited scopes,

            // since that gets handled by leave().

            nelems = n;

        }

        /** Enter symbol sym in this scope.

         */

        public void enter(Symbol sym) {

            Assert.check(shared == 0);

            if (nelems * 3 >= hashMask * 2)

                dble();

            int hash = getIndex(sym.name);

            Entry old = table[hash];

            if (old == null) {

                old = sentinel;

                nelems++;

            }

            Entry e = new Entry(sym, old, elems, this);

            table[hash] = e;

            elems = e;

            //notify listeners

            for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {

                l.head.symbolAdded(sym, this);

            }

        }

        /** Remove symbol from this scope.

         */

        public void remove(Symbol sym) {

            Assert.check(shared == 0);

            Entry e = lookup(sym.name, candidate -> candidate == sym);

            if (e.scope == null) return;

            // remove e from table and shadowed list;

            int i = getIndex(sym.name);

            Entry te = table[i];

            if (te == e)

                table[i] = e.shadowed;

            else while (true) {

                if (te.shadowed == e) {

                    te.shadowed = e.shadowed;

                    break;

                }

                te = te.shadowed;

            }

            // remove e from elems and sibling list

            te = elems;

            if (te == e)

                elems = e.sibling;

            else while (true) {

                if (te.sibling == e) {

                    te.sibling = e.sibling;

                    break;

                }

                te = te.sibling;

            }

            //notify listeners

            for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {

                l.head.symbolRemoved(sym, this);

            }

        }

        /** Enter symbol sym in this scope if not already there.

         */

        public void enterIfAbsent(Symbol sym) {

            Assert.check(shared == 0);

            Entry e = lookup(sym.name);

            while (e.scope == this && e.sym.kind != sym.kind) e = e.next();

            if (e.scope != this) enter(sym);

        }

        /** Given a class, is there already a class with same fully

         *  qualified name in this (import) scope?

         */

        public boolean includes(Symbol c) {

            for (Scope.Entry e = lookup(c.name);

                 e.scope == this;

                 e = e.next()) {

                if (e.sym == c) return true;

            }

            return false;

        }

        /** Return the entry associated with given name, starting in

         *  this scope and proceeding outwards. If no entry was found,

         *  return the sentinel, which is characterized by having a null in

         *  both its scope and sym fields, whereas both fields are non-null

         *  for regular entries.

         */

        protected Entry lookup(Name name) {

            return lookup(name, noFilter);

        }

        protected Entry lookup(Name name, Filter<Symbol> sf) {

            Entry e = table[getIndex(name)];

            if (e == null || e == sentinel)

                return sentinel;

            while (e.scope != null && (e.sym.name != name || (sf != null && !sf.accepts(e.sym))))

                e = e.shadowed;

            return e;

        }

        public Symbol findFirst(Name name, Filter<Symbol> sf) {

            return lookup(name, sf).sym;

        }

        /*void dump (java.io.PrintStream out) {

            out.println(this);