summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMura Li <mail@ctli.io>2019-10-20 17:12:21 +0800
committerOri Bernstein <ori@eigenstate.org>2019-10-21 23:48:43 -0700
commitf891bee473eccf9bdeb895dc3a2193355f264c5e (patch)
tree8de85d811540326494f5b676f86ba00fe4202895
parent2448eaba236da5bbcda95177582eb617ea1bbdf7 (diff)
downloadmc-f891bee473eccf9bdeb895dc3a2193355f264c5e.tar.gz
Update comments
-rw-r--r--mi/match.c27
1 files changed, 18 insertions, 9 deletions
diff --git a/mi/match.c b/mi/match.c
index 50d01be..1ae8cc7 100644
--- a/mi/match.c
+++ b/mi/match.c
@@ -25,10 +25,12 @@ static int ndtree;
* 0 is the root
* 0,0 and 0,1 are two subtrees of the root.
*
- * Note: the order of the sequence is reversed with regard to the reference paper.
+ * Note: the order of the sequence is reversed with regard to the reference paper
+ * "When Do Match-Compilation Heuristics Matter" by Kevin Scott and Norman Ramse.
*
* Each pattern of a match rule conrresponds to a unique Path of the subject tree.
- * When we have m match rules, for a given Path, there can be at most m patterns associated with the Path.
+ * When we have m match rules, for a given Path, there can be at most m patterns
+ * associated with the Path.
*
* Given
* match v
@@ -531,16 +533,23 @@ project(Node *pat, Path *pi, Node *val, Frontier *fs)
return out;
}
-/* compile implements the algorithm outlined in the paper "When Do Match-Compilation Heuristics Matter?" by Kevin Scott and Norman Ramsey
+/* compile implements the algorithm outlined in the paper
+ * "When Do Match-Compilation Heuristics Matter?" by Kevin Scott and Norman Ramsey
* It generates either a TEST or MATCH (accept=1) dtree, where MATCH is the base case.
*
* Summary:
- * 1. if the first Frontier of the input list of Frontiers does not contain any non-wildcard pattern, return a MATCH dtree (accept=1)
- * 2. for each call to the function, it will select a Path from the first match rule in the input Frontiers.
- * 3. scan the input frontiers 'vertically' at the selected Path to form a set of unique constructors. (the list 'cs')
- * 4. for each constructor in 'cs', recursively compile the 'projected' frontiers, which is roughly the frontiers minus the slot at the Path.
- * 5. recursively compile the remaining Frontiers (if any) corresponding to the matches rules with a wildcard at the selected Path.
- * 6. return a new dtree, where the compiled outputs at step 4 form the outgoing edges (dt->next), and the one produced at step 5 serves as the default edage (dt->any)
+ * 1. if the first Frontier of the input list of Frontiers does not contain any
+ * non-wildcard pattern, return a MATCH dtree (accept=1)
+ * 2. for each call to the function, it will select a Path from
+ * the first match rule in the input Frontiers.
+ * 3. scan the input frontiers 'vertically' at the selected Path to form a set
+ * of unique constructors. (the list 'cs')
+ * 4. for each constructor in 'cs', recursively compile the 'projected' frontiers,
+ * which is roughly the frontiers minus the slot at the Path.
+ * 5. recursively compile the remaining Frontiers (if any) corresponding to the matches
+ * rules with a wildcard at the selected Path.
+ * 6. return a new dtree, where the compiled outputs at step 4 form the outgoing edges
+ * (dt->next), and the one produced at step 5 serves as the default edage (dt->any)
*
* NOTE:
* a. how we select the Path at the step 2 is determined by heuristics.