feat(group): use device groups in -n flag

The final pass for 'madb group' commands, which allows group names to
be used as one of the device specifiers.

Closes #2

Change-Id: Ie694fd869e84af5fac1ab2cbcb43d11dda0e6f06
diff --git a/doc.go b/doc.go
index ebd7b87..50d0ebb 100644
--- a/doc.go
+++ b/doc.go
@@ -38,9 +38,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -102,9 +103,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -156,9 +158,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -208,9 +211,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -365,9 +369,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -470,9 +475,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -560,9 +566,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -621,9 +628,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
@@ -681,9 +689,10 @@
    Restrict the command to only run on emulators.
  -n=
    Comma-separated device serials, qualifiers, device indices (e.g., '@1',
-   '@2'), or nicknames (set by 'madb name'). A device index is specified by an
-   '@' sign followed by the index of the device in the output of 'adb devices'
-   command, starting from 1. Command will be run only on specified devices.
+   '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group').
+   A device index is specified by an '@' sign followed by the index of the
+   device in the output of 'adb devices' command, starting from 1. Command will
+   be run only on specified devices.
  -prefix=name
    Specify which output prefix to use. You can choose from the following
    options:
diff --git a/group.go b/group.go
index 60e5768..2d6d18d 100644
--- a/group.go
+++ b/group.go
@@ -8,7 +8,6 @@
 	"fmt"
 	"os"
 	"sort"
-	"strconv"
 	"strings"
 
 	"github.com/olekukonko/tablewriter"
@@ -16,8 +15,6 @@
 	"v.io/x/lib/cmdline"
 )
 
-// TODO(youngseokyoon): use the groups for filtering devices.
-
 var cmdMadbGroup = &cmdline.Command{
 	Children: []*cmdline.Command{
 		cmdMadbGroupAdd,
@@ -83,7 +80,7 @@
 
 	members := removeDuplicates(args[1:])
 	for _, member := range members {
-		if err := isValidMember(member, cfg); err != nil {
+		if err := isValidDeviceSpecifier(member); err != nil {
 			return fmt.Errorf("Invalid member %q: %v", member, err)
 		}
 	}
@@ -288,24 +285,6 @@
 	return writeConfig(cfg, filename)
 }
 
-// isValidMember takes a member string given as an argument, and returns nil
-// when the member string is valid. Otherwise, an error is returned inicating
-// the reason why the given member string is not valid.
-// TODO(youngseokyoon): reuse this function in madb.go.
-func isValidMember(member string, cfg *config) error {
-	if strings.HasPrefix(member, "@") {
-		index, err := strconv.Atoi(member[1:])
-		if err != nil || index <= 0 {
-			return fmt.Errorf("Invalid device specifier %q. '@' sign must be followed by a numeric device index starting from 1.", member)
-		}
-		return nil
-	} else if !isValidSerial(member) && !isValidName(member) {
-		return fmt.Errorf("Invalid device specifier %q. Not a valid serial or a nickname.", member)
-	}
-
-	return nil
-}
-
 // removeDuplicates takes a string slice and removes all the duplicates.
 func removeDuplicates(s []string) []string {
 	result := make([]string, 0, len(s))
@@ -339,3 +318,39 @@
 
 	return result
 }
+
+// expandGroups takes a slice of device specifier tokens and returns a new slice
+// where all the group name tokens are expanded to include all their members.
+// The expansion process is transitive; if a group includes other groups, all
+// the members of the other groups are also included in the returned slice. Each
+// group is processed at most once, in order to avoid infinite loops.
+func expandGroups(tokens []string, cfg *config) []string {
+	expanded := make([]string, 0, len(tokens))
+
+	queue := make([]string, len(tokens))
+	copy(queue, tokens)
+
+	visitedGroups := make(map[string]bool)
+
+	for len(queue) > 0 {
+		// Pop a token from the queue
+		token := queue[0]
+		queue = queue[1:]
+
+		if isGroupName(token, cfg) {
+			// If this group was already processed before, ignore and proceed
+			// to the next token to avoid infinite loops.
+			if visitedGroups[token] {
+				continue
+			}
+			visitedGroups[token] = true
+
+			// Otherwise, expand the group and add all the members to the queue.
+			queue = append(queue, cfg.Groups[token]...)
+		} else {
+			expanded = append(expanded, token)
+		}
+	}
+
+	return expanded
+}
diff --git a/madb.go b/madb.go
index 510d2a8..8020832 100644
--- a/madb.go
+++ b/madb.go
@@ -52,7 +52,7 @@
 func init() {
 	cmdMadb.Flags.BoolVar(&allDevicesFlag, "d", false, `Restrict the command to only run on real devices.`)
 	cmdMadb.Flags.BoolVar(&allEmulatorsFlag, "e", false, `Restrict the command to only run on emulators.`)
-	cmdMadb.Flags.StringVar(&devicesFlag, "n", "", `Comma-separated device serials, qualifiers, device indices (e.g., '@1', '@2'), or nicknames (set by 'madb name'). A device index is specified by an '@' sign followed by the index of the device in the output of 'adb devices' command, starting from 1. Command will be run only on specified devices.`)
+	cmdMadb.Flags.StringVar(&devicesFlag, "n", "", `Comma-separated device serials, qualifiers, device indices (e.g., '@1', '@2'), nicknames (set by 'madb name'), or group names (set by 'madb group'). A device index is specified by an '@' sign followed by the index of the device in the output of 'adb devices' command, starting from 1. Command will be run only on specified devices.`)
 	cmdMadb.Flags.BoolVar(&sequentialFlag, "seq", false, `Run the command sequentially, instead of running it in parallel.`)
 	cmdMadb.Flags.StringVar(&prefixFlag, "prefix", "name", `Specify which output prefix to use. You can choose from the following options:
     name   - Display the nickname of the device. The serial number is used instead if the
@@ -147,17 +147,12 @@
 }
 
 // Runs "adb devices -l" command, and parses the result to get all the device serial numbers.
-func getDevices(configFile string) ([]device, error) {
+func getDevices(cfg *config) ([]device, error) {
 	sh := gosh.NewShell(nil)
 	defer sh.Cleanup()
 
 	output := sh.Cmd("adb", "devices", "-l").Stdout()
 
-	cfg, err := readConfig(configFile)
-	if err != nil {
-		return nil, err
-	}
-
 	return parseDevicesOutput(output, cfg)
 }
 
@@ -233,12 +228,17 @@
 		return nil, err
 	}
 
-	allDevices, err := getDevices(configFile)
+	cfg, err := readConfig(configFile)
 	if err != nil {
 		return nil, err
 	}
 
-	filtered, err := filterSpecifiedDevices(allDevices)
+	allDevices, err := getDevices(cfg)
+	if err != nil {
+		return nil, err
+	}
+
+	filtered, err := filterSpecifiedDevices(allDevices, cfg)
 	if err != nil {
 		return nil, err
 	}
@@ -255,7 +255,7 @@
 	token string
 }
 
-func filterSpecifiedDevices(devices []device) ([]device, error) {
+func filterSpecifiedDevices(devices []device, cfg *config) ([]device, error) {
 	// If no device specifier flags are set, run on all devices and emulators.
 	if noDevicesSpecified() {
 		return devices, nil
@@ -265,18 +265,17 @@
 
 	var specs = []deviceSpec{}
 	if devicesFlag != "" {
+		// Check if the provided specifiers are all valid.
 		tokens := strings.Split(devicesFlag, ",")
 		for _, token := range tokens {
-			if strings.HasPrefix(token, "@") {
-				index, err := strconv.Atoi(token[1:])
-				if err != nil || index <= 0 {
-					return nil, fmt.Errorf("Invalid device specifier %q. '@' sign must be followed by a numeric device index starting from 1.", token)
-				}
-				specs = append(specs, deviceSpec{index, ""})
-			} else {
-				specs = append(specs, deviceSpec{0, token})
+			if err := isValidDeviceSpecifier(token); err != nil {
+				return nil, err
 			}
 		}
+
+		// Expand all the groups and get the device specs.
+		tokens = expandGroups(tokens, cfg)
+		specs = getDeviceSpecsFromTokens(tokens, cfg)
 	}
 
 	for _, d := range devices {
@@ -288,6 +287,23 @@
 	return result, nil
 }
 
+// getDeviceSpecsFromTokens takes device specifier tokens and turns them into
+// the corresponding deviceSpec structs.
+func getDeviceSpecsFromTokens(tokens []string, cfg *config) []deviceSpec {
+	specs := make([]deviceSpec, 0, len(tokens)*2)
+
+	for _, token := range tokens {
+		if strings.HasPrefix(token, "@") {
+			index, _ := strconv.Atoi(token[1:])
+			specs = append(specs, deviceSpec{index, ""})
+		} else {
+			specs = append(specs, deviceSpec{0, token})
+		}
+	}
+
+	return specs
+}
+
 func noDevicesSpecified() bool {
 	return allDevicesFlag == false &&
 		allEmulatorsFlag == false &&
@@ -455,6 +471,23 @@
 	return r.MatchString(name)
 }
 
+// isValidMember takes a member string given as an argument, and returns nil
+// when the member string is valid. Otherwise, an error is returned indicating
+// the reason why the given member string is not valid.
+func isValidDeviceSpecifier(member string) error {
+	if strings.HasPrefix(member, "@") {
+		index, err := strconv.Atoi(member[1:])
+		if err != nil || index <= 0 {
+			return fmt.Errorf("Invalid device specifier %q. '@' sign must be followed by a numeric device index starting from 1.", member)
+		}
+		return nil
+	} else if !isValidSerial(member) && !isValidName(member) {
+		return fmt.Errorf("Invalid device specifier %q. Not a valid serial or a nickname.", member)
+	}
+
+	return nil
+}
+
 type subCommandRunner struct {
 	// init is an optional function that does some initial work that should only
 	// be performed once, before directing the command to all the devices.
diff --git a/madb_test.go b/madb_test.go
index 7c4c946..e9bf5f0 100644
--- a/madb_test.go
+++ b/madb_test.go
@@ -213,16 +213,30 @@
 		flags deviceFlags
 		want  []device
 	}{
-		{deviceFlags{false, false, ""}, allDevices},                        // Nothing is specified
-		{deviceFlags{true, true, ""}, allDevices},                          // Both -d and -e are specified
-		{deviceFlags{true, false, ""}, []device{d1, d2, d3}},               // Only -d is specified
-		{deviceFlags{false, true, ""}, []device{e1, e2}},                   // Only -e is specified
-		{deviceFlags{false, false, "device:bullhead"}, []device{d1, d3}},   // Device qualifier
-		{deviceFlags{false, false, "ARMv7,SecondPhone"}, []device{e1, d3}}, // Nicknames
-		{deviceFlags{false, false, "@2,@4"}, []device{d2, d3}},             // Device Indices
-		{deviceFlags{true, false, "ARMv7"}, []device{d1, d2, e1, d3}},      // Combinations
-		{deviceFlags{false, true, "model:Nexus_9"}, []device{d2, e1, e2}},  // Combinations
-		{deviceFlags{false, false, "@1,SecondPhone"}, []device{d1, d3}},    // Combinations
+		{deviceFlags{false, false, ""}, allDevices},                                         // Nothing is specified
+		{deviceFlags{true, true, ""}, allDevices},                                           // Both -d and -e are specified
+		{deviceFlags{true, false, ""}, []device{d1, d2, d3}},                                // Only -d is specified
+		{deviceFlags{false, true, ""}, []device{e1, e2}},                                    // Only -e is specified
+		{deviceFlags{false, false, "device:bullhead"}, []device{d1, d3}},                    // Device qualifier
+		{deviceFlags{false, false, "ARMv7,SecondPhone"}, []device{e1, d3}},                  // Nicknames
+		{deviceFlags{false, false, "@2,@4"}, []device{d2, d3}},                              // Device Indices
+		{deviceFlags{false, false, "NormalGroup"}, []device{d1, d2, e1}},                    // Normal group
+		{deviceFlags{false, false, "SelfRefGroup"}, []device{d2}},                           // Self referencing group
+		{deviceFlags{false, false, "CyclicGroup1"}, []device{d1, d2, d3}},                   // Cyclic group inclusion
+		{deviceFlags{true, false, "ARMv7"}, []device{d1, d2, e1, d3}},                       // Combinations
+		{deviceFlags{false, true, "model:Nexus_9"}, []device{d2, e1, e2}},                   // Combinations
+		{deviceFlags{false, false, "@1,SecondPhone"}, []device{d1, d3}},                     // Combinations
+		{deviceFlags{false, false, "SecondPhone,NormalGroup,@1"}, []device{d1, d2, e1, d3}}, // Combinations
+	}
+
+	cfg := &config{
+		Groups: map[string][]string{
+			"NormalGroup":  []string{"deviceid01", "deviceid02", "@3"},
+			"SelfRefGroup": []string{"deviceid02", "SelfRefGroup"},
+			"CyclicGroup1": []string{"CyclicGroup2", "@1"},
+			"CyclicGroup2": []string{"@2", "CyclicGroup3"},
+			"CyclicGroup3": []string{"deviceid03", "CyclicGroup1"},
+		},
 	}
 
 	for i, testCase := range testCases {
@@ -230,7 +244,7 @@
 		allEmulatorsFlag = testCase.flags.allEmulators
 		devicesFlag = testCase.flags.devices
 
-		got, err := filterSpecifiedDevices(allDevices)
+		got, err := filterSpecifiedDevices(allDevices, cfg)
 		if err != nil {
 			t.Fatalf(err.Error())
 		}