func makeMemberDir(dir string) error {
	membdir := path.Join(dir, "member")
	_, err := os.Stat(membdir)
	switch {
	case err == nil:
		return nil
	case !os.IsNotExist(err):
		return err
	}
	if err := os.MkdirAll(membdir, 0700); err != nil {
		return err
	}
	v1Files := types.NewUnsafeSet("conf", "log", "snapshot")
	v2Files := types.NewUnsafeSet("wal", "snap")
	names, err := fileutil.ReadDir(dir)
	if err != nil {
		return err
	}
	for _, name := range names {
		switch {
		case v1Files.Contains(name):
			// Link it to the subdir and keep the v1 file at the original
			// location, so v0.4 etcd can still bootstrap if the upgrade
			// failed.
			if err := os.Symlink(path.Join(dir, name), path.Join(membdir, name)); err != nil {
				return err
			}
		case v2Files.Contains(name):
			if err := os.Rename(path.Join(dir, name), path.Join(membdir, name)); err != nil {
				return err
			}
		}
	}
	return nil
}

// merge applies the properties of the passed-in User to the User on which it
// is called and returns a new User with these modifications applied. Think of
// all Users as immutable sets of data. Merge allows you to perform the set
// operations (desired grants and revokes) atomically
func (u User) merge(n User) (User, error) {
	var out User
	if u.User != n.User {
		return out, authErr(http.StatusConflict, "Merging user data with conflicting usernames: %s %s", u.User, n.User)
	}
	out.User = u.User
	if n.Password != "" {
		hash, err := bcrypt.GenerateFromPassword([]byte(n.Password), bcrypt.DefaultCost)
		if err != nil {
			return User{}, err
		}
		out.Password = string(hash)
	} else {
		out.Password = u.Password
	}
	currentRoles := types.NewUnsafeSet(u.Roles...)
	for _, g := range n.Grant {
		if currentRoles.Contains(g) {
			plog.Noticef("granting duplicate role %s for user %s", g, n.User)
			return User{}, authErr(http.StatusConflict, fmt.Sprintf("Granting duplicate role %s for user %s", g, n.User))
		}
		currentRoles.Add(g)
	}
	for _, r := range n.Revoke {
		if !currentRoles.Contains(r) {
			plog.Noticef("revoking ungranted role %s for user %s", r, n.User)
			return User{}, authErr(http.StatusConflict, fmt.Sprintf("Revoking ungranted role %s for user %s", r, n.User))
		}
		currentRoles.Remove(r)
	}
	out.Roles = currentRoles.Values()
	sort.Strings(out.Roles)
	return out, nil
}

// merge applies the properties of the passed-in User to the User on which it
// is called and returns a new User with these modifications applied. Think of
// all Users as immutable sets of data. Merge allows you to perform the set
// operations (desired grants and revokes) atomically
func (ou User) merge(nu User, s PasswordStore) (User, error) {
	var out User
	if ou.User != nu.User {
		return out, authErr(http.StatusConflict, "Merging user data with conflicting usernames: %s %s", ou.User, nu.User)
	}
	out.User = ou.User
	if nu.Password != "" {
		hash, err := s.HashPassword(nu.Password)
		if err != nil {
			return ou, err
		}
		out.Password = hash
	} else {
		out.Password = ou.Password
	}
	currentRoles := types.NewUnsafeSet(ou.Roles...)
	for _, g := range nu.Grant {
		if currentRoles.Contains(g) {
			plog.Noticef("granting duplicate role %s for user %s", g, nu.User)
			return User{}, authErr(http.StatusConflict, fmt.Sprintf("Granting duplicate role %s for user %s", g, nu.User))
		}
		currentRoles.Add(g)
	}
	for _, r := range nu.Revoke {
		if !currentRoles.Contains(r) {
			plog.Noticef("revoking ungranted role %s for user %s", r, nu.User)
			return User{}, authErr(http.StatusConflict, fmt.Sprintf("Revoking ungranted role %s for user %s", r, nu.User))
		}
		currentRoles.Remove(r)
	}
	out.Roles = currentRoles.Values()
	sort.Strings(out.Roles)
	return out, nil
}

func DetectDataDir(dirpath string) (DataDirVersion, error) {
	names, err := fileutil.ReadDir(dirpath)
	if err != nil {
		if os.IsNotExist(err) {
			err = nil
		}
		// Error reading the directory
		return DataDirUnknown, err
	}
	nameSet := types.NewUnsafeSet(names...)
	if nameSet.Contains("member") {
		ver, err := DetectDataDir(path.Join(dirpath, "member"))
		if ver == DataDir2_0 {
			return DataDir2_0_1, nil
		}
		return ver, err
	}
	if nameSet.ContainsAll([]string{"snap", "wal"}) {
		// .../wal cannot be empty to exist.
		walnames, err := fileutil.ReadDir(path.Join(dirpath, "wal"))
		if err == nil && len(walnames) > 0 {
			return DataDir2_0, nil
		}
	}
	if nameSet.ContainsAll([]string{"proxy"}) {
		return DataDir2_0Proxy, nil
	}
	return DataDirUnknown, nil
}

func DetectVersion(dirpath string) (WalVersion, error) {
	if _, err := os.Stat(dirpath); os.IsNotExist(err) {
		return WALNotExist, nil
	}
	names, err := fileutil.ReadDir(dirpath)
	if err != nil {
		// Error reading the directory
		return WALNotExist, err
	}
	if len(names) == 0 {
		// Empty WAL directory
		return WALNotExist, nil
	}
	nameSet := types.NewUnsafeSet(names...)
	if nameSet.ContainsAll([]string{"snap", "wal"}) {
		// .../wal cannot be empty to exist.
		if Exist(path.Join(dirpath, "wal")) {
			return WALv0_5, nil
		}
	}
	if nameSet.ContainsAll([]string{"snapshot", "conf", "log"}) {
		return WALv0_4, nil
	}

	return WALUnknown, nil
}

func checkVersion(dataDir string) (version, error) {
	names, err := fileutil.ReadDir(dataDir)
	if err != nil {
		if os.IsNotExist(err) {
			err = nil
		}
		return empty, err
	}
	if len(names) == 0 {
		return empty, nil
	}
	nameSet := types.NewUnsafeSet(names...)
	if nameSet.ContainsAll([]string{"member"}) {
		return v2_0, nil
	}
	if nameSet.ContainsAll([]string{"proxy"}) {
		return v2_0Proxy, nil
	}
	if nameSet.ContainsAll([]string{"snapshot", "conf", "log"}) {
		return v0_4, nil
	}
	if nameSet.ContainsAll([]string{"standby_info"}) {
		return v0_4, nil
	}
	return unknown, fmt.Errorf("failed to check version")
}

// Grant adds a set of permissions to the permission object on which it is called,
// returning a new permission object.
func (rw rwPermission) Grant(n rwPermission) (rwPermission, error) {
	var out rwPermission
	currentRead := types.NewUnsafeSet(rw.Read...)
	for _, r := range n.Read {
		if currentRead.Contains(r) {
			return out, authErr(http.StatusConflict, "Granting duplicate read permission %s", r)
		}
		currentRead.Add(r)
	}
	currentWrite := types.NewUnsafeSet(rw.Write...)
	for _, w := range n.Write {
		if currentWrite.Contains(w) {
			return out, authErr(http.StatusConflict, "Granting duplicate write permission %s", w)
		}
		currentWrite.Add(w)
	}
	out.Read = currentRead.Values()
	out.Write = currentWrite.Values()
	return out, nil
}

func newStore(namespaces ...string) *store {
	s := new(store)
	s.CurrentVersion = defaultVersion
	s.Root = newDir(s, "/", s.CurrentIndex, nil, "", Permanent)
	for _, namespace := range namespaces {
		s.Root.Add(newDir(s, namespace, s.CurrentIndex, s.Root, "", Permanent))
	}
	s.Stats = newStats()
	s.WatcherHub = newWatchHub(1000)
	s.ttlKeyHeap = newTtlKeyHeap()
	s.readonlySet = types.NewUnsafeSet(append(namespaces, "/")...)
	return s
}

// Revoke removes a set of permissions to the permission object on which it is called,
// returning a new permission object.
func (rw rwPermission) Revoke(n rwPermission) (rwPermission, error) {
	var out rwPermission
	currentRead := types.NewUnsafeSet(rw.Read...)
	for _, r := range n.Read {
		if !currentRead.Contains(r) {
			plog.Noticef("revoking ungranted read permission %s", r)
			continue
		}
		currentRead.Remove(r)
	}
	currentWrite := types.NewUnsafeSet(rw.Write...)
	for _, w := range n.Write {
		if !currentWrite.Contains(w) {
			plog.Noticef("revoking ungranted write permission %s", w)
			continue
		}
		currentWrite.Remove(w)
	}
	out.Read = currentRead.Values()
	out.Write = currentWrite.Values()
	return out, nil
}

func DetectVersion(dirpath string) WalVersion {
	names, err := fileutil.ReadDir(dirpath)
	if err != nil || len(names) == 0 {
		return WALNotExist
	}
	nameSet := types.NewUnsafeSet(names...)
	if nameSet.ContainsAll([]string{"snap", "wal"}) {
		// .../wal cannot be empty to exist.
		if Exist(path.Join(dirpath, "wal")) {
			return WALv0_5
		}
		return WALNotExist
	}
	if nameSet.ContainsAll([]string{"snapshot", "conf", "log"}) {
		return WALv0_4
	}

	return WALUnknown
}