Revision: 71749 http://sourceforge.net/p/brlcad/code/71749 Author: starseeker Date: 2018-09-19 16:44:11 +0000 (Wed, 19 Sep 2018) Log Message: ----------- Rework the cyclic path test into a public librt API and expose the test through the GED lint command.
Modified Paths: -------------- brlcad/trunk/include/ged/database.h brlcad/trunk/include/rt/db_fullpath.h brlcad/trunk/src/libged/lint.cpp brlcad/trunk/src/librt/db_fullpath.c brlcad/trunk/src/librt/db_tree.c brlcad/trunk/src/librt/librt_private.h brlcad/trunk/src/librt/search.c brlcad/trunk/src/mged/setup.c Modified: brlcad/trunk/include/ged/database.h =================================================================== --- brlcad/trunk/include/ged/database.h 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/include/ged/database.h 2018-09-19 16:44:11 UTC (rev 71749) @@ -245,11 +245,12 @@ */ GED_EXPORT extern int ged_set_output_script(struct ged *gedp, int argc, const char *argv[]); +/** + * Check database objects for errors + */ +GED_EXPORT extern int ged_lint(struct ged *gedp, int argc, const char *argv[]); - - - __END_DECLS #endif /* GED_DATABASE_H */ Modified: brlcad/trunk/include/rt/db_fullpath.h =================================================================== --- brlcad/trunk/include/rt/db_fullpath.h 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/include/rt/db_fullpath.h 2018-09-19 16:44:11 UTC (rev 71749) @@ -201,7 +201,26 @@ RT_EXPORT extern int db_full_path_search(const struct db_full_path *a, const struct directory *dp); + /** + * Function to test whether a path has a cyclic entry in it. + * + * @param fp [i] Full path to test + * @param lname [i] String to use when checking path (optional). If NULL, use the name of the current directory pointer in fp. + * @param full_check [i] Flag to instruct the cyclic test to check using all directory pointers in fp, not just the lname/current dp test. + * @return 1 if the path is cyclic, 0 if it is not. + * + * By default, only the leaf (or test_name if supplied) will be used to test if + * the path is cyclic. If full_check is set, all object names in the path will + * be checked, as well as lname if set. This more expensive check is not + * necessary if calling code is checking for cyclic paths as paths are being + * built, but is necessary to fully "clear" a db_full_path from an arbitrary + * source. Calling code must use its knowledge of the origins of the full path + * (or lack thereof) to determine how much validation work is needed. + */ +RT_EXPORT extern int db_full_path_cyclic(const struct db_full_path *p, const char *lname, int full_check); + +/** * Build the transformation matrix obtained when traversing the path * to the specified depth. * Modified: brlcad/trunk/src/libged/lint.cpp =================================================================== --- brlcad/trunk/src/libged/lint.cpp 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/src/libged/lint.cpp 2018-09-19 16:44:11 UTC (rev 71749) @@ -74,27 +74,146 @@ } } +/* Because lint is intended to be a deep inspection of the .g looking for problems, + * we need to do this check using the low level tree walk rather than operating on + * a search result set (which has checks to filter out cyclic paths.) */ +HIDDEN void +_ged_cyclic_search_subtree(struct db_full_path *path, int curr_bool, union tree *tp, + void (*traverse_func) (struct db_full_path *path, void *), void *client_data) +{ + struct directory *dp; + struct ged *gedp = (struct ged *)client_data; + int bool_val = curr_bool; + + if (!tp) { + return; + } + + RT_CK_FULL_PATH(path); + RT_CK_TREE(tp); + + switch (tp->tr_op) { + case OP_UNION: + case OP_INTERSECT: + case OP_SUBTRACT: + case OP_XOR: + if (tp->tr_op == OP_UNION) bool_val = 2; + if (tp->tr_op == OP_INTERSECT) bool_val = 3; + if (tp->tr_op == OP_SUBTRACT) bool_val = 4; + _ged_cyclic_search_subtree(path, bool_val, tp->tr_b.tb_right, traverse_func, client_data); + /* fall through */ + case OP_NOT: + case OP_GUARD: + case OP_XNOP: + _ged_cyclic_search_subtree(path, OP_UNION, tp->tr_b.tb_left, traverse_func, client_data); + break; + case OP_DB_LEAF: + if ((dp=db_lookup(gedp->ged_wdbp->dbip, tp->tr_l.tl_name, LOOKUP_QUIET)) == RT_DIR_NULL) { + return; + } else { + /* See if we've got a cyclic path */ + db_add_node_to_full_path(path, dp); + DB_FULL_PATH_SET_CUR_BOOL(path, bool_val); + if (!db_full_path_cyclic(path, NULL, 0)) { + /* Not cyclic - keep going */ + traverse_func(path, client_data); + } else { + /* Cyclic - report it */ + char *path_string = db_path_to_string(path); + bu_vls_printf(gedp->ged_result_str, "%s\n", path_string); + bu_free(path_string, "free path str"); + } + DB_FULL_PATH_POP(path); + break; + } + + default: + bu_log("db_functree_subtree: unrecognized operator %d\n", tp->tr_op); + bu_bomb("db_functree_subtree: unrecognized operator\n"); + } +} + +void +_ged_cyclic_search(struct db_full_path *fp, void *client_data) +{ + struct ged *gedp = (struct ged *)client_data; + struct directory *dp; + + RT_CK_FULL_PATH(fp); + + dp = DB_FULL_PATH_CUR_DIR(fp); + + if (!dp) return; + + /* If we're not looking at a comb object we can't have + * cyclic paths - else, walk the comb */ + if (dp->d_flags & RT_DIR_COMB) { + struct rt_db_internal in; + struct rt_comb_internal *comb; + + if (rt_db_get_internal(&in, dp, gedp->ged_wdbp->dbip, NULL, &rt_uniresource) < 0) return; + + comb = (struct rt_comb_internal *)in.idb_ptr; + _ged_cyclic_search_subtree(fp, OP_UNION, comb->tree, _ged_cyclic_search, client_data); + rt_db_free_internal(&in); + } +} + int -_ged_cyclic_check(struct ged *gedp, int argc, struct directory *dpa) +_ged_cyclic_check(struct ged *gedp, int argc, struct directory **dpa) { + int i; + struct db_full_path *start_path = NULL; int ret = GED_OK; - if (!gedp || argc == 0 || !dpa) return GED_ERROR; + if (!gedp) return GED_ERROR; + if (argc) { + if (!dpa) return GED_ERROR; + BU_GET(start_path, struct db_full_path); + db_full_path_init(start_path); + for (i = 0; i < argc; i++) { + db_add_node_to_full_path(start_path, dpa[i]); + _ged_cyclic_search(start_path, (void *)gedp); + DB_FULL_PATH_POP(start_path); + } + } else { + struct directory *dp; + BU_GET(start_path, struct db_full_path); + db_full_path_init(start_path); + /* We can't do db_ls to get a set of tops objects here, because a cyclic + * path can produce a situation where there are no tops objects and/or + * hide the paths we need to report. */ + for (i = 0; i < RT_DBNHASH; i++) { + for (dp = gedp->ged_wdbp->dbip->dbi_Head[i]; dp != RT_DIR_NULL; dp = dp->d_forw) { + db_add_node_to_full_path(start_path, dp); + _ged_cyclic_search(start_path, (void *)gedp); + DB_FULL_PATH_POP(start_path); + } + } + } + db_free_full_path(start_path); + BU_PUT(start_path, struct db_full_path); return ret; } int -_ged_missing_check(struct ged *gedp, int argc, struct directory *dpa) +_ged_missing_check(struct ged *gedp, int argc, struct directory **dpa) { int ret = GED_OK; - if (!gedp || argc == 0 || !dpa) return GED_ERROR; + if (!gedp) return GED_ERROR; + if (argc) { + if (!dpa) return GED_ERROR; + } return ret; } int -_ged_non_solid_check(struct ged *gedp, int argc, struct directory *dpa) +_ged_non_solid_check(struct ged *gedp, int argc, struct directory **dpa) { int ret = GED_OK; - if (!gedp || argc == 0 || !dpa) return GED_ERROR; + if (!gedp) return GED_ERROR; + if (argc) { + if (!dpa) return GED_ERROR; + } return ret; } @@ -107,7 +226,7 @@ int print_help = 0; struct _ged_lint_opts *opts; struct bu_opt_desc d[6]; - struct directory *dpa; + struct directory **dpa = NULL; int nonexist_obj_cnt = 0; GED_CHECK_DATABASE_OPEN(gedp, GED_ERROR); @@ -131,23 +250,24 @@ /* parse standard options */ argc = bu_opt_parse(NULL, argc, argv, d); - if (print_help || !argc) { + if (print_help) { _ged_cmd_help(gedp, usage, d); - ret = (print_help) ? GED_OK : GED_ERROR; + ret = GED_OK; goto ged_lint_memfree; } - dpa = (struct directory *)bu_calloc(argc+1, sizeof(struct directory *), "dp array"); - nonexist_obj_cnt = _ged_sort_existing_objs(gedp, argc, argv, &dpa); - - if (nonexist_obj_cnt) { - int i; - bu_vls_printf(gedp->ged_result_str, "Object argument(s) supplied to lint that do not exist in the database:\n"); - for (i = argc - nonexist_obj_cnt - 1; i < argc; i++) { - bu_vls_printf(gedp->ged_result_str, " %s\n", argv[i]); + if (argc) { + dpa = (struct directory **)bu_calloc(argc+1, sizeof(struct directory *), "dp array"); + nonexist_obj_cnt = _ged_sort_existing_objs(gedp, argc, argv, dpa); + if (nonexist_obj_cnt) { + int i; + bu_vls_printf(gedp->ged_result_str, "Object argument(s) supplied to lint that do not exist in the database:\n"); + for (i = argc - nonexist_obj_cnt - 1; i < argc; i++) { + bu_vls_printf(gedp->ged_result_str, " %s\n", argv[i]); + } + ret = GED_ERROR; + goto ged_lint_memfree; } - ret = GED_ERROR; - goto ged_lint_memfree; } _ged_lint_opts_verify(opts); Modified: brlcad/trunk/src/librt/db_fullpath.c =================================================================== --- brlcad/trunk/src/librt/db_fullpath.c 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/src/librt/db_fullpath.c 2018-09-19 16:44:11 UTC (rev 71749) @@ -591,15 +591,32 @@ return 0; } +HIDDEN int +cyclic_path(const struct db_full_path *fp, const char *test_name, long int depth) +{ + if (!test_name || !fp || depth < 0) + return 0; + /* Check the path starting at depth to see if we have a match. */ + while (depth >= 0) { + if (BU_STR_EQUAL(test_name, fp->fp_names[depth]->d_namep)) { + return 1; + } + depth--; + } + + /* not cyclic */ + return 0; +} + int -cyclic_path(const struct db_full_path *fp, const char *name) +db_full_path_cyclic(const struct db_full_path *fp, const char *lname, int full_check) { - /* skip the last one added since it is currently being tested. */ long int depth; const char *test_name; + const struct directory *dp; - if (!name || !fp) + if (!fp) return 0; RT_CK_FULL_PATH(fp); @@ -606,23 +623,36 @@ depth = fp->fp_len - 1; - if (name[0] != '\0') { - test_name = name; - } else { - const struct directory *dp = DB_FULL_PATH_CUR_DIR(fp); - if (!dp) - return 0; + if (!full_check) { + if (lname) { + test_name = lname; + } else { + dp = DB_FULL_PATH_CUR_DIR(fp); + if (!dp) + return 0; - test_name = dp->d_namep; + test_name = dp->d_namep; + depth--; + } + + return cyclic_path(fp, test_name, depth); } - /* check the path to see if it is groundhog day */ - while (--depth >= 0) { - if (BU_STR_EQUAL(test_name, fp->fp_names[depth]->d_namep)) { - return 1; - } + /* full_check is set - check everything */ + if (lname) { + if (cyclic_path(fp, lname, depth)) return 1; } + + /* Check each element in the path against all elements + * above it - the first instance of a cycle ends + * the check. */ + while (depth > 0) { + test_name = fp->fp_names[depth]->d_namep; + depth--; + if (cyclic_path(fp, lname, depth)) return 1; + } + /* not cyclic */ return 0; } Modified: brlcad/trunk/src/librt/db_tree.c =================================================================== --- brlcad/trunk/src/librt/db_tree.c 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/src/librt/db_tree.c 2018-09-19 16:44:11 UTC (rev 71749) @@ -899,7 +899,7 @@ } /* protect against cyclic geometry */ - if (cyclic_path(pathp, tp->tr_l.tl_name)) { + if (db_full_path_cyclic(pathp, tp->tr_l.tl_name, 0)) { int depth = pathp->fp_len; bu_log("Detected cyclic reference of %s\nPath stack is:\n", tp->tr_l.tl_name); Modified: brlcad/trunk/src/librt/librt_private.h =================================================================== --- brlcad/trunk/src/librt/librt_private.h 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/src/librt/librt_private.h 2018-09-19 16:44:11 UTC (rev 71749) @@ -112,18 +112,6 @@ extern void rt_plot_cell(const union cutter *cutp, struct rt_shootray_status *ssp, struct bu_list *waiting_segs_hd, struct rt_i *rtip); -/* db_fullpath.c */ - -/** - * Function to test whether a path has a cyclic entry in it. - * - * @param fp [i] Full path to test - * @param name [i] String to use when checking path (optional). If NULL, use the name of the current directory pointer in fp. - * @return 1 if the path is cyclic, 0 if it is not. - */ -extern int cyclic_path(const struct db_full_path *fp, const char *name); - - /* db_diff.c */ /** Modified: brlcad/trunk/src/librt/search.c =================================================================== --- brlcad/trunk/src/librt/search.c 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/src/librt/search.c 2018-09-19 16:44:11 UTC (rev 71749) @@ -196,7 +196,7 @@ db_dup_full_path(newpath, path); /* Insert the path in the bu_ptbl collecting paths */ bu_ptbl_ins(lcd->full_paths, (long *)newpath); - if (!cyclic_path(path, NULL)) { + if (!db_full_path_cyclic(path, NULL, 0)) { /* Keep going */ traverse_func(path, client_data); } else { Modified: brlcad/trunk/src/mged/setup.c =================================================================== --- brlcad/trunk/src/mged/setup.c 2018-09-19 13:46:35 UTC (rev 71748) +++ brlcad/trunk/src/mged/setup.c 2018-09-19 16:44:11 UTC (rev 71749) @@ -200,6 +200,7 @@ {"labelface", f_labelface, GED_FUNC_PTR_NULL}, {"lc", cmd_ged_plain_wrapper, ged_lc}, {"left", f_bv_left, GED_FUNC_PTR_NULL}, + {"lint", cmd_ged_plain_wrapper, ged_lint}, {"listeval", cmd_ged_plain_wrapper, ged_pathsum}, {"lm", cmd_lm, GED_FUNC_PTR_NULL}, {"loadtk", cmd_tk, GED_FUNC_PTR_NULL}, This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. _______________________________________________ BRL-CAD Source Commits mailing list brlcad-commits@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/brlcad-commits