How to parse a hierarchical data structure containing inner references and possible circular references?

I'm implementing a GUI for setting up user roles, where the admin of the application has the possibility to define nested roles. Roles in this particular case are defined by simple key-value pairs, the key identifying the role, and the value being either a "child role" that the current role extends, or a path to some part of the application. Here are some arbitrary examples of the possible structures:

user => path::/articles/read
user => path::/settings/edit/my

moderator => extend::user
moderator => path::/articles/edit

siteadmin => extend::moderator
siteadmin => extend::some-other-role
siteadmin => path::/user/ban

As you can see, roles can be nested, and a single role can extend multiple roles.

My objective is to

• detect and warn about circular references caused by extending roles
• flatten out the whole data structure, so rules will only contain "path" type definitions.

How would you approach this problem? I'm implementing this in php, but any solution (pseudo code, java, et开发者_开发技巧c) is appreciated (given the algorithm is right).

---

Code below should do the trick. You will need to provide a simple parser to parse values to the left and to the right of '=>' sign and feed it the Flatten.update() method below.

The code works in two stages:

1) Build a mapping for each role to the list of paths declared with "path::" and list of parent roles declared with "extend::"

2) Flatten all paths for each role, by traversing the mapping while keeping a map of all visited parent nodes to avoid circular dependencies.

class ChildValue {
    Set<String> paths = new HashSet<String>();
    Set<String> extend = new HashSet<String>();
}

/*
 * Logic to flatten interpret and flatten out
 * roles data
 */
class Flatten {
    // logical mapping store
    Map<String, ChildValue> mapping = new HashMap<String, ChildValue>();

    // Stage 1. Build logical mappin
    //
    // Call this method for every "role" => "path::/path" or "extend::role" pair
    void update(String roleName, String value) {
        ChildValue child = mapping.get(roleName);
        if (null == child) {
            // create new child node
            child = new ChildValue();
            mapping.put(roleName, child);
        }

        if (value.startsWith("path::")) {
            String path = value.substring(6);
            child.paths.add(path);
        } else {// assume "extend::"
            String extend = value.substring(8);
            child.extend.add(extend);
        }
    }

    // Stage 2.
    // After the mapping is build, call this method to
    // find all flattened paths for the role you need
    Set<String> getPathsFor(String roleName) {
        Set<String> visited = new HashSet<String>();
        return getPathsFor(roleName, visited);
    }

    // this method is called recursively
    private Set<String> getPathsFor(String roleName, Set<String> visited) {
        Set<String> paths = new HashSet<String>();
        ChildValue child = mapping.get(roleName);
        if (child != null) {
            // first add all paths directly declared with "path::"
            paths.addAll(child.paths);
            // then add all transitive paths
            for (String extendedRole : child.extend) {
                // check if parent node has not yet been visited
                // to avoid circular dependencies
                if (!visited.contains(extendedRole)) {
                    // not yet visited here, add all extended paths
                    visited.add(extendedRole);
                    paths.addAll(getPathsFor(extendedRole, visited));
                }else{
                        // node already visited, seems like we
                        // we have a circular dependency
                        throw new RuntimeException("Detected circular dep");
                }
            }
        }
        return paths;
    }
}

Here is a simple test for the code above

public class Roles {
    public static void main(String[] args) {
        Flatten ft = new Flatten();
        ft.update("user", "path::/path1");
        ft.update("user", "path::/path2");
        ft.update("user", "extend::parent");

        ft.update("parent", "path::/parent/path1");
        ft.update("parent", "path::/parent/path2");
        ft.update("parent", "extend::user");// circular dep

        System.out.println("paths for user => " + ft.getPathsFor("user"));
        System.out.println("paths for parent => " + ft.getPathsFor("parent"));
        System.out.println("paths for unknown => " + ft.getPathsFor("unknown"));

            //will print
            // paths for user => [/path2, /path1, /parent/path2, /parent/path1]
            // paths for parent => [/path2, /path1, /parent/path2, /parent/path1]
            // paths for unknown => []
    }
}

Hope this captures the general idea.