diff --git a/cmdline/.api b/cmdline/.api
index fa05fd7..b48e367 100644
--- a/cmdline/.api
+++ b/cmdline/.api
@@ -5,6 +5,8 @@
 pkg cmdline, func Main(*Command)
 pkg cmdline, func Parse(*Command, *Env, []string) (Runner, []string, error)
 pkg cmdline, func ParseAndRun(*Command, *Env, []string) error
+pkg cmdline, method (*Env) LookPath(string) string
+pkg cmdline, method (*Env) LookPathAll(string, map[string]bool) []string
 pkg cmdline, method (*Env) TimerPop()
 pkg cmdline, method (*Env) TimerPush(string)
 pkg cmdline, method (*Env) UsageErrorf(string, ...interface{}) error
diff --git a/cmdline/cmdline.go b/cmdline/cmdline.go
index 3c06f57..e548b78 100644
--- a/cmdline/cmdline.go
+++ b/cmdline/cmdline.go
@@ -45,6 +45,7 @@
 	"io/ioutil"
 	"os"
 	"os/exec"
+	"path/filepath"
 	"reflect"
 	"sort"
 	"strings"
@@ -372,8 +373,7 @@
 	}
 	if cmd.LookPath {
 		// Look for a matching executable in PATH.
-		subCmd := cmd.Name + "-" + subName
-		if lookPath(env, subCmd) {
+		if subCmd := env.LookPath(cmd.Name + "-" + subName); subCmd != "" {
 			extArgs := append(flagsAsArgs(setFlags), subArgs...)
 			return binaryRunner{subCmd, cmdPath}, extArgs, nil
 		}
@@ -491,10 +491,10 @@
 
 // subNames returns the sub names of c which should be ignored when using look
 // path to find external binaries.
-func (c *Command) subNames() map[string]bool {
-	m := map[string]bool{"help": true}
+func (c *Command) subNames(prefix string) map[string]bool {
+	m := map[string]bool{prefix + "help": true}
 	for _, child := range c.Children {
-		m[child.Name] = true
+		m[prefix+child.Name] = true
 	}
 	return m
 }
@@ -537,7 +537,7 @@
 }
 
 func (b binaryRunner) Run(env *Env, args []string) error {
-	env.TimerPush("run " + b.subCmd)
+	env.TimerPush("run " + filepath.Base(b.subCmd))
 	defer env.TimerPop()
 	vars := envvar.CopyMap(env.Vars)
 	vars["CMDLINE_PREFIX"] = b.cmdPath
@@ -555,54 +555,3 @@
 	}
 	return err
 }
-
-// lookPath returns true iff an executable with the given name can be found in
-// any of the PATH directories.
-func lookPath(env *Env, name string) bool {
-	env.TimerPush("lookpath " + name)
-	defer env.TimerPop()
-	for _, dir := range env.pathDirs() {
-		fileInfos, err := ioutil.ReadDir(dir)
-		if err != nil {
-			continue
-		}
-		for _, fileInfo := range fileInfos {
-			if m := fileInfo.Mode(); !m.IsRegular() || (m&os.FileMode(0111)) == 0 {
-				continue
-			}
-			if fileInfo.Name() == name {
-				return true
-			}
-		}
-	}
-	return false
-}
-
-// lookPathAll returns a deduped list of all executables found in the PATH
-// directories whose name starts with "name-", and where the name doesn't match
-// the given seen set.  The seen set may be mutated by this function.
-func lookPathAll(env *Env, name string, seen map[string]bool) (result []string) {
-	env.TimerPush("lookpathall " + name)
-	defer env.TimerPop()
-	for _, dir := range env.pathDirs() {
-		fileInfos, err := ioutil.ReadDir(dir)
-		if err != nil {
-			continue
-		}
-		for _, fileInfo := range fileInfos {
-			if m := fileInfo.Mode(); !m.IsRegular() || (m&os.FileMode(0111)) == 0 {
-				continue
-			}
-			if !strings.HasPrefix(fileInfo.Name(), name+"-") {
-				continue
-			}
-			subname := fileInfo.Name()[len(name+"-"):]
-			if seen[subname] {
-				continue
-			}
-			seen[subname] = true
-			result = append(result, fileInfo.Name())
-		}
-	}
-	return
-}
diff --git a/cmdline/env.go b/cmdline/env.go
index a1cffe9..d9fbbd3 100644
--- a/cmdline/env.go
+++ b/cmdline/env.go
@@ -42,6 +42,17 @@
 	Usage func(env *Env, w io.Writer)
 }
 
+func (e *Env) clone() *Env {
+	return &Env{
+		Stdin:  e.Stdin,
+		Stdout: e.Stdout,
+		Stderr: e.Stderr,
+		Vars:   envvar.CopyMap(e.Vars),
+		Usage:  e.Usage,
+		Timer:  e.Timer, // use the same timer for all operations
+	}
+}
+
 // UsageErrorf prints the error message represented by the printf-style format
 // and args, followed by the output of the Usage function.  Returns ErrUsage to
 // make it easy to use from within the Runner.Run function.
@@ -63,15 +74,20 @@
 	}
 }
 
-func (e *Env) clone() *Env {
-	return &Env{
-		Stdin:  e.Stdin,
-		Stdout: e.Stdout,
-		Stderr: e.Stderr,
-		Vars:   envvar.CopyMap(e.Vars),
-		Usage:  e.Usage,
-		Timer:  e.Timer, // use the same timer for all operations
-	}
+// LookPath returns the absolute path of the executable with the given name,
+// based on the directories in PATH.  Calls envvar.LookPath.
+func (e *Env) LookPath(name string) string {
+	e.TimerPush("lookpath " + name)
+	defer e.TimerPop()
+	return envvar.LookPath(e.pathDirs(), name)
+}
+
+// LookPathAll returns the absolute paths of all executables with the given name
+// prefix, based on the directories in PATH.  Calls envvar.LookPath.
+func (e *Env) LookPathAll(prefix string, names map[string]bool) []string {
+	e.TimerPush("lookpathall " + prefix)
+	defer e.TimerPop()
+	return envvar.LookPathAll(e.pathDirs(), prefix, names)
 }
 
 func usageErrorf(env *Env, usage func(*Env, io.Writer), format string, args ...interface{}) error {
diff --git a/cmdline/help.go b/cmdline/help.go
index 6be123c..6971b8b 100644
--- a/cmdline/help.go
+++ b/cmdline/help.go
@@ -10,6 +10,7 @@
 	"fmt"
 	"go/doc"
 	"io"
+	"path/filepath"
 	"regexp"
 	"strings"
 	"unicode"
@@ -126,9 +127,8 @@
 	}
 	if cmd.LookPath {
 		// Look for a matching executable in PATH.
-		extName := cmd.Name + "-" + subName
-		if lookPath(env, extName) {
-			runner := binaryRunner{extName, cmdPath}
+		if subCmd := env.LookPath(cmd.Name + "-" + subName); subCmd != "" {
+			runner := binaryRunner{subCmd, cmdPath}
 			envCopy := env.clone()
 			envCopy.Vars["CMDLINE_STYLE"] = config.style.String()
 			if len(subArgs) == 0 {
@@ -226,9 +226,9 @@
 		usageAll(w, env, append(path, help), config, false)
 	}
 	if cmd.LookPath {
-		extNames := lookPathAll(env, cmd.Name, cmd.subNames())
-		for _, extName := range extNames {
-			runner := binaryRunner{extName, cmdPath}
+		cmdPrefix := cmd.Name + "-"
+		for _, subCmd := range env.LookPathAll(cmdPrefix, cmd.subNames(cmdPrefix)) {
+			runner := binaryRunner{subCmd, cmdPath}
 			var buffer bytes.Buffer
 			envCopy := env.clone()
 			envCopy.Stdout = &buffer
@@ -260,7 +260,8 @@
 			}
 			// The external child does not support "help" or "-help".
 			lineBreak(w, config.style)
-			fmt.Fprintln(w, godocHeader(cmdPath+" "+strings.TrimPrefix(extName, cmd.Name+"-"), missingDescription))
+			subName := strings.TrimPrefix(filepath.Base(subCmd), cmdPrefix)
+			fmt.Fprintln(w, godocHeader(cmdPath+" "+subName, missingDescription))
 		}
 	}
 	for _, topic := range cmd.Topics {
@@ -307,8 +308,9 @@
 		}
 	}
 	var extChildren []string
+	cmdPrefix := cmd.Name + "-"
 	if cmd.LookPath {
-		extChildren = lookPathAll(env, cmd.Name, cmd.subNames())
+		extChildren = env.LookPathAll(cmdPrefix, cmd.subNames(cmdPrefix))
 	}
 	hasSubcommands := len(cmd.Children) > 0 || len(extChildren) > 0
 	if hasSubcommands {
@@ -326,8 +328,9 @@
 			nameWidth = w
 		}
 	}
-	for _, ext := range extChildren {
-		if w := len(strings.TrimPrefix(ext, cmd.Name+"-")); w > nameWidth {
+	for _, extCmd := range extChildren {
+		extName := strings.TrimPrefix(filepath.Base(extCmd), cmdPrefix)
+		if w := len(extName); w > nameWidth {
 			nameWidth = w
 		}
 	}
@@ -351,8 +354,8 @@
 		fmt.Fprintln(w, "The", cmdPath, "external commands are:")
 		// Print as a table with aligned columns Name and Short.
 		w.SetIndents(spaces(3), spaces(3+nameWidth+1))
-		for _, ext := range extChildren {
-			runner := binaryRunner{ext, cmdPath}
+		for _, extCmd := range extChildren {
+			runner := binaryRunner{extCmd, cmdPath}
 			var buffer bytes.Buffer
 			envCopy := env.clone()
 			envCopy.Stdout = &buffer
@@ -363,7 +366,8 @@
 				// The external child supports "-help".
 				short = buffer.String()
 			}
-			printShort(nameWidth, strings.TrimPrefix(ext, cmd.Name+"-"), short)
+			extName := strings.TrimPrefix(filepath.Base(extCmd), cmdPrefix)
+			printShort(nameWidth, extName, short)
 		}
 	}
 	// Command footer.
diff --git a/envvar/.api b/envvar/.api
index af7a167..d88baae 100644
--- a/envvar/.api
+++ b/envvar/.api
@@ -2,6 +2,8 @@
 pkg envvar, func CopySlice([]string) []string
 pkg envvar, func JoinKeyValue(string, string) string
 pkg envvar, func JoinTokens([]string, string) string
+pkg envvar, func LookPath([]string, string) string
+pkg envvar, func LookPathAll([]string, string, map[string]bool) []string
 pkg envvar, func MapToSlice(map[string]string) []string
 pkg envvar, func MergeMaps(...map[string]string) map[string]string
 pkg envvar, func MergeSlices(...[]string) []string
diff --git a/envvar/lookpath.go b/envvar/lookpath.go
new file mode 100644
index 0000000..2c9983e
--- /dev/null
+++ b/envvar/lookpath.go
@@ -0,0 +1,82 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package envvar
+
+import (
+	"io/ioutil"
+	"path/filepath"
+	"sort"
+	"strings"
+)
+
+// LookPath returns the absolute path of the executable with the given name,
+// based on the given dirs.  If multiple exectuables match the name, the first
+// match in dirs is returned.  Invalid dirs are silently ignored.
+func LookPath(dirs []string, name string) string {
+	if strings.Contains(name, string(filepath.Separator)) {
+		return ""
+	}
+	for _, dir := range dirs {
+		fileInfos, err := ioutil.ReadDir(dir)
+		if err != nil {
+			continue
+		}
+		for _, fileInfo := range fileInfos {
+			if m := fileInfo.Mode(); !m.IsRegular() || (m&0111 == 0) {
+				continue
+			}
+			if fileInfo.Name() == name {
+				return filepath.Join(dir, name)
+			}
+		}
+	}
+	return ""
+}
+
+// LookPathAll returns the absolute paths of all executables with the given name
+// prefix, based on the given dirs.  If multiple exectuables match the prefix
+// with the same name, the first match in dirs is returned.  Invalid dirs are
+// silently ignored.  Returns a list of paths sorted by name.
+//
+// The names are filled in as the method runs, to ensure the first matching
+// property.  As a consequence, you may pass in a pre-populated names map to
+// prevent matching those names.  It is fine to pass in a nil names map.
+func LookPathAll(dirs []string, prefix string, names map[string]bool) []string {
+	if strings.Contains(prefix, string(filepath.Separator)) {
+		return nil
+	}
+	if names == nil {
+		names = make(map[string]bool)
+	}
+	var all []string
+	for _, dir := range dirs {
+		fileInfos, err := ioutil.ReadDir(dir)
+		if err != nil {
+			continue
+		}
+		for _, fileInfo := range fileInfos {
+			if m := fileInfo.Mode(); !m.IsRegular() || (m&0111 == 0) {
+				continue
+			}
+			name, prefixLen := fileInfo.Name(), len(prefix)
+			if len(name) < prefixLen || name[:prefixLen] != prefix {
+				continue
+			}
+			if names[name] {
+				continue
+			}
+			names[name] = true
+			all = append(all, filepath.Join(dir, name))
+		}
+	}
+	sort.Sort(byBase(all))
+	return all
+}
+
+type byBase []string
+
+func (x byBase) Len() int           { return len(x) }
+func (x byBase) Less(i, j int) bool { return filepath.Base(x[i]) < filepath.Base(x[j]) }
+func (x byBase) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
diff --git a/envvar/lookpath_test.go b/envvar/lookpath_test.go
new file mode 100644
index 0000000..57d5933
--- /dev/null
+++ b/envvar/lookpath_test.go
@@ -0,0 +1,122 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package envvar
+
+import (
+	"io/ioutil"
+	"os"
+	"path/filepath"
+	"reflect"
+	"testing"
+)
+
+func mkdir(t *testing.T, d ...string) string {
+	path := filepath.Join(d...)
+	if err := os.MkdirAll(path, 0755); err != nil {
+		t.Fatal(err)
+	}
+	return path
+}
+
+func mkfile(t *testing.T, dir, file string, perm os.FileMode) string {
+	path := filepath.Join(dir, file)
+	f, err := os.OpenFile(path, os.O_CREATE|os.O_EXCL|os.O_WRONLY, perm)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if err := f.Close(); err != nil {
+		t.Fatal(err)
+	}
+	return path
+}
+
+func initTmpDir(t *testing.T) (string, func()) {
+	tmpDir, err := ioutil.TempDir("", "envvar_lookpath")
+	if err != nil {
+		t.Fatal(err)
+	}
+	return tmpDir, func() {
+		if err := os.RemoveAll(tmpDir); err != nil {
+			t.Error(err)
+		}
+	}
+}
+
+func TestLookPath(t *testing.T) {
+	tmpDir, cleanup := initTmpDir(t)
+	defer cleanup()
+	dirA, dirB := mkdir(t, tmpDir, "a"), mkdir(t, tmpDir, "b")
+	aFoo, aBar := mkfile(t, dirA, "foo", 0755), mkfile(t, dirA, "bar", 0755)
+	bBar, bBaz := mkfile(t, dirB, "bar", 0755), mkfile(t, dirB, "baz", 0755)
+	_, bExe := mkfile(t, dirA, "exe", 0644), mkfile(t, dirB, "exe", 0755)
+	tests := []struct {
+		Dirs []string
+		Name string
+		Want string
+	}{
+		{nil, "", ""},
+		{nil, "foo", ""},
+		{[]string{dirA}, "foo", aFoo},
+		{[]string{dirA}, "bar", aBar},
+		{[]string{dirA}, "baz", ""},
+		{[]string{dirB}, "foo", ""},
+		{[]string{dirB}, "bar", bBar},
+		{[]string{dirB}, "baz", bBaz},
+		{[]string{dirA, dirB}, "foo", aFoo},
+		{[]string{dirA, dirB}, "bar", aBar},
+		{[]string{dirA, dirB}, "baz", bBaz},
+		// Make sure we find bExe, since aExe isn't executable
+		{[]string{dirA, dirB}, "exe", bExe},
+	}
+	for _, test := range tests {
+		if got, want := LookPath(test.Dirs, test.Name), test.Want; got != want {
+			t.Errorf("dirs=%v name=%v got %v, want %v", test.Dirs, test.Name, got, want)
+		}
+	}
+}
+
+func TestLookPathAll(t *testing.T) {
+	tmpDir, cleanup := initTmpDir(t)
+	defer cleanup()
+	dirA, dirB := mkdir(t, tmpDir, "a"), mkdir(t, tmpDir, "b")
+	aFoo, aBar := mkfile(t, dirA, "foo", 0755), mkfile(t, dirA, "bar", 0755)
+	bBar, bBaz := mkfile(t, dirB, "bar", 0755), mkfile(t, dirB, "baz", 0755)
+	aBzz, bBaa := mkfile(t, dirA, "bzz", 0755), mkfile(t, dirB, "baa", 0755)
+	_, bExe := mkfile(t, dirA, "exe", 0644), mkfile(t, dirB, "exe", 0755)
+	tests := []struct {
+		Dirs   []string
+		Prefix string
+		Names  map[string]bool
+		Want   []string
+	}{
+		{nil, "", nil, nil},
+		{nil, "foo", nil, nil},
+		{[]string{dirA}, "foo", nil, []string{aFoo}},
+		{[]string{dirA}, "bar", nil, []string{aBar}},
+		{[]string{dirA}, "baz", nil, nil},
+		{[]string{dirA}, "f", nil, []string{aFoo}},
+		{[]string{dirA}, "b", nil, []string{aBar, aBzz}},
+		{[]string{dirB}, "foo", nil, nil},
+		{[]string{dirB}, "bar", nil, []string{bBar}},
+		{[]string{dirB}, "baz", nil, []string{bBaz}},
+		{[]string{dirB}, "f", nil, nil},
+		{[]string{dirB}, "b", nil, []string{bBaa, bBar, bBaz}},
+		{[]string{dirA, dirB}, "foo", nil, []string{aFoo}},
+		{[]string{dirA, dirB}, "bar", nil, []string{aBar}},
+		{[]string{dirA, dirB}, "baz", nil, []string{bBaz}},
+		{[]string{dirA, dirB}, "f", nil, []string{aFoo}},
+		{[]string{dirA, dirB}, "b", nil, []string{bBaa, aBar, bBaz, aBzz}},
+		// Don't find baz, since it's already provided.
+		{[]string{dirA, dirB}, "b", map[string]bool{"baz": true}, []string{bBaa, aBar, aBzz}},
+		// Make sure we find bExe, since aExe isn't executable
+		{[]string{dirA, dirB}, "exe", nil, []string{bExe}},
+		{[]string{dirA, dirB}, "e", nil, []string{bExe}},
+	}
+	for _, test := range tests {
+		if got, want := LookPathAll(test.Dirs, test.Prefix, test.Names), test.Want; !reflect.DeepEqual(got, want) {
+			t.Errorf("dirs=%v prefix=%v names=%v got %v, want %v", test.Dirs, test.Prefix, test.Names, got, want)
+		}
+	}
+}