diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c
index 2021187d..46477d0e 100644
--- a/libsepol/cil/src/cil.c
+++ b/libsepol/cil/src/cil.c
@@ -837,7 +837,7 @@ void cil_destroy_data(void **data, enum cil_flavor flavor)
 		cil_destroy_class(*data);
 		break;
 	case CIL_CLASSORDER:
-		cil_destroy_classorder(*data);
+		cil_destroy_ordered(*data);
 		break;
 	case CIL_CLASSPERMISSION:
 		cil_destroy_classpermission(*data);
@@ -934,7 +934,7 @@ void cil_destroy_data(void **data, enum cil_flavor flavor)
 		cil_destroy_aliasactual(*data);
 		break;
 	case CIL_SENSITIVITYORDER:
-		cil_destroy_sensitivityorder(*data);
+		cil_destroy_ordered(*data);
 		break;
 	case CIL_SENSCAT:
 		cil_destroy_senscat(*data);
@@ -952,7 +952,7 @@ void cil_destroy_data(void **data, enum cil_flavor flavor)
 		cil_destroy_aliasactual(*data);
 		break;
 	case CIL_CATORDER:
-		cil_destroy_catorder(*data);
+		cil_destroy_ordered(*data);
 		break;
 	case CIL_LEVEL:
 		cil_destroy_level(*data);
@@ -964,7 +964,7 @@ void cil_destroy_data(void **data, enum cil_flavor flavor)
 		cil_destroy_sid(*data);
 		break;
 	case CIL_SIDORDER:
-		cil_destroy_sidorder(*data);
+		cil_destroy_ordered(*data);
 		break;
 	case CIL_NAME:
 		cil_destroy_name(*data);
@@ -2164,6 +2164,14 @@ void cil_sort_destroy(struct cil_sort **sort)
 	*sort = NULL;
 }
 
+void cil_ordered_init(struct cil_ordered **ordered)
+{
+	*ordered = cil_malloc(sizeof(**ordered));
+	(*ordered)->merged = CIL_FALSE;
+	(*ordered)->strs = NULL;
+	(*ordered)->datums = NULL;
+}
+
 void cil_netifcon_init(struct cil_netifcon **netifcon)
 {
 	*netifcon = cil_malloc(sizeof(**netifcon));
@@ -2281,13 +2289,6 @@ void cil_class_init(struct cil_class **class)
 	(*class)->ordered = CIL_FALSE;
 }
 
-void cil_classorder_init(struct cil_classorder **classorder)
-{
-	*classorder = cil_malloc(sizeof(**classorder));
-
-	(*classorder)->class_list_str = NULL;
-}
-
 void cil_classcommon_init(struct cil_classcommon **classcommon)
 {
 	*classcommon = cil_malloc(sizeof(**classcommon));
@@ -2315,13 +2316,6 @@ void cil_sidcontext_init(struct cil_sidcontext **sidcontext)
 	(*sidcontext)->context = NULL;
 }
 
-void cil_sidorder_init(struct cil_sidorder **sidorder)
-{
-	*sidorder = cil_malloc(sizeof(**sidorder));
-
-	(*sidorder)->sid_list_str = NULL;
-}
-
 void cil_userrole_init(struct cil_userrole **userrole)
 {
 	*userrole = cil_malloc(sizeof(**userrole));
@@ -2877,20 +2871,6 @@ void cil_cat_init(struct cil_cat **cat)
 	(*cat)->value = 0;
 }
 
-void cil_catorder_init(struct cil_catorder **catorder)
-{
-	*catorder = cil_malloc(sizeof(**catorder));
-
-	(*catorder)->cat_list_str = NULL;
-}
-
-void cil_sensorder_init(struct cil_sensorder **sensorder)
-{
-	*sensorder = cil_malloc(sizeof(**sensorder));
-
-	(*sensorder)->sens_list_str = NULL;
-}
-
 void cil_args_init(struct cil_args **args)
 {
 	*args = cil_malloc(sizeof(**args));
diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
index 8976c254..efe1601c 100644
--- a/libsepol/cil/src/cil_build_ast.c
+++ b/libsepol/cil/src/cil_build_ast.c
@@ -186,6 +186,83 @@ static void cil_clear_node(struct cil_tree_node *ast_node)
 	ast_node->flavor = CIL_NONE;
 }
 
+int cil_gen_ordered(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, enum cil_flavor flavor)
+{
+	enum cil_syntax syntax[] = {
+		CIL_SYN_STRING,
+		CIL_SYN_LIST,
+		CIL_SYN_END
+	};
+	size_t syntax_len = sizeof(syntax)/sizeof(*syntax);
+	struct cil_ordered *ordered = NULL;
+	struct cil_list_item *curr = NULL;
+
+	int rc = SEPOL_ERR;
+
+	if (db == NULL || parse_current == NULL || ast_node == NULL) {
+		goto exit;
+	}
+
+	rc = __cil_verify_syntax(parse_current, syntax, syntax_len);
+	if (rc !=  SEPOL_OK) {
+		goto exit;
+	}
+
+	cil_ordered_init(&ordered);
+
+	rc = cil_fill_list(parse_current->next->cl_head, flavor, &ordered->strs);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	cil_list_for_each(curr, ordered->strs) {
+		if (curr->data == CIL_KEY_UNORDERED) {
+			if (flavor == CIL_CLASSORDER) {
+				if (curr == ordered->strs->head && curr->next == NULL) {
+					cil_log(CIL_ERR, "classorder 'unordered' keyword must be followed by one or more class.\n");
+					rc = SEPOL_ERR;
+					goto exit;
+				} else if (curr != ordered->strs->head) {
+					cil_log(CIL_ERR, "classorder can only use 'unordered' keyword as the first item in the list.\n");
+					rc = SEPOL_ERR;
+					goto exit;
+				}
+			} else {
+				cil_log(CIL_ERR, "The 'unordered' keyword can only be used with classorder rules.\n");
+				rc = SEPOL_ERR;
+				goto exit;
+			}
+		}
+	}
+
+	ast_node->data = ordered;
+	ast_node->flavor = flavor;
+
+	return SEPOL_OK;
+
+exit:
+	cil_tree_log(parse_current, CIL_ERR, "Bad ordered declaration");
+	cil_destroy_ordered(ordered);
+	return rc;
+}
+
+void cil_destroy_ordered(struct cil_ordered *ordered)
+{
+	if (ordered == NULL) {
+		return;
+	}
+
+	if (ordered->strs != NULL) {
+		cil_list_destroy(&ordered->strs, CIL_FALSE);
+	}
+	if (ordered->datums != NULL) {
+		cil_list_destroy(&ordered->datums, CIL_FALSE);
+	}
+
+	free(ordered);
+}
+
+
 int cil_gen_block(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, uint16_t is_abstract)
 {
 	enum cil_syntax syntax[] = {
@@ -510,74 +587,6 @@ void cil_destroy_class(struct cil_class *class)
 	free(class);
 }
 
-int cil_gen_classorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node)
-{
-	enum cil_syntax syntax[] = {
-		CIL_SYN_STRING,
-		CIL_SYN_LIST,
-		CIL_SYN_END
-	};
-	size_t syntax_len = sizeof(syntax)/sizeof(*syntax);
-	struct cil_classorder *classorder = NULL;
-	struct cil_list_item *curr = NULL;
-	struct cil_list_item *head = NULL;
-	int rc = SEPOL_ERR;
-
-	if (db == NULL || parse_current == NULL || ast_node == NULL) {
-		goto exit;
-	}
-
-	rc = __cil_verify_syntax(parse_current, syntax, syntax_len);
-	if (rc !=  SEPOL_OK) {
-		goto exit;
-	}
-
-	cil_classorder_init(&classorder);
-
-	rc = cil_fill_list(parse_current->next->cl_head, CIL_CLASSORDER, &classorder->class_list_str);
-	if (rc != SEPOL_OK) {
-		goto exit;
-	}
-
-	head = classorder->class_list_str->head;
-	cil_list_for_each(curr, classorder->class_list_str) {
-		if (curr->data == CIL_KEY_UNORDERED) {
-			if (curr == head && curr->next == NULL) {
-				cil_log(CIL_ERR, "Classorder 'unordered' keyword must be followed by one or more class.\n");
-				rc = SEPOL_ERR;
-				goto exit;
-			} else if (curr != head) {
-				cil_log(CIL_ERR, "Classorder can only use 'unordered' keyword as the first item in the list.\n");
-				rc = SEPOL_ERR;
-				goto exit;
-			}
-		}
-	}
-
-	ast_node->data = classorder;
-	ast_node->flavor = CIL_CLASSORDER;
-
-	return SEPOL_OK;
-
-exit:
-	cil_tree_log(parse_current, CIL_ERR, "Bad classorder declaration");
-	cil_destroy_classorder(classorder);
-	return rc;
-}
-
-void cil_destroy_classorder(struct cil_classorder *classorder)
-{
-	if (classorder == NULL) {
-		return;
-	}
-
-	if (classorder->class_list_str != NULL) {
-		cil_list_destroy(&classorder->class_list_str, 1);
-	}
-
-	free(classorder);
-}
-
 int cil_gen_perm(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, enum cil_flavor flavor, unsigned int *num_perms)
 {
 	char *key = NULL;
@@ -1220,66 +1229,6 @@ void cil_destroy_sidcontext(struct cil_sidcontext *sidcon)
 	free(sidcon);
 }
 
-int cil_gen_sidorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node)
-{
-	enum cil_syntax syntax[] = {
-		CIL_SYN_STRING,
-		CIL_SYN_LIST,
-		CIL_SYN_END
-	};
-	size_t syntax_len = sizeof(syntax)/sizeof(*syntax);
-	struct cil_sidorder *sidorder = NULL;
-	struct cil_list_item *curr = NULL;
-	int rc = SEPOL_ERR;
-
-	if (db == NULL || parse_current == NULL || ast_node == NULL) {
-		goto exit;
-	}
-
-	rc = __cil_verify_syntax(parse_current, syntax, syntax_len);
-	if (rc !=  SEPOL_OK) {
-		goto exit;
-	}
-
-	cil_sidorder_init(&sidorder);
-
-	rc = cil_fill_list(parse_current->next->cl_head, CIL_SIDORDER, &sidorder->sid_list_str);
-	if (rc != SEPOL_OK) {
-		goto exit;
-	}
-
-	cil_list_for_each(curr, sidorder->sid_list_str) {
-		if (curr->data == CIL_KEY_UNORDERED) {
-			cil_log(CIL_ERR, "Sidorder cannot be unordered.\n");
-			rc = SEPOL_ERR;
-			goto exit;
-		}
-	}
-
-	ast_node->data = sidorder;
-	ast_node->flavor = CIL_SIDORDER;
-
-	return SEPOL_OK;
-
-exit:
-	cil_tree_log(parse_current, CIL_ERR, "Bad sidorder declaration");
-	cil_destroy_sidorder(sidorder);
-	return rc;
-}
-
-void cil_destroy_sidorder(struct cil_sidorder *sidorder)
-{
-	if (sidorder == NULL) {
-		return;
-	}
-
-	if (sidorder->sid_list_str != NULL) {
-		cil_list_destroy(&sidorder->sid_list_str, 1);
-	}
-
-	free(sidorder);
-}
-
 int cil_gen_user(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node)
 {
 	enum cil_syntax syntax[] = {
@@ -3699,126 +3648,6 @@ void cil_destroy_catset(struct cil_catset *catset)
 	free(catset);
 }
 
-int cil_gen_catorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node)
-{
-	enum cil_syntax syntax[] = {
-		CIL_SYN_STRING,
-		CIL_SYN_LIST,
-		CIL_SYN_END
-	};
-	size_t syntax_len = sizeof(syntax)/sizeof(*syntax);
-	struct cil_catorder *catorder = NULL;
-	struct cil_list_item *curr = NULL;
-	int rc = SEPOL_ERR;
-
-	if (db == NULL || parse_current == NULL || ast_node == NULL) {
-		goto exit;
-	}
-
-	rc = __cil_verify_syntax(parse_current, syntax, syntax_len);
-	if (rc !=  SEPOL_OK) {
-		goto exit;
-	}
-
-	cil_catorder_init(&catorder);
-
-	rc = cil_fill_list(parse_current->next->cl_head, CIL_CATORDER, &catorder->cat_list_str);
-	if (rc != SEPOL_OK) {
-		goto exit;
-	}
-
-	cil_list_for_each(curr, catorder->cat_list_str) {
-		if (curr->data == CIL_KEY_UNORDERED) {
-			cil_log(CIL_ERR, "Category order cannot be unordered.\n");
-			rc = SEPOL_ERR;
-			goto exit;
-		}
-	}
-
-	ast_node->data = catorder;
-	ast_node->flavor = CIL_CATORDER;
-
-	return SEPOL_OK;
-
-exit:
-	cil_tree_log(parse_current, CIL_ERR, "Bad categoryorder declaration");
-	cil_destroy_catorder(catorder);
-	return rc;
-}
-
-void cil_destroy_catorder(struct cil_catorder *catorder)
-{
-	if (catorder == NULL) {
-		return;
-	}
-
-	if (catorder->cat_list_str != NULL) {
-		cil_list_destroy(&catorder->cat_list_str, 1);
-	}
-
-	free(catorder);
-}
-
-int cil_gen_sensitivityorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node)
-{
-	enum cil_syntax syntax[] = {
-		CIL_SYN_STRING,
-		CIL_SYN_LIST,
-		CIL_SYN_END
-	};
-	size_t syntax_len = sizeof(syntax)/sizeof(*syntax);
-	struct cil_sensorder *sensorder = NULL;
-	struct cil_list_item *curr = NULL;
-	int rc = SEPOL_ERR;
-
-	if (db == NULL || parse_current == NULL || ast_node == NULL) {
-		goto exit;
-	}
-
-	rc = __cil_verify_syntax(parse_current, syntax, syntax_len);
-	if (rc != SEPOL_OK) {
-		goto exit;
-	}
-
-	cil_sensorder_init(&sensorder);
-
-	rc = cil_fill_list(parse_current->next->cl_head, CIL_SENSITIVITYORDER, &sensorder->sens_list_str);
-	if (rc != SEPOL_OK) {
-		goto exit;
-	}
-
-	cil_list_for_each(curr, sensorder->sens_list_str) {
-		if (curr->data == CIL_KEY_UNORDERED) {
-			cil_log(CIL_ERR, "Sensitivity order cannot be unordered.\n");
-			rc = SEPOL_ERR;
-			goto exit;
-		}
-	}
-
-	ast_node->data = sensorder;
-	ast_node->flavor = CIL_SENSITIVITYORDER;
-
-	return SEPOL_OK;
-
-exit:
-	cil_tree_log(parse_current, CIL_ERR, "Bad sensitivityorder declaration");
-	cil_destroy_sensitivityorder(sensorder);
-	return rc;
-}
-
-void cil_destroy_sensitivityorder(struct cil_sensorder *sensorder)
-{
-	if (sensorder == NULL) {
-		return;
-	}
-
-	if (sensorder->sens_list_str != NULL) {
-		cil_list_destroy(&sensorder->sens_list_str, CIL_TRUE);
-	}
-
-	free(sensorder);
-}
-
 int cil_gen_senscat(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node)
 {
 	enum cil_syntax syntax[] = {
@@ -6314,7 +6143,7 @@ static struct cil_tree_node * parse_statement(struct cil_db *db, struct cil_tree
 	} else if (parse_current->data == CIL_KEY_CLASS) {
 		rc = cil_gen_class(db, parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_CLASSORDER) {
-		rc = cil_gen_classorder(db, parse_current, new_ast_node);
+		rc = cil_gen_ordered(db, parse_current, new_ast_node, CIL_CLASSORDER);
 	} else if (parse_current->data == CIL_KEY_MAP_CLASS) {
 		rc = cil_gen_map_class(db, parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_CLASSMAPPING) {
@@ -6332,7 +6161,7 @@ static struct cil_tree_node * parse_statement(struct cil_db *db, struct cil_tree
 	} else if (parse_current->data == CIL_KEY_SIDCONTEXT) {
 		rc = cil_gen_sidcontext(db, parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_SIDORDER) {
-		rc = cil_gen_sidorder(db, parse_current, new_ast_node);
+		rc = cil_gen_ordered(db, parse_current, new_ast_node, CIL_SIDORDER);
 	} else if (parse_current->data == CIL_KEY_USER) {
 		rc = cil_gen_user(db, parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_USERATTRIBUTE) {
@@ -6446,9 +6275,9 @@ static struct cil_tree_node * parse_statement(struct cil_db *db, struct cil_tree
 	} else if (parse_current->data == CIL_KEY_CATSET) {
 		rc = cil_gen_catset(db, parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_CATORDER) {
-		rc = cil_gen_catorder(db, parse_current, new_ast_node);
+		rc = cil_gen_ordered(db, parse_current, new_ast_node, CIL_CATORDER);
 	} else if (parse_current->data == CIL_KEY_SENSITIVITYORDER) {
-		rc = cil_gen_sensitivityorder(db, parse_current, new_ast_node);
+		rc = cil_gen_ordered(db, parse_current, new_ast_node, CIL_SENSITIVITYORDER);
 	} else if (parse_current->data == CIL_KEY_SENSCAT) {
 		rc = cil_gen_senscat(db, parse_current, new_ast_node);
 	} else if (parse_current->data == CIL_KEY_LEVEL) {
diff --git a/libsepol/cil/src/cil_build_ast.h b/libsepol/cil/src/cil_build_ast.h
index aca84b24..96af3c91 100644
--- a/libsepol/cil/src/cil_build_ast.h
+++ b/libsepol/cil/src/cil_build_ast.h
@@ -42,6 +42,8 @@ int cil_add_decl_to_symtab(struct cil_db *db, symtab_t *symtab, hashtab_key_t ke
 int cil_gen_node(struct cil_db *db, struct cil_tree_node *ast_node, struct cil_symtab_datum *datum, hashtab_key_t key, enum cil_sym_index sflavor, enum cil_flavor nflavor);
 int cil_parse_to_list(struct cil_tree_node *parse_cl_head, struct cil_list *ast_cl, enum cil_flavor flavor);
 
+int cil_gen_ordered(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, enum cil_flavor flavor);
+void cil_destroy_ordered(struct cil_ordered *ordered);
 int cil_gen_block(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, uint16_t is_abstract);
 void cil_destroy_block(struct cil_block *block);
 int cil_gen_blockinherit(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
@@ -52,8 +54,6 @@ int cil_gen_in(struct cil_db *db, struct cil_tree_node *parse_current, struct ci
 void cil_destroy_in(struct cil_in *in);
 int cil_gen_class(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
 void cil_destroy_class(struct cil_class *class);
-int cil_gen_classorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
-void cil_destroy_classorder(struct cil_classorder *classorder);
 int cil_gen_perm(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node, enum cil_flavor flavor, unsigned int *num_perms);
 void cil_destroy_perm(struct cil_perm *perm);
 int cil_gen_perm_nodes(struct cil_db *db, struct cil_tree_node *current_perm, struct cil_tree_node *ast_node, enum cil_flavor flavor, unsigned int *num_perms);
@@ -78,8 +78,6 @@ int cil_gen_sid(struct cil_db *db, struct cil_tree_node *parse_current, struct c
 void cil_destroy_sid(struct cil_sid *sid);
 int cil_gen_sidcontext(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
 void cil_destroy_sidcontext(struct cil_sidcontext *sidcon);
-int cil_gen_sidorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
-void cil_destroy_sidorder(struct cil_sidorder *sidorder);
 int cil_gen_user(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
 void cil_destroy_user(struct cil_user *user);
 int cil_gen_userattribute(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
@@ -158,10 +156,6 @@ int cil_gen_category(struct cil_db *db, struct cil_tree_node *parse_current, str
 void cil_destroy_category(struct cil_cat *cat);
 int cil_set_to_list(struct cil_tree_node *parse_current, struct cil_list *ast_cl);
 void cil_destroy_catset(struct cil_catset *catset);
-int cil_gen_catorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
-void cil_destroy_catorder(struct cil_catorder *catorder);
-int cil_gen_sensitivityorder(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
-void cil_destroy_sensitivityorder(struct cil_sensorder *sensorder);
 int cil_gen_senscat(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
 void cil_destroy_senscat(struct cil_senscat *senscat);
 int cil_gen_level(struct cil_db *db, struct cil_tree_node *parse_current, struct cil_tree_node *ast_node);
diff --git a/libsepol/cil/src/cil_copy_ast.c b/libsepol/cil/src/cil_copy_ast.c
index bc972f03..735628df 100644
--- a/libsepol/cil/src/cil_copy_ast.c
+++ b/libsepol/cil/src/cil_copy_ast.c
@@ -97,6 +97,24 @@ static int cil_copy_node(__attribute__((unused)) struct cil_db *db, void *data,
 	return SEPOL_OK;
 }
 
+int cil_copy_ordered(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab)
+{
+	struct cil_ordered *orig = data;
+	struct cil_ordered *new = NULL;
+
+	cil_ordered_init(&new);
+	if (orig->strs != NULL) {
+		cil_copy_list(orig->strs, &new->strs);
+	}
+	if (orig->datums != NULL) {
+		cil_copy_list(orig->datums, &new->datums);
+	}
+
+	*copy = new;
+
+	return SEPOL_OK;
+}
+
 int cil_copy_block(__attribute__((unused)) struct cil_db *db, void *data, void **copy, symtab_t *symtab)
 {
 	struct cil_block *orig = data;
@@ -261,21 +279,6 @@ int cil_copy_class(__attribute__((unused)) struct cil_db *db, void *data, void *
 	return SEPOL_OK;
 }
 
-int cil_copy_classorder(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab)
-{
-	struct cil_classorder *orig = data;
-	struct cil_classorder *new = NULL;
-
-	cil_classorder_init(&new);
-	if (orig->class_list_str != NULL) {
-		cil_copy_list(orig->class_list_str, &new->class_list_str);
-	}
-
-	*copy = new;
-
-	return SEPOL_OK;
-}
-
 int cil_copy_classpermission(__attribute__((unused)) struct cil_db *db, void *data, void **copy, symtab_t *symtab)
 {
 	struct cil_classpermission *orig = data;
@@ -368,21 +371,6 @@ int cil_copy_sidcontext(struct cil_db *db, void *data, void **copy, __attribute_
 	return SEPOL_OK;
 }
 
-int cil_copy_sidorder(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab)
-{
-	struct cil_sidorder *orig = data;
-	struct cil_sidorder *new = NULL;
-
-	cil_sidorder_init(&new);
-	if (orig->sid_list_str != NULL) {
-		cil_copy_list(orig->sid_list_str, &new->sid_list_str);
-	}
-
-	*copy = new;
-
-	return SEPOL_OK;
-}
-
 int cil_copy_user(__attribute__((unused)) struct cil_db *db, void *data, void **copy, symtab_t *symtab)
 {
 	struct cil_user *orig = data;
@@ -969,36 +957,6 @@ int cil_copy_senscat(struct cil_db *db, void *data, void **copy, __attribute__((
 	return SEPOL_OK;
 }
 
-int cil_copy_catorder(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab)
-{
-	struct cil_catorder *orig = data;
-	struct cil_catorder *new = NULL;
-
-	cil_catorder_init(&new);
-	if (orig->cat_list_str != NULL) {
-		cil_copy_list(orig->cat_list_str, &new->cat_list_str);
-	}
-
-	*copy = new;
-
-	return SEPOL_OK;
-}
-
-int cil_copy_sensitivityorder(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab)
-{
-	struct cil_sensorder *orig = data;
-	struct cil_sensorder *new = NULL;
-
-	cil_sensorder_init(&new);
-	if (orig->sens_list_str != NULL) {
-		cil_copy_list(orig->sens_list_str, &new->sens_list_str);
-	}
-
-	*copy = new;
-
-	return SEPOL_OK;
-}
-
 void cil_copy_fill_level(struct cil_db *db, struct cil_level *orig, struct cil_level **new)
 {
 	cil_level_init(new);
@@ -1768,7 +1726,7 @@ static int __cil_copy_node_helper(struct cil_tree_node *orig, uint32_t *finished
 		copy_func = &cil_copy_class;
 		break;
 	case CIL_CLASSORDER:
-		copy_func = &cil_copy_classorder;
+		copy_func = &cil_copy_ordered;
 		break;
 	case CIL_CLASSPERMISSION:
 		copy_func = &cil_copy_classpermission;
@@ -1786,7 +1744,7 @@ static int __cil_copy_node_helper(struct cil_tree_node *orig, uint32_t *finished
 		copy_func = &cil_copy_sidcontext;
 		break;
 	case CIL_SIDORDER:
-		copy_func = &cil_copy_sidorder;
+		copy_func = &cil_copy_ordered;
 		break;
 	case CIL_USER:
 		copy_func = &cil_copy_user;
@@ -1907,10 +1865,10 @@ static int __cil_copy_node_helper(struct cil_tree_node *orig, uint32_t *finished
 		copy_func = &cil_copy_senscat;
 		break;
 	case CIL_CATORDER:
-		copy_func = &cil_copy_catorder;
+		copy_func = &cil_copy_ordered;
 		break;
 	case CIL_SENSITIVITYORDER:
-		copy_func = &cil_copy_sensitivityorder;
+		copy_func = &cil_copy_ordered;
 		break;
 	case CIL_LEVEL:
 		copy_func = &cil_copy_level;
diff --git a/libsepol/cil/src/cil_copy_ast.h b/libsepol/cil/src/cil_copy_ast.h
index 9f695ec5..9e6be5ac 100644
--- a/libsepol/cil/src/cil_copy_ast.h
+++ b/libsepol/cil/src/cil_copy_ast.h
@@ -37,12 +37,12 @@
 void cil_copy_list(struct cil_list *orig, struct cil_list **copy);
 int cil_copy_expr(struct cil_db *db, struct cil_list *orig, struct cil_list **new);
 
+int cil_copy_ordered(__attribute__((unused)) struct cil_db *db, void *data, void **copy, __attribute__((unused)) symtab_t *symtab);
 int cil_copy_block(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_blockabstract(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_blockinherit(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_perm(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_class(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
-int cil_copy_classorder(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_classmapping(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_permset(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 
@@ -55,7 +55,6 @@ int cil_copy_common(struct cil_db *db, void *data, void **copy, symtab_t *symtab
 int cil_copy_classcommon(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_sid(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_sidcontext(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
-int cil_copy_sidorder(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_user(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_userattribute(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_userattributeset(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
@@ -88,8 +87,6 @@ int cil_copy_cat(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_catalias(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_catset(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 int cil_copy_senscat(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
-int cil_copy_catorder(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
-int cil_copy_sensitivityorder(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 void cil_copy_fill_level(struct cil_db *db, struct cil_level *orig, struct cil_level **new);
 int cil_copy_level(struct cil_db *db, void *data, void **copy, symtab_t *symtab);
 void cil_copy_fill_levelrange(struct cil_db *db, struct cil_levelrange *orig, struct cil_levelrange *new);
diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h
index 9e492cb9..013483c9 100644
--- a/libsepol/cil/src/cil_internal.h
+++ b/libsepol/cil/src/cil_internal.h
@@ -347,6 +347,12 @@ struct cil_sort {
 	void **array;
 };
 
+struct cil_ordered {
+	int merged;
+	struct cil_list *strs;
+	struct cil_list *datums;
+};
+
 struct cil_block {
 	struct cil_symtab_datum datum;
 	symtab_t symtab[CIL_SYM_NUM];
@@ -387,10 +393,6 @@ struct cil_class {
 	uint32_t ordered; /* Only used for kernel class */
 };
 
-struct cil_classorder {
-	struct cil_list *class_list_str;
-};
-
 struct cil_classperms_set {
 	char *set_str;
 	struct cil_classpermission *set;
@@ -446,10 +448,6 @@ struct cil_sidcontext {
 	struct cil_context *context;
 };
 
-struct cil_sidorder {
-	struct cil_list *sid_list_str;
-};
-
 struct cil_user {
 	struct cil_symtab_datum datum;
 	struct cil_user *bounds;
@@ -685,10 +683,6 @@ struct cil_sens {
 	uint32_t ordered;
 };
 
-struct cil_sensorder {
-	struct cil_list *sens_list_str;
-};
-
 struct cil_cat {
 	struct cil_symtab_datum datum;
 	uint32_t ordered;
@@ -706,10 +700,6 @@ struct cil_catset {
 	struct cil_cats *cats;
 };
 
-struct cil_catorder {
-	struct cil_list *cat_list_str;
-};
-
 struct cil_senscat {
 	char *sens_str;
 	struct cil_cats *cats;
@@ -1012,6 +1002,7 @@ int cil_string_to_uint64(const char *string, uint64_t *value, int base);
 
 void cil_sort_init(struct cil_sort **sort);
 void cil_sort_destroy(struct cil_sort **sort);
+void cil_ordered_init(struct cil_ordered **ordered);
 void cil_netifcon_init(struct cil_netifcon **netifcon);
 void cil_ibendportcon_init(struct cil_ibendportcon **ibendportcon);
 void cil_context_init(struct cil_context **context);
@@ -1023,11 +1014,9 @@ void cil_blockinherit_init(struct cil_blockinherit **inherit);
 void cil_blockabstract_init(struct cil_blockabstract **abstract);
 void cil_in_init(struct cil_in **in);
 void cil_class_init(struct cil_class **class);
-void cil_classorder_init(struct cil_classorder **classorder);
 void cil_classcommon_init(struct cil_classcommon **classcommon);
 void cil_sid_init(struct cil_sid **sid);
 void cil_sidcontext_init(struct cil_sidcontext **sidcontext);
-void cil_sidorder_init(struct cil_sidorder **sidorder);
 void cil_userrole_init(struct cil_userrole **userrole);
 void cil_userprefix_init(struct cil_userprefix **userprefix);
 void cil_selinuxuser_init(struct cil_selinuxuser **selinuxuser);
@@ -1083,8 +1072,6 @@ void cil_userrange_init(struct cil_userrange **userrange);
 void cil_role_init(struct cil_role **role);
 void cil_type_init(struct cil_type **type);
 void cil_cat_init(struct cil_cat **cat);
-void cil_catorder_init(struct cil_catorder **catorder);
-void cil_sensorder_init(struct cil_sensorder **sensorder);
 void cil_args_init(struct cil_args **args);
 void cil_call_init(struct cil_call **call);
 void cil_optional_init(struct cil_optional **optional);
diff --git a/libsepol/cil/src/cil_reset_ast.c b/libsepol/cil/src/cil_reset_ast.c
index 9069317e..fa312c6f 100644
--- a/libsepol/cil/src/cil_reset_ast.c
+++ b/libsepol/cil/src/cil_reset_ast.c
@@ -11,6 +11,12 @@ static inline void cil_reset_levelrange(struct cil_levelrange *levelrange);
 static inline void cil_reset_context(struct cil_context *context);
 
 
+static void cil_reset_ordered(struct cil_ordered *ordered)
+{
+	ordered->merged = CIL_FALSE;
+	cil_list_destroy(&ordered->datums, CIL_FALSE);
+}
+
 static int __class_reset_perm_values(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, void *args)
 {
 	struct cil_perm *perm = (struct cil_perm *)d;
@@ -638,14 +644,16 @@ static int __cil_reset_node(struct cil_tree_node *node,  __attribute__((unused))
 	case CIL_BOOLEANIF:
 		cil_reset_booleanif(node->data);
 		break;
-	case CIL_TUNABLEIF:
-	case CIL_CALL:
-		break; /* Not effected by optional block disabling */
-	case CIL_MACRO:
 	case CIL_SIDORDER:
 	case CIL_CLASSORDER:
 	case CIL_CATORDER:
 	case CIL_SENSITIVITYORDER:
+		cil_reset_ordered(node->data);
+		break;
+	case CIL_TUNABLEIF:
+	case CIL_CALL:
+		break; /* Not effected by optional block disabling */
+	case CIL_MACRO:
 		break; /* Nothing to reset */
 	default:
 		break;
diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c
index 595bd2b9..0172bbdd 100644
--- a/libsepol/cil/src/cil_resolve_ast.c
+++ b/libsepol/cil/src/cil_resolve_ast.c
@@ -1213,55 +1213,6 @@ exit:
 	return rc;
 }
 
-struct cil_ordered_list {
-	int merged;
-	struct cil_list *list;
-	struct cil_tree_node *node;
-};
-
-static void __cil_ordered_list_init(struct cil_ordered_list **ordered)
-{
-	*ordered = cil_malloc(sizeof(**ordered));
-
-	(*ordered)->merged = CIL_FALSE;
-	(*ordered)->list = NULL;
-	(*ordered)->node = NULL;
-}
-
-static void __cil_ordered_list_destroy(struct cil_ordered_list **ordered)
-{
-	cil_list_destroy(&(*ordered)->list, CIL_FALSE);
-	(*ordered)->node = NULL;
-	free(*ordered);
-	*ordered = NULL;
-}
-
-static void __cil_ordered_lists_destroy(struct cil_list **ordered_lists)
-{
-	struct cil_list_item *item = NULL;
-
-	if (ordered_lists == NULL || *ordered_lists == NULL) {
-		return;
-	}
-
-	item = (*ordered_lists)->head;
-	while (item != NULL) {
-		struct cil_list_item *next = item->next;
-		struct cil_ordered_list *ordered = item->data;
-		__cil_ordered_list_destroy(&ordered);
-		free(item);
-		item = next;
-	}
-	free(*ordered_lists);
-	*ordered_lists = NULL;
-}
-
-static void __cil_ordered_lists_reset(struct cil_list **ordered_lists)
-{
-	__cil_ordered_lists_destroy(ordered_lists);
-	cil_list_init(ordered_lists, CIL_LIST_ITEM);
-}
-
 static struct cil_list_item *__cil_ordered_item_insert(struct cil_list *old, struct cil_list_item *curr, struct cil_list_item *item)
 {
 	if (item->flavor == CIL_SID) {
@@ -1310,24 +1261,30 @@ static int __cil_ordered_list_insert(struct cil_list *old, struct cil_list_item
 	return SEPOL_OK;
 }
 
-static struct cil_list_item *__cil_ordered_find_match(struct cil_list_item *t, struct cil_list_item *i)
+static void __cil_ordered_find_next_match(struct cil_list_item **i, struct cil_list_item **j, struct cil_list_item **p)
 {
-	while (i) {
-		if (i->data == t->data) {
-			return i;
+	struct cil_list_item *pstart = *p;
+	struct cil_list_item *jstart = *j;
+
+	while (*i) {
+		*p = pstart;
+		*j = jstart;
+		while (*j) {
+			if ((*i)->data == (*j)->data) {
+				return;
+			}
+			*p = *j;
+			*j = (*j)->next;
 		}
-		i = i->next;
+		*i = (*i)->next;
 	}
-	return NULL;
 }
 
 static int __cil_ordered_lists_merge(struct cil_list *old, struct cil_list *new)
 {
-	struct cil_list_item *omatch = NULL;
 	struct cil_list_item *ofirst = old->head;
 	struct cil_list_item *ocurr = NULL;
 	struct cil_list_item *oprev = NULL;
-	struct cil_list_item *nmatch = NULL;
 	struct cil_list_item *nfirst = new->head;
 	struct cil_list_item *ncurr = NULL;
 	int rc = SEPOL_ERR;
@@ -1338,75 +1295,41 @@ static int __cil_ordered_lists_merge(struct cil_list *old, struct cil_list *new)
 
 	if (ofirst == NULL) {
 		/* First list added */
-		rc = __cil_ordered_list_insert(old, NULL, nfirst, NULL);
-		return rc;
+		return __cil_ordered_list_insert(old, NULL, nfirst, NULL);
 	}
 
-	/* Find a match between the new list and the old one */
-	for (nmatch = nfirst; nmatch; nmatch = nmatch->next) {
-		omatch = __cil_ordered_find_match(nmatch, ofirst);
-		if (omatch) {
+	ncurr = nfirst;
+	ocurr = ofirst;
+	oprev = NULL;
+	while (ncurr && ocurr) {
+		__cil_ordered_find_next_match(&ncurr, &ocurr, &oprev);
+		if (!ncurr || !ocurr) {
 			break;
 		}
-	}
-
-	if (!nmatch) {
-		/* List cannot be merged yet */
-		return SEPOL_ERR;
-	}
-
-	if (nmatch != nfirst && omatch != ofirst) {
-		/* Potential ordering conflict--try again later */
-		return SEPOL_ERR;
-	}
-
-	if (nmatch != nfirst) {
-		/* Prepend the beginning of the new list up to the first match to the old list */
-		rc = __cil_ordered_list_insert(old, NULL, nfirst, nmatch);
-		if (rc != SEPOL_OK) {
-			return rc;
+		if (ncurr != nfirst) {
+			rc = __cil_ordered_list_insert(old, oprev, nfirst, ncurr);
+			if (rc != SEPOL_OK) {
+				return rc;
+			}
 		}
+		ncurr = ncurr->next;
+		nfirst = ncurr;
+		oprev = ocurr;
+		ocurr = ocurr->next;
 	}
 
-	/* In the overlapping protion, add items from the new list not in the old list */
-	ncurr = nmatch->next;
-	ocurr = omatch->next;
-	oprev = omatch;
-	while (ncurr && ocurr) {
-		if (ncurr->data == ocurr->data) {
-			oprev = ocurr;
-			ocurr = ocurr->next;
-			ncurr = ncurr->next;
+	if (!ncurr) {
+		if (!nfirst) {
+			/* Done */
+			return SEPOL_OK;
 		} else {
-			/* Handle gap in old: old = (A C)  new = (A B C) */
-			nmatch = __cil_ordered_find_match(ocurr, ncurr->next);
-			if (nmatch) {
-				rc = __cil_ordered_list_insert(old, oprev, ncurr, nmatch);
-				if (rc != SEPOL_OK) {
-					return rc;
-				}
-				oprev = ocurr;
-				ocurr = ocurr->next;
-				ncurr = nmatch->next;
-				continue;
-			}
-			/* Handle gap in new: old = (A B C)  new = (A C) */
-			omatch = __cil_ordered_find_match(ncurr, ocurr->next);
-			if (omatch) {
-				/* Nothing to insert, just skip */
-				oprev = omatch;
-				ocurr = omatch->next;
-				ncurr = ncurr->next;
-				continue;
-			} else {
-				return SEPOL_ERR;
-			}
+			/* Can't merge yet */
+			return SEPOL_ERR;
 		}
 	}
 
-	if (ncurr) {
-		/* Add the rest of the items from the new list */
-		rc = __cil_ordered_list_insert(old, old->tail, ncurr, NULL);
+	if (ncurr && !ocurr) { /* some remaining */
+		rc = __cil_ordered_list_insert(old, oprev, ncurr, NULL);
 		if (rc != SEPOL_OK) {
 			return rc;
 		}
@@ -1415,18 +1338,19 @@ static int __cil_ordered_lists_merge(struct cil_list *old, struct cil_list *new)
 	return SEPOL_OK;
 }
 
-static int insert_unordered(struct cil_list *merged, struct cil_list *unordered)
+static int insert_unordered(struct cil_list *merged, struct cil_list *unordered_list)
 {
+	struct cil_tree_node *node;
+	struct cil_ordered *unordered;
 	struct cil_list_item *curr = NULL;
-	struct cil_ordered_list *unordered_list = NULL;
 	struct cil_list_item *item = NULL;
 	struct cil_list_item *ret = NULL;
 	int rc = SEPOL_ERR;
 
-	cil_list_for_each(curr, unordered) {
-		unordered_list = curr->data;
-
-		cil_list_for_each(item, unordered_list->list) {
+	cil_list_for_each(curr, unordered_list) {
+		node = curr->data;
+		unordered = node->data;
+		cil_list_for_each(item, unordered->datums) {
 			if (cil_list_contains(merged, item->data)) {
 				/* item was declared in an ordered statement, which supersedes
 				 * all unordered statements */
@@ -1453,40 +1377,50 @@ exit:
 static struct cil_list *__cil_ordered_lists_merge_all(struct cil_list **ordered_lists, struct cil_list **unordered_lists)
 {
 	struct cil_list *composite = NULL;
+	struct cil_tree_node *node;
+	struct cil_ordered *ordered;
 	struct cil_list_item *curr = NULL;
 	int changed = CIL_TRUE;
 	int waiting = 1;
 	int rc = SEPOL_ERR;
 
-	cil_list_init(&composite, CIL_LIST_ITEM);
+	cil_list_init(&composite, (*ordered_lists)->flavor);
 
 	while (waiting && changed == CIL_TRUE) {
 		changed = CIL_FALSE;
 		waiting = 0;
 		cil_list_for_each(curr, *ordered_lists) {
-			struct cil_ordered_list *ordered_list = curr->data;
-			if (ordered_list->merged == CIL_FALSE) {
-				rc = __cil_ordered_lists_merge(composite, ordered_list->list);
+			node = curr->data;
+			ordered = node->data;
+			if (ordered->merged == CIL_FALSE) {
+				rc = __cil_ordered_lists_merge(composite, ordered->datums);
 				if (rc != SEPOL_OK) {
 					/* Can't merge yet */
 					waiting++;
 				} else {
-					ordered_list->merged = CIL_TRUE;
+					ordered->merged = CIL_TRUE;
 					changed = CIL_TRUE;
 				}
 			}
 		}
 		if (waiting > 0 && changed == CIL_FALSE) {
 			cil_list_for_each(curr, *ordered_lists) {
-				struct cil_ordered_list *ordered_list = curr->data;
-				if (ordered_list->merged == CIL_FALSE) {
-					cil_tree_log(ordered_list->node, CIL_ERR, "Unable to merge ordered list");
+				node = curr->data;
+				ordered = node->data;
+				if (ordered->merged == CIL_FALSE) {
+					cil_tree_log(node, CIL_ERR, "Unable to merge ordered list");
 				}
 			}
 			goto exit;
 		}
 	}
 
+	rc = cil_verify_completed_ordered_list(composite, *ordered_lists);
+	if (rc != SEPOL_OK) {
+		cil_log(CIL_ERR, "Unable to validate ordering\n");
+		goto exit;
+	}
+
 	if (unordered_lists != NULL) {
 		rc = insert_unordered(composite, *unordered_lists);
 		if (rc != SEPOL_OK) {
@@ -1494,31 +1428,24 @@ static struct cil_list *__cil_ordered_lists_merge_all(struct cil_list **ordered_
 		}
 	}
 
-	__cil_ordered_lists_destroy(ordered_lists);
-	__cil_ordered_lists_destroy(unordered_lists);
-
 	return composite;
 
 exit:
-	__cil_ordered_lists_destroy(ordered_lists);
-	__cil_ordered_lists_destroy(unordered_lists);
 	cil_list_destroy(&composite, CIL_FALSE);
 	return NULL;
 }
 
 int cil_resolve_classorder(struct cil_tree_node *current, struct cil_db *db, struct cil_list *classorder_list, struct cil_list *unordered_classorder_list)
 {
-	struct cil_classorder *classorder = current->data;
-	struct cil_list *new = NULL;
+	struct cil_ordered *ordered = current->data;
 	struct cil_list_item *curr = NULL;
 	struct cil_symtab_datum *datum = NULL;
-	struct cil_ordered_list *class_list = NULL;
 	int rc = SEPOL_ERR;
 	int unordered = CIL_FALSE;
 
-	cil_list_init(&new, CIL_CLASSORDER);
+	cil_list_init(&ordered->datums, CIL_DATUM);
 
-	cil_list_for_each(curr, classorder->class_list_str) {
+	cil_list_for_each(curr, ordered->strs) {
 		if (curr->data == CIL_KEY_UNORDERED) {
 			unordered = CIL_TRUE;
 			continue;
@@ -1535,37 +1462,32 @@ int cil_resolve_classorder(struct cil_tree_node *current, struct cil_db *db, str
 			rc = SEPOL_ERR;
 			goto exit;
 		}
-		cil_list_append(new, CIL_CLASS, datum);
+		cil_list_append(ordered->datums, CIL_CLASS, datum);
 	}
 
-	__cil_ordered_list_init(&class_list);
-	class_list->list = new;
-	class_list->node = current;
 	if (unordered) {
-		cil_list_append(unordered_classorder_list, CIL_CLASSORDER, class_list);
+		cil_list_append(unordered_classorder_list, CIL_CLASSORDER, current);
 	} else {
-		cil_list_append(classorder_list, CIL_CLASSORDER, class_list);
+		cil_list_append(classorder_list, CIL_CLASSORDER, current);
 	}
 
 	return SEPOL_OK;
 
 exit:
-	cil_list_destroy(&new, CIL_FALSE);
+	cil_list_destroy(&ordered->datums, CIL_FALSE);
 	return rc;
 }
 
 int cil_resolve_sidorder(struct cil_tree_node *current, struct cil_db *db, struct cil_list *sidorder_list)
 {
-	struct cil_sidorder *sidorder = current->data;
-	struct cil_list *new = NULL;
+	struct cil_ordered *ordered = current->data;
 	struct cil_list_item *curr = NULL;
 	struct cil_symtab_datum *datum = NULL;
-	struct cil_ordered_list *ordered = NULL;
 	int rc = SEPOL_ERR;
 
-	cil_list_init(&new, CIL_SIDORDER);
+	cil_list_init(&ordered->datums, CIL_DATUM);
 
-	cil_list_for_each(curr, sidorder->sid_list_str) {
+	cil_list_for_each(curr, ordered->strs) {
 		rc = cil_resolve_name(current, (char *)curr->data, CIL_SYM_SIDS, db, &datum);
 		if (rc != SEPOL_OK) {
 			cil_log(CIL_ERR, "Failed to resolve sid %s in sidorder\n", (char *)curr->data);
@@ -1577,18 +1499,15 @@ int cil_resolve_sidorder(struct cil_tree_node *current, struct cil_db *db, struc
 			goto exit;
 		}
 
-		cil_list_append(new, CIL_SID, datum);
+		cil_list_append(ordered->datums, CIL_SID, datum);
 	}
 
-	__cil_ordered_list_init(&ordered);
-	ordered->list = new;
-	ordered->node = current;
-	cil_list_append(sidorder_list, CIL_SIDORDER, ordered);
+	cil_list_append(sidorder_list, CIL_SIDORDER, current);
 
 	return SEPOL_OK;
 
 exit:
-	cil_list_destroy(&new, CIL_FALSE);
+	cil_list_destroy(&ordered->datums, CIL_FALSE);
 	return rc;
 }
 
@@ -1608,57 +1527,47 @@ static void cil_set_cat_values(struct cil_list *ordered_cats, struct cil_db *db)
 
 int cil_resolve_catorder(struct cil_tree_node *current, struct cil_db *db, struct cil_list *catorder_list)
 {
-	struct cil_catorder *catorder = current->data;
-	struct cil_list *new = NULL;
+	struct cil_ordered *ordered = current->data;
 	struct cil_list_item *curr = NULL;
-	struct cil_symtab_datum *cat_datum;
-	struct cil_cat *cat = NULL;
-	struct cil_ordered_list *ordered = NULL;
+	struct cil_symtab_datum *datum;
 	int rc = SEPOL_ERR;
 
-	cil_list_init(&new, CIL_CATORDER);
+	cil_list_init(&ordered->datums, CIL_DATUM);
 
-	cil_list_for_each(curr, catorder->cat_list_str) {
-		struct cil_tree_node *node = NULL;
-		rc = cil_resolve_name(current, (char *)curr->data, CIL_SYM_CATS, db, &cat_datum);
+	cil_list_for_each(curr, ordered->strs) {
+		rc = cil_resolve_name(current, (char *)curr->data, CIL_SYM_CATS, db, &datum);
 		if (rc != SEPOL_OK) {
 			cil_log(CIL_ERR, "Failed to resolve category %s in categoryorder\n", (char *)curr->data);
 			goto exit;
 		}
-		node = NODE(cat_datum);
-		if (node->flavor != CIL_CAT) {
-			cil_log(CIL_ERR, "%s is not a category. Only categories are allowed in categoryorder statements\n", cat_datum->name);
+		if (FLAVOR(datum) != CIL_CAT) {
+			cil_log(CIL_ERR, "%s is not a category. Only categories are allowed in categoryorder statements\n", datum->name);
 			rc = SEPOL_ERR;
 			goto exit;
 		}
-		cat = (struct cil_cat *)cat_datum;
-		cil_list_append(new, CIL_CAT, cat);
+
+		cil_list_append(ordered->datums, CIL_CAT, datum);
 	}
 
-	__cil_ordered_list_init(&ordered);
-	ordered->list = new;
-	ordered->node = current;
-	cil_list_append(catorder_list, CIL_CATORDER, ordered);
+	cil_list_append(catorder_list, CIL_CATORDER, current);
 
 	return SEPOL_OK;
 
 exit:
-	cil_list_destroy(&new, CIL_FALSE);
+	cil_list_destroy(&ordered->datums, CIL_FALSE);
 	return rc;
 }
 
 int cil_resolve_sensitivityorder(struct cil_tree_node *current, struct cil_db *db, struct cil_list *sensitivityorder_list)
 {
-	struct cil_sensorder *sensorder = current->data;
-	struct cil_list *new = NULL;
+	struct cil_ordered *ordered = current->data;
 	struct cil_list_item *curr = NULL;
 	struct cil_symtab_datum *datum = NULL;
-	struct cil_ordered_list *ordered = NULL;
 	int rc = SEPOL_ERR;
 
-	cil_list_init(&new, CIL_LIST_ITEM);
+	cil_list_init(&ordered->datums, CIL_DATUM);
 
-	cil_list_for_each(curr, sensorder->sens_list_str) {
+	cil_list_for_each(curr, ordered->strs) {
 		rc = cil_resolve_name(current, (char *)curr->data, CIL_SYM_SENS, db, &datum);
 		if (rc != SEPOL_OK) {
 			cil_log(CIL_ERR, "Failed to resolve sensitivity %s in sensitivityorder\n", (char *)curr->data);
@@ -1669,18 +1578,15 @@ int cil_resolve_sensitivityorder(struct cil_tree_node *current, struct cil_db *d
 			rc = SEPOL_ERR;
 			goto exit;
 		}
-		cil_list_append(new, CIL_SENS, datum);
+		cil_list_append(ordered->datums, CIL_SENS, datum);
 	}
 
-	__cil_ordered_list_init(&ordered);
-	ordered->list = new;
-	ordered->node = current;
-	cil_list_append(sensitivityorder_list, CIL_SENSITIVITYORDER, ordered);
+	cil_list_append(sensitivityorder_list, CIL_SENSITIVITYORDER, current);
 
 	return SEPOL_OK;
 
 exit:
-	cil_list_destroy(&new, CIL_FALSE);
+	cil_list_destroy(&ordered->datums, CIL_FALSE);
 	return rc;
 }
 
@@ -4115,11 +4021,11 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current)
 	extra_args.abstract_blocks = NULL;
 
 	cil_list_init(&extra_args.to_destroy, CIL_NODE);
-	cil_list_init(&extra_args.sidorder_lists, CIL_LIST_ITEM);
-	cil_list_init(&extra_args.classorder_lists, CIL_LIST_ITEM);
-	cil_list_init(&extra_args.unordered_classorder_lists, CIL_LIST_ITEM);
-	cil_list_init(&extra_args.catorder_lists, CIL_LIST_ITEM);
-	cil_list_init(&extra_args.sensitivityorder_lists, CIL_LIST_ITEM);
+	cil_list_init(&extra_args.sidorder_lists, CIL_SIDORDER);
+	cil_list_init(&extra_args.classorder_lists, CIL_CLASSORDER);
+	cil_list_init(&extra_args.unordered_classorder_lists, CIL_CLASSORDER);
+	cil_list_init(&extra_args.catorder_lists, CIL_CATORDER);
+	cil_list_init(&extra_args.sensitivityorder_lists, CIL_SENSITIVITYORDER);
 	cil_list_init(&extra_args.in_list_before, CIL_IN);
 	cil_list_init(&extra_args.in_list_after, CIL_IN);
 	cil_list_init(&extra_args.abstract_blocks, CIL_NODE);
@@ -4227,11 +4133,16 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current)
 					cil_log(CIL_INFO, "Resetting declarations\n");
 
 					if (pass >= CIL_PASS_MISC1) {
-						__cil_ordered_lists_reset(&extra_args.sidorder_lists);
-						__cil_ordered_lists_reset(&extra_args.classorder_lists);
-						__cil_ordered_lists_reset(&extra_args.unordered_classorder_lists);
-						__cil_ordered_lists_reset(&extra_args.catorder_lists);
-						__cil_ordered_lists_reset(&extra_args.sensitivityorder_lists);
+						cil_list_destroy(&extra_args.sidorder_lists, CIL_FALSE);
+						cil_list_destroy(&extra_args.classorder_lists, CIL_FALSE);
+						cil_list_destroy(&extra_args.catorder_lists, CIL_FALSE);
+						cil_list_destroy(&extra_args.sensitivityorder_lists, CIL_FALSE);
+						cil_list_destroy(&extra_args.unordered_classorder_lists, CIL_FALSE);
+						cil_list_init(&extra_args.sidorder_lists, CIL_SIDORDER);
+						cil_list_init(&extra_args.classorder_lists, CIL_CLASSORDER);
+						cil_list_init(&extra_args.unordered_classorder_lists, CIL_CLASSORDER);
+						cil_list_init(&extra_args.catorder_lists, CIL_CATORDER);
+						cil_list_init(&extra_args.sensitivityorder_lists, CIL_SENSITIVITYORDER);
 						cil_list_destroy(&db->sidorder, CIL_FALSE);
 						cil_list_destroy(&db->classorder, CIL_FALSE);
 						cil_list_destroy(&db->catorder, CIL_FALSE);
@@ -4263,11 +4174,11 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current)
 
 	rc = SEPOL_OK;
 exit:
-	__cil_ordered_lists_destroy(&extra_args.sidorder_lists);
-	__cil_ordered_lists_destroy(&extra_args.classorder_lists);
-	__cil_ordered_lists_destroy(&extra_args.catorder_lists);
-	__cil_ordered_lists_destroy(&extra_args.sensitivityorder_lists);
-	__cil_ordered_lists_destroy(&extra_args.unordered_classorder_lists);
+	cil_list_destroy(&extra_args.sidorder_lists, CIL_FALSE);
+	cil_list_destroy(&extra_args.classorder_lists, CIL_FALSE);
+	cil_list_destroy(&extra_args.catorder_lists, CIL_FALSE);
+	cil_list_destroy(&extra_args.sensitivityorder_lists, CIL_FALSE);
+	cil_list_destroy(&extra_args.unordered_classorder_lists, CIL_FALSE);
 	cil_list_destroy(&extra_args.to_destroy, CIL_FALSE);
 	cil_list_destroy(&extra_args.in_list_before, CIL_FALSE);
 	cil_list_destroy(&extra_args.in_list_after, CIL_FALSE);
diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c
index 579e7962..45bf4689 100644
--- a/libsepol/cil/src/cil_verify.c
+++ b/libsepol/cil/src/cil_verify.c
@@ -519,6 +519,78 @@ exit:
 	return rc;
 }
 
+int cil_verify_completed_ordered_list(struct cil_list *complete, struct cil_list *ordered_lists)
+{
+	struct cil_list_item *cprev, *ccurr, *cnext;
+	int found_prev, found_next;
+	int rc = SEPOL_OK;
+
+	found_prev = CIL_FALSE;
+	found_next = CIL_FALSE;
+	cprev = NULL;
+	ccurr = complete->head;
+	cnext = ccurr ? ccurr->next : NULL;
+	while (ccurr) {
+		struct cil_tree_node *node;
+		struct cil_ordered *ordered;
+		struct cil_list_item *curr_list, *oprev, *ocurr, *onext;
+		int change = CIL_FALSE;
+		cil_list_for_each(curr_list, ordered_lists) {
+			node = curr_list->data;
+			ordered = node->data;
+			oprev = NULL;
+			cil_list_for_each(ocurr, ordered->datums) {
+				onext = ocurr ? ocurr->next : NULL;
+				if (ccurr->data == ocurr->data) {
+					if (found_prev == CIL_FALSE && ((!cprev && !oprev) ||
+						(cprev && oprev && cprev->data == oprev->data))) {
+						found_prev = CIL_TRUE;
+						change = CIL_TRUE;
+					}
+					if (found_next == CIL_FALSE && ((!cnext && !onext) ||
+						(cnext && onext && cnext->data == onext->data))) {
+						found_next = CIL_TRUE;
+						change = CIL_TRUE;
+					}
+					if (found_prev && found_next) {
+						cprev = ccurr;
+						ccurr = cnext;
+						cnext = ccurr ? ccurr->next : NULL;
+						found_prev = CIL_FALSE;
+						found_next = CIL_FALSE;
+						if (!ccurr) {
+							/* Went through the whole list */
+							return rc;
+						}
+					}
+				}
+				oprev = ocurr;
+			}
+		}
+		if (!change) {
+			rc = SEPOL_ERR;
+			cil_log(CIL_ERR, "Unable to verify the order of %s\n", DATUM(ccurr->data)->fqn);
+			cil_log(CIL_ERR, "Found in the following ordering rules:\n");
+			cil_list_for_each(curr_list, ordered_lists) {
+				node = curr_list->data;
+				ordered = node->data;
+				cil_list_for_each(ocurr, ordered->datums) {
+					if (ccurr->data == ocurr->data) {
+						cil_tree_log(node, CIL_ERR, "    ");
+					}
+				}
+			}
+			cprev = ccurr;
+			ccurr = cnext;
+			cnext = ccurr ? ccurr->next : NULL;
+			found_prev = CIL_FALSE;
+			found_next = CIL_FALSE;
+		}
+	}
+
+	return rc;
+}
+
 struct cil_args_verify_order {
 	uint32_t *flavor;
 };
diff --git a/libsepol/cil/src/cil_verify.h b/libsepol/cil/src/cil_verify.h
index bb1a072c..daa2f80a 100644
--- a/libsepol/cil/src/cil_verify.h
+++ b/libsepol/cil/src/cil_verify.h
@@ -64,6 +64,7 @@ int cil_verify_constraint_expr_syntax(struct cil_tree_node *current, enum cil_fl
 int cil_verify_conditional_blocks(struct cil_tree_node *current);
 int cil_verify_decl_does_not_shadow_macro_parameter(struct cil_macro *macro, struct cil_tree_node *node, const char *name);
 int __cil_verify_ranges(struct cil_list *list);
+int cil_verify_completed_ordered_list(struct cil_list *complete, struct cil_list *ordered_lists);
 int __cil_verify_ordered_node_helper(struct cil_tree_node *node, uint32_t *finished, void *extra_args);
 int __cil_verify_ordered(struct cil_tree_node *current, enum cil_flavor flavor);
 int __cil_verify_initsids(struct cil_list *sids);
diff --git a/libsepol/cil/src/cil_write_ast.c b/libsepol/cil/src/cil_write_ast.c
index 4da7a77c..59122a17 100644
--- a/libsepol/cil/src/cil_write_ast.c
+++ b/libsepol/cil/src/cil_write_ast.c
@@ -765,9 +765,13 @@ void cil_write_ast_node(FILE *out, struct cil_tree_node *node)
 		break;
 	}
 	case CIL_CLASSORDER: {
-		struct cil_classorder *classorder = node->data;
+		struct cil_ordered *ordered = node->data;
 		fprintf(out, "(classorder ");
-		write_string_list(out, classorder->class_list_str);
+		if (ordered->datums) {
+			write_datum_list(out, ordered->datums);
+		} else {
+			write_string_list(out, ordered->strs);
+		}
 		fprintf(out, ")\n");
 		break;
 	}
@@ -834,9 +838,13 @@ void cil_write_ast_node(FILE *out, struct cil_tree_node *node)
 		break;
 	}
 	case CIL_SIDORDER: {
-		struct cil_sidorder *sidorder = node->data;
+		struct cil_ordered *ordered = node->data;
 		fprintf(out, "(sidorder ");
-		write_string_list(out, sidorder->sid_list_str);
+		if (ordered->datums) {
+			write_datum_list(out, ordered->datums);
+		} else {
+			write_string_list(out, ordered->strs);
+		}
 		fprintf(out, ")\n");
 		break;
 	}
@@ -888,9 +896,13 @@ void cil_write_ast_node(FILE *out, struct cil_tree_node *node)
 		break;
 	}
 	case CIL_CATORDER: {
-		struct cil_catorder *catorder = node->data;
+		struct cil_ordered *ordered = node->data;
 		fprintf(out, "(categoryorder ");
-		write_string_list(out, catorder->cat_list_str);
+		if (ordered->datums) {
+			write_datum_list(out, ordered->datums);
+		} else {
+			write_string_list(out, ordered->strs);
+		}
 		fprintf(out, ")\n");
 		break;
 	}
@@ -903,9 +915,13 @@ void cil_write_ast_node(FILE *out, struct cil_tree_node *node)
 		break;
 	}
 	case CIL_SENSITIVITYORDER: {
-		struct cil_sensorder *sensorder = node->data;
+		struct cil_ordered *ordered = node->data;
 		fprintf(out, "(sensitivityorder ");
-		write_string_list(out, sensorder->sens_list_str);
+		if (ordered->datums) {
+			write_datum_list(out, ordered->datums);
+		} else {
+			write_string_list(out, ordered->strs);
+		}
 		fprintf(out, ")\n");
 		break;
 	}
