downstream_dependency_map 0.1.0

/*
 * This is free and unencumbered software released into the public domain.
 *
 * Anyone is free to copy, modify, publish, use, compile, sell, or
 * distribute this software, either in source code form or as a compiled
 * binary, for any purpose, commercial or non-commercial, and by any
 * means.
 *
 * In jurisdictions that recognize copyright laws, the author or authors
 * of this software dedicate any and all copyright interest in the
 * software to the public domain. We make this dedication for the benefit
 * of the public at large and to the detriment of our heirs and
 * successors. We intend this dedication to be an overt act of
 * relinquishment in perpetuity of all present and future rights to this
 * software under copyright law.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 *
 * For more information, please refer to <http://unlicense.org/>
*/

use std::io::Write;
use std::borrow::Cow;
use std::fs::{self, File};
use std::path::PathBuf;
use std::collections::BTreeMap;
use serde_json::{json, Value};
use std::env;

#[derive(Debug, Clone)]
enum DepTree {
    Children((PathBuf, Vec<DepTree>)),
    Childless(PathBuf),
}

fn main() {
    let arglist_full = &env::args().collect::<Vec<String>>();

    let binary_name = PathBuf::from(&arglist_full[0]).file_name().unwrap().to_string_lossy().to_string();

    let arglist = &arglist_full[1..];

    let help_message = format!("
Usage: {} [downstream_compile_commands.json] [downstream kernel directory] [relative build directory name (must be in the high source tree)] [mainline kernel directory] [option] ...

Example: {} downstream_kernel/build/compile_commands.json downstream_kernel/ build/ mainline_kernel/ -pd

Options:
  --path-absolute, -a : Use absolute path to the source directory
  --print-dependencies, -pd : Print dependencies tree
  --print-includes, -pi : Print includes
  --dependencies-json, -dj [output.json] : Export dependencies tree to a .json file
  --dependencies-dot, -dd [output.dot] : Export dependencies tree to a .dot file
  --includes-json, -ij [output.json] : Export includes to a .json file
  --includes-dot, -id [output.dot] : Export includes to a .dot file

How to make it work:
  1. Compile your downstream kernel with Clang, generate \"compile_commands.json\" from the build, I recommend using \"bear -- [./build_script.sh]\"
  2. Download the mainline kernel of an exactly same version
  3. Use the utility to generate the dependencies and includes trees
"
    , binary_name, binary_name);

    if arglist.contains(&"--help".to_string()) || arglist.contains(&"-h".to_string()) || arglist.len() < 4 {
        println!("{}", help_message);
    } else if arglist.len() >= 4 {
        let mut option_path_absolute = false;
        let mut option_print_dependencies = false;
        let mut option_print_includes = false;
        let mut option_dependencies_json: Option<String> = None;
        let mut option_dependencies_dot: Option<String> = None;
        let mut option_includes_json: Option<String> = None;
        let mut option_includes_dot: Option<String> = None;

        let arg_flags = &arglist[4..];

        let mut flags_list = arg_flags.iter();

        while let Some(flag_read) = flags_list.next() {
            match flag_read.as_str() {
                "--path-absolute" | "-a" => {
                    option_path_absolute = true;
                },
                "--print-dependencies" | "-pd" => {
                    option_print_dependencies = true;
                },
                "--print-includes" | "-pi" => {
                    option_print_includes = true;
                },
                "--dependencies-json" | "-dj" => {
                    if let Some(file_name) = flags_list.next() {
                        option_dependencies_json = Some(file_name.to_string());
                    }
                },
                "--dependencies-dot" | "-dd" => {
                    if let Some(file_name) = flags_list.next() {
                        option_dependencies_dot = Some(file_name.to_string());
                    }
                },
                "--includes-json" | "-ij" => {
                    if let Some(file_name) = flags_list.next() {
                        option_includes_json = Some(file_name.to_string());
                    }
                },
                "--includes-dot" | "-id" => {
                    if let Some(file_name) = flags_list.next() {
                        option_includes_dot = Some(file_name.to_string());
                    }
                },
                _ => ()
            }
        }

        if option_path_absolute == false && option_print_dependencies == false && option_print_includes == false && option_dependencies_json == None && option_dependencies_dot == None && option_includes_json == None && option_includes_dot == None {
            println!("{}", help_message);
        } else {
            if let Ok(_) = fs::read_dir(arglist.get(1).unwrap()) {

                if let Ok(read_data) = fs::read(arglist.get(0).unwrap().clone()) {

                    let mut path_source = std::fs::canonicalize(&arglist.get(1).unwrap()).unwrap();
                    let path_source_out = path_source.join(PathBuf::from(&arglist.get(2).unwrap()).iter().last().unwrap().to_str().unwrap());
                    let path_dest = std::fs::canonicalize(&arglist.get(3).unwrap()).unwrap();

                    let read_data_string = String::from_utf8(read_data).unwrap();

                    let mut list_dirs_includes: BTreeMap<PathBuf, Vec<PathBuf>> = BTreeMap::new();

                    if let Ok(got_val) = serde_json::from_str::<Value>(read_data_string.as_str()) {

                        for f in got_val.as_array().unwrap() {

                            let to_read_file = PathBuf::from(f["file"].as_str().unwrap());
                            let to_read_dir = to_read_file.parent().unwrap().to_path_buf();

                            if !has_parent(&path_source, &to_read_dir, &path_source_out) {

                                let to_read_dir_str = get_path_relative(&path_source, &to_read_dir);

                                let to_read_dir_local = path_dest.join(to_read_dir_str);

                                if !to_read_dir_local.exists() {
                                    for a in f["arguments"].as_array().unwrap() {
                                        let mut include = a.as_str().unwrap().to_string();

                                        /* Assuming the include is above the build directory */

                                        if include.starts_with("-I../") {

                                            include = include.replace("-I../", "").replace("//", "/");
                                            let include_check = path_dest.clone().join(include.clone());

                                            if include_check.exists() == false {
                                                let include_got_file = path_source.clone().join(include.clone());

                                                if include_got_file.exists() {
                                                    if !has_parent(&path_source, &include_got_file, &path_source_out) {
                                                        let include_got = include_got_file.canonicalize().unwrap();

                                                        if include_got != to_read_dir {
                                                            match list_dirs_includes.get_mut(&to_read_dir) {
                                                                Some(list_dep) => {
                                                                    if !list_dep.contains(&include_got) {
                                                                        list_dep.push(include_got);
                                                                    }
                                                                },
                                                                None => {
                                                                    list_dirs_includes.insert(to_read_dir.clone(), vec![]);
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }

                                }
                            }
                        }
                    }

                    for key in list_dirs_includes.keys().map(|x| x.clone()).collect::<Vec<PathBuf>>() {
                        let mut path_back: PathBuf = key.to_path_buf();

                        loop {
                            if path_back == *path_source {
                                break;
                            }

                            match child_clean_inherited_includes(&path_source, &mut list_dirs_includes, &path_back, &key) {
                                Some(path_result) => {
                                    path_back = path_result;
                                },
                                None => {
                                    break;
                                }
                            }
                        }
                    }

                    let mut results_depends: BTreeMap<PathBuf, Vec<PathBuf>> = BTreeMap::new();

                    for (dirname, includes) in &list_dirs_includes.clone() {
                        let mut deps_list: Vec<PathBuf> = vec![];

                        for incl in includes {
                            for res_dir in list_dirs_includes.keys().map(|x| x.clone()).collect::<Vec<PathBuf>>() {
                                if has_parent(&path_source, &incl, &res_dir) {
                                    if !deps_list.contains(&res_dir) && res_dir != *dirname {
                                        deps_list.push(res_dir.clone());
                                    }
                                }
                            }
                        }

                        results_depends.insert(dirname.to_path_buf(), deps_list);
                    }

                    for key in results_depends.keys().map(|x| x.clone()).collect::<Vec<PathBuf>>() {
                        if let Some(key_parent) = find_lowest_unique_parent(&path_source, &results_depends.keys().map(|x| x.clone()).collect::<Vec<PathBuf>>(), &key, &path_dest) {
                            if key_parent != key {
                                let all_vals = results_depends[&key].clone();
        
                                if results_depends.contains_key(&key_parent) {
                                    results_depends.get_mut(&key_parent).unwrap().extend_from_slice(&all_vals);
                                } else {
                                    results_depends.insert(key_parent, all_vals);
                                }

                                results_depends.remove(&key);
                            }
                        }
                    }

                    for key in results_depends.keys().map(|x| x.clone()).collect::<Vec<PathBuf>>() {
                        results_depends.get_mut(&key).unwrap().sort();
                        results_depends.get_mut(&key).unwrap().dedup();
                    }

                    if !option_path_absolute {
                        results_depends = remove_dir_context(&results_depends, &path_source);
                        list_dirs_includes = remove_dir_context(&list_dirs_includes, &path_source);

                        path_source = PathBuf::from(path_source.iter().last().unwrap().to_str().unwrap());
                    }

                    let tree = start_tree(&mut results_depends, &path_source);

                    if option_print_dependencies {
                        dep_tree_print(&tree, 0);
                    }

                    if option_print_includes {
                        includes_print(&list_dirs_includes);
                    }

                    if let Some(file_deps_json) = option_dependencies_json {
                        let mut out_f = File::create(file_deps_json).unwrap();
                        out_f.write_all(dep_tree_json(&tree).to_string().as_bytes()).unwrap();
                    }

                    if let Some(file_deps_dot) = option_dependencies_dot {
                        let mut out_f = File::create(file_deps_dot).unwrap();
                        render_dep_tree(&tree, &mut out_f);
                    }

                    if let Some(file_includes_json) = option_includes_json {
                        let mut out_f = File::create(file_includes_json).unwrap();
                        out_f.write_all(includes_json(&list_dirs_includes).to_string().as_bytes()).unwrap();
                    }

                    if let Some(file_includes_dot) = option_includes_dot {
                        let mut out_f = File::create(file_includes_dot).unwrap();
                        render_includes_tree(&list_dirs_includes, &mut out_f);
                    }
                }
            }
        }
    }
}

fn remove_dir_context(tree: &BTreeMap<PathBuf, Vec<PathBuf>>, root: &PathBuf) -> BTreeMap<PathBuf, Vec<PathBuf>> {
    let root_prefix = root.to_string_lossy().to_string() + "/";
    let mut new_map: BTreeMap<PathBuf, Vec<PathBuf>> = BTreeMap::new();

    for (key, values) in tree {
        let key_new = PathBuf::from(key.to_string_lossy().to_string().replacen(&root_prefix, "", 1));
        let mut values_new: Vec<PathBuf> = vec![];
        for val in values {
            values_new.push(PathBuf::from(val.to_string_lossy().to_string().replacen(&root_prefix, "", 1)));
        }
        new_map.insert(key_new, values_new);
    }

    new_map
}

struct DotDepTree {
    keys_list: Vec<String>,
    edges: Vec<(usize, usize)>,
}

fn render_dep_tree<W: Write>(tree: &DepTree, output: &mut W) {
    let dep_keys = tree.get_keys();
    let dep_tree = DotDepTree { keys_list: dep_keys.clone(), edges: tree.get_edges(&dep_keys, None) };

    dot::render(&dep_tree, output).unwrap()
}

impl<'a> dot::Labeller<'a, usize, &'a (usize, usize)> for DotDepTree {
    fn graph_id(&'a self) -> dot::Id<'a> {
        dot::Id::new("kernel_graph").unwrap()
    }

    fn node_id(&'a self, n: &usize) -> dot::Id<'a> {
        dot::Id::new(format!("N{}", n)).unwrap()
    }

    fn node_label(&'a self, n: &usize) -> dot::LabelText<'a> {
        dot::LabelText::LabelStr(Cow::Borrowed(self.keys_list.iter().nth(*n).unwrap()))
    }
}

impl<'a> dot::GraphWalk<'a, usize, &'a (usize, usize)> for DotDepTree {
    fn nodes(&self) -> dot::Nodes<'a, usize> {
        (0..self.keys_list.len()).collect()
    }

    fn edges(&'a self) -> dot::Edges<'a, &'a (usize, usize)> {
        self.edges.iter().collect()
    }

    fn source(&self, e: &&'a (usize, usize)) -> usize { e.0 }

    fn target(&self, e: &&'a (usize, usize)) -> usize { e.1 }
}

impl DepTree {
    fn get_name(&self) -> String {
        match self {
            DepTree::Children((name, _)) => {
                return name.to_string_lossy().to_string();
            },
            DepTree::Childless(name) => {
                return name.to_string_lossy().to_string();
            }
        }
    }

    fn get_keys(&self) -> Vec<String> {
        let mut keys_traverse_list: Vec<String> = vec![];

        match self {
            DepTree::Children((name, children)) => {
                let name_string = name.to_string_lossy().to_string();
                if !keys_traverse_list.contains(&name_string) {
                    keys_traverse_list.push(name_string);
                }

                for child in children {
                    for key_found in child.get_keys() {
                        if !keys_traverse_list.contains(&key_found) {
                            keys_traverse_list.push(key_found);
                        }
                    }
                }
            },
            DepTree::Childless(name) => {
                let name_string = name.to_string_lossy().to_string();
                if !keys_traverse_list.contains(&name_string) {
                    keys_traverse_list.push(name_string);
                }
            }
        }

        keys_traverse_list
    }

    fn get_edges(&self, keys: &Vec<String>, parent_name: Option<String>) -> Vec<(usize, usize)> {
        let mut edges_traverse: Vec<(usize, usize)> = vec![];

        match self {
            DepTree::Children((name, children)) => {
                if let Some(edge_parent) = keys.iter().position(|x| *x == self.get_name()) {
                    if let Some(edge_second_parent) = keys.iter().position(|x| *x == self.get_name()) {
                        let edge_found = (edge_second_parent, edge_parent);
                        if !edges_traverse.contains(&edge_found) && edge_found.0 != edge_found.1 {
                            edges_traverse.push(edge_found);
                        }
                    }

                    for child in children {
                        if let Some(edge_child) = keys.iter().position(|x| *x == child.get_name()) {
                            let edge_found = (edge_parent, edge_child);
                            if !edges_traverse.contains(&edge_found) && edge_found.0 != edge_found.1 {
                                edges_traverse.push(edge_found);
                            }
                            for edge_recurse in child.get_edges(&keys, Some(name.to_string_lossy().to_string())) {
                                if !edges_traverse.contains(&edge_recurse) && edge_recurse.0 != edge_recurse.1 {
                                    edges_traverse.push(edge_recurse);
                                }
                            }
                        }
                    }
                }
            },
            DepTree::Childless(_) => {
                if let Some(found_parent) = parent_name {
                    if let Some(edge_parent) = keys.iter().position(|x| *x == found_parent) {
                        if let Some(edge_child) = keys.iter().position(|x| *x == self.get_name()) {
                            let edge_found = (edge_parent, edge_child);
                            if !edges_traverse.contains(&edge_found) && edge_found.0 != edge_found.1 {
                                edges_traverse.push(edge_found);
                            }
                        }
                    }
                }
            }
        }

        edges_traverse
    }
}

fn tree_find_indep(tree: &BTreeMap<PathBuf, Vec<PathBuf>>) -> Vec<PathBuf> {
    let mut indep: Vec<PathBuf> = vec![];

    for tree_key in tree.keys() {
        let mut found_dep = false;

        for tree_val in tree.values() {
            if !found_dep {
                if tree_val.contains(tree_key) {
                    found_dep = true;
                }
            }
        }

        if !found_dep {
            indep.push(tree_key.clone());
        }
    }

    indep
}

fn start_tree(tree: &mut BTreeMap<PathBuf, Vec<PathBuf>>, root: &PathBuf) -> DepTree {
    tree_add_root(tree, root);
    get_dep_tree(tree, root)
}

fn tree_add_root(tree: &mut BTreeMap<PathBuf, Vec<PathBuf>>, root: &PathBuf) {
    tree.insert(root.clone(), tree_find_indep(tree));
}

struct IncludesTree {
    keys_list: Vec<String>,
    edges: Vec<(usize, usize)>,
}

fn render_includes_tree<W: Write>(tree: &BTreeMap<PathBuf, Vec<PathBuf>>, output: &mut W) {
    let mut incl_keys: Vec<String> = vec![];

    for (key, includes) in tree {
        let key_name = key.to_string_lossy().to_string();

        if !incl_keys.contains(&key_name) {
            incl_keys.push(key_name);
        }

        for incl in includes {
            let incl_name = incl.to_string_lossy().to_string();
            if !incl_keys.contains(&incl_name) {
                incl_keys.push(incl_name);
            }
        }
    }

    let mut incl_edges: Vec<(usize, usize)> = vec![];

    for (key, includes) in tree {
        let key_name = key.to_string_lossy().to_string();
        if let Some(key_pos) = incl_keys.iter().position(|x| *x == key_name) {
            for incl in includes {
                let incl_name = incl.to_string_lossy().to_string();
                if let Some(incl_pos) = incl_keys.iter().position(|x| *x == incl_name) {
                    let incl_edge = (key_pos, incl_pos);
                    if !incl_edges.contains(&incl_edge) && incl_edge.0 != incl_edge.1 {
                        incl_edges.push(incl_edge);
                    }
                }
            }
        }
    }

    let incl_tree = IncludesTree { keys_list: incl_keys, edges: incl_edges };

    dot::render(&incl_tree, output).unwrap()
}

impl<'a> dot::Labeller<'a, usize, &'a (usize, usize)> for IncludesTree {
    fn graph_id(&'a self) -> dot::Id<'a> {
        dot::Id::new("kernel_graph").unwrap()
    }

    fn node_id(&'a self, n: &usize) -> dot::Id<'a> {
        dot::Id::new(format!("N{}", n)).unwrap()
    }

    fn node_label(&'a self, n: &usize) -> dot::LabelText<'a> {
        dot::LabelText::LabelStr(Cow::Borrowed(self.keys_list.iter().nth(*n).unwrap()))
    }
}

impl<'a> dot::GraphWalk<'a, usize, &'a (usize, usize)> for IncludesTree {
    fn nodes(&self) -> dot::Nodes<'a, usize> {
        (0..self.keys_list.len()).collect()
    }

    fn edges(&'a self) -> dot::Edges<'a, &'a (usize, usize)> {
        self.edges.iter().collect()
    }

    fn source(&self, e: &&'a (usize, usize)) -> usize { e.0 }

    fn target(&self, e: &&'a (usize, usize)) -> usize { e.1 }
}

fn includes_print(includes: &BTreeMap<PathBuf, Vec<PathBuf>>) {
    for (name, list) in includes {
        if !list.is_empty() {
            println!("Dir: {}\n -- Includes:", name.display());
            for incl in list {
                println!("  {}", incl.display());
            }
            println!("");
        }
    }
}

fn dep_tree_print(dep_tree: &DepTree, depth: usize) -> Value {
    let mut path_start = "".to_string();

    for _ in 0..depth {
        path_start.push_str("‖");
    }

    let json_tree = json!({"name": "", "children": []});

    match dep_tree {
        DepTree::Children((name, children)) => {
            println!("{}=> {}", path_start, name.to_string_lossy().to_string());
            for child in children {
                dep_tree_print(child, depth+1);
            }
        },
        DepTree::Childless(name) => {
            println!("{}=> {}", path_start, name.to_string_lossy().to_string());
        }
    }

    json_tree
}

fn includes_json(includes: &BTreeMap<PathBuf, Vec<PathBuf>>) -> Value {
    let mut json_list = json!([]);

    for (name, list) in includes {
        let mut json_include = json!({"dir": name.to_string_lossy().to_string(), "includes": []});
        if !list.is_empty() {
            for incl in list {
                json_include["includes"].as_array_mut().unwrap().push(Value::String(incl.to_string_lossy().to_string()));
            }
        }
        json_list.as_array_mut().unwrap().push(json_include);
    }

    json_list
}

fn dep_tree_json(dep_tree: &DepTree) -> Value {
    let mut json_tree = json!({"name": "", "children": []});

    match dep_tree {
        DepTree::Children((name, children)) => {
            json_tree["name"] = Value::String(name.to_string_lossy().to_string());
            for child in children {
                json_tree["children"].as_array_mut().unwrap().push(dep_tree_json(child));
            }
        },
        DepTree::Childless(name) => {
            json_tree["name"] = Value::String(name.to_string_lossy().to_string());
        }
    }

    json_tree
}

fn get_dep_tree(tree: &BTreeMap<PathBuf, Vec<PathBuf>>, root: &PathBuf) -> DepTree {
    let mut output_children: Vec<DepTree> = vec![];

    for (dirname, other_data) in tree {
        if *dirname == *root {
            for dep in other_data {
                output_children.push(get_dep_tree(tree, dep));
            }
        }
    }

    if output_children.len() != 0 {
        return DepTree::Children((root.clone(), output_children));
    }

    DepTree::Childless(root.clone())
}

fn get_path_relative(parent_dir: &PathBuf, path: &PathBuf) -> String {
    let mut path_show = path.display().to_string().replace(&parent_dir.display().to_string(), "");
    if path_show.starts_with("/") {
        path_show = path_show.replacen("/", "", 1);
    }
    path_show
}

fn find_lowest_unique_parent(parent_dir: &PathBuf, tree_keys: &Vec<PathBuf>, element: &PathBuf, dest_path: &PathBuf) -> Option<PathBuf> {
    if tree_keys.contains(&element) {
        if !element.display().to_string().starts_with(&parent_dir.display().to_string()) {
            return None;
        }

        let element_local_str = get_path_relative(&parent_dir, &element);

        let mut element_local = dest_path.clone().join(element_local_str.clone());
        let mut element_local_last = element_local.clone();

        while element_local.exists() == false && element_local != *parent_dir {
            element_local_last = element_local.clone();
            element_local = element_local.parent().unwrap().to_path_buf();
        }

        let element_local_str = get_path_relative(&dest_path, &element_local_last);

        element_local_last = parent_dir.clone().join(element_local_str);

        Some(element_local_last)
    } else {
        None
    }
}

fn has_parent(parent_dir: &PathBuf, element: &PathBuf, parent: &PathBuf) -> bool {
    let mut element_parent = element.clone();

    while element_parent != *parent_dir {
        if element_parent == *parent {
            return true;
        }

        match element_parent.parent() {
            Some(parent_found) => {
                element_parent = parent_found.to_path_buf();
            },
            None => {
                break;
            },
        }
    }

    false
}

fn child_clean_inherited_includes(parent_dir: &PathBuf, tree: &mut BTreeMap<PathBuf, Vec<PathBuf>>, element: &PathBuf, element_child: &PathBuf) -> Option<PathBuf> {
    if tree.get(element).is_some() {
        let tree_copy = tree.clone();

        let mut element_parent = element.parent().unwrap().to_path_buf();
        let mut element_parent_get = tree_copy.get(&element_parent);

        while element_parent_get.is_none() {
            if element_parent == *parent_dir {
                return None;
            }

            element_parent = element_parent.parent().unwrap().to_path_buf();
            element_parent_get = tree_copy.get(&element_parent);
        }

        if let Some(found_parent_attribs) = element_parent_get {
            if let Some(found_child) = tree.get_mut(element_child) {
                found_child.retain(|x| !found_parent_attribs.contains(x))
            }
        }

        if *element_parent == *parent_dir {
            return None;
        }

        return Some(element_parent);
    }

    None
}