Repository: aws-cloudformation/rain (go)

Issue:
tree command misses some resource dependencies
```
$ rain --version
Rain v1.8.1 linux/amd64
```

Consider the following template:

```yaml
Parameters:
  BackupPlanId:
    Type: String

Resources:
  BackupSelection:
    Type: AWS::Backup::BackupSelection
    Properties:
      BackupPlanId: !Ref BackupPlanId
      BackupSelection:
        IamRoleArn: !Sub arn:${AWS::Partition}:iam::${AWS::AccountId}:role/service-role/AWSBackupDefaultServiceRole
        Resources:
          - !Sub arn:${AWS::Partition}:elasticfilesystem:${AWS::Region}:${AWS::AccountId}:file-system/${EfsFileSystem}
        SelectionName: !Sub ${AWS::StackName}

  EfsFileSystem:
    Type: AWS::EFS::FileSystem
```

`rain tree` outputs the following:
```yaml
Resources:
  BackupSelection:
    DependsOn:
      Parameters:
        - AWS::Partition
        - AWS::StackName
        - BackupPlanId
```

Notice that the following dependencies are missing:
  1. Parameter `AWS::AccountId` (referenced in `Resources.BackupSelection.Properties.BackupSelection.IamRoleArn`)
  2. Resource `EfsFileSystem` (referenced in property `Resources.BackupSelection.Properties.BackupSelection.Resources[0]`)
  
If `Resources.BackupSelection.Properties.BackupSelection.Resources[0]` is changed to `!Sub ${EfsFileSystem.Arn}`, the resource dependency is found:

```yaml
Resources:
  BackupSelection:
    DependsOn:
      Parameters:
        - AWS::Partition
        - AWS::StackName
        - BackupPlanId
      Resources:
        - EfsFileSystem
```

Pull request:
Fix tree so it correctly parses Subs
Fixes #320

Patch:
diff --git a/cft/graph/util.go b/cft/graph/util.go
index 5efdafa9..f78ac32e 100644
--- a/cft/graph/util.go
+++ b/cft/graph/util.go
@@ -2,18 +2,44 @@ package graph
 
 import (
 	"fmt"
-	"regexp"
 	"strings"
 
+	"github.com/aws-cloudformation/rain/cft/parse"
 	"github.com/aws-cloudformation/rain/internal/config"
 )
 
-var subRe = regexp.MustCompile(`\$\{([^!].+?)\}`)
-
 func getRefs(t map[string]interface{}) []string {
 	return findRefs(t)
 }
 
+func parseSubString(refs []string, substr string) []string {
+	words, err := parse.ParseSub(substr)
+	if err != nil {
+		config.Debugf("Unable to parse Sub %s: %v", substr, err)
+		return refs
+	}
+
+	for _, word := range words {
+		switch word.T {
+		case parse.AWS:
+			refs = append(refs, fmt.Sprintf("AWS::%s", word.W))
+		case parse.REF:
+			refs = append(refs, word.W)
+		case parse.GETATT:
+			left, _, found := strings.Cut(word.W, ".")
+			if !found {
+				config.Debugf("unexpected GetAtt %s", word.W)
+			} else {
+				refs = append(refs, left)
+			}
+		}
+	}
+
+	config.Debugf("After parsing Sub, refs is now: %v", refs)
+
+	return refs
+}
+
 func findRefs(t map[string]interface{}) []string {
 	refs := make([]string, 0)
 
@@ -47,9 +73,7 @@ func findRefs(t map[string]interface{}) []string {
 		case "Fn::Sub":
 			switch v := value.(type) {
 			case string:
-				for _, groups := range subRe.FindAllStringSubmatch(v, 1) {
-					refs = append(refs, groups[1])
-				}
+				refs = parseSubString(refs, v)
 			case []interface{}:
 				switch {
 				case len(v) != 2:


Test patch:
diff --git a/internal/cmd/tree/tree_test.go b/internal/cmd/tree/tree_test.go
index f0e85855..ef6c5e83 100644
--- a/internal/cmd/tree/tree_test.go
+++ b/internal/cmd/tree/tree_test.go
@@ -23,3 +23,27 @@ func Example_tree() {
 	//       Parameters:
 	//         - BucketName
 }
+
+func Example_sub() {
+
+	os.Args = []string{
+		os.Args[0],
+		"../../../test/templates/fix-320.yaml",
+	}
+
+	console.NoColour = true
+
+	tree.Cmd.Execute()
+	// Output:
+	// Resources:
+	//   BackupSelection:
+	//     DependsOn:
+	//       Parameters:
+	//         - AWS::AccountId
+	//         - AWS::Partition
+	//         - AWS::Region
+	//         - AWS::StackName
+	//         - BackupPlanId
+	//       Resources:
+	//         - EfsFileSystem
+}
diff --git a/test/templates/fix-320.yaml b/test/templates/fix-320.yaml
new file mode 100644
index 00000000..03b1d496
--- /dev/null
+++ b/test/templates/fix-320.yaml
@@ -0,0 +1,18 @@
+Parameters:
+  BackupPlanId:
+    Type: String
+
+Resources:
+  BackupSelection:
+    Type: AWS::Backup::BackupSelection
+    Properties:
+      BackupPlanId: !Ref BackupPlanId
+      BackupSelection:
+        IamRoleArn: !Sub arn:${AWS::Partition}:iam::${AWS::AccountId}:role/service-role/AWSBackupDefaultServiceRole
+        Resources:
+          - !Sub arn:${AWS::Partition}:elasticfilesystem:${AWS::Region}:${AWS::AccountId}:file-system/${EfsFileSystem}
+        SelectionName: !Sub ${AWS::StackName}
+
+  EfsFileSystem:
+    Type: AWS::EFS::FileSystem
+