// getTableLease acquires a lease for the specified table. The lease will be
// released when the planner closes.
func (p *planner) getTableLease(qname *parser.QualifiedName) (*TableDescriptor, *roachpb.Error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return nil, roachpb.NewError(err)
	}

	if qname.Database() == systemDB.Name || testDisableTableLeases {
		// We don't go through the normal lease mechanism for system tables. The
		// system.lease and system.descriptor table, in particular, are problematic
		// because they are used for acquiring leases itself, creating a
		// chicken&egg problem.
		return p.getTableDesc(qname)
	}

	tableID, pErr := p.getTableID(qname)
	if pErr != nil {
		return nil, pErr
	}

	if p.leases == nil {
		p.leases = make(map[ID]*LeaseState)
	}

	lease, ok := p.leases[tableID]
	if !ok {
		var pErr *roachpb.Error
		lease, pErr = p.leaseMgr.Acquire(p.txn, tableID, 0)
		if pErr != nil {
			return nil, pErr
		}
		p.leases[tableID] = lease
	}

	return proto.Clone(&lease.TableDescriptor).(*TableDescriptor), nil
}

func (s *Server) getTableDesc(database string, qname parser.QualifiedName) (
	*structured.TableDescriptor, error) {
	var err error
	qname, err = s.normalizeTableName(database, qname)
	if err != nil {
		return nil, err
	}
	dbID, err := s.lookupDatabase(qname.Database())
	if err != nil {
		return nil, err
	}
	gr, err := s.db.Get(keys.MakeNameMetadataKey(dbID, qname.Table()))
	if err != nil {
		return nil, err
	}
	if !gr.Exists() {
		return nil, fmt.Errorf("table \"%s\" does not exist", qname)
	}
	descKey := gr.ValueBytes()
	desc := structured.TableDescriptor{}
	if err := s.db.GetProto(descKey, &desc); err != nil {
		return nil, err
	}
	if err := desc.Validate(); err != nil {
		return nil, err
	}
	return &desc, nil
}

// expandTableGlob expands wildcards from the end of `expr` and
// returns the list of matching tables.
// `expr` is possibly modified to be qualified with the database it refers to.
// `expr` is assumed to be of one of several forms:
// 		database.table
// 		table
// 		*
func (p *planner) expandTableGlob(expr *parser.QualifiedName) (
	parser.QualifiedNames, *roachpb.Error) {
	if len(expr.Indirect) == 0 {
		return parser.QualifiedNames{expr}, nil
	}

	if err := expr.QualifyWithDatabase(p.session.Database); err != nil {
		return nil, roachpb.NewError(err)
	}
	// We must have a single indirect: either .table or .*
	if len(expr.Indirect) != 1 {
		return nil, roachpb.NewErrorf("invalid table glob: %s", expr)
	}

	switch expr.Indirect[0].(type) {
	case parser.NameIndirection:
		return parser.QualifiedNames{expr}, nil
	case parser.StarIndirection:
		dbDesc, pErr := p.getDatabaseDesc(string(expr.Base))
		if pErr != nil {
			return nil, pErr
		}
		tableNames, pErr := p.getTableNames(dbDesc)
		if pErr != nil {
			return nil, pErr
		}
		return tableNames, nil
	default:
		return nil, roachpb.NewErrorf("invalid table glob: %s", expr)
	}
}

// mustGetTableDesc implements the SchemaAccessor interface.
func (p *planner) mustGetTableDesc(qname *parser.QualifiedName) (*sqlbase.TableDescriptor, error) {
	desc, err := p.getTableDesc(qname)
	if err != nil {
		return nil, err
	}
	if desc == nil {
		return nil, sqlbase.NewUndefinedTableError(qname.String())
	}
	return desc, nil
}

// Initializes a scanNode with a tableName. Returns the table or index name that can be used for
// fully-qualified columns if an alias is not specified.
func (n *scanNode) initTable(p *planner, tableName *parser.QualifiedName) (string, *roachpb.Error) {
	if n.desc, n.pErr = p.getTableLease(tableName); n.pErr != nil {
		return "", n.pErr
	}

	if err := p.checkPrivilege(&n.desc, privilege.SELECT); err != nil {
		return "", roachpb.NewError(err)
	}

	alias := n.desc.Name

	indexName := tableName.Index()
	if indexName != "" && !equalName(n.desc.PrimaryIndex.Name, indexName) {
		for i := range n.desc.Indexes {
			if equalName(n.desc.Indexes[i].Name, indexName) {
				// Remove all but the matching index from the descriptor.
				n.desc.Indexes = n.desc.Indexes[i : i+1]
				n.index = &n.desc.Indexes[0]
				break
			}
		}
		if n.index == nil {
			n.pErr = roachpb.NewUErrorf("index \"%s\" not found", indexName)
			return "", n.pErr
		}
		// Use the index name instead of the table name for fully-qualified columns in the
		// expression.
		alias = n.index.Name
		// Strip out any columns from the table that are not present in the
		// index.
		visibleCols := make([]ColumnDescriptor, 0, len(n.index.ColumnIDs)+len(n.index.ImplicitColumnIDs))
		for _, colID := range n.index.ColumnIDs {
			col, err := n.desc.FindColumnByID(colID)
			n.pErr = roachpb.NewError(err)
			if n.pErr != nil {
				return "", n.pErr
			}
			visibleCols = append(visibleCols, *col)
		}
		for _, colID := range n.index.ImplicitColumnIDs {
			col, err := n.desc.FindColumnByID(colID)
			n.pErr = roachpb.NewError(err)
			if n.pErr != nil {
				return "", n.pErr
			}
			visibleCols = append(visibleCols, *col)
		}
		n.isSecondaryIndex = true
		n.initVisibleCols(visibleCols, len(n.index.ImplicitColumnIDs))
	} else {
		n.initDescDefaults()
	}

	return alias, nil
}

// Initializes a scanNode with a tableName. Returns the table or index name that can be used for
// fully-qualified columns if an alias is not specified.
func (n *scanNode) initTable(
	p *planner,
	tableName *parser.QualifiedName,
	indexHints *parser.IndexHints,
	scanVisibility scanVisibility,
) (string, error) {
	var err error

	// AS OF SYSTEM TIME queries need to fetch the table descriptor at the
	// specified time, and never lease anything. The proto transaction already
	// has its timestamps set correctly so getTableDesc will fetch with the
	// correct timestamp.
	if p.asOf {
		desc, err := p.getTableDesc(tableName)
		if err != nil {
			return "", err
		}
		if desc == nil {
			return "", sqlbase.NewUndefinedTableError(tableName.String())
		}
		n.desc = *desc
	} else {
		n.desc, err = p.getTableLease(tableName)
	}
	if err != nil {
		return "", err
	}

	if err := p.checkPrivilege(&n.desc, privilege.SELECT); err != nil {
		return "", err
	}

	alias := n.desc.Name

	if indexHints != nil && indexHints.Index != "" {
		indexName := sqlbase.NormalizeName(string(indexHints.Index))
		if indexName == sqlbase.NormalizeName(n.desc.PrimaryIndex.Name) {
			n.specifiedIndex = &n.desc.PrimaryIndex
		} else {
			for i := range n.desc.Indexes {
				if indexName == sqlbase.NormalizeName(n.desc.Indexes[i].Name) {
					n.specifiedIndex = &n.desc.Indexes[i]
					break
				}
			}
			if n.specifiedIndex == nil {
				return "", fmt.Errorf("index \"%s\" not found", indexName)
			}
		}
	}
	n.noIndexJoin = (indexHints != nil && indexHints.NoIndexJoin)
	n.initDescDefaults(scanVisibility)
	return alias, nil
}

func (p *planner) normalizeTableName(qname *parser.QualifiedName) error {
	if qname == nil || qname.Base == "" {
		return fmt.Errorf("empty table name: %s", qname)
	}
	if len(qname.Indirect) == 0 {
		if p.session.Database == "" {
			return fmt.Errorf("no database specified")
		}
		qname.Indirect = append(qname.Indirect, parser.NameIndirection(qname.Base))
		qname.Base = parser.Name(p.session.Database)
	}
	return nil
}

// getTableID retrieves the table ID for the specified table. It uses the
// descriptor cache to perform lookups, falling back to the KV store when
// necessary.
func (p *planner) getTableID(qname *parser.QualifiedName) (ID, *roachpb.Error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return 0, roachpb.NewError(err)
	}

	// Lookup the database in the cache first, falling back to the KV store if it
	// isn't present. The cache might cause the usage of a recently renamed
	// database, but that's a race that could occur anyways.
	dbDesc, pErr := p.getCachedDatabaseDesc(qname.Database())
	if pErr != nil {
		dbDesc, pErr = p.getDatabaseDesc(qname.Database())
		if pErr != nil {
			return 0, pErr
		}
	}

	// Lookup the ID of the table in the cache. The use of the cache might cause
	// the usage of a recently renamed table, but that's a race that could occur
	// anyways.
	nameKey := tableKey{dbDesc.ID, qname.Table()}
	key := nameKey.Key()
	if nameVal := p.systemConfig.GetValue(key); nameVal != nil {
		id, err := nameVal.GetInt()
		return ID(id), roachpb.NewError(err)
	}

	gr, pErr := p.txn.Get(key)
	if pErr != nil {
		return 0, pErr
	}
	if !gr.Exists() {
		return 0, roachpb.NewErrorf("table %q does not exist", nameKey.Name())
	}
	return ID(gr.ValueInt()), nil
}

// getTableID retrieves the table ID for the specified table. It uses the
// descriptor cache to perform lookups, falling back to the KV store when
// necessary.
func (p *planner) getTableID(qname *parser.QualifiedName) (sqlbase.ID, error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return 0, err
	}

	dbID, err := p.getDatabaseID(qname.Database())
	if err != nil {
		return 0, err
	}

	// Lookup the ID of the table in the cache. The use of the cache might cause
	// the usage of a recently renamed table, but that's a race that could occur
	// anyways.
	// TODO(andrei): remove the used of p.systemConfig as a cache for table names,
	// replace it with using the leases for resolving names, and do away with any
	// races due to renames. We'll probably have to rewrite renames to perform
	// an async schema change.
	nameKey := tableKey{dbID, qname.Table()}
	key := nameKey.Key()
	if nameVal := p.systemConfig.GetValue(key); nameVal != nil {
		id, err := nameVal.GetInt()
		return sqlbase.ID(id), err
	}

	gr, err := p.txn.Get(key)
	if err != nil {
		return 0, err
	}
	if !gr.Exists() {
		return 0, tableDoesNotExistError(qname.String())
	}
	return sqlbase.ID(gr.ValueInt()), nil
}

func (p *planner) getTableDesc(qname *parser.QualifiedName) (
	*structured.TableDescriptor, error) {
	if err := p.normalizeTableName(qname); err != nil {
		return nil, err
	}
	dbDesc, err := p.getDatabaseDesc(qname.Database())
	if err != nil {
		return nil, err
	}

	desc := structured.TableDescriptor{}
	if err := p.getDescriptor(tableKey{dbDesc.ID, qname.Table()}, &desc); err != nil {
		return nil, err
	}
	return &desc, nil
}

// findColumn looks up the column described by a QualifiedName. The qname will be normalized.
func (qt qvalResolver) findColumn(qname *parser.QualifiedName) (columnRef, error) {

	ref := columnRef{colIdx: invalidColIdx}

	if err := qname.NormalizeColumnName(); err != nil {
		return ref, err
	}

	// We can't resolve stars to a single column.
	if qname.IsStar() {
		err := fmt.Errorf("qualified name \"%s\" not found", qname)
		return ref, err
	}

	// TODO(radu): when we support multiple FROMs, we will find the node with the correct alias; if
	// no alias is given, we will search for the column in all FROMs and make sure there is only
	// one.  For now we just check that the name matches (if given).
	if qname.Base == "" {
		qname.Base = parser.Name(qt.table.alias)
	}
	if equalName(qt.table.alias, string(qname.Base)) {
		colName := qname.Column()
		for idx, col := range qt.table.columns {
			if equalName(col.Name, colName) {
				ref.table = qt.table
				ref.colIdx = idx
				return ref, nil
			}
		}
	}

	err := fmt.Errorf("qualified name \"%s\" not found", qname)
	return ref, err
}

// findColumn looks up the column described by a QualifiedName. The qname will be normalized.
func (qt qvalResolver) findColumn(qname *parser.QualifiedName) (columnRef, error) {

	ref := columnRef{colIdx: invalidColIdx}

	if err := qname.NormalizeColumnName(); err != nil {
		return ref, err
	}

	// We can't resolve stars to a single column.
	if qname.IsStar() {
		err := fmt.Errorf("qualified name \"%s\" not found", qname)
		return ref, err
	}

	colName := sqlbase.NormalizeName(qname.Column())
	for _, table := range qt.tables {
		if qname.Base == "" || sqlbase.EqualName(table.alias, string(qname.Base)) {
			for idx, col := range table.columns {
				if sqlbase.NormalizeName(col.Name) == colName {
					if ref.colIdx != invalidColIdx {
						return ref, fmt.Errorf("column reference \"%s\" is ambiguous", qname)
					}
					ref.table = table
					ref.colIdx = idx
				}
			}
		}
	}

	if ref.colIdx == invalidColIdx {
		return ref, fmt.Errorf("qualified name \"%s\" not found", qname)
	}
	return ref, nil
}

// getTableLease acquires a lease for the specified table. The lease will be
// released when the planner closes. Note that a shallow copy of the table
// descriptor is returned. It is safe to mutate fields of the returned
// descriptor, but the values those fields point to should not be modified.
func (p *planner) getTableLease(qname *parser.QualifiedName) (sqlbase.TableDescriptor, error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return sqlbase.TableDescriptor{}, err
	}

	if qname.Database() == sqlbase.SystemDB.Name || testDisableTableLeases {
		// We don't go through the normal lease mechanism for system tables. The
		// system.lease and system.descriptor table, in particular, are problematic
		// because they are used for acquiring leases itself, creating a
		// chicken&egg problem.
		desc, err := p.getTableDesc(qname)
		if err != nil {
			return sqlbase.TableDescriptor{}, err
		}
		if desc == nil {
			return sqlbase.TableDescriptor{}, tableDoesNotExistError(qname.String())
		}
		return *desc, nil
	}

	tableID, err := p.getTableID(qname)
	if err != nil {
		return sqlbase.TableDescriptor{}, err
	}

	var lease *LeaseState
	var commitBy time.Time
	for _, l := range p.leases {
		commitBy = updateCommitBy(commitBy, l)
		if l.TableDescriptor.ID == tableID {
			lease = l
		}
	}
	if lease == nil {
		var err error
		lease, err = p.leaseMgr.Acquire(p.txn, tableID, 0)
		if err != nil {
			if _, ok := err.(*roachpb.DescriptorNotFoundError); ok {
				// Transform the descriptor error into an error that references the
				// table's name.
				return sqlbase.TableDescriptor{}, tableDoesNotExistError(qname.String())
			}
			return sqlbase.TableDescriptor{}, err
		}
		p.leases = append(p.leases, lease)
		commitBy = updateCommitBy(commitBy, lease)
	}
	p.txn.SetDeadline(roachpb.Timestamp{WallTime: commitBy.UnixNano()})
	return lease.TableDescriptor, nil
}

func (v *qnameVisitor) getDesc(qname *parser.QualifiedName) *TableDescriptor {
	if v.desc == nil {
		return nil
	}
	if qname.Base == "" {
		qname.Base = parser.Name(v.desc.Alias)
		return v.desc
	}
	if equalName(v.desc.Alias, string(qname.Base)) {
		return v.desc
	}
	return nil
}

// getTableLease acquires a lease for the specified table. The lease will be
// released when the planner closes. Note that a shallow copy of the table
// descriptor is returned. It is safe to mutate fields of the returned
// descriptor, but the values those fields point to should not be modified.
//
// TODO(pmattis): Return a TableDesriptor value instead of a pointer.
func (p *planner) getTableLease(qname *parser.QualifiedName) (*TableDescriptor, *roachpb.Error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return nil, roachpb.NewError(err)
	}

	if qname.Database() == systemDB.Name || testDisableTableLeases {
		// We don't go through the normal lease mechanism for system tables. The
		// system.lease and system.descriptor table, in particular, are problematic
		// because they are used for acquiring leases itself, creating a
		// chicken&egg problem.
		return p.getTableDesc(qname)
	}

	tableID, pErr := p.getTableID(qname)
	if pErr != nil {
		return nil, pErr
	}

	var lease *LeaseState
	found := false
	for _, lease = range p.leases {
		if lease.TableDescriptor.ID == tableID {
			found = true
			break
		}
	}
	if !found {
		var pErr *roachpb.Error
		lease, pErr = p.leaseMgr.Acquire(p.txn, tableID, 0)
		if pErr != nil {
			return nil, pErr
		}
		p.leases = append(p.leases, lease)
	}

	desc := &TableDescriptor{}
	*desc = lease.TableDescriptor
	return desc, nil
}

// getTableID retrieves the table ID for the specified table.
func getTableID(p *planner, qname *parser.QualifiedName) (sqlbase.ID, error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return 0, err
	}

	dbID, err := p.getDatabaseID(qname.Database())
	if err != nil {
		return 0, err
	}

	nameKey := tableKey{dbID, qname.Table()}
	key := nameKey.Key()
	gr, err := p.txn.Get(key)
	if err != nil {
		return 0, err
	}
	if !gr.Exists() {
		return 0, sqlbase.NewUndefinedTableError(qname.String())
	}
	return sqlbase.ID(gr.ValueInt()), nil
}

// getTableDesc implements the SchemaAccessor interface.
func (p *planner) getTableDesc(qname *parser.QualifiedName) (*sqlbase.TableDescriptor, error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return nil, err
	}
	dbDesc, err := p.getDatabaseDesc(qname.Database())
	if err != nil {
		return nil, err
	}
	if dbDesc == nil {
		return nil, sqlbase.NewUndefinedDatabaseError(qname.Database())
	}

	desc := sqlbase.TableDescriptor{}
	found, err := p.getDescriptor(tableKey{parentID: dbDesc.ID, name: qname.Table()}, &desc)
	if err != nil {
		return nil, err
	}
	if !found {
		return nil, nil
	}
	return &desc, nil
}

func (p *planner) getTableDesc(qname *parser.QualifiedName) (*TableDescriptor, *roachpb.Error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return nil, roachpb.NewError(err)
	}
	dbDesc, pErr := p.getDatabaseDesc(qname.Database())
	if pErr != nil {
		return nil, pErr
	}

	desc := TableDescriptor{}
	if pErr := p.getDescriptor(tableKey{dbDesc.ID, qname.Table()}, &desc); pErr != nil {
		return nil, pErr
	}
	return &desc, nil
}

// getCachedTableDesc looks for a table descriptor in the descriptor cache.
// Looks up the database descriptor, followed by the table descriptor.
//
// Returns: the table descriptor, whether it comes from the cache, and an error.
func (p *planner) getCachedTableDesc(qname *parser.QualifiedName) (*TableDescriptor, bool, error) {
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return nil, false, err
	}
	dbDesc, cached, err := p.getCachedDatabaseDesc(qname.Database())
	if err != nil {
		return nil, false, err
	}

	desc := &TableDescriptor{}
	// Only attempt cached lookup if the database descriptor was found in the cache.
	if cached {
		if err := p.getCachedDescriptor(tableKey{dbDesc.ID, qname.Table()}, desc); err == nil {
			return desc, true, nil
		}
		// Problem, or not found in the cache: fall back on KV lookup.
	}

	if err := p.getDescriptor(tableKey{dbDesc.ID, qname.Table()}, desc); err != nil {
		return nil, false, err
	}
	return desc, false, nil
}

// getTableLease implements the SchemaAccessor interface.
func (p *planner) getTableLease(qname *parser.QualifiedName) (sqlbase.TableDescriptor, error) {
	if log.V(2) {
		log.Infof("planner acquiring lease on table %q", qname)
	}
	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return sqlbase.TableDescriptor{}, err
	}

	if qname.Database() == sqlbase.SystemDB.Name || testDisableTableLeases {
		// We don't go through the normal lease mechanism for system tables. The
		// system.lease and system.descriptor table, in particular, are problematic
		// because they are used for acquiring leases itself, creating a
		// chicken&egg problem.
		desc, err := p.getTableDesc(qname)
		if err != nil {
			return sqlbase.TableDescriptor{}, err
		}
		if desc == nil {
			return sqlbase.TableDescriptor{}, sqlbase.NewUndefinedTableError(qname.String())
		}
		return *desc, nil
	}

	if err := qname.NormalizeTableName(p.session.Database); err != nil {
		return sqlbase.TableDescriptor{}, err
	}

	dbID, err := p.getDatabaseID(qname.Database())
	if err != nil {
		return sqlbase.TableDescriptor{}, err
	}

	// First, look to see if we already have a lease for this table.
	// This ensures that, once a SQL transaction resolved name N to id X, it will
	// continue to use N to refer to X even if N is renamed during the
	// transaction.
	var lease *LeaseState
	for _, l := range p.leases {
		if sqlbase.NormalizeName(l.Name) == sqlbase.NormalizeName(qname.Table()) &&
			l.ParentID == dbID {
			lease = l
			if log.V(2) {
				log.Infof("found lease in planner cache for table %q", qname)
			}
			break
		}
	}

	// If we didn't find a lease, acquire one.
	if lease == nil {
		var err error
		lease, err = p.leaseMgr.AcquireByName(p.txn, dbID, qname.Table())
		if err != nil {
			if err == errDescriptorNotFound {
				// Transform the descriptor error into an error that references the
				// table's name.
				return sqlbase.TableDescriptor{}, sqlbase.NewUndefinedTableError(qname.String())
			}
			return sqlbase.TableDescriptor{}, err
		}
		p.leases = append(p.leases, lease)
		// If the lease we just acquired expires before the txn's deadline, reduce
		// the deadline.
		p.txn.UpdateDeadlineMaybe(roachpb.Timestamp{WallTime: lease.Expiration().UnixNano()})
	}
	return lease.TableDescriptor, nil
}