1 /*
2 * Copyright (C) 2018 Alexander Borisov
3 *
4 * Author: Alexander Borisov <borisov@lexbor.com>
5 */
6
7 #include "lexbor/dom/interfaces/node.h"
8
9 #include "lexbor/html/tree/active_formatting.h"
10 #include "lexbor/html/tree/open_elements.h"
11 #include "lexbor/html/interfaces/element.h"
12
13
14 static lxb_html_element_t lxb_html_tree_active_formatting_marker_static;
15
16 static lxb_dom_node_t *lxb_html_tree_active_formatting_marker_node_static =
17 (lxb_dom_node_t *) &lxb_html_tree_active_formatting_marker_static;
18
19
20 lxb_html_element_t *
lxb_html_tree_active_formatting_marker(void)21 lxb_html_tree_active_formatting_marker(void)
22 {
23 return &lxb_html_tree_active_formatting_marker_static;
24 }
25
26 void
lxb_html_tree_active_formatting_up_to_last_marker(lxb_html_tree_t * tree)27 lxb_html_tree_active_formatting_up_to_last_marker(lxb_html_tree_t *tree)
28 {
29 void **list = tree->active_formatting->list;
30
31 while (tree->active_formatting->length != 0) {
32 tree->active_formatting->length--;
33
34 if (list[tree->active_formatting->length]
35 == &lxb_html_tree_active_formatting_marker_static)
36 {
37 break;
38 }
39 }
40 }
41
42 void
lxb_html_tree_active_formatting_remove_by_node(lxb_html_tree_t * tree,lxb_dom_node_t * node)43 lxb_html_tree_active_formatting_remove_by_node(lxb_html_tree_t *tree,
44 lxb_dom_node_t *node)
45 {
46 size_t delta;
47 void **list = tree->active_formatting->list;
48 size_t idx = tree->active_formatting->length;
49
50 while (idx != 0) {
51 idx--;
52
53 if (list[idx] == node) {
54 delta = tree->active_formatting->length - idx - 1;
55
56 memmove(list + idx, list + idx + 1, sizeof(void *) * delta);
57
58 tree->active_formatting->length--;
59
60 break;
61 }
62 }
63 }
64
65 bool
lxb_html_tree_active_formatting_find_by_node(lxb_html_tree_t * tree,lxb_dom_node_t * node,size_t * return_pos)66 lxb_html_tree_active_formatting_find_by_node(lxb_html_tree_t *tree,
67 lxb_dom_node_t *node,
68 size_t *return_pos)
69 {
70 void **list = tree->active_formatting->list;
71
72 for (size_t i = 0; i < tree->active_formatting->length; i++) {
73 if (list[i] == node) {
74 if (return_pos) {
75 *return_pos = i;
76 }
77
78 return true;
79 }
80 }
81
82 if (return_pos) {
83 *return_pos = 0;
84 }
85
86 return false;
87 }
88
89 bool
lxb_html_tree_active_formatting_find_by_node_reverse(lxb_html_tree_t * tree,lxb_dom_node_t * node,size_t * return_pos)90 lxb_html_tree_active_formatting_find_by_node_reverse(lxb_html_tree_t *tree,
91 lxb_dom_node_t *node,
92 size_t *return_pos)
93 {
94 void **list = tree->active_formatting->list;
95 size_t len = tree->active_formatting->length;
96
97 while (len != 0) {
98 len--;
99
100 if (list[len] == node) {
101 if (return_pos) {
102 *return_pos = len;
103 }
104
105 return true;
106 }
107 }
108
109 if (return_pos) {
110 *return_pos = 0;
111 }
112
113 return false;
114 }
115
116 lxb_status_t
lxb_html_tree_active_formatting_reconstruct_elements(lxb_html_tree_t * tree)117 lxb_html_tree_active_formatting_reconstruct_elements(lxb_html_tree_t *tree)
118 {
119 /* Step 1 */
120 if (tree->active_formatting->length == 0) {
121 return LXB_STATUS_OK;
122 }
123
124 lexbor_array_t *af = tree->active_formatting;
125 void **list = af->list;
126
127 /* Step 2-3 */
128 size_t af_idx = af->length - 1;
129
130 if(list[af_idx] == &lxb_html_tree_active_formatting_marker_static
131 || lxb_html_tree_open_elements_find_by_node_reverse(tree, list[af_idx],
132 NULL))
133 {
134 return LXB_STATUS_OK;
135 }
136
137 /*
138 * Step 4-6
139 * Rewind
140 */
141 while (af_idx != 0) {
142 af_idx--;
143
144 if(list[af_idx] == &lxb_html_tree_active_formatting_marker_static ||
145 lxb_html_tree_open_elements_find_by_node_reverse(tree, list[af_idx],
146 NULL))
147 {
148 /* Step 7 */
149 af_idx++;
150
151 break;
152 }
153 }
154
155 /*
156 * Step 8-10
157 * Create
158 */
159 lxb_dom_node_t *node;
160 lxb_html_element_t *element;
161 lxb_html_token_t fake_token = {0};
162
163 while (af_idx < af->length) {
164 node = list[af_idx];
165
166 fake_token.tag_id = node->local_name;
167 fake_token.base_element = node;
168
169 element = lxb_html_tree_insert_html_element(tree, &fake_token);
170 if (element == NULL) {
171 return LXB_STATUS_ERROR_MEMORY_ALLOCATION;
172 }
173
174 /* Step 9 */
175 list[af_idx] = lxb_dom_interface_node(element);
176
177 /* Step 10 */
178 af_idx++;
179 }
180
181 return LXB_STATUS_OK;
182 }
183
184 lxb_dom_node_t *
lxb_html_tree_active_formatting_between_last_marker(lxb_html_tree_t * tree,lxb_tag_id_t tag_idx,size_t * return_idx)185 lxb_html_tree_active_formatting_between_last_marker(lxb_html_tree_t *tree,
186 lxb_tag_id_t tag_idx,
187 size_t *return_idx)
188 {
189 lxb_dom_node_t **list = (lxb_dom_node_t **) tree->active_formatting->list;
190 size_t idx = tree->active_formatting->length;
191
192 while (idx) {
193 idx--;
194
195 if (list[idx] == lxb_html_tree_active_formatting_marker_node_static) {
196 return NULL;
197 }
198
199 if (list[idx]->local_name == tag_idx && list[idx]->ns == LXB_NS_HTML) {
200 if (return_idx) {
201 *return_idx = idx;
202 }
203
204 return list[idx];
205 }
206 }
207
208 return NULL;
209 }
210
211 void
lxb_html_tree_active_formatting_push_with_check_dupl(lxb_html_tree_t * tree,lxb_dom_node_t * node)212 lxb_html_tree_active_formatting_push_with_check_dupl(lxb_html_tree_t *tree,
213 lxb_dom_node_t *node)
214 {
215 lxb_dom_node_t **list = (lxb_dom_node_t **) tree->active_formatting->list;
216 size_t idx = tree->active_formatting->length;
217 size_t earliest_idx = (idx ? (idx - 1) : 0);
218 size_t count = 0;
219
220 while (idx) {
221 idx--;
222
223 if (list[idx] == lxb_html_tree_active_formatting_marker_node_static) {
224 break;
225 }
226
227 if(list[idx]->local_name == node->local_name && list[idx]->ns == node->ns
228 && lxb_dom_element_compare(lxb_dom_interface_element(list[idx]),
229 lxb_dom_interface_element(node)))
230 {
231 count++;
232 earliest_idx = idx;
233 }
234 }
235
236 if(count >= 3) {
237 lxb_html_tree_active_formatting_remove(tree, earliest_idx);
238 }
239
240 lxb_html_tree_active_formatting_push(tree, node);
241 }
242
