-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
-
20
-
21
-
22
-
23
-
24
-
25
-
26
-
27
-
28
-
29
-
30
-
31
-
32
-
33
-
34
-
35
-
36
-
37
-
38
-
39
-
40
-
41
-
42
-
43
-
44
-
45
-
46
-
47
-
48
-
49
-
50
-
51
-
52
-
53
-
54
-
55
-
56
-
57
-
58
-
59
-
60
-
61
-
62
-
63
-
64
-
65
-
66
-
67
-
68
-
69
-
70
-
71
-
72
-
73
-
74
-
75
-
76
-
77
-
78
-
79
-
80
-
81
-
82
-
83
-
84
-
85
-
86
-
87
-
88
-
89
-
90
-
91
-
92
-
93
-
94
-
95
-
96
-
97
-
98
-
99
-
100
-
101
-
102
-
103
-
104
-
105
-
106
-
107
-
108
-
109
-
110
-
111
-
112
-
113
-
114
-
115
-
116
-
117
-
118
-
119
-
120
-
121
-
122
-
123
-
124
-
125
-
126
-
127
-
128
-
129
-
130
-
131
-
132
-
133
-
134
-
135
-
136
-
137
-
138
-
139
-
140
-
141
-
142
-
143
-
144
-
145
-
146
-
147
-
148
-
149
-
150
-
151
-
152
-
153
-
154
-
155
-
156
-
157
-
158
-
159
-
160
-
161
-
162
-
163
-
164
-
165
-
166
-
167
-
168
-
169
-
170
-
171
-
172
-
173
-
174
-
175
-
176
-
177
-
178
-
179
-
180
-
181
-
182
-
183
-
184
-
185
-
186
-
187
-
188
-
189
-
190
-
191
-
192
-
193
-
194
-
195
-
196
-
197
-
198
-
199
-
200
-
201
-
202
-
203
-
204
-
205
-
206
-
207
-
208
-
209
-
210
-
211
-
212
-
213
-
214
-
215
-
216
-
217
-
218
-
219
-
220
-
221
-
222
-
223
-
224
-
225
-
226
-
227
-
228
-
229
-
230
-
231
-
232
-
233
-
234
-
235
-
236
-
237
-
238
-
239
-
240
-
241
-
242
-
243
-
244
-
245
-
246
-
247
-
248
-
249
-
250
-
251
-
252
-
253
-
254
-
255
-
256
-
257
-
258
-
259
-
260
-
261
-
262
-
263
-
264
-
265
-
266
-
267
-
268
-
269
-
270
-
271
-
272
-
273
-
274
-
275
-
276
-
277
-
278
-
279
-
280
-
281
-
282
-
283
-
284
-
285
-
286
-
287
-
288
-
289
-
290
-
291
-
292
-
293
-
294
-
295
-
296
-
297
-
298
-
299
-
300
-
301
-
302
-
303
-
304
-
305
-
306
-
307
-
308
-
309
-
310
-
311
-
312
-
313
-
314
-
315
-
316
-
317
-
318
-
319
-
320
-
321
-
322
-
323
-
324
-
325
-
326
-
327
-
328
-
329
-
330
-
331
-
332
-
333
-
334
-
335
-
336
-
337
-
338
-
339
-
340
-
341
-
342
-
343
-
344
-
345
-
346
-
347
-
348
-
349
-
350
-
351
-
352
-
353
-
354
-
355
-
356
-
357
-
358
-
359
-
360
-
361
-
362
-
363
-
364
-
365
-
366
-
367
-
368
-
369
-
370
-
371
-
372
-
373
-
374
-
375
-
376
-
377
-
378
-
379
-
380
-
381
-
382
-
383
-
384
-
385
-
386
-
387
-
388
-
389
-
390
-
391
-
392
-
393
-
394
-
395
-
396
-
397
-
398
-
399
-
400
-
401
-
402
-
403
-
404
-
405
-
406
-
407
-
408
-
409
-
410
-
411
-
412
-
413
-
414
-
415
-
416
-
417
-
418
-
419
-
420
-
421
-
422
-
423
-
424
-
425
-
426
-
427
-
428
-
429
-
430
-
431
-
432
-
433
-
434
-
435
-
436
-
437
-
438
-
439
-
440
-
441
-
442
-
443
-
444
-
445
-
446
-
447
-
448
-
449
-
450
-
451
-
452
-
453
-
454
-
455
-
456
-
457
-
458
-
459
-
460
-
461
-
462
-
463
-
464
-
465
-
466
-
467
-
468
-
469
-
470
-
471
-
472
-
473
-
474
-
475
-
476
-
477
-
478
-
479
-
480
-
481
-
482
-
483
-
484
-
485
-
486
-
487
-
488
-
489
-
490
-
491
-
492
-
493
-
494
-
495
-
496
-
497
-
498
-
499
-
500
-
501
-
502
-
503
-
504
-
505
-
506
-
507
-
508
-
509
-
510
-
511
-
512
-
513
-
514
-
515
-
516
-
517
-
518
-
519
-
520
-
521
-
522
-
523
-
524
-
525
-
526
-
527
-
528
-
529
-
530
-
531
-
532
-
533
-
534
-
535
-
536
-
537
-
538
-
539
-
540
-
541
-
542
-
543
-
544
-
545
-
546
-
547
-
548
-
549
-
550
-
551
-
552
-
553
-
554
-
555
-
556
-
557
-
558
-
559
-
560
-
561
-
562
-
563
-
564
-
565
-
566
-
567
-
568
-
569
-
570
-
571
-
572
-
573
-
574
-
575
-
576
-
577
-
578
-
579
-
580
-
581
-
582
-
583
-
584
-
585
-
586
-
587
-
588
-
589
-
590
-
591
-
592
-
593
-
594
-
595
-
596
-
597
-
598
-
599
-
600
-
601
-
602
-
603
-
604
-
605
-
606
-
607
-
608
-
609
-
610
-
611
-
612
-
613
-
614
-
615
-
616
-
617
-
618
-
619
-
620
-
621
-
622
-
623
-
624
-
625
-
626
-
627
-
628
-
629
-
630
-
631
-
632
-
633
-
634
-
635
-
636
-
637
-
638
-
639
-
640
-
641
-
642
-
643
-
644
-
645
-
646
-
647
-
648
-
649
-
650
-
651
-
652
-
653
-
654
-
655
-
656
-
657
-
658
-
659
-
660
-
661
-
662
-
663
-
664
-
665
-
666
-
667
-
668
-
669
-
670
-
671
-
672
-
673
-
674
-
675
-
676
-
677
-
678
-
679
-
680
-
681
-
682
-
683
-
684
-
685
-
686
-
687
-
688
-
689
-
690
-
691
-
692
-
693
-
694
-
695
-
696
-
697
-
698
-
699
-
700
-
701
-
702
-
703
-
704
-
705
-
706
-
707
-
708
-
709
-
710
-
711
-
712
-
713
-
714
-
715
-
716
-
717
-
718
-
719
-
720
-
721
-
722
-
723
-
724
-
725
-
726
-
727
-
728
-
729
-
730
-
731
-
732
-
733
-
734
-
735
-
736
-
737
-
738
-
739
-
740
-
741
-
742
-
743
-
744
-
745
-
746
-
747
-
748
-
749
-
750
-
751
-
752
-
753
-
754
-
755
-
756
-
757
-
758
-
759
-
760
-
761
-
762
-
763
-
764
-
765
-
766
-
767
-
768
-
769
-
770
-
771
-
772
-
773
-
774
-
775
-
776
-
777
-
778
-
779
-
780
-
781
-
782
-
783
-
784
-
785
-
786
-
787
-
788
-
789
-
790
-
791
-
792
-
793
-
794
-
795
-
796
-
797
-
798
-
799
-
800
-
801
-
802
-
803
-
804
-
805
-
806
-
807
-
808
-
809
-
810
-
811
-
812
-
813
-
814
-
815
-
816
-
817
-
818
-
819
-
820
-
821
-
822
-
823
-
824
-
825
-
826
-
827
-
828
-
829
-
830
-
831
-
832
-
833
-
834
-
835
-
836
-
837
-
838
-
839
-
840
-
841
-
842
-
843
-
844
-
845
-
846
-
847
-
848
-
849
-
850
-
851
-
852
-
853
-
854
-
855
-
856
-
857
-
858
-
859
-
860
-
861
-
862
-
863
-
864
-
865
-
866
-
867
-
868
-
869
-
870
-
871
-
872
-
873
-
874
-
875
-
876
-
877
-
878
-
879
-
880
-
881
-
882
-
883
-
884
-
885
-
886
-
887
-
888
-
889
-
890
-
891
-
892
-
893
-
894
-
895
-
896
-
897
-
898
-
899
-
900
-
901
-
902
-
903
-
904
-
905
-
906
-
907
-
908
-
909
-
910
-
911
-
912
-
913
-
914
-
915
-
916
-
917
-
918
-
919
-
920
-
921
-
922
-
923
-
924
-
925
-
926
-
927
-
928
-
929
-
930
-
931
-
932
-
933
-
934
-
935
-
936
-
937
-
938
-
939
-
940
-
941
-
942
-
943
-
944
-
945
-
946
-
947
-
948
-
949
-
950
-
951
-
952
-
953
-
954
-
955
-
956
-
957
-
958
-
959
-
960
-
961
-
962
-
963
-
964
-
965
-
966
-
967
-
968
-
969
-
970
-
971
-
972
-
973
-
974
-
975
-
976
-
977
-
978
-
979
-
980
-
981
-
982
-
983
-
984
-
985
-
986
-
987
-
988
-
989
-
990
-
991
-
992
-
993
-
994
-
995
-
996
-
997
-
998
-
999
-
1000
-
1001
-
1002
-
1003
-
1004
-
1005
-
1006
-
1007
-
1008
-
1009
-
1010
-
1011
-
1012
-
1013
-
1014
-
1015
-
1016
-
1017
-
1018
-
1019
-
1020
-
1021
-
1022
-
1023
-
1024
-
1025
-
1026
-
1027
-
1028
-
1029
-
1030
-
1031
-
1032
-
1033
-
1034
-
1035
-
1036
-
1037
-
1038
-
1039
-
1040
-
1041
-
1042
-
1043
-
1044
-
1045
-
1046
-
1047
-
1048
-
1049
-
1050
-
1051
-
1052
-
1053
-
1054
-
1055
-
1056
-
1057
-
1058
-
1059
-
1060
-
1061
-
1062
-
1063
-
1064
-
1065
-
1066
-
1067
-
1068
-
1069
-
1070
-
1071
-
1072
-
1073
-
1074
-
1075
-
1076
-
1077
-
1078
-
1079
-
1080
-
1081
-
1082
-
1083
-
1084
-
1085
-
1086
-
1087
-
1088
-
1089
-
1090
-
1091
-
1092
-
1093
-
1094
-
1095
-
1096
-
1097
-
1098
-
1099
-
1100
-
1101
-
1102
-
1103
-
1104
-
1105
-
1106
-
1107
-
1108
-
1109
-
1110
-
1111
-
1112
-
1113
-
1114
-
1115
-
1116
-
1117
-
1118
-
1119
-
1120
-
1121
-
1122
-
1123
-
1124
-
1125
-
1126
-
1127
-
1128
-
1129
-
1130
-
1131
-
1132
-
1133
-
1134
-
1135
-
1136
-
1137
-
1138
-
1139
-
1140
-
1141
-
1142
-
1143
-
1144
-
1145
-
1146
-
1147
-
1148
-
1149
-
1150
-
1151
-
1152
-
1153
-
1154
-
1155
-
1156
-
1157
-
1158
-
1159
-
1160
-
1161
-
1162
-
1163
-
1164
-
1165
-
1166
-
1167
-
1168
-
1169
-
1170
-
1171
-
1172
-
1173
-
1174
-
1175
-
1176
-
1177
-
1178
-
1179
-
1180
-
1181
-
1182
-
1183
-
1184
-
1185
-
1186
-
1187
-
1188
-
1189
-
1190
-
1191
-
1192
-
1193
-
1194
-
1195
-
1196
-
1197
-
1198
-
1199
-
1200
-
1201
-
1202
-
1203
-
1204
-
1205
-
1206
-
1207
-
1208
-
1209
-
1210
-
1211
-
1212
-
1213
-
1214
-
1215
-
1216
-
1217
-
1218
-
1219
-
1220
-
1221
-
1222
-
1223
-
1224
-
1225
-
1226
-
1227
-
1228
-
1229
-
1230
-
1231
-
1232
-
1233
-
1234
-
1235
-
1236
-
1237
-
1238
-
1239
-
1240
-
1241
-
1242
-
1243
-
1244
-
1245
-
1246
-
1247
-
1248
-
1249
-
1250
-
1251
-
1252
-
1253
-
1254
-
1255
-
1256
-
1257
-
1258
-
1259
-
1260
-
1261
-
1262
-
1263
-
1264
-
1265
-
1266
-
1267
-
1268
-
1269
-
1270
-
1271
-
1272
-
1273
-
1274
-
1275
-
1276
-
1277
-
1278
-
1279
-
1280
-
1281
-
1282
-
1283
-
1284
-
1285
-
1286
-
1287
-
1288
-
1289
-
1290
-
1291
-
1292
-
1293
-
1294
-
1295
-
1296
-
1297
-
1298
-
1299
-
1300
-
1301
-
1302
-
1303
-
1304
-
1305
-
1306
-
1307
-
1308
-
1309
-
1310
-
1311
-
1312
-
1313
-
1314
-
1315
-
1316
-
1317
-
1318
-
1319
-
1320
-
1321
-
1322
-
1323
-
1324
-
1325
-
1326
-
1327
-
1328
-
1329
-
1330
-
1331
-
1332
-
1333
-
1334
-
1335
-
1336
-
1337
-
1338
-
1339
-
1340
-
1341
-
1342
-
1343
-
1344
-
1345
-
1346
-
1347
-
1348
-
1349
-
1350
-
1351
-
1352
-
1353
-
1354
-
1355
-
1356
-
1357
-
1358
-
1359
-
1360
-
1361
-
1362
-
1363
-
1364
-
1365
-
1366
-
1367
-
1368
-
1369
-
1370
-
1371
-
1372
-
1373
-
1374
-
1375
-
1376
-
1377
-
1378
-
1379
-
1380
-
1381
-
1382
-
1383
-
1384
-
1385
-
1386
-
1387
-
1388
-
1389
-
1390
-
1391
-
1392
-
1393
-
1394
-
1395
-
1396
-
1397
-
1398
-
1399
-
1400
-
1401
-
1402
-
1403
-
1404
-
1405
-
1406
-
1407
-
1408
-
1409
-
1410
-
1411
-
1412
-
1413
-
1414
-
1415
-
1416
-
1417
-
1418
-
1419
-
1420
-
1421
-
1422
-
1423
-
1424
-
1425
-
1426
-
1427
-
1428
-
1429
-
1430
-
1431
-
1432
-
1433
-
1434
-
1435
-
1436
-
1437
-
1438
-
1439
-
1440
-
1441
-
1442
-
1443
-
1444
-
1445
-
1446
-
1447
-
1448
-
1449
-
1450
-
1451
-
1452
-
1453
-
1454
-
1455
-
1456
-
1457
-
1458
-
1459
-
1460
-
1461
-
1462
-
1463
-
1464
-
1465
-
1466
-
1467
-
1468
-
1469
-
1470
-
1471
-
1472
-
1473
-
1474
-
1475
-
1476
-
1477
-
1478
-
1479
-
1480
-
1481
-
1482
-
1483
-
1484
-
1485
-
1486
-
1487
-
1488
-
1489
-
1490
-
1491
-
1492
-
1493
-
1494
-
1495
-
1496
-
1497
-
1498
-
1499
-
1500
-
1501
-
1502
-
1503
-
1504
-
1505
-
1506
-
1507
-
1508
-
1509
-
1510
-
1511
-
1512
-
1513
-
1514
-
1515
-
1516
-
1517
-
1518
-
1519
-
1520
-
1521
-
1522
-
1523
-
1524
-
1525
-
1526
-
1527
-
1528
-
1529
-
1530
-
1531
-
1532
-
1533
-
1534
-
1535
-
1536
-
1537
-
1538
-
1539
-
1540
-
1541
-
1542
-
1543
-
1544
-
1545
-
1546
-
1547
-
1548
-
1549
-
1550
-
1551
-
1552
-
1553
-
1554
-
1555
-
1556
-
1557
-
1558
-
1559
-
1560
-
1561
-
1562
-
1563
-
1564
-
1565
-
1566
-
1567
-
1568
-
1569
-
1570
-
1571
-
1572
-
1573
-
1574
-
1575
-
1576
-
1577
-
1578
-
1579
-
1580
-
1581
-
1582
-
1583
-
1584
-
1585
-
1586
-
1587
-
1588
-
1589
-
1590
-
1591
-
1592
-
1593
-
1594
-
1595
-
1596
-
1597
-
1598
-
1599
-
1600
-
1601
-
1602
-
1603
-
1604
-
1605
-
1606
-
1607
-
1608
-
1609
-
1610
-
1611
-
1612
-
1613
-
1614
-
1615
-
1616
-
1617
-
1618
-
1619
-
1620
-
1621
-
1622
-
1623
-
1624
-
1625
-
1626
-
1627
-
1628
-
1629
-
1630
-
1631
-
1632
-
1633
-
1634
-
1635
-
1636
-
1637
-
1638
-
1639
-
1640
-
1641
-
1642
-
1643
-
1644
-
1645
-
1646
-
1647
-
1648
-
1649
-
1650
-
1651
-
1652
-
1653
-
1654
-
1655
-
1656
-
1657
-
1658
-
1659
-
1660
-
1661
-
1662
-
1663
-
1664
-
1665
-
1666
-
1667
-
1668
-
1669
-
1670
-
1671
-
1672
-
1673
-
1674
-
1675
-
1676
-
1677
-
1678
-
1679
-
1680
-
1681
-
1682
-
1683
-
1684
-
1685
-
1686
-
1687
-
1688
-
1689
-
1690
-
1691
-
1692
-
1693
-
1694
-
1695
-
1696
-
1697
-
1698
-
1699
-
1700
-
1701
-
1702
-
1703
-
1704
-
1705
-
1706
-
1707
-
1708
-
1709
-
1710
-
1711
-
1712
-
1713
-
1714
-
1715
-
1716
-
1717
-
1718
-
1719
-
1720
-
1721
-
1722
-
1723
-
1724
-
1725
-
1726
-
1727
-
1728
-
1729
-
1730
-
1731
-
1732
-
1733
-
1734
-
1735
-
1736
-
1737
-
1738
-
1739
-
1740
-
1741
-
1742
-
1743
-
1744
-
1745
-
1746
-
1747
-
1748
-
1749
-
1750
-
1751
-
1752
-
1753
-
1754
-
1755
-
1756
-
1757
-
1758
-
1759
-
1760
-
1761
-
1762
-
1763
-
1764
-
1765
-
1766
-
1767
-
1768
-
1769
-
1770
-
1771
-
1772
-
1773
-
1774
-
1775
-
1776
-
1777
-
1778
-
1779
-
1780
-
1781
-
1782
-
1783
-
1784
-
1785
-
1786
-
1787
-
1788
-
1789
-
1790
-
1791
-
1792
-
1793
-
1794
-
1795
-
1796
-
1797
-
1798
-
1799
-
1800
-
1801
-
1802
-
1803
-
1804
-
1805
-
1806
-
1807
-
1808
-
1809
-
1810
-
1811
-
1812
-
1813
-
1814
-
1815
-
1816
-
1817
-
1818
-
1819
-
1820
-
1821
-
1822
-
1823
-
1824
-
1825
-
1826
-
1827
-
1828
-
1829
-
1830
-
1831
-
1832
-
1833
-
1834
-
1835
-
1836
-
1837
-
1838
-
1839
-
1840
-
1841
-
1842
-
1843
-
1844
-
1845
-
1846
-
1847
-
1848
-
1849
-
1850
-
1851
-
1852
-
1853
-
1854
-
1855
-
1856
-
1857
-
1858
-
1859
-
1860
-
1861
-
1862
-
1863
-
1864
-
1865
-
1866
-
1867
-
1868
-
1869
-
1870
-
1871
-
1872
-
1873
-
1874
-
1875
-
1876
-
1877
-
1878
-
1879
-
1880
-
1881
-
1882
-
1883
-
1884
-
1885
-
1886
-
1887
-
1888
-
1889
-
1890
-
1891
-
1892
-
1893
-
1894
-
1895
-
1896
-
1897
-
1898
-
1899
-
1900
-
1901
-
1902
-
1903
-
1904
-
1905
-
1906
-
1907
-
1908
-
1909
-
1910
-
1911
-
1912
-
1913
-
1914
-
1915
-
1916
-
1917
-
1918
-
1919
-
1920
-
1921
-
1922
-
1923
-
1924
-
1925
-
1926
-
1927
-
1928
-
1929
-
1930
-
1931
-
1932
-
1933
-
1934
-
1935
-
1936
-
1937
-
1938
-
1939
-
1940
-
1941
-
1942
-
1943
-
1944
-
1945
-
1946
-
1947
-
1948
-
1949
-
1950
-
1951
-
1952
-
1953
-
1954
-
1955
-
1956
-
1957
-
1958
-
1959
-
1960
-
1961
-
1962
-
1963
-
1964
-
1965
-
1966
-
1967
-
1968
-
1969
-
1970
-
1971
-
1972
-
1973
-
1974
-
1975
-
1976
-
1977
-
1978
-
1979
-
1980
-
1981
-
1982
-
1983
-
1984
-
1985
-
1986
-
1987
-
1988
-
1989
-
1990
-
1991
-
1992
-
1993
-
1994
-
1995
-
1996
-
1997
-
1998
-
1999
-
2000
-
2001
-
2002
-
2003
-
2004
-
2005
-
2006
-
2007
-
2008
-
2009
-
2010
-
2011
-
2012
-
2013
-
2014
-
2015
-
2016
-
2017
-
2018
-
2019
-
2020
-
2021
-
2022
-
2023
-
2024
-
2025
-
2026
-
2027
-
2028
-
2029
-
2030
-
2031
-
2032
-
2033
-
2034
-
2035
-
2036
-
2037
-
2038
-
2039
-
2040
-
2041
-
2042
-
2043
-
2044
-
2045
-
2046
-
2047
-
2048
-
2049
-
2050
-
2051
-
2052
-
2053
-
2054
-
2055
-
2056
-
2057
-
2058
-
2059
-
2060
-
2061
-
2062
-
2063
-
2064
-
2065
-
2066
-
2067
-
2068
-
2069
-
2070
-
2071
-
2072
-
2073
-
2074
-
2075
-
2076
-
2077
-
2078
-
2079
-
2080
-
2081
-
2082
-
2083
-
2084
-
2085
-
2086
-
2087
-
2088
-
2089
-
2090
-
2091
-
2092
-
2093
-
2094
-
2095
-
2096
-
2097
-
2098
-
2099
-
2100
-
2101
-
2102
-
2103
-
2104
-
2105
-
2106
-
2107
-
2108
-
2109
-
2110
-
2111
-
2112
-
2113
-
2114
-
2115
-
2116
-
2117
-
2118
-
2119
-
2120
-
2121
-
2122
-
2123
-
2124
-
2125
-
2126
-
2127
-
2128
-
2129
-
2130
-
2131
-
2132
-
2133
-
2134
-
2135
-
2136
-
2137
-
2138
-
2139
-
2140
-
2141
-
2142
-
2143
-
2144
-
2145
-
2146
-
2147
-
2148
-
2149
-
2150
-
2151
-
2152
-
2153
-
2154
-
2155
-
2156
-
2157
-
2158
-
2159
-
2160
-
2161
-
2162
-
2163
-
2164
-
2165
-
2166
-
2167
-
2168
-
2169
-
2170
-
2171
-
2172
-
2173
-
2174
-
2175
-
2176
-
2177
-
2178
-
2179
-
2180
-
2181
-
2182
-
2183
-
2184
-
2185
-
2186
-
2187
-
2188
-
2189
-
2190
-
2191
-
2192
-
2193
-
2194
-
2195
-
2196
-
2197
-
2198
-
2199
-
2200
-
2201
-
2202
-
2203
-
2204
-
2205
-
2206
-
2207
-
2208
-
2209
-
2210
-
2211
-
2212
-
2213
-
2214
-
2215
-
2216
-
2217
-
2218
-
2219
-
2220
-
2221
-
2222
-
2223
-
2224
-
2225
-
2226
-
2227
-
2228
-
2229
-
2230
-
2231
-
2232
-
2233
-
2234
-
2235
-
2236
-
2237
-
2238
-
2239
-
2240
-
2241
-
2242
-
2243
-
2244
-
2245
-
2246
-
2247
-
2248
-
2249
-
2250
-
2251
-
2252
-
2253
-
2254
-
2255
-
2256
-
2257
-
2258
-
2259
-
2260
-
2261
-
2262
-
2263
-
2264
-
2265
-
2266
-
2267
-
2268
-
2269
-
2270
-
2271
-
2272
-
2273
-
2274
-
2275
-
2276
-
2277
-
2278
-
2279
-
2280
-
2281
-
2282
-
2283
-
2284
-
2285
-
2286
-
2287
-
2288
-
2289
-
2290
-
2291
-
2292
-
2293
-
2294
-
2295
-
2296
-
2297
-
2298
-
2299
-
2300
-
2301
-
2302
-
2303
-
2304
-
2305
-
2306
-
2307
-
2308
-
2309
-
2310
-
2311
-
2312
-
2313
-
2314
-
2315
-
2316
-
2317
-
2318
-
2319
-
2320
-
2321
-
2322
-
2323
-
2324
-
2325
-
2326
-
2327
-
2328
-
2329
-
2330
-
2331
-
2332
-
2333
-
2334
-
2335
-
2336
-
2337
-
2338
-
2339
-
2340
-
2341
-
2342
-
2343
-
2344
-
2345
-
2346
-
2347
-
2348
-
2349
-
2350
-
2351
-
2352
-
2353
-
2354
-
2355
-
2356
-
2357
-
2358
-
2359
-
2360
-
2361
-
2362
-
2363
-
2364
-
2365
-
2366
-
2367
-
2368
-
2369
-
2370
-
2371
-
2372
-
2373
-
2374
-
2375
-
2376
-
2377
-
2378
-
2379
-
2380
-
2381
-
2382
-
2383
-
2384
-
2385
-
2386
-
2387
-
2388
-
2389
-
2390
-
2391
-
2392
-
2393
-
2394
-
2395
-
2396
-
2397
-
2398
-
2399
-
2400
-
2401
-
2402
-
2403
-
2404
-
2405
-
2406
-
2407
-
2408
-
2409
-
2410
-
2411
-
2412
-
2413
-
2414
-
2415
-
2416
-
2417
-
2418
-
2419
-
2420
-
2421
-
2422
-
2423
-
2424
-
2425
-
2426
-
2427
-
2428
-
2429
-
2430
-
2431
-
2432
-
2433
-
2434
-
2435
-
2436
-
2437
-
2438
-
2439
-
2440
-
2441
-
2442
-
2443
-
2444
-
2445
-
2446
-
2447
-
2448
-
2449
-
2450
-
2451
-
2452
-
2453
-
2454
-
2455
-
2456
-
2457
-
2458
-
2459
-
2460
// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package html
import (
"errors"
"fmt"
"io"
"strings"
a "golang.org/x/net/html/atom"
)
// A parser implements the HTML5 parsing algorithm:
// https://html.spec.whatwg.org/multipage/syntax.html#tree-construction
type parser struct {
// tokenizer provides the tokens for the parser.
tokenizer *Tokenizer
// tok is the most recently read token.
tok Token
// Self-closing tags like <hr/> are treated as start tags, except that
// hasSelfClosingToken is set while they are being processed.
hasSelfClosingToken bool
// doc is the document root element.
doc *Node
// The stack of open elements (section 12.2.4.2) and active formatting
// elements (section 12.2.4.3).
oe, afe nodeStack
// Element pointers (section 12.2.4.4).
head, form *Node
// Other parsing state flags (section 12.2.4.5).
scripting, framesetOK bool
// The stack of template insertion modes
templateStack insertionModeStack
// im is the current insertion mode.
im insertionMode
// originalIM is the insertion mode to go back to after completing a text
// or inTableText insertion mode.
originalIM insertionMode
// fosterParenting is whether new elements should be inserted according to
// the foster parenting rules (section 12.2.6.1).
fosterParenting bool
// quirks is whether the parser is operating in "quirks mode."
quirks bool
// fragment is whether the parser is parsing an HTML fragment.
fragment bool
// context is the context element when parsing an HTML fragment
// (section 12.4).
context *Node
}
func (p *parser) top() *Node {
if n := p.oe.top(); n != nil {
return n
}
return p.doc
}
// Stop tags for use in popUntil. These come from section 12.2.4.2.
var (
defaultScopeStopTags = map[string][]a.Atom{
"": {a.Applet, a.Caption, a.Html, a.Table, a.Td, a.Th, a.Marquee, a.Object, a.Template},
"math": {a.AnnotationXml, a.Mi, a.Mn, a.Mo, a.Ms, a.Mtext},
"svg": {a.Desc, a.ForeignObject, a.Title},
}
)
type scope int
const (
defaultScope scope = iota
listItemScope
buttonScope
tableScope
tableRowScope
tableBodyScope
selectScope
)
// popUntil pops the stack of open elements at the highest element whose tag
// is in matchTags, provided there is no higher element in the scope's stop
// tags (as defined in section 12.2.4.2). It returns whether or not there was
// such an element. If there was not, popUntil leaves the stack unchanged.
//
// For example, the set of stop tags for table scope is: "html", "table". If
// the stack was:
// ["html", "body", "font", "table", "b", "i", "u"]
// then popUntil(tableScope, "font") would return false, but
// popUntil(tableScope, "i") would return true and the stack would become:
// ["html", "body", "font", "table", "b"]
//
// If an element's tag is in both the stop tags and matchTags, then the stack
// will be popped and the function returns true (provided, of course, there was
// no higher element in the stack that was also in the stop tags). For example,
// popUntil(tableScope, "table") returns true and leaves:
// ["html", "body", "font"]
func (p *parser) popUntil(s scope, matchTags ...a.Atom) bool {
if i := p.indexOfElementInScope(s, matchTags...); i != -1 {
p.oe = p.oe[:i]
return true
}
return false
}
// indexOfElementInScope returns the index in p.oe of the highest element whose
// tag is in matchTags that is in scope. If no matching element is in scope, it
// returns -1.
func (p *parser) indexOfElementInScope(s scope, matchTags ...a.Atom) int {
for i := len(p.oe) - 1; i >= 0; i-- {
tagAtom := p.oe[i].DataAtom
if p.oe[i].Namespace == "" {
for _, t := range matchTags {
if t == tagAtom {
return i
}
}
switch s {
case defaultScope:
// No-op.
case listItemScope:
if tagAtom == a.Ol || tagAtom == a.Ul {
return -1
}
case buttonScope:
if tagAtom == a.Button {
return -1
}
case tableScope:
if tagAtom == a.Html || tagAtom == a.Table || tagAtom == a.Template {
return -1
}
case selectScope:
if tagAtom != a.Optgroup && tagAtom != a.Option {
return -1
}
default:
panic("unreachable")
}
}
switch s {
case defaultScope, listItemScope, buttonScope:
for _, t := range defaultScopeStopTags[p.oe[i].Namespace] {
if t == tagAtom {
return -1
}
}
}
}
return -1
}
// elementInScope is like popUntil, except that it doesn't modify the stack of
// open elements.
func (p *parser) elementInScope(s scope, matchTags ...a.Atom) bool {
return p.indexOfElementInScope(s, matchTags...) != -1
}
// clearStackToContext pops elements off the stack of open elements until a
// scope-defined element is found.
func (p *parser) clearStackToContext(s scope) {
for i := len(p.oe) - 1; i >= 0; i-- {
tagAtom := p.oe[i].DataAtom
switch s {
case tableScope:
if tagAtom == a.Html || tagAtom == a.Table || tagAtom == a.Template {
p.oe = p.oe[:i+1]
return
}
case tableRowScope:
if tagAtom == a.Html || tagAtom == a.Tr || tagAtom == a.Template {
p.oe = p.oe[:i+1]
return
}
case tableBodyScope:
if tagAtom == a.Html || tagAtom == a.Tbody || tagAtom == a.Tfoot || tagAtom == a.Thead || tagAtom == a.Template {
p.oe = p.oe[:i+1]
return
}
default:
panic("unreachable")
}
}
}
// parseGenericRawTextElements implements the generic raw text element parsing
// algorithm defined in 12.2.6.2.
// https://html.spec.whatwg.org/multipage/parsing.html#parsing-elements-that-contain-only-text
// TODO: Since both RAWTEXT and RCDATA states are treated as tokenizer's part
// officially, need to make tokenizer consider both states.
func (p *parser) parseGenericRawTextElement() {
p.addElement()
p.originalIM = p.im
p.im = textIM
}
// generateImpliedEndTags pops nodes off the stack of open elements as long as
// the top node has a tag name of dd, dt, li, optgroup, option, p, rb, rp, rt or rtc.
// If exceptions are specified, nodes with that name will not be popped off.
func (p *parser) generateImpliedEndTags(exceptions ...string) {
var i int
loop:
for i = len(p.oe) - 1; i >= 0; i-- {
n := p.oe[i]
if n.Type != ElementNode {
break
}
switch n.DataAtom {
case a.Dd, a.Dt, a.Li, a.Optgroup, a.Option, a.P, a.Rb, a.Rp, a.Rt, a.Rtc:
for _, except := range exceptions {
if n.Data == except {
break loop
}
}
continue
}
break
}
p.oe = p.oe[:i+1]
}
// addChild adds a child node n to the top element, and pushes n onto the stack
// of open elements if it is an element node.
func (p *parser) addChild(n *Node) {
if p.shouldFosterParent() {
p.fosterParent(n)
} else {
p.top().AppendChild(n)
}
if n.Type == ElementNode {
p.oe = append(p.oe, n)
}
}
// shouldFosterParent returns whether the next node to be added should be
// foster parented.
func (p *parser) shouldFosterParent() bool {
if p.fosterParenting {
switch p.top().DataAtom {
case a.Table, a.Tbody, a.Tfoot, a.Thead, a.Tr:
return true
}
}
return false
}
// fosterParent adds a child node according to the foster parenting rules.
// Section 12.2.6.1, "foster parenting".
func (p *parser) fosterParent(n *Node) {
var table, parent, prev, template *Node
var i int
for i = len(p.oe) - 1; i >= 0; i-- {
if p.oe[i].DataAtom == a.Table {
table = p.oe[i]
break
}
}
var j int
for j = len(p.oe) - 1; j >= 0; j-- {
if p.oe[j].DataAtom == a.Template {
template = p.oe[j]
break
}
}
if template != nil && (table == nil || j > i) {
template.AppendChild(n)
return
}
if table == nil {
// The foster parent is the html element.
parent = p.oe[0]
} else {
parent = table.Parent
}
if parent == nil {
parent = p.oe[i-1]
}
if table != nil {
prev = table.PrevSibling
} else {
prev = parent.LastChild
}
if prev != nil && prev.Type == TextNode && n.Type == TextNode {
prev.Data += n.Data
return
}
parent.InsertBefore(n, table)
}
// addText adds text to the preceding node if it is a text node, or else it
// calls addChild with a new text node.
func (p *parser) addText(text string) {
if text == "" {
return
}
if p.shouldFosterParent() {
p.fosterParent(&Node{
Type: TextNode,
Data: text,
})
return
}
t := p.top()
if n := t.LastChild; n != nil && n.Type == TextNode {
n.Data += text
return
}
p.addChild(&Node{
Type: TextNode,
Data: text,
})
}
// addElement adds a child element based on the current token.
func (p *parser) addElement() {
p.addChild(&Node{
Type: ElementNode,
DataAtom: p.tok.DataAtom,
Data: p.tok.Data,
Attr: p.tok.Attr,
})
}
// Section 12.2.4.3.
func (p *parser) addFormattingElement() {
tagAtom, attr := p.tok.DataAtom, p.tok.Attr
p.addElement()
// Implement the Noah's Ark clause, but with three per family instead of two.
identicalElements := 0
findIdenticalElements:
for i := len(p.afe) - 1; i >= 0; i-- {
n := p.afe[i]
if n.Type == scopeMarkerNode {
break
}
if n.Type != ElementNode {
continue
}
if n.Namespace != "" {
continue
}
if n.DataAtom != tagAtom {
continue
}
if len(n.Attr) != len(attr) {
continue
}
compareAttributes:
for _, t0 := range n.Attr {
for _, t1 := range attr {
if t0.Key == t1.Key && t0.Namespace == t1.Namespace && t0.Val == t1.Val {
// Found a match for this attribute, continue with the next attribute.
continue compareAttributes
}
}
// If we get here, there is no attribute that matches a.
// Therefore the element is not identical to the new one.
continue findIdenticalElements
}
identicalElements++
if identicalElements >= 3 {
p.afe.remove(n)
}
}
p.afe = append(p.afe, p.top())
}
// Section 12.2.4.3.
func (p *parser) clearActiveFormattingElements() {
for {
if n := p.afe.pop(); len(p.afe) == 0 || n.Type == scopeMarkerNode {
return
}
}
}
// Section 12.2.4.3.
func (p *parser) reconstructActiveFormattingElements() {
n := p.afe.top()
if n == nil {
return
}
if n.Type == scopeMarkerNode || p.oe.index(n) != -1 {
return
}
i := len(p.afe) - 1
for n.Type != scopeMarkerNode && p.oe.index(n) == -1 {
if i == 0 {
i = -1
break
}
i--
n = p.afe[i]
}
for {
i++
clone := p.afe[i].clone()
p.addChild(clone)
p.afe[i] = clone
if i == len(p.afe)-1 {
break
}
}
}
// Section 12.2.5.
func (p *parser) acknowledgeSelfClosingTag() {
p.hasSelfClosingToken = false
}
// An insertion mode (section 12.2.4.1) is the state transition function from
// a particular state in the HTML5 parser's state machine. It updates the
// parser's fields depending on parser.tok (where ErrorToken means EOF).
// It returns whether the token was consumed.
type insertionMode func(*parser) bool
// setOriginalIM sets the insertion mode to return to after completing a text or
// inTableText insertion mode.
// Section 12.2.4.1, "using the rules for".
func (p *parser) setOriginalIM() {
if p.originalIM != nil {
panic("html: bad parser state: originalIM was set twice")
}
p.originalIM = p.im
}
// Section 12.2.4.1, "reset the insertion mode".
func (p *parser) resetInsertionMode() {
for i := len(p.oe) - 1; i >= 0; i-- {
n := p.oe[i]
last := i == 0
if last && p.context != nil {
n = p.context
}
switch n.DataAtom {
case a.Select:
if !last {
for ancestor, first := n, p.oe[0]; ancestor != first; {
ancestor = p.oe[p.oe.index(ancestor)-1]
switch ancestor.DataAtom {
case a.Template:
p.im = inSelectIM
return
case a.Table:
p.im = inSelectInTableIM
return
}
}
}
p.im = inSelectIM
case a.Td, a.Th:
// TODO: remove this divergence from the HTML5 spec.
//
// See https://bugs.chromium.org/p/chromium/issues/detail?id=829668
p.im = inCellIM
case a.Tr:
p.im = inRowIM
case a.Tbody, a.Thead, a.Tfoot:
p.im = inTableBodyIM
case a.Caption:
p.im = inCaptionIM
case a.Colgroup:
p.im = inColumnGroupIM
case a.Table:
p.im = inTableIM
case a.Template:
// TODO: remove this divergence from the HTML5 spec.
if n.Namespace != "" {
continue
}
p.im = p.templateStack.top()
case a.Head:
// TODO: remove this divergence from the HTML5 spec.
//
// See https://bugs.chromium.org/p/chromium/issues/detail?id=829668
p.im = inHeadIM
case a.Body:
p.im = inBodyIM
case a.Frameset:
p.im = inFramesetIM
case a.Html:
if p.head == nil {
p.im = beforeHeadIM
} else {
p.im = afterHeadIM
}
default:
if last {
p.im = inBodyIM
return
}
continue
}
return
}
}
const whitespace = " \t\r\n\f"
// Section 12.2.6.4.1.
func initialIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
p.tok.Data = strings.TrimLeft(p.tok.Data, whitespace)
if len(p.tok.Data) == 0 {
// It was all whitespace, so ignore it.
return true
}
case CommentToken:
p.doc.AppendChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
case DoctypeToken:
n, quirks := parseDoctype(p.tok.Data)
p.doc.AppendChild(n)
p.quirks = quirks
p.im = beforeHTMLIM
return true
}
p.quirks = true
p.im = beforeHTMLIM
return false
}
// Section 12.2.6.4.2.
func beforeHTMLIM(p *parser) bool {
switch p.tok.Type {
case DoctypeToken:
// Ignore the token.
return true
case TextToken:
p.tok.Data = strings.TrimLeft(p.tok.Data, whitespace)
if len(p.tok.Data) == 0 {
// It was all whitespace, so ignore it.
return true
}
case StartTagToken:
if p.tok.DataAtom == a.Html {
p.addElement()
p.im = beforeHeadIM
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Head, a.Body, a.Html, a.Br:
p.parseImpliedToken(StartTagToken, a.Html, a.Html.String())
return false
default:
// Ignore the token.
return true
}
case CommentToken:
p.doc.AppendChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
}
p.parseImpliedToken(StartTagToken, a.Html, a.Html.String())
return false
}
// Section 12.2.6.4.3.
func beforeHeadIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
p.tok.Data = strings.TrimLeft(p.tok.Data, whitespace)
if len(p.tok.Data) == 0 {
// It was all whitespace, so ignore it.
return true
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Head:
p.addElement()
p.head = p.top()
p.im = inHeadIM
return true
case a.Html:
return inBodyIM(p)
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Head, a.Body, a.Html, a.Br:
p.parseImpliedToken(StartTagToken, a.Head, a.Head.String())
return false
default:
// Ignore the token.
return true
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
case DoctypeToken:
// Ignore the token.
return true
}
p.parseImpliedToken(StartTagToken, a.Head, a.Head.String())
return false
}
// Section 12.2.6.4.4.
func inHeadIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
s := strings.TrimLeft(p.tok.Data, whitespace)
if len(s) < len(p.tok.Data) {
// Add the initial whitespace to the current node.
p.addText(p.tok.Data[:len(p.tok.Data)-len(s)])
if s == "" {
return true
}
p.tok.Data = s
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Base, a.Basefont, a.Bgsound, a.Link, a.Meta:
p.addElement()
p.oe.pop()
p.acknowledgeSelfClosingTag()
return true
case a.Noscript:
if p.scripting {
p.parseGenericRawTextElement()
return true
}
p.addElement()
p.im = inHeadNoscriptIM
// Don't let the tokenizer go into raw text mode when scripting is disabled.
p.tokenizer.NextIsNotRawText()
return true
case a.Script, a.Title:
p.addElement()
p.setOriginalIM()
p.im = textIM
return true
case a.Noframes, a.Style:
p.parseGenericRawTextElement()
return true
case a.Head:
// Ignore the token.
return true
case a.Template:
// TODO: remove this divergence from the HTML5 spec.
//
// We don't handle all of the corner cases when mixing foreign
// content (i.e. <math> or <svg>) with <template>. Without this
// early return, we can get into an infinite loop, possibly because
// of the "TODO... further divergence" a little below.
//
// As a workaround, if we are mixing foreign content and templates,
// just ignore the rest of the HTML. Foreign content is rare and a
// relatively old HTML feature. Templates are also rare and a
// relatively new HTML feature. Their combination is very rare.
for _, e := range p.oe {
if e.Namespace != "" {
p.im = ignoreTheRemainingTokens
return true
}
}
p.addElement()
p.afe = append(p.afe, &scopeMarker)
p.framesetOK = false
p.im = inTemplateIM
p.templateStack = append(p.templateStack, inTemplateIM)
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Head:
p.oe.pop()
p.im = afterHeadIM
return true
case a.Body, a.Html, a.Br:
p.parseImpliedToken(EndTagToken, a.Head, a.Head.String())
return false
case a.Template:
if !p.oe.contains(a.Template) {
return true
}
// TODO: remove this further divergence from the HTML5 spec.
//
// See https://bugs.chromium.org/p/chromium/issues/detail?id=829668
p.generateImpliedEndTags()
for i := len(p.oe) - 1; i >= 0; i-- {
if n := p.oe[i]; n.Namespace == "" && n.DataAtom == a.Template {
p.oe = p.oe[:i]
break
}
}
p.clearActiveFormattingElements()
p.templateStack.pop()
p.resetInsertionMode()
return true
default:
// Ignore the token.
return true
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
case DoctypeToken:
// Ignore the token.
return true
}
p.parseImpliedToken(EndTagToken, a.Head, a.Head.String())
return false
}
// 12.2.6.4.5.
func inHeadNoscriptIM(p *parser) bool {
switch p.tok.Type {
case DoctypeToken:
// Ignore the token.
return true
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Basefont, a.Bgsound, a.Link, a.Meta, a.Noframes, a.Style:
return inHeadIM(p)
case a.Head:
// Ignore the token.
return true
case a.Noscript:
// Don't let the tokenizer go into raw text mode even when a <noscript>
// tag is in "in head noscript" insertion mode.
p.tokenizer.NextIsNotRawText()
// Ignore the token.
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Noscript, a.Br:
default:
// Ignore the token.
return true
}
case TextToken:
s := strings.TrimLeft(p.tok.Data, whitespace)
if len(s) == 0 {
// It was all whitespace.
return inHeadIM(p)
}
case CommentToken:
return inHeadIM(p)
}
p.oe.pop()
if p.top().DataAtom != a.Head {
panic("html: the new current node will be a head element.")
}
p.im = inHeadIM
if p.tok.DataAtom == a.Noscript {
return true
}
return false
}
// Section 12.2.6.4.6.
func afterHeadIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
s := strings.TrimLeft(p.tok.Data, whitespace)
if len(s) < len(p.tok.Data) {
// Add the initial whitespace to the current node.
p.addText(p.tok.Data[:len(p.tok.Data)-len(s)])
if s == "" {
return true
}
p.tok.Data = s
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Body:
p.addElement()
p.framesetOK = false
p.im = inBodyIM
return true
case a.Frameset:
p.addElement()
p.im = inFramesetIM
return true
case a.Base, a.Basefont, a.Bgsound, a.Link, a.Meta, a.Noframes, a.Script, a.Style, a.Template, a.Title:
p.oe = append(p.oe, p.head)
defer p.oe.remove(p.head)
return inHeadIM(p)
case a.Head:
// Ignore the token.
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Body, a.Html, a.Br:
// Drop down to creating an implied <body> tag.
case a.Template:
return inHeadIM(p)
default:
// Ignore the token.
return true
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
case DoctypeToken:
// Ignore the token.
return true
}
p.parseImpliedToken(StartTagToken, a.Body, a.Body.String())
p.framesetOK = true
return false
}
// copyAttributes copies attributes of src not found on dst to dst.
func copyAttributes(dst *Node, src Token) {
if len(src.Attr) == 0 {
return
}
attr := map[string]string{}
for _, t := range dst.Attr {
attr[t.Key] = t.Val
}
for _, t := range src.Attr {
if _, ok := attr[t.Key]; !ok {
dst.Attr = append(dst.Attr, t)
attr[t.Key] = t.Val
}
}
}
// Section 12.2.6.4.7.
func inBodyIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
d := p.tok.Data
switch n := p.oe.top(); n.DataAtom {
case a.Pre, a.Listing:
if n.FirstChild == nil {
// Ignore a newline at the start of a <pre> block.
if d != "" && d[0] == '\r' {
d = d[1:]
}
if d != "" && d[0] == '\n' {
d = d[1:]
}
}
}
d = strings.Replace(d, "\x00", "", -1)
if d == "" {
return true
}
p.reconstructActiveFormattingElements()
p.addText(d)
if p.framesetOK && strings.TrimLeft(d, whitespace) != "" {
// There were non-whitespace characters inserted.
p.framesetOK = false
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
if p.oe.contains(a.Template) {
return true
}
copyAttributes(p.oe[0], p.tok)
case a.Base, a.Basefont, a.Bgsound, a.Link, a.Meta, a.Noframes, a.Script, a.Style, a.Template, a.Title:
return inHeadIM(p)
case a.Body:
if p.oe.contains(a.Template) {
return true
}
if len(p.oe) >= 2 {
body := p.oe[1]
if body.Type == ElementNode && body.DataAtom == a.Body {
p.framesetOK = false
copyAttributes(body, p.tok)
}
}
case a.Frameset:
if !p.framesetOK || len(p.oe) < 2 || p.oe[1].DataAtom != a.Body {
// Ignore the token.
return true
}
body := p.oe[1]
if body.Parent != nil {
body.Parent.RemoveChild(body)
}
p.oe = p.oe[:1]
p.addElement()
p.im = inFramesetIM
return true
case a.Address, a.Article, a.Aside, a.Blockquote, a.Center, a.Details, a.Dialog, a.Dir, a.Div, a.Dl, a.Fieldset, a.Figcaption, a.Figure, a.Footer, a.Header, a.Hgroup, a.Main, a.Menu, a.Nav, a.Ol, a.P, a.Section, a.Summary, a.Ul:
p.popUntil(buttonScope, a.P)
p.addElement()
case a.H1, a.H2, a.H3, a.H4, a.H5, a.H6:
p.popUntil(buttonScope, a.P)
switch n := p.top(); n.DataAtom {
case a.H1, a.H2, a.H3, a.H4, a.H5, a.H6:
p.oe.pop()
}
p.addElement()
case a.Pre, a.Listing:
p.popUntil(buttonScope, a.P)
p.addElement()
// The newline, if any, will be dealt with by the TextToken case.
p.framesetOK = false
case a.Form:
if p.form != nil && !p.oe.contains(a.Template) {
// Ignore the token
return true
}
p.popUntil(buttonScope, a.P)
p.addElement()
if !p.oe.contains(a.Template) {
p.form = p.top()
}
case a.Li:
p.framesetOK = false
for i := len(p.oe) - 1; i >= 0; i-- {
node := p.oe[i]
switch node.DataAtom {
case a.Li:
p.oe = p.oe[:i]
case a.Address, a.Div, a.P:
continue
default:
if !isSpecialElement(node) {
continue
}
}
break
}
p.popUntil(buttonScope, a.P)
p.addElement()
case a.Dd, a.Dt:
p.framesetOK = false
for i := len(p.oe) - 1; i >= 0; i-- {
node := p.oe[i]
switch node.DataAtom {
case a.Dd, a.Dt:
p.oe = p.oe[:i]
case a.Address, a.Div, a.P:
continue
default:
if !isSpecialElement(node) {
continue
}
}
break
}
p.popUntil(buttonScope, a.P)
p.addElement()
case a.Plaintext:
p.popUntil(buttonScope, a.P)
p.addElement()
case a.Button:
p.popUntil(defaultScope, a.Button)
p.reconstructActiveFormattingElements()
p.addElement()
p.framesetOK = false
case a.A:
for i := len(p.afe) - 1; i >= 0 && p.afe[i].Type != scopeMarkerNode; i-- {
if n := p.afe[i]; n.Type == ElementNode && n.DataAtom == a.A {
p.inBodyEndTagFormatting(a.A, "a")
p.oe.remove(n)
p.afe.remove(n)
break
}
}
p.reconstructActiveFormattingElements()
p.addFormattingElement()
case a.B, a.Big, a.Code, a.Em, a.Font, a.I, a.S, a.Small, a.Strike, a.Strong, a.Tt, a.U:
p.reconstructActiveFormattingElements()
p.addFormattingElement()
case a.Nobr:
p.reconstructActiveFormattingElements()
if p.elementInScope(defaultScope, a.Nobr) {
p.inBodyEndTagFormatting(a.Nobr, "nobr")
p.reconstructActiveFormattingElements()
}
p.addFormattingElement()
case a.Applet, a.Marquee, a.Object:
p.reconstructActiveFormattingElements()
p.addElement()
p.afe = append(p.afe, &scopeMarker)
p.framesetOK = false
case a.Table:
if !p.quirks {
p.popUntil(buttonScope, a.P)
}
p.addElement()
p.framesetOK = false
p.im = inTableIM
return true
case a.Area, a.Br, a.Embed, a.Img, a.Input, a.Keygen, a.Wbr:
p.reconstructActiveFormattingElements()
p.addElement()
p.oe.pop()
p.acknowledgeSelfClosingTag()
if p.tok.DataAtom == a.Input {
for _, t := range p.tok.Attr {
if t.Key == "type" {
if strings.ToLower(t.Val) == "hidden" {
// Skip setting framesetOK = false
return true
}
}
}
}
p.framesetOK = false
case a.Param, a.Source, a.Track:
p.addElement()
p.oe.pop()
p.acknowledgeSelfClosingTag()
case a.Hr:
p.popUntil(buttonScope, a.P)
p.addElement()
p.oe.pop()
p.acknowledgeSelfClosingTag()
p.framesetOK = false
case a.Image:
p.tok.DataAtom = a.Img
p.tok.Data = a.Img.String()
return false
case a.Textarea:
p.addElement()
p.setOriginalIM()
p.framesetOK = false
p.im = textIM
case a.Xmp:
p.popUntil(buttonScope, a.P)
p.reconstructActiveFormattingElements()
p.framesetOK = false
p.parseGenericRawTextElement()
case a.Iframe:
p.framesetOK = false
p.parseGenericRawTextElement()
case a.Noembed:
p.parseGenericRawTextElement()
case a.Noscript:
if p.scripting {
p.parseGenericRawTextElement()
return true
}
p.reconstructActiveFormattingElements()
p.addElement()
// Don't let the tokenizer go into raw text mode when scripting is disabled.
p.tokenizer.NextIsNotRawText()
case a.Select:
p.reconstructActiveFormattingElements()
p.addElement()
p.framesetOK = false
p.im = inSelectIM
return true
case a.Optgroup, a.Option:
if p.top().DataAtom == a.Option {
p.oe.pop()
}
p.reconstructActiveFormattingElements()
p.addElement()
case a.Rb, a.Rtc:
if p.elementInScope(defaultScope, a.Ruby) {
p.generateImpliedEndTags()
}
p.addElement()
case a.Rp, a.Rt:
if p.elementInScope(defaultScope, a.Ruby) {
p.generateImpliedEndTags("rtc")
}
p.addElement()
case a.Math, a.Svg:
p.reconstructActiveFormattingElements()
if p.tok.DataAtom == a.Math {
adjustAttributeNames(p.tok.Attr, mathMLAttributeAdjustments)
} else {
adjustAttributeNames(p.tok.Attr, svgAttributeAdjustments)
}
adjustForeignAttributes(p.tok.Attr)
p.addElement()
p.top().Namespace = p.tok.Data
if p.hasSelfClosingToken {
p.oe.pop()
p.acknowledgeSelfClosingTag()
}
return true
case a.Caption, a.Col, a.Colgroup, a.Frame, a.Head, a.Tbody, a.Td, a.Tfoot, a.Th, a.Thead, a.Tr:
// Ignore the token.
default:
p.reconstructActiveFormattingElements()
p.addElement()
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Body:
if p.elementInScope(defaultScope, a.Body) {
p.im = afterBodyIM
}
case a.Html:
if p.elementInScope(defaultScope, a.Body) {
p.parseImpliedToken(EndTagToken, a.Body, a.Body.String())
return false
}
return true
case a.Address, a.Article, a.Aside, a.Blockquote, a.Button, a.Center, a.Details, a.Dialog, a.Dir, a.Div, a.Dl, a.Fieldset, a.Figcaption, a.Figure, a.Footer, a.Header, a.Hgroup, a.Listing, a.Main, a.Menu, a.Nav, a.Ol, a.Pre, a.Section, a.Summary, a.Ul:
p.popUntil(defaultScope, p.tok.DataAtom)
case a.Form:
if p.oe.contains(a.Template) {
i := p.indexOfElementInScope(defaultScope, a.Form)
if i == -1 {
// Ignore the token.
return true
}
p.generateImpliedEndTags()
if p.oe[i].DataAtom != a.Form {
// Ignore the token.
return true
}
p.popUntil(defaultScope, a.Form)
} else {
node := p.form
p.form = nil
i := p.indexOfElementInScope(defaultScope, a.Form)
if node == nil || i == -1 || p.oe[i] != node {
// Ignore the token.
return true
}
p.generateImpliedEndTags()
p.oe.remove(node)
}
case a.P:
if !p.elementInScope(buttonScope, a.P) {
p.parseImpliedToken(StartTagToken, a.P, a.P.String())
}
p.popUntil(buttonScope, a.P)
case a.Li:
p.popUntil(listItemScope, a.Li)
case a.Dd, a.Dt:
p.popUntil(defaultScope, p.tok.DataAtom)
case a.H1, a.H2, a.H3, a.H4, a.H5, a.H6:
p.popUntil(defaultScope, a.H1, a.H2, a.H3, a.H4, a.H5, a.H6)
case a.A, a.B, a.Big, a.Code, a.Em, a.Font, a.I, a.Nobr, a.S, a.Small, a.Strike, a.Strong, a.Tt, a.U:
p.inBodyEndTagFormatting(p.tok.DataAtom, p.tok.Data)
case a.Applet, a.Marquee, a.Object:
if p.popUntil(defaultScope, p.tok.DataAtom) {
p.clearActiveFormattingElements()
}
case a.Br:
p.tok.Type = StartTagToken
return false
case a.Template:
return inHeadIM(p)
default:
p.inBodyEndTagOther(p.tok.DataAtom, p.tok.Data)
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
case ErrorToken:
// TODO: remove this divergence from the HTML5 spec.
if len(p.templateStack) > 0 {
p.im = inTemplateIM
return false
}
for _, e := range p.oe {
switch e.DataAtom {
case a.Dd, a.Dt, a.Li, a.Optgroup, a.Option, a.P, a.Rb, a.Rp, a.Rt, a.Rtc, a.Tbody, a.Td, a.Tfoot, a.Th,
a.Thead, a.Tr, a.Body, a.Html:
default:
return true
}
}
}
return true
}
func (p *parser) inBodyEndTagFormatting(tagAtom a.Atom, tagName string) {
// This is the "adoption agency" algorithm, described at
// https://html.spec.whatwg.org/multipage/syntax.html#adoptionAgency
// TODO: this is a fairly literal line-by-line translation of that algorithm.
// Once the code successfully parses the comprehensive test suite, we should
// refactor this code to be more idiomatic.
// Steps 1-2
if current := p.oe.top(); current.Data == tagName && p.afe.index(current) == -1 {
p.oe.pop()
return
}
// Steps 3-5. The outer loop.
for i := 0; i < 8; i++ {
// Step 6. Find the formatting element.
var formattingElement *Node
for j := len(p.afe) - 1; j >= 0; j-- {
if p.afe[j].Type == scopeMarkerNode {
break
}
if p.afe[j].DataAtom == tagAtom {
formattingElement = p.afe[j]
break
}
}
if formattingElement == nil {
p.inBodyEndTagOther(tagAtom, tagName)
return
}
// Step 7. Ignore the tag if formatting element is not in the stack of open elements.
feIndex := p.oe.index(formattingElement)
if feIndex == -1 {
p.afe.remove(formattingElement)
return
}
// Step 8. Ignore the tag if formatting element is not in the scope.
if !p.elementInScope(defaultScope, tagAtom) {
// Ignore the tag.
return
}
// Step 9. This step is omitted because it's just a parse error but no need to return.
// Steps 10-11. Find the furthest block.
var furthestBlock *Node
for _, e := range p.oe[feIndex:] {
if isSpecialElement(e) {
furthestBlock = e
break
}
}
if furthestBlock == nil {
e := p.oe.pop()
for e != formattingElement {
e = p.oe.pop()
}
p.afe.remove(e)
return
}
// Steps 12-13. Find the common ancestor and bookmark node.
commonAncestor := p.oe[feIndex-1]
bookmark := p.afe.index(formattingElement)
// Step 14. The inner loop. Find the lastNode to reparent.
lastNode := furthestBlock
node := furthestBlock
x := p.oe.index(node)
// Step 14.1.
j := 0
for {
// Step 14.2.
j++
// Step. 14.3.
x--
node = p.oe[x]
// Step 14.4. Go to the next step if node is formatting element.
if node == formattingElement {
break
}
// Step 14.5. Remove node from the list of active formatting elements if
// inner loop counter is greater than three and node is in the list of
// active formatting elements.
if ni := p.afe.index(node); j > 3 && ni > -1 {
p.afe.remove(node)
// If any element of the list of active formatting elements is removed,
// we need to take care whether bookmark should be decremented or not.
// This is because the value of bookmark may exceed the size of the
// list by removing elements from the list.
if ni <= bookmark {
bookmark--
}
continue
}
// Step 14.6. Continue the next inner loop if node is not in the list of
// active formatting elements.
if p.afe.index(node) == -1 {
p.oe.remove(node)
continue
}
// Step 14.7.
clone := node.clone()
p.afe[p.afe.index(node)] = clone
p.oe[p.oe.index(node)] = clone
node = clone
// Step 14.8.
if lastNode == furthestBlock {
bookmark = p.afe.index(node) + 1
}
// Step 14.9.
if lastNode.Parent != nil {
lastNode.Parent.RemoveChild(lastNode)
}
node.AppendChild(lastNode)
// Step 14.10.
lastNode = node
}
// Step 15. Reparent lastNode to the common ancestor,
// or for misnested table nodes, to the foster parent.
if lastNode.Parent != nil {
lastNode.Parent.RemoveChild(lastNode)
}
switch commonAncestor.DataAtom {
case a.Table, a.Tbody, a.Tfoot, a.Thead, a.Tr:
p.fosterParent(lastNode)
default:
commonAncestor.AppendChild(lastNode)
}
// Steps 16-18. Reparent nodes from the furthest block's children
// to a clone of the formatting element.
clone := formattingElement.clone()
reparentChildren(clone, furthestBlock)
furthestBlock.AppendChild(clone)
// Step 19. Fix up the list of active formatting elements.
if oldLoc := p.afe.index(formattingElement); oldLoc != -1 && oldLoc < bookmark {
// Move the bookmark with the rest of the list.
bookmark--
}
p.afe.remove(formattingElement)
p.afe.insert(bookmark, clone)
// Step 20. Fix up the stack of open elements.
p.oe.remove(formattingElement)
p.oe.insert(p.oe.index(furthestBlock)+1, clone)
}
}
// inBodyEndTagOther performs the "any other end tag" algorithm for inBodyIM.
// "Any other end tag" handling from 12.2.6.5 The rules for parsing tokens in foreign content
// https://html.spec.whatwg.org/multipage/syntax.html#parsing-main-inforeign
func (p *parser) inBodyEndTagOther(tagAtom a.Atom, tagName string) {
for i := len(p.oe) - 1; i >= 0; i-- {
// Two element nodes have the same tag if they have the same Data (a
// string-typed field). As an optimization, for common HTML tags, each
// Data string is assigned a unique, non-zero DataAtom (a uint32-typed
// field), since integer comparison is faster than string comparison.
// Uncommon (custom) tags get a zero DataAtom.
//
// The if condition here is equivalent to (p.oe[i].Data == tagName).
if (p.oe[i].DataAtom == tagAtom) &&
((tagAtom != 0) || (p.oe[i].Data == tagName)) {
p.oe = p.oe[:i]
break
}
if isSpecialElement(p.oe[i]) {
break
}
}
}
// Section 12.2.6.4.8.
func textIM(p *parser) bool {
switch p.tok.Type {
case ErrorToken:
p.oe.pop()
case TextToken:
d := p.tok.Data
if n := p.oe.top(); n.DataAtom == a.Textarea && n.FirstChild == nil {
// Ignore a newline at the start of a <textarea> block.
if d != "" && d[0] == '\r' {
d = d[1:]
}
if d != "" && d[0] == '\n' {
d = d[1:]
}
}
if d == "" {
return true
}
p.addText(d)
return true
case EndTagToken:
p.oe.pop()
}
p.im = p.originalIM
p.originalIM = nil
return p.tok.Type == EndTagToken
}
// Section 12.2.6.4.9.
func inTableIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
p.tok.Data = strings.Replace(p.tok.Data, "\x00", "", -1)
switch p.oe.top().DataAtom {
case a.Table, a.Tbody, a.Tfoot, a.Thead, a.Tr:
if strings.Trim(p.tok.Data, whitespace) == "" {
p.addText(p.tok.Data)
return true
}
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Caption:
p.clearStackToContext(tableScope)
p.afe = append(p.afe, &scopeMarker)
p.addElement()
p.im = inCaptionIM
return true
case a.Colgroup:
p.clearStackToContext(tableScope)
p.addElement()
p.im = inColumnGroupIM
return true
case a.Col:
p.parseImpliedToken(StartTagToken, a.Colgroup, a.Colgroup.String())
return false
case a.Tbody, a.Tfoot, a.Thead:
p.clearStackToContext(tableScope)
p.addElement()
p.im = inTableBodyIM
return true
case a.Td, a.Th, a.Tr:
p.parseImpliedToken(StartTagToken, a.Tbody, a.Tbody.String())
return false
case a.Table:
if p.popUntil(tableScope, a.Table) {
p.resetInsertionMode()
return false
}
// Ignore the token.
return true
case a.Style, a.Script, a.Template:
return inHeadIM(p)
case a.Input:
for _, t := range p.tok.Attr {
if t.Key == "type" && strings.ToLower(t.Val) == "hidden" {
p.addElement()
p.oe.pop()
return true
}
}
// Otherwise drop down to the default action.
case a.Form:
if p.oe.contains(a.Template) || p.form != nil {
// Ignore the token.
return true
}
p.addElement()
p.form = p.oe.pop()
case a.Select:
p.reconstructActiveFormattingElements()
switch p.top().DataAtom {
case a.Table, a.Tbody, a.Tfoot, a.Thead, a.Tr:
p.fosterParenting = true
}
p.addElement()
p.fosterParenting = false
p.framesetOK = false
p.im = inSelectInTableIM
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Table:
if p.popUntil(tableScope, a.Table) {
p.resetInsertionMode()
return true
}
// Ignore the token.
return true
case a.Body, a.Caption, a.Col, a.Colgroup, a.Html, a.Tbody, a.Td, a.Tfoot, a.Th, a.Thead, a.Tr:
// Ignore the token.
return true
case a.Template:
return inHeadIM(p)
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
case DoctypeToken:
// Ignore the token.
return true
case ErrorToken:
return inBodyIM(p)
}
p.fosterParenting = true
defer func() { p.fosterParenting = false }()
return inBodyIM(p)
}
// Section 12.2.6.4.11.
func inCaptionIM(p *parser) bool {
switch p.tok.Type {
case StartTagToken:
switch p.tok.DataAtom {
case a.Caption, a.Col, a.Colgroup, a.Tbody, a.Td, a.Tfoot, a.Thead, a.Tr:
if !p.popUntil(tableScope, a.Caption) {
// Ignore the token.
return true
}
p.clearActiveFormattingElements()
p.im = inTableIM
return false
case a.Select:
p.reconstructActiveFormattingElements()
p.addElement()
p.framesetOK = false
p.im = inSelectInTableIM
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Caption:
if p.popUntil(tableScope, a.Caption) {
p.clearActiveFormattingElements()
p.im = inTableIM
}
return true
case a.Table:
if !p.popUntil(tableScope, a.Caption) {
// Ignore the token.
return true
}
p.clearActiveFormattingElements()
p.im = inTableIM
return false
case a.Body, a.Col, a.Colgroup, a.Html, a.Tbody, a.Td, a.Tfoot, a.Th, a.Thead, a.Tr:
// Ignore the token.
return true
}
}
return inBodyIM(p)
}
// Section 12.2.6.4.12.
func inColumnGroupIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
s := strings.TrimLeft(p.tok.Data, whitespace)
if len(s) < len(p.tok.Data) {
// Add the initial whitespace to the current node.
p.addText(p.tok.Data[:len(p.tok.Data)-len(s)])
if s == "" {
return true
}
p.tok.Data = s
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
case DoctypeToken:
// Ignore the token.
return true
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Col:
p.addElement()
p.oe.pop()
p.acknowledgeSelfClosingTag()
return true
case a.Template:
return inHeadIM(p)
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Colgroup:
if p.oe.top().DataAtom == a.Colgroup {
p.oe.pop()
p.im = inTableIM
}
return true
case a.Col:
// Ignore the token.
return true
case a.Template:
return inHeadIM(p)
}
case ErrorToken:
return inBodyIM(p)
}
if p.oe.top().DataAtom != a.Colgroup {
return true
}
p.oe.pop()
p.im = inTableIM
return false
}
// Section 12.2.6.4.13.
func inTableBodyIM(p *parser) bool {
switch p.tok.Type {
case StartTagToken:
switch p.tok.DataAtom {
case a.Tr:
p.clearStackToContext(tableBodyScope)
p.addElement()
p.im = inRowIM
return true
case a.Td, a.Th:
p.parseImpliedToken(StartTagToken, a.Tr, a.Tr.String())
return false
case a.Caption, a.Col, a.Colgroup, a.Tbody, a.Tfoot, a.Thead:
if p.popUntil(tableScope, a.Tbody, a.Thead, a.Tfoot) {
p.im = inTableIM
return false
}
// Ignore the token.
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Tbody, a.Tfoot, a.Thead:
if p.elementInScope(tableScope, p.tok.DataAtom) {
p.clearStackToContext(tableBodyScope)
p.oe.pop()
p.im = inTableIM
}
return true
case a.Table:
if p.popUntil(tableScope, a.Tbody, a.Thead, a.Tfoot) {
p.im = inTableIM
return false
}
// Ignore the token.
return true
case a.Body, a.Caption, a.Col, a.Colgroup, a.Html, a.Td, a.Th, a.Tr:
// Ignore the token.
return true
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
}
return inTableIM(p)
}
// Section 12.2.6.4.14.
func inRowIM(p *parser) bool {
switch p.tok.Type {
case StartTagToken:
switch p.tok.DataAtom {
case a.Td, a.Th:
p.clearStackToContext(tableRowScope)
p.addElement()
p.afe = append(p.afe, &scopeMarker)
p.im = inCellIM
return true
case a.Caption, a.Col, a.Colgroup, a.Tbody, a.Tfoot, a.Thead, a.Tr:
if p.popUntil(tableScope, a.Tr) {
p.im = inTableBodyIM
return false
}
// Ignore the token.
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Tr:
if p.popUntil(tableScope, a.Tr) {
p.im = inTableBodyIM
return true
}
// Ignore the token.
return true
case a.Table:
if p.popUntil(tableScope, a.Tr) {
p.im = inTableBodyIM
return false
}
// Ignore the token.
return true
case a.Tbody, a.Tfoot, a.Thead:
if p.elementInScope(tableScope, p.tok.DataAtom) {
p.parseImpliedToken(EndTagToken, a.Tr, a.Tr.String())
return false
}
// Ignore the token.
return true
case a.Body, a.Caption, a.Col, a.Colgroup, a.Html, a.Td, a.Th:
// Ignore the token.
return true
}
}
return inTableIM(p)
}
// Section 12.2.6.4.15.
func inCellIM(p *parser) bool {
switch p.tok.Type {
case StartTagToken:
switch p.tok.DataAtom {
case a.Caption, a.Col, a.Colgroup, a.Tbody, a.Td, a.Tfoot, a.Th, a.Thead, a.Tr:
if p.popUntil(tableScope, a.Td, a.Th) {
// Close the cell and reprocess.
p.clearActiveFormattingElements()
p.im = inRowIM
return false
}
// Ignore the token.
return true
case a.Select:
p.reconstructActiveFormattingElements()
p.addElement()
p.framesetOK = false
p.im = inSelectInTableIM
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Td, a.Th:
if !p.popUntil(tableScope, p.tok.DataAtom) {
// Ignore the token.
return true
}
p.clearActiveFormattingElements()
p.im = inRowIM
return true
case a.Body, a.Caption, a.Col, a.Colgroup, a.Html:
// Ignore the token.
return true
case a.Table, a.Tbody, a.Tfoot, a.Thead, a.Tr:
if !p.elementInScope(tableScope, p.tok.DataAtom) {
// Ignore the token.
return true
}
// Close the cell and reprocess.
if p.popUntil(tableScope, a.Td, a.Th) {
p.clearActiveFormattingElements()
}
p.im = inRowIM
return false
}
}
return inBodyIM(p)
}
// Section 12.2.6.4.16.
func inSelectIM(p *parser) bool {
switch p.tok.Type {
case TextToken:
p.addText(strings.Replace(p.tok.Data, "\x00", "", -1))
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Option:
if p.top().DataAtom == a.Option {
p.oe.pop()
}
p.addElement()
case a.Optgroup:
if p.top().DataAtom == a.Option {
p.oe.pop()
}
if p.top().DataAtom == a.Optgroup {
p.oe.pop()
}
p.addElement()
case a.Select:
if !p.popUntil(selectScope, a.Select) {
// Ignore the token.
return true
}
p.resetInsertionMode()
case a.Input, a.Keygen, a.Textarea:
if p.elementInScope(selectScope, a.Select) {
p.parseImpliedToken(EndTagToken, a.Select, a.Select.String())
return false
}
// In order to properly ignore <textarea>, we need to change the tokenizer mode.
p.tokenizer.NextIsNotRawText()
// Ignore the token.
return true
case a.Script, a.Template:
return inHeadIM(p)
case a.Iframe, a.Noembed, a.Noframes, a.Noscript, a.Plaintext, a.Style, a.Title, a.Xmp:
// Don't let the tokenizer go into raw text mode when there are raw tags
// to be ignored. These tags should be ignored from the tokenizer
// properly.
p.tokenizer.NextIsNotRawText()
// Ignore the token.
return true
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Option:
if p.top().DataAtom == a.Option {
p.oe.pop()
}
case a.Optgroup:
i := len(p.oe) - 1
if p.oe[i].DataAtom == a.Option {
i--
}
if p.oe[i].DataAtom == a.Optgroup {
p.oe = p.oe[:i]
}
case a.Select:
if !p.popUntil(selectScope, a.Select) {
// Ignore the token.
return true
}
p.resetInsertionMode()
case a.Template:
return inHeadIM(p)
}
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
case DoctypeToken:
// Ignore the token.
return true
case ErrorToken:
return inBodyIM(p)
}
return true
}
// Section 12.2.6.4.17.
func inSelectInTableIM(p *parser) bool {
switch p.tok.Type {
case StartTagToken, EndTagToken:
switch p.tok.DataAtom {
case a.Caption, a.Table, a.Tbody, a.Tfoot, a.Thead, a.Tr, a.Td, a.Th:
if p.tok.Type == EndTagToken && !p.elementInScope(tableScope, p.tok.DataAtom) {
// Ignore the token.
return true
}
// This is like p.popUntil(selectScope, a.Select), but it also
// matches <math select>, not just <select>. Matching the MathML
// tag is arguably incorrect (conceptually), but it mimics what
// Chromium does.
for i := len(p.oe) - 1; i >= 0; i-- {
if n := p.oe[i]; n.DataAtom == a.Select {
p.oe = p.oe[:i]
break
}
}
p.resetInsertionMode()
return false
}
}
return inSelectIM(p)
}
// Section 12.2.6.4.18.
func inTemplateIM(p *parser) bool {
switch p.tok.Type {
case TextToken, CommentToken, DoctypeToken:
return inBodyIM(p)
case StartTagToken:
switch p.tok.DataAtom {
case a.Base, a.Basefont, a.Bgsound, a.Link, a.Meta, a.Noframes, a.Script, a.Style, a.Template, a.Title:
return inHeadIM(p)
case a.Caption, a.Colgroup, a.Tbody, a.Tfoot, a.Thead:
p.templateStack.pop()
p.templateStack = append(p.templateStack, inTableIM)
p.im = inTableIM
return false
case a.Col:
p.templateStack.pop()
p.templateStack = append(p.templateStack, inColumnGroupIM)
p.im = inColumnGroupIM
return false
case a.Tr:
p.templateStack.pop()
p.templateStack = append(p.templateStack, inTableBodyIM)
p.im = inTableBodyIM
return false
case a.Td, a.Th:
p.templateStack.pop()
p.templateStack = append(p.templateStack, inRowIM)
p.im = inRowIM
return false
default:
p.templateStack.pop()
p.templateStack = append(p.templateStack, inBodyIM)
p.im = inBodyIM
return false
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Template:
return inHeadIM(p)
default:
// Ignore the token.
return true
}
case ErrorToken:
if !p.oe.contains(a.Template) {
// Ignore the token.
return true
}
// TODO: remove this divergence from the HTML5 spec.
//
// See https://bugs.chromium.org/p/chromium/issues/detail?id=829668
p.generateImpliedEndTags()
for i := len(p.oe) - 1; i >= 0; i-- {
if n := p.oe[i]; n.Namespace == "" && n.DataAtom == a.Template {
p.oe = p.oe[:i]
break
}
}
p.clearActiveFormattingElements()
p.templateStack.pop()
p.resetInsertionMode()
return false
}
return false
}
// Section 12.2.6.4.19.
func afterBodyIM(p *parser) bool {
switch p.tok.Type {
case ErrorToken:
// Stop parsing.
return true
case TextToken:
s := strings.TrimLeft(p.tok.Data, whitespace)
if len(s) == 0 {
// It was all whitespace.
return inBodyIM(p)
}
case StartTagToken:
if p.tok.DataAtom == a.Html {
return inBodyIM(p)
}
case EndTagToken:
if p.tok.DataAtom == a.Html {
if !p.fragment {
p.im = afterAfterBodyIM
}
return true
}
case CommentToken:
// The comment is attached to the <html> element.
if len(p.oe) < 1 || p.oe[0].DataAtom != a.Html {
panic("html: bad parser state: <html> element not found, in the after-body insertion mode")
}
p.oe[0].AppendChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
}
p.im = inBodyIM
return false
}
// Section 12.2.6.4.20.
func inFramesetIM(p *parser) bool {
switch p.tok.Type {
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
case TextToken:
// Ignore all text but whitespace.
s := strings.Map(func(c rune) rune {
switch c {
case ' ', '\t', '\n', '\f', '\r':
return c
}
return -1
}, p.tok.Data)
if s != "" {
p.addText(s)
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Frameset:
p.addElement()
case a.Frame:
p.addElement()
p.oe.pop()
p.acknowledgeSelfClosingTag()
case a.Noframes:
return inHeadIM(p)
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Frameset:
if p.oe.top().DataAtom != a.Html {
p.oe.pop()
if p.oe.top().DataAtom != a.Frameset {
p.im = afterFramesetIM
return true
}
}
}
default:
// Ignore the token.
}
return true
}
// Section 12.2.6.4.21.
func afterFramesetIM(p *parser) bool {
switch p.tok.Type {
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
case TextToken:
// Ignore all text but whitespace.
s := strings.Map(func(c rune) rune {
switch c {
case ' ', '\t', '\n', '\f', '\r':
return c
}
return -1
}, p.tok.Data)
if s != "" {
p.addText(s)
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Noframes:
return inHeadIM(p)
}
case EndTagToken:
switch p.tok.DataAtom {
case a.Html:
p.im = afterAfterFramesetIM
return true
}
default:
// Ignore the token.
}
return true
}
// Section 12.2.6.4.22.
func afterAfterBodyIM(p *parser) bool {
switch p.tok.Type {
case ErrorToken:
// Stop parsing.
return true
case TextToken:
s := strings.TrimLeft(p.tok.Data, whitespace)
if len(s) == 0 {
// It was all whitespace.
return inBodyIM(p)
}
case StartTagToken:
if p.tok.DataAtom == a.Html {
return inBodyIM(p)
}
case CommentToken:
p.doc.AppendChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
return true
case DoctypeToken:
return inBodyIM(p)
}
p.im = inBodyIM
return false
}
// Section 12.2.6.4.23.
func afterAfterFramesetIM(p *parser) bool {
switch p.tok.Type {
case CommentToken:
p.doc.AppendChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
case TextToken:
// Ignore all text but whitespace.
s := strings.Map(func(c rune) rune {
switch c {
case ' ', '\t', '\n', '\f', '\r':
return c
}
return -1
}, p.tok.Data)
if s != "" {
p.tok.Data = s
return inBodyIM(p)
}
case StartTagToken:
switch p.tok.DataAtom {
case a.Html:
return inBodyIM(p)
case a.Noframes:
return inHeadIM(p)
}
case DoctypeToken:
return inBodyIM(p)
default:
// Ignore the token.
}
return true
}
func ignoreTheRemainingTokens(p *parser) bool {
return true
}
const whitespaceOrNUL = whitespace + "\x00"
// Section 12.2.6.5
func parseForeignContent(p *parser) bool {
switch p.tok.Type {
case TextToken:
if p.framesetOK {
p.framesetOK = strings.TrimLeft(p.tok.Data, whitespaceOrNUL) == ""
}
p.tok.Data = strings.Replace(p.tok.Data, "\x00", "\ufffd", -1)
p.addText(p.tok.Data)
case CommentToken:
p.addChild(&Node{
Type: CommentNode,
Data: p.tok.Data,
})
case StartTagToken:
if !p.fragment {
b := breakout[p.tok.Data]
if p.tok.DataAtom == a.Font {
loop:
for _, attr := range p.tok.Attr {
switch attr.Key {
case "color", "face", "size":
b = true
break loop
}
}
}
if b {
for i := len(p.oe) - 1; i >= 0; i-- {
n := p.oe[i]
if n.Namespace == "" || htmlIntegrationPoint(n) || mathMLTextIntegrationPoint(n) {
p.oe = p.oe[:i+1]
break
}
}
return false
}
}
current := p.adjustedCurrentNode()
switch current.Namespace {
case "math":
adjustAttributeNames(p.tok.Attr, mathMLAttributeAdjustments)
case "svg":
// Adjust SVG tag names. The tokenizer lower-cases tag names, but
// SVG wants e.g. "foreignObject" with a capital second "O".
if x := svgTagNameAdjustments[p.tok.Data]; x != "" {
p.tok.DataAtom = a.Lookup([]byte(x))
p.tok.Data = x
}
adjustAttributeNames(p.tok.Attr, svgAttributeAdjustments)
default:
panic("html: bad parser state: unexpected namespace")
}
adjustForeignAttributes(p.tok.Attr)
namespace := current.Namespace
p.addElement()
p.top().Namespace = namespace
if namespace != "" {
// Don't let the tokenizer go into raw text mode in foreign content
// (e.g. in an SVG <title> tag).
p.tokenizer.NextIsNotRawText()
}
if p.hasSelfClosingToken {
p.oe.pop()
p.acknowledgeSelfClosingTag()
}
case EndTagToken:
for i := len(p.oe) - 1; i >= 0; i-- {
if p.oe[i].Namespace == "" {
return p.im(p)
}
if strings.EqualFold(p.oe[i].Data, p.tok.Data) {
p.oe = p.oe[:i]
break
}
}
return true
default:
// Ignore the token.
}
return true
}
// Section 12.2.4.2.
func (p *parser) adjustedCurrentNode() *Node {
if len(p.oe) == 1 && p.fragment && p.context != nil {
return p.context
}
return p.oe.top()
}
// Section 12.2.6.
func (p *parser) inForeignContent() bool {
if len(p.oe) == 0 {
return false
}
n := p.adjustedCurrentNode()
if n.Namespace == "" {
return false
}
if mathMLTextIntegrationPoint(n) {
if p.tok.Type == StartTagToken && p.tok.DataAtom != a.Mglyph && p.tok.DataAtom != a.Malignmark {
return false
}
if p.tok.Type == TextToken {
return false
}
}
if n.Namespace == "math" && n.DataAtom == a.AnnotationXml && p.tok.Type == StartTagToken && p.tok.DataAtom == a.Svg {
return false
}
if htmlIntegrationPoint(n) && (p.tok.Type == StartTagToken || p.tok.Type == TextToken) {
return false
}
if p.tok.Type == ErrorToken {
return false
}
return true
}
// parseImpliedToken parses a token as though it had appeared in the parser's
// input.
func (p *parser) parseImpliedToken(t TokenType, dataAtom a.Atom, data string) {
realToken, selfClosing := p.tok, p.hasSelfClosingToken
p.tok = Token{
Type: t,
DataAtom: dataAtom,
Data: data,
}
p.hasSelfClosingToken = false
p.parseCurrentToken()
p.tok, p.hasSelfClosingToken = realToken, selfClosing
}
// parseCurrentToken runs the current token through the parsing routines
// until it is consumed.
func (p *parser) parseCurrentToken() {
if p.tok.Type == SelfClosingTagToken {
p.hasSelfClosingToken = true
p.tok.Type = StartTagToken
}
consumed := false
for !consumed {
if p.inForeignContent() {
consumed = parseForeignContent(p)
} else {
consumed = p.im(p)
}
}
if p.hasSelfClosingToken {
// This is a parse error, but ignore it.
p.hasSelfClosingToken = false
}
}
func (p *parser) parse() error {
// Iterate until EOF. Any other error will cause an early return.
var err error
for err != io.EOF {
// CDATA sections are allowed only in foreign content.
n := p.oe.top()
p.tokenizer.AllowCDATA(n != nil && n.Namespace != "")
// Read and parse the next token.
p.tokenizer.Next()
p.tok = p.tokenizer.Token()
if p.tok.Type == ErrorToken {
err = p.tokenizer.Err()
if err != nil && err != io.EOF {
return err
}
}
p.parseCurrentToken()
}
return nil
}
// Parse returns the parse tree for the HTML from the given Reader.
//
// It implements the HTML5 parsing algorithm
// (https://html.spec.whatwg.org/multipage/syntax.html#tree-construction),
// which is very complicated. The resultant tree can contain implicitly created
// nodes that have no explicit <tag> listed in r's data, and nodes' parents can
// differ from the nesting implied by a naive processing of start and end
// <tag>s. Conversely, explicit <tag>s in r's data can be silently dropped,
// with no corresponding node in the resulting tree.
//
// The input is assumed to be UTF-8 encoded.
func Parse(r io.Reader) (*Node, error) {
return ParseWithOptions(r)
}
// ParseFragment parses a fragment of HTML and returns the nodes that were
// found. If the fragment is the InnerHTML for an existing element, pass that
// element in context.
//
// It has the same intricacies as Parse.
func ParseFragment(r io.Reader, context *Node) ([]*Node, error) {
return ParseFragmentWithOptions(r, context)
}
// ParseOption configures a parser.
type ParseOption func(p *parser)
// ParseOptionEnableScripting configures the scripting flag.
// https://html.spec.whatwg.org/multipage/webappapis.html#enabling-and-disabling-scripting
//
// By default, scripting is enabled.
func ParseOptionEnableScripting(enable bool) ParseOption {
return func(p *parser) {
p.scripting = enable
}
}
// ParseWithOptions is like Parse, with options.
func ParseWithOptions(r io.Reader, opts ...ParseOption) (*Node, error) {
p := &parser{
tokenizer: NewTokenizer(r),
doc: &Node{
Type: DocumentNode,
},
scripting: true,
framesetOK: true,
im: initialIM,
}
for _, f := range opts {
f(p)
}
if err := p.parse(); err != nil {
return nil, err
}
return p.doc, nil
}
// ParseFragmentWithOptions is like ParseFragment, with options.
func ParseFragmentWithOptions(r io.Reader, context *Node, opts ...ParseOption) ([]*Node, error) {
contextTag := ""
if context != nil {
if context.Type != ElementNode {
return nil, errors.New("html: ParseFragment of non-element Node")
}
// The next check isn't just context.DataAtom.String() == context.Data because
// it is valid to pass an element whose tag isn't a known atom. For example,
// DataAtom == 0 and Data = "tagfromthefuture" is perfectly consistent.
if context.DataAtom != a.Lookup([]byte(context.Data)) {
return nil, fmt.Errorf("html: inconsistent Node: DataAtom=%q, Data=%q", context.DataAtom, context.Data)
}
contextTag = context.DataAtom.String()
}
p := &parser{
doc: &Node{
Type: DocumentNode,
},
scripting: true,
fragment: true,
context: context,
}
if context != nil && context.Namespace != "" {
p.tokenizer = NewTokenizer(r)
} else {
p.tokenizer = NewTokenizerFragment(r, contextTag)
}
for _, f := range opts {
f(p)
}
root := &Node{
Type: ElementNode,
DataAtom: a.Html,
Data: a.Html.String(),
}
p.doc.AppendChild(root)
p.oe = nodeStack{root}
if context != nil && context.DataAtom == a.Template {
p.templateStack = append(p.templateStack, inTemplateIM)
}
p.resetInsertionMode()
for n := context; n != nil; n = n.Parent {
if n.Type == ElementNode && n.DataAtom == a.Form {
p.form = n
break
}
}
if err := p.parse(); err != nil {
return nil, err
}
parent := p.doc
if context != nil {
parent = root
}
var result []*Node
for c := parent.FirstChild; c != nil; {
next := c.NextSibling
parent.RemoveChild(c)
result = append(result, c)
c = next
}
return result, nil
}