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
