Fossil SCM

When doing "fossil export" make sure the output is in strict topological orders, since Git hates timewarps.

drh 2018-05-04 15:39 trunk
Commit c0a3e9ff6fbe3b48bf3c3a31173b7f168758d6e6591eecdf31c267dbce907c95
Parent 8d1cb59fe074bb0…
1 file changed +103 -4
~ src/export.c
M src/export.c
+103 -4
--- src/export.c
+++ src/export.c
@@ -600,17 +600,20 @@
600600
 db_finalize(&q2);
601601
 db_finalize(&q3);
602602
603603
 /* Output the commit records.
604604
 */
605
+ topological_sort_checkins(0);
605606
 db_prepare(&q,
606607
 "SELECT strftime('%%s',mtime), objid, coalesce(ecomment,comment),"
607608
 " coalesce(euser,user),"
608609
 " (SELECT value FROM tagxref WHERE rid=objid AND tagid=%d)"
609
- " FROM event"
610
- " WHERE type='ci' AND NOT EXISTS (SELECT 1 FROM oldcommit WHERE objid=rid)"
611
- " ORDER BY mtime ASC",
610
+ " FROM toponode, event"
611
+ " WHERE toponode.tid=event.objid"
612
+ " AND event.type='ci'"
613
+ " AND NOT EXISTS (SELECT 1 FROM oldcommit WHERE toponode.tid=rid)"
614
+ " ORDER BY toponode.tseq ASC",
612615
 TAG_BRANCH
613616
 );
614617
 db_prepare(&q2, "INSERT INTO oldcommit VALUES (:rid)");
615618
 while( db_step(&q)==SQLITE_ROW ){
616619
 Stmt q4;
@@ -623,11 +626,13 @@
623626
624627
 bag_insert(&vers, ckinId);
625628
 db_bind_int(&q2, ":rid", ckinId);
626629
 db_step(&q2);
627630
 db_reset(&q2);
628
- if( zBranch==0 || fossil_strcmp(zBranch, "trunk")==0 ) zBranch = gexport.zTrunkName;
631
+ if( zBranch==0 || fossil_strcmp(zBranch, "trunk")==0 ){
632
+ zBranch = gexport.zTrunkName;
633
+ }
629634
 zMark = mark_name_from_rid(ckinId, &unused_mark);
630635
 printf("commit refs/heads/");
631636
 print_ref(zBranch);
632637
 printf("\nmark %s\n", zMark);
633638
 free(zMark);
@@ -737,5 +742,99 @@
737742
 }
738743
 }
739744
 bag_clear(&blobs);
740745
 bag_clear(&vers);
741746
 }
747
+
748
+/*
749
+** Construct the temporary table toposort as follows:
750
+**
751
+** CREATE TEMP TABLE toponode(
752
+** tid INTEGER PRIMARY KEY, -- Check-in id
753
+** tseq INT -- integer total order on check-ins.
754
+** );
755
+**
756
+** This table contains all check-ins of the repository in topological
757
+** order. "Topological order" means that every parent check-in comes
758
+** before all of its children. Topological order is *almost* the same
759
+** thing as "ORDER BY event.mtime". Differences only arrise when there
760
+** are timewarps. In as much as Git hates timewarps, we have to compute
761
+** a correct topological order when doing an export.
762
+**
763
+** Since mtime is a usually already nearly in topological order, the
764
+** algorithm is to start with mtime, then make adjustments as necessary
765
+** for timewarps. This is not a great algorithm for the general case,
766
+** but it is very fast for the overwhelmingly common case where there
767
+** are few timewarps.
768
+*/
769
+int topological_sort_checkins(int bVerbose){
770
+ int nChange = 0;
771
+ Stmt q1;
772
+ Stmt chng;
773
+ db_multi_exec(
774
+ "CREATE TEMP TABLE toponode(\n"
775
+ " tid INTEGER PRIMARY KEY,\n"
776
+ " tseq INT\n"
777
+ ");\n"
778
+ "INSERT INTO toponode(tid,tseq) "
779
+ " SELECT objid, CAST(mtime*8640000 AS int) FROM event WHERE type='ci';\n"
780
+ "CREATE TEMP TABLE topolink(\n"
781
+ " tparent INT,\n"
782
+ " tchild INT,\n"
783
+ " PRIMARY KEY(tparent,tchild)\n"
784
+ ") WITHOUT ROWID;"
785
+ "INSERT INTO topolink(tparent,tchild)"
786
+ " SELECT pid, cid FROM plink;\n"
787
+ "CREATE INDEX topolink_child ON topolink(tchild);\n"
788
+ );
789
+
790
+ /* Find a timewarp instance */
791
+ db_prepare(&q1,
792
+ "SELECT P.tid, P.tseq, C.tid, C.tseq\n"
793
+ " FROM toponode P, toponode C, topolink X\n"
794
+ " WHERE X.tparent=P.tid\n"
795
+ " AND X.tchild=C.tid\n"
796
+ " AND P.tseq>=C.tseq;"
797
+ );
798
+
799
+ /* Update the timestamp on :tid to have value :tseq */
800
+ db_prepare(&chng,
801
+ "UPDATE toponode SET tseq=:tseq WHERE tid=:tid"
802
+ );
803
+
804
+ while( db_step(&q1)==SQLITE_ROW ){
805
+ int iParent = db_column_int(&q1, 0);
806
+ i64 iParentTime = db_column_int64(&q1, 1);
807
+ int iChild = db_column_int(&q1, 2);
808
+ i64 iChildTime = db_column_int64(&q1, 3);
809
+ nChange++;
810
+ if( nChange>10000 ){
811
+ fossil_fatal("failed to fix all timewarps after 100000 attempts");
812
+ }
813
+ db_reset(&q1);
814
+ db_bind_int64(&chng, ":tid", iChild);
815
+ db_bind_int64(&chng, ":tseq", iParentTime+1);
816
+ db_step(&chng);
817
+ db_reset(&chng);
818
+ if( bVerbose ){
819
+ fossil_print("moving %d from %lld to %lld\n",
820
+ iChild, iChildTime, iParentTime+1);
821
+ }
822
+ }
823
+
824
+ db_finalize(&q1);
825
+ db_finalize(&chng);
826
+ return nChange;
827
+}
828
+
829
+/*
830
+** COMMAND: test-topological-sort
831
+**
832
+** Invoke the topological_sort_checkins() interface for testing
833
+** purposes.
834
+*/
835
+void test_topological_sort(void){
836
+ int n;
837
+ db_find_and_open_repository(0, 0);
838
+ n = topological_sort_checkins(1);
839
+ fossil_print("%d reorderings required\n", n);
840
+}
742841
--- src/export.c
+++ src/export.c
@@ -600,17 +600,20 @@
600 db_finalize(&q2);
601 db_finalize(&q3);
602
603 /* Output the commit records.
604 */
 
605 db_prepare(&q,
606 "SELECT strftime('%%s',mtime), objid, coalesce(ecomment,comment),"
607 " coalesce(euser,user),"
608 " (SELECT value FROM tagxref WHERE rid=objid AND tagid=%d)"
609 " FROM event"
610 " WHERE type='ci' AND NOT EXISTS (SELECT 1 FROM oldcommit WHERE objid=rid)"
611 " ORDER BY mtime ASC",
 
 
612 TAG_BRANCH
613 );
614 db_prepare(&q2, "INSERT INTO oldcommit VALUES (:rid)");
615 while( db_step(&q)==SQLITE_ROW ){
616 Stmt q4;
@@ -623,11 +626,13 @@
623
624 bag_insert(&vers, ckinId);
625 db_bind_int(&q2, ":rid", ckinId);
626 db_step(&q2);
627 db_reset(&q2);
628 if( zBranch==0 || fossil_strcmp(zBranch, "trunk")==0 ) zBranch = gexport.zTrunkName;
 
 
629 zMark = mark_name_from_rid(ckinId, &unused_mark);
630 printf("commit refs/heads/");
631 print_ref(zBranch);
632 printf("\nmark %s\n", zMark);
633 free(zMark);
@@ -737,5 +742,99 @@
737 }
738 }
739 bag_clear(&blobs);
740 bag_clear(&vers);
741 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
742
--- src/export.c
+++ src/export.c
@@ -600,17 +600,20 @@
600 db_finalize(&q2);
601 db_finalize(&q3);
602
603 /* Output the commit records.
604 */
605 topological_sort_checkins(0);
606 db_prepare(&q,
607 "SELECT strftime('%%s',mtime), objid, coalesce(ecomment,comment),"
608 " coalesce(euser,user),"
609 " (SELECT value FROM tagxref WHERE rid=objid AND tagid=%d)"
610 " FROM toponode, event"
611 " WHERE toponode.tid=event.objid"
612 " AND event.type='ci'"
613 " AND NOT EXISTS (SELECT 1 FROM oldcommit WHERE toponode.tid=rid)"
614 " ORDER BY toponode.tseq ASC",
615 TAG_BRANCH
616 );
617 db_prepare(&q2, "INSERT INTO oldcommit VALUES (:rid)");
618 while( db_step(&q)==SQLITE_ROW ){
619 Stmt q4;
@@ -623,11 +626,13 @@
626
627 bag_insert(&vers, ckinId);
628 db_bind_int(&q2, ":rid", ckinId);
629 db_step(&q2);
630 db_reset(&q2);
631 if( zBranch==0 || fossil_strcmp(zBranch, "trunk")==0 ){
632 zBranch = gexport.zTrunkName;
633 }
634 zMark = mark_name_from_rid(ckinId, &unused_mark);
635 printf("commit refs/heads/");
636 print_ref(zBranch);
637 printf("\nmark %s\n", zMark);
638 free(zMark);
@@ -737,5 +742,99 @@
742 }
743 }
744 bag_clear(&blobs);
745 bag_clear(&vers);
746 }
747
748 /*
749 ** Construct the temporary table toposort as follows:
750 **
751 ** CREATE TEMP TABLE toponode(
752 ** tid INTEGER PRIMARY KEY, -- Check-in id
753 ** tseq INT -- integer total order on check-ins.
754 ** );
755 **
756 ** This table contains all check-ins of the repository in topological
757 ** order. "Topological order" means that every parent check-in comes
758 ** before all of its children. Topological order is *almost* the same
759 ** thing as "ORDER BY event.mtime". Differences only arrise when there
760 ** are timewarps. In as much as Git hates timewarps, we have to compute
761 ** a correct topological order when doing an export.
762 **
763 ** Since mtime is a usually already nearly in topological order, the
764 ** algorithm is to start with mtime, then make adjustments as necessary
765 ** for timewarps. This is not a great algorithm for the general case,
766 ** but it is very fast for the overwhelmingly common case where there
767 ** are few timewarps.
768 */
769 int topological_sort_checkins(int bVerbose){
770 int nChange = 0;
771 Stmt q1;
772 Stmt chng;
773 db_multi_exec(
774 "CREATE TEMP TABLE toponode(\n"
775 " tid INTEGER PRIMARY KEY,\n"
776 " tseq INT\n"
777 ");\n"
778 "INSERT INTO toponode(tid,tseq) "
779 " SELECT objid, CAST(mtime*8640000 AS int) FROM event WHERE type='ci';\n"
780 "CREATE TEMP TABLE topolink(\n"
781 " tparent INT,\n"
782 " tchild INT,\n"
783 " PRIMARY KEY(tparent,tchild)\n"
784 ") WITHOUT ROWID;"
785 "INSERT INTO topolink(tparent,tchild)"
786 " SELECT pid, cid FROM plink;\n"
787 "CREATE INDEX topolink_child ON topolink(tchild);\n"
788 );
789
790 /* Find a timewarp instance */
791 db_prepare(&q1,
792 "SELECT P.tid, P.tseq, C.tid, C.tseq\n"
793 " FROM toponode P, toponode C, topolink X\n"
794 " WHERE X.tparent=P.tid\n"
795 " AND X.tchild=C.tid\n"
796 " AND P.tseq>=C.tseq;"
797 );
798
799 /* Update the timestamp on :tid to have value :tseq */
800 db_prepare(&chng,
801 "UPDATE toponode SET tseq=:tseq WHERE tid=:tid"
802 );
803
804 while( db_step(&q1)==SQLITE_ROW ){
805 int iParent = db_column_int(&q1, 0);
806 i64 iParentTime = db_column_int64(&q1, 1);
807 int iChild = db_column_int(&q1, 2);
808 i64 iChildTime = db_column_int64(&q1, 3);
809 nChange++;
810 if( nChange>10000 ){
811 fossil_fatal("failed to fix all timewarps after 100000 attempts");
812 }
813 db_reset(&q1);
814 db_bind_int64(&chng, ":tid", iChild);
815 db_bind_int64(&chng, ":tseq", iParentTime+1);
816 db_step(&chng);
817 db_reset(&chng);
818 if( bVerbose ){
819 fossil_print("moving %d from %lld to %lld\n",
820 iChild, iChildTime, iParentTime+1);
821 }
822 }
823
824 db_finalize(&q1);
825 db_finalize(&chng);
826 return nChange;
827 }
828
829 /*
830 ** COMMAND: test-topological-sort
831 **
832 ** Invoke the topological_sort_checkins() interface for testing
833 ** purposes.
834 */
835 void test_topological_sort(void){
836 int n;
837 db_find_and_open_repository(0, 0);
838 n = topological_sort_checkins(1);
839 fossil_print("%d reorderings required\n", n);
840 }
841

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button